2018年延安大学数学与计算机科学学院812数据结构与程序设计之数据结构考研核心题库
● 摘要
一、单项选择题
1． 某计算机处理器主频为50MHz , 采用定时查询方式控制设备A 的
则CPU 用于设备A 的
A. B. C. D.
【答案】C , 查询程序运行一次所用的时钟周期数至少为500。在设备A 工作期间, 为保证数据不丢失, 每秒需对其查询至少200次, 的时间占整个CPU 时间的百分比至少是（ ）。 【解析】对于设备A , 每秒中查询至少200次, 每次查询至少500个时钟周期, 总的时钟周期数为100000, 又因为处理器主频为50MHz 。所以CPU 用于设备A 的的时间占整个CPU 时间的百分比至少为100000/50。
2． 在含有n 个关键字的小根堆(堆顶元素最小) 中，关键字最大的记录有可能存储在（ ）位置上。 A. B.
C.1 D.
【答案】D
【解析】小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于Ln/2」的结点上。
3． 由3个结点可以构造出多少种不同的有向树？（ ）
A.2
B.3
C.4
D.5
【答案】A
【解析】满足以下条件的有向图称为有向树:①有且仅有一个结点的入度为0；②除树根外结点的入度为1；③从树根到任一结点有一有向通路。
4． 设栈S 和队列Q 的初始状态均为空，元素a ，b ，c ，d ，e ，f ，g 依次进入栈S. 若每个元素出
d ，c ，f ，e ，a ，g ，. 栈后立即进入队列Q ，且7个元素出队的顺序是b ，则找S 的容量至少是（ ）
A.1
B.2
C.3
D.4
【答案】C
【解析】由于栈具有先进后出的特性，队列具有先进先出的特性，出队顺序即为人队顺序.. 在本题中，每个元素出栈S 后立即进入队列Q ，出栈顺序即为入队顺序，所以本题中队列的作用形同虚设，根据题意出队顺序即为出栈顺序. 根据出桟顺序可以分析各个元素进出栈的过程：第一个出栈元素为b ，表明栈内还有元素a ，b 出栈前的深度为2；第二个出栈元素为d ，栈内元素为a 和c ，d 出栈前的深度为3；c 出栈后，剩余元素为a ，c 出栈前的深度为2；f 出栈后，剩余元素为a 和e ，f 出栈前的深度为3；e 出栈后，剩余元素为a ，e 出栈前的深度为2；a 出栈后，无剩余元素，a 出栈前的深度为1；g 出栈后，无剩余元素，g 出栈前的深度为1. 所以栈容量至少是3.
5． float 型数据通常用IEEE754单精度浮点数格式表示。若编译器将float 型变量x 分配在一个32位浮点寄存器FR1中,
且
A.C1040000H
B.C2420000H
C.C1840000H
D.C1C20000H
【答案】A , 则FR1的内容是（ ）。
【解析】首先将十进制数转换为二进制数-1000.01,
接着把它写成规格化形式
IEEE754标准) , 然后计算阶码的移码=偏置值+
阶码真值(按, 最后短浮点数代码:数符位=1, 阶码=10000010, 尾数00001000000000000000000, 写成十六进制为C1040000H 。选项D 是一个很容易被误选的选项, 其错误在于没有考虑IEEE754标准中隐含最高位1的情况, 偏置值是128。
6． 已知序列25, 13, 10, 12, 9是大根堆, 在序列尾部插入新元素18, 将其再调整为大根堆, 调整过程中元素之间进行的比较次数是（ ）。
A.1
B.2
C.4
D.5
【答案】B
【解析】对堆插入或删除一个元素, 有可能不满足堆的性质, 堆被破坏, 需要调整为新堆。
(1)为原堆,
(2)为插入18后,
(3)比较10与18, 交换后,
(4)比较25与18, 不交换, 即为调整后的新的大根堆。
因此调整过程中元素之间进行的比较次数为2。
7． 执行（ ）操作时，需要使用队列做辅助存储空间。
A. 查找哈希(Hash)表
B. 广度优先搜索网
C. 前序(根) 遍历二叉树
D. 深度优先搜索网
【答案】B
【解析】查找哈希表不需要辅助存储空间，前序遍历二叉树和深度优先搜索网需要使用栈做辅助存储空间，广度优先搜索树需要队列做辅助存储空间。
8． 若一个有向图具有拓扑排序序列，那么它的邻接矩阵必定为（ ）。
A. 对称矩阵
B. 稀疏矩阵
C. 三角矩阵
D. —般矩阵
【答案】C
【解析】在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为改图的一个拓扑排序:①每个顶点出现且出现一次；②若顶点在序列中排在顶点B 的前面，则在图
中不存在从顶点B 到顶点A 的路径。由拓扑排序的性质知，有向图的邻接矩阵必定为三角矩阵。
9． 一个TCP 连接总是以1KB 的最大段发送TCP 段，发送方有足够多的数据要发送。当拥塞窗口为16KB 时发生了超时，如果接下来的4个RTT(往返时间) 时间内的TCP 段的传输都是成功的，那么当第4个RTT 时间内发送的所有TCP 段都得到肯定应答时，拥塞窗口大小是（ ）。
A.7KB
B.8KB
C.9KB
D.16KB
【答案】C
【解析】回顾TCP 流量控制和拥塞控制(慢启动) 的知识点，从第一个MSS 开始，每次发送成