Algorithm Analysis and Design Quiz Answers

Question:- The running time of Dijkastra’s algorithm is
(A) O(V²)          

(B) O(V+E)       

(C) O(n log n)              

(D) all of the above

Question:-  kruskal’s algorithm uses-------- and prim’s algorithm uses------ in determining the MST
(A) edges,vertex          

(B)vertex,edges           

(C)edges,edges           

(D)vertex,vertex

Question:- The running time of kruskal’s algorithm for MST
(A) O(E)           

(B) O(V)           

(C) O(E log V)              

(D) all of the above

Question:- We can perform a topological sort in time -----------, since DFS takes ------ time.
(A) ϴ (V+E), ϴ (E)        

(B) ϴ (E), ϴ (V+E)
(C) ϴ (V+E), ϴ (V+E)   

(D) all of the above

Question:-  The running time of BFS is------------
(A)  ϴ (1)         

(B) ϴ (n log n)             

(C) O(V+E)       

(D) ϴ (n²)

Question:-  For------ insertion sort beats merge sort
(A) n≥43          

(B) n≤23          

(C) n≤43         

 (D) cannot say

Question:- Best case running time of quick sort is

(A)  O(n)                               

(B) O(logn)                         

(C) O(nlogn )                            

(D) O(n²)

Question:-   A characteristic of the data that binary search tree but the linear search ignores, is the

(A) Order of the list                            (B) length of the list   

(C) maximum value in the list                        (D) mean of data values

Question:-  A sort which compares adjacent elements in a list and switches where necessary is a

(A) insertion sort                     

(B) heap sort

(C) quick sort                           

(D) bubble sort

Question:-  A sort which iteratively passes through a list  to exchange the first element with any element less than it and then repeats with a new first element is called

(A) Insertion sort         

(B) selection sort

(C) Heap sort               

(D) quick sort

Question:-  A sort which uses the binary tree concept such that any number is larger than all the numbers is the subtree below it is called

(A) Selection sort        

(B) insertion sort         

(C) quick sort               

(D) heap sort

Question:-  which of the sorting algorithm does not have a worst case running time of O(n²)

(A) Selection sort        

(B) insertion sort         

(C) merge sort            

(D) quick sort

Question:-  which of the following sorting method is stable?

(A) Straight insertion sort                   

(B) binary search tree

(C) Shell sort                                       

(D) Heap sort

Question:-   A complete binary tree with the property that the value at each node is at least as large as the values at its children is known as

(A) Binary search tree                        

(B) AVL tree

(C) Completely balanced tree            

(D) Heap

Question:-  The recurrence relation T(n) = mT(n/2)+ an² is satisfied by

(A) T (n) = O(n^m)          

(B) T(n) = O(n log m)              

(C) T(n) = O( n log n)   

(D) T(n) =O(m log n)

Question:- The time required to find shortest path in a graph with n vertices and e edges is

(A) O (e)          

(B) O (n)          

(C) O (e²)                     

(D) O (n²)

Question:- The goal of hashing is to produce a search tree that takes

(A) O(1) time               

(B) O(n²) time             

(C) O (log n) time                    

(D) O (n log n) time

Question:-  which of the following best described sorting?

(A) Accessing and processing each record exactly once

(B) Finding the location of the record with a given key

(C) Arranging the data in some given order

(D) Adding a new record to the data structure

Question:-  The worst case complexity of straight insertion sort algorithm to sort n elements is

(A) O(n)           

(B) O(n log n)              

(C) O(n^1.2)                    

(D) O(n²)

Question:-  The worst case complexity of binary insertion sort algorithm to sort in n elements is

(A) O(n)           
(B) O(n log n)              
(C) O(n^1.2)                    
(D) O(n²)

• Twitter
• Facebook
• Google
• Tumblr
• Pinterest