2017年郑州大学产业技术研究院945软件工程专业基础综合之数据结构考研题库
● 摘要
一、选择题
1． float 类型（即IEEE754单精度浮点数格式）能表示的最大正整数是（ ）。
A.
B.
C.
D.
【答案】D 。
【解析】IEEE754单精度浮点数尾数采用隐藏位策略的原码表示，且阶码用移码表示的浮点数。规格化的短 浮点数的真值为：
故float 类型能表示的最大整数是
2． 下列选项中，在用户态执行的是（ ）。
A. 命令解释程序 B. 缺页处理程序 C. 进程调度程序 D. 时钟中断处理程序 【答案】A
【解析】题目是问用户态执行，可见是有关操作系统基本概念的问题。四个选项中，用户唯一能面对的是命令解释程序，缺页处理程序和时钟中断都属于中断，在核心态执行，而进城调度属于系统调用在核心态执行。只有命令解释程序属于命令接口，可以运行在用户态，接受用户的命令操作控制。
3． 若平衡二叉树的高度为6, 且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为（ ）。
A.12 B.20 C.32 D.33
【答案】B 。
【解析】本题题目的实际问题是，具有6层结点的平衡二叉树含有最少的结点数是多少。表示深度为h 的平衡二叉树中含有的最少结点数，有
由此可得
对应的平衡二叉树如下图所示。
S 为符号位，E 的取值为
f 为23位；
4． 某系统有n 台互斥使用的同类设备，3个并发进程需要3, 4, 5台设备，可确保系统不发生死锁的设备数n 最小为（ ）
A.9 B.10 C.11 D.12
【答案】B
【解析】2+3+4+1 = 10
5． 下列关于管道（Pipe ）通信的叙述中，正确的是（ ）
A. —个管道可实现双向数据传输 B. 管道的容量仅受磁盘容量大小限制
C. 进程对管道进行读操作和写操作都可以被阻塞 D. —个管道只能有一个读写进程或一个写进程对其操作 【答案】C
【解析】只有写进程才能对管道写入数据，读进程对管道进行读取数据，只能半双工通信，即某一时刻只能单向传输。管道为空，则读操作被堵塞，而如果有写操作对管道进行写的话那就要堵塞了。那么C 正确
6． n 个结点的完全有向图含有边的数目（ ）。
A.n*n
B.n （n+l） C.n/2
D.n*（n-l ）
【答案】D
【解析】在有向图中，如果任意两个顶点之间都存在边，则称为有向完全图。顶点个数为n 的无向图，最多有为n （n-l ）。
条边。如是有向图，需要在无向图的最多边的基础上乘以2，则
7． 有向带权图如题图所示，若采用迪杰斯特拉（Dijkstra ）算法求从源点a 到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b ，第二条最短路径的目标顶点是c ，后续得到的其余各最短路径的目标顶点依次是（ ）。
题图有向带权图
A.d , e , f
B.e , d , f C.f , d , e D.f , e , d 【答案】C 。
【解析】本题主要考查Dijkstra 算法的思想和解题步骤。题目执行算法过程中各步的状态如下表所示。
执行Dijkstra 算法过程中各步的状态表，故后续目标顶点依次为f ，d , e 。
8． 设哈希表
长
哈希函
数
表中已有4个结点
：其余地址为空，如用二次探测
再哈希法解决冲突，关键字为49的结点的地址是（ ）。
【答案】D
【解析】15，38，61，84用哈希函数为5，发生冲突，用二次探测再散列法解决冲突：
仍然发生冲突。
仍然发生冲突。
不再发生冲突。
9． 算法的计算量的大小称为计算的（ ）。
A. 效率
计算后得地址：4，5，6，7。49计算后