1. Zoltan Mesko decides to implement a Java stack using a void version of pop. (
ID: 660980 • Letter: 1
Question
1. Zoltan Mesko decides to implement a Java stack using a void version of pop.
(If the user wants to see what's on top, they need to use peek instead.) Which
trio of denitions for push, peek, and pop should Zoltan use to correctly
implement a stack?
A. public void push(T element) {
this.elements.add(0, element);
}
public T peek() {
return this.elements(0);
}
public void pop() {
this.elements.remove(0);
}
B. public void push(T element) {
this.elements.add(element);
}
public T peek() {
return this.elements(0);
}
public void pop() {
this.elements.remove(0);
}
C. public void push(T element) {
this.elements.add(element);
}
public T peek() {
return this.elements(this.elements.size());
}
public void pop() {
this.elements.remove(this.elements.size());
}
D. public void push(T element) {
this.elements.add(this.elements.size(), element);
}
public T peek() {
return this.elements(this.elements.size());
}
public void pop() {
this.elements.remove(this.elements.size());
}
2. How long does it take to get the bottom element in a stack of n elements?
A. O(1)
B. O(n)
C. O(n log(n))
D. O(n2)
3. How long does it take to get the last element in an ArrayList?
A. O(1)
B. O(n)
C. O(n log(n))
D. O(n2)
4. A binary tree (not necessarily balanced) has nodes a; b; c; and d. An in-order
traversal visits them in this order: b; c; d; a. Which of the nodes could not be
the root of the tree?
A. a
B. b
C. c
D. d
E. Any of them could be the root!
5. What is the running time for InsertionSort on an array with n elements?
A. O(1)
B. O(n)
C. O(n log(n))
D. O(n2)
6. A binary tree (not necessarily balanced) has nodes a; b; c; and d. A post-order
traversal visits them in this order: b; c; d; a. Which of the nodes is the root
of the tree?
A. a
B. b
C. c
D. d
E. Any of them could be the root!
7. An undirected graph, G, has vertices named a; b; c; d; e; f. A depth-
rst search starting at a traverses the following edges in this order:
(a; b); (b; c); (b; d); (b; e); (e; f). Which of the following edges is denitely not
in G?
A. (a; b)
B. (a; d)
C. (b; d)
D. (c; d)
8. You run BubbleSort on this array: [6; 5; 4; 4; 2; 1]. Which of the following
could not be the array part-way through the algorithm?
A. [5; 6; 4; 4; 2; 1]
B. [5; 4; 6; 4; 1; 2]
C. [5; 4; 4; 2; 1; 6]
D. [4; 4; 2; 5; 1; 6]
9. What is the running time for BubbleSort on an array with n elements?
A. O(1)
B. O(n)
C. O(n log(n))
D. O(n2)
10. How long does it take to get the middle element in an ArrayList?
A. O(1)
B. O(n)
C. O(n log(n))
D. O(n2)
The next 3 questions refer to the following:
Consider the following class:
public class Dobby implements Comparator {
public int compare(Integer a, Integer b) {
return (a / 10) - (b / 10);
}
}
11. Is this a legitimate comparator of integers?
A. Yes.
B. Only on some values of a and b.
C. No.
12. If I create a priority queue using this comparator, which of the following
elements will have the highest priority? (Meaning, which would be chosen
first to be removed from the priority queue.)
A. 16
B. 256
C. 1024
D. 2048
E. All of the above values have the same priority.
13. If I create a priority queue using this comparator, which of the following
elements will have the highest priority? (Meaning, which would be chosen
rst to be removed from the priority queue.)
A. 110
B. 112
C. 117
D. 118
E. All of the above values have the same priority.
14. How long does it take to get the biggest element in an (unsorted) ArrayList
of n elements?
A. O(1)
B. O(n)
C. O(n log(n))
D. O(n2)
15. What is the running time for SelectionSort on an array with n elements?
A. O(1)
B. O(n)
C. O(n log(n))
D. O(n2)
16. Which of the following is not an algorithm that traverses a graph starting at
a single vertex?
A. Cycle-First Search
B. Depth-First Search
C. Breadth-First Search
17. What is the running time for HeapSort on an array with n elements?
A. O(1)
B. O(n)
C. O(n log(n))
D. O(n2)
18. meeses is a Linked List with 12 elements. Which of the following will always
do the same as:
System.out.println(meeses.get(2));
A. System.out.println(meeses.getFirst());
B. System.out.println(meeses.getTail().getFirst());
C. System.out.println(meeses.getTail().getTail().getFirst());
D. System.out.println(meeses.getTail().getTail().getTail().getFirst());
19. How long does it take to get the top element in a stack of n elements?
A. O(1)
B. O(n)
C. O(n log(n))
D. O(n2)
20. An undirected graph, G, has vertices named a; b; c; d; e; f. A breadth-
rst search starting at a traverses the following edges in this order:
(a; b); (a; c); (b; d); (b; e); (b; f). Which of the following edges is denitely not
in G?
A. (a; c)
B. (a; d)
C. (f; b)
D. (f; d)
Explanation / Answer
1. D
2. B
3. B
4. A
5. C
6. A
7. D
8. D
9. D
10.A
11.C
12.A
13.A
14.B
15.D
16.A
17.C
18.A
19.A
20.B
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.