Total No. of Questions : 4] SEAT No.

8
23
PA-4976 [Total No. of Pages : 2

ic -
[6008] - 228

ta t
S.E. (Computer /A.I. & D.S.) (Insem)

6s
DATA STRUCTURES AND ALGORITHMS

0:0
02 91
(2019 Pattern) (Semester - II) (210252)

5:1
0
31
5/0 13
0
4/2
Time : 1 Hour] [Max. Marks : 30
.23 GP

Instructions to the candidates:

1) Solve Q.1 or Q.2, Q.3 or Q.4.
E
80

8
C

23
2) Figures to the right side indicate full marks.

ic-
4) Assume suitable data, if necessary.
16

t
sta
8.2

Q1) a) We have a hash table of size 10 to store integer keys, with hash function

:06
.24

h(x) = x mod 10. Construct a hash table step by step using linear probing
91
:10
without replacement strategy and insert elements in the order
49

31,3,4,21,61,6,71,8,9,25. Calculate average number of comparisons

15
30

required to search given data from hash table using linear probing without
23
01

replacement. [6]
/20
GP
/04

b) Explain the concept of quadratic probing using example. What are the
advantages and disadvantages of quadratic probing over linear probing?
5
CE
80

8
[5]

23
.23

c) What is hashing? Explain the properties of good hash function with

ic-
16

tat
examples. [4]
8.2

6s
.24

0:0

OR
91
49

5:1

Q2) a) Insert the following data in the hash table of size 10 using linear probing
30
31

with chaining by applying with replacement : 11, 33, 20, 88, 79, 98, 68,
01
02

44, 66, 24. Calculate average number of comparisons required to search

4/2

given data from hash table. [6]

GP
5/0

b) Add following keys in hash table by applying extendible hashing

CE
80

mechanism. Assume capacity of each directory to store buckets is 3.

.23

Keys are 10, 20, 15, 12, 25, 30, 7, 11, 08. [5]
16

c) Write short note on skip list. [4]

8.2
.24

P.T.O.
49
 8
Q3) a) Write an algorithm to delete a node from Threaded binary Search Tree.

23
[6]

ic -
ta t
b) The following numbers are inserted into an empty binary search tree in

6s
the given order : G, C, B, A , D, E, F, I, H. Construct tree step by step.

0:0
Represent the constructed tree using static memory allocation. [5]

02 91
5:1
c) Let characters a, b, c, d, e, f has probabilities 0.07, 0.09, 0.12, 0.22,

0
31
0.23, 0.27 respectively. Find an optimal Huffman code and draw Huffman
5/0 13
tree. [4]
0
4/2
.23 GP

OR
E

Q4) a) Construct threaded binary tree step by step if the preorder traversal is
80

8
C

23
G, B, D, C, A, K, Q, P, R & in-order traversal is B, A, C, D, G, K, P, Q,

ic-
R. Delete G and redraw a tree. [6]
16

t
sta
8.2

b) Write a non-recursive function to display data in Binary Search Tree in

:06
.24

descending order. [5]

91
:10
49

15
30

c) Explain how to convert general tree to binary tree with example. [4]
23
01
/20
GP
5 /04
CE

  
80

8
23
.23

ic-
16

tat
8.2

6s
.24

0:0
91
49

5:1
30
31
01
02
4/2
GP
5/0
CE
80
.23
16
8.2
.24
49

[6008] - 228 2