12

13

14

15

16

17

18

19

20

a)
b)
a)

b)
a)

b)

a)

R3946 Pages: 2

PART 0

Answer any two full questions, each carries 9 marks.
Illustrate the result of each operation in the sequence PUSH(S,4),
PUSH(S,1), PUSH(S,3), POP(S), PUSH(S,8) and POP(S) on an initially
empty stack 5 stored in array S[1..6]
Write an algorithm to insert an element into a binary search tree.
Convert the following infix expression into prefix expression
(A-B/C) * (D*E-F)
Write an algorithm to evaluate a postfix expression.
In a complete binary tree of depth d (complete including last level), give an
expression to find the number of leaf nodes in the binary tree.
Given five memory partitions of 300Kb, 700Kb, 400Kb, 500Kb, 800Kb (in
order), how would the first-fit, best-fit, and worst-fit algorithms place
processes of 412 Kb, 617 Kb, 112 Kb, and 626 Kb (in order)?

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

What are the characteristics of a good hash function?

Demonstrate the insertion of the keys 5, 28, 15, 20, 33, 12, 17, 32 into a
hash table with collisions resolved by linear probing. Let the table have 9
slots, with the starting index 0. Let the hash function be h(k) = k mod 9

Give the heap sort algorithm. Write the complexity of your algorithm.
Using the above heap sort algorithm sort the input file [35 15 40 1 60].
What is Primary Clustering?

Given input keys {1, 3, 23, 9, 4, 29, 19} and a hash function

h(X) = X mod tablesize. The initial hash table contains 10 slots, with
starting index 0. Show the resulting table after rehashing when the load
factor= 0.5, using linear probing

Give a non recursive algorithm for binary search.

Suppose an array contains elements {10, 13, 21, 32, 35, 44, 55}. Give the
steps to find an element “35” using i) linear search ii) binary search

Give two different types of representation for graphs.

Write a procedure to do DFS in ೩ graph.

Write an algorithm to perform selection sort in an array.

Using the above selection sort algorithm, sort the input file

[25, 7, 46, 11, 85].

KKK

Page 2 of 2

(3)

(6)
(3)

(6)
(3)

(6)

(4)
(6)

(4)
(6)
(4)
(6)

(4)
(6)

(4)
(6)
(4)
(6)