Himachal Pradesh University (HPU) 2007-3rd Sem B.Tech Computer Science and Engineering ( - Question Paper

B.Tech. IIIrd Semester Examination(2007)
Data Structure and Algorithm (CSE/IT)
Paper: IT(ID)-3003
Note: Attempt 5 ques. in all, selecting 1 every from parts A,B,C and D. part E is compulsory.

Section-A
1. What are the different measures of complexity of an algorithm? explain every of them with an example. [15]
2. What is a Doubly link list? Write an algorithm for every of the operation possible on Doubly link list. [15]
Section-B
3. Giving a Binary tree T, write algorithm to
(a) Count the number of Non-leaf elements of T.
(b) Check if the tree is balanced. [15]

4. What is a Binary search tree? Write the operation of insertion and deletion in a Binary search tree. [15]


Section-C
5. What are the different techniques for representation of a graph? discuss every of them with an example. [15]
6. Explain the Djikstra’s algorithm to obtain the shortest distance in a weighted graph. [15]


Section-D
7. Explain the subsequent searching algorithm with their complexity:
(i) Binary Search
(ii) Linear Search [15]

8. provided an array: 17 eight two three six 12 14 one 15
How these will be sorted in the following:
(a) Radix sort.
(b) Selection sort.
(c) Bubble sort. [15]
.


Section- E

8. Attempt the subsequent questions:
(i) What is the complexity of insertion sort?
(ii) What is a Data Structure?
(iii) Convert a^b^c+d*e-f into postfix expression.
(iv) Define Heap.
(v) What is a Circular link list?
(vi) What is a B-tree?
(vii) What is a height of a balanced tree?
(viii) What is an AVL tree?
(ix) How a node is represented in C?
(x) How an element is searched in singly link list?



[4*10=40]

Earning:   Approval pending.