Data Structure MCQ

by | Jan 9, 2021 | MCQ | 0 comments

Data Structure MCQ

1) Which of the following is the correct statement of the array?

  1. The array is a storage that stores multiple data types at one time.
  2. The array is a function that runs at only compile-time.
  3. The array is an object in the data structure.
  4. Stores the similar data types.

Answer: (d) Stores the similar data types.

Explanation: The array is a non-primitive and linear data structure that stores the same data types. That means it stores only one type of data-type.

2) How do you initialize an array in the C language?

  1. int a[4] = (1, 2, 3, 4);
  2. int a[4] = {1, 2, 3, 4};
  3. int a(4) = (1, 2, 3, 4);
  4. int a(4) = {1, 2, 3, 4};

Answer: (b) int a[4] = {1, 2, 3, 4};

Explanation: Option (b) is the correct syntax to initialize an array in C language.

Syntax:

3) Suppose int is of 2 bytes, then what is the size of “int a[20];”?

  1. 2
  2. 20
  3. 40
  4. None of the above

Answer: (c) 40

Explanation: Given, size of array = 20

Each int size is 2 bytes.
= 20 * 2
= 40

4) The minimum number of fields with each node of a doubly linked list is __.

  1. One
  2. Two
  3. Three
  4. Four

Answer: (c) Three

Explanation: In general, each node of a double linked list always have three fields, i.e., the data field, the previous node field, and the next node field.

5) How many different characters is an eight-bit byte able to represent?

  1. 64
  2. 128
  3. 256
  4. 512

Answer: (c) 256

Explanation: 1-bit can have possible states, 21 = 2

2-bit can have possible states, 22 = 4

4-bit can have possible states, 24 = 16

8-bit can have possible states, 28 = 256

6) What is the notation used to evaluate arithmetic expressions using prefix and postfix forms?

  1. Polish and Reverse Polish notations
  2. Asymptotic Notation
  3. Postfix and Infix notations
  4. All of the above

Answer: (a) Polish and Reverse Polish notations

Explanation: Polish notation (prefix notation) refers to the notation in which the operator is placed before its two operands, such as (+ – A B C).

Reverse Polish notation (postfix notation) refers to the notation in which the operator is placed after its two operands, such as (A B C + – /).

7) ‘Push’ and ‘Pop’ are appropriate operations for which data structure?

  1. A linked list
  2. A queue
  3. A stack
  4. A two-dimensional array

Answer: (c) A stack

Explanation: A stack is a special type of linear data structure that works on LIFO’s principle (last in first out). When an item is inserted in the stack, it is called push operation, and when the item in the stack is deleted, it is called pop operation.

8) Modular programming relates to the use of which of the following?

  1. Data files
  2. Subroutines
  3. Conditional If statements
  4. Do loops

Answer: (b) Subroutines

Explanation: Modular programming is a process of subdividing a computer program into separate sub-programs. It is used in a variety of functions and subroutines, along with other components of the system.

9) Which of the following scheduling algorithm is non-preemptive?

  1. FCFS and Priority scheduling
  2. Shortest Remaining Time First
  3. Round-robin scheduling
  4. None of the these

Answer: (a) FCFS and Priority scheduling

Explanation: Non-preemptive scheduling is a CPU scheduling technique that takes the process resource (CPU time) and holds it until the process is finished. There are three types of non-preemptive scheduling: FCFS, SJN, and Priority scheduling.

10) Entries in a stack are “ordered”. What is the meaning of this statement?

  1. A group of stacks is a program of the sort
  2. There are Sequential entry that are one by one
  3. The stack is a very powerful data structure
  4. The stack function has a serial number

Answer: (b) There are Sequential entry that are one by one

Explanation: Elements are inserted into the stack one by one with the help of push operation because the stack follows the LIFO principle.

11) If the user wants to store a mixed type of data type, what type of the data structure will the user use to store the data?

  1. Array
  2. Structure and union
  3. Linked list
  4. None of the these

Answer: (a) Structure and union

Explanation: We use arrays for the same type of data, but if we want to store a data-type of mix type, the structure or union is used.

12) Which of the following is not the application of stack?

  1. Data Transfer between two asynchronous processes.
  2. A parenthesis balancing program
  3. Stack writer programming
  4. Location marking system

Answer: (a) Data Transfer between two asynchronous processes.

Explanation: Queue is used to data transfer between two processes in an asynchronous manner. For example – IO buffers, pipes, file IO etc.

13) Process of inserting an element in the stack is called ____?

  1. Create
  2. Push
  3. Pop
  4. Call

Answer: (b) Push

Explanation: Elements are inserted into the stack one by one with the help of push operation.

14) In a stack if a user tries to remove an element from an empty stack, it is called___.

  1. Overflow
  2. Underflow
  3. Pop
  4. Push

Answer: (b) Underflow

Explanation: If the stack is empty and the user tries to delete an element from it, then that particular situation is called “underflow”.

15) Which data structure is needed to convert infix notation to postfix notation?

  1. Graph
  2. Heap
  3. Array
  4. Stack

Answer: (d) Stack

Explanation: The stack retains precedence, so the stack data structure is used to convert the infix expression to a postfix expression.

16) How many passes does the insertion sort algorithm have?

  1. N
  2. N – 1
  3. N + 1
  4. N2

Answer: (b) N – 1

Explanation: When an array of n elements is given, n-1 pass is required in the insertion algorithm.

17) What is the average case running time of an insertion sort algorithm?

  1. log n * log n
  2. O(log n)
  3. O(log n2)
  4. O(n2)

Answer: (d) O(n2)

Explanation: Average case running time is O(n2)

18) Which of the following real-time example is based on the insertion sort?

  1. Collect the multiple data from the algorithm
  2. Arranging the pages of the book on a library shelf
  3. Arranging a pack of playing cards
  4. Time-sharing systems

Answer: (c) Arranging a pack of playing cards

Explanation: In insertion sort, we pick an element and insert it in its appropriate place. Therefore, “arranging a pack of playing cards” is a real-time example of the insertion sort.

19) What is the worst time complexity of bubble sort?

  1. log n * log n
  2. O(log n2)
  3. O(n)
  4. O(n2)

Answer: (d) O(n2)

Explanation: The worst time complexity of bubble is O(n2).

20) List out the areas in which data structures are applied extensively?

  1. C, C++, and java
  2. Compiler Design, Graphics, DBMS, OS, Numerical analysis
  3. Monitors, Keyboards, Mouses, and Laptops
  4. All of the above

Answer: (b) Compiler design, Graphics, DBMS, OS, Numerical analysis

Explanation: The name of those areas are Compiler design, Graphics, DBMS, OS, Numerical analysis, and Simulation.

21) There are 8, 15, 13, 14 nodes in 4 different trees. Which of them could have formed a full binary tree?

  1. 8, 14
  2. 15
  3. 13, 15
  4. 13

Answer: (b) 15

Explanation: In general, there are 2n – 1 nodes in a full binary tree.

FBT takes the only odd number. So, 8 or 14 cannot be FBT. 13 is a Complete Binary Tree (CBT) but not an FBT. So, the right answer is 15.

22) Convert the expression ((A + B) * C – D + F) to equivalent prefix forms?

  1. – * + A B C + D F
  2. + + – A B C + D F
  3. – * + A B C + D F
  4. – + + A B C * D F

Answer: (c) – * + A B C + D F

Explanation: Reverse the given expression and scan the expression from left to right.

Character Scanned Stack Expression
F F
+ + F
D + F D
– – F D +
C – F D + C
* – * F D + C
( – * ( F D + C
B – * ( F D + C B
+ – * ( + F D + C B
A – * ( + F D + C B A
) – * F D + C B A + *
F D + C B A + * –

Now, Reverse the expression (F D + C B A + * -).

Prefix notation: (- * + A B C + D F)

23) Convert the expression ((A + B) * C – D + F) to equivalent postfix forms?

  1. F D + C B A + * –
  2. F D + C B A + – *
  3. F D + C B A – + *
  4. F D + C B A * – +

Answer: (a) F D + C B A + * –

Explanation: Scan the expression left to right.

Character Scanned Stack Expression
F F
+ + F
D + F D
– – F D +
C – F D + C
* – * F D + C
( – * ( F D + C
B – * ( F D + C B
+ – * ( + F D + C B
A – * ( + F D + C B A
) – * F D + C B A + *
F D + C B A + * –

24) The average-case and worst-case complexities for merge sort algorithm are?

  1. O(n2), O(n2)
  2. O(n2), O(n log2n)
  3. O(n log2n), O(n2)
  4. O(n log2n), O(n log2n)

Answer: (d) O(n log2n), O(n log2n)

Explanation: Complexity table of Merge sort

Complexity Best case Average case Worst case
Time O(nlogn) O(nlogn) O(nlogn)

25) The worst-case running times of insertion sort, merge sort, and quick sort, respectively, are?

  1. O(n log n), O(n log n), and O(n2)
  2. O(n2), O(n2), and O(n log n)
  3. O(n2), O(n log n), and O(n log n)
  4. O(n2), O(n log n), and O(n2)

Answer: (d) O(n2), O(n log n), and O(n2)

Explanation: The worst-case running times of insertion sort, merge sort, and quick sort, respectively, are O(n2), O(n log n), and O(n2).

26) A binary search tree in which every non-leaf node has non-empty left and right subtrees are called a strictly binary tree. Such a tree with 19 leaves:

  1. Has exactly 36 nodes
  2. Has exactly 37 nodes
  3. Cannot have more than 37 nodes
  4. Cannot have more than 36 nodes

Answer: (b) Has exactly 37 nodes

Explanation:

N = 2 * i + 1

where, i = Internal node

i = leaves – 1

i = 19 – 1 = 18

N = 2 * 18 + 1

N = 37 nodes

27) Which technique is used in the Merge sort algorithm?

  1. Randomized technique
  2. Brute Force technique
  3. Divide and conquer technique
  4. Recursive technique

Answer: (c) Divide & conquer technique

Explanation: Divide & conquer technique is used in the merge sort. The divide & conquer is a technique in which a complex list of data is divided into the sub-list, and thus the list is split until only one element is left in the list and then these sub-lists are sorted and aligned.

28) Which of the following is the best and average time complexity of the bucket sort?

  1. O(n + k) and O(n + k)
  2. O(n + k) and O(n2)
  3. O(n2) and O(n2)
  4. O(n2) and O(n + k)

Answer: (a) O(n + k) and O(n + k)

Explanation: Complexity table of bucket sort

Complexity Best case Average case Worst case
Time O(n + k) O(n + k) O(n2)

29) Which data structure is used in Network Data Modal?

  1. Stack
  2. Array
  3. B-Tree
  4. Graph

Answer: (d) Graph

Explanation: A graph is a group of the nodes in which one node is associated with another node.

30) Which one of the following expressions is correct infix notation?

  1. A + B * C
  2. + * A B C
  3. A B + C * /
  4. A B C + * /

Answer: (a) A + B * C

Explanation: In the infix notation, every operator is in-between the operands. Therefore, the option (a) is the correct answer.

31) Which one of the following expressions is correct prefix notation?

  1. A + B * C
  2. + * A B C
  3. A B + C * /
  4. A B C + * /

Answer: (b) + * A B C

Explanation: In the prefix notation, operator is written ahead of operands. Therefore, the option (b) is the correct answer.

32) Which of the following is an illegal array definition?

  1. var x : array [‘a’… ‘z’] of REAL;
  2. var x : array [REAL] of REAL;
  3. var x : array [BOOLEAN] of REAL;
  4. Type FRUIT : (mango, apple, banana); var x : array [FRUIT] of REAL;

Answer: (b) var x : array [REAL] of REAL;

Explanation: Array index must be integers. Characters, Boolean, and Enumerators can be used in place of an integer but not real.

33) Where are the new node to the queue added?

  1. Rear-end
  2. Front-end
  3. Both ends
  4. Middle

Answer: c) Rear-end

Explanation: A queue has two ends: the front-end and rear-end. The node is added to rear-end and removed from the front-end.

34) Which of the following is the correct condition of stack overflow?

  1. top = Maxsize +1
  2. top = Minsize -1
  3. top = Size -1
  4. top = 0

Answer: (a) top = Maxsize +1

Explanation: “Top = Maxsize +1” is a correct condition of the stack overflow.

35) Which of the following is a non-linear data structure?

  1. Linked list
  2. Array
  3. Tree
  4. Stack

Answer: (c) Tree

Explanation: A linked list, array, and stack is a linear data structure, so the tree is the correct answer.

36) Suppose a merge sort takes 30 seconds for a 64-input size. How long will it take for a 512-input size?

  1. 4 minutes
  2. 7 minutes
  3. 6 minutes
  4. 10 minutes

Answer: (c) 6 minutes

Explanation: Merge sort time complexity is o (n log n)

C * 64 log 64 = 30

C * 64 * 6 = 30

C = 5 / 64

For 512 input size

(5 / 64) * 512 log 512 = t * 60

t = 6 minutes

Question numbers 37-39 are based on the following Binary Search Tree.

attach image here – data-structure-mcq-q37

37) If the user wants to insert a new node a = 55 in this tree, what is the right position of this node in this tree without violating the BST property?

  1. The correct position is the right child of node 18
  2. The correct position is the right child of node 52
  3. The correct position is the left child of node 54
  4. The correct position is the right child of node 54

Answer: (d) The correct position is the right child of node 54.

Explanation:

attach image here – data-structure-mcq-q37_2

38) If the user wants to remove node 60 after inserting the “a” = 55, what is the correct node for this position?

  1. 63 node
  2. 54 node
  3. 52 node
  4. 75 node

Answer: (a) 63 node

Explanation: Find the In-order successor of the node 60.

10, 16, 18, 52, 53, 54, 60, 63, 75, 80, 85, 87

The In-order successor of the node 60 is 63, so 63 is the correct node for this position.

39) If the user wants to insert a new node a = 84, after the “a” = 55 in this tree, what is the right position of this node in this tree without violating the BST property?

  1. The correct position is the right child of the node 87
  2. The correct position is the left child of the node 75
  3. The correct position is the left child of the node 80
  4. The correct position is the right child of the node 80

Answer: (d) The correct position is the right child of the node 80

Explanation:

attach image here – data-structure-mcq-q39

40) Which of the following is a linear data structure?

  1. Tree
  2. Graph
  3. Integer
  4. None of the these

Answer: (d) None of the these

Explanation: Tree and graph is a non-linear data structure, and the integer is a primitive data structure, so the option (d) is the correct answer.

41) In the data structure, which of the following is a hash function?

  1. Coupling and Square
  2. Square and Add
  3. Division, Mid square, and Folding
  4. None of the these

Answer: (a) Division, Mid square, and Folding

Explanation: List of the hash function:

  1. Division
  2. Mid square
  3. Folding
  4. Binary
  5. Extraction

42) Consider an array X [20, 10] with four words per memory cell and the base address of array X is 100. What is the address of X [11, 5]? Assume row-major storage.

  1. 565
  2. 555
  3. 560
  4. 525

Answer: (c) 560

Explanation: Let X[m, n] be the size of the array, w be the word size, then

X[©, j] = Base address of X + w(© * n + j)

© = 11, j = 5, n = 10

So, X[11 , 5] = 100 + 4(11 * 10 + 5)

                  = 100 + 4(115)

                  = 560

43) Which of the following is the correct asymptotic notation expression for the O- Big Oh?

  1. 0 <= f(n) <= C(g(n))
  2. 0 >= f(n) >= C(g(n))
  3. 0 <= C(g(n)) <= f(n)
  4. 0 >= C(g(n)) >= f(n)

Answer: (a) 0 <= f(n) <= C(g(n))

Explanation: O- Big Oh asymptotic notation

0 <= f(n) <= C(g(n))

44) Which of the following is correct asymptotic notation expression for the Ω-Big omega?

  1. 0 <= f(n) <= C(g(n))
  2. 0 >= f(n) >= C(g(n))
  3. 0 <= C(g(n)) <= f(n)
  4. 0 >= C(g(n)) >= f(n)

Answer: (c) 0 <= C(g(n)) <= f(n)

Explanation: Ω-Big omega asymptotic notation

0 <= C(g(n)) <= f(n)

Questions 45, 46 and 47 are based on the following tree structure.

attach image here – data-structure-mcq-q45

45) Which of the following expression show the correct pre-order traversal?

  1. 1, 2, 3, 5, 9, 6, 10, 4, 7, 8, 11, 12
  2. 1, 2, 3, 5, 6, 9, 10, 4, 7, 8, 11, 12
  3. 1, 2, 4, 7, 8, 11, 12, 3, 5, 6, 9, 10
  4. 1, 2, 3, 5, 9, 10, 5, 7, 4, 11, 8, 12

Answer: (a) 1, 2, 3, 5, 9, 6, 10, 4, 7, 8, 11, 12

Explanation: Pre-order-traversal (tree)

Step 1: Start with the root node (1 → 2)

Step 2: Left sub-tree (3 → 5 → 9 → 6 → 10)

Step 3: Right sub-tree (4 → 7 → 8 → 11 → 12)

            = 1 → 2 → 3 → 5 → 9 → 6 → 10 → 4 → 7 → 8 → 11 → 12

46) Which of the following expression show the correct post-order traversal?

  1. 9, 5, 6, 10, 3, 7, 11, 12, 8, 4, 2, 1
  2. 9, 5, 10, 6, 3, 7, 11, 12, 8, 4, 2, 1
  3. 9, 5, 3, 6, 10, 7, 4, 11, 8, 12, 2, 1
  4. 9, 10, 5, 6, 3, 7, 11, 12, 8, 4, 2, 1

Answer: (b) 9, 5, 10, 6, 3, 7, 11, 12, 8, 4, 2, 1

Explanation: Pre-order-traversal (tree)

Step 1: Start with left sub-tree (9 → 5 → 10 → 6 → 3)

Step 2: Right sub-tree (7 → 11 → 12 → 8 → 4)

Step 3: Root tree (2 → 1)

            = 9 → 5 → 10 → 6 → 3 → 7 → 11 → 12 → 8 → 4 → 2 → 1

47) Which of the following expression show the correct in-order traversal?

  1. 9, 5, 3, 10, 6, 2, 1, 7, 4, 11, 8, 12
  2. 9, 5, 10, 6, 3, 2, 1, 7, 11, 12, 8, 4
  3. 9, 5, 10, 6, 3, 2, 7, 11, 12, 8, 4, 1
  4. 9, 5, 3, 10, 6, 2, 7, 4, 11, 8, 12, 1

Answer: (d) 9, 5, 3, 10, 6, 2, 7, 4, 11, 8, 12, 1

Explanation: In-order-traversal (tree)

Step 1: Start with left sub-tree (9 → 5 → 3 → 10 → 6)

Step 2: Root of sub-tree (2)

Step 3: Right sub-tree (7 → 4 → 11 → 8 → 12)

Step 4: Root (1)

            = 9 → 5 → 3 → 10 → 6 → 2 → 7 → 4 → 11 → 8 → 12 → 1

48) Which of the following is not an inherent application of the stack?

  1. Job scheduling
  2. Evaluation of a postfix expression
  3. Reverse a string
  4. Implementation of recursion

Answer: (a) Job scheduling

Explanation: Postfix expression, String reversal, and “Implementation of recursion” are the applications of the stack, but the stack does not do job scheduling. So, option (a) is the correct answer.

49) Consider the following BST.

attach image here – data-structure-mcq-q49

Which node contains the 4th smallest element?

  1. B
  2. D
  3. E
  4. G

Answer: (c) E

Explanation: In a BST, value (left node) < value (root) < value (right node)

50) Consider the following expression tree representation:

attach image here – data-structure-mcq-q50

Which of the following expression is correct about the above tree?

  1. (1 * 2 + 3) ^ (1 + 2 * 3)
  2. (1 + 2 ^ 3) * (1 + 2 * 3)
  3. (1 + 2 * 3) ^ (1 + 2 * 3)
  4. (1 + 2 * 3) + (1 * 2 ^ 3)

Answer: (c) (1 + 2 * 3) ^ (1 + 2 * 3)

Explanation:

Step 1: Start with left sub-tree = (1 + 2 * 3)

Step 2: Root of the tree = (^)

Step 3: Right sub-tree = (1 + 2 * 3)

            = (1 + 2 * 3) ^ (1+ 2 * 3)

Submit a Comment

Your email address will not be published. Required fields are marked *