MCQGeeks
CBSE
JEE
NTSE
NEET
English
UK Quiz
Quiz
Driving Test
Practice
Games
Quiz
Computer Science
Design And Analysis Of Algorithms
Quiz 2
Solution
Q.1.
Which of the following is not the algorithm to find the minimum spanning tree of the given graph?
boruvka’s algorithm
prim’s algorithm
kruskal’s algorithm
bellman–ford algorithm
Q.2.
How many priority queue operations are involved in Dijkstra’s Algorithm?
1
3
2
4
Q.3.
In what time can the Hamiltonian path problem can be solved using dynamic programming?
o(n)
o(n log n)
o(n2)
o(n2 2n)
Q.4.
What is a subset sum problem?
finding a subset of a set that has sum of elements equal to a given number
checking for the presence of a subset that has sum of elements equal to a given number and printing true or false based on the result
finding the sum of elements present in a set
finding the sum of all the subsets of a set
Q.5.
The problem of finding a path in a graph that visits every vertex exactly once is called?
hamiltonian path problem
hamiltonian cycle problem
subset sum problem
turnpike reconstruction problem
Q.6.
What is the average running time of a quick sort algorithm?
o(n2)
o(n)
o(n log n)
o(log n)
Q.7.
In which of the following cases, the maximum sum rectangle is thematrix itself?
when all the elements are negative
when all the elements are positive
when some elements are positive and some negative
when diagonal elements are positive and rest are negative
Q.8.
The shortest distance between a line and a point is achieved when?
a line is drawn at 90 degrees to the given line from the given point
a line is drawn at 180 degrees to the given line from the given point
a line is drawn at 60 degrees to the given line from the given point
a line is drawn at 270 degrees to the given line from the given point
Q.9.
Worst case is the worst case time complexity of Prim’s algorithm if adjacency matrix is used?
o(log v)
o(v2)
o(e2)
o(v log e)
Q.10.
To which class does the Euler’s circuit problem belong?
p class
np class
partition class
complete class
Q.11.
Which of the following statements is not a part of Chan’s algorithm?
eliminate points not in the hull
recompute convex hull from scratch
merge previously calculated convex hull
reuse convex hull from the previous iteration
Q.12.
Which of the following techniques can be used to search an element in an unsorted array?
iterative linear search
recursive binary search
iterative binary search
normal binary search
Q.13.
Which of the following strategies does the following diagram depict?
divide and conquer strategy
brute force
exhaustive search
backtracking
Q.14.
The Euler’s circuit problem can be solved in?
o(n)
o( n log n)
o(log n)
o(n2)
Q.15.
The problem of maximizing the sum of weights on edges connecting matched pairs of vertices is?
maximum- mass matching
maximum bipartite matching
maximum weight matching
maximum node matching
Q.16.
What is the length of an augmenting path?
even
odd
depends on graph
1
Q.17.
Who was the first person to solve the maximum matching problem?
jack edmonds
hopcroft
karp
claude berge
Q.18.
Which of the following problems is similar to that of a Hamiltonian path problem?
knapsack problem
closest pair problem
travelling salesman problem
assignment problem
Q.19.
What is the set partition problem?
finding a subset of a set that has sum of elements equal to a given number
checking for the presence of a subset that has sum of elements equal to a given number
checking whether the set can be divided into two subsets of with equal sum of elements and printing true or false based on the result
finding subsets with equal sum of elements
Q.20.
Which of the following is not true about subset sum problem?
the recursive solution has a time complexity of o(2n)
there is no known solution that takes polynomial time
the recursive solution is slower than dynamic programming solution
the dynamic programming solution has a time complexity of o(n log n)
Support mcqgeeks.com by disabling your adblocker.
×
Please disable the adBlock and continue.
Thank you.
Reload page