1.Algorithm is a ________________.
Processing of problem
Step by Step method to solve a problem
Graphical method
None of the above
2.Algorithm should have _______________ or more output.
Zero
One
Two
Three
3.Which is correct according to increasing order of growth rate
n, n! , nlogn , n^2 , n^3 , n^5 , 2^n
nlogn , n^2 , n^3 , n^5 , 2^n , n!
n , nlogn , n^2 , n^3 , n^5 , 2^n , n!
n , nlogn , n^2 , n^3 , n^5 , n!, 2^n
4.Big Oh! notation looks for____________ value.
Maximum
Minimum
Average
Mean
5.Omega (Ω) notation looks for ___________ value.
Maximum
Minimum
Average
Mean
6.A function which calls itself is called __________ function.
Null
Default
Recursive
Non recursive
7. _____________ method is used to solve recurrence.
Main
Major
Divide
Master
8.Time complexity of binary search is _____________.
O(n)
O(logn)
O(nlogn)
None of the above
9.The condition for applying binary search is _______________.
Elements should be sorted
Elements should be unsorted
Elements should have priority
None of the above
10.best case of binary search, the searching element is at _______________ position.
First
Second
Last
Middle
11.The __________________of an algorithm is the amount of computer time it needs to run to completion.
Time complexity
Space complexity
Time period
None of the above
12.The minimum number of comparisons required finding the minimum and maximum of 100 numbers is ________
99
100
101
None of the above
13.Divide and Merge operation is done in ____________.
Binary search
Merge sort
Quicksort
Heap sort
14.Which sort takes an extra array.
Binary search
Merge sort
Quicksort
Heap sort
15.Recurrence equation of merge sort is _______________.
T(n) = T(n/2) + O(n)
T(n) = 2T(n/2) + O(n)
T(n) = 3T(n/2) + O(n)
None of the above
16.Pivot element is used in ___________ sort.
Binary search
Mergesort
Quick sort
Heap sort
17.Partition operation is done in _____________ sort.
Binary search
Mergesort
Quick sort
Heap sort
18.Quick sort algorithm is an example of
Greedy
Improved search
Dynamic Programming
Divide and Conquer
19.Time complexity of merge sort is ___________.
O(n)
O(logn)
O(nlogn)
None of the above
20.Time complexity of quick sort is depends on _____________.
O(n)
O(logn)
O(nlogn)
None of the above
21.Merge sort uses which of the following technique to implement sorting?
Backtracking
Greedy algorithm
Divide and conquer
Dynamic programming
22.What is the average case time complexity of merge sort ?
O(n log n)
O(n^2)
O(n^2log n)
O(n log n2)
23.What is the auxiliary space complexity of merge sort?
O(1)
O(log n)
O(n)
O(n log n)
24.Merge sort can be implemented using O(1) auxiliary space.
True
False
25.What is the worst case time complexity of merge sort?
O(n log n)
O(n^2)
O(n^2 log n)
O(n logn2 )
26.Which of the following method is used for sorting in merge sort?
Merging
Partitioning
Selection
Exchanging
27.What will be the best case time complexity of merge sort ?
O(n log n)
O(n2)
O(n2 logn)
O(n logn2)
28. Which of the following is not a variant of merge sort ?
In-place merge sort
Bottom up merge sort
Top down merge sort
Linear merge sort
29.Choose the incorrect statement about merge sort from the following?
It is a comparison based sort
It is an adaptive algorithm
It is not an in place algorithm
It is stable algorithm
30.Which of the following is not in place sorting algorithm?
Merge sort
Quick sort
Heap sort
Insertion sort
31.Which of the following is not a stable sorting algorithm?
Quick sort
Cocktail sort
Bubble sort
Merge sort
32.Which of the following stable sorting algorithm takes the least time when applied to an almost sorted array?
Quick sort
Insertion sort
Selection sort
Merge sort
33.Merge sort is preferred for arrays over linked lists.
True
False
34.Which of the following sorting algorithm makes use of merge sort?
Tim sort
Intro sort
Bogo sort
Quick sort
35.Choose the correct code for merge sort.
void merge_sort(int arr[], int left, int right) { if (left > right) { int mid = (right-left)/2; merge_sort(arr, left, mid); merge_sort(arr, mid+1, right); merge(arr, left, mid, right); //function to merge sorted arrays } }
void merge_sort(int arr[], int left, int right) { if (left < right) { int mid = left+(right-left)/2; merge_sort(arr, left, mid); merge_sort(arr, mid+1, right); merge(arr, left, mid, right); //function to merge sorted arrays } }
void merge_sort(int arr[], int left, int right) { if (left < right) { int mid = left+(right-left)/2; merge(arr, left, mid, right); //function to merge sorted arrays merge_sort(arr, left, mid); merge_sort(arr, mid+1, right); } }
void merge_sort(int arr[], int left, int right) { if (left < right) { int mid = (right-left)/2; merge(arr, left, mid, right); //function to merge sorted arrays merge_sort(arr, left, mid); merge_sort(arr, mid+1, right); } }
36. Which of the following sorting algorithm does not use recursion?
Quick sort
Merge sort
Heap sort
Bottom up merge sort
37.Which of the following sorting algorithms is the fastest ?
Merge sort
Quick sort
Insertion sort
Shell sort
38.Quick sort follows Divide-and-Conquer strategy.
True
False
39.What is the worst case time complexity of a quick sort algorithm?
O(N)
O(N log N)
O(N^2 )
O(log N)
40.Which of the following methods is the most effective for picking the pivot element ?
First element
Last element
Median-of-three partitioning
Random element
41.Find the pivot element from the given input using median-of-three partitioning method. 8, 1, 4, 9, 6, 3, 5, 2, 7, 0.
8
7
9
6
42.Which is the safest method to choose a pivot element ?
Choosing a random element as pivot
Choosing the first element as pivot
Choosing the last element as pivot
Median-of-three partitioning method
43.What is the average running time of a quick sort algorithm ?
O(N^2 )
O(N)
O(N log N)
O(log N)
44.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
45.Quick sort uses join operation rather than merge operation.
True
False
46.How many sub arrays does the quick sort algorithm divide the entire array into?
One
Two
Three
Four
47.Which is the worst method of choosing a pivot element ?
First element as pivot
Last element as pivot
Median-of-three partitioning
Random element as pivot
48.Which among the following is the best cut-off range to perform insertion sort within a quick sort ?
N=0-5
N=5-20
N=20-30
N>30
49.Recursion is a method in which the solution of a problem depends on ____________
Larger instances of different problems
Larger instances of the same problem
Smaller instances of the same problem
Smaller instances of different problems
50.Which of the following problems can’t be solved using recursion?
Factorial of a number
Nth fibonacci number
Length of a string
Problems without base case
Friday, October 09, 2020
Algorithms Multiple choice questions
Friday, June 19, 2020
Analysis and Design of Algorithm quiz
1.
How
many number of comparisons are required in insertion sort to sort a file if the
file is sorted in reverse order?
a.
N2
b.
N
c.
N-1
d.
N/2
2.
How
many number of comparisons are required in insertion sort to sort a file if the
file is already sorted?
a.
N2
b.
N
c.
N-1
d.
N/2
3.
The
worst-case time complexity of Quick Sort is________.
a.
O(n2)
b.
O(log
n)
c.
O(n)
d.
O(n
logn)
4.
The
worst-case time complexity of Bubble Sort is________.
a.
O(n2)
b.
O(log
n)
c.
O(n)
d.
O(n
logn)
5.
The
worst-case time complexity of Selection Sort is________.
a.
O(n2)
b.
O(log
n)
c.
O(n)
d.
O(n
logn)
6.
The
worst-case time complexity of Merge Sort is________.
a.
O(n2)
b.
O(log
n)
c.
O(n)
d.
O(n
logn)
7.
The
algorithm like Quick sort does not require extra memory for carrying out the
sorting procedure. This technique is called __________.
a.
in-place
b.
stable
c.
unstable
d.
in-partition
8.
Which
of the following sorting procedures is the slowest?
a.
Quick
sort
b.
Heap
sort
c.
Shell
sort
d.
Bubble
sort
9.
Two
main measures for the efficiency of an algorithm are
a.
Processor
and memory
b.
Complexity
and capacity
c.
Time
and space
d.
Data
and space
10.
The
space factor when determining the efficiency of algorithm is measured by
a.
Counting
the maximum memory needed by the algorithm
b.
Counting
the minimum memory needed by the algorithm
c.
Counting
the average memory needed by the algorithm
d.
Counting
the maximum disk space needed by the algorithm
11.
The
time factor when determining the efficiency of algorithm is measured by
a.
Counting
microseconds
b.
Counting
the number of key operations
c.
Counting
the number of statements
d.
Counting
the kilobytes of algorithm
12.
A
list of n strings, each of length n, is sorted into lexicographic order using
the merge-sort algorithm. The worst case running time of this computation is
i.
(n
log n)
ii.
(n2
log n)
iii.
(n2
+ log n)
iv.
(n2)
13.
Which
of the following case does not exist in complexity theory?
a.
Best
case
b.
Worst
case
c.
Average
case
d.
Null
case
14.
The
concept of order Big O is important because
a.
It
can be used to decide the best algorithm that solves a given problem
b.
It
determines the maximum size of a problem that can be solved in a given amount
of time
c.
It
is the lower bound of the growth rate of algorithm
d.
Both
A and B
15.
Which
of the following sorting methods would be most suitable for sorting a list
which is almost sorted?
a.
Bubble
Sort
b.
Insertion
Sort
c.
Selection
Sort
d.
Quick
Sort
16.
Suppose
we are sorting an array of eight integers using some quadratic sorting
algorithm. After four iterations of the algorithm’s main loop, the array elements
are ordered as shown here: - 2 4 5 7 8 1
3 6. Which of the following sorting technique is used?
a.
Insertion
sort
b.
Selection
sort
c.
Either
of a and b
d.
None
of the above
17.
The
running time of insertion sort is
a.
O(n^2)
b.
O(n)
c.
O(log
n)
d.
O(n
log n)
18.
A
sort which iteratively passes through a list to exchange the first element with
any element less than it and then repeats with a new first element is called
a.
insertion
sort
b.
selection
sort
c.
heap
sort
d.
quick
sort
19.
The
way a card game player arranges his cards as he picks them one by one can be
compared to
a.
Quick
sort
b.
Merge
sort
c.
Insertion
sort
d.
Bubble
sort
20.
Which
among the following is the best when the list is already sorted?
a.
Insertion
sort
b.
Bubble
sort
c.
Merge
sort
d.
Selection
sort
21.
As
part of the maintenance work, you are entrusted with the work of rearranging
the library books in a shelf in proper order, at the end of each day. The ideal
choice will be
a.
Bubble
sort
b.
Insertion
sort
c.
Selection
sort
d.
Merge
sort
22.
In
quick sort, the number of partitions into which the file of size n is divided
by a selected record is
a.
n
b.
n
- 1
c.
2
d.
None
of the above
23.
Quick
sort is the fastest available method of sorting because of
a.
low
over head
b.
O(n
log n) comparisons
c.
low
overhead and also O(n log n) comparisons
d.
None
of the above
24.
Suppose
we need to sort a list of employee records in ascending order, using the social
security number (a 9-digit number) as the key (i.e., sort the records by social
security number). If we need to guarantee that the running time will be no
worse than n log n, which sorting methods could we use?
a.
mergesort
b.
quicksort
c.
insertion
sort
d.
Either
mergesort or quicksort
25.
Consider
the following function f:
int f(int n)
{
int
s = 0;
while(n
> 1)
{
n
= n/2;
s++;
}
return
s;
}
What
is the asymptotic complexity in terms of n? (Pick the smallest correct answer)
a.
O(nlog
n)
b.
O(n)
c.
O(
n)
d.
O(log
n)
e.
O(n^2
)
26.
The Knapsack problem
is an example of ____________
a) Greedy algorithm
b) 2D dynamic programming
c) 1D dynamic programming
d) Divide and conquer
27.
Which of the following methods can be used to
solve the Knapsack problem?
a) Brute force algorithm
b) Recursion
c) Dynamic programming
d) Brute force, Recursion and Dynamic Programming
28.
You are given a
knapsack that can carry a maximum weight of 60. There are 4 items with weights
{20, 30, 40, 70} and values {70, 80, 90, 200}. What is the maximum value of the
items you can carry using the knapsack?
a) 160
b) 200
c) 170
d) 90
29.
Which of the
following is false in the case of a spanning tree of a graph G?
a) It is tree that spans G
b) It is a subgraph of the G
c) It includes every vertex of the G
d) It can be either cyclic or acyclic
30.
Every graph has only
one minimum spanning tree.
a) True
b) False
31.
Consider a complete
graph G with 4 vertices. The graph G has ____ spanning trees.
a) 15
b) 8
c) 16
d) 13
32.
The travelling
salesman problem can be solved using _________
a) A spanning tree
b) A minimum spanning tree
c) Bellman – Ford algorithm
d) DFS traversal
33.
Consider the graph M
with 3 vertices. Its adjacency matrix is shown below. Which of the following is
true?
a) Graph M has no minimum spanning tree
b) Graph M has a unique minimum spanning trees of cost 2
c) Graph M has 3 distinct minimum spanning trees, each of cost 2
d) Graph M has 3 spanning trees of different costs
34.
Consider a
undirected graph G with vertices { A, B, C, D, E}. In graph G, every edge has
distinct weight. Edge CD is edge with minimum weight and edge AB is edge with
maximum weight. Then, which of the following is false?
a) Every minimum spanning tree of G must contain CD
b) If AB is in a minimum spanning tree, then its removal must disconnect G
c) No minimum spanning tree contains AB
d) G has a unique minimum spanning tree
35.
If all the weights
of the graph are positive, then the minimum spanning tree of the graph is a
minimum cost subgraph.
a) True
b) False
36.
Consider the graph
shown below. Which of the following are the edges in the MST of the given
graph?
a) (a-c)(c-d)(d-b)(d-b)
b) (c-a)(a-d)(d-b)(d-e)
c) (a-d)(d-c)(d-b)(d-e)
d) (c-a)(a-d)(d-c)(d-b)(d-e)
37.
Which of the
following is not the algorithm to find the minimum spanning tree of the given
graph?
a) Boruvka’s algorithm
b) Prim’s algorithm
c) Kruskal’s algorithm
d) Bellman–Ford algorithm
38.
Which of the
following is false?
a) The spanning trees do not have any cycles
b) MST have n – 1 edges if the graph has n edges
c) Edge e belonging to a cut of the graph if has the weight smaller than any
other edge in the same cut, then the edge e is present in all the MSTs of the
graph
d) Removing one edge from the spanning tree will not make the graph
disconnected
39.
Which
of the following algorithms is the best approach for solving Huffman codes?
a) exhaustive search
b) greedy algorithm
c) brute force algorithm
d) divide and conquer algorithm
40.
The code length does
not depend on the frequency of occurrence of characters.
a) true
b) false
41.
In Huffman coding,
data in a tree always occur?
a) roots
b) leaves
c) left sub trees
d) right sub trees
42.
For
how many queens was the extended version of Eight Queen Puzzle applicable for
n*n squares?
a) 5
b) 6
c) 8
d) n
43.
Which of the
problems cannot be solved by backtracking method?
a) n-queen problem
b) subset sum problem
c) hamiltonian circuit problem
d) travelling salesman problem
44.
Backtracking
algorithm is implemented by constructing a tree of choices called as?
a) State-space tree
b) State-chart tree
c) Node tree
d) Backtracking tree
45.
What happens when
the backtracking algorithm reaches a complete solution?
a) It backtracks to the root
b) It continues searching for other possible solutions
c) It traverses from a different route
d) Recursively traverses through the same route
46.
A node is said
to be ____________ if it has a possibility of reaching a complete solution.
a) Non-promising
b) Promising
c) Succeeding
d) Preceding
47.
In what manner is a
state-space tree for a backtracking algorithm constructed?
a) Depth-first search
b) Breadth-first search
c) Twice around the tree
d) Nearest neighbour first
48.
The leaves in a
state-space tree represent only complete solutions.
a) true
b) false
49.
The problem of
finding a subset of positive integers whose sum is equal to a given positive
integer is called as?
a) n- queen problem
b) subset sum problem
c) knapsack problem
d) hamiltonian circuit problem
50.
The problem of
placing n queens in a chessboard such that no two queens attack each other is
called as?
a) n-queen problem
b) eight queens puzzle
c) four queens puzzle
d) 1-queen problem
51.
Which of the following
is/are property/properties of a dynamic programming problem?
a) Optimal substructure
b) Overlapping subproblems
c) Greedy approach
d) Both optimal substructure and overlapping subproblems
52.
If an optimal solution
can be created for a problem by constructing optimal solutions for its
subproblems, the problem possesses ____________ property.
a) Overlapping subproblems
b) Optimal substructure
c) Memoization
d) Greedy
53.
If a problem can be
broken into subproblems which are reused several times, the problem possesses
____________ property.
a) Overlapping subproblems
b) Optimal substructure
c) Memoization
d) Greedy
54.
If a problem can be
solved by combining optimal solutions to non-overlapping problems, the strategy
is called _____________
a) Dynamic programming
b) Greedy
c) Divide and conquer
d) Recursion
55.
When dynamic
programming is applied to a problem, it takes far less time as compared to
other methods that don’t take advantage of overlapping subproblems.
a) True
b) False
56.
A greedy algorithm can
be used to solve all the dynamic programming problems.
a) True
b) False
57.
In dynamic
programming, the technique of storing the previously calculated values is
called ___________
a) Saving value property
b) Storing value property
c) Memoization
d) Mapping
58.
When a top-down
approach of dynamic programming is applied to a problem, it usually
_____________
a) Decreases both, the time complexity and the space complexity
b) Decreases the time complexity and increases the space complexity
c) Increases the time complexity and decreases the space complexity
d) Increases both, the time complexity and the space complexity
59.
Which of the following
problems is NOT solved using dynamic programming?
a) 0/1 knapsack problem
b) Matrix chain multiplication problem
c) Edit distance problem
d) Fractional knapsack problem
60.
Which of the following
problems should be solved using dynamic programming?
a) Mergesort
b) Binary search
c) Longest common subsequence
d) Quicksort
61.
What is vertex
coloring of a graph?
a) A condition where any two vertices having a common edge should not have same
color
b) A condition where any two vertices having a common edge should always have
same color
c) A condition where all vertices should have a different color
d) A condition where all vertices should have same color
62.
How many edges will
a tree consisting of N nodes have?
a) Log(N)
b) N
c) N – 1
d) N + 1
63.
Minimum number of
unique colors required for vertex coloring of a graph is called?
a) vertex matching
b) chromatic index
c) chromatic number
d) color number
64.
The worst-case
efficiency of solving a problem in polynomial time is?
a) O(p(n))
b) O(p( n log n))
c) O(p(n2))
d) O(p(m log n))
65.
Problems that can be
solved in polynomial time are known as?
a) intractable
b) tractable
c) decision
d) complete
66.
The sum and
composition of two polynomials are always polynomials.
a) true
b) false
67.
_________ is the class
of decision problems that can be solved by non-deterministic polynomial
algorithms?
a) NP
b) P
c) Hard
d) Complete
68.
Problems that cannot
be solved by any algorithm are called?
a) tractable problems
b) intractable problems
c) undecidable problems
d) decidable problems
69.
The Euler’s circuit
problem can be solved in?
a) O(N)
b) O( N log N)
c) O(log N)
d) O(N2)
70.
To which class does
the Euler’s circuit problem belong?
a) P class
b) NP class
c) Partition class
d) Complete class
71.
Halting problem is an
example for?
a) decidable problem
b) undecidable problem
c) complete problem
d) trackable problem
72.
How many stages of
procedure does a non-deterministic algorithm consist of?
a) 1
b) 2
c) 3
d) 4
73.
A non-deterministic
algorithm is said to be non-deterministic polynomial if the time-efficiency of
its verification stage is polynomial.
a) true
b) false
74.
What
is the worst case running time in searching phase of Boyer-Moore’s algorithm?
a) O(n)
b) O(log n)
c) O(m+n)
d) O(mn)
75.
Given
input string = “ABCDABCATRYCARCABCSRT” and pattern string = “CAT”. Find the
first index of the pattern match using quick search algorithm.
a) 2
b) 6
c) 11
d) 14
76.
What
character shift tables does Boyer-Moore algorithm use?
a) good-character shift tables
b) bad-character shift tables
c) next-character shift tables
d) both good and bad character shift tables
77.
Which
of the following is is a pattern matching algorithm?
a) Boyer-Moore’s algorithm
b) Naïve String matching algorithm
c) KMP algorithm
d) All of the above
78.
Branch and bound is
a __________
a) problem solving technique
b) data structure
c) sorting algorithm
d) type of tree
79.
Which of the
following is not a branch and bound strategy to generate branches?
a) LIFO branch and bound
b) FIFO branch and bound
c) Lowest cost branch and bound
d) Highest cost branch and bound
80.
Which data structure
is used for implementing a LIFO branch and bound strategy?
a) stack
b) queue
c) array
d) linked list
81.
Which data structure
is used for implementing a FIFO branch and bound strategy?
a) stack
b) queue
c) array
d) linked list
82.
Which data structure
is most suitable for implementing best first branch and bound strategy?
a) stack
b) queue
c) priority queue
d) linked list
83.
Which of the
following branch and bound strategy leads to breadth first search?
a) LIFO branch and bound
b) FIFO branch and bound
c) Lowest cost branch and bound
d) Highest cost branch and bound
84.
Which of the
following branch and bound strategy leads to depth first search?
a) LIFO branch and bound
b) FIFO branch and bound
c) Lowest cost branch and bound
d) Highest cost branch and bound
85.
Both FIFO branch and
bound strategy and backtracking leads to depth first search.
a) true
b) false
86.
Both LIFO branch and
bound strategy and backtracking leads to depth first search.
a) true
b) false
87.
Choose the correct
statement from the following.
a) branch and bound is more efficient than backtracking
b) branch and bound is not suitable where a greedy algorithm is not applicable
c) branch and bound divides a problem into at least 2 new restricted sub
problems
d) backtracking divides a problem into at least 2 new restricted sub problems
88.
Which of the
following can traverse the state space tree only in DFS manner?
a) branch and bound
b) dynamic programming
c) greedy algorithm
d) backtracking
89.
Which
of the following methods can be used to solve the matrix chain multiplication
problem?
a) Dynamic programming
b) Brute force
c) Recursion
d) Dynamic Programming, Brute force, Recursion
90.
Consider
the two matrices P and Q which are 10 x 20 and 20 x 30 matrices respectively.
What is the number of multiplications required to multiply the two matrices?
a) 10*20
b) 20*30
c) 10*30
d) 10*20*30
91.
If
Matrix A is of order X*Y and Matrix B is of order M*N, then what is the order
of the Matrix A*B given that Y=M?
a) Y*N
b) X*M
c) X*N
d) Y*M
92.
What
is the time complexity of matrix multiplied recursively by Divide and Conquer
Method?
a) O(n)
b) O(n2)
c) O(n3)
d) O(n!)
93.
What
is the time complexity of matrix multiplied recursively by Strassen’s Method?
a) O(nlog7)
b) O(n2)
c) O(n3)
d) O(n!)
94.
How many recursive
calls are there in Recursive matrix multiplication by Strassen’s Method?
a) 5
b) 7
c) 8
d) 4
95.
Matrix A is of order 3*4
and Matrix B is of order 4*5. How many elements will be there in a matrix A*B
multiplied recursively.
a) 12
b) 15
c) 16
d) 20
96.
What
is the worst case time complexity of KMP algorithm for pattern searching (m =
length of text, n = length of pattern)?
a) O(n)
b) O(n*m)
c) O(m)
d) O(log n)
97.
Which
of the following is a sub string of “AKS UNIVERSITY”?
a) AKU
b) KSNI
c) AKS
d) ASU
98.
The
naive pattern searching algorithm is an in place algorithm.
a) true
b) false
99.
Which
of the following problems can’t be solved using recursion?
a) Factorial of a number
b) Nth fibonacci number
c) Length of a string
d) Problems without base case
100.
Which
of the following statements is true?
a) Recursion is always better than iteration
b) Recursion uses more memory compared to
iteration
c) Recursion uses less memory compared to
iteration
d) Iteration is always better and simpler than
recursion