Font size
WorksheetsCSE214 Final Review
Total questions: 44
Worksheet time: 57mins
Order from least to greatest Time complexity
O(3), O(log n), O(n log n), O(10n), O(n^2), O(n^10), O(2^n), O(n!), O(n^n)
O(3), O(log n), O(10n), O(n^2), O(n log n), O(n^10), O(2^n), O(n!), O(n^n)
O(3), O(log n), O(10n), O(n log n), O(n^2), O(2^n), O(n^10), O(n^n), O(n!)
O(3), O(log n), O(10n), O(n log n), O(n^2), O(n^10), O(2^n), O(n!), O(n^n)
Evaluate the time complexity
O(N)
O(N^2)
O(N log N)
O(1)
For N=20, what will be printed?
(a)
Consider the following method, which is supposed to remove all nodes of a linked list containing a value and return the new head. Select the 2 test cases where the removeVal(head,1); performs as expected
1 -> 2 -> 3 -> 4
2 -> 1 -> 1 -> 2
2 -> 2 -> 2 -> 2
2 -> 1 -> 2 -> 2
What are the benefits of using a DOUBLY linked list rather than a SINGLY
(You have access to head and tail)
Remove Head becomes faster
Remove Tail becomes faster
Insert Tail becomes faster
Doubly uses less space than singly
For a stack implemented using a singly linked list with top = head and no tail reference, what are the time complexities?
PUSH: O(1)
POP: O(1)
PUSH: O(1)
POP: O(N)
PUSH: O(N)
POP: O(1)
PUSH: O(N)
POP: O(N)
For a stack implemented using a singly linked list with bottom = head and top = tail, what are the time complexities?
PUSH: O(1)
POP: O(1)
PUSH: O(1)
POP: O(N)
PUSH: O(N)
POP: O(1)
PUSH: O(N)
POP: O(N)
Evaluate the prefix expression of integers:
- / + 5 * 4 3 2 4
(a)
Evaluate the postfix expression of integers:
5 4 * 2 1 - - 3 /
(a)
Convert the infix to postfix:
A + (B + C / D) * E
A B C + D / + E * +
A B C D / + E + *
A B + C + D / E *
A B C D / + E * +
Convert the postfix to infix:
A B + C / D E * -
A + B / C - D * E
(A + B) / C - D * E
(A + B) / C * D - E
A + B / C * D - E
A normal queue, implemented using a circular array, gets FULL when?
rear == CAPACITY
rear == CAPACITY – 1
(rear + 1) % CAPACITY == front
None of Above
A normal queue, implemented using a circular array, is empty when?
front == −1 && rear == −1
rear == front
front = 0 && rear = 0
None of above
Which of the following traversals prints the elements out in ascending order?
Preorder Traversal
Inorder Traversal
Postorder Traversal
Breadth-first search
What does the following method count?
The number of internal nodes
The number of leaves
The number of nodes with a null reference
The number of nodes without a null reference
What is the worst case time complexity of Quick sort, and why?
O(n^2) because the pivot always ends up being the maximum or minimum element in every partition.
O(n^2) because it effectively acts as bubble sort when the list is sorted in ascending or descending order.
O(n log n) because the partitioning step efficiently divides the array into smaller segments, reducing the overall time complexity.
O(n log n) because the algorithm recursively divides the array and combines the results using a divide-and-conquer strategy.
Which of the following sorts does not have an O(N) best case?
Quick sort
Bubble sort
Insertion sort
Counting sort
Which sequence of numbers creates this BST?
7, 26, 1, 5, 29, 31, 22, 9, 11
7, 26, 5, 1, 31, 29, 22, 11, 9
7, 1, 5, 26, 31, 29, 22, 9, 11
7, 26, 1, 5, 31, 29, 9, 22, 11
Postorder:
1, 5, 7, 9, 11, 22, 26, 29, 31
7, 1, 5, 26, 22, 9, 11, 31, 29
5, 1, 11, 9, 22, 29, 31, 26, 7
7, 1, 26, 5, 22, 31, 9, 29, 11
Inorder
(a)
A binary tree has 1000 nodes. How many null references does it have?
(a)
A full tree has a depth of 4. How many nodes does it have?
(a)
All (a) trees are (b), and all (b) trees are (c).
What is a, b, and c?
Balanced, complete, full
Full, balanced, complete
Balanced, full, complete
Full, complete, balanced
Full?
Complete?
Balanced?
Heap?
BST?
Full NO
Complete NO
Balanced YES
Heap NO
BST YES
Full NO
Complete NO
Balanced YES
Heap NO
BST NO
Full NO
Complete NO
Balanced NO
Heap NO
BST NO
Full NO
Complete NO
Balanced NO
Heap NO
BST YES
Remove node 22 from BST
IF a 2-3-4 Tree has a height of 2, What is the maximum number of ELEMENTS it can contain?
63
48
51
64
Assuming Root is at index 0 and node is at index i.
What are the correct formulas for accessing members of a heap?
Parent: i/2
Left Child: 2i+1
Right Child: 2i+2
Parent: (i-1)/2
Left Child: 2i-1
Right Child: 2i-2
Parent: (i-1)/2
Left Child: 2i
Right Child: 2i+1
Parent: (i-1)/2
Left Child: 2i+1
Right Child: 2i+2
Heap sort's time complexity is O(N log N) because...
Heapify: O(N)
Remove all elements from heap: O(N log N)
Heapify: O(N log N)
Remove all elements from heap: O(N)
Heapify: O(N log N)
Remove all elements from heap: O(N log N)
Heapify: O(N)
Remove all elements from heap: O(log N)
Insert 55 into the following heap: [100, 19, 36, 17, 3, 25]
Which array index will it be in?
(a)
Time complexity to find the minimum value in a max-heap is (and why)
O(log n) - Need to search every leaf
O(n log n) - Need to remove every element until finding that value
O(n) - Need to search every element in the heap
O(n) - Need to search every leaf in the heap
Select all of the following that is sufficient for reconstructing an unique binary tree
Preorder and inorder
Inorder and postorder
Preorder and postorder
What is the minimum number of nodes that a red black tree with depth 2 can have?
(a)
Create the Binary Tree:
Inorder: DBEAFC
Preorder: ABDECF
Perform first outer loop iteration of selection sort on
25 20 30 15 45 50 10 13
(a)
Perform first outer loop iteration of insertion sort on
25 20 30 15 45 50 10 13
(a)
Perform first outer loop iteration of bubble sort on
25 20 30 15 45 50 10 13
Please answer in the same format as the question
(a)
Given: 25, 20, 30, 15, 45, 50, 10, 13
Perform the first partition of Quick Sort
Assume first element is choosen as the pivot
10, 13, 15, 20, 25, 30, 45, 50
20, 13, 15, 10, 25, 50, 45, 30
13, 20, 10 15, 25, 50, 45, 30
20, 30, 15, 25, 45, 50, 10, 13
Which of the following are NOT a property of red-black trees?
All root to null paths must have the same number of black nodes
It is a binary search tree
The left and right subtree depths cannot differ by more than 1
Red nodes cannot have red children
Perform these Operations on this original heap:
Remove()
Add(14)
Add(26)
Now, What Data is stored at the parent of index 4 of the array representation?
(a)
Which Sort does NOT sort in place?
Heap Sort
Selection Sort
Bubble Sort
Counting Sort
Sequential and binary search time complexities?
Sequential: O(log N)
Binary: O(N)
Sequential: O(N)
Binary: O(N^2)
Sequential: O(log N)
Binary: O(log N)
Sequential: O(N)
Binary: O(log N)
Which search is better if the array is unsorted
Sequential
Binary
Which search is better when the target is the first element
Sequential
Binary
Which search is better for very large lists
Sequential
Binary
