Gujarat Technological University 2010 M.C.A Data Structures (DS) - exam paper

Seat No.:

Enrolment No.

GUJARAT TECHNOLOGICAL UNIVERSITY

MCA Sem-II Examination July 2010

Subject code: 620001 Subject Name: Data Structures

Date:

: 03 /07 /2010 Time: 11.00 am - 01.30 pm

Total Marks: 70

Instructions:

1.

Attempt all questions.

2.

Make suitable assumptions wherever necessary.

3.

Figures to the right indicate full marks.

Q.1

Attempt following.

14

(^a)

Give definition of Data structure. List various primitive and nonprimitive

data structure with example.

(b)

Write algorithm of change operation of stack.

^(c)

What is ADT? Explain it with example.

(d)

Compare recursion and iteration.

(e)

Write an algorithm to insert an element into circular queue.

(f)

Give definition and explain following.

1. Binary tree

2. Height of tree

⁽g⁾

Explain matrix and list representation of a graph

Q2

^(a)

Write an algorithm to convert parenthesized infix string to reverse polish

07

notation.

(b)

Write algorithm of factorial using recursion and iteration. Discuss which is

07

better and why.

OR

(b)

Write an algorithm for following

07

1. Delete an element from singly link list.

2. Delete an element form doubly link list.

Q.3

^(a)

Write an algorithm to traverse a tree in preorder using iteration. Take

07

example data and trace the content of stack for traversal.

(b)

Write short note on threaded storage representation of binary tree.

07

OR

Q.3

^(a)

Compare BFS and DFS.

06

(b)

Write short note on 2-3 tree.

04

^(c)

Write short note on Hashing function.

04

Q4

^(a)

Translate the infix string a + b * c - d / e * h ^A I ^A j into Reverse Polish

07

expression and trace the content of stack.

(b)

Construct AVL tree for the following set of months

07

March , May, August, April, January, December, July ,February, June,

October, September