NSCT Data Structures & Algorithms Revision Guide

Data Structures & Algorithms (DSA) sits at the centre of the NSCT's computing core. The weightage published for the NSCT syllabus lists DSA at 10%; confirm the current figure in the official student guide on nsct.hec.gov.pk, since the question count, duration and marking scheme are announced per cycle.

This is a revision sheet, not a textbook: the complexities and traps MCQs tend to test, plus worked questions showing how to reason to an answer. For the full topic list, see the Data Structures & Algorithms subject page and the NSCT syllabus page.

Complexity Cheat Table

Memorise the tables below, but also know why each entry is true, because trap questions change one detail (sorted input, worst case, extra space).

Core Data Structures

Sorting Algorithms

Three points examiners like to probe:

• Insertion sort is O(n) on already sorted data: one comparison per element.
• Quick sort hits O(n²) when the pivot is always the smallest or largest element, e.g. first-element pivot on sorted input.
• Comparison sorts cannot beat O(n log n) in the worst case. Counting sort avoids comparisons, relying on integer keys in a known range k.

Practise these in the sorting algorithms MCQs.

Worked Example 1: Loop Complexity

Question. What is the time complexity of the following code?

for (int i = 1; i < n; i = i * 2)
    for (int j = 0; j < i; j++)
        count++;

• A) O(log n)
• B) O(n)
• C) O(n log n)
• D) O(n²)

Reasoning. The outer loop runs with i = 1, 2, 4, 8, ... while i < n, so it executes about log₂ n times. But the inner loop does not run n times on each pass; it runs i times. The total work is the sum 1 + 2 + 4 + ... + 2ᵏ, where 2ᵏ < n. A geometric series with ratio 2 sums to 2ᵏ⁺¹ − 1, which is less than 2n. So the total is O(n).

Answer: B.

Why the distractors are wrong. C is the most common trap: it multiplies "log n outer iterations" by "n inner iterations", but the inner loop is bounded by i, not n. A counts only the outer loop. D would require both loops to run up to n.

Stacks, Queues and Linked Lists

These linear structures are covered in the linear data structures MCQs. Know the access rule, the typical implementation and the standard applications.

• Stack (LIFO). Used for function calls, undo, expression evaluation, parenthesis matching and iterative DFS.
• Queue (FIFO). Used in BFS and scheduling. A circular queue reuses freed slots in a fixed array; a common convention treats it as full when (rear + 1) % size == front.
• Deque and priority queue. A deque inserts and deletes at both ends; a priority queue removes the highest-priority item first and is usually a binary heap.
• Linked lists. A doubly linked list can delete a node in O(1) when you already hold a pointer to it, because the node knows its predecessor. A singly linked list cannot. Floyd's cycle detection (slow and fast pointers) finds a loop in O(n) time and O(1) extra space.

Expression conversion also appears often. The infix expression A + B * C becomes A B C * + in postfix, because * has higher precedence than +.

Worked Example 2: Stack Code Trace

Question. What does this sequence print?

push(5); push(3); print(pop());
push(7); push(2); print(pop()); print(pop());
push(9);

• A) 3 2 7
• B) 3 7 2
• C) 5 3 7
• D) 3 2 9

Reasoning. Track the stack from bottom to top:

1. push 5 → [5]; push 3 → [5, 3]; pop prints 3 → [5]
2. push 7 → [5, 7]; push 2 → [5, 7, 2]; pop prints 2 → [5, 7]; pop prints 7 → [5]
3. push 9 → [5, 9]. Nothing more is printed.

Answer: A. The final stack is [5, 9].

Why the distractors are wrong. B treats the second phase as FIFO (queue behaviour). C prints from the bottom of the stack. D prints 9, but 9 is pushed after the last pop and never removed.

Trees: BST, AVL and Heaps

Trees come up often in DSA questions, both as definitions and as traces. The tree algorithms MCQs cover them in depth.

Key Facts

• A binary tree of height h (root at height 0) has at most 2ʰ⁺¹ − 1 nodes.
• A complete binary tree with n nodes has height ⌊log₂ n⌋.
• Traversals: preorder (root, left, right), inorder (left, root, right), postorder (left, right, root), level order (BFS using a queue).
• Inorder traversal of a BST gives keys in ascending order. This single fact answers many MCQs.
• Inserting already sorted keys into a plain BST produces a chain (a "skewed" tree), so search becomes O(n).

AVL Trees

An AVL tree is a self-balancing BST in which every node's balance factor (left height minus right height) is −1, 0 or +1. When an insertion breaks this, one of four rotation cases fixes it:

Binary Heaps

A binary heap is a complete binary tree stored in an array. With 0-based indexing, index i has children at 2i + 1 and 2i + 2 and its parent at ⌊(i − 1) / 2⌋. In a min-heap every parent is at most its children. Insertion appends and bubbles up; extraction moves the last key to the root and sifts down. Both are O(log n).

Worked Example 3: BST Traversal

Question. The keys 50, 30, 70, 20, 40, 60, 80 are inserted in that order into an empty BST. What is the postorder traversal?

• A) 20 30 40 50 60 70 80
• B) 50 30 20 40 70 60 80
• C) 20 40 30 60 80 70 50
• D) 20 40 60 80 30 70 50

Reasoning. Build the tree: 50 is the root; 30 goes left, 70 right; 20 and 40 become children of 30; 60 and 80 become children of 70. The result is a perfectly balanced tree. Postorder visits left subtree, right subtree, then root. The left subtree gives 20 40 30, the right subtree gives 60 80 70, and the root comes last: 50.

Answer: C.

Why the distractors are wrong. A is the inorder traversal (sorted order). B is the preorder traversal. D lists nodes level by level from the bottom, which is not a standard traversal of this tree.

Worked Example 4: Heap Insertion

Question. A min-heap is stored as the array [2, 5, 3, 9, 6, 8]. After inserting 1, what is the array?

• A) [1, 2, 3, 9, 6, 8, 5]
• B) [1, 5, 2, 9, 6, 8, 3]
• C) [1, 2, 3, 5, 6, 8, 9]
• D) [2, 5, 1, 9, 6, 8, 3]

Reasoning. Append 1 at index 6. Its parent is index ⌊(6 − 1) / 2⌋ = 2, holding 3. Since 1 < 3, swap: [2, 5, 1, 9, 6, 8, 3]. Now 1 is at index 2, whose parent is index 0, holding 2. Since 1 < 2, swap again: [1, 5, 2, 9, 6, 8, 3]. Index 0 is the root, so we stop.

Answer: B.

Why the distractors are wrong. D stops after the first swap, leaving a parent (2) larger than its child (1). C is a fully sorted array, which is a valid heap but not what the insertion algorithm produces. A is also a valid min-heap, but it rearranges the left branch; the new key was appended at index 6, a child of index 2, so only the path from index 6 to index 2 to the root changes.

Graphs: BFS, DFS, Dijkstra and MST

Graph questions test both algorithm behaviour and complexity. Practise them in the graph algorithms MCQs.

Representation

An adjacency matrix uses O(V²) space and checks an edge in O(1). An adjacency list uses O(V + E) space and suits sparse graphs. BFS and DFS take O(V + E) with a list and O(V²) with a matrix.

Traversal and Shortest Paths

Hold onto three facts: Dijkstra can give wrong answers with negative edge weights, because it finalises a vertex once it leaves the queue; a spanning tree of V vertices has exactly V − 1 edges; and topological sort applies only to directed acyclic graphs (DAGs).

Worked Example 5: Dijkstra Trace

Question. A directed graph has these edges and weights: A→B (4), A→C (1), C→B (2), B→D (1), C→D (5), D→E (3). Using Dijkstra's algorithm from A, what is the shortest distance to E?

• A) 6
• B) 7
• C) 8
• D) 9

Reasoning. Start with dist(A) = 0 and every other distance at infinity.

1. Remove A (0). Relax: B = 4, C = 1.
2. Remove C (1). Relax: B = min(4, 1 + 2) = 3; D = 1 + 5 = 6.
3. Remove B (3). Relax: D = min(6, 3 + 1) = 4.
4. Remove D (4). Relax: E = 4 + 3 = 7.
5. Remove E (7). Done.

The shortest path is A → C → B → D → E with cost 7.

Answer: B.

Why the distractors are wrong. C (8) follows the direct edge A→B and misses the cheaper route through C. D (9) takes A→C→D, ignoring that going through B is cheaper. A (6) is the tentative distance to D before B is processed, not the distance to E.

Hashing

A hash function maps a key to one of m slots. The load factor α = n / m drives performance: lower α means fewer expected collisions. Revise these in the hashing MCQs.

• Separate chaining stores colliding keys in a list at each slot. α can exceed 1.
• Open addressing stores every key in the table itself, so α must stay at or below 1. Probing schemes include linear probing, quadratic probing and double hashing.
• Linear probing suffers from primary clustering: occupied slots form long runs that any colliding key extends. Quadratic probing and double hashing reduce this.
• Deleting from an open-addressing table needs a "deleted" marker (tombstone); emptying the slot can break later searches.

Worked Example 6: Linear Probing

Question. A hash table has 7 slots (0 to 6), uses h(k) = k mod 7, and resolves collisions with linear probing. The keys 10, 17, 24 and 3 are inserted in that order. In which slot does 3 end up?

• A) 3
• B) 4
• C) 5
• D) 6

Reasoning. Every one of these keys hashes to slot 3: 10 mod 7 = 3, 17 mod 7 = 3, 24 mod 7 = 3 and 3 mod 7 = 3.

• 10 goes into slot 3.
• 17 finds slot 3 full and probes to slot 4.
• 24 finds 3 and 4 full and lands in slot 5.
• 3 finds 3, 4 and 5 full and lands in slot 6.

Answer: D.

Why the distractors are wrong. A ignores the collision. B and C stop probing too early, as if only one or two earlier keys had collided. The example also shows primary clustering: four keys now form one contiguous run.

Recurrences

Some complexity questions arrive as recurrences. Know these by sight:

• T(n) = T(n/2) + O(1) → O(log n) (binary search)
• T(n) = 2T(n/2) + O(n) → O(n log n) (merge sort)
• T(n) = T(n − 1) + O(n) → O(n²) (quick sort's worst case)
• T(n) = 2T(n − 1) + O(1) → O(2ⁿ) (naive Tower of Hanoi)

A related favourite: greedy selection by value-to-weight ratio is optimal for fractional knapsack but not for 0/1 knapsack, which needs dynamic programming. For proofs of these results, Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein (MIT Press) is the standard reference.

Quick Revision Checklist

Before a practice session, make sure you can answer each of these without notes:

• Which sorts are stable, and which run in O(1) extra space?
• Why does inserting sorted keys ruin a BST, and how does an AVL tree prevent it?
• When must you use Bellman-Ford instead of Dijkstra?
• What is primary clustering, and which probing scheme suffers from it?

Turning Revision into Practice

After each section of this guide, take a short topic quiz from the DSA subject page; NSCT Prep has 33,808+ practice MCQs across all subjects. For every question you get wrong, write one line explaining the trap, as the distractor notes above do. End the week with the complexity and optimization MCQs.