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.

Alorithm should have finite number of steps

a)

True

b)

False

c)

sometimes

d)

none

9.

which is not the important aspect of Loop

a)

Initial condition

b)

nested loop

c)

invariant relation

d)

termination

10.

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)

11.

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

12.

This characteristic describes whether the data items are arranged in chronological sequence, such as with an array, or in an unordered sequence, such as with a graph.

a)

Static or dynamic

b)

Linear or non-linear

c)

Homogeneous or non-homogeneous

13.

It is a method of solving problems that involves breaking a problem down into smaller and smaller sub problems until you get to a small enough problem that it can be solved trivially.

a)

Recursion

b)

Iteration

c)

Looping

14.

In this type of search, a sequential search is made over all items one by one.

a)

Search

b)

Binary Search

c)

Linear Search

15.

It is used to implement an associative array, a structure that can map keys to values.

a)

linked list

b)

hashing

c)

trees

d)

array

16.

It is a linear data structure that stores a collection of elements. Operates on first in first out (FIFO) algorithm.

a)

stack

b)

data structure

c)

queue

d)

array

17.

push() and pop() functions are found in..

a)

stacks

b)

trees

c)

queues

d)

lists

18.

How is an array initialized in C language?

a)

int a[3] = {1, 2, 3};

b)

int a = {1, 2, 3};

c)

int a[] = new int[3]

d)

int a(3) = [1, 2, 3];

19.

Which of the following is not the type of queue?

a)

Priority queue

b)

Single-ended queue

c)

Circular queue

d)

Ordinary queue

20.

What will the output of the following code snippet?

void solve() {

int a[] = {1, 2, 3, 4, 5};

int sum = 0;

for(int i = 0; i < 5; i++) {

if(i % 2 == 0) {

sum += *(a + i);

}

else {

sum -= *(a + i);

}

cout << sum << endl;

}

a)

15

b)

syntax error

c)

3

d)

2

21.

How are String represented in memory in C?

a)

LinkedList of characters.

b)

The object of some class.

c)

An array of characters.

d)

Same as other primitive data types.

22.

In Binary trees nodes with no successor are called......

a)

Final nodes

b)

Last nodes

c)

Terminal nodes

d)

End nodes

23.

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

a)

Inserting

b)

Traversal

c)

Merging

d)

Sorting

24.

In ........, search start at the beginning of the list and check every element in the list.

a)

Binary Search

b)

Binary Tree Search

c)

Hash Search

d)

Linear Search

25.

Any node is the path from the root to the node is called

a)

Ancestor node

b)

Internal node

c)

Successor node

d)

None of the above

26.

A graph is a tree if and only if graph is

a)

Directed graph

b)

Contains no cycles

c)

Planar

d)

Completely connected

27.

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

a)

Simple graph

b)

Multi graph

c)

Regular graph

d)

Complete graph

28.

Which of following data structure is more appropriate for

implementing quick sort iteratively?

a)

Deque

b)

Priority queue

c)

Stack

d)

Queue

29.

If two trees have same structure and node content, then they are

called __

a)

Equivalent trees

b)

Synonyms trees

c)

Similar trees

d)

Joint trees

30.

Which of the following is not the type of queue?

a)

Ordinary queue

b)

Single and queue

c)

Circular queue

d)

Priority queue

31.

Finding the location of a given item in a collection of items is called ……

a)

Discovering

b)

Mining

c)

Finding

d)

Searching

32.

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

33.

What is the worst case time complexity of merge sort?

a)

O(n log n)

b)

O(n²)

c)

O(n² log n)

d)

O(n log n²)

34.

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

35.

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

36.

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

a)

barchart

b)

Graph

c)

Pie chart

d)

Flowchart

37.

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

38.

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

39.

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

40.

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

41.

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

a)

Big-oh

b)

Big-Omega

c)

little-Theta

d)

little-oh

e)

theta

42.

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)

43.

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)

44.

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)

45.

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

a)

Input

b)

infiniteness

c)

Effectiveness

d)

output

e)

finiteness

46.

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

47.

The worst case running time of shell sort, using Shell’s increments is?

a)

O(N)

b)

O(N log N)

c)

O(log N)

d)

O(N²)

48.

On how many increment sequences does the worst case analysis of shell sort depends?

a)

1

b)

2

c)

3

d)

4

49.

Shell sort is an improvement on ____

a)

insertion sort

b)

selection sort

c)

binary tree sort

d)

quick sort

50.

On which algorithm is heap sort based on?

a)

Fibonacci heap

b)

Binary tree

c)

Priority queue

d)

FIFO

51.

In what position does the array for heap sort contains data?

a)

0

b)

1

c)

-1

d)

Anywhere

52.

Is there any difference in the speed of execution between linear serach(recursive) vs linear search(lterative)?

a)

Both execute at same speed

b)

Linear search(recursive) is faster

c)

Linear search(Iterative) is faster

d)

Cant be said

53.

Is the space consumed by the linear search(recursive) and linear search(iterative) same?

a)

No, recursive algorithm consumes more space

b)

No, recursive algorithm consumes less space

c)

Yes

d)

Nothing can be said

54.

Linear search(recursive) algorithm used in _____________

a)

When the size of the dataset is low

b)

When the size of the dataset is large

c)

When the dataset is unordered

d)

Never used

55.

The array is as follows: 1,2,3,6,8,10. At what time the element 6 is found? (By using linear search(recursive) algorithm)

a)

3rd call

b)

4th call

c)

6th call

d)

5th call

56.

What is the advantage of recursive approach than an iterative approach?

a)

Consumes less memory

b)

Less code and easy to implement

c)

Consumes more memory

d)

More code has to be written

57.

Which of the following is not an application of binary search?

a)

To find the lower/upper bound in an ordered sequence

b)

Union of intervals

c)

Debugging

d)

To search in unordered list

58.

Binary Search can be categorized into which of the following?

a)

Brute Force technique

b)

Divide and conquer

c)

Greedy algorithm

d)

Dynamic programming

59.

Which of the following method is used for sorting in merge sort?

a)

merging

b)

partitioning

c)

selection

d)

exchanging

60.

Which of the following is not a variant of merge sort?

a)

in-place merge sort

b)

bottom up merge sort

c)

top down merge sort

d)

linear merge sort

61.

Which type of sort algorithm is this?

a)

Insertion

b)

Bubble

c)

Merge

62.

is a recursive algorithm that continually splits a list in half. If the list is empty or has one item, it is sorted by definition (the base case).

a)

Shell Sort

b)

Merge Sort

c)

Quick Sort

63.

Can we divide problem into more than 2 sub problems?

a)

Yes

b)

No

64.

In a stack, if a user tries to remove an element from empty stack it is called _________

a)

Underflow

b)

Empty collection

c)

Overflow

d)

Garbage Collection

65.

Process of inserting an element in stack is called ____________

a)

Create

b)

Push

c)

Evaluation

d)

Pop

66.

Consider the usual algorithm for determining whether a sequence of parentheses is balanced.

Suppose that you run the algorithm on a sequence that contains 2 left parentheses and 3 right parentheses (in some order).

The maximum number of parentheses that appear on the stack AT ANY ONE TIME during the computation?

a)

1

b)

2

c)

3

d)

4 or more

67.

User perform following operations on stack of size 5 then -

push(1);

pop();

push(2);

push(3);

pop();

push(2);

pop();

push(4);

pop();

push(5);

a)

Overflow Occurs

b)

Stack Operations will be performed Smoothly

c)

Underflow Occurs

d)

None of these

68.

What is the value of the postfix expression 6 3 2 4 + – *

a)

1

b)

40

c)

74

d)

-18

69.

To evaluate an expression without any embedded function calls:

a)

One stack is enough

b)

Two stacks are needed

c)

As many stacks as the height of the expression tree are needed

d)

A Turing machine is needed in the general case

70.

Which one of the following is an application of Stack Data Structure?

a)

Managing function calls

b)

The stock span problem

c)

Arithmetic expression evaluation

d)

All of the above

DAA Tutorial-1

Total questions: 70

Worksheet time: 36mins

Similar Resources on Wayground