Question 1
Which of these data structures allow duplicate values? Choose all that apply.
Queue
Set
Priority queue
List
Question 2
Which of these data structures is most similar to a dictionary, in which more information about an entity is retrieved based on its key?
Stack
Set
Priority queue
Map
Question 3
If you add several objects to a HashSet and it appears that there are multiple copies of the same item, what have you most likely forgotten to do?
override toString()
declare a class field as the key
override equals() and hashcode()
implement Serializable
Question 4
In order to use a TreeMap, which of the following must be true?
the keys must be a class that implements Comparable or you must pass the TreeMap constructor a Comparator for the key objects
the values must be a class that implements Comparable or you must pass the TreeMap constructor a Comparator for the value objects
the keys must be numeric
all of these
Question 5
Which of these is approximately the largest value of n that is feasible for an exponential algorithm on modern computers?
n=3
n= 30
n=300
n=3000
Question 6
What is the time complexity of this method?
public static intnumberOfLargest(int[] data)
{
int max = Integer.MIN_VALUE;
int count = 0;
for (int d: data)
{ if (d > max) { max = d; } }
for (int d: data) { if (d == max) { count++; } }return count;}
constant
quadratic
logarithmic
linear
Question 7
What is the time complexity of this method? public static void printMultiplicationSquare(int n) { for (inti=1; i<= n; i++) { for (int j=1; j<=n; j++) { System.out.print(i*j + "\t"); } System.out.println("\n"); }}
constant
quadratic
logarithmic
linear
Question 8
You need to choose a sorting algorithm that is as fast as possible, and memory space is in short supply. Which of these is the best choice?
bubble sort
merge sort
heap sort
they are all equivalent
Question 9
Which of these sorting algorithms only works on integers? Choose all that apply.
quick sort
bucket sort
heap sort
radix sort
Question 10
What does this array look like after the first pass of bubble sort? Assume the values are being sorted into ascending (smallest-to-largest) order.
15, 27, 3, 9, 17, 46, 14, 22, 8
15, 27, 3, 9, 17, 14, 22, 8, 46
15, 3, 9, 17, 27, 14, 22, 8, 46
3, 8, 9, 14, 15, 17, 22, 27, 46
15, 27, 3, 9, 17, 8, 14, 22, 46
Question 11
Which of these are characteristics of a heap? Choose all that apply. (Be careful not to confuse heaps with binary search trees.)
each node has at most two children
every node is greater than both of its children
every node is larger than its left child and smaller than its right child
the largest value is in the bottom-right node
You need to write a program that frequently adds and removes items at the beginning of a list. Is it better to use an ArrayList or a LinkedList?
ArrayList
LinkedList
the choice doesn't matter in this case
Question 13
You need to write a program that frequently retrieves items from specific indices in a list. Is it better to use an ArrayList or a LinkedList?
ArrayList
LinkedList
the choice doesn't matter in this case
Question 14
You need to write a program that frequently iterates through all the items in a list. Is it better to use an ArrayList or a LinkedList?
ArrayList
LinkedList
the choice doesn't matter in this case
Question 15
If an ArrayList has reached its capacity and you try to add another item, there is a performance hit while a new, larger list is created and the values from the current list are copied over to it. How can this delay be avoided?
add all the items at once
set the initial capacity of the list to an estimate of the number of items it will need to hold
multi-thread your application
add items to the beginning rather than the end of the list
Question 16
What is the third value in the breadth-first traversal of this binary search tree?
2
7
14
23
Question 17
What is the third value in the inorder traversal of this binary search tree?
12
14
10
23
Question 18
What is the third value in the preorder traversal of this binary search tree?
12
14
2
16
Question 19
What is the third value in the postorder traversal of this binary search tree?
23
46
12
16
Question 20
LinkedHashSet
HashSet
TreeSet
1. Very efficient; items are stored unordered
2. Items are stored in the order they are added
3. Items are stored in their 'natural' ordering
Question 21
Match the following complexity terms with their Big-O notation.
Constant
logarithmic
cubic
exponential
linear
quadratic
6. O(2n)
Question 22
Put the following time complexities in order from smallest to largest.
cubic
constant
linear
quadratic
exponential
logarithmic.