Deck 8: Queues

Question 1

The structure of a queue lends itself to either an array implementation or a linked implementation.

Answer 1

True

Question 2

Performing a pop operation on an empty queue throws an exception.

Answer 2

True

Question 3

The array implementation of a queue must access items at the logical beginning and the logical end.

Answer 3

True

Question 4

In the array implementation of a queue, the pop operation is most efficient if the front of the queue is fixed at index position 0.

Question 5

The list data structure in Python cannot be used to emulate a queue because there is no pop method.

Question 6

In computer science, process scheduling can be handled by simple or priority queues.

Question 7

By using a circular array implementation, you can simultaneously achieve good running times for both add and pop .

Question 8

The peek operation on a queue returns the item at the back of the queue without removing it.

Question 9

Both classes, LinkedStack and LinkedQueue, use a singly linked Node class to implement nodes.

Question 10

The add operation for a queue adds a node at the head of the structure.

Question 11

The most common type of CPU scheduling technique is called last in, first-out.

Question 12

The ready queue contains processes waiting to use the CPU.

Question 13

Each process on the ready queue is pushed onto a stack before being given a slice of CPU time.

Question 14

Similar to stacks, queues support a FILO protocol.

Question 15

An example of a computer simulation that can use queues is traffic flow on a busy highway.

Question 16

Queues are linear collections.

Question 17

A checkout line at a grocery store is an example of a queue.

Question 18

The two fundamental operations supported by queues are pop and insert.

Question 19

Simulation programs can use a range of integer values to mimic variability in the simulation.

Question 20

In a priority queue, items waiting in the queue the longest are always popped next.

Question 21

Which of the following is true about a standard queue?

A) the item that has been waiting the shortest is popped next
B) the items are popped in LIFO order
C) the item that has been waiting the longest is popped next
D) removals are done from the rear of the queue

Question 22

What happens to processes on the ready queue in a round-robin CPU scheduling scheme?

A) they are pushed and put in the priority queue
B) they are popped and allocated memory
C) they are pushed to the end of the queue
D) they are popped and given a slice of CPU time

Question 23

What type of collection is a queue?

A) linear
B) parallel
C) random
D) geometric

Question 24

When using a circular array implementation for a queue, during the add operation, the front pointer moves ahead of the rear pointer.

Question 25

In a linked implementation of a queue, what does the add operation do?

A) adds a node to the head
B) adds a node to the tail
C) inserts a node in the middle
D) creates a new instance of the queue

Question 26

Which protocol is supported by queues?

A) last-in first-out
B) last-in last-out
C) first-in first-out
D) first-in last-out

Question 27

What is the precondition to using the pop method on a queue?

A) the queue must not be empty
B) the queue must be full
C) the queue must not be full
D) the queue must first be resized

Question 28

When items are removed from a priority queue, items of lower priority are removed before those of higher priority.

Question 29

What is the returned value and the state of the queue after the operation is executed? Current queue state: x a z b
Q.peek()

A) b, x a z b
B) x, a z b
C) x, x a z b
D) b, x a z

Question 30

When using a circular array implementation for a queue, when either pointer is about to run off the end of the array, that pointer is reset to -1.

Question 31

What is one reason that it is difficult to devise formulas to answer simple questions about a supermarket checkout system?

A) the variability of essential factors
B) the regularity in which customers arrive
C) because customers always purchase the same number of items
D) because the same number of customers are there at all times of the day

Question 32

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

A) higher-priority items are popped before those of lower priority
B) items of equal priority are popped in LIFO order
C) items of equal priority are popped according to which item arrived first
D) higher-priority items can jump ahead of lower-priority items

Question 33

When using a circular array implementation for a queue, you maintain a count of the items in the queue to determine if it is full or empty.

Question 34

How would you use a Python list method to remove and return an item at the front of the queue?

A) peek(len(queue)-1)
B) peek(1)
C) pop(len(queue)-1)
D) pop(0)

Question 35

Which example best represents a queue?

A) print jobs sent to a printer
B) a pickup game of football
C) items selected via a random number generator
D) people exiting a sporting event

Question 36

What are the two fundamental operations of a queue?

A) insert, push
B) insert, pop
C) push, add
D) add, pop

Question 37

In the supermarket simulation, which of the following would be a property of a Cashier object?

A) assigns customers to cashiers
B) a queue of customer objects
C) a variable to track when service is received
D) generates new customer objects

Question 38

Which type of computer activity would likely be assigned to the priority queue?

A) a background process that defragments the disk
B) sending email
C) mouse movement
D) a background process that releases unused memory blocks

Question 39

When items are added to a priority queue, they are assigned an order of rank.

Question 40

Which of the following is NOT an important factor to consider by a manager of a supermarket trying to schedule checkout cashiers?

A) the frequency with which new customers arrive
B) the number of checkout cashiers available
C) the number of items in a customer's shopping cart
D) the number of aisles in the supermarket

Question 41

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

A) it must be added to the priority queue
B) it must be unwrapped
C) it must be compared to the next item
D) it must be discarded

Question 42

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

A) self.rear -= 1
B) self.front = self.rear
C) self.size -= 1
D) self.size += 1

Question 43

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

A) using a front pointer that advanced through the array
B) using a fixed front pointer to index position 0
C) using an insert function instead of add
D) using a circular array implementation

Question 44

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

A) user a wrapper class
B) remove them from the queue
C) remove them in FIFO order
D) put them in the back of the queue

Question 45

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

A) return type(other)
B) return other
C) return False
D) return self.priority

Question 46

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

A) when items are added, they are assigned an order of rank
B) items of higher priority are removed before those of lower priority
C) items of higher priority are removed in FIFO order
D) items of equal priority are removed in FIFO order

Question 47

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

A) -1
B) 0
C) None
D) 1

Question 48

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?

A) it adds the item to the front
B) it puts the item in a wrapper
C) it adds the item to the rear
D) it increases the size of the queue

Question 49

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

A) self.rear = newNode
B) self.rear -= 1
C) self.rear.prev = None
D) self.front = self.next

Question 50

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

A) O( n² )
B) exponential
C) logarithmic
D) O( n )