# Data Structure Questions and Answers-Propositional and Directed Acyclic Word Graph

## Data Structure Questions and Answers-Propositional and Directed Acyclic Word Graph

 Question 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
Question 1 Explanation:
A Directed Acyclic Word Graph is similar to suffix tree, it can be viewed as a Deterministic Finite Automata.

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

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
Question 2 Explanation:
Words namely BATS, BOTS, BAT and BOT can be formed.

 Question 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
Question 3 Explanation:
Starting from the initial state and choosing B, A, T, S respectively.

 Question 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)
Question 4 Explanation:
For each check of a word of length S1, we need to follow at most S1 edges.

 Question 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
Question 5 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) ⊥

There are 5 questions to complete.