Data Structures with C - Jun 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) Define a pointer. Write a C function to swap two numbers using pointers.(5 marks) 1 (b) Explain the functions supported by C to carryout dynamic memory allocation.(5 marks) 1 (c) Explain performance analysis and performance measurement.(10 marks) 2 (a) Define structure and union with suitable example.(8 marks) 2 (b) Write a C program with an appropriate structure definition and variable declaration to store information about an employee using nested structures. Consider the following fields like Ename, Empid, DOJ (Date, Month, Year) and salary(Basic, DA, HRA).(12 marks) 3 (a) Write a C program to implement the two primite operations on stack using dynamic memory allocation.(8 marks) 3 (b) Write an algorithm to convert infix to postfix expression and apply the same to convert the following expression from infix to postfix:
ii) (((a/b)-c) + (de)) - (a*c)(12 marks) 4 (a) Define linked list. Write a C program to implement the insert and delete operation on a queue using linked list.(10 marks) 4 (b) Write a C function to add two polynomials using linked list representation. Explain with suitable example.(10 marks) 5 (a) Define binary trees. For the given tree find the following:
ii) Leaf nodes
iii) Non-leaf nodes
v) Level of trees.
i) Pre order: / + * 1 $ 2 3 4 5 \ltbr\gt A B D G C E H I F \ltbr\gt In order: 1 + 2 * 3 $ 4 - 5
D G B A H E I C F.(8 marks) 6 (c) Define furest with example.(4 marks) 7 (a) Define leftlist trees. Explain varieties of leftist trees.(8 marks) 7 (b) Write short notes on:
i) Priority queues
ii) Binomial heaps
iii) Priority heaps
iv) Fibonacci heaps.(12 marks) 8 (a) Define AVL trees. Write a C-routine for
i) Inserting into an AVL tree
ii) LL and LR rotation.(10 marks) 8 (b) Explain the following with example:
i) Red-black trees
ii) Splay trees.(10 marks)