Scribd Logo
Upload

Welcome to Scribd!

  • 35 views

    ADA Questions

    Uploaded by

    Aman Kumar
    Depth First Search (DFS) is equivalent to pre-order tree traversal. The time complexity of DFS is O(V+E) where V is the number of vertices and E is the number of edges. The standard data structure used to implement Breadth First Search (BFS) is a queue. DFS traversal of a graph is unique when the graph is a binary tree. Dijkstra's algorithm runs in O(ElogV) time and performs decrease key operations at most equal to the number of vertices.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    ADA Questions

    Uploaded by

    Aman Kumar
    35 views3 pages
    Depth First Search (DFS) is equivalent to pre-order tree traversal. The time complexity of DFS is O(V+E) where V is the number of vertices and E is the number of edges. The standard data structure used to implement Breadth First Search (BFS) is a queue. DFS traversal of a graph is unique when the graph is a binary tree. Dijkstra's algorithm runs in O(ElogV) time and performs decrease key operations at most equal to the number of vertices.

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Depth First Search (DFS) is equivalent to pre-order tree traversal. The time complexity of DFS is O(V+E) where V is the number of vertices and E is the number of edges. The standard data structure used to implement Breadth First Search (BFS) is a queue. DFS traversal of a graph is unique when the graph is a binary tree. Dijkstra's algorithm runs in O(ElogV) time and performs decrease key operations at most equal to the number of vertices.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    35 views3 pages

    ADA Questions

    Uploaded by

    Aman Kumar
    Depth First Search (DFS) is equivalent to pre-order tree traversal. The time complexity of DFS is O(V+E) where V is the number of vertices and E is the number of edges. The standard data structure used to implement Breadth First Search (BFS) is a queue. DFS traversal of a graph is unique when the graph is a binary tree. Dijkstra's algorithm runs in O(ElogV) time and performs decrease key operations at most equal to the number of vertices.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 3

    1. Depth First Search is equivalent to which of the traversal in the Binary Trees?

    a) Pre-order Traversal
    b) Post-order Traversal
    c) Level-order Traversal
    d) In-order Traversal

    2. Time Complexity of DFS is? (V – number of vertices, E – number of edges)


    a) O(V + E)
    b) O(V)
    c) O(E)
    d) O(V*E)

    3. The Data structure used in standard implementation of Breadth First Search is?
    a) Stack
    b) Queue
    c) Linked List
    d) Tree

    4. When the Depth First Search of a graph is unique?


    a) When the graph is a Binary Tree
    b) When the graph is a Linked List
    c) When the graph is a n-ary Tree
    d) When the graph is a ternary Tree

    5. Which of the following is false in the case of a spanning tree of a graph G?


    a) It is tree that spans G
    b) It is a subgraph of the G
    c) It includes every vertex of the G
    d) It can be either cyclic or acyclic

    6. Regarding implementation of Breadth First Search using queues, what is the


    maximum distance between two nodes present in the queue? (considering each edge
    length 1)
    a) Can be anything
    b) 0
    c) At most 1
    d) Insufficient Information

    7. The Breadth First Search traversal of a graph will result into?


    a) Linked List
    b) Tree
    c) Graph with back edges
    d) Arrays

    8. Every graph has only one minimum spanning tree.


    a) True
    b) False

    9. The travelling salesman problem can be solved using _________


    a) A spanning tree
    b) A minimum spanning tree
    c) Bellman – Ford algorithm
    d) DFS traversal

    10. If all the weights of the graph are positive, then the minimum spanning tree of the
    graph is a minimum cost subgraph.
    a) True
    b) False

    11. Consider the graph shown below. Which of the following are the edges in the MST of
    the given graph?

    a) (a-c)(c-d)(d-b)(d-b)
    b) (c-a)(a-d)(d-b)(d-e)
    c) (a-d)(d-c)(d-b)(d-e)
    d) (c-a)(a-d)(d-c)(d-b)(d-e)

    12. Which of the following is false?


    a) The spanning trees do not have any cycles
    b) MST have n – 1 edges if the graph has n edges
    c) Edge e belonging to a cut of the graph if has the weight smaller than any other edge
    in the same cut, then the edge e is present in all the MSTs of the graph
    d) Removing one edge from the spanning tree will not make the graph
    disconnected
    13. What is the time complexity of Dijikstra’s algorithm?
    a) O(N)
    b) O(N3)
    c) O(N2)
    d) O(logN)

    14. The maximum number of times the decrease key operation performed in Dijkstra’s
    algorithm will be equal to ___________
    a) Total number of vertices
    b) Total number of edges
    c) Number of vertices – 1
    d) Number of edges – 1

    15. What is the running time of Bellmann Ford Algorithm?


    a) O(V)
    b) O(V2)
    c) O(ElogV)
    d) O(VE)

    You might also like