Data structure MCQ questions
1. Process of inserting an element in stack is called ____________
Ans: Push
2. Process of removing an element from stack is called __________
Ans: Pop
3. In a stack, if a user tries to remove an element from an empty stack it is called _________
Ans: underflow
4. Pushing an element into stack already having five elements and stack size of 5, then stack becomes ___________
Ans: Overflow
5. Which of the following is not the application of stack?
a) A parentheses balancing program
b) Tracking of local variables at run time
c) Compiler Syntax Analyzer
d) Data Transfer between two asynchronous process
Ans: d
6. Consider the usual algorithm for determining whether a sequence of parentheses is balanced. Suppose that
you run the algorithm on a sequence that contains 2 left parentheses and 3 right parentheses (in some order).
The maximum number of parentheses that appear on the stack AT ANY ONE TIME during the computation ?
Ans: 2
7. What data structure would you mostly likely see in non recursive implementation of a recursive algorithm?
Ans; stack
8. he result of evaluating the postfix expression 5, 4, 6, +, *, 4, 9, 3, /, +, * is?
Ans: 350
9. Consider the following operation performed on a stack of size 5
Push(1);
Pop();
Push(2);
Push(3);
Pop();
Push(4);
Pop();
Pop();
Push(5);
After the completion of all operation, the number of elements present in stack is?
Ans: 1
10. A linear list of elements in which deletion can be done from one end (front) and insertion can take place
only at the other end (rear) is known as _____________
Ans: Queue
11. A data structure in which elements can be inserted or deleted at/from both ends but not in the middle is?
Ans: Dequeue
12. A normal queue, if implemented using an array of size MAX_SIZE, gets full when?
Ans: Rear = MAX_SIZE – 1
13. The data structure required for Breadth First Traversal on a graph is?
Ans: Queue
14. A linear collection of data elements where the linear node is given by means of pointer is called?
Ans: Linked list
15. Consider an implementation of unsorted singly linked list. Suppose it has its representation with a head
pointer only. Given the representation, which of the following operation can be implemented in O(1) time?
1) Insertion at the front of the linked list
2) Deletion at the end of the linked list
3) Deletion of the front node of the linked list
4) Deletion of the last node of the linked list
Ans: (1) and (3)
16. What would be the asymptotic time complexity to insert an element at the front of the linked list (head is
known)?
a) O(1) b) O(n2) c) O(n) d) O(lgn2n)
Ans: a
17. What would be the asymptotic time complexity to insert an element at the second position in the linked list?
Ans: O(1)
18. The concatenation of two lists can be performed in O(1) time. Which of the following variation of the linked
list can be used?
Ans: Circular or doubly circular list
19. The ______________ of an algorithm is the amount of memory it needs to run to completion
Ans: Space complexity
20. When we say that an algorithm has a time complexity of O(n), what does it mean?
Ans: The computation time taken by the algorithm is proportional to n
21. Which of the following that determines the need for the Circular Queue?
a) Avoid wastage of memory b) Access the Queue using priority
c) Follows the FIFO principal d) None
Ans: a
22. In a circular queue implementation using array of size 5, the array index starts with 0 where front and rear
values are 3 and 4 respectively. Determine the array index at which the insertion of the next element will take
place.
Ans: 0
23. What would be the time complexity if user tries to insert the element at the end of the linked list (head
pointer is known)?
Ans: O(n)
24. How can we define a AVL tree?
Ans: A tree which is binary search tree and height balanced tree.
25. In linked list implementation of a queue, front and rear pointers are tracked. Which of these pointers will
change?
a) Only front pointer
b) Only rear pointer
c) Both front and rear pointer
d) No pointer will be changed during an insertion into EMPTY queue?
Ans: c
26. Linked lists are not suitable for the implementation of ___________
a) Insertion sort
b) Radix sort
c) Polynomial manipulation
d) Binary search
Ans: d
27. A binary tree is a rooted tree but not an ordered tree.
a) True b) False
Ans: b
28. If binary trees are represented in arrays, what formula can be used to locate a left child, if the node has an
index i?
Ans: 2*i+1
29. If binary trees are presented in arrays then using what formula can a parent node of ith node be located in an
array?
Ans: (i-1)/2
30. What is the space complexity of the in-order traversal in the recursive fashion? (d is the tree depth and n is
the number of nodes)
Ans: O(d)
31. What is the time complexity of level order traversal?
Ans: O(n)
32. What term is used to is used to describe an O(n) algorithm
Ans: Linear
33. Consider the following code segment
while(n>0)
{
n=n/10 // Use integer division
}
What is the worst case time analysis for the above loop?
Ans: O(log n)
34. Which of the following formula in Big-O notation best represent the expression n2+35n+6
Ans: O(n2)
35. A algorithm is made up of 2 modules M1 and M2. If order of M1 is f(n) and M2 is g(n) then the order
of the algorithm is
Ans: max( f(n), g(n) )
36. The expression used to access the (i, j)th entry of a (m x n) matrix stored in Column Major form is
n*i+j
37. Suppose a two dimensional array declared as “ char a[5][6] “ is internally stored in contiguous memory
locations starting from the location 1000 in a column major manner. The address where a[i][j] will be
stored is
Ans: 1000+i+j*5
38. Having address of the node to be deleted inn double liked list, the node can be deleted without
traversing the list. ( True/False )
Ans: True
39. The concatenation of two list is to be performed in O(1) time. The implementation of this is possible if
the list is
Ans: Circular or Doubly Circular
40. Recursion is equivalent to
Ans: Divide and Conquer paradigm
41. Tail recursion is
Ans: The recursive call is the last statement executed in a recursive procedure or function.
42. Advantage of recursion is
Ans: Coding complexity is less
43. A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is
Ans: n-1
44. Level of any node of a tree is
Ans: its distance from the root
45. The minimum number of edges in a connected cyclic graph is
Ans: n
46. In an adjacency matrix parallel edges cannot be represented ( True/ False )
Ans: True
47. In worst case, a binary search tree having n nodes will take how much time to search an element?
Ans: O(n)
48. How much time does an AVL tree take to perform a search, insert, and delete operations in the average
case as well as in worst case?
Ans: O(log n)
49. Which rotation is done when a new node is inserted in the right sub tree of the right sub tree of the
critical node.
Ans: RR
50. If we take two empty binary search trees and insert the same elements but in different order, then the
resultant tree will be the same ( True/False)?
Ans: False
51. Mirror image of a binary search tree is obtained by interchanging the left sub tree with the right sub
tree at every node of the tree (True/False)?
Ans: True
52. To find the node with the largest value, we will find the value of the right most node of the
__________?
Ans: Right Sub tree
53. If the parent appears in the right field of a in orderly threaded binary tree, then it will point to the
____________?
Ans: In order successor
54. In a priority queue, two elements with the same priority are processed on a FCFS( First Come First
Served) basis( True/False)?
Ans: True
55. _____________ are appropriate data structures to process a list of employees having a contract for a
seniority system for hiring and firing
Ans: Queues
56. Inserting a node at the beginning of a doubly linked list needs to modify ____________ pointers
Ans: 2
57. Deleting a node from a end of a circularly linked list needs to modify __________ pointer/s
Ans: 1
58. First node of a linked list is called the _____________
Ans: header node
59. The time complexity of an algorithm is the running time given as a function of _____________
Ans: Input size
60. Abstract means____________
Ans: Considered apart from the detailed specifications or implementations
61. ____________ specifies the expected behavior of an algorithm when an input is randomly drawn from
a given distribution.
Ans: Average case running time
62. In _____________ hash functions, consecutive keys map to consecutive hash values
Ans: Division remainder method
63. The process of examining memory locations in a hash table is called ____________
Ans: probing
64. Which open addressing technique is free from clustering problem?
Ans: Double hashing
65. Linear probing is sensitive to the distribution of input values ( True/False)?
Ans: True
66. A chained hash table is faster than a simple hash table (True/False)?
Ans: True
67. In which sorting, consecutive adjacent pairs of elements in the array are compared with each other.
Ans: Bubble sort
68. Which sorting algorithm sorts by moving the current data element past the already sorted values and
repeatedly interchanging it with the preceding value until it is in its correct place?
Ans: Insertion sort
69. The partitioning of the array in quick sort is done in O (n) time (True/False).
Ans: True
70. The running time of the merge sort algorithm in average case and in worst case is O(n log n)
( True/False)
Ans: True
71. The efficiency of quick sort algorithm depends on______________
Ans: pivot element
72. The memory use( space complexity) of adjacency matrix is
Ans: O(n2)
73. In a graph ___________ has a zero degree.
Ans: Isolated vertex
74. In a graph a path p is known as a ____________ path if the edge has the same end points.
Ans: Cycle
75. A graph having parallel edges and/or self loop is called _______________
Ans: multi-graph
76. The term optimal means
a) shortest b) cheapest c) fastest d) all
Ans: d) all
77. The space complexity of DFS is lower than that of BFS ( True/False )
Ans: False
78. The size of graph is total no of vertices in it.( True/False)
Ans: True
79. In M-way search tree M stands for
Ans: Degree of node
80. Every node in a B tree of order M has at most ___________ children
Ans: M
81. A balanced BST that has height O( log N) always guarantees____________ time to insert, delete and
search an element.
Ans: O( log N)
