Data Structures

What to remember

• A data structure is a way to store and organise data so that operations like search, insert and delete are efficient. Choose by the operations you need most.
• Stack is LIFO and Queue is FIFO. Binary search needs sorted data and takes O(log n) time; linear search takes O(n).
• Tree and graph structures model hierarchy and networks. Know the traversal orders, the node-count rules and the time complexity of the standard sorting methods.

Basic classification

Abstract Data Type (ADT): a description of data and operations, without saying how it is coded. Stack, queue and list are ADTs.

Arrays

• An array stores elements of the same type in contiguous memory, accessed by index.
• Address formula (one-dimensional): Address of A[i] = Base + (i − LB) × w, where LB is the lower bound (0 in C) and w is the size of one element.
• Example: Base = 1000, w = 4, A[5]: address = 1000 + 5 × 4 = 1020.
• Two-dimensional array, row-major: Address of A[i][j] = Base + (i × n + j) × w, where n is the number of columns.
• Column-major: Address = Base + (j × m + i) × w, where m is the number of rows.
• Access is O(1). Insertion or deletion in the middle needs shifting, so it is O(n).
• Number of elements in a matrix with m rows and n columns is m × n.

Linked lists

• A linked list is a chain of nodes. Each node has data and a pointer to the next node.
• Singly linked: one pointer (next). Doubly linked: two pointers (previous and next). Circular: the last node points back to the first.
• Insertion at the head is O(1). Searching is O(n); there is no random access.
• The first node is pointed to by the head. The last node's next pointer is NULL in a singly linked list.
• Compared with an array: a linked list grows easily and insertion is cheap, but it uses extra memory for pointers and has no direct index access.

Stack

• LIFO (Last In, First Out). Operations: push (insert at top), pop (remove from top), peek (see top).
• Overflow: push into a full stack. Underflow: pop from an empty stack.
• Uses: function calls (call stack), undo operation, expression evaluation, bracket matching, and depth-first search.
• Expression forms: Infix (A + B), Prefix (+ A B), Postfix (A B +).
• Conversion example: A + B × C in postfix is A B C × +. (A + B) × C in postfix is A B + C ×.
• Postfix evaluation: read left to right; push operands; on an operator, pop two, apply, push the result. For 2 3 4 × +: 3 × 4 = 12, then 2 + 12 = 14.
• Operator precedence (high to low): ^, then × and ÷, then + and −.

Queue

• FIFO (First In, First Out). Operations: enqueue (insert at the rear), dequeue (remove from the front).
• Types: simple queue, circular queue, double-ended queue (deque), priority queue.
• Circular queue: the rear wraps to the start, so freed space is reused. Next rear position = (rear + 1) mod size.
• Uses: printer job queue, CPU scheduling, breadth-first search, call centres.
• A queue of size n in a simple array can be full even if front spaces are empty; the circular queue solves this.

Trees

• A tree is a hierarchical structure with one root; each node can have children. A node with no child is a leaf.
• Terms: degree (number of children), level (root at level 0 or 1 by convention), height (longest path from root to a leaf), depth (distance from root).
• Binary tree: each node has at most two children (left and right).
• Facts: A binary tree with n nodes has n − 1 edges. A binary tree of height h (root at height 0) has at most 2^(h+1) − 1 nodes. The maximum nodes at level L (root at level 0) is 2^L.
• Full binary tree: every node has 0 or 2 children. Complete binary tree: all levels full except possibly the last, filled left to right.
• Binary search tree (BST): left subtree values are smaller than the node; right subtree values are larger. Inorder traversal of a BST gives sorted order.
• Traversals: Inorder (Left, Root, Right), Preorder (Root, Left, Right), Postorder (Left, Right, Root).
• Example: Insert 50, 30, 70, 20, 40 into a BST. Inorder: 20 30 40 50 70. Preorder: 50 30 20 40 70. Postorder: 20 40 30 70 50.
• Balanced trees: AVL tree (height difference of the two subtrees of every node is at most 1).
• Heap: a complete binary tree. In a max-heap each parent is larger than or equal to its children. In an array with index starting at 1, the children of node i are 2i and 2i + 1, and its parent is i/2 (integer division).

Graphs

• A graph has vertices (nodes) and edges (links). Edges may be directed or undirected, weighted or unweighted.
• Representation: adjacency matrix (n × n array; needs n² space) and adjacency list (less space for sparse graphs).
• Traversal: BFS uses a queue; DFS uses a stack (or recursion).
• Maximum edges in a simple undirected graph with n vertices = n(n − 1)/2. Example: n = 5 gives 10.
• Spanning tree: a subgraph that connects all vertices with n − 1 edges and no cycle. Minimum spanning tree algorithms: Prim and Kruskal. Shortest path algorithm: Dijkstra.

Hashing

• A hash table stores keys by using a hash function that gives an index. Average search time is O(1).
• Collision: two keys give the same index. Resolution: chaining (a list at each slot) and open addressing (linear probing, quadratic probing, double hashing).
• Example: hash function key mod 10; keys 25 and 35 both map to index 5 (collision).

Searching and sorting

Binary search example: For 1000 sorted items, the maximum comparisons are about log2(1000) ≈ 10 (since 2^10 = 1024). For 64 sorted items, the worst case is log2(64) + 1 = 7 comparisons.

Complexity

• Time complexity counts steps as input size n grows; space complexity counts memory.
• Order of growth (small to large): O(1), O(log n), O(n), O(n log n), O(n²), O(2^n).
• Big-O is the upper bound (worst case), Omega is the lower bound, Theta is the tight bound.

Exam traps

• 1. LIFO vs FIFO: stack is LIFO, queue is FIFO.
• 2. Inorder of a BST is sorted; preorder and postorder are not.
• 3. Binary search needs sorted data; linear search does not.
• 4. BFS uses a queue; DFS uses a stack.
• 5. Overflow vs underflow: overflow is a push into a full stack; underflow is a pop from an empty one.
• 6. Quick sort worst case is O(n²), merge sort worst case is O(n log n).
• 7. Array has O(1) access; linked list has O(n) access.
• 8. Edges in a tree = n − 1; a graph can have more edges.

One-liners

• 1. A stack follows the LIFO rule.
• 2. A queue follows the FIFO rule.
• 3. The root of a tree has no parent.
• 4. A leaf has no children.
• 5. Binary search takes O(log n) time.
• 6. Linear search takes O(n) time.
• 7. Inorder traversal of a BST gives sorted order.
• 8. A tree with n nodes has n − 1 edges.
• 9. BFS uses a queue.
• 10. A hash collision is when two keys map to the same index.
• 11. Postfix of A + B is A B +.
• 12. Merge sort takes O(n log n) in every case.

Practice questions

1. Which data structure follows the LIFO principle?

   1. Queue
   2. Binary tree
   3. Stack
   4. Array
   Answer

   C. Stack

   Last In, First Out is the stack rule.

2. Which data structure follows the FIFO principle?

   1. Graph
   2. Binary tree
   3. Stack
   4. Queue
   Answer

   D. Queue

   First In, First Out is the queue rule.

3. Which of these is a non-linear data structure?

   1. Array
   2. Tree
   3. Queue
   4. Stack
   Answer

   B. Tree

   Trees and graphs are non-linear.

4. Inserting an element into a full stack is called

   1. Overflow
   2. Traversal
   3. Underflow
   4. Hashing
   Answer

   A. Overflow

   Push into a full stack causes overflow.

5. Removing an element from an empty stack is called

   1. Collision
   2. Underflow
   3. Rotation
   4. Overflow
   Answer

   B. Underflow

   Pop from an empty stack causes underflow.

6. Which traversal of a binary search tree gives the keys in sorted order?

   1. Inorder
   2. Level order reversed
   3. Postorder
   4. Preorder
   Answer

   A. Inorder

   Left, Root, Right gives ascending order in a BST.

7. Binary search can be applied only on

   1. Unsorted data
   2. Linked lists only
   3. Graphs
   4. Sorted data
   Answer

   D. Sorted data

   Binary search halves a sorted range each step.

8. The time complexity of binary search in the worst case is

   1. O(n)
   2. O(n log n)
   3. O(log n)
   4. O(1)
   Answer

   C. O(log n)

   Each step halves the search range.

9. The time complexity of linear search in the worst case is

   1. O(1)
   2. O(log n)
   3. O(n)
   4. O(n²)
   Answer

   C. O(n)

   Every element may need a check.

10. Breadth-first search of a graph uses a

    1. Queue
    2. Stack
    3. Hash table
    4. Heap
    Answer

    A. Queue

    BFS visits level by level using a queue.

11. Depth-first search of a graph uses a

    1. Priority queue
    2. Stack
    3. Queue
    4. Array of strings
    Answer

    B. Stack

    DFS uses a stack or recursion.

12. A hash collision occurs when

    1. A key is deleted
    2. A key is not found
    3. The table is empty
    4. Two keys map to the same index
    Answer

    D. Two keys map to the same index

    Collision is the same slot for different keys.

13. The first node of a linked list is pointed to by the

    1. Tail
    2. Leaf
    3. Head
    4. Root
    Answer

    C. Head

    The head pointer stores the first node's address.

14. Which linked list has a last node that points back to the first node?

    1. Circular linked list
    2. Header list with NULL end
    3. Singly linked list
    4. Doubly linked list
    Answer

    A. Circular linked list

    A circular list closes the chain.

15. A node with no children in a tree is called a

    1. Sibling
    2. Root
    3. Parent
    4. Leaf
    Answer

    D. Leaf

    A leaf has degree zero.

16. The address of A[5] in a one-dimensional array with base address 1000 and 4 bytes per element (index from 0) is

    1. 1005
    2. 1020
    3. 1024
    4. 1016
    Answer

    B. 1020

    1000 + 5 × 4 = 1020.

17. The address of A[10] in an array with base 2000 and 2 bytes per element (index from 0) is

    1. 2020
    2. 2012
    3. 2010
    4. 2022
    Answer

    A. 2020

    2000 + 10 × 2 = 2020.

18. An array A[i][j] is stored row-wise with base 1000, 5 columns and 4 bytes per element. The address of A[2][3] is

    1. 1056
    2. 1060
    3. 1048
    4. 1052
    Answer

    D. 1052

    (2 × 5 + 3) × 4 = 52, so 1000 + 52 = 1052.

19. An array is stored column-wise with base 100, 3 rows and 2 bytes per element. The address of A[1][2] is

    1. 116
    2. 108
    3. 114
    4. 112
    Answer

    C. 114

    (2 × 3 + 1) × 2 = 14, so 100 + 14 = 114.

20. The value of the postfix expression 5 6 2 + * 12 4 / - is

    1. 43
    2. 37
    3. 35
    4. 40
    Answer

    B. 37

    6 + 2 = 8; 5 × 8 = 40; 12 / 4 = 3; 40 − 3 = 37.

21. The postfix form of (A + B) * C is

    1. A B C + *
    2. * + A B C
    3. A + B C *
    4. A B + C *
    Answer

    D. A B + C *

    Operands first, then the operator after them.

22. The maximum number of nodes in a binary tree of height 3 (root at height 0) is

    1. 8
    2. 7
    3. 15
    4. 16
    Answer

    C. 15

    2^(3+1) − 1 = 15.

23. The maximum number of nodes at level 4 of a binary tree (root at level 0) is

    1. 16
    2. 8
    3. 15
    4. 32
    Answer

    A. 16

    2^4 = 16.

24. A binary tree has 20 nodes. How many edges does it have?

    1. 18
    2. 19
    3. 21
    4. 20
    Answer

    B. 19

    A tree with n nodes has n − 1 edges.

25. The maximum number of comparisons to find a key in a sorted array of 1023 elements by binary search is

    1. 512
    2. 10
    3. 9
    4. 11
    Answer

    B. 10

    2^10 − 1 = 1023, so at most 10 comparisons.

26. The maximum number of edges in a simple undirected graph with 6 vertices is

    1. 36
    2. 12
    3. 30
    4. 15
    Answer

    D. 15

    n(n − 1)/2 = 6 × 5 / 2 = 15.

27. A circular queue has size 8 and the rear is at position 7. The next rear position is

    1. 7
    2. 8
    3. 1
    4. 0
    Answer

    D. 0

    (7 + 1) mod 8 = 0.

28. With the hash function key mod 7, the key 50 is stored at index

    1. 0
    2. 6
    3. 7
    4. 1
    Answer

    D. 1

    50 = 7 × 7 + 1, so the remainder is 1.

29. Push 1, 2, 3; pop; push 4; pop; pop. Which element is now on top of the stack?

    1. 2
    2. 3
    3. 1
    4. 4
    Answer

    C. 1

    After the pops 3, 4 and 2 are removed, leaving only 1.

30. Enqueue 5, 6, 7; dequeue; enqueue 8. Which element is at the front?

    1. 6
    2. 5
    3. 8
    4. 7
    Answer

    A. 6

    5 is removed first; 6 is now at the front.

31. A graph has 8 vertices. How many edges does its spanning tree have?

    1. 6
    2. 7
    3. 8
    4. 9
    Answer

    B. 7

    A spanning tree has n − 1 edges.

32. An adjacency matrix for a graph with 10 vertices has how many entries?

    1. 20
    2. 10
    3. 100
    4. 45
    Answer

    C. 100

    The matrix is 10 × 10.

33. Which sorting method has a worst-case time of O(n²) but average time of O(n log n)?

    1. Quick sort
    2. Merge sort
    3. Selection sort
    4. Heap sort
    Answer

    A. Quick sort

    Quick sort degrades to O(n²) with bad pivots.

34. Which sorting method always takes O(n log n) time and needs extra space?

    1. Selection sort
    2. Merge sort
    3. Bubble sort
    4. Insertion sort
    Answer

    B. Merge sort

    Merge sort uses an auxiliary array.

35. Consider the statements. 1. A stack follows the LIFO rule. 2. A queue follows the LIFO rule. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2
    Answer

    A. 1 only

    A queue is FIFO.

36. Consider the statements about binary search. 1. It needs sorted data. 2. It takes O(log n) time. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2
    Answer

    C. Both 1 and 2

    Both statements are correct.

37. Consider the statements about arrays and linked lists. 1. An array gives direct access to an element by index. 2. A linked list gives direct access by index. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2
    Answer

    A. 1 only

    A linked list must be traversed from the head.

38. Consider the statements about trees. 1. A tree with n nodes has n − 1 edges. 2. A leaf has two children. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2
    Answer

    A. 1 only

    A leaf has no children.

39. Consider the statements about graph traversal. 1. BFS uses a queue. 2. DFS uses a stack or recursion. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2
    Answer

    C. Both 1 and 2

    Both statements are correct.

40. Consider the statements about the inorder traversal of a binary search tree. 1. It visits Left, Root, Right. 2. It gives the keys in descending order. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2
    Answer

    A. 1 only

    It gives ascending order.

41. Match the data structure with the operation. A. Stack B. Queue C. Binary search D. Hashing 1. Enqueue 2. Push 3. Halving 4. Collision

    1. A-1, B-2, C-3, D-4
    2. A-2, B-1, C-4, D-3
    3. A-4, B-1, C-3, D-2
    4. A-2, B-1, C-3, D-4
    Answer

    D. A-2, B-1, C-3, D-4

    Push (stack), enqueue (queue), halving (binary search), collision (hashing).

42. Match the sort with its worst-case time. A. Bubble sort B. Merge sort C. Quick sort D. Heap sort 1. O(n²) 2. O(n log n)

    1. A-1, B-1, C-2, D-2
    2. A-1, B-2, C-1, D-2
    3. A-2, B-1, C-2, D-1
    4. A-2, B-2, C-1, D-1
    Answer

    B. A-1, B-2, C-1, D-2

    Bubble and quick sort are O(n²) in the worst case; merge and heap sort are O(n log n).

43. In a heap stored in an array with index starting at 1, the children of node 5 are at positions

    1. 9 and 10
    2. 6 and 7
    3. 5 and 6
    4. 10 and 11
    Answer

    D. 10 and 11

    Children of node i are 2i and 2i + 1.

44. In a heap stored in an array with index starting at 1, the parent of node 9 is at position

    1. 3
    2. 5
    3. 9
    4. 4
    Answer

    D. 4

    Parent is i/2 with integer division: 9/2 = 4.