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;}

Question 6 options:

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

Question 10 options:

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

Question 12. 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

1.O(n)

2.O(n2)

3.O(log n)

4.O(1)

5.O(n3)

6.O(2n)

Question 22. Put the following time complexities in order from smallest to largest.

cubic

constant

linear

quadratic

exponential

logarithmic