Take this Exam: A-Level Computer Science: Algorithms and Data Structures | Zestly

Question 1

An array [5, 2, 9, 1, 5, 6] is being sorted using bubble sort. What is the state of the array after the first full pass?

Accepted Answer

2, 5, 1, 5, 6, 9

Answer

1, 2, 5, 5, 6, 9

Answer

1, 5, 2, 9, 5, 6

Answer

5, 2, 1, 5, 6, 9

Question 2

A recursive function is defined as: FUNCTION f(n) IF n = 0 THEN RETURN 1 ELSE RETURN n * f(n-1) ENDIF. What happens if the base case 'IF n = 0' is removed?

Accepted Answer

The program crashes due to stack overflow

Answer

The function returns 0

Answer

The function returns 1

Answer

The function returns n

Question 3

A class BankAccount stores a balance and provides methods deposit and withdraw. The balance field is declared private, so no code outside the class can change it directly. Which principle is being used, and what does it buy?

Accepted Answer

Encapsulation: the internal state can only be changed through methods that enforce the rules, so no outside code can set a balance the class would have refused.

Answer

Inheritance: a subclass can reuse the balance field without rewriting it.

Answer

Polymorphism: deposit and withdraw can accept arguments of different types.

Answer

Abstraction: the balance is left out of the model because it is not relevant to it.

Question 4

Which of the following describes an undecidable problem?

Answer

Sorting a list of integers

Answer

Finding the shortest path in a graph

Answer

Determining if an arbitrary program will eventually stop

Answer

Calculating the factorial of a number

Question 5

A binary search tree is built by inserting, in this order: 10, 5, 15, 3, 7. So 10 is the root, 5 is its left child and 15 its right child; 3 is the left child of 5 and 7 the right child of 5. The root is now deleted and replaced by its IN-ORDER PREDECESSOR, that is, the largest value in its left subtree. Which node moves to the root, and what becomes of the place it came from?

Answer

3 moves to the root, and the position left of 5 becomes empty.

Answer

15 moves to the root, and the right subtree becomes empty.

Answer

5 moves to the root, and 3 and 7 become its two children.

Answer

7 moves to the root, and the position right of 5 becomes empty.