QUIZ TIME
Choose the answer and count your score.
1. Which of the following standard algorithms is not a Greedy algorithm?
(A) Kruskal's Minimum Spanning Tree (B) Prim's Minimum Spanning Tree (C) Dijkstra's Shortes Path (D) Huffman Coding (E) Bellmen Ford Shortest path algorithm |
2. Which of the following is true about merge sort?
(A) Merge Sort works better than quick sort if data is accessed from slow sequential memory. (B) Merge Sort is stable sort by nature (C) Merge sort outperforms heap sort in most of the practical situations. (D) All of the above. |
3. Given two vertices in a graph s and t, which of the two traversals (BFS and DFS) can be used to find if there is path from s to t?
(A) Only BFS (B) Only DFS (C) Both BFS and DFS (D) Neither BFS nor DFS |
4. Consider the problem of searching an element x in an array ‘arr[]’ of size n. The problem can be solved in O(Logn) time if.
1) Array is sorted 2) Array is sorted and rotated by k. k is given to you and k <= n 3) Array is sorted and rotated by k. k is NOT given to you and k <= n 4) Array is not sorted (A) 1 Only (B) 1 & 2 only (C) 1, 2 and 3 only (D) 1, 2, 3 and 4 |
5. Which sorting algorithms is most efficient to sort string consisting of ASCII characters?
(A) Quick sort (B) Heap sort (C) Merge sort (D) Counting sort |
6. Which of the following sorting algorithms has the lowest worst-case complexity?
(A) Merge Sort (B) Bubble Sort (C) Quick Sort (D) Selection Sort |
7. Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then
(A) T(n) <= 2T(n/5) + n (B) T(n) <= T(n/5) + T(4n/5) + n (C) T(n) <= 2T(4n/5) + n (D) T(n) <= 2T(n/2) + n |
8. A networking company uses a compression technique to encode the message before transmitting over the network. Suppose the message contains the following characters with their frequency:character Frequency
a 5 b 9 c 12 d 13 e 16 f 45 If the compression technique used is Huffman Coding, how many bits will be saved in the message? |
9. In a village, people build houses in the same side of the road. A thief plans to loot the village. He wants maximum amount of money without having any risk of getting caught. By some means, the villagers know that their adjacent house is being looted or not and thus they become alert. So the thief cannot loot contiguous two houses. Given that the thief knows the amount of money stored in each house and the road is straight and there is no turning, which is the most efficient algorithmic strategy to solve this problem?
(A) Brute-force (B) Dynamic Programming (C) Backtracking (D) Divide and Conquer |
10. Which of the following is not a stable sorting algorithm in its typical implementation.
(A) Insertion Sort (B) Merge Sort (C) Quick Sort (D) Bubble Sort |
answer.docx | |
File Size: | 18 kb |
File Type: | docx |