Data Structures and Algorithm Analysis (MC211) : July 2005

Section A : Basic Concepts (30 Marks)
1. In analysis of algorithm, approximate relationship between the size of the job and the amount of work required to do is expressed by using _________
(a) Central tendency (b) Differential equation (c) Order of execution (d) Order of magnitude
(e) Order of Storage.
2. Pick the correct prefix form to the given infix expression {a*[b/(c-d)*f]/g}/[e+h]
(a) //*a/b*-cdfg+ch (b) abcd-f*/g/*eh+/ (c) //*a*/b-cdfg+eh (d) //*ab*/-cdfg+eh
(e) -//*a*/bcdfg+eh.
3. For recursive MinMax algorithm, the average, worst cases are __________
(a) 3n / 2 - 2 , 3n-4 / 2 (b) 3n / 2 – 1 , 3n / 2 – 2 (c) 3n – 2 / 2 , 3n / 2 – 1 (d) 3n / 2 – 4 , 3n – 4 / 4 (e) 3n – 1 , 3n – 1 / 2
4. P, Q and R are pointer variables. The statements below are intended to swap the contents of the nodes pointed to by P and Q. rewrite it so that it will work as intended.
P = Q; R = Q; Q = R;
(a) R=Q; P=R; Q=R; (b) R=P; P=P; Q=Q; (c) P=P; P=Q; R=Q; (d) R=P; P=Q; Q=R;
(e) P=R; R=Q; Q=R;
6. If f, r are the front, rear pointers respectively in a circular queue then the condition (( f – r + size) % size == 1) && ( (f != 0) (r != -1) ) represents
(a) Queue has only one element (b) Two Elements (c) More than 2 elements but not full (d) Impossible values (e) Queue is full.
7. For the following two statements, choose the correct answer.
I. n2 € O (n3 )
II. n =Ø ((n + 1) ! )
(a) (I) and (II) are TRUE
(b) (I), (II) are FALSE
(c) (I) is FALSE, but (II) is TRUE
(d) (I) is TRUE and (II) is FALSE
(e) (I) is TRUE but (II) can’t be defined.
8. The statement head->Link->Link->Link = NULL terminates a lin<=ked list after its ____ node.
(a) 2nd (b) 4th (c) 5th (d) 3rd (e) first.
9. For analyzing an algorithm, which is better computing time?
(a) O (100 Log N) (b) O (N) (c) O (2N) (d) O (N log N) (e) O (N2).
10. To implement the Round Robin algorithm, which of the following data structure is used?
(a) Stack (b) Linear Queue (c) Circular Queue (d) Priority Queue (e) Double Stack.
11. Let f, t: N-> R ≥ 0, and t (n) € O (f ( n ) ) iff t ( n ) <= c f ( n ) where c is positive real constant n >= n0, then no is ___________
(a) Upper bound (b) Lower bound (c) Duality value (d) Threshold value (e) Maximum value.
12. In a circular queue, we can disambiguate empty from full queue by
(a) Using a gap in the array
(b) Incrementing queue positions by 2 instead of 1
(c) Keeping a count of the number of elements
(d) (a) and (c) above
(e) (a), (b), and (c) above.
13. In a graph, a vertex with degree one is known as ___________
(a) Pendant vertex (b) Leaf (c) Root (d) End vertex (e) Internal.
14. Consider the usual algorithm for determining whether a sequence of parentheses is balanced. What is the maximum number of parentheses that will appear on the stack AT ANY ONE TIME when the algorithm analyzes: (()(())(()))
(a) 1 (b) 2 (c) 3 (d) 4 (e) 5 or more.
15. If a graph G = (N, E), where E= {ö}, then the corresponding adjacency matrix is _____
(a) Unit Matrix (b) Identity Matrix (c) Having Diagonal elements Zero
(d) Matrix with all 1’s (e) Zero Matrix.
16. Suppose we have an array implementation of the stack class, with ten items in the stack stored at data[0] through data[9]. The SIZE is 42. Where does the push method place the new entry in the array?
(a) data[0] (b) data[1] (c) data[9] (d) data[10] (e) data[11].
17. Breadth first search __________
(a) Scans each incident node along with its children.
(b) Scans all incident edges before moving to other node.
(c) Is same as backtracking
(d) Scans all the nodes in random order.
(e) Scans all the nodes in pre-order manner.
18. Provided the space is available, then to insert an element in the queue, we can use for the following structure struct queue
{
int Q[20];
int f, r;
}Q;
(a) ++Q.Q[Q.r] = x; (b) Q.Q[++Q.r] = x; (c) Q.Q[Q.r]++ = x; (d) Syntax error (e) Q.Q[Q.r++] = x;
19. Which method of traversal does not use stack to hold nodes that are waiting to be processed?
(a) Dept First (b) D-search (c) Breadth first (d) Back-tracking (e) Bounding.
20. If the characters 'D', 'C', 'B', 'A' are placed in a queue (in that order), and then removed one at a time, in what order will they be removed?
(a) ABCD (b) ABDC (c) DCAB (d) DCBA (e) ACDB.
21. The Knapsack problem where the objective function is to minimize the profit is ______
(a) Greedy (b) Dynamic 0 / 1 (c) Back tracking (d) Branch & Bound 0/1 (e) NP Knapsack.
22. I have implemented the queue with a linked list, keeping track of a front node and a rear node with two reference variables. Which of these reference variables will change during an insertion into a NONEMPTY queue?
(a) Neither changes (b) Only front changes (c) Only rear changes (d) Both change (e) (a) or (d) above.
23. For the given 5 jobs with penalties 6,3,4,8,5 respectively, the static state space tree is generated, then if the first job is selected but not the second job for the first two jobs consideration, then the rank of such situational node is ______
(a) 6 (b) 3 (c) 0 (d) 9 (e) 20.
24. Which of the following statements is/are TRUE?
i) ADTs define how data is stored and manipulated.
ii) Every linked list has to have at least one external pointer.
iii) Recursive solutions may be easier to understand.
(a) (i),(ii) and (iii) above (b) Only (i) above
(c) Only (ii) above (d) Only (iii)above
(e) Only (ii) and (iii) above.
25. Choose the correct answer for the following statements:
I. The theory of NP–completeness provides a method of obtaining a polynomial time for NP
algorithms.
II. All NP-complete problem are NP-Hard.
(a) I is FALSE and II is TRUE
(b) I is TRUE and II is FALSE
(c) Both are TRUE
(d) Both are FALSE
(e) II is TRUE, I can’t be determined.
26. Having the address of the node to be deleted in doubly linked list, the node can be deleted
(a) Without traversing the list
(b) Only after traversing the list from the head
(c) Only after traversing the list from the tail
(d) (b) or (c) above
(e) Can’t be deleted.
27. The Hamiltonian cycles problem uses the following line of code to generate a next vertex, provided x[ ] is a global array and kth vertex is under consideration:
(a) x[k] ← (x[k] + 1) mod n (b) x[k] ← (x[k]) mod (n) (c) x[k] ← (x[k] + 1) mod (n+1) (d) x[k] ← x[k+1] mod n (e) x[k] ← x[k+1] mod (n + 1)
28. Suppose cursor refers to a node in a linked list, what statement changes cursor so that it refers to the next node?
(a) cursor++; (b) cursor = link; (c) cursor += link; (d) cursor = cursor->link; (e) (a) and (c) above.
(Note:
struct cursor {
int data;
struct cursor *link;
};
29. The graph coloring algorithm’s time can be bounded by _________
(a) O(mnm) (b) O(nm) (c) O(nm. 2n) (d) O(mn.2n) (e) O(nmn).
30. For 0/1 KNAPSACK problem, the algorithm takes ________ amount of time for memory table, and______time to determine the optimal load, for N objects and W as the capacity of KNAPSACK.
(a) O(N+W), O(NW) (b) è(NW), O(N+W) (c) O(N), O(NW) (d) O(NW), O(N) (e) O(N+W), O(N+W).
Section B : Problems (50 Marks)
1. There is a requirement to keep track of calling sequence of nested function calls, but during the course of execution of the program, at any point of time the maximum number of function calls in the sequence is not known in advance. For this problem suggest an appropriate Data Structure and also write a simple ‘C’ program to illustrate the same, so as to
(i) Create the entries when ever a function call occurred
(ii) Delete an entry when ever the called function is terminated
(iii) To display the entries of all function calls in the nested sequence. (10 marks)
2. (a) What is a B – Tree? Insert the following entries into an empty B–Tree of order 4. Show stepwise construction of the B – Tree i c f a u n v e r s t y d p b m .
(b) Draw an AVL tree for the following set of data numbers. Also show at each step of insertion, which rotation technique is used to restore the balance if that insertion causes imbalance.
58, 45, 67, 89, 70, 20, 60, 10, 5, 8, 9 . (4 + 6 = 10 marks)
3. (a) Write the randomized quick sort algorithm. Justify to which category this one belongs to.
(b) Define mathematically the time complexity of merge sort algorithm. Justify why its complexity is same for all the cases. (5 + 5 = 10 marks)
4. (a) State the multistage graph problem. Write an algorithm for the forward approach.
(b) There is a map of ‘n’ districts. One has to draw the map as planar graphs with a given chromatic number ‘m’ write the algorithm for the above problem--- Also define its time complexity. (5 + 5 = 10 marks)
5. (a) Define ‘N queens’ problem. Also write an algorithm to solve the problem and discuss its complexity.
(b) Write briefly about the following:
i. P class and NP class
ii. NP complete and NP Hard
iii. Approximation algorithms. (4 + 6 = 10 marks)
Section C : Applied Theory (20 Marks)
6. Obtain an optimal tour for a Traveling salesman problem for the following data:
0 12 16 30
6 0 10 13
8 15 0 14
10 9 11 0 (8 marks)
7. What is collision? With the help of a complete ‘C’ program, show how it can be resolved using the chaining technique. List the advantages, disadvantages of this technique over the other techniques. (12 marks)
Suggested Answers
1. Answer : (d)
Reason : The order of the magnitude is the approximate relationship between the size of the job and the amount of work required to do. All the other options are not related to the asked
question.
2. Answer : (c)
Reason : According to the priority of the operators ( as first inner round brackets, then the inner
square brackets and hence so on.
3. Answer : (a)
Reason : According to the time analysis of the algorithm
4. Answer : (d)
Reason : According to the pointer manipulations of the variables
5. Answer : (b)
Reason : According to the limit rule for the omega notation ( Using the duality rule )
6. Answer : (e)
Reason : This is the one of the conditions to define the circular queue is full. All other are invalid
choices.
7. Answer : (d)
Reason : According to the limit rule for the big Oh notation and the theta notation
8. Answer : (d)
Reason : As the are only three nodes, and the list is pointed by head.
9. Answer : (a)
Reason : As this is a very small value when compared with all the other values.
10. Answer : (c)
Reason : According to the concepts of OS at process scheduling, circular queue is the best suitable one when compared with all the remaining one.
11. Answer : (d)
Reason : According to the mathematical definition of the big Oh notation, this is the Threshold value defines the upper limit on the size of the instance.
12. Answer : (d)
Reason : The option B is not the suitable one and not correct also, while the other two(a, c ) can be used
13. Answer : (a)
Reason : According to the definition of the graph, and the degrees of the vertex.
14. Answer : (c)
Reason : Use stack and increment counter by one if opening bracket is encountered, and decrement it by one if a closing bracket is encountered.
15. Answer : (e)
Reason : As E = empty set, means there is no any edge between any two set of vertices. And hence it is zero matrix.
16. Answer : (d)
Reason : As it is Stack always the items are pushed at the top of the stack if there is any space. Also data[10] is the next space as data[0] to data[9] are already filled.
17. Answer : (b)
Reason : As BFS always make use of the Queue.
18. Answer : (b)
Reason : Because first we have to increment the rear pointer and at that place we can insert an
element.
19. Answer : (c)
Reason : As D search, DFS uses stack, so BFS only uses queue and not the stack.
20. Answer : (d)
Reason : As Queue follows FIFO structure.
21. Answer : (d)
Reason : As there for the generation of the state space tree we use minimization of the profit.
22. Answer : (c)
Reason : As the queue is non empty and there is rear pointer pointing, this only must be incremented.
23. Answer : (b)
Reason : As we have considered first two jobs and have not considered the second job so we have to pay the penalty of second job.
24. Answer : (c)
Reason : As the other two options are not true and correct.
25. Answer : (a)
Reason : Because the theory of NP does not provides a way to obtain a polynomial time for NP
algorithms. Hence the I statement is wrong while the II statement is correct.
26. Answer : (a)
Reason : That is the advantage of doubly linked list. No need to traverse if the address of the desired node is provided.
27. Answer : (c)
Reason : As to find the next node to be traversed this is the formula.
28. Answer : (d)
Reason : All the other options are invalid operations.
29. Answer : (e)
Reason : As all the n nodes are required to be colored, and there are mn ways of coloring a specific node.
30. Answer : (b)
Reason : As the memory table ( 2 –D matrix ) contains N rows and W columns, hence it is NW, and for the composition of the optimal load it is up to N+W time it takes.