11

12

13

14

15

16

17

18

a)
b)

a)
b)

a)

b)

a)
b)

a)
b)

a)
b)

C1142 Pages 3

Draw the binary tree whose sequential representation is given below.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

PART 0
Answer any two full questions, each carries9 marks.
What is a binary search tree (BST)? Give an example of a BST with five nodes.

Assume that a stack is represented using linked list. Write algorithms for the
following operations:-
(i) Push
(ii) Pop
Write an algorithm to evaluate postfix expression. Trace the algorithm on the
following input
623+-84/+23%+ (all numbers are single digits)
Write an algorithm to search for a substring in a given string.
Write an iterative algorithm to perform in order traversal of a binary tree.
PART E

Answer any four full questions, each carries10 marks.
Explain the various ways in which a graph can be represented bringing out the
advantages and disadvantages of each representation.
Write an algorithm to perform bubble sort on a collection of ‘n’ numbers.
Write algorithms for DFS and BFS traversal on a graph.
Write the output of DFS and BFS traversals on the following graph considering

starting vertex as 1.

Write an algorithm for Quick sort.

Trace the working of the algorithm on the following input

38, 8, 0, 28, 45, -13, 89, 66, 42

Compare Binary Search and Linear Search.

Write an algorithm to perform binary search on a given set of ‘n’ numbers.

Using the algorithm search for the element 23 in the set [12, 23, 34, 44, 48, 53,

Page 2 of 3

(3)

(3)

(6)

(9)
(4)
(5)

(6)

(4)

(6)
(4)

(5)
(5)

(3)

(7)