Quiz on Theory of Computation

1.   Which string is not accepted by the following FSA?

                               

      a. 00110                b. 01010                      c. 11010                                           d. 00111

2.   Consider the following language L = {aⁿbⁿ|n ≥ 1} then  L is

      a.  regular              b. CSL but not CFL                c.  CFL but not regular        d. type 0 language but not type 1

Basic Computer quiz

Q.1 If h is any hashing function and is used to hash n keys in to a table of size m, where n<=m, the expected number of collisions involving a particular key x is :
(A) less than 1. (B) less than n.
(C) less than m. (D) less than n/2.
Ans:A

Q.2 Let A be an adjacency matrix of a graph G. The th ij entry in the matrix K A , gives
(A) The number of paths of length K from vertex Vi to vertex Vj.
(B) Shortest path of K edges from vertex Vi to vertex Vj.
(C) Length of a Eulerian path from vertex Vi to vertex Vj.
(D) Length of a Hamiltonian cycle from vertex Vi to vertex Vj.
Ans:B