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 least 2n - 2 comparisons, 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 following need not be a binary tree?
(a) Search tree
(b) Heap
(c) AVL-Tree
(d) B-Tree
6. Which of the following is a collection of items into which items can be inserted arbitrarily and from which only the smallest item can be removed ?
(a) Ascending priority queue
(b) Descending priority queue
(c) FIFO queue
(d) None of these
7. A _______ search begins the search with the element that is located in the middle of the array.
(a) Serial
(b) Random
(c) Binary Search
(d) Parallel
8. The data structure required to evaluate a postfix expression is
(a) Stack
(b) Queue
(c) Array
(d) Linked-list
9. The five items: A, B, C, D and E are pushed in a stack, one after the other starting from A. The stack is popped four times and each element is inserted in a queue. Then two elements are deleted from the queue and pushed back on the stack. Now one item is popped from the stack.
The popped item is
(a) B
(b) E
(c) D
(d) C
10. Which of the following statements is false?
(a) Every tree is a bipartite graph
(b) A tree contains a cycle
(c) A tree with n nodes contains n - 1 edges
(d) A tree is a connected graph
Answer
1. (b) Abstract Data Type(ADT) is a data type, where only behaviour is defined but not implementation. Array, List, Map, Queue, Set, Stack, Table, Tree, and Vector are ADTs.
2. (a) There can be three cases possible with f(n) and g(n) -
Case A : f(n) > g(n)
In this case we take O(f(n)) the complexity of the algorithm as g(n) is a lower order term, we drop it.
Case B : f(n) < g(n)
In this case, we take O(g(n)) the complexity of the algorithm as f(n) is a lower order term, we drop it.
Case C : f(n) == g(n)
Time Complexity can be either O(g(n)) or O(f(n)) (which is equal asymptotically).
Hence, max(f(n), g(n))
3. (b) To find the smallest element in the array will take n−1 comparisons.
To find the largest element
a. After the first round of Tournament, there will be exactly n/2 numbers that will lose the round.
b. So the biggest looser (the largest number) should be among these, 50 losers. To find the largest number will take n/2 − 1.
Total Comparisons = (n - 1) + (n/2 - 1) = 1.5n - 2
4. (b)
- Heap allocation is required for languages that support dynamic data structures.
- Dynamic data structures are data structures that grow and shrink as you need them to by allocating and deallocating memory from a place called the heap.
- Dynamic data structures allocate blocks of memory from the heap as required, and link those blocks together into some kind of data structure using pointers.
5. (d) Search tree, heap and AVL tree can be of maximum of order 2. So, these must be a binary trees. But, in case of B-tree, the order of B-tree could be any number.
6. (a) An ascending priority queue is a collection of items into which Items can be inserted arbitrarily and from which only the smallest item can be removed.
7. (c) A binary search begins the search with the element that is located in the middle of the array. Binary search is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array. Even implementing binary search correctly requires attention to some subtleties about its exit conditions and midpoint calculation.
8. (a) A Stack is a linear data structure in which elements are inserted and deleted from one end only, i.e. top of the stack. It follows an order to insert the elements into the stack, which is known as LIFO (last in first out). Operations that are performed on a stack are : Push, Pop and peek.
9. (c) When five items: A, B, C, D, and E are pushed in a stack: Order of stack becomes: A, B, C, D, and E (A at the bottom and E at the top.) stack is popped four items and each element is inserted in a queue: Order of queue: B, C, D, E (B at rear and E at the front) Order of stack after pop operations = A. Two elements deleted from the queue and pushed back on the stack: New order of stack = A, E, D(A at the bottom, D at the top) As D is on the top so when pop operation occurs D will be popped out.
10. (b) Use the property that bipartite graphs have no odd-length cycles. Trees are graphs that are acyclic. Being acyclic implies there cannot be any cycles in the graph, including odd-length cycles. Therefore, every tree is a bipartite graph (no cycles).
---
- The study material for AMIE/B Tech/Junior Engineer exams is available at https://amiestudycircle.com
- If you like the post please share your thoughts in the comment section
Comments