## Data Structures with C - Jun 2014

### 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)** What is pointer? How pointer are declared and initialized in C?(3 marks)
**1 (b)** What is dangling pointer reference and how to avoid it?(4 marks)
**1 (c)** Estimate the space complexity of a recursive function for summing a list of numbers(5 marks)
**1 (d)** Define the term "space and time complexity". Apply program step counter method to estimate the time complexity of a function to add two matrices.(8 marks)
**2 (a)** With a suitable example, explain dynamic memory allocation for 2-d arrays.(4 marks)
**2 (b)** Define a structure for the employee with the following fields:

Emp_Id(integer), Emp_Name(string), Emp_Basic(float), Emp_Dept(strng) and Emp_Age(integer). Write the following functions to process the employee data:

i) Function to read an employee record

ii) Function to print an employee record(8 marks)
**2 (c)** Write the "fast transpose" algorithm of a sparse matrix. Why the name "fast transpose"?(8 marks)
**3 (a)** What is the advantages of circular queue over linear queue? Write the insert and delete functions for circular implementation of queues.(8 marks)
**3 (b)** Explain infix to postfix expression algorithm and trace it for an expression "a*(b+c)*d".(8 marks)
**3 (c)** How multiple stacks implemented using one dimensional array? Explain with a suitable example.(4 marks)
**4 (a)** Write the following functions for singly linked list:

i) Reverse the list ii) Concatenate two list(8 marks)
**4 (b)** Write the node structure for linked representation of polynomial. Explain the algorithm to add two polynomials represented using linked lists.(8 marks)
**4 (c)** What is the advantage of doubly linked list over singly linked list? Illustrate with an example.(4 marks)
**5 (a)** Illustrate with a suitable example define:

i) Binary tree

ii) Degree of a binary tree

iii) Level of a binary tree

iv) Sibling(8 marks)
**5 (b)** For any nonempty binary tree T, if n_{0} is the number of leaf nodes and n_{2} the number of nodes of degree 2, then prove that n_{0}=n_{2}+1(4 marks)
**5 (c)** What is the advantage of threaded binary tree over binary tree? Explain threaded binary tree construction with a suitable example.(8 marks)
**6 (a)** What is binary search tree? Write a recursive search routine for a binary search tree.(8 marks)
**6 (b)** Explain selection trees, with suitable example.(6 marks)
**6 (c)** What is a forest? With suitable example illustrate how you transform a forest into a binary tree.(6 marks)
**7 (a)** Define priority queue. List the single-ended and double-ended priority queue operations.(6 marks)
**7 (b)** Define the following:

i) Leftist trees

ii) Min leftist trees and

iii) Weighted leftist trees.(6 marks)
**7 (c)** What is binomial heap? Explain the following associated with binomial heap:

i) Insertion into a binomial heap

ii) Melding two binomial heaps and

iii) Deletion of min element.(8 marks)

### Write short notes on:

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