Data Structures and Applications - Dec 2015

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 spare polynomials using array of structures and also write a function to add two polynomials and give the analysis of the function.(10 marks) 2 (c) For the given sparse matrix A and its transpose. Give the triple 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 expressions using stack.
i) ASBC-D+E/F/(G+H)
ii) 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 advantages 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 623+382/+*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 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/BCD+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) WBTL(8 marks) 7 (b) Write short notes on:
i) Priority queues
ii) Binomial heaps
iii) Priority heaps
iv) Fibonacci heaps.(12 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)