Made Easy Online Test Series 1 5t535v

2/13/2017

MADE EASY ONLINE TEST SERIES

 

  CBT 2017

Ankit Kumar Yadav  (Enroll )

Log Out

 

HOME

  SCORE CARD

TIME MANAGEMENT

QUESTIONS REPORT

SOLUTION

COMPARE YOUR SELF

 

MY TEST MY PROFILE

Solution Report For Algorithms Represent whole test solution with correct and incorrect answers.

REPORTS   View Your Test Analysis

BUY PACKAGE NEWS Ask an Expert

Q. No Q.1

Question Status What is the worst case time complexity to sort on array A [0 to n] where the elements at index A [2i] (at even array index) is in its correct position ? a. Ο(n2 ) b. 

 Ο(n log n)

c. Ο(n) d. None of these

Not Attempt

Q.2

Correct Ans.

b

Video Solution

FAQ?

Have any doubt?

Solution

What  is  the  worst  case  time  complexity  to  sort  ‘n’  elements  by  first  constructing  a  Binary  Search  Tree  on  those  ‘n’ elements followed by an in order traversal on the tree ? a. 

 Ο(n2 )

b. Ο(n log n) c. Ο(n2  log n) d. Ο(n)

Not Attempt

Q.3

Correct Ans.

a

Video Solution

FAQ?

Have any doubt?

Solution

What is the worst case time complexity to construct an AVL tree from an array which satisfies the min heap property ? a. 

 Ο(n log n)

b. Ο(n2 ) c. Ο(n2  log n) d. Ο(n)

Not Attempt

Q.4

Correct Ans.

a

Video Solution

FAQ?

Have any doubt?

Solution

Which of the following procedure results same output as Dijkstra’s algorithm on unweighted graph with ‘n’ vertices ? a. 

Breadth first search

b. Depth first search c. Kruskal algorithm d. Prim’s algorithm

Not Attempt

Q.5

Correct Ans.

a

Video Solution

FAQ?

Have any doubt?

Solution

Consider the following function.

What is the worst case running time of the function f for any positive value of n ? a. Ο(1) b. Ο(n) c. 

 Ο(n2 )

d. Ο(n3 ) https://onlinetestseriesmadeeasy.in/madeeasy/index.php?pageName=timeManagementReport&testid=1221&t=cont­1&testType=2

1/6

2/13/2017

MADE EASY ONLINE TEST SERIES

Not Attempt

Q.6

Correct Ans.

c

Video Solution

FAQ?

Have any doubt?

Solution

Have any doubt?

Solution

What is the time complexity of Huffman coding using heap tree data structure ? a. Ο(n) b. Ο(log n) c. 

 Ο(n log n)

d. Ο(n2 )

Not Attempt

Q.7

Correct Ans.

c

Video Solution

FAQ?

Consider the following knapsack problem with capacity W = 8

Which of the following item is not selected in the optimal solution of 0/1 Knapsack problem ? a. I1  only b. 

 I2  only

c. I3  only d. None of these

Not Attempt

Q.8

Correct Ans.

b

FAQ?

Have any doubt?

Solution

What  is  worst  case  time  complexity  to  find  all  the  nodes  at  height  “v  /2”  from  a  particular  node  in  a  graph  having  ‘v  ’ vertices and ‘e’ edges ? a. Ο(v2 ) b. Ο(v log e) c. 

 Ο(v + e)

d. Ο(v2  log e)

Not Attempt

Q.9

Correct Ans.

c

Video Solution

FAQ?

Have any doubt?

Solution

Which of the following is true? a. If a topological sort exists for the vertices in a directed graph, then DFS on the graph will produce no back edges. b. Traversing DFS algorithm on a directed graph G. If we removed all back edges from graph G, then resulting graph is acyclic graph. c. 

Both (a) and (b)

d. None of these

Not Attempt

Q.10

Correct Ans.

c

Video Solution

FAQ?

Have any doubt?

Solution

Which of the following is true ? a. The running time of Radix Sort is effectively independent of whether the input is already sorted. b. Changing the RELAX function to update is d[v] ≥ d[u] + w (u, v) (instead of strictly greater than) will produce shortest path, but will not effect the correctness of Bellman­Ford algorithms outputs. c. 

 Both (a) and (b)

d. None of these

Not Attempt

Q.11

Correct Ans.

c

Video Solution

FAQ?

Have any doubt?

Solution

The  maximum  number  of  nodes  in  Binary  Search  Tree  of  height  ‘h’  which  have  same  inorder  and  preorder  will  be __________ (assume h = 10 and root is at height 0)

Not Attempt

Q.12

Correct Ans.

11

Video Solution

FAQ?

Have any doubt?

Solution

Consider the following sorting algorithm            Sorting (A, low, high)

https://onlinetestseriesmadeeasy.in/madeeasy/index.php?pageName=timeManagementReport&testid=1221&t=cont­1&testType=2

2/6

2/13/2017

MADE EASY ONLINE TEST SERIES

The running time of sorting (A, 1, n) function is θ (nx ). The value of x + 3 is __________ [Use value of x upto 1 decimal places]

Not Attempt

Q.13

Correct Ans.

5.7

FAQ?

Have any doubt?

Solution

FAQ?

Have any doubt?

Solution

Consider the following graph G.

The total number of minimum spanning trees from graph G are ______.

Not Attempt

Q.14

Correct Ans.

3

Consider the following table

The number of bits that are needed to encode a string containing 14 a’s, 3 b’s, 6 c’s and 10 d’s using the huffman coding are ___________.

Not Attempt

Q.15

Correct Ans.

61

FAQ?

Have any doubt?

Solution

Assume  there  is  an  algorithm  which  take  Ο(log2   log2   n)  time  to  sort  n  elements  algorithm,  person  one  will  takes  22 seconds to execute on some data of size Y.  Person  to  will  take  33  seconds  for  data  size  of  256.  The  data  size  of  Y  is __________ .

Not Attempt

Q.16

Correct Ans.

16

Video Solution

FAQ?

Have any doubt?

Solution

Consider the weighted undirected graph below

Assume that edge ‘BF’  is  added  to  the  minimum  spanning  tree.  The  maximum  value  of  ‘BF’  so  that  this  new  edge  can belong to the minimum spanning tree is _________.

Not Attempt

Q.17

Correct Ans.

12

Video Solution

FAQ?

Have any doubt?

Solution

Consider we have an algorithm which generate preorder of any tree in Ο(n2 ) time, we have to create a Binary Search Tree with n distinct element. Which of the following will represents the worst case time complexity ? a. Ο(n) b. Ο(n log n) c. 

 Ο(n2 )

https://onlinetestseriesmadeeasy.in/madeeasy/index.php?pageName=timeManagementReport&testid=1221&t=cont­1&testType=2

3/6

2/13/2017

MADE EASY ONLINE TEST SERIES

d. Ο(1)

Not Attempt

Q.18

Correct Ans.

c

Video Solution

FAQ?

Have any doubt?

Solution

FAQ?

Have any doubt?

Solution

Let f(n) = Ο(n), g(n) = Ω(n) and h(n) = θ(n). Then g(n) + f(n).h(n) is ______ a. 

 Ω(n)

b. θ(n2 ) c. Ω(n2 ) d. θ(n)

Not Attempt

Q.19

Correct Ans.

a

Video Solution

Consider the graph given below:

Suppose you are running Dijkstra’s algorithm starting from source vertex ‘D’. What will be the order of vertices which will be relaxed using Dijkastra’s algorithm? a. 

DFBHEGCA

b. DFBHGECA c. DFBHEGAC d. DFBEHGCA

Not Attempt

Q.20

Correct Ans.

a

FAQ?

Have any doubt?

Solution

Consider the following adjacency matrix

Which of the following is transitive closure of the directed graph defined by the above adjacency matrix?

a. 

b. 

c. 

 

d. 

Not Attempt

Q.21

Correct Ans.

c

FAQ?

Have any doubt?

Solution

Match List­I (Dynamic algorithm) with List­II (Average case running time) and select the correct answer using the codes given below the lists: List­I (Dynamic algorithm)

List­II (Average case running time)

A. Matrix chain multiplication

1. Ο(mn)

B. Travelling salesman problem 2. Ο(n3 ) C. 0/1 knapsack

3. Ο(nn)

D. Fibonacci series

4. Ο(n)

Codes:   (a) (b)

A 1 1

B 3 3

C 2 3

D 4 2

https://onlinetestseriesmadeeasy.in/madeeasy/index.php?pageName=timeManagementReport&testid=1221&t=cont­1&testType=2

4/6

2/13/2017

MADE EASY ONLINE TEST SERIES

(c) (d)

2 2

3 3

3 1

2 4

a. a b. b c. c d. 

d

Not Attempt

Q.22

Correct Ans.

d

Video Solution

FAQ?

Have any doubt?

Solution

Consider two vertices ‘a’ and ‘b’ that are simultaneously on the FIFO queue at same point during the execution of breadth first search from ‘s’ in an undirected graph. Consider the following statements:   S1 : The number of edges on the shortest path between ‘s’ and ‘a’ is atmost one more than the number of      edges on the shortest path between ‘s’ and ‘b’. S2 : The number of edges on the shortest path between ‘s’ and ‘a’ is atleast one less than the number of        edges on the shortest path between ‘s’ and ‘b’. S3 : There is a edge between ‘a’ and ‘b’.   Which of the following is true? a. S1  and S3  only b. S1  and S2  only c. 

 S1  only

d. S1 , S2  and S3

Not Attempt

Q.23

Correct Ans.

c

Video Solution

FAQ?

Have any doubt?

Solution

Let G(V, E) be an undirected graph with positive edge weights. What is the worst case time complexity to find minimum spanning tree using Kruskal algorithm is implemented using array data structure ? a. Ο(|E | + |V |log|V |) b. 

 Ο(|V | log |V |)

c. Ο(|V |2 ) d. Ο(|V | log2  |V |)

Not Attempt

Q.24

Correct Ans.

b

Video Solution

FAQ?

Have any doubt?

Solution

Have any doubt?

Solution

A certain problem is having an algorithm with the following recurrence relation.

How much time would the algorithm take to solve the problem? a.  b.  c. 

 

d. 

Not Attempt

Q.25

Correct Ans.

c

FAQ?

Consider the following statements I.   Let T be a minimum spanning tree of a graph G. Then for any two vertices u and v the path from u to      v in T is the shortest path from u to v in the graph G. II.  Suppose that average edge weight for a graph G is Aavg. Then the minimum spanning tree of G will       have weight at most (n – 1) Aavg, where n is number of vertices in graph G. Which of the above statements are true? a. Only I b. Only II c. Both I and II d. 

None of these

Not Attempt

Q.26

Correct Ans.

d

FAQ?

Have any doubt?

Solution

Let A is a Max­Heap with heap size ‘log n’. A function MHY (A, i, key) that replaces A[i] with a given value ‘key’ and it will adjust so that result become Max Heap. What is the worst case time complexity to perform MHY (A, i, key)? a. 

 Θ(log log n)

b. Θ(n) c. Θ(1) d. Θ(n log n)

https://onlinetestseriesmadeeasy.in/madeeasy/index.php?pageName=timeManagementReport&testid=1221&t=cont­1&testType=2

5/6

2/13/2017

MADE EASY ONLINE TEST SERIES

Not Attempt

Q.27

Correct Ans.

a

Video Solution

FAQ?

Have any doubt?

Solution

Consider the following statements : S1  : Given a minheap of height logn, it will take Ο(logn) time to delete the root element of the heap. S2  : Time complexity of fractional Knapsack using greedy algorithm is Ο(n2 ). S3  : Selection sort works on greedy approach. Which of the following option is correct a. S1  and S2  are correct b. 

 S1  and S3  are correct

c. Only S1  is correct d. Only S3  is correct

Not Attempt

Q.28

Correct Ans.

b

Video Solution

FAQ?

Have any doubt?

Solution

Consider  a  procedure  find  (  )  which  take  array  of  n  integers  as  input  and  produce  pair  of  elements  of  array  whose difference is not greater than the difference of any other pair of element of that array. Which of the following represent worst case time complexity of find ( ) procedure ? a. Ο(n) b. 

 Ο(n log n)

c. Ο(n2 ) d. Ο(n2  log n)

Not Attempt

Q.29

Correct Ans.

b

Video Solution

FAQ?

Have any doubt?

Solution

Consider the hashing table with ‘m’ slots and ‘n’ keys. If the expected number of probes in unsuccessful search is 3. The expected number of probes in a successful search is _______ (upto 2 decimal place).

Not Attempt

Q.30

Correct Ans.

1.647 [1.64 ­ 2.00]

FAQ?

Have any doubt?

Solution

Assume that an upper triangular matrix A[0... 99, 0 ...99] is stored in a linear array C of size 5050 with row major order. If A[0, 0] is stored in C[0], find the index of C where A[70, 90] is stored in it.

Not Attempt

Q.31

Correct Ans.

4605

FAQ?

Have any doubt?

Solution

Consider the following statements with respect to quick sort. S1  :While performing sorting at any iteration only 1 element can be present at its correct position. S2  : At first iteration, none of the element changes its position, iff given input is already sorted. S3  : After ith iteration applied on the set of elements left after (i – 1) iterations, if any element is found to be         at its correct position, then that element must have been the pivot for the ith iteration. The number of statements that are true __________ .

Not Attempt

Q.32

Correct Ans.

0

Video Solution

FAQ?

Have any doubt?

Solution

The maximum number of orders in which we can insert element {1, 2, ....., 7} into an empty AVL binary tree so that no rotation need to be performed on it are __________ (Consider key of root node is ‘4’ always).

Not Attempt

Q.33

Correct Ans.

48

Video Solution

FAQ?

Have any doubt?

Solution

A  min  heap  having  1024  distinct  elements  with  keys  ranging  from  0  to  1023  is  stored  in  array  of  1024  indices.  The maximum  difference  between  the  keys  of  all  the  element  that  can  possibly  be  stored  at 

  index  of  the  array  is

__________ .

Not Attempt

Correct Ans.

1014

 

https://onlinetestseriesmadeeasy.in/madeeasy/index.php?pageName=timeManagementReport&testid=1221&t=cont­1&testType=2

Video Solution

FAQ?

Have any doubt?

Solution

 

6/6