Design and Analysis of Algorithms MCQs - Unit 2
A
push and pop
B
insert and delete
C
read and write
D
union and find
Correct Answer
union and find
A
the number of sets
B
the set (root of the tree) containing element i
C
the size of the array
D
the largest element
Correct Answer
the set (root of the tree) containing element i
A
becomes the root
B
becomes a subtree of the tree with more nodes
C
is deleted
D
is copied twice
Correct Answer
becomes a subtree of the tree with more nodes
A
path expansion
B
path compression
C
tree deletion
D
weighted union
Correct Answer
path compression
A
queues
B
stacks only
C
trees
D
hash tables only
Correct Answer
trees
A
less than its children
B
equal to the root only
C
unrelated to its children
D
greater than or equal to the values of its children
Correct Answer
greater than or equal to the values of its children
A
full ternary tree
B
complete binary tree
C
linked list
D
binary search tree
Correct Answer
complete binary tree
A
⌊log₂ n⌋
B
n
C
n²
D
n/2
Correct Answer
⌊log₂ n⌋
A
O(1) always
B
O(n²)
C
O(n log n)
D
O(log n)
Correct Answer
O(log n)
A
O(n log n)
B
O(n²)
C
O(n)
D
O(log n)
Correct Answer
O(n log n)
A
O(n²)
B
O(n)
C
O(log n)
D
O(n log n) only
Correct Answer
O(n)
A
the last leaf only
B
the root
C
a random node
D
the smallest element
Correct Answer
the root
A
in place using O(1) extra space
B
using O(n) extra space
C
using O(n²) extra space
D
without comparisons
Correct Answer
in place using O(1) extra space
A
breadth-first search only
B
random search only
C
sorting only
D
depth-first search with bounding functions
Correct Answer
depth-first search with bounding functions
A
kill nodes that cannot lead to a solution
B
add more nodes
C
sort the nodes
D
store the solutions
Correct Answer
kill nodes that cannot lead to a solution
A
row only
B
row, column or diagonal
C
column only
D
corner
Correct Answer
row, column or diagonal
Correct Answer
2
Correct Answer
92
A
the number of weights
B
zero always
C
the largest weight
D
a given value M
Correct Answer
a given value M
A
degree
B
diameter
C
chromatic number
D
clique size
Correct Answer
chromatic number
A
4 colors
B
3 colors
C
5 colors
D
6 colors
Correct Answer
4 colors
A
visits every edge exactly once
B
visits only two vertices
C
has no vertices
D
visits every vertex exactly once and returns to the start
Correct Answer
visits every vertex exactly once and returns to the start
A
dead node
B
leaf node only
C
live node
D
root node only
Correct Answer
live node
A
E-node
B
D-node
C
X-node
D
Z-node
Correct Answer
E-node
A
have a solution that can be built step by step with constraints
B
have no constraints
C
require no search
D
use only sorting
Correct Answer
have a solution that can be built step by step with constraints
Fill in the Blanks
26
The two operations on disjoint sets are union and ______.
Correct Answer
find
27
In the weighted union rule, the tree with fewer nodes becomes a ______ of the other tree.
Correct Answer
subtree (child)
28
The collapsing rule is also called ______ compression.
Correct Answer
path
29
A heap is a complete ______ tree.
Correct Answer
binary
30
The root of a max-heap holds the ______ element.
Correct Answer
largest
31
The time complexity of heap sort is ______.
Correct Answer
O(n log n)
32
Building a heap from n elements takes ______ time.
Correct Answer
O(n)
33
Backtracking uses ______ functions to kill nodes that cannot lead to a solution.
Correct Answer
bounding
34
In the n-queens problem, no two queens may be in the same row, column or ______.
Correct Answer
diagonal
35
The 4-queens problem has ______ solutions.
Correct Answer
2
36
The 8-queens problem has ______ solutions.
Correct Answer
92
37
In the sum of subsets problem, we find subsets whose sum equals a given value ______.
Correct Answer
M
38
The smallest number of colors needed to color a graph is its ______ number.
Correct Answer
chromatic
39
A Hamiltonian cycle visits every vertex ______ once.
Correct Answer
exactly
40
In backtracking, the node currently being expanded is called the ______.
Correct Answer
E-node