Chapter 15 Questions
Multiple Choice Questions
1. The ADT ______ is value-oriented.
a. list
b. sorted list
c. stack
d. queue
e. binary tree
2. The ADT stack manages an association between data items and the ______ of the data items.
a. names
b. values
c. sizes
d. positions
3. The operations of the ADT sorted list are based upon the ______ of data items.
a. names
b. values
c. sizes
d. positions
4. The ______ is a position-oriented ADT that is not linear.
a. sorted list
b. queue
c. binary tree
d. list
5. Which one of the following ADTs is position-oriented?
a. binary tree
b. sorted list
c. table
d. priority queue
6. The node of a tree that has no parent is called a(n) ______.
a. edge
b. root
c. leaf
d. vertex
7. The lines between the nodes of a tree are called ______.
a. branches
b. edges
c. arches
d. subtrees
8. The node that is directly above node n in a tree is called the ______ of node n.
a. root
b. leaf
Chapter 15 Questions
c. parent
d. child
9. A node directly below node n in a tree is called a ______ of node n.
a. root
b. leaf
c. parent
d. child
10. In a tree, the children of the same parent are called ______.
a. leafs
b. siblings
c. roots
d. contemporaries
11. Each node in a tree has ______.
a. exactly one parent
b. at most one parent
c. exactly one leaf
d. at most two leaves
12. A node on the path from the root to node n is a(n) ______ of node n.
a. ancestor
b. descendant
c. subtree
d. leaf
13. A descendant of node n is a node on a path from node n to ______.
a. the root
b. a leaf
c. a sibling of node n
d. a child of node n
14. A subtree of node n is a subtree rooted at ______.
a. node n
b. the parent of node n
c. a child of node n
d. a sibling of node n
15. Each node in a binary tree has ______.
a. exactly one child
b. at most one child
c. exactly two children
d. at most two children
16. The ______ of a tree is the number of nodes on the longest path from the root to a leaf.
a. height
b. length
Chapter 15 Questions
c. depth
d. balance
17. In a ______ of height h, all nodes that are at a level less than h have two children each.
a. general tree
b. binary tree
c. full binary tree
d. complete binary tree
18. A ______ of height h is full down to level h – 1, with level h filled in from left to right.
a. full binary tree
b. complete binary tree
c. balanced binary tree
d. general tree
19. In ______, the left and right subtrees of any node have heights that differ by at most 1.
a. all trees
b. all binary tress
c. n-ary trees
d. balanced binary trees
20. Which of the following is NOT a property of a complete binary tree of height h?
a. all nodes at level h – 2 and above have two children each
b. when a node at level h – 1 has children, all nodes to its left at the same level have two children each
c. when a node at level h – 1 has one child, it is a left child
d. all leaves are at level h
21. The traversal of a binary tree is ______.
a. O(n)
b. O(1)
c. O(n2)
d. O(log2 n)
22. Any data element within a record of a binary search tree is called a ______.
a. field
b. tree
c. collection
d. key
23. The maximum number of comparisons for a retrieval operation in a binary search tree is the ______.
a. length of the tree
b. height of the tree
c. number of nodes in the tree
d. number of leaves in the tree
24. The maximum height of a binary tree of n nodes is ______.
a. n
b. n / 2
Chapter 15 Questions
c. (n / 2) – 2
d. log2(n + 1)
25. The minimum height of a binary tree of n nodes is ______.
a. n
b. n / 2
c. (n / 2) – 2
d. log2(n + 1)
26. Locating a particular item in a binary search tree of n nodes requires at most ______ comparisons.
a. n
b. n / 2
c. (n / 2) – 2
d. log2(n + 1)
27. Locating a particular item in a balanced binary search tree of n nodes requires at most ______ comparisons.
a. n
b. n / 2
c. (n / 2) – 2
d. log2(n + 1)
28. A full binary tree whose height is 4 has ______ nodes.
a. 7
b. 8
c. 15
d. 31
29. The post order traversal of the following tree is
a. 1, 2, 3, 4, 5, 6, 7, 8, 9
b. 6, 2, 1, 4, 3, 5, 8, 7, 9
c. 6, 2, 8, 1, 4, 7, 9, 3, 5
d. 1, 3, 5, 4, 2, 7, 9, 8, 6
30. Each node in a binary tree has ______.
a. exactly one child
b. at most one child
c. exactly two children
d. at most two children
31. The maximum number of comparisons for a retrieval operation in a binary search tree is the
______.
a. length of the tree
b. height of the tree
c. number of nodes in the tree
Chapter 15 Questions
d. number of leaves in the tree
Chapter 15 Questions
True/False Questions
1. The ADT queue is value-oriented.
2. The ADT binary tree is position-oriented.
3. The ADT binary search tree is value-oriented.
4. All trees are hierarchical in nature.
5. The root of a tree has one parent.
6. A binary tree cannot be empty.
7. A tree whose height is h has its root at level h.
8. An inorder traversal visits a node before it traverses either of the node’s subtrees.
9. A complete binary tree with n nodes has a height of log2(n + 1).
11. The height of a binary search tree is sensitive to the order in which items are inserted into the tree.
12. A balanced binary search tree has the minimum height possible for the tree.
13. The in order traversal is only applicable to binary trees.
Chapter 15 Questions
Short Answer Questions
1. What are the three general categories of data management operations?
2. List three position-oriented ADTs.
3. Define the root of a tree.
4. Define a leaf of a tree.
5. What is a subtree?
6. What are the characteristics of a binary tree?
7. Define the left child of node n in a binary tree.
8. What are the three properties of each node n in a binary search tree?
9. In what order does a preorder traversal visit a node and its subtrees?
10. In what order does an inorder traversal visit a node and its subtrees?
11. In what order does a postorder traversal visit a node and its subtrees?
12. What is a search key?
13. Define an n-ary tree.
14. State the formal definition of a “general tree”
Chapter 15 Questions
15. Given the following tree:
List the preorder transversal of the tree.