Midterm Practice Questions: Data Structures and Algorithms

CS 152 Fall, 2025

Note: This midterm exam is developed based exclusively on the materials covered in the class so far, following the topics from Week 1 through Week 6.

Part I: Multiple Choice Questions (20 Questions)

Please select the best answer for each question.

Collections Overview

  1. Which statement accurately defines the organizational principle of a linear collection?
    A. Items are organized as nodes connected by edges, forming a network structure.
    B. Items are ordered in a structure resembling an upside-down tree.
    C. Items are stored without any specific order or position.
    D. Items are ordered by position, and each non-endpoint item has a unique predecessor and successor.

  2. Which Python built-in collection type is described as an ordered, immutable sequence of items?
    A. List
    B. Dictionary
    C. Set
    D. Tuple

  3. What is the process of using a computer’s clock to obtain the actual run time of an algorithm called?
    A. Complexity Analysis
    B. Rate of Growth Determination
    C. Benchmarking or Profiling
    D. Big-O Notation

Algorithms and Complexity

  1. Which complexity class describes the rate of growth of work that is proportional to the \log_2 of the problem size?
    A. Constant
    B. Linear
    C. Logarithmic
    D. Quadratic

  2. What does the “O” stand for in Big-O notation?
    A. Over capacity
    B. Optimal time
    C. Order of magnitude
    D. On the order of

  3. In the context of algorithm performance analysis, what is the best-case time complexity for the sequentialSearch algorithm?
    A. O(n)
    B. O(log n)
    C. O(1)
    D. O(n²)

  4. What is the computational complexity (Big-O notation) of the comparison operations performed by the Bubble Sort algorithm?
    A. O(n)
    B. O(log n)
    C. O(n²)
    D. O(2ⁿ)

  5. If the Insertion Sort algorithm were modified to use binary search to find the insertion point, why would the overall time complexity remain O(n^2)?
    A. Binary search takes O(n) time in this context.
    B. The comparison steps still take O(n^2) time in total.
    C. Shifting elements to make room for the new item still takes O(n) time per insertion.
    D. The total number of comparisons does not change.

Recursion Applications and OOP

  1. When developing a recursive puzzle solver, which step is essential to define when the recursion stops?
    A. Defining the recursive case.
    B. Marking visited positions.
    C. Identify the base case (when to stop recursion).
    D. Generating all possible next moves.

  2. The Minimax Algorithm is discussed as a recursive approach for strategy evaluation in which specific game case study?
    A. Maze Puzzle
    B. Tower of Hanoi
    C. Tic-Tac-Toe
    D. Sudoku solvers

  3. According to the rules for the Tower of Hanoi puzzle, what constraint applies to placing disks?
    A. A disk may only be moved to an adjacent rod.
    B. No disk may be placed on top of a smaller disk.
    C. Only two disks can be moved at a time.
    D. Disks must remain in ascending order of diameter on all rods.

  4. In Object-Oriented Programming (OOP), what term is used for the software entity that contains data (attributes) and functions (methods)?
    A. Interface
    B. Module
    C. Object
    D. List

Arrays and NumPy

  1. Which characteristic differentiates traditional arrays (e.g., in C or Java) from Python lists?
    A. They are mutable (elements can be changed).
    B. They support random access.
    C. They have a fixed size; you cannot change their length after creation.
    D. They store references to objects.

  2. What is the running time complexity for accessing an element at the i^{th} position in a traditional array?
    A. O(n)
    B. O(log n)
    C. O(1)
    D. O(n²)

  3. When a dynamic array’s capacity needs to be increased, which step is primarily responsible for the resulting O(n) running time?
    A. Creating a new, larger array.
    B. Resetting the old array variable.
    C. Checking for available space.
    D. Copying the data from the old array to the new array.

  4. What is the core object in the NumPy library that is homogeneous, contiguous, and optimized for scientific computing?
    A. Python list
    B. Pandas DataFrame
    C. ndarray
    D. Array module’s array type

  5. NumPy achieves massive speed gains over standard Python loops for numerical operations primarily through what mechanism?
    A. Multithreading in Python
    B. Dynamic resizing
    C. Vectorization
    D. Homogeneous referencing

Linked Structures

  1. What is the primary operational advantage that linked structures have over arrays concerning insertion and removal?
    A. Faster sequential search
    B. O(1) access by position
    C. Insertion or removal can take place with no shifting of data items in memory.
    D. The head pointer is always None.

  2. In a singly linked structure, what is the running time complexity for Insertion at the end when starting traversal from the head link?
    A. O(1)
    B. O(n)
    C. O(log n)
    D. O(n²)

  3. A circular linked structure with a dummy header node is used primarily to simplify which aspect of list management?
    A. O(1) access to internal nodes
    B. Maintaining contiguous memory
    C. Edge cases related to insertions and deletions at the head or tail.
    D. Implementing a search function

Part II: Short Answer Questions (18 Questions)

Please answer the following questions clearly and concisely, drawing only on the provided source materials.

  1. List the four general categories of collections defined in the learning objectives.

  2. Compare the relative speeds of Bubble Sort, Selection Sort, and Insertion Sort based on the source material, given that they all have a complexity of O(n^2).

  3. List the three recursive steps required to solve the Tower of Hanoi problem involving n disks.

  4. Why is the concept of Object-Oriented Programming (OOP) introduced in the class, specifically regarding the upcoming Bag Mini-Project?

  5. Explain the concept of random access in arrays and state its running time complexity.

  6. What are two differences in the memory characteristics between a traditional array (or NumPy array) and a standard Python list?

  7. List two distinct reasons, according to the sources, why standard Python lists are slower than NumPy arrays for large numerical operations.

  8. What are the two methods that the Grid class (representing a 2D array) must recognize, and what information do they return?

  9. In a singly linked structure, why is it easy to get the successor of an item but not easy to get to the predecessor?

  10. List two crucial consequences regarding memory usage and operation efficiency that arise from the noncontiguous memory allocation of linked structures, compared to arrays.

  11. Contrast the running time complexity for Insertion at the end between a singly linked structure (starting from the head) and a doubly linked structure that maintains a tail pointer.

  12. Distinguish between an Abstract Collection Type and its Implementations.

  13. When implementing the add method for a LinkedBag, how does the implementation leverage constant-time access, and what does this generally involve changing?

  14. Define the space/time trade-off in algorithm design.

  15. If Insertion Sort were modified to use binary search to find the insertion point, why would the overall time complexity remain O(n^2)?

  16. Explain what Vectorization is in the context of NumPy and why it provides massive speed gains over standard Python lists for numerical operations.

  17. In a singly linked structure, what are the running time complexities for Access by position and Insertion at the beginning?

  18. When comparing the memory usage of a full ArrayBag versus a LinkedBag of the same logical size, which implementation uses less memory, and what is the approximate memory cost difference in the worst case?