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
No comments:
Post a Comment
Open Researcher and Contributor ID (ORCID)