480
. ,.j
B. E.(Co~P. En.gg.) IUrd Semester (New Scheme) Examination, December-2002
~!
.\
DATA STRUCTURES
Paper-CSE-20S-C Maximum'Marks : 100 TIme allowed: 3 hours Note: Attempt any five questions. 1.
Differenciate between built-in and user-defined data structures, giving two-two examples of each.
20
Obtain an addressing formula for an element A [i, j) in an array declared as A (bl: e. ' b2: e2) using roW major order representation. Assume a. as the base
2. (a)
address. 10 (b)
Discuss the implementation of the following data structures : (i)
Sparse matrices
(ii) Union. Discuss various applications of stacks.
3. (a) (b)
10
10
Define infix, postfix and prefix expressions. Convert the following into prefix and infix notations:
*493/+* (ii) ABC - D E F + * (i) 5 4 6 +
10
4. (a)
Why are queues that are housed in arrays are represented in circular than linear fashion ? 5 Describe
(b)
an algorithm to insert and remove an element from a linear queue. 15
480-3,400 P-2 (Q-8)
I
P.T.O.
\ •.. I
a
5 •. (a) 'Write'a routine insert that takes pOintetto a s~'" list and a pointer to a node, and inserts the node into its correct position in the linked list. 10 , (b)
Discuss the dynamic implementation of a doubly linked lists.
10
Following is the pre-order and in-order traversal of a
6. (a)
binary tree : Pre-order: ABC E D F In-order : ABEACF Construct a tree and explain the procedure. (b)
Write a program to count the number of leaves in a binary tree.
7.
8
12
Given the following values, show how the original heap tree would look:
14,27,52, 10,45,97,20,27, 10,4 Write and apply heapsort algorithm to sort Llte given data. Also, discuss its performance in terms of storage and time. 20 8. Write short notes on : (i)
Transitive closure
(ii)
Minimum spanning trees
(iii) Breadth first traversal.
480-3,400
7 7 6