Data Structures with C - Dec 2012

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 are pointer variables? How to declare a pointer variable?(5 marks) 1 (b) What are the various memory allocation techniques? Explain how memory can be dynamically allocated using malloc()?(10 marks) 1 (c) What is recursion? What are the various types of recursion?(5 marks) 2 (a) What is the difference between int a and int a[5] and int *[5]?(6 marks) 2 (b) What is a structure? How to declare and initialize a structure?(6 marks) 2 (c) Write a programin C o.read a sparse matrix of integer values and search this matrix for an element specified by the user.(8 marks) 3 (a) Define stack. List the operation on stack.(8 marks) 3 (b) Obtain the postfix and prefix expression for (((A+(B-C)D)E)+F)(6 marks) 3 (c) What is system stack? How the control is transferred to or from the function with the help of activation record?(6 marks) 4 (a) What is a linked list? Explain the different types of linked list with diagram.(10 marks) 4 (b) Write a function to insert a node at front and rear end in a circular linked list. Write down sequence of steps to be followed.(10 marks) 5 (a) What is a tree? Explain: i) root.node, ii) child, iii) siblings, iv) ancestors using structure representation.(6 marks) 5 (b) What is a binary tree? How it is represented using array and linklist?(10 marks) 5 (c) What is a heap? Explain the different types of heap?(4 marks) 6 (a) What is the binary search tree? Draw the binary serach tree for the following input:
14, 5, 6, 2, 18, 20, 16, 18, -1, 21.(10 marks) 6 (b) What is a forest? Explain the different method of traversing a tree with following tree; (10 marks) 7 (a) What is priority queue? Explain the various types of priority queues.(8 marks) 7 (b) Write short notes on:
i) Binomial heaps, ii) Fibonacci heap(6 marks) 7 (c) What is leftist tree? Explain different types of leftist trees.(6 marks) 8 (a) What is an AVL tree? Write the algorithm to insert an item into AVL tree.(8 marks) 8 (b) Write short notes on: i) Red-black tree ii) Spaly trees.(6 marks) 8 (c) Explain the different types of rotations of an AVL tree.(6 marks)