Courses‎ > ‎APCS - Term 1‎ > ‎Konstantinovich‎ > ‎

2019-05-14 Exam Questions

posted May 14, 2019, 6:19 AM by Konstantinovich Samuel   [ updated May 14, 2019, 8:28 AM ]
Do Now:
A. Given a sorted list of 1's and 0's, what is the runtime of finding the rightmost 0?
sample data:

B. Given a 2d array of lists that are sorted 1's and 0's, at some point, the lists may stop containing 0's.
If any row has no 0's, then no future row can have 0's.
What is the runtime of finding the rightmost 0 in the last list that contains 0's ?
sample data:
[   [0,0,0,0,0,0,1,1,1,1],
    [1,1,1,1,1,1,1,1,1]    ]

For these problems, work with a partner and come up with a solution. Then confirm with other groups.

1. Suppose you watched a cartoon that had a really cool thing that was both a cat and a bus. Now you decided
to make this for your java project. You create:
public class Cat {/∗ not shown ∗/}
public class Bus {/∗ not shown ∗/}
Which describes the correct way to make a class CatBus such that: CatBus is-a Cat, and CatBus is-a Bus?
A. You can have CatBus extend both Cat and Bus.
B. You can have CatBus extend Cat, and CatBus implement Bus.
C. You can have CatBus extend Cat, and make Bus extend CatBus.
D. You can have Cat extend CatBus, and Bus extend CatBus.
E. None of these choices.

2. (3 points) What is the output of the following code?
int x = 5, y = 2;
System.out.println( x / y - (double)(x / y));

A. 0.0        B. 0.5        C. -0.5        D. -2.5        E. none of these

3. (3 points) Given an initialized LinkedList<Integer>c, that contains N elements: What is the runtime of the following
int total = 0;
for(int i = 0; i < c.size(); i++)
total += c.get(i);

A. O(N )        B. O(log(N ))        C. O(N log(N ))        D. O(N^2 )        E. none of the choices.

4. (3 points) Suppose you call a binary search function on a sorted list with 2000 elements. What is the maximum number
of elements that must be examined to determine if a specified number is stored in the list or not?
A. 2000     B. 1000     C. 12     D. 11     E. 10

5. (3 points) What is the runtime of converting an array of values into a heap?
A. O(1)         B. O(logn)         C. O(n)         D. O(nlogn)

6. (3 points) In a heapsort there are two components, first heapify the array, then remove all elements one after another to
sort them. Which of the following is true about these two steps?
A. The heapify step is always faster than removing all the elements.
B. The heapify step is always slower than removing all the elements.
C. The heapify step is always the same speed as removing all the elements.
D. The steps speeds depend on the order of the data.

7. (3 points) An n by n 2d array of char contains period ’.’ and ’x’. The left most several columns have one or more ’x’ at
the top of the column, with all of the ’.’ below them. The remaining columns are filled with ’.’ entirely. e.g.

What is the worst case big-O for the number of values to examine in order to find the position of the lowest x in the
right most column that has x in it?
A. O(logn)     B. O(n)     C. O(nlogn)     D. O((logn)^2 )     E. O(n^2 )

8. (3 points) Given an array with the values: 1 3 2 5 13 8 21, which of the values will not be found if you ran a binary
search on the array?
A. 1         B. 3         C. 5         D. 13         E. 21