Bengal Engineering and Science University 2007 B.E Computer Science and Engineering Data Structure and Algorithm - Question Paper
The ques. paper is with the attachment.
Ex/BESUS/ CS-302/07
B.E. (CST) Part-II 3rd Semester Examination, 2007
Data Structure & Algorithms (CS-302)
Time : 3 hours Full Marks : 70
Use separate answerscript for each half.
Answer SIX questions, taking THREE from each half.
Two marks are reserved for neatness & claritu of presentation in each half.
FIRST HALF
1. a) Saddle point of a matrix is defined as the point (s) which is (are) minimum in
the row and maximum in the column and vice versa. For example, for the following matrix there are two saddle points : A(l, 3) = 3 and A(3, 1) = 7.
Write an algorithm to determine the saddle point(s) of a given mxn matrix.
b) Derive the worst case time complexity of the algorithm that you have developed in 1 (a), assuming that there can be not more than 2 saddle points in any row/column.
c) Write a C function for insertion sort. [5+3+3]
2. a) What is a heap? How can a heap be used to represent a priority queue?
Describe algorithms to perform the operations of item insertion and removal in heap used to represent a priority queue.
b) Show that time complexity of merge sort is 0 (nlog2n) for an unsorted array of n elements. Assume n to be a power of 2. [(l+2+5)+3]
3. a) Write algorithms for inorder traversal of a binary tree.
i) using recursion,
ii) using a stack.
b) Given preorder and inorder traversal of a binary tree. Write an algorithm to construct the tree.
c) Discuss the advantages of binary search tree data structure over array and linked list. f(l+3)+5+2]
4. a) Define
i) order notation Big O,
ii) worst case and average case time complexity of algorithm.
b) Show that worst case time complexity of binary search algorithm is O (log2 n).
c) Explain how interpolation search works? What is its average case time complexity assuming the keys to be uniformly distributed? What is its worst case time complexity? |2+5+4]
5. a) Give examples of the following hashing methods
i) Digit-extraction hashing,
ii) Folding.
b) Explain different methods of collision resolution in hashing mentioning advantages and disadvantages of each method. [3+8]
6. a) Write pseudo code using linked list for the following
i) ENQUEUE
ii) DEQUEUE
During ENQUEUE operation consider the following separately
Queue is empty
Queue has only one node.
b) Identify the difference (if any) between POP operation in stack and DEQUEUE operation in queue. (4+4+3|
7. a) Change the following infix expression to postfix expression
((A - (B + C)) * D) / (E + F)
b) Write the routine for the above task using stack. Show all the intermediate values in stack for the evaluation. [3+4+4]
8. a) What are the two approaches to write repetitive algorithm?
*
b) Compare these two approaches citing one example. [2+9[
9. a) Define directed graph.
b) Define path and path length in directed graph.
c) Give adjacency matrix representation of the following digraph. Explain the demerit of it.
d) What is the other representation which overcomes the demerits.
|l+(l+l)+4+4]
10. Write short notes for the following : [5+6]
a) Usage of header node in a list
b) ADT.
|
Attachment: |
| Earning: Approval pending. |
