Skip to main content

Data Structures - MCQs from AMIE exams (Summer 2019)

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) log2(2)
(b) n - 1
(c) n
(d) 2n

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
(b) 20,20,10,10,20
(c) 10,20,20,10,20
(d) 20,20,10,20,10

7. The worst case running times of Insertion sort, merge sort and Quick sort, respectively, are :
(a) Θ(n log n), Θ(n log n) and Θ(n2)
(b) Θ(n2), Θ(n2) and Θ(n log n)

(c) Θ(n2), Θ(n log n) and Θ(n log n)

(d) Θ(n2), Θ(n log n) and Θ(n2)


8. Which one of the following array satisfied the max-heap property?
(a) 25,12,16,13,10,8,14
(b) 25,14,13,16,10,8,12
(c) 25,14,16,13,10,8,12
(d) 25,14,12,13,10,8,16

9. Let G be any connected, weighted, undirected graph.
I. G has a unique minimum spanning tree, if no two edges of G have the same weight.
II. G has a unique minimum spanning tree, if for every cut G, there is a unique minimum weight edge crossing the cut.
Which of the above two statements is/arc TRUE ?
(a) Neither I nor II
(b) I only
(c) II only
(d) Both I and II

10. Which of the following is essential for converting an infix expression to the postfix form efficiently?
(a) Operator Stack
(b) Operand Stack
(c) Operator and Operand Stack
(d) Parse Tree

Answer

1. (b) In selection sort we repeatedly choose the smallest element, and put in the right place, hence total number of swaps are n-1 in worst case. Hence, section sort has the minimum number of swaps among the all sorting algorithms.

2. (c) Height of BST could have order n, that is, O(n). Where n represents a number of elements in BST.

3. (a) A max-heap is a complete binary tree in which the value in each internal node is greater than or equal to the values in the children of that node. 

4. (b) In a binary tree
Internal node,  N = (N + 1) leaf
Hence, N leaf = (N - 1) internal node

5. (a) The time complexity of the evaluation algorithm is O(n) where n is a number of characters in the input expression.

6. (b) 

7. (d) 

8. (c)  A tree is max-heap if data at every node in the tree is greater than or equal to its children’s data. In array representation of heap tree,  a node at index i has its left child at index 2i + 1 and right child at index 2i + 2.

9. (d) 

10. (a) Operator stack is used for converting infix to postfix expression such that operators like as +, *, (,), / are pushed in stack whereas operand stack is used for converting Postfix to Prefix evaluation such that operands are 7, 2, 1, 2 etc.

---
  • 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 


Labels:

Comments

Post a Comment

Popular posts from this blog

Mechanics of Fluids (Solved Numerical Problems)

Numerical The surface Tension of water in contact with air at 20°C is 0.0725 N/m. The pressure inside a droplet of water is to be 0.02 N/cm² greater than the outside pressure. Calculate the diameter of the droplet of water. (7 marks) (AMIE Summer 2023) Solution Surface tension, σ = 0.0725 N/m Pressure intensity, P = 0.02 N/m 2 P = 4σ/d Hence, the Diameter of the dropd = 4 x 0.0725/200 = 1.45 mm Numerical Find the surface tension in a soap bubble of 40 mm diameter when the inside pressure is 2.5 N/m² above atmospheric pressure. (7 marks) (AMIE Summer 2023) Answer: 0.0125 N/m Numerical The pressure outside the droplet of water of diameter 0.04 mm is 10.32 N/cm² (atmospheric pressure). Calculate the pressure within the droplet if surface tension is given as 0.0725 N/m of water. (AMIE Summer 2023, 7 marks) Answer: 0.725 N/cm 2   Numerical An open lank contains water up to a depth of 2 m and above it an oil of specific gravity 0.9 for a depth of 1 m. Find the pressure intensity (i) at t...
Post a Comment
Read more

Design of Electrical Systems (Solved Numerical Problems)

Important note There is something wrong with this question paper. It seems that instead of "Design of Electrical Systems" the IEI has given problems from "Electrical Machines". You should raise a complaint to director_eea@ieindia.org in this regard. Numerical A 120 V DC shunt motor draws a current of 200A. The armature resistance is 0.02 ohms and the shunt field resistance is 30 ohms. Find back emf. If the lap wound armature has 90 slots with 4 conductors per slots, at what speed will the motor run when flux per pole is 0.04 Wb?​ (AMIE Summer 2023, 8 marks) Solution The back EMF (E b ) of a DC motor can be calculated using the formula: E b = V - I a R a   Given: V = 120 V I a = 200 A R a = 0.02 ohms Substituting the values into the formula: E b = 120 − 200 × 0.02 = 120 − 4​ = 116 V Now, let's calculate the speed (N) at which the motor will run using the given flux per pole (φ p ). The formula to calculate the speed of a DC motor is: N = 60×E b /(P×φ p ) Wh...
Post a Comment
Read more

Energy Systems (Solved Numerical Problems)

Wind at 1 standard atmospheric pressure and \({15^0}C\) has velocity of 15 m/s, calculate (i) the total power density in the wind stream (ii) the maximum obtainable power density (iii) a reasonably obtainable power density (iv) total power (v) torque and axial thrust Given: turbine diameter = 120 m, and turbine operating speed = 40 rpm at maximum efficiency. Propeller type wind turbine is considered. (AMIE Winter 2023) Solution For air, the value of gas constant is R = 0.287 kJ/kg.K 1 atm = 1.01325 x 105 Pa Air density \(\rho  = \frac{P}{{RT}} = \frac{{1.01325x{{10}^5}}}{{287}}(288) = 1.226\,kg/{m^3}\) Total Power \({P_{total}} = \rho A{V_1}^3/2\) Power density \(\begin{array}{l}\frac{{{P_{total}}}}{A} = \frac{1}{2}\rho {V_1}^3\\ = \frac{1}{2}(1.226){(15)^3}\\ = 2068.87{\mkern 1mu} W/{m^2}\end{array}\) Maximum power density \(\begin{array}{l}\frac{{{P_{\max }}}}{A} = \frac{8}{{27}}\rho A{V^3}_1\\ = \frac{8}{{27}}(1.226){(15)^3}\\ = 1226{\mkern 1mu} W/{m^2}\end{array}\) Assuming eff...
Post a Comment
Read more