Midterm Examination: Data Structures and Algorithms

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. The correct answer is highlighted in bold.

Week 1: Collections Overview

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.
Which Python built-in collection type is described as an ordered, immutable sequence of items?
A. List
B. Dictionary
C. Set
D. Tuple
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

Week 2.1: Algorithms and Complexity

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
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
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²)
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ⁿ)
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.

Week 3.1: Recursion Applications and OOP

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.
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
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.
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

Week 4: Arrays and NumPy

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.
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²)
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.
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
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

Week 5: Linked Structures

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.
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²)
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 (20 Questions)

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

List the four general categories of collections defined in the learning objectives.
Answer: The four general categories are linear, hierarchical, graph, and unordered.
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).
Answer: Within the O(n^2) complexity class, Bubble Sort is described as very slow and should probably never be used. Selection Sort is intermediate in speed. Insertion Sort is usually the fastest of the three; in fact, for small arrays (e.g., 10 or 15 elements), it is faster than more complicated sorting algorithms.
List the three recursive steps required to solve the Tower of Hanoi problem involving n disks.
Answer:
1. Move n-1 disks from the source rod to the auxiliary rod.
2. Move the largest disk (disk n) to the destination rod.
3. Move n-1 disks from the auxiliary rod to the destination rod.
Why is the concept of Object-Oriented Programming (OOP) introduced in the class, specifically regarding the upcoming Bag Mini-Project?
Answer: OOP is introduced because it allows students to model real-world entities (like a Bag) as objects. For the Bag mini-project, students will use classes to represent a Bag with attributes (like items) and methods (like add, remove),
Explain the concept of random access in arrays and state its running time complexity.
Answer: Array indexing (random access) means that the computer obtains the location of the i^{th} item by performing a constant number of steps. No matter how large the array, it takes the same amount of time to access the first item as the last item. The running time for random access is O(1) in both best and worst cases.
What are two differences in the memory characteristics between a traditional array (or NumPy array) and a standard Python list?
Answer:
1. Memory Layout: Traditional/NumPy arrays use contiguous memory. Python lists are dynamic and store references to objects scattered throughout memory.
2. Efficiency/Content: Traditional/NumPy arrays are homogeneous (store elements of a single, fixed type) and are memory-efficient for large numeric data. Python lists are heterogeneous and less memory-efficient because they store pointers.
List two distinct reasons, according to the sources, why standard Python lists are slower than NumPy arrays for large numerical operations.
Answer:
1. Python lists require the system to “de-reference” each pointer one by one.
2. The for loop used for standard Python list operations is an interpreted operation.
3. Python has to perform type checking on each element.
4. Each calculation is done separately, unlike the vectorized approach of NumPy. (Any two of these are acceptable).
What are the two methods that the Grid class (representing a 2D array) must recognize, and what information do they return?
Answer: The two methods are getHeight and getWidth. getHeight returns the number of rows, and getWidth returns the number of columns.
In a singly linked structure, why is it easy to get the successor of an item but not easy to get to the predecessor?
Answer: A singly linked structure accesses the successor of an item by chaining through the single links that emanate from the items. Because each node only contains a reference (link) to the next node, there is no direct link to the previous node, making predecessor access difficult.
List two crucial consequences regarding memory usage and operation efficiency that arise from the noncontiguous memory allocation of linked structures, compared to arrays.
Answer:
1. Insertion/Removal: Once an insertion or removal point is found, the operation can take place with no shifting of data items in memory.
2. Resizing: The linked structure can be resized during each insertion or removal with no extra memory cost and no copying of data items.
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.
Answer:
- For a singly linked structure, insertion at the end requires traversing the entire list to find the last node, resulting in O(n) complexity.
- For a doubly linked structure that maintains a tail pointer, the tail pointer allows direct, constant-time access to the last node, allowing insertion at the end to be completed in O(1) time.
Distinguish between an Abstract Collection Type and its Implementations.
Answer: Abstract Collection Types define the behavior and operations of a collection without specifying how they are implemented. Implementations provide concrete ways to realize these abstract types using specific data structures and algorithms (like arrays or linked structures).
When implementing the add method for a LinkedBag, how does the implementation leverage constant-time access, and what does this generally involve changing?
Answer: The add method in LinkedBag leverages constant-time O(1) access by placing the new item at the head of the linked structure. This involves resetting the instance variable self.items to be the new node, which points to the old head.
Define the space/time trade-off in algorithm design.
Answer: When choosing algorithms, one can settle for a space/time trade-off, where an algorithm is designed to achieve faster run times (time efficiency) at the cost of using extra space (memory), or vice versa.
If Insertion Sort were modified to use binary search to find the insertion point, why would the overall time complexity remain O(n^2)?
Answer: Although using binary search reduces the time for finding the insertion point to O(\log n) per insertion, the total time complexity remains O(n^2) because shifting elements to make room for the new item still takes O(n) time per insertion.
Explain what Vectorization is in the context of NumPy and why it provides massive speed gains over standard Python lists for numerical operations.
Answer: Vectorization is the ability to perform operations on entire arrays at once, without explicit Python loops. This provides speed gains because the operations are implemented in highly optimized C/Fortran code underneath, bypassing the slower interpreted Python loops and type checking.
In a singly linked structure, what are the running time complexities for Access by position and Insertion at the beginning?
Answer: Access (by position) takes O(n) because it requires traversal from the head. Insertion at the beginning takes O(1) because it only requires updating the head pointer.
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?
Answer: When full, the ArrayBag uses less memory. In the worst case, a LinkedBag uses twice as much memory as an ArrayBag whose array is full.