Data Structure and Algorithm Analysis
Questions 51 to 60
51.
|
The
Knapsack problem where the objective function is to minimize the profit is
______
(a) Greedy (b) Dynamic 0 / 1 (c) Back
tracking
(d) Branch & Bound 0/1 (e)
NP Knapsack.
|
52.
|
I have
implemented the queue with a linked list, keeping track of a front node and a
rear node with two reference variables. Which of these reference variables
will change during an insertion into a NONEMPTY queue?
(a) Neither
changes (b) Only front
changes (c) Only rear
changes
(d) Both
change (e) (a) or (d) above.
|
53.
|
For the
given 5 jobs with penalties 6,3,4,8,5 respectively, the static state space
tree is generated, then if the first job is selected but not the second job
for the first two jobs consideration, then the rank of such situational node
is ______
(a) 6 (b) 3 (c) 0 (d) 9 (e)
20.
|
54.
|
Which of
the following statements is/are TRUE?
i) ADTs
define how data is stored and manipulated.
ii)
Every linked list has to have at
least one external pointer.
iii)
Recursive solutions may be easier to
understand.
(a) (i),(ii) and (iii) above (b) Only (i) above
(c) Only (ii) above (d) Only (iii)above
(e) Only (ii) and (iii) above.
|
55.
|
Choose
the correct answer for the following statements:
I. The theory of NP–completeness provides a
method of obtaining a polynomial time for NPalgorithms.
II. All NP-complete problem are NP-Hard.
(a) I is FALSE and II is TRUE
(b) I is TRUE and II is FALSE
(c) Both are TRUE
(d) Both are FALSE
(e) II is TRUE, I can’t be determined.
|
56.
|
Having
the address of the node to be deleted in doubly linked list, the node can be
deleted
(a) Without traversing the list
(b) Only after traversing the list from the
head
(c) Only after traversing the list from the
tail
(d) (b) or (c) above
(e) Can’t be deleted.
|
57.
|
The
Hamiltonian cycles problem uses the following line of code to generate a next
vertex, provided x[ ] is a global array and kth vertex is under
consideration:
(a) x[k] ¬ (x[k] + 1) mod n (b) x[k] ¬ (x[k]) mod (n)
(c) x[k] ¬ (x[k] + 1) mod (n+1) (d) x[k] ¬ x[k+1] mod n
(e) x[k] ¬ x[k+1] mod (n + 1)
|
58.
|
Suppose
cursor refers to a node in a linked list, what statement changes cursor so
that it refers to the next node?
(a) cursor++;
(b) cursor = link;
(c) cursor += link;
(d) cursor = cursor->link;
(e) (a) and (c) above.
(Note:
struct cursor {
int
data;
struct cursor *link;
};
|
59.
|
The graph
coloring algorithm’s time can be bounded by _________
(a) O(mnm) (b) O(nm) (c) O(nm. 2n) (d)
O(mn.2n) (e)
O(nmn).
|
60.
|
For 0/1
KNAPSACK problem, the algorithm takes ________ amount of time for memory
table, and ______time to determine the optimal load, for N objects and W as
the capacity of KNAPSACK.
(a) O(N+W), O(NW) (b) q(NW), O(N+W)
(c) O(N), O(NW) (d)
O(NW), O(N) (e) O(N+W), O(N+W).
|
Answers
51.
|
Answer : (d)
Reason : As there for the generation of the state
space tree we use minimization Of the profit.
|
52.
|
Answer : (c)
Reason : As the queue is non empty and there is rear
pointer pointing, this only must be incremented.
|
53.
|
Answer : (b)
Reason : As we have considered first two jobs and have
not considered the second job so we have to pay the penalty of second job.
|
54.
|
Answer : (c)
Reason : As the other two options are not true and
correct.
|
55.
|
Answer : (a)
Reason : Because the theory of NP does not provides a
way to obtain a polynomial time for NP algorithms. Hence the I statement is
wrong while the II statement is correct.
|
56.
|
Answer : (a)
Reason : That is the advantage of doubly linked list.
No need to traverse if the address of the desired node is provided.
|
57.
|
Answer : (c)
Reason : As to find the next node to be traversed this
is the formula.
|
58.
|
Answer : (d)
Reason : All the other options are invalid operations.
|
59.
|
Answer : (e)
Reason : As all the n nodes are required to be
colored, and there are mn ways of coloring a specific node.
|
60.
|
Answer : (b)
Reason : As the memory table ( 2 –D matrix ) contains
N rows and W columns, hence it is NW, and for the composition of the optimal
load it is up to N+W time it takes.
|
No comments :
Post a Comment