1. : What is a graph in data structures?
(A) A collection of nodes and edges
(B) A linear data structure
(C) A data structure that stores data in a sorted manner
(D) A type of tree
2. : Which of the following represents a directed graph?
(A) A graph where edges have no direction
(B) A graph where edges point from one vertex to another
(C) A graph that forms a cycle
(D) A graph with weighted edges
3. : What is an undirected graph?
(A) A graph with directed edges
(B) A graph where edges have no direction
(C) A graph with weighted edges
(D) A graph that contains cycles
4. : What is the degree of a vertex in a graph?
(A) The number of edges connected to the vertex
(B) The number of vertices connected to the graph
(C) The length of the longest path
(D) The total number of vertices in the graph
5. : What is a weighted graph?
(A) A graph with no edges
(B) A graph where edges have weights assigned to them
(C) A graph that only contains directed edges
(D) A graph that forms a cycle
6. : What is the main purpose of a graph traversal algorithm?
(A) To find the shortest path
(B) To visit all the vertices in a graph
(C) To sort the vertices
(D) To remove edges
7. : Which of the following algorithms is used for finding the shortest path in a graph?
(A) Depth-first search
(B) Breadth-first search
(C) Dijkstra’s algorithm
(D) Prim’s algorithm
8. : What is a cycle in a graph?
(A) A path that visits each vertex exactly once
(B) A path that starts and ends at the same vertex
(C) A graph with no edges
(D) A directed graph
9. : What is the time complexity of depth-first search (DFS) in a graph with V vertices and E edges?
(A) O(V)
(B) O(E)
(C) O(V + E)
(D) O(V * E)
10. : What is the time complexity of breadth-first search (BFS) in a graph with V vertices and E edges?
(A) O(V)
(B) O(E)
(C) O(V + E)
(D) O(V * E)
11. : What type of data structure is commonly used to implement a graph?
(A) Array
(B) Linked list
(C) Hash table
(D) Both A and B
12. : What is an adjacency matrix?
(A) A list of edges in a graph
(B) A 2D array representing the connection between vertices
(C) A list of vertices
(D) A representation of weights in a graph
13. : What is an adjacency list?
(A) A 2D array representation of a graph
(B) A collection of lists where each list corresponds to a vertex
(C) A matrix representing the graph
(D) A table of edges
14. : Which traversal algorithm would you use to find the shortest path in an unweighted graph?
(A) Depth-first search
(B) Breadth-first search
(C) Dijkstra’s algorithm
(D) A* search
15. : What is a complete graph?
(A) A graph with no edges
(B) A graph where every pair of vertices is connected by an edge
(C) A directed graph
(D) A graph that forms a cycle
16. : What is a bipartite graph?
(A) A graph with only two vertices
(B) A graph whose vertices can be divided into two disjoint sets
(C) A graph with cycles
(D) A graph where all edges are directed
17. : What is a spanning tree?
(A) A tree that connects all vertices with minimum edges
(B) A tree that contains all edges of the graph
(C) A cycle that includes all vertices
(D) A disconnected subgraph
18. : What algorithm is commonly used to find the minimum spanning tree?
(A) Dijkstra’s algorithm
(B) Prim’s algorithm
(C) Kruskal’s algorithm
(D) Both B and C
19. : In a graph, what is the difference between a path and a cycle?
(A) A path can have repeated vertices, while a cycle cannot
(B) A path cannot have repeated vertices, while a cycle can
(C) Both paths and cycles are the same
(D) A cycle is always longer than a path
20. : What is the purpose of the Floyd-Warshall algorithm?
(A) To find the shortest path between two specific vertices
(B) To find the shortest path between all pairs of vertices
(C) To find the maximum flow in a network
(D) To detect cycles in a graph