Time: 2.30 Hrs. M.M.: 100
Notes: Attempt five questions including question No. 1 which is compulsory.
1. (a) Fill in the blanks. 5*2=10
(i) A vertex of degree one is called...............
(ii) Postfix equivalent of A + B * C expression is.......................
(iii) The time complexity of a binary search Algorithm is.....................
(iv) Quick short uses ................. programming technique.
(v) The maximum number of nodes at level K in binary the tree is.....................
(b) Multiple choice questions— 5*2=10
(i) Which of the following sorting procedure is the slowest
(1) Quicksort (2) Heap sort
(3) Shell sort (4) Bubble sort
(ii) How many cycles should be contained in the tree—
(1) 0 (2) At least one
(3) Any number (4) None of these
(iii) The extra key inserted at the end of the array is called a—
(1) End key (2) Stop key
(3) Sentinel (4) Transposition
(iv) The height of its left subtree and right subtree differ at least by one—
(1) Binary search tre (2) AVL-tree
(2) complete tree (4) Non ubo this
2. (a)What is a circular queued? Write C function for printing element of in reverse order. 10
(b) What is stack? Write down the C function for different operation perform on stack. 10
3. (a) A Binary Tree with 9 node has its pre order and in order transversal sequence, as follows— 10
Pre order 1,2, 3, 4, 5, 6, 7, 8, 9
In order 2, 3,1, 5,4, 7, 8, 6, 9
Reconstruct the original tree
(b) What is sorting? How does it differ from merging? Explain the working of the merge sort.
4. (a) Construct on AVL tree by using following nodes— 10
(b) Write an algorithm for inserting a node in the beginning in the middle and at the end of the linked list.
5. (a) What is Heap? Define min Heap & Max Heap. 10
(b) Write a C program for the insertion sort algorithm.
6. (a) Define the Hash function & write down the benefits of hash tables. 10
(b) Write a program to produce the binary search algorithm.
7. Write short notes on any four. 5*4=20
(a) Malloc and Calloc function (b) Symbol table
(c) Abstract data structure (d) Polyriominal
(e) BFS (f) DFS