NEW
Font size
WorksheetsFinal Exam - Algorithms and Complexity 1
Total questions: 60
Worksheet time: 30mins
What is the first step of Merge Sort?
Merging pairs immediately
Splitting the list into two halves
Sorting each element individually
Removing duplicates
Using Merge sort, After the first split, the list [38,12,27,3,9,82,10,5] becomes:
[38,12,27] | [3,9,82,10,5]
[38,12,27,3] | [9,82,10,5]
[38,12] | [27,3] | [9,82] | [10,5]
[3,5,9,10] | [12,27,38,82]
Unsorted [38,12,27,3,9,82,10,5] using Merge Sort,
What is the result of merging [38] and [12]?
[38, 12]
[12, 38]
[50]
[38]
Unsorted [38,12,27,3,9,82,10,5] use the Merge Sort,
Which pair results in [3, 27] after merging?
[12] and [38]
[27] and [3]
[5] and [10]
[9] and [82]
Unsorted [38,12,27,3,9,82,10,5] using the Merge Sort,
What is the result of merging [12, 38] and [3, 27]?
[3, 12, 27, 38]
[12, 27, 3, 38]
[38, 12, 3, 27]
[3, 27, 12, 38]
Unsorted [38,12,27,3,9,82,10,5] using the Merge Sort,
What is the result of merging [10] and [5]?
[10, 5]
[5, 10]
[15]
[5]
Unsorted [38,12,27,3,9,82,10,5] using the Merge Sort,
What is the result of merging [9, 82] and [5, 10]?
[82, 9, 10, 5]
[9, 5, 10, 82]
[5, 9, 10, 82]
[5, 10, 9, 82]
Merge Sort is an example of which algorithmic technique?
Greedy Algorithm
Dynamic Programming
Divide and Conquer
Backtracking
Unsorted [38,12,27,3,9,82,10,5] using the Merge Sort, What is the correct final sorted output?
[3, 5, 9, 10, 12, 27, 38, 82]
[82, 38, 27, 12, 10, 9, 5, 3]
[12, 27, 38, 3, 5, 9, 10, 82]
[3, 9, 5, 10, 12, 27, 38, 82]
Unsorted [38,12,27,3,9,82,10,5] using the Merge Sort, Why does Merge Sort guarantee a correct sorted result?
Because it guesses the correct order
Because it sorts using random swaps
Because merging always produces sorted lists
Because it sorts only the largest elements
What is the main idea of Quick Sort?
Repeatedly merging sorted lists
Repeatedly splitting into equal halves
Partitioning the array around a pivot
Using frequency counts
Unsorted List: [38, 12, 27, 3, 9, 82, 10, 5] using Quick Sort,
which element was chosen as the first pivot?
38
3
5
27
Unsorted List: [38, 12, 27, 3, 9, 82, 10, 5] using Quick Sort,
After the first partition using pivot 5, which number ends up immediately to the left of the pivot?
9
3
12
27
Unsorted List: [38, 12, 27, 3, 9, 82, 10, 5] using Quick Sort,
After placing pivot 5 in its correct position, what does the array look like?
[5, 3, 27, 38, 9, 82, 10, 12]
[3, 27, 5, 38, 9, 82, 10, 12]
[3, 5, 27, 38, 9, 82, 10, 12]
[3, 27, 38, 5, 9, 10, 82, 12]
Unsorted List: [38, 12, 27, 3, 9, 82, 10, 5] using Quick Sort,
Which element served as the pivot for the sub-array [27, 38, 9, 82, 10, 12]?
10
12
27
82
Unsorted List: [38, 12, 27, 3, 9, 82, 10, 5] using Quick Sort,
What is the result after partitioning with pivot 12?
[9, 10, 12, 82, 38, 27]
[10, 9, 12, 38, 82, 27]
[12, 9, 10, 27, 38, 82]
[3, 5, 12, 10, 9, 27]
Unsorted List: [38, 12, 27, 3, 9, 82, 10, 5] using Quick Sort,
Which sub-array is already sorted after processing pivot 10?
[38, 27]
[9, 10]
[82, 38, 27]
[3]
Unsorted List: [38, 12, 27, 3, 9, 82, 10, 5] using Quick Sort,
For the sub-array [82, 38, 27], which element is used as the pivot?
27
82
38
5
Unsorted List: [38, 12, 27, 3, 9, 82, 10, 5] using Quick Sort,
The final sorted array after applying Quick Sort is:
[3, 5, 9, 10, 12, 27, 38, 82]
[82, 38, 27, 12, 10, 9, 5, 3]
[3, 9, 5, 12, 10, 27, 38, 82]
[3, 5, 9, 10, 12, 27, 82, 38]
What causes Quick Sort to fail worst-case performance?
Choosing a pivot that is always the smallest or largest
Using too many loops
Sorting only half the array
Removing duplicates
Before using Binary Search, what must be done to the array?
Remove duplicates
Sort it in ascending order
Reverse the array
Replace all values with indexes
Using Binary Search, What is the sorted version of the array [38,12,27,3,9,82,10,5]?
[3, 5, 9, 10, 12, 27, 38, 82]
[82, 38, 27, 12, 10, 9, 5, 3]
[3, 9, 5, 12, 10, 27, 38, 82]
[10, 9, 12, 27, 38, 82, 3, 5]
What is the formula for finding the mid index?
mid = (low + high)
mid = low - high / 2
mid = low + (high - low) // 2
mid = (low - high) // 3
in Binary Search - unsorted [38,12,27,3,9,82,10,5], When searching for 10, what value is found at mid on the first step?
5
3
10
12
What is returned when the target is found during Binary Search?
The array length
The index of the target
The mid value multiplied by 2
The sorted array
In Binary Search, When searching for 7, what happens when mid points to value 10?
Set low = mid + 1
Set high = mid − 1
Return the index
Swap low and high
In which condition does Binary Search stop and declare “not found”?
When low == mid
When mid == high
When low > high
When high > low
What is the time complexity of Binary Search?
O(n²)
O(n)
O(log n)
O(1)
In Binary Search unsorted [38, 12, 27, 3, 9, 82, 10, 5], When searching for 7, what value does mid point to in the second step?
3
5
9
10
Binary Search is best described as:
A linear scanning algorithm
A divide-and-conquer search algorithm
A greedy algorithm
A recursive-only algorithm
A greedy algorithm always chooses the option that is:
Globally optimal
Locally optimal
Randomly chosen
Computed through recursion
Greedy algorithms work only when the problem has:
NP-hard structure
Optimal substructure and greedy-choice property
Dynamic programming property
Backtracking behavior
Most greedy algorithms run in:
O(n²)
O(n³)
O(n log n) or better
O(1)
Which of the following is NOT a greedy algorithm.
Activity Selection
Huffman Coding
Minimum Spanning Tree
QuickSort
The greedy-choice property means:
All choices must be evaluated
The local choice leads to global optimality
The solution must always use recursion
Choices must be random
Greedy algorithms fail when:
Local choices do not guarantee global optimality
The input size is small
Only one solution exists
Recursion is removed
The goal of the Activity Selection problem is to:
Minimize total duration
Select maximum non-overlapping activities
Maximize total finish time
Minimize number of selected activities
The greedy rule for Activity Selection is to pick the activity:
With shortest start time
With longest duration
That finishes earliest
That starts latest
which activity is selected first?
B
C
A
D
Which activity is rejected because it starts before activity A finishes?
B
C
A
D
In the final answer, the selected activities are:
A, B, F
A, D, E
B, C, D
A, C, F
The maximum number of activities selected is:
2
3
4
5
Huffman coding assigns shorter codes to characters that are:
Used rarely
Most frequent
Alphabetically earlier
Randomly generated
The Huffman algorithm repeatedly combines the two:
Longest codes
Most frequent nodes
Least frequent nodes
Random nodes
the two smallest frequencies combined first were:
C and D
E and F
A and B
B and C
In HUFFMAN CODING, After combining A (5) and B (9), the new node has frequency:
12
13
14
15
In HUFFMAN CODING, Which frequency pair was combined next?
12 + 13
16 + 45
14 + 16
25 + 30
Huffman trees assign:
1 to left and 0 to right
0 to left and 1 to right
Both 1
Both 0
The final root of the Huffman tree in the example has value:
45
30
55
100
Huffman codes are:
Prefix-free
Always the same length
Randomly assigned
Linear search trees
A Minimum Spanning Tree contains:
All vertices with maximum weight
All vertices with no cycles
Some vertices only
Duplicate edges
Kruskal's algorithm sorts edges by:
Alphabetical order
Start vertex
Weight (ascending)
Vertex degree
Kruskal builds the MST by:
Adding edges that form cycles
Selecting largest edges
Adding smallest edges without forming cycles
Removing edges randomly
the smallest edge is:
A–B (4)
A–C (2)
B–C (1)
D–E (2)
The total MST weight using Kruskal is:
8
12
10
15
Prim’s Algorithm begins with:
The largest vertex
Any chosen vertex
All vertices at once
A sorted edge list
Prim adds the edge that:
Creates a cycle
Has the maximum weight
Is the smallest connecting to the tree
Connects two visited nodes
Starting at A, the first edge chosen
A–B (4)
A–C (2)
C–B (1)
B–D (5)
The final MST edges for Prim are the same as:
QuickSort results
Bellman-Ford
Kruskal’s MST
Dijkstra’s output
Prim works best for:
Sparse graphs
Dense graphs
Linear arrays
Directed acyclic graphs
