数据结构C语言版期末考试试题（有答案）

81．在一个有向图中

所有顶点的入度之和等于所有顶点的出度之和的 B 倍

A．1/2 B 1 C 2 D 4

82．某二叉树结点的中序序列为ABCDEFG 后序序列为BDCAFGE

则其左子树中结点数目为： C

A．3 B．2 C．4 D．5

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 条边

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｝

当折半查找值为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．所有结点的右子树都为空的二叉排序树

C．平衡二叉树

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

98．排序方法中

从未排序序列中依次取出元素与已排序序列中的元素进行比较 将其放入已排序序列的正确位置上的方法 称为 C

A．希尔排序 B

冒泡排序 C插入排序 D 选择排序

99．在所有的排序方法中

关键字比较的次数与记录的初始排列次序无关的是 D

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