Sathyabama University 2008 B.E Computer Science and Engineering Data Structures

SATHYABAMA UNIVERSITY

(Established under section 3 of UGC Act, 1956)

 

Course & Branch: B.E/ B. Tech CSE/IT (Part Time)

Title of the paper: Data Structures & Algorithms

Semester: I Max. Marks: 80

Sub.Code: 6CPT0003 (2006 / 2007 JAN) Time: 3 Hours

 

PART A (10 x 2 = 20)

Answer All the Questions

1. Differentiate class and an instance.

2. What is Dynamic programming?

 

3. Differentiate Linear and non Linear Data Structure.

 

4. Define complete binary tree.

 

5. What is the time complexity of binary search and quick sort?

 

6. What is mean by sorting? Mention its types.

 

7. What is external sorting?

 

8. Define 0/1 knapsack problem.

 

9. Write the computing time for traveling salesperson problem.

 

10. Define optimal Solution.

 

 

 

 

PART B (5 x 12 = 60)

Answer All the Questions

11. Implement a queue so that each element of the queue holds a list of integers. Write the function add_Q and remove-Q for such queue.

(or)

12. Write an algorithm to insert a node beginning, middle and delete end of a node in the linked list.

 

13. Explain Binary tree with example and give implementation of all traversals.

(or)

14. Explain B-Tree with neat Examples.

 

15. Give a suitable example and explain Merge sort algorithms.

(or)

16. Explain quick sort algorithm with neat examples.

 

17. Explain the divide and conquer method with control abstractions and give example.

(or)

18. What is Knapsack problem? For the following knapsack instance, find an optimal solution

n = 7, m = 5

(p1,p2,p3,p4,p5,p6,p7) = (10,5,15,7,6,18,3)

(w1,w2,w3,w4,w5,w6,w7) = (2,3,5,7,1,4,1)

 

19. Explain Traveling Salesman application with example.

(or)

20. Explain 8-queens application with example.