Linear Data Structures

Q1. (4 marks)

• Amortized time = the average cost per operation over a worst-case sequence of operations, spreading the cost of expensive operations across many cheap ones. (2)
• Amortized cost of dynamic-array append = $O(1)$. (1)
• Why: resizing (copy of $n$ elements) happens only when the array is full, and doubling capacity means resizes occur after $1,2,4,8,\dots$ appends. Total copy work over $n$ appends is $n + n/2 + n/4 + \dots < 2n = O(n)$, so cost per append averages $O(1)$. (1)

Q2. (4 marks)

• Two differences (1 each, any two): static array has fixed size at compile/allocation time vs dynamic can grow/shrink; static allocated on stack (often) vs dynamic on heap; dynamic needs resize logic. (2)
• Cache locality: array elements are stored contiguously in memory, so accessing one element loads neighboring elements into cache lines. (1)
• Arrays benefit more than linked lists because linked-list nodes are scattered (non-contiguous) on the heap, causing more cache misses during traversal. (1)

Q3. (4 marks)

• Singly node: data + next (pointer to next node). (1.5)
• Doubly node: data + next + prev (pointers to next and previous). (1.5)
• Insert at head of singly list = $O(1)$. (1)

Q4. (4 marks) (1 each)

• (a) $O(n)$
• (b) $O(1)$
• (c) $O(n)$ (must walk to end)
• (d) $O(1)$ trick (copy next node's data into current, delete next) for a non-tail node; otherwise $O(n)$. Accept $O(n)$ with reasoning.

Q5. (4 marks)

• Stack = linear structure following LIFO (Last-In-First-Out) ordering. (1)
• Operations: push — add element to top; pop — remove and return top element; peek/top — return top without removing. (3, 1 each)

Q6. (4 marks) Step-by-step (stack top on right):

Mismatch occurs: closing ] does not match top {. (3) Final answer: NOT balanced. (1)

Q7. (5 marks) Convert $A + B * C - D$. Precedence: * > +,-; left-associative.

Postfix = A B C * + D - (5) — (2 for correct method/trace, 3 for correct result)

Q8. (5 marks) Capacity 5. Advance formula: rear = (rear + 1) % capacity (and similarly for front). Tracing (using count to track fullness):

• enqueue(10): arr[0]=10, rear→1
• enqueue(20): arr[1]=20, rear→2
• enqueue(30): arr[2]=30, rear→3
• dequeue(): removes arr[0]=10, front→1
• enqueue(40): arr[3]=40, rear→4
• enqueue(50): arr[4]=50, rear→0 (wraps)

Final: front = 1, rear = 0. Array = [50, 20, 30, 40, 50] where valid elements are indices 1–4: 20, 30, 40, 50. Index 0 holds stale/overwritten 50. (3 for trace, 1 for indices, 1 for formula)

Q9. (3 marks)

• Deque = double-ended queue: elements can be inserted/removed at both ends. (1)
• Four operations: pushFront, pushBack, popFront, popBack (accept peekFront/peekBack too). (1)
• Use case (any valid): sliding-window maximum, undo/redo history, browser navigation, palindrome checking. (1)

Q10. (3 marks)

• Priority queue = a queue where each element has a priority; elements are served by priority rather than insertion order. (2)
• Difference: FIFO queue dequeues the earliest inserted element; priority queue dequeues the highest (or lowest) priority element regardless of insertion order. (1)

[
  {"claim":"Dynamic array total copy cost for n appends with doubling is < 2n (O(1) amortized)","code":"n=1024; total=sum(2**k for k in range(0,11)); result = total < 2*n and total == 2047"},
  {"claim":"Circular queue rear wraps to 0 after 5 enqueues from index 0 with capacity 5","code":"cap=5; rear=0\nfor _ in range(5): rear=(rear+1)%cap\nresult = rear==0"},
  {"claim":"Q8 final front index = 1 after 5 enqueues and 1 dequeue","code":"cap=5; front=0; rear=0\nenq=[10,20,30]; \nfor _ in enq: rear=(rear+1)%cap\nfront=(front+1)%cap  # one dequeue\nfor _ in [40,50]: rear=(rear+1)%cap\nresult = front==1 and rear==0"},
  {"claim":"Bracket string ( [ { ] } ) is NOT balanced","code":"s='([{]})'; pairs={')':'(',']':'[','}':'{'}; st=[]; ok=True\nfor c in s:\n    if c in '([{': st.append(c)\n    else:\n        if not st or st.pop()!=pairs[c]: ok=False; break\nresult = (ok and not st)==False"}
]