Data Structures and Algorithms MCQs – Set 23

By Atul Sahu • Computer Science, Data Structures and Algorithms

Data Structures and Algorithms MCQs – Set 23

UGC NET Paper 2 Computer Science DEC 2014 – Data Structures and Algorithms

441. Nearly sorted list: best sort is ___.

Data Structures and Algorithms • Sorting • UGC NET Paper 2 Computer Science DEC 2014

A. Bubble sort B. Selection sort C. Quick sort D. Insertion sort

442. A full binary tree with n leaves has ___ nodes.

Data Structures and Algorithms • Trees • UGC NET Paper 2 Computer Science DEC 2014

A. n B. log₂n C. 2n−1 D. 2n

443. Which equalities are correct? E1: n^{K+1}+n^{K} lg n = Θ(n^{K+1}); E2: n·2^{n}+6n^{2}3^{n} = O(n·2^{n}).

Data Structures and Algorithms • Asymptotic Analysis • UGC NET Paper 2 Computer Science DEC 2014

A. E1 true, E2 true B. E1 true, E2 false C. E1 false, E2 true D. E1 false, E2 false

444. Bounds on #leaves in a B-tree of degree K and height h are ___.

Data Structures and Algorithms • B-trees • UGC NET Paper 2 Computer Science DEC 2014

A. Kʰ and 2^{⌈K/2⌉(h−1)} B. K*h and 2^{⌈K/2⌉(h−1)} C. Kʰ and 2^{⌊K/2⌋(h−1)} D. K*h and 2^{⌊K/2⌋(h−1)}

445. Algorithm with modules M1 O(h(n)) and M2 O(g(n)) has complexity ___.

Data Structures and Algorithms • Complexity • UGC NET Paper 2 Computer Science DEC 2014

A. min(h,g) B. max(h,g) C. h+g D. h*g

446. Chars a,b,g,d,s with p=.12,.40,.15,.08,.25. Optimal coding avg length ≈ ___.

Data Structures and Algorithms • Compression • UGC NET Paper 2 Computer Science DEC 2014

A. 1.7 B. 2.15 C. 3.4 D. 3.8

447. Code-word length=10, words: 0000000000,0000011111,1111100000,1110000011,1111111111. Minimum Hamming distance is ___.

Data Structures and Algorithms • Error-Correcting Codes • UGC NET Paper 2 Computer Science DEC 2014

A. 5 B. 10 C. 8 D. 9

448. Hash search is O(1) for ____ and direct addressing is ____ time.

Data Structures and Algorithms • Hashing • UGC NET Paper 2 Computer Science DEC 2014

A. average, worst-case B. worst-case, average C. worst-case, worst-case D. best, average

449. In universal hashing with n keys and m table slots (n

Data Structures and Algorithms • Hashing • UGC NET Paper 2 Computer Science DEC 2014

A. <1 B. C. >1 D. >log n
Answer: A. <1
Explanation: Load factor α=n/m<1 gives expected α collisions per key, so <1.

450. Quicksort splits subproblems of size (1–a)n and a n (0

Data Structures and Algorithms • Quicksort Analysis • UGC NET Paper 2 Computer Science DEC 2014

A. –log n / log(1–a) B. –log(1–a) / log n C. –log n / log a D. –log a / log n
Answer: A. –log n / log(1–a)
Explanation: Height ≈ log₁/(1–a) n = –log n / log(1–a).

451. Solve T(n)=3T(⌊n/4⌋)+n. Then T(n)= ___.

Data Structures and Algorithms • Recurrence Relations • UGC NET Paper 2 Computer Science DEC 2014

A. O(n²) B. O(n log n) C. O(n) D. O(log n)
Answer: C. O(n)
Explanation: By Master theorem a=3,b=4, n^{log₄3}=n^{0.79}

452. After mergesort’s two recurses but before merge: ___.

Data Structures and Algorithms • Sorting • UGC NET Paper 2 Computer Science DEC 2014

A. array is a heap B. each half is sorted C. all in first half ≤ second half D. all of the above
Answer: B. each half is sorted
Explanation: Each recursive call sorts its subarray, but they are not yet merged or compared across halves.

453. Max parentheses on stack for ((()(() )(() ))) is ___.

Data Structures and Algorithms • Stacks • UGC NET Paper 2 Computer Science DEC 2014

A. 2 B. 3 C. 4 D. 5
Answer: C. 4
Explanation: Maximum nesting depth = 4 (count of consecutive unmatched '(' ).

454. S1: Queue via two stacks. S2: Stack via two queues. Which is correct?

Data Structures and Algorithms • Abstract Data Types • UGC NET Paper 2 Computer Science DEC 2014

A. S1 yes, S2 no B. S1 no, S2 yes C. Both yes D. Both no
Answer: A. S1 is correct and S2 is not correct.
Explanation: Implementing queue with two stacks is standard; stack via two queues is possible but less efficient and not universal.

455. Matrix chain <30×35,35×15,15×5,5×10>: min scalar multiplications = ?

Data Structures and Algorithms • DP algorithms • UGC NET Paper 2 Computer Science DEC 2014

A. 14875 B. 21000 C. 9375 D. 11875
Answer: A. 14875
Explanation: Optimal parenthesization yields cost 14875 via dynamic programming.

456. Match: Prim’s, Bellman–Ford, Floyd–Warshall, Johnson’s to i.O(V²E) ii.O(VE lgV) iii.O(E lgV) iv.O(V³).

Data Structures and Algorithms • Graph algorithms • UGC NET Paper 2 Computer Science DEC 2014

A. i iii iv ii B. i iii ii iv C. iii i iv ii D. iii i ii iv
Answer: C. iii i iv ii
Explanation: Prim’s=O(E lgV) iii, Bellman–Ford=O(VE) i, Floyd=O(V³) iv, Johnson’s=O(E lgV+V² log V) approximates ii.

457. Hash table m=10000, h(K)=floor(m*(KA mod 1)), A=(√5−1)/2, K=123456 maps to:

Data Structures and Algorithms • Hashing • UGC NET Paper 2 Computer Science DEC 2014

A. 46 B. 41 C. 43 D. 48
Answer: C. 43
Explanation: Compute fractional part and multiply: h≈floor(10000((123456×0.618…) mod1)).

458. Max-heap [20,18,15,13,12], insert 10 then 17. New level-order = ?

Data Structures and Algorithms • Heaps • UGC NET Paper 2 Computer Science DEC 2014

A. 20,18,17,15,13,12,10 B. 20,18,17,12,13,10,15 C. 20,18,17,10,12,13,15 D. 20,18,17,13,12,10,15
Answer: A. 20,18,17,15,13,12,10
Explanation: Insert 10 then 17, bubble up produces that heap order.

459. On a singly linked list (head, tail), which is not O(1)?

Data Structures and Algorithms • Linked Lists • UGC NET Paper 2 Computer Science DEC 2014

A. Insert front B. Insert end C. Delete front D. Delete last
Answer: D. Deletion of the last node.
Explanation: Deleting last requires traversal to penultimate node in a singly linked list.

460. Radix sort n integers with d digits: time complexity = ?

Data Structures and Algorithms • Sorting algorithms • UGC NET Paper 2 Computer Science DEC 2014

A. O(k(n+d)) B. O(d(n+k)) C. O((n+k) lg d) D. O((n+d) lg k)
Answer: B. O(d(n+k))
Explanation: Each digit sorted in O(n+k), repeated d times.

Disclaimer for MCQ Quiz
This quiz is for educational purposes only…

0 0 votes

Article Rating

Subscribe

0 Comments

Oldest
Newest Most Voted

Inline Feedbacks

View all comments

Data Structures and Algorithms MCQs – Set 23

Related Posts