Data Structures and Algorithm Analysis (MC211) : January 2006

Section A : Basic Concepts (30 Marks)
1. Standard queue operations are
(a) empty(), fill(), place(), remove() (b) enque(), dequeue(), isempty(), isfull()
(c) init(), delete(), add() (d) isempty(), isfull(), fill(), remove()
(e) isempty(), isfull(), init(), delete(), add().
2. Assume that variable A is a sorted array of integers of length L. Consider the following code segment: int k=1, flag=0;
for ( ; k{
if (A[k-l] == A[k] ) flag = 1;
}
Which of the following best describes when variable flag is 1 after this code segment executes?
(a) Always (b) Never (c) If and only if array A really is sorted
(d) If and only if array A contains adjacent duplicate values
(e) If and only if all values in array A are the same.
3. Consider using binary search to look for a given value in an array of integers. Which of the following must be true in order for the search to work?
I. The values in the array are stored in sorted order.
II. The array does not contain any duplicate values.
Ill. The array does not contain any negative values.
(a) Only (I) above (b) Only (II) above (c) Both (I) and (II) above
(d) Both (I) and (III) above (e) Both (II) and (III) above.
4. A program is required to store and process information about the solar system. Which types of data structure would be most appropriate for storing the following respectively : (i) A list of the names of the planets, (ii) full details of a planet including distance from sun, diameter, atmospheric composition, etc,
(iii) a predetermined list of scientific observations made of the planet.
(a) (i) linked list (ii) structure (iii) linked list
(b) (i) array (ii) structure (iii) linked list
(c) (i) linked list (ii) array (iii) array
(d) (i) linked list (ii) linked list (iii) linked list
(e) (i) array (ii) structure (iii) array.
5. If data is a circular array of CAPACITY elements, and R is an rear index into that array, what is the formula for the index after R?
(a) (R + 1) % CAPACITY (b) R % (1 + CAPACITY) (c) (R % 1) + CAPACITY (d) R + (1 % CAPACITY) (e) R = R + 1.
6. In the linked list implementation of the queue, where does the insert method place the new entry on the linked list?
(a) At the head
(b) At the tail
(c) After all other entries that are greater than the new entry
(d) After all other entries that are smaller than the new entry
(e) This operation is not possible.
7. One difference between a queue and a stack is:
(a) Queues require linked lists, but stacks do not
(b) Stacks require linked lists, but queues do not
(c) Queue is used for complex programs and stack is used for simple programs
(d) Stacks use two ends of the structure, queues use only one
(e) Queues use two ends of the structure; stacks use only one.
8. Suppose cursor refers to a node in a linked list. What boolean expression will be true when cursor refers to the tail node of the list?
(a) cursor.next == null (b) cursor == null (c) cursor.data == null
(d) cursor.data == 0 (e) cursor.next == cursor.
9. Five statements about lists and stacks are below. Four of them are correct. Which one is incorrect?
(a) Lists can be implemented by using arrays or linked lists
(b) Lists are the dynamic data structures
(c) A stack is a special kind of list in which all insertions and deletions take place at one end
(d) A list is a sequence of one or more data items
(e) Stacks are easier to implement than lists.
10. For questions 10-11, refer to the following:
Queue q;
int i=1;
const int value = 10;
for ( ; i < value; i++) insert(i, q);
printf(“%d”, frontofqueue(q) ) ;
delete(q);
delete(q);
printf(“%d”, frontofqueue(q) ) ;
while (! isempty(q))
delete(q);
What is the output for the above code?
(a) 1, 3 (b) 1, 4 (c) No output (d) 9, 6 (e) 9, 7.
11. At the end of this code segment the queue
(a) Contains numbers 1 to 8 (b) Contain numbers 1 to 10 but we can't see them
(c) Is empty (d) Contains numbers 3 to 10 (e) Contains only 1.
12. What is the correct post fix form of the given infix expression a+b/(c+d)%e*(g-h/(i+j)*k)?
(a) abcd+/e%ghij+/k**-+ (b) abcd+e/%ghij+/k**-+
(c) ab+cd/e%ghij+/k**- (d) ab+cd+/e%ghij+/k*-*
(e) abcd+/e%ghij+/k*-*+.
13. With the “wrap around” implementation of a queue, which of the following code should be used to work out the next location of deletion?
(a) front++ (b) front-- (c) front = (front % max_queue_size) + 1
(d) front = (front ++) % max_queue_size (e) front = 0.
14. Which boolean expression indicates whether the number in two nodes (p and q) are the same? Assume that neither p nor q is null.
(a) p == q (b) p.data == q.data (c) p.link == q.link (d) p.link = q.link (e) p.data = q.data.
15. Which of the following statements is not true?
(a) An array is a data structure containing a number of items of the same type
(b) An array is normally used to store two or more items of data
(c) The lower bound of an array can be declared as any unsigned value
(d) The elements of an array can be initialized when the array is declared
(e) The number of elements in an array must be declared at compile time.
16. Consider searching for a given value in a large, sorted array. Under which of the following conditions is sequential search slower than binary search?
(a)Always (b) Never (c) When the value being searched for is the first element in the array
(d) When the value being searched for is the second element in the array
(e) When the value being searched for is the last element in the array.
17. The following data structure is used to store the values of the extreme ends of the freely hanging simple pendulum for every oscillation.
(a) Linked List (b) Priority Queue (c) Deque (d) Double Stack (e) Array.
18. The linked list which can be processed in either of the direction is
(a) Single linked list (b) Circular linked list (c) Stack implemented as linked list (d) Queue implemented as linked list (e) Double linked list.
19. What does a run-time analysis usually count?
(a) The number of arithmetic and other operations required for the program to run
(b) The number of megabytes required for the program to run
(c) The number of seconds required for the program to run
(d) The number of seconds plus the number of megabytes
(e) The number of seconds times the number of megabytes.
20. Which of these is the correct big-O expression for 1+2+3+...+n?
(a) O(log n) (b) O(n) (c) O(n log n) (d) O(n²) (e) O(1).
21. Which of the following formulas in Omega notation best represent the expression n²+35n+6?
(a) Ω ( n 3 ) (b) Ω ( n 2 ) (c) Ω ( n ) (d) Ω ( 35 ) (e) Ω ( 6 )
22. What term is used to describe an O(n) algorithm?
(a) Constant (b) Non Polynomial Deterministic (c) Logarithmic (d) Quadratic (e) Linear.
23. Express the formula (n - 2)*(n -4) using Ø notation :
(a) Ø ( n 2 ) (b) Ø (8) (c) Ø (log n ) (d) Ø (n ) (e) Ø ( 1 )
24. Read the following statements carefully and pick the right most option.
I. A linear algorithm to solve a problem must perform faster than a quadratic algorithm to solve the same problem.
II. An algorithm with worst case time behavior of 3n takes at least 30 operations for every input of size n=10.
(a) Both (I) and (II) are TRUE
(b) Both (I) and (II) are FALSE
(c) Only (I) is true but (II) depends upon the instance size.
(d) (I) is TRUE but (II) is FALSE
(e) (I) is FALSE and (II) is TRUE.
25. Which of the following are essential statement types for describing algorithms?
(a) Sequence (b) Selection (c) Repetition (d) All the above (e) A and B only.
26. When we say an algorithm has a time complexity of O (n), what does it mean?
(a) The algorithm has ‘n’ nested loops
(b) The computation time taken by the algorithm is proportional to n
(c) The algorithm is ‘n’ times slower than a standard algorithm
(d) There are ‘n’ number of statements in the algorithm
(e) The computation time taken by the algorithm is less than ‘n’ seconds.
27. Can we read a data item at any location of a list within a constant time (i.e. O(1))?
(a) Yes
(b) Yes, only if the list is implemented by pointers (i.e. linked-list)
(c) Yes, only if the list is implemented by an array
(d) No, we need O(n) computation steps no matter what kind of implementation is used
(e) No, as constant time is not possible for algorithms.
28. Sequential search has a time complexity of O(n), and binary search has a time complexity of O(log(n)). What difference will it make when the size n is 1000?
(a) You would not notice much difference because computers run very fast anyway
(b) As n is 1000, binary search is twice as fast as sequential search
(c) As n is 1000, binary search is 10 times as fast as sequential search
(d) As n is 1000, binary search is 10 times as slow as sequential search
(e) As n is 1000, binary search is 100 times as fast as sequential search.
29. Read the following statements carefully, and choose the correct answer.
I. The Ω notation is Anti Symmetric _
II. The big Oh notation is Semi Equivalence.
(a) (I) is FALSE but (II) is TRUE (b) Both (I), (II) are TRUE
(c) (I) is TRUE but (II) is FALSE (d) Both (I), (II) are FALSE
(e) (II) is TRUE and (I) cannot be defined.
30. Find the odd one out.
(a) Bin-Packing Problem (b) TVSP Problem (c) Knap Sack Problem
(d) OBST Problem (e) Sum of Sub Sets Problem.
Section B : Problems (50 Marks)
1. a. Following is a simple code of linked list, the statement in bold ( reverse ) is a function call to reverse the linked list. Write the appropriate ‘C’ function (definition ) to this function call.
typedef struct nodetype
{
int data;
struct nodetype *next;
}node; /* ADT Of Linked List Node */
void main( )
{
NODE *first;
….
first = create( );
….
reverse( &first );
….
}
b. To find the solution for 0/1 Knapsack problem, Backtracking strategy is adopted. Write an algorithm for this strategy along with its bounding function. (4 + 6 = 10 marks)
2. a. There are N Queens, which are required to be placed on an 8x8 chessboard such that no two Queens are there on the same row and same column. Write the algorithm to solve this problem.
b. Write a ‘C’ functional code to create a Binary Search Tree. (5 + 5 = 10 marks)
3. a. Let there be a graph with ‘N’ nodes. One would like to find the shortest path for all the pair of nodes in the graph. Write a ‘C’ program to find the solution for all pairs shortest path problem.
b. Write a ‘C’ function to find the height of the binary tree. (6 + 4 = 10 marks)
4. a. Write a ‘C’ program to sort an array of size ‘N’ using the Heap sort technique.
b. Write an algorithm to find the minimum spanning tree following Kruskal’s technique.
(6 + 4 = 10 marks)
5. a. Find the shortest path for the traveling salesperson problem for the following data.
b. Write a ‘C’ function to count the number of nodes in a binary tree. (6 + 4 = 10 marks)
Section C : Applied Theory (20 Marks)
6. Write a program in ‘C’ to sort the given array of ‘n’ numbers using the divide and conquer technique where the division is made about the pivotal element. Also prove that its time complexity in worst case is O(n2). (8 + 2 = 10 marks)
7. a. Explain briefly about P-Class and NP-Class problems.
b. There is a data structure where the elements of it are processed based on first come first serve basis. What can be the good ADT for such a data structure? Write and explain it briefly.
(5 + 5 = 10 marks)
Suggested Answers
1. Answer : (b)
Reason: As fill( ), place( ), add( ),empty( )are not the standard operations on queue, while
enque ( ), dequeue( ), isempty( ), isfull( ) are the standard one.
2. Answer : (d)
Reason: Because this is an array, and k is the index. So k, k-1 are the adjacent index
values.
3. Answer : (c)
Reason: Because the precondition for binary search is, the array must be there in sorted
order, should not contain duplicate values and may have positive or negative values.
4. Answer : (e)
Reason: To keep track of the planets a fixed size array is enough as the number of
plants is finite value. In addition, to keep track of complex information as a single logical unit structure is the best suitable data structure. For predetermined list array is suitable.
5. Answer : (a)
Reason: As the circular queue is given, if the empty places are there at any place and
rear pointer R is a rear index, then this is the best ever formula to increment R. All other are not valid or appropriate one.
6. Answer : (b)
Reason: Because, in queue always the new entries are inserted at the end of queue, no
matter the queue is implemented as array or linked list.
7. Answer : (e)
Reason: As all the other options are meaning less.
8. Answer : (a)
Reason: As the ‘next’ field of the node is holding NULL address, means it is the last
node .
9. Answer : (d)
Reason: As in lists only one data item of some type can only be stored. More data
items can’t be stored in a list.
10. Answer : (a)
Reason: As using insert we are inserting the elements in queue are 1, 2, 3, 4, 5, 6, 7, 8,
9. Then using printf statement we are displaying the first element, then we are
deleting the front element twice (i.e. 1, 2) then again we are displaying front element.
11. Answer : (c)
Reason: As using ‘while loop’ we have removed all the elements. Queue becomes empty.
12. Answer : (e)
Reason: Once we convert it all the other options are wrong except E
13. Answer : (d)
Reason: As in circular queue all the other options are not correct to identify the location pointed by front pointer where the recent deletion is made.
14. Answer : (b)
Reason: As we are comparing the data of both of the nodes, we have to check for the
data, a member of nodes p, q. Also we have to use relational operator( ==).
15. Answer : (c)
Reason: As there is no any syntax to declare the lower bound of the array except the
size of the array which can be declared.
16. Answer : (a)
Reason: As in all the cases the time taken by sequential( linear) search is O(n) which is
greater than the time taken by binary search which is O(log n).
17. Answer : (d)
Reason: As the other data structures are not suitable to store the elements from both of
the ends simultaneously.
18. Answer : (e)
Reason: As the Doubly linked list contains two pointers to keep track the address of
both the previous and next nodes.
19. Answer : (c)
Reason: All the other options are meaning less. Because for run-time analysis, the
number of operations and memory is not considered, but the unit time(i.e., seconds)
20. Answer : (d)
Reason: Because this the summation of the first ‘n’ numbers, that is n(n+1)/2 => (n2+n)/2 => then by ignoring the lower order terms and the constants this becomes n2.
21. Answer : (b)
Reason: As the given expression is a quadratic equation of degree 2, then by ignoring
the constants and lower order terms, the highest term is n2, and hence it is Ω ( n 2 ).
22. Answer : (e)
Reason: Because it is a single term of degree one. And all the remaining options are wrong.
23. Answer : (a)
Reason: Again this is a polynomial of degree 2 i.e. n2 – 6n + 8. And hence n2 according to above reason of Question (21).
24. Answer : (d)
Reason: As the first statement is true according to the definition of linear algorithms, the second is false as 30 operations are not needed.
25. Answer : (d)
Reason: Because all are essential for the algorithm to state the solution of a given problem.
26. Answer : (b)
Reason: As all the other options are meaning less and are wrong.
27. Answer : (c)
Reason: For an array implementation, we can find the given location straightway with the index value and hence it takes constant time. But for a linked list, we have to follow the pointers one by one. The cost of this is proportional to the size of the list.
28. Answer : (e)
Reason: log(1024) = 10, 1000/log(1000) is roughly equal to 1000/10 = 100
29. Answer : (b)
Reason: According to the definitions of Omega, Big Oh notations.
30. Answer : (a)
Reason: As Bin-Packing problem belongs to NP ( Non Deterministic Polynomial) hard problems and the remaining all are Deterministic polynomial time algorithms.