Top 45+ DAA MCQ Questions with Answers

Algorithm

The algorithm is a step-by-step process to solve any problem and is a sequence of instructions that act on some input data to produce some output in a finite number of steps. The algorithm is independent of any programming language.

Why analysis of algorithms?

For a given problem, there are many ways to design algorithms for it
Analysis of algorithms to determine which algorithm should be chosen to solve the problem.

The complexity of algorithm on performance analysis of algorithm:

Time complexity: time complexity of an algorithm is the total time required by the program to run till its completion
Space complexity: Space complexity is the total space required by an algorithm to run till its completion.

Time and space complexity depends on lots of things like hardware, OS, processes, etc.

The analysis is of two types:

Posteriori analysis: In Posteriori analysis, Algorithm is implemented and executed on certain fixed hardware and software. Then the algorithm is selected which takes the least amount of time to execute. Hence, the time used is given in time units like ms, ns, etc.
Priori analysis: In Priori analysis, The time of the algorithm is found prior to implementation. Here time is not in terms of any such time units. Instead, it represents the number of operations that are carried out while executing the algorithm.

Asymptotic notations:

Asymptotic notations are used to represent the complexity of an algorithm
With the help of asymptotic notations, we can analyze the time performance of the algorithm.

There are three types of asymptotic notations:

Theta notation
Omega notation
Big Oh Notation

Design and Analysis of Algorithms MCQ

View All

Network lock

Single source shortest path

All pair shortest path

Sorting

String

Boolean

Double

Integer

Greedy algorithm

Dynamic programming

Backtracking

Sorting

The difference between the heights of left and right nodes cannot be more than 1.

The height of an AVL Tree always remains of the order of O(logn)

AVL Trees are a type of self-balancing Binary Search Trees.

All of the above.

Storage structure

File structure

Recursive

Abstract Data Type

O(V + E)

O(V)

O(E)

O(V * logE)

Time and space complexity

Data and space

Processor and memory

Complexity and capacity

Merge Sort

Quick Sort

Bubble Sort

Selection Sort

Bubble Sort

Selection Sort

Heap Sort

Merge Sort

Linked list

Array

Queue

Stack

O(nlogn)

O(n^2)

O(n)

O(1)

Non-continuous knapsack problem

Divisible knapsack problem

0/1 knapsack problem

Continuous Knapsack Problem

Linear programming

Dynamic Programming

Greedy Technique

Backtracking

NP problem

P class problem

NP-complete problem

N class problem

15.

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;
}

O(n)

O(n^2)

O(1)

O(log n)

Overflow

Underflow

Syntax Error

Garbage Value

O(n)

O(1)

O(log2n)

O(n^2)

Bubble Sort

Merge Sort

Counting Sort

Heap Sort

O(nlog(logn)) Precomputation, O(1) for check.

O(n) Precomputation, O(1) for the check.

O(n * logn) Precomputation, O(logn) for check.

O(n) Precomputation, O(logn) for check.

O(n)

O(1)

O(log2n)

O(n^2)

Stable

Unstable

In-place

In-partition

Merge Sort

Quick Sort

Bubble Sort

Selection Sort

T(N) = 2T(N-1)+1

T(N) = 2T(N/2)+1

T(N) = 2T(N-1)+N

T(N) = 2T(N-2)+2

Merge Sort

Quick Sort

Bubble Sort

Selection Sort

Merge Sort

Insertion Sort

Bubble Sort

Selection Sort

O(1)

O(n)

O(log2n)

O(n^2)

BFS

Djikstra’s Algorithm

Prims Algorithm

Kruskal’s Algorithm

Sentence Ordering

Course Scheduling

OS Deadlock Detection

All of the above

O(1)

O(N)

O(logN)

O(NlogN)

A problem

A procedure for solving a problem

A real-life mathematical problem

None of the above

As programs

As flow charts

As syntax

As pseudo-codes

O(n)

O(1)

O(logn)

O(n * logn)

If this software is used correctly

In the hardware is used correctly

If there is more than one way to solve the problem

All of the above are correct

Vertex Cover Problem

0/1 Knapsack Problem

Maximal Independent Set Problem

Travelling Salesman Problem

O(n)

O(1)

O(log2n)

O(n^2)

Tree structure

Complete binary tree

Binary tree

None of the above

n - 1

n - 2

O(n)

O(n * logn)

O(1)

O(logn)

Exactly 1

At most 1

At most 2

Depending on the graph

DP Problem

Greedy Algorithm

Adhoc Problem

None of the above

Z Algorithm

Rabin Karp Algorithm

KMP Algorithm

All of the above

O(n)

O(1)

O(nlog2n)

O(n^2)

pop()

peek()

push()

findTop()

O(n^3)

O(n^2)

O(n)

O(n^4)

f1(n) = n^(3/2)

f2(n) = n^(logn)

f3(n) = nlogn

f4(n) = 2^n.

O(N)

O(M * N)

O(M)

O(log N)