数据结构考试 急 谢谢！

Question

第1题 假定一个顺序循环队列存储于数组A[n]中，其队首和队尾指针分别用front和rear表示，则判断队满的条件是（ ）
A、(rear-1)%n==front
B、(rear+1)%n==front
C、rear==(front-1)%n
D、rear==(front+1)%n

第2题 若串S=“software”,其子串数目是（ ）
A、8
B、37
C、36
D、9

第3题
已知广义表LS=((a,b,c),(d,e,f)),运用head和tail函数取出LS中元素e的运算是（ ）

A、head(tail(LS))
B、tail(head(LS))
C、head(tail(head(tail(LS))))
D、head(tail(tail(head(LS))))

第4题
二维数组A的每个元素是由6个字符组成的串，其行下标i=0、1、…、8，列下标j=1、2、…、4、若A按行先存储，元素A[8，5]的起始地址与当A按列先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。

A、A[8，5]
B、A[3,10]
C、A[5,8]
D、A[0,9]

第5题 若在线性表中采用折半查找法查找元素，该线性表应该（ ）
A、元素按值有序
B、采用顺序存储结构
C、元素按值有序，且采用顺序存储结构
D、元素按值有序，且采用链式存储结构

第6题
设深度为K的二叉树上只有度为0和度为2的结点，则这类二叉树上所含的结点总数为（ ）

A、K+1
B、2K
C、2K-1
D、2K+1

第7题 设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有（ ）个结点
A、13
B、12
C、26
D、25

第8题 下面哪一种方法可以判断出一个有向图中是否有环（回路）( )
A、深度优先遍历
B、拓扑排序
C、求最短路径
D、求关键路径

第9题 二分查找法要求查找表中各元素的键值必须是（ ）排列
A、递增或递减
B、递增
C、递减
D、无序

第10题 以下说法错误的是（ ）
A、哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近
B、若一个二叉树的树叶是某子树中序遍历序列中的第一个结点，则它必是该子树后序
C、已知二叉树的前序遍历和后序遍历并不能唯一地确定这棵树，因为不知道树的根结
D、前序遍历二叉树的序列中，任何结点其子树的所有结点都是直接跟在该结点之后的

判断题
第11题 两个字符串相等的充分必要条件是长度相等，并且各个对应位置上的字符都相等
正确
错误

第12题 若一个广义表的表头为空表，则此广义表亦为空表。
正确
错误

第13题 广义表中原子个数即为广义表的长度。
正确
错误

第14题 存在这样的二叉树，对它采用任何次序的遍历，结果相同。
正确
错误

第15题 二叉树就是结点度为2的树。
正确
错误

第16题 二叉树中不存在度大于2的结点，当某个结点只有一棵子树时无所谓左、右子树之分。
正确
错误

第17题 将一棵树转换成二叉树后，根结点没有左子树。
正确
错误

第18题 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。
正确
错误

第19题 线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。
正确
错误

第20题 有n个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素之和的一半。
正确
错误

Answer 1

1题 答案是B。顺序循环队列可以采用牺牲一个单元来区分队空队满，队满是B；队空是rear==front。
2题 答案是B。子串长度为0，1，2，3，4，5，6，7，8分别讨论即可。
3题 暂不清楚。
4题 列下标的最终位置没有提出
5题 答案是C。折半查找的要求。
6题 无答案。深度为k不能确定出结点总数。若叶子结点的个数为k，则总结点个数为2k-1。
7题 答案是D。哈夫曼树只有度为0和2的结点，设度为0的结点个数为x，度为2的结点个数为y，则x+y=2y+1，所以x-1=y，x即为13，也就是叶子结点，所以总结点个数为13+12=25.
8题 答案暂定为AB。C是绝对不行的，至于D原因不清楚。
9题 答案是A。二分查找必须在有序的顺序表中进行，至于递增或递减则无要求。
10题 题目不完整
11题 正确。
12题 暂不清楚。
13题 暂不清楚。
14题 正确。只有一个结点的二叉树。
15题 错误。二叉树中结点的度可以为0，1，2。
16题 错误。
17题 错误。根节点没有右子树。
18题 正确。
19题 错误。非线性数据结构可以顺序存储，比如图的邻接矩阵存储。
20题 错误。如果图中有结点的自回路，则邻接矩阵主对角线上有数据。

有一些问题有争议，还可以讨论，关于广义表的问题，没涉及过故不作解答。

Answer 2

zfdbdhf

Answer 3

不会