North Maharashtra University 2011 B.E Computer Science and Engineering IM uploading a

NMU exam S.E.(NEW) MAY-2011 (COMPUTER)
DATA STRUCTURE & FILES (NEW)

TIME: three HOURS MAX.MARKS:100
________________________________________
INSTRUCTIONS: 1) ans ANY 2 SUBQUESTIONS FROM every UNIT.
2) ASSUME SUITABLE DATA WHEREVER NECESSARY.
3) FIGURES TO THE RIGHT shows FULL MARKS.
4) DRAWS NEAT DIAGRAMS WHEREVER NECESSARY.
________________________________________
UNIT-1
1. A) i) Write and discuss the algorithm for conversion of infix expression into post form
Justify it with subsequent example: A*B/C+D [5 marks]
ii) explain Tower of Hanoi as application of stack. [5 marks]
B) discuss the algorithm for circular queue along with proper example. Write
the procedure for addition of elements and deletion of elements for a circular
queue of five elements. [10 marks]
C) Write a note on: [10 marks]
i) Priority Queue
ii) Multiple Stack.

UNIT-2
2. A) discuss the concept of 1st fit, best fit and worst fit memory allocation strategy along
with proper example of every. [10 marks]
B) Write a note on: [10 marks]
i) Generalized list
ii) Circular linked list.
C) Compare and discuss single linked list with double linked list with respect to
subsequent operations:
i)Searching
ii) Traversing
iii) Insertion of new element
iv) Deletion of element.
State and discuss the advantages and disadvantages of double link list with
SLL w.r.t. above operations. [10 marks]

UNIT -3
3. A) Write and discuss the procedure (Algorithm) to delete the element from binary
Search tree. For every case justify the identical with proper diagram. [10 marks]
B) find a height balanced tree, starting with an empty tree, on the subsequent
Sequence of insertion of symbols using AVL algorithm:
SUB,POP,NOP,MOV,LDA,JMP,JNR,HLT,DEC,COM,BR,ADD. [10 marks]
C) i) discuss Huffman algorithm with example. [5 marks]
ii) Compare binary tree with other data structures. [5 marks]

UNIT-4
4. A) Suppose table T has 11 memory locations T[1], T[2], .. T[11] and suppose the file
F consists of eight records, P,Q,R,S,T,U,V,W with subsequent hash address 4,8,2,11,4,11,5,1 respectively. presume table T as circular. organize the above records in table T. list all the collisions. How the collisions can be resolved by linear probing method? compute Aug. no. of probes for successful and unsuccessful search. Justify the identical. [10 marks]
B) Write and discuss algorithm for insertion and deletion from heap tree. [10 marks]
C) i) Write algorithm for Radix sort. [5 marks]
ii) discuss quick sort with proper example. [5 marks]

UNIT-5
5. A) Compare sequential file organization with relative file organization. discuss different
Basic primitive operations given by sequential file organization. [10 marks]
B) discuss multi list file and inverted files. Consider the employee table provided beneath.
find multi list file organization and inverted file organization for it.


Record E# Name Occupation Degree Sex Location MS Salary
A 800 XYZ Programmer B.S. M Pune S 10,000
B 510 PQR Analyst B.S. F Pune M 15,000
C 950 ABC Analyst M.S. F Mumbai S 12,000
D 750 LMN Programmer B.S. F Pune S 12,000
E 620 DEF Programmer B.S. M Mumbai M 9,000

presume E# , occupation, sex and salary as key fields. [10 marks]
C) State and discuss advantages and disadvantages of the subsequent file organization:
i) Indexed-sequential
ii) Direct [10 marks]

***********************

Earning:   Approval pending.