Programming & Computer Science Answers

1. Explain briefly how to insert a given key in a binary search tree

2. Find following questions are True or False? If false write the correct answer:
a. The insertion operation in a binary search tree has a running time of O(1) in the worst case.
b. In a stack implemented using an array, the push operation is O(log n) in the worst case.
(Assume the array is not full)
c. n^2 logm + n^3 is O(n^3)
d. n^2 + n^3 = O(n^3)
e. If we sort n numbers using quicksort, then the worst case running time is O(n).
f. A (2,4) tree is also a binary search tree.
g. The height of a red black tree with n entries, is always less than the height of every binary
search tree on the same set of entries.
h. An undirected graph with n vertices has at least n edges.
i. An undirected graph with n vertices and n + 2 edges must always contain a cycle.
j. The worst case running time of sorting n elements using heapsort is O(n log n)

1. An n-­‐vertex directed acyclic graph G is compact if there is some way of numbering the vertices
of G with the integers from 0 to n ­‐ 1 such that G contains the edge (i ; j) if and only if i < j, for all i;
j in [0; n ‐1]. Give an O(n^2) -­ time algorithm for detecting if G is compact.
2. Describe a recursive method that counts the number of leaves in a given binary tree.
3. Describe a non‐recursive method that counts the number of leaves in a given binary tree.

1. A desk can be modelled as a simple data structure with the following ADT Desk:
• add(x) puts item x on top of the desk
• process() processes the top item on the desk and removes it (either sending it to someone else or
just throwing it away!)
• find(x) finds and retrieves the item x if it’s somewhere on the desk
• scan() looks at the top item on the desk, but doesn’t remove it
i). What data structure can you think of that is most like the ADT Desk? Give reasons.
ii). Write out in pseudocode in the space below how you would implement the find(x)
method in the ADT Desk above, using only stacks. Assume the standard methods for a stack have
already been defined.
iii). What is the running time of your method above? explain.

1. The following code fragment operates on a stack S initially empty. What is the output of
this code fragment?
S.push(2);
S.push(4);
S.push(6);
S.push(8);
while (! S.isEmpty() )
System.out.println(S.pop());

2. The following code fragment operates on a queue Q initially empty. What is the output of
this code fragment?
Q.enqueue(2);
Q.enqueue(4);
Q.enqueue(6);
Q.enqueue(8);
while (! Q.isEmpty() )
System.out.println(Q.dequeue());

3.
i) Describe in detail (using pseudocode) the implementation of a priority queue based on a sorted
array. Show that your implementation achieves O(1) for operations min and removeMin, and O(n)
for insertions.
ii) Explain in a high-level way as well as in pseudo code how the removeMin operation works in
a min-heap.
iii). Explain in a high-­level way and also using pseudo-­code how to insert a key into a hash
table that uses linear probing for collisions. Assume the hash table is implemented using an array.

At which positions in a heap might the largest key be found?