Deck 13: Advanced Implementations of Tables

Question 1

A 4-node contains ______ data item(s).

A)one
B)two
C)three
D)four

Answer 1

C

Question 2

In a 2-3-4 tree,a leaf may contain ______ data items.

A)one or two
B)two or three
C)one,two,or three
D)one,two,three,or four

Answer 2

C

Question 3

All the nodes in a binary tree are ______.

A)single nodes
B)1-nodes
C)2-nodes
D)double nodes

Answer 3

C

Question 4

If a particular 2-3 tree does NOT contain 3-nodes,it is like a ______.

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

Question 5

In a 4-node,the smallest search key is found in the ______ subtree.

A)left
B)middle-left
C)middle-right
D)right

Question 6

A node that contains two data items and has three children is called a ______.

A)2-node
B)3-node
C)double node
D)triple node

Question 7

In a 2-3 tree,______.

A)all internal nodes have 2 children
B)all internal nodes have 3 children
C)all leaves are at the same level
D)all nodes have 2 data items

Question 8

In a 4-node,the largest search key is found in the ______ subtree.

A)left
B)middle-left
C)middle-right
D)right

Question 9

The maximum height of a binary search tree of n nodes is ______.

A)n
B)n - 1
C)n / 2
D)log2(n + 1)

Question 10

A 4-node is found in a(n)______.

A)AVL tree
B)2-3 tree
C)2-3-4 tree
D)red-black

Question 11

In a 3-node,______.

A)the left child has the largest search key
B)the middle child has smallest search key
C)the middle child has the largest search key
D)the right child has the largest search key

Question 12

In the binary search tree implementation of the ADT table,the maximum number of comparisons required by the tableInsert operation is equal to ______.

A)the number of nodes in the binary search tree
B)the height of the binary search tree
C)the number of leaves in the binary search tree
D)the number of internal nodes in the binary search tree

Question 13

Searching a 2-3 tree is ______.

A)O(n)
B)O(log2ⁿ)
C)O(log2ⁿ * n)
D)O(n²)

Question 14

A 2-3 implementation of a table is ______ for all table operations.

A)O(n)
B)O(log2ⁿ)
C)O(log2ⁿ * n)
D)O(n²)

Question 15

Locating a particular item in a binary search tree of n nodes requires at most ______ comparisons.

A)n
B)n * 3
C)n / 2
D)n - (n / 2)

Question 16

A node that contains one data item and has two children is called a ______.

A)1-node
B)2-node
C)single node
D)double node

Question 17

In a 2-3 tree,a leaf may contain ______ data item(s).

A)one
B)one or two
C)two
D)two or three
E)three

Question 18

A(n)______ is a tree in which each internal node has either two or three children,and all leaves are at the same level.

A)red-black tree
B)2-3 tree
C)2-3-4 tree
D)AVL tree

Question 19

A 2-3 tree of height h always has at least ______ nodes.

A)h²
B)h² - 2
C)2h
D)2h - 1

Question 20

Which of the following is NOT true about a red-black tree?

A)it is balanced
B)its insertion operation requires one pass from root to leaf
C)its deletion operation requires one pass from root to leaf
D)it requires more storage than a 2-3-4 tree

Question 21

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

Question 22

A 2-3-4 tree is always balanced.

Question 23

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

Question 24

______ 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.

A)Linear probing
B)Quadratic probing
C)Double hashing
D)Separate chaining

Question 25

A 2-3 tree is a binary tree.

Question 26

A hash table is a(n)______.

A)stack
B)queue
C)array
D)list

Question 27

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

Question 28

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

Question 29

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

A)revolutions
B)rotations
C)hash functions
D)refractions

Question 30

______ 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.

A)Linear probing
B)Double hashing
C)Quadratic probing
D)Separate chaining

Question 31

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

A)hash function
B)hash table
C)AVL tree
D)red-black tree

Question 32

A 3-node contains three data items.

Question 33

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

Question 34

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

Question 35

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

A)iteration
B)hash
C)collision
D)probe

Question 36

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

A)disturbance
B)collision
C)rotation
D)congestion

Question 37

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

A)Linear probing
B)Double hashing
C)Quadratic probing
D)Separate chaining

Question 38

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

A)table size + current number of table items
B)table size - current number of table items
C)current number of table items * table size
D)current number of table items / table size

Question 39

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

Question 40

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

A)2-3 tree
B)2-3-4 tree
C)red-black
D)AVL

Question 41

What is a bucket?

Question 42

What is a 3-node?

Question 43

What is a disadvantage of a 2-3-4 tree when compared with a binary search tree?

Question 44

In a 2-3 tree,how is the search key of a 3-node related to the search keys in the left subtree,the middle subtree,and the right subtree of the 3-node?

Question 45

What is the advantage of using a variation of a binary search tree,such as a 2-3 tree or a 2-3-4 tree,instead of a binary search tree?

Question 46

What is a perfect hash function?

Question 47

Suppose we have already inserted the values 5,10 and 15 into an empty 2-3-4 tree.Explain what happens when we insert the value 20 into this tree.

Question 48

What makes 2-3-4 trees more attractive than 2-3 trees?

Question 49

Suppose we wanted to use a hash table to store people's names.Each name is a String object.What is wrong with using the length of the string as the hash value of each name?

Question 50

In designing a hash table,why do we want the size of the table to be significantly larger than the maximum number of entries that we will insert into it?

Question 51

What are the two types of rotations possible in an AVL tree?

Question 52

What is the maximum and the minimum number of children that an internal node can have in a 2-3 tree?

Question 53

In a 2-3 tree,how is the search key of a 2-node related to the search keys in the left subtree and the right subtree of the 2-node?

Question 54

What is meant by clustering? How does clustering affect the overall efficiency of hashing?

Question 55

What are the two types of approaches for resolving collisions in a hash table design?

Question 56

Suppose we want to delete a node from an AVL tree.If this node does not have any children,is it possible that removing this node would require us to perform a rotation operation? Explain.

Question 57

What is a 4-node?

Question 58

In a 2-3-4 tree,when is a 4-node split during an insertion operation?

Question 59

What is a 2-node?

Question 60

What is a collision?