COEN 352 Yan Liu Data structure and algorithm Sample Midterm Solution sample new update Concordia University

COEN 352Yan Liu Data structure and algorithm
Sample Midterm Solution sample new update
Concordia University


.

, COEN 352 Midterm Exam
Time allowed 70 minutes; Attempt all questions; Total marks 90; Questions equally weighted.
Name: ID: _ Signature:

Q01. Suppose that a client performs a sequence of stack push and pop operations. The push operations
put the integers 0 through 9 in order onto the stack; the pop operations print out the return values. Which
of the following sequences - if any - could not occur?

a. 2 1 4 3 6 5 8 7 9 0
b. 4 6 8 7 5 3 2 9 0 1
c. 2 5 6 7 4 8 9 3 1 0
d. 1 2 3 4 5 6 9 8 7 0
e. 4 3 2 1 0 5 6 7 8 9

Q02. What does the following code fragment print when N is 43?

Stack<Integer> stack = new Stack<Integer>();
while (N > 0)
{ stack.push(N % 2);
N = N/2; }
for (int d : stack) StdOut.print(d);
StdOut.println();

a. 101010
b. 001011
c. 101000
d. 101111
e. 101011

Q03. The order of time complexity of enqueue-ing an element into a priority queue (with n elements):

a. is independent of the particular implementation
b. is O(1) for any implementation using ordered arrays
c. is always O(nlogn)
d. is always the same as the order of complexity of the dequeue operation
e. none of the above

Q04. Suppose x is a linked-list node and not the last node on the list. What is the effect of the following
code fragment?
x.next = x.next.next;

a. Deletes from the list the node immediately preceding x.
b. Deletes from the list the node immediately following x.
c. Deletes from the list the node following the node following x.
d. Deletes from the list the node immediately following the node preceding x.
e. Has no effect: neither deletes nor adds a node to the linked list.




Page 1 of 4