2018年中原工学院计算机学院815专业基础(含数据结构、操作系统)之数据结构考研核心题库
● 摘要
一、单项选择题
1． float 类型(即IEEE754单精度浮点数格式) 能表示的最大正整数是（ ）。 A. B. C. D.
【答案】D 。
【解析】IEEE754单精度浮点数尾数采用隐藏位策略的原码表示, 且阶码用移码表示的浮点数。规格化的短浮点数的真值为:
故float 类型能表示的最大整数是
。
2． 下列关于无向连通图特性的叙述中，正确的是（ ）.
(1)所有的顶点的度之和为偶数
(2)边数大于顶点个数减1
(3)至少有一个顶点的度为1
A. 只有(1)
B. 只有(2)
C. (1)和(2)
D.(1)和(3)
【答案】A
【解析】在图中，
顶点的度之和与边的数目满足关系式：(n为图的, S 为符号位, E 的取值为, f 为23位; 总结点数，e 为总边数) ，因此， (1)项正确. 对于(2)、(3)项中的特性不是一般无向连通图的特性，可以轻松地举出反例.“至少有一个顶点的度为1”的反例如下图1所示，“边数大于顶点个数减1”的反例如下图2所示
.
图
1
图2
3． 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）。
A.(2，5，12，16)26(60，32，72)
B.(5，16，2，12)28(60，32，72)
C.(2，16，12，5)28(60，32，72)
D.(5，16，2，12)28(32，60，72)
【答案】B
【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。
第一次比较:28比72小，不交换;
第二次比较:28比5大，交换，此时为(5，16，32，12，60，2，28，72) ;
第三次比较:16比28小，不交换；
第四次比较:32比28大，交换，此时为(5，16，28，12，60，2，32，72) ;
第五次比较:28比2大，交换，此时为(5，16，2，12，60，28，32，72) ;
第六次比较:28比12大，不交换；
第七次比较:28比60小，交换，此时为(5，16，2，12，28，60，32，72) ;
一次划分结束。
4． 对序列{15，9，7，8，20，-1，4，}用希尔排序方法排序，经一趟后序列变为{15，-1，4，8，20，9，7}则该次釆用的增量是（ ）。
A.1
B.4
C.3
D.2
【答案】B
【解析】由所给的序列知，本序列要进行递增排序，经过一趟后15的位置没有变化，而给的序列中只有20比15大，20的位置和15的位置相差4。所以该次采用的增量是4。
5． 响应外部中断的过程中, 中断隐指令完成的操作, 除保护断点外, 还包括（ ）。
Ⅰ. 开关中断
Ⅱ. 保存通用寄存器的内容
Ⅲ. 形成中断服务程序入口地址并送PC
A. 仅Ⅰ、Ⅱ
B. 仅Ⅰ、Ⅲ
C. 仅Ⅱ、Ⅲ
D. Ⅰ、Ⅱ、Ⅲ
【答案】B 。
【解析】中断隐指令完成的操作有3个:
①保存断点; ②关中断; ③引出中断服务程序(形成中断服务程序入口地址并送PC) 。
而保存通用寄存器内容的操作是由软件来实现, 不是由中断隐指令实现的。
6． 下列选项中, 不可能是快速排序第2趟排序结果的是（ ）
A.2, 3, 5, 4, 6, 7, 9
B.2, 7, 5, 6, 4, 3, 9
C.3, 2, 5, 4, 7, 6, 9
D.4, 23, 5, 7, 6, 9
【答案】C
【解析】对于快速排序, 每一趟都会使一个元素位于有序时的位置, 而有序序列为2, 3, 4, 5, 6, 7, 9, 与C 进行对比, 只有9位于它有序的时候的位置, 显然不是第二趟快速排序的结果
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. 直接插入排序
【答案】C
【解析】稳定排序有:插入排序、起泡排序、归并排序、基数排序。不稳定排序有:快速排序、
堆排序、shell 排序。时间复杂度平均为的有:归并排序、堆排序、shell 排序、快速排序。
9． 有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（ ）。
A.60
和确认序
号的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是