Data Structures Previous Year Questions (page 2)

Explanation

In-order traversal of any binary search tree visits the keys in ascending sorted order: 10, 20, ..., 100.

Explanation

In an AVL tree, the heights of the left and right subtrees of every node differ by at most 1: |h(TL) − h(TR)| ≤ 1.

Explanation

Binary search needs at most ⌈log₂(n+1)⌉ comparisons. 2²⁰ = 1,048,576 ≥ 10,00,000, so the maximum is 20.

Explanation

The root is B (last in postorder). Left subtree {E,I,C,F} has root C, with E (right child I) and F. Right subtree {G,D,J,H,K} has root D, with left G and right H (J, K). Preorder: B, C, E, I, F, D, G, H, J, K.

Explanation

Each of the n nodes connects to the other n − 1. Each edge is then counted twice, so there are n(n − 1)/2 edges.

Explanation

In a B-tree all leaves are at the same level, so statement (C) is false. The others are standard B-tree properties.

Explanation

By the handshaking lemma the sum of degrees is 2|E|, which is even, so the number of odd-degree vertices must be even.

Explanation

In a red-black tree every node is red or black, and a red node's children must be black. Leaves (NIL nodes) are black, not red, so II is false.

Explanation

Add 20 at position 9 as the child of 6, then swap it with 6. Its parent is now 17, so swap again. The parent 23 is larger, so it stops: 23, 20, 14, 17, 13, 10, 1, 5, 6.

Explanation

Kruskal: take Q–R (5), S–T (10), Q–T (15); skip Q–S (20) and R–T (25), which would form cycles; take P–Q (30). Weight = 5 + 10 + 15 + 30 = 60.

Explanation

Rows run from −4 to 1, which is 1 − (−4) + 1 = 6 rows. Columns run from 6 to 10, which is 10 − 6 + 1 = 5 columns. Total elements = 6 × 5 = 30.

Explanation

A stack holds pending work in LIFO order. The postponed items wait on the stack and are processed only after the current conditions are met, as in recursion or backtracking.

Explanation

This new-order is right, node, left, which is reverse in-order. The right subtree of P gives Z, V, Y, X, W. Then comes P. The left subtree gives S, U, T, Q, R.

Explanation

14 has two children, so it is replaced by its in-order successor 16, the smallest key in its right subtree. 16's right child 20 moves up. Pre-order is then 16, 10, 7, 13, 11, 20, 18, 25, 22.

Explanation

An AVL tree allows each node a balance factor (left height minus right height) of only −1, 0 or +1. So 1 is valid, while 2, 3 and 4 would need a rebalancing rotation.

Explanation

A pendant vertex has degree exactly one. An isolated vertex has degree zero.

Explanation

The matrix is square, vertex by vertex, and entry (i, j) = 1 exactly when vi and vj are joined by an edge. For example, V1 is joined to V3 and V4. So it is the adjacency matrix. An incidence matrix would be vertex by edge.

Explanation

The unary * operator, which gives the value a pointer points to, is called the indirection (dereference) operator.

Explanation

An in-order traversal (Left, Node, Right) of a BST visits the keys in ascending order. Pre-order and post-order do not.

Explanation

LR and RL cases each need two single rotations, so they are called double rotations. LL and RR need only one.

Explanation

Bottom-up heapify: 215 swaps with 300, 250 swaps with 300, then 289 swaps with 300. No other node violates the heap, so 3 interchanges.

Explanation

Binary search needs a sorted list with direct (random) access to the middle element, which an array provides. A linked list has no direct access to the middle, so III is false.

Explanation

A matrix with a high proportion of zero entries is a sparse matrix; one with few zeros is a dense matrix.

Explanation

A binary tree of height n has at most 1 + 2 + ... + 2ⁿ = 2ⁿ⁺¹ − 1 nodes (completely full) and at least n + 1 nodes (one node per level, a chain).

Explanation

^ binds tighter, so 3 ^ 4 is grouped first: 9 v (3 ^ 4) v 2. v is left associative, so it is (9 v (3 ^ 4)) v 2: root v with left child the inner v and right child 2.

Explanation

Double hashing, quadratic probing and chaining resolve collisions. Folding is a method of computing a hash function, not a collision resolution technique.

Explanation

Merge sort is stable: equal keys keep their original order. Selection, quick and heap sort are not stable in their usual forms.

Explanation

Post-order traversal visits the left subtree, then the right subtree, then the node (Left, Right, Node).

Explanation

After deleting 13, the left subtree of 14 is just node 1 (height 1). The right subtree 64 → 98 → 85 has height 3. BF = 1 − 3 = −2.

Explanation

Insert 350 at the end (position 10). Its parent 150 is smaller, so swap. The new parent 300 is smaller, so swap again. 400 is larger, so stop: 400, 350, 200, 100, 300, 160, 170, 80, 40, 150.

Explanation

Right-left-node is the exact reverse of preorder (node-left-right). The preorder is A, B, C, D, E, F, G, H, I, J, K, so the new-order is K, J, I, H, G, F, E, D, C, B, A.

Explanation

In a BST, the value at N is greater than every value in its left subtree and less than (or equal to) every value in its right subtree. Both statements reverse this, so neither is correct.

Explanation

Each edge adds 2 to the total degree, so the sum of degrees is even (handshaking lemma), and hence the number of odd-degree vertices must also be even.

Explanation

A leaf node is removed by setting its parent's pointer to null (I correct). A node with two children is replaced by its inorder successor (or predecessor), not its preorder successor, so II is wrong.

Explanation

Binary search keeps narrowing Beg..End; when Beg passes End (End < Beg) the search range is empty, so the element is not present.

Explanation

71 is the root; 56 and 48 go left; 96 goes right; 76 becomes the left child of 96; 82 goes right of 76 (level 4); 98 is the right child of 96. So 82 is at the deepest level.

Explanation

A DFD is also called a bubble chart because processes are drawn as circles (bubbles).

Explanation

McCabe's cyclomatic complexity for a connected control flow graph is V(G) = E − N + 2 (or number of decisions + 1).

Explanation

A max-heap must be a complete binary tree with every parent ≥ its children. Option B satisfies both. A and C are not complete trees, and in D the node 50 has a larger child 80.

Explanation

LL and RR imbalances are fixed by one rotation (single rotations). LR and RL need two rotations, so they are double rotations.

Explanation

A red-black tree with n internal nodes has height at most 2log₂(n + 1), since the black height is at least half the height.

Explanation

20 goes to the right of 18, making 23 unbalanced (left height 2, right 0) with a left-right pattern. An LR double rotation makes 20 the subtree root with 18 and 23 as children, as in option B.

Explanation

The BST is 38 with left subtree 14 (8, and 23 with left child 18 whose right child is 20) and right subtree 56 (45, and 82 with left child 70). Postorder: 8, 20, 18, 23, 14, 45, 70, 82, 56, 38.

Explanation

A 2D array can be initialised with a flat list when both sizes are given: {1,2,3,4} fills row by row. [2,2] is not C syntax, and only the first dimension may be left empty.

Explanation

Offset = i × (4 × 5) + j × 5 + k = 2 × 20 + 3 × 5 + 4 = 59, so the address is 3000 + 59 = 3059.

Explanation

A recursive function needs a base condition to stop and a recursive call that moves toward that base case. Without a base case the recursion never ends.

Explanation

To insert at position i, elements i to n each move one place to the right, so they become i+1, i+2, ..., n+1.

Explanation

Recursive search makes up to n calls, so the time is O(n). Each pending call uses a stack frame, so the space is also O(n).

Explanation

C stores 2D arrays contiguously in one block, row after row (row-major order).