MORE IN Data Structures and Applications
VTU Computer Science (Semester 3)
Data Structures and Applications
June 2014
Total marks: --
Total time: --
INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary

1 (a) What is pointer? How pointer are declared and initialized in C?
3 M
1 (b) What is dangling pointer reference and how to avoid it?
4 M
1 (c) Estimate the space complexity of a recursive function for summing a list of numbers
5 M
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 M

2 (a) With a suitable example, explain dynamic memory allocation for 2-d arrays.
4 M
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 M
2 (c) Write the "fast transpose" algorithm of a sparse matrix. Why the name "fast transpose"?
8 M

3 (a) What is the advantages of circular queue over linear queue? Write the insert and delete functions for circular implementation of queues.
8 M
3 (b) Explain infix to postfix expression algorithm and trace it for an expression "a*(b+c)*d".
8 M
3 (c) How multiple stacks implemented using one dimensional array? Explain with a suitable example.
4 M

4 (a) Write the following functions for singly linked list:
i) Reverse the list ii) Concatenate two list
8 M
4 (b) Write the node structure for linked representation of polynomial. Explain the algorithm to add two polynomials represented using linked lists.
8 M
4 (c) What is the advantage of doubly linked list over singly linked list? Illustrate with an example.
4 M

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 M
5 (b) For any nonempty binary tree T, if n0 is the number of leaf nodes and n2 the number of nodes of degree 2, then prove that n0=n2+1
4 M
5 (c) What is the advantage of threaded binary tree over binary tree? Explain threaded binary tree construction with a suitable example.
8 M

6 (a) What is binary search tree? Write a recursive search routine for a binary search tree.
8 M
6 (b) Explain selection trees, with suitable example.
6 M
6 (c) What is a forest? With suitable example illustrate how you transform a forest into a binary tree.
6 M

7 (a) Define priority queue. List the single-ended and double-ended priority queue operations.
6 M
7 (b) Define the following:
i) Leftist trees
ii) Min leftist trees and
iii) Weighted leftist trees.
6 M
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 M

Write short notes on:
8 (a) Optimal binary search trees
5 M
8 (b) AVL trees
5 M
8 (c) Red-Black trees
5 M
8 (d) Splay trees
5 M

More question papers from Data Structures and Applications