Free Printable DAA Tutorial-1

1.

Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1?

T(1) = 2T (n/2) + log n

a)

$\theta\left(n\right)$

b)

$\theta\left(n\ \log n\right)$

c)

$\theta\left(n^2\right)$

d)

$\theta\left(\log n\right)$

2.

The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:

a)

$\theta\left(n\ \log n\right),\ \theta\left(n\ \log n\right),\theta\left(n^2\right)$

b)

$\theta\left(n^2\right),\theta\left(n^2\right),\ \theta\left(n\log n\right)$

c)

$\theta\left(n^2\right),\ \theta\left(n\ \log n\right),\ \theta\left(n\ \log n\right)$

d)

$\theta\left(n^2\right),\ \theta\left(n\ \log n\right),\theta\left(n^2\right)$

3.

To main measures of the efficiency of an algorithm are?

a)

time and space complexity

b)

data and space

c)

processor and memory

d)

complexity and capacity

4.

Which of the following data structure is used to perform recursion?

a)

linked list

b)

stack

c)

array

d)

queue

5.

Identify the best case time complexity of selection sort?

a)

O(nlogn)

b)

O(n^2)

c)

O(n)

d)

O(1)

6.

What is the time complexity of the binary search algorithm?

a)

O(log(2n))

b)

O(n)

c)

O(1)

d)

O(n^2)

7.

Algorithm can be represented as

a)

Pseudocode

b)

Flowchart

c)

Flowchart & Pseudocode

d)

none

8.

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

b)

O(nLogn)

c)

O(n)

d)

O(nLognLogn)

9.

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

10.

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

a)

Inserting

b)

Traversal

c)

Merging

d)

Sorting

11.

A graph in which all vertices have equal degree is known as __

a)

Simple graph

b)

Multi graph

c)

Regular graph

d)

Complete graph

12.

Linked list are not suitable data structure of which one of the following problems ?

a)

Insertion sort

b)

Binary search

c)

Polynomial manipulation

d)

Radix sort

13.

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

14.

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)

15.

Heap is an example of

a)

binary search tree

b)

spanning tree

c)

sparse tree

d)

complete binary tree

16.

What’s happen if base condition is not defined in recursion

a)

Stack underflow

b)

Stack Overflow

c)

None

d)

Both overflow and underflow

17.

Which Data Structure is used to perform Recursion

a)

Queue

b)

Stack

c)

Linked List

d)

Tree

18.

If the size of the stack is 10 and we try to add the 11th element in the stack then the condition is known as___

a)

Underflow

b)

Garbage Collection

c)

Overflow

d)

None

19.

Which one of the following is not the application of the stack data structure

a)

String Reversal

b)

Recursion

c)

Backtracking

d)

Asynchronous data transfer

20.

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

a)

Queue

b)

Stack

c)

Binary tree

d)

Linked list

21.

Which one of the following is not the type of the Queue?

a)

Priority Queue

b)

Circular Queue

c)

Single Ended Queue

d)

Double ended Queue

22.

How many Queues are required to implement a Stack?

a)

3

b)

2

c)

1

d)

4

23.

Which of the following is the time complexity to search an element in the linked list?

a)

O(1)

b)

O(n)

c)

O(logn)

d)

O(nlogn)

24.

Which one of the following node is considered the top of the stack if the stack is implemented using the linked list?

a)

First Node

b)

Second Node

c)

Last node

d)

None

25.

A list of elements in which enqueue operation takes place from one end, and dequeue operation takes place from one end is__

a)

Binary tree

b)

Stack

c)

Queue

d)

Linked list

26.

Which one of the following is the overflow condition if linear queue is implemented using an array with a size MAX_SIZE?

a)

rear = front

b)

rear = front+1

c)

rear=MAX_SIZE -1

d)

rear = MAX_SIZE

27.

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

b)

O(nLogn)

c)

O(n)

d)

O(nLognLogn)

28.

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

c)

O(nlogn)

d)

O(n(logn)²)

29.

Which of the following statements is not true?

a)

Quicksort and merge sort are both examples of divide and conquer algorithms.

b)

If we randomly choose a pivot element each time, quicksort will always terminate in time O(n log n).

c)

For every fixed strategy to choose a pivot for quicksort, we can construct a worst case input that requires time O(n²).

d)

If we could find the median in time O(n), quicksort would have worst case complexity O(n log n).

30.

Which is purely upper bound notation?

a)

Big-oh

b)

Small-oh

c)

Big-omega

d)

Theta

31.

The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:

a)

$\theta\left(n\ \log n\right),\ \theta\left(n\ \log n\right),\theta\left(n^2\right)$

b)

$\theta\left(n^2\right),\theta\left(n^2\right),\ \theta\left(n\log n\right)$

c)

$\theta\left(n^2\right),\ \theta\left(n\ \log n\right),\ \theta\left(n\ \log n\right)$

d)

$\theta\left(n^2\right),\ \theta\left(n\ \log n\right),\theta\left(n^2\right)$

32.

Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1?

T(1) = 2T (n/2) + log n

a)

$\theta\left(n\right)$

b)

$\theta\left(n\ \log n\right)$

c)

$\theta\left(n^2\right)$

d)

$\theta\left(\log n\right)$

DAA Tutorial-1

Total questions: 32

Worksheet time: 16mins

Similar Resources on Wayground