## 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)ASB*C-D+E/F/(G+H) A-B/(C*D$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)