Test: Graphs Algorithms- 1 - Computer Science Engineering (CSE) MCQ

# Test: Graphs Algorithms- 1 - Computer Science Engineering (CSE) MCQ

Test Description

## 15 Questions MCQ Test GATE Computer Science Engineering(CSE) 2025 Mock Test Series - Test: Graphs Algorithms- 1

Test: Graphs Algorithms- 1 for Computer Science Engineering (CSE) 2024 is part of GATE Computer Science Engineering(CSE) 2025 Mock Test Series preparation. The Test: Graphs Algorithms- 1 questions and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus.The Test: Graphs Algorithms- 1 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- 1 below.
Solutions of Test: Graphs Algorithms- 1 questions in English are available as part of our GATE Computer Science Engineering(CSE) 2025 Mock Test Series for Computer Science Engineering (CSE) & Test: Graphs Algorithms- 1 solutions in Hindi for GATE Computer Science Engineering(CSE) 2025 Mock Test Series 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- 1 | 15 questions in 45 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study GATE Computer Science Engineering(CSE) 2025 Mock Test Series for Computer Science Engineering (CSE) Exam | Download free PDF with solutions
Test: Graphs Algorithms- 1 - Question 1

### Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices  and . Which one will be reported by Dijkstra’s shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex  is updated only when a strictly shorter path to  is discovered.

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

Relaxation at every vertex is as follows
Note the next vertex is taken out here is in RED colour

Now We see for S to T its (S->A->C->E->.T)
which is Option d

Test: Graphs Algorithms- 1 - Question 2

### Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time on Depth First Search of G? Assume that the graph is represented using adjacency matrix.

 1 Crore+ students have signed up on EduRev. Have you?
Test: Graphs Algorithms- 1 - Question 3

### What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?

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

Time complexity of Bellman-Ford algorithm is    is number of vertices and   is number of edges. If the graph is complete, the value of  becomes    So overall time complexity becomes     And given here is n vertices. So answers ends up to

Test: Graphs Algorithms- 1 - Question 4

Consider the directed graph below given.

Which one of the following is TRUE?

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

The C option has been copied wrongly
C) Both PSRQ and SPRQ are topological orderings
i)Apply DFS by choosing P or S as starting vertices
ii)As the vertex gets a finishing time assign it to the head of a linked list

Test: Graphs Algorithms- 1 - Question 5

Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing

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

BFS always having starting node. It does not calculate shortest path between every pair but it computes shorted path between W and any other vertex ..

Test: Graphs Algorithms- 1 - Question 6

be a simple undirected graph, and  be a particular vertex in it called the source.    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 Tthen which one of the following CANNOT be the value of ,

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

is possible when both u and v have an edge from t and t is in the shortest path from s to u or v .

is possible when v and t are in the shortest path from s to u and both t  and v are siblings- same distance from s to both t and v causing t-u to both and causing v-u

is possible as explained above by interchanging u and v.

is not possible. This is because on BFS traversal we either visit u first or v . Let's u take first. Now, we put all neighbors of u on queue. Since v is a neighbour and v is not visited before as assumed, d(v) will become d(u)+1

Similarly, for v being visited first.

Test: Graphs Algorithms- 1 - Question 7

In an adjacency list representation of an undirected simple graph G = (V,E) , each edge (u,v)  has two adjacency list entries: [v] in the adjacency list of u , and [u] in the adjacency list of v. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If    , and the memory size is not a constraint, what is the time complexity of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?

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

Applying BFS on Undirected graph give you twin pointer .Visit every vertex level-wise for every vertex fill adjacent vertex in the adjacency list. BFS take 0(m+n) time.

take extra field for storing no. of linked list for perticular vertex. take extra m+n time( m vertex and n edges).

Test: Graphs Algorithms- 1 - Question 8

Let G = (V,E) be  connected undirected edge-weighted graph. The weights of the edges in E are positive and distinct. Consider the following statements:

(I) Minimum Spanning Tree of G is always unique.

(II) Shortest path between any two vertices of G is always unique.

Which of the above statements is/are necessarily true?

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

> MST is not unique only when edges are not distinct. Here the edges are distinct. Be careful for the keyword
DISTINCT.

> Shortest Path can be different even if the edges are distinct. Example is shown below. Shortest path from A
to C is not unique here.

Test: Graphs Algorithms- 1 - Question 9

The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph below?

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

In BFS starting from a node, we traverse all node adjacent to it at first then repeat same for next nodes

Here you can see only D is following BFS sequence properly

As per BFS if we start from M then RQN has to come after it in any order but in A here O comes so it is not
As per BFS if we start from Nthen QMO has to come after it in any order but in A here P comes so it is not
As per BFS if we start from M then MNOP has to come after it in any order but in A here R comes so it is not but D following the sequences

Test: Graphs Algorithms- 1 - Question 10

Let G be an undirected graph. Consider a depth-first traversal of G, and let T be the resulting depth-first search tree. Let u be a vertex in G and let v be the first new (unvisited) vertex visited after visiting u in the traversal. Which of the following statement is always true?

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

Correct option is C. If {u, v} is not an edge in G then u is a leaf in T

Test: Graphs Algorithms- 1 - Question 11

Consider the following directed graph.

Suppose a depth-first traversal of this graph is performed, assuming that whenever there is a choice, the vertex earlier in the alphabetical order is to be chosen. Suppose the number of tree edges is , the number of back edges is  and the number of cross edges is . Then

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

Since they said that whenever their is a choice we will have to select the node which is alphabetically earlier , therefore we choose the starting node as A .

The tree then becomes A-B-E-C . Therefore no of tree edges is 3 that is (T=3) .
Now there is one cycle B-E-C so we will get a back edge from C to B while performing DFS. Hence B=1 .
Now D becomes disconnected node and it can only contribute in forming cross edge . There are 2 cross edges D-A , D-B .
Therefore C=2 .

Test: Graphs Algorithms- 1 - Question 12

The minimum number of record movements required to merge five files A (with 10 records), B (with 20 records), C (with 15 records), D (with 5 records) and E (with 25 records) is:

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

Arrange files in increasing order of records

5(D) 10(A)
No of movements=15+30+45+75=165

Test: Graphs Algorithms- 1 - Question 13

We are given 9 tasks    The execution of each task requires one unit of time. We can execute one task at a time. Each task  Thas a profit Pi and a deadline di . Profit  Pis earned if the task is completed before the end of the dith unit of time.

Are all tasks completed in the schedule that gives maximum profit?

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

The most important statement in question is

each task requires one unit of time

This shows that we can greedily choose the better task and that should give us the optimal solution. The best task would be the one with maximum profit. Thus we can sort the tasks based on deadline and then profit as follows:

0 ----T7 ----- 1----T2-----2-----T9-----3-----T5-----4-----T3-----5-----T8-----6-----T1------7

T4 and T6 left out

Test: Graphs Algorithms- 1 - Question 14

We are given 9 tasks    The execution of each task requires one unit of time. We can execute one task at a time. Each task  Thas a profit Pi and a deadline di . Profit  Pis earned if the task is completed before the end of the dith unit of time.

What is the maximum profit earned?

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

The most important statement in question is

each task requires one unit of time

This shows that we can greedily choose the better task and that should give us the optimal solution. The best task would be the one with maximum profit. Thus we can sort the tasks based on deadline and then profit as follows:

0 --T7 -- 1 -- T2 -- 2 -- T9 -- 3 -- T5 -- 4 -- T3 -- 5 -- T8 -- 6 -- T1 -- 7

so we know that T4 and T6 are left
so profit will not include T4 and T6 = 15 + 20 +30 +18 + 16 + 23 + 25 = 147

Test: Graphs Algorithms- 1 - Question 15

For which of the following combinations of the degrees of vertices would the connected graph be eulerian?

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

A graph is eulerian if either all of its vertices are even or if only two of its vertices are odd.

## GATE Computer Science Engineering(CSE) 2025 Mock Test Series

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

## GATE Computer Science Engineering(CSE) 2025 Mock Test Series

55 docs|215 tests