MCQOPTIONS
Saved Bookmarks
MCQOPTIONS
This section includes 37 Mcqs, each offering curated multiple-choice questions to sharpen your Data Structures and Algorithms knowledge and support exam preparation. Choose a topic below to get started.
| 1. |
Let H be a primary min-heap consisting of n elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in H? |
| A. | θ(log n) |
| B. | θ(n) |
| C. | θ(1) |
| D. | θ(n log n) |
| Answer» C. θ(1) | |
| 2. |
Given two sorted list of size ‘m’ and ‘n’ respectively. The number of comparisons needed in the worst case by the merge sort algorithm will be: |
| A. | m × n |
| B. | minimum of m, n |
| C. | maximum of m, n |
| D. | m + n - 1 |
| Answer» E. | |
| 3. |
A priority queue is implemented as a Max-heap. Initially it has 5 elements. The level order traversal of the heap is 10, 8, 5, 3, 2. Two new elements ‘1’ and ‘7’ are inserted into the heap in that order. The level order traversal of the heap after the insertion of the elements is |
| A. | 10, 8, 7, 5, 3, 2, 1 |
| B. | 10, 8, 7, 2, 3, 1, 5 |
| C. | 10, 8, 7, 1, 2, 3, 5 |
| D. | 10, 8, 7, 3, 2, 1, 5 |
| Answer» E. | |
| 4. |
Given a binary-max heap. The elements are stored in an arrays as 25, 14, 16, 13, 10, 8, 12.What is the content of the array after two delete operations? |
| A. | 14, 13, 8, 12, 10 |
| B. | 14, 12, 13, 10, 8 |
| C. | 14, 13, 12, 8, 10 |
| D. | 14, 13, 12, 10, 8 |
| Answer» D. 14, 13, 12, 10, 8 | |
| 5. |
In a binary max heap containing n numbers, the smallest element can be found in ______ time. |
| A. | O(n) |
| B. | O(log2 n) |
| C. | O(1) |
| D. | O(log2 log2 n) |
| Answer» B. O(log2 n) | |
| 6. |
______ Sorting compares two adjoining values and exchange them if they are not in proper order. |
| A. | Heap |
| B. | Selection |
| C. | Insertion |
| D. | Bubble |
| Answer» E. | |
| 7. |
Algorithm design technique used in quicksort algorithm is? |
| A. | Dynamic programming |
| B. | Backtracking |
| C. | Divide and conquer |
| D. | Greedy method |
| Answer» D. Greedy method | |
| 8. |
In hashing, collision resolution is carried out by close addressing. Which of the following is close addressing technique –I. Buckets (for contiguous storage)II. Chains (for linked storage) |
| A. | Only I |
| B. | I and II |
| C. | Only II |
| D. | None |
| Answer» D. None | |
| 9. |
If one uses straight two-way merge sort algorithm to sort the following elements in ascending order 20, 47, 15, 8, 9, 4, 40, 30, 12, 17 then the order of these elements after the second pass of the algorithm is: |
| A. | 8, 9, 15, 20, 47, 4, 12, 17, 30, 40 |
| B. | 8, 15, 20, 47, 4, 9, 30, 40, 12, 17 |
| C. | 15, 20, 47, 4, 8, 9, 12, 30, 40, 17 |
| D. | 4, 8, 9, 15, 20, 47, 12, 17, 30, 40 |
| Answer» C. 15, 20, 47, 4, 8, 9, 12, 30, 40, 17 | |
| 10. |
Consider the C function given below. Assume that the array listA contains n (> 0) elements, sorted in ascending orderint ProcessArray(int *listA, int x, int n){int i, j, k;i = 0;j = n-1;do { k = (i+j)/2; if (x <= listA[k]) j = k-1; if (listA[k] <= x) i = k+1; } while (i <= j);if (listA[k] == x) return(k);else return -1;}Which one of the following statements about the function ProcessArray is CORRECT? |
| A. | It will run into an infinite loop when x is not in listA. |
| B. | It is an implementation of binary search. |
| C. | It will always find the maximum element in listA |
| D. | It will return- 1 even when x is present in listA |
| Answer» C. It will always find the maximum element in listA | |
| 11. |
Match the following and choose the correct answer in the order A, B, CA.Heap Constructionp.O(nlogn)B.Hash table construction with linear probingq.O (n2 )C.AVL Tree constructionr.O(n)(Bounds given may or may not be asymptotically tight) |
| A. | q, r, p |
| B. | p, q, r |
| C. | q, p, r |
| D. | r, q, p |
| Answer» E. | |
| 12. |
A _______ is an ordered collection of finite, homogeneous data elements. |
| A. | Linked List |
| B. | Graph |
| C. | Tree |
| D. | Hash Table |
| Answer» E. | |
| 13. |
Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE?I. Quicksort runs in Θ (n2) timeII. Bubblesort runs in Θ (n2) timeIII. Mergesort runs in Θ (n) timeIV. Insertion sort runs in Θ (n) time |
| A. | I and II only |
| B. | I and III only |
| C. | II and IV only |
| D. | I and IV only |
| Answer» E. | |
| 14. |
Consider the following array of elements.〈89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100〉The minimum number of interchanges needed to convert it into a max – heap is |
| A. | 4 |
| B. | 5 |
| C. | 2 |
| D. | 3 |
| Answer» E. | |
| 15. |
In hashing, collision results when _______. |
| A. | an attempt is made to insert a record at full primary bucket. |
| B. | an attempt is made to insert a record anywhere in primary bucket. |
| C. | an attempt is made to insert a record at empty primary bucket. |
| D. | an attempt is made to delete a record at full primary bucket. |
| Answer» B. an attempt is made to insert a record anywhere in primary bucket. | |
| 16. |
Consider an array of positive integers between 123456 to 876543, which sorting algorithm can be used to sort these number in linear time? |
| A. | Impossible to sort in linear time |
| B. | Radix Sort |
| C. | Insertion Sort |
| D. | Bubble Sort |
| Answer» C. Insertion Sort | |
| 17. |
Ordered pair that represents time complexity of divide phase and combine phase of merge sort algorithm respectively is: |
| A. | O(1), O(n) |
| B. | O(n), O(1) |
| C. | O(log2 n), O(n log2 n) |
| D. | O(n), O(n) |
| Answer» B. O(n), O(1) | |
| 18. |
Consider the following sorting algorithms.I. QuicksortIl. HeapsortIll. MergesortWhich of them perform in least time in the worst case? |
| A. | I and II only |
| B. | II and III only |
| C. | III only |
| D. | I, II and III |
| Answer» C. III only | |
| 19. |
Consider the following statements1. Insertion Sort and Merge Sort are stable.2. Heap Sort is inherently unstable.3. Selection Sort is not inherently stable, but may be coded in such a way that it is stable |
| A. | Only statement 1 and 2 is correct |
| B. | Statement 3 is not correct |
| C. | Only statement 1 is correct |
| D. | All statements are correct |
| Answer» E. | |
| 20. |
If the array A contains the items 10, 4, 7, 23, 67, 12 and 5 in that order, what will be the resultant array A after third pass of insertion sort? |
| A. | 67, 12, 10, 5, 4, 7, 23 |
| B. | 4, 7, 10, 23, 67, 12, 5 |
| C. | 4, 5, 7, 67, 10, 12, 23 |
| D. | 10, 7, 4, 67, 23, 12, 5 |
| Answer» C. 4, 5, 7, 67, 10, 12, 23 | |
| 21. |
Average number of comparison required for a successful search for sequential search on ‘n’ items is |
| A. | \(n/2\) |
| B. | \((n - 1)/2\) |
| C. | \((n + 1)/2\) |
| D. | None of the above |
| Answer» D. None of the above | |
| 22. |
Algorithm design technique used in quick sort algorithm is |
| A. | Dynamic programming |
| B. | Backtracking |
| C. | Divide and Conquer |
| D. | Greedy Method |
| E. | Merging |
| Answer» D. Greedy Method | |
| 23. |
An operator delete(i) for a binary heap data structure is to be designed to delete the item in the i-th node. Assume that the heap is implemented in an array and i refers to the i-th index of the array. If the heap tree has depth d (number of edges on the path from the root to the farthest leaf), then what is the time complexity to re-fix the heap efficiently after the removal of the element? |
| A. | O(1) |
| B. | O(d) but not O(1) |
| C. | O(2d) but not O(d) |
| D. | O(d2d) but not O(2d) |
| Answer» C. O(2d) but not O(d) | |
| 24. |
A machine needs a minimum of 100 sec to sort 1000 names by quick sort. The minimum time needed to sort 100 names will be approximately |
| A. | 50.2 sec |
| B. | 6.7 sec |
| C. | 72.7 sec |
| D. | 11.2 sec |
| Answer» B. 6.7 sec | |
| 25. |
For which of the following tasks, stack is not suitable data structure?(a) Binary search in an array(b) Breadth first search(c) Implementing function calls(d) Process scheduling |
| A. | (b) and (d) |
| B. | (b) and (c) |
| C. | (a) and (c) |
| D. | (c) and (d) |
| Answer» B. (b) and (c) | |
| 26. |
A list of n strings, each of length n, is sorted into lexicographic order using merge - sort algorithm. The worst case running time of this computation is: |
| A. | O(n log n) |
| B. | O(n2 log n) |
| C. | O(n2 + log n) |
| D. | O(n3) |
| Answer» C. O(n2 + log n) | |
| 27. |
Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64.Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes? |
| A. | 256 |
| B. | 512 |
| C. | 1024 |
| D. | 2048 |
| Answer» C. 1024 | |
| 28. |
Let P be a quicksort program to sort numbers in ascending order using the first element as the pivot. Let t1 and t2 be the number of comparison made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds? |
| A. | t1 = 5 |
| B. | t1 < t2 |
| C. | t1 > t2 |
| D. | t1 = t2 |
| Answer» D. t1 = t2 | |
| 29. |
How many passes does a Bubble sort algorithm require for sorting a given list of 'n' items? |
| A. | n2 |
| B. | √n |
| C. | n + 1 |
| D. | n - 1 |
| Answer» E. | |
| 30. |
Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4.ArrayIndex012345678Value4030201015161784 Now consider that a value 35 is inserted into this heap. After insertion, the new heap is |
| A. | 40, 30, 20, 10, 15, 16, 17, 8, 4, 35 |
| B. | 40, 35, 20, 10, 30, 16, 17, 8, 4, 15 |
| C. | 40, 30, 20, 10, 35, 16, 17, 8, 4, 15 |
| D. | 40, 35, 20, 10, 15, 16, 17, 8, 4, 30 |
| Answer» C. 40, 30, 20, 10, 35, 16, 17, 8, 4, 15 | |
| 31. |
Consider a hash table of size 7, with hash function H (k) = k % 7, and pseudo random i = (i + 5) % 7. We want to insert the following keys one by one from left to right.15, 11, 25, 16, 9, 8, 12What will be the position of the key 25, if we use random probing? |
| A. | 4 |
| B. | 5 |
| C. | 1 |
| D. | 2 |
| Answer» E. | |
| 32. |
Quick sort is run on 2 inputs shown below to sort in ascending orderA. 1, 2, 3……nB. n, n – 1, n – 2 …… 1Let C1 and C2 be the number of comparisons made for A and B respectively. Then |
| A. | C1 > C2 |
| B. | C1 = C2 |
| C. | C1 < C2 |
| D. | Cannot say anything for arbitrary n |
| Answer» C. C1 < C2 | |
| 33. |
Consider a dynamic hashing approach for 4-bit integer keys:1. There is a main hash table of size 4.2. The 2 least significant bits of a key is used to index into the main hash table.3. Initially, the main hash table entries are empty.4. Thereafter, when more keys are hashed into it, to resolve collisions, the set of all keys corresponding to a main hash table entry is organized as a binary tree that grows on demand.5. First, the 3rd least significant bit is used to divide the keys into left and right subtrees.6. to resolve more collisions, each node of the binary tree is further sub-divided into left and right subtrees based on 4th least significant bit.7. A split is done only if it is needed, i. e. only when there is a collision.Consider the following state of the hash table.Which of the following sequence of key insertions can cause the above state of the hash table (assume the keys are in decimal notation)? |
| A. | 10, 9, 6, 7, 5, 13 |
| B. | 5, 9, 4, 13, 10, 7 |
| C. | 9, 5, 13, 6, 10, 14 |
| D. | 9, 5, 10, 6, 7, 1 |
| Answer» B. 5, 9, 4, 13, 10, 7 | |
| 34. |
Consider the following array.2332456972738997Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort above array in ascending order? |
| A. | Insertion sort |
| B. | Selection sort |
| C. | Quicksort using the last element as pivot |
| D. | Merge sort |
| Answer» B. Selection sort | |
| 35. |
Consider a 13 element hash table for which f(key) = key mod 13 is used with integer keys. Assuming linear probing is used for collision resolution, at which location would the key 103 be inserted, if the keys 661, 182, 24 and 103 are inserted in that order? |
| A. | 0 |
| B. | 1 |
| C. | 11 |
| D. | 12 |
| Answer» C. 11 | |
| 36. |
Of the following sort algorithms, which has execution time that is least dependent on initial ordering of the input? |
| A. | Insertion sort |
| B. | Quick sort |
| C. | Merge sort |
| D. | Selection sort |
| Answer» D. Selection sort | |
| 37. |
Of the following sorting algorithms, which has a running time that is least dependent on the initial ordering of the input? |
| A. | Merge Sort |
| B. | Insertion Sort |
| C. | Selection Sort |
| D. | Quick Sort |
| Answer» B. Insertion Sort | |