Chapter 15 Quiz: Dynamic Data Structures: Linked Lists, Stacks, and Queues

Chapter 15 Quiz: Dynamic Data Structures: Linked Lists, Stacks, and Queues

Instructions: Answer all 20 questions. For multiple-choice, select the single best answer. For code traces, show your work.

Questions 1–8: Multiple Choice

1. Which operation on a singly-linked list (without a tail pointer) takes O(n) time?

(a) Insert at head
(b) Delete the head node
(c) Insert at tail
(d) Check if the list is empty

2. In a stack, the Pop operation removes:

(a) The first element added
(b) The last element added
(c) The element with the highest value
(d) A random element

3. A queue follows which access principle?

(a) LIFO — Last In, First Out
(b) FIFO — First In, First Out
(c) Random access
(d) Priority-based access

4. What is the main advantage of a doubly-linked list over a singly-linked list?

(a) Uses less memory per node
(b) Supports bidirectional traversal
(c) Faster insertion at the head
(d) Allows binary search

5. Why must we pass the head pointer as a var parameter when inserting at the head of a linked list?

(a) To prevent the procedure from reading the pointer
(b) Because pointers cannot be passed by value in Pascal
(c) So that the caller's pointer is updated to the new head
(d) To save memory by avoiding a copy

6. In the queue implementation with Front and Rear pointers, what must happen when the last element is dequeued?

(a) Set Front to nil only
(b) Set Rear to nil only
(c) Set both Front and Rear to nil
(d) Set Rear to Front

7. Which data structure would be most appropriate for implementing an "Undo" feature?

(a) Queue
(b) Array
(c) Stack
(d) Circular list

8. Which of the following is NOT a valid reason to choose a linked list over an array?

(a) The number of elements is not known at compile time
(b) Frequent insertions at the beginning of the collection
(c) Need for fast random access by index
(d) Frequent deletions from the middle of the collection

Questions 9–13: True or False

9. A singly-linked list supports O(1) deletion of a node when you have a pointer to the node and a pointer to the previous node.

10. In a circular linked list, the last node's Next pointer is nil.

11. A stack can be implemented using either an array or a linked list.

12. Traversing an array is typically faster than traversing a linked list of the same size due to cache locality.

13. If you call Dispose(P) and then access P^.Data, the program will always crash immediately.

Questions 14–17: Short Answer

14. Explain the difference between a memory leak and a dangling pointer. Give one example of each in the context of linked list operations.

15. You have a singly-linked list with a head pointer and a tail pointer. List the time complexity (O(1) or O(n)) for each of these operations: - (a) Insert at head - (b) Insert at tail - (c) Delete the head - (d) Delete the tail - (e) Search for a value

16. A deque supports insertion and removal at both ends. Explain why a singly-linked list with head and tail pointers cannot implement all four deque operations in O(1) time. Which operation fails?

17. Describe the "two-pointer" technique for finding the middle node of a singly-linked list in a single pass. What are the two pointers called, and how do they move?

Questions 18–20: Code Trace

18. Trace the following code and state the final output:

var S: TStack;
begin
  InitStack(S);
  Push(S, 1);
  Push(S, 2);
  Push(S, 3);
  WriteLn(Pop(S));
  WriteLn(Peek(S));
  Push(S, 4);
  WriteLn(Pop(S));
  WriteLn(Pop(S));
  WriteLn(Pop(S));
end.

19. Trace the following code and draw the final state of the linked list:

var Head: PNode;
begin
  Head := nil;
  InsertAtHead(Head, 5);
  InsertAtHead(Head, 10);
  InsertAtTail(Head, 15);
  InsertAtHead(Head, 20);
  DeleteNode(Head, 10);
  InsertAtTail(Head, 25);
end;

20. The following procedure is intended to free all nodes in a linked list. It contains a bug. Identify the bug, explain why it is dangerous, and write the corrected version.

procedure FreeListBuggy(var Head: PNode);
begin
  while Head <> nil do
  begin
    Dispose(Head);
    Head := Head^.Next;
  end;
end;

Answer Key

1. (c) — Insert at tail requires traversing the entire list to find the last node.

2. (b) — LIFO: the last element pushed is the first one popped.

3. (b) — FIFO: the first element enqueued is the first one dequeued.

4. (b) — Each node has both Next and Prev pointers, allowing traversal in both directions.

5. (c) — Without var, the assignment Head := NewNode only modifies the local copy. The caller's pointer remains unchanged, leaving the new node unreachable (leaked).

6. (c) — Both must be set to nil. If only Front becomes nil but Rear still points to the disposed node, the next Enqueue will dereference a dangling pointer.

7. (c) — A stack's LIFO behavior naturally supports undoing the most recent action first.

8. (c) — Linked lists require O(n) traversal for random access. Arrays provide O(1) random access.

9. True — Unlinking is O(1): set Previous^.Next := Target^.Next and dispose.

10. False — In a circular list, the last node's Next points back to the first node, not nil.

11. True — Both implementations are valid; the linked-list version has no fixed capacity.

12. True — Array elements are contiguous in memory, benefiting from CPU cache prefetching. Linked list nodes are scattered across the heap.

13. False — The behavior is undefined. The memory might still contain the old data, so the program might appear to work. It might also crash, or produce garbage values. The outcome is unpredictable.

14. A memory leak occurs when allocated memory cannot be freed because no pointer references it. Example: Head := Head^.Next without first disposing the old head. A dangling pointer is a pointer that references memory that has been freed. Example: Dispose(P); WriteLn(P^.Data) — P still holds the old address, but the memory is no longer valid.

15. (a) O(1), (b) O(1) — tail pointer gives direct access, (c) O(1), (d) O(n) — even with a tail pointer, we need the node before the tail to update it, and a singly-linked list has no Prev pointer, (e) O(n).

16. PopBack (remove from the tail) cannot be O(1) with a singly-linked list because after removing the tail, we need to update the tail pointer to the previous node. In a singly-linked list, we have no Prev pointer, so we must traverse from the head to find the second-to-last node — O(n). A doubly-linked list solves this: Tail^.Prev gives the new tail in O(1).

17. Use a "slow" pointer that moves one node at a time and a "fast" pointer that moves two nodes at a time. Start both at the head. When the fast pointer reaches the end (or nil), the slow pointer is at the middle. This finds the middle in a single O(n) pass without needing to know the list length in advance.

18. Output:

Explanation: Push 1, 2, 3. Pop returns 3. Peek returns 2 (still on stack). Push 4. Pop returns 4, then 2, then 1.

19. Final list: 20 -> 5 -> 15 -> 25 -> nil

Step-by-step: - InsertAtHead(5): 5 -> nil - InsertAtHead(10): 10 -> 5 -> nil - InsertAtTail(15): 10 -> 5 -> 15 -> nil - InsertAtHead(20): 20 -> 10 -> 5 -> 15 -> nil - DeleteNode(10): 20 -> 5 -> 15 -> nil - InsertAtTail(25): 20 -> 5 -> 15 -> 25 -> nil

20. Bug: Dispose(Head) is called before Head := Head^.Next. After disposing, Head^.Next reads freed memory (dangling pointer access). Corrected version:

procedure FreeList(var Head: PNode);
var
  Temp: PNode;
begin
  while Head <> nil do
  begin
    Temp := Head;
    Head := Head^.Next;
    Dispose(Temp);
  end;
end;

Save the current node in Temp, advance Head, then dispose Temp.