1Quicksort Best and Average Runtime Complexity
O(NlogN)
2What is Data Structures?
Organizing, Storing, and Performing Operations on Data
3Stack: Push and Pop
Push / append() : Add the integer to the top
Pop / pop(: Remove from the top
Read the table number from top to bottom
4s.push(5)
s.push(1)
s.push(4)
s.pop()
s.push(2)
s.pop()
s.push(8)
s.push(7)
s.pop()
s.push(3)
3
8
1
5
5Python Reversing The String Code:
def reverse_string(s):
reversed_string = ""
stack = [] # Initialize an empty stack
# 1. Push each character onto the stack
for char in s:
stack.append(char)
# 2. Pop from the stack and build reversed string
while len(stack) != 0:
reversed_string += stack.pop()
return reversed_string
string_to_reverse = "hello world"
reversed_string = reverse_string(string_to_reverse)
print(reversed_string)
6In an AVL tree of height 6, what is the maximum nodes?
127
7In an AVL tree of height 6, what is the minimum nodes?
33
8Binary Tree Traversals: Pre-Order
Root -> Left -> Right
9Binary Tree Traversals: In-Order
Left -> Root -> Right
10Binary Tree Traversals: Post-Order
Left -> Right -> Root
11What is a record?
Data Structures that stores subitems, fields, with a name associated with each subitem
12What is an array list []
Mutable or Changeable Data structure that stores an ordered list of items, where each item is directly accessible by a positional index
13What is a linked list?
data structure that stores an ordered list of items in nodes, where each node stores data and has a pointer to the next node.
14what is a hash table?
data structure that stores unordered items by mapping (or hashing) each item to a location in an array.
15A linked list stores items in an unspecified order.
16A node in binary tree can have zero, one, or two children.
17A list node's data can store a record with multiple subitems.
18Items stored in an array can be accessed using a positional index.
19What is an algorithm?
Describes a sequence of steps to solve a computational problem or perform a calculation
20What is computational problem?
Specifies an input, a question about the input that can be answered using a computer, and the desired output.
21Do two student essays share a common phrase consisting of a sequence of more than 100 letters?
Longest Common Substring
22A remove operation for a list ADT removes the specified item. Given a list with contents: 2, 20, 30, what is the list after the following operation?
Remove(list, item 2)
20, 30
23Priority Queue
Items are ordered based on items' priority. Duplicate items are allowed.
25F(N) = N^1/2 + LogN
O(N^1/2)
26F(N) = (N N N * N)^3
O(N)^12