ā˜‘ MCQ PRACTICE

Design and Analysis of Algorithms Unit 4

Practice objective questions for quick revision and examination preparation. Try answering each question before revealing the answer.

šŸ“š Design and Analysis of Algorithms
šŸ“– Unit 4
šŸŽÆ MCQs
Design and Analysis of Algorithms MCQs - Unit 4

Design and Analysis of Algorithms MCQs - Unit 4

1

The greedy method makes at each step

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
2

In job sequencing with deadlines, the objective is to

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
3

In the greedy solution of job sequencing with deadlines, the jobs are first sorted in

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
4

The greedy solution of the fractional knapsack problem picks items in decreasing order of

A weight only
B profit/weight ratio
C profit only
D item number
Correct Answer profit/weight ratio
5

The greedy method gives an optimal solution for the

A 0/1 knapsack problem always
B travelling salesperson problem
C fractional knapsack problem
D n-queens problem
Correct Answer fractional knapsack problem
6

A minimum cost spanning tree is a spanning tree with

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
7

A spanning tree of a graph with n vertices has

A n edges
B n āˆ’ 1 edges
C n + 1 edges
D n² edges
Correct Answer n āˆ’ 1 edges
8

Prim's algorithm builds a minimum spanning tree by

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
9

Kruskal's algorithm

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
10

The time complexity of Kruskal's algorithm is

A O(V³)
B O(E log E)
C O(1)
D O(E!)
Correct Answer O(E log E)
11

The time complexity of Prim's algorithm with an adjacency matrix is

A O(V²)
B O(V³)
C O(E³)
D O(log V)
Correct Answer O(V²)
12

Dijkstra's algorithm solves the

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
13

Dijkstra's algorithm with an array takes

A O(V²) time
B O(V³) time
C O(log V) time
D O(1) time
Correct Answer O(V²) time
14

Dijkstra's algorithm may fail when the graph has

A positive edge weights
B negative edge weights
C no edges
D only one vertex
Correct Answer negative edge weights
15

The three standard traversals of a binary tree are

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
16

The inorder traversal of a binary search tree gives the keys in

A sorted (ascending) order
B descending order only
C random order
D reverse insertion order
Correct Answer sorted (ascending) order
17

Breadth-first search uses a

A stack
B heap
C queue
D hash table
Correct Answer queue
18

Depth-first search uses a

A queue only
B heap only
C array only
D stack (or recursion)
Correct Answer stack (or recursion)
19

The time complexity of BFS on a graph with an adjacency list is

A O(V²) always
B O(E²)
C O(V + E)
D O(V log V) only
Correct Answer O(V + E)
20

Connected components of an undirected graph can be found using

A BFS or DFS
B only quick sort
C only binary search
D only Floyd's algorithm
Correct Answer BFS or DFS
21

An articulation point is a vertex whose removal

A disconnects the graph
B adds more edges
C does nothing to the graph
D makes the graph complete
Correct Answer disconnects the graph
22

A graph with no articulation points is called

A disconnected
B acyclic
C directed
D biconnected
Correct Answer biconnected
23

Biconnected components are found using DFS numbers and

A low values
B BFS levels
C edge weights only
D vertex colors
Correct Answer low values
24

In DFS of an undirected graph, an edge from a vertex to one of its ancestors is a

A tree edge
B cross edge
C forward edge
D back edge
Correct Answer back edge
25

A graph with n vertices and no edges has how many connected components?

A n
B 1
C 0
D n āˆ’ 1
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)
← Back to All MCQs