 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 a. 3 b. 4 c. 5 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? a. 0 b. 1 c. 2 d. infinitely many

 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 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

 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

 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]

 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)

 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? 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
 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? a. A b. B c. C d. D