Deck 11: Binary Trees and B-Trees

Question 1

When data is being organized, a programmer's highest priority is to organize it in such a way that item insertion, deletion, and lookups (searches) are fast.

Answer 1

True

Question 2

Because an array is not a random access data structure, we cannot use a binary search to effectively find and retrieve an item from an array list.

Answer 2

False

Question 3

In an array, item insertion (especially if the array is sorted) and item deletion can be very time consuming, especially if the list size is very large.

Answer 3

True

Question 4

Item insertion and deletion in a linked list requires significant data movement.

Question 5

A sequential search is good only for very small lists because the average search length of a sequential search is half the size of the list.

Question 6

Every node in a binary tree has at most three children.

Question 7

A binary tree is a dynamic data structure.

Question 8

After inserting an item in a binary search tree, the resulting binary tree must also be a binary search tree.

Question 9

In a preorder traversal of a binary tree, for each node, first the node is visited, then the right subtree is visited, and then the left subtree is visited.

Question 10

In a preorder traversal of a binary tree, after visiting a node and before moving to the right subtree, we must save a pointer to the node so that after visiting the right subtree, we can visit the left subtree.

Question 11

As in the case of an inorder traversal, in a postorder traversal, the first node visited is the rightmost node of the binary tree.

Question 12

To specify a function as a formal parameter to another function, we specify the function type, followed by the function name as a pointer, followed by the parameter types of the function.

Question 13

The performance of the search algorithm on a binary search tree depends on how large the binary tree is.

Question 14

Because an AVL tree is a binary search tree, the search algorithm for an AVL tree is the same as the search algorithm for a binary search tree.

Question 15

Operations, such as finding the height, determining the number of nodes, checking whether the tree is empty, tree traversal, and so on, on AVL trees cannot be implemented the same way they are implemented on binary trees.

Question 16

After inserting (or deleting) a node from an AVL tree, the resulting binary tree does not have to be an AVL tree.

Question 17

To insert an item in an AVL tree, first we search the tree and find the place where the new item is to be inserted.

Question 18

After inserting the node, the reconstruction can occur at any node on the path back to the root node.

Question 19

The performance of a binary search tree depends on the width of the tree.

Question 20

Each node should store the number of keys in the node, the records, and the pointer to subtrees.

Question 21

The class implementing the properties of a B-tree must, among others, implement the search, traversal, insertion, and deletion algorithms.

Question 22

A search in a B-tree must start at the bottom node.

Question 23

When inserting into a B-tree, if the key is already in the tree, you should output an error message.

Question 24

To implement the insertion algorithm in a B-tree, we only need algorithms to split a node and insert an item into a node.

Question 25

When deleting from a B-tree, if the leaf contains only the minimum number of keys, look at the sibling nodes that are adjacent to the leaf.

Question 26

To speed up item insertion and deletion in a data set, use ____.

A) arrays
B) linked lists
C) classes
D) ADTs

Question 27

One of the drawbacks of linked lists is that they must be processed ____.

A) recursively
B) in order
C) out of order
D) sequentially

Question 28

The item insertion, deletion, and lookup operations require that the binary tree be ____.

A) duplicated
B) traversed
C) inverted
D) converted

Question 29

In a ____ traversal of a binary tree, for each node, first the left subtree is visited, then the right subtree is visited, and then the node is visited.

A) preorder
B) inorder
C) postorder
D) recursive

Question 30

In C++, a function name without any parentheses is considered a ____.

A) reference to the function
B) address of the function
C) pointer to an entry point
D) pointer to the function

Question 31

The ____ is one in which the resulting binary search is nearly balanced.

A) ABL tree
B) AVL tree
C) BVL tree
D) BDL tree

Question 32

The balance factor of x, written bf(x), is defined by ____.

A) bf(x)= x_l - x₁
B) bf(x)= x₁ - x_h
C) bf(x)= x_h - x₁
D) bf(x)= l(x_h) - l(x₁)

Question 33

Let x be a node in a binary tree, then we say that the node x violates the ____ if |x_h - x₁| > 1, that is, the heights of the left and right subtrees of x differ by more than 1.

A) balance criteria
B) balance factor
C) rebalance criteria
D) rebalance factor

Question 34

If the item to be inserted in an AVL tree is already in the tree, the search ends at a ____.

A) leaf node
B) linear subtree
C) linked subtree
D) nonempty subtree

Question 35

There are two types of AVL tree rotations: ____.

A) left rotation and right rotation
B) inner rotation and outer rotation
C) inner rotation and left rotation
D) right rotation and left inversion

Question 36

The reconstruction procedure for an AVL tree is called ____.

A) reverting the tree
B) balancing the tree
C) rotating the tree
D) inverting the tree

Question 37

To delete a node, we adjust one of the pointers of the ____.

A) leaf node
B) parent node
C) branch node
D) child node

Question 38

In the worst case, the height of an AVL tree with n nodes is approximately ____.

A) (1.44)logn
B) (1.44)nlogn
C) (1.44)log₂n
D) (1.44)logn²

Question 39

The height of a perfectly balanced binary tree with n nodes is ____.

A) logn
B) n²
C) nlogn
D) log₂n

Question 40

An ____ is a tree in which each node has at most m children.

A) m-way search tree
B) m-level search tree
C) m-node search tree
D) m-height search tree

Question 41

In a ____ the root has at least 2 children if it is not a leaf, and at most m children.

A) B-tree of height m
B) B-tree of level m
C) B-tree of size m
D) B-tree of order m

Question 42

The basic operations performed on a B-tree are search the tree, insert an item in the tree, delete an item from the tree, and ____.

A) rotate the tree
B) balance the tree
C) traverse the tree
D) copy the tree

Question 43

The function ____ searches the binary search tree for a given item.

A) insert
B) search
C) replace
D) traverse

Question 44

A B-tree can be ____ in three ways: inorder, preorder, and postorder.

A) copied
B) reversed
C) traversed
D) inversed

Question 45

When inserting into a B-tree, if the key is not in the tree, the search terminates at a ____.

A) leaf
B) root
C) node
D) branch

Question 46

When inserting into a B-tree, if the leaf is full, split the node into two nodes and the median key is moved to the ____ node.

A) child
B) empty
C) adjacent
D) parent

Question 47

Because the insertion of an item might require the splitting of a node and moving the median key to the parent node, the simplest way to implement the insertion algorithm is to use ____.

A) recursion
B) iteration
C) inversion
D) sequential traversal