McqMate
| 301. |
A finite non-empty set of symbols is called _________. |
| A. | alphabet |
| B. | letter |
| C. | string |
| D. | language |
| Answer» A. alphabet | |
| 302. |
The specification of proper construction of a sentence is called ______. |
| A. | alphabet |
| B. | letter |
| C. | syntax |
| D. | word |
| Answer» C. syntax | |
| 303. |
Context free grammar is also known as _______ grammar. |
| A. | type 0 |
| B. | type 1 |
| C. | type 2 |
| D. | type 3 |
| Answer» C. type 2 | |
| 304. |
A class of machine which accepts a ________ language is called finite state automata. |
| A. | type 0 |
| B. | type 1 |
| C. | type 2 |
| D. | type 3 |
| Answer» D. type 3 | |
| 305. |
Accepting states are denoted by ________. |
| A. | circle |
| B. | an arrow mark |
| C. | double circle |
| D. | straight line |
| Answer» C. double circle | |
| 306. |
For converting NDFA to DFA we should __________ all the states which have no incoming. |
| A. | add |
| B. | subtract |
| C. | multiply |
| D. | delete |
| Answer» D. delete | |
| 307. |
The set of all finite words over E is denoted by ________. |
| A. | E+ |
| B. | E* |
| C. | E |
| D. | E |
| Answer» A. E+ | |
| 308. |
Surjective function is also called ________. |
| A. | onto |
| B. | into |
| C. | one to one |
| D. | one one onto |
| Answer» A. onto | |
| 309. |
One to one onto function is also called __________. |
| A. | bijective |
| B. | injective |
| C. | surjective |
| D. | composite function |
| Answer» A. bijective | |
| 310. |
The composition of function is associative but not _______. |
| A. | commutative |
| B. | associative |
| C. | distributive |
| D. | idempotent |
| Answer» A. commutative | |
| 311. |
A mapping x into itself is called __________. |
| A. | reflexive |
| B. | symmetric |
| C. | transitive |
| D. | equivalence |
| Answer» A. reflexive | |
| 312. |
The duality law of (P^Q)vT is ________. |
| A. | (P^Q)^T |
| B. | (PvQ)^T |
| C. | (PvQ)vF |
| D. | (PvQ)^F |
| Answer» D. (PvQ)^F | |
| 313. |
A sum of the variables and their negations in a formula is called _________. |
| A. | elementary sum |
| B. | elementary product |
| C. | cnf |
| D. | dnf |
| Answer» A. elementary sum | |
| 314. |
A premise may be introduced at any point in the derivation is called ________. |
| A. | Rule P |
| B. | Rule P and Rule T |
| C. | Rule T |
| D. | Rule CP |
| Answer» A. Rule P | |
| 315. |
A product of the variables and their negations in a formula is called _________. |
| A. | elementary product |
| B. | elementary sum |
| C. | cnf |
| D. | dnf |
| Answer» A. elementary product | |
| 316. |
Min-terms of two statements are formed by introducing the connective _________. |
| A. | Conjunction |
| B. | disjunction |
| C. | Conditional |
| D. | negation |
| Answer» A. Conjunction | |
| 317. |
Any vertex having degree one is called _______. |
| A. | Simple vertex |
| B. | pendent vertex |
| C. | regular vertex |
| D. | complete vertex |
| Answer» B. pendent vertex | |
| 318. |
A graph that has neither self loops nor parallel edges is called_____graph. |
| A. | regular |
| B. | simple |
| C. | complete |
| D. | null |
| Answer» B. simple | |
| 319. |
A graph in which every vertex has same degree is called _________graph. |
| A. | regular |
| B. | simple |
| C. | complete |
| D. | null |
| Answer» A. regular | |
| 320. |
Kn denotes _______graph. |
| A. | regular |
| B. | simple |
| C. | complete |
| D. | null |
| Answer» C. complete | |
| 321. |
The number of vertices of odd degree in a graph is always________. |
| A. | odd |
| B. | even |
| C. | zero |
| D. | one |
| Answer» B. even | |
| 322. |
A path of a graph is said to be ______ if it contains all the edges of the graph. |
| A. | eulerian |
| B. | hamiltonian |
| C. | tournament |
| D. | planar |
| Answer» A. eulerian | |
| 323. |
Traveling salesman problem is example for_______graph. |
| A. | eulerian |
| B. | hamiltonian |
| C. | tournament |
| D. | planar |
| Answer» B. hamiltonian | |
| 324. |
If a node v is reachable from node u then the path of minimum length u to v is called _____. |
| A. | reachability |
| B. | node base |
| C. | geodesic |
| D. | accessibility |
| Answer» C. geodesic | |
| 325. |
The eccentricity of a center in a tree is defined as ______ of the tree. |
| A. | radius |
| B. | diameter |
| C. | length |
| D. | path |
| Answer» A. radius | |
| 326. |
P -> Q , Q ->R then________. |
| A. | P -> R |
| B. | R -> P |
| C. | Q |
| D. | R |
| Answer» A. P -> R | |
| 327. |
If a normal form contains all minterms, then it is ________. |
| A. | a tautology |
| B. | a contradiction |
| C. | a contingency |
| D. | both a and b |
| Answer» A. a tautology | |
| 328. |
PCNF is also called _______. |
| A. | sum of product canonical form. |
| B. | product of sum canonical form |
| C. | sum canonical form |
| D. | product canonical form |
| Answer» B. product of sum canonical form | |
| 329. |
PDNF is also called _____________ |
| A. | sum of product canonical form |
| B. | product of sum canonical form |
| C. | sum canonical form |
| D. | product canonical form |
| Answer» A. sum of product canonical form | |
| 330. |
Max-terms of two statements are formed by introducing the connective _________. |
| A. | disjunction |
| B. | conjunction |
| C. | negation |
| D. | conditional |
| Answer» A. disjunction | |
| 331. |
The Subset relation on a set of sets is ________. |
| A. | partial ordering |
| B. | equivalence relation |
| C. | reflexive and symmetric only |
| D. | symmetric and transitive only |
| Answer» A. partial ordering | |
| 332. |
A relation R is defined on the set of integers as xRy if and only if (x+y) is even. Which of the following statement is TRUE? |
| A. | R is not an equivalence relation. |
| B. | R is an equivalence relation having one equivalence classes |
| C. | R is an equivalence relation having two equivalence classes |
| D. | R is an equivalence relation having three equivalence classes |
| Answer» C. R is an equivalence relation having two equivalence classes | |
| 333. |
If R = {(1, y), (1, z), (3, y)} then R power (-1)= ___________. |
| A. | {(1, a), (y, z)} |
| B. | {(y, 1), (z, 1), (y, 3)} |
| C. | {(y, a), (1, z), (3, y)} |
| D. | {(y, a), (z, a), (3, y)} |
| Answer» B. {(y, 1), (z, 1), (y, 3)} | |
| 334. |
Let R ={ (a,b),(c,d),(b,b)}, S = {(d,b),(c,b),(a,d)} then R composite S = ___________ |
| A. | {(a,e),(c,b),(b,e)} |
| B. | {(d,b),(c,b),(a,d)} |
| C. | {(a,b),(b,b)} |
| D. | {(c,b)} |
| Answer» D. {(c,b)} | |
| 335. |
Let R and S be two relations on a set of positive integers I. If R = {(a, 3a+a)},S = {(a,a+a)} then R composition R composition R = __________. |
| A. | {(a,3a+a)} |
| B. | {(a,9a+a)} |
| C. | {(a,27a+a)} |
| D. | {(a,9a+c)} |
| Answer» C. {(a,27a+a)} | |
| 336. |
The number of relations from A = {a,b,c} to B = {1,2} are __________. |
| A. | 6 |
| B. | 8 |
| C. | 32 |
| D. | 64 |
| Answer» D. 64 | |
| 337. |
The minimum number of edges in a connected graph with n vertices is ___________. |
| A. | n |
| B. | n-1 |
| C. | n+1 |
| D. | n+2 |
| Answer» B. n-1 | |
| 338. |
The number of distinct simple graphs with up to three nodes is _________. |
| A. | 7 |
| B. | 9 |
| C. | 15 |
| D. | 25 |
| Answer» A. 7 | |
| 339. |
A graph is planar if and only if it does not contain ________. |
| A. | subgraphs homeomorphic to k3 & k3,3 |
| B. | subgraphs isomorphic to k5 or k3,3 |
| C. | subgraphs isomorphic to k3 & k3,3 |
| D. | sub graphs homeomorphic to k5 or k3,3 |
| Answer» D. sub graphs homeomorphic to k5 or k3,3 | |
| 340. |
Maximum number of edges in an n-node undirected graph without self loops is ____. |
| A. | [n(n-a)]/2 |
| B. | n-1 |
| C. | n |
| D. | [n(n+a)]/2 |
| Answer» A. [n(n-a)]/2 | |
| 341. |
Number of distinct nodes in any elementary path of length p is ________. |
| A. | p |
| B. | p-1 |
| C. | p+1 |
| D. | p*1 |
| Answer» C. p+1 | |
| 342. |
The total number of edges in a complete graph of n vertices is _________. |
| A. | n |
| B. | n/2 |
| C. | [n(n-a)]/3 |
| D. | [n(n-a)]/2 |
| Answer» D. [n(n-a)]/2 | |
| 343. |
A directed complete graph of n vertices contains __________. |
| A. | one arrow between each pair of distinct vertices |
| B. | two arrows between each pair of distinct vertices |
| C. | n-1 arrows between each pair of distinct vertices |
| D. | path between every two distinct vertices |
| Answer» A. one arrow between each pair of distinct vertices | |
| 344. |
A directed graph G = (V, E) is said to be finite if its ________. |
| A. | set V of vertices is finite |
| B. | set V of vertices & set E of edges are finite |
| C. | set E of edges are finite |
| D. | no vertices & edges are repeated |
| Answer» A. set V of vertices is finite | |
| 345. |
A state from which a deterministic finite state automata can never come out is called a ____________. |
| A. | trape state |
| B. | starting symbol |
| C. | transition table |
| D. | transition diagram |
| Answer» A. trape state | |
| 346. |
If a compound statement is made up of three simple statements then the number of rows in the truth table is _______. |
| A. | 2 |
| B. | 4 |
| C. | 6 |
| D. | 8 |
| Answer» D. 8 | |
| 347. |
Let R = {(3, 3), (6, 6), (9, 9), (12,12), (3,6), (6,3), (3, 9), (9, 3), (9, 12),(12,9)} be a relation on the set A = {3, 6, 9, 12}. The relation is _________ |
| A. | reflexive and transitive |
| B. | reflexive and symmetric |
| C. | symmetric and transitive |
| D. | equivalence relation |
| Answer» D. equivalence relation | |
| 348. |
Let R={(1,b),(3,d),(2,b)} and S={(b,4),(2,5),(d,a)} be a relation then R composition S=____. |
| A. | {(1,b),(3,d),(2,b)} |
| B. | {(1,4),(3,a),(2,4)} |
| C. | {(4,b),(2,5),(3,a)} |
| D. | {(1,d),(3,b),(2,c)} |
| Answer» B. {(1,4),(3,a),(2,4)} | |
| 349. |
If R= {(x, 2x)} and S= {(x, 4x)} then R composition S=____. |
| A. | {(x, 4x)} |
| B. | {(x, 2x)} |
| C. | {(x, 8x)} |
| D. | {(x, 10x)} |
| Answer» C. {(x, 8x)} | |
| 350. |
If R= {(x, 2x)} and S= {(x, 5x)} then R composition S=____. |
| A. | {(x, 4x)} |
| B. | {(x, 2x)} |
| C. | {(x, 8x)} |
| D. | {(x, 10x)} |
| Answer» D. {(x, 10x)} | |
| 351. |
A regular grammar contains rules of the form _____. |
| A. | A tends to AB |
| B. | AB tends to a |
| C. | A tends to aB |
| D. | AB tends to CD |
| Answer» C. A tends to aB | |
| 352. |
A type-2 grammar contains the rules of the form is____. |
| A. | a tends to AB |
| B. | AaB tends to a |
| C. | A tends to aBC |
| D. | AB tends to CD |
| Answer» C. A tends to aBC | |
| 353. |
Let R={(1, 3), (4, 2), (2, 2), (3, 3), (1, 1),(4,4)} be a relation on the set A={1, 2, 3, 4}. The relation R is ____. |
| A. | transitive |
| B. | reflexive |
| C. | not symmetric |
| D. | function |
| Answer» C. not symmetric | |
| 354. |
The NAND statement is a combination of ______. |
| A. | NOT and AND |
| B. | NOT and OR |
| C. | AND and OR |
| D. | NOT or OR |
| Answer» A. NOT and AND | |
| 355. |
The NOR statement is a combination of ________. |
| A. | NOT and AND |
| B. | NOT and OR |
| C. | AND and OR |
| D. | NOT or OR |
| Answer» B. NOT and OR | |
| 356. |
If a relation is reflexive then in the graph of a relation there must be a loop at _____. |
| A. | each node |
| B. | only first node |
| C. | any two nodes |
| D. | only first and last nodes |
| Answer» A. each node | |
| 357. |
Which of the following traversal techniques lists the nodes of binary search in ascending order? |
| A. | pre order |
| B. | post order |
| C. | in order |
| D. | root order |
| Answer» C. in order | |
| 358. |
The grammar G ={{S},{0,1},P,S}} where P={S tends to 0S1 , S tends to S1} is a ________. |
| A. | recursively enumerable grammar. |
| B. | regular grammar |
| C. | context sensitive grammar |
| D. | context free grammar |
| Answer» D. context free grammar | |
| 359. |
Which of the following regular expressions identifiers are true? |
| A. | (r*)* = r |
| B. | (r+s)* = r* . s* |
| C. | r*.s* = r* + s* |
| D. | (r.s)* = r*/s* |
| Answer» A. (r*)* = r | |
| 360. |
In a grammar or language LAMDA is used to denote _______. |
| A. | empty word |
| B. | entire set |
| C. | set of words |
| D. | set of letters |
| Answer» A. empty word | |
| 361. |
The number of letters in a word is called ________. |
| A. | length |
| B. | string |
| C. | syntax |
| D. | alphabet |
| Answer» A. length | |
| 362. |
If r is a regular expression then r* is a _______ expression. |
| A. | regular |
| B. | irregular |
| C. | isomorphic |
| D. | homomorphic |
| Answer» A. regular | |
| 363. |
An example for regular grammar is _____. |
| A. | S tends to Ab |
| B. | AB tends to SAB |
| C. | S tends to aB |
| D. | S tends to aBB |
| Answer» C. S tends to aB | |
| 364. |
If all the productions have single non-terminal in the left hand side then the grammar defined is ________grammar. |
| A. | context free |
| B. | context sensitive |
| C. | regular |
| D. | phrase structure |
| Answer» A. context free | |
| 365. |
In Backus Naur Form the symbol:: = is used instead of _______. |
| A. | { } |
| B. | tends to |
| C. | <> |
| D. | $ |
| Answer» B. tends to | |
| 366. |
Any subset L of A* is called ________ over A. |
| A. | Language |
| B. | Syntax |
| C. | Alphabet |
| D. | Word |
| Answer» A. Language | |
| 367. |
Let S be a start symbol and S -> aA, A -> BA, A -> a, B -> b be the productions in a grammar then one of the string derived form the grammar is _____. |
| A. | baba |
| B. | bbaa |
| C. | abba |
| D. | aabb |
| Answer» C. abba | |
| 368. |
If S is a start symbol and S -> AB, A -> aB, B -> b are the productions then a string generated by the grammar is _______. |
| A. | baa |
| B. | aba |
| C. | abb |
| D. | bab |
| Answer» C. abb | |
| 369. |
In FSA ,the notation for M being in state S0, reading the input symbol a, moving one cell right and reaching the state S1 is given by ________. |
| A. | f(Si , x) = Sj |
| B. | f(S0 , a) = S1 |
| C. | f(Si , a) = Sj |
| D. | f(S0 , x) = S1 |
| Answer» B. f(S0 , a) = S1 | |
| 370. |
If "S -> aS, S -> a" are the productions in a grammar G, then the grammar is called_____. |
| A. | regular grammar |
| B. | phrase structure grammar |
| C. | context free grammar |
| D. | context sensitive grammar |
| Answer» A. regular grammar | |
| 371. |
The rank of the incidence matrix of any connected graph G with n vertices is ______. |
| A. | n |
| B. | n+1 |
| C. | n-1 |
| D. | n-2 |
| Answer» C. n-1 | |
| 372. |
The number of 1's in each row of an incidence matrix of a graph G is equal to _____. |
| A. | the degree of the corresponding vertices |
| B. | the sum of degrees of all vertices |
| C. | the degree of the initial vertex |
| D. | the degree of the terminal vertex |
| Answer» A. the degree of the corresponding vertices | |
| 373. |
Each column of an incidence matrix of a graph G has exactly _______. |
| A. | one 1's |
| B. | two 1's |
| C. | one 2's |
| D. | two 2's |
| Answer» B. two 1's | |
| 374. |
An undirected graph is tripartite if and only if it has no circuits of _______ lengths |
| A. | odd |
| B. | even |
| C. | distinct |
| D. | equal |
| Answer» A. odd | |
| 375. |
A graph is bipartite if and only if its chromatic number is ________. |
| A. | 1 |
| B. | 2 |
| C. | odd |
| D. | even |
| Answer» B. 2 | |
| 376. |
G is strongly connected implies _________. |
| A. | G is unilaterally connected. |
| B. | G is bilaterally connected |
| C. | G is unilaterally connected |
| D. | G has more than one component |
| Answer» A. G is unilaterally connected. | |
| 377. |
The number of pendant vertices in a full binary tree with n vertices is ________. |
| A. | (n-a)/2 |
| B. | (n-1)/2 |
| C. | (n+a)/2 |
| D. | n/2 |
| Answer» C. (n+a)/2 | |
| 378. |
The number of vertices in a full binary tree is _______. |
| A. | odd |
| B. | even |
| C. | equal |
| D. | 0 |
| Answer» A. odd | |
| 379. |
A binary tree with 2k vertices of level k has at least _______ vertices. |
| A. | 2 power k |
| B. | 2 power (k-1) |
| C. | 2 power (k-1)-1) |
| D. | 2 power (k+1)-1 |
| Answer» D. 2 power (k+1)-1 | |
| 380. |
For a symmetric digraph, the adjacency matrix is _________. |
| A. | symmetric |
| B. | antisymmetric |
| C. | asymmetric |
| D. | symmetric and asymmetric |
| Answer» A. symmetric | |
| 381. |
The diagonal entries of A A^T where A is the adjacency matrix are the _______. |
| A. | outdegrees of the node |
| B. | indegrees of the nodes |
| C. | unit degree of the nodes |
| D. | in & out degrees of the nodes |
| Answer» A. outdegrees of the node | |
| 382. |
DFSA and NDFSA represent the ________ language. |
| A. | regular |
| B. | context free |
| C. | context sensitive |
| D. | phrase structure |
| Answer» A. regular | |
| 383. |
The chromatic number of the chess board is ______. |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | 4 |
| Answer» B. 2 | |
| 384. |
The total number of degrees of an isolated node is _______. |
| A. | 0 |
| B. | 1 |
| C. | 2 |
| D. | 3 |
| Answer» A. 0 | |
| 385. |
If G is a connected planar graph then it has a vertex of degree _______. |
| A. | 3 or less |
| B. | 4 or less |
| C. | 5 or less |
| D. | 6 or less |
| Answer» C. 5 or less | |
| 386. |
A product of the variable and their negation in a formula is called ________. |
| A. | an elementary sum |
| B. | an elementary product |
| C. | a well-formed formula |
| D. | an equivalence of relation formula |
| Answer» B. an elementary product | |
| 387. |
A formula consisting of disjunctions of min-terms is called _________. |
| A. | DNF |
| B. | CNF |
| C. | PDNF |
| D. | PCNF |
| Answer» C. PDNF | |
| 388. |
The less than relation < on real is __________. |
| A. | a partial ordering since it is asymmetric and reflexive |
| B. | a partial ordering since it is anti-symmetric and reflexive |
| C. | not a partial ordering since it is not asymmetric and not reflexive |
| D. | not a partial ordering since it is not anti-symmetric and not reflexive |
| Answer» D. not a partial ordering since it is not anti-symmetric and not reflexive | |
| 389. |
A relation R in X is said to be a ________, if it is reflexive and symmetric. |
| A. | void relation |
| B. | circular |
| C. | partial order relation |
| D. | compatibility relation |
| Answer» D. compatibility relation | |
| 390. |
The set X*X itself defines a relation in X is called a _____relation. |
| A. | void |
| B. | universal |
| C. | partial |
| D. | equivalence |
| Answer» B. universal | |
| 391. |
A self complemented distributive lattice is called _______. |
| A. | boolean algebra |
| B. | modular lattice |
| C. | complete lattice |
| D. | self dual lattice |
| Answer» A. boolean algebra | |
| 392. |
Every finite subset of a lattice has ____________. |
| A. | a Least Upper Bound and Greatest Lower Bound |
| B. | many Least Upper Bounds and a Greatest Lower Bound |
| C. | many Least Upper Bounds and many Greatest Lower Bounds |
| D. | either some Least Upper Bounds or some Greatest Lower Bounds |
| Answer» A. a Least Upper Bound and Greatest Lower Bound | |
| 393. |
A formula consisting of conjunctions of max-terms is called _________. |
| A. | DNF |
| B. | CNF |
| C. | PCNF |
| D. | PDNF |
| Answer» C. PCNF | |
| 394. |
The set of all divisors of 24 are ___________. |
| A. | {1, 2, 3, 4, 6, 8, 12, 24} |
| B. | {2, 3, 4, 6, 8, 12} |
| C. | {1, 3, 6, 12,} |
| D. | {2, 4, 6, 8} |
| Answer» A. {1, 2, 3, 4, 6, 8, 12, 24} | |
| 395. |
Which of the following is Absorption Law? |
| A. | a*a <=>a |
| B. | a+(a*b)<=> a |
| C. | a*b <=>a*a |
| D. | (a*b)*c <=>a*(b*c) |
| Answer» B. a+(a*b)<=> a | |
| 396. |
In a bounded lattice, an element b belongs to L is called a complement of an element a belongs to L if ______. |
| A. | a*b=0 |
| B. | a+b=1 |
| C. | both a and b |
| D. | none |
| Answer» C. both a and b | |
| 397. |
If each non-empty subset of a lattice has a least upper bound and greatest lower bound then the lattice is called ________. |
| A. | complete |
| B. | associative |
| C. | absorption |
| D. | commutative |
| Answer» A. complete | |
| 398. |
A __________ is a complemented distributive lattice. |
| A. | boolean homomorphism |
| B. | boolean algebra |
| C. | boolean isomorphism |
| D. | boolean function |
| Answer» D. boolean function | |
| 399. |
Boolean expression except 0 expressed in an equivalent form is called _____. |
| A. | canonical |
| B. | sum |
| C. | product |
| D. | standard |
| Answer» A. canonical | |
| 400. |
_________relations are useful in solving certain minimization problems of switching theory. |
| A. | Void |
| B. | Universal |
| C. | Compatibility |
| D. | Equivalence |
| Answer» C. Compatibility | |
Done Reading?