D

D7144

13 a) Here is a small binary tree:

14

15

16

17

18

19

20

a)

14

/ \
2 11

∕∖∕∖
13 10 0

∕∕
7 40
What is the output obtained after preorder, inorder and postorder traversal of the
following tree.
Write the non-recursive algorithm for post order traversal of tree.
Write a function( C/ pseudo code ) to insert an element into BST.
Write a program in C to check a particular sub string is present in a given string
or not? If found print its location.

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

Draw the directed graph that corresponds to this adjacency matrix:

0 1 2 3
0 | true false true false |
1 | true false falsefalse |
2 | false falsefalse true |
3 | true false true false |

Give the algorithm for BFS graph traversal.

Show all the passes using insertion sort for the following list
54,26,93,17,77,31,44,55,20

Write a function (C/ pseudo code) of heap sort using min heap.

Write a program to do the partition of a list using quick sort and then use
insertion sort for sorting sub lists. Explain it with example.

Write a program of binary search which tells how many comparisons it did to
search an element given as user input.

Do the performance comparisons of Linear search and Binary search.

Consider a hash table of size 7 and hash function h(k)= k mod 7. Draw the table
that results after inserting in the given order, the following values.
19,26,13,48.17 for each of the three scenarios.

When collisions are handled by separate chaining.

When collisions are handled by linear probing.

When collisions are handled by double hashing using second hash function h’=5-
(5 mod k).

Get the hash index in table of size 7 for the following list. 56,43,27,32,3.

Do the rehashing when the inserted elements are more than 4.

Briefly explain any 2 hasting functions.
KK

Page 2 of 2

(4.5)

(4.5)
(4)
(5)

(5)

(5)
(5)

(5)
(10)

(7)
(3)

(3)
(3)
(4)

(3)
(3)
(4)