BITS WILP Data Structures and Algorithms Design Quiz-3 2017-H1

Question 1

Consider the experiment of tossing a coin until 10 heads appear. Then expected
number of tosses is

Select one:

a. 2

b. 20

c. None of the above

d. 11

e. 10

Feedback

The correct answer is: 20

Question 2

Total number of comparisons needed for merge(L1,L2) where L1 is 2,4,6,8 and
L2 is 10, 12, 13,15, 17,19

Select one:

a. 6

b. 10

c. 9

d. None of the above

e. 4

Feedback

The correct answer is: 4

Question 3

Consider the problem of sorting a sequence in ascending order. If the input is
already in ascending order, which of the following sorting procedure is most
efficient.

Select one:

a. Merge Sort

b. Quick Sort

c. Heap  Sort

d. None of the above

e. Insertion Sort

Feedback

The correct answer is: Insertion Sort

Question 4

Suppose the input to Quick sort is 1,2,...17. What would be the best pivot
element during the first invocation?

Select one:

a. 9

b. 1

c. None of the above

d. 2

e. 17

Feedback

The correct answer is: 9

Question 5

Let G be a simple undirected graph with n vertices. Then number of edges in G
is

Select one:

a. at least n(n-1)/2

b. at least n

c. at most n

d. None of the above

e. at most n(n-1)/2

Feedback

The correct answer is: at most n(n-1)/2

Question 6

Let T be a tree with m edges. Then the number of vertices in T is

Select one:

a. None of the above

b. exactly m+1

c. exactly m

d. exactly m-1

e. at most m

Feedback

The correct answer is: exactly m+1

Question 7

Let A be an adjacency matrix of an undirected graph in G. Then sum of all
entries in the matrix is equal to

Select one:

a. Number of edges in G

b. Number of  vertices in G

c. Twice the number of edges in G

d. None of the above

e. Twice the number of vertices in G

Feedback

The correct answer is: Twice the number of edges in G

Question 8

Worst case running time for quick sort is

Select one:

a. O(nlogn)

b. O(n^2)

c. None of the above

d. O(n)

e. O(log n)

Feedback

The correct answer is: O(n^2)

Question 9

Suppose an undirected graph, which has n vertices and d maximum degree, is
represented using adjacency list. The running time to find the degree of a given
vertex is

Select one:

a. O(d)

b. O(1)

c. O(logn)

d. O(n)

e. None of the above

Feedback

The correct answer is: O(d)

Question 10

Consider the experiment of  tossing a coin until a head appears. The number of
elements in the sample space is

Select one:

a. None of the above

b. 0

c. 4

d. 2

e. 1

Feedback

The correct answer is: None of the above

Question 11

Suppose a directed graph is represented using adjacency list. The running time
to calculate indegree of a vertex is

Select one:

a. O(log n)

b. None of the above

c. O(m+n)

d. O(n)

e. O(d)

Feedback

The correct answer is: O(n)

Question 12

Which of the following statements is correct.
i) Any comparison based algorithm must perform Ω(nlogn) comparisons to sort n
elements in the worst case
ii. Any comparison based algorithm must perform Ω(nlogn) comparisons to sort n
elements in the best case

Select one:

a. Both of them is true

b. None of them is true

c. ii only true

d. i only true

e. None of the above

Feedback

The correct answer is: i only true

Question 13

The space complexity to represent a graph with n vertices and m edges using
adjacency matrix is

Select one:

a. None of the above

b. O(m+n)

c. O(n^2)

d. O(m)

e. O(n)

Feedback

The correct answer is: O(n^2)

Question 14

Average case running time for quick sort is

Select one:

a. O(n)

b. O(n^2)

c. None of the above

d. O(nlogn)

Feedback

The correct answer is: O(nlogn)

Question 15

Worst case running time for merge sort is

Select one:

a. O(n)

b. O(n2)

c. O(nlog logn)

d. O(nlog n)

e. None of the above

Feedback

The correct answer is: O(nlog n)

Question 16

Assume the keys are inserted in the following order. 1055, 1492, 1776, 1812,
1918, 1945.
1812 is stored in the slot ___________ if double hashing policy is used with
h_1(k) = 5*x mod 8 and h_2(x) = 1+ (k mod 7).

Select one:

a. 7

b. None of the above

c. 4

d. 3

e. 1

Feedback

The correct answer is: None of the above

Question 17

Suppose a simple uniform hashing function is used with chaining. The expected
number of key comparisons in successful search is at most __________

Select one:

a. α

b. 1+α

c. 1+α/2-α/2n

d. 1

e. None of the above

Feedback

The correct answer is: 1+α/2-α/2n

Question 18

Which of the following statements are true?
i. In linear probing method, there are only m different probe sequences are
possible.
ii. In quadratic probing method,  there are m^2 different probe sequences are
possible
iii. In double hashing, there are only m different probe sequences are possible.

Select one:

a. i only true

b. None of the above

c. All of them are false

d. All of them are true

e. i and ii are true and iii is false

Feedback

The correct answer is: All of them are true

Question 19

1812 is stored in the slot ___________ if double hashing policy is used with h_1(k) = 5*x mod

8 and h_2(x) = 1+ (k mod 7).

Select one:

a. 1

b. None of the above

c. 7

d. 4

e. 3

Feedback

The correct answer is: 3

Question 20

Let T be a tree with a maximum degree d. Then the number of leaf vertices is

Select one:

a. at most d

b. 1

c. None of the above

d. exactly d

e. at least d

Feedback

The correct answer is: at least d