Course Code : MCS-021 Course Title : Data and File Structures Assignment Number : MCA(2)/021/Assign/07 Maximum Marks : 100 Weightage : 25% Last Date of Submission : 15 th October, 2007 This assignment has ten questions. Answer all questions. Rest 20 marks are for viva voce. You may use illustrations and diagrams to enhance the explanations. Please go through the guidelines regarding assignments given in the Programme Guide. Ensure that you don’t copy the program from course material or any other source. All the programs should be written using “C” language. Question 1: Define the term array. How are two-dimensional arrays represented in memory? Explain how address of an element is calculated in a two dimensional array. (8 Marks) Question 2: What is a sparse matrix? How is it stored in the memory of a computer? Write a function to find the transpose of a sparse matrix using this representation. (8 Marks) Question 3: What is the smallest value of n such that an algorithm whose running time is 100n2 runs faster than an algorithm whose running time is 2n on the same machine. (6 Marks) Question 4: Implement a Queue using a singly linked list L. The operations INSERT and DELETE should still take O (1) time. (10 Marks) Question 5: Two Binary Trees are similar if they are both empty or if they are both non-empty and left and right sub trees are similar. Write an algorithm to determine if two Binary Trees are similar. (10 Marks) Question 6: What is the difference between Prims algorithm and Kruskals algorithm for finding the minimum-spanning tree of a graph? Execute both Prims and Kruskals algorithms on the following graph. (10 Marks) Question 7: Give an AVL tree for which the deletion of a node requires two double rotations. Draw the tree and explain why two rotations are needed? (10 Marks) Question 8: Draw a B-tree of order 3 for the following sequence of keys: 2, 4, 9, 8, 7, 6, 3, 1, 5, 10 (6 Marks) Question 9: Explain the difference between depth first and breadth first traversing techniques of a graph. (6 Marks) Question 10: What are priority Queues? How can priority queues be implemented? Explain. (6 Marks)
CLICK HERE TO ATTACH WITH WORD FILE
|