Deck 6: Trees

Question 1

The node at the top of a tree is called its ____________________.

Answer 1

root

Question 2

The links from a node to its successors care called ____________________.

Answer 2

branches

Question 3

The predessor of a node is called its ____________________.

Answer 3

parent

Question 4

Nodes that have the same parent are ____________________.

Question 5

You declare that an object is serializable by adding the declaration ____________________.

Question 6

Leaf nodes are also known as ____________________ nodes.

Question 7

The ____________________ is the number of nodes in the longest path from the root node to a leaf node.

Question 8

The ____________________ is used to implement a priority queue.

Question 9

A(n) ____________________ is a data structure in which only the highest-priority item is accessible.

Question 10

The ____________________ of a node is a measure of its distance from the root.

Question 11

Removal from a heap is always from the bottom.

Question 12

If node A is the parent of node B, which is the parent of node C, node A is node C's ancestor, and node C is node A's descendant.

Question 13

If node n is not the root of tree T, its level is 1 + the level of its parent.

Question 14

Parentheses are not stored in a binary tree, because the tree structure dictates the order of operator evaluation.

Question 15

Using Huffman codes to encode text files should give you files with more bits than you would get using other codes.

Question 16

A set of nodes T is a binary search tree ____.

A) if T is not empty, its root node has two subtrees, T_L and T_R, such that T_L and T_R are binary search trees and the value in the root node of T is greater than all values in T_L and is less than all values in T_R.
B) if T is not empty, its root node has two subtrees, T_L and T_R, such that T_L and T_R are binary trees.
C) if T is empty and its height is 0
D) if T is not empty, its height height is the maximum depth of its nodes.

Question 17

Searching a binary search tree is a(n) ____ process.

A) O(n)
B) O(log n)
C) O(1)
D) O(log₂n)

Question 18

Which of the following is the preorder traversal of a binary tree?

A) Traverse T_L, visit root node, traverse T_R.
B) Visit root node, traverse T_L, traverse T_R.
C) Traverse T_L, traverse T_R, visit root node.
D) Visit root node, traverse T_R, traverse T_L.

Question 19

Which of the following is the postorder traversal of of a binary tree?

A) Traverse T_L, visit root node, visit root node.
B) Visit root node, traverse T_L, traverse T_R.
C) Traverse T_L, traverse T_R, visit root node.
D) Visit root node, traverse T_R, traverse T_L.

Question 20

In a priority queue, the poll method first saves the item at the top of the heap.

Question 21

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.

Question 22

Which of the following is the algorithm for insertion in a heap?

A) Insert the new item in the next position at the bottom of the heap.
while new item is not at the root and new item is smaller that its parent
Swap the new item with its parent, moving the item up the heap.
B) Insert the new item in the next position at the top of the heap.
while new item is at the root and new item is smaller that its parent
Swap the new item with its parent, moving the item up the heap.
C) Insert the new item in the next position at the bottom of the heap.
while new item is at the root and new item is larger that its parent
Swap the new item with its parent, moving the item up the heap.
D) Insert the new item in the next position at the bottom of the heap.
while new item is at the root and new item is smaller that its parent
Swap the new item with its parent, moving the item down the heap.

Question 23

Insertion into and removal from a heap is ____.

A) O(n)
B) O(n²)
C) O(log n)
D) O(log₂n)

Question 24

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 intoa a binary tree
D) recursive algorithm for searching a binary tree

Question 25

Expanding and contracting arrays are ____ operations.

A) O(n).
B) O(log n)
C) O(n)
D) O(n²)