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.





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 NP-complete and NP-hard problems.
85.
Answer : (e)
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).
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(n3).
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(n3) 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.



Writed by
Labels: , , , , , , , , , , ,

1 comment :

  1. UnknownMarch 11, 2017 at 6:30 AM

    the question 81 answer is wrong, please correct it, thanks

    ReplyDelete

Subscribe to: Post Comments ( Atom )