model_questions.md (13072B)
1 --- 2 source: 'docs/semester_2/model_questions.md' 3 title: '<svg xmlns="http://www.w3.org/2000/svg" width="16" height="16" viewBox="0 0 24 24" fill="none" stroke="currentColor" stroke-width="2" stroke-linecap="round" stroke-linejoin="round" style="display:inline; margin-bottom:-2px; margin-right:6px;"><rect width="18" height="18" x="3" y="3" rx="2"/><path d="M7 8h8"/><path d="M7 12h10"/><path d="M7 16h6"/></svg> Model Questions: Data Structures (with C/C++)' 4 --- 5 6 # Model Questions: Data Structures (with C/C++) 7 ### Paper Code: CMSDSC202T (NEP, WBSU — Sem 2) 8 9 --- 10 11 ::: info How to use this file 12 This is a **sure-shot / high-priority** list only — not exhaustive like the Sem 1 file. 13 It is built directly on top of the [Sem 2 DSA notes (N01–N13)](../download) — read those PDFs alongside this. 14 Focus on these first; if time remains, expand into the full notes. 15 ::: 16 17 ## Unit 1 — Introduction, ADT & Complexity 18 19 **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. 20 21 **Q2.** What is an **Abstract Data Type (ADT)**? Explain with the example of the Stack ADT (operations only, no implementation). 22 23 **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. 24 25 **Q4.** Differentiate between **best case, average case, and worst case** complexity with an example (e.g., linear search). 26 27 28 ## Unit 2 — Arrays 29 30 **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. 31 32 **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. 33 34 **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. 35 36 **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? 37 38 **Q9.** Explain **Linear Search** and **Binary Search** algorithms with example and code. Derive their time complexities. Why does binary search require a sorted array? 39 40 **Q10.** What is a **Circular Array**? Why is it needed? Explain how insertion and deletion are done in a circular array. 41 42 **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). 43 44 **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. 45 46 47 ## Unit 3 — Linked List 48 49 **Q12.** What is a linked list? Compare **array vs linked list** (memory, insertion/deletion, access time, static/dynamic). 50 51 **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. 52 53 **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. 54 55 **Q15.** Write an algorithm to **reverse a singly linked list** (iterative). Explain each step with a diagram. 56 57 **Q16.** What is a **doubly linked list**? Explain its node structure. Write insertion and deletion algorithms for a doubly linked list. 58 59 **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? 60 61 **Q18.** Write an algorithm/program to **search for an element** and to **count the number of nodes** in a singly linked list. 62 63 **Q19.** Explain how a **polynomial** can be represented and added using linked lists. 64 65 **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). 66 67 68 ## Unit 4 — Stack 69 70 **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. 71 72 **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? 73 74 **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`. 75 76 **Q23.** Write the algorithm to **evaluate a postfix expression** using a stack. Evaluate: `5 6 2 + * 12 4 / -` showing the stack at each step. 77 78 **Q24.** Explain how a stack is used to check for **balanced parentheses** in an expression. Write the algorithm. 79 80 **Q25.** Explain the application of stack in **recursion** (function call stack) and in **reversing a string**. 81 82 **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). 83 84 **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. 85 86 87 ## Unit 5 — Queue 88 89 **Q26.** What is a queue? Explain the **FIFO** principle. List all queue operations (`enqueue`, `dequeue`, `front`, `rear`, `isEmpty`, `isFull`) using an array. 90 91 **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. 92 93 **Q28.** Implement a **queue using a linked list**. Write `enqueue()` and `dequeue()` operations. 94 95 **Q29.** What is a **Deque (double-ended queue)**? Differentiate between input-restricted and output-restricted deque. 96 97 **Q30.** What is a **priority queue**? Give one real-life application. How is it different from a normal queue? 98 99 **Q31.** Explain how a queue can be implemented using **two stacks** (or vice versa) — write the algorithm. 100 101 **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. 102 103 **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. 104 105 106 ## Unit 6 — Recursion 107 108 **Q32.** What is recursion? Differentiate between **direct and indirect recursion**, and between **tail recursion and non-tail (general) recursion** with examples. 109 110 **Q33.** Write a recursive algorithm/program to compute **factorial of n** and trace the recursion tree / stack for `n = 5`. 111 112 **Q34.** Write a recursive algorithm/program for the **Fibonacci series**. Draw the recursion tree for `n = 5` and comment on its time complexity. 113 114 **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. 115 116 **Q36.** Explain how recursion is internally implemented using a **stack** (activation records / stack frames). What are the advantages and disadvantages of recursion over iteration? 117 118 **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). 119 120 **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. 121 122 123 ## Unit 7 — Trees (Binary Tree & BST) 124 125 **Q37.** Define **tree** and its terminologies: root, node, edge, parent, child, sibling, leaf, degree, depth, height, level. 126 127 **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`? 128 129 **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. 130 131 **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. 132 133 **Q41.** Explain **Level-order traversal** (BFS) of a binary tree using a queue. Write the algorithm. 134 135 **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? 136 137 **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. 138 139 **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. 140 141 **Q45.** What is a **threaded binary tree**? Why is it used? (short note) 142 143 **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). 144 145 **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. 146 147 **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). 148 149 150 ## Quick Reference: Syllabus Unit Map 151 152 | Unit | Topics | Questions | 153 |------|--------|-----------| 154 | 1 | ADT, Complexity, Big-O, Knuth's classification | Q1–Q4, Q11a | 155 | 2 | Arrays, Sparse Matrix, Searching, Sorting | Q5–Q11 | 156 | 3 | Singly/Doubly/Circular Linked List, `Chain<T>` class | Q12–Q19, Q19a | 157 | 4 | Stack, Infix-Postfix-Prefix, Applications, MinStack | Q20–Q25, Q25a–Q25b | 158 | 5 | Queue, Circular Queue, Deque, Priority Queue (Heap) | Q26–Q31, Q31a–Q31b | 159 | 6 | Recursion, Direct/Indirect, Applications | Q32–Q36, Q36a–Q36b | 160 | 7 | Tree, Binary Tree, BST, Traversals (array + linked) | Q37–Q45, Q45a–Q45c | 161 162 --- 163 164 ::: tip Exam Strategy for me 165 - **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). 166 - **Sure-shot 10–15 mark topics**: Linked list insertion/deletion (all positions), Postfix evaluation, Circular queue, BST full construction + traversal, Tower of Hanoi. 167 - Always draw diagrams for linked list operations and trees — most marks are lost for missing diagrams. 168 - 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. 169 ::: 170 ::: info Key Algorithms to Memorise (plase) 171 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 172 :::