University:
California State University, Northridge
Course:
COMP 182 | Data Structures and Program Design and Lab
Academic year:

2022
Views:

26

Pages:

8
Author:

NyiH

Question 1 What is the number of vertices of degree 2 in a path graph having n vertices,here n>2. п-2 On 02 00 Question 2 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? O(EE) O(VV) O(E) O(V) Question 3 A graph having an edge from each vertex to every other vertex is called a Tightly Connected Strongly Connected Weakly Connected Loosely Connected Question 4 What is the number of unlabeled simple directed graph that can be made with 1 or 2 vertices? 2 4 05 09 Question 5 Floyd Warshall Algorithm used to solve the shortest path problem has a time complexity of O(VV) O(V*V*V) O(EV) O(EE) Question 6 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? add all values by 10 subtract 10 from all the values multiply all values by 10 in both the cases of multiplying and adding by 10 Question 7 What is the maximum possible number of edges in a directed graph with no self loops having 8 vertices? 28 64 256 56 Question 8 What is the maximum number of edges present in a simple directed graph with 7 vertices if there exists no cycles in the graph? 21 07 6 49 Question 9 The topological sorting of any Directed Acyclic Graph can be done in time. cubic quadratic linear logarithmic Question 10 Which of the given statement is true? All the Cyclic Directed Graphs have topological sortings All the Acyclic Directed Graphs have topological sortings All Directed Graphs have topological sortings All the cyclic directed graphs hace non topological sortings Question 11 2 ptsWhat is the value of the sum of the minimum in-degree and maximum out-degree of an Directed Acyclic Graph? Depends on a Graph Will always be zero Will always be greater than zero May be zero or greater than zero Question 12 Determine the number of vertices for the given Graph or Multigraph? G is a 4-regular Graph having 12 edges. 03 6 04 Information given is insufficient Question 13 Possible number of labelled simple Directed, Pseudo and Multigarphs exist having 2 vertices? 3. Infinite, 4 4, 3, Infinite 4. Infinite, infinite 4, Infinite, Infinite Question 14 Which of the following is a Hyper Graph, where V is the set of vertices. E is the set of edges? V= (v1, v2, v3) E= [e1, e2}={(v2, v3} {v1, v3}} V= [v1, v2] E = [e1] = {{v1, v2}} V= (v1, v2, v3] E= [e1, e2, e3] = {{v2, v3)[v3, v1][v2, v1]] All of the mentioned Question 15 What is the degree sequence of the given Hyper Graph, in non- increasing order. V= (v1,v2 v3 v4,v5,v6) E= {{v1,v4,v5) (v2,v3.v4.v5) [v2] [v1] (v1.v6]] 3.2.1.1.1.1 3,2,2,2,1,1 3,2,2,2,2,1 3,2,2,1,1,1