Total No. of Questions : 5] SEAT No.

82
PC-1572 [Total No. of Pages : 2

tic-
[6328]-41

sta
S.Y. [Link].

9
3:1
Computer Science

1
9:2
2/2 21
CS-241: DATA STRUCTURES AND ALGORITHMS-II

40
(Revised 2019 Pattern) (Semester - IV) (CBCS) (24121)
9/1 10
02
Time : 2 Hours] [Max. Marks : 35
0
9.8 AP

Instructions to the candidates:

1) All questions are compulsory.
49 CA

2) Figures to the right indicate full marks.

20

82
3) Neat diagrams must be drawn wherever necessary.

ic-
4) Your answers will be values as a whole.
.21

tat
Q1) Attempt any Eight of the following: [8 × 1 = 8]

9s
2.1

3:1
11
a) What is complete binary tree?
20

9:2
02
40

b) Define degree of the tree.

02
01
2/2
AP
9/1

c) What is expression tree?

CA
20

-82
9.8

d) Define Balance factor.

tic
.21

sta
49

e) What do you understand by splay tree?

:19
2.1

:23
11
20

f) Write about inverse adjacency list.

09
02
24
01

g) Give any two uses of graph in social network.

/20
9.8 AP
/12

h) Define topological sort.

9
CA
20

i) What is a Bucket?
.21
49

j) List any two collision resolution techniques.

2.1
20

P.T.O.
Q2) Attempt any Four of the following: [4 × 2 = 8]

82
a) What do you mean by Huffman Encoding?

t ic-
b) Write a short note on B-tree.

sta
c) Define:

9
3:1
i) Height of tree ii) Siblings

1
9:2
2/2 21
d) Draw adjacency list of following graph.

40
9/1 10
02
0
9.8 AP
49 CA

20

82
e) What do you understand by collision in hashing?

ic-
.21

tat
Q3) Attempt Any Two of the following: [2 × 4 = 8]

9s
a) Write a C program to calculate indegree, outdegree of each node and
2.1

3:1
total degree of graph.
11
20

9:2
b) Write a 'C' function for deleting a node from Binary search tree.
02
40

c) Write a 'C' function 'Search' - that will searches an element in a hash

02
01

table.
2/2
AP

Q4) Attempt Any Two of the following: [2 × 4 = 8]

9/1

a) Differentiate between BFS and DFS.

CA
20

-82
b) Construct AVL tree for following data.
9.8

RUS, BRA, GER, IND, PAK, BAN, USA, AFR

tic
.21

sta
c) Describe coalesced chaining with an example.
49

:19
2.1

Q5) Attempt Any One of the following: [1 × 3 =3]

:23
11
20

09

a) Write the conditions and rules that red black tree must be satisfied.
02
24
01

b) Define the following terms.

/20
9.8 AP
/12

i) Spanning Tree
9

ii) Acyclic Graph

CA
20

iii) Weighted Graph

.21

JJJ
49
2.1
20

[6328]-41 2