NEW
Font size
S
M
L
XL
WorksheetsGraph Theory Quiz
Total questions: 40
Worksheet time: 10hrs 46mins
Name
Class
Date
1.
A graph G is defined as:
a)
A set of vertices only
b)
A set of edges only
c)
A pair (V, E) where V is a set of vertices and E is a set of edges
d)
A tree with no cycles
2.
In an undirected graph, edges are:
a)
Ordered pairs
b)
Unordered pairs
c)
Always weighted
d)
Always directed
3.
Which of the following is true for a directed graph?
a)
Edges have no direction
b)
Each edge is an unordered pair
c)
Each edge is an ordered pair
d)
It cannot have cycles
4.
The degree of a vertex in an undirected graph is:
a)
Number of outgoing edges
b)
Number of incoming edges
c)
Number of incident edges
d)
Sum of weights of edges
5.
A self-loop is:
a)
An edge connecting two different vertices
b)
An edge connecting a vertex to itself
c)
A cycle of length 2
d)
A parallel edge
6.
A simple path is:
a)
A path with repeated vertices
b)
A path with repeated edges
c)
A path where all vertices and edges are distinct
d)
A path that starts and ends at the same vertex
7.
A cycle in a graph is:
a)
A path that starts and ends at different vertices
b)
A path that starts and ends at the same vertex
c)
A path with no repeated vertices
d)
A path with no repeated edges
8.
A forest is:
a)
A connected graph with cycles
b)
A disconnected graph with cycles
c)
A collection of trees (acyclic components)
d)
A spanning tree of a graph
9.
An adjacency matrix for a graph with n vertices has size:
a)
n x m
b)
m x m
c)
n x n
d)
m x n
10.
In an adjacency matrix, the entry at row i, column j is:
a)
Always 0
b)
1 if edge (i,j) exists, else 0
c)
Weight of vertex i
d)
Degree of vertex j
11.
Adjacency lists are more space-efficient for:
a)
Dense graphs
b)
Sparse graphs
c)
Weighted graphs only
d)
Directed graphs only
12.
For an undirected graph with no self-loops, the sum of degrees of all vertices equals:
a)
|E|
b)
2|E|
c)
|V|
d)
n^2
13.
Maximum number of edges in a simple undirected graph with n vertices is:
a)
n(n-1)
b)
n(n-1)/2
c)
2n
d)
n^2
14.
DFS runs in:
a)
O(|V|^2)
b)
O(|V|+|E|)
c)
O(|E| log |V|)
d)
O(|V|+|E| log |V|)
15.
BFS uses which data structure?
a)
Stack
b)
Queue
c)
Priority Queue
d)
Linked List
16.
BFS is particularly useful for finding:
a)
Minimum spanning tree
b)
Shortest path in unweighted graphs
c)
Strongly connected components
d)
Topological order
17.
Dijkstra’s algorithm assumes:
a)
Negative edge weights allowed
b)
Graph is disconnected
c)
All edge weights are non-negative
d)
Graph is a DAG
18.
Time complexity of Dijkstra’s algorithm using a binary heap is:
a)
O(|V|+|E|)
b)
O((|V|+|E|)log |V|)
c)
O(|V|^2)
d)
O(|E|^2)
19.
The Floyd-Warshall algorithm computes:
a)
Single-source shortest paths
b)
All-pairs shortest paths
c)
Minimum spanning tree
d)
Topological sort
20.
Floyd-Warshall runs in:
a)
O(|V|+|E|)
b)
O(|V|^2)
c)
O(|V|^3)
d)
O(|E|^3)
21.
A topological sort is possible only if the graph is:
a)
Connected
b)
Undirected
c)
A DAG
d)
Weighted
22.
Which algorithm is commonly used for minimum spanning tree?
a)
BFS
b)
DFS
c)
Prim’s or Kruskal’s
d)
Floyd-Warshall
23.
Prim’s algorithm and Dijkstra’s algorithm are similar because:
a)
Both use BFS
b)
Both use a greedy approach
c)
Both work only on DAGs
d)
Both require negative weights
24.
Kruskal’s algorithm requires which data structure for efficiency?
a)
Stack
b)
Disjoint-set (Union-Find)
c)
Queue
d)
Heap only
25.
In a flow network, the source and sink refer to:
a)
Vertices with maximum degree
b)
Start and end points of flow
c)
Vertices with no incoming edges
d)
Vertices with no outgoing edges
26.
Which of the following is not a property of a tree?
a)
It is connected
b)
It has no cycles
c)
It is a directed graph
d)
It has n-1 edges for n vertices
27.
A directed acyclic graph (DAG) is:
a)
A graph with no cycles
b)
A graph with directed cycles
c)
A tree
d)
A graph with self-loops
28.
Two vertices are strongly connected if:
a)
There is a path from one to the other
b)
There is a path in both directions
c)
They share an edge
d)
They have the same degree
29.
A parallel edge refers to:
a)
Two edges sharing the same endpoints
b)
Two edges with different endpoints
c)
An edge with weight zero
d)
An edge forming a cycle
30.
A spanning tree of a graph:
a)
Contains all edges of the graph
b)
Contains all vertices and is acyclic
c)
Is always weighted
d)
Is disconnected
31.
A connected component is:
a)
A subgraph where every vertex is reachable from every other vertex
b)
A graph with no edges
c)
A graph with cycles only
d)
A disconnected graph
32.
A simple cycle must satisfy:
a)
All vertices are distinct except the first and last
b)
All edges are distinct
c)
Both a and b
d)
None of the above
33.
Which representation is best for dense graphs?
a)
Adjacency list
b)
Adjacency matrix
c)
Edge list
d)
Incidence list
34.
Space complexity of an adjacency matrix for n vertices with m edges is:
a)
O(n+m)
b)
O(n^2)
c)
O(m^2)
d)
O(n log n)
35.
For an undirected graph, the sum of degrees m of all vertices n equals:
a)
m
b)
2m
c)
n
d)
n^2
36.
Maximum number of edges in a directed simple graph with n vertices is:
a)
n(n-1)/2
b)
n(n-1)
c)
n^2
d)
2n
37.
The relaxation step in shortest path algorithms means:
a)
Removing an edge from the graph
b)
Updating distance if a shorter path is found
c)
Adding a new vertex
d)
Ignoring cycles
38.
A topological sort is used for:
a)
Weighted graphs
b)
DAGs
c)
Undirected graphs
d)
Strongly connected graphs
39.
In a flow network, the capacity constraint means:
a)
Flow on an edge cannot exceed its capacity
b)
Flow must equal capacity
c)
Flow can be negative
d)
Flow is always zero
40.
The unused capacity of an edge in a flow network is:
a)
Augmented capacity
b)
Constrained flow
c)
The residual
d)
Always unusable
Reset
