441. Nearly sorted list: best sort is ___.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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