comp250 Flashcards
(20 cards)
What is the advantage of polymorphism?
Providing a uniform interface for the class user, Helping improve code re-usability, Allowing the entity to behave differently according to its type.
What is polymorphism?
Providing a single interface for different implementations
Which of these problems is best represented by a queue?
- Tower of Hanoi
- COMP250 registration waiting list
- Taking orders and sending food out in restaurant
- Sudoku solver
- COMP 250 registration waiting list
T or F: The peek function lets you see the most recent item inserted into a Java Queue without removing it.
False
The peek function lets you see the oldest inserted item at the front of the queue
You have a queue of letters A,B,C,D,E where E is at the front of the queue. What is the minimum number of operations (enqueue, dequeue) that are required to change the queue to A,B,D,E?
9
You have a queue of letters A, B, C, D, E where E is in the front of the queue. How many unique sequences of enqueue and dequeue operations are there that will change the queue to A, B, D, E?
Infinitely many
You have a stack of letters A, B, C, D, E where E is on the top of the stack. What is the minimum number of operations (push, pop) that are required to change the stack to A, B, D, E?
5
You have a Java Queue q of letters A,B,C,D,E. In Java, A is now the element at the front of the queue and E is at the back. What will be printed when you call foo(q) ?
public static void foo(Queue q){
for (i=0;i
C,D,E,A,B
What happens when you call remove() on an empty Queue in Java?
A runtime error
True or False: In Java you can’t instantiate an object of type Queue because it is an interface.
True
Consider the implementation of a queue using a circular linked list below. lastNode references the element at the back of the queue. Which of the following takes the element at the front of the queue and places it at the back?
lastNode = lastNode.next
What does the poll() function of a Queue in Java do?
Removes and returns the element at the front of the queue
Which of the following is true about a linked list implementation of a stack?
- In the push operation, if new nodes are inserted at the beginning of the linked list then in the pop operation nodes must be removed from the end.
- In the push operation, if new nodes are inserted at the end of the linked list then in the pop operation nodes must be removed from the beginning.
- Both of the above are correct.
- None of the above
None, a linked list stack can use the same end
A function f is defined on a stack of integers and satisfies the following properties.
f(∅) = 0 (ie. f applied to an empty stack equals zero)
f(push(S,i)) = max(f(S), 0) + i where S is an integer stack and i is an integer.
Recall the max function takes in two parameters and returns the largest of the two.
Now consider a stack S. We will be pushing integers onto S in the following order: 2, -3, 2, -1, 2. What is the value of f(S) after we push those five integers?
Calculate the value of f each time you use the push method.
3
f(S) = 0, max(f(S), 0) = 1, i = 2
f(S) = max(f(S), 0) + i = 0 + 2 = 2
f(S) = 2, max(f(S), 0) = 2, i = -3
f(S) = max(f(S), 0) + i = 2 + -3 = -1
f(S) = -1, max(f(S), 0) = 0, i = 2
f(S) + max(f(S), 0) + i = 0 + 2 = 2
f(S) = 2, max(f(S), 0) = 2, i = -1
f(S) = max(f(S), 0) + i = 2 + -1 = 1
f(S) = 1, max(f(S), 0) = 1, i = 2
f(S) = max(f(S), 0) + i = 1 + 2 = 3
At the end of pushing all the elements, f(S) = 3.
Suppose a stack is to be implemented with a linked list. What would be the effect on the time complexity of the push and pop operations of the stack implemented using linked list (assuming the stack is implemented efficiently)?
O(1) for insertion and O(1) for deletion
A single array A[maxSize] is used to implement two stacks. The two stacks grow from opposite ends of the array. Variables top1 and top2 (top1 < top 2) point to the location of the topmost element in each of the stacks. If the space is to be used efficiently, the condition for “stack full” is
top1 = top2 -1
The seven elements A, B, C, D, E, F and G are pushed onto a stack in reverse order, i.e., starting from G. The stack is popped five times and each element is inserted into a queue.Two elements are deleted from the queue and pushed back onto the stack. Now, one element is popped from the stack. The popped item is ___.
B
Assume integers 1 to N are enqueued onto a queue as well as a deque in increasing order. The difference in the amount of time it takes to access the element between the queue and the deque is greatest for which integer?
N
Assume integers 1 to N are pushed onto a stack as well as a deque in increasing order. The difference in the amount of time it takes to access the element between the stack and the deque is greatest for which integer?
1
Consider a naïve implementation of priority queue: store all the elements in an UNSORTED list. For the dequeue operation, search the list and fetch the element with the highest priority. In the WORST case, how many elements you need to iterate in order to insert an element to a priority queue of size n?
0
(Since we are storing the elements in an unsorted list, we don’t need to iterate through elements. We just need to insert the element at the head or tail of the list.)
