Engineering Questions with Answers - Multiple Choice Questions

# Data Structure MCQ – Binary Decision Diagrams & And Inverter Graph

1 - Question

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

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

2 - Question

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

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

3 - Question

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

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

4 - Question

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

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

5 - Question

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

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

6 - Question

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

Explanation: And Inverter Graphs are not canonical in nature.

7 - Question

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

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

8 - Question

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

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

9 - Question

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

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

10 - Question

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