10
11

12

13

14

15

16

17

a)

b)
a)

b)
a)
b)

a)
b)
a)

b)

a)

08000CS205122001

PART C
Answer all questions, each carries 3 marks.

What are the limitations of array implementation of queue? Give two
alternative representations of the same.
How are multiple stacks implemented? Illustrate.
Write an algorithm for substring search within a string.
How can a complete binary tree be represented using an array? Can a normal
binary tree be represented using an array?

PART D

Answer any two full questions, each carries9 marks.
Given five memory partitions of 30050, 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)?
Write the algorithm for non-recursive pre-order traversal of a binary tree.
Write an algorithm to convert a given infix expression to postfix Expression.
Trace the steps involved in converting the given infix expression
((A +B)4C)-((D*C)/F) to postfix expression.
Write the algorithm for inserting an element to a circular queue.
Given an infix expression (A +B)4C-(D*C)/F, convert into its prefix form.
Show the structure of the binary search tree after adding each of the following
values in that order: 10, 25, 2, 4, 7, 13.
(i) Illustrate how the element 2 can be deleted from the resultant tree.

(11) What is the height of the final tree?

PART E

Answer any four full questions, each carries 10 marks.
Give two representations of graphs.
How can linear probing be used to resolve collisions? Explain with example.
Construct a max heap with the following set of numbers entered sequentially.
10, 5, 14, 7, 12, 18, 15, 13
Write the algorithms for linear and binary search and compare their
performances.

What is a max heap? How can a heap be represented using an array?

(3)

(3)

(3)
(3)

(4.5)

(4.5)
(6)

(3)
(3)
(6)

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

(4)

2/3