comp 2503 midterm additional flashcards

Question 1

What is the process for drawing an object reference diagram for a linked list?

Answer 1

1. Draw boxes for each node containing data, 2. Draw arrows for references between nodes, 3. Label reference variables (head/tail/current), 4. Show null references with ground symbol or ×

Question 2

How do you verify if parentheses match using a stack?

Answer 2

1. Push opening parentheses onto stack, 2. For each closing parenthesis, pop stack and verify match, 3. Stack should be empty at end, 4. Return false if mismatch or stack not empty

Question 3

What are the steps to implement Binary Search?

Answer 3

1. Find middle element, 2. Compare with target, 3. If target smaller, search left half, 4. If target larger, search right half, 5. Repeat until found or subarray empty

Question 4

What is the process for growing an array-based implementation when full?

Answer 4

1. Create new array (typically 2x size), 2. Copy all elements to new array, 3. Update reference to new array, 4. Update capacity variables

Question 5

How do you maintain references when removing a node from middle of doubly-linked list?

Answer 5

1. Update previous node’s next pointer to skip removed node, 2. Update next node’s previous pointer to skip removed node, 3. Clear removed node’s references, 4. Update size counter