Question 1

What must occur when a wrapped item is accessed with the peek or pop method in a priority queue?

Accepted Answer

When an item is accessed with the peek or pop method in a priority queue, it must be unwrapped in order to access the actual value that was wrapped for storage in the priority queue.

Question 2

In the following code for the pop method for a linked queue implementation, what is the missing code?
Def pop(self):
OldItem = self.front.data
Self.front = self.front.next
If self.front is None:
Self.rear = None
< missing code >
Return oldItem

Accepted Answer

The missing code should decrease the size of the queue by 1 after removing an item, so the correct choice is to decrement the size by 1 using the statement "self.size -= 1". Choices A, B, and D are incorrect because they don't correctly update the size of the queue.

Question 3

What is the solution to achieving good performance for both the add and pop methods in the array implementation of a queue?

Accepted Answer

A circular array implementation allows for both add and pop methods to have good performance as it avoids wasted space and keeps the items in contiguous memory locations. The front and rear pointers can wrap around the ends of the array, allowing the queue to function as if it has no fixed endpoints.

Question 4

What can you do if items in a priority queue cannot use the comparison operators?

Accepted Answer

Using a wrapper class allows us to customize the comparison for the objects in the queue, and use them in the priority queue. Removing them, removing in FIFO order or putting them in the back of the queue may not be viable options if these items are important or necessary for the functionality of the program.

Question 5

In the following code for the __eq__ method for the Comparable class, what is the missing code? def __eq__(self, other):
If self is other: return True
If type(self) != type(other): < missing code >
Return self.priority == other.priority

Accepted Answer

If the two objects are not of the same type, they cannot be compared and so the method should return False, as they are not equal.

Question 6

Which of the following is NOT true of a priority queue?

Accepted Answer

Priority queues remove items based on their priority order, not in the order they were added. Therefore, items of higher priority are removed before those of lower priority, regardless of when they were added. However, there is no guarantee that items of equal priority will be removed in a specific order, such as FIFO.

Question 7

What is the initial value of the front and rear instance variables in the linked queue?

Accepted Answer

In the linked queue implementation, the front and rear instance variables are initially set to None as there are no nodes in the queue.

Question 8

In a priority queue, what does the add method do when handling a new item and the new item is greater than or equal to the item at the rear?

Accepted Answer

In a priority queue, items are organized in a way that ensures the highest priority item is always at the front. Therefore, if the new item is greater than or equal to the item at the rear (i.e. lowest priority), it can be added to the rear of the queue without disturbing the order. Therefore, the add method will add the new item to the rear.

Question 9

In the following code for the add method for a linked queue implementation, what is the missing code? def add(self, newItem):
NewNode = Node(newItem, None)
If self.isEmpty():
Self.front = newNode
Else:
Self.rear.next = newNode
< missing code >
Self.size += 1

Accepted Answer

To add a new node to the rear of the queue, we must set the "next" attribute of the current last node in the queue to the new node, and then set the "rear" attribute of the queue to the new node. Therefore, the missing code should be "self.rear = newNode", as this updates the "rear" attribute of the linked queue to the new node.

Question 10

In the linked priority queue, what is the time and space analysis for the add method?

Accepted Answer

The time complexity for the add method in a linked priority queue is O(n) because, in the worst case, the method may need to traverse the entire list to find the correct insertion point for maintaining the priority order. The space complexity is not explicitly mentioned in the options, but it is generally O(1) for adding a single element, as only a constant amount of extra space is required for the new node, regardless of the size of the input.

Quiz 8: Queues

What must occur when a wrapped item is accessed with the peek or pop method in a priority queue?

In the following code for the pop method for a linked queue implementation, what is the missing code? Def pop(self) : OldItem = self.front.data Self.front = self.front.next If self.front is None: Self.rear = None < missing code > Return oldItem

What is the solution to achieving good performance for both the add and pop methods in the array implementation of a queue?

What can you do if items in a priority queue cannot use the comparison operators?

In the following code for the eq method for the Comparable class, what is the missing code? def eq(self, other) : If self is other: return True If type(self) != type(other) : < missing code > Return self.priority == other.priority

Which of the following is NOT true of a priority queue?

What is the initial value of the front and rear instance variables in the linked queue?

In a priority queue, what does the add method do when handling a new item and the new item is greater than or equal to the item at the rear?

In the following code for the add method for a linked queue implementation, what is the missing code? def add(self, newItem) : NewNode = Node(newItem, None) If self.isEmpty() : Self.front = newNode Else: Self.rear.next = newNode < missing code > Self.size += 1

In the linked priority queue, what is the time and space analysis for the add method?

Quiz 8: Queues

What must occur when a wrapped item is accessed with the peek or pop method in a priority queue?

In the following code for the pop method for a linked queue implementation, what is the missing code? Def pop(self) : OldItem = self.front.data Self.front = self.front.next If self.front is None: Self.rear = None < missing code > Return oldItem

What is the solution to achieving good performance for both the add and pop methods in the array implementation of a queue?

What can you do if items in a priority queue cannot use the comparison operators?

In the following code for the __eq__ method for the Comparable class, what is the missing code? def __eq__(self, other) : If self is other: return True If type(self) != type(other) : < missing code > Return self.priority == other.priority

Which of the following is NOT true of a priority queue?

What is the initial value of the front and rear instance variables in the linked queue?

In a priority queue, what does the add method do when handling a new item and the new item is greater than or equal to the item at the rear?

In the following code for the add method for a linked queue implementation, what is the missing code? def add(self, newItem) : NewNode = Node(newItem, None) If self.isEmpty() : Self.front = newNode Else: Self.rear.next = newNode < missing code > Self.size += 1

In the linked priority queue, what is the time and space analysis for the add method?

In the following code for the eq method for the Comparable class, what is the missing code? def eq(self, other) : If self is other: return True If type(self) != type(other) : < missing code > Return self.priority == other.priority