## Data Structure & Algorithm Analysis - May 2013

### Information Technology (Semester 3)

TOTAL MARKS: 80

TOTAL TIME: 3 HOURS
(1) Question 1 is compulsory.

(2) Attempt any **three** from the remaining questions.

(3) Assume data if required.

(4) Figures to the right indicate full marks.
**1 (a)** Explain linear and non-linear data structure with example.(5 marks)
**1 (b)** What is recursion? State its advantages and disadvantages.(5 marks)
**1 (c)** What is AVL tree? Give example.(5 marks)
**1 (d)** Explain Abstract data type.(5 marks)
**2 (a)** Write any Pattern Matching Algorithm and explain it with suitable example.(10 marks)
**2 (b)** Write a program to implement queue using array.(10 marks)
**3 (a)** Write a program to search an element in an array using binary search technique.(10 marks)
**3 (b)** Write algorithm for heap sort and explain Descending heap with suitable example.(10 marks)
**4 (a)** Hash the following in a table of size 12. Use any two collision resolution technique.

98, 20, 94, 27, 67, 99, 41, 0, 4, 17, 2, 15.(10 marks)
**4 (b)** Write a program to implement a stack ADT using linked list.(10 marks)
**5 (a)** Write and explain QUICK SORT algorithm with suitable example.(10 marks)
**5 (b)** Write an algorithm to traverse a graph using :-

(i) Breadth first search

(ii) Depth first search (10 marks)
**6 (a)** Define Binary Tree. Write an algorithm to implement INSERTION and DELETION operation.(10 marks)
**6 (b)** What is Doubly Linked List? Write an algorithm to implement following operations :-

(i) Insertion (All Cases)

(ii) Traversal (Forward and Backward)(10 marks)

### Write short notes on (any four)

**7 (a)** Shortest Path Algorithm(5 marks)
**7 (b)** Priority and Circular Queue (5 marks)
**7 (c) ** Red and Black Tree(5 marks)
**7 (d)** Pattern Matching(5 marks)
**7 (e) ** Expression Tree.(5 marks)