421. In any n-element heap, the number of nodes of height h is ≤ ⌊n/2ʰ⌋ or ≤ ⌊n/2ʰ⁺¹⌋?

Data Structures and Algorithms • Heaps • UGC NET Paper 2 Computer Science JUNE 2013

422. To delete the name before “Vivek” in an alphabetical list, the most efficient structure is a

Data Structures and Algorithms • Linked lists • UGC NET Paper 2 Computer Science JUNE 2013

423. Which is true for priority queues?

Data Structures and Algorithms • Priority queues • UGC NET Paper 2 Computer Science JUNE 2013

424. Solution of T(n)=2T(⌊n/2⌋)+log n is

Data Structures and Algorithms • Recurrences • UGC NET Paper 2 Computer Science JUNE 2013

425. Value of postfix expression 8 3 4 + – 3 8 2 / + * 2 $ 3 + is

Data Structures and Algorithms • Stacks & expressions • UGC NET Paper 2 Computer Science JUNE 2013

426. Program subtracts smaller from larger until x or y zero; prints x. Computes?

Data Structures and Algorithms • Algorithms • UGC NET Paper 2 Computer Science JUNE 2013

427. Most efficient structure to insert/delete in a stored set is ___.

Data Structures and Algorithms • Dictionary Structures • UGC NET Paper 2 Computer Science JUNE 2013

428. For undirected graph with 100 nodes, max edges while still disconnected = _____.

Data Structures and Algorithms • Graph Connectivity • UGC NET Paper 2 Computer Science JUNE 2013

429. Which statements about trees are true? (i) Unique path ⇔ tree. (ii) Connected & e=v–1 ⇔ tree. (iii) e=v–1 & acyclic ⇔ tree.

Data Structures and Algorithms • Graph Theory • UGC NET Paper 2 Computer Science JUNE 2013

430. Linked lists are not suitable for ______.

Data Structures and Algorithms • Linear Data Structures • UGC NET Paper 2 Computer Science JUNE 2013

431. In Quicksort with splits 1–β to β, max recursion depth ≈ _____.

Data Structures and Algorithms • Quicksort Analysis • UGC NET Paper 2 Computer Science JUNE 2013

432. Amortized time per operation in Splay trees for ______ is O(log n).

Data Structures and Algorithms • Self-Adjusting Trees • UGC NET Paper 2 Computer Science JUNE 2013

433. Minimum nodes in binary tree of depth d (root at level 0) = _____.

Data Structures and Algorithms • Tree Properties • UGC NET Paper 2 Computer Science JUNE 2013

434. Given In-order and Post-order traversals (as above), Pre-order is ___.

Data Structures and Algorithms • Tree Traversals • UGC NET Paper 2 Computer Science JUNE 2013

435. An optimal assignment requires that # lines covering all zeros = # ________

Data Structures and Algorithms • Assignment problem • UGC NET Paper 2 Computer Science JUNE 2013

436. Minimum cost for the assignment problem (matrix given) is ________

Data Structures and Algorithms • Assignment problem • UGC NET Paper 2 Computer Science JUNE 2013

437. Number of parenthesizations of n matrices grows as ________

Data Structures and Algorithms • Combinatorics • UGC NET Paper 2 Computer Science JUNE 2013

438. Longest increasing subsequence in n numbers can be found in time ________

Data Structures and Algorithms • Dynamic Programming • UGC NET Paper 2 Computer Science JUNE 2013

439. Time complexity of T(n)=T(n/3)+T(2n/3)+O(n) is ________

Data Structures and Algorithms • Recurrences • UGC NET Paper 2 Computer Science JUNE 2013

440. Optimal BST cost (given pᵢ,qᵢ) is ________

Data Structures and Algorithms • Search Structures • UGC NET Paper 2 Computer Science JUNE 2013