Data Structures with C - Dec 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 are pointer variables ?How to declare a pointer variable?(5 marks) 1(b) What are the various memory allocation techniques? Explain how dynamic allocation is done using malloc()?(10 marks) 1(c) What is recursion? What are the various types of recursion?(5 marks) 2(a) Define structure and union with suitable example(8 marks) 2(b) Write a C program with appropriate structure definition and variable declaration to store information about an employee,using nested structures.Consider the following fields like: ENAME, EMPD, DOJ (Date, Month,Year) and Salary (Basic,DA,HRA)(12 marks) 3(a) Define stack.Give the C implementation of push and pop function. Include check for empty and full conditions of stack.(8 marks) 3(b) Write an algorithm to convert infix to post fix expression and apply the same to convert the following expression form in fix to post fix:
i) (a×b)+c/d
ii) ((( a/b(-e)+(d×e))-(a×c))(12 marks) 4(a) Define linked list. Write a C program to implement the insert and delete operation on queue using linked list.(10 marks) 4(b) Explain the different types of linked list with diagram.(10 marks) 5(a) Define the following :
i) binary tree
ii) Complete binary tree
Almost complete binary tree
iv) Binary search tree
v) Depth of a tree.(10 marks) 5(b) In brief describe any five application of trees.(5 marks) 5(c) What is thrcaded binary tree? Explain right and left in threaded binary tree.(5 marks) 6(a) Write C function for the following tree traversals :
i) inorder
II) preorder
iii) postorder.(10 marks) 6(b) Explain min and heap with example.(10 marks) 7(a) implement Fibonacci with example.(10 marks) 7(b) What is binomial heap? Explain the steps involved in the deletion of min element form a binomial heap.(10 marks) 8(a) Explain AVL tree.(10 marks) 8(b) Explain the red-black tree.Also,state its properties.(10 marks)