wayground logo

Free Printable Worksheets

Font size

S
M
L
XL
Worksheets

DAA 2023- 2024 Test 8

Total questions: 100

Worksheet time: 1hrs 18mins

Name
Class
Date
1.

What is the time complexity of this code

int a = 0, i = N;

while (i > 0)

{

a += i;

i /= 2;

}

a)

O(N)

b)

O(Sqrt(N))

c)

O(N / 2)

d)

O(log N)

2.

The complexity of Binary search algorithm is

a)

O(n)

b)

O(log n)

c)

O(n2)

d)

O(n log n)

3.

Time Complexity of this program:

def f():

a = 0

for i = 1 to n:

a += i;

b = 0

for i = 1 to m:

b += i;

a)

O(n)

b)

O(m)

c)

O(n+m)

d)

O(n*m)

4.

The complexity of Bubble sort algorithm is

a)

O(n)

b)

O(log n)

c)

O(n2)

d)

O(n log n)

5.

If for an algorithm time complexity is given by O(1) then complexityof it is:

a)

constant

b)

polynomial

c)

exponential

d)

none of the mentioned

6.

If for an algorithm time complexity is given by O(log2n) then complexity will:

a)

constant

b)

polynomial

c)

exponential

d)

none of the mentioned

7.

If for an algorithm time complexity is given by O(n) then complexityof it is:

a)

A. constant

b)

B. linear

c)

C. exponential

d)

D. none of the mentioned

8.

To measure Time complexity of an algorithm Big O notation is used which:

a)

A. describes limiting behaviour of the function

b)

B. characterises a function based on growth of function

c)

C. upper bound on growth rate of the function

d)

D. all of the mentioned

9.

What is the time complexity of following code:

int a = 0;

for (i = 0; i < N; i++) {

for (j = N; j > i; j--) {

a = a + i + j;

}

}

a)

O(N)

b)

O(N*log(N))

c)

O(N * Sqrt(N))

d)

O(N*N)

10.

What is the time complexity of following code:

int i, j, k = 0;

for (i = n / 2; i <= n; i++) {

for (j = 2; j <= n; j = j * 2) {

k = k + n / 2;

}

}

a)

O(n)

b)

O(nLogn)

c)

O(n^2)

d)

O(n^2Logn)

11.

Which of the problems cannot be solved by backtracking method?

a)

n-queen problem

b)

subset sum problem

c)

Hamiltonian circuit problem

d)

travelling salesman problem

12.

Backtracking algorithm is implemented by constructing a tree of choices called as?

a)

State-space tree


b)

state chart tree

c)

node tree

d)

Backtracking tree

13.

The problem of finding a path in a graph that visits every vertex exactly once is called?

a)

Hamiltonian path problem

b)

Hamiltonian cycle problem

c)

sum of subset problem

d)

Turnpike reconstruction problem

14.

Which of the following problems is similar to that of a Hamiltonian path problem?

a)

Knapsack problem

b)

closest pair problem

c)

travelling salesman problem

d)

assignment problem

15.

The problem of finding a subset of positive integers whose sum is equal to a given positive integer is called as?

a)

n- queen problem


b)

sum of subsets problem

c)

knapsack problem

d)

Hamiltonian circuit problem

16.

Branch and bound is a __________


a)

problem solving technique

b)

data structure

c)

sorting algorithm

d)

type of tree

17.

Choose the correct statement from the following.

a)

Greedy method is efficient than dynamic programming approach

b)

Backtracking approach gives only one optimal solution

c)

Branch and bound can be used for solving Optimization problems

d)

None of these

18.

Problems that can be solved in polynomial time are known as?

a)

intractable

b)

tractable

c)

decision

d)

complete

19.

28. _________ is the class of decision problems that can be solved by non-deterministic polynomial algorithms?

a)

NP

b)

P

c)

Hard

d)

Complete

20.

Problems that can be verified in Polynomial time are called

a)

P problems

b)

NP problems

c)

Tractable problems

d)

none of these

21.

To which of the following class does a CNF-satisfiability (say 3-SAT)problem belong?

a)

NP class

b)

P class

c)

NP complete

d)

NP hard

22.

Which of the following problems is NOT solved using dynamic programming?

a)

0/1 knapsack problem

b)

Matrix chain multiplication problem

c)

Edit distance problem

d)

Fractional knapsack problem

23.

A greedy algorithm can be used to solve all the dynamic programming problems.

a)

True

b)

False

24.

What happens when the backtracking algorithm reaches a complete solution?

a)

It backtracks to the root

b)

It continues searching for other possible solutions

c)

It traverses from a different route

d)

Recursively traverses through the same route

25.

..................................... of an undirected graph is to find minimum subset of vertices that cover all the edges.

a)

3-SAT Problem

b)

Clique problem

c)

Boolean problem

d)

vertex cover problem

26.

A graph with 'n' number of vertices is said to be complete if it contains ............number of edges.

a)

n

b)

n-1

c)

n(n-1)/2

d)

n/2

27.

....................... is the act of finding a set of variable assignments to True or False that make that statement true or alternately providing a proof that no such set of variable assignments can exist.

a)

3-SAT Problem

b)

Vertex Cover Problem

c)

Clique problem

d)

Clique decision problem

28.

Clique is a sub-graph of a graph which is complete.

a)

True

b)

False

29.

Dynamic programming differs from the greedy method since the greedy method produces only one feasible solution, which may or may not be optimal, while dynamic programming produces all possible sub-problems at most once, one of which guaranteed to be optimal.

a)

True

b)

False

30.

A...................... is a maximal connected sub-graph of a graph

a)

Component

b)

Connected component

c)

Bi-connected component

d)

none

31.

........................ are a type of computer memory used to quickly accept, store, and transfer data and instructions that are being used immediately by the CPU.

a)

Input Unit

b)

Registers

c)

Output Unit

d)

Control memory

32.

The symbolic notation used to describe the micro-operations performed on registers is called a ............................................

a)

Binary Language

b)

High level language

c)

Register Transfer Language

d)

None of these

33.

Operations that can be performed on data stored in Registers are called...........

a)

Micro operations

b)

Binary operations

c)

Low level operations

d)

High level operations

34.

................................ are the categories of Register Micro-operations

a)

Register Transfer Micro operations

b)

Arithmetic Micro operations

c)

Logic Micro operations

d)

Shift Micro operations

e)

All of the above

35.

......................................... Micro-operations implies transfer of binary information form one register to another register.

a)

Register Transfer Micro-operations

b)

logic Micro-operations

c)

shift Micro-operations

d)

Arithmetic Micro-operations

36.

...............................micro operations perform Arithmetic operations on numeric data stored in registers.

a)

Logic

b)

Arithmetic

c)

Shift

d)

Register Transfer

37.

.........................micro operations perform shift operations on data stored in registers.

a)

Shift

b)

Logic

c)

Register Transfer

d)

Arithmetic

38.

..........................micro -operations perform bit manipulation operations on non numeric data stored in registers.

a)

shift

b)

Logic

c)

Register Transfer

d)

Arithmetic

39.

........................Operator is used to transfer data from from one register to another register

a)

Conditional Operator

b)

Replacement operator

c)

Unary Operator

d)

Binary operator

40.

A multiplexer also known as a data selector, is a device that selects between several analog or digital input signals and forwards it to a single output line.

a)

True

b)

False

41.

........................... , ........................ and ...........................are the different ways in which an algorithm can be specified.

a)

Asymptotic Notations, Flowchart, Pseudocode

b)

English like statements, Flowchart, Pseudocode

c)

English like statements,Sets, Pseudsocode

d)

None of the above

42.

Algorithm can be represented graphically using...........................

a)

barchart

b)

Graph

c)

Pie chart

d)

Flowchart

43.

...............................is defined as step by step procedure for solving a particular problem

a)

Space complexity

b)

Time complexity

c)

Performance Analysis

d)

Algorithm

44.

An Algorithm's performance an be analysed by using............................

a)

Time complexity

b)

Space Complexity

c)

Number of inputs

d)

Time and space complexity

45.

..............................is defined as the amount of Computer time required to complete the execution of a program/problem

a)

Space Complexity

b)

Time complexity

c)

CPU Time

d)

None of these

46.

Upper bound running time complexity of an algorithm is also called as.....................

a)

Best case time complexity

b)

Worst case time complexity

c)

Average case time complexity

d)

None of these

47.

.......................is the amount of computer memory required to the execute the program /problem.

a)

Time complexity

b)

Space complexty

c)

Memory complexity

d)

None of these

48.

Lower bound running time complexity of an algorithm is also called as.................

a)

Best case time complexty

b)

Worst case time complexity

c)

Average case time complexity

d)

None of these

49.

............................Notation is used to represent strict upper bound running time complexity of an algotihm

a)

Big-oh

b)

Big-Omega

c)

Theta

d)

None of these

50.

............................Notation is used to represent strict lower bound running time complexity of an algorithm.

a)

Big-Oh

b)

Big-Omega

c)

Theta

d)

None of these

51.

.................................notation denotes Average case Time complexity

a)

Big-Oh

b)

Big Omega

c)

Theta

d)

None of these

52.

........................................Notations are called as Asymptotic Notations.

a)

Big-oh

b)

Big-Omega

c)

little-Theta

d)

little-oh

e)

theta

53.

......................is used to represent strict upper bound running time complexity where as.................is used to represent upper bound running time complexity of an algorithm.

a)

Big-oh,little-oh

b)

little-oh,Big-oh

c)

Big-oh,small-oh

d)

small-oh,Big-oh

54.

......................is used to represent strict lower bound running time complexity where as.................is used to represent lower bound running time complexity of an algorithm.

a)

Big-Omega,small-omega

b)

Big-Omega,little-omega

c)

lttle-omega,Big-omega

d)

small-omega,Big-Omega

55.

Let f(n) and g(n) be two non-negative functions,f(n)=O(g(n)) if and only if..........................

a)

f(n)<=c*g(n)

b)

f(n)>=c*g(n)

c)

f(n)<c*g(n)

d)

f(n)<c*g(n)

56.

Let f(n) and g(n) be two non-negative functions,f(n)= ω\omega  (g(n)) if and only if..........................


a)

f(n)<=c*g(n)

b)

f(n)>=c*g(n)

c)

f(n)<c*g(n)

d)

f(n)<c*g(n)

57.

Let f(n) and g(n) be two non-negative functions,f(n)=  θ\theta  (g(n)) if and only if..........................

a)

c1*g(n)<=f(n)<=c2*g(n)

b)

c1*g(n)>=f(n)>=c2*g(n)

c)

c1*g(n)<f(n)<c2*g(n)

d)

c1*g(n)>f(n)>c2*g(n)

58.

...................................are the characteristics of an algorithm

a)

Input

b)

infiniteness

c)

Effectiveness

d)

output

e)

finiteness

59.

Find the time complexity for the following algorithm using step count method.

Algorithm sum(a,n)

{

nsum=0;

for(i=1;i<=n;i++)

{

nsum=nsum+a[i];

}

}

a)

2n+2 units

b)

2n+1 units

c)

n+1 units

d)

n+2 units

60.

Find the space complexity for the following algorithm

Algorithm sum(a,b,c)

{

a=10;

b=20;

c=30;

d=a+b+c;

}

a)

3 units

b)

4 units

c)

5 units

d)

6 units

61.
What is the best case and worst case complexity of ordered linear search?
a)
O(nlogn), O(logn)
b)
O(logn), O(nlogn)
c)
O(n), O(1)
d)
O(1), O(n)
62.

What does the following piece of code do?

for (int i = 0; i < arr.length-1; i++) {

for (int j = i+1; j < arr.length; j++) {

if( (arr[i].equals(arr[j])) && (i != j) ) {

System.out.println(arr[i]);

}

}

}

a)

Print the duplicate elements in the array

b)

Print the element with maximum frequency

c)

Print the unique elements in the array

d)

Prints the element with minimum frequnecy

63.
Which of the following is a disadvantage of linear search?
a)
Requires more space
b)
Greater time complexities compared to other searching algorithms
c)
Not easy to understand
d)
Not easy to implement
64.
For the following question, how will the array elements look like after second pass? 34, 8, 64, 51, 32, 21
a)
8, 21, 32, 34, 51, 64
b)
8, 32, 34, 51, 64, 21
c)
8, 34, 51, 64, 32, 21
d)
8, 34, 64, 51, 32, 21
65.
Choose the incorrect statement about merge sort from the following?
a)
it is a comparison based sort
b)
it is an adaptive algorithm
c)
it is not an in place algorithm
d)
it is stable algorithm
66.
Which is the safest method to choose a pivot element in quick sort?
a)
choosing a random element as pivot
b)
choosing the first element as pivot
c)
choosing the last element as pivot
d)
median-of-three partitioning method
67.
The given array is arr = {2,3,4,1,6}. What are the pivots that are returned as a result of subsequent partitioning?
a)
1 and 3
b)
3 and 1
c)
2 and 6
d)
6 and 2
68.
Apply Quick sort on a given sequence 7 11 14 6 9 4 3 12. What is the sequence after first phase, pivot is first element?
a)
6 4 3 7 11 9 14 12
b)
6 3 4 7 9 14 11 12
c)
7 6 14 11 9 4 3 12
d)
7 6 4 3 9 14 11 12
69.
Depth First Search is equivalent to which of the traversal in the Binary Trees?
a)
Pre-order Traversal
b)
Post-order Traversal
c)
Level-order Traversal
d)
In-order Traversal
70.
In BFS, how many times a node is visited?
a)
Once
b)
Twice
c)
Equivalent to number of indegree of the node
d)
Thrice
71.
Choose the correct statement from the following.
a)
branch and bound is more efficient than backtracking
b)
branch and bound is not suitable where a greedy algorithm is not applicable
c)
branch and bound divides a problem into at least 2 new restricted sub problems
d)
backtracking divides a problem into at least 2 new restricted sub problems
72.
Consider the graph M with 3 vertices. Its adjacency matrix is shown below. Which of the following is true?
a)
Graph M has no minimum spanning tree
b)
Graph M has a unique minimum spanning trees of cost 2
c)
Graph M has 3 distinct minimum spanning trees, each of cost 2
d)
Graph M has 3 spanning trees of different costs
73.
Consider the graph shown below. Which of the following are the edges in the MST of the given graph?
a)
(a-c)(c-d)(d-b)(d-b)
b)
(c-a)(a-d)(d-b)(d-e)
c)
(a-d)(d-c)(d-b)(d-e)
d)
(c-a)(a-d)(d-c)(d-b)(d-e)
74.
Consider the following graph. Using Kruskal’s algorithm, which edge will be selected first?
a)
GF
b)
DE
c)
BE
d)
BG
75.
 Which of the following edges form minimum spanning tree on the graph using kruskals algorithm?
a)
(B-E)(G-E)(E-F)(D-F)
b)
(B-E)(G-E)(E-F)(B-G)(D-F)
c)
(B-E)(G-E)(E-F)(D-E)
d)
(B-E)(G-E)(E-F)(D-F)(D-G)
76.
Consider the given graph.What is the weight of the minimum spanning tree using the Prim’s algorithm,starting from vertex a?
a)
23
b)
28
c)
27
d)
11
77.
Worst case is the worst case time complexity of Prim’s algorithm if adjacency matrix is used?
a)
O(log V)
b)
O(V^2)
c)
O(E^2)
d)
O(V log E)
78.
Let us consider a list of numbers (34, 16, 2, 93, 80, 77, 51) and has table size is 10. What is the order of elements(from index 0 to size-1) in the hash table?
a)
null, null, 77, 16, null, 34, 93, 2, 51, 80
b)
77, 16, 34, 93, 2, 51, 80
c)
80, 51, 2, 93, 34, null, 16, 77, null, null
d)
80, 51, 2, 93, 34, 16, 77
79.
Consider a hash table of size 7, with hash function H (k) = k % 7, and pseudo random i = (i + 5) % 7. We want to insert the following keys one by one from left to right. 15, 11, 25, 16, 9, 8, 12 What will be the position of the key 25, if we use random probing?
a)
4
b)
5
c)
1
d)
2
80.

What is the running time of Strassen's algorithm for matrix multiplication?

a)

O(n2.81)

b)

O(n3)

c)

O(n1.8)

d)

O(n2)

81.

Which of the following standard algorithms is not Dynamic Programming based

a)

Floyd Warshall Algorithm for all pairs shortest paths

b)

0-1 Knapsack problem

c)

Prim's

d)

Optimal Binary Search Trees

82.

In dynamic programming, the technique of storing the previously calculated values is called .....

a)

Saving value property

b)

Storing value property

c)

Memoization

d)

Mapping

83.

When dynamic programming is applied to a problem, it takes far less time as compared to other methods that don't take advantage of overlapping sub problems.

a)

True

b)

False

84.

 Floyd Warshall’s Algorithm is used for solving ____________

a)

All pair shortest path problems

b)

Single Source shortest path problems

c)

Network flow problems

d)

Sorting problems

85.

What is the time complexity of Dijikstra’s algorithm?

a)

O(N)

b)

O(N3)

c)

O(N2)

d)

O(logN)

86.

Prim's algorithm is a .....

a)

Divide and conquer algorithm

b)

Greedy algorithm

c)

Dynamic Programming

d)

Approximation algorithm

87.

From the following given tree, what is the code word for the character ‘a’?

a)

011

b)

010

c)

100

d)

101

88.

Two main measures for the efficiency of an algorithm are

a)

Time and Space

b)

Processor and Memory

c)

Complexity and Capacity

d)

Data and space

89.

Which algorithm is used to solve a maximum flow problem?

a)

Prim’s algorithm

b)

Kruskal’s algorithm

c)

Dijkstra’s algorithm

d)

Ford-Fulkerson algorithm

90.

The "I" in the AIDA stands for

a)

Impact

b)

Interest

c)

Intution

d)

Importance

91.

The "D" in the AIDA stands for

a)

Denial

b)

Detailing

c)

Duplication

d)

Desire

92.

It is culturally acceptable to show enthusiasm

a)

US Culture

b)

UK Culture

93.

This culture believes in Hierarchy

a)

US Culture

b)

UK Culture

94.

The globally number 1 time waster is _________

a)

Indecision

b)

Aimless Meetings

c)

Over Reliance on Emails

d)

Web Surfing Breaks

95.

The globally number 2 time waster is _________

a)

Indecision

b)

Aimless Meetings

c)

Over Reliance on Emails

d)

Web Surfing Breaks

96.

RAC Stands for

a)

Record - Assimilate - Change

b)

Record - Analyse - Change

c)

Receive - Analyse - Change

d)

Record - Analyse - Collaborate

97.

Which one of these statements is true about Customer Focus

a)

Be problem focused

b)

Be solution focused

c)

Be task focused

d)

Be deliverable focused

98.

Small talk is an absolute must in this culture

a)

US Culture

b)

UK Culture

99.

Supervisors encourage creativity over hierarchy

a)

US Culture

b)

UK Culture

100.

Which of the following standard algorithms is not Dynamic Programming based.

a)

Bellman–Ford Algorithm for single source shortest path

b)

Floyd Warshall Algorithm for all pairs shortest paths

c)

0-1 Knapsack problem

d)

Prim's Minimum Spanning Tree

Similar Resources on Wayground

Daily RS Challenge Trivia

100 questions

Daily RS Challenge Trivia

quiz

Worksheet

•

KG - Professional Dev...

Minecraft

100 questions

Minecraft

quiz

Worksheet

•

KG - Professional Dev...

lathan bing

100 questions

lathan bing

quiz

Worksheet

•

1st Grade

CHRISTMAS GAME🎄

96 questions

CHRISTMAS GAME🎄

quiz

Worksheet

•

1st - 5th Grade

Trắc Nghiệm Học Phần 2

96 questions

Trắc Nghiệm Học Phần 2

quiz

Worksheet

•

1st Grade - University

Nature [ENG-VIET Complete] Level 3

100 questions

Nature [ENG-VIET Complete] Level 3

quiz

Worksheet

•

KG - Professional Dev...

Heat Pump Prep Test

100 questions

Heat Pump Prep Test

quiz

Worksheet

•

1st Grade - Professio...

LATIHAN PENILAAN SEMESTER GANJIL

95 questions

LATIHAN PENILAAN SEMESTER GANJIL

quiz

Worksheet

•

1st Grade