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]

Accepted Answer

In an array-based implementation, elements are stored in the array in order of their priority. The element with the highest priority is stored in the last index of the array (i.e., at index size - 1), so pqDelete should return the element at that index.

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

Accepted Answer

In a linked list implementation of priority queue, the newly inserted item with highest priority is placed at the beginning of the list, as items are stored in ascending or descending order based on their priority value. Thus, the first node of the linked list contains the item with the highest priority value.

Question 3

The ______ operation of the ADT table throws a TableException.
A)tableInsert
B)tableDelete
C)tableRetrieve
D)tableTraverse

Accepted Answer

The `tableInsert` operation throws a `TableException` if an insertion fails, such as when trying to insert a duplicate key in a table that does not allow duplicates.

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)

Accepted Answer

In an unsorted array, the retrieval operation involves linear searching through the array elements to find the desired value. Therefore, the time complexity of retrieval operation in unsorted array-based implementation of the ADT table is O(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)

Accepted Answer

Insertion in an unsorted array-based implementation of the ADT table is O(1) because it involves adding an element at the end of the array, which does not require shifting or rearranging the existing elements.

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

Accepted Answer

Traversal of the binary search tree requires visiting each node in the tree in a specific order, such as in-order, pre-order, or post-order. Since visiting each node takes O(1) time and there are n nodes in the tree, traversal requires O(n) time, making it the only operation among the four choices that is O(n). Insertion, deletion, and retrieval in a balanced binary search tree take O(log n) time on average because the height of the tree is log n.

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²)

Accepted Answer

In a sorted array-based implementation, inserting an element requires potentially moving all other elements to maintain the sorted order, which takes O(n) time.

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²)

Accepted Answer

The sorted reference-based implementation of the tableDelete operation is O(n) because, after finding the element to delete (which can be done in O(log n) time if binary search is used), the algorithm must shift all subsequent elements to fill the gap left by the deleted element, which takes O(n) time in the worst case.

Question 9

A(n)______ implementation of a table is nonlinear.
A)list
B)linked list
C)binary search tree
D)array

Accepted Answer

A binary search tree is a non-linear implementation of a table because it is a tree-based data structure where each node has at most two children, and the order of the nodes is determined by a comparison function. This allows for efficient searching, insertion, and deletion operations, but the order of the nodes does not follow a linear progression, making it a non-linear structure. The other choices (list, linked list, array) are linear data structures.

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

Accepted Answer

In a sorted linear implementation of a table, the proper position of a new item to be inserted is determined by the value of the search key of the item. The search key is a field in the item that is used to search, sort, and retrieve the item from the table. This key is used to determine the position of the item in the table based on its value. Therefore, choice D is the correct answer.

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

Accepted Answer

Priority queues prioritize items based on a priority value assigned to each item. The item with the highest priority value is given the highest priority and is removed first from the queue. Therefore, the correct option is D.

Question 12

The ADT table is also known as a ______.
A)map
B)queue
C)heap
D)dictionary

Accepted Answer

The ADT table is also known as a dictionary, which consists of key-value pairs. Each key is like a word and each value is like a definition, which can be looked up in the dictionary. A map is another type of data structure that also uses key-value pairs, but is not specifically referred to as a table. Queues and heaps are also different types of data structures with their own specific functions.

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)

Accepted Answer

The sorted reference-based implementation of the tableInsert operation involves finding the correct position in the sorted list to insert the new element. This requires traversing the list until the correct position is found, which takes a linear time complexity of O(n). Therefore, the best choice is B.

Question 14

An array based implementation of an ADT is a ______ implementation.
A)vertical
B)linear
C)nonlinear
D)compound

Accepted Answer

Array-based implementation is a linear implementation because the elements are stored sequentially in the memory with contiguous indexes. It allows access to any element in constant time using index values. However, inserting or deleting an element from the middle of the array requires shifting the subsequent elements, making it inefficient for large arrays.

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]

Accepted Answer

In an unsorted array-based implementation of a table, a new item is typically inserted at the end of the array. Given that arrays are zero-indexed, the next available position for a new item is at index `size`, where `size` represents the current number of elements in the array. Therefore, `items[size]` is the correct location for insertion.

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

Accepted Answer

When the item with a given search key does not exist in a table, the logical choice would be to return a null reference, indicating that there is no data to retrieve. This is a common practice in many programming languages and avoids returning any erroneous or misleading values. The other options of returning a value such as -1, 0, or false may cause confusion or issues in further processing of the data.

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

Accepted Answer

In a binary search tree, the rightmost node will always have the highest priority value as all the larger elements are stored on the right side of the root node. Therefore, the correct choice is C - rightmost node 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

Accepted Answer

A maxheap is a heap in which the maximum element is always stored at the root.

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

Accepted Answer

Sorted or unsorted implementations of a table typically maintain a count of the current number of items to manage the data structure efficiently, allowing for operations like insertion, deletion, and searching to be performed with knowledge of the table's size.

Question 20

A priority queue orders its items by their ______.
A)position
B)value
C)priority value
D)size

Accepted Answer

As the name suggests, a priority queue is based on priority values of items. The items with higher priority values are given higher priority and are processed first. Therefore, option C is the correct choice as it is the priority value that determines the order of items in a priority queue.

Quiz 12: Tables and Priority Queues

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

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

The ______ operation of the ADT table throws a TableException.

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

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

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

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

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

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

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

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

The ADT table is also known as a ______.

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

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

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

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

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

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

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

A priority queue orders its items by their ______.