Font size
WorksheetsGraph
Total questions: 64
Worksheet time: 44mins
In a simple graph, the number of edges is equal to twice the sum of the degrees of the vertices.
True
False
A connected graph T without any cycles is called .......
Free graph
no cycle graph
non cycle graph
circular graph
A graph is said to be (a) if every node u in G is adjacent to every other node v in G.
What would be the DFS traversal of the given Graph?
ABCDE
AEDCB
EDCBA
ADECB
The topological sorting of any DAG can be done in ________ time
cubic
quadratic
linear
logarithmic
What sequence would the BFS traversal of the given graph yield?
A F D B C E
C B A F D
A B D C F
A B C D E F
Which of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph?
In adjacency list representation, space is saved for sparse graphs.
DFS and BSF can be done in O(V + E) time for adjacency list representation. These operations take O(V^2) time in adjacency matrix representation. Here is V and E are number of vertices and edges respectively.
Adding a vertex in adjacency list representation is easier than adjacency matrix representation.
All of the above
Which of the following statements is/are TRUE for an undirected graph?
P: Number of odd degree vertices is even
Q: Sum of degrees of all vertices is even
P Only
Q Only
Both P and Q
Neither P nor Q
Which of the following is true?
Prim’s algorithm initialises with a vertex
Prim’s algorithm initialises with a edge
Prim’s algorithm initialises with a vertex which has smallest edge
Prim’s algorithm initialises with a forest
Consider the given graph. What is the weight of the minimum spanning tree using the Prim’s algorithm, starting from vertex a?
23
28
27
11
Prim’s algorithm is a ______
Divide and conquer algorithm
Greedy algorithm
Dynamic Programming
Approximation algorithm
Consider the graph shown below. Which of the following edges form the MST of the given graph using Prim’s algorithm, starting from vertex 4.
(4-3)(5-3)(2-3)(1-2)
(4-3)(3-5)(5-1)(1-2)
(4-3)(3-5)(5-2)(1-5)
(4-3)(3-2)(2-1)(1-5)
What is the time complexity of Dijikstra’s algorithm?
O(N)
O(N3)
O(N2)
O(logN)
Dijkstra’s Algorithm cannot be applied on ______________
Directed and weighted graphs
Graphs having negative weight function
Unweighted graphs
Undirected and unweighted graphs
Consider the following graph. If b is the source vertex, what is the minimum cost to reach f vertex?
8
9
4
6
In the given graph, identify the shortest path having minimum cost to reach vertex E if A is the source vertex.
a-b-e
a-c-e
a-c-d-e
a-c-d-b-e
The Data structure used in standard implementation of Breadth First Search is?
Stack
Queue
Linked List
Tree
A person wants to visit some places. He starts from a vertex and then wants to visit every place connected to this vertex and so on. What algorithm he should use?
Depth First Search
Breadth First Search
Trim’s algorithm
Kruskal’s algorithm
Which of the following is not an application of Breadth First Search?
Finding shortest path between two nodes
Finding bipartiteness of a graph
GPS navigation system
Path Finding
What are the appropriate data structures for following algorithms?
1) Breadth First Search
2) Depth First Search
3) Prim's Minimum Spanning Tree
4) Kruskal' Minimum Spanning Tree
1) Stack
2) Queue
3) Priority Queue 4) Union Find
1) Queue
2) Stack
3) Priority Queue 4) Union Find
1) Stack
2) Queue
3) Union Find
4) Priority Queue
1) Priority Queue 2) Queue
3) Stack
4) Union Find
A complete, undirected, weighted graph GGG is defined on vertices {0,1,2,…,n−1}\{0,1,2,\dots,n-1\}{0,1,2,…,n−1}.
Find the structure of the Minimum Spanning Tree (MST) in the following cases:
(a) Weight of edge (u,v)=∣u−v∣(u,v) = |u - v|(u,v)=∣u−v∣
(b) Weight of edge (u,v)=u+v(u,v) = u + v(u,v)=u+v
(a) Star centered at 0
(b) Path: 0−1−2−⋯−(n−1)0 - 1 - 2 - \cdots - (n-1)0−1−2−⋯−(n−1)
(a) Path: 0−1−2−⋯−(n−1)0 - 1 - 2 - \cdots - (n-1)0−1−2−⋯−(n−1)
(b) Star centered at 0
(a) Complete graph
(b) Path: 0−1−2−⋯−(n−1)0 - 1 - 2 - \cdots - (n-1)0−1−2−⋯−(n−1)
(a) Star centered at n−1n-1n−1
(b) Star centered at 1
We are interested in the shortest paths from A. Output the sequence of vertices identified by the Dijkstra’s algorithm for single source shortest path when the algorithm is started at node A.
(a)
Let G be the directed, weighted graph shown in below figure graph. We are interested in the shortest paths from A. (q) Write down sequence of vertices in the shortest path from A to F. (b) What is the cost of the shortest path from A to E?
(a)
Which of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph?
In adjacency list representation, space is saved for sparse graphs.
DFS and BSF can be done in O(V + E) time for adjacency list representation. These operations take O(V^2) time in adjacency matrix representation. Here is V and E are number of vertices and edges respectively.
Adding a vertex in adjacency list representation is easier than adjacency matrix representation.
All of the above
In the following graph, discovery time stamps and finishing time stamps of Depth First Search (DFS) are shown as x/y, where x is discovery time stamp and y is finishing time stamp.
It shows which of the following depth first forest?
{a, b, e} {c, d, f, g, h}
{a, b, e} {c, d, h} {f, g}
{a, b, e} {f, g} {c, d} {h}
{a, b, c, d} {e, f, g} {h}
Consider a segment tree built on an array of N elements. What is the minimum number of node updates required to rebuild the entire tree if the original array is reversed?
n
n-1
2n-1
nlogn
In an undirected connected planar graph G, there are eight vertices and five faces. The number of edges in G is _________.
10
11
12
6
Consider the following undirected graph with edge weights as shown:
The number of minimum-weight spanning trees of the graph is ___________.
3
4
5
2
The cyclomatic complexity of the flow graph of a program provides
an upper bound for the number of tests that must be conducted to ensure that all statements have been executed at most once
a lower bound for the number of tests that must be conducted to ensure that all statements have been executed at most once
an upper bound for the number of tests that must be conducted to ensure that all statements have been executed at least once
a lower bound for the number of tests that must be conducted to ensure that all statements have been executed at least once
What is the largest integer m such that every simple connected graph with n vertices and n edges contains at least m different spanning trees?
1
2
3
n
Which of the following data structure is useful in traversing a given graph by depth first search?
Stack
List
Queue
None
What is the worst case efficiency for a path compression algorithm?
O(M log N)
O(N log N)
O(log N)
O(N)
Let G be a weighted undirected graph and e be an edge with maximum weight in G. Suppose there is a minimum weight spanning tree in G containing the edge e. Which of the following statements is always TRUE?
There exists a cutset in G having all edges of maximum weight.
There exists a cycle in G having all edges of maximum weight
Edge e cannot be contained in a cycle.
All edges in G have the same weight
What is the maximum number of edges in an acyclic undirected graph with n vertices?
n-1
n
n+1
2n-1
The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity.
theta(n)
theta(m)
theta(m+n)
theta(mn)
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. lf u is visited before v during the breadth-first traversal, which of the following statements is correct?
d(r, u) < d (r, v)
d(r, u) > d(r, v)
d(r, u) <= d (r, v)
none
How many undirected graphs (not necessarily connected) can be constructed out of a given set V= {V 1, V 2,…V n} of n vertices ?
n(n-l)/2
2^n
n!
2^(n(n-1)/2)
Which of the following statements is/are TRUE for an undirected graph?
P: The number of odd-degree vertices is even
Q: Sum of degrees of all vertices is even
P Only
Q Only
Both P and Q
Neither P and Q
Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three?
1/8
1
7
8
In which scenario would a directed acyclic graph (DAG) be most suitable?
Representing dependencies between tasks in a project schedule
Modeling a social network with friend connections
Finding the shortest path between two nodes in a weighted graph
Performing breadth-first search (BFS) on a graph
How many undirected graphs (not necessarily connected) can be constructed out of a given set V = {v1, v2, ... vn} of n vertices?
n(n-1)/2
2n
n!
2n(n-1)/2
A sink in a directed graph is a vertex i such that there is an edge from every vertex j ≠ i to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adjacency matrix A, where A[i] [j] = 1 if there is an edge directed from vertex i to j and 0 otherwise. The following algorithm determines whether there is a sink in the graph G. Choose the correct expressions for E3
(A[i][j] && !A[j][i])
(!A[i][j] && A[j][i])
(!A[i][j] | | A[j][i])
(A[i][j] | | !A[j][i])
For the undirected, weighted graph given below, which of the following sequences of edges represents a correct execution of Prim's algorithm to construct a Minimum Spanning Tree?
(a, b), (d, f), (f, c), (g, i), (d, a), (g, h), (c, e), (f, h)
(c, e), (c, f), (f, d), (d, a), (a, b), (g, h), (h, f), (g, i)
(d, f), (f, c), (d, a), (a, b), (c, e), (f, h), (g, h), (g, i)
(h, g), (g, i), (h, f), (f, c), (f, d), (d, a), (a, b), (c, e)
Consider a directed graph with n vertices and m edges such that all edges have same edge weights. Find the complexity of the best known algorithm to compute the minimum spanning tree of the graph?
O(m+n)
O(m logn)
O(mn)
O(n logm)
You are given a graph containing n vertices and m edges and given that the graph doesn’t contain cycle of odd length. Time Complexity of the best known algorithm to find out whether the graph is bipartite or not is ?
O(m+n)
O(1)
O(mn)
O(n2)
Let G be a simple graph with 20 vertices and 8 components. If we delete a vertex in G, then number of components in G should lie between ____.
8 and 20
8 and 19
7 and 19
7 and 20
Let G be the graph with 100 vertices numbered 1 to 100. Two vertices i and j are adjacent if |i−j|=8 or |i−j|=12. The number of connected components in G is
8
4
12
25
What is the primary difference between a directed graph and a undirected graph?
A directed graph has nodes with unique identifiers, while an undirected graph does not.
A directed graph has edges with direction, while an undirected graph does not.
There is no difference between them.
A directed graph has nodes with unique identifiers, while an undirected graph does not.
In a graph of n nodes and n edges, how many cycles will be present?
Exactly 1
At most 1
At most 2
Depend on graph
Why is the state graph for tic-tac-toe a directed graph rather than an undirected graph
Once a move is made, it cannot be unmade.
There is an odd number of vertices.
There is an odd number of edges
There is more than one player in the game.
Suppose you have a directed graph representing all the flights that an airline flies. What algorithm might be used to find the best sequence of connections from one city to another?
Breadth first search.
Depth first search.
A cycle-finding algorithm.
A shortest-path algorithm.
If G is an directed graph with 20 vertices, how many boolean values will be needed to represent G using an adjacency matrix?
20
40
200
400
How many linked lists are used to represent a graph with n nodes and m edges, when using an edge list representation,
m
n
m+n
mn
How are loops represented in an edge-list representation of a graph?
A vertex will be on its own edge-list.
The edge-list will be a circular linked list.
The edge-list will be empty for that particular vertex.
The edge-list will be full for that particular vertex.
What is the expected number of operations needed to loop through all the edges terminating at a particular vertex given an adjacency matrix representation of the graph? (Assume n vertices are in the graph and m edges terminate at the desired node.)
O(m)
O(n)
O(m²)
O(n²)
For the figure as below, which edge does not occur in the depth first spanning tree resulting from depth first search starting at node B:
F → E
E → C
C → G
C → F
The set of all edges generated by DFS tree starting at node B is:
B A D C G F E
A D
B A C D G F E
Cannot be generated
The set of all edges generated by BFS tree starting at node B is:
B A D C G F E
A D
B A C D G F E
Cannot be generated
Which of the following statements is/are true?
I. Adjacency list representation is better for sparse graph than adjacency matrix representation.
II. Finding whether there is an edge between any two node s in a graph is easier in Adjacency list representation.
III. Adding a vertex in adjacency list representation is easier than adjacency Matrix representation.
I only
I & III only
II & III only
I, II & III
An undirected graph G has n nodes. Its adjacency matrix is given by an nxn square matrix whose (I) diagonal elements are ‘0’s (II) Non-diagonal elements are ‘1’s. Which one of the following is True?
Graph G has no minimum spanning tree (MST)
Graph G has unique MST’s each of cost n–1
Graph G has multiple distinct MST’s each of cost n–1
Graph G has multiple spanning trees of different costs
How many distinct spanning trees do exist in an undirected cycle graph of n vertices?
n
n+1
n–1
n+2
If every node in a graph ‘G’ is adjacent to equal number of nodes, then the graph G is said to be
Regular
Finite
Complete
Strongly connected
Consider an undirected graph G with 100 nodes. The maximum number of edges to be included in G so that the graph is not connected is
2451
4851
4950
9801
A connected (all vertices have at least one neighbour), undirected graph of N vertices has (N-1) edges. Number of spanning tree that can be constructed are
1
N
N - 1
N × (N-1)
