Data Structure UNIT TEST 4 and Sorting

JavaScript isn't enabled in your browser, so this file can't be opened. Enable and reload.

ROLL NUMBER *

NAME *

Q1 Which of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph?

1 point

In adjacency list representation, space is saved for sparse graphs.

DFS and BSF can be done in O(V + E) time for adjacency list representation. These operations take O(V^2) time in adjacency matrix representation. Here is V and E are number of vertices and edges respectively.

Adding a vertex in adjacency list representation is easier than adjacency matrix representation.

All of the above

Clear selection

Q2 Which of the following statements is/are TRUE for an undirected graph? P: Number of odd degree vertices is even Q: Sum of degrees of all vertices is even

1 point

P Only

Q Only

Both P and Q

Neither P nor Q

Clear selection

Q 3 Given an undirected graph G with V vertices and E edges, the sum of the degrees of all vertices is

1 point

Clear selection

Q4 What is the maximum number of edges in an acyclic undirected graph with n vertices?

1 point

n-1

n + 1

2n-1

Clear selection

Q5 For the undirected, weighted graph given below, which of the following sequences of edges represents a correct execution of Prim's algorithm to construct a Minimum Spanning Tree?

1 point

(a, b), (d, f), (f, c), (g, i), (d, a), (g, h), (c, e), (f, h)

(c, e), (c, f), (f, d), (d, a), (a, b), (g, h), (h, f), (g, i)

(d, f), (f, c), (d, a), (a, b), (c, e), (f, h), (g, h), (g, i)

(h, g), (g, i), (h, f), (f, c), (f, d), (d, a), (a, b), (c, e)

Clear selection

Q6 Consider a directed graph with n vertices and m edges such that all edges have same edge weights. Find the complexity of the best known algorithm to compute the minimum spanning tree of the graph?

1 point

O(m+n)

O(m logn)

O(mn)

O(n logm)

Clear selection

Q7 Which of the following data structure is useful in traversing a given graph by breadth first search?

1 point

Stack

List

Queue

None of the above.

Clear selection

Q 8 The number of edges in a simple, n-vertex, complete graph is

1 point

n*(n-2)

n*(n-1)

n*(n-1)/2

n*(n-1)*(n-2)

Clear selection

Q 9 Graphs are represented using ............

1 point

Adjacency tree

Adjacency linked list

Adjacency graph

Adjacency queue

Clear selection

Q 10 The spanning tree of connected graph with 10 vertices contains ..............

1 point

9 edges

11 edges

10 edges

9 vertices

Clear selection

Q 11 Which of the following algorithms solves the all-pair shortest path problem?

1 point

Floyd's Warshall's algorithm

Prim's algorithm

Dijkstra's algorithm

Kruskal algorithm

Clear selection

Q 12 What is the maximum number of possible non zero values in an adjacency matrix of a simple graph with n vertices?

1 point

(n*(n-1))/2

(n*(n+1))/2

n*(n-1)

n*(n+1)

Clear selection

Q13 How many undirected graphs (not necessarily connected) can be constructed out of a given set V= {V 1, V 2,…V n} of n vertices ?

1 point

n(n-l)/2

2^n

2^(n(n-1)/2)

Clear selection

Q 14 A graph is a tree if and only if graph is

1 point

Directed graph

Contains no cycles

Planar

Completely connected

Clear selection

Q 15 Which of the following is a linear data structure?

1 point

Array

Graph

Tree

AVl Tree

Clear selection

Q 16 Which of the following is not a stable sorting algorithm in its typical implementation.

1 point

Insertion Sort

Merge Sort

Quick Sort

Bubble Sort

Clear selection

Q 17 Suppose we are sorting an array of eight integers using quicksort, and we have just finished the first partitioning with the array looking like this: 2 5 1 7 9 12 11 10 Which statement is correct?

1 point

The pivot could be either the 7 or the 9.

The pivot could be the 7, but it is not the 9

The pivot is not the 7, but it could be the 9

Neither the 7 nor the 9 is the pivot

Clear selection

Q18 Which of the following is true about merge sort?

1 point

Merge Sort works better than quick sort if data is accessed from slow sequential memory.

Merge Sort is stable sort by nature

Merge sort outperforms heap sort in most of the practical situations.

All of the above

Clear selection

Q 19 What is the largest integer m such that every simple connected graph with n vertices and n edges contains at least m different spanning trees?

1 point

Clear selection

Q 20 Which of the following is not an in-place sorting algorithm?

1 point

Selection sort

Heap sort

Quick sort

Merge sort

Clear selection

Submit

Clear form

Never submit passwords through Google Forms.

Forms

This content is neither created nor endorsed by Google.