Kurukshetra University 2009 B.Tech Computer Science and Engineering - Question Paper
Roil No. .........................Total Pages : 2
-v. *W":;
DATA STRUCTURES Paper : CSE-203(E)
rime : Three Hours] [Maximum Marks : 100
\'ote : Attempt five questions in all picking: at least one question from each unit
(a) How do you define a data structure ? Give different types of data" structures.
(b) Obtain the addressing formula for elements stored in an upper right triangular square sparse matrix A into a linear array B using both row major and column major representations. (8,12)
(a) Consider a sparse m x n matrix A with t non-zero terms. Write an algorithm for finding the transpose of A which is to be stored in an array B using 0(t + n) operations.
(b) Write a function that changes a decimal number to a hexadecimal number using stacks. (12,8)
(a) Write a fuuction for a singly linked list which deletes all nodes whose keys are negative.
(b) Implement a function to copy one queue to another when the queue is implemented as a linked list. (10,10)
(a) Write a function to reverse print a linked list. Now delete this linked list.
[P.T.O.
/I4300/K.D/40
(b) Write an algorithm that uses queue, to compress a string by deleting all space characters in the string. (10,10)
5. (a) A binary tree has 10 nodes. The preorder and inorder
traversals pf the tree are shown below. Draw the tree.
Preorder fcBADEFIGH
Inorder: ABCEDFJGIH
L '
(b) Calculate the maximum number of data entries in m-way tree of height h.
(c) What is the minimum number of keys in a B-tree of order 5 and height 3 ? (8,8,4)
6. (a) Write algorithms for AVL insert and ddeie.-
(b) Create a B+ tree of order 5 for the following data arriving in sequence :
92,24,6,7,11,8,22,4,5, 16,19,20,78. (10,10) UNIT-IV
7. (a) Write an algorithm that traverses a graph and returns
true if the graph is connected and false if it is disjoint.
(b) What is open addressing scheme of collision resolution ? Explain any two techniques for open addressing scheme. (10,10)
8. (a) Write algorithms for depth first search and breadth first
search using iteration.
(b) Write the algorithm for insertion sort and show each step for sorting when the given sequence is 7, 5, 3, 4, 10, 1, 9, 8, 5, 2. (12,8)
8102/14300/KD/40
2
|
Attachment: |
| Earning: Approval pending. |
