FYMCA (Engg. Faculty) (Semester - II),University Of Pune Question Paper,DATA STRUCTURE AND FILES,2014 Question Paper

University Of Pune Question Paper
FYMCA (Engg. Faculty)
DATA STRUCTURE AND FILES
(Semester - II) (2008 Pattern) (510910)
MAY/JUNE 2013 EXAMINATION
Time: 3 Hours] [Max. Marks : 70
Instructions to the candidates:
1) Answer Q1 or Q2, Q3 orQ4, Q5 or Q6 from Section –I and Q7 or Q8, Q9 or Q10, Q11 or Q12
from Section -II
2) Answers to the two sections should be written in separate answer books.
3) Assume Suitable data if necessary.
4) Draw sketches wherever necessary.
5) Figures to the right side indicate full marks.
SECTION I
Q1) a) What is sparse matrix? Explain fast transpose of sparse matrix. [4]
b) Consider integer array int a[10] [20] declared in C program. If the base address is
590, find the address of the element a[8] [15] with the row major and column
major representation.
[5]
c) Define the following with example:
 I. Ordered List
 II. ADT
 III. Data object
[3]
OR
Q2) a) Write a pseudo C code for the multiplication of two polynomials. [5]
b) Compare Linked representation with sequential representation. [4]
c) Write an ADT for addition of RATIONAL number. [3]
Q3) a) Write a pseudo C code for the insertion of an element at beginning & end in
doubly linked list.
[6]
b) Discuss insertion and deletion of an element in the singly linked list.
(Give supporting C code and pictorial Representation).
 [3]
c) Explain the representation of a linked list in memory. Also describe Garbage
Collection.
 [3]
OR
Q4) a) Represent multiplication of following two polynomials in the form of a circular [6]
[4366]-202 Page 2 of 3
linked list. Clearly show the node structure used for each polynomial.
 i) P(x) = x3
– 5x2
– 10 & Q(x) = 4x2
+ 7x
 ii) P(x) = 2.2x4
– 8.1x2
+ 5.6 & Q(x) = 3x3
+ 10x + 30
b) Write a pseudo C code for the deletion & insertion of an element in Circular
linked list.
[6]
Q5) a) Convert the following infix expression into postfix expression by showing the
content of stack for every iteration:
A * (B + D) / E – F * ( G + H / K)
[5]
b) Write an ADT for STACK. Write a program for STACK using array in C. [6]
OR
Q6) a) What is QUEUE? Write an algorithm of operation on QUEUE. [6]
b) Write a note on recursion; Also write an algorithm for Tower of Hanoi recursion
with illustration.
[5]
SECTION II
Q7) a) Write a non recursive procedure for the following traversal of binary tree:
 I) Preorder
 II) Inorder
[6]
b) Construct a binary search tree from the following:
50, 33, 44, 22, 77, 17, 10, 12, 22, 35, 30, 60, 40,
[6]
OR
Q8) a) Define the following:
 I) Graph
 II) Multigraph
 III) Loop
 IV) Connected graph
[4]
b) Using following graph construct the Adjacency Matrix, Adjacency List, Breadth
First Search (BFS) and Depth First Search (DFS) :
[8]
[4366]-202 Page 3 of 3
Consider starting point as “A”
Q9) a) Explain index Sequential Search with example. [4]
b) Write a pseudo „C‟ routine to sort the following numbers using quick sort. Show
all the passes to sort the values in ascending order :
56, 12, 84, 56, 28, 0, -13, 47, 94, 31, 12, -2
 [8]
OR
Q10) a) Compare Linear Search and Binary Search method. [3]
b) Write a C code for Bubble Sort and calculate its complexity. [5]
c) Define the following :
 I) Sort order
 II) Sort Stability
 III) Sort Efficiency and Sort passes
[4]
Q11) a) What is hashing? What are the characteristics of a good hash function? [6]
b) Compare Sequential and Direct access file. [5]
OR
Q12) a) What do you mean by collision resolution? Explain collision resolution
Techniques with example.
[11]

Share This