Data Structure and Algorithm Analysis
Questions 201 to 210
201.

The time
taken by NPclass sorting algorithm is


For the
functions f, g : N –> R^{}
for all n, f(n) = n and
g(n) = n log n then


What is the
type of the algorithm used in solving the 8 Queens problem?


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


What is the
major data structure used in the Network data model?


Minimum
number of queue(s) needed to implement the priority queue is(are)


Sorting is
not possible by using which of the following methods?


The number
of null branches for a binary tree with 20 nodes is


The time
complexity of binary search in best, worst cases for the array of size N is


A desired
key in a table is searched, starting itself from hash address, sequentially
for the following.

Answers
201.

Answer : (e)
Reason : Here
only one loop from one to n is there. And hence it runs for ‘n’ times only

Answer : (a)
Reason : According
to the limit rules for big Oh notation


Answer : (e)
Reason : As
the other types of algorithms are not suitable to find the solution for the
given problem.


Answer : (a)
Reason : As
the number of internal nodes in the state space tree are m^{n}, 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(nm^{n}).


Answer : (c)
Reason : As
the graph is the suitable data structure to represent the connectivity
between the nodes as edges.


Answer : (c)
Reason : Two
: One queue is used for actual storing of data and another for storing
priorities.


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.


Answer : (a)
Reason : For
‘n’ nodes there are always ‘n+1’ null branches in a binary tree.


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.


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.

No comments :
Post a Comment