Algorithms Design And Analysis MCQS with Answers Set 9

Algorithms Design And Analysis MCQS with Answers

Algorithms Design And Analysis MCQS with Answers is mainly intended fro GATE aspirants.These questions can also came in Btech Computer science university exams and various interview for computer science students
(131) there are 5 items as follows
Items
wi
vi
Item1
5 pounds
30$
Item2
10 pounds
20$
Item3
20 pounds
100$
Item4
30 pounds
90$
Item5
40 pounds
160$
The knapsack can hold 60 pounds find the optimal solution
(A)   250$                (B) 260 $         (C) 270 $                      (D) 290$
(132) there are 5 items as follows
Items
wi
vi
Item1
5 pounds
30$
Item2
10 pounds
20$
Item3
20 pounds
100$
Item4
30 pounds
90$
Item5
40 pounds
160$
The knapsack can hold 60 pounds find the solution by greedy technique
(A)   230$                (B) 260 $         (C) 220 $                      (D) 250$
(133) what is an optimal Huffman code for alphabeta of the following set of frequencies a: 05, b:48, c:07, d:17, e:10, f:13
(A) 1010                      (B)0101                       (C) 1001                      (D) 1100
(134) the total running time of Huffman on the set of n characters is
(A) O(n)                       (B) O(n log n)              (C) O(n2)                      (D) O(log n)
(135) the total running time of matrix chain multiplication of n matrices
(A) ϴ (n4)         (B) ϴ (n3)         (C) ϴ (n2)         (D) ϴ (n)
(136) which of the following is true
(A) P is subset of NP                            (B) NP is subset of P
(C) P and NP are equal                       (D) NP is subset of NP hard
(137) the total running time of optimal binary search tree of n nodes
(A) O(n2)                      (B) O(n)                       (C) O(n3)                      (D) O(n log n)
(138) If every square of the board is visited, then the total number of knight moves of n-queen problem is
(A) n3-1            (B) n-1                         (C)n2-1                         (D) log n-1
(139) If every square of the board is visited, then the total number of knight moves of 4-queen problem is
(A) 14              (B) 15                          (C) 16                          (D) 12
(140) If every square of the board is visited, then the total number of knight moves of 8-queen problem is
(A) 64              (B) 62                          (C) 61                          (D) 63
(141) In which of the following cases n-queen problem does not exist
(A) n=2 and n=4          (B) n=4 and n=6          (C) n=2 and n=3          (D) n=4 and n=8
(142) the total running time of knapsack problem for a simple approach
(A) O(n)                       (B) O( log n)                (C) O(2n log n)                         (D) O(2n)
(143) what is an optimal Huffman code for alphabeta of the following set of frequencies a: 01, b:01, c:02, d:03, e:05, f:8, g:13, h:21
(A) 001010                  (B) 001111                  (C) 111100                  (D) 101010
(144)  what is an optimal Huffman code for alphabet b of the following set of frequencies a: 45, b:13, c:12, d:16, e:9, f:5
(A) 100                        (B) 111                        (C) 001                        (D) 101
(145) what is an optimal Huffman code for alphabete of the following set of frequencies a: 29, b:25, c:20, d:12, e:05, f:09
(A) 100 0                      (B) 1110                                  (C) 0010                                  (D) 1011
(146) Which of the following method is taking overcharge for some operations in amortized analysis?
(A) Aggregate method                        (B) accounting method          
(C) potential method              (D) both (A) and (C)
(147) Which of the following method is most flexible in amortized analysis?
(A) Aggregate method                        (B) accounting method          
(C) potential method              (D) both (A) and (B)
(148) Which of the following method is taken different operations different charges in amortized analysis?
 (A) Aggregate method                       (B) accounting method          
(C) potential method                          (D) both (A) and (B)
(149) Which of the following method is computing total cost of an algorithm in amortized analysis?
(A) Aggregate method                        (B) accounting method          
(C) potential method              (D) both (C) and (B)
(150) which of the following method is credit as the potential energy to pay for future operations?
(A) Aggregate method                        (B) accounting method          
(C) potential method              (D) both (A) and (B)
(151) If all c(i, j )’s and r(i, j)’s are calculated, then OBST algorithm in worst case takes one of the following time.
(a)  O(n log n)         
(b)  O(n3)                
(c)  O(n2)                 
(d)  O(log n)            
(e)  O(n4).
(152) The following is a weighted binary tree, then what is the weighted array for the TVS problem?

(a)  [9, 2, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 4]  
(b)  [9, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 4, 6]
(c)  [9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 6, 7, 4]  
(d)  [9, 2, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 6, 4]
(e)  [9, 2, 0, 0, 0, 7, 0, 0, 0, 0, 6, 4, 0, 0]

(153) The upper bound on the time complexity of the nondeterministic sorting algorithm is
(a)  O(n)                 
(b)  O(n log n)         
(c)  O(1)                 
(d)  O( log n)          

(154) The worst case time complexity of the nondeterministic dynamic knapsack algorithm is
(a)  O(n log n)                                      
(b)  O( log n)          
(c)  O(n2)                
(d)  O(n)                 

(155) The time complexity of the normal quick sort, randomized quick sort algorithms in the worst case is
(a)  O(n2), O(n log n)                  (b)  O(n2), O(n2)
(c)  O(n log n), O(n2)                  (d)  O(n log n), O(n log n)

(156) Let there be an array of length ‘N’, and the selection sort algorithm is used to sort it, how many times a swap function is called to complete the execution?
(a)  N log N times                                  (b)  log N times
(c)  N2 times                                       (d)  N-1 times       

(157) The Sorting method which is used for external sort is
(a)  Bubble sort                 (b)  Quick sort                       (c)  Merge sort        (d)  Radix sort      


(158) In analysis of algorithm, approximate relationship between the size of the job and the amount of work required to do is expressed by using _________
(a)   Central tendency                                                      
(b) Differential equation
(c)   Order of execution                          (d) Order of magnitude

(159) P, Q and R are pointer variables. The statements below are intended to swap the contents of the nodes pointed to by P and Q. rewrite it so that it will work as intended.
P = Q;    R = Q;   Q = R;
(a)   R=Q;  P=R;   Q=R;                          (b)   R=P;   P=P;   Q=Q;
(c)   P=P;   P=Q;   R=Q;                         (d)   R=P;   P=Q;   Q=R;

(160) Consider the usual algorithm for determining whether a sequence of parentheses is balanced. What is the maximum number of parentheses that will appear on the stack AT ANY ONE TIME when the algorithm analyzes: (()(())(()))
(a) 1                        (b) 2                        (c) 3                        (d) 4               
 (161) The Knapsack problem where the objective function is to minimize the profit is ______
(a)   Greedy                                          (b)  Dynamic 0 / 1       
(c)  Back tracking                                  (d)   Branch & Bound 0/1  


(162) Choose the correct answer for the following statements:
I.     The theory of NP–completeness provides a method of obtaining a polynomial time for NPalgorithms.
II.     All NP-complete problem are NP-Hard.

(a)   I is FALSE and II is TRUE
(b)   I is TRUE and II is FALSE
(c)   Both are TRUE
(d)   Both are FALSE

(163) For 0/1 KNAPSACK problem, the algorithm takes ________ amount of time for memory table, and ______time to determine the optimal load, for N objects and W as the capacity of KNAPSACK.
(a)   O(N+W), O(NW)      (b)  O(NW), O(N+W)
(c)   O(N), O(NW)           (d)  O(NW), O(N)                           

(164) What is the type of the algorithm used in solving the 8 Queens problem?
(a)Greedy
(b)Dynamic
(c)Branch and Bound
(d)Backtracking.

(165) Sorting is not possible by using which of the following methods?
(a)Insertion
(b)Selection
(c)Deletion
(d)Exchange

Algorithms Design And Analysis MCQS with Answers

130 B
131 B
132 C
133 A
134 B
135 B
136 A
137 C
138 C
139 B
140 D
141 C
142 D
143 C
144 D
145 B
146 B
147 C
148 B
149 A
150 C
151 B
152 D
153 A
154 D
155 B
156 D
157 C
158 D
159 D
160 C
161 D
162 A
163 B
164 D
165 C


This entry was posted on Friday, 5 September 2014 and is filed under . You can follow any responses to this entry through the RSS 2.0. You can leave a response.

2 Responses to “Algorithms Design And Analysis MCQS with Answers Set 9”