Gujarat Technological University 2010 M.C.A Data Structures (DS) - Question Paper
GUJARAT TECHNOLOGICAL UNIVERSITY
MCA. Sem-II Examination June 2011
Seat No. Enrolment No.
Subject code: 620001 Subject Name: Data Structures (DS)
Date: 20-06-2011 Time: 2:30pm TO 5:00pm
Total Marks: 70
1. Attempt all questions.
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.
Q.1 (a) Calculate the complexity of the following code by using Big 'O' notation: 07
1. scanf ("%d", &n);
2. for (i=1, m=n+66; i<=m; i++)
3. printf ("%d\n", i);
4. for (j =n/21, m=n/5; j<=m; j++)
5. printf ("%d\n", j);
Also compute the overall complexity of the given code.
(b) Write an algorithm to convert a given INFIX expression to POSTFIX 07 expression with brackets. ( A * B ) + ( C * D / E ) * F - G.
Q.2 (a) Write an algorithm for the multiplication of two polynomials in one 07 variable
(b) Construct an AVL tree from the following input list : 6 , 4 , 2 , 12, 10, 3. 07 Applying appropriate rotation.
OR
(b) Explain, with an example, the usefulness of height-balancing while 07 constructing a Binary Search Tree.
Q.3 (a) For a given problem with inputs of size n, Algorithms A and B are 07 executed. In terms of running time, one of the algorithms is O(n) and another is O(n log n). Some measured running times of these algorithms are given below_,_,_,_,
|
512 |
1024 |
2048 | |
|
A |
70 |
134 |
262 |
|
B |
42 |
86 |
182 |
Identify which algorithm is which and also find the running times. Which algorithm would you select for different values of n?
(b) Define multiple stacks. Write algorithm for its implementation. 07
OR
Q.3 (a) Show that the lower ordered terms and the constant terms do not matter in 07 computing the complexity of the algorithm in Big 'O' notation.
(b) Write an algorithm for multiplication of two sparse matrices 07
Q.4 (a) Write the algorithm for insertion and deletion of node in linked 07 representation of Queue and explain the benefits of linked representation against array representation of Queue. Specify two applications of queue
(b) (i) Define the terms "Internal path length" and "External path length" for a 07 binary tree.
(ii) Prove that for any binary tree of n nodes the External path length: Internal path length + 2n.
OR
Q.4 (a) What are the characteristics f a B-tree ? Construct a B-tree of order 3 from 07 the following data : 10, 20, 30, 40, 50, 60, 70, 80, 90, 100.
Showing the structure after each insertion.
(b) Explain Dijkstra's algorithm with the help of an example. Which shortest 07 path algorithm is the most efficient? And why?
Q.5 (a) Construct a heap for the list given below. Clearly indicate the changes in 07 each step.
29,14,9,64,76,34,88,14,96,26.
(b) What is Collision Resolution? Compare Linear probing and Quadratic 07 probing with giving suitable examples.
OR
Q.5 (a) Demonstrate Quick Sort on the following set of numbers. 07 91,16,53,31,98,12,79,82,63,77.
Take the last number as pivot. Show the order the number changes during each step of Quick Sort.
(b) Describe briefly Circular Linked List and a typical Node Structure used for 07 it. Write the pseudo code of an Algorithm to Delete a Node from Circular Linked List whose address is specified.
*************
2
|
Attachment: |
| Earning: Approval pending. |
