Unit 4 graph mcqs - Dm unit 1 set mcqs sppu 3rd sem mcq of all units PDF

Preview

Summary

Dm unit 1 set mcqs sppu 3rd sem mcq of all units...

Description

Graph

SE Computer DM Unit - 4 Graph MCQs Question Id

1

Which one of the following is the example of non linear data structure

2

Let A be an adjacency matrix of a graph G. The ij th entry in the matrix AK , gives

4

An undirected graph G with n vertices and e edges is represented by adjacency list. What is the time required to generate all the connected components?

5 6 7

8

The maximum degree of any vertex in a simple graph with n vertices is The data structure required for Breadth First Traversal on a graph is A graph with n vertices will definitely have a parallel edge or self loop if the total number of edges are An adjacency matrix representation of a graph cannot contain information of :

Option A

Option B

Option C

Option D

Correct Option

Graph

Binary Tree

Queue

Link List

A

Length of a Eulerian path from vertex Vi to vertex Vj.

Length of a Hamiltonian cycle from vertex Vi to vertex Vj.

B

Shortest path of K The number of paths of length K from vertex Vi edges from vertex Vi to vertex Vj. to vertex Vj.

O (n)

O (e)

O (e+n)

O (e2 )

C

n–1

n+1

2n–1

n

A

queue (LIFO)

stack (FIFO)

array

tree

A

greater than n–1

less than n(n–1)

greater than n(n–1)/2

less than n2/2

A

nodes

edges

direction of edges

parallel edges

D

Page 1

Graph

9 10 11

12

13

14

A queue is a,

FIFO (First In First Out) LIFO (Last In First Out) list list In Breadth First Search of Graph, which of the following data structure is Stack. Queue. used? For an undirected graph G with n vertices and e edges, the sum of the ne 2n degrees of each vertex is Indicate which, if any, of the following A {1,3}B {2,4} five graphs G = (V,E, ), |V | = 5, is n {1,2}b {1,2}c {2,3}d C{1,2}D{2,3} E{3,5}F {3,4}e {3,4}a {4,5} isomorphic to any of the other four. t {4,5} A graph with V = {1, 2, 3, 4} is described by = a {1,2} b {1,2} c {1,4} d {2,3} e {3,4} f {3,4}How many Hamiltonian cycles does it have? A graph with V = {1, 2, 3, 4} is described by = a {1,2} b {1,2} c {1,4} d {2,3} e {3,4} f {3,4} It has weights on its edges given by = a b c d e f 3 2 1 2 4 2 . How many minimum spanning trees does it have?

Ordered array.

Linear tree.

A

Linked List.

None of the above.

B

2e

en

C

b {4,5}f {1,3} e {1,3} d {2,3}c {2,4}a {4,5}

 1 {1,}2 {2,3}3 {2,3} 4{3,4} 5{4,5}6 {4,5}

A

1

2

4

16

C

2

3

4

5

B

Page 2

Graph

16 18 19 20

21

22

23 24 25

For which of the following does there exist a simple graph G = (V,E) satisfying the specified conditions? The number of simple digraphs with |V | = 3 and exactly 3 edges is The number of oriented simple graphs with |V | = 3 is

It has 7 vertices, 10 It is connected and has It has 6 vertices, 11 It has 3 components 20 edges, and more than 10 edges 5 vertices and edges, and more than vertices and 16 edges. two components. fewer than 6 cycles. one component. 92

88

80

84

D

27

24

21

18

D

50

60

70

C

5

6

7

C

b {4,5} f {1,3} e {1,3} d {2,3} c {2,4} a {4,5}.

a {1,2} b {2,3} c {1,2} d {2,3} e {3,4} f {1,5} .

A

The number of oriented simple graphs 40 with |V | = 4 and 2 edges is Compute the total number of bicomponents in all of the following three simple graphs, G = (V,E) with |V | = 5. For each graph 4 the edge sets are as follows: E = {1, 2}, {2, 3}, {3, 4}, {4, 5}, {1, 3}, {1, 5}, {3, 5} Indicate which, if any, of the following a {1,2} b {2,3} c {1,2} five graphs G = (V,E, ), |V | = 5, isot d {1,3} e {2,3} f {4,5}. connected. Indicate which, if any, of the following five graphs G = (V,E, ), |V | = 5, have an Eulerian circuit. A graph is The degree of a vertex in a graph is

27

series of edges that connect two vertices is called

28

To design a communications network that joins all nodes without excessive lines, we must find a

D

b{4,5} a {1,3} e {1,3} d {2,3} c {2,5} f {4,5}.

F{1,2} B {1,2} C {2,3} D{3,4} E {4,5} A {4,5}.

b {4,5} f {1,3} e {1,3} d {2,3} c {2,4} a {4,5}.

1 {1,2} 2 {1,2} 3 {2,3} 4 {3,4}5 {4,5} 6 {4,5}.

a {1,3} b {3,4} c{1,2} d {2,3} e {3,5} f {4,5}.

D

a set of integers;

a set of integers;

a set of vertices and a set of edges;

a set of edges;

C

the number of vertices in its graph;

the number of other vertices incident to it

the number of paths;

the number of distinct connected subgraphs;

B

a path;

a cycle;

a connection;

a tree;

A

path;

minimal spanning three;

expression tree;

search tree

B

Page 3

Graph

29 30 32 33 34

A series of edges that form a path from a vertex to itself is A weighted graph has an adjacency matrix that is A graph may be fully represented by The prerequesite relationships among required courses in the Computer Science major form a Graph path search involves finding a

36

Graphs for which bijections of a special kind exist between their sets of vertices and edges are

37

Graphs that have the same structure are

38

Graph isomorphism invariant properties include

39

The reflexive transitive closure of . maps from

a tree;

B

real numbers and .;

booleans;

A C

a spanning path;

a cycle;

a connection;

integers;

vertices;

its vertices;

its edges;

an adjacency matrix;

the degrees of its vertices;

binary tree;

linked list;

directed acyclic graph;

weighted graph;

C

set of vertices;

sequence of vertices;

set of edges;

minimal set of edges;

B

nested;

transitive;

undecidable;

isomorphic

D

nested;

transitive;

undecidable;

isomorphic

C

having the same numbers of vertices and edges;

satisfiability;

reachability;

well ordering;

A

states to states;

states and symbols to states;

states and strings to states;

states and symbols to symbols;

none of these

40

How many edges are there in an undirected graph with two vertices of degree 7, four vertices of degree 5, and the remaining four vertices of degree is 6?

29

30

64

24

A

42

Suppose v is an isolated vertex in a graph, then the degree of v is:

0

1

2

3

A

Page 4

Graph

43

In an undirected graph the number of nodes with odd degree must be

44

Which of the following statement is true:

45

The length of Hamiltonian Path in a connected graph of n vertices is

46

A graph with one vertex and no edges is:

47

A complete graph of n vertices should have __________ edges. A Euler graph is one in which

48 49

A spanning tree of a graph is one that includes In multigraph-----------------------

50 In Pseudographs-----------------------

51 Simple graph -----------------------

52 56

How many nodes are necessary to construct 8 edges in which each node is of degree 2

Zero

Odd

Every graph is not its The terminal vertex of a graph are of degree two. own subgraph

Prime

Even

D

A tree with n vertices has n edges.

A single vertex in graph G is a subgraph of G.

D

n–1

n

n+1

n/2

A

multigraph

digraph

isolated graph

trivial graph

D

n-1

n

n(n-1)/2

n(n+1)/2

C

All the vertices are of odd degree

All the vertices are of even degree

D

Only the vertices of odd degree

Only the vertices of even degree

A

Only two vertices are of Only two vertices are of even degree and rests odd degree and rests are odd are even All the vertices of the graph more than one edge can join two vertices, but no edge can join to itself . more than one edge can join two vertices, but no edge can join to itself . self loops as well as parallel edges are allowed.

All the edges of the graph parallel edges allowed but not selfloops

A or B

None of these

C

self loops as well as parallel edges are allowed.

A&B

None of these

B

no self loop and no parallel edges are present.

A&B

None of these

B

8

16

32

B

4

Page 5

Graph

If in a graph each edge has a direction, the graph known as ___________

directed graph

simple graph

weighted graph

None of these

A

directed graph

simple graph

weighted graph

Regular graph

D

V1∩ V2

V1∪ V2

V1∩ V2 & V1∪ V2

None of these

C

null graph

bipartite graph

simple graph

None of these

A

8

16

24

32

C

63

A graph G is called ______________if the edges do not repeat in the path.

Circuit

Simple path

A&B

None of these

B

64

A closed path is known as __________

Circuit

Simple path

A&B

None of these

A

66

A path is known as ________ if every edge of the graph appers exactly once in the path.

Hamiltonoin Circuit

Hamiltonoin path

Eulerian Circuit

Eulerian path

D

67

The circuit which contains every edge of the graph exactly once is called___________

Hamiltonoin Circuit

Hamiltonoin path

Eulerian Circuit

Eulerian path

C

69

A circuit in a connected graph G is a ________________ if it contains every vertex of G exactly once except the first and the last vertex

Hamiltonoin Circuit

Hamiltonoin path

Eulerian Circuit

Eulerian path

A

57

58

59

60 62

In a graph if degree of each vertex is same then the graph is known as________ G is a graph whose set of vertices is v. If V can be partitioned into two subsets V1 & V2 such that every edge of G joins V1 with V2 also______________ A graph with n vertices and no edge is known as _________________ How many edges has of the K4,6 graph.

Page 6...