Final Exam Practice Questions: Data Structures and Algorithms

CS 152 Fall, 2025

Note: This final exam practice questions are developed based exclusively on the materials covered in the class so far, following the topics from Week 6 through Week 14.

Part 1: Multiple Choice Questions (20 Questions)

Instructions: Select the best answer. The correct answer is indicated in bold.

  1. Which principle defines the removal protocol for a standard Queue?
    A. LIFO
    B. LILO
    C. FIFO (Correct)
    D. FILO

  2. What data structure is used as the collection in the generic graph traversal algorithm to perform a Breadth-First Traversal (BFS)?
    A. Stack
    B. List
    C. Dictionary
    D. Queue (Correct)

  3. In the context of graph implementation, which representation typically requires O(N²) memory, regardless of the number of edges (M)?
    A. Adjacency List
    B. Linked List of Edges
    C. Adjacency Matrix (Correct)
    D. Hash Map

  4. A graph that contains no cycles is referred to as a(n):
    A. Complete graph
    B. Connected graph
    C. Dense graph
    D. Acyclic graph (Correct)

  5. Which type of binary tree traversal visits the root node after visiting both the left and right subtrees?
    A. Inorder
    B. Preorder
    C. Level order
    D. Postorder (Correct)

  6. If a binary tree is vine-like and contains N nodes, what is its maximum height?
    A. log₂(N)
    B. N+1
    C. 1
    D. N−1 (Correct)

  7. In a Priority Queue, if two items have the same priority, how are they removed?
    A. Randomly
    B. In FIFO order (Correct)
    C. Based on the insertion order
    D. Based on priority rank

  8. Which operation is used to add an item to the top of a Stack?
    A. Pop
    B. Peek
    C. Push (Correct)
    D. Add

  9. What is the complexity of determining whether an edge exists between two given vertices using an Adjacency Matrix representation?
    A. O(N)
    B. O(N²)
    C. O(log N)
    D. O(1) (Constant time) (Correct)

  10. What is the fundamental structure used to manage function and method calls in computer memory?
    A. The Object Heap
    B. The Data Segment
    C. The Instruction Pointer
    D. The Call Stack (Correct)

  11. The initialization step of Dijkstra’s shortest path algorithm is analyzed to have what time complexity, where N is the number of vertices?
    A. O(N³)
    B. O(N) (Correct)
    C. O(N²)
    D. O(M)

  12. When evaluating a postfix expression using a stack, what action is taken when an operand is encountered?
    A. It is ignored.
    B. It is applied to the two preceding operands.
    C. It is pushed onto the operand stack. (Correct)
    D. It is appended to the postfix expression.

  13. A Directed Acyclic Graph (DAG) is commonly used to model processes involving:
    A. Mutual relationships (like road networks)
    B. Network cycles
    C. Dependencies (like scheduling tasks) (Correct)
    D. Fully connected systems

  14. In a Min-Heap, where is the smallest data item always located?
    A. At the last level, leftmost position
    B. At the root (Correct)
    C. Near the leaf nodes
    D. At the rightmost node

  15. When implementing a Queue using a circular array, what is the running time complexity for both the add and pop operations?
    A. O(N)
    B. O(logN)
    C. O(1) (Correct)
    D. O(N²)

  16. Which specific type of tree is defined by the property that the key in each node is greater than all keys in its left subtree and less than all keys in its right subtree?
    A. Expression Tree
    B. Min-Heap
    C. Full Binary Tree
    D. Binary Search Tree (BST) (Correct)

  17. What specialized structure is used to implement a priority queue when the implementation uses a min-heap?
    A. Linked List
    B. Array Stack
    C. Complete Binary Tree (Correct)
    D. Adjacency List

  18. When converting an infix expression to a postfix expression, what happens to an opening parenthesis ( when encountered?
    A. It is discarded immediately.
    B. It is appended to the postfix expression.
    C. It is pushed onto the stack. (Correct)
    D. It forces all pending operators to be popped.

  19. What term is used for a subgraph that includes all the vertices of the original connected, undirected graph, and is also acyclic?
    A. Connected Component
    B. Depth-First Search Tree
    C. Spanning Tree (Correct)
    D. Directed Graph

  20. A vertex in a graph that has a degree of 0 is called a(n):
    A. Successor
    B. Neighbor
    C. Isolated vertex (Correct)
    D. Root

Part 2: Short Answer Questions (1-2 Words) (10 Questions)

  1. What data structure is used to implement the collection in a Depth-First Traversal (DFS)?
    Answer: Stack

  2. What term describes the value used to label an edge in a weighted graph?
    Answer: Weight (or Weights)

  3. What name is given to a path that does not pass through the same vertex more than once?
    Answer: Simple path

  4. In the context of the LinkedDirectedGraph implementation, what type of Python data structure maintains the mapping between vertex labels and corresponding vertex objects?
    Answer: Dictionary (or dict)

  5. What is the term for a node in a tree that has no children?
    Answer: Leaf

  6. What type of tree structure is defined by the property that all levels are fully filled except possibly the last, which is filled from left to right?
    Answer: Complete

  7. What is the main technique used by operating systems for fair allocation of CPU resources among processes waiting in a queue?
    Answer: Round-Robin

  8. The length of a path in a graph is defined as the number of what?
    Answer: Edges

  9. What is the name of the general algorithmic technique that incrementally builds candidates to solutions and abandons them as soon as they cannot lead to a valid solution?
    Answer: Backtracking

  10. Which type of queue allows items of higher rank to be removed before those of lower rank?
    Answer: Priority

Part 3: Applied Questions (5 Questions)

1. Scenario: Social Media Connectivity

A software company is modeling user relationships on a new social media platform. They initially used an Adjacency Matrix to represent the “following” relationship. However, they observed that 98% of users follow less than 100 other users, but the platform has millions of users (N is very large).

Query: Explain the performance and storage trade-off implications of using the Adjacency Matrix in this scenario, and recommend the superior alternative representation.

Answer:
Trade-off Explanation: The Adjacency Matrix always requires N² storage cells, regardless of the number of actual edges (relationships, M). Since the graph is sparse (98% of users follow relatively few others, meaning M ≪ N²), most cells in the matrix will be unused (containing 0), leading to massive memory waste (high storage cost). Although checking for an edge between two specific users is O(1), iterating across all neighbors of a specific user is slow, requiring O(N) time per row.
Recommendation: The Adjacency List is the superior choice. For a sparse graph, the adjacency list requires memory proportional to N (for the array of pointers) plus 2M (for edges in an undirected graph, or M for directed). Given M is small relative to N², the memory consumption is drastically lower. Furthermore, iterating across all neighbors of a given vertex is faster with an adjacency list, scaling with the actual number of neighbors, not N.

2. Scenario: Compiler Optimization

A compiler is processing a complex arithmetic expression: ((4 + 5) 6) - 3.*

Query: Describe the sequence of steps a stack-based algorithm would perform to evaluate the Postfix equivalent of this expression. Use only the operators and operands from the expression above. Explain what happens to the stack when the first operator * is encountered in the Postfix evaluation process.

Answer:
First, the infix expression ((4 + 5) * 6) - 3 must be converted to postfix (which is 4 5 + 6 * 3 -).
Postfix Evaluation Steps: 1. Scan 4: Push 4 onto the stack. 2. Scan 5: Push 5 onto the stack. 3. Scan +: Pop 5, Pop 4. Calculate 4+5=9. Push 9. 4. Scan 6: Push 6 onto the stack. 5. Scan : (First encounter of the operator) Pop 6 (operand 2), Pop 9 (operand 1). Calculate 96=54. Push 54. 6. Scan 3: Push 3 onto the stack. 7. Scan -: Pop 3 (operand 2), Pop 54 (operand 1). Calculate 54−3=51. Push 51. 8. End of expression: The result (51) is the final item on the stack.

3. Scenario: Airline Route Mapping

An airline wants to find the cheapest route between its hub city (S) and all other available cities (V). The cost of flying between any two cities (edges) is always positive. The total number of cities (N) is 100.

Query: Which algorithm—Dijkstra’s or Floyd’s—is appropriate for this task, and what is the computational complexity of the chosen algorithm? Justify your choice based on the problem requirements and time complexity.

Answer:

  • Chosen Algorithm:

  • Complexity:

  • Justification:

4. Scenario: Emergency Room Scheduling

You are designing the ERModel for an Emergency Room Scheduler system, which must manage patients based on priority (Critical=1, Serious=2, Fair=3).

Query: If you use a LinkedPriorityQueue implementation based on a sorted linked list, how does the add method ensure that a new patient item is placed correctly? If the queue currently holds [Patient_A (1), Patient_B (2), Patient_C (2), Patient_D (3)], where would a new patient, Patient_E (2), be inserted, and why?

Answer:
Add Method Implementation Strategy: The LinkedPriorityQueue implementation, based on a sorted list, requires overriding the standard add method. The add method conducts a search for the new item’s position. It iterates through the list, finding the correct insertion point such that the list remains sorted by priority (where smaller rank means higher priority). The new item is inserted ahead of items of lesser priority (higher rank) or after items of greater or equal priority (lower rank).
Insertion of Patient_E (2): Patient_E (2) has a lower priority (higher rank number) than Patient_A (1). It has the same priority as Patient_B (2) and Patient_C (2). Patient_E would be inserted after Patient_C (2). Items of equal priority are removed in FIFO order. To maintain this FIFO order among equal priorities, the new patient (E) must be placed at the rear of the existing patients with that same priority (B and C).
New Queue Order: [Patient_A (1), Patient_B (2), Patient_C (2), Patient_E (2), Patient_D (3)].

5. Scenario: Tree Structure Verification

A student has implemented the LinkedBST class and wants to check its integrity by analyzing the visitation order of nodes. The tree contains nodes labeled 10, 5, 15, 3, 7, 12, 18.

Query: Provide the expected node visitation order for the Inorder Traversal and explain why this traversal is particularly useful for verifying a Binary Search Tree (BST).

Answer:
Inorder Traversal Definition: Inorder traversal visits the left subtree, then the root node, then the right subtree.
Expected Inorder Visitation Order: 3, 5, 7, 10, 12, 15, 18.
Utility for BST Verification: In a Binary Search Tree (BST), the keys in the left subtree are smaller than the root, and the keys in the right subtree are larger than the root. When an Inorder Traversal is performed on a valid BST, the data retrieved is always guaranteed to be in ascending (sorted) order. Therefore, running an Inorder Traversal is the standard way to verify that a tree structure correctly maintains the BST property.