True/False (13)

Chapter 11 - Queue, Deque, and Priority Queue Implementations

1. In a linked chain implementation of a queue, when both the firstNode and lastNode entries are null, the chain is empty.

2. In a linked chain implementation of a queue, the enqueue operation requires a traversal to the end of the chain to insert a new entry onto the queue.

3. In a linked chain implementation of a queue, the enqueue operation could potentially be dependent on the other entries and will require a search.

4. In an array-based implementation of a queue, keeping the front entry of the queue at queue[0] is inefficient.

5. In an array-based implementation of a queue, inserting and deleting entries is accomplished using modulo arithmetic.

6. In a circular array-based implementation of a queue, frontIndex is equal to one more than backIndex when the queue is empty.

7. In a circular array-based implementation of a queue, frontIndex is equal to one less than backIndex when the queue is full.

8. In a circular array-based implementation of a queue, you cannot use only frontIndex to determine when a queue is full.

9. When a circular linked chain is used to represent a queue, it is not necessary to maintain a firstNode data field.

10. In a circular array-based implementation of a queue, the available locations are not contiguous.

11. When a circular linked chain has one node, the node references itself.

12. Each node in an ordinary linked chain references only the next node.

13. You need two external references for a circular doubly linked chain, one for the firstNode and

    one for the lastNode.

Short Answer (5)

1. In an array-based implementation of a queue, if waitingList is the name of the array, and the index to the last entry in the queue is called backIndex, write a single assignment statement to update backIndex to add an entry to the queue.

2. In an array-based implementation of a queue, if waitingList is the name of the array, and the index to the last entry in the queue is called frontIndex, write a single assignment statement to update frontIndex to remove an entry to the queue.

3. In a circular array-based implementation of a queue, if waitingList is the name of the array, and the index to the last entry in the queue is called backIndex, write a single assignment statement to update backIndex to add an entry to the queue.

4. In a circular array-based implementation of a queue, if waitingList is the name of the array, and the index to the last entry in the queue is called frontIndex, write a single assignment statement to update frontIndex to remove an entry to the queue.

5. In a circular array-based implementation of a queue, explain why checking for frontIndex equal to backIndex + 1 does not work.

Multiple Choice (31)

1. If we use a chain of linked nodes with only a head reference to implement a queue which statement is true?

   1. You must traverse the entire chain to access the last node.

   2. Accessing the last node is very inefficient.

   3. Both a & b

   4. None of the above

2. In a linked chain implementation of a queue, an external reference to the last node in the chain is called a(n)

   1. tail reference

   2. last node

   3. linked reference

   4. final node

3. To efficiently remove a node at the end of a linked chain implementation of a queue requires as

a. b. c. d.

4. In the a. b. c. d.

5. In the a. b. c. d.

tail reference traversal extra reference in the node pointing to the previous node none of the above

linked chain implementation of a queue, the chains first node contains the queues front entry the queues back entry both a & b

none of the above

linked chain implementation of a queue, the chains tail last node contains the queues back entry the queues front entry both a & b

none of the above

6. In a linked chain implementation of a queue, when the queue is empty

   1. the firstNode is null

   2. the lastNode is null

   3. both a & b

   4. none of the above

7. In a linked chain implementation of a queue, the performance of the enqueue operation is

   1. O(1)

   2. O(log n)

   3. O(n)

   4. O(n2)

8. In a linked chain implementation of a queue, the performance of the getFront operation is

   1. O(1)

   2. O(log n)

   3. O(n)

   4. O(n2)

9. An array whose index of the first location follows the index its last one is call a. circular

   b. following c. round d. oval

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

    1. maintain a count of queue items

    2. check for frontIndex equal to backIndex

    3. wait for an arrayFullExcetion to be thrown

    4. all of the above

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

    1. leave one array location unused

    2. check for frontIndex equal to backIndex

    3. wait for an arrayFullExcetion to be thrown

    4. all of the above

12. In a circular array-based implementation of a queue, the initial size of the array should be

    1. one more than the queues initial capacity

    2. one less than the queues initial capacity

    3. two more than the queues initial capacity

d. two less than the queues initial capacity

13. In a circular array-based implementation of a queue implementation where one unused location is used to differentiate between the front and back of the queue, the frontIndex is _____ than the backIndex.

    1. two more

    2. one more

    3. one less

    4. two less

14. In a circular array-based implementation of a queue, what is the performance when the enqueue operation does not resize the array?

    1. O(1)

    2. O(log n)

    3. O(n)

    4. O(n2)

15. In a circular array-based implementation of a queue, what is the performance when the enqueue operation must resize the array?

    1. O(n2)

    2. O(n)

    3. O(log n)

    4. O(1)

16. In a circular array-based implementation of a queue, what is the performance when the enqueue operation if you amortize the cost of resizing the array over all additions to the queue?

    1. O(1)

    2. O(log n)

    3. O(n)

    4. O(n2)

17. In a circular array-based implementation of a queue, what is the performance when the dequeue operation ?

    1. O(1)

    2. O(log n)

    3. O(n)

    4. O(n2)

18. In a ______ the last node references the first node.

    1. circular linked chain

    2. array based queue

    3. array based circular queue

d. linked chain

19. A linked chain whose last node is null is sometimes called a(n)

1. linear linked chain

2. circular linked chain

3. null terminated linked chain

4. all of the above

20. In a circular linked chain, when a node is removed from the queue

1. it is deallocated

2. it is moved to a separate list

3. it is ignored

4. none of the above

21. A two-part circular linked chain implementation of a queue

1. conceptually has two lists

2. uses a freeNode reference for the first available node that follows the queue

3. has nodes that form the queue followed by nodes that are available for use in the queue

4. all of the above

22. A two-part circular linked chain implementation of a queue

1. is initialized with no available nodes

2. keeps nodes that are deallocated for future use

3. allocates new nodes on demand when there are no available nodes

4. all of the above

23. How can we tell if a two-part circular linked chain queue is empty?

1. both the queueNode and freeNode reference the same node

2. the freeNode is one node behind the queueNode

3. the freeNode is one node in front of the queueNode

4. the empty field is set to true

24. In a two-part circular linked chain implementation of a queue

a. b. c. d.

25. When a. b. c.

queueNode references the front node of the queue freeNode references the node that follows the queue the queue is empty if queueNode equals freeNode all of the above

adding a node to a two-part circular linked chain implementation of a queue first check if a node is already available in the chain check to see if the linked chain needs resized allocate a new node and assign the reference to freeNode

d. all of the above

26. When adding a node to a two-part circular linked chain implementation of a queue we insert the new node into the chain

1. after the node that freeNode references

2. before the node that freeNode references

3. it has nothing to do with the location of freeNode

4. none of the above

27. When

    1. the entry at the front of the queue is returned

    2. the node is moved to the part of the chain that is available for the enqueue method

    3. the queueNode is advanced

    4. all of the above

28. In a two-part circular linked chain implementation of a queue, what is the performance when

the dequeue operation ?

1. O(1)

2. O(log n)

3. O(n)

4. O(n2)

30. When is called a(n)

removing a node from a two-part circular linked chain implementation of a queue

29. When

1. when you frequently add an entry after removing one

2. when you rarely add entries after removing one

3. when you are space constrained

4. when you dont want the garbage collector running

would you choose a two-part circular chain over a circular chain?

a linked chain contain nodes that reference both the next node and the previous node, it

1. doubly linked chain

2. ordinary chain

3. multi-linked chain

4. two-way linked chain

31. In a doubly linked chain implementation of a queue, what is the performance when the dequeue operation ?

1. O(1)

2. O(log n)

3. O(n)

4. O(n2)