Advanced Database Management System - Tutorials and Notes: Questions and answers in Data Structures and Algorithms 02

Saturday, 25 April 2020

Questions and answers in Data Structures and Algorithms 02

TRUE/FALSE Quiz Questions with Answers in time complexities Data Structures and Algorithms


Data Structures and Algorithms TRUE / FALSE Questions – Set 02



1. O(1), O(n), O(nlog n), O(n2) is the correct ascending order of time complexities (low to high time complexities)

(a) TRUE                                                   (b) FALSE

Answer: TRUE

Time complexity is one of the measures to calculate the performance of an algorithm or program.

O(1) is constant time. It takes constant amount of time. For example, to access any particular element in an array of any size would take same amount of time).
O(n) denotes linear time. Here, the running time grows linearly with the size of input. For example, time required to sum n numbers grows along with n.
O(n log n) denotes linearithmic time.
O(n2) is quadratic time. For example, bubble sort algorithm takes quadratic time to sort the elements.

2. Let f(n) = 2n2 + 5n +12. Then f(n) is O(2n).
(a) TRUE                                                   (b) FALSE

Answer: TRUE
Let us assume f(n) = 2n2 + 5n +12 and g(n) = 2n. Assuming n>1 then
f(n)/g(n) = (2n2 + 5n +12)/ 2n < (2(2n)+5(2n)+12(2n))/2n = 19(2n)/2n = 19.
Choose C = 19. Thus, 2n2 + 5n +12 ≤ 19*2n whenever n>1.


3. Queue and Stack are the linear data structures

(a) TRUE                                                   (b) FALSE

Answer: TRUE
The data structure where data items are organized sequentially or linearly where data elements attached one after another is called linear data structure. In linear data structure, each element can be traversed one after the other.
Queue is FIFO, where the first element that enters the queue will be accessed first then the next, and so on. Stack is LIFO, where the last element inserted will be accessed first then the next last and so on. In both of these cases, elements are accessed one after the other in a linear or sequential order.

Other linear data structures are array and linked list.


4. Average case running time of Bubble sort is O(n log n).
(a) TRUE                                                   (b) FALSE

Answer: FALSE

Average case running time of bubble sort is O(n2).

Bubble sort compares the adjacent elements in a list and swap them if they are in a wrong order in its first pass. It does this continuously in consequent passes until the all the elements in the list gets sorted.

5. O(n2) ≥ O(2n/4) is true for any value of n.
(a) TRUE                                                   (b) FALSE

Answer: FALSE
The given comparison is not always true. For certain values of n it is true; for others it is not.
If n ≤ 8, then it is true. For other values of n (n > 8), O(2n/4) is larger.

6. The tightest bound time complexity of function T(N) = T(N/2) + 100 is O(N)
(a) TRUE                                                   (b) FALSE

Answer: FALSE
The tightest bound time complexity for the given function is O(log N). This is less complex than O(N).


7. Queue is the suitable data structure for the application that tracks the customer orders in an ice cream parlor.

(a) TRUE                                                   (b) FALSE

Answer: TRUE
Customers orders should be handled in a First In First Out (FIFO) manner.


8. A complete binary tree with a height of h can have more nodes than a full binary tree with a height of h.

(a) TRUE                                                   (b) FALSE

Answer: FALSE
A complete binary tree with a height of h have 2h−1 to 2h − 1 nodes.
A complete binary tree with a height of h have 2h − 1 nodes.

9. O(1) is the worst case time complexity of dequeue in a queue containing M elements implemented using an array.
(a) TRUE                                                   (b) FALSE

Answer: TRUE
Dequeue is an operation that get the elements out of a queue. This operation can be done on the element that is currently at the front of the queue. Hence, the complexity is O(1).

10. If we have two algorithms A1 and A2, and A1 takes time O(N) while A2 is O(N3), then A1 always runs faster than A2, for any input.
(a) TRUE                                                   (b) FALSE

Answer: FALSE
For very large N, A1 will be faster than A2, but perhaps not for smaller N.


***********

Interview questions and answers in data structure and algorithms

DSA quiz questions with answers explained

Solved true or false questions in DSA

Practice questions in data structures

TRUE  or FALSE questions in data structures and algorithms



 
 

No comments:

Post a comment

Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

All time most popular contents