Model Questions: Data Structures (with C/C++)
Paper Code: CMSDSC202T (NEP, WBSU — Sem 2)
How to use this file
This is a sure-shot / high-priority list only — not exhaustive like the Sem 1 file. It is built directly on top of the Sem 2 DSA notes (N01–N13) — read those PDFs alongside this. Focus on these first; if time remains, expand into the full notes.
Unit 1 — Introduction, ADT & Complexity
Q1. What is a data structure? Differentiate between linear and non-linear data structures with examples. Also differentiate between primitive and non-primitive data structures.
Q2. What is an Abstract Data Type (ADT)? Explain with the example of the Stack ADT (operations only, no implementation).
Q3. Explain time complexity and space complexity. What is asymptotic notation? Explain Big-O, Big-Ω, and Big-θ with simple examples. Find the time complexity of a nested loop that runs n times outer and n times inner.
Q4. Differentiate between best case, average case, and worst case complexity with an example (e.g., linear search).
Unit 2 — Arrays
Q5. What is an array? Explain how a 1-D array is stored in memory. Derive the address calculation formula for the i-th element of a 1-D array.
Q6. Explain row-major and column-major order for storing a 2-D array. Derive the address formula for an element A[i][j] in both cases.
Q7. What is a sparse matrix? Why do we need special representation for it? Explain the triplet (3-tuple) representation of a sparse matrix with an example.
Q8. Write an algorithm/program to insert an element at a given position and delete an element from a given position in an array. What is the time complexity of each?
Q9. Explain Linear Search and Binary Search algorithms with example and code. Derive their time complexities. Why does binary search require a sorted array?
Q10. What is a Circular Array? Why is it needed? Explain how insertion and deletion are done in a circular array.
Q11. Write short notes on any two sorting algorithms among Bubble Sort, Selection Sort, Insertion Sort — algorithm, dry run on an example array, and time complexity (best/worst/average).
Q11a. Give Knuth's definition of a data structure (as covered in note N01). Classify the following into Linear / Non-Linear / Multi-linked / Dynamic structures: Array, Tree, Doubly Linked List, Stack, Graph, Memory Management structures.
Unit 3 — Linked List
Q12. What is a linked list? Compare array vs linked list (memory, insertion/deletion, access time, static/dynamic).
Q13. Explain the structure of a singly linked list node. Write an algorithm/program to insert a node at (a) the beginning, (b) the end, (c) a given position of a singly linked list.
Q14. Write an algorithm/program to delete a node from (a) the beginning, (b) the end, (c) a given position of a singly linked list.
Q15. Write an algorithm to reverse a singly linked list (iterative). Explain each step with a diagram.
Q16. What is a doubly linked list? Explain its node structure. Write insertion and deletion algorithms for a doubly linked list.
Q17. What is a circular linked list? How does it differ from a singly linked list? What is one practical application of a circular linked list?
Q18. Write an algorithm/program to search for an element and to count the number of nodes in a singly linked list.
Q19. Explain how a polynomial can be represented and added using linked lists.
Q19a. Write the C++ node structure and the Chain<T> class outline for a template-based singly linked list (data field + link/next pointer field). Using this, write the Length(), Find(k, x), Insert(k, x), and Delete(k, x) member functions, explaining the special handling needed when k = 0 (inserting/deleting at the head).
Unit 4 — Stack
Q20. What is a stack? Explain the LIFO principle. List all stack operations (push, pop, peek/top, isEmpty, isFull) with their algorithms using an array.
Q21. Implement a stack using a linked list. Write push() and pop() operations. Why is a linked-list stack preferred over an array-based stack in some cases?
Q22. What is infix, postfix (Reverse Polish), and prefix notation? Convert the following infix expression to postfix using the stack-based algorithm (show step-by-step stack contents): (A + B) * (C - D) / E.
Q23. Write the algorithm to evaluate a postfix expression using a stack. Evaluate: 5 6 2 + * 12 4 / - showing the stack at each step.
Q24. Explain how a stack is used to check for balanced parentheses in an expression. Write the algorithm.
Q25. Explain the application of stack in recursion (function call stack) and in reversing a string.
Q25a. Write a Stack<T> class (array-based, using push, pop, top, isEmpty) and use it to solve any two of the following practice problems from your notes: (a) reverse a string using a stack, (b) check balanced parentheses, (c) design a MinStack that supports GetMin() in O(1), (d) check for redundant brackets in an expression, (e) sort a stack using another stack (or recursively).
Q25b. Explain how a stack can be implemented using two queues, and conversely how a queue can be implemented using two stacks. Write the Push/Pop (or Enqueue/Dequeue) logic for one of these conversions.
Unit 5 — Queue
Q26. What is a queue? Explain the FIFO principle. List all queue operations (enqueue, dequeue, front, rear, isEmpty, isFull) using an array.
Q27. What is the "false overflow" problem in a linear (array-based) queue? How is a circular queue used to solve it? Write the enqueue/dequeue algorithm for a circular queue.
Q28. Implement a queue using a linked list. Write enqueue() and dequeue() operations.
Q29. What is a Deque (double-ended queue)? Differentiate between input-restricted and output-restricted deque.
Q30. What is a priority queue? Give one real-life application. How is it different from a normal queue?
Q31. Explain how a queue can be implemented using two stacks (or vice versa) — write the algorithm.
Q31a. Compare the time complexity of Insert, DeleteMax, and Max operations on a priority queue implemented as: (a) an unordered array, (b) an ordered array, (c) a binary heap. Write the HeapifyUp and HeapifyDown functions for a max-heap-based priority queue.
Q31b. Write an algorithm/program to check whether a queue is a palindrome (using an auxiliary stack), and to interleave the first and second halves of a queue.
Unit 6 — Recursion
Q32. What is recursion? Differentiate between direct and indirect recursion, and between tail recursion and non-tail (general) recursion with examples.
Q33. Write a recursive algorithm/program to compute factorial of n and trace the recursion tree / stack for n = 5.
Q34. Write a recursive algorithm/program for the Fibonacci series. Draw the recursion tree for n = 5 and comment on its time complexity.
Q35. Write a recursive algorithm/program to find the GCD of two numbers (Euclidean algorithm) and to solve the Tower of Hanoi problem for n disks. State the recurrence relation and total number of moves for Tower of Hanoi.
Q36. Explain how recursion is internally implemented using a stack (activation records / stack frames). What are the advantages and disadvantages of recursion over iteration?
Q36a. Differentiate between direct and indirect recursion with a code example for each (e.g. a function A() calling B() which calls back into A()). List at least three common mistakes made while writing recursive functions (missing base case, wrong recursive relation, stack overflow from deep recursion).
Q36b. List at least four applications of recursion in data structures and algorithms (tree traversal, graph DFS, backtracking, divide-and-conquer such as Merge/Quick Sort). Write a recursive function to compute xⁿ (power) and to reverse a linked list recursively.
Unit 7 — Trees (Binary Tree & BST)
Q37. Define tree and its terminologies: root, node, edge, parent, child, sibling, leaf, degree, depth, height, level.
Q38. What is a binary tree? Explain its types: full/strict, complete, perfect, skewed binary tree. What is the maximum number of nodes at level i and in a binary tree of height h?
Q39. Explain array representation and linked representation of a binary tree. For array representation, give the formulas to find parent/left-child/right-child index.
Q40. Explain and write algorithms for Preorder, Inorder, and Postorder tree traversal (recursive). Given a binary tree diagram, write its preorder, inorder, and postorder sequences.
Q41. Explain Level-order traversal (BFS) of a binary tree using a queue. Write the algorithm.
Q42. What is a Binary Search Tree (BST)? Write the algorithm to insert a node and to search for a key in a BST. What is the time complexity in the best and worst case?
Q43. Write the algorithm to delete a node from a BST. Explain all three cases: (a) leaf node, (b) node with one child, (c) node with two children.
Q44. Construct a BST by inserting the following keys in order: 50, 30, 70, 20, 40, 60, 80. Show the tree after every insertion and give its inorder traversal.
Q45. What is a threaded binary tree? Why is it used? (short note)
Q45a. Write the array-representation rules for a binary tree (root at index 0; left child of i is 2i+1; right child is 2i+2; parent of i is ⌊(i-1)/2⌋). Using these rules, write the recursive Inorder, Preorder, and Postorder traversal functions directly on the array (without converting to a linked tree).
Q45b. Write iterative (stack-based) algorithms for Preorder and Inorder traversal of a binary tree using its linked representation. Why is Postorder traversal harder to do iteratively than Preorder/Inorder? Explain the two-pointer/lastVisited technique used to solve it.
Q45c. Write recursive functions to: (a) count total nodes, (b) count leaf nodes, (c) compute the height, (d) check if two binary trees are identical, and (e) validate whether a binary tree is a valid BST (using a min/max range check).
Quick Reference: Syllabus Unit Map
| Unit | Topics | Questions |
|---|---|---|
| 1 | ADT, Complexity, Big-O, Knuth's classification | Q1–Q4, Q11a |
| 2 | Arrays, Sparse Matrix, Searching, Sorting | Q5–Q11 |
| 3 | Singly/Doubly/Circular Linked List, Chain<T> class | Q12–Q19, Q19a |
| 4 | Stack, Infix-Postfix-Prefix, Applications, MinStack | Q20–Q25, Q25a–Q25b |
| 5 | Queue, Circular Queue, Deque, Priority Queue (Heap) | Q26–Q31, Q31a–Q31b |
| 6 | Recursion, Direct/Indirect, Applications | Q32–Q36, Q36a–Q36b |
| 7 | Tree, Binary Tree, BST, Traversals (array + linked) | Q37–Q45, Q45a–Q45c |
Exam Strategy for me
- Sure-shot 5-mark topics: Array vs Linked List, Infix→Postfix conversion, Stack/Queue array implementation, BST insertion/deletion, Recursion trace (Factorial/Fibonacci/Tower of Hanoi).
- Sure-shot 10–15 mark topics: Linked list insertion/deletion (all positions), Postfix evaluation, Circular queue, BST full construction + traversal, Tower of Hanoi.
- Always draw diagrams for linked list operations and trees — most marks are lost for missing diagrams.
- Practice at least one full dry run (step-by-step) for: infix-to-postfix, postfix evaluation, and BST construction — these are asked almost every year.
Key Algorithms to Memorise (plase)
Binary Search · Bubble Sort · Singly Linked List insert/delete/reverse (Chain<T> style) · Stack push/pop (array + linked list) · Infix→Postfix conversion · Postfix evaluation · Balanced Parentheses check · MinStack (GetMin in O(1)) · Circular Queue enqueue/dequeue · Priority Queue via Binary Heap (HeapifyUp/HeapifyDown) · Factorial & Fibonacci recursion · Euclid's GCD · Tower of Hanoi · BST insert/search/delete · Tree traversals — recursive (array-based) and iterative stack-based (Pre/In/Post) + Level-order (queue-based) · Count nodes/leaves, height, IsBST validation