# Data Structures MCQ Questions and Answers

The Free download links of Data Structures MCQ Questions and Answers Papers enclosed below. Candidates who are going to start their preparation for the Data Structures MCQ papers can use these links. Download the Data Structures MCQ Papers PDF along with the Answers. Data Structures MCQ Papers are updated here. A vast number of applicants are browsing on the Internet for the Data Structures MCQ Question Papers & Syllabus. For those candidates, here we are providing the links for Data Structures MCQ Papers. Improve your knowledge by referring the Data Structures MCQ Question papers. ## MCQ Questions and Answers on Data Structures

1. The number of vertices of odd degree in a graph is
(a) always even
(b) either even or odd
(c) always odd
(d) always zero

2. A graph in which all nodes are of equal degree is known as
(a) Multigraph
(b) regular graph
(c) non regular graph
(d) complete graph

3. A vertex of degree one is called as
(a) Pendant
(b) null vertex
(c) isolated vertex
(d) coloured vertex

4. The maximum degree of any node in a simple graph with n vertices is
(a) n – 1
(b) n/2
(c) n
(d) n – 2

5. Two isomorphic graphs must have
(a) the same number of vertices
(b) an equal number of vertices
(c) the same number of edges
(d) all of the above

6. The terminal vertices of a path are of degree
(a) One
(b) Zero
(c) Two
(d) more than four

7. If there exists at least one path between every pair of vertices in a graph, the graph is known
(a) complete graph
(b) disconnected graph
(c) connected graph
(d) Eular graph

8. A simple graph with n vertices and k components can have at most
(a) n edges
(b) n-k edges
(c) (n-k) (n-k-1)/2 edges.
(d) (n-k) (n-k + 1)/2 edges

9. A given connected graph G is a Euler graph if and only if all vertices of G are of
(a) same degree
(b) odd degree
(c) even degree
(d) different degree

10. A circuit in a connected graph which includes every vertex of the graph is known as
(a) Eular
(b) Hamiltonian
(c) Unicursal
(d) Clique

11. The length of a Hamiltonian path (if exists) in a connected graph of n vertices is
(a) n-1
(b) n + 1
(c) n
(d) n/2

12. A simple graph in which there exists an edge between every pair vertices is called a (an)
(a) incomplete graph
(b) Eular graph
(c) complete graph
(d) planner graph

13. The total number of edges in a complete graph of n vertices is
(a) n
(b) n(n+1)/2
(c) n²/2
(d) n(n-1)/2

14. A tree with n nodes has
(a) n/2 edges
(b) n edges
(c) n – 1 edges
(d) n + 1 edges

15. The number of paths between any pair of nodes in a tree on n nodes is
(a) 0
(b) 1
(c) (n-1)
(d) n

16. A complete graph with five vertices is
(a) nonplanar
(b) a non-regular graph
(c) planar
(d) a tree

17. Kuratowski’s first graph is the nonplanar complete graph with the smallest number of vertices. The number of vertices is
(a) 4
(b) 6
(c) 5
(d) 7

18. f a graph G does not contain either Kuratowski’s two graphs or any graph isomorphic to them, the graph G is then
(a) planar graph
(b) Eular graph
(c) non planar graph
(d) regular graph

19. The number of regions is a connected planar graph with n vertices and e edges is
(a) n + e
(b) e-n-2
(c) e-n
(d) e/2

20. The number of circuits in a tree with n nodes is
(a) zero.
(b) n-1
(c) 1
(d) n/2

21. A graph is a tree if and only if it
(a) is completely connected
(b) contains a circuit
(c) is minimally connected
(d) is planar

22. The minimum number of spanning trees in a connected graph with n nodes is
(a) 1
(b) n-1
(c) 2
(d) n/2

23. The rank of a graph with n vertices, e edges and k components is
(a) n
(b) n-1
(c) e-n+k
(d) n + k

24. The nullity of a graph with n vertices, e edges and k components is
(a) n
(b) n-k
(c) e-n + k
(d) n + k

25. The number of elements (edges) in a cutset of a tree with n vertices is
(a) 1
(b) n/2
(c) n-1
(d) n

26. Let a graph G has edge connectivity and node connectivity. Then
(a) α < ß
(b) α = ß
(c) α ≥ ß
(d) α ≤ ß

27. What is the edge connectivity of a complete graph with n vertices?
(a) 1
(b) n + 1
(c) n-1
(d) n(n+1)/2

28. If A(G) is an incident matrix of a connected graph G with n vertices, the rank of A(G) is
(a) 1
(b) n-1
(c) 2
(d) n

29. If G is a disconnected graph with n vertices and k components, the rank of the incident matrix A(G) of the graph is
(a) n-k-1
(b) n + k-1
(c) n-k
(d) n + k

30. A graph with n vertices and n-1 edges that is not a tree, is
(a) Connected
(b) Eular
(c) Disconnected
(d) a circuit

31. If B is a circuit matrix of a graph with k components, e edges and n vertices, the rank of B is
(a) n-k
(b) e-n+k
(c) e-n-k
(d) e+n-k

32. Consider a graph G having cutset matrix C(G) and incidence matrix A(G). The rank of C(G) is
(a) same as the rank of A(G)
(b) more than the rank of A(G)
(c) independent of the rank of A(G)
(d) less than the rank of A(G)

33. Let X be the adjacency matrix of a graph G with no self loops. The entries along the principle diagonal of X are
(a) all zeros
(b) both zeros and ones
(c) all ones
(d) different

34. A graph consisting of only isolated n vertices is
(a) k/2
(b) k
(c) k-1
(d) 1

35. If a graph requires k different colours for its proper colouring, then the chromatic number of the graph is
(a) 1-chromatic
(b) 3-chromatic
(c) 2-chromatic
(d) n-chromatic

36. A graph with one or more edges (wothout self loop) is a least
(a) 2-chromatic
(b) n-chromatic
(c) 1-chromatic
(d) 3-chromatic

37. A complete graph with n vertices is
(a) 2-chromatic
(b) (n-1) chromatic
(c) n/2 chromatic
(d) n-chromatic

38. 1f d_{max} is the maximum degree of the vertices in a graph G, the chromatic number of G is
(a) equal to d_{max}
(b) less than or equal to d_{max}
(c) greater than d_{max}
(d) less than or equal to d_{max} + 1

39. If the vertex set V of a graph can be decomposed into two subsets V₁ and V₂ such that every edge in G joins a vertex in V₁ with a vertex in V₂, the graph is called
(a) Bipartite
(b) 1-chromatic
(c) tri-partite
(d) V-partite

40. A covering of an n-vertex graph has at least
(a) n/2 edges
(b) [(n-1)/2] edges
(c) [n/2] edges
(d) n edges

41. The number of colors required to properly color the vertices of every planar graph is
(a) 2
(b) 3
(c) 5
(d) 4

42. 1f A(G) is the incidence matrix of a connected digraph of n vertices the rank of A(G) is
(a) n
(b) 2
(c) n/2
(d) n-1

43. The number of different rooted labeled trees with n vertices is
(a) 2^{n-1}
(b) 2^{n}
(c) n^{n-1}
(d) n^{n}

44. Let A = {1, 2, 3, 4, 5} Which of the following sets equal A?
(a) {4, 1, 2, 3, 5}
(b) {3, 2, 4, 1}
(c) {5, 1, 3, 2, 1}
(d) {3, 4, 5}

45. Which of the following sets are empty?
(a) {x|x is a real number and x² – 1 = 0}
(b) {x|x is a real number and x = 2x + 1}
(c) {x|x is a real number and x² + 1 = 0}
(d) {x|x is a real number and x² = -9}

46. A computer company must hire 25 programmers to handle systems programming tasks and 40 programmers for applications programming. Out of these, 10 will be expected to perform tasks of each type. How many programmers must be hired?
(a) 55
(b) 45
(c) 65
(d) 35

47. In how many ways can six people be seated in a circle?
(a) 720
(b) 120
(c) 360
(d) 12

48. In how many ways can six men and six women be seated in a row if any person may sit next to any other person?
(a) 12!
(b) 6!
(c) 12!/2
(d) 6! /4

49. Which of the following tool is used to specify lexical analyzers for a variety of languages
(a) Yaac
(b) TeX
(c) Lex
(d) EQN

50. Any deterministic finite automata for the regular expression (al b)* a(a| b)(a| b)… (a b), where there are n-1 (a| b)’s at the end, must have at least
(a) n states
(b) n^{2} states
(c) 2^{n} states
(d) 2^{2n} states