Algorithm - Quiz(MCQ)
A)
A problem
B)
A real life mathematical problem
C)
A procedure for solving a problem
D)
None of the above

Correct Answer :   A procedure for solving a problem

A)
Network lock
B)
Sorting
C)
All pair shortest path
D)
Single source shortest path

Correct Answer :   Single source shortest path

Explanation : Dijkstra’s algorithm is used to solve single source shortest path problems.

A)
Brute Force
B)
Divide and Conquer
C)
GreedyAlgorithm
D)
None of the above

Correct Answer :   Divide and Conquer

A)
Bubble
B)
Merge
C)
Insertion
D)
None of the above

5 .
An unordered list contains n distinct elements.

The number of comparisons to find an element in this list that is neither maximum nor minimum is :
A)
O(1)
B)
O (n)
C)
O(!n)
D)
O (n log n)

A)
O (n)
B)
O(!n)
C)
O(n^2)
D)
O (n log n)

A)
148
B)
147
C)
146
D)
140

A)
Selection Sort
B)
Quick Sort
C)
Bubble Sort
D)
Merge Sort

A)
Brute Force
B)
Divide and Conquer
C)
Dynamic programming algorithms
D)
None of the above

Correct Answer :   Dynamic programming algorithms

A)
Time only
B)
Space only
C)
Both (A) and (B)
D)
None of the above

Correct Answer :   Both (A) and (B)

A)
A is better than B
B)
B is better than A
C)
Both are equally good
D)
None of the above

Correct Answer :   B is better than A

A)
Insertion
B)
Merge
C)
Bubble
D)
None of the above

13 .
The following list is to be sorted using a bubble sort:
12  6  8  1  3
What will the list look like after the first iteration through the list?
A)
1  3  6  8  12
B)
6  8  1  12  3
C)
6 12  1  8   3
D)
6  8  1  3  12

Correct Answer :   6  8  1  3  12

A)
Bubble
B)
Merge
C)
Insertion
D)
None of them do

A)
Bubble
B)
Merge
C)
Insertion
D)
None of them do

A)
0
B)
1
C)
2
D)
3

A)
Binary
B)
Merge
C)
Bubble
D)
Insertion

A)
flow charts
B)
pseudo codes
C)
instructions in common language
D)
All of the above

Correct Answer :   All of the above

Explanation : Algorithm is represented through pseudo codes, normal language sentences or flow charts.

A)
Fast
B)
Compact
C)
Correctness and Precision
D)
None of the above

Correct Answer :   Correctness and Precision

Explanation : An algorithm should be correct otherwise it’s of no use even if it is fast and compact.

A)
making that algorithm slow by time and large by space
B)
making that algorithm fast by time and compact by space
C)
making that algorithm fast by time and large by space
D)
making that algorithm slow by time and compact by space

Correct Answer :   making that algorithm fast by time and compact by space

Explanation : An Algorithm should be fast and compact.

A)
Brute Force
B)
Divide and Conquer
C)
Dynamic programming algorithms
D)
None of the above

Explanation : In Brute force, all the possibilities are tried.

A)
doesnot solve a base case directly
B)
a base case is not necessary
C)
a base case is necessary and is solved without recursion.
D)
None of the above

Correct Answer :   a base case is not necessary

A)
0-1 Knapsack problem
B)
Floyd Warshall Algorithm for all pairs shortest paths
C)
Prim's Minimum Spanning Tree
D)
Bellmanâ€“Ford Algorithm for single source shortest path

Correct Answer :   Prim's Minimum Spanning Tree

A)
Counting Sort is not a comparison based sorting algorithm
B)
The minimum possible time complexity of a comparison based sorting algorithm is O(nLogn) for a random input array
C)
Any comparison based sorting algorithm can be made stable by using position as a criteria when two elements are compared
D)
Heap Sort is not a comparison based sorting algorithm.

Correct Answer :   Heap Sort is not a comparison based sorting algorithm.

A)
n^3 / (sqrt(n))
B)
n^1.98
C)
(2^20) * n
D)
(15^10) * n + 12099

Correct Answer :   n^3 / (sqrt(n))

A)
Bubble
B)
Merge
C)
Insertion
D)
None of the above

A)
Make an empty new list
B)
Compare the first and second elements
C)
Put the first element in the correct place
D)
Make a new list with the first item of the original list as the ordered list

Correct Answer :   Make a new list with the first item of the original list as the ordered list

28 .
The following two lists are to be merged, what would be the correct first step?

List 1

2 4 8 9

List 2

1 6 8 4
A)
Compare 1 and 6 and put 1 into a new list
B)
Compare 9 and 4 and put 4 into a new list
C)
Compare 2 and 1 and put 1 into a new list
D)
Compare 2 and 4 and put 2 into a new list

Correct Answer :   Compare 2 and 1 and put 1 into a new list

A)
Merge
B)
Insertion
C)
Bubble
D)
None of them do

A)
Denary search
B)
Binary search
C)
Random search
D)
Next Item search

A)
Elements do not need to be in order, check each item in turn
B)
Put the elements in order, check each item in turn
C)
Put the elements in order, compare to the middle value, split the list in order and repeat
D)
Elements do not need to be in order, compare to the middle value, split the list in order and repeat

Correct Answer :   Elements do not need to be in order, check each item in turn

A)
Put the elements in order, check each item in turn
B)
Elements do not need to be in order, check each item in turn
C)
Elements do not need to be in order, compare to the middle value, split the list in order and repeat
D)
Take an ordered list, compare the search value to the middle value, if it's higher than the middle take the right side of the list otherwise take the left and repeat

Correct Answer :   Take an ordered list, compare the search value to the middle value, if it's higher than the middle take the right side of the list otherwise take the left and repeat

A)
Tree Search
B)
Linear Search
C)
Hashing
D)
Binary Search

A)
Worst than Average case
B)
Same as in Average case
C)
Better than Average case
D)
None of the above

Correct Answer :   Worst than Average case

A)
O(n2)
B)
O(n)
C)
O(log2n)
D)
O(nlog2n)

A)
Counting microseconds
B)
Counting the number of statements
C)
Counting the kilobytes of algorithm
D)
Counting the number of key operations

Correct Answer :   Counting the number of key operations

A)
Tree
B)
Stack
C)
Queue
D)

A)
Backtracking
B)
Greedy method
C)
Divide and conquer
D)
Dynamic programming

Correct Answer :   Divide and conquer

A)
log(n)
B)
2n
C)
n*n
D)
nlog(n)

A)
O(2n)
B)
O(n2)
C)
O(2n)
D)
O(n3)

A)
best case: O(log(n)) worst case: O(n2)
B)
best case: O(n2), worst case: O(n log(n))
C)
best case: O(n log(n) ) worst case: O(n2)
D)
best case: O(n2), worst case: O(n2log(n) )

Correct Answer :   best case: O(n log(n) ) worst case: O(n2)

A)
Using a computer
B)
C)
Making a computer use arti cial intelligence
D)
Developing an algorithm to solve a problem

Correct Answer :   Developing an algorithm to solve a problem

A)
Typing
B)
Abstraction
C)
Decomposition
D)
Algorithmic thinking

A)
B)
Representing real world problems in a computer program, using symbols and removing unnecessary elements
C)
Performing multiple calculations on a list of variables
D)
Taking a real world problem and designing a computer program that exactly replicates every part of that problem in the computer

Correct Answer :   Representing real world problems in a computer program, using symbols and removing unnecessary elements

A)
The breaking down of waste to make compost
B)
The breaking down of a problem into smaller problems
C)
The creation of music that can be played on a computer
D)
The breaking down of a program until it no longer exists

Correct Answer :   The breaking down of a problem into smaller problems

A)
Writing binary numbers
B)
Thinking like a computer
C)
Identifying what problems need to be solved
D)
Identifying the steps involved in solving a problem

Correct Answer :   Identifying the steps involved in solving a problem

A)
A problem
B)
A solution to a problem
C)
The steps that are taken to solve a problem
D)
The words to enter when typing

Correct Answer :   The steps that are taken to solve a problem

48 .
The following algorithm should take an input and add together two numbers, outputting the result.

Identify the correct algorithm
A)
num1=input("Enter the first number")

num2=input("Enter the second number")

num3=num1+num2

print(num3)
B)
num1=input("Enter the first number")

num3=input("Enter the secon number")

num3=num1+num2

print(num3)
C)
num1=input("Enter the first number")

num2=input("Enter the second number")

num3=num1+num2

print(num2)
D)
Num1=input("Enter the first number")

Num2=input("Enter the second number")

num3=num1+num2

print(Num3)

num1=input("Enter the first number")

num2=input("Enter the second number")

num3=num1+num2

print(num3)

49 .
The following algorithm should take a numerical input, and output the 1 to 12 times table for that number.

Identify the correct algorithm
A)
number=input("Enter a number")

for x = 0 to 12

print(number * x)

next x
B)
number=input("Enter a number")

for x = 1 to 12

print(number*number)

next x
C)
number=input("Enter a number")

for x = 1 to 12

print(number X x)

next x
D)
number=input("Enter a number")

for x = 1 to 12

print(number*x)

next x

number=input("Enter a number")

for x = 1 to 12

print(number*x)

next x

50 .
The following algorithm should take as input two numbers, add them together, multiply the answer by 11, add 4, then divide by 2. It should output the result. Identify the correct algorithm.
A)
number = input(“Enter a number”)
number2 = input(“Enter the second number”)
final = number + number2 +4 *11 / 2
print (final)
B)
number = input(“Enter a number”)
number2 = input(“Enter the second number”)
final = (((number + number2) * 11) + 4) / 2 print (final)
C)
number = input(“Enter a number”)
number = input(“Enter the second number”)
final = (((number + number) * 11) + 4) / 2
print(final)
D)
number2 = input(“Enter the second number”)
final = (((number + number2) * 11) + 4) * 2
print (final)

number = input(“Enter a number”)
number2 = input(“Enter the second number”)
final = (((number + number2) * 11) + 4) / 2 print (final)

A)
Merge
B)
Binary
C)
Bubble
D)
Insertion

A)
Merge
B)
Binary
C)
Bubble
D)
Insertion

A)
x + y using repeated subtraction
B)
the greatest common divisor of x and y
C)
x mod y using repeated subtraction
D)
the least common multiple of x and y

Correct Answer :   the greatest common divisor of x and y

A)
Tower of hanoi
B)
N queen problem
C)
M coloring problem
D)
Knight tour problem

Correct Answer :   Tower of hanoi

55 .
Suppose T(n) = 2T(n/2) + n, T(0) = T(1) = 1 Which one of the following is false.
a) T(n) = O(n^2)
b) T(n) = theta(nLogn)
c) T(n) = Omega(n^2)
d) T(n) = O(nLogn)
A)
A
B)
B
C)
C
D)
D

T(n) = Omega(n^2)

A)
nk
B)
n( k â€“ 1)
C)
(n â€“ 1) k+ 1
D)
n( k â€“ 1) + 1

Correct Answer :   n( k â€“ 1) + 1

A)
Theta(n^4)
B)
Theta(n^3)
C)
O(n^2logn)
D)
Theta(n^2logn)

58 .
Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program is erroneous.
``````   f(int Y[10], int x) {
int i, j, k;
i = 0; j = 9;
do {
k =  (i + j) /2;
if( Y[k] < x)  i = k; else j = k;
} while(Y[k] != x && i < j);
if(Y[k] == x) printf ("x is in the array ") ;
else printf (" x is not in the array ") ;
}``````

On which of the following contents of Y and x does the program fail?

A)
Y is [2 2 2 2 2 2 2 2 2 2] and x > 2
B)
Y is [1 2 3 4 5 6 7 8 9 10] and x < 10
C)
Y is [1 3 5 7 9 11 13 15 17 19] and x < 1
D)
Y is [2 4 6 8 10 12 14 16 18 20] and 2 < x < 20 and x is even

Correct Answer :   Y is [2 2 2 2 2 2 2 2 2 2] and x > 2

Explaination : The above program doesn’t work for the cases where element to be searched is the last element of Y[] or greater than the last element (or maximum element) in Y[]. For such cases, program goes in an infinite loop because i is assigned value as k in all iterations, and i never becomes equal to or greater than j. So while condition never becomes false.

A)
NP-complete is a subset of NP Hard
B)
The first problem that was proved as NP-complete was the circuit satisfiability problem.
C)
If we want to prove that a problem X is NP-Hard, we take a known NP-Hard problem Y and reduce Y to X
D)
All of the above

Correct Answer :   All of the above

A)
11, 10, 011, 010, 001, 000
B)
11, 10, 01, 001, 0001, 0000
C)
0, 10, 110, 1110, 11110, 11111
D)
110, 100, 010, 000, 001, 111

Correct Answer :   0, 10, 110, 1110, 11110, 11111

A)
1.9375
B)
2.1875
C)
2.25
D)
3

A)
23
B)
34
C)
43
D)
54

A)
Sequence
B)
Selection
C)
Iteration
D)
All of the above

Correct Answer :   All of the above

A)
TCP
B)
DIV
C)
MOD
D)
SHOW

A)
Boolean
B)
String
C)
Double
D)
Integer

Explanation : The Bellmann Ford Algorithm returns a boolean value.

A)
Sorting
B)
Greedy algorithm
C)
Dynamic programming
D)
Backtracking

A)
AVL Trees are a type of self-balancing Binary Search Trees.
B)
The height of an AVL Tree always remains of the order of O(logn)
C)
The difference between the heights of left and right nodes cannot be more than 1.
D)
All of the above

Correct Answer :   All of the above

A)
Recursive
B)
Abstract Data Type
C)
File structure
D)
Storage structure

Correct Answer :   Abstract Data Type

A)
Overflow
B)
Garbage Value
C)
Underflow
D)
Syntax Error

A)
NP-complete problem
B)
NP problem
C)
P Class Problem
D)
N Class Problem

A)
Backtracking
B)
Greedy Technique
C)
Linear programming
D)
Dynamic Programming

A)
0/1 knapsack problem
B)
Continuous Knapsack Problem
C)
Divisible knapsack problem
D)
Non-continuous knapsack problem

Correct Answer :   Continuous Knapsack Problem

A)
O(V)
B)
O(E)
C)
O(V + E)
D)
O(V * log E)

Correct Answer :   O(V + E)

A)
Merge Sort
B)
Bubble Sort
C)
Heap Sort
D)
Counting Sort

A)
O(nlog(logn)) Precomputation, O(1) for check.
B)
O(n) Precomputation, O(1) for the check.
C)
O(n) Precomputation, O(logn) for check.
D)
O(n * logn) Precomputation, O(logn) for check.

Correct Answer :   O(nlog(logn)) Precomputation, O(1) for check.

A)
T(n)= T(n/2)+n
B)
T(n)= T(n/2)+k
C)
T(n)= 2T(n/2)+k
D)
T(n)= T(n/2)+logn

A)
B)
Cubic
C)
Linear
D)
Exponential

A)
equal to deterministic algorithm
B)
greater than deterministic algorithm
C)
less than deterministic algorithm
D)
None of the above

Correct Answer :   less than deterministic algorithm

A)
5
B)
14
C)
20
D)
45

Explanation :

The no of keys given are 4
apply the formula Bn=1/(n+1)*(2n!/n!n!)
where B is the binary tree and n is the number of keys.
Bn=1/(4+1)*(8!/4!4!)
Bn=1/5*(8*7*6*5*4!)/4!4!
Bn=8*7*9*6/(4*3*2)
Bn=56/4
Bn=14
Hence, the total no of binary trees with n=4 is 14.

A)
6
B)
4
C)
3
D)
2

Explanation :

A B-tree of order m contains n records and each contains b records on average then the tree will have about n/b leaves. If we split k nodes along the path from leaves then
k<=1+logm/2 [n/b]
here n=10,b=3,m=4 so
k<=1+log4/2 [n/b]
k<=1+log2 4
k<= 1+2
k<=3

A)
Post-order Traveral
B)
In-order Traversal
C)
Pre-order Traversal
D)
None of the above

A)
1, 3, 3, 6, 8, 9
B)
1, 3, 4, 6, 8, 9
C)
9, 8, 6, 3, 3, 1
D)
9, 8, 6, 4, 3, 1

Correct Answer :   9, 8, 6, 3, 3, 1

Explanation : A sequence of values is said to be in non-increasing order, if the successive element is less than or equal to its previous element in the sequence.

A)
size of array
B)
sequence of values
C)
pivot element
D)
None of the above

A)
B)
C)
takes input which is already sorted.
D)
None of the above

Explanation : A sorting algorithm is said to be adaptive, if it takes advantage of already 'sorted' elements in the list that is to be sorted.

A)
Stable
B)
Unstable
C)
In-Partition
D)
In-Place

A)
Insertion Sort
B)
Bubble Sort
C)
Merge Sort
D)
Selection Sort

A)
BFS
B)
Prims Algorithm
C)
Kruskalâ€™s Algorithm
D)
Djikstraâ€™s Algorithm

A)
Sentence Ordering
B)
Course Scheduling
C)
D)
All of the above

Correct Answer :   All of the above

A)
O(1)
B)
O(N)
C)
O(logN)
D)
O(NlogN)

A)
Vertex Cover Problem
B)
0/1 Knapsack Problem
C)
Travelling Salesman Problem
D)
Maximal Independent Set Problem

Correct Answer :   0/1 Knapsack Problem

A)
Binary tree
B)
Tree structure
C)
Complete binary tree
D)
None of the above

Correct Answer :   Complete binary tree

A)
n - 1
B)
n
C)
1
D)
n - 2

Correct Answer :   n - 1

A)
n+e-1
B)
n-e+1
C)
e-n-1
D)
e-n+1

Explanation : We can remove maximum `e-n+1` edges to get a spanning tree from complete graph. Any more deletion of edges will lead the graph to be disconnected.

A)
9 edges
B)
10 edges
C)
11 edges
D)
11 vertices

A)
T(n2), T(n2) and T(n Log n)
B)
T(n2), T(n log n) and T(n2)
C)
T(n log n), T(n log n) and T(n2)
D)
T(n2), T(n log n) and T(n log n)

Correct Answer :   T(n2), T(n log n) and T(n2)

A)
If, It can be reduced to the 3-SAT problem in polynomial time
B)
some problem in NP can be reduced to it in polynomial time
C)
The 3-SAT problem can be reduced to it in polynomial time
D)
It can be reduced to any other problem in NP in polynomial time

Correct Answer :   The 3-SAT problem can be reduced to it in polynomial time

A)
At most 1
B)
At most 2
C)
Exactly 1
D)
Depending on the graph

A)
DP Problem
B)
C)
Both (A) and (B)
D)
Greedy Algorithm

A)
Z Algorithm
B)
KMP Algorithm
C)
Rabin Karp Algorithm
D)
All of the above

Correct Answer :   All of the above

A)
pop()
B)
peek()
C)
push()
D)
findTop()

A)
f4(n) = 2^n.
B)
f3(n) = nlogn
C)
f2(n) = n^(logn)
D)
f1(n) = n^(3/2)

Correct Answer :   f4(n) = 2^n.

102 .
Consider the following pseudo code, where x and y are positive integers.
``````begin
q := 0
r := x
while r >= y do
begin
r := r – y
q := q + 1
end
end ``````
The post condition that needs to be satisfied after the program terminates is
A)
{r = qx + y ∧ r < y}
B)
{ q + 1 < r–y ∧ y > 0}
C)
{x = qy + r ∧ r < y}
D)
{y = qx + r ∧ 0 < r < y}

Correct Answer :   {x = qy + r ∧ r < y}

Explaination :

The given pseudo code does following for given x and y which positive integers.
1) It initializes r as x.
2) It repeatedly subtracts y from r until r becomes
smaller than y.  For every subtraction, it
increments count q.
3) Finally r contains remainder, i.e., x%y and q contains
⌊x/y⌋
See below pseudo code with comments.
``````begin
q := 0  // q is going to contain floor(x/y)
r := x  // r is going to contain x % y

// Repeatedly subtract y from x.
while r >= y do
begin
r := r – y
q := q + 1
end
end``````

A)
When elements are sorted in ascending order
B)
When elements are not sorted by any order
C)
When elements are sorted in descending order
D)
There is no best case for Bubble Sort. It always takes O(n*n) time

Correct Answer :   When elements are sorted in ascending order

A)
Circle
B)
Ellipse
C)
Hexagon
D)
Rectangle