Deck 12: Tables and Priority Queues

Question 1

In an array-based implementation of the priority queue,the pqDelete operation returns the item in ______.

A)items[size]
B)items[0]
C)items[size-1]
D)items[size+1]

Answer 1

C

Question 2

In a linear implementation of the priority queue based on a linked list,the item with the highest priority value is located ______.

A)at the beginning of the linked list
B)at the end of the linked list
C)in the middle of the linked list
D)at a random location in the linked list

Answer 2

A

Question 3

The ______ operation of the ADT table throws a TableException.

A)tableInsert
B)tableDelete
C)tableRetrieve
D)tableTraverse

Answer 3

A

Question 4

In an unsorted array-based implementation of the ADT table,the retrieval operation is ______.

A)O(1)
B)O(n)
C)O(n²)
D)O(log n)

Question 5

In an unsorted array-based implementation of the ADT table,the insertion operation is ______.

A)O(1)
B)O(n)
C)O(n²)
D)O(log n)

Question 6

Which of the following operations of the binary search tree implementation of the ADT tree is O(n)?

A)insertion
B)deletion
C)retrieval
D)traversal

Question 7

The sorted array-based implementation of the tableInsert operation is ______.

A)O(1)
B)O(log n)
C)O(n)
D)O(n²)

Question 8

The sorted reference-based implementation of the tableDelete operation is ______.

A)O(1)
B)O(log n)
C)O(n)
D)O(n²)

Question 9

A(n)______ implementation of a table is nonlinear.

A)list
B)linked list
C)binary search tree
D)array

Question 10

In the sorted linear implementation of a table,the proper position of a new item to be inserted is determined ______.

A)by the data type of the item
B)by the size of the item
C)by the value of the item
D)by the value of the search key of the item

Question 11

The first item to be removed from a priority queue is the item ______.

A)in the front of the priority queue
B)in the end the priority queue
C)with the highest value
D)with the highest priority value

Question 12

The ADT table is also known as a ______.

A)map
B)queue
C)heap
D)dictionary

Question 13

The sorted reference-based implementation of the tableInsert operation is ______.

A)O(1)
B)O(n)
C)O(n²)
D)O(log n)

Question 14

An array based implementation of an ADT is a ______ implementation.

A)vertical
B)linear
C)nonlinear
D)compound

Question 15

In an unsorted array-based implementation of a table,a new item is inserted at location ______.

A)items[size]
B)items[size-1]
C)items[size+1]
D)items[size+2]

Question 16

If the item with a given search key does not exist in a table,the tableRetrieve operation returns ______.

A)the value -1
B)the value 0
C)the value false
D)a null reference

Question 17

In a binary search tree implementation of the ADT table,the item with the highest priority value is always in the ______.

A)root of the tree
B)leftmost node of the tree
C)rightmost node of the tree
D)leftmost node at level 1 of the tree

Question 18

A heap in which the root contains the item with the largest search key is called a ______.

A)minheap
B)maxheap
C)complete heap
D)binary heap

Question 19

Which of the following is true about a linear implementation of a table?

A)the unsorted implementations must insert a new item into its proper position as determined by the value of its search key
B)the sorted implementations can insert a new item into any convenient location
C)the sorted implementations maintain a count of the current number of items in the table
D)the unsorted implementations do not maintain a count of the current number of items in the table

Question 20

A priority queue orders its items by their ______.

A)position
B)value
C)priority value
D)size

Question 21

A heap in which the root contains the item with the smallest search key is called a ______.

A)minheap
B)maxheap
C)complete heap
D)binary heap

Question 22

In an array-based implementation of a heap,the parent of the node in items[i] is always stored in ______.

A)items[i/2]
B)items[(i-1)/2]
C)items[i-2]
D)items[(i-2)/2]

Question 23

In a maxheap,the root contains a search key greater than or equal to the search key in each of its children.

Question 24

The ADT table is position-oriented.

Question 25

In an array-based implementation of a heap,the heapDelete operation is ______.

A)O(1)
B)O(n)
C)O(n²)
D)O(log n)

Question 26

A binary search tree implementation of a table is a linear implementation.

Question 27

In an unsorted reference-based implementation of a table,the tableInsert operation requires a constant time regardless of the table size.

Question 28

The heapsort is ______ in the worst case.

A)O(n)
B)O(log n)
C)O(n * log n)
D)O(n²)

Question 29

A heap is a ______.

A)general tree
B)table
C)full binary tree
D)complete binary tree

Question 30

In an array-based implementation of a heap,the number of array items that must be swapped to transform a semiheap of n nodes into a heap is ______.

A)n
B)n + 1
C)log2ⁿ
D)log2(n + 1)

Question 31

Which of the following is true about the heapsort?

A)the heapsort does not require a second array
B)the heapsort is more efficient than the mergesort in the worst case
C)the heapsort is more efficient than the mergesort in the average case
D)the heapsort is better than the quicksort in the average case

Question 32

The ADT table uses a search key to identify its items.

Question 33

The search key of an item must not change for as long as the item is stored in a table.

Question 34

The heapsort is ______ in the average case.

A)O(1)
B)O(n)
C)O(log n)
D)O(n * log n)

Question 35

In an array-based implementation of a heap,the heapInsert operation is ______.

A)O(1)
B)O(n)
C)O(n²)
D)O(log n)

Question 36

A binary search tree implementation of the ADT table is easier to understand than a linear implementation.

Question 37

A semiheap is a ______.

A)table
B)complete binary tree
C)general tree
D)full binary tree

Question 38

A sorted implementation of a table can insert a new item into any convenient location.

Question 39

In a heap,the search keys of the children of a particular node have no relationship.

Question 40

The mergesort is more efficient than the heapsort in the worst case.

Question 41

What kind of implementation of the ADT table is appropriate for retrieval-dominated applications if the maximum size of the table is NOT known?

Question 42

What is the effect of the assumption that all items in a table have distinct search keys,on the insertion operation of a table?

Question 43

What are the four categories of linear implementations of tables?

Question 44

What does the priority value in a priority queue correspond to in a heap?

Question 45

Heapsort is a sorting algorithm that uses the heap data structure.Discuss how we can use a binary search tree to sort a list of values.Why would such an algorithm not perform as efficiently as heapsort?

Question 46

What is a linear implementation?

Question 47

In the Java Collections Framework,what is the difference between a Collection and a Set?

Question 48

What is the major advantage that a heap implementation of a priority queue has over a binary search tree implementation?

Question 49

What are the two main differences between a heap and a binary search tree?

Question 50

For what kinds of situations is a linear implementation of the ADT table more efficient than a binary search tree implementation?

Question 51

The Java Collections Framework includes classes called maps such as HashMap and TreeMap.In such classes,the individual elements each have two attributes.What are they?

Question 52

What are the two possible outcomes of the tableRetrieve operation of the ADT table?

Question 53

Why is a binary search operation impractical for a reference-based implementation of the ADT table?

Question 54

How does the pqDelete operation work in a linear implementation of the priority queue based on a linked list?

Question 55

What is a semiheap?

Question 56

What are the advantages of a linear implementation of the ADT table over a binary search tree implementation?

Question 57

In an array-based implementation of the priority queue,where is the item with the highest priority value located?

Question 58

What function is performed by the tableLength operation of the ADT table?

Question 59

When implementing an ADT such as a table,one design question is how often each ADT operation is to be performed.Why do we ask ourselves this question?

Question 60

What kind of implementation of the ADT table is appropriate for retrieval-dominated applications if the maximum size of the table is known?