# Data Structure and Algorithm Analysis Set 9

## Data Structure and Algorithm Analysis

### Questions 81 to 90

81.
A "queue" is also known as what?
 (a) A FIFO (b) A stack (c) A LIFO (d) A Linked List (e) A FOFI.
82.
A "linked list" always contains elements that can be described as
 (a) Redundant (b) Recursive (c) Sentinel (d) Bidirectional (e) Self-referential.
83.
In tree construction, which is the suitable and efficient data structure?
 (a) Array (b) Linked list (c) Stack (d) Queue (e) Graph.
84.
The following are the statements regarding the NP problems. Chose the right option from the following options:
I.     All NP-complete problems are not NP-hard.
II.     Some NP-hard problems are not known to be NP-complete.
 (a) Both (I) and (II) are true (b) Both (I) and (II) are false (c) Only (I) is true (d) Only (II) is true (e) (I) is true but (II) is not always true.
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
 (a) O(nm) (b) O(n+m) (c) O(mnm) (d) O(nm) (e) O(nmn).
86.
The time complexity of the shortest path algorithm can be bounded by
 (a) O(n2) (b) O(n4) (c) O(n3) (d) O(n) (e) O(n log n ).
87.
Read the following statements carefully and pick the correct option:
I.     The worst time complexity of the Floyd’s algorithm is O(n3).
II.     The worst time complexity of the Warshall’s algorithm is O(n3).
 (a) (I) is false but (II) is true (b) (I) is true but (II) is false (c) Both (I) and (II) are true (d) (I) is true and (II) is not true always (e) Both (I) and (II) are false.
88.
The asymptotic notation for defining the average time complexity is
 (a) Equivalence (b) Symmetric (c) Reflexive (d) Transitive (e) Both (c) and (d) above.
89.
The suitable data structure to represent the IDs of employees is
 (a) Stack (b) Queue (c) Linked List (d) Array (e) Tree.
90.
The number of nodes a null tree can have is
 (a) One (b) Two (c) Three (d) Zero (e) Null tree is invalid tree.