ANALYSIS & DESIGN OF ALGORITHMS (23PCSC01) - TOPIC-WISE - MCQ
ANALYSIS & DESIGN OF ALGORITHMS (23PCSC01)
UNIT 1
Algorithm Definition and Specification
1.
What is an algorithm?
A.
A set of mathematical equations
B.
A stepbystep procedure to solve a problem
C.
A programming language
D.
A type of hardware component
Answer:
B
2.
Which of the following is NOT a characteristic of an algorithm?
A.
Finiteness
B.
Definiteness
C.
Ambiguity
D.
Effectiveness
Answer:
C
Space Complexity and Time Complexity
3.
What does space complexity of an algorithm measure?
A.
The amount of time an algorithm takes
B.
The number of operations an algorithm performs
C.
The amount of memory required by an algorithm
D.
The size of the input data
Answer:
C
Asymptotic Notations
4.
Which of the following is the tightest upper bound for an algorithm's growth?
A. BigO
B. Theta (Θ)
C. Omega (Ω)
D. Smallo
Answer: A
5.
What is the asymptotic notation used to represent the bestcase complexity of an
algorithm?
A.
BigO
B.
Theta (Θ)
C.
Omega (Ω)
D.
None of the above
Answer: C
Stacks and Queues
6.
In a stack, the operation that removes the top element is called:
A.
Enqueue
B.
Dequeue
C.
Pop
D.
Push
Answer:
C
7.
Which data structure is used to implement a queue?
A.
Array
B.
Linked List
C.
Both A and B
D.
None of the above
Answer:
C
Binary Tree and Binary Search Tree
8.
What is the maximum number of children a node in a binary tree can have?
A.
1
B.
2
C.
3
D.
Unlimited
Answer:
B
9.
What is the difference between a binary tree and a binary search tree (BST)?
A.
BST has exactly two children per node, while binary tree has no such
restriction.
B.
Binary tree allows duplicate keys, BST does not.
C.
In BST, the left child contains smaller keys, and the right child contains
larger keys.
D.
Binary tree has sorted nodes, BST does not.
Answer:
C
Heap and Heapsort
10.
Which data structure is best suited for implementing a priority queue?
A.
Stack
B.
Queue
C.
Heap
D.
Binary Search Tree
Answer:
C
11.
Which of the following is true for a Max Heap?
A. Every parent node is greater than or equal
to its children
B. Every parent node is less than or equal to
its children
C. Left subtree is always smaller than the
right subtree
D. None of the above
Answer: A
12.
What is the time complexity of heapsort in the worst case?
A.
( O(n^2) )
B.
( O(n log n) )
C.
( O(log n) )
D.
( O(n) )
Answer:
B
Graphs
13.
Which of the following is true for a graph?
A. A graph always has cycles
B. A graph has no edges
C. A graph consists of vertices and edges
D. A graph is always connected
Answer: C
14.
In a graph, a tree is a special case where:
A.
There are no cycles, and it is fully connected.
B.
There are cycles, but all vertices are connected.
C.
All edges have equal weight.
D.
It is not connected, but has no cycles.
Answer:
A
UNIT – II
Basic Traversal Techniques for Binary Trees
Q1:
What is the correct order of traversal in an Inorder Traversal of a binary
tree?
A)
Root → Left → Right
B)
Left → Right → Root
C)
Left → Root → Right
D)
Right → Root → Left
Answer:
C) Left → Root → Right
Q2:
Which of the following is NOT a traversal technique for binary trees?
A)
Preorder
B)
Postorder
C)
Inorder
D)
BreadthFirst Search
Answer:
D) BreadthFirst Search
Basic
Traversal Techniques for Graphs
Q3:
In a graph, DepthFirst Search (DFS) uses which data structure?
A)
Queue
B)
Stack
C)
Priority Queue
D)
Heap
Answer:
B) Stack
Q4:
Which of the following traversal techniques is used to find the shortest path
in an unweighted graph?
A)
DepthFirst Search (DFS)
B)
BreadthFirst Search (BFS)
C)
Dijkstra’s Algorithm
D)
FloydWarshall Algorithm
Answer:
B) BreadthFirst Search (BFS)
Divide
and Conquer: General Method
Q5:
Divide and Conquer technique involves which of the following steps?
A)
Divide the problem, Conquer each subproblem, Combine the results
B)
Split the problem, Iterate over subproblems, Merge the results
C)
Recursion, Iteration, Result
D)
None of the above
Answer:
A) Divide the problem, Conquer each subproblem, Combine the results
Q6:
Which of the following algorithms does NOT use the Divide and Conquer
technique?
A)
Merge Sort
B)
Quick Sort
C)
Binary Search
D)
Linear Search
Answer:
D) Linear Search
Binary Search
Q7:
Binary Search can be applied to:
A)
Unsorted Arrays
B)
Sorted Arrays
C)
Graphs
D)
Trees
Answer:
B) Sorted Arrays
Q8:
What is the time complexity of Binary Search in the worst case?
A)
( O(1) )
B)
( O(n) )
C)
( O(log n) )
D)
( O(n^2) )
Answer:
C) ( O(log n) )
Merge
Sort
Q9:
Merge Sort divides the array into:
A)
Single elements
B)
Groups of size 3
C)
Halfsize subarrays
D)
Equal number of odd and even elements
Answer:
C) Halfsize subarrays
Q10:
What is the worstcase time complexity of Merge Sort?
A)
( O(n) )
B)
( O(n log n) )
C)
( O(n^2) )
D)
( O(log n) )
Answer:
B) ( O(n log n) )
Quick Sort
Q11:
In Quick Sort, the element selected as a pivot is:
A)
Always the first element
B)
Always the last element
C)
Can be any element
D)
The largest element
Answer:
C) Can be any element
Q12:
What is the worstcase time complexity of Quick Sort?
A)
( O(n) )
B)
( O(n log n) )
C)
( O(n^2) )
D)
( O(log n) )
Answer:
C) ( O(n^2) )
UNIT – III
Greedy Method
1.
What is the main characteristic of a greedy algorithm?
(a)
It solves subproblems recursively.
(b)
It always considers all possible solutions.
(c)
It makes the locally optimal choice at each step.
(d)
It divides the problem into smaller problems.
Answer: (c)
2.
Which of the following is NOT a property of problems solved by greedy
algorithms?
(a)
Optimal substructure
(b)
Overlapping subproblems
(c)
Greedy choice property
(d)
Feasible solutions
Answer: (b)
3.
In which type of problems is the greedy method guaranteed to provide an optimal
solution?
(a)
Problems with overlapping subproblems
(b)
Problems with the greedychoice property
(c)
Problems with exponential time complexity
(d)
Problems requiring backtracking
Answer: (b)
Knapsack
Problem
4.
The greedy approach to solving the fractional knapsack problem is based on which
of the following?
(a)
Maximum weight
(b)
Minimum cost
(c)
Maximum profittoweight ratio
(d)
Minimum profittoweight ratio
Answer: (c)
5.
Which type of knapsack problem can be solved optimally using a greedy algorithm?
(a) 01
Knapsack Problem
(b)
Fractional Knapsack Problem
(c)
Bounded Knapsack Problem
(d)
Unbounded Knapsack Problem
Answer: (b)
6.
What is the time complexity of solving the fractional knapsack problem using
the greedy method?
(a) (
O(n^2) )
(b) (
O(n log n) )
(c) (
O(n) )
(d) (
O(n^3) )
Answer: (b)
Minimum
Cost Spanning Tree (MST)
7.
Which of the following algorithms is used to find the Minimum Cost Spanning
Tree using a greedy method?
(a)
FloydWarshall
(b)
Kruskal’s Algorithm
(c)
BellmanFord
(d)
Johnson’s Algorithm
Answer: (b)
8.
What is the primary data structure used in Prim’s algorithm for Minimum Cost
Spanning Tree?
(a)
Stack
(b)
Priority Queue (Heap)
(c)
Hash Table
(d)
Linked List
Answer: (b)
9.
If a graph has ( V ) vertices and ( E ) edges, what is the time complexity of
Kruskal’s algorithm using a Disjoint Set Union?
(a) (
O(E log E) )
(b) (
O(V^2) )
(c) (
O(V log V) )
(d) (
O(E^2) )
Answer: (a)
Single
Source Shortest Path
10.
Which algorithm is a greedy approach to finding the shortest path from a single
source in a graph with nonnegative edge weights?
(a)
Dijkstra’s Algorithm
(b)
FloydWarshall Algorithm
(c)
BellmanFord Algorithm
(d)
A Search Algorithm
Answer: (a)
11.
In Dijkstra’s algorithm, which data structure is commonly used to efficiently
extract the next vertex with the smallest tentative distance?
(a)
Stack
(b)
MinHeap
(c)
Queue
(d)
Graph Adjacency List
Answer: (b)
12.
What is the time complexity of Dijkstra’s algorithm when implemented with a
binary heap and adjacency list for a graph with ( V ) vertices and ( E ) edges?
(a) (
O(V^2) )
(b) (
O(E + V) )
(c) (
O((V + E) log V) )
(d) (
O(V log V) )
Answer: (c)
UNIT – IV
Dynamic Programming
1.
Which of the following is a key principle of dynamic programming?
(a)
Divide and conquer
(b)
Overlapping subproblems and optimal substructure
(c)
Greedy approach
(d)
Randomized strategy
Answer: (b)
2.
Dynamic programming works efficiently for problems that exhibit:
(a)
Nondeterministic behavior
(b)
Greedychoice property
(c)
Overlapping subproblems
(d)
No recursive nature
Answer: (c)
Multistage
Graphs
3.
In a multistage graph, vertices are divided into:
(a)
Layers or stages
(b)
Levels
(c)
Cycles
(d)
Components
Answer: (a)
4.
What is the goal in solving a multistage graph problem?
(a)
Find all paths between source and destination
(b)
Find the longest path
(c)
Find the shortest path from source to destination through stages
(d)
Find a random path
Answer: (c)
AllPairs
Shortest Path
5.
Which algorithm is commonly used for solving the AllPairs Shortest Path
problem?
(a)
Prim's Algorithm
(b)
FloydWarshall Algorithm
(c)
BellmanFord Algorithm
(d)
Kruskal's Algorithm
Answer: (b)
6.
In FloydWarshall, if the graph has a negative weight cycle, the algorithm:
(a)
Produces incorrect results
(b)
Ignores the cycle
(c)
Detects the cycle but fails to calculate distances
(d)
Detects the cycle and stops execution
Answer: (d)
Optimal Binary Search Trees
7.
Optimal Binary Search Trees are designed to minimize:
(a)
Height of the tree
(b)
Access time based on search probabilities
(c)
Number of nodes
(d)
Space complexity
Answer: (b)
8.
In an Optimal Binary Search Tree problem, the weights are typically:
(a)
Frequencies or probabilities of searching for keys
(b)
Edge weights in the graph
(c)
Random values assigned to nodes
(d)
Depth of nodes in the tree
Answer: (a)
01
Knapsack Problem
9.
In the 01 Knapsack problem, what does "01" signify?
(a)
Items can only have weights 0 or 1
(b)
Items are either fully included or excluded
(c)
Only one item can be included in the knapsack
(d)
No items can be repeated
Answer: (b)
10.
Which approach is typically used to solve the 01 Knapsack problem?
(a)
Divide and conquer
(b)
Dynamic programming
(c)
Backtracking
(d)
Greedy algorithm
Answer: (b)
Traveling Salesman Problem
11.
The Traveling Salesman Problem aims to find:
(a)
The longest path visiting each city
(b)
The shortest cycle visiting each city exactly once
(c)
A minimum spanning tree
(d)
The shortest path from source to destination
Answer: (b)
12.
The Traveling Salesman Problem is an example of a:
(a)
Greedy problem
(b)
Pcomplete problem
(c) NPhard problem
(d)
Divideandconquer problem
Answer: (c)
Flow
Shop Scheduling
13.
Flow shop scheduling involves:
(a)
Assigning jobs to workers randomly
(b)
Scheduling jobs on machines in a specific order
(c)
Minimizing inventory costs
(d)
Arranging products in a factory layout
Answer: (b)
14.
What is the objective of flow shop scheduling?
(a)
Minimize the makespan
(b)
Maximize machine usage
(c)
Randomize the job schedule
(d)
Maximize profit
Answer: (a)
UNIT – V
Backtracking
1.
Which of the following is the main idea of backtracking?
a)
Divide and Conquer
b) Searching and Undoing
c) Greedy Approach
d) Dynamic Programming
Answer: b) Searching and Undoing
2.
What is the time complexity of the backtracking approach in the worst case for
the nqueens problem?
a) (O(n^2))
b) (O(n!))
c) (O(2^n))
d) (O(n^n))
Answer: b) (O(n!))
8Queens
Problem
3.
How many queens are placed on a chessboard in the 8queens problem?
a) 4
b) 8
c) 16
d) 64
Answer: b) 8
4.
In the 8queens problem, the main constraint is to ensure:
a) All queens are placed on the same
row.
b) No two queens threaten each other.
c) The sum of row indices is even.
d) All queens are on the same diagonal.
Answer: b) No two queens threaten each
other.
Sum
of Subsets
5.
What is the main purpose of the "Sum of Subsets" problem?
a) To maximize the total weight of the
subset.
b) To find subsets with sums equal to a
given value.
c) To minimize the subset difference.
d) To find all possible subsets.
Answer: b) To find subsets with sums equal
to a given value.
6.
Which condition is checked to prune branches in the "Sum of Subsets"
problem?
a) Subset size exceeds the total set
size.
b) Subset sum exceeds the target value.
c) Subset contains duplicate elements.
d) All elements in the subset are odd.
Answer: b) Subset sum exceeds the target
value.
Graph
Coloring
7.
What is the graph coloring problem mainly used for?
a) Finding shortest paths in graphs.
b) Assigning colors to vertices such that
adjacent vertices have different colors.
c) Calculating the diameter of a graph.
d) Minimizing the number of edges in a
graph.
Answer: b) Assigning colors to vertices such
that adjacent vertices have different colors.
8.
The minimum number of colors required to color a graph is known as:
a) Chromatic index
b) Chromatic number
c) Eulerian number
d) Degree of the graph
Answer: b) Chromatic number
Hamiltonian
Cycles
9.
What is a Hamiltonian cycle?
a) A cycle that visits each edge exactly
once.
b) A path that visits each vertex exactly
once and returns to the starting vertex.
c) A path that visits all vertices without
forming a cycle.
d) A cycle with the minimum number of
edges.
Answer: b) A path that visits each vertex
exactly once and returns to the starting vertex.
10.
Which algorithm is commonly used to solve the Hamiltonian Cycle problem?
a) Kruskal's Algorithm
b) Backtracking
c) Dijkstra's Algorithm
d) BellmanFord Algorithm
Answer: b) Backtracking
Branch
and Bound
11.
The "Branch and Bound" method is primarily used to solve:
a) Decisionmaking problems
b) NPhard optimization problems
c) Sorting problems
d) Graph traversal problems
Answer: b) NPhard optimization
problems
12.
In the Traveling Salesperson Problem (TSP), the goal is to:
a) Minimize the total distance
traveled.
b) Maximize the number of visited
cities.
c) Minimize the number of edges in the
graph.
d) Find the shortest path between two
cities.
Answer: a) Minimize the total distance
traveled.
Comments
Post a Comment