# Data Structure MCQ

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

- The array is a storage that stores multiple data types at one time.
- The array is a function that runs at only compile-time.
- The array is an object in the data structure.
- 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?

- int a[4] = (1, 2, 3, 4);
- int a[4] = {1, 2, 3, 4};
- int a(4) = (1, 2, 3, 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:**

1 |
data_type array name[size]; |

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

- 2
- 20
- 40
- 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 __.

- One
- Two
- Three
- 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?

- 64
- 128
- 256
- 512

**Answer:** (c) 256

**Explanation:** 1-bit can have possible states, 2^{1} = 2

2-bit can have possible states, 2^{2} = 4

4-bit can have possible states, 2^{4} = 16

8-bit can have possible states, 2^{8} = 256

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

- Polish and Reverse Polish notations
- Asymptotic Notation
- Postfix and Infix notations
- 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?

- A linked list
- A queue
- A stack
- 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?

- Data files
- Subroutines
- Conditional If statements
- 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?

- FCFS and Priority scheduling
- Shortest Remaining Time First
- Round-robin scheduling
- 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?

- A group of stacks is a program of the sort
- There are Sequential entry that are one by one
- The stack is a very powerful data structure
- 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?

- Array
- Structure and union
- Linked list
- 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?

- Data Transfer between two asynchronous processes.
- A parenthesis balancing program
- Stack writer programming
- 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 ____?

- Create
- Push
- Pop
- 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___.

- Overflow
- Underflow
- Pop
- 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?

- Graph
- Heap
- Array
- 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?

- N
- N – 1
- N + 1
- N
^{2}

**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?

- log n * log n
- O(log n)
- O(log n
^{2}) - O(n
^{2})

**Answer:** (d) O(n^{2})

**Explanation:** Average case running time is O(n^{2})

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

- Collect the multiple data from the algorithm
- Arranging the pages of the book on a library shelf
- Arranging a pack of playing cards
- 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?

- log n * log n
- O(log n
^{2}) - O(n)
- O(n
^{2})

**Answer:** (d) O(n^{2})

**Explanation:** The worst time complexity of bubble is O(n^{2}).

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

- C, C++, and java
- Compiler Design, Graphics, DBMS, OS, Numerical analysis
- Monitors, Keyboards, Mouses, and Laptops
- 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?

- 8, 14
- 15
- 13, 15
- 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?

- – * + A B C + D F
- + + – A B C + D F
- – * + A B C + D F
- – + + 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?

- F D + C B A + * –
- F D + C B A + – *
- F D + C B A – + *
- 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?

- O(n
^{2}), O(n^{2}) - O(n
^{2}), O(n log_{2}n) - O(n log
_{2}n), O(n^{2}) - O(n log
_{2}n), O(n log_{2}n)

**Answer:** (d) O(n log_{2}n), O(n log_{2}n)

**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?

- O(n log n), O(n log n), and O(n
^{2}) - O(n
^{2}), O(n^{2}), and O(n log n) - O(n
^{2}), O(n log n), and O(n log n) - O(n
^{2}), O(n log n), and O(n^{2})

**Answer:** (d) O(n^{2}), O(n log n), and O(n^{2})

**Explanation:** The worst-case running times of insertion sort, merge sort, and quick sort, respectively, are O(n^{2}), O(n log n), and O(n^{2}).

### 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:

- Has exactly 36 nodes
- Has exactly 37 nodes
- Cannot have more than 37 nodes
- 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?

- Randomized technique
- Brute Force technique
- Divide and conquer technique
- 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?

- O(n + k) and O(n + k)
- O(n + k) and O(n
^{2}) - O(n
^{2}) and O(n^{2}) - O(n
^{2}) 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(n^{2}) |

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

- Stack
- Array
- B-Tree
- 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?

- A + B * C
- + * A B C
- A B + C * /
- 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?

- A + B * C
- + * A B C
- A B + C * /
- 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?

- var x : array [‘a’… ‘z’] of REAL;
- var x : array [REAL] of REAL;
- var x : array [BOOLEAN] of REAL;
- 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?

- Rear-end
- Front-end
- Both ends
- 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?

- top = Maxsize +1
- top = Minsize -1
- top = Size -1
- 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?

- Linked list
- Array
- Tree
- 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?

- 4 minutes
- 7 minutes
- 6 minutes
- 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?

- The correct position is the right child of node 18
- The correct position is the right child of node 52
- The correct position is the left child of node 54
- The correct position is the right child of node 54

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

**Explanation:**

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

- 63 node
- 54 node
- 52 node
- 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?

- The correct position is the right child of the node 87
- The correct position is the left child of the node 75
- The correct position is the left child of the node 80
- 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:**

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

- Tree
- Graph
- Integer
- 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?

- Coupling and Square
- Square and Add
- Division, Mid square, and Folding
- None of the these

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

**Explanation:** List of the hash function:

- Division
- Mid square
- Folding
- Binary
- 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.

- 565
- 555
- 560
- 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?

- 0 <= f(n) <= C(g(n))
- 0 >= f(n) >= C(g(n))
- 0 <= C(g(n)) <= f(n)
- 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?

- 0 <= f(n) <= C(g(n))
- 0 >= f(n) >= C(g(n))
- 0 <= C(g(n)) <= f(n)
- 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, 2, 3, 5, 9, 6, 10, 4, 7, 8, 11, 12
- 1, 2, 3, 5, 6, 9, 10, 4, 7, 8, 11, 12
- 1, 2, 4, 7, 8, 11, 12, 3, 5, 6, 9, 10
- 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?

- 9, 5, 6, 10, 3, 7, 11, 12, 8, 4, 2, 1
- 9, 5, 10, 6, 3, 7, 11, 12, 8, 4, 2, 1
- 9, 5, 3, 6, 10, 7, 4, 11, 8, 12, 2, 1
- 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?

- 9, 5, 3, 10, 6, 2, 1, 7, 4, 11, 8, 12
- 9, 5, 10, 6, 3, 2, 1, 7, 11, 12, 8, 4
- 9, 5, 10, 6, 3, 2, 7, 11, 12, 8, 4, 1
- 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?

- Job scheduling
- Evaluation of a postfix expression
- Reverse a string
- 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 4 ^{th} smallest element?**

- B
- D
- E
- 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 * 2 + 3) ^ (1 + 2 * 3)
- (1 + 2 ^ 3) * (1 + 2 * 3)
- (1 + 2 * 3) ^ (1 + 2 * 3)
- (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)