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

1 .

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()

2 .

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

3 .

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).

4 .

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

5 .

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).

6 .

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.