Total No.
of Questions : 4]
SEAT No. :
PA-4976 [Total No. of Pages : 2 [6008] - 228
15:06:56
S.E. (Computer /A.I. & D.S.) (Insem)
DATA STRUCTURES AND ALGORITHMS
P013871
(2019 Pattern) (Semester - II) (210252)
05/04/2023
Time : 1 Hour] [Max. Marks : 30 Instructions to the candidates:
103.167.184.38
CEG
1) Solve Q.1 or Q.2, Q.3 or Q.4.
2) Figures to the right side indicate full marks.
4) Assume suitable data, if
necessary.
15:06:56
Q1) a) We have a hash table of size 10 to store integer keys, with hash function
h(x) = x mod 10. Construct a hash table step by step using linear probing
P013871
without replacement strategy and insert elements in the order
05/04/2023
31,3,4,21,61,6,71,8,9,25. Calculate average number of comparisons
required to search given data from hash table using linear probing
without replacement. [6]
b) Explain the concept of quadratic probing using example. What are the
103.167.184.38
CEG
advantages and disadvantages of quadratic probing over linear
pr
o
bi
n
g?
[5
]
c) What is hashing? Explain the properties of good hash function with
15:06:56
examples. [4]
OR
05/04/2023
P013871
Q2) a) Insert the following data in the hash table of size 10 using linear probing
with chaining by applying with replacement : 11, 33, 20, 88, 79, 98,
68, 44, 66, 24. Calculate average number of comparisons required to
search given data from hash table. [6]
103.167.184.38
CEG
b) Add following keys in hash table by applying extendible hashing
mechanism. Assume capacity of each directory to store buckets is 3.
Keys are 10, 20, 15, 12, 25, 30, 7, 11, 08. [5]
c) Write short note on skip list. [4] P.T.O.
Q3) a) Write an algorithm to delete a node from Threaded binary Search Tree.
[6
]
15:06:56
b) The following numbers are inserted into an empty binary search tree in
the given order : G, C, B, A , D, E, F, I, H. Construct tree step by step.
Represent the constructed tree using static memory allocation. [5]
P013871
05/04/2023
c) Let characters a, b, c, d, e, f has probabilities 0.07, 0.09, 0.12, 0.22, 0.23,
0.27 respectively. Find an optimal Huffman code and draw Huffman
tree. [4]
OR
103.167.184.38
CEG
Q4) a) Construct threaded binary tree step by step if the preorder traversal is G,
B, D, C, A, K, Q, P, R & in-order traversal is B, A, C, D, G, K, P, Q, R. Delete
G and redraw a tree. [6] 15:06:56
b) Write a non-recursive function to display data in Binary Search Tree in
descending order. [5] P013871
05/04/2023
c) Explain how to convert general tree to binary tree with example. [4]
103.167.184.38
E
C G
15:06:56
P013871
05/04/2023
103.167.184.38
CEG
2
[6008] - 228
