SVKM’S NMIMS

MUKESH PATEL SCHOOL OF TECHNOLOGY MANAGEMENT& ENGINEERING

(Campus Name)
Academic Year: 2020-2021
Program: BTI Stream ; Computer Year: II Semester: IV
Subject: Advanced Data Structures Time: 11:10 to 12:10 hrs. 1
Date: 08 /03 / 2021 No. of Pages:
Marks: 20
Test-II [SET-A]
Div C
MCQ

Q.1 The number of values that can be stored in a node of m-way tree, having m=6 is
__________________________ [1]

Q.2 State true or false: Each tree can be considered as a graph, however each graph may not
be considered as a tree. [1]
Q.3 For a given graph find the in-degree of node C and out-degree of node D. [1]

a. In-degree of node C – 2, Out-degree of node D -2

b. In-degree of node C- 2, Out-degree of node D – 1

c. In-degree of node C – 1, Out degree of node D- 1

d. In-degree of node C- 2, Out degree of node D -0

Q.4 For the given graph below, find the cost of connecting all the nodes using shortest path. Connect
each node only once. [2]
a. 24

b. 20

c. 29

d. 25

Q.5 For a given graph, identify the depth first search sequence starting from node A. [2]

a. A D F B C E G H

b. A B E F C G H D

c. A B F D E C G H

d. A D F E C B G H
Q. 6 Suppose we run Dijkstra’s single source shortest-path algorithm on the following edge
weighted directed graph with vertex P as the source. In what order do the nodes get included
into the set of vertices for which the shortest path distances are finalized? [2]

a. P, Q, R , S , T, U
b. P, Q, R, U, S, T
c. P, Q, R, U, T, S
d. P, Q, T, R, U, S

Q.7 Consider the following graph:

Which one of the following cannot be the sequence of edges added, in that order, to a minimum
spanning tree using Kruskal’s algorithm? [2]

a. (a-b), (d-f), (b-f), (d-c), (d-e)

b. (a-b), (d-f), (d-c), (b-f), (d-e)

c. (d-f), (a-b), (d-c), (b-f), (d-e)

d. (d-f), (a-b), (b-f), (d-e), (d-c)

Q.8 For the given adjacency matrix, identify the correct graph. [1]

1 2 3 4 5
1 0 0 1 1 0
2 0 0 0 1 1
3 1 0 0 0 1
4 1 1 0 0 0
5 0 1 1 0 0

a.

b.

c.

d. None
 Subjective:

Q.1 Construct a b-tree of order 3, inserting below values. [4]

17, 1, 2, 66, 23, 45, 21, 7, 56, 41

Q.2 Write a function to implement a breadth first search traversal for a graph. [4]

SVKM’S NMIMS
MUKESH PATEL SCHOOL OF TECHNOLOGY MANAGEMENT& ENGINEERING
(Campus Name)
Academic Year: 2020-2021
Program: BTI Stream ; Computer Year: II Semester: IV
Subject: Advanced Data Structures Time: 11:10 to 12:10 hrs. 1
Date: 08 /03 / 2021 No. of Pages:
Marks: 20
Test-II [SET-B]
Div C
MCQ
Q.1 The number of values that can be stored in a node of m-way tree, having m=8 is
___________________ [1]

Q.2 State true or false: Each tree can be considered as a graph, however each graph may not
be considered as a tree. [1]
Q.3 For a given graph find the in-degree of node D and degree of node A. [1]
a. In-degree of D – 1, Degree of node A -2

b. In-degree of D – 2, Degree of node A- 4

c. In-degree of D – 4, Degree of node A – 4

d. In-degree of D -2, Degree of node A -2

Q.4 For the given graph below, find the cost of connecting all the nodes using shortest path. Connect
each node only once. [2]

a. 13

b. 11

c. 14

d. 7

Q.5 For a given graph, identify the breadth first search sequence starting from node 3. [2]

a. 3 4 1 0 2 5

b. 3 4 0 5 1 2
c. 3 4 5 1 2 0

d. 3 4 2 1 0 5

Q.6 For the given graph, find the shortest path from node 0 to all other nodes. [2]

Q.7 Consider the following graph:

Which one of the following cannot be the sequence of edges added, in that order, to a minimum
spanning tree using Kruskal’s algorithm? [2]

a. (a-b), (d-f), (b-f), (d-c), (d-e)

b. (a-b), (d-f), (d-c), (b-f), (d-e)

c. (d-f), (a-b), (d-c), (b-f), (d-e)

d. (d-f), (a-b), (b-f), (d-e), (d-c)

Q.8 For the given adjacency matrix, identify the correct graph. [1]
a.

b.

c.

d. None

Q.1 Construct a b-tree of order 3, inserting below values into the tree. [4]

21, 30, 45, 1, 56, 67, 22, 16, 33, 29

Q.2 Write a function to implement depth first search traversal for a graph. [4]
 SVKM’S NMIMS
MUKESH PATEL SCHOOL OF TECHNOLOGY MANAGEMENT& ENGINEERING
(Campus Name)
Academic Year: 2020-2021
Program: BTI Stream ; Computer Year: II Semester: IV
Subject: Advanced Data Structures Time: 11:10 to 12:10 hrs. 1
Date: 08 /03 / 2021 No. of Pages:
Marks: 20
Test-II [SET-A]
Div B
MCQ
Q.1 The data structure required for the breadth first traversal on a graph is [1]

a. Queue b. Stack c. array d.tree

Q.2 For the given adjacency matrix, identify the correct graph. [1]

1 2 3 4 5
1 0 0 1 1 0
2 0 0 0 1 1
3 1 0 0 0 1
4 1 1 0 0 0
5 0 1 1 0 0

a.
b.

c.

d. None

Q.3 The set of all edges generated by DFS tree starting at node B is: [2]

a. B A D C G F E

b. B A D

c. B A C D G F E

d. B C D A F E G

Q.4 For a given graph, find the minimum cost of connecting all the nodes once. [2]
a. 12 b. 10 c. 14 d. 11

Q.5 Suppose we run Dijkstra’s single source shortest-path algorithm on the following edge
weighted directed graph with vertex P as the source. In what order do the nodes get included
into the set of vertices for which the shortest path distances are finalized? [3]

a. P, Q, R , S , T, U
b. P, Q, R, U, S, T
c. P, Q, R, U, T, S
d. P, Q, T, R, U, S

Q.6 Consider the following graph, If we run breadth first search on this graph starting at any vertex,
which one of the following is a possible order for visiting the nodes? [2]

a. MNOPQR b. NQMPOR c. QMNPRO d. QMNPOR

 Q.7 The number of values that can be stored in a node of m-way tree, having m=8 is
___________________ [1]

Subjective:

Q.1 Construct a b-tree of order 3, inserting below data. [4 marks]

12, 15, 1, 67, 34, 22, 20, 17, 2, 88, 16, 21, 9

Q.2 Explain how dijkstra’s algorithm differ from Kruskal’s algorithm. Write an algorithm for finding
shortest path from a single source to all other nodes in a graph. [4 marks]

SVKM’S NMIMS
MUKESH PATEL SCHOOL OF TECHNOLOGY MANAGEMENT& ENGINEERING
(Campus Name)
Academic Year: 2020-2021
Program: BTI Stream ; Computer Year: II Semester: IV
Subject: Advanced Data Structures Time: 11:10 to 12:10 hrs. 1
Date: 08 /03 / 2021 No. of Pages:
Marks: 20
Test-II [SET-B]
Div B
MCQ
Q.1 The data structure required for the depth first traversal on a graph is [1]

a. Queue b. Stack c. array d.tree

Q.2 For the given adjacency matrix, identify the correct graph. [1]

1 2 3 4 5
1 0 1 0 1 0
2 1 0 0 0 1
3 0 0 0 1 1
4 1 0 1 0 0
5 0 1 1 0 0

a.

b.

c.
d. None

Q.3 The set of all edges generated by BFS, starting at node B is: [2]

a. B A D C G F E

b. B A D

c. B A C D G F E

d. B C D A F E G

Q.4 For a given graph, find the minimum cost of connecting all nodes once. [2]

a. 37 b. 38 c. 36 d. 35

Q.5 Suppose we run Dijkstra’s single source shortest-path algorithm on the following edge
weighted directed graph with vertex P as the source. In what order do the nodes get included
into the set of vertices for which the shortest path distances are finalized? [3]
a. P, Q, R , S , T, U
b. P, Q, R, U, S, T
c. P, Q, R, U, T, S
d. P, Q, T, R, U, S

Q.6 Consider the following graph, among the following sequences, which are the depth first
traversals of the below graph? [2]
I. 0 1 2 4 5 II 0 1 3 4 5 2 III 0 2 3 4 5 1 IV 0 1 2 3 4 5

a. Only I

b. I and II

c. II and IV

d. II, III and IV

Q.7 The number of values that can be stored in a node of m-way tree, having m=5 is
___________________ [1]

Subjective:

Q.1 Construct b-tree of order 3, inserting below data [4 marks]

34, 56, 12, 1, 78, 8, 4, 99, 3, 21, 42, 6, 76

Q.2 State the difference between Kruskal’s algorithm and Prim’s algorithm. Write a function for
depth first search traversal technique. [4 marks]