A directory of Objective Type Questions covering all the Computer Science subjects. Here you can access and discuss Multiple choice questions and answers for various compitative exams and interviews.

91. A graph G = (V, E) satisfies |E| ≤ 3 |V| - 6. The min-degree of G is defined as follows. Therefore, min-degree of G cannot be
min-degree of a graph
a. 3
b. 4
c. 5
d. 6
View Answer Report Discuss Too Difficult! Search Google
Answer: (d).6

92. Consider the following system of linear equations Notice that the second and the third columns of the coefficient matrix are linearly dependent. For how many values of a, does this system of equations have infinitely many solutions?
coefficient matrix are linearly dependent
a. 0
b. 1
c. 2
d. infinitely many
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).1

93. A piecewise linear function f(x) is plotted using thick solid lines in the figure below (the plot is drawn to scale). If we use the Newton-Raphson method to find the roots of f(x) = 0 using x0, x1 and x2 respectively as initial guesses, the roots obtained would be
Newton-Raphson method
a. 1.3, 0.6, and 0.6 respectively
b. 0.6, 0.6, and 1.3 respectively
c. 1.3, 1.3, and 0.6 respectively
d. 1.3, 0.6, and 1.3 respectively
View Answer Report Discuss Too Difficult! Search Google
Answer: (d).1.3, 0.6, and 1.3 respectively

94. Consider two languages L1 and L2 each on the alphabet ∑. Let f : ∑ → ∑ be a polynomial time computable bijection such that (∀ x) [x ∈ L1 iff f(x) ∈ L2]. Further, let f^-1 be also polynomial time computable. Which of the following CANNOT be true?
a. L1 ∈ P and L2 is finite
b. L1 ∈ NP and L2 ∈ P
c. L1 is undecidable and L2 is decidable
d. L1 is recursively enumerable and L2 is recursive
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).L1 is undecidable and L2 is decidable

95. In a permutation a1.....an of n distinct integers, an inversion is a pair (ai, aj) such that i < j and ai > aj. If all permutations are equally likely, what is the expected number of inversions in a randomly chosen permutation of 1.....n ?
a. n(n - 1)/2
b. n(n - 1)/4
c. n(n + 1)/4
d. 2n[log2 n]
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).n(n - 1)/4

96. In a permutation a1.....an of n distinct integers, an inversion is a pair (ai, aj) such that i < j and ai > aj. What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to permutations of 1.....n with at most n inversions?
a. Θ (n^2)
b. Θ (n log n)
c. Θ (n^1.5)
d. Θ (n)
View Answer Report Discuss Too Difficult! Search Google
Answer: (d).Θ (n)

97. The cube root of a natural number n is defined as the largest natural number m such that m^3 ≤ n. The complexity of computing the cube root of n (n is represented in binary notation) is:
a. O(n) but not O(n^0.5)
b. O(n^0.5) but not O((log n)^k) for any constant k > 0
c. O((log n)^k) for some constant k > 0, but not O ((log log n)^m) for any constant m > 0
d. O((log log n)^m) for some constant k > 0.5, but not O((log log n)^0.5)
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).O((log n)^k) for some constant k > 0, but not O ((log log n)^m) for any constant m > 0

98. Let G = (V, E) be an undirected graph with a subgraph G1 = (V1, El). Weights are assigned to edges of G as follows :
A single-source shortest path algorithm is executed on the weighted graph (V, E, w) with an arbitrary vertex ν1 of V1 as the source. Which of the following can always be inferred from the path costs computed?
undirected graph
a. The number of edges in the shortest paths from ν1 to all vertices of G
b. G1 is connected
c. V1 forms a clique in G
d. G1 is a tree
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).G1 is connected

99. Consider the following logic program P A(x) <- B(x, y), C(y) <- B(x,x) Which of the following first order sentences is equivalent to P?
Propositional and First Order Logic
a. A
b. B
c. C
d. D
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).C

100. The following resolution rule is used in logic programming:

Derive clause (P v Q) from clauses (P v R), (Q v ¬ R)

Which of the following statements related to this rule is FALSE?
a. ((P v R) ^ (Q v ¬ R)) (P v Q) is logically valid
b. (P v Q) ⇒ ((P v R) ^ (Q v ¬ R)) is logically valid
c. (P v Q) is satisfiable if and only if (P v R) ^ (Q v ¬ R) is satisfiable
d. (P v Q) ⇒ FALSE if and only if both P and Q are unsatisfiable
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).(P v Q) ⇒ ((P v R) ^ (Q v ¬ R)) is logically valid

Page 10 of 23