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₀ is the number of leaf nodes and n₂ the number of nodes of degree 2, then prove that n₀=n₂+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)