Data Structures and Programming Methodology - DSPM Paper 3

Download FREE Computer Science Engineering (CSE Engg. Branch) Previous 5 Years solved Regular and Reappear Question Papers B.tech PTU (2007, 2006, 2005, 2004, 2003) and related Placement HR - Technical Interview Questions for subject Data Structures and Programming Methodology

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