☑ MCQ PRACTICE

Design and Analysis of Algorithms Unit 2

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

📚 Design and Analysis of Algorithms
📖 Unit 2
🎯 MCQs
Design and Analysis of Algorithms MCQs - Unit 2

Design and Analysis of Algorithms MCQs - Unit 2

1

The two main operations on disjoint sets are

A push and pop
B insert and delete
C read and write
D union and find
Correct Answer union and find
2

The Find(i) operation returns

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
3

In the weighted union rule, the tree with fewer nodes

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
4

The collapsing rule is also called

A path expansion
B path compression
C tree deletion
D weighted union
Correct Answer path compression
5

Disjoint sets are usually represented using

A queues
B stacks only
C trees
D hash tables only
Correct Answer trees
6

In a max-heap, the value of a parent node is

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
7

A heap is a

A full ternary tree
B complete binary tree
C linked list
D binary search tree
Correct Answer complete binary tree
8

The height of a heap with n elements is

A ⌊log₂ n⌋
B n
C n²
D n/2
Correct Answer ⌊log₂ n⌋
9

Inserting an element into a heap takes

A O(1) always
B O(n²)
C O(n log n)
D O(log n)
Correct Answer O(log n)
10

The time complexity of heap sort is

A O(n log n)
B O(n²)
C O(n)
D O(log n)
Correct Answer O(n log n)
11

Building a heap from n elements takes

A O(n²)
B O(n)
C O(log n)
D O(n log n) only
Correct Answer O(n)
12

In a max-priority queue implemented with a heap, the delete-max operation removes

A the last leaf only
B the root
C a random node
D the smallest element
Correct Answer the root
13

Heap sort sorts the array

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
14

Backtracking is a systematic search of the state space tree using

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
15

The purpose of a bounding function in backtracking is to

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
16

In the n-queens problem, no two queens may be placed in the same

A row only
B row, column or diagonal
C column only
D corner
Correct Answer row, column or diagonal
17

The number of solutions of the 4-queens problem is

A 1
B 2
C 4
D 8
Correct Answer 2
18

The number of solutions of the 8-queens problem is

A 8
B 64
C 92
D 40
Correct Answer 92
19

In the sum of subsets problem, we find subsets of the given weights whose sum equals

A the number of weights
B zero always
C the largest weight
D a given value M
Correct Answer a given value M
20

The smallest number of colors needed to color a graph is called its

A degree
B diameter
C chromatic number
D clique size
Correct Answer chromatic number
21

According to the four color theorem, any planar map can be colored using at most

A 4 colors
B 3 colors
C 5 colors
D 6 colors
Correct Answer 4 colors
22

A Hamiltonian cycle in a graph

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
23

In backtracking, a node that has been generated and whose children have not all been generated is a

A dead node
B leaf node only
C live node
D root node only
Correct Answer live node
24

In backtracking, the live node whose children are currently being generated is the

A E-node
B D-node
C X-node
D Z-node
Correct Answer E-node
25

Backtracking is generally applied to problems that

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
← Back to All MCQs