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

2022
Views:

6

Pages:

9
Author:

NyiH

Question 1 Which of the following statements for a simple graph is correct? Every path is a trail Every trail is a path Every trail is a path as well as every path is a trail Path and trail have no relation Question 2 What is the number of edges present in a complete graph having n vertices? (n*(n+1))/2 (n*(n-1))/2 On The information given is insufficient Question 3 If a simple graph G, contains n vertices and m edges, the number of edges in the Graph G'(Complement of G) is (n*n-n-2*m)/2 (n*n+n+2*m)/2 (n*n-n-2*m)/2 (n*n-n+2*m)/2 Question 4 Which of the following properties does a simple graph not hold? Must be connected Must be unweighted Must have no loops or multiple edges Must have no multiple edges Question 5 Which of the following is true? A graph may contain no edges and many vertices A graph may contain many edges and no vertices A graph may contain no edges and no vertices A graph may contain no vertices and many edges Question 6 Which of the following ways can be used to represent a graph? Adjacency List and Adjacency Matrix Incidence Matrix Adjacency List, Adjacency Matrix as well as Incidence Matrix No way to represent Question 7 The number of elements in the adjacency matrix of a graph having 7 vertices is 07 14 36 49 Question 8 The time complexity to calculate the number of edges in a graph whose information in stored in form of an adjacency matrix is O(V) O(E^2) O(E) O(V^2) Question 9 On which of the following statements does the time complexity of checking if an edge exists between two particular vertices is not, depends? Depends on the number of edges Depends on the number of vertices Is independent of both the number of edges and vertices It depends on both the number of edges and vertices Question 10 Which of these adjacency matrices represents a simple graph? [[1,0,0], [0, 1, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 1], [1, 1, 1]] [[0, 0, 1], [0,0,0], [0,0,1]] [[0.0.1], [1,0, 1], [1.0.0]] Question 11 If A[x+3][y+5] represents an adjacency matrix, which of these could be the value of x and y. x=5, y=3 x=3, y=5 x=3, y=3 x=5,y=5 Question 12 For the given conditions, which of the following is in the correct order of increasing space requirement? i) Undirected, no weight ii) Directed, no weight iii) Directed, weighted iv) Undirected, weighted ii iii i iv i iii ii iv iv iii i ii i ii iii iv Question 13 Space complexity for an adjacency list of an undirected graph having large values of V (vertices) and E (edges) is O(E) O(VV) O(E+V) O(V) Question 14 Time complexity to find if there is an edge between 2 particular vertices is O(V) O(E) O(1) O(V+E) Question 15 In which case adjacency list is preferred in front of an adjacency matrix? Dense graph Sparse graph Adjacency list is always preferred Complete graph