B.E-B.E Computer Engineering DATA STRUCTURES (Karunya University, Coimbatore-2012)

Reg. No. ________                                                                                                                                                   

Karunya University

(Karunya Institute of Technology and Sciences)

(Declared as Deemed to be University under Sec.3 of the UGC Act, 1956)

 

End Semester Examination – November/ December - 2012

 

Subject Title: DATA STRUCTURES                                                                                                             Time: 3 hours

Subject Code:            09CS208                                                                                                                Maximum Marks: 100          

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              

Answer ALL questions

PART – A (10 x 1 = 10 MARKS)

 

1.         Convert the following infix expression into prefix and postfix notations.

            A – B / (C * D $ E)

2.         Define the term divide and conquer algorithm.

3.         Define priority queue.

4.         Write any two disadvantages of doubly linked list.

5.         What is pivot element in quick sort?

6.         What is a hash function?

7.         Define B-trees.

8.         Differentiate between full binary tree and complete binary tree.

9.         What are graphs?

10.       Expands DFS and BFS.

 

PART – B (5 x 3 = 15 MARKS)

 
11.       Write down the ideas of infix to postfix conversion.

12.  Briefly explain any two advantages using single linked list over doubly linked list and vice-versa.

13.  Write down the different types of sorting techniques.

14.  Insert the following elements into the B-tree.

       a g f b k d h m j e s i r x c l n t u p

15.  What is the difference between DFS and BFS?

 

PART – C (5 x 15 = 75 MARKS)

 

16.       What is stack? Discuss about the array and linked implementations of stack in detail.                   

(OR)

17.       Write a short note on the following:

            a.         Divide and conquer – Towers of Hanoi                                                                                                                                 (8)

            b.         Postfix expression evaluation                                                                                                                                                 (7)

 

18.       What is a queue? Implement the queue using list.                                      

(OR)

19.  Explain the different operations that can be performed on singly linked list. Write the algorithm for each operation.

 

20.       Discuss the linear search and binary search in detail.                                

(OR)

21.       What is a heap? Sort the following elements using heap sort.

            55 46 35 10 90 84 31                                                                

  
[P.T.O]

 

22.       What are different ways of traversing binary tree? Explain.                      

(OR)

23.       What is an AVL tree? Explain AVL trees with suitable illustrations.                    

 
24.       Explain graph traversals in detail.                                                               

(OR)

25.       Discuss about the minimum spanning tree with suitable example.             

Earning:  ₹ 5.50/-