Practice Design And Analysis Of Algorithms Multiple Choice Questions with Answers Quiz-1

Q.1.

Which of the following is false in the case of a spanning tree of a graph G?

it is tree that spans g
it is a subgraph of the g
it includes every vertex of the g
it can be either cyclic or acyclic

Q.2.

Which of the following problems is NOT solved using dynamic programming?

0/1 knapsack problem
matrix chain multiplication problem
edit distance problem
fractional knapsack problem

Q.3.

Which of the following problems should be solved using dynamic programming?

mergesort
binary search
longest common subsequence
quicksort

Q.4.

Problems that cannot be solved by any algorithm are called?

tractable problems
intractable problems
undecidable problems
decidable problems

Q.5.

What is the time complexity of Kruskal’s algorithm?

o(log v)
o(e log v)
o(e2)
o(v log e)

Q.6.

What will be the recurrence relation of the code of recursive selection sort?

t(n) = 2t(n/2) + n
t(n) = 2t(n/2) + c
t(n) = t(n-1) + n
t(n) = t(n-1) + c

Q.7.

Master’s theorem is used for?

solving recurrences
solving iterative relations
analysing loops
calculating the time complexity of any code

Q.8.

What is the running time of the Floyd Warshall Algorithm?

big-oh(v)
theta(v2)
big-oh(ve)
theta(v3)

Q.9.

Which of the following sorting algorithm is NOT stable?

selection sort
brick sort
bubble sort
merge sort

Q.10.

What is the worst case time complexity of a quick sort algorithm?

o(n)
o(n log n)
o(n2)
o(log n)

Q.11.

Which of the following is false about the Kruskal’s algorithm?

it is a greedy algorithm
it constructs mst by selecting edges in increasing order of their weights
it can accept cycles in the mst
it uses union-find data structure

Q.12.

What is the running time of Bellmann Ford Algorithm?

o(v)
o(v2)
o(elogv)
o(ve)

Q.13.

Which of the following is the most commonly used data structure for implementing Dijkstra’s Algorithm?

max priority queue
stack
circular queue
min priority queue

Q.14.

What is the LCM of two coprime numbers?

1
0
addition of two coprime numbers
multiplication of two coprime numbers

Q.15.

Which of the following is false about Prim’s algorithm?

it is a greedy algorithm
it constructs mst by selecting edges in increasing order of their weights
it never accepts cycles in the mst
it can be implemented using the fibonacci heap

Q.16.

What is the objective of tower of hanoi puzzle?

to move all disks to some other rod by following rules
to divide the disks equally among the three rods by following rules
to move all disks to some other rod in random order
to divide the disks equally among three rods in random order

Q.17.

Who formulated the first ever algorithm for solving the Hamiltonian path problem?

martello
monte carlo
leonard
bellman

Q.18.

How many sub arrays does the quick sort algorithm divide the entire array into?

one
two
three
four

Q.19.

Which of the following sorting algorithms is used along with quick sort to sort the sub arrays?

merge sort
shell sort
insertion sort
bubble sort

Q.20.

Problems that can be solved in polynomial time are known as?

intractable
tractable
decision
complete

Support mcqgeeks.com by disabling your adblocker.