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

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

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)
View Answer

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
View Answer

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

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

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

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

Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter