Maharashi Dayanand University (MDU) 2010 B.Tech Data structure using 'c' - Question Paper

B.Tech.3rd Semester(Electronics and Communication Engg.) (Branch-III)
Examination,December-2010
DATA STRUCTURE USING 'C'
Paper-CSE-201-F
Time allowed:3hours Maximum Marks:100
_________________________________________________________________________________
Note: Attempt any 5 ques..

1 (a) Write an algorithm that determines whether a provided number is prime or not. 10
(b) What is an array?Discuss the different operations that are allowed on array data structure .Describe the formula for calculating the address of any element of a 2 dimensional array. 10

2 (a) Write a non recursive algorithm for reversal of a string of characters. 10
(b) Write a program that takes a list pointed by List and traverses it in such a manner that after travel the links of the visited nodes become reversed. 10

3 (a) define insertion sort algorithm and trace the steps of insertion sort for sorting the list :-12,19,33,26,29,35,22. obtain the total number of comparison made. 10
(b) What is circular queue? Write a program that implements a circular queue. 10

4. (a) Write an algorithm of complexity O(n) to obtain the Kth smallest element in an array num[n], where n and k are provided as input. 10
(b) discuss Binary search algorithm and compare it with linear search algorithm. 10

5. (a) describe heap and heap sort with suitable example. 10
(b) Write a program which counts the number of times a provided alphabet appears in a text file. 10

6. (a) Write merge sort algorithm and derive the expression for its run time complexity in best, avg. and wrost case. 12
(b) What is threaded binary tree? explain with the help of examples. 8

7. (a) Draw the directed graph that corresponds to the subsequent adjacency matrix:

V0 V1 V2 V3
V0 1 0 1 0
V1 1 0 0 0
V2 0 0 0 1
V3 1 0 1 0

Also write down the adjacency list corresponding to the
graph. 12
(b) Write an algorithm that inserts an edge into an undirected graph represented using an adjacency matrix. 8

8. Write shorts notes on any 2 of the
following: 20
(i) B Tree
(ii) AVL Tree
(iii) Skip Lists

Earning:   Approval pending.