Data Structures and Applications - May 2016

Computer Science Engg. (Semester 3)

TOTAL MARKS: 100
TOTAL TIME: 3 HOURS (1) Question 1 is compulsory.
(2) Attempt any four from the remaining questions.
(3) Assume data wherever required.
(4) Figures to the right indicate full marks. 1(a) Explain the functions supported by C to carry out dynamic memory allocation with example.(6 marks) 1(b) What is recursion? What are the various types of recursion? Write a recursive function to implement binary search.(7 marks) 1(c) Define the term 'Space and time complexity'. Determine the time complexity of an iterative and recursive functions that adds n elements of an array using tabular method.(7 marks) 2(a) Write a note on dynamically allocated array's with example.(6 marks) 2(b) How would you represent two sparse polynomials using array of structures and also write a function to add two polynomial and give the analysis of the function.(10 marks) 2(c) For the given sparse matrix A and its transpose, give the triplet representation 'A' is the given sparse matrix and 'B' will be its transpose. $$\text{Sparse \ matrix\ A}-\begin{bmatrix} 25 & 0 & 0 & 11 & 0 & -10\\ 0 & 12 & 3 & 0 & 0 & 0\\ 0 & 0 & 0 & 6 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 81 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & -18 & 0 & 0 & 0 \end{bmatrix}$$(4 marks) 3(a) Define stack. Implement push and pop functions for stacks using arrays.(5 marks) 3(b) Write the postfix form of the following expression using stack:
i)ASBC-D+E/F/(G+H)
A-B/(CD$E)\lt/span\gt\ltspan class='paper-ques-marks'\gt(6 marks)\lt/span\gt \lt/span\gt\ltspan class='paper-question'\gt\ltspan class='paper-ques-desc'\gt\ltb\gt3(c)\lt/b\gt What is the advantage of circular queue over linear queue? Write insert and delete functions for circular implementation of queues.\lt/span\gt\ltspan class='paper-ques-marks'\gt(5 marks)\lt/span\gt \lt/span\gt\ltspan class='paper-question'\gt\ltspan class='paper-ques-desc'\gt\ltb\gt3(d)\lt/b\gt Evaluate the following postfix expression 6 2 3 + - 3 8 2 / + * 2 $ 3 + using stack.(4 marks) 4(a) Write C functions to implement the insert and delete operations on a queue using linked list.(8 marks) 4(b) With the node structure show how would you store the given polynomials a and b in linked list? Write a C function for adding 2 polynomials using linked lists.(8 marks) 4(c) Write a note on doubly linked list. How is it different from single linked list?(4 marks) 5(a) What is binary tree? State its properties. How it is represented using array and linked list? Give example.(8 marks) 5(b) Show the binary tree with the arithmetic expression A / B * C * D + E. Give the algorithm for inorder, preorder, postorder traversals and show the result of these traversals.(8 marks) 5(c) What is heap? Explain different types of heap.(4 marks) 6(a) Define binary search tree. Draw the binary search tree for the following input 14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5(7 marks) 6(b) Construct a binary tree having the following sequence:
i) Preorder seq ABCDEFGHI
ii) Inorder seq BCAEDGHFI(5 marks) 6(c) Write a iterative search routine for a binary search tree.(5 marks) 6(d) Define the following terms:
i) Forests
ii) Graphs
iii) Winner trees(3 marks) 7(a) Briefly explain the following with examples:
i) HBLT ii) WBLT(8 marks)

Write short notes on:

7(b)(i) Priority queues(3 marks) 7(b)(ii) Binomial heaps(3 marks) 7(b)(iii) Priority heaps(3 marks) 7(b)(iv) Fibonacci heaps(3 marks)

Write short notes on:

8(a) AVL trees(5 marks) 8(b) Red-black trees(5 marks) 8(c) Optimal binary search trees.(5 marks) 8(d) Splay trees.(5 marks)