Gujarat Technological University 2010 M.C.A Data Structures (DS) Remedial ember- - Question Paper
Seat No. Enrolment No.
GUJARAT TECHNOLOGICAL UNIVERSITY
MCA. Sem-II Remedial Examination December 2010
Subject code: 620001 Subject Name: Data Structures
Date: 16 /12 /2010 Time: 10.30 am - 01.00 pm
Total Marks: 70
1. Attempt all questions.
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.
Q.1 (a) What is Heap? Describe Heap Sort Algorithm and write its pseudo code. You can 07 assume that CREATE_HEAP(K, N) function is available
(b) Given a vector K, consisting of N elements arranged in ascending order, write the 07 pseudo code for the Iterative Binary Search Algorithm to search a given element X.
For this algorithm, give the Order of Running Time and also the Order of Storage requirements.
Q.2 (a) Differentiate between Stack and Queue. Convert the following Infix expression to the 07 corresponding Reverse Polish expression:
(a + b| c| d) * (e + f / d)
Give the trace of the steps including Stack Contents and Rank in tabular form.
(b) Write the pseudo code for the Algorithms for (i) Inserting a given element at the rear 07 of a Circular Queue, and for (ii) Deleting and returning the last element from a Circular Queue.
OR
(b) Write a short note on Array, and Storage Structure for Arrays. Consider a 3- 07 dimensional array X whose subscripts limits are:
1 <= i <= 3; 1 <= j <= 4; -1 <= k <= 0 Give the Addressing Function for the element X[i, j, k] where the storage representation is in Row-major order. Justify your answer briefly.
Q.3 (a) Describe briefly Singly Linked List and a typical Node Structure used for it. What 07 will be a Node Structure for a linked-list representation of a polynomial in three variables. Write the pseudo code of an Algorithm to Insert a Node at the end of a Singly Linked List.
(b) Write pseudo code for the algorithm INSEND(X, FIRST) to insert a node at the end 07 of the List. X is a new element, and FIRST is a pointer to the first element of a linked linear list whose typical node contains INFO (i.e. information field) and LINK (i.e. pointer) fields.
OR
Q.3 (a) Describe briefly Doubly Linked List and a typical Node Structure used for it. Is it 07 same as Circularly Linked Linear List? Justify. Write the pseudo code of an Algorithm to Delete a Node from Doubly Linked List whose address is specified.
(b) Represent the following polynomial using the linked-list representation of a 07 polynomial in three variables: f(X, Y, Z) = 3X3
Represent first each of the following terms using the linked-list representation of a
polynomial and then give the (logical) steps to be followed if these terms are to be added one at a time at appropriate position in the latest f(X, Y, Z) polynomial:
(i) + 2 XY, (ii) + 7X2 , (iii) + XYZ, (iv) + 4Y2 Rules for appropriateness of the position of a term:
The priority of variable X is the highest while the priority of variable Z is the lowest. Thus,
The terms containing X will appear first and in such terms, the power of X cannot be higher than that of the previous term. In case the power of X is same as or lower than in the previous term, the power of Y cannot be higher than that of the previous term. Similarly, if the power of X as well as the power of Y are either same or lower than the corresponding powers in the previous term, the power of Z cannot be higher than that of the previous term.
Q.4 (a) (i) Describe the basic characteristics of Linear and Non-linear Data Structures. Write 03 the difference between the two types of structures.
(ii) Construct an Expression Tree for the following expression: 04
(a + b) * c - d / (e + f) * g / h State the result of Pre-order, In-order, and Post-order Traversal of this tree.
(b) What are the (i) Node Table Directory Structure, and (ii) Edge Structure used in 07 Breadth-First Search (BFS). Using these structures, display the storage representation of the following graph (Assume initial value of REACH to be false, that of DIST to be 0):
Write the trace of the procedure BFS(INDEX) for the above graph taking INDEX = 1 (allotted to Node A).
The pseudo code for the procedure BFS(INDEX) is give below:
1. [Initialize the 1st nodes DIST number and place node in queue]
REACH[INDEX] true
DIST[INDEX] 0
Call QINSERT(QUEUE, INDEX)
2. [Repeat until all nodes have been examined]
Repeat thru step 5 while queue is not empty
3. [Remove current node to be examined from queue]
Call QDELETE(QUEUE, INDEX)
4. [Find all unlabeled nodes adjacent to current node]
LINK LISTPTR[INDEX]
Repeat step 5 while LINK 4 NULL
5. [If this is an unlabeled node, label it and add it to the queue]
If not REACH[DESTIN(LINK)]
Then DIST[DESTIN(LINK)] DIST[INDEX] + 1 REACH[DESTIN(LINK)] true Call QINSERT(QUEUE, DESTIN(LINK))
LINK EDGEPTR(LINK) (Move down edge list)
6. [Finished]
Return
The procedure QINSERT(QUEUE, INDEX) inserts the INDEX value at the end of QUEUE, while the procedure QDELETE(QUEUE, INDEX) deletes the 1st element of QUEUE and returns the INDEX value.
OR
Q.4 (a) (i) Define the asymptotic notation Big-Oh (O). State briefly its significance in 03 Algorithm Analysis with an example.
(ii) What are the characteristics of Sparse Matrices? Is the following matrix a Sparse 04
|
matrix? " 0 0 |
0 |
4 |
0 |
0 |
1 |
0 |
|
0 G\ |
0 |
0 |
0 |
0 |
0 |
3 |
|
0 0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
6 0 |
7 |
8 |
0 |
0 |
0 |
0 |
|
2 o 0 |
0 |
0 |
0 |
0 |
2 |
0 |
|
0 0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
1 5 7 |
0 |
0 |
0 |
13 |
0 |
0 |
Represent the above matrix using two types of sequential representations so as to store only non-zero elements.
Q.4 (b) Write the pseudo code for recursive algorithm of Depth-First Search (DFS). Give the 07 trace of DFS (1, 0) for the first two (2) recursive calls of DFS for the graph shown in the Main part of Q. 4 (b) above.
Q.5 (a) What is 2-3 Tree? Give the structure of Leaf Nodes and Non-leaf Nodes used in 2-3 07 Tree. Fill-up the contents in each non-leaf node in the following 2-3 Tree:
How the above 2-3 Tree will be transformed if the number 10 is inserted as a new leaf node? Trace (write) each intermediate step with tree drawn for that step.
(b) What is the major application and utility of Hashing Function? What problem is 07 encountered if the key space is large and how this problem is resolved? Describe the Division Method of Hashing Function. Using the Division Method with m = 101, obtain the hash values for the following set of two keys (Use Pre-conditioning of the
keys by using 11, 12, ...., 36 for letters A, B,....., Z):
(i) PAY (ii) AGE
OR
Q.5 (a) Describe briefly Trie Structure. List down all the three-letter sequences built from a, 07 b, c beginning with the first letter as b. Take from this list of sequences one sequence at a time and tabulate a Trie structure in step-by-step manner. (Hint: Take Null character, i.e. A in addition to a, b, c.)
(b) In a Height-Balanced Tree, what are the cases causing imbalance and how 07 rebalancing is done in such cases. Write a step-by-step method (taking one number at a time) to develop Height-Balanced Tree (by rebalancing at each stage in case of imbalance) for the following sequence of numbers:
12, 6, 9, 11, 10, 4, 7
*************
4
|
Attachment: |
| Earning: Approval pending. |
