☑ MCQ PRACTICE

Design and Analysis of Algorithms Unit 5

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

📚 Design and Analysis of Algorithms
📖 Unit 5
ðŸŽŊ MCQs
Design and Analysis of Algorithms MCQs - Unit 5

Design and Analysis of Algorithms MCQs - Unit 5

1

Branch and bound is mainly used to solve

A only sorting problems
B only searching problems
C only printing problems
D optimization problems
Correct Answer optimization problems
2

In LC (least-cost) branch and bound, the next E-node is the live node with

A the highest cost
B the oldest entry
C the newest entry
D the least cost
Correct Answer the least cost
3

FIFO branch and bound uses a

A stack
B heap only
C table of keys
D queue
Correct Answer queue
4

LIFO branch and bound uses a

A queue
B linked list only
C stack
D graph
Correct Answer stack
5

In branch and bound for a minimization problem, a node is killed if its lower bound is

A less than the best solution found so far
B zero
C greater than or equal to the best solution found so far
D negative
Correct Answer greater than or equal to the best solution found so far
6

In the branch and bound solution of the travelling salesperson problem, the lower bound is found using

A a sorted array
B a reduced cost matrix
C a hash table
D a binary tree
Correct Answer a reduced cost matrix
7

To solve the 0/1 knapsack problem by branch and bound as a minimization problem, the profits are

A squared
B ignored
C doubled
D negated
Correct Answer negated
8

The class P contains problems that can be solved

A in polynomial time by a deterministic algorithm
B only in exponential time
C only by non-deterministic machines
D by no algorithm
Correct Answer in polynomial time by a deterministic algorithm
9

The class NP contains problems that can be solved

A only in exponential time by any algorithm
B by no algorithm
C in polynomial time by a non-deterministic algorithm
D in logarithmic time only
Correct Answer in polynomial time by a non-deterministic algorithm
10

A non-deterministic algorithm uses the functions

A push, pop and peek
B read, write and seek
C choice, failure and success
D open, close and flush
Correct Answer choice, failure and success
11

A problem is NP-hard if

A it can be solved in linear time
B every problem in NP can be reduced to it in polynomial time
C it is in P
D it has no input
Correct Answer every problem in NP can be reduced to it in polynomial time
12

A problem is NP-complete if it is

A both in NP and NP-hard
B in P only
C neither in NP nor NP-hard
D NP-hard only
Correct Answer both in NP and NP-hard
13

Cook's theorem states that

A the satisfiability (SAT) problem is NP-complete
B sorting is NP-complete
C P is a subset of NP only
D binary search is NP-hard
Correct Answer the satisfiability (SAT) problem is NP-complete
14

The first problem proved to be NP-complete was

A travelling salesperson problem
B knapsack problem
C satisfiability (SAT)
D graph coloring
Correct Answer satisfiability (SAT)
15

If any NP-complete problem can be solved in polynomial time, then

A P = NP
B P ≠ NP
C NP = EXP
D all problems are unsolvable
Correct Answer P = NP
16

Which of the following decision problems is NP-complete?

A Binary search
B Sorting an array
C Hamiltonian cycle
D Finding the maximum element
Correct Answer Hamiltonian cycle
17

Which of the following problems has a polynomial-time algorithm?

A Travelling salesperson problem
B Hamiltonian cycle
C Graph coloring (decision, k â‰Ĩ 3)
D Single-source shortest path with non-negative weights
Correct Answer Single-source shortest path with non-negative weights
18

A â‰Īp B means that problem A is

A polynomial-time reducible to problem B
B harder than B always
C unrelated to B
D solved by B in constant time only
Correct Answer polynomial-time reducible to problem B
19

The clique decision problem is

A in P
B unsolvable
C NP-complete
D linear-time solvable
Correct Answer NP-complete
20

An NP-hard problem need not belong to

A P
B NP
C the set of all problems
D the set of languages
Correct Answer NP
21

Which of the following relationships is known to be true?

A P ⊆ NP
B NP ⊆ P
C P âˆĐ NP is empty
D NP = EXP
Correct Answer P ⊆ NP
22

The SAT problem asks whether

A a graph is connected
B an array is sorted
C a Boolean formula can be made true by some assignment of values
D a matrix is square
Correct Answer a Boolean formula can be made true by some assignment of values
23

Branch and bound differs from backtracking in that it

A uses bounds on the cost to prune and is used for optimization
B never prunes nodes
C uses only recursion
D does not use a state space tree
Correct Answer uses bounds on the cost to prune and is used for optimization
24

In the state space tree of branch and bound, the nodes that are generated but not yet expanded are the

A dead nodes
B answer nodes only
C root nodes only
D live nodes
Correct Answer live nodes
25

To show that a problem is NP-hard, we reduce

A the problem to sorting
B a known NP-hard problem to it
C the problem to binary search
D the problem to a constant
Correct Answer a known NP-hard problem to it

Fill in the Blanks

26 Branch and bound is mainly used to solve ______ problems.
Correct Answer optimization
27 In LC branch and bound, the next E-node is the live node with the ______ cost.
Correct Answer least
28 FIFO branch and bound uses a ______.
Correct Answer queue
29 LIFO branch and bound uses a ______.
Correct Answer stack
30 In the branch and bound solution of the TSP, the lower bound is found by reducing the cost ______.
Correct Answer matrix
31 P stands for ______ time.
Correct Answer Polynomial
32 NP stands for ______ Polynomial.
Correct Answer Non-deterministic
33 A non-deterministic algorithm uses the functions choice, failure and ______.
Correct Answer success
34 Cook's theorem states that the ______ problem is NP-complete.
Correct Answer satisfiability (SAT)
35 A problem is NP-complete if it is in NP and is ______.
Correct Answer NP-hard
36 The first problem proved to be NP-complete was ______.
Correct Answer satisfiability (SAT)
37 If any NP-complete problem can be solved in polynomial time, then P = ______.
Correct Answer NP
38 A â‰Īp B means that A is polynomial-time ______ to B.
Correct Answer reducible
39 NP-hard problems are at least as ______ as every problem in NP.
Correct Answer hard
40 The Hamiltonian cycle decision problem is ______-complete.
Correct Answer NP
← Back to All MCQs