Data Structures Multiple Choice Questions and Answers on Propositional and Directed Acyclic Word Graph

1. 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) None of the mentioned

Answer: a

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

Answer the following questions(2-3) for the given DWAG.

2. What is the number of words that can be formed from the given Directed Acyclic Word Graph?

a) 2
b) 4
c) 12
d) 7

Answer: b

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

3. Determine the longest string which is described by the given Directed Acyclic Word Graph.

a) BATS
b) BOATS
c) BOT
d) None of the mentioned

Answer: a

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

4. 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)

Answer: a

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

5. 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

Answer: a

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

For the given symbols answer the following questions.
i) Δ
ii) ◊
iii) ∇
iv) T
v) ⊥

6. Which of the given symbols represent nodes having at least one child?

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

Answer: c

Explanation: The two symbols represent logical AND and OR gates.

7. Which of the given symbols represent nodes having exactly one child?

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

Answer: d

Explanation: This symbol represents the logical NOT gate.

8. Which of the given symbols represent may represent leaf nodes?

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

Answer: a

Explanation: The two symbols represent the Boolean values.

9. Every Binary Decision Diagram is also a Propositional Directed Acyclic Graph.

a) True
b) False

Answer: a

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

10. In a Propositional Directed Acyclic Graph Leaves maybe labelled with a boolean variable.

a) True
b) False

Answer: a

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