![Mcqmate logo](https://mcqmate.com/images/logos/logo-black.png)
![Mcqmate logo](https://mcqmate.com/images/logos/logo-white.png)
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?