381. A hash table of size 75: probability of collision at 6% load ≈ __.

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

382. Total number of comparisons in bubble sort (worst case) is __.

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

383. Postorder DEBFCA; what is the preorder?

Data Structures and Algorithms • Tree Traversals • UGC NET Paper 2 Computer Science DEC 2011

384. In a max-heap of size n, insertion and deletion are O( ) and O( ) respectively

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

385. Given inorder E I C F B G D J H K and preorder B C E I F D G H J K, postorder is

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

386. A tree where each node’s subtrees differ in height ≤1 is?

Data Structures and Algorithms • Balanced Trees (AVL) • UGC NET Paper 2 Computer Science DEC 2011

387. In a tree, vertices with minimal eccentricity (centers) are?

Data Structures and Algorithms • Graph Theory • UGC NET Paper 2 Computer Science DEC 2011

388. Hash f(k)=k mod 13, linear probing, existing keys 55,58,68,91,27,145; location for 79?

Data Structures and Algorithms • Hashing (Open Addressing) • UGC NET Paper 2 Computer Science DEC 2011

389. Empty stack: push1,push2,pop,push3,push4,pop,pop,push5,pop. Top = ?

Data Structures and Algorithms • Stack Operations • UGC NET Paper 2 Computer Science DEC 2011

390. Worst-case time complexity of AVL tree vs BST is better for?

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

391. Circuit steady-state Y=1. Possible values A,B,C are?

Data Structures and Algorithms • Combinational Circuits • UGC NET Paper 2 Computer Science DEC 2011

392. Match algorithms to complexities: (a) Bellman–Ford (b) Kruskal (c) Floyd–Warshall (d) Topological sort — (1) O(m log n) (2) O(n³) (3) O(m n) (4) O(n+m)

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

393. Merging log n lists of size n log n each takes time:

Data Structures and Algorithms • Multiway Merge • UGC NET Paper 2 Computer Science DEC 2011

394. If T(n)=2T(⌊n/2⌋)+n, then T(n)=

Data Structures and Algorithms • Recurrences • UGC NET Paper 2 Computer Science DEC 2011

395. In the given sequential circuit starting 00, after 4 clocks Q1Q0=

Data Structures and Algorithms • Sequential Circuits • UGC NET Paper 2 Computer Science DEC 2011

396. Which permutation is achievable with a size-3 stack from 1,2,3,4,5?

Data Structures and Algorithms • Stack Permutations • UGC NET Paper 2 Computer Science DEC 2011

397. Given graphs G1 and G2, which are planar?

Data Structures and Algorithms • Graph Theory • UGC NET Paper 2 Computer Science DEC 2011

398. (Duplicate) Preorder for postorder DEBFCA is __.

Data Structures and Algorithms • Tree Traversals • UGC NET Paper 2 Computer Science DEC 2011

399. BST is a binary tree where __.

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

400. Leaves of which of the following trees are at the same level?

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