Question 1

The height of a binary tree is sensitive to the order in which items are inserted into the tree.

Accepted Answer

The height of a binary tree depends on the order in which items are inserted. For example, if items are inserted in a way that the binary tree is perfectly balanced, the height of the tree will be log(n), where n is the number of items in the tree. However, if items are inserted in a way that the binary tree is unbalanced, the height of the tree can be as large as n, which is the number of items in the tree. Therefore, the height of a binary tree is sensitive to the order in which items are inserted into the tree.

Question 2

A 2-3-4 tree is always balanced.

Accepted Answer

A 2-3-4 tree, also known as a 2-4 tree, is a type of self-balancing search tree in which every node has 2, 3, or 4 child nodes. The tree is always balanced, meaning that the height of the tree is typically kept small relative to the number of data items stored in the tree. This makes it efficient for searching, insertion, and deletion operations.

Question 3

A 2-3 tree is never taller than a minimum-height binary tree.

Accepted Answer

A 2-3 tree is a type of self-balancing tree that can have either one or two data values per node. The minimum-height binary tree is a binary tree where all the leaves are at the same level. In a 2-3 tree, every node must have at least one data value, so it is impossible for there to be a level in the tree with no nodes. Therefore, the height of a 2-3 tree is always less than or equal to the minimum-height binary tree.

Question 4

______ is a collision-resolution scheme that searches the hash table sequentially,starting from the original location specified by the hash function,for an unoccupied location.

Accepted Answer

Linear probing is a collision-resolution scheme that sequentially searches the hash table starting from the original location specified by the hash function. It checks each subsequent location until an unoccupied location is found. This is a simple and easy-to-implement technique that does not require additional data structures. However, linear probing can suffer from clustering, where groups of adjacent locations become occupied, leading to longer search times. Nonetheless, it is still an effective and commonly used method for resolving collisions in hash tables.

Question 5

A 2-3 tree is a binary tree.

Accepted Answer

A 2-3 tree is not a binary tree, it is a type of self-balancing tree with either two or three children nodes for each non-leaf node.

Question 6

A hash table is a(n)______.

Accepted Answer

A hash table is an array that uses a hash function to map keys to indexes, making it an efficient data structure for storing and retrieving key-value pairs. A stack is a data structure that follows the last in, first out (LIFO) principle, a queue follows first in, first out (FIFO), and a list may refer to a linked list or an array list which may have different functionalities than a hash table.

Question 7

Insertions and deletions on a 2-3 tree requires fewer steps than insertions and deletions on a 2-3-4 tree.

Accepted Answer

Insertions and deletions in a 2-3 tree can sometimes require more steps than in a 2-3-4 tree because a 2-3-4 tree allows for more flexibility in node capacities before splitting or merging is needed, potentially reducing the number of restructuring operations.

Question 8

A balanced binary search tree would have the maximum height possible for the tree.

Accepted Answer

A balanced binary search tree would have the minimum height possible for the number of nodes it contains, as it is optimized for efficient searching and insertion. A tree with maximum height would be highly unbalanced and slow down operations on the tree.

Question 9

Operations which are used to maintain the balance of AVL trees are known as ______.

Accepted Answer

The correct term for maintaining the balance of AVL trees is "rotations". Options A, C, and D are irrelevant and do not describe AVL tree operations.

Question 10

______ is a collision-resolution scheme that searches the hash table for an unoccupied location beginning with the original location that the hash function specifies and continuing at increments of 12,22,32,and so on.

Accepted Answer

This collision-resolution scheme described is quadratic probing. Linear probing searches for the next available location in a consecutive manner, double hashing uses a secondary hash function to determine an alternate location, and separate chaining uses linked lists to store multiple values at the same location. Therefore, only option C) is the correct choice.

Question 11

A(n)______ maps the search key of a table item into a location that will contain the item.

Accepted Answer

A hash function is a function that takes a search key and returns an index, where the item should be placed in the hash table. Hence, a hash function is used to map the search key of a table item into a location that will contain the item.

Question 12

A 3-node contains three data items.

Accepted Answer

A 3-node contains two data items and two child pointers, while a 4-node contains three data items and four child pointers.

Question 13

A 2-3-4 tree requires more storage than a binary search tree.

Accepted Answer

A 2-3-4 tree stores multiple keys in a single node (up to 3 keys and 4 children per node), whereas a binary search tree stores only one key per node, leading to a 2-3-4 tree generally requiring more storage for the same number of keys.

Question 14

A red-black representation of a 2-3-4 tree is unique.

Accepted Answer

The red-black representation of a 2-3-4 tree is not unique because there are multiple ways to color the nodes and structure the tree while maintaining the red-black properties, leading to different valid red-black trees for the same 2-3-4 tree.

Question 15

The sequence of locations in a hash table that a collision resolution scheme examines is known as a(n)______ sequence.

Accepted Answer

The sequence of locations in a hash table that a collision resolution scheme examines is known as a probe sequence.

Question 16

The condition that occurs when a hash function maps two or more distinct search keys into the same location is called a(n)______.

Accepted Answer

This is the definition of a hash collision. It can occur due to the finite size of the hash table and the large number of possible input values. When two distinct keys are mapped to the same location, it can cause performance issues in the hash table operations.

Question 17

______ is a collision-resolution scheme that uses an array of linked lists as a hash table.

Accepted Answer

Separate chaining is a collision-resolution scheme that uses an array of linked lists as a hash table. It is an effective method for handling collisions because it allows multiple values to be stored at the same index of the hash table, improving the efficiency of hash table operations. Linear probing, double hashing, and quadratic probing are all examples of open addressing collision-resolution schemes, which have different trade-offs and may require additional steps to handle collisions.

Question 18

The load factor of a hash table is calculated as ______.

Accepted Answer

The load factor of a hash table is typically calculated as the current number of items in the hash table divided by the total number of slots in the hash table. Therefore, the correct choice is D.

Question 19

A node in a red-black tree requires less storage than a node in a 2-3-4 tree.

Accepted Answer

A node in a red-black tree only requires 3 fields (color, key, and pointers to left and right child), whereas a node in a 2-3-4 tree requires up to 3 keys and 4 child pointers, making it larger in size.

Question 20

A(n)______ is a balanced binary search tree.

Accepted Answer

An AVL tree is a balanced binary search tree.

Quiz 13: Advanced Implementations of Tables