Data Structures and Algorithm Analysis (MC211) : October 2005

Section A : Basic Concepts (30 Marks)
1. The suitable data structure to represent the data of rainfall of week days in ten cities of three states is
(a) Stack (b) Queue (c) Array
(d) Multi way tree (e) Connected graph.
2. The data structure which allows the insertion at both the ends, but allows the deletion at only one end is
(a) Output restricted Deque
(b) Input restricted Deque
(c) Circular queue
(d) Linear queue
(e) Priorityqueue.
3. Searching the linked list requires linked list be created in _________
(a) Ascending order (b) Descending order
(c) With underflow condition (d) Any order (e) Without underflow condition.
4. The time complexity of binary search in best, worst cases for an array of size N is
(a) N, N2(b) N, N (c) Log N, N2(d) 1, N log N (e) 1, log N.
5. How many minimum number of spanning trees, one can have from a given connected graph with Nnodes is having different weights for the edges.
(a) N-1 (b) One (c) 1/(N+1) 2NCN (d) 2NCN(e) N.
6. How many children do an external node of a binary tree of order N contains.
(a) N at least (b) 2 exactly(c) More than two (d) 0 (e) N at most.
7. In-order traversal of binary search tree implies visiting the nodes in __________
(a) Post-order
(b) The order of increasing magnitude of their key
(c) Pre-order
(d) The order of decreasing magnitude of their key N
(e) Arbitrary order.
8. For a binarytree the In-order traversal was found to be as HIGCEFD. Once the post-order traversal was conducted the output is IHGFEDC. What is the per-order for the given tree?
(a) CGDHEIF (b) GHICDEF (c) CGHIDEF
(d) CDEFGHI (e) Data insufficient and hence can’t be answered.
9. Breadth first search uses __________ as an auxiliary structure to hold nodes for future processing.
(a) Stack (b) Linked list (c) Graph (d) B-Tree (e) Queue.
10. Folding is a method of generating ________
(a) A hash function
(b) Index function for a triangular matrix
(c) Header node for a circular linked list
(d) Linear probing
(e) Chaining.
11. This algorithm scans the list by swapping the entries whenever pair of adjacent keys are out of desiredorder.
(a) Insertion sort(b) Quick sort(c) Shell sort(d) Bubble sort (e) Radix sort.
12. At a given node of a simple graph, the number of loops are _________
(a) More than one (b) Not more than one (c) Zero
(d) Exactly two (e) Equal to the number of nodes of the graph.
13. In the linked list implementation of the stack, where does the push member function place the new entryon the linked list?
(a) At the head
(b) At the tail
(c) After all other entries those are greater than the new entry
(d) After all other entries those are smaller than the new entry
(e) At null node.
14. I have implemented the queue with a circular array, keeping track of first, last, and count (the numberof items in the array). Suppose first is zero, and last is SIZE-1. What can you tell me aboutcount?
(a) count must be zero.
(b) count must be SIZE
(c) count must be SIZE-2
(d) count must be SIZE+1
(e) count could be zero or SIZE, but no other values could occur.
15. Convert the following postfix expression to a fully-parenthesized infix expression:
A B C - D E + * F * +
(a) (A + ((B - C) * (D + E) * F))
(b) (A + (((B - C) * (D + E)) * F))
(c) A + (((B - C) * (D + E)) * F)
(d) (A + ((B - C) * (D + E)) * F)
(e) A + ((B - C) * (D + E)) * F.
16. The linked list would be able to make use of a -------------whose value is the address of the location which stores the node.
(a) integer (b) float (c) char (d) void (e) pointer.
17. What kind of list is best to answer questions such as "What is the item at position n?"
(a) Lists implemented with an array
(b) Doubly-linked lists
(c) Singly-linked lists
(d) Doubly-linked or singly-linked lists are equally best
(e) Circular linked list implemented with priorities.
18. Consider the following pseudo code:
declare a stack of characters while (there are more characters in the word to read ) { read a character push the character on the stack } while ( the stack is not empty) { pop a character off the stack write the character to the screen } What is written to the screen for the input "carpets"?
(a) serc (b) steprac (c) carpets (d) ccaarrppeettss (e) stepr.
19. What is the value of the postfix expression 6 3 2 4 + - *
(a) Something between 5 and 15
(b) Something between -5 and -15
(c) Something between 5 and -5
(d) Something between -15 and -100
(e) Something between 15 and 100.
20. Suppose we have a circular array implementation of the queue type, with ten items in the queue storedat data[2] through data[11]. The current SIZE is 22.Where does the insert method place the new entryin the array?
(a) data[1](b) data[22](c) data[12](d) data[11](e) data[21].
21. The mathematical definition for Omega can be defined as, provided f,g:N􀃆R+andc is a positive constant and n > n0,
(a) f(n) ≥ c. g(n) ∀ n
(b) f(n) ≤ c. g(n) ∀ n
(c) f(n) ≥ c + g(n) ∀ n
(d) f(n) ≤ c + g(n) ∀ n
(e) f(n) ≤ g(n) ∀ n.
22. The θ notation is __________
I. Symmetric.
II. Reflexive.
III. Transitive.
(a) Only (I) above
(b) Only (II) above
(c) Only (III) above
(d) Both (I) and (II) above
(e) All (I), (II) and (III) above.
23. From the following pick the one which does not belongs to the same paradigm to which others belongsto.
(a) Minimum & Maximum problem
(b) Knapsack problem
(c) Selection problem
(d) Merge sort
(e) Quick sort.
24. The OBST algorithm in worst case takes _______ time if all c(i, j )’s and r(i, j)’s are calculated.
(a) Ο(log n) (b) Ο(n4) (c) Ο(n3) (d) Ο(n log n) (e) Ο(n2).
25. Read the following statements carefully, and choose the correct answer
I. For the Backtracking algorithmsstack data structure is used.
II. For the Branch-and-bound algorithms queue data structure is used.
(a) (I) is FALSE but (II) is TRUE
(b) (I) and (II) both are FALSE
(c) (I) is TRUE but (II) is FALSE
(d) (I) and (II) both are TRUE
(e) (II) is TRUE and (I) can’t be defined.
26. The weighted array used in TVS problems for the following binary tree is __________





(a) [ 1,2,3,0,0,4,0,5,6 ] (b) [ 1,2,3,0,0,4,0,5,0,0,0,0,6 ] (c) [1,2,3,4,5,6 ] (d) [1,2,3,0,0,4,5,6 ]
(e) [1,3,5,2,4,6 ]
27. Let f, +
(a) Limit rule (b) Rule of inference (c) Duality rule (d) Rule of consequences (e) Rule of symmetricity.
28. o, then no is ___________
(a) Upper bound (b) Lower bound (c) Duality value (d) Threshold value (e) Maximum value. 29. The time taken by nondeterministic sorting algorithm is ______
(a) O(1) (b) O(log n) (c) O(n2) (d) O(n log n) (e) O(n).

Section B : Problems (50 Marks)
1.
a. Define Algorithm. Also write about the characteristics and constraints on Algorithms. =
b. For the following statements, prove whether they are correct or wrong using appropriat rules.
i. 3n + 2 = O(n2)
ii. n3 + 105n2 θ (n∈Ω3)
iii. 33n3 + 4n2 (n/ log n 2)
iv. n2 ∈θ (n2. 2)
v. 100n2 + 102 = O(n) (5 + 1 + 1 + 1 + 1+ 1 = 10 marks)
2. a. What is a Hamiltonian Graph? Write an algorithm for finding the Hamiltonian Cycles of the given graph.
b. Write an algorithm to search an element following the divide and conquer rule. Also write about it time complexity. (5 + 5 = 10 marks)
3.
a. Write an algorithm to solve the Knapsack problem following the dynamic programming. Also write about its time complexity.
b. Define Sum of Subsets Problem, also write an algorithm to find the solution for the problem.
( 5 + 5 = 10 marks)
4.
a. Explain about the general analogy of the greedy algorithms. .
b. Write a simple C program to evaluate a given post fix expression. (4 + 6 = 10 marks)
5.
a. Write a ‘C’ function to create a Binary Tree.
b. What is meant by Minimum Cost Spanning trees? Write about the greedy approach to find the Minimum Cost Spanning trees. (5 + 5 = 10 marks)
Section C : Applied Theory (20 Marks)
6. Write a ‘C’ program to traverse the graph of ‘N’ nodes following the Depth First Search technique. (10 marks)
7. Write a ‘C’ program to sort an array following the divide and conquer merge sort technique. Also discuss about its time complexity. (9 + 1 = 10 marks)