Programming in C++ - Dec 2015

Electronics & Communication (Semester 7)

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 the uses of template functions?(2 marks) 1 (b) What is dynamic memory allocation? Name and explain the operator used to allocate and deallocate memory dynamically.(4 marks) 1 (c) Explain formula - based linear list representation and write a C++ program for the same using template functions.(10 marks) 1 (d) Why is linked representation preferred over formula based linear list representation.(4 marks) 2 (a) What are special matrices? Explain in detail.(6 marks) 2 (b) Write a store and retrieve function for a diagonal matrix.(6 marks) 2 (c) Write a C++ program to find the sum of two sparse matrices.(8 marks) 3 (a) What is stack? Write the abstract data type of a stack.(4 marks) 3 (b) Write a C++ program for linked stack from a chain class.(8 marks) 3 (c) Write a C++ recursive function for towers of Hanoi and explain in detail.(8 marks) 4 (a) Write a C++ program to perform the following operations on a linked queue:
i) To insert element from the rear end
ii) To delete element from the front end
iii) To display queue content(10 marks) 4 (b) What is queue? Explain formula based queue representation.(10 marks) 5 (a) List the operations to be performed on a directory and write dictionary abstract data type.(4 marks) 5 (b) Illustrate and explain with an example fast searching of a sorted chain using skip list representation.(10 marks) 5 (c) Compare hashing with chains and hashing with linear open addressing.(6 marks) 6 (a) What are essential differences between a binary tree and tree? List the properties of binary trees.(6 marks) 6 (b) Write a recursive routine that can print the contents of a binary tree in preorder, in order and post order.(6 marks) 6 (c) i) Write the pre-order, in-order and post-order expression for the following tree shows in Fig. Q6(c) below:
ii) What is the height of the tree shown in figure?
:!MAGE-(8 marks) 7 (a) What is a max heap? Explain insertion into a max heap and deletion from a max heap.(6 marks) 7 (b) Explain melding two max HBL Ts and also write a C++ function for melding two leftist trees.(10 marks) 7 (c) What is priority queue? Write abstract data type for max priority queue.(4 marks) 8 (a) Write C++ function to perform the following operations on a binary search tree:
i) Inserting an element.
ii) Deleting an element
iii) Searching on element.(12 marks) 8 (b) Explain m-way search trees.(8 marks)