Engineering Questions with Answers - Multiple Choice Questions

Data Structure MCQ – Propositional and Directed Acyclic Word Graph

1 - Question

In which of the following does a Directed Acyclic Word Graph finds its application in?
a) String Matching
b) Number Sorting
c) Manipulations on numbers
d) Pattern Printing

View Answer

Answer: a
Explanation: A Directed Acyclic Word Graph is similar to suffix tree, it can be viewed as a Deterministic Finite Automata.




2 - Question

 What is the number of words that can be formed from the given Directed Acyclic Word Graph?
data-structure-questions-answers-propositional-directed-acyclic-word-graph-q2
a) 2
b) 4
c) 12
d) 7

View Answer

Answer: b
Explanation: Words namely BATS, BOTS, BAT and BOT can be formed.




3 - Question

Determine the longest string which is described by the given Directed Acyclic Word Graph.
data-structure-questions-answers-propositional-directed-acyclic-word-graph-q2
a) BATS
b) BOATS
c) BOT
d) BAT

View Answer

Answer: a
Explanation: Starting from the initial state and choosing B, A, T, S respectively.




4 - Question

What is time complexity to check if a string(length S1) is a substring of another string(length S2) stored in a Directed Acyclic Word Graph, given S2 is greater than S1?
a) O(S1)
b) O(S2)
c) O(S1+S2)
d) O(1)

View Answer

Answer: a
Explanation: For each check of a word of length S1, we need to follow at most S1 edges.




5 - Question

In which of the following case does a Propositional Directed Acyclic Graph is used for?
a) Representation of Boolean Functions
b) String Matching
c) Searching
d) Sorting of number

View Answer

Answer: a
Explanation: A Propositional Directed Acyclic Graph is used to represent a boolean function.




6 - Question

Consider the following symbols and choose which of the symbols represent nodes having atleast one child?

i) Δ ii) ◊ iii) ∇ iv) T v) ⊥

a) iv) and v)
b) iii) iv) and v)
c) i) and ii)
d) i) and iii)

View Answer

Answer: c
Explanation: The symbols Δ and ◊ represents logical AND and OR gates.




7 - Question

Which of the following symbols represent nodes having exactly one child?

i) Δ ii) ◊ iii) ∇ iv) T v) ⊥

a) iv) and v)
b) v)
c) i) and iii)
d) iii)

View Answer

Answer: d
Explanation: ∇ symbol represents the logical NOT gate.




8 - Question

Which of the following symbols represent leaf nodes?

i) Δ ii) ◊ iii) ∇ iv) T v) ⊥ 

a) iv) and v)
b) v)
c) i) and iii)
d) ii)

View Answer

Answer: a
Explanation: The two symbols T, ⊥ represent the Boolean values.




9 - Question

Every Binary Decision Diagram is also a Propositional Directed Acyclic Graph.
a) True
b) False

View Answer

Answer: a
Explanation: Both Binary Decision Diagram and Propositional Directed Acyclic Graph may be used to represent the same Boolean function.




10 - Question

In a Propositional Directed Acyclic Graph Leaves maybe labelled with a boolean variable.
a) True
b) False

View Answer

Answer: a
Explanation: In a Propositional Directed Acyclic Graph leaves maybe labelled with a boolean variable, T or ⊥.

Get weekly updates about new MCQs and other posts by joining 18000+ community of active learners