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

Uncategorized

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

1. Two or more And Inverter Graphs can represent same function.
A) True
B) False

Explanation: Inverter Graphs are not canonical in nature.

2. 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 And Inverter Graph’s attributes are formed by the given statement.

3. And Inverter Graph is a type of __________
A) Multigraph
B) Cyclic Graph
C) Directed Acyclic Graph
D) Directed Acyclic Word Graph

Explanation: Inverter is a directed graph with no loops that is used to solve boolean expressions.

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

Explanation: The network logic conversion is quicker and more scalable than the Binary Decision Diagram conversion.

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

Explanation: Conjunction, Disjunction, and Negotiation can be implemented in polynomial time in a Binary Decision Diagram, while tautology verification can be implemented in linear time.

6. 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 with no loops that is used to solve Boolean expressions.

7. 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 Boolean function is represented using a Binary Decision Diagram.

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

9. 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 differentiate between the two values without having to write them down directly.

10. 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: Full Binary Trees of level V + 1, where V is the number of variables, are known as Binary Decision Trees.

A branching software, also known as a binary decision diagram (BDD), is a data structure that is used to describe a Boolean function. BDDs can be thought of as a compact representation of sets or relations on a more abstract basis. Unlike other compressed representations, operations are carried out directly on the compressed representation, without the need for decompression. Negation normal form (NNF), Zhegalkin polynomials, and propositional directed acyclic graphs are some of the other data structures used to describe Boolean functions (PDAG).

Leave a Reply

Your email address will not be published. Required fields are marked *