31. An all-pairs shortest-paths problem is efficiently solved using:
(A) Dijkstra’ algorithm (B) Bellman-Ford algorithm
(C) Kruskal Algorithm (D) Floyd-Warshall algorithm
Answer: D
32. The travelling salesman problem can be solved in:
(A) Polynomial time using dynamic programming algorithm
(B) Polynomial time using branch-and-bound algorithm
(C) Exponential time using dynamic programming algorithm or branch-and-bound algorithm.
(D) Polynomial time using backtracking algorithm.
Answer: C
33. Which of the following is asymptotically smaller?
(A) lg(lg*n) (B) lg*(lg n)
(C) lg(n!) (D) lg*(n!)
Answer: A
34. Consider a hash table of size m=100 and the hash function h(k) = floor(m(kA mod 1)) for A = (√5 − 1)/2 = 0.618033. Compute the location to which the key k = 123456 is placed in hash table.
(A) 77 (B) 82
(C) 88 (D) 89
Answer: C
Explanation:
h(k) = ↳m(kA mod 1),
A=(√5 − 1)/2=0.618033.
given K = 123456, m=100.
h(k) = 100(123456 x 0.618033 mod 1) = 100(76299.88204 mod 1)
= 100 x 0.882048
= 88.2048 =88
35. Let f(n) and g(n) be asymptotically non-negative functions. Which of the following is correct?
(A) θ(f(n) * g(n)) = min(f(n), g(n))
(B) θ(f(n) * g(n)) = max(f(n), g(n))
(C) θ(f(n) + g(n)) = min(f(n), g(n))
(D) θ(f(n) + g(n)) = max(f(n), g(n))
Answer: D
36. The number of nodes of height h in any n – element heap is …………..
(A) h (B) zh
(C) ceil(n/zh) (D) ceil(n/zh+1)
Answer: D
37. In Java, when we implement an interface method, it must be declared as:
(A) Private (B) Protected
(C) Public (D) Friend
Answer: C
38. The Servlet Response interface enables a servlet to formulate a response for a client using the method ……………
(A) void log(Exception e, String s)
(B) void destroy()
(C) int getServerPort()
(D) void setContextType(String Type)
Answer: D
39. Which one of the following is correct?
(A) Java applets cannot be written in any programming language
(B) An applet is not a small program.
(C) An applet can be run on its own.
(D) Applets are embedded in another applications.
Answer: D
40. In XML we can specify the frequency of an element by using the symbols:
(A) + * ! (B) # * !
(C) + * ? (D) – * ?
Answer: C
Explanation.
+ symbol for one or more time.
* for 0 or more time.
? for zero or more time.
41. In XML, DOCTYPE declaration specifies to include a reference to ………… file.
(A) Document Type Definition (B) Document Type Declaration
(C) Document Transfer Definition (D) Document Type language
Answer: A
42. Module design is used to maximize cohesion and minimize coupling. Which of the following is the key to implement this rule?
(A) Inheritance (B) Polymorphism
(C) Encapsulation (D) Abstraction
Answer: C
Explanation.
The basic idea underlying modular design is to organize a complex system (such as a large program, an electronic circuit, or a mechanical device) as a set of distinct components that can be developed independently and then plugged together. Although this may appear a simple idea, experience shows that the effectiveness of the technique depends critically on the manner in which systems are divided into components and the mechanisms used to plug components together. The following design principles are particularly relevant to parallel programming. Ensure that modules hide information.
- related functions that can benefit from a common implementation or that are used in many parts of a system,
- functionality that is likely to change during later design or deployment,
- aspects of a problem that are particularly complex, and/or
- code that is expected to be reused in other programs.
The benefits of modularity do not follow automatically from the act of subdividing a program. The way in which a program is decomposed can make an enormous difference to how easily the program can be implemented and modified. Experience shows that each module should encapsulate information that is not available to the rest of a program. This information hiding reduces the cost of subsequent design changes.
43. Verification:
(A) refers to the set of activities that ensure that software correctly implements a specific function.
(B) gives answer to the question – Are we building the product right ?
(C) requires execution of software
(D) both (A) and (B)
Answer: D
44. Which design metric is used to measure the compactness of the program in terms of lines of code?
(A) Consistency (B) Conciseness
(C) Efficiency (D) Accuracy
Answer: B