Data Structure and Algorithm Analysis
Questions 81 to 90
81.

A
"queue" is also known as what?


82.

A
"linked list" always contains elements that can be described as


83.

In tree
construction, which is the suitable and efficient data structure?


84.

The
following are the statements regarding the NP problems. Chose the right option from the following
options:
I. All NPcomplete problems are not NPhard.
II. Some NPhard problems are not known to be
NPcomplete.


85.

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


86.

The time
complexity of the shortest path algorithm can be bounded by


87.

Read the
following statements carefully and pick the correct option:
I. The worst time complexity of the Floyd’s
algorithm is O(n^{3}).
II. The worst time complexity of the
Warshall’s algorithm is O(n^{3}).


88.

The
asymptotic notation for defining the average time complexity is


89.

The
suitable data structure to represent the IDs of employees is


90.

The
number of nodes a null tree can have is

Answers
81.

Answer : (a)
Reason : As the Stack behaves in Last In First Out manner.

82.

Answer : (e)
Reason : There should be a self referential structure in linked list so as
to point to the other node in the link list. The other options are wrong.

83.

Answer : (b)
Reason : If a linked list is used then a node can hold the address of both
the left child and right child. Stack, Queue and Graph can never be used.
Arrays can also be used but careful indexing is required to be done and hence
is not a valid data structure.

84.

Answer : (d)
Reason : According to the theory of NPcomplete and NPhard problems.

85.

Answer : (e)
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}).

86.

Answer : (c)
Reason : As the algorithm contains three ‘for loops’ nested together
running from 1 to ‘n’ and hence the total time is O(n^{3}).

87.

Answer : (c)
Reason : As the both the algorithms contains three ‘for loops’ nested
together running from 1 to ‘n’ and hence the total time is O(n^{3})
for both the algorithms.

88.

Answer : (a)
Reason : This is a theta notation which is Reflexive, Symmetric and
Transitive and hence it is an Equivalence relation.

89.

Answer : (d)
Reason : As the type of all Id for all the employees is same then a simple
array is enough to store the values.

90.

Answer : (d)
Reason : As a null tree is a valid tree with zero number of nodes.

No comments :
Post a Comment