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

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Propositional and Directed Acyclic Word Graph”.

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

Explanation: Logic AND and OR gates are represented by the symbols and.

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

Explanation: The logical NOT gate is represented by the symbol.

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

Explanation: The Boolean values are represented by the two symbols T.

4. Every Binary Decision Diagram is also a Propositional Directed Acyclic Graph.
A) True
B) False

Explanation: The same Boolean function can be represented using both a Binary Decision Diagram and a Propositional Directed Acyclic Graph.

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

Explanation: A boolean variable, T or, may be used to mark leaves in a Propositional Directed Acyclic Graph.

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

Explanation: We must obey at least S1 edges for each search of a word of length S1.

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

Explanation: A boolean function is represented by a Propositional Directed Acyclic Graph.

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

Explanation: A Directed Acyclic Word Graph is a Deterministic Finite Automata that is analogous to a suffix tree.

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

Explanation: BATS, BOTS, BAT, and BOT are examples of words that can be created.

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

A) BATS
B) BOATS
C) BOT
D) BAT

Explanation: Starting with B, A, T, and S, choose B, A, T, and S, respectively.

A directed acyclic graph (DAG or dag /d/ (About this soundlisten)) is a graph that does not have any directed cycles. That is, it is made up of vertices and edges (also known as arcs), each of which is directed from one vertex to the next in such a way that following those directions can never result in a closed loop. A directed graph is a DAG if and only if the vertices can be topologically ordered in a linear order that is consistent across all edge directions. From biology (evolution, family trees, epidemiology) to sociology (citation networks) to computing, DAGs have a wide range of scientific and computational applications (scheduling).