13

14

15

16

17

18
19

20

a)

b)
a)
b)

a)

b)

D3826 Pages: 2

binary search tree?

Given five memory partitions of 100Kb, 500Kb, 200Kb, 300Kb, 600Kb (in order),
how would the first-fit and best-fit algorithms place processes of 212 Kb, 417 Kb,
112 Kb, and 426 Kb (in order)? Which algorithm makes the most efficient use of
memory?

Develop an algorithm to add an element into a binary search tree.

Write a C Program/algorithm to implement two stacks using a single array.

What are the applications of trees?

PART E
Answer any four full questions, each carries 10 marks

Write an algorithm/ C program to perform merge sort. Given the following list of
numbers: [21, 1, 26, 45, 29, 28, 2] find the output obtained after each recursive call
of merge sort algorithm.

Write C program/algorithm to perform linear search. Find the time complexity for
best, worst and average casefor a linear search in an array of n elements.

Write algorithm to perform Breadth First Search.Write one possible order of
visiting the nodes of the following graph starting at vertex A.

९ „९
५/१ /

What is hash table? What are the properties of hash function?

What is max heap?Write an algorithm to perform heap sort. Give example.

Write C program/algorithm to perform selection sort. Perform selection sort on an
array [5,3,1,7,9].

What is double hashing? Suppose size of the hash table is 11. Open addressing
and double hashing is used to resolve collisions.The hash function used is H(k) =k
mod 11.The second hash function 15 H2(k) = 5 - (k mod 5)

What values will be in the hash table after the following sequence of insertions?
16, 23 9, 34, 12, 56

ಶೇತೇ मं ‏د‎

Page 2 of 2

(4.5)

(4.5)
(7)
(2)

(10)

(10)

(5)

(5)
(10)

(10)

(10)