Loading

SET 1


  Question 1

Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n(>= 2) numbers? In the recurrence equations given in the options below, c is a constant.

A : T(n) = 2T (n/2) + cn
B : T(n) = T(n 1) + T(1) + cn
C : T(n) = 2T (n 2) + cn
D : T(n) = T(n/2) + cn


  •  
    .

     Correct answer is :B

     Solution :
      When the pivot is the smallest (or largest) element at partitioning on a block of size n the result yields one empty sub-block, one element (pivot) in the correct place and sub block of size n-1 Hence recurrence relation
    T(n) = T(n-1)+T(1)+Cn

  •   Question 2

    Match the following



    A : P - iii, Q - ii, R - iv, S - i
    B : P - i, Q - ii, R - iv, S - iii
    C : P - ii, Q - iii, R - iv, S - i
    D : P - ii, Q - i, R - iii, S - i v


  •  
    .

     Correct answer is :C

     Solution :
      Prim?s algorithm always select minimum distance between two of its sets which is nothing but greedy method.
    Floyd-warshall always changes it distance at each iteration which is nothing but dynamic programming
    Merge sort In merge sort first we always divide and merge to perform sorting hence divide and conquer.
    Hamiltonian circuit Used to reach all the vertex once, if some vertex is repeating in its path it will backtrack.

  •   Question 3

    What are the worst-case complexities of insertion and deletion of a key in a binary search tree?

    A : ?(logn) for both insertion and deletion
    B : ?(n) for both insertion and deletion
    C : ?(n) for insertion and ?(logn) for deletion
    D : ?(logn) for insertion and ?(n) for deletion


  •  
    .

     Correct answer is :B

     Solution :
      Consider a single string of binary search tree, we have to trace all the nodes for insertion or deletion in worst case hence ?(n) for both.

  •   Question 4

    An algorithm performs (log N)1/2 find operations, N insert operations,(log N)1/2 delete operations, and (log N)1/2 decrease-key operations on a set of data items with keys drawn from a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted. For the decrease-key operation, a pointer is provided to the record that has its key decreased. Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best total asymptotic complexity considering all the operations?

    A : Unsorted array
    B : Min - heap
    C : Sorted array
    D : Sorted doubly linked list


  •  
    .

     Correct answer is :A

     Solution :
      decrease-key operations on a set of data items with keys drawn from a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted. For the decrease-key operation, a pointer is provided to the record that has its key decreased. Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best total asymptotic complexity considering all the operations?
    (log N)1/2 find operations wil

  •   Question 5

    Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For x V, let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is performed starting at s. Let T be the resultant BFS tree. If (u, v) is an edge of G that is not in T, then which one of the following CANNOT be the value of d(u) d(v)?



  •  
    .

     Correct answer is :


  •   Question 6

    The graph shown below 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: {(A, C), (B, C), (B, E), (E, F), (D, F)}. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all 8 edges of this graph is ______________.





  •  
    .

     Correct answer is :69

     Solution :
      Total sum=10+9+ 2+15+ 7 +16+ 4+ 6 = 69


  •   Question 7

    Let an represent the number of bit strings of length n containing two consecutive 1s. What is the recurrence relation for an?

    A : an2 + an1 + 2n2
    B : an2 + 2an1 + 2n2
    C : 2an2 + an1 + 2n2
    D : 2an2 + 2an1 + 2n2


  •  
    .

     Correct answer is :A


  •   Question 8

    An unordered list contain n distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is

    A : Θ(nlogn )
    B : Θ(n)
    C : Θ(log n)
    D : Θ(1)


  •  
    .

     Correct answer is :D

     Solution :
      Consider first three element of the list, atleast one of them will be neither minimum nor maximum
    Θ(1)

  •   Question 9

    In the context of abstract-syntax-tree (AST) and control-flow-graph (CFG), which one of the following is TRUE?

    A : In both AST and CFG, let node, N2 be the successor of node N1. In the input program, the code corres
    B : For any input program, neither AST nor CFG will contain a cycle
    C : The maximum number of successors of a node in an AST and a CFG depends on the input program
    D : Each node is AST and CFG corresponds to at most one statement in the input program


  •  
    .

     Correct answer is :C

     Solution :
      Optional (A) is not true when CFG contains cycle
    Option (B) is false as CFG can contain cycle
    Option (D) is false as a single node can contain block of statements.

  •   Question 10

    Given below are some algorithms, and some algorithm design paradigms.
    (1) Dijkstra?s Shortest Path (i) Divide and Conquer
    (2) Floyd-Warshall algorithm to compute
    all pair shortest path
    (ii) Dynamic Progamming
    Binary search on a sorted array (iii) Greedy design
    (4) Backtracking search on a graph (iv) Depth-first search
    (iv) Breadth-first search
    Match the above algorithms on the left to the corresponding design paradigm they follow.


    A : 1-i, 2 -iii, 3-i, 4 - v
    B : 1-iii, 2 -iii, 3-i, 4 - v
    C : 1-iii, 2 -ii, 3-i, 4 - iv
    D : 1-iii, 2 -ii, 3-i, 4 - v


  •  
    .

     Correct answer is :C

     Solution :
      Dijkstra shortest path algorithm find next node by choosing minimum distance hence greedy approach.
    Floyd warshall always apply dynamic programming, once it saves a cost and in the next iteration it will change if this is minimum hence dynamic.
    Binary search always divide on two parts .Hence divide and conquer.
    Backtracking uses by DFS, one it will reach to dead end it will take back track.

  •   Question 11

    Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?

    A : h (i)= i2 mod 10
    B : h (i)= i3 mod 10
    C : h (i)= (11 * i2) mod 10
    D : h (i)=(12 * i2) mod 10


  •  
    .

     Correct answer is :B

     Solution :
      If we take first 10 elements, number of collisions taken by the hash function given by option (B) is less when compared to others.

  •   Question 12

    Given a has table T with 25 slots that stores 2000 elements, the load factor  for T is ___________.



  •  
    .

     Correct answer is :80

     Solution :
      Load factor = no of elements / no of slots = 2000/25 = 80

  •   Question 13

    Let f(n)=n and g(n)=n (1 sin n) , where n is a positive integer. Which of the following statement is/are correct?
    I. f (n) = 0(g(n))
    II. f (n) = Ω g(n))


    A : Only I
    B : Only II
    C : Both I and II
    D : Neither I and II


  •  
    .

     Correct answer is :D

     Solution :
      As -1<=sinx<=1, neither of them is true

  •   Question 14

    Assume that a mergesort algorithm in the worst case takes 30 second for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?

    A : 256
    B : 512
    C : 1024
    D : 2048


  •  
    .

     Correct answer is :B

     Solution :
      O(n log n)=30s
    n = 64 O (64 log 64) = 30
    Hence will get factor of 12.8 for 6 min= 660 = 360s
    O (256 log256) = 360
    O (512 log 512) = 360
    O(1024 log 1024) = 360
    O (2048 log 2048) = 360
    So for 512 will get 12.8 as a factor

  • MY REPORT
    TOTAL = 14
    ANSWERED =
    CORRECT / TOTAL = /14
    POSITIVE SCORE =
    NEGATIVE SCORE =
    FINAL SCORE =