题39

题39

题目

Q:【2019 统考真题】用有向无环图描述表达式 ,需要的顶点个数至少是 ( ).
A. 5
B. 6
C. 8
D. 9

分析

A:按照运算的优先级来作为优先分配的结点
有向无环图: 若一个有向图中不存在环, 则称为有向无环图, 简称 DAG 图。
有向无环图是描述含有公共子式的表达式的有效工具。
例如表达式

可以用上一章描述的二叉树来表示, 如图 6.20 所示。
仔细观察该表达式, 可发现有一些相同的子表达式 和 ，而在二叉树中，它们也重复出现。
若利用有向无环图,则可实现对相同子式的共享, 从而节省存储空间, 图 6.21 所示为该表达式的有向无环图表示。

图 6.20 二叉树描述表达式

在表达式的有向无环图表示中, 不可能出现重复的操作数顶点。

解

A
先将该表达式转换成有向二叉树, 该二叉树中有些顶点是重复的, 为了节省存储空间, 去除重复的顶点, 将有向二叉树去重转换成有向无环图, 如下图所示。