SW10: Trees

Question 1

An in-order traversal of the expression tree for (a - b) * c would result in which sequence?

Answer 1

a - b * c

Question 2

A collection of disconnected trees is called a:

Answer 2

Forest

Question 3

The degree of a tree is defined by:

Answer 3

The maximum degree of any vertex in the tree.

Question 4

A tournament bracket… is a perfect real-world example of what kind of tree?

Answer 4

A full binary tree

Question 5

Which tree theorem is most critical for understanding the maximum performance of database search operations?

Answer 5

The theorem relating the height to the number of nodes (h is at least lg(n+1) - 1).

Question 6

The Java constructor public BTNode(T el) calls this(el, null, null);. What is the purpose of this line?

Answer 6

To call the other constructor, reusing its logic to set children to null.

Question 7

Which of the following is the biggest drawback of using K-ary Tree Representation 1 (“One pointer per potential child”)?

Answer 7

Poor space efficiency for non-uniform trees.

Question 8

In the breadthFirst algorithm, what is the purpose of the line p = dequeue()?

Answer 8

To get the next node to visit from the front of the queue.

Question 9

An Abstract Data Type (ADT) is composed of:

Answer 9

Data and Operations

Question 10

What does the getParent(n) operation return?

Answer 10

The direct parent node of n.

Question 11

What is a “subtree”?

Answer 11

Any node in a tree and all of its descendants.

Question 12

The term “ordered binary tree” implies that:

Answer 12

The positions of the left and right children are distinct and meaningful.

Question 13

If you call setRight(n, el) on a node n that already has a right child, what is the outcome?

Answer 13

The existing right child and its entire subtree are replaced by the new node.

Question 14

Fill in the Blank: The toString(T) operation typically starts by calling toString(n) on the root.

Answer 14

root

Question 15

Fill in the Blank: The time complexity of a Breadth-First traversal is O(n).

Answer 15

O(n)

Question 16

Fill in the Blank: The base case for the recursive depth-first traversals checks if the current node is null.

Answer 16

null

Question 17

In an array representation of an almost complete binary tree, the parent of a node at index k is at index: (for 1-based indexing).

Answer 17

l k/2 l

Question 18

The breadthFirst algorithm is:

Answer 18

iterative.

Question 19

The acronym for Inorder traversal is:

Answer 19

LVR

Question 20

To create a syntax tree, the algorithm first converts the infix expression to:

Answer 20

postfix

Question 21

Two nodes that have the same parent are called:

Answer 21

siblings

Question 22

A subtree consists of a node and all of its:

Answer 22

descendants

Question 23

The operation isEmpty(T) returns true if T.root is:

Answer 23

null

Question 24

The “first-child, next-sibling” representation is an example of a:

Answer 24

linked list

Question 25

The number of children a specific node has is its:

Answer 25

degree

Question 26

The new(btnode, el) constructor is ideal for creating a new:

Answer 26

leaf node

Question 27

Overwriting a child pointer using setLeft or setRight will disconnect the old subtree from the tree.

Answer 27

disconnect

Question 28

A Preorder traversal is also known as a:

Answer 28

depth-first traversal

Question 29

The ExprToSyntaxTree algorithm uses a stack of tree nodes to build the tree.

Answer 29

stack

Question 30

In K-ary Tree Representation 2, parent retrieval time is:

Answer 30

O(1)

Question 31

The number of vertices at level L of a complete binary tree is:

Answer 31

2^L

Question 32

What is the defining characteristic of a Depth-First Traversal (DFT)? A. It processes all nodes at one level before moving to the next. B. It uses a queue data structure to manage visited nodes. C. It explores as far down one path as possible before backtracking. D. It always selects the node with the highest priority to visit next.

Answer 32

C. It explores as far down one path as possible before backtracking.

Question 33

In the ExprToSyntaxTree algorithm, what is the purpose of the stack? A. To store the final, constructed syntax tree. B. To hold the operands and operators of the expression. C. To temporarily store variables and their values. D. To hold temporary tree nodes during the tree's construction.

Answer 33

D. To hold temporary tree nodes during the tree's construction.

Question 34

In K-ary Tree Representation 2 ("Pointer to parent"), how would you find the siblings of a given node n? A. Check the pointers of all other nodes to see which ones point to n. B. Follow the parent pointer of n, then search the entire tree for other nodes that point to n's children. C. Search the entire tree for all nodes at the same height as n. D. Follow the parent pointer of n, then search the entire tree for other nodes that point to that same parent.

Answer 34

D. Follow the parent pointer of n, then search the entire tree for other nodes that point to that same parent.

Question 35

What is the height of a single-node tree? A. 1 B. log₂(1) C. 0 D. Undefined

Answer 35

C. 0

Question 36

Which of the following is NOT a property of a tree? A. There is a unique path between any two vertices. B. A tree with n vertices has exactly n−1 edges. C. It is a connected acyclic graph. D. Every node can have multiple parents.

Answer 36

D. Every node can have multiple parents.

Question 37

In the Java BTNode class, what is the purpose of the generic type? A. To restrict the node data to only primitive types like int or double. B. To signify that the node is a Binary Search Tree node. C. To enforce that the data held must be comparable. D. A generic type parameter, allowing the node to hold any type of data.

Answer 37

D. A generic type parameter, allowing the node to hold any type of data.

Question 38

In the BTNode class, the isLeaf(n) operation is given a BTNode n. Why would it return false if n is null? A. Because null is considered a branch, not a leaf. B. To indicate that the tree is empty. C. To throw a NullPointerException and halt the program for debugging. D. To prevent a NullPointerException when checking n.left and n.right.

Answer 38

D. To prevent a NullPointerException when checking n.left and n.right.

Question 39

Fill in the Blank: The topmost node in a tree is called the root.

Answer 39

root

Question 40

Fill in the Blank: The level or depth of the root vertex is always zero.

Answer 40

zero

Question 41

Fill in the Blank: A binary tree where all interior nodes have two children and all leaves are at the same level is a full binary tree.

Answer 41

full

Question 42

Fill in the Blank: According to the tree theorems, a full binary tree with k internal vertices has k + 1 leaves.

Answer 42

k + 1

Question 43

Fill in the Blank: The new(btree) operation initializes the root pointer to null.

Answer 43

null

Question 44

Fill in the Blank: The info part of a btnode record holds the actual data of the node.

Answer 44

data

Question 45

Fill in the Blank: In K-ary Tree Representation 1, child retrieval time is O(1).

Answer 45

O(1)

Question 46

True or False: A tree is a linear data structure.

Answer 46

False

Question 47

True or False: A rooted tree must have exactly one node with no parent.

Answer 47

True

Question 48

True or False: In a tree, the path between any two vertices is always unique.

Answer 48

True

Question 49

True or False: A node's ancestors include its siblings.

Answer 49

False

Question 50

True or False: A binary tree can have a node with three children.

Answer 50

False

Question 51

True or False: The height of a tree is defined by the level of its root node.

Answer 51

False

Question 52

True or False: A full binary tree can have nodes with only one child.

Answer 52

False

Question 53

True or False: A complete binary tree can have gaps on its last level, as long as they are on the right side.

Answer 53

False

Question 54

True or False: A tree with 10 vertices will have exactly 9 edges.

Answer 54

True

Question 55

True or False: The isLeaf(n) operation would return true for an internal node.

Answer 55

False

Question 56

True or False: In the Java BTNode implementation, the BTNode(T el)constructor is primarily used for creating internal nodes.

Answer 56

False

Question 57

True or False: The setRoot(T, n) operation creates a new node from raw data and sets it as the root.

Answer 57

False

Question 58

True or False: K-ary Tree Representation 1 ("One pointer per potential child") is highly space-efficient for non-uniform trees.

Answer 58

False

Question 59

True or False: In K-ary Tree Representation 2 ("Pointer to parent"), finding a node's parent is an O(1) operation.

Answer 59

True

Question 60

Which property of trees guarantees that such a path is the only one?

Answer 60

The simple path between any two vertices is unique.

Question 61

According to the tree theorems, what should be your primary goal for the tree's structure for search performance?

Answer 61

Keep the height of the tree as low as possible.

Question 62

Which traversal strategy is most naturally suited for showing hierarchy (processing a parent before its children)?

Answer 62

Preorder

Question 63

You need to store a k-ary tree where the most common operation is finding an employee's direct manager. Which representation is the best fit?

Answer 63

Pointer to parent (Representation 2)

Question 64

In the "first-child, next-sibling" representation, how are all the direct children of a single node linked together?

Answer 64

Through a singly linked list using the "next sibling" pointers.

Question 65

In an array representation of an almost complete binary tree (1-based indexing), a node is at index k=5. Where is its left child located?

Answer 65

Index 10

Question 66

The isLeaf(n) operation returns true if and only if:

Answer 66

n.left is null AND n.right is null.

Question 67

What is the primary functional difference between setRoot(T, el) and setRoot(T, n)?

Answer 67

setRoot(T, el) creates a new node, while setRoot(T, n) uses an existing node.

Question 68

A system that manages a print queue would process jobs in an order analogous to which traversal?

Answer 68

Breadth-First

Question 69

What is the state of the queue in the Breadth First algorithm just before the while loop begins?

Answer 69

It contains only the root node.

Question 70

The recursive calls in the depth-first traversal algorithms stop when what condition is met?

Answer 70

The root of the subtree being traversed is null.

Question 71

To build a syntax tree from a postfix expression A B + C *, what is the last operation performed by the ExprToSyntaxTree?

Answer 71

A new tree with * as the root is pushed onto the stack.

Question 72

True or False: The "first-child, next-sibling" representation uses three pointers per node.

Answer 72

False

Question 73

True or False: An almost complete binary tree is poorly suited for an array representation due to wasted space.

Answer 73

False

Question 74

True or False: The isEmpty(T) operation checks if the number of nodes is zero by looking at the T.root pointer.

Answer 74

True

Question 75

True or False: Calling setLeft(n, el) on a node n that already has a left child will result in an error.

Answer 75

False

Question 76

True or False: Breadth-First Traversal explores one branch of a tree as deeply as possible before backtracking.

Answer 76

False

Question 77

True or False: A queue is the essential data structure for implementing a recursive Preorder traversal.

Answer 77

False

Question 78

True or False: The visit action in a Postorder traversal happens before traversing the left and right subtrees.

Answer 78

False

Question 79

True or False: The time complexity for all three main depth-first traversals is O(n).

Answer 79

True

Question 80

True or False: The ExprToSyntaxTree algorithm works directly on the infix expression to build the tree.

Answer 80

False

Question 81

True or False: A Preorder traversal of a syntax tree yields the postfix expression.

Answer 81

False

Question 82

True or False: Grandchildren are considered direct children in a tree.

Answer 82

False

Question 83

An information system needs to model a company's organizational chart. Which term best describes the entire chart?

Answer 83

A rooted tree

Question 84

In a file system, the C:\ drive has a folder named Users, which contains a folder named Documents. What is the relationship of Documents to C:?

Answer 84

Documents is a descendant of C:.