Cumulative Test Study Guide (covering all chapters from Quiz 1 & 2
and Chapters 12 & 13)
You are still responsible for knowing the topics from Quiz 1 & 2
(in fact, I will cull many questions on the test from those study
guides...)
In addition you should be familiar with the following:
- From Chapter 12
- Special issues related to 2-dimensional arrays. (how to find
out the size of both dimensions)
- BufferedReader and PrintWriter classes
- From Chapter 13
- The basic idea of O(N), how to estimate it, and what the
consequences of it are
- Know the differences, advantages, disadvantages, and how to
code binary seach and linear search
- Sorts. How to use them, how they are written, what are
the plusses and minuses to each one
- SelectionSort
- InsertionSort
- QuickSort
The test will be in two parts:
- Part 1 (given on Thursday, 4/29) will be all multiple
choice. This will count for half of the points of the entire
test. At LEAST half of the questions will come from or be very
closely related to the questions in the cumulative quiz 1, cumulative
quiz 2 and the following multiple choice questions. They may or
may not be the ones used on the previous quizzes, so you should study
all of them.
- Part 2 (given on Friday, 4/30) will be all free response.
This will count for the other half of the points for the entire
test. To get an idea of what problems will be included on this
portion, review the worksheets (including worksheet 3, even though it
was not collected) as more than a few of these problems, or slightly
modified versions of them will find their way to the exam.
More multiple choice questions (covering Chapters 12 & 13)
1) Given a BufferedReader called foo, which of the
following will return true if the end of the file is reached? A)
foo.endOfFile() B) foo == null C) (foo.readLine()==null) D) (foo.eof()
== true) E) none of the above
2) In the average case of each of these sorts, which
of the following algorithms is the fastest for a large set of data?
A) QuickSort B) InsertionSort C) BubbleSort D) SelectionSort E) they
all should be about the same
3) At the end of the first pass of the inner loop of
the SelectionSort as defined below, what can be said for sure?
public static void
selectionSort(int[] data) {
for (int a =
data.length-1; a > 1; a--) {
for (int b = 0; b <
a;
b++) {
if (data[a] >
data[b])
{
int temp = data[b];
data[b] = data[a];
data[a] = temp;
}}}}
A) all the data is
sorted
B) the largest value is at the last position in the array C) the
smallest value is at the last position in the array D) A & B E)
no conclusions can be made
4) In order to find data from an unordered array,
which search algorithm will be the quickest to find the data?
A) linear search B)
binary search C) bubble sort D) quick sort E) merge sort
5) What is the approximate O(N) for the following code?
public int findit(int[] items, int
item) {
for (int a= 0; a < items.length;
a++) {
if (items[a] == item) return a;
}
return -1;
}
A) 1 B) N C) N^2 D) N*Log(N) E) N!