2018年武汉科技大学生物医学研究院856数据结构(C语言版)考研核心题库
● 摘要
一、单项选择题
1． 在双向链表指针P 的结点前插入一个指针q 的结点操作是（ ）。
A.p ﹣＞llink ＝q ；q ﹣＞Rlink ＝p ；p ﹣＞Llink ﹣＞Rlink ＝q ；q ﹣＞Llink ＝q ；
B.p ﹣＞llink ＝q ；p ﹣＞Llink ﹣＞Rlink ＝q ；q ﹣＞Rlink ＝p ；q ﹣＞Llink ＝p ﹣＞Llink ；
C.q ﹣＞Rlink ＝p ；q ﹣＞Llink ＝p ﹣＞L1ink ；p ﹣＞L1ink ﹣＞Rlink ＝q ；p ﹣＞Llink ＝q ；
D.q ﹣＞llink ＝p ﹣>llink；q ﹣＞Rlink ＝q ；p ﹣＞llink ＝q ；p ﹣＞llink ＝q ；
【答案】C
2． 下列选项中, 会导致用户进程从态切换到内核的操作是（ ）
Ⅰ. 整数除以零
Ⅱ.sin （ ）函数调用
Ⅲ.read 系统调用
A. 仅Ⅰ、Ⅱ
B. 仅Ⅰ、Ⅲ
C. 仅Ⅱ、Ⅲ
D. Ⅰ、Ⅱ和Ⅲ
【答案】B
【解析】对于Ⅰ, 系统发生异常, 需要进入内核态由操作系统进行处理, 而read 系统调用函数也是在内核态执行, sin （ ）就是普通的用户函数, 在用户态执行, 故答案为C 。
3． 下列有关浮点数加减运算的叙述中, 正确的是（ ）。
Ⅰ. 对阶操作不会引起阶码上溢或下溢
Ⅱ. 右规和尾数舍入都可能引起阶码上溢
Ⅲ. 左规时可能引起阶码下溢
Ⅳ. 尾数溢出时结果不一定溢出
A. 仅Ⅱ Ⅲ
B. 仅Ⅰ Ⅱ Ⅳ
C. 仅Ⅰ Ⅲ Ⅳ
D. Ⅰ Ⅱ ⅢⅣ
【答案】D
【解析】浮点数的加减运算步骤包括:①对阶, 使两个操作数的小数点位置对齐, 阶码小的尾数
右移, 可能产生溢出, 但是阶码不会溢出; ②尾数求和, 将对阶后的尾数按定点数加(减) 运算规则运算; ③规格化, 包括左规和右规, 左规时阶码减少, 可能出现阶码下溢, 而右规时, 阶码增加可能出现阶码上溢; ④舍入, 该过程可能需要右规调整, 因此可能出现阶码上溢; ⑤溢出判断, 浮点数的溢出与否是由阶码的符号决定的, 而不是由尾数溢出判断的, 因此尾数溢出时结果不一定溢出。因此Ⅰ Ⅱ Ⅲ Ⅳ均正确。
4． 执行（ ）操作时，需要使用队列做辅助存储空间。
A. 查找哈希(Hash)表
B. 广度优先搜索网
C. 前序(根) 遍历二叉树
D. 深度优先搜索网
【答案】B
【解析】查找哈希表不需要辅助存储空间，前序遍历二叉树和深度优先搜索网需要使用栈做辅助存储空间，广度优先搜索树需要队列做辅助存储空间。
5． 假定编译器规定int 和short 类型长度分别为32位和16位, 执行下列C 语言语句:
;
A.00007FFAH
B.0000FFFAH
C.FFFF7FFAH
D.FFFFFFFAH
【答案】B 。
X 和y 均为无符号数, 其中X 为16位, y 为32位, 将16位无符号数转化成32位无符【解析】
号数, 前面要补零。因为X=65530=FFFAH, 所以y=0000FFFAH。
6． 先序序列为a , b , c , d 的不同二叉树的个数是（ ）。
A.13
B.14
C.15
D.16
【答案】B
【解析】二叉树的先序遍历定义为:若二叉树为空, 则空操作; 否则, 访问根节点, 然后先序遍历左子树, 最后先序遍历右子树。本题中, 结点a 为二叉树的根节点, 左右子树的先序遍历可能存在下面四种情况:
①左子树为空, bcd 为右子树; ②b 为左子树, cd 为右子树; ③bc 为左子树, d 为右子树; ④bcd 为左子树, 右子树为空。
然后将左右子树继续分解, 如第①种情况的右子树先序遍历(bcd)可能有:
A. 左子树为空, 右子树为cd ;
b. 左子树为c , 右子树为d ;
:得到y 的机器数为（ ）。
c. 左子树为cd , 右子树为空。
按照这种方法继续分解左右子树, 直到不能再分解为止, 可得第①和④种情况各包含5种不同情况, 第②和③种情况各包含2种情况, 因此总共有14种不同的二叉树。
7． 处理外部中断时, 应该由操作系统保存的是（ ）。
A. 程序计数器(PC)的内容
B. 通用寄存器的内容
C. 快表(TLB)的内容
D.Cache 中的内容
【答案】B
【解析】外部中断处理过程首先要保护现场, 使得中断处理完后能够恢复程序的状态继续执行。保护现场有两个含义:
①由中断隐指令保存程序的断点(程序计数器) ;
②由中断服务程序保存通用寄存器和状态寄存器的内容。中断服务程序是操作系统的一部分。
8． 将两个各有N 个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。
A.N
B.2N －1
C.2N
D.N －1
【答案】A
【解析】归并排序基本思想:归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。归并排序最好情况下的复杂度为O(n)。
9． 假定基准程序A 在某计算机上的运行时间为100秒, 其中90秒为CPU 时间, 其余为若CPU 速度提高
A.55秒
B.60秒
C.65秒
D.70秒
【答案】D 。
CPU 速度提高50%, 即CPU 性能提高比为【解析】, 改进之后的CPU 运行时间秒。速度不变, 仍维持10秒, 所以运行基准程序A 所耗费的时间为70秒。
10．对一组数据(2, 12, 16, 88, 5, 10) 进行排序, 若前三趟排序结果如下:
第一趟:2, 12, 16, 5, 10, 88
时间。, 速度不变, 则运行基准程序A 所耗费的时间是（ ）。