Mahesh: CSE & IT 3rd SEMESTER

[EURCS 304 / EURIT 304]

B.Tech. DEGREE EXAMINATION

III SEMESTER

DATA STRUCTURES

(Effective from the admitted batch 2007–08)

(Common for CSE & IT branches)

Time: 3 Hours Max.Marks: 60

------------------------------------------------------------------------------------

Instructions: Each Unit carries 12 marks.

Answer all units choosing one question from each unit.

All parts of the unit must be answered in one place only.

Figures in the right hand margin indicate marks allotted.

-------------------------------------------------------------------------------------------

UNIT-I

1. a) Distinguish between linear data structures and non-linear

data structures. 6

b) What is indirect addressing? Explain with a suitable example. 6

2. a) What is an array? Compare and contrast array with lists. 6

b) Briefly explain single linked list. 6

UNIT-II

3. a) Explain the linked representation of stacks. 6

b) Discuss about the application of parenthesis matching. 6

4. a) Briefly explain the ADT queue. 6

b) Explain the application of machine shop simulation. 6

UNIT-III

5. a) Briefly explain the properties of binary trees. 6

b) Discuss the common binary tree operations. 6

6. a) Write the steps for AVL search tree insertion. 6

b) Enumerate the steps involved in inserting an element into

a B-Tree. 6

UNIT-IV

7. a) What is selection sort? Explain with a suitable example. 6

b) Compare the complexity analysis of merge sort and quick

sort. 6

8. a) Describe two hashing functions with suitable examples. 6

b) What is binary search? Explain with a suitable example. 6

UNIT-V

9. Briefly explain D I J K S T R A’S Algorithm. 12

10. Write algorithms for DFS and BFS algorithms and explain

with examples. 12

[03-07/IIIS/107]