unit-5 test-1

Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex t at a distance four from the root. If t is the n-th vertex in this BFS traversal, then the maximum possible value of n is ___________.

• 29

• 30

• 31

• 32

Consider the following directed graph:

The number of different topological orderings of the vertices of the graph is ________________.

• 5

• 6

• 7

• 8

Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?

• O(n log n)
• O(n!)
• O(m^2)
• O(n^2)

Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.

• 17

• 18

• 19

• 20

Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing

• longest paths from the source node to all other nodes in the graph
• paths from all nodes to the source node in the graph
• random paths from the source node to all other nodes in the graph
• shortest paths from the source node to all other nodes in the graph

In a depth-first traversal of a graph G with n vertices,k edges are marked as tree edges. The number of connected components in G is

• n - k + 1
• n / k
• n - k
• n + k + 1

Consider the following graph among the following sequences
I. a b e g h f
II. a b f e h g
III. a b f h g e
IV. a f g h b e

• I. II.

• I. III. IV.

• II. III. IV.

• I. II. III. IV

Let G be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1,2,…,100. There is an edge between vertices U and V if and only if the label of U can be obtained by swapping two adjacent numbers in the label of V. Let y denote the degree of a vertex in G, and 𝑧 denote the number of connected components in G. Then, 𝑦+10𝑧= _____.

• 110

• 109

• 108

• 107

In an adjacency list representation of an undirected simple graph G=(V,E), each edge (u,v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency list of v. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If |E|=m and |V|=n, and the memory size is not a constraint, what is the time complexity of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?

• O(m*n)
• O(m^2)
• O(m+n)
• O(n^2)

Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For x∈V, let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is performed starting at s. Let T be the resultant BFS tree. If (u, v) is an edge of G that is not in T, then which one of the following CANNOT be the value of d(u)−d(v)?

• -1

• 0

• 1

• 2