1. Resolving collisions by using buckets that are linked chains is called

a.separate chaining

b. bucket chaining

c.list resolution

d. joint chaining

2. Which of these statements about binary search is true?

a. Searching a sorted array is O( n ).

b. Searching an unsorted array is O( log n ).

c. Searching a sorted linked list is as efficient as searching a sorted array.

d. On each pass half the remaining elements in the list are eliminated

3. The method for removing an item from the front of a queue is called

a.dequeue

b. enqueue

c.getFront

d. none of the above

4.Given a linked list containing the following values: first -> 5 -> 10 -> 15 -> 20 ->

null, which of the following best describes what needs to happen when 10 is deleted from

the list?

a. The node containing 5 must be changed to point to the node which contains 15. Then

the node containing 10 can be deleted.

b. The value from the first node (5) is copied over the value 10. Then the first node is

deleted. Then first is set to the node that now contains 5.

c. The node containing 10 is deleted and first is changed to point to the node containing 15.

d. None of the above.

5. Linear probing

a. is used to insert values into a doubly linked list.

b. is a method of resolving collisions which uses chaining in a hash table.

c. searches linearly thru the table starting at the location specified by the hash function.

d. none of the above.

6. A data structure which exhibits LIFO behavior is known as

a. An array.

b. A stack.

c. A vector.

d. None of the above.

7. Assume we have a queue implementation which is based on using an array. We have front and back variables which identify the positions in the array where items are removed or added. The size of the array is defined by a constant named SIZE. The queue is defined to be empty when front == back. When adding an item to this queue, how would you tell when the queue was full?

a. if ((back + 1)% SIZE == front) the queue would be full

b. if ((front + 1) % SIZE == back) the queue would be full

c. if ((back + 1) == front) the queue would be full

d. if ((front + 1) == back) the queue would be full

8. In quick sort, the partition step takes at most ______ comparisons for n items.

a. n

b. n/2

c. 2n

d. logn

e. n²

9. In an array-based implementation of a queue, a possible solution to dealing with the full condition

is to

a. maintain a count of queue items

b. check for frontIndex equal to backIndex

c. wait for an arrayFullExcetion to be thrown

d. all of the above

10. Given a stack variable stk which provides a push operation that places an integer on the top of the stack, and a pop operation which removes and returns the integer from the

top of the stack, what would the stack look like, after the following code executed?

for(int k = 1; k < 10; k++)

{

if (k % 3 == 0)

stk.push( k+ stk.pop( ) );

else

stk.push( k );

}

Answer:

11. Given a queue variable que which provides an add operation which places an integer at the back of the queue, and a get operation which removes and returns the integer from

the front of the queue, what would the queue look like after the following code executed?

for(int k = 1; k < 10; k++)

{

if (k % 3 == 0)

que.add( k+ que.get( ) );

else

que.add( k );

}

Answer:

14. What is the order of complexity of the following function? Why?

int func(unsigned n)

{

int sum = 0;

int p, m;

int q = 100;

p = n;

m = n;

while ( q > 0)

{

while (m > 0) {

n = p;

while ( n > 0 )

{

sum += n;

n = n/2;

}

m = m -1;

}

q = q 1;

}

return sum;

}

Answer:

16- Write the code for implementing the Queue to see if it is full by using one unused location.

17- Write the code for the quicksort.