2018年杭州电子科技大学计算机学院851数据结构考研核心题库
● 摘要
一、是非题
1． 内排序要求数据一定要以顺序方式存储。（ ）
【答案】×
【解析】由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为两大类:一类 是内部排序；另一类是外部排序。因此，内部排序没有要求数据一定是以顺序方式存储。
2． 在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。（ ）
【答案】√
【解析】在进行分块查找时，首先查找元素在哪一块，然后在确定的块中查找元素，因此，在索引顺序表中，进行分块查找的平均查找长度不仅与表中元素的个数有关，而且与每块中的元素个数有关。
3． 如果完全二叉树从根结点开始按层次遍历的输序列为1，2，3，4，5，6，7，则该完全二叉树是二叉排序树。（ ）
【答案】×
【解析】不是，2，3作为1的左右孩子，由于左节点2比1大，所以不具有二叉排序树的性质。
4． 两分法插入排序所需比较次数与待排序记录的初始排列状态相关。（ ）
【答案】×
【解析】折半插入排序所需的附加存储空间和直接插入排序相同，从时间上比较，折半插入排序仅减少了关 键字间的比较次数，而记录的移动次数不变。因此，折半插入排序的时间复杂度，与待排序记录的初始排列状态无关。 仍为
5． 二叉树是一般树的特殊情形。（ ）
【答案】×
【解析】树与二叉树是两种不同的树形结构，二叉树中的孩子结点有着严格左右之分的。
6． 数组是同类型值的集合。（ ）
【答案】 ×
【解析】数组是具有相同性质的数据元素的集合，数据元素不仅有值，还有下标。因此，可以说数组是元素值和下标构成的偶对的有穷集合。
二、单项选择题
7． 主机甲与乙之间已建立一个TCP 连接, 双方持续有数据传输, 且无差错与丢失。若甲收到1个来自乙的TCP 段, 该段的序号为1913、确认序号为2046、有效载荷为100字节, 则甲立即发送给乙的TCP 段的序号和确认分别是（ ）
A.2046、2012
B.2046、2013
C.2047、2012
D.2047、2012
【答案】B
【解析】若甲收到1个来自乙的TCP 段, 该段的序号seq=1913、确认序号ack=2046、有效载荷为100字节, 则甲立即发送给乙的TCP 段的序
号
, 答案为B 。
8． 就平均性能而言，目前最好的内排序方法是（ ）排序法。
A. 起泡
B. 希尔插入
C. 交换
D. 快速
【答案】D
【解析】快速排序的平均时间复杂度是nlogn 所需要的辅助存储为
间复杂度也是
注意仅仅表示的是一个量级，比如和的量级都为，虽然堆排序的时。之所以说，所需要的辅助存储为O(1)，看似堆排序比快速排序的性能好，但是需要和确认序
号快排最好，是在综合考虑的情况下。
9． 设有数组A[i，j]，数组的每个元素长度为3字节，i 的值为1到8，j 的值为1到10，数组从内存首地址BA 开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为（ ）。
A.BA+141
B.BA+180
C.BA+222
D.BA+225
【答案】B
【解析】在计算中，可以考虑按照列存放时，A[5，8]在内存的位置，比较容易计算元素的首地址。比如A[5，8]顺序存放时，它是第7*8＋5＝61个元素，由于首地址为BA ，所以它的存储首地址为BA ＋(61﹣1)*3＝180+BA。
10．一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是（ ）.
A.28字节
B.216字节
C.224字节
D.232字节
【答案】C
【解析】段内位移的最大值就是最大段长. 段号长度占了8位，剩下32﹣8＝24位是段内位移空间，因此最大段长为2B.
11．在有向图G 的拓扑序列中，若顶点在顶点之前，则下列情形不可能出现的是（ ）。 24
A.G 中有弧
C.G 中没有弧
【答案】D B.G 中有一条从到的路径 D.G 中有一条从到的路径
【解析】若想实现图的一个拓扑排序，需要满足的一个条件为:若顶点A 在序列中排在顶点B 的前面，则在图中不存在从顶点B 到顶点A 的路径。又因为若G 中有一条从到的路径，则在拓扑序列中不可能在前。
12．对下图进行拓扑排序, 可以得到不同的拓扑序列的个数是（ ）。
图
A.4
B.3
C.2
D.1
【答案】B
【解析】拓扑排序的步骤为:
(1)在有向图中选一个没有前驱的顶点并且输出它;
(2)从图中删除该顶点和以它为尾的弧。重复上述两步, 直至全部顶点均已输出。由于没有前驱的顶点可能不唯一, 所以拓扑排序的结果也不唯一。题中所给图有三个不同的拓扑排序序列, 分别为abced , abecd , aebcd 。