Multiple Choice Questions

An algorithm’s ability to detect invalid inputs and respond appropriately is termed its robustness.Answer: A. Robustness

In a singly linked list with n nodes, the average number of comparisons needed to find a node with value x upon success is (n+1)/2.Answer: D. (n+1)/2

Given input sequence "abc" to a deque, the output sequance that cannot be generated by either input-restricted or output-restricted deques is dbca.Answer: A. dbca

The correct statement about strings is: The number of characters in a string is its length.Answer: A. A string’s character count is its length

For a full binary tree with m leaves and depth k, the total number of nodes n satisfies: n = 2k - 1.Answer: C. n = 2k - 1

In a directed graph with 10 vertices, the difference between the sum of in-degrees and out-degrees is always 0.Answer: C. 0

Using hash function H(K) = K % 9 on the list (7,34,55,25,64,46,20,10), elements hashing to address 1 are: 64, 46, 25, 7 → 4 elements.Answer: D. 4

The problem that cannot be solved optimally using a greedy algorithm is the 0-1 Knapsack Problem.Answer: A. 0-1 Knapsack Problem

In a circular queue stored in array Q[m], with rear pointing to the last element and len as the current length, the first element’s index is: (rear + m - len) % m.Answer: B. (rear + m - len) % m

When storing a linear list via linked structure, memory addresses of nodes need not be contiguous.Answer: D. Can be either contiguous or non-contiguous

In a circular singly linked list with head pointer head and length > 1, if p→next→next == head, then p points to the tail node.Answer: D. *p’s direct successor is the tail node

The worst-case time complexity of quicksort is O(n²).Answer: C. O(n²)

A ternary tree with 45 nodes has a minimum height of 5 (since 3⁴ = 81 > 45 ≥ 3³ = 27).Answer: C. 5

If the first output from stack input (1,2,…,n) is 3, then the second output could be 2 (e.g., push 1,2,3; pop 3; pop 2).Answer: D. Could be 2

Inserting an element at position i (1 ≤ i ≤ n+1) in a sequential list requires moving n - i + 1 elements.Answer: A. n - i + 1

True/False Questions

Linked stacks avoid overflow better than array stacks → True In a circular queue, the front pointer points to the first element → False (often points to position before first) Arrays are typically stored contiguously; chaining is not standard → False A substring is a contiguous sequence of characters → False (definition is correct, but phrasing implies non-contiguous) Sum of elements in undirected adjacency matrix = 2 × edges → False 6 vertices require at least 5 edges for connectivity, not 6 → False Sequential lists store logically adjacent elements in physically adjacent memory → True Linked lists are often slower for access but faster for insertions → False Hash functions may have collisions; absolute avoidance is impossible → False Quicksort is not always optimal (e.g., worst-case O(n²)) → False Optimal substructure is essential for dynamic programming → True Top-down and bottom-up are standard hierarchical design methods → True Data structrues and algorithms are interdependent → True Binary trees are ordered by structure, not unordered → False Traversal space complexity is O(h), not necessarily O(log n) for unbalanced trees → False

Fill-in-the-Blank Questions

Data element Linear and nonlinear structures 2n - 1 501 (500 nodes → 1000 pointers → 500 used → 500 empty + 1 null root pointer) front == rear n - 1 (second element is n only if 1 to n-1 pushed, then n pushed and popped second) A + s × i Connected component 1, 2, 3, 6, 5, 4 Pointers r→next = s 210 (200 + 5×2) Largest prime ≤ table size Collision Depth in the binary search tree

Problem Solving

Array Storage Calculation Given A[6][8], 6 bytes per element, base address = 1000:

(1) Total space = 6 × 8 × 6 = 288 bytes
(2) Last element’s first byte: 1000 + 288 - 6 = 1282
(3) Row-major A[1][4]: 1000 + (1×8 + 4)×6 = 1000 + 72 = 1072
(4) Column-major A[4][7]: 1000 + (7×6 + 4)×6 = 1000 + 276 = 1276

Binary Search Tree Construction Inserting (45,80,48,40,22,78):

• 45 → root
• 80 → right child of 45
• 48 → left child of 80
• 40 → left child of 45
• 22 → left child of 40
• 78 → left child of 80’s right child (48)

Final structure:
45
/ \
40 80
/ / \
22 48 78

Minimum Spanning Tree (Prim & Kruskal) (Diagram required — omitted per enstructions)
Prim (from a): Select minimum-weight edges greedily from connected component.
Kruskal: Sort all edges, add without forming cycles. Both yield same MST weight.

Huffman Tree Construction Frequencies: 8, 21, 37, 24, 6, 18, 23, 41, 56, 14
Merge smallest pairs iteratively:

1. 6 + 8 = 14
2. 14 + 14 = 28
3. 18 + 21 = 39
4. 23 + 24 = 47
5. 28 + 37 = 65
6. 39 + 41 = 80
7. 47 + 56 = 103
8. 65 + 80 = 145
9. 103 + 145 = 248

Assign 0 to left, 1 to right (left child ≤ right child).
Resulting codes vary by merge order, but all are prefix-free and optimal.

Quick Sort First Partition Input: [46,58,15,45,90,18,10,62]
Pivot: 46

• Compare from both ends:
  • 10 < 46 → swap with 46 → [10,58,15,45,90,18,46,62]
  • 58 > 46 → skip
  • 15 < 46 → swap with 58 → [10,15,58,45,90,18,46,62]
  • 45 < 46 → swap with 58 → [10,15,45,58,90,18,46,62]
  • 18 < 46 → swap with 58 → [10,15,45,18,90,58,46,62]
  • 90 > 46 → stop
  • Swap 46 with 18 → [10,15,45,18,46,58,90,62]

First pass result: [10,15,45,18] | 46 | [58,90,62]

Algorithm Design

Find Level of Key in BST

int level(bitree *bt, int x) {
    int lev = 0;
    while (bt != NULL) {
        if (bt->key == x) return lev;
        else if (bt->key < x) {
            bt = bt->rchild;
        } else {
            bt = bt->lchild;
        }
        lev++;
    }
    return -1; // Not found
}

Check Symmetric String Pattern

BOOL Symmetry(char a[]) {
    int i = 0;
    Stack s;
    InitStack(s);
    ElemType x;

    while (a[i] != '&' && a[i] != '@') {
        Push(s, a[i]);
        i++;
    }
    if (a[i] == '@') return FALSE;
    i++;

    while (a[i] != '@') {
        Pop(s, x);
        if (x != a[i]) {
            DestroyStack(s);
            return FALSE;
        }
        i++;
    }
    return TRUE;
}

Insert m Elements After First Occurrence of x

int InsertM(sequenlist *L, int x, int m) {
    int n = 0;
    while (L[n] != 0) n++; // Find length

    int pos = -1;
    for (int i = 0; i < n; i++) {
        if (L[i] == x) {
            pos = i;
            break;
        }
    }
    if (pos == -1) return 0;

    // Shift elements right by m positions
    for (int i = n; i > pos; i--) {
        L[i + m] = L[i];
    }

    // Insert m new elements
    for (int j = 0; j < m; j++) {
        L[pos + 1 + j] = /* new value */; // Assuming input provided
    }
    return 1;
}