2018年东北财经大学计算机应用技术806计算机综合之数据结构考研核心题库
● 摘要
一、单项选择题
1． 下列网络设备中，能够抑制广播风暴的是（ ）.
(1)中继器
(2)集线器
(3)网桥
(4)路由器
A. 仅(1)和(2)
B. 仅(3)
C. 仅(3)和(4)
D. 仅(4)
【答案】D
【解析】中继器和集线器工作在物理层，不能抑制网络风暴. 为了解决冲突域的问题，提高共享介质的利用率，通常利用网桥和交换机来分隔互联网的各个网段中的通信量，以建立多个分离的冲突域. 但是，当网桥和交换机接收到一个未知转发信息的数据帧时，为了保证该帧能被目的结点正确接收，将该帧从所有的端口广播出去. 于是可以看出，网桥和交换机的冲突域等于端口的个数，广播域为1. 因此网桥不能抑制网络风暴.
2． 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。
3． 每个结点的度或者为0或者为2的二叉树称为正则二叉树。n 个结点的正则二叉树中有（ ）个叶子。 A.
B.
C.
D.
【答案】D
【解析】二叉树结点总数n ＝n 0＋n 1＋n 2(n0，n 1，n 2分别代表度为0，度为1，度为2的结点数) 。又在非空二叉树中:n 0＝n 2＋l ，且本题所给树为正则二叉树，n 1＝0，所以n ＝2*n0﹣l ，因此n 1＝(n+1)/2。
4． 某机器有一个标志寄存器, 其中有进位/借位标志CF 、零标志ZF 、符号标志SF 和溢出标志OF , 条件转移指令bgt(无符号整数比较大于时转移) 的转移条件是（ ）。
A.CF+OF=0
B.SF+ZF=0
C.CF+ZF=0
D.CF+SF=0
【答案】C
【解析】判断无符号整数A>B成立, 满足的条件是结果不等于0, 即零标志ZF=0, 且不发生进位, 即进位/借位标志CF=0。所以正确选项为C 。其余选项中用到了符号标志SF 和溢出标志OF , 显然可以排除掉。
5． 希尔排序的组内排序采用的是（ ）。
A. 直接插入排序
B. 折半插入排序
C. 快速排序
D. 归并排序
【答案】A
【解析】希尔排序基本思想是:先将整个待排元素序列按某个增量分割成若干个子序列, 在子序列内进行直接插入排序, 然后依次缩减增量再进行排序, 待整个序列中的元素基本有序(增量足够小) 时, 再对全体元素进行一次直接插入排序。
6． 在系统内存中设置磁盘缓冲区的主要目的是（ ）。
A. 减少磁盘次数
B. 减少平均寻道时间
C. 提高磁盘数据可靠性
D. 实现设备无关性
【答案】A
【解析】访问磁盘的开销远远大于访问内存的开销。磁盘缓冲区便是利用主存中的存储空间, 来暂存从磁盘中读出(或写入) 的信息, 频繁使用的一部分磁盘数据和信息, 暂时存放在磁盘缓存中,
可减少访问磁盘的次数。
7． 若无向图中含7个顶点, 则保证图G 在任何情况下都是连通的, 则需要的边数最少是（ ）。
A.6
B.15
C.16
D.21
【答案】C
【解析】要保证无向图G 在任何情况下都是连通的, 即任意变动图G 中的边, G 始终保持连通。首先需要图G 的任意6个结点构成完全连通子图
再添加一条边将第7个结点与, 需条边, 然后连接起来, 共需16条边。本题非常容易错误地选择选项A , 主要原因是对“保证图G 在任何情况下都是连通的”的理解, 分析选项A , 在图G 中, 具有7个顶点6条边并不能保证其一定是连通图, 即有n-1条边的图不一定是连通图。分析选项D , 图G 有7个顶点21条边, 那么图G 一定是无向完全图, 无向完全图能保证其在任何情况下都是连通的, 但是这不符合题目中所需边数最少的要求。
8． 某队列允许在其两端进行入队操作, 但仅允许在一端进行出队操作, 元素a , b , c , d , e 依次入此队列后再进行出队操作, 则不可能得到的出队序列是（ ）。
A.b , a , c , d , e
B.d , b , a , c , e
C.d , b , c , a , e
D.e , c , b , a , d
【答案】C
【解析】根据题意, 队列两端都可以输入数据元素, 但是只能在一端输出数据元素, 这种队列为
输出受限的双端队列。本题解题方法分别判断每个选项如何入队和出队, 从而得出不可能的情况。
假设L 代表从左端入队, R 代表从右端入队, 出队都是从左端L 出。四个选项所给序列的进队操作序列分别为:
选项A.aL(或aR) , bL , cR , dR , eR
选项B.aL(或aR) , bL , cR , dL , eR
选项C. 不可能出现选项
D.aL(或aR) , bL , cL , dR , eL
9． 对一组数据(2, 12, 16, 88, 5, 10) 进行排序, 若前三趟排序结果如下:
第一趟:2, 12, 16, 5, 10, 88
第二趟:2, 12, 5, 10, 16, 88
第三趟:2, 5, 10, 12, 16, 88
则采用的排序方法可能是（ ）。