## Data Structure MCQ

### 1) For sorting random linked list with the minimum time complexity, which of the following algorithm requires?

- Merge Sort
- Bubble
- Selection Sort
- Insertion Sort

**Answer:** (A)

**Explanation:** Both Merge sort and Insertion sort can be used for linked lists. Merge sort is preferred because the worst-case time complexity of merge sort is better than Insertion sort, which is O(n log n) over O(n^2). So we can use merge sort for sorting a random linked list.

### 2) Which of the following data structure used to implement priority queues efficiently?

- Stack
- Linked List
- Binary Heap
- None of Above

**Answer:** (C)

**Explanation:** Binary heap is used to implement priority queues because it takes O(log n) in the worst case.

### 3) Which of the following data structure works on insertion at only one end but deletions at both ends of the list?

- Priority Queues
- Input – restricted deque
- Output – restricted deque
- Stack

**Answer:** (B)

### 4) For solving the N-Queens problem, which of the algorithm need to use?

- Dynamic
- Divide and Conquer
- Backtracking
- None of Above

**Answer:** (C)

**Explanation:** In backtracking, we find the correct steps one-by-one, and if any step which has been taken is not correct, then we backtrack the step and try to find the correct step.

### 5) Which of the following algorithm takes the same time in all three cases (e.g., best, average, and worst)?

- Merge Sort
- Quick Sort
- Selection Sort
- Bubble Sort

**Answer:** (A)

**Explanation:** Merge sort divides the array into two parts and takes linear time to merge two halves, so its time complexity is O(n logn).

### 6) Which data structure is best for checking whether an expression has balanced parenthesis?

- Tree
- Linked List
- Graph
- Stack

**Answer:** (D)

**Explanation:** Stack works on the Last in First out (LIFO) rule, so it is suitable for checking parenthesis is balanced or not.

### 7) The balance factor range of any node that can be accepted in the AVL tree?

- [-2, -1, 0]
- [-2, -1, 0, 1]
- [-1, 0, 1]
- None of the Above

**Answer:** (C)

**Explanation:** The balance factor of any node should not be less than -1 and greater than 1; otherwise, the AVL tree needs to be balanced.

### 8) The minimum time required to check if an integer appears more than n/2 times in the array, assume that the array is sorted?

- O(log n)
- O(n)
- O(1)
- None of the Above

**Answer:** (A)

**Explanation:** For the solution of this problem, the best way would be the Binary Search approach because it takes O(log n) time if an array is sorted.

### 9) For declaring an array, which of the following way is correct?

- int arr;
- int arr[10];
- arr{10};
- None of the above

**Answer:** (B)

**Explanation:** arr is the name of an array,10 is the size of an array, and int is the data type of an array.

### 10) For implementing a breadth-first search, which of the following data structure is used?

- Stack
- Linked List
- Queue
- None of the above

**Answer:** (C)

**Explanation:** BFS requires to visit the child nodes in order their parents were discovered. Whenever we visit a node, we insert all the nodes into our data structure. If you use a queue data structure, it is guaranteed that you pop the nodes in order their parents were discovered.

### 11) Which of the following condition is necessary for checking queue is full? Assume that the queue is circular.

- Front == Rear+
- Front == 0 && Rear == len-1
- (Front == Rear+1) || (Front == 0 && Rear == len-1)
- (Front == Rear+1) && (Front == 0 && Rear == len-1)

**Answer:** (C)

**Explanation:** C is correct because if one of these conditions is true, that means queue is full if queue is circular.

### 12) Which of the following scans the list by swapping the entries whenever pair of adjacent keys are out of the desired order?

- Selection Sort
- Insertion Sort
- Merge Sort
- Bubble Sort

**Answer:** (D)

### 13) In which linked list, No NULL link is there?

- Null linked list
- Doubly linked list
- Circular linked list
- None of the above

**Answer:** (C)

**Explanation:** Both ends are connected to each other in a circular linked list; that’s why there is no null link in the node of it.

### 14) In stack, for accessing an nth element from the top, which command needs to use?

- S [ Top-n ]
- S[ Top+n ]
- S[ Top-n+1 ]
- None of the above

**Answer:** (C)

**Explanation:** Suppose we want to access the 3^{rd} element from the top, and if top=4, then 4-3+1=2, which will be the 3^{rd} element from the top.

### 15) The result of prefix expression * / b + – d a c d, where a = 3, b = 6, c = 1, d = 5 is

- 0
- 5
- 10
- 8

**Answer:** (C)

**Explanation:** Expression is * / 6 + – 5 3 1 5, so we have to use stack for finding the result; we push expression into the stack from right to left, and if we encounter operand, then we simply push operand into the stack, or if we encounter operator then we pop last two operands and evaluate them with the help of operator then again push their result into the stack recursively, e.g. (5*(6/((5-3)+1)))=10.

### 16) Which of the following approach Recursive algorithms are worked on?

- Bottom-up approach
- Top-down approach
- Hierarchical approach
- All of the above

**Answer:** (A)

**Explanation:** In the recursive algorithm, we try to solve sub-problems first, then we use their result and arrive at the solution of bigger-problems.

### 17) Which among the following data structures is best suited for storing very large numbers.

- HashMap
- Linked List
- Tree
- Stack

**Answer:** (B)

**Explanation:** We have two options for it, which are array and linked list. Arrays have fixed size so we can’t go with arrays, but we can use linked list because linked-list is flexible over arrays.

### 18) Suppose server and client are communicating with each other, and both are working at a different speed. Which of the following data structure is best suited for synchronization?

- Graph
- Tree
- Queue
- None of the above

**Answer:** (C)

**Explanation:** A queue can be used for synchronization because it works on the FIFO rule.

### 19) How does breadth-first work?

- Traverse each incident node along with its children
- Traverse all node in random order
- Is the same as backtracking
- Traverse all neighbor nodes before moving to their child

**Answer:** (D)

**Explanation:** Breadth-first search searches the node level by level.

### 20) Suppose we are working on heap data structure, so which of the following is used for storing the data of heap?

- Tree
- Array
- Linked List
- None of the above

**Answer:** (B)

**Explanation:** Heap data structure is the complete binary tree, so an array is preferred for storing its data.

### 21) Which of the following order is given by binary search tree if we traverse it in inorder?

- Ascending order
- Descending order
- Random order
- None of the above

**Answer:** (A)

**Explanation:** The inorder traversal of a binary search tree always gives the elements in sorted order, which is ascending.

### 22) Which of the following time complexity of bubble sort in best/worst case?

- Best case: O(n), Worst case: O(n log(n))
- Best case: O(n), Worst case: O(n^2)
- Best case: O(n*log(n)), worst case: O(n*log(n))
- None of the above

**Answer:** (B)

**Explanation:** If there is no swap in one pass, then bubble sort terminates the loop, so its best-case complexity is O(n) and bubble sort compares each & every element with other elements, so it’s worst-case time complexity is O(n^2).

### 23) Which of the following is the aim of implementing prim’s and kruskal’s algorithms?

- Maximum spanning tree
- Spanning tree
- Minimum Spanning tree
- None of the above

**Answer:** (C)

**Explanation:** The prim’s algorithm works on the vertex, and the kruskal’s algorithm works on edges for finding a minimum spanning tree.

### 24) Which of the following is the process of executing a correct program on data sets and measuring the time and space it takes to compute the results?

- Testing
- Combining
- Profiling
- All of the above

**Answer:** (C)

### 25) Which of the following is the time complexity if the graph is represented as an adjacency matrix in kruskal’s algorithm?

- O( E log V )
- O( V log E)
- O( V^2)
- O( log E)

**Answer:** (A)

**Explanation:** The kruskal’s algorithm works on the sorting of the edges after it combines all of the edges, which takes O(E log v) time.

### 26) If there’s no base criteria in a recursive program, the program will?

- Gives Error
- Execute until all conditions match
- Execute infinitely
- All of the above

**Answer:** (C)

**Explanation:** Recursive program stops when it encounters the base condition, but if there no base condition, then it executes infinitely.

### 27) If we want to convert infix notation to postfix notation, then which of the following data structure should we use?

- Stack
- Queue
- Singly Linked List
- HashMap

**Answer:** (A)

**Explanation:** Stack works on the Last in First out rule.

### 28) Which of the following is the sum of the degree of each vertex is equal to if there an undirected graph with n vertices and e edges?

- 2*n
- 2*e
- (e^2+1) / 2
- (2*n-1) / 2

**Answer:** (B)

### 29) What of the following is the time complexity to add a node at the end of the singly linked list, if the pointer is initially pointing to the head of the list?

- O(1)
- O(n)
- θ(n)
- θ(1)

**Answer:** (C)

**Explanation:** For adding a node at the end of a singly linked-list, then we have to traverse all nodes present in the linked-list. Suppose there are n nodes, then time complexity will be θ(n).

### 30) If we compare array and linked – list then which of the following point is not true about linked list?

- Linked – lists are dynamic in nature
- Access of elements in linked list takes less time than compared to arrays
- In linked list, random access is not allowed
- It is easy to delete elements in Linked List

**Answer:** (B)

**Explanation:** Linked list doesn’t work on indexes so it takes more time to access an element as compared to array.

### 31) Which of the following operations are dependent on the length of the linked list if we have pointers to first and the last node of a singly linked list?

- Delete the last element of the list
- Insert a new element as a first element
- Delete the first element
- Add a new element at the end of the list

**Answer:** (A)

**Explanation:** For deleting last node of the linked-list, we have to traverse all nodes so we can say that operation depends on the length of the linked-list.

### 32) How can we define the memory-efficient doubly linked list?

- Each node has only one pointer to traverse the list back and forth
- The list has breakpoints for faster traversal
- A singly linked list acts as a helper list to traverse through the doubly linked list
- A doubly linked list that uses bitwise AND operator for storing addresses

**Answer:** (A)

**Explanation:** In memory-efficient doubly linked list has only one space to store address of every node and it uses bitwise XOR.

### 33) Which of the following supports the statement, Array implementation of stack is not dynamic?

- Space allocation for array is fixed and cannot be changed during run-time
- Reduce time and space complexity
- Compilation Error
- Array implementation is flexible

**Answer:** (A)

**Explanation:** we can’t grow and shrink the size of an array during the run time.

### 34) Which of the following statement is true in linked list implementation of queue?

- In push operation, if new nodes are inserted at the beginning, then in pop operation, nodes must be removed from the beginning
- In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from the end
- In a push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from beginning.
- In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from end

**Answer:** (D)

### 35) Which of the following operation is correct, while evaluating a postfix expression, when an operator is encountered?

- Push it directly on to the stack
- Pop 2 operands, evaluate them and push the result on to the stack
- Pop the entire stack
- Ignore the operator

**Answer:** (B)

**Explanation:** When we encounter operator then we just pop last 2 operands from the stack and evaluate them with help of operator and push their result back in to the stack.

### 36) Which of the following is the time complexity of converting a prefix notation to infix notation is?

- O(n) where n is the length of the equation
- O(n) where n is number of operands
- O(1)
- O(logn) where n is length of the equation

**Answer:** (A)

### 37) In a complete k-ary tree, every internal node has exactly k children or no child. The number of leaves in such a tree with n internal nodes is?

- nk
- (n-1)k + 1
- n(k-1) + 1
- n(k-1)

**Answer:** (C)

### 38) Which of the following statement is correct about deque?

- A queue with insert and delete defined for both front and rear ends of the queue
- Works on last in first order
- A queue implemented with both singly and doubly linked lists
- A queue with insert/delete defined for front side of the queue

**Answer:** (A)

**Explanation:** Deque is combination of both stack and queue data structures.

### 39) What is the number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children?

- n/2
- (n-1)/3
- (n-1)/2
- (2n+1)/3

**Answer:** (D)

### 40) The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is?

- 2h – 1
- 2h – 1 – 1
- 2h + 1 – 1
- 2 * (h+1)

**Answer:** (C)

### 41) Which of the following is the graphical representation of an algorithm?

- Pseudocode
- Flow Chart
- Graph Coloring
- Dynamic Programming

**Answer:** (B)

**Explanation:** Before solving any problem, firstly we make step by step procedures called algorithm then according to this we make graphical representation of it called flowchart.

### 42) Which of the following method will choose when sub-problems share sub-problems?

- Backtracking
- Greedy Method
- Divide and Conquer
- Dynamic Programming

**Answer:** (D)

**Explanation:** Dynamic programming is an optimal recursion method and is used when a problem has overlapping sub-problems.

### 43) The step by step procedure for a program is called?

- Process
- Greedy Method
- Algorithm
- Problem

**Answer:** (C)

**Explanation:** An algorithm is step by step procedures of any program.

### 44) Which of the following is the advantage of finding maximum and minimum using the divide and conquer method instead of conditional operators?

- Reduce Space Complexity
- For getting the consistent result
- Reduce Time Complexity
- All of the above

**Answer:** (C)

**Explanation:** The divide and conquer works on top-down approach, divide problem in to sub-problems and solving them and it takes less time in finding max and min.

### 45) Which of the following data structure that contains a relationship between a pair of elements; this is not necessarily hierarchical in nature?

- Tree
- Graph
- String
- None of the above

**Answer:** (B)

**Explanation:** Graph may contain cycle so it doesn’t follow hierarchical order.

### 46) Which of the following operations accesses each record exactly once?

- Inserted
- Deletion
- Traversing
- Searching

**Answer:** (C)

**Explanation:** In traversing, we access each record or data exactly once.

### 47) Which of the following is a set of data values and associated operations that are specified accurately, independent of any particular implementation?

- Stack
- Tree
- Abstract Data Type
- None of the above

**Answer:** (C)

### 48) Which of the following is something that has certain attributes or properties which may be assigned values?

- Field
- File
- Record
- Entity

**Answer:** (D)

### 49) Below C program that takes a number as an argument, and uses a stack S to do processing.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
void convert(int no ) { Stack St; // For creating the empty stack while ( no > 0 ) { // For pushing the value of no%2 into stack St push(&St, no%2); no = no/2; } // Continuously checking whether stack is empty or not while( !isEmpty(&St) ) printf("%d ", pop(&St)); // pop an element from St and print it } |

**What does the above function do in general?**

- Prints binary representation of number in reverse order
- Prints binary representation of number
- Prints the value of number
- Prints the value of number in reverse order

**Answer:** (B)

**Explanation:** In this program, we just take a modulus of the number and store them to the stack while number is greater than 0, so by doing this we can find binary representation of any number.

### 50) Below C program that takes a Queue as an argument, and uses a stack S to do processing.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
void function( Queue *Qu ) { Stack St; // For creating an empty stack St // Continuously checking whether Queue is empty or not while ( !isEmpty(Qu) ) { // For remove an item from Qu and push the removed item to St push(&St, deQueue(Qu)); } // Continuously checking whether stack is empty or not while ( !isEmpty(&St) ) { // For remove an item from St and add the removed item to Qu enQueue(Qu, pop( &St )); } } |

**What does the above function do in general?**

- Removes the last from Qu
- Keeps the Qu same as it was before the call
- Reverses the Qu
- None of the above

**Answer:** (C)

**Explanation:** The function takes a queue Qu as an argument. It removes all items of Qu and adds them to a stack St. Then remove all items from St and adds the items back to Qu. Since stack works on LIFO rule, so the elements of queue will be reversed.

### 51) If we want to implement a stack using queue then how many queues are needed? Consider the situation where no other data structure like arrays, linked list is there.

- 1
- 2
- 3
- 4

**Answer:** (B)

**Explanation:** A stack can be implemented using two queues.

### 52) If an algorithm takes O(n) for some computing then which of the following is the meaning of it?

- In this algorithm, the nested loop count is ‘n’
- The computation time taken by the algorithm is proportional to ‘n’
- If we compare it with the standard algorithm, then it is ‘n’ times faster than a standard algorithm
- There are ‘n’ numbers of statements in the algorithm

**Answer:** (B)

**Explanation:** The time complexity refers to how complex your program is, i.e., how many operations it takes to actually solve a problem. O(n) means your algorithm takes the time as the number of items in your list.

### 53) It is possible if we want to read a data item at any location of a list within a constant time then how can we do it?

- Yes, only if the list is implemented by stack
- Yes, only if the list is implemented by an array
- Yes, only if the list is implemented by (i.e. linked list)
- No, we need O(n) computation steps on matter what kind of implementation is used

**Answer:** (B)

**Explanation:** Array works on indexes, so if we want to read a data item at any location within constant time then we can do it.

### 54) How many minimum number of spanning trees, one can have from a given connected graph with N nodes with different weights for the edges.

- N-1
- One
- 1/ (N+1)
- None of the above

**Answer:** (B)

### 55) Which are the following two phases of testing of program?

- Best case and worst case
- Space complexity and the time complexity
- Validation and checking errors
- Debugging and profiling

**Answer:** (D)

### 56) The applications of stack data structure is/are?

- Backtracking
- Memory management
- Arithmetic expression evaluation
- All of the above

**Answer:** (D)

**Explanation:** The stack data structure is capable to do these all tasks.

### 57) In the arrays, the smallest element of its index also known as?

- Lower bound
- Upper bound
- Range
- All of the above

**Answer:** (A)

### 58) What happens when you push a new node in linked list representation of a stack?

- The new node is placed at the front of linked list
- The new node is placed at the back of the linked list
- The new node is placed at the middle of the linked list
- None of the above

**Answer:** (A)

**Explanation:** We can place the new node at the front of linked list because it will take less time to insert or delete.

### 59) Which of following is the advantage of using linked list?

- For relatively permanent collections of data
- Linked list is more flexible it can grow and shrink easily
- Less time complexity
- None of the above

**Answer:** (B)

**Explanation:** We can grow and shrink the size of linked list according to our requirements.

### 60) Which of the following linear list is unidirectional or can be traversed in only one direction from starting to end?

- Singly linked list
- Array list
- Null linked list
- None of the above

**Answer:** (A)

**Explanation:** Singly linked list contains pointer which is pointed to only one or unidirectional only.

### 61) Which of the following is another name of circular queue?

- Curve buffer
- Square Buffer
- Ring buffer
- None of the above

**Answer:** (C)

**Explanation:** In circular queue, last position is connected to the first position of it and also called ring buffer.

### 62) Which of following is contained by the header of the linked list?

- The address of the first node
- The address of the last node
- Pointer to the last record of the actual data
- Middle record of the actual data

**Answer:** (A)

**Explanation:** Header contains only the address of the first node of the linked list.

### 63) Which of the following linear list in which the last node points to the first node?

- Null linked list
- Circular linked list
- Doubly linked list
- None of the above

**Answer:** (B)

**Explanation:** No null pointer in circular linked list so it’s last node points to the first node.

### 64) In binary search algorithm, which of the following statement doesn’t support the binary search properties?

- Array must be sorted
- Requirement of sorted array is expensive when a lot of insertion and deletions are needed
- We can access middle element directly
- If data items are more than 2000 then it will not be efficient.

**Answer:** (D)

**Explanation:** The binary search algorithm doesn’t affect by size of the input or data if data is sorted.

### 65) Which of the following can be characterized of sorting algorithm?

- Simple algorithm which require the order of n2 comparisons to sort n items.
- Sophisticated algorithms that require the O(nlog2n) comparisons to sort items.
- Both of the above
- None of the above

**Answer:** (C)

### 66) In binary search algorithm, which of the following is not required condition?

- The data items must be sorted
- We can access to the middle element in any sub list
- There should be a function to delete and/or insert elements in the list.
- Number values should only be present in the list

**Answer:** (C)

**Explanation:** In binary search, there is no need of function that can delete or insert in to it.