Daily 10 Questions(12-07-2012)
1. Let S be a set of n elements. The number of ordered pairs in the largest and the
smallest equivalence relations on S are:
2. What is the maximum number of different Boolean functions involving n Boolean
variables?
3. Let G be the non-planar graph with the minimum possible number of edges. Then
G has
(A) 9 edges and 5 vertices (B) 9 edges and 6 vertices
(C) 10 edges and 5 vertices (D) 10 edges and 6 vertices
4. Consider the DAG with V = {1,2,3,4,5,6}, shown below.
Which of the following is NOT a topological ordering?
(A) 1 2 3 4 5 6 (B) 1 3 2 4 5 6 (C) 1 3 2 4 6 5 (D) 3 2 4 1 6 5
5. Which of the following problems is undecidable?
(A) Membership problem for CFGs. (B) Ambiguity problem for CFGs.
(C) Finiteness problem for FSAs. (D) Equivalence problem for FSAs.
6. Which of the following is TRUE?
(A) Every subset of a regular set is regular.
(B) Every finite subset of a non-regular set is regular.
(C) The union of two non-regular sets is not regular.
(D) Infinite union of finite sets is regular.
7. Consider the following Boolean function of four variables:
f (w,x,y ,z ) = (1,3,4,6,9,11,12,14)
The function is:
(A) independent of one variables. (B) independent of two variables.
(C) independent of three variables. (D) dependent on all the variables.
8. The height of a binary tree is the maximum number of edges in any root to leaf
path. The maximum number of nodes in a binary tree of height h is:
9. The maximum number of binary trees that can be formed with three unlabeled
nodes is:
(A) 1 (B) 5 (C) 4 (D) 3
10. Which of the following sorting algorithms has the lowest worst-case complexity?
(A) Merge sort (B) Bubble sort (C) Quick sort (D) Selection sort
1. Let S be a set of n elements. The number of ordered pairs in the largest and the
smallest equivalence relations on S are:
2. What is the maximum number of different Boolean functions involving n Boolean
variables?
3. Let G be the non-planar graph with the minimum possible number of edges. Then
G has
(A) 9 edges and 5 vertices (B) 9 edges and 6 vertices
(C) 10 edges and 5 vertices (D) 10 edges and 6 vertices
4. Consider the DAG with V = {1,2,3,4,5,6}, shown below.
Which of the following is NOT a topological ordering?
(A) 1 2 3 4 5 6 (B) 1 3 2 4 5 6 (C) 1 3 2 4 6 5 (D) 3 2 4 1 6 5
5. Which of the following problems is undecidable?
(A) Membership problem for CFGs. (B) Ambiguity problem for CFGs.
(C) Finiteness problem for FSAs. (D) Equivalence problem for FSAs.
6. Which of the following is TRUE?
(A) Every subset of a regular set is regular.
(B) Every finite subset of a non-regular set is regular.
(C) The union of two non-regular sets is not regular.
(D) Infinite union of finite sets is regular.
7. Consider the following Boolean function of four variables:
f (w,x,y ,z ) = (1,3,4,6,9,11,12,14)
The function is:
(A) independent of one variables. (B) independent of two variables.
(C) independent of three variables. (D) dependent on all the variables.
8. The height of a binary tree is the maximum number of edges in any root to leaf
path. The maximum number of nodes in a binary tree of height h is:
9. The maximum number of binary trees that can be formed with three unlabeled
nodes is:
(A) 1 (B) 5 (C) 4 (D) 3
10. Which of the following sorting algorithms has the lowest worst-case complexity?
(A) Merge sort (B) Bubble sort (C) Quick sort (D) Selection sort
Answer (A)
ReplyDeleteWorst case complexities for the above sorting algorithms are as follows:
Merge Sort — nLogn
Bubble Sort — n^2
Quick Sort — n^2
Selection Sort — n^2