**RTU Previous Exam Papers BE CS 3rd Semester**

**Data Structure and Algorithms January 2013**

**UNIT – I**

1.(a) Explain time and space complexity of an algorithm and also explain big 0, omega and theta notation with graph. Define array as data structure and its operation. Write an algorithm to read a M x N matrix using row major mapping.

**OR**

(b) What do you understand by descending order priority queue ? Explain the importance of heap in java language program execution.

How are 2-0 arrays implemented in memory ? Derive the formulae for finding the location of elements LOC using base address technique.** **

**UNIT – II**

2.(a) Define stack as important data structure. Explain its basic operation and implement a stack using linked list.

(b) Write algorithm for postfix expression evaluation. Show each step for the following postfix expression evaluation AB’t C*D- where A = % B * 1, C ~ 2, D =

OR

2. (a) Can the tower of Hanoi problem be solved using recursion ? (b) Circular queue is to be implemented using a array of 10 elements.

(b) Write the pseudo code for implementation of inserting an element in queue and checking whether queue is empty or not.

**UNIT – III**

3 (a) What is Josephas problem ? Write algorithm to create circular list and delete from circular list also.

(b) What is the significance of header in a linked list ? How can a polynomial be represent in a linked list ?

**OR**

3. (a) Write an algorithm to insert an element into a single linked list.

(b) A doubly linked list can be made circularly by setting the values of links in the first and last nodes appropriately. Discuss the advantage and disadvantages of circular doubly linked list in doing the various list operations.

**UNIT – IV**

4. (a) Write an algorithm for deleting a node from a binary search tree. Take all possible case.

(b) Insert the following list of characters in the binary search tree. Also traverse the tree in order D B L F H A N.

**OR**

4. (a) A random binary search tree having n nodes, where n = 2 – 1, for same positive integer K, is to be reorganized into a perfectly balanced binary search tree. Outline an efficient algorithm for this task. The algorithm should not use any memory locations other than those already used by the random binary search tree, fb) Insert the following list of element in an AVL tree ?

**UNIT – V**

5 (a) How symbol table is implemented with hasty table ? How the collision is resolving ?

(b) Write an algorithm for bubble sort. Sort the following list by your algorithm.

73, 49, 53, 12, 48, 10, 84, 70, 20, 16

**OR**

(a) What do you mean by graph data structure ? Explain the sequential and linked list implementation of graph data structure.

(b) Write short notes on the following :

(i) Selection sort

(ii) Quick sort

(iii) Merge sort.

Can i have the solution of this dsa question paper?