1 (a)
Explain the functions supported by C to carry out dynamic memory allocation with example.

6 M

1 (b)
What is recursion? What are the various types of recursion? Write a recursive function to implement binary search.

7 M

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 M

2 (a)
Write a note on dynamically allocated array's with example.

6 M

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 M

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 M

3 (a)
Define stack. Implement push and pop functions for stacks using arrays.

5 M

3 (b)
Write the postfix form of the following expressions using stack.

i) ASB*C-D+E/F/(G+H)

ii) A-B/(C*D$E)

i) ASB*C-D+E/F/(G+H)

ii) A-B/(C*D$E)

6 M

3 (c)
What is the advantages of circular queue over linear queue? Write insert and delete functions for circular implementation of queues.

5 M

3 (d)
Evaluate the following postfix expression 623+382/+*2$3+using stack.

4 M

4 (a)
Write C functions to implement the insert and delete operations on a queue using linked list.

8 M

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 M

4 (c)
Write a note on doubly linked list. How is it different from single linked list?

4 M

5 (a)
What is binary tree? State its properties. How it is represented using array and linked list? Give example.

8 M

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 M

5 (c)
What is heap? Explain different types of heap.

4 M

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 M

6 (b)
Construct a binary tree having the following sequence:

i) Preorder seq ABCDEFGHI

ii) Inorder seq BCAEDGHFI

i) Preorder seq ABCDEFGHI

ii) Inorder seq BCAEDGHFI

5 M

6 (c)
Write a iterative search routine for a binary search tree.

5 M

6 (d)
Define the following terms:

i) Forests

ii) Graphs

iii) Winner trees.

i) Forests

ii) Graphs

iii) Winner trees.

3 M

7 (a)
Briefly explain the following with examples:

i) HBLT : ii) WBTL

i) HBLT : ii) WBTL

8 M

7 (b)
Write short notes on:

i) Priority queues

ii) Binomial heaps

iii) Priority heaps

iv) Fibonacci heaps.

i) Priority queues

ii) Binomial heaps

iii) Priority heaps

iv) Fibonacci heaps.

12 M

Write short notes on:

8 (a)
AVL trees.

5 M

8 (b)
Red-black trees

5 M

8 (c)
Optimal binary search trees.

5 M

8 (d)
Splay trees.

5 M

More question papers from Data Structures and Applications