(1).
Suppose that queue is a QueueClass object and the size of the array implementing queue is 100Also, suppose that the value of queueFront is 99 and the value of queueRear is 25.
a. What are the values of queueFront and queueRear after adding an element to queue?
b. What are the values of queueFront and queueRear after removing an element from queue?
(2).
Suppose that queue is a QueueClass object and the size of the array implementing queue is 100 Also, suppose that the value of queueFront is 99 and the value of queueRear is 99.
a. What are the values of queueFront and queueRear after adding an element to queue?
b. What are the values of queueFront and queueRear after removing an element from queue?
(3)
Suppose that queue is a QueueClass object and the size of the array implementing queue is 100 Also, suppose that the value of queueFront is 99 and the value of queueRear is 25.
a. What are the values of queueFront and queueRear after adding an element to queue?
b. What are the values of queueFront and queueRear after removing an element from queue?
(4)
Suppose that queue is implemented as an array with the special reserved slot, as described in this chapter. Suppose that the sizeof the array implementing queue is 100. Also, suppose thatthe value of queueFront is 74 and the value of queueRearis 99
a)
what are the values ofqueueFront and queueRear after adding an element to queue?
b)
what are the values ofqueueFront and queueRear after removing an element to queue? Also, what
is the position of the removed queue element?
(5).
Explain how collision is resolved using linear probing?
(6).
Explain how collision is resolved using quadratic probing?
(7).
What is double hashing?
(8).
suppose that the size of the hash table is 101 and items are inserted in the table using quadratic probing. Also, suppose that a new item is to be inserted in the table and its hash address is 30. If position 30 in the hash table is occupied and the next 4 positions given by the probe sequence are also occupied, determine where in the table the item will be inserted.
(9)
Suppose that an item is to be removed from a hash table that was implemented using linear or quadratic probing. Why wouldn't you mark the position of the item to be deleting as empty?
(10)
What are the advantage of open hashing?
(11)
Give a numerical example to show that collision resolution by quadratic probing is better than chaining?
(12)
Give a numerical example to show that collision resolution by chaining is better that quadratic probing?
(13).
Suppose that 550 items are to be stored in a hash table. If, on average in a successful search, three comparisons are needed to determine whether an item is in the table what would be the size of the hash table if
a) Linear probing is used
b) Chaining is used
(13)
Assume the following list: 7, 28, 31, 40, 5, 20. The first four keys are in order. to move 5 to its proper position, using insertion sort as described in this chapter, exactly how many key comparisons are executed?
(14)
Recall the insertions sort algorithm (contiguous version) as discussed in this chapter. Assume the following list of keys: 18, 8, 11, 9, 15, 20, 32, 61, 22, 48, 75, 83, 35, 3.
Exactly how many comparisons are executed to sort this list using the insertion sort algorithm?
(15)
Both the merge sort and quick sort algorithms sort a list by partitioning the list. Explain how the merge sort algorithm differs from the quick sort algorithm in partitioning the list.
(16)
Assume the following list of keys
18,40,16,82,64,67,57,50,37.47,72,14,17,27,35
This list is to be sorted using the quick sort algorithm as discussed in this chapter. Use pivot as the median of the first, last, and middle elements of the list.
a) What is the pivot?
b) Give the resulting list after one call to the partition procedure.
(17)
use the method buildHeap as given in this chapter to convert the following array into a heap. Show the final form of the array.
47,78,81,52,50,82,58,42,65,80,92,53,63,87,95,59, 34,37,7,20
(18)
Suppose that the following list was created by the method buldHeap during the heap creation phase of the heap sort algorithm.
100,85,94,47,72,82,76,30,20,60,65,50,45,17,35,14,28,5
Show the resulting array after two poses of the heap sort algorithm. (use heapfy method as guven in this chapter). Exactly how many key comparisons are executed during the first pass?