| DATA STRUCTURES AND PROGRAMMING METHODOLOGY |
| PAPER NO.2 |
 |
 |
 |
|
| PUT ON JUNE, 2K2 |
| CS-207 Data Structures and Programming Methodology (B.Tech 3rd Semester, 1202) Time : 3 Hours Maximum Marks : 60 NOTE:- This paper consist of Three Sections. Section A is compulsory. Do any Four questions from Section B and any two questions from Section C Section-A Marks : 20 1(a) What is sparse about a sparse matrix ? (b) Is a two dimensional M X M array more or less efficient than a one dimensional array of extent M X M ? (c) Under what circumstances would you not use a quick sort. (d) Sort the given set of elements s = (1,7,3,2,0,5,0,8) using selection sort. (e) Given the following expression, represent the generalized list L L = (a,(d,(f,g),e),b,c) (f) Write the prefix form of (i) A ** -B + C (ii) -A + B - C + D (g) Running time of merge sort algrothim is............ (h) Draw the binary tree with threads to indicate the post order traversal for the expression A - B + C * E/F (i) From the followinf B tree of order 3 delete4 the key 30. Assuming that the tree is kept an a disk and one node may be fetched at a time how many disk accesses are neede ? (j) Differentiate between the internal sorting and external sorting. Section-B Marks:5 Each 2. How one would implement a queue if the elements that are to be placed on the queue are arbitary length strings ? How long does it takes to enqueue a string ? 3. Given an Array A(20.. 50,20..40). The elements are stored in Column Major Order. What is the starting location of A (32,23) ? 4. Write an algrothim (non-recursive) to implement quick sort. 5. Write a C function to insert an element into an AVL tree. 6. Define Threaded Binary tree. Write an algrothim for preorder trrnversal of threaded binary tree without a stack. Section-C Marks : 10 Each 7. Develop a C function (T,X, Y) which returns 1 if X is the ancestor of Y in the binary tree T and 0 otherwise. 8. Implement transposition of a sparse matrix in C-language. 9. Write an algrothim to find a longest simlpe path from a given vertex of a diagram. What is the time complexity of your program ? |
| <<PREVIOUS 1 2 |
 |