Level 1 — RecognitionLinear Data Structures

Linear Data Structures

⏱ 20 minutes30 marksprintable — key stays hidden on paper

Time limit: 20 minutes Total marks: 30

Section A — Multiple Choice (1 mark each)

Choose the single best answer.

Q1. The amortized time complexity of appending an element to a dynamic array is:

(a) $O(n)$
(b) $O(\log n)$
(c) $O(1)$
(d) $O(n^2)$

Q2. Which data structure follows LIFO (Last-In-First-Out) semantics?

(a) Queue
(b) Stack
(c) Circular linked list
(d) Deque

Q3. A queue follows which ordering discipline?

(a) LIFO
(b) FIFO
(c) Random access
(d) Priority-based

Q4. Which property gives arrays a performance advantage due to storing elements in contiguous memory?

(a) Amortized resizing
(b) Cache locality
(c) Pointer chasing
(d) Dynamic typing

Q5. In a singly linked list, each node contains:

(a) Data and a pointer to the previous node
(b) Data and pointers to both neighbours
(c) Data and a pointer to the next node
(d) Only data

Q6. Which operation is used to view the top element of a stack without removing it?

(a) push
(b) pop
(c) peek
(d) enqueue

Q7. A doubly linked list is preferred over a singly linked list mainly because it allows:

(a) Cache locality
(b) Bidirectional traversal
(c) Constant-size storage
(d) Faster random indexing

Q8. The classic stack application for checking (a[b]{c}) correctness is:

(a) Infix-to-postfix conversion
(b) Balanced parentheses matching
(c) Function call scheduling
(d) Cache eviction

Q9. A circular array implementation of a queue primarily helps to:

(a) Reuse freed slots and avoid wasted space
(b) Sort elements automatically
(c) Give priority to larger elements
(d) Allow random deletion

Q10. In a priority queue, the element served next is the one with:

(a) The earliest insertion time
(b) The latest insertion time
(c) The highest (or lowest) priority
(d) A random selection

Section B — Matching (1 mark each, 5 marks)

Q11. Match each structure/term in Column X with its best description in Column Y.

Column X	Column Y
(i) Deque	(A) FIFO order
(ii) Stack	(B) Insert/remove at both ends
(iii) Queue	(C) Uses next pointer that loops to head
(iv) Circular linked list	(D) LIFO order
(v) Function call stack	(E) Tracks active function invocations

Write your answer as pairs, e.g. (i)-(X).

Section C — True / False with Justification (2 marks each: 1 for verdict, 1 for reason)

Q12. A static array can grow in size at runtime as more elements are appended.

Q13. Deleting the head node of a singly linked list is an $O(1)$ operation.

Q14. Infix-to-postfix conversion can be performed using a stack.

Q15. In a stack, pop() returns and removes the bottom-most element.

Q16. A deque can be used to implement both a stack and a queue.

Q17. Accessing the $k$ -th element of a singly linked list by index is $O(1)$ .

Q18. Every append to a dynamic array is individually $O(1)$ in the worst case.

Answer keyMark scheme & solutions

Section A (10 marks)

Q1 — (c) $O(1)$ . Doubling capacity spreads the cost of occasional $O(n)$ copies over many cheap inserts, giving amortized $O(1)$ . (1)

Q2 — (b) Stack. LIFO = last pushed is first popped. (1)

Q3 — (b) FIFO. First enqueued is first dequeued. (1)

Q4 — (b) Cache locality. Contiguous storage means nearby elements load together into cache lines. (1)

Q5 — (c) Data and a pointer to the next node. Singly linked = one forward pointer. (1)

Q6 — (c) peek. Peek reads the top without modifying the stack. (1)

Q7 — (b) Bidirectional traversal. Each node's prev pointer allows moving backward. (1)

Q8 — (b) Balanced parentheses matching. Push openers, pop on closers to check nesting. (1)

Q9 — (a) Reuse freed slots and avoid wasted space. Wrap-around indexing recycles positions vacated by dequeues. (1)

Q10 — (c) The highest (or lowest) priority. Priority queue orders service by priority, not arrival. (1)

Section B (5 marks)

Q11:

(i)-(B) Deque = insert/remove at both ends (1)
(ii)-(D) Stack = LIFO (1)
(iii)-(A) Queue = FIFO (1)
(iv)-(C) Circular linked list = tail's next loops to head (1)
(v)-(E) Function call stack tracks active invocations (1)

Section C (14 marks)

Q12 — FALSE. (verdict 1) A static array has a fixed size set at allocation; growth requires a dynamic array that reallocates. (reason 1)

Q13 — TRUE. (1) We just move head to head.next (and free old head) — constant work, no traversal. (1)

Q14 — TRUE. (1) Operators are pushed/popped by precedence using a stack (shunting-yard algorithm), producing postfix. (1)

Q15 — FALSE. (1) pop() removes and returns the top (most recently pushed) element, not the bottom. (1)

Q16 — TRUE. (1) Restricting a deque to one end gives a stack; using front-remove and rear-insert gives a queue. (1)

Q17 — FALSE. (1) No random access; you must traverse from head, so indexing is $O(k)$ (worst case $O(n)$ ). (1)

Q18 — FALSE. (1) A resize triggers an $O(n)$ copy; the worst-case single append is $O(n)$ . Only the amortized cost is $O(1)$ . (1)

[
  {"claim":"Doubling from 1: total copies to insert n=16 elements is < 2n (amortized O(1))","code":"n=16; cap=1; copies=0; count=0\nfor i in range(n):\n    if count==cap:\n        copies+=count; cap*=2\n    count+=1\nresult = copies < 2*n"},
  {"claim":"Sum of copy costs 1+2+4+8 for growth up to 16 equals 15 (< n=16)","code":"result = (1+2+4+8) == 15 and 15 < 16"},
  {"claim":"Stack LIFO: pushing 1,2,3 then popping yields 3,2,1","code":"s=[]; \n[s.append(x) for x in [1,2,3]]\nout=[s.pop() for _ in range(3)]\nresult = out == [3,2,1]"},
  {"claim":"Queue FIFO: enqueue 1,2,3 then dequeue yields 1,2,3","code":"from collections import deque\nq=deque([1,2,3]); out=[q.popleft() for _ in range(3)]\nresult = out == [1,2,3]"}
]