83．已知一算术表达式的中缀形式为A＋B *C–D/E，后缀形式为ABC *+DE/–，其前缀形式为 D 。将算术表达式的中缀形式作为一棵二叉树的中序遍历序列，将后缀形式 作为

这棵二叉树的后序遍历序列，再由二叉树的中序遍历序列和后序遍历序列唯一的确定 这棵 二叉树，在对其进行先序遍历，就可得出算术表达式的前缀形式。

A

．

–A+B*C/DE

B

．

–A+B*CD/E

C

–+*ABC/DE D．–+A*BC/DE

84．已知一个图，如图所示，若从顶点a出发索法进行遍历，则可能得到的一种顶点序列____D___；按广度搜索法进行遍历，则可能种顶点序列为___A___；

①A．a，b，e，c，d，f B．a，c，f，e，b，d C．a，e，b，c，f，d， D．a，e，d，f，c，b ②A．a，b，c，e，d，f B．a，b，c，e，f，d C．a，e，b，c，f，d， D．a，c，f，d，e，b

85．采用邻接表存储的图的深度优先遍历算法类似于二叉树的___A____。 A．先序遍历 B．中序遍历 C．后序遍历 D．按层遍历

86．采用邻接表存储的图的广度优先遍历算法类似于二叉树的___D____。 A．先序遍历 B．中序遍历 C．后序遍历 D．按层遍历

87．具有n 个结点的连通图至少有 A 条边。

17

abdefc按深度搜为得到的一

A． n-1 B． n C． n(n-1)/2 D． 2n

88．广义表（（a），a）的表头是 C ，表尾是 C 。 A．a B （） C （a） D （（a））

89．广义表（（a））的表头是 C ，表尾是 B 。 A．a B （） C （a） D （（a））

90．顺序查找法适合于存储结构为 B 的线性表。

A 散列存储 B 顺序存储或链式存储 C 压缩存储 D 索引存储

91．对线性表进行折半查找时，要求线性表必须 B 。

A 以顺序方式存储 B 以顺序方式存储，且结点按关键字有序排列

C 以链式方式存储 D 以链式方式存储，且结点按关键字有序排列

92．采用折半查找法查找长度为n的线性表时，每个元素的平均查找长度为 D 。

A O(n2) B O(nlog2n) C O(n) D O(log2n)

93．有一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，

18

当折半查找值为82的结点时， C 次比较后查找成功。 A． 11 B 5 C 4 D 8

94．二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法 B 。 A 正确 B 错误

95．下面关于B树和B+树的叙述中，不正确的结论是 A 。

A B树和B+树都能有效的支持顺序查找 B B树和B+树都能有效的支持随机查找

C B树和B+树都是平衡的多叉树 D B树和B+树都可用于文件索引结构

96．以下说法错误的是 B 。

A．散列法存储的思想是由关键字值决定数据的存储地址 B．散列表的结点中只包含数据元素自身的信息，不包含指针。 C．负载因子是散列表的一个重要参数，它反映了散列表的饱满程度。 D．散列表的查找效率主要取决于散列表构造时选取的散列函数和处理冲突的方法。

97．查找效率最高的二叉排序树是 C 。 A．所有结点的左子树都为空的二叉排序树。 B．所有结点的右子树都为空的二叉排序树。

19

C．平衡二叉树。

D．没有左子树的二叉排序树。

98．排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 C 。 A．希尔排序 B。冒泡排序 C插入排序 D。选择排序

99．在所有的排序方法中，关键字比较的次数与记录的初始排列次序无关的是 D 。

A．希尔排序 B．冒泡排序 C．直接插入排序 D．直接选择排序

？100．堆是一种有用的数据结构。下列关键码序列 D 是一个堆。 A．94,31,53,23,16,72 B．94,53,31,72,16,23 将所有数据序列按完全二叉树从根开始放,

如果所有分支都小于或者等于孩子结点关键码,就是小顶堆,反之,如果所有分支结点的关键码大于或者等于孩子结点关键码,则为大顶堆

C．16,53,23,94,31,72 D．16,31,23,94,53,72

101．堆排序是一种 B 排序。

A．插入 B．选择 C．交换 D．归并

102． D 在链表中进行操作比在顺序表中进行操作效率高。 A．顺序查找 B．折半查找 C．分块查找 D．插入

20