Data Structure Questions and Answers – Binary Decision Diagrams & And Inverter Graph

«

This set of Data Structure test focuses on “Binary Decision Diagrams & And Inverter Graph”.

1. Binary Decision Diagram is a type of __________
a) Multigraph
b) Cyclic Graph
c) Directed Acyclic Graph
d) Directed Acyclic Word Graph
View Answer

Answer: c
Explanation: An Inverter is a directed graph which is used to solve Boolean expressions, hence have no loops.
advertisement

2. In which of the following case does a Binary Decision Diagram is used for?
a) Representation of Boolean Functions
b) String Matching
c) Searching
d) Sorting of number
View Answer

Answer: a
Explanation: A Binary Decision Diagram is used to represent a Boolean function.

3. In a Binary Decision Diagram, how many types of terminal exists?
a) 1
b) 2
c) 3
d) 4
View Answer

Answer: b
Explanation: In a BDD, 2 terminals namely terminal-0 and terminal-1 exists.

4. In a Binary Decision Diagrams 0 values by a _________ line and the 1 values are represented by a _________ line.
a) dashed, bold
b) bold, dashed
c) dotted, bold
d) dotted, dashed
View Answer

Answer: c
Explanation: It is used to distinguish between the 2 values without explicitly writing.

5. How many nodes are required to create a Binary Decision Tree having 4 variables?
a) 24
b) 24-1
c) 25
d) 25-1
View Answer

Answer: d
Explanation: Binary Decision Trees are complete Binary Trees of level V + 1, here V is the number of variables.
advertisement

6. Two or more And Inverter Graphs can represent same function.
a) True
b) False
View Answer

Answer: a
Explanation: And Inverter Graphs are not canonical in nature.

7. Size of an And Inverter Graph is the number of _______ gates and the number of logic levels is number of ________ gates on the __________ path from a primary input to a primary output.
a) AND, AND, average
b) AND, OR, longest
c) OR, OR, shortest
d) AND, AND, longest
View Answer

Answer: d
Explanation: The given statement forms the attributes of the And Inverter Graph.

8. And Inverter Graph is a type of __________
a) Multigraph
b) Cyclic Graph
c) Directed Acyclic Graph
d) Directed Acyclic Word Graph
View Answer

Answer: c
Explanation: And Inverter is a directed graph which is used to solve boolean expressions, hence have no loops.

9. The And Inverter Graph representation of a Boolean function is more efficient than the Binary Decision Diagram.
a) True
b) False
View Answer

Answer: a
Explanation: The conversion from the network logic is faster and more scalable than in the case of the Binary Decision Diagram.
advertisement

10. Which of the following logical operation can’t be implemented by polynomial time graph manipulation algorithms using Binary Decision Diagrams?
a) Conjunction
b) Disjunction
c) Negation
d) Tautology Checking
View Answer

Answer: d
Explanation: In Binary Decision Diagram, Conjunction, Disjunction, Negotiation can be implemented in polynomial time whereas tautology checking can be implemented in linear time.

Sanfoundry Global Education & Learning Series – Data Structure.

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

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