Data Structures Algorithms MCQ (Multiple Choice Questions), Data Structures Algorithms Online Quiz

1 .

What could be the worst case height of an AVL tree?

A)

1.44 log n

B)

n2 log n

C)

0.97 log n

D)

2.13 log n

Correct Answer : Option (A) : 1.44 log n

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

2 .

A circular linked list can be used for

A)

Stack

B)

Queue

C)

Both Stack & Queue

D)

Neither Stack or Queue

Correct Answer : Option (C) : Both Stack & Queue

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

3 .

Which of the following is example of in-place algorithm?

A)

Bubble Sort

B)

Merge Sort

C)

Insertion Sort

D)

All of the above

Correct Answer : Option (B) : Merge Sort

4 .

Heap is an example of_________

A)

sparse tree

B)

spanning tree

C)

binary search tree

D)

complete binary tree

Correct Answer : Option (D) : complete binary tree

5 .

A pivot element to partition unsorted list is used in______

A)

Quick Sort

B)

Merge Sort

C)

Selection Sort

D)

Insertion Sort

Correct Answer : Option (A) : Quick Sort

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

6 .

The memory address of the first element of an array is called_____

A)

first address

B)

base address

C)

floor address

D)

foundation address

Correct Answer : Option (B) : base address

7 .

Herder node is used as sentinel in ____

A)

Queues

B)

Graphs

C)

Stacks

D)

Binary tree

Correct Answer : Option (D) : Binary tree

8 .

Linear arrays are also called ______

A)

Vertical array

B)

Horizontal array

C)

One-dimensional array

D)

Straight line array

Correct Answer : Option (C) : One-dimensional array

9 .

Stack is also called as_________

A)

Last in first out

B)

Last in last out

C)

First in first out

D)

First in last out

Correct Answer : Option (A) : Last in first out

10 .

Two dimensional arrays are also called_________

A)

tables arrays

B)

matrix arrays

C)

Both (A) and (B)

D)

None of the above

Correct Answer : Option (C) : Both (A) and (B)

11 .

Which of the following is not the required condition for binary search algorithm?

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 : Option (B) : There must be mechanism to delete and/or insert elements in list

12 .

Interpolation search is an improved variant of binary search. It is necessary for this search algorithm to work that

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 : Option (B) : 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.

13 .

In a min-heap_______

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 : Option (A) : 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.

14 .

What data structure is used for breadth first traversal of a graph?

A)

list

B)

stack

C)

queue

D)

None of the above

Correct Answer : Option (C) : queue

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

15 .

____ is not the component of data structure.

A)

Operations

B)

Algorithms

C)

Storage Structures

D)

None of the above

Correct Answer : Option (D) : None of the above

16 .

Which of the following data structure can't store the non-homogeneous data elements?

A)

Arrays

B)

Records

C)

Pointers

D)

None of the above

Correct Answer : Option (A) : Arrays

17 .

Travelling salesman problem is an example of_______

A)

Divide & Conquer

B)

Recursive Approach

C)

Dynamic Algorithm

D)

Greedy Algorithm

Correct Answer : Option (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.

18 .

Which of the following algorithm is not stable?

A)

Merge Sort

B)

Quick Sort

C)

Bubble Sort

D)

Insertion Sort

Correct Answer : Option (B) : Quick Sort

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

19 .

Which of the below given sorting techniques has highest best-case runtime complexity_______

A)

quick sort

B)

bubble sort

C)

selection sort

D)

insertion sort

Correct Answer : Option (C) : selection sort

20 .

If queue is implemented using arrays, what would be the worst run time complexity of queue and dequeue operations?

A)

ÎŸ(1), ÎŸ(n)

B)

ÎŸ(1), ÎŸ(1)

C)

ÎŸ(n), ÎŸ(n)

D)

ÎŸ(n), ÎŸ(1)

Correct Answer : Option (B) : ÎŸ(1), ÎŸ(1)

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

21 .

A data structure where elements can be added or removed at either end but not in the middle

A)

Deque

B)

Queues

C)

Stacks

D)

Linked lists

Correct Answer : Option (A) : Deque

22 .

Tower of hanoi is a classic example of_______

A)

divide and conquer

B)

recursive approach

C)

B but not A

D)

Both (A) & (B)

Correct Answer : Option (D) : Both (A) & (B)

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

23 .

The situation when in a linked list START=NULL is

A)

underflow

B)

overflow

C)

housefull

D)

saturated

Correct Answer : Option (A) : underflow

24 .

Which if the following is/are the levels of implementation of data structure

A)

Abstract level

B)

Application level

C)

Implementation level

D)

All of the above

Correct Answer : Option (D) : All of the above

25 .

The operation of processing each element in the list is known as

A)

Merging

B)

Traversal

C)

Sorting

D)

Inserting

Correct Answer : Option (B) : Traversal

26 .

When inorder traversing a tree resulted E A C K F H D B G; the preorder traversal would return

A)

FEAKDCHBG

B)

FAEKCDBHG

C)

FAEKCDHGB

D)

EAFKHDCBG

Correct Answer : Option (C) : FAEKCDHGB

27 .

When does top value of the stack changes?

A)

Before deletion

B)

After deletion

C)

At the time of deletion

D)

While checking underflow

Correct Answer : Option (B) : After deletion

28 .

Which of the following is not the type of queue?

A)

Ordinary queue

B)

Priority queue

C)

Circular queue

D)

Single ended queue

Correct Answer : Option (D) : Single ended queue

29 .

If we choose Prim's Algorithm for uniquely weighted spanning tree instead of Kruskal's Algorithm, then

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 : Option (A) : 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.

30 .

Project scheduling is an example of__________

A)

divide and conquer

B)

greedy programming

C)

dynamic programming

D)

None of the above.

Correct Answer : Option (C) : dynamic programming

31 .

Prefix notation is also known as________

A)

Polish Notation

B)

Reverse Notation

C)

Reverse Polish Notation

D)

Polish Reverse Notation

Correct Answer : Option (A) : Polish Notation

32 .

Which of the following data structure is linear type?

A)

Trees

B)

Stack

C)

Graph

D)

Binary tree

Correct Answer : Option (B) : Stack

33 .

Which of the following is non-liner data structure?

A)

List

B)

Trees

C)

Stacks

D)

Strings

Correct Answer : Option (B) : Trees

34 .

The logical or mathematical model of a particular organization of data is called a___________

A)

Data arrangement

B)

Data formation

C)

Data configuration

D)

Data structure

Correct Answer : Option (D) : Data structure

35 .

Which of the following case does not exist in complexity theory

A)

Best case

B)

Worst case

C)

Average case

D)

Null case

Correct Answer : Option (D) : Null case

36 .

A linked-list is a dynamic structure

A)

true

B)

false

C)

None of the above

D)

--

Correct Answer : Option (A) : true

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

37 .

In binary heap, whenever the root is removed then the rightmost element of last level is replaced by the root. Why?

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 : Option (C) : 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.

38 .

Which of the following uses memoization?

A)

Greedy approach

B)

Divide and conquer approach

C)

Dynamic programming approach

D)

None of the above

Correct Answer : Option (C) : Dynamic programming approach

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

39 .

Which of the following points is/are true about Linked List data structure when it is compared with array

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 : Option (D) : All of the above

40 .

If locality is a concern, you can use _______ to traverse the graph.

A)

Breadth First Search

B)

Depth First Search

C)

Either BFS or DFS

D)

None of the above

Correct Answer : Option (B) : Depth First Search

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

41 .

How is an array initialized in C language?

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

42 .

Which of the following is a linear data structure?

A)

Array

B)

Graphs

C)

AVL Trees

D)

Binary Trees

Correct Answer : Option (A) : Array

43 .

Which data structure is mainly used for implementing the recursive algorithm?

A)

List

B)

Array

C)

Stack

D)

Queue

Correct Answer : Option (C) : Stack

44 .

What is the best time complexity we can achieve to precompute all-pairs shortest paths in a weighted graph?

A)

O(n)

B)

O(n^2)

C)

O(n^4)

D)

O(n^3)

Correct Answer : Option (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 : Option (D) : Stores depths of all the nodes in a given tree, with respect to some root node.

46 .

A node in a tree, such that removing it splits the tree into forests, with size of each connected component being not greater than n / 2 is called?

A)

Path

B)

Centroid

C)

Center

D)

Diameter

Correct Answer : Option (B) : Centroid

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 : Option (C) : Calculates the number of edges in an undirected graph.

48 .

Which of the following represents the Post order Traversal of a Binary Tree?

A)

Left -> Right -> Root

B)

Left -> Root -> Right

C)

Right -> Left -> Root

D)

Right -> Root -> Left

Correct Answer : Option (A) : Left -> Right -> Root

49 .

What is the information, which a LinkedList's Node must store?

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 : Option (C) : Both (A) and (B)

50 .

How is the 2nd element in an array accessed based on pointer notation?

A)

*(a + 2)

B)

*a + 2

C)

&(a + 2)

D)

*(*a + 2)

Correct Answer : Option (A) : *(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

Correct Answer : Option (B) : 9

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

Correct Answer : Option (B) : 3

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.

53 .

What is the disadvantage of array data structure?

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 : Option (D) : The amount of memory to be allocated should be known beforehand.

54 .

How are String represented in memory in C?

A)

LinkedList of characters.

B)

An array of characters.

C)

The object of some class.

D)

Same as other primitive data types.

Correct Answer : Option (B) : An array of characters.

55 .

What will be the value of “sum” after the following code snippet terminates?

void solve(ListNode* root) {
   /*
   The LinkedList is defined as:
   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

Correct Answer : Option (C) : 10

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)

Correct Answer : Option (B) : 3

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

Correct Answer : Option (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.

58 .

Maps in C++ are implemented using which of the following data structures?

A)

AVL Trees.

B)

Hash Tables.

C)

Red-Black Trees.

D)

Binary Search Trees.

Correct Answer : Option (C) : Red-Black 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 : Option (A) : 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 : Option (D) : 3 2 1

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

61 .

What function is used to append a character at the back of a string in C++?

A)

push_back()

B)

push()

C)

insert()

D)

append()

Correct Answer : Option (A) : push_back()

62 .

Which one of the following is an application of queue data structure

A)

Load Balancing

B)

When data is transferred asynchronously

C)

When a resource is shared among multiple consumers.

D)

All of the above

Correct Answer : Option (D) : 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)

Correct Answer : Option (B) : O(n^2)

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 : Option (C) : 5 3 1 2 4

65 .

Consider we have a function, getLCA(), which returns us the Lowest Common Ancestor between 2 nodes of a tree. Using this getLCA() function, how can we calculate the distance between 2 nodes, given that distance from the root, to each node is calculated?

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 : Option (B) : 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.

Correct Answer : Option (D) : Segment Trees.