Algorithm MCQ (Multiple Choice Questions), Algorithm Online Quiz

1 .

An Algorithm is__________

A)

A problem

B)

A real life mathematical problem

C)

A procedure for solving a problem

D)

None of the above

Correct Answer : Option (C) : A procedure for solving a problem

2 .

Dijkstra's algorithm is used to solve __________ problems?

A)

Network lock

B)

Sorting

C)

All pair shortest path

D)

Single source shortest path

Correct Answer : Option (D) : Single source shortest path

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

3 .

An algorithm in which we divide the problem into subproblem and then we combine the subsolutions to form solution to the original problem is known as _________

A)

Brute Force

B)

Divide and Conquer

C)

GreedyAlgorithm

D)

None of the above

Correct Answer : Option (A) : Divide and Conquer

4 .

Which sorting algorithm is described by: split a list into individual lists, then combine these, two lists at a time.

A)

Bubble

B)

Merge

C)

Insertion

D)

None of the above

Correct Answer : Option (B) : Merge

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)

Correct Answer : Option (A) : O(1)

6 .

Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using randomized quicksort?

A)

O (n)

B)

O(!n)

C)

O(n^2)

D)

O (n log n)

Correct Answer : Option (C) : O(n^2)

7 .

The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is

A)

148

B)

147

C)

146

D)

140

Correct Answer : Option (A) : 148

8 .

Which of the following sorting algorithms has the lowest worst-case complexity?

A)

Selection Sort

B)

Quick Sort

C)

Bubble Sort

D)

Merge Sort

Correct Answer : Option (D) : Merge Sort

9 .

An algorithm which uses the past results and uses them to find the new results is _________

A)

Brute Force

B)

Divide and Conquer

C)

Dynamic programming algorithms

D)

None of the above

Correct Answer : Option (C) : Dynamic programming algorithms

10 .

A Complexity of algorithm depends upon _________

A)

Time only

B)

Space only

C)

Both (A) and (B)

D)

None of the above

Correct Answer : Option (C) : Both (A) and (B)

11 .

There are two algorithms suppose A takes 1.41 milli seconds while B takes 0.9 milliseconds, which one of them is better considering all other things the same?

A)

A is better than B

B)

B is better than A

C)

Both are equally good

D)

None of the above

Correct Answer : Option (B) : B is better than A

12 .

Which sorting algorithm is described by taking each item in turn, compare it to the items in the sorted list and place it in the ordered position in the sorted list?

A)

Insertion

B)

Merge

C)

Bubble

D)

None of the above

Correct Answer : Option (A) : Insertion

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 : Option (D) : 6 8 1 3 12

14 .

Which sorting algorithm splits a list of items into individual lists?

A)

Bubble

B)

Merge

C)

Insertion

D)

None of them do

Correct Answer : Option (B) : Merge

15 .

Which sorting algorithm takes an item from the list, and puts it in the correct place in a sorted list?

A)

Bubble

B)

Merge

C)

Insertion

D)

None of them do

Correct Answer : Option (C) : Insertion

16 .

How many arrows should come out of a decision symbol in a flowchart?

A)

0

B)

1

C)

2

D)

3

Correct Answer : Option (C) : 2

17 .

Which of the following is not a sorting algorithm?

A)

Binary

B)

Merge

C)

Bubble

D)

Insertion

Correct Answer : Option (A) : Binary

18 .

An algorithm: can be represented through _________

A)

flow charts

B)

pseudo codes

C)

instructions in common language

D)

All of the above

Correct Answer : Option (D) : All of the above

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

19 .

For an algorithm which is the most important characteristic that makes it acceptable _________

A)

Fast

B)

Compact

C)

Correctness and Precision

D)

None of the above

Correct Answer : Option (C) : Correctness and Precision

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

20 .

Optimization of algorithm means _________

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 : Option (B) : making that algorithm fast by time and compact by space

Explanation : An Algorithm should be fast and compact.

21 .

An algorithm which tries all the possibilities unless results are satisfactory is and generally is time-consuming is________

A)

Brute Force

B)

Divide and Conquer

C)

Dynamic programming algorithms

D)

None of the above

Correct Answer : Option (A) : Brute Force

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

22 .

For a recursive algorithm ________

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 : Option (B) : a base case is not necessary

23 .

Which of the following standard algorithms is not Dynamic Programming based.

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 : Option (C) : Prim's Minimum Spanning Tree

24 .

Which of the following is not true about comparison based sorting algorithms?

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 : Option (D) : Heap Sort is not a comparison based sorting algorithm.

25 .

Which of the following is not O(n^2)?

A)

n^3 / (sqrt(n))

B)

n^1.98

C)

(2^20) * n

D)

(15^10) * n + 12099

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

26 .

Which sorting algorithm is described by moving through a list repeatedly, swapping elements that are in the wrong order?

A)

Bubble

B)

Merge

C)

Insertion

D)

None of the above

Correct Answer : Option (A) : Bubble

27 .

What is the first action in an insertion sort?

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 : Option (D) : 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 : Option (C) : Compare 2 and 1 and put 1 into a new list

29 .

Which sorting algorithm always requires the same number of iterations as the length of the list?

A)

Merge

B)

Insertion

C)

Bubble

D)

None of them do

Correct Answer : Option (B) : Insertion

30 .

Identify the search algorithm

A)

Denary search

B)

Binary search

C)

Random search

D)

Next Item search

Correct Answer : Option (B) : Binary search

31 .

Identify the description of a linear 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 : Option (A) : Elements do not need to be in order, check each item in turn

32 .

Identify the description of a binary search

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 : Option (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

33 .

A technique for direct search is_______

A)

Tree Search

B)

Linear Search

C)

Hashing

D)

Binary Search

Correct Answer : Option (C) : Hashing

34 .

Assume the input array is nearly sorted. Then performance of Quick sort is______

A)

Worst than Average case

B)

Same as in Average case

C)

Better than Average case

D)

None of the above

Correct Answer : Option (A) : Worst than Average case

35 .

What is the time complexity of insertion sort in best case?

A)

O(n2)

B)

O(n)

C)

O(log2n)

D)

O(nlog2n)

Correct Answer : Option (B) : O(n)

36 .

The time factor when determining the efficiency of algorithm is measured by

A)

Counting microseconds

B)

Counting the number of statements

C)

Counting the kilobytes of algorithm

D)

Counting the number of key operations

Correct Answer : Option (D) : Counting the number of key operations

37 .

An hash table with chaining as a collision resolution technique degenerates to a

A)

Tree

B)

Stack

C)

Queue

D)

Linked List

Correct Answer : Option (D) : Linked List

38 .

Which of the following algorithm design technique is used in the quick sort algorithm?

A)

Backtracking

B)

Greedy method

C)

Divide and conquer

D)

Dynamic programming

Correct Answer : Option (C) : Divide and conquer

39 .

Binary Search Method has Worst Case Time Complexity of

A)

log(n)

B)

2n

C)

n*n

D)

nlog(n)

Correct Answer : Option (A) : log(n)

40 .

The average case complexity of Insertion Sort is

A)

O(2n)

B)

O(n2)

C)

O(2n)

D)

O(n3)

Correct Answer : Option (B) : O(n2)

41 .

For the Quick sort algorithm, what is the time complexity of the best/worst case?

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 : Option (C) : best case: O(n log(n) ) worst case: O(n2)

42 .

Define the term computational thinking

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 : Option (D) : Developing an algorithm to solve a problem

43 .

Which of the following is not a component of computational thinking?

A)

Typing

B)

Abstraction

C)

Decomposition

D)

Algorithmic thinking

Correct Answer : Option (A) : Typing

44 .

Define the term abstraction within computational thinking

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 : Option (B) : Representing real world problems in a computer program, using symbols and removing unnecessary elements

45 .

Define the term decomposition within computational thinking_________

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 : Option (B) : The breaking down of a problem into smaller problems

46 .

Identify which statement describes algorithmic thinking

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 : Option (D) : Identifying the steps involved in solving a problem

47 .

Identify the correct definition for 'algorithm'

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 : Option (C) : 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)

Correct Answer : Option (A) :

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

Correct Answer : Option (D) :

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)

Correct Answer : Option (B) :

number = input(“Enter a number”)

number2 = input(“Enter the second number”)

final = (((number + number2) * 11) + 4) / 2 print (final)

51 .

Which sorting algorithm is the fastest for a very unordered list?

A)

Merge

B)

Binary

C)

Bubble

D)

Insertion

Correct Answer : Option (A) : Merge

52 .

Which sorting algorithm is the fastest for a list that is in the correct order?

A)

Merge

B)

Binary

C)

Bubble

D)

Insertion

Correct Answer : Option (C) : Bubble

53 .

What does the program compute?

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 : Option (B) : the greatest common divisor of x and y

54 .

Which of the following is not a backtracking algorithm?

A)

Tower of hanoi

B)

N queen problem

C)

M coloring problem

D)

Knight tour problem

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

Correct Answer : Option (C) :

T(n) = Omega(n^2)

56 .

In a complete k-ary tree, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is:

A)

nk

B)

n( k â€“ 1)

C)

(n â€“ 1) k+ 1

D)

n( k â€“ 1) + 1

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

57 .

What is the time complexity of Floydâ€“Warshall algorithm to calculate all pair shortest path in a graph with n vertices?

A)

Theta(n^4)

B)

Theta(n^3)

C)

O(n^2logn)

D)

Theta(n^2logn)

Correct Answer : Option (B) : 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 : Option (A) : 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.

59 .

Which of the following is true about NP-Complete and NP-Hard problems.

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 : Option (D) : All of the above

60 .

Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. Which of the following is the Huffman code for the letter a, b, c, d, e, f?

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 : Option (C) : 0, 10, 110, 1110, 11110, 11111

61 .

Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. What is the average length of Huffman codes?

A)

1.9375

B)

2.1875

C)

2.25

D)

3

Correct Answer : Option (A) : 1.9375

62 .

Consider two strings A = "qpqrr" and B = "pqprqrp". Let x be the length of the longest common subsequence (not necessarily contiguous) between A and B and let y be the number of such longest common subsequences between A and B. Then x + 10y = ___.

A)

23

B)

34

C)

43

D)

54

Correct Answer : Option (B) : 34

63 .

Identify which of the following are basic programming constructs

A)

Sequence

B)

Selection

C)

Iteration

D)

All of the above

Correct Answer : Option (D) : All of the above

64 .

Which key word will return the remainder of a division

A)

TCP

B)

DIV

C)

MOD

D)

SHOW

Correct Answer : Option (C) : MOD

65 .

The Bellmann Ford Algorithm returns __________ value?

A)

Boolean

B)

String

C)

Double

D)

Integer

Correct Answer : Option (A) : Boolean

Explanation : The Bellmann Ford Algorithm returns a boolean value.

66 .

Which of the following is used for solving the N Queens Problem?

A)

Sorting

B)

Greedy algorithm

C)

Dynamic programming

D)

Backtracking

Correct Answer : Option (D) : Backtracking

67 .

Which of the following statements is true about AVL Trees?

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 : Option (D) : All of the above

68 .

Representation of data structure in memory is known as?

A)

Recursive

B)

Abstract Data Type

C)

File structure

D)

Storage structure

Correct Answer : Option (B) : Abstract Data Type

69 .

When a pop() operation is called on an empty queue, what is the condition called?

A)

Overflow

B)

Garbage Value

C)

Underflow

D)

Syntax Error

Correct Answer : Option (C) : Underflow

70 .

Hamiltonian path problem is _________?

A)

NP-complete problem

B)

NP problem

C)

P Class Problem

D)

N Class Problem

Correct Answer : Option (A) : NP-complete problem

71 .

Identify the approach followed in Floyd Warshall's algorithm?

A)

Backtracking

B)

Greedy Technique

C)

Linear programming

D)

Dynamic Programming

Correct Answer : Option (D) : Dynamic Programming

72 .

Another name of the fractional knapsack is?

A)

0/1 knapsack problem

B)

Continuous Knapsack Problem

C)

Divisible knapsack problem

D)

Non-continuous knapsack problem

Correct Answer : Option (B) : Continuous Knapsack Problem

73 .

In what time complexity can we find the diameter of a binary tree optimally?

A)

O(V)

B)

O(E)

C)

O(V + E)

D)

O(V * log E)

Correct Answer : Option (C) : O(V + E)

74 .

What will be the best sorting algorithm, given that the array elements are small (<= 1e6)?

A)

Merge Sort

B)

Bubble Sort

C)

Heap Sort

D)

Counting Sort

Correct Answer : Option (D) : Counting Sort

75 .

What is the time complexity of the Sieve of Eratosthenes to check if a number is prime?

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 : Option (A) : O(nlog(logn)) Precomputation, O(1) for check.

76 .

The recurrence relation that arises in relation with the complexity of the binary search is

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 : Option (B) : T(n)= T(n/2)+k

77 .

What is the Time complexity of insertion sort?

A)

Quadratic

B)

Cubic

C)

Linear

D)

Exponential

Correct Answer : Option (A) : Quadratic

78 .

The time complexity of the non-deterministic algorithm is always__________

A)

equal to deterministic algorithm

B)

greater than deterministic algorithm

C)

less than deterministic algorithm

D)

None of the above

Correct Answer : Option (C) : less than deterministic algorithm

79 .

Out of 4 distinct keys how many distinct primary keys can be created?

A)

5

B)

14

C)

20

D)

45

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

80 .

Algorithms: Consider a B-tree of order 4 and is built from scratch by 10 successive insertions. What would be the maximum number of node splitting operations that take place?

A)

6

B)

4

C)

3

D)

2

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

81 .

Visiting root node after visiting left and right sub-trees is called

A)

Post-order Traveral

B)

In-order Traversal

C)

Pre-order Traversal

D)

None of the above

Correct Answer : Option (A) : Post-order Traveral

82 .

Which of the below given series is Non-Increasing Order âˆ’

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 : Option (C) : 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.

83 .

Quick sort running time depends on the selection of

A)

size of array

B)

sequence of values

C)

pivot element

D)

None of the above

Correct Answer : Option (C) : pivot element

84 .

An adaptive sorting algorithm_______

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 : Option (B) : 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.

85 .

What is the technique called in which it does not require extra memory for carrying out the sorting procedure?

A)

Stable

B)

Unstable

C)

In-Partition

D)

In-Place

Correct Answer : Option (D) : In-Place

86 .

Among the following options which is the best sorting algorithm when the list is already sorted?

A)

Insertion Sort

B)

Bubble Sort

C)

Merge Sort

D)

Selection Sort

Correct Answer : Option (A) : Insertion Sort

87 .

Which of the following algorithms are used to find the shortest path from a source node to all other nodes in a weighted graph?

A)

BFS

B)

Prims Algorithm

C)

Kruskalâ€™s Algorithm

D)

Djikstraâ€™s Algorithm

Correct Answer : Option (D) : Djikstraâ€™s Algorithm

88 .

Which of the following are applications of Topological Sort of a graph?

A)

Sentence Ordering

B)

Course Scheduling

C)

OS Deadlock Detection

D)

All of the above

Correct Answer : Option (D) : All of the above

89 .

What is the time complexity in decreasing the node value in a binomial heap?

A)

O(1)

B)

O(N)

C)

O(logN)

D)

O(NlogN)

Correct Answer : Option (C) : O(logN)

90 .

Which of the following is known to be not an NP-Hard Problem?

A)

Vertex Cover Problem

B)

0/1 Knapsack Problem

C)

Travelling Salesman Problem

D)

Maximal Independent Set Problem

Correct Answer : Option (B) : 0/1 Knapsack Problem

91 .

Heap is a_________?

A)

Binary tree

B)

Tree structure

C)

Complete binary tree

D)

None of the above

Correct Answer : Option (C) : Complete binary tree

92 .

What is the maximum number of swaps that can be performed in the Selection Sort algorithm?

A)

n - 1

B)

n

C)

1

D)

n - 2

Correct Answer : Option (A) : n - 1

93 .

From a complete graph, by removing maximum _______________ edges, we can construct a spanning tree.

A)

n+e-1

B)

n-e+1

C)

e-n-1

D)

e-n+1

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

94 .

The spanning tree of connected graph with 10 vertices contains

A)

9 edges

B)

10 edges

C)

11 edges

D)

11 vertices

Correct Answer : Option (A) : 9 edges

95 .

The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:

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 : Option (B) : T(n2), T(n log n) and T(n2)

96 .

A problem in NP is NP-complete

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 : Option (C) : The 3-SAT problem can be reduced to it in polynomial time

97 .

In a graph of n nodes and n edges, how many cycles will be present?

A)

At most 1

B)

At most 2

C)

Exactly 1

D)

Depending on the graph

Correct Answer : Option (C) : Exactly 1

98 .

Kruskalâ€™s Algorithm for finding the Minimum Spanning Tree of a graph is a kind of a?

A)

DP Problem

B)

Adhoc Problem

C)

Both (A) and (B)

D)

Greedy Algorithm

Correct Answer : Option (D) : Greedy Algorithm

99 .

Which of the following algorithms are used for string and pattern matching problems?

A)

Z Algorithm

B)

KMP Algorithm

C)

Rabin Karp Algorithm

D)

All of the above

Correct Answer : Option (D) : All of the above

100 .

Identify the function of the stack that returns the top data element of the stack?

A)

pop()

B)

peek()

C)

push()

D)

findTop()

Correct Answer : Option (B) : peek()

101 .

Which of the following functions provides the maximum asymptotic complexity?

A)

f4(n) = 2^n.

B)

f3(n) = nlogn

C)

f2(n) = n^(logn)

D)

f1(n) = n^(3/2)

Correct Answer : Option (A) : 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 : Option (C) : {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

103 .

Assume that we use Bubble Sort to sort n distinct elements in ascending order. When does the best case of Bubble Sort occur?

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 : Option (A) : When elements are sorted in ascending order

104 .

External entities in DFD are shown by_________

A)

Circle

B)

Ellipse

C)

Hexagon

D)

Rectangle

Correct Answer : Option (D) : Rectangle