# Data Structure and Algorithm Analysis Set 21

## Data Structure and Algorithm Analysis

### Questions 201 to 210

201.
The time taken by NP-class sorting algorithm is
 (a) O(1) (b) O(log n) (c) O(n2) (d) O(n log n) (e) O(n).
202.
For the functions f, g : N –> R  for all n,   f(n) = n and g(n) = n log n then
 (a) f(n) Ï( g(n)), but g(n) ( f(n)) (b) f(n) ( g(n)), but g(n) Ï( f(n)) (c) g(n) ( f(n)), but f(n) Ï( g(n)) (d) f(n) ( g(n)), and g(n) ( f(n)) (e) f(n) ( g(n)), but f(n) Ï( g(n)).
203.
What is the type of the algorithm used in solving the 8 Queens problem?
 (a) Greedy (b) Dynamic (c) Branch and Bound (d) Divide and Conquer (e) Backtracking.
204.
Let G be a graph with ‘n’ nodes and let ‘m’ be the chromatic number of the graph. Then the time taken by the backtracking algorithm to color it is
 (a) O(nmn) (b) O(n+m) (c) O(mnm) (d) O(nm) (e) O(nm).
205.
What is the major data structure used in the Network data model?
 (a) Stack (b) Array (c) Graph (d) Tree (e) Queue.
206.
Minimum number of queue(s) needed to implement the priority queue is(are)
 (a) Four (b) Three (c) Two (d) One (e) Depends upon the application.
207.
Sorting is not possible by using which of the following methods?
 (a) Insertion (b) Selection (c) Exchange (d) Deletion (e) Partitioning.
208.
The number of null branches for a binary tree with 20 nodes is
 (a) 21 (b) 20 (c) 22 (d) 19 (e) 18
209.
The time complexity of binary search in best, worst cases for the array of size N is
 (a) N, N2 (b) ­­­N, N (c) 1, logN (d) 1, NlogN (e) logN, N2.
210.
A desired key in a table is searched, starting itself from hash address, sequentially for the following.
 (a) Quadratic probing (b) Linear probing (c) Random probing (d) Chaining (e) Reverse probing.

#### Answers

 201 Answer : (e) Reason  :       Here only one loop from one to n is there. And hence it runs for ‘n’ times only 202 Answer : (a) Reason  :       According to the limit rules for big Oh notation 203 Answer : (e) Reason  :       As the other types of algorithms are not suitable to find the solution for the given problem. 204 Answer : (a) Reason  :       As the number of internal nodes in the state space tree are mn, and O(mn) is the time spent by the NextValue algorithm to determine the children corresponding to legal colorings. Hence the total time is bounded by O(nmn). 205 Answer : (c) Reason  :       As the graph is the suitable data structure to represent the connectivity between the nodes as edges. 206 Answer : (c) Reason  :       Two : One queue is used for actual storing of data and another for storing priorities. 207 Answer : (d) Reason  :       There is no sorting algorithm available where we delete an element. Using insertion we can perform insertion sort, using selection we can perform selection sort, using exchange we can perform the bubble sort (and other similar sorting methods) and using the portioning we can perform merge sort(and other similar sorting methods) But no sorting method can be done just using deletion. 208 Answer : (a) Reason  :       For ‘n’ nodes there are always ‘n+1’ null branches in a binary tree. 209 Answer : (c) Reason  :       In best case if the required element is at the middle then it takes O( 1 ) time other wise it takes O( log n ) time in worst case. 210 Answer : (b) Reason  :       According to opening addressing techniques, the linear probing starts probing from the hash address and it continues sequentially in a linear manner.

<< PrevNext >>

#### No comments :

What you think about these Questions and Answers ? Let me know in comments.