Discrete Mathematics - Questions & Answers for Competitive Exams | GkSeries

25. 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: Option [C]

26. The number of letters in a word is called ________.

• [A] length
• [B] string
• [C] syntax
• [D] alphabet

Answer: Option [A]

27. 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: Option [C]

28. Any subset L of A* is called ________ over A.

• [A] Language
• [B] Syntax
• [C] Alphabet
• [D] Word

Answer: Option [A]

29. 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: Option [C]

30. 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: Option [C]

31. An undirected graph is tripartite if and only if it has no circuits of _______ lengths

• [A] odd
• [B] even
• [C] distinct
• [D] equal

Answer: Option [A]

32. A graph is bipartite if and only if its chromatic number is ________.

• [A] 1
• [B] 2
• [C] odd
• [D] even

Answer: Option [B]

33. 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: Option [C]

34. For a symmetric digraph, the adjacency matrix is _________.

• [A] symmetric
• [B] antisymmetric
• [C] asymmetric
• [D] symmetric and asymmetric

Answer: Option [A]

35. DFSA and NDFSA represent the ________ language.

• [A] regular
• [B] context free
• [C] context sensitive
• [D] phrase structure

Answer: Option [A]

36. The total number of degrees of an isolated node is _______.

• [A] 0
• [B] 1
• [C] 2
• [D] 3

Answer: Option [A]