Q1. In a simple graph, the number of edges is equal to twice the sum of the degrees of the vertices..
A. TRUE.
B. FALSE.
C. Nothing can be said.
D. None of the mentioned.
Answer= FALSE
Q2. A connected planar graph having 6 vertices, 7 edges contains _____________ regions..
A. 15.
B. 3.
C. 1.
D. 11.
Answer= 3
Q3. If a simple graph G, contains n vertices and m edges, the number of edges in the Graph G'(Complement of G) is ___________.
A. (n*n-n-2*m)/2.
B. (n*n+n+2*m)/2.
C. (n*n-n-2*m)/2.
D. (n*n-n+2*m)/2.
Answer= (n*n-n-2*m)/2
Q4. Which of the following properties does a simple graph not hold?.
A. Must be connected.
B. Must be unweighted.
C. Must have no loops or multiple edges.
D. All of the mentioned.
Answer= Must be connected
Q5. What is the maximum number of edges in a bipartite graph having 10 .
A. vertices?.
B. 24.
C. 21.
D. 25.
Answer= 16
Q6. Which of the following is true?.
A. A graph may contain no edges and many vertices.
B. A graph may contain many edges and no vertices.
C. A graph may contain no edges and no vertices.
D. None of the mentioned.
Answer= A graph may contain many edges and no vertices
Q7. For a given graph G having v vertices and e edges which is connected and has no cycles, which of the following statements is true?.
A. v=e.
B. v = e+1.
C. v + 1 = e.
D. None of the mentioned.
Answer= v = e+1
Q8. For which of the following combinations of the degrees of vertices would the connected graph be eulerian?.
A. 1,2,3.
B. 2,3,4.
C. 2,4,5.
D. 1,3,5.
Answer= 1,2,3
Q9. A graph with all vertices having equal degree is known as a __________.
A. Multi Graph.
B. Regular Graph.
C. Simple Graph.
D. Complete Graph.
Answer= Regular Graph
Q10. Which of the following ways can be used to represent a graph?.
A. Adjacency List and Adjacency Matrix.
B. Incidence Matrix.
C. Adjacency List, Adjacency Matrix as well as Incidence Matrix.
D. None of the mentioned.
Answer= Adjacency List, Adjacency Matrix as well as Incidence Matrix
Q11. The number of elements in the adjacency matrix of a graph having 7 vertices is __________.
A. 7.
B. 14.
C. 36.
D. 49.
Answer= 49
Q12. Adjacency matrix of all graphs are symmetric..
A. FALSE.
B. TRUE.
C. Nothing can be said.
D. None of the mentioned.
Answer= FALSE
Q13. The time complexity to calculate the number of edges in a graph whose information in stored in form of an adjacency matrix is ____________.
A. O(V).
B. O(E2).
C. O(E).
D. O(V2).
Answer= O(V2)
Q14. For the adjacency matrix of a directed graph the row sum is the _________ degree and the column sum is the ________ degree..
A. in, out.
B. out, in.
C. in, total.
D. total, out.
Answer= out, in
Q15. What is the maximum number of possible non zero values in an adjacency matrix of a simple graph with n vertices?.
A. (n*(n-1))/2.
B. (n*(n+1))/2.
C. n*(n-1).
D. n*(n+1).
Answer= n*(n-1)
Q16. On which of the following statements does the time complexity of checking if an edge exists between two particular vertices is not, depends?.
A. Depends on the number of edges.
B. Depends on the number of vertices.
C. Is independent of both the number of edges and vertices.
D. It depends on both the number of edges and vertices.
Answer= Is independent of both the number of edges and vertices
Q17. In the given connected graph G, what is the value of rad(G) and diam(G)?.
A. 2, 3.
B. 3, 2.
C. 2, 2.
D. 3, 3.
Answer= 2, 3
Q18. Given an adjacency matrix A = [ [0, 1, 1], [1, 0, 1], [1, 1, 0] ], how many ways are there in which a vertex can walk to itself using 2 edges..
A. 2.
B. 4.
C. 6.
D. 8.
Answer= 6
Q19. If A[x+3][y+5] represents an adjacency matrix, which of these could be the value of x and y..
A. x=5, y=3.
B. x=3, y=5.
C. x=3, y=3.
D. x=5, y=5.
Answer= x=5, y=3
Q20. Two directed graphs(G and H) are isomorphic if and only if A=PBP-1, where P and A are adjacency matrices of G and H respectively..
A. TRUE.
B. FALSE.
C. Nothing can be said.
D. None of the mentioned.
Answer= TRUE
Q21. Incidence matrix and Adjacency matrix of a graph will always have same dimensions?.
A. TRUE.
B. FALSE.
C. Nothing Can be said.
D. None of the mentioned.
Answer= FALSE
Q22. The column sum in an incidence matrix for a simple graph is __________.
A. depends on number of edges.
B. always greater than 2.
C. equal to 2.
D. equal to the number of edges.
Answer= equal to 2
Q23. What are the dimensions of an incidence matrix?.
A. Number of edges*number of edges.
B. Number of edges*number of vertices.
C. Number of vertices*number of vertices.
D. None of the mentioned statements.
Answer= Number of edges*number of vertices
Q24. The column sum in an incidence matrix for a directed graph having no self loop is __________.
A. 0.
B. 1.
C. 2.
D. equal to the number of edges.
Answer= 0
Q25. Time complexity to check if an edge exists between two vertices would be ___________.
A. O(V*V).
B. O(V+E).
C. O(1).
D. O(E).
Answer= O(E)
Q26. If a connected Graph (G) contains n vertices what would be the rank of its incidence matrix?.
A. n-1.
B. values greater than n are possible.
C. values less than n-1 are possible.
D. insufficient Information is given.
Answer= n-1
Q27. In the following DAG find out the number of required Stacks in order to represent it in a Graph Structured Stack..
A. 1.
B. 2.
C. 3.
D. 4.
Answer= 3
Q28. A Graph Structured Stack is a _____________.
A. Undirected Graph.
B. Directed Graph.
C. Directed Acyclic Graph.
D. Regular Graph.
Answer= Directed Acyclic Graph
Q29. If a Graph Structured Stack contains {1,2,3,4} {1,5,3,4} {1,6,7,4} and {8,9,7,4}, what would be the source and sink vertices of the DAC?.
A. Source - 1, 8 Sink - 7,4.
B. Source - 1 Sink - 8,4.
C. Source - 1, 8 Sink - 4.
D. None of the Mentioned.
Answer= Source - 1, 8 Sink - 4
Q30. Graph Structured Stack finds its application in _____________.
A. Bogo Sort.
B. Tomita's Algorithm.
C. Todd-Coxeter algorithm.
D. All of the mentioned.
Answer= Tomita's Algorithm
Q31. If in a DAG N sink vertices and M source vertices exists, then the number of possible stacks in the Graph Structured Stack representation would come out to be N*M..
A. TRUE.
B. FALSE.
C. Nothing Can be said.
D. None of the mentioned .
Answer= FALSE
Q32. The number of possible undirected graphs which may have self loops but no multiple edges and have n vertices is ________.
A. 2((n*(n-1))/2).
B. 2((n*(n+1))/2).
C. 2((n-1)*(n-1))/2).
D. 2((n*n)/2).
Answer= 2((n*n)/2)
Q33. Given a plane graph, G having 2 connected component, having 6 vertices, 7 edges and 4 regions. What will be the number of connected components?.
A. 1.
B. 2.
C. 3.
D. 4.
Answer= 2
Q34. Number of vertices with odd degrees in a graph having a eulerian walk is ________.
A. 0.
B. Can't be predicted.
C. 2.
D. either 0 or 2.
Answer= either 0 or 2
Q35. How many of the following statements are correct?i) All cyclic graphs are complete graphs.ii) All complete graphs are cyclic graphs.iii) All paths are bipartite.iv) All cyclic graphs are bipartite.v) There are cyclic graphs which are complete..
A. 1.
B. 2.
C. 3.
D. 4.
Answer= 2
Q36. All paths and cyclic graphs are bipartite graphs..
A. TRUE.
B. FALSE.
C. Nothing Can be said.
D. None of the mentioned.
Answer= FALSE
Q37. What is the number of vertices of degree 2 in a path graph having n vertices,here n>2..
A. n-2.
B. n.
C. 2.
D. 0.
Answer= n-2
Q38. All trees with n vertices consists of n-1 edges..
A. TRUE.
B. FALSE.
C. Nothing Can be said.
D. None of the mentioned.
Answer= TRUE
Q39. What would the time complexity to check if an undirected graph with V vertices and E edges is Bipartite or not given its adjacency matrix?.
A. O(E*E).
B. O(V*V).
C. O(E).
D. O(V).
Answer= O(V*V)
Q40. Dijkstra's Algorithm will work for both negative and positive weights?.
A. TRUE.
B. FALSE.
C. Nothing Can be said.
D. None of the mentioned.
Answer= FALSE
Q41. A graph having an edge from each vertex to every other vertex is called a ___________.
A. Tightly Connected.
B. Strongly Connected.
C. Weakly Connected.
D. Loosely Connected.
Answer= Tightly Connected
Q42. What is the number of unlabeled simple directed graph that can be made with 1 or 2 vertices?.
A. 2.
B. 4.
C. 5.
D. 9.
Answer= 4
Q43. Floyd Warshall Algorithm used to solve the shortest path problem has a time complexity of __________.
A. O(V*V).
B. O(V*V*V).
C. O(E*V).
D. O(E*E).
Answer= O(V*V*V)
Q44. All Graphs have unique representation on paper..
A. TRUE.
B. FALSE.
C. Nothing Can be said.
D. None of the mentioned.
Answer= FALSE
Q45. Assuming value of every weight to be greater than 10, in which of the following cases the shortest path of a directed weighted graph from 2 vertices u and v will never change?.
A. add all values by 10.
B. subtract 10 from all the values.
C. multiply all values by 10.
D. in both the cases of multiplying and adding by 10.
Answer= multiply all values by 10
Q46. What is the maximum possible number of edges in a directed graph with no self loops having 8 vertices?.
A. 28.
B. 64.
C. 256.
D. 56.
Answer= 56
Q47. Every Directed Acyclic Graph has at least one sink vertex..
A. TRUE.
B. FALSE.
C. Nothing can be said.
D. None of the mentioned.
Answer= TRUE
Q48. With V(greater than 1) vertices, how many edges at most can a Directed Acyclic Graph possess? .
A. (V*(V-1))/2 .
B. (V*(V+1))/2 .
C. (V+1)C2 .
D. (V-1)C2 .
Answer= (V*(V-1))/2
Q49. The topological sorting of any DAG can be done in ________ time. .
A. cubic .
B. quadratic .
C. linear .
D. logarithmic .
Answer= linear
Q50. If there are more than 1 topological sorting of a DAG is possible, which of the following is true..
A. Many Hamiltonian paths are possible.
B. No Hamiltonian path is possible.
C. Exactly 1 Hamiltonian path is possible.
D. Given information is insufficient to comment anything.
Answer= No Hamiltonian path is possible
Q51. Which of the given statement is true?.
A. All the Cyclic Directed Graphs have topological sortings.
B. All the Acyclic Directed Graphs have topological sortings.
C. All Directed Graphs have topological sortings.
D. None of the given statements is true.
Answer= All the Cyclic Directed Graphs have topological sortings
Q52. For any two different vertices u and v of an Acyclic Directed Graph if v is reachable from u, u is also reachable from v?.
A. TRUE.
B. FALSE.
C. Nothing can be said.
D. None of the mentioned.
Answer= FALSE
Q53. What is the value of the sum of the minimum in-degree and maximum out-degree of an Directed Acyclic Graph?.
A. Depends on a Graph.
B. Will always be zero.
C. Will always be greater than zero.
D. May be zero or greater than zero.
Answer= Will always be zero
Q54. In which of the following does a Directed Acyclic Word Graph finds its application in?.
A. String Matching.
B. Number Sorting.
C. Manipulations on numbers.
D. None of the mentioned.
Answer= String Matching
Q55. What is the number of words that can be formed from the given Directed Acyclic Word Graph?.
A. 2.
B. 4.
C. 12.
D. 7.
Answer= 4
Q56. Determine the longest string which is described by the given Directed Acyclic Word Graph..
A. BATS.
B. BOATS.
C. BOT.
D. None of the mentioned.
Answer= BATS
Q57. What is time complexity to check if a string(length S1) is a substring of another string(length S2) stored in a Directed Acyclic Word Graph, given S2 is greater than S1?.
A. O(S1).
B. O(S2).
C. O(S1+S2).
D. O(1).
Answer= O(S1)
Q58. In which of the following case does a Propositional Directed Acyclic Graph is used for?.
A. Representation of Boolean Functions.
B. String Matching.
C. Searching.
D. Sorting of number.
Answer= Representation of Boolean Functions
Q59. Every Binary Decision Diagram is also a Propositional Directed Acyclic Graph..
A. TRUE.
B. FALSE.
C. Nothing Can be said.
D. None of the mentioned.
Answer= TRUE
Q60. In a Propositional Directed Acyclic Graph Leaves maybe labelled with a boolean variable..
A. TRUE.
B. FALSE.
C. Nothing can be said.
D. None of the mentioned.
Answer= TRUE
Q61. Given Adjacency matrices determine which of them are PseudoGraphs?i) {{1,0} {0,1}}ii) {{0,1}{1,0}}iii) {{0,0,1}{0,1,0}{1,0,0}}.
A. only i).
B. ii) and iii).
C. i) and iii).
D. i) ii) and iii).
Answer= i) and iii)
Q62. All undirected Multigraphs contain eulerian cycles..
A. TRUE.
B. FALSE.
C. Nothing can be said.
D. None of the mentioned.
Answer= TRUE
Q63. Determine the number of vertices for the given Graph or Multigraph?G is a 4-regular Graph having 12 edges..
A. 3.
B. 6.
C. 4.
D. Information given is insufficient.
Answer= 6
Q64. Which of the following statement is true..
A. There exists a Simple Graph having 10 vertices such that minimum degree of the graph is 0 and maximum degree is 9.
B. There exists a MultiGraph having 10 vertices such that minimum degree of the graph is 0 and maximum degree is 9.
C. There exists a MultiGraph as well as a Simple Graph having 10 vertices such .
D. that minimum degree of the graph is 0 and maximum degree is 9.
Answer= None of the mentioned
Q65. Given Adjacency matrices determine which of them are PseudoGraphs?i) {{1,0} {0,1}}ii) {{0,1}{1,0}}iii) {{0,0,1}{0,1,0}{1,0,0}}.
A. only i).
B. ii) and iii).
C. i) and iii).
D. i) ii) and iii).
Answer= i) and iii)
Q66. Possible number of labelled simple Directed, Pseudo and Multigarphs .
A. exist having 2 vertices?.
B. 3, Infinite, 4.
C. 4, 3, Infinite.
D. 4, Infinite, infinite.
Answer= 4, Infinite, Infinite
Q67. Which of the following is a HyperGraph, where V is the set of vertices, E is the set of edges?.
A. V = {v1, v2, v3} E = {e1, e2} = {{v2, v3} {v1, v3}}.
B. V = {v1, v2} E = {e1} = {{v1, v2}}.
C. V = {v1, v2, v3} E = {e1, e2, e3} = {{v2, v3}{v3, v1}{v2, v1}}.
D. All of the mentioned.
Answer= All of the mentioned
Q68. What would be the Incidence Matrix of the given HyperGraph?V = {x,y,z} E = {{x,y}{y}{x,z}{z,y}}.
A. {{1,0,1,0}, {1,1,0,1}, {0,0,1,1}}.
B. {{1,1,0,0}, {0,1,0,0}, {1,1,1,0}}.
C. {{0,1,0,1}, {0,0,1,0}, {1,1,0,0}}.
D. None of the Mentioned.
Answer= {{1,0,1,0}, {1,1,0,1}, {0,0,1,1}}
Q69. What is the degree sequence of the given HyperGraph, in non-increasing order.V = {v1,v2,v3,v4,v5,v6} E = {{v1,v4,v5} {v2,v3,v4,v5} {v2} {v1} {v1,v6}}.
A. 3,2,1,1,1,1.
B. 3,2,2,2,1,1.
C. 3,2,2,2,2,1.
D. 3,2,2,1,1,1.
Answer= 3,2,2,2,1,1
Q70. MultiGraphs having self-loops are called PseudoGraphs?.
A. TRUE.
B. FALSE.
C. Nothing can be said.
D. None of the mentioned.
Answer= TRUE
Q71. Binary Decision Diagram is a type of __________.
A. Multigraph.
B. Cyclic Graph.
C. Directed Acyclic Graph.
D. Directed Acyclic Word Graph.
Answer= Directed Acyclic Graph
Q72. In which of the following case does a Binary Decision Diagram is used for?.
A. Representation of Boolean Functions.
B. String Matching.
C. Searching.
D. Sorting of number.
Answer= Representation of Boolean Functions
Q73. In a Binary Decision Diagram, how many types of terminal exists?.
A. 1.
B. 2.
C. 3.
D. 4.
Answer= 2
Q74. In a Binary Decision Diagrams 0 values by a _________ line and the 1 values are represented by a _________ line..
A. dashed, bold.
B. bold, dashed.
C. dotted, bold.
D. dotted, dashed.
Answer= dotted, bold
Q75. How many nodes are required to create a Binary Decision Tree having 4 variables?.
A. 24.
B. 24-1.
C. 25.
D. 25-1.
Answer= 25-1
Q76. Two or more And Inverter Graphs can represent same function..
A. TRUE.
B. FALSE.
C. Nothing can be said.
D. None of the mentioned.
Answer= TRUE
Q77. Size of an And Inverter Graph is the number of _______ gates and the number of logic levels is number of ________ gates on the __________ path from a primary input to a primary output..
A. AND, AND, average.
B. AND, OR, longest.
C. OR, OR, shortest.
D. AND, AND, longest.
Answer= AND, AND, longest
Q78. And Inverter Graph is a type of __________.
A. Multigraph.
B. Cyclic Graph.
C. Directed Acyclic Graph.
D. Directed Acyclic Word Graph.
Answer= Directed Acyclic Graph
Q79. The And Inverter Graph representation of a Boolean function is more efficient than the Binary Decision Diagram..
A. TRUE.
B. FALSE.
C. Nothing can be said.
D. None of the mentioned.
Answer= TRUE
Q80. Which of the following logical operation can be implemented by polynomial time graph manipulation algorithms using Binary Decision Diagrams?.
A. Conjunction.
B. Disjunction.
C. Negation.
D. All of the mentioned.
Answer= All of the mentioned
Q81. Where is linear searching used?.
A. When the list has only a few elements.
B. When performing a single search in an unordered list.
C. Used all the time.
D. When the list has only a few elements and When performing a single search in an unordered list.
Answer= When the list has only a few elements and When performing a single search in an unordered list
Q82. What is the best case for linear search?.
A. O(nlogn).
B. O(logn).
C. O(n).
D. O(1).
Answer= O(1)