Design and Analysis of Algorithms MCQ Set-2

45. 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

46. 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

47. The worst-case time complexity of Quick Sort is________.

A. O(n2)

B. O(log n)

C. O(n)

D. O(n logn)

47. The worst-case time complexity of Bubble Sort is________.

A. O(n2)

B. O(log n)

C. O(n)

D. O(n logn)

48. The worst-case time complexity of Selection Exchange Sort is________.

A. O(n2)

B. O(log n)

C. O(n)

D. O(n logn)

49. The worst-case time complexity of Merge Sort is________.

A. O(n2)

B. O(log n)

C. O(n)

D. O(n logn)

50. 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

51. Which of the following sorting procedures is the slowest?

A. Quick sort

B. Heap sort

C. Shell sort

D. Bubble sort

52. 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

53. 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

54. 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

55. 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

A. O (n log n)

B. O (n2 log n)

C. O (n2 + log n)

D. O (n2)

56. Which of the following case does not exist in complexity theory?

A. Best case

B. Worst case

C. Average case

D. Null case

57. 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

58. The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is

A. T(n) = 2T(n - 2) + 2

B. T(n) = 2T(n - 1) + n

C. T(n) = 2T(n/2) + 1

D. T(n) = 2T(n - 1) + 1

59. 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

60. 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

A. Insertion sort

B. Selection sort

C. Either of a and b

D. None of the above

61. The running time of insertion sort is

A. O(n^2)

B. O(n)

C. O(log n)

D. O(n log n)

62. A sort which compares adjacent elements in a list and switches where necessary is ____.

A. insertion sort

B. heap sort

C. quick sort

D. bubble sort

63. The correct order of the efficiency of the following sorting algorithms according to their overall running time comparison is

A. Insertion>selection>bubble

B. Insertion>bubble>selection

C. Selection>bubble>insertion.

D. bubble>selection>insertion

64. 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

65. The number of swapping’s needed to sort the numbers 8, 22, 7, 9, 31, 19, 5, 13 in ascending order, using bubble sort is

A. 10

B. 9

C. 13

D. 14

66. 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

67. 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

68. 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

69. 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

70. The total number of comparisons made in quick sort for sorting a file of size n, is

A. O(n log n)

B. O(n2)

C. n(log n)

D. None of the above

71. Quick sort efficiency can be improved by adopting

A. non-recursive method

B. insertion method

C. tree search method

D. None of the above

72. For the improvement of efficiency of quick sort the pivot can be

A. the first element

B. the mean element

C. the last element

D. None of the above

73. 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

74. Straight selection sort is basically a method of repeated

A. interchange

B. searching

C. position adjustment

D. None of the above

75. Number of selections required to sort a file of size N by straight selection requires

A. N - 1

B. log N

C. O(N2)

D. None of the above

76. For sorting a file of size n by straight selection sort, the number of comparisons made in the first pass is

A. n

B. n - 1

C. n(n - 1)/2

D. None of the above

77. Heap is defined to be a

A. complete binary tree

B. binary tree

C. tree structure

D. None of the above

78. In a Max heap the largest key is at

A. the root

B. a leaf

C. a node

D. None of the above

79. In heap sort the input is arranged in the form of a

A. heap

B. tree

C. queue

D. None of the above

80. Heap sort is found to be very efficient

A. with regard to storage requirement

B. in time consumption

C. regarding overheads involved

D. None of the above

81. 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

82. 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 )

83. The most important reason for including a destructor in a class is:

A. To print a message for debugging purposes

B. To store information about an object before it goes out of scope

C. To free up resources allocated by that class

D. To reset the original object’s pointer to NULL

E. To make your TA happy

84. One of these code fragments calls the copy constructor for class A. Which one? (Assume that doSomething is a void function with a parameter of the appropriate type.)

A. A a;

B b;

a = b;

B. A array[20];

C. A a;

doSomething(a);

D. A* a;

doSomething(a)

E. A a;

doSomething(&a);

85. What is the asymptotic runtime for traversing all nodes in a binary search tree with n nodes and printing them in order?

A. O(n ⋅ log(n))

B. O(n)

C. O( n)

D. O(log(n))

E. O(n^2 )

86. Consider a class List that implements an unordered list. Suppose it has as its representation a dynamically expanding (resizable) array. Which of these operations might need to delete some dynamically allocated storage to avoid a memory leak?

I. Default Constructor

II. Copy Constructor

III. Destructor

IV. Assignment operator

A. I and II

B. II and III

C. II and IV

D. III and IV

E. II, III, and IV

87. What is the postfix representation of this expression?

(12 – a) * (b + 9) / (d * 4)

A. 4 b * d 9 + a 12 - * /

B. / 12 a – b 9 + d 4 *

C. 12 – a * b + 9 / d * 4

D. 12 a – b 9 + * d 4 * /

E. None of the above

88. Assuming that the hash function for a table works well, and the size of the hash table is reasonably large compared to the number of items in the table, the expected (average) time needed to find an item in a hash table containing n items is