Font size
WorksheetsQuicksort. Hash Tables, and Binary Search Trees
Total questions: 18
Worksheet time: 13mins
What is the time complexity of the following code? (Click on image to view full screen)
O(nlogn)
O( 2n )
O(n)
O(1)
What is the Time Complexity of the attached code?(Click on image to view full screen)
O(n)
O(1)
O(log n)
O( n2 )
What is the time complexity of the following code?(Click on image to view full screen)
O( n2 )
O(1)
O(n log n)
O(n)
What is the time complexity of the code?(Click on image to view full screen)
O(1)
O(n)
O(n log n)
O(2)
What is the search complexity in direct addressing of hash tables?
O(n)
O(log n)
O(n log n)
O(1)
What is the average run time for quick sort algorithm?
O( n2 )
O(n)
O(nlog n)
O(log n)
How many sub arrays does the quick sort algorithm divide the entire array into?
One
Two
Four
Three
What is the worst case time complexity of the Quick sort?
O(nlogn)
O(n)
O( n3 )
O( n2 )
In Order Traversal
50 40 20 30 10
40 50 20 30 10
10 20 30 40 50
40 20 50 10 30
What is the worst case time complexity for search, insert and delete operations in a GENERAL Binary Search Tree?
O(n) for all
O(logn) for all
O(logn) for search, insert and O(n) for delete
O(logN)
Complete this code
quicksort(A, p, r)
if p< r
q=partition(A, p,r)
quicksort(A, p, q-1)
(a)
What is a Collision Resolution Method for hash table:
Linear Probing
Primary Clustering
Hashing
What is the worst case time complexity for basic operations on a COMPLETE binary tree?
O(n)
O(logn)
O( n2 )
O(1)
For a Binary Search Tree, the left value is greater than the root
True
False
Let us consider a list of numbers (34, 16, 2, 93, 80, 77, 51) and has a hash function of x % 10, what is the order of the elements ?
null, null, 77, 16, null, 34, 93, 2, 51, 80
77, 16, 34, 93, 2, 51, 80
80, 51, 2, 93, 34, null, 16, 77, null, null
80, 51, 2, 93, 34, 16, 77
Is this a Binary Search Tree?
Yes
No
Complete the code: (Answer in the format: answer, answer)
inorder-tree-walk(x)
if n NOT nil
inorder-tree-walk(___)
print x.key
inorder-tree-walk(___)
(a)
When is time complexity of Quicksort O( n2 )?
Pivot is the middle element.
Too many elements.
Pivot is the first element.
Pivot is the highest or smallest element.
