Computer Science Engineering (CSE) Exam > Computer Science Engineering (CSE) Tests > Test: Graphs Algorithms- 2 - Computer Science Engineering (CSE) MCQ

Test Description

Test: Graphs Algorithms- 2 for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Test: Graphs Algorithms- 2 questions and answers have been prepared
according to the Computer Science Engineering (CSE) exam syllabus.The Test: Graphs Algorithms- 2 MCQs are made for Computer Science Engineering (CSE) 2024 Exam.
Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Test: Graphs Algorithms- 2 below.

Solutions of Test: Graphs Algorithms- 2 questions in English are available as part of our course for Computer Science Engineering (CSE) & Test: Graphs Algorithms- 2 solutions in
Hindi for Computer Science Engineering (CSE) course.
Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Attempt Test: Graphs Algorithms- 2 | 25 questions in 75 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study for Computer Science Engineering (CSE) Exam | Download free PDF with solutions

1 Crore+ students have signed up on EduRev. Have you? Download the App |

*Answer can only contain numeric values

Test: Graphs Algorithms- 2 - Question 1

Consider the following directed graph:

The number of different topological orderings of the vertices of the graph is _____________.

Detailed Solution for Test: Graphs Algorithms- 2 - Question 1

*Answer can only contain numeric values

Test: Graphs Algorithms- 2 - Question 2

Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex * t* at a distance four from the root. If

Detailed Solution for Test: Graphs Algorithms- 2 - Question 2

Detailed Solution for Test: Graphs Algorithms- 2 - Question 3

Test: Graphs Algorithms- 2 - Question 4

Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph?

Detailed Solution for Test: Graphs Algorithms- 2 - Question 4

Test: Graphs Algorithms- 2 - Question 5

The most appropriate matching for the following pairs

is:

Detailed Solution for Test: Graphs Algorithms- 2 - Question 5

Test: Graphs Algorithms- 2 - Question 6

Consider an undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r. Let d(r,u) and d(r,v) be the lengths of the shortest paths from r to u and v respectively in G. if u visited before v during the breadth-first traversal, which of the following statements is correct?

Detailed Solution for Test: Graphs Algorithms- 2 - Question 6

Test: Graphs Algorithms- 2 - Question 7

Consider the following graph

Among the following sequences

I. abeghf

II. abfehg

III. abfhge

IV. afghbe

which are depth first traversals of the above graph?

Detailed Solution for Test: Graphs Algorithms- 2 - Question 7

Test: Graphs Algorithms- 2 - Question 8

Suppose we run Dijkstra’s single source shortest-path algorithm on the following edge-weighted directed graph with vertex P as the source.

In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized?

Detailed Solution for Test: Graphs Algorithms- 2 - Question 8

Test: Graphs Algorithms- 2 - Question 9

Let G_{1} = (V, E_{1}) and G_{2} = (V, E_{2}) be connected graphs on the same vertex set V with more than two vertices. If G_{1} ∩ G_{2} = (V, E_{1 }∩ E_{2} ) is not a connected graph, then the graph G_{1} ∪ G_{2} = (V, E_{1 }∪ E_{2} )

Detailed Solution for Test: Graphs Algorithms- 2 - Question 9

Test: Graphs Algorithms- 2 - Question 10

Consider the undirected graph below:

Using Prim's algorithm to construct a minimum spanning tree starting with node A, which one of the following sequences of edges represents a possible order in which the edges would be added to construct the minimum spanning tree?

Detailed Solution for Test: Graphs Algorithms- 2 - Question 10

Test: Graphs Algorithms- 2 - Question 11

Let S and t be two vertices in a undirected graph G=(V,E) having distinct positive edge weights. Let [X,Y] be a partition of V such that s ∈ X and t ∈ Y . Consider the edge having the minimum weight amongst all those edges that have one vertex in X and one vertex in Y

The edge e must definitely belong to:.

Detailed Solution for Test: Graphs Algorithms- 2 - Question 11

Test: Graphs Algorithms- 2 - Question 12

In a depth-first traversal of a graph G with n vertices, K edges are marked as tree edges. The number of connected components in G is

Detailed Solution for Test: Graphs Algorithms- 2 - Question 12

Test: Graphs Algorithms- 2 - Question 13

In the following table, the left column contains the names of standard graph algorithms and the right column contains the time complexities of the algorithms. Match each algorithm with its time complexity.

Detailed Solution for Test: Graphs Algorithms- 2 - Question 13

Test: Graphs Algorithms- 2 - Question 14

To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:

Detailed Solution for Test: Graphs Algorithms- 2 - Question 14

Test: Graphs Algorithms- 2 - Question 15

Let T be a depth first search tree in an undirected graph G. Vertices u and ν are leaves of this tree T. The degrees of both u and ν in G are at least 2. which one of the following statements is true?

Detailed Solution for Test: Graphs Algorithms- 2 - Question 15

Test: Graphs Algorithms- 2 - Question 16

Which of the following is the correct decomposition of the directed graph given below into its strongly connected components?

Detailed Solution for Test: Graphs Algorithms- 2 - Question 16

Test: Graphs Algorithms- 2 - Question 17

Consider the depth-first-search of an undirected graph with 3 vertices P, Q, and R. Let discovery time d(u) represent the time instant when the vertex u is first visited, and finish time f(u) represent the time instant when the vertex u is last visited. Given that

Which one of the following statements is TRUE about the graph

Detailed Solution for Test: Graphs Algorithms- 2 - Question 17

Test: Graphs Algorithms- 2 - Question 18

In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity, by

Detailed Solution for Test: Graphs Algorithms- 2 - Question 18

Test: Graphs Algorithms- 2 - Question 19

Consider the DAG with

Which of the following is not a topological ordering?

Detailed Solution for Test: Graphs Algorithms- 2 - Question 19

Test: Graphs Algorithms- 2 - Question 20

A depth-first search is performed on a directed acyclic graph. Let d[u] denote the time at which vertex u is visited for the first time and f[u] the time at which the dfs call to the vertex u terminates. Which of the following statements is always true for all edges (u, v) in the graph ?

Detailed Solution for Test: Graphs Algorithms- 2 - Question 20

Test: Graphs Algorithms- 2 - Question 21

Consider a weighted undirected graph with positive edge weights and let be an edge in the graph. It is known that the shortest path from the source vertex to has weight 53 and the shortest path from to has weight 65. Which one of the following statements is always true?

Detailed Solution for Test: Graphs Algorithms- 2 - Question 21

Test: Graphs Algorithms- 2 - Question 22

The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is

Detailed Solution for Test: Graphs Algorithms- 2 - Question 22

Test: Graphs Algorithms- 2 - Question 23

Dijkstra's single source shortest path algorithm when run from vertex in the above graph, computes the correct shortest path distance to

Detailed Solution for Test: Graphs Algorithms- 2 - Question 23

Test: Graphs Algorithms- 2 - Question 24

The most efficient algorithm for finding the number of connected components in an undirected graph on vertices and edges has time complexity

Detailed Solution for Test: Graphs Algorithms- 2 - Question 24

Test: Graphs Algorithms- 2 - Question 25

Consider the following sequence of nodes for the undirected graph given below.

A Depth First Search (DFS) is started at node a. The nodes are listed in the order they are first visited. Which all of the above is (are) possible output(s)?

Detailed Solution for Test: Graphs Algorithms- 2 - Question 25

Information about Test: Graphs Algorithms- 2 Page

In this test you can find the Exam questions for Test: Graphs Algorithms- 2 solved & explained in the simplest way possible.
Besides giving Questions and answers for Test: Graphs Algorithms- 2, EduRev gives you an ample number of Online tests for practice

Download as PDF