CS2 Final Review

RECURSION & EXCEPTIONS

100

What is the base case in recursion?

b) Stopping condition

200

What happens if recursion has no base case?

StackOverflowError

300

Which exception occurs when dividing by zero?

ArithmeticException

400

Which keyword is used to declare exceptions?

throws

500

In a try-catch block for the GCD program, this is what should happen when gcd(-5, 18) is called, and this is what gets printed.

The method throws an IllegalArgumentException, control jumps to the catch block, and "Invalid input" is printed. Execution continues normally after the catch block.

SORTING & COMPLEXITY

100

Time complexity of binary search is:

O(log n)

200

Worst-case time complexity of Quick Sort:

 O(n²)

300

Best-case time complexity of Merge Sort:

O(n log n)

400

Which sorting algorithm is stable? (Quick Sort, Selection Sort, Merge Sort, Heap Sort)

Merge Sort

500

Selection Sort and Bubble Sort are both O(n²), but one performs significantly fewer swaps in the worst case. Name which one, state its exact number of swaps for an array of size n, and explain why.

Selection Sort performs at most n − 1 swaps in the worst case. This is because each pass finds the minimum of the unsorted portion and performs only one swap to place it in its correct position. Bubble Sort, in contrast, swaps adjacent elements repeatedly and can perform up to n(n−1)/2 swaps in the worst case. So while both have O(n²) comparisons, Selection Sort is preferable when swap cost is high.

DATA STRUCTURES BASICS

100

Access time of an array element:

O(1)

200

Linked list elements are stored:

Randomly in memory

300

Which data structure uses FIFO?

Queue

400

Stack follows:

LIFO

500

Queue underflow occurs when:

Empty

TREES & AVL

100

Worst-case search in BST:

O(n)

200

AVL tree is:

Self-balancing BST

300

Balance factor range in AVL tree:

-1 to 1

400

30, 20, 25 into an empty AVL tree in that order. Identify the imbalanced node, name the rotation case, and draw the resulting balanced tree.

After inserting 25, node 30 becomes imbalanced (balance factor = +2, with the new node on the right of its left child → Left-Right case). Fix with an LR rotation: first left-rotate at 20, then right-rotate at 30. 

500

A BST is built by inserting these values in order: 50, 30, 70, 20, 40, 60, 80. Give the inorder, preorder, and postorder traversals.

• Inorder (L-Root-R): 20, 30, 40, 50, 60, 70, 80

• Preorder (Root-L-R): 50, 30, 20, 40, 70, 60, 80

• Postorder (L-R-Root): 20, 40, 30, 60, 80, 70, 50

CODE & CONCEPTS

100

In insertion sort, best case occurs when:

Array is sorted

200

Explain recursion with an example. Identify base and recursive cases.

Recursion is when a method calls itself to solve a smaller subproblem. Example — factorial(n): base case is if (n == 0) return 1; and recursive case is return n * factorial(n - 1);. The base case stops the recursion; the recursive case breaks the problem into smaller pieces.

300

Differentiate between Merge Sort and Quick Sort (time complexity, stability, space).

• Merge Sort: O(n log n) in all cases (best/avg/worst), stable, requires O(n) extra space.

• Quick Sort: O(n log n) avg, O(n²) worst, not stable, in-place with O(log n) stack space.

400

Sort [45, 12, 78, 34, 23] using Insertion Sort. Show each pass and the final array.

• Pass 1: key=12 → shift 45 → [12, 45, 78, 34, 23]

• Pass 2: key=78 → no shift → [12, 45, 78, 34, 23]

• Pass 3: key=34 → shift 78, 45 → [12, 34, 45, 78, 23]

• Pass 4: key=23 → shift 78, 45, 34 → [12, 23, 34, 45, 78]

• Final: [12, 23, 34, 45, 78]

500

A singly linked list has n nodes. State the time complexity of: (1) inserting at the end, (2) deleting all occurrences of a key, and (3) reversing the list — and explain why insert-at-end is not O(1) like a stack push.

(1) O(n), (2) O(n), (3) O(n). Insert-at-end is O(n) because a singly linked list only stores a head pointer, so you must traverse every node to find the tail before linking the new node. A stack push is O(1) because it inserts at the head, which is directly accessible.