Punjabi University 2008 M.Sc Information Technology DATA AND FILE STRUCTURES - Question Paper
Tuesday, 05 February 2013 05:35Web
M.Sc-021 : DATA AND FILE STRUCTURES
Time: three hours
Maximum Marks: 100
(Weightage 75%)
Note : ques. number one is compulsory. Attempt any 3 ques. from the rest. All algorithms should be written nearer to 'C' language.
1. (a) Write an algorithm for the addition of 2 polynomials in 1 variable. (10)
(b) describe a stack. discuss the operations that can be performed on a stack. How are multiple stack implemented using arrays ? (10)
(c) describe and provide an example of a Minimum Cost Spanning Tree. Write at lowest 2 differences ranging from Kruskal's and Prim's Algorithms. (10)
(d) describe a heap. Sort the subsequent numbers using Heap Sort : (10)
2, 3, 81, 64, 4, 25, 36, 16, 9, 49
Clearly write all the steps involved in sorting the numbers.
2. (a) provide simplified big-O notation for the subsequent functions : (5)
(i) 30 n2
(ii) log n+3n
(b) describe dequeue. Wnte an algorithm for the implementation of a dequeue using arrays. (15)
3. (a) describe a tree, and a binary tree. elaborate the various ways of traversing a binary tree ? Write an algorithm for any 1 of the traversal methods. (14)
(b) Write an algorithm for the implementation of Binary Search. elaborate its Space and Time complexities ? (6)
4. (a) describe an AVL tree. In case an AVL tree becomes unbalanced, how will you balance it ? discuss with example(s). (15)
(b) discuss an indexed Sequential File Organisation. (5)
5. (a) describe a Splay tree. discuss the possible splay rotations. (10)
(b) Write an algorithm for the implementation of a Singly Linked List. (10)
Earning: Approval pending. |