# 2005 Centre for Development of Advanced Computing C DAC M C A MCA 102 Data Structure University Question paper

** University Question Papers **

**
**2005 Centre for Development of Advanced Computing C DAC M C A MCA 102 Data Structure University Question paper

End-Term Examination

Second Semester [MCA] – MAY 2005

Paper Code: MCA-102 Subject: Data Structure

Time: 3 Hours Maximum Marks: 60

Q. 1 (a) Define B-Tree

(b) Convert following infix expression into prefix and postfix

A* (B + C) * D/E .

(c) Give the difference between external and internal sorting. Give names of some

external sorting techniques.

(d) Define stack and give some application s of stacks.

(e) How many nodes are there on level I of a binary tree? Prove the answer.

(f) Define transitive closure of a graph.

(g) Define inverted files.

(h) Describe adjacency list representation of graph with the help of an example.

(i) Give two examples of Hash function.

(j) Give difference between complete and full binary tree.

UNIT - I

Q. 2 How polynomial are represented using linked list. Write program for addition of

two polynomials represented using linked list.

Q. 3 Explain with the help of algorithm how infix expression converted to postfix

expression using stack.

UNIT - II

Q. 4 Write Prim’s algorithm for finding minimum cost spanning tree. Show its

working on a graph.

Q. 5 Explain how trees can used for representation of disjoint sets. Explain Union of

find operations on these sets.

UNIT - III

Q. 6 Explain Merge sort algorithm and show its working on following members

4, 10, 2, 6, 8, 12, 5, 7

Q. 7 What is hashing? What are various types of Hash functions? What are various

methods of collision resolution?

UNIT - IV

Q. 8 What do you mean by file organization? Explain various file organization

techniques.

Q. 9 Write short notes on any two of the following Index techniques –

(d) Cylinder surface indexing

(e) Hashed Indexes

(f) Tree indexing.