Please answer all parts of the question Let Q be a non-empty queue and S be an e

Question

Please answer all parts of the question

Let Q be a non-empty queue and S be an empty stack. Using the stack and queue ADT functions and the stack S, write an algorithm to reverse the order of the elements in Q. (ii) Draw the 7-item hash table resulting from hashing the keys 19, 26, 13, 48, and 17 using the hash function h(x) = x mod 7. Assume that collisions are handled by double hashing using a second hash function h'(x) = 5 - (x mod 5). Assume that the LIST ADT is implemented using a doubly linked list. Using pseudo-code, describe the implementation of the method insert Before(p, e) of the LIST ADT. Suppose that the data stored at each node in a binary search tree is a positive integer. Write a recursive algorithm that finds the sum of all values, which are less than a given value x in the binary search tree.

Explanation / Answer

Ans : 2 (a) (i) : The Pesudo code:

x = 0
while [not queue.isempty()] do
... x = x + 1
... e = queue.get() /* gets and *removes* next element */
... stack.push(e);
end while
while x > 0
... x = x - 1
... e = stack.pop());
... queue.add(e);
end while

In the first while above , copies all entries from the queue into the stack, and counts them where as the second while copies x elements from the stack back into the queue. Since the stack is LIFO ("last-in, first-out"), it reverses the order of the elements. That's a natural side effect of storing entries in a stack.

Using x as a counter means that you don't depend on the stack being empty. The stack has the same contents on completion as it did upon entry.

ii)

2 b) PSEUDO CODE

     InsertBefore takes p, a pointer to the element, e the element to insert. Inserts e before p.

InsertBefore(L, p, e)
1 if p = nil
2 then error "Element to insert before doesn't exist"
3   else if head[L] = p
4     then head[L] e
5     prev[e] prev[p]
6     prev[p] e
7     if prev[e] <> nil
8       then next[prev[e]] e
9     next[e] p

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.