Data Structures Algorithms - Quiz(MCQ)
A)
1.44 log n
B)
n2 log n
C)
0.97 log n
D)
2.13 log n

Correct Answer :   1.44 log n

Explanation : Worst case height of an AVL tree is 1.44 log n

A)
Stack
B)
Queue
C)
Both Stack & Queue
D)
Neither Stack or Queue

Correct Answer :   Both Stack & Queue

Explanation : Both stack and queue data structure can be represented by circular linked-list.

A)
Bubble Sort
B)
Merge Sort
C)
Insertion Sort
D)
All of the above

A)
sparse tree
B)
spanning tree
C)
binary search tree
D)
complete binary tree

Correct Answer :   complete binary tree

A)
Quick Sort
B)
Merge Sort
C)
Selection Sort
D)
Insertion Sort

Explanation : The quick sort partitions an array using pivot element and then calls itself recursively twice to sort the resulting two subarray.

A)
B)
C)
D)

A)
Queues
B)
Graphs
C)
Stacks
D)
Binary tree

A)
Vertical array
B)
Horizontal array
C)
One-dimensional array
D)
Straight line array

A)
Last in first out
B)
Last in last out
C)
First in first out
D)
First in last out

Correct Answer :   Last in first out

A)
tables arrays
B)
matrix arrays
C)
Both (A) and (B)
D)
None of the above

Correct Answer :   Both (A) and (B)

A)
The list must be sorted
B)
There must be mechanism to delete and/or insert elements in list
C)
there should be the direct access to the middle element in any sublist
D)
None of the above

Correct Answer :   There must be mechanism to delete and/or insert elements in list

A)
data collection should be equally distributed but not sorted.
B)
data collection should be in sorted form and equally distributed.
C)
data collection should be in sorted form and but not equally distributed.
D)
None of the above.

Correct Answer :   data collection should be in sorted form and equally distributed.

Explanation : For this algorithm to work properly the data collection should be in sorted form and equally distributed.

A)
parent nodes have values greater than or equal to their childs
B)
parent nodes have values less than or equal to their childs
C)
both statements are true
D)
both statements are wrong

Correct Answer :   parent nodes have values greater than or equal to their childs

Explanation : In a min heap, parents always have lesser or equal values than that of their childs.

A)
list
B)
stack
C)
queue
D)
None of the above

Explanation : Queue is used for breadth first traversal whereas stack is used for depth first traversal.

A)
Operations
B)
Algorithms
C)
Storage Structures
D)
None of the above

Correct Answer :   None of the above

A)
Arrays
B)
Records
C)
Pointers
D)
None of the above

A)
Divide & Conquer
B)
Recursive Approach
C)
Dynamic Algorithm
D)
Greedy Algorithm

Explanation : Travelling salesman is an example of greedy algorithm. Greedy algorithms tries to find localized optimum solution which may eventually land in globally optimized solutions.

A)
Merge Sort
B)
Quick Sort
C)
Bubble Sort
D)
Insertion Sort

Explanation : Among the given, only quick sort is not stable that is it may re-arrange the already sorted items.

A)
quick sort
B)
bubble sort
C)
selection sort
D)
insertion sort

A)
ÃŽÅ¸(1), ÃŽÅ¸(n)
B)
ÃŽÅ¸(1), ÃŽÅ¸(1)
C)
ÃŽÅ¸(n), ÃŽÅ¸(n)
D)
ÃŽÅ¸(n), ÃŽÅ¸(1)

Explanation : As queue is maintained by two separate pointers for queue and dequeue operations, the run time for both is Ο(1).

A)
Deque
B)
Queues
C)
Stacks
D)

A)
divide and conquer
B)
recursive approach
C)
B but not A
D)
Both (A) & (B)

Correct Answer :   Both (A) & (B)

Explanation : The recursive approach of tower of hanoi uses divide and conquer method.

A)
underflow
B)
overflow
C)
housefull
D)
saturated

A)
Abstract level
B)
Application level
C)
Implementation level
D)
All of the above

Correct Answer :   All of the above

A)
Merging
B)
Traversal
C)
Sorting
D)
Inserting

A)
FEAKDCHBG
B)
FAEKCDBHG
C)
FAEKCDHGB
D)
EAFKHDCBG

A)
Before deletion
B)
After deletion
C)
At the time of deletion
D)
While checking underflow

A)
Ordinary queue
B)
Priority queue
C)
Circular queue
D)
Single ended queue

Correct Answer :   Single ended queue

A)
we'll get the same spanning tree.
B)
spanning will have less edges.
C)
we'll get a different spanning tree.
D)
spanning will not cover all vertices.

Correct Answer :   we'll get the same spanning tree.

Explanation : Regardless of which algorithm is used, in a graph with unique weight, resulting spanning tree will be same.

A)
divide and conquer
B)
greedy programming
C)
dynamic programming
D)
None of the above.

A)
Polish Notation
B)
Reverse Notation
C)
Reverse Polish Notation
D)
Polish Reverse Notation

A)
Trees
B)
Stack
C)
Graph
D)
Binary tree

A)
List
B)
Trees
C)
Stacks
D)
Strings

A)
Data arrangement
B)
Data formation
C)
Data configuration
D)
Data structure

A)
Best case
B)
Worst case
C)
Average case
D)
Null case

A)
true
B)
false
C)
None of the above
D)
--

Explanation : A linked-list is dynamic structure, it can shrink and expand as required by the program.

A)
It is the easiest possible way.
B)
Because left and right subtree might be missing.
C)
To make sure that it is still complete binary tree.
D)
None of the above

Correct Answer :   To make sure that it is still complete binary tree.

Explanation : A binary heap (whether max or min) has to satisfy the property of complete binary tree at all times.

A)
Greedy approach
B)
Divide and conquer approach
C)
Dynamic programming approach
D)
None of the above

Correct Answer :   Dynamic programming approach

Explanation : Remembering the results of previously calculated solutions is called memoization.

A)
It is easy to insert and delete elements in Linked List
B)
Random access is not allowed in a typical implementation of Linked Lists
C)
Arrays have better cache locality that can make them better in terms of performance
D)
All of the above

Correct Answer :   All of the above

A)
B)
Depth First Search
C)
Either BFS or DFS
D)
None of the above

Correct Answer :   Depth First Search

Explanation : DFS is a better choice when locality-wise items are concerned.

A)
int a[3] = {1, 2, 3};
B)
int a = {1, 2, 3};
C)
int a(3) = [1, 2, 3];
D)
int a[] = new int[3]

Correct Answer :   int a[3] = {1, 2, 3};

A)
Array
B)
Graphs
C)
AVL Trees
D)
Binary Trees

A)
List
B)
Array
C)
Stack
D)
Queue

A)
O(n)
B)
O(n^2)
C)
O(n^4)
D)
O(n^3)

45 .
What does the following code snippet do?
``````void dfs(int node, vector<vector<int>> &edges, vector<bool> &vis, vector<int> &dp) {
vis[node] = true;
for(auto x: edges[node]) {
if(!vis[x]) {
dp[x] = dp[node] + 1;
dfs(x, edges, vis, dp);
}
}
}``````
A)
Finds the diameter of a tree.
B)
Counts the number of nodes in a given tree.
C)
Checks if all the nodes are reachable in a given tree.
D)
Stores depths of all the nodes in a given tree, with respect to some root node.

Correct Answer :   Stores depths of all the nodes in a given tree, with respect to some root node.

A)
Path
B)
Centroid
C)
Center
D)
Diameter

47 .
What does the following code snippet calculate (edges represent the adjacency list representation of a graph)?
``````void solve(vector<vector<int>> edges) {
int count = 0;
for(auto x: edges) {
for(auto y: x) {
count += 1;
}
}
cout << count / 2 << endl;
}``````
A)
Calculates the number of nodes in a given graph.
B)
Calculates the sum of degrees of all nodes in a given graph.
C)
Calculates the number of edges in an undirected graph.
D)
None of the above.

Correct Answer :   Calculates the number of edges in an undirected graph.

A)
Left -> Right -> Root
B)
Left -> Root -> Right
C)
Right -> Left -> Root
D)
Right -> Root -> Left

Correct Answer :   Left -> Right -> Root

A)
The value of the current node
B)
The address of the next node if it exists
C)
Both (A) and (B)
D)
None of the above

Correct Answer :   Both (A) and (B)

A)
*(a + 2)
B)
*a + 2
C)
&(a + 2)
D)
*(*a + 2)

Correct Answer :   *(a + 2)

51 .
What will be the output of the following code snippet?
``````void solve() {
int a[] = {1, 2, 3, 4, 5};
int sum = 0;
for(int i = 0; i < 5; i++) {
if(i % 2 == 0) {
sum += a[i];
}
}
cout << sum << endl;
}``````
A)
15
B)
9
C)
6
D)
5

52 .
What will the output of the following code snippet?
``````void solve() {
int a[] = {1, 2, 3, 4, 5};
int sum = 0;
for(int i = 0; i < 5; i++) {
if(i % 2 == 0) {
sum += *(a + i);
}
else {
sum -= *(a + i);
}
}
cout << sum << endl;
}``````
A)
2
B)
3
C)
15
D)
Syntax Error

Explaination : This is an example of accessing an array element through pointer notation. So *(a + i) is equivalent to a[i], and we are adding all the even indices elements, and subtracting all the elements at odd indices, which gives a result of 3.

A)
Elements are stored in contiguous memory blocks.
B)
Elements of an array can be accessed in constant time.
C)
Multiple other data structures can be implemented using arrays.
D)
The amount of memory to be allocated should be known beforehand.

Correct Answer :   The amount of memory to be allocated should be known beforehand.

A)
B)
An array of characters.
C)
The object of some class.
D)
Same as other primitive data types.

Correct Answer :   An array of characters.

55 .
What will be the value of “sum” after the following code snippet terminates?
``````void solve(ListNode* root) {
/*
root-> val = value of the node
root-> next = address of next element from the node
The List is 1 -> 2 -> 3 -> 4 -> 5
*/
int sum = 0;
while(root -> next != NULL) {
sum += root -> val;
root = root -> next;
}
cout << sum << endl;
}``````
A)
1
B)
2
C)
10
D)
20

Explaination : The code calculates the sum of values of the nodes of the given LinkedList, which is 10.

56 .
What will be the output of the following code snippet?
``````int search(int l, int r, int target, vector<int> &a) {
int mid = (l + r) / 2;
if(a[mid] == target) {
return mid;
}
else if(a[mid] < target) {
return search(mid + 1, r, target, a);
}
else {
return search(0, mid - 1, target, a);
}
}
void solve() {
vector<int> a = {1, 2, 3, 4, 5};
cout << search(0, 4, 4, a) << endl;
}``````
A)
4
B)
3
C)
2
D)

Explaination : The above code is just a recursive implementation of binary search which searches for the index of value 4, which is 3.

57 .
What will be the output of the following code snippet?
``````void solve() {
int n = 24;
int l = 0, r = 100, ans = n;
while(l <= r) {
int mid = (l + r) / 2;
if(mid * mid <= n) {
ans = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
cout << ans << endl;
}``````
A)
1
B)
2
C)
3
D)
4

Explaination : The code snippet basically uses binary search to calculate the floor of the square root of a number. Since the square root is an increasing function, so binary search is applicable here. Here, for n = 24, the answer is 4.

A)
AVL Trees.
B)
Hash Tables.
C)
Red-Black Trees.
D)
Binary Search Trees.

59 .
What will be the output of the following code snippet?
``````void solve() {
string s = "00000001111111";
int l = 0, r = s.size() - 1, ans = -1;
while(l <= r) {
int mid = (l + r) / 2;
if(s[mid] == '1') {
ans = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
}
cout << ans << endl;
}``````
A)
7
B)
6
C)
5
D)
4

Correct Answer :   This code snippet shows one of the many applications of binary search. Here, we are binary searching for the index of the first occurrence of the character ‘1’ in the given string. When we get the character ‘1’ at the mid index, we store it as the answer and move to the left half which will have the first index of ‘1’ if it occurs. Else we move to the right half. So, the answer will be 7 (0-based indexing).

60 .
What is the output of the following code snippet?
``````void solve() {
stack<int> s;
s.push(1);
s.push(2);
s.push(3);
for(int i = 1; i <= 3; i++) {
cout << s.top() << “ “;
s.pop();
}
}``````
A)
1
B)
2
C)
1 2 3
D)
3 2 1

Correct Answer :   3 2 1

Explaination : Stack follows a last in first out methodology, so the elements are popped out in reverse order.

A)
push_back()
B)
push()
C)
insert()
D)
append()

A)
B)
When data is transferred asynchronously
C)
When a resource is shared among multiple consumers.
D)
All of the above

Correct Answer :   All of the above

63 .
What is the time complexity of the following code snippet in C++?
``````void solve() {
string s = "scaler";
int n = s.size();
for(int i = 0; i < n; i++) {
s = s + s[i];
}
cout << s << endl;
}``````
A)
O(n)
B)
O(n^2)
C)
O(1)
D)
O(log n)

Explaination : The s = s + s[i] line first makes a copy of the original string and then appends the new character in it, leading to each operation being O(n). So the total time complexity is O(n^2).

64 .
What will be the output of the following code snippet?
``````void solve() {
deque<int> dq;
for(int i = 1; i <= 5; i++) {
if(i % 2 == 0) {
dq.push_back(i);
}
else {
dq.push_front(i);
}
}
for(auto x: dq) {
cout << x << " ";
}
cout << endl;
}``````
A)
1 2 3 4 5
B)
1 3 5 2 4
C)
5 3 1 2 4
D)
5 4 3 2 1

Correct Answer :   5 3 1 2 4

A)
dist(u) + dist(v)
B)
dist(u) + dist(v) - 2 * dist(getLCA(u, v))
C)
dist(u) + dist(v) - dist(getLCA(u, v))
D)
dist(u) + dist(v) + 2 * dist(getLCA(u, v))

Correct Answer :   dist(u) + dist(v) - 2 * dist(getLCA(u, v))

Explanation : The distance between 2 nodes, can be broken down into the sum of distances from the root, to each of the nodes. Observe, that in each of these paths, the path from the root to the LCA comes in each of them. So, this needs to be removed from the answer, and hence we get our formula in Option (B).

66 .
Consider the following code snippet:
``````void solve(vector<int> &a) {
int queries;
cin >> queries;
while(queries--) {
int type;
cin >> type;
if(type == 1) {
int index, value;
cin >> index >> value;
update(a, index, value);
}
else {
int l, r;
cin >> l >> r;
cout << getXOR(a, l, r) << endl;
}
}
}``````
The `update()` function updates the element at the given index in the array to some given value. The `getXOR()` function returns the XOR of the elements in the array a, in the `range [l, r]`. Which of the following data structures can perform the above tasks optimally?
A)
Tries.
B)
Stacks
C)
Prefix XOR Arrays.
D)
Segment Trees.