Font size
S
M
L
XL
WorksheetsDSA_LT1_Trees
Total questions: 92
Worksheet time: 2hrs 32mins
Name
Class
Date
1.
A Preorder traversal is also known as a _______ traversal.
a)
Breadth-first
b)
Depth-first
c)
Level-order
d)
Linear
2.
A binary tree where all interior nodes have two children and all leaves are at the same level is called a:
a)
Full binary tree
b)
Complete binary tree
c)
Balanced binary tree
d)
Degenerate binary tree
3.
A collection of disconnected trees is called a:
a)
Path
b)
Forest
c)
k-ary tree
d)
Subtree
4.
A developer is creating a toString(T) method to debug a tree structure. To be useful, the output string must show the hierarchy. Which traversal strategy is most naturally suited for this, processing a parent before its children?
a)
Preorder
b)
Postorder
c)
Level-order
d)
Inorder
5.
A subtree consists of a node and all of its:
a)
Children
b)
Ancestors
c)
Siblings
d)
Descendants
6.
A tournament bracket, where every match has exactly two competitors, is a perfect real-world example of what kind of tree?
a)
A complete binary tree
b)
A skewed tree
c)
An ordered tree
d)
A full binary tree
7.
According to the tree theorems, a full binary tree with k internal vertices has how many leaves?
a)
k - 1
b)
2k
c)
k + 1
d)
k
8.
An Inorder traversal of the expression tree for (a - b) * c would result in which sequence?
a)
- a b c
b)
a b - c
c)
c a - b
d)
a - b c
9.
An algorithm needs to find the fastest path between two nodes in a network designed as a tree. Which property of trees guarantees that such a path is the only one?
a)
Every node must have at least one child.
b)
A tree has no parent nodes.
c)
A tree has n-1 edges.
d)
The simple path between any two vertices is unique.
10.
An information system needs to model a company's organizational chart. Which term best describes the entire chart?
a)
A leaf node
b)
A forest
c)
A simple path
d)
A rooted tree
11.
From the given nodes, 63, 9, 19... After inserting the first three nodes (63, 9, 19) into an AVL tree, what is the first type of rotation required?
a)
Left rotation (RR)
b)
Right rotation (LL)
c)
Right-left rotation (RL)
d)
Left-right rotation (LR)
12.
Given the logical representations of two tree data structures, which of the following properties can be used to distinguish a binary heap from a binary search tree (BST)?
a)
Nodes contain values where left children are always smaller and right children are always larger than the parent
b)
The tree is represented as a linked structure or array
c)
Every node has at most two children
d)
Nodes are arranged so that the tree satisfies the heap property but not necessarily the BST property
13.
Given the nodes 63, 9, 19, 27, 18, 108, 99, 81 inserted in that order into an AVL tree, what is the minimum number of rotations required to maintain balance?
a)
0
b)
2
c)
3
d)
1
14.
Given the nodes 65, 81, 19, and 36, consider the following trees:
a)
1 and 2 only
b)
2 and 3 only
c)
1 only
d)
4 - All of the above.
15.
How many rotations are required at most to rebalance an AVL tree after insertion?
a)
1
b)
4 rotations
c)
3
d)
2
16.
How many total rotations are required to maintain balance after inserting the entire sequence 63, 9, 19, 27, 18, 108, 99, 81 into an AVL tree?
a)
6
b)
4
c)
2
d)
3
17.
If a node has no parent in a tree, what is it called?
a)
Internal Node
b)
Leaf Node
c)
Degree node
d)
Root node
18.
If you call setRight(n, el) on a node n that already has a right child, what is the outcome based on standard tree pseudo-code?
a)
The operation fails and returns an error.
b)
The new element el is added as a grandchild.
c)
The new node is ignored.
d)
The existing right child and its entire subtree are replaced by the new node.
19.
In a complete binary tree, what is the number of vertices at level L (assuming the root is at level 0)?
a)
L^2
b)
2L
c)
2^L
d)
2^(L-1)
20.
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:\?
a)
Documents is a descendant of C:\
b)
Documents is a child of C:\
c)
Documents is a sibling of C:\
d)
Documents is an ancestor of C:\
21.
In a heap implemented as an array with 1-based indexing, what is the index of the parent node of the element at index i?
a)
2i + 1
b)
i - 1
c)
i / 2
d)
2i
22.
In a min-heap, where is the minimum value located?
a)
At the rightmost leaf node
b)
At any leaf node
c)
At the leftmost leaf node
d)
At the root node
23.
In a standard tree definition, the level or depth of the root vertex is always:
a)
1
b)
-1
c)
0
d)
Variable depending on the tree
24.
In an array representation of a binary tree (1-based indexing), the parent of a node at index k is located at which index?
a)
2k
b)
2k + 1
c)
k + 1
d)
floor(k/2)
25.
In an array representation of an almost complete binary tree (using 1-based indexing), a node is located at index k=5. Where is its left child located?
a)
Index 2
b)
Index 6
c)
Index 10
d)
Index 11
26.
In an array-based max-heap, if the element at index i violates the heap property by being smaller than one of its children, which operation restores the heap property?
a)
Bubble up (sift up)
b)
Complete tree reconstruction
c)
Level order traversal
d)
Heapify (sift down) starting at index i
27.
In the ExprToSyntaxTree algorithm (Postfix to Expression Tree), what is the purpose of the stack s?
a)
To evaluate the final expression.
b)
To store the initial infix expression.
c)
To convert the infix expression to postfix.
d)
To hold temporary tree nodes during the tree's construction.
28.
In the Java BTNode class, the <T> signifies:
a)
The tree's name.
b)
The traversal type.
c)
That the node is a terminal (leaf) node.
d)
A generic type parameter, allowing the node to hold any type of data.
29.
In the context of tree traversals, which term best describes the utility of "Deleting nodes safely by processing children first"?
a)
Preorder
b)
Postorder
c)
Inorder
d)
Depth-First
30.
In the context of tree traversals, which term best describes the utility of "Duplicating a tree structure exactly"?
a)
Preorder
b)
Postorder
c)
Inorder
d)
Breadth-First
31.
How many direct children does Uranus have?
a)
5
b)
4
c)
3
d)
2
32.
Match the term: Degree of a tree
a)
A collection of disconnected trees.
b)
The maximum number of children any single node has.
c)
A node with no children.
d)
The longest path from the root to a leaf.
33.
Match the term: Forest
a)
A collection of disconnected trees.
b)
The maximum number of children any single node has.
c)
A node with no children.
d)
A sequence of connected vertices.
34.
Match the term: Height
a)
The maximum number of children any single node has.
b)
The longest path from the root to a leaf.
c)
A collection of disconnected trees.
d)
A sequence of connected vertices.
35.
Match the term: Leaf
a)
A sequence of connected vertices.
b)
The longest path from the root to a leaf.
c)
A node with no children.
d)
A collection of disconnected trees.
36.
Match the term: Path
a)
A node with no children.
b)
A sequence of connected vertices.
c)
The longest path from the root to a leaf.
d)
The maximum number of children any single node has.
37.
Match the term: getRoot(T)
a)
Attaches a new node as the left child.
b)
Creates a new, empty tree structure.
c)
Returns the starting point for traversing the tree T.
38.
Match the term: isEmpty(T)
a)
Attaches a new node as the left child of n.
b)
Checks if a given node n has any children.
c)
Checks if the tree T has any nodes at all.
39.
Match the term: isLeaf(n)
a)
Creates a new, empty tree structure.
b)
Checks if the tree T has any nodes at all.
c)
Checks if a given node n has any children.
40.
Match the term: new(btree)
a)
Checks if a given node n has any children.
b)
Returns the starting point for traversing the tree T.
c)
Creates a new, empty tree structure.
41.
Match the term: setLeft(n, el)
a)
Checks if the tree T has any nodes.
b)
Returns the starting point for traversing the tree.
c)
Attaches a new node as the left child of n.
42.
The ExprToSyntaxTree algorithm uses which data structure to manage tree nodes while building the tree?
a)
Queue
b)
Stack
c)
Array
d)
Hash Map
43.
The Java constructor public BTNode(T el) calls this(el, null, null);. What is the purpose of this line?
a)
To create a recursive node structure.
b)
To initialize a new empty tree.
c)
To declare a new generic type T.
d)
To call the other constructor, reusing its logic to set children to null.
44.
The degree of a tree is defined by:
a)
The total number of nodes in the tree.
b)
The height of the tree.
c)
The number of leaf nodes.
d)
The maximum degree of any vertex in the tree.
45.
The height of a single-node tree is:
a)
-1
b)
0
c)
1
d)
Undefined
46.
The info part of a btnode record holds the actual _______ of the node.
a)
Pointer
b)
Height
c)
Data
d)
Index
47.
The isLeaf(n) operation is given a btnode n. Why would it return false if n is null?
a)
This is a trick question; it would return true.
b)
Because a null value represents an empty tree, not a leaf.
c)
To prevent a NullPointerException when checking n.left and n.right.
d)
Because a null value represents a node with children.
48.
The isLeaf(n) operation returns true if and only if:
a)
n.right is null
b)
n.left is null
c)
n is not null
d)
n.left is null AND n.right is null
49.
The new(btnode, el) constructor is ideal for creating a new _______ node.
a)
Root
b)
Internal
c)
Leaf
d)
Full
50.
The new(btree) operation initializes the root pointer to what value?
a)
The first node created
b)
A dummy node
c)
Undefined
d)
null
51.
The number of children a specific node has is referred to as its:
a)
Height
b)
Depth
c)
Degree
d)
Level
52.
The operation isEmpty(T) returns true if T.root is:
a)
0
b)
-1
c)
Undefined
d)
null
53.
The term "ordered binary tree" implies that:
a)
The tree must be a complete binary tree.
b)
The nodes are stored in an array.
c)
The tree is sorted.
d)
The positions of the left and right children are distinct and meaningful.
54.
The toString(T) operation typically starts by calling toString(n) on which node?
a)
The base
b)
The root
c)
The last leaf
d)
The middle node
55.
The toString(n) operation shown in the slides is based on which traversal?
a)
Inorder
b)
Breadth-First
c)
Preorder
d)
Postorder
56.
To build a syntax tree from the postfix expression "A B + C *", what is the last operation performed by the ExprToSyntaxTree algorithm?
a)
A new tree with as the root is pushed onto the stack
b)
A new tree with + as the root is pushed onto the stack
c)
The stack is initialized
d)
A node for A is pushed onto the stack
57.
To create a syntax tree, the algorithm first converts the infix expression to:
a)
Prefix
b)
Postfix
c)
Infix
d)
Reverse-Infix
58.
True or False: A Preorder traversal of a syntax tree yields the postfix expression.
a)
True
b)
False
59.
True or False: A full binary tree can have nodes with only one child.
a)
True
b)
False
60.
True or False: A node's ancestors include its siblings.
a)
True
b)
False
61.
True or False: A queue is the essential data structure for implementing a recursive Preorder traversal.
a)
True
b)
False
62.
True or False: A rooted tree must have exactly one node with no parent.
a)
False
b)
True
63.
True or False: A tree with 10 vertices will have exactly 9 edges.
a)
False
b)
True
64.
True or False: An almost complete binary tree is poorly suited for an array representation due to wasted space.
a)
True
b)
False
65.
True or False: Grandchildren are considered direct children in a tree.
a)
True
b)
False
66.
True or False: In a tree, the path between any two vertices is always unique.
a)
False
b)
True
67.
True or False: K-ary Tree Representation 1 ("One pointer per potential child") is highly space-efficient for non-uniform trees.
a)
True
b)
False
68.
True or False: The "first-child, next-sibling" representation uses three pointers per node.
a)
True
b)
False
69.
True or False: The ExprToSyntaxTree algorithm works directly on the infix expression to build the tree.
a)
True
b)
False
70.
True or False: The height of a tree is defined by the level of its root node.
a)
True
b)
False
71.
True or False: The isEmpty(T) operation checks if the number of nodes is zero by looking at the T.root pointer.
a)
True
b)
False
72.
True or False: The isLeaf(n) operation would return true for an internal node.
a)
True
b)
False
73.
True or False: The setRoot(T, n) operation creates a new node from raw data and sets it as the root.
a)
True
b)
False
74.
True or False: The visit action in a Postorder traversal happens before traversing the left and right subtrees.
a)
True
b)
False
75.
Two nodes that have the same parent are called:
a)
Cousins
b)
Children
c)
Siblings
d)
Neighbors
76.
What does the getParent(n) operation return?
a)
A list of all ancestors of n.
b)
The direct parent node of n.
c)
A boolean indicating if n has a parent.
d)
The root of the tree.
77.
What is a "subtree"?
a)
A tree with only one level.
b)
A synonym for a forest.
c)
A tree where every node is a leaf.
d)
Any node in a tree and all of its descendants.
78.
What is the degree of Zeus in this tree?
a)
2
b)
3
c)
5
d)
4
79.
What is the maximum allowed difference in height between the left and right subtrees of any node in an AVL tree?
a)
0
b)
2
c)
-1
d)
1
80.
What is the relationship between Zeus and Apollo in the tree structure?
a)
Cousins
b)
Uncle-Nephew
c)
Parent-Child
d)
Sibling
81.
What is the specific term for the topmost node in a tree?
a)
The Leaf
b)
The Base
c)
The Root
d)
The Parent
82.
What key property must a binary heap satisfy besides being complete?
a)
Nodes store only unique values
b)
Each level of the heap contains nodes with increasing values
c)
Nodes have unordered values with no relation to their children
d)
All nodes have values greater than their children (max-heap) or less than their children (min-heap)
83.
What level is Athena in, if Uranus is at level 0?
a)
4
b)
1
c)
2
d)
3
84.
Which data structure is commonly used to implement a heap?
a)
Linked list
b)
Hash table
c)
Array
d)
Binary tree with pointers
85.
Which of the following best describes the structure of a heap?
a)
A binary tree with all levels fully filled except possibly the last, which is filled from right to left
b)
A balanced binary search tree with random node filling
c)
A tree with variable number of child nodes and no specific filling order
d)
A binary tree with all levels fully filled except possibly the last, which is filled from left to right
86.
Which of the following is NOT a property of a tree?
a)
There is a unique path between any two nodes
b)
There are no cycles
c)
It is a non-linear structure
d)
Every node can have multiple parents
87.
Which of the following is the biggest drawback of using K-ary Tree Representation 1 ("One pointer per potential child")?
a)
Inability to represent binary trees
b)
Slow child retrieval time
c)
Poor space efficiency for non-uniform trees
d)
Slow parent retrieval time
88.
Which statement best describes the property of a HEAP TREE (Max-Heap)?
a)
Every parent node has a value less than or equal to its children
b)
Every leaf node is greater than its parent
c)
All nodes have exactly two children
d)
Every parent node has a value greater than or equal to its children
89.
Which term describes a general strategy that "explores as deep as possible before backtracking"?
a)
Breadth-First
b)
Depth-First
c)
Level-Order
d)
Linear Search
90.
Which traversal method is best described as "Retrieving data in sorted order from a Binary Search Tree (BST)"?
a)
Preorder
b)
Postorder
c)
Breadth-First
d)
Inorder
91.
Which traversal method is best described as "Visiting nodes level-by-level"?
a)
Depth-First
b)
Inorder
c)
Breadth-First
d)
Preorder
92.
You are designing a system where search performance is the most critical factor. According to the tree theorems, what should be your primary goal for the tree's structure?
a)
Maximize the number of leaf nodes.
b)
Ensure the tree is a full binary tree.
c)
Use a k-ary tree with a large k.
d)
Keep the height of the tree as low as possible.
Reset
