CMS 702: Practice Questions

Built from the emphasis in the lecturer's notes (worked examples repeated in class are the likeliest exam questions). Try each before reading the answer.

Section A: Definitions (short answer)

Define an algorithm and list any five types of algorithms.
What is asymptotic analysis? State the three cases it considers.
Differentiate between Big O, Θ and Ω notation.
Define hashing. List the three components of hashing.
What is a collision in hashing, and state two methods of handling it.
Define a load factor.
Differentiate between a stack and a queue.
Define a tree. State three properties of a tree.
Differentiate between the height and the depth of a node.
State the binary search tree property.

Answers

A step-by-step procedure / set of commands to solve a specific problem. Any five of: brute force, recursive, encryption, backtracking, search, sort, divide and conquer, greedy, dynamic programming, randomized.
Computing the running time of a piece of code in a mathematical unit of computation, expressed as f(n), describing limiting behaviour. Cases: worst, best, average.
Big O = upper bound (worst case); Θ = tight bound, both upper and lower; Ω = lower bound (best case).
Hashing means lookup, the most widely used technique to find aggregate data by key or id. Components: key, hash function, hash table.
A collision occurs when h(x) = h(y), two different keys map to the same hash value. Handled by separate chaining or open addressing.
Number of items the hash table contains ÷ size of the hash table.
A stack is open at one end only and follows LIFO (PUSH/POP); a queue is open at both ends and follows FIFO (Enqueue/Dequeue).
A non-linear hierarchical data structure of nodes connected by edges. Properties: one root node with no parent; each node has one parent but may have many children; each node connects to its children via an edge.
Depth = number of edges from the root down to the node. Height = number of edges from the node down to its deepest leaf.
The value of the left node is less than its parent; the value of the right node is greater than its parent.

Section B: Complexity

List the five complexity classes covered in class, with an example of each.
Arrange in increasing order of growth: O(n²), O(1), O(2ⁿ), O(log n), O(n).
What is the time complexity of binary search, and what condition must the data satisfy?
A nested loop over n elements has what complexity? Justify.

Answers

O(1) constant, fixed time regardless of data volume; O(log n) logarithmic, halves the problem each step, e.g. binary search; O(n) linear, time proportional to input size; O(n²) quadratic, nested loops; O(2ⁿ) exponential, grows rapidly with input size, e.g. naïve recursion.
O(1) < O(log n) < O(n) < O(n²) < O(2ⁿ).
O(log n); the dataset must be sorted.
O(n²), the inner loop runs n times for each of the n outer iterations, giving n × n operations.

Section C: Hashing (worked-example style)

Given the strings {"ab", "cd", "efg"} with a=1, b=2 … g=7, compute the hash index of each in a table of size 7 and show the resulting table.
State four properties of a good hash function.
A hash table of size 10 holds 7 items. Compute the load factor.

Answers

ab = 1+2 = 3 → 3 mod 7 = index 3; cd = 3+4 = 7 → 7 mod 7 = index 0; efg = 5+6+7 = 18 → 18 mod 7 = index 4.
```
index: 0    1  2  3    4    5  6
      [cd] [ ][ ][ab] [efg][ ][ ]
```
Efficiently computable; uniformly distributes the keys; minimizes collision; low load factor.
7 / 10 = 0.7.

Section D: Trees & BST (highest-yield section)

For the tree below, state the depth and height of nodes 10, 5, 2 and 1.

Construct a BST from the values 37, 21, 13, 40, 36, 50.
Give the in-order, pre-order and post-order traversal of the BST you built in Q19.
For the tree below, find the in-order successor of 8 and the in-order predecessor of 14.

What is returned when the in-order successor does not exist?
Construct a binary tree from Pre-order = 1, 2, 4, 8, 9, 10, 11, 5, 3, 6, 7 and In-order = 8, 4, 10, 9, 11, 2, 5, 1, 6, 3, 7.
Differentiate between a full, a perfect and a complete binary tree.
A perfect binary tree has height 3. How many leaf nodes and how many total nodes does it have?

Answers

10: d=0, h=3 · 5: d=1, h=2 · 2: d=2, h=1 · 1: d=3, h=0.

          37
         /  \
       21    40
      /     /  \
    13    36    50

In-order: 13, 21, 36, 37, 40, 50 (sorted, always true for a BST). Pre-order: 37, 21, 13, 40, 36, 50. Post-order: 13, 21, 36, 50, 40, 37.
In-order traversal = 4, 8, 10, 12, 14, 20, 22. Successor of 8 = 10; predecessor of 14 = 12.
−1 is returned. (The in-order predecessor of the first node is null.)

              1
            /   \
           2      3
          / \    / \
         4   5  6   7
        / \
       8   9
          /  \
        10    11

Full, every node has 0 or 2 children. Perfect, every internal node has exactly 2 children and all leaves are on the same level. Complete, every level completely filled, leaves lean left, and the last leaf may lack a right sibling.
l = 2^h = 2³ = 8 leaves; n = 2^(h+1) − 1 = 2⁴ − 1 = 15 nodes.

Section E: Data structures generally

Define a data structure and state the three categories of data types.
List six basic operations performed on data structures.
List the three types of linked list.
Explain, with a diagram, how a node is deleted from a singly linked list.
Differentiate between a fixed-size array and a dynamic array.

Answers

A data organization, management and storage format enabling efficient access and modification, a collection of data values, the relationships among them, and the operations applicable to them. Categories: inbuilt/primitive (integer, float, boolean); derived (stack, queue, list, array); complex (linked list, tree, graph).
Traversal, searching, sorting, merging, insertion, deletion.
Simple (singly), complex (doubly), circular.
Locate the target node, then set the previous node's pointer to the target's next node, bypassing it: Head → [A|•] → [TARGET|•] → [C|•] becomes Head → [A|•] ──────────────→ [C|•].
Fixed-size arrays cannot be altered and have numbered indexes; dynamic arrays can be altered/resized and may be one-, two- or three-dimensional.

Section F: Likely "gap" questions (from the outline, not the notes, see the syllabus gap notes)

Define a graph and describe its two standard representations.
Compare BFS and DFS, naming the data structure each uses.
Compare merge sort and quick sort in terms of method and worst-case complexity.
Explain the time–space tradeoff with one example.
Differentiate between stack allocation and heap allocation.

Answers, see [the syllabus gap notes](syllabus-gaps.html) for full detail

G = (V, E): a set of vertices and a set of edges connecting them. Adjacency matrix, V×V, O(V²) space, O(1) edge check, best for dense graphs. Adjacency list, array of neighbour lists, O(V + E) space, best for sparse graphs.
BFS uses a queue (FIFO) and visits level by level; DFS uses a stack (LIFO) or recursion and goes as deep as possible first. Both O(V + E).
Merge sort divides in half, sorts each half and merges; guaranteed O(n log n), needs O(n) extra space. Quick sort partitions around a pivot and recurses; O(n log n) average but O(n²) worst case when the pivot is always the smallest/largest element.
More memory can buy speed, and vice versa, e.g. a hash table spends O(n) extra space to make search O(1) instead of O(n).
Stack: automatic, LIFO, fast, holds local variables and call frames, fixed small size, fails by overflow. Heap: manual/dynamic, any order, slower, holds dynamically allocated objects, large, fails by leak or fragmentation.