Maharashi Dayanand University (MDU) 2009 B.E Computer Science and Engineering DATA STRUCTURE & ALGOITHM (DSA) - Question Paper

B.E. third Semester (ECE)
Examination- December, 2009
DATA STRUCTURE & ALGORITHM
Paper Code: CSE-201-E

Time: three Hrs.
Max. Marks: 100

Note: Attempt 5 ques.. All ques. carry equal marks.

1. (a) What do you mean by the term Data Structure? explain the basic operations of data structures with examples.
(b) What is a 2-dimensional array? define the formula for calculating the address of any element of a 2 dimensional array.

2. (a) What is a circular queue? explain its advantages over linear queue.
(b) What do you understand by Dynamic Memory management? Create a circular link list using dynamic memory and show its advantages over linear linked list.

3. (a) What do you mean by Stack? describe with the help of algorithms for its operations e.g. PUSH and POP. define a method to convert an infix expression into a postfix expression with the help of an example.
(b) What do you mean by searching? explain and compare different search methods.

4. (a) Write an algorithm for complexity O(n) to obtain the Kth smallest element in an array num (n), where n and k are provided as input.
(b) What is meant by height balanced tree? Show insert and delete operations on it.

5. Propose a data structure that supports a special operation for finding smallest or largest element in O(1) time. Prove for such data structure the insert operation must take O(log2n) time.

6. (a) Write merge sort algorithm and derive the expression for its run time complexity in best, avg. and worst case.
(b) What is threaded binary tree? explain with the help of examples.

7. (a) What is graph? How can it be stored in memory? discuss BFT and DFT with the help of suitable examples.
(b) What is hashing? What is the condition for collision? How collision can be resolved?

8. Write short notes on any 2 of the following:-
i. Doubly linked list
ii. Asymptotic notations (Big O, T etc..)
iii. Priority Queues

Earning:   Approval pending.