How To Exam?

# North Maharashtra University 2008 B.E Computer Science and Engineering Data Structure And Files, S.E CSE, /E - Question Paper

Monday, 04 February 2013 02:20Web

North Maharashtra university exam May/June 2008
subject: Data Structure and Files,
Branch: Computer science and engineering.
Year : second year (semester 4th)

DATA STRUCTURES AND FILES MAY - JUNE 2008

TIsm l TV** Hour*    n    Max. Mark*; 100

________,__f t- y*

Instructions to Candidates :

1.    Do not write anything on question paper except Seat No.

2.    Answer any two questions from each unit Assume suitable data, If necessary

I. Figures to right indicate full marks

5 In place of algorithms / procedure / function, writing programs in C/C + '/SPARKS language are allowed with proper

UNIT -1

1.    a) Define the terms :    5

i) Data Type li) Data Object

iii) Deta Structure.

b) Write a procedure to ADD and DELETE elements from a

DEQUEUE ?    *

2.    a) Convert the following expressions into prefix and postfix form ;

0 Aa0*C + O-E/F G

l) -PaQaR*S    6

b) Write a function to convert a postfix expression to Infix form ? 4

3.    a) Dmcuh any one application of stack using an example ?    4

b) Gtve the stack based solution for expression verification containing various type* of parenthesis ? Aba wtitt the procedure for it ? 6

UNIT - II

f

Write procedure to Insert and Remove elements from a linked list maintained as a UFO list ?    5

Represent the multivariable polynomial

10x3y2* + 2x2y3*2 f 2xy*3 -7xV generalized list

without tag ?    5

Draw and discuss the use of *ach field in the data structure used by boundary tag method for dynamic storage management ?    5

Let DLL be a pointer to the first node in a doubly linked list. The data field of the node hold Roll number of students Write a procedure to delete a node just before a node holding a value X, where X is an integer variable holding roll number.    5

Write a procedure to add two polynomials A and 8 Also give the required data structure ?    10

UNIT Ill

identifier

(oj. a2, 03, 04)    flQCQ, print, read)

(Pl.P2.P3.P<)*(3.2.ll)    10

tot). <h- <I2> <13* <14) (3.2,1,1,1)

t

Obtain a height balanced tree, starting with an empty tree, on the following sequence of insertions of symbols using AVL algorithm : ADD, SUB, MUL, DIV, MOV, JMP. INC, DEC, PUSH, POP 10 If the post order traversal of a binary tree Is 30, 20, 45, 60, 50,

40. 90, 100, 130, 150, 120, 75 and the inorder traversal Is 20,30, 40,45, 50, 60, 75, 90, 100, 120, 130, 150.

Corutruct binaiy tr ?    %

........... - I__ _    j    " ii;

~    m m - ~    m - * - m * m m m     m m    m m m mm

b) Construct an>Hoffman tree for

(9l.q2.<J3. <J4. 9s. Q6)-(2, 4. 8.12,15,19).    5

UNIT - IV

10.    Sort the following numbers in ascending order using bubble sort and insertion sort technique. The numbers are :

75, 28, 42. 18, 33, 100, 60. Show each step dearty.    10

11.    Build a min-heap for following numbers :    1

75, 28, 42. 18, 33, 100, 60, 59.    10

12.    Discuss the need of hashing using an example ? Define Hash function ? Also discuss the problem of hash collission and its possible solutions using an example ?    10

UNIT - V

IS. a) What are linear indexes ? Compare the basic operations of hnear

index with file types ?    6

b) Describe a direct access file system and comment on Its

organization ?    *

14.    a) Write Procedure to perform following operations on a sequential file :

I)    Read a record wtth specific key value.

II)    Read all records in key order Abo define the record structure used

15.    Write algorithm to perform following operations on a relative file storing the record having fields PNR number, name of passenger and train number PNR number is the primary key.

ii) Delete a existing record

10

Hi) Read and display a record with specific key value.

*r it ** * Hf