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

Correct Answer : Merge

A)

O(1)

B)

O (n)

C)

O(!n)

D)

O (n log n)

Correct Answer : O(1)

A)

O (n)

B)

O(!n)

C)

O(n^2)

D)

O (n log n)

Correct Answer : O(n^2)

A)

148

B)

147

C)

146

D)

140

Correct Answer : 148

A)

Selection Sort

B)

Quick Sort

C)

Bubble Sort

D)

Merge Sort

Correct Answer : 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

Correct Answer : Insertion

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

Correct Answer : Merge

A)

Bubble

B)

Merge

C)

Insertion

D)

None of them do

Correct Answer : Insertion

A)

0

B)

1

C)

2

D)

3

Correct Answer : 2

A)

Binary

B)

Merge

C)

Bubble

D)

Insertion

Correct Answer : Binary

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

Correct Answer : Brute Force

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

Correct Answer : Bubble

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

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

Correct Answer : Insertion

A)

Denary search

B)

Binary search

C)

Random search

D)

Next Item search

Correct Answer : Binary 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

Correct Answer : Hashing

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)

Correct Answer : O(n)

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)

Linked List

Correct Answer : Linked List

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)

Correct Answer : log(n)

A)

O(2n)

B)

O(n2)

C)

O(2n)

D)

O(n3)

Correct Answer : O(n2)

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)

Google is computational thinking

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

Correct Answer : Typing

A)

Adding together numbers

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

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)

Correct Answer :

num1=input("Enter the first number")

num2=input("Enter the second number")

num3=num1+num2

print(num3)

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

Correct Answer :

number=input("Enter a number")

for x = 1 to 12

print(number*x)

next x

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)

Correct Answer :

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

Correct Answer : Merge

A)

Merge

B)

Binary

C)

Bubble

D)

Insertion

Correct Answer : Bubble

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

A)

A

B)

B

C)

C

D)

D

Correct Answer :

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)

Correct Answer : Theta(n^3)

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

Correct Answer : 1.9375

A)

23

B)

34

C)

43

D)

54

Correct Answer : 34

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

Correct Answer : MOD

A)

Boolean

B)

String

C)

Double

D)

Integer

Correct Answer : Boolean

Explanation : The Bellmann Ford Algorithm returns a boolean value.

A)

Sorting

B)

Greedy algorithm

C)

Dynamic programming

D)

Backtracking

Correct Answer : 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

Correct Answer : Underflow

A)

NP-complete problem

B)

NP problem

C)

P Class Problem

D)

N Class Problem

Correct Answer : NP-complete problem

A)

Backtracking

B)

Greedy Technique

C)

Linear programming

D)

Dynamic Programming

Correct Answer : 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

Correct Answer : 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

Correct Answer : T(n)= T(n/2)+k

A)

Quadratic

B)

Cubic

C)

Linear

D)

Exponential

Correct Answer : Quadratic

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

Correct Answer : 14

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

Correct Answer : 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

Correct Answer : Post-order Traveral

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

Correct Answer : pivot element

A)

adapts to new computers.

B)

takes advantage of already sorted elements.

C)

takes input which is already sorted.

D)

None of the above

Correct Answer : takes advantage of already sorted elements.

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

Correct Answer : In-Place

A)

Insertion Sort

B)

Bubble Sort

C)

Merge Sort

D)

Selection Sort

Correct Answer : Insertion Sort

A)

BFS

B)

Prims Algorithm

C)

Kruskalâ€™s Algorithm

D)

Djikstraâ€™s Algorithm

Correct Answer : Djikstraâ€™s Algorithm

A)

Sentence Ordering

B)

Course Scheduling

C)

OS Deadlock Detection

D)

All of the above

Correct Answer : All of the above

A)

O(1)

B)

O(N)

C)

O(logN)

D)

O(NlogN)

Correct Answer : O(logN)

A)

Vertex Cover Problem

B)

0/1 Knapsack Problem

C)

Travelling Salesman Problem

D)

Maximal Independent Set Problem

Correct Answer : 0/1 Knapsack Problem

91 .

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

Correct Answer : 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

Correct Answer : 9 edges

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

Correct Answer : Exactly 1

A)

DP Problem

B)

Adhoc Problem

C)

Both (A) and (B)

D)

Greedy Algorithm

Correct Answer : 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()

Correct Answer : peek()

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.

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

Correct Answer : Rectangle