wayground logo

Free Printable Worksheets

Font size

S
M
L
XL
Worksheets

DAA- Tutorial

Total questions: 73

Worksheet time: 41mins

Name
Class
Date
1.

What is the Complexity of BUILD_MAX_HEAP function?

a)

O(log n)

b)

O(n log n)

c)

O(n)

d)

None of the above

2.

Heap_Increase_key operation is used for

a)

Increase the depth of the heap

b)

to insert a new node in the heap with given key.

c)

to increase the value of the given index with the new key value

d)

to remove the max value from the heap

3.

What is the lower bound for comparison based sorting algorithms?

a)

nlogn

b)

n2

c)

logn

d)

n

4.

What is the order of partition algorithm in quick sort?

a)

O(logn)

b)

O(nlogn)

c)

O(n)

d)

O(1)

5.

Order the complexity function in ascending order of their complexity

a. n

b. log n

c. n2

d. n logn

a)

a, b, c, d

b)

c, d, a, b

c)

b, a, d, c

d)

d, c, b, a

6.
Which sorting algorithm makes one swap per pass (possibly swapping an element with itself)?
a)
Selection Sort
b)
Bubble Sort
c)
Insertion Sort
7.
Which sorting algorithm may make multiple swaps per pass?
a)
Bubble Sort
b)
Selection Sort
c)
Insertion Sort
8.
Which sorting algorithm shifts elements instead of swapping elements if needed in each pass.
a)
Bubble Sort
b)
Selection Sort
c)
Insertion Sort
9.
How many passes will both the selection and insertion sorts make?
a)
N
b)
N-1
c)
N+1
d)
(N+1)/2
10.
The following lists represent 3 passes of a sorting algorithm. Which algorithm is being used to sort the list?
 
4    5    9    6    2    7
4    5    6    2    7    9 
4    5    2    6    7    9
a)
Bubble Sort
b)
Selection Sort
c)
Insertion Sort
11.
The following lists represent 3 passes of a sorting algorithm. Which algorithm is being used to sort the list?
 
4    8    3    9    2    6 
2    8    3    9    4    6
2    3    8    9    4    6
a)
Bubble Sort
b)
Selection Sort
c)
Insertion Sort
12.
We are sorting the following list in ascending order:
 
1    4    2    9    3    8    5
 
What does the list look like after one pass of the bubble sort algorithm. 
a)
1 2 4 3 8 5 9
b)
1 4 2 5 3 8 9
c)
4 2 9 3 8 5 1
13.
We are sorting the following list in descending order:
 
1    4    2    9    3    8    5
 
What does the list look like after one pass of the selection sort algorithm.
a)
1 4 2 9 3 8 5
b)
9 4 2 1 3 8 5
c)
4 2 9 3 8 5 1
14.
We are sorting the following list in ascending order:
 
1    4    2    9    3    8    5
 
What does the list look like after one pass of the insertion sort algorithm. 
a)
1 4 2 9 3 8 5
b)
4 2 9 3 8 5 1
c)
4 1 2 9 3 8 5
15.

Which of the following is not a stable sorting algorithm?

a)

a) Insertion sort

b)

b) Selection sort

c)

c) Bubble sort

d)

d) Merge sort

16.

Running merge sort on an array of size n which is already sorted is

a)

a) O(n)

b)

b) O(nlogn)

c)

c) O(n2)

d)

d) None

17.

The time complexity of heap sort in worst case is

a)

a) O(logn)

b)

b) O(n)

c)

c) O(nlogn)

d)

d) O(n2)

18.

Which of the following algorithm pays the least attention to the ordering of the elements in the input list?

a)

a) Insertion sort

b)

b) Selection sort

c)

c) Quick sort

d)

d) None

19.

Time complexity of bubble sort in best case is

a)

a) θ (n)

b)

b) θ (nlogn)

c)

c) θ (n2)

d)

d) θ (n(logn) 2)

20.

Which of the following is not an in-place sorting algorithm?

a)

a) Selection sort

b)

b) Heap sort

c)

c) Quick sort

d)

d) Merge sort

21.

If a problem can be solved by combining optimal solutions to non-overlapping problems, the strategy is called _____________

a)

Dynamic programming

b)

Greedy

c)

Divide and conquer

d)

Recursion

22.

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

23.

Binary Search Uses

a)

Decrease and Conquer Design Technique

b)

Divide Conquer Design Technique

c)

Greedy Design Technique

d)

None of these

24.

Efficiency of an Algorithm is decided by the

a)

Number of times the basic operation is executed

b)

Time taken for executing the program

c)

Number of instructions in the program

d)

All of these

25.

Heap should satisfy

a)

Shape Property

b)

Parental Dominance Property

c)

Both Shape and Parental Dominance Property

d)

None of these

26.

__________solves only subproblems that are

necessary and does so only once.

a)

Dynamic Programming

b)

Memory Function

c)

Both Dynamic Programming & Memory Function

d)

Greedy Approach

27.
Which sorting algorithm makes one swap per pass (possibly swapping an element with itself)?
a)
Selection Sort
b)
Bubble Sort
c)
Insertion Sort
28.

What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?

a)

Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n^2)

b)

Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n^2)

c)

Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn)

d)

Recurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nLogn)

29.

Binary Search Algorithm cannot be applied to

a)

Sorted linear array

b)

Sorted binary tree

c)

Sorted linked list

d)

Pointer array

30.

Its central assumption is that instructions are executed one after another, one operation at a time.

(a)  

31.

ADT stands for?

a)

Abstract Data Type

b)

Algorithmic Design Technique

c)

Algebraic Data Text

d)

Assignment Data Transfer

32.

It is the better implementation of a priority queue that is based on ingenious data structure.

(a)  

33.

important Properties of Graphs. (Select all that applies)

a)

Connectivity

b)

Acyclicity

c)

Height

d)

Depth

e)

Dictionary

34.

Execution time taken by an algorithm is evaluated while the algorithm is being executed

a)

Posteriori Analysis

b)

Priori Analysis

c)

Both a and b

d)

None

35.

What is time complexity of fun()?

int fun(int n)

{

int count = 0;

for (int i = n; i > 0; i /= 2)

for (int j = 0; j < i; j++)

count += 1;

return count;

}

a)

O(n2)

b)

O(nLogn)

c)

O(n)

d)

O(nLognLogn)

36.

What is the time complexity of fun()?

int fun(int n)

{

int count = 0;

for (int i = 0; i < n; i++)

for (int j = i; j > 0; j--)

count = count + 1;

return count;

}

a)

Theta (n)

b)

Theta (n2)

c)

Theta (nLogn)

d)

Theta (nLognLogn)

37.

Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2, f3 and f4?

f1(n) = 2^n

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

f3(n) = nLogn

f4(n) = n^(Logn)

a)

f3, f2, f4, f1

b)

f3, f2, f1, f4

c)

f2, f3, f1, f4

d)

f2, f3, f4, f1

38.

What is the best case time complexity of fun()?

void fun(int n, int arr[])

{

int i = 0, j = 0;

for(; i < n; ++i)

while(j < n && arr[i] < arr[j])

j++;

}

a)

O(n)

b)

O(n2)

c)

O(nlogn)

d)

O(n(logn)2)

39.

What is the complexity of the function unknown()

int unknown(int n) {

int i, j, k = 0;

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

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

k = k + n/2;

return k;

}

a)

𝞱(n2)

b)

𝞱(nlogn)

c)

𝞱(n2logn)

d)

𝞱(n3logn)

40.

What is the complexity of the function unknown()

int unknown(int n) {

int i, j, k = 0;

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

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

k = k + n/2;

return k;

}

a)

𝞱(n2)

b)

𝞱(nlogn)

c)

𝞱(n2logn)

d)

𝞱(n3logn)

41.

. What does it mean when we say that an algorithm X is asymptotically more efficient than Y?

a)

X will be a better choice for all inputs

b)

X will be a better choice for all inputs except small inputs

c)

X will be a better choice for all inputs except large inputs

d)

Y will be a better choice for small inputs

42.

In a min-heap:

a)

parent nodes have values less than or equal to their childs

b)

parent nodes have values greater than or equal to their childs

c)

parent nodes have values greater than their childs

d)

parent nodes have values less than their childs

43.

Time required to merge two sorted lists of size m and n, is

a)

Ο(m | n)

b)

Ο(m + n)

c)

Ο(m log n)

d)

Ο(n log m)

44.

Index of arrays in C programming language starts from

a)

0

b)

1

c)

either 0 or 1

d)

undefined

45.

Heap is an example of

a)

binary search tree

b)

spanning tree

c)

sparse tree

d)

complete binary tree

46.

The right child of Binary search tree always should be

a)

less than root node

b)

greater than root node

c)

should be equal to left child

d)

none

47.

Dijkstra’s Algorithm cannot be applied on ______________

a)

Directed and weighted graphs

b)

Graphs having negative weight function

c)

Undirected graphs

d)

None

48.

Which Data Structure is used to perform Recursion

a)

Queue

b)

Stack

c)

Linked List

d)

Tree

49.

Which data structure is required to convert the infix to prefix notation?

a)

Stack

b)

Linked List

c)

Binary Tree

d)

Queue

50.

Which of the following is not the correct statement for a stack data structure?

a)

Arrays can be used to implement the stack

b)

Stack follows FIFO

c)

Elements are stored in a sequential manner

d)

Top of the Stack contains the last inserted element

51.

Which of the following statement is not true regarding the priority queue?

a)

Processes with different priority can be easily handled

b)

Easy to implement

c)

Deletion is easier

d)

None of the above

52.

Which one of the following is the size of int arr[9] assuming that int is of 4 bytes?

a)

9

b)

36

c)

35

d)

None

53.

The number of elements that can be sorted in O(logn ) time using heap sort is:

a)

O(1)

b)

O(logn)

c)


O(log⁡n)O\left(\sqrt{\log n}\right)

d)

O(log⁡nlog⁡ log⁡n)O\left(\frac{\log n}{\log\ \log n}\right)

54.

If we use Radix sort to sort n integers in the range 

(nk2, nk]\left(n^{\frac{k}{2}},\ n^k\right] , for some k>0 which is independent of n, the time taken would be:

a)

O(n)

b)

O(kn)

c)

O(nlogn)

d)

O(n^2)

55.

Following algorithm can be used to sort n integers in the range

[1.......n3]\left[1.......n^3\right]  in O(n) time:

a)

Heap Sort

b)

Quick Sort

c)

Merge Sort

d)

Radix Sort

56.

Consider the following sorting algorithms.

I. Quick Sort

II. Heap Sort

III. Merge Sort

Which of them perform in least time in the worst case?

a)

I and II only

b)

II and III only

c)

III only

d)

I, II and III

57.

Which of the following is true for computation time in insertion, deletion and finding maximum and minimum element in a sorted array?

a)

Insertion-O(1), Deletion-O(1), Maximum-O(1), Minimum-O(1)

b)

Insertion-O(1), Deletion-O(1), Maximum-O(n), Minimum-O(n)

c)

Insertion-O(n), Deletion-O(n), Maximum-O(1), Minimum-O(1)

d)

Insertion-O(n), Deletion-O(n), Maximum-O(n), Minimum-O(n)

58.

Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE?

I. QuickSort runs in O(n2) time.

II. BubbleSort runs in O(n2) time.

III. MergeSort runs in O(n) time.

IV. InsertionSort runs in O(n) time.

a)

I and II only

b)

I and III only

c)

II and IV only

d)

I and IV only

59.

Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?

a)

256

b)

512

c)

1024

d)

2048

60.

Merge sort follow which strategy

(a)  

61.

Choose the recursive formula for the Fibonacci series.(n>=1)

a)

F(n) = F(n+1) + F(n+2)

b)

F(n) = F(n) + F(n+1)

c)

F(n) = F(n-1) + F(n-2)

d)

F(n) = F(n-1) – F(n-2)

62.

Which of the following sorting algorithms is the fastest?

a)

Merge sort

b)

Quick sort

c)

Insertion sort

d)

Shell sort

63.

Which of the following methods is the most effective for picking the pivot element?

a)

first element

b)

last element

c)

median-of-three partitioning

d)

random element

64.

Recursion is similar to which of the following?

a)

Switch Case

b)

Loop

c)

If-else

d)

if elif else

65.

There are two ducks in front of a duck, two ducks behind a duck and a duck in the middle. How many ducks are there?

a)

Four

b)

Three

66.

रामप्रकाश की ओर संकेत करते हुये नीलम ने कहा कि-"उसके भाई का पिता मेरे दादाजी का एकमात्र पुत्र है"। नीलम का रामप्रकाश की साथ क्या रिश्ता है?

Pointing towards Ramprakash, Neelam said, "His brother's father is the only son of my grandfather". How is Neelam related to Ramprakash?

a)

बहन

b)

पुत्री

c)

माँ

d)

भेतीजी

67.
Ken got 6 out of 24 questions correct on a test. What is his grade? 
a)
6%
b)
25%
c)
50%
d)
33%
68.

A is the brother of B, C is the father of D, E is the mother of B. A and D are brother. How is E related to C?

a)

Niece

b)

Wife

c)

Sister

d)

Sister-in-law

69.

X is the father of W. But W is not his son. B is the daughter of W. I is the spouse of X. O is the brother of W. D is the son of O.G is the spouse of O. H is the father of G.

i) Who is the paternal grandfather of D?

a)

X

b)

H

c)

O

d)

None Of these

70.

Pointing to a man in a photograph, Sayali said, “His mother’s only daughter is my mother.” How is Sayali related to that man?

a)

Nephew

b)

Sister

c)

Wife

d)

Niece

71.

Pointing to a girl in the photograph, Umesh said, “Her mother’s brother is the only son of my mother’s father.” How is the girl’s mother related to Umesh?

a)

Mother

b)

Sister

c)

Aunt

d)

Grand mother

72.

Q is the brother of R; P is the sister of Q; T is the brother of S; S is the daughter of R. How is Q related to T?

a)

Uncle

b)

Father

c)

Brother-in-law

d)

Nephew

73.

Pointing to a lady, Anup said, “She is the only daughter of the lady who is the mother of my mother’s only grandson”. How is the lady which is pointed related to Anup?

a)

daughter

b)

Wife

c)

Sister

d)

Mother

Similar Resources on Wayground

WCA Welcome to the Industry Quizziz 2

73 questions

WCA Welcome to the Industry Quizziz 2

quiz

Worksheet

•

9th Grade - University

Chapter 5: Infection Control - Principles & Practices

75 questions

Chapter 5: Infection Control - Principles & Practices

quiz

Worksheet

•

9th Grade - Professio...

DAA Tutorial-1

70 questions

DAA Tutorial-1

quiz

Worksheet

•

University

1 bimestre Biomas Brasileiro e Mundial

68 questions

1 bimestre Biomas Brasileiro e Mundial

quiz

Worksheet

•

University

CET Section I-1

75 questions

CET Section I-1

quiz

Worksheet

•

University

Revision

72 questions

Revision

quiz

Worksheet

•

University

Randomness

69 questions

Randomness

quiz

Worksheet

•

4th Grade - University

Ninjago

72 questions

Ninjago

quiz

Worksheet

•

KG - Professional Dev...