Data Structures Multiple Choice Questions and Answers on Undirected Graph

1. 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: d

Explanation: There can be at most, n*n edges in an undirected graph.
2. 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: b

Explanation: Euler’s Identity says V – E + R = 1+ number of connected components.
3. 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: d

Explanation: If the start and end vertices for the path are same the answer would be 0 otherwise 2.
4. 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: b

Explanation: statements iii) and v) are correct.
5. All paths and cyclic graphs are bipartite graphs.

a) True
b) False
Answer: b

Explanation: Only paths and even cycles are bipartite graphs.
6. 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: a

Explanation: Only the first and the last vertex would have degree 1, others would be of degree 2.
7. All trees with n vertices consists of n-1 edges.

a) True
b) False
Answer: a

Explanation: A trees is acyclic in nature.
8. Which of the following graphs are isomorphic to each other?

Undir_1.html   draw.io
a) fig 1 and fig 2
b) fig 2 and fig 3
c) fig 1 and fig 3
d) fig 1, fig 2 and fig 3
Answer: d

Explanation: All three graphs are Complete graphs with 4 vertices.
9. In the given graph which edge should be removed to make it a Bipartite Graph?

184_4.html   draw.io
a) A-C
b) B-E
c) C-D
d) D-E
Answer: a

Explanation: The resultant graph would be a Bipartite Graph having {A,C,E} and {D, B} as its subgroups.
10. 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: b

Explanation: A graph can be checked for being Bipartite by seeing if it is 2-colorable or not, which can be obtained with the help of BFS.

Related

Multiple choice Questions and Answers on Provisioning Cloud Storage of Cloud Computing for Freshers

1. Which of the following cloud storage is mainly meant for developers and to support applications built using Web services ? a) Managedb) Unmanagedc) Diskd) All of the mentioned Answer: a Explan...

Computer Fundamentals Multiple choice Questions and Answers on Optical Disks for Freshers

1. A ____________ disk consists of a circular disk, which is coated with a thin metal or some other material that is highly reflective. a) magneticb) opticalc) compactd) hard Answer: b Explanatio...

Multiple choice Questions and Answers on Cloud Storage in the Digital Universe of Cloud Computing for Freshers

1. Which of the following is storage data interchange interface for stored data objects ? a) OCCb) OCCIc) OCMId) All of the mentioned Answer: b Explanation: OCCI stands for Open Cloud Computing I...

Post a Comment

emo-but-icon
:noprob:
:smile:
:shy:
:trope:
:sneered:
:happy:
:escort:
:rapt:
:love:
:heart:
:angry:
:hate:
:sad:
:sigh:
:disappointed:
:cry:
:fear:
:surprise:
:unbelieve:
:shit:
:like:
:dislike:
:clap:
:cuff:
:fist:
:ok:
:file:
:link:
:place:
:contact:

item