Design and Analysis of Algorithms MCQs - Unit 4
A
a random choice
B
a globally optimal choice always verified
C
no choice
D
a locally optimal choice
Correct Answer
a locally optimal choice
A
maximize the total profit
B
minimize the number of jobs
C
minimize the deadlines
D
maximize the number of machines
Correct Answer
maximize the total profit
A
non-decreasing order of profit
B
non-increasing order of profit
C
alphabetical order
D
random order
Correct Answer
non-increasing order of profit
A
weight only
B
profit/weight ratio
C
profit only
D
item number
Correct Answer
profit/weight ratio
A
0/1 knapsack problem always
B
travelling salesperson problem
C
fractional knapsack problem
D
n-queens problem
Correct Answer
fractional knapsack problem
A
the minimum total edge weight
B
the maximum total edge weight
C
no edges
D
only one vertex
Correct Answer
the minimum total edge weight
A
n edges
B
n ā 1 edges
C
n + 1 edges
D
n² edges
Correct Answer
n ā 1 edges
A
sorting all edges and skipping cycles
B
removing the heaviest edge
C
growing a single tree by adding the cheapest edge connecting it to a new vertex
D
coloring vertices
Correct Answer
growing a single tree by adding the cheapest edge connecting it to a new vertex
A
adds edges in increasing order of weight if they do not form a cycle
B
adds edges in decreasing order of weight
C
adds all edges
D
uses a queue of vertices only
Correct Answer
adds edges in increasing order of weight if they do not form a cycle
A
O(V³)
B
O(E log E)
C
O(1)
D
O(E!)
Correct Answer
O(E log E)
A
O(V²)
B
O(V³)
C
O(E³)
D
O(log V)
Correct Answer
O(V²)
A
all-pairs shortest path problem
B
single-source shortest path problem
C
travelling salesperson problem
D
n-queens problem
Correct Answer
single-source shortest path problem
A
O(V²) time
B
O(V³) time
C
O(log V) time
D
O(1) time
Correct Answer
O(V²) time
A
positive edge weights
B
negative edge weights
C
no edges
D
only one vertex
Correct Answer
negative edge weights
A
BFS, DFS and Dijkstra
B
inorder, preorder and postorder
C
push, pop and peek
D
sort, search and merge
Correct Answer
inorder, preorder and postorder
A
sorted (ascending) order
B
descending order only
C
random order
D
reverse insertion order
Correct Answer
sorted (ascending) order
A
stack
B
heap
C
queue
D
hash table
Correct Answer
queue
A
queue only
B
heap only
C
array only
D
stack (or recursion)
Correct Answer
stack (or recursion)
A
O(V²) always
B
O(E²)
C
O(V + E)
D
O(V log V) only
Correct Answer
O(V + E)
A
BFS or DFS
B
only quick sort
C
only binary search
D
only Floyd's algorithm
Correct Answer
BFS or DFS
A
disconnects the graph
B
adds more edges
C
does nothing to the graph
D
makes the graph complete
Correct Answer
disconnects the graph
A
disconnected
B
acyclic
C
directed
D
biconnected
Correct Answer
biconnected
A
low values
B
BFS levels
C
edge weights only
D
vertex colors
Correct Answer
low values
A
tree edge
B
cross edge
C
forward edge
D
back edge
Correct Answer
back edge
Correct Answer
n
Fill in the Blanks
26
The greedy method makes a ______ optimal choice at each step.
Correct Answer
locally
27
In job sequencing with deadlines, jobs are considered in ______ order of profit.
Correct Answer
decreasing (non-increasing)
28
In the fractional knapsack problem, items are considered in decreasing order of ______ ratio.
Correct Answer
profit/weight
29
A spanning tree of a graph with n vertices has ______ edges.
Correct Answer
n ā 1
30
Prim's algorithm grows a single ______ by adding the cheapest connecting edge.
Correct Answer
tree
31
Kruskal's algorithm adds edges in increasing order of weight if they do not form a ______.
Correct Answer
cycle
32
The time complexity of Kruskal's algorithm is ______.
Correct Answer
O(E log E)
33
Dijkstra's algorithm fails when the graph has ______ edge weights.
Correct Answer
negative
34
The time complexity of Dijkstra's algorithm with an array is O(______).
Correct Answer
V²
35
Breadth-first search uses a ______.
Correct Answer
queue
36
Depth-first search uses a ______ (or recursion).
Correct Answer
stack
37
The time complexity of BFS with an adjacency list is O(______).
Correct Answer
V + E
38
A vertex whose removal disconnects the graph is called an ______ point.
Correct Answer
articulation
39
A graph with no articulation points is called ______.
Correct Answer
biconnected
40
The inorder traversal of a binary search tree gives the keys in ______ order.
Correct Answer
sorted (ascending)