WorksheetsG&TLQ
Total questions: 76
Worksheet time: 17mins
It is specially designed node (or data items) in a tree
(a)
The (a) of a tree is the maximum level of any node in a given tree.
Which of the following statement about binary tree is CORRECT?
Every binary tree is either complete or full
Every complete binary tree is also a full binary tree
Every full binary tree is also a complete binary tree
A binary tree cannot be both complete and full
Which type of traversal of binary search tree outputs the value in sorted order?
Pre-order
Post-order
In-Order
None
A binary search tree is generated by inserting in order the following integers:
50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24
The number of the node in the left sub-tree and right sub-tree of the root, respectively, is
(4, 7)
(7, 4)
(8, 3)
(3, 8)
In delete operation of BST, we need inorder successor (or predecessor) of a node when the node to be deleted has both left and right child as non-empty. Which of the following is true about inorder successor needed in delete operation?
Inorder Successor is always a leaf node
Inorder successor is always either a leaf node or a node with empty left child
Inorder successor may be an ancestor of the node
Inorder successor is always either a leaf node or a node with empty right child
What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.
2
3
4
5
In the balanced binary tree in the figure given below, how many nodes will become unbalanced when a node is inserted as a child of the node “g”?
1
3
7
8
Which of the following sequences denotes the post order traversal sequence of the tree?
f e g c d b a
g c b d a f e
g c d b f e a
f e d g c b a
Example of linear data structure except
array
tree
queue
stack
Which of these tree traversal methods is used to output the contents of a binary tree in ascending order?
Pre-Order
In-Order
Post-Order
Monastic Orders
In preorder traversal of a binary tree the second step is ____________
traverse the right subtree
traverse the left subtree
traverse right subtree and visit the root
visit the root
What is the value of the ROOT node in this Tree?
35
24
42
20
Tree
data structure similar to a graph, with no loops.
an object in a graph also known as a vertex
a join of relationship between nodes - also know as an arc
the starting node in a rooted tree structure from which all other nodes branch off./
How many leaf are there in the tree?
1
3
4
7
What are the 3 depth traversals for a tree data structure?
Pre-, In- and Post-order
Pro-, In- and Past-order
Pre-, Out- and Post-order
Pre-, In- and New-order
A connected, undirected graph with no cycles
Tree
Stack
List
Vector
Data within a tree structure is stored in a h (a) rather than linear
Tree data structures begin at the bottom and work through to the top
True
False
What is the maximum number of children each node can contain in a binary tree?
(a)
In a balanced binary tree, the depth of each subtree never differs by more than (a)
Select the correct order of steps to follow when constructing a binary tree
Start at the root
If the item is less than the root - add to the left
If the item is more than the root - add to the right
Start at the root
If the item is less than the root - add to the right
If the item is more than the root - add to the left
Start at the bottom
If the item is less than the root - add to the left
If the item is more than the root - add to the right
End at the root
Start at the bottom
If the item is less than the root - add to the right
If the item is more than the root - add to the left
End at the root
Select the correct tree traversal method for the following description:
Root - Left Subtree - Right Subtree
Pre-Order
In-Order
Post-Order
Select the correct tree traversal method for the following description:
Left Subtree - Root - Right Subtree
Pre-Order
In-Order
Post-Order
Select the correct tree traversal method for the following description:
Left Subtree - Right Subtree - Root
Pre-Order
In-Order
Post-Order
Post-Order traversal is used to create a copy of the original tree
True
False
Select the correct response for a pre-order traversal
A B D E G H C F I J
D B E G H A I F J C
D G H E B I J F C A
Select the correct response for a post-order traversal
G H D I E B J F C A
A B D G H E I C F J
G D H B E J A J F C
A binary tree data structure can be implemented as a diagram or as an (a) of records
Select all ways a leaf (node with no children) could be represented in a tree structure array table
2 answers
-1
Null
0
Enter the missing value in the array index table for this tree data structure
(a)
Enter the missing value in the array index table for this tree data structure
(a)
Which value in this array record table indicates a leaf (node with no child)?
(a)
Root
data structure similar to a graph, with no loops.
an object in a graph also known as a vertex
a join of relationship between nodes - also know as an arc
the starting node in a rooted tree structure from which all other nodes branch off./
How many leaf are there in the tree?
1
3
4
7
What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.
2
3
4
5
AVL tree got its name after its
Adelson-Velsky and Landis
Adam Velsky Lenin
Adelson Vel Landis
None
The sequence of insertion 10,12,14 will lead to imbalance by using which rotation can be used to balance the tree
RR rotation
LL rotation
LR rotation
RL rotation
Why we need to a binary tree which is height balanced?
a) to avoid formation of skew trees
b) to save memory
c) to attain faster memory access
d) to simplify storing
Given an empty AVL tree, how would you construct AVL tree when a set of numbers are given without performing any rotations?
a) just build the tree with the given input
b) find the median of the set of elements given, make it as root and construct the tree
c) use trial and error
d) use dynamic programming to build the tree
Is the following tree a valid splay tree?
no
yes
When splaying X, what is the first rotation performed?
zig-zig
zig-zag
zig
zag
When splaying X, which node do you rotate FIRST?
rotate T left around L
rotate X left around T
rotate S right around T
When splaying S, what is the first rotation performed?
zig-zag
zig-zig
zig
zag
When splaying S, which node do you rotate FIRST?
rotate S right around T
rotate T left around L
rotate X left around T
Post order traversal :
1a+b*c+d*e+f*g
1abc*+de*f+g*+
++a*bc*+*defg
abc+*+defg*+*
In Order traversal
40 20 50 10 30
40 50 20 30 10
10 20 30 40 50
50 40 20 30 10
What is the MAXIMUM number of nodes in a binary search tree with height = 5 ?
26-1
25-1
25
26
6
What is the MINIMUM number of nodes in a binary search tree with height = 5?
6
5
26-1
25-1
25
What is the worst-case runtime of lookUp/get in a binary search tree?
O(n)
O(logn)
O(1)
O(n2)
What is the worst-case runtime of lookUp/get in a *perfectly balanced* binary search tree?
O(logn)
O(n)
O(1)
O(n2)
Which method checks that two objects are equivalent?
toString
equals
compareTo
binarySearch
Binary Search works best on
Equally effective on sorted and unsorted lists
Unsorted lists
Sorted lists
None of the above
If the specified value is present binary search will return
true
false
the value
the position of the value
The graph shown contains NO cycles.
True
False
The graph shown contains NO cycles.
True
False
Create a minimal spanning tree, then find the minimum total cost.
30
39
47
50
Using Kruskal’s algorithm, which edge should you choose second?
AE
BD
DE
AB
Using Kruskal’s algorithm, which edge should you choose fourth?
AB
BC
BD
DE
30
A cycle is...
A path that starts and ends at different vertices.
A path that starts and ends at the same vertex where backtracking is allowed.
A path that starts and ends at the same vertex and uses every edge exactly once.
A path that starts and ends at the same vertex and does not use any edge more than once.
What is the weight of the minimum spanning tree according to Prim's Algorithm?
29
7
11
5
What is the weight of the minimum spanning tree according to Prim's algorithm?
7
9
10
16
How many leaf are there in the tree?
1
3
4
7
A __________ is a part of a graph or the whole graph redrawn.
network
graph
subgraph
vertice
What is the most accurate name for the highlighted edges in this picture?
Spanning Tree
Minimum Spanning Tree
Tree
Subgraph
True or false: The black edges in this graph show one possible spanning tree.
True
False: It shows the MINIMUM spanning tree
False: It does not show a spanning tree because there are cycles present
False: It does not show a spanning tree because it does not reach to every vertex
