Paper 2 CS · UNIT 07 · MOCK TEST

Mock 5 – Sorting & Searching

Unit 7: Data Structures and Algorithms · 19 questions · about 22 minutes. Press End Mock any time to see your score and the correct answers.

All 11 topic-wise mocks in this unit

0 / 19 answered 00:00

Q1. Match List - I with List - II.

List - I	List - II
A. Merge sort	I. n²
B. Binary search	II. nlogn
C. Quick sort	III. n
D. Search in an unsorted array	IV. logn

Choose the correct answer from the options given below:

AA-I, B-IV, C-II, D-III BA-I, B-II, C-III, D-IV CA-II, B-I, C-III, D-IV DA-II, B-IV, C-I, D-III

Q2. In the worst case, the smallest number of comparisons required by any sorting algorithm, which does only binary comparisons, is

A⌈log n⌉ B⌈log n!⌉ C⌈log n(n−1)⌉ D2ⁿ

Q3. A binary search tree is obtained by inserting the words "Mathematics", "Physics", "Geography", "Zoology", "Metrology", "Geology", "Psychology" and "Chemistry" in order. Words are compared by dictionary order. Arrange the following words in increasing order of their level in the tree.
A. Mathematics
B. Zoology
C. Psychology
D. Physics
Choose the correct answer from the options given below:

AA, D, C, B BA, C, D, B CA, D, B, C DC, B, D, A

Q4. Which of the following is NOT a divide and conquer method?

ABinary Search BMerge Sort CQuick Sort DHeap Sort

Q5. Match List I with List II

List I	List II
A. Insertion Sort	I. O(log n)
B. Binary Search	II. O(n²)
C. Quick Sort	III. O(n)
D. Selection Sort	IV. O(n log n)

AA-III, B-I, C-IV, D-II BA-II, B-III, C-I, D-IV CA-I, B-II, C-IV, D-III DA-II, B-III, C-IV, D-I

Q6. Select the sorting algorithms that are stable.
(A) Quick Sort
(B) Bubble Sort
(C) Insertion Sort
(D) Merge Sort
(E) Shell Sort
Choose the correct answer from the options given below:

A(A), (B), (C) and (E) Only B(A), (D) and (E) Only C(B) and (C) Only D(B), (C) and (D) Only

Q7. f(n) = a·f(n/b) + g(n) is a divide-and-conquer recurrence. Match the algorithms in List I with their recurrences in List II.

List I	List II
A. Binary Search	I. f(n) = 7f(n/2) + 15n²/4
B. Find maximum and minimum of a sequence	II. f(n) = 2f(n/2) + n
C. Merge Sort	III. f(n) = 2f(n/2) + 2
D. Fast Matrix Multiplication	IV. f(n) = f(n/2) + 2

AA-I, B-II, C-III, D-IV BA-II, B-III, C-IV, D-I CA-III, B-IV, C-I, D-II DA-IV, B-III, C-II, D-I

Q8. Arrange the following search and sort algorithms in ascending order of their worst-case complexities:
A. Merge sort
B. Linear search
C. Bubble sort
D. Binary search
Choose the correct answer from the options given below:

AD, B, A, C BB, D, A, C CB, D, C, A DB, A, D, C

Q9. Which algorithm design approach is used in the quick sort algorithm?

ADynamic programming BBacktracking CDivide and conquer DGreedy approach

Q10.

Match the LIST-I with LIST-II

AA-III, B-I, C-IV, D-II BA-II, B-III, C-I, D-IV CA-I, B-II, C-IV, D-III DA-II, B-III, C-IV, D-I

Q11.

Select the Sorting Algorithms that are stable.

(A) Quick Sort

(B) Bubble Sort

(D) Merge Sort

(E) Shell Sort

A(A), (B), (C) and (E) Only B(A), (D) and (E) Only C(B) and (C) Only D(B), (C) and (D) Only

Q12.

Match List - I with List - II. f(n) = a f(n / b) + g(n) is a divide-and- conquer recurrence relation for the Listed-I algorithms, match their recurrence in Listed-II.

AA-I, B-II, C-III, D-IV BA-II, B-III, C-IV, D-I CA-III, B-IV, C-I, D-II DA-IV, B-III, C-II, D-I

Q13.

Two balanced binary trees are given with m and n elements, respectively. They can be merged into a balanced binary search tree in ____ time.

AO(m*n) BO(m + n) CO(m*log n) DO(m*log(m + n))

Q14.

There are many sorting algorithms based on comparison. The running time of heapsort O(n lg n) P Q algorithm is . Like , but unlike , (P, Q) heapsort sorts in place where is equal to

AMerge sort, Quick sort BQuick sort, insertion sort CInsertion sort, Quick sort DInsertion sort, Merge sort

Q15.

Which of the following is best running time to n n2 − 1 sort integers in the range 0 to ?

AO(lg n) BO(n) CO(n lg n) DΘ(n²)

Q16.

Which of the following is application of depth- first search?

AOnly topological sort BOnly strongly connected components CBoth topological sort and strongly connected components DNeither topological sort nor strongly connected components

Q17.

The second smallest of n elements can be found with ____________ comparisons in the worst case.

An − 1 Blog n Cn + ⌈log n⌉ − 2 D3n/2

Q18.

A text is made up of the characters A, B, C, D, E each occurring with the probability 0.08, 0.40, 0.25, 0.15 and 0.12 respectively. The optimal coding technique will have the average length of :

A2.4 B1.87 C3.0 D2.15

Q19.

The maximum number of comparisons needed to sort 9 items using radix sort is (assume each item is 5 digit octal number) :

A45 B72 C360 D450

Next: Mock 6 – Complexity, Recurrences & Divide and Conquer (Part 1) →