Sorts + Inheritance

Sort

100

What is the time complexity for selection sort? (worst case)

O(n^2)

200

Consider the selection sort algorithm applied to the array [45, 18, 27, 36, 14].

After the algorithm completes its sorting process:

a. The array will be sorted in ascending order, and the minimum element will be at the beginning.

b. The array will be sorted in descending order, and the maximum element will be at the end.

c. The array will remain unchanged as selection sort does not modify the original order.

d. The array will have random elements rearranged due to the selection sort process.

Choose the correct option:

1. a
2. b
3. c
4. d

a. (p easy imo)

300

Discuss a scenario where selection sort might be preferred over other sorting algorithms, considering both time and space complexity.

Useful with small datasets, minimal memory constraints and the datasets partially sorted

400

Consider an array of distinct integers [38, 92, 47, 19, 73, 10, 56]. During the second pass of the selection sort algorithm, identify and compare the elements in the unsorted region. Provide the specific comparisons made and the resulting changes in the array after this pass.

• 10 is swapped with 32 in the first pass
• 19 is swapped with 92 in the second pass

Final Array:

10, 19, 47, 92, 73, 38, 56

Recursion

100

What does this do?

public static int val(List ints) {

     if(ints.size() == 0) {

          return 0;

     } else {

          return ints.get(0) + val(ints.subList(1, ints.size()));

     }

}

Sums integers in a dataset with recursive approach.

200

What does foo(5,9) output?

public static int foo(int a, int b) {

    if(b <= 1 || b <= a) {

        return 1;

    }

    return (b - a) * foo(a,b-1);

}

24

300

What gets printed out?

public void run() {

int n = 2;

n = factorial(n);

n = n + factorial(n);

System.out.println(n);

}

public int factorial(int n) {

if (n==1) {

return 1;

}

else {

return n * factorial(n - 1);

}

}

4

400

Briefly explain what this method does. How many print statements will execute if there are 3 disks and 3 poles?

public static void towers(int disk, String starting, String intermediate, String destination) {
        //the base case. if
        if (disk == 1) {
            System.out.println("Move disk 1 " + "from rod " + starting +" to rod " + destination);
        } else {
            towers(disk-1, starting, destination, intermediate);
            System.out.println("Move disk " + disk + " from rod " + starting +" to rod " + destination);

            towers(disk-1, intermediate, starting, destination);

        }

• first pass: 42 bubbles up to index 2, 93 bubbles up to index 5
• second pass: 18 bubbles up to index 1, 56 bubbles up to index 4
• third pass: 42 bubbles up to index 3
• fourth pass: already sorted 

final array at fourth pass:

[8, 18, 27, 42, 56, 93]

Logic

100

The boolean expression (A || B) && A is true when...

whenever A is true

200

For what values of n will this code generate output?

//int n declaration 

if(!(n > 50 && n < 100)

     sout("Hello");

For all values of n NOT in the range 51 - 99

300

Simplify !(x < 3 && y > 2) by DeMorgan's Laws

!(x < 3) || !(y > 2)

simplifies to

(x >= 3 || y <= 2)

Inheritance

100

What is the primary purpose of inheritance in object-oriented programming?

• a. To enable code reuse and promote modularity
• b. To reduce the size of the codebase.
• c. To eliminate the need for polymorphism.
• d. To enforce encapsulation.

A.

200

Consider a scenario where a subclass overrides a method from its superclass. What is the term used to describe this behavior?

• a. Method hiding
• b. Method overloading
• c. Method overriding
• d. Method encapsulation

C.

300

Consider a sorted array of integers: [2, 5, 8, 12, 16, 23, 28, 32, 40]. Perform a binary search to find the index of the element 23. Indicate the steps involved in the search process, including the values of the low, high, and mid indices at each step.

Choose the correct option:

a. First step: low=0, high=8, mid=4
Second step: low=4, high=8, mid=6
Third step: Element found at index 5.

b. First step: low=0, high=8, mid=4
Second step: low=4, high=8, mid=5
Third step: Element found at index 5.

c. First step: low=0, high=8, mid=4
Second step: low=4, high=8, mid=7
Third step: Element found at index 6.

d. First step: low=0, high=8, mid=5
Second step: low=5, high=8, mid=6
Third step: Element found at index 5.

b. First step: low=0, high=8, mid=4
Second step: low=4, high=8, mid=5
Third step: Element found at index 5.

400

Consider a car management system designed for an AP Computer Science A project. The system includes classes such as Automobile, Truck , Car, and Wheels. 

Explain the UML relationships between these classes.

Example Response:

Make the automobile the superclass. Have truck and cars the child classes of automobile. Have wheels be an object in the automobile class.

Everything else

100

List<String> list = new ArrayList<String();

list.add("a");

list.add("b");

list.set(1,"c");

list.add(2, "d");

list.set(2,"e");

list.add("g");

System.out.println(list);

[a,c,e,g]

200

If string1 and string2 are equal, then string1.compareTo(string2)___________. Fill in the blank with the correct option.

==0

300

In Java, how can you create an ArrayList that can only store objects of a specific class, for example, Person?

a) ArrayList<Object> personList = new ArrayList<>();

b) ArrayList<? extends Person> personList = new ArrayList<>();

c) ArrayList<Person> personList = new ArrayList<>();

d) ArrayList<? super Person> personList = new ArrayList<>();

C.

400

for(int i = 0; i <= 3; i++){

for(int j = 1; j <= 5; j+=2)

{

System.out.println("*");

}

}

How many times is * printed?

9 times