AMIE Study Circle Blog

Choose the most appropriate one (10 x 2) 1. Given two sorted lists of size “m” and “n” respectively, the number of comparisons needed in the worst case by the merge sort will be: (a) m*n (b) max (m, n) (c) min (m, n) (d) m + n - 1 2. Time complexity of insertion sort algorithm in the best case is (a) O(n) (a) O(nlog 2 n) (c) O(n 2 ) (d) None of the above 3. Time complexity of quick sort algorithm in the worst case is (a) O(n) (b) O(nlog 2 n) (c) O(n 2 ) (d) None of the above 4. Time complexity of heap sort algorithm in the best, average and worst case is (a) O(n), O(nlog 2 n) and O(n 2 ) (b) O(n) O(n2) and O(nlog 2 n) (c) O(nlog 2 n), O(nlog 2 n) and O(nlog 2 n) (d) None of the above 5. Any string of bits of length n represents a unique non-negative integer between (a) 0 and 2 n-1  - 1 (b) 0 and 2 n  - 1 (c) 1 and 2 n  - 1 (d) None of the above 6. Which of the following expressions accesses the (i, j)th entry of an m*n matrix stored in a column-major form? (a) m*(i ...

Answer the following questions (10 x 2) 1. Binary search can be performed if data items are stored in an: (a) unordered array (b) ordered array (c) unordered linked list (d) ordered linked list 2. Strings can be defined directly by using the data type: (a) char (b) string (c) String (d) Str 3. The Linked list is preferred over arrays for the following operation: (a) search (b) insertion (c) bubble-sorting (d) heap-sorting 4. When the input size is not known in advance we prefer linked lists over arrays due to: (a) Static memory allocation (b) random memory allocation (c) heap allocation (d) dynamic memory allocation 5. What is the postfix representation of the following 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 / - 6. If a queue is implemented by a circular array QUEUE The number of elements in the queue if FRONT - 10 and REAR - 3 will be (number of memory locatio...

1. Time complexity of insertion sort algorithm in the best case is (a) O(n) (b) O(n log 2 n) (c) O(n 2 ) (d) None of the above 2. The prefix equivalent of the following infix expression is: a/b – c + d * e – a * c (a) - + - / a b c * d e * a c (b)  - - + / a b c * d e * a c (c) + - - / a b c * d e * a c (d) None of the above 3. In linked list representation, a node contains at least (a) Node address field, data field (b) Node number, data field (c) Next address field, information field (d) None of the above 4. The following sequence of operations is performed on a stack push(1) push(2), pop, push(1), push(2), pop, pop, pop, push(2), pop. The sequences of popped out values are (a) 2, 2, 1, 2, 1 (b) 2, 2, 1, 1, 2 (c) 2, 1, 2, 2, 1 (d) 2, 1, 2, 2, 2 5. For the following statement find the values generated for p and q?      int p = 0, q = 1;      p = q++;      p = ++q;      p = q--;      ...

Choose the correct answers for the following (2 marks each) 1. Which of the following sorting technique leads to minimum number of swapping? (a) Quick Sort (b) Selection Sort (c) Heap Sort (d) Insertion Sort 2. Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of n nodes? (a) O(l) (b) O (log n) (c) O (n) (d) O (n log n) 3. In a max heap, both the insertion and deletion operations can be performed in time: (a) O (log n) (b) O (n log n) (c) O(n) (d) O (n²) 4. A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is : (a)  log 2 (2) (b) n - 1 (c)  n (d) 2 n 5. The time complexity for evaluating a postfix expression is: (a) O(n) (b) O (n log n) (c) O(log n) (d) O (n²) 6. The following sequence of operations is performed on stack: PUSH (10), PUSH (20), POP, PUSH (10), PUSH (20), POP, POP, POP, PUSH(20), POP.  The sequence of values popped out is: (a) 20,10,20,10,20 (...

Multiple Choice Questions (2 marks each) 1. A mathematical-model with a collection of operations defined on that model is called (a) Data Structure (b) Abstract Data Type (c) Primitive Data Type (d) Algorithm 2. An algorithm is made up of 2 modules, M1 and M2. If the order of M1 is f(n) and M2 is g(n) then the order of algorithm is? (a) max (f(n), g(n)) (b) min (f(n), g(n)) (c) f(n) + g(n) (d) f(n) x g(n) 3. An array of n numbers is given, where n is an even number. The maximum as well as the minimum of these n numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed? (a) At lea st 2n  - 2  comp arisons, for some constant c, are needed (b) At most 1.5n - 2 comparisons are needed (c) At least nlog₂(2) comparisons are needed (d) None of the above 4. Heap allocation is required for languages (a) That support recursion (b) That support dynamic data structure (c) That use dynamic scope rules (d) All of the above 5. Which of the foll...