DATA STRUCTURE QUIZ 3 WITH CORRECT ANSWERS

DATA STRUCTURE QUIZ 3



Which of the following is an example of a map?
(a) (J, Jane), (B, Bill), (S, Sam), (B1, Bob), (B, Bill)
(b) (J, Jane), (B, Bill), (S, Sam), (B1, Bob), (B2, Bill)
(c) (J, Jane), (B, Bill), (S, Sam), (B1, Bob), (J, Jane)
(d) (S, Sam), (B, Bill), (S, Sam), (B1, Bob), (B2, Bill) - Correct Answers -(b) (J, Jane), (B,
Bill), (S, Sam), (B1, Bob), (B2, Bill)

Because Map cannot have a duplicate key

(True/False) Using a hash table enables us to retrieve an item in O(nlog(n)) time. -
Correct Answers -False

Hash table retrival is O(1)

(True/False) Using Huffman codes to encode text files should give you files with more
bits than you would get using other codes. - Correct Answers -False

Huffman codes uses fewer bits for the most common characters and more bits for the
uncommon characters

The following algorithm is a(n) .
if the tree is empty
Return null (target is not found).
else if the target matches the root node's data
Return the data stored at the root node.
else if the target is less than the root node's data
Return the result of searching the left subtree of the root.
else
Return the result of searching the right subtree of the root.

(a) algorithm for removal from a heap
(b) algorithm for insertion into a heap
(c) algoithm for insertion into a a binary tree
(d) recursive algorithm for searching a binary tree - Correct Answers -(d) recursive
algorithm for searching a binary tree

Expanding and contracting arrays are operations.
(a) O(n)

, (b) O(log2 n)
(c) O(√n)
(d) O(n2) - Correct Answers -(a) O(n)

Insertion into and removal from a heap is a operation.
(a) O(n)
(b) O(n2)
(c) O(log2 n)
(d) O(nlog2 n)
(e) O(log10 n) - Correct Answers -(c) O(log2 n)

Complete the following algorithm which recursively inserts an item into a binary search
tree.

if the root is null
Replace empty tree with a new tree with the item at the root and return true.
else if the item is equal to root.data
__________
else if the item is less than root.data
Recursively insert the item in the left subtree.
else
Recursively insert the item in the right subtree.

(a) The item is not in the tree; return false.
(b) The item is already in the tree; return false.
(c) The item is not in the tree; return true.
(d) The item is already in the tree; return true. - Correct Answers -(b) The item is already
in the tree; return false.

(True/False) In Java's PriorityQueue, the poll method first saves the item at the top of
the heap. (Check your answer by consulting the javadoc). - Correct Answers -True

Searching a binary search tree is a process.
(a) O(n)
(b) O(1)
(c) O(logn)
(d) O(n2) - Correct Answers -(c) O(logn)

(True/False) Removal from a heap is always from the bottom. - Correct Answers -False

The _________ of a node is a measure of its distance from the root. - Correct Answers -
Level

The __________ is used to implement a priority queue. - Correct Answers -Heap