Data Structure and Algorithm Analysis Set 6

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 :

What you think about these Questions and Answers ? Let me know in comments.

Post a Comment