Monday, June 22, 2020

Digital Electronics Quiz

1. The number of level in a digital signal is:

 a) one

b) two

c) four

d) ten

 

2. A pure sine wave is :

 a) a digital signal

b) analog signal

c) can be digital or analog signal

d) neither digital nor analog signal

 

3. The high voltage level of a digital signal in positive logic is :

 a) 1

b) 0

c) either 1 or 0

 

4. A device that converts from decimal to binary numbered is called :

 a) decoder

b) encoder

c) CPU

d) convertor

 

5. K is an abbreviation used with a number of units. Thus 2K means

a) 2000 units

b) 2048 units

c) 2024 units

d) none of these

 

6. Bit is:

 a) smallest piece of electronic hardware

b) a drilling tool

c) an abbreviation for binary digit

d) the smallest number

 

7. A register is:

 a) a group of memories

b) a group of devices that store digital data

c) a chip used in computer

d) a pure silica piece used in digital system

 

8. A typical microcomputer has 65,536 registers in its memory. It will be specified as :

 a) 65,536 memory

b) 65,536 K memory

c) 64 K memory

d) 8 K memory

 

9. Nibble is :

 a) a string of 4 bits

b) a string of 8 bits

c) a string of 16 bits

d) a string of 64 bits

 

10. The high voltage level of a digital signal in negative logic is :

 a) 1

b) 0

c) either 1 or 0

 

11.Number of gates/chip in SSI :

 a) < 12

b) < 100

c) < 1000

d)  > 1000

 

11. Number of gates/chip in LSI :

 a) < 12

b) Between 12 and 99

c) < 1000

d)  > 1000

 

 

12. Number of gates/chip in VLSI :

 a) < 12

b) < 100

c) < 1000

d)  >10000

 

 

13.The electronic, magnetic and mechanical devices of a computer are known as:

 a) CPU

b) memory

c) hardware

d) radix

 

14. Ordinary electrical switch is:

 a) Analog

b) Digital

c) None of the above

 

15. Train of pulses is:

 a) Analog

b) Digital

c) None of the above

 

 

16. Octal 16 is equal to decimal:

 a) 13

b) 14

c) 15

d) 16

 

17. The binary number 101101 is equal to octal number:

 a) 65

b) 55

c) 51

d) 45

 

18. Binary number 101101 when converted to its 2’s complement will become :

 a) 0101.01

b) 0100.11

c) 0100.10

d) 0101.10

 

19. The sum of binary numbers 11111 and 00001 is given by :

 a) 100100

b) 100000

c) 100001

d) 100010

 

 

20. The hexadecimal digits are :

 a) 1 to 16

b) 1 to 9

c) 0 to 9

d) 1 to 6

 

21. A gate in which all input must be low to get a high output is called:

 a) an inverter

b) A NOR gate

c) an AND gate

d) a NAND gate

 

22. A NAND circuit with positive logic will operate as :

 a) NOR with negative logic

b) AND with negative logic

c) OR with negative logic input

d) AND with positive logic output

 

23. To implement all function of the basic logic function, is sufficient to have:

 a) OR

b) NOT

c) AND NOT

d) none of these

 

24. Which of the following ICs has only one NAND gate:

 a) 7410

b) 7420

c) 7430

d) 7447

 

25. OR operation is:

 a) X + XY

B) XY

C) X+Y

D) (X+Y) (X+Y)

 

26. AND operation is:

 a) X(X + Y )

B) XY

C) X+Y

D) (X+Y) (X+Y)

 

27. NOR operation is:

 a)X + Y

B) XY

C) X+Y

D) (X+Y) (X+Y)

 

28. NAND operation is:

 a)X + Y

B) XY

C) X+Y

D) (X+Y) (X+Y)

 

29. What is the no. of OR IC. :

 a) 7402

b) 7486

c) 7432

d) 7404

 

 

30. What is the no. of AND IC. :

 a) 7402

b) 7408

c) 7447

d) 7492

 

32. What is the no. of NOR IC. :

 a) 7402

b) 7486

c) 7447

d) 7492

 

33. What is the no. of NAND IC. :

 a) 7402

b) 7404

c) 7400

d) 7492

 

34. What is the no. of NOT IC. :

 a) 7402

b) 7486

c) 7404

d) 7492

 

35. What is the no. of EX-OR IC. :

 a) 7402

b) 7486

c) 7447

d) 7492

 

36. Which of the following ICs has three input NAND gate:

 a) 7420

b) 7430

c) 7410

d) 7474


37. Which of the following is Boolean eq. of EX-OR gate:

 a) A+B

B) A+B

C) AB

D) A B + A B

 

38. Which one is the universal gate:

 a) AND gate

b) OR gate

c) NAND gate

d) EX-OR gate

 

39. Bubbles on the gate shows

 a) active high

b) active low

c) both a and b

d) none

 

40. Which statement is verify NAND gate :

 a) if all input are high output is low

b) if all input are low output is low

c) any one n are low output is low

d) none of them

 

41. In regard to NAND gate the following four statement are made:

 1. it is equivalent to an AND gate followed by an inverter

2. if all input to it are low, the output is low

3. if all input are high, the output is low

4. NAND operation on two elements is equivalent to OR operation on them. OF thses, the only true statements are

a) 1,2

b) 1,3

c) 1,4

d) 2,4

 

42.The Gray code for number 7 is :

 a) 1100

b) 1001

c) 0100

d) 0110

 

43. The gray code for number 2 is :

 a) 0010

b) 0011

c) 1000

d) 0101

 

44. The gray code for number 6 is :

 a) 1100

b) 1001

c) 0101

d) None of the above

 

45. The Excess 3 for number 6 is :

 a) 1100

b) 1001

c) 0101

d) 0110

 

46. The excess 3 number 8 is:

 a) 1100

b) 1011

c) 0101

d) 0110

 

47. BCD numbers are obtained by :

a) converting decimal number to binary

b) converting decimal to octal number

c) each decimal digit is represented by a four bit binary

d) converting binary to decimal

 

48. (100101. 2 is

 a) (37. 10

b) (69. 10

c) (41. 10

d) (5. 10

 

49. (1001-10) is equal to :

a) 7

b) 88

c) 74

d) 84

 

50. Square root of 4 is :

 a) 1616

b) 210

c) 816

d) 516

 

51. In the expression A(A+B) by writing the first term A as A+0, the expression is best simplified as :

 a) A+AB

b) AB

c) A

d) A+B

 

52. A four bit number is given 1001. its one’s complement is :

 a) 1001

b) 1110

c) 0110

d) 0111

 

53. The term VLSI generally refers to a digital IC having :

 (a) more than 1000 gates

(b) more than 100 gates

(c) more than 1000 but less than 9999 gates

(d) more than 100 but less than 999 gates

 

54. The expression for sum of A, B in the half adder is given by:

 a) AB

b) A + B

c) AÐ B

d) none of these

 

55. Which expression for the sum of full adder circuit.:

 a) AB

B) A+B

C) A ® B

D) none of these

 

56. Combinational circuit has :

 a) memory

b) no memory

c) flip-flops

d) counters

 

57. The sum of 1110102 and 110112 in decimal form will be

a) 65

b) 75

c) 85

d) 95

 

58. The digit 0 with carry of I is the sum of binary addition:

 a) 1 + 1

b) 1 + 0

c) 0 + 1

d) 0 + 0

 

59. Which of the following flips-flop is used as latch:

 a) TTL

b) ECL

c) CMO

d) LSI

 

 60. Which of the following flip-flops is used as latch:

 a) JK flip-flop

b) D flip-flop

c) RS flip-flop

d) T flip-flop

 

61. Which of the following circuit can be used as parallel to series converter

 a) digital counter

b) decoder

c) de-multiplexer

d) multiplexer

 

62. Which of the following ICs contain four negative edge triggered flip-flops.

 a) 7493

b) 7486

c) 7490

d) 7419

 

63. Multiplexer is :

 a) 1 input many output

b) many inputs 1 output

c) many input many output

d) one input one output


64. Demultiplexer is :

a) 1 input many output

b) many inputs 1 output

c) many input many output

d) one input one output

 

64. In 8:1 mux the no. of select lines are :

 a) 1

b) 3

c) 5

d) 32

 

65. In 16:1 mux the no. of select lines are :

 a) 6

b) 3

c) 4

d) 5

 

66. In 3: 8 decoder the no. of inputs are

 a) 8

b) 3

c) 1

d) 2

 

67. Decoder is:

 a) ) 1 input many output

b) many inputs 1 output

c) many input many output

d) one input one output

 

68. Sequential circuit has :

a) feedback

b) no feedback

c) may or may not

d) none of these

 

 

69. For a level input sequential circuit :

 a) output in a level only

b) output is in the pulse form

c) output may be a pulse or a level form

d) none of these

 

70. In a ring counter 1 for N clock pulse the scale for the counter is :

 a) N:1

b) N:2

c) N:10

d) N:100

 

71. Binary coded decimal number express each decimal digit as a :

 a) unit

b) bit

c) byte

d) nibble

 

72. How many bytes are there in 1111 1011 0111 0100 1010:

 a) 2

b) 2 ½

c) 3

d) 3 ½

 

73. For a decade counter, number of binaries required is :

a) five

b) ten

c) eight

d) two

 

74. Counter ;

 a) it counts the no. randomly

b) it counts the no. sequentially

c) both a and b

d) none of these

 

 75. What is asynchronous counter :

 a) each flip-flop has it own clock

b) all the flip-flop are combined to common clock

c) both a and b

d) none of the above

 

76. UP Counter is :

 a) it counts in upward manner

b) it count in down ward manner

c) it counts in both the direction

d) none of the above

 

77. DOWN counter is:

 a) it counts in upward manner

b) it count in down ward manner

c) it counts in both the direction

d) none of the above

 

78. Another name of Johnson counter :

 a) asynchronous counter

b) synchronous counter

c) ring counter

d) none of above

 

79. Give full form of SIPO shift registers :

 a) serial in parallel output

b) single in parallel output

c) series input peripherals output

d) none of above

 

80. Give full form of PISO shift registers :

 a) primary input secondary output

b) parallel in secondary output

c) parallel in serial out

d) none of above

 

81. Give full form of PIPO shift registers :

 a) parallel in parallel out

b) primary in parallel out

c) parallel in primary out

d) none

 

82. What is tristate shift registers :

 a) it has 3 inputs

b) it has high , low or high impedance output

c) both a and b

d) none

 

83. Which ICs belongs to tristate shift registers

 a) 7483

b) 7492

c) 74164

d) none

 

84. In bidirectional shift registers date can be shifted to:

 a) right or left

b) up or down

c) both

d) none

 

85. How many 7490 ICs are to be cascaded to count upto 999:

 a) 1

b) 2

c) 3

d) 4


86. Program counter in a digital computer :

 a) counts the number of program run in the machine

b) counts the number of times a subroutine is called

c) counts the number of times the loops are executed

d) points the memory address of the current or the next instruction to be executed

 

87. A ring counter is same as :

 a) up-down counter

b) parallel

c) shift register

d) none of these above

 

88. In a sign magnitude representation, the leading bit

 a) is a part of the number itself

b) is unity for positive

c) is always unity

d) stands for the sign

 

89. In a four variable Karnaugh map eight adjacent cells give a :

 (a) two variable term

(b) single variable term

(c) three variable term

(d) four variable term

 

90. A Karnaugh map with 4 variables has :

 (a) 2 cells

(b) 4 cells

(c) 8 cells

(d) 16 cells

 

91. In a Karnaugh map for an expression having ‘don’t care terms’ the don’t cares can be treated as :

 (a) 0

(b) 1

(c) 1 or 0

(d) none of the above

 

93. The Boolean expression A B + A B C +(A+B+C) simplifies to :

 a. A B + B C

b. AB + BC

c. A B + B C

d. A B + B C

 

94. The radix for binary system is :

 a. 0

b. 1

c. 2

d. 10

 

95. The radix for decimal system is :

 a. 0

b. 1

c. 10

d. Log, 10

 

96. The radix for octal system is :

 a. 1

b. Log, 6

c. 6

d. 8

 

97. Typical size of digital IC is about :

(a) 1 "x 1"

(b) 2 " x 2"

(c) 0.1 "X 0.1"

(d) 0.001 "x 6.001"

 

98. A digital clock uses 4 chip :

 (a) SSI

(b) LSI

(C) VLSI

(d) MSI

 

99. Digital tectionologies being used now-a-days are :

 (a) DTL and EMOS

(b) TTL, ECL, CMOS and RTL

(c) TTL, ECL and CMOS

(d) TTL, ECL. CMOS and DTL

 

100. A TTL circuit with totem pole output has :

 (a) high output impedance

(b) low output impedance

(c) very high output impedance

(d) any of above

 

101. TTL uses:

 (a) multi emitter transistors

(b) multi collector transistors

(c) multi base transistors

(d) multi emitter or multi collector transistors


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

Search Aptipedia