computer science mcqs

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	w_i	v_i
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	w_i	v_i
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(n²) (D) O(log n)

(135) the total running time of matrix chain multiplication of n matrices

(A) ϴ (n⁴) (B) ϴ (n³) (C) ϴ (n²) (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(n²) (B) O(n) (C) O(n³) (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) n³-1 (B) n-1 (C)n²-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(2ⁿ log n) (D) O(2ⁿ)

(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(n³)
(c) O(n²)
(d) O(log n)
(e) O(n⁴).

(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(n²)
(d) O(n)

(155) The time complexity of the normal quick sort, randomized quick sort algorithms in the worst case is

(a) O(n²), O(n log n) (b) O(n²), O(n²)

(c) O(n log n), O(n²) (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

Algorithms Design And Analysis MCQS with Answers Set 8

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

(111) If each node in a tree has value greater than every value in its left sub tree and value less than every value in its right sub tree, the tree is known as

(A) complete tree (B) full binary tree

(C) binary search tree (D) threaded tree

(112) Which of the following sorting procedure is the slowest?

(A) Quick sort (B) Heap sort (C) Shell sort (D) Bubble sort

(113) which of the following shows the correct relationship among some of the more common computing times on algorithms

(A) O(log n) < O(n) < O( n* log n) < O(2ⁿ) < O(n²)

(B) O(n) < O(log n) < O( n* log n) < O(2ⁿ) < O(n²)

(C) O(n) < O(log n) < O( n* log n) < O(n²) < O(2ⁿ)

(D) O(log n) < O(n) < O( n* log n) < O(n²) < O(2ⁿ)

(114) The average time required to perform a successful sequential search for an element in an array A(1..n) is given by

(A) (n+1)/2 (B) n(n+1)/2 (C) log n (D) n²

(115) the time complexity of linear search algorithm over an array of n elements is

(A) O(log n) (B) O(n) (C) O( n log n) (D) O(n²)

(116) the time taken by binary search algorithm to search a key in a sorted array of n elements is

(A) O(log n) (B) O(n) (C) O( n log n) (D) O(n²)

(117) the time required to search an element in a linked list of length n is

(A) O(log n) (B) O(n) (C) O( 1) (D) O(n²)

(118) the worst case time required to search a given element in sorted linked list of length n is

(A) O(1) (B) O( log n) (C) O(n) (D) O(n log n)

(119) consider a linked list of n elements which is pointed by an external pointer. What is the time taken to delete the element which is successor of the element pointed to by a given pointer?

(A) O(1) (B) O( log n) (C) O(n) (D) O(n log n)

(120) consider a linked list of n elements. What is the time taken to insert an element an after element pointed by some pointer?

(A) O(1) (B) O( log n) (C) O(n) (D) O(n log n)

(121) which of the following operations is performed more efficiently by doubly linked list than by linear linked list?

(A) Deleting a node whose location is given

(B) searching an unsorted list for a given item

(C) inserting a node after the node with a given location

(D) Traversing the list to process each node

(122) the five items: A,B,C,D and E are pushed in a stack, one after the other starting from A. The stack is popped four items and each element is inserted in a queue. Then two elements are deleted from the queue and pushed back on the stack. Now on item is popped from the stack. The popped item is

(A) A (B) B (C) C (D) D

(123) the time required to search an element in a binary search tree having n elements is

(A) O(1) (B) O( log n) (C) O(n) (D) O(n log n)

(124) for a linear search in an array of n elements the time complexity for best, worst and average case are …., and …respectively.

(A) O(n) , O(1) and O(n/2) (B) O(1) , O(n) and O(n/2)

(C) ) O(1) , O(n) and O(n) (D) ) O(1) , O(n) and O((n-1)/2)

(125) the number of comparisons required by binary search of 100000 elements is

(A) 15 (B) 20 (C) 25 (D) 30

(126) Find an optimal parenthesization of a matrix chain product whose sequence of dimension s is <5,4,6,2,7>

(A) 156 (B) 154 (C) 158 (D) 157

(127) Find an optimal parenthesization of a matrix chain product whose sequence of dimension s is <5,10,3,12, 5, 50, 6>

(A) 2010 (B) 2020 (C) 2015 (D) 2030

(128) Find an optimal parenthesization of a matrix chain product whose sequence of dimension s is <4,10,3,12,20,7>

(A) 1334 (B) 1324 (C)1344 (D)1354

(129) Find an optimal parenthesization of a matrix chain product whose sequence of dimension s is <5,4,3> (for three matrices)

(A) 125 (B) 130 (C) 135 (D) 140

(130) Find an optimal parenthesization of a matrix chain product whose sequence of dimension s is <30,35,15,5,10,20,25> (for six matrices)

(A)7130 (B) 7125 (C) 7145 (D) 7135

Algorithms Design And Analysis MCQS with Answers

111	C
112	D
113	D
114	A
115	B
116	A
117	B
118	C
119	A
120	A
121	A
122	D
123	B
124	C
125	B

126	C
127	A
128	C
129	C
130	B

Algorithms Design And Analysis MCQS with Answers Set 7

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

(91) The running time of Dijkastra’s algorithm is
(A) O(V²)          (B) O(V+E)       (C) O(n log n)              (D) all of the above
(92) kruskal’s algorithm uses-------- and prim’s algorithm uses------ in determining the MST
(A) edges,vertex          (B)vertex,edges           (C)edges,edges           (D)vertex,vertex
(93) The running time of kruskal’s algorithm for MST
(A) O(E)           (B) O(V)           (C) O(E log V)              (D) all of the above
(94) We can perform a topological sort in time -----------, since DFS takes ------ time.
(A) ϴ (V+E), ϴ (E)        (B) ϴ (E), ϴ (V+E)
(C) ϴ (V+E), ϴ (V+E)   (D) all of the above
(95) The running time of BFS is------------
(A) ϴ (1)         (B) ϴ (n log n)             (C) O(V+E)       (D) ϴ (n²)
(96) For------ insertion sort beats merge sort
(A) n≥43          (B) n≤23          (C) n≤43          (D) cannot say

(97) Best case running time of quick sort is

(A) O(n) (B) O(logn) (C) O(nlogn ) (D) O(n²)

(98) A characteristic of the data that binary search tree but the linear search ignores, is the

(A) Order of the list (B) length of the list

(C) maximum value in the list (D) mean of data values

(99) A sort which compares adjacent elements in a list and switches where necessary is a

(A) insertion sort (B) heap sort

(C) quick sort (D) bubble sort

(100) 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

(101) A sort which uses the binary tree concept such that any number is larger than all the numbers is the subtree below it is called

(A) Selection sort (B) insertion sort (C) quick sort (D) heap sort

(102) which of the sorting algorithm does not have a worst case running time of O(n²)

(A) Selection sort (B) insertion sort (C) merge sort (D) quick sort

(103) which of the following sorting method is stable?

(A) Straight insertion sort (B) binary search tree

(C) Shell sort (D) Heap sort

(104) A complete binary tree with the property that the value at each node is at least as large as the values at its children is known as

(A) Binary search tree (B) AVL tree

(C) Completely balanced tree (D) Heap

(105) The recurrence relation T(n) = mT(n/2)+ an² is satisfied by

(A) T (n) = O(n^m) (B) T(n) = O(n log m) (C) T(n) = O( n log n) (D) T(n) =O(m log n)

(106)The time required to find shortest path in a graph with n vertices and e edges is

(A) O (e) (B) O (n) (C) O (e²) (D) O (n²)

(107)The goal of hashing is to produce a search tree that takes

(A) O(1) time (B) O(n²) time (C) O (log n) time (D) O (n log n) time

(108) which of the following best described sorting?

(A) Accessing and processing each record exactly once

(B) Finding the location of the record with a given key

(C) Arranging the data in some given order

(D) Adding a new record to the data structure

(109) The worst case complexity of straight insertion sort algorithm to sort n elements is

(A) O(n) (B) O(n log n) (C) O(n^1.2) (D) O(n²)

(110) The worst case complexity of binary insertion sort algorithm to sort in n elements is

(A) O(n) (B) O(n log n) (C) O(n^1.2) (D) O(n²)

Algorithms Design And Analysis MCQS with Answers

91	A
92	A
93	C
94	C
95	C
96	C
97	C
98	A
99	D
100	B

101	C
102	C
103	A
104	D
105
106	D
107	A
108	C
109	D
110	D

Algorithms Design And Analysis MCQS with Answers Set 6

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.

(76) Struct x

{

int i;

char c;

}

union y{

struct x a;

double d;

};

printf("%d",sizeof(union y));

(A)8 (B)5 (C)4 (D)1

(77) Worst case complexity of the insertion sort algorithm is
(A) O(n²)          (B) O(n)           (C) O(n-1)        (D) O(n+1)
(78) Average case complexity of the insertion sort algorithm is
(A) O(n²)          (B) O(n)           (C) O(n-1)        (D) O(n+1)
(79) Best case complexity of the insertion sort algorithm is
(A) O(n²)          (B) O(n)           (C) O(n-1)        (D) O(n+1)

(80) Worst case complexity of the bubble sort algorithm is
(A) O(n³)          (B) O(n⁴)          (C) O(n²)          (D) O(n)

(81) Best case complexity of the bubble sort algorithm is
(A) O(n³)          (B) O(n⁴)          (C) O(n²)          (D) O(n)
(82) Average case complexity of the bubble sort algorithm is
(A) O(n³)          (B) O(n⁴)          (C) O(n²)          (D) O(n)
(83) Worst case complexity of the selection sort algorithm is
(A) O(n³)          (B) O(n⁴)          (C) O(n²)          (D) O(n)
(84) Average case complexity of the selection sort algorithm is
(A) O(n³)          (B) O(n⁴)          (C) O(n²)          (D) O(n)
(85) Best case complexity of the selection sort algorithm is
(A) O(n³)          (B) O(n⁴)          (C) O(n²)          (D) O(n)
(86) If a complete binary tree T_n has n=1000 nodes then its height is
(A) 21              (B) 10              (C) 11              (D) 12
(87) If a complete binary tree T_nhas n=1000000 nodes then its height is
(A) 21              (B) 20              (C) 23              (D) 22
(88) The running time of Strassen’s algorithm for matrix multiplication is
(A) ϴ (n)          (B) ϴ (n³)         (C) ϴ (n²)         (D) ϴ (n^2.81)
(89) The running time of Floyd-Warshall algorithm is
(A) ϴ (n)          (B) ϴ (n³)         (C) ϴ (n²)         (D) ϴ (n log n)
(90) Dijkastra’s algorithm bears some similarity to
(A) BFS             (B) prim’s algorithm               (C) DFS            (D) Both (A) & (C)

Algorithms Design And Analysis MCQS with Answers

76	A
77	A
78	A
79	C
80	C
81	C
82	C
83	C
84	C
85	C
86	C
87	A
88	D
89	C
90	D