Cs501 - Design & Analysis Of Algorithm - Iem

40 Questions | Total Attempts: 170

SettingsSettingsSettings
Please wait...
Cs501 - Design & Analysis Of Algorithm - Iem

.


Questions and Answers
  • 1. 
    What are the correct intermediate steps of the following data set when it is being sorted with the Quick sort? 15,20,10,18
    • A. 

      15,10,20,18 -- 15,10,18,20 -- 10,15,18,20

    • B. 

      15,20,10,18 -- 15,10,20,18 -- 10,15,20,18

    • C. 

      10, 20,15,18 -- 10,15,20,18 -- 10,15,18,20

    • D. 

      10, 20,15,18 -- 10,18,15,20 -- 10,15,18,20

  • 2. 
    Quick sort uses
    • A. 

      Exchanging

    • B. 

      Partitioning

    • C. 

      Selection

    • D. 

      Merging

  • 3. 
    Using quick sort is a stable way of sorting
    • A. 

      True

    • B. 

      False

  • 4. 
    Which of the following is False about merge sort algorithm?
    • A. 

      It is a comparison sorting algorithm.

    • B. 

      The unsorted array is divided into sublists, which are in turn divided into more sublists.

    • C. 

      The unsorted array is divided into sublists, each sublist is then sorted recursively by re-applying the algorithm.

    • D. 

      All of the above statements are true

  • 5. 
    An array has indices ranging from x to x+n; the merge sort would be applied from c to x+n, where c
    • A. 

      Is the remainder of x/2, if x is an odd number

    • B. 

      Is the the non-integer part of x/2

    • C. 

      Is the integer part of x/2

    • D. 

      Is an integer chosen arbitrarily, so long that it is smaller than x+n

  • 6. 
    Which of the following Big O Notations has constant order of growth?
    • A. 

      O(n)

    • B. 

      O(1)

    • C. 

      O(n2)

    • D. 

      O(log n)

  • 7. 
    To implement __________ search algorithm, the list should be sorted.
    • A. 

      Linear

    • B. 

      Binary

    • C. 

      Both

    • D. 

      None

  • 8. 
    Consider the algorithm of deleting a node from the beginning of a linked list and identify the error:                         1. Mark the first node in the list as current                         2. Make START point to the next node in sequence.                         3. Release the memory for the node marked as current.
    • A. 

      The algorithm has no error

    • B. 

      The sequence is wrong, the correct one is 3->1->2

    • C. 

      The sequence is wrong, the correct one is 2->1->3

    • D. 

      The sequence is wrong, the correct one is 3->2->1

  • 9. 
    Is a data structure consisting of a collection of elements (values or variables), each identified by one or more integer indices, stored so that the address of each element can be computed from its index tuple by a simple mathematical formula
    • A. 

      Loop

    • B. 

      Array

    • C. 

      Binary Search

    • D. 

      One-dimensional array

    • E. 

      Sorting

  • 10. 
    Is a technique for locating a particular value in a sorted list.
    • A. 

      Sorting

    • B. 

      Do Loop

    • C. 

      One-dimensional array

    • D. 

      Array

    • E. 

      Binary Search

  • 11. 
    The Big O Notation of the expression f(n) = 2n + 6n2 + 3n is:
    • A. 

      O( )

    • B. 

      O( )

    • C. 

      O(n)

    • D. 

      None of these

  • 12. 
    Which algorithm design technique is used in quick sort?
    • A. 

      Dynamic Programming

    • B. 

      Divide and Conquer

    • C. 

      Greedy Method

    • D. 

      Branch and Bound

  • 13. 
    ω Notation provides and asymptotic:
    • A. 

      Upper Bound

    • B. 

      Lower Bound

    • C. 

      Between upper & lower bounds

    • D. 

      None of these

  • 14. 
    Complexity of binary search is:
    • A. 

      O(n)

    • B. 

      O( )

    • C. 

      O( )

    • D. 

      O(n.

  • 15. 
    Optimal Substructure property is exploited by:
    • A. 

      Dynamic Programming

    • B. 

      Greedy Method

    • C. 

      Both

    • D. 

      None

  • 16. 
    Which of the following approaches is adopted in Divide & Conquer algorithms?
    • A. 

      Top-down

    • B. 

      Bottom-up

    • C. 

      Both

    • D. 

      None

  • 17. 
    In a Backtracking algorithm the solution space is searched using:
    • A. 

      BFS

    • B. 

      DFS

    • C. 

      Binary Search

    • D. 

      None

  • 18. 
    Binary Search algorithm can't be applied to:
    • A. 

      Sorted linked lists

    • B. 

      Sorted binary trees

    • C. 

      Sorted linear array

    • D. 

      Sorted integer array

  • 19. 
    The technique of Pruning is used in:
    • A. 

      Branch & Bound

    • B. 

      Backtracking

    • C. 

      Divide & Conquer

    • D. 

      Dynamic Programming

  • 20. 
    Shortest path to all the vertices of a graph from a given vertex of the same graph is obtained by:
    • A. 

      Kruskal's Algorithm

    • B. 

      Dijkstra's Algorithm

    • C. 

      BFS

    • D. 

      DFS

  • 21. 
    Which of the following problems is solved using the branch and bound method?
    • A. 

      Knapsack problem

    • B. 

      Hamiltonian Problem

    • C. 

      Graph coloring

    • D. 

      15 puzzle problem

  • 22. 
    Lower Bound for any comparison sort is:
    • A. 

      O( )

    • B. 

      O( )

    • C. 

      O(n )

    • D. 

      O( )

  • 23. 
    O(g(n)) is [Read as small oh of g(n) is]
    • A. 

      Asymptotically loose

    • B. 

      asymptotically tight

    • C. 

      Same as big oh

    • D. 

      None of these

  • 24. 
    Big O notation of the expression f(n) = nlog2 n + n2 + elog2 n
    • A. 

      O(n)

    • B. 

      O( )

    • C. 

      O(n )

    • D. 

      O(e

  • 25. 
    Which one of the following statements is true?
    • A. 

      All NP Hard problems are NP Complete

    • B. 

      All NP Complete problems are NP Hard

    • C. 

      Some NP Complete problems are NP Hard

    • D. 

      None of these

Back to Top Back to top