1. What is the running space of merge sort? A. (log n) B. (n) C. (n log n) D. (n
ID: 3873801 • Letter: 1
Question
1. What is the running space of merge sort?
A. (log n) B. (n) C. (n log n) D. (n 2 )
2. What is the worst case of heap sort in terms of running time?
A. (log n) B. (n) C. (n log n) D. (n 2 )
3. Pick the strongest, correct description of the asymptotic behavior of f(n):. f(n) = p n2 + 10n For the purposes of this question: • is stronger than O, which is stronger than • A simpler statement is stronger than a more complex one, e.g. O(n) is stronger than O(n + 1) or O(2n). • For O, O(g(n)) is stronger than O(f(n)) if g(n) = O(f(n)) and f(n) 6= O(g(n)). The same is true for
A. O(n) B. (n) C. (n) D. ( n)
4. Pick the strongest, correct description of the asymptotic behavior of f(n):. f(n) = n 3 + n 2 For the purposes of this question: • is stronger than O, which is stronger than • A simpler statement is stronger than a more complex one, e.g. O(n) is stronger than O(n + 1) or O(2n). • For O, O(g(n)) is stronger than O(f(n)) if g(n) = O(f(n)) and f(n) 6= O(g(n)). The same is true for
A. O(n 3 ) B. (n 3 ) C. (n 3 + n 2 ) D. (n 3 )
5. For this question, pick the correct ordering of the given expressions. For the purposes of this question, f(n) < g(n) means f(n) = O(g(n)), and f(n) = g(n) means f(n) = O(g(n)) and g(n) = O(f(n)).
A. n log n < n < n1+ < 2 n < 3 n B. n < n log n < n1+ < 2 n = 3n C. n < n log n < n1+ < 2 n < 3 n D. n < n1+ < n log n < 2 n < 3 n 5
6. For this question, pick the correct ordering of the given expressions. For the purposes of this question, f(n) < g(n) means f(n) = O(g(n)), and f(n) = g(n) means f(n) = O(g(n)) and g(n) = O(f(n)).
A. log10 n = log4 = log2 n < n log n < n1+ B. log10 n < log4 < log2 n < n1+ < n log n C. n 1+ < log10 n < log4 < log2 n < n log n D. log10 n = log4 = log2 n < n1+ < n log n
7. What is the worst-case running time of the dictionary operation Search(L, k) implemented by an unsorted array?
A. O(1) B. O(n) C. O(log n) D. O( n)
8. What is the worst-case running time of the dictionary operation Insert(L, k) implemented by a sorted array?
A. O(1) B. O(n) C. O(log n) D. O( n)
9. What is the worst-case running time of the dictionary operation Delete(L, k) implemented by a doubly linked list?
A. O(1) B. O(n) C. O(log n) D. O( n)
10. What is the worst-case running time of the dictionary operation Search(L, k) implemented by a sorted doubly linked list?
A. O(1) B. O(n) C. O(log n) D. O( n)
11. What is the worst-case running time of the dictionary operation Search(L, k) implemented by a sorted array?
A. O(1) B. O(n) C. O(log n) D. O( n)
12. What is the best-case time complexity of searching in hash table?
A. O(lg n) B. O(n) C. O(1) D. O(n lg n)
13. The expected time of finding the minimum value in a min-heap is ( ).
A. O(lg n) B. O(n) C. O(1) D. O(n lg n)
14. The worst case time for quick sort is ( ).
A. O(lg n) B. O(n) C. O(n lg n) D. O(n 2 )
15. Which of the following algorithms does not use divide and conquer?
A. insertion sort B. binary search C. quick sort D. merge sort
16. The worst case time for merge sort is ( ).
A. O(lg n) B. O(n) C. O(n lg n) D. O(n 2 )
17. How many bits do you need to represent the numbers from 0 to 2i 1?
A. i 1 B. i C. 2i1 D. 2i
18. Which algorithm demonstrates the power of using the correct data structure for the job?
A. Selection Sort B. Insertion Sort C. Heap Sort D. Merge Sort 6
19. Assume that we are given n pairs, each of the form (color, number) where color is one of {red, blue, yellow}. We want to sort these pairs first by their color (the order of precedence the same as states) then by their number. Now assume that the items arrive already sorted by color. How quickly can we accomplish this task?
A. (n 3/2 ) B. (n log n) C. (n) D. (n 2 )
20. Assume that we are given n pairs, each of the form (color, number) where color is one of {red, blue, yellow}. We want to sort these pairs first by their color (the order of precedence the same as states) then by their number. Now assume that the items in arbitrary (unsorted) order. How quickly can we accomplish this task?
A. (n 3/2 ) B. (n log n) C. (n) D. (n 2 )
21. I’ve implemented a min-heap as an array. What’s the time complexity of finding the maximum element?
A. (1) B. (log n) C. (n) D. (n log n)
22. What’s the running time of mergesort on a doubly-linked list instead of an array?
A. (n log n) B. (n) C. (n 2 ) D. (2n)
23. f(x) = (g(x)) implies that
A. f(x) = O(g(x)) B. f(x) = (g(x)) C. All of the above D. None of the above
24. What data structure can be used to represent customers waiting on line to pay at the register?
A. Array B. Stack C. Dictionary D. Queue
25. What data structure cannot be used to store an unknown number of data elements?
A. Static Array B. Dynamic Array C. Singly Linked List D. Doubly Linked List
26. Placing the daily problem in folders according to student name is an example of what data structure?
A. Array B. Binary Sort Tree C. Priority Queue D. Hash Table
27. Which sorting algorithm is generally more efficient due to less overhead than the others except in its worst case scenario?
A. Quicksort B. Mergesort C. Heapsort D. Binary Search
28. Given the worst case efficiency of two different algorithms, which runs faster?
A. O((1/2)n 3 ) B. O(n 3 ) C. O(n 3 + n 2 ) D. Asymptotically equivalent
29. Given the worst case efficiency of two different algorithms, which runs faster?
A. O(2n+1) B. O(2n) C. Asymptotically equivalent
30. Suppose you need to implement the dictionary using a sorted array of n elements. What is the dictionary operation of search, insert and delete, respectively?
A. O(n), O(1), O(1) B. O(n), O(log n), O(log n) C. O(log n), O(n), O(n) D. O(log n), O(log n), O(log n)
Explanation / Answer
1. What is the running space of merge sort?
A. (log n) B. (n) C. (n log n) D. (n 2 )
Ans -> C. (n log n)
Merge Sort divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.
2. What is the worst case of heap sort in terms of running time?
A. (log n) B. (n) C. (n log n) D. (n 2 )
Ans-> C. (n log n)
Heap sort is a comparison based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for remaining element
4. Pick the strongest, correct description of the asymptotic behavior of f(n):. f(n) = n 3 + n 2 For the purposes of this question: • is stronger than O, which is stronger than • A simpler statement is stronger than a more complex one, e.g. O(n) is stronger than O(n + 1) or O(2n). • For O, O(g(n)) is stronger than O(f(n)) if g(n) = O(f(n)) and f(n) 6= O(g(n)). The same is true for
A. O(n 3 ) B. (n 3 ) C. (n 3 + n 2 ) D. (n 3 )
Ans - > C. (n 3 + n 2 )
5. For this question, pick the correct ordering of the given expressions. For the purposes of this question, f(n) < g(n) means f(n) = O(g(n)), and f(n) = g(n) means f(n) = O(g(n)) and g(n) = O(f(n)).
A. n log n < n < n1+ < 2 n < 3 n B. n < n log n < n1+ < 2 n = 3n C. n < n log n < n1+ < 2 n < 3 n D. n < n1+ < n log n < 2 n < 3 n 5
Ans-> D
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.