2018年北京航空航天大学408计算机学科专业基础综合[专业学位]之数据结构考研核心题库
● 摘要
一、填空题
1．
【答案】5
2． 执行顺序查找时，存储方式可以是_____，折半查找时，要求线性表_____，分块查找时要求线性表_____，而哈希表的查找，要求线性表的存储方式是_____。
【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储
3． 对n 个记录的表
【答案】n (n－1) /2
【解析】第一次需要n －1次比较，第i 此需要n －i 此比较，所以共需要。
4． 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。
【答案】n ; n+1
【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。
5． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度, 当它为一棵_____时，具有最大高度。
【答案】完全；只有一个叶结点的二叉树
进行简单选择排序，所需进行的关键字间的比较次数为_____。 ＝_____
二、单项选择题
6． 某计算机的指令流水线由4个功能段组成，指令流经各功能段的时间(忽略各功能段之间的缓存时间) 分别为90ns 、80ns 、70ns 和60ns ，则该计算机的CPU 时钟周期至少是（ ）.
A.90ns
B.80ns
C.70ns
D.60ns
【答案】A
【解析】对于各功能段执行时间不同的指令流水线，计算机的CPU 时钟周期应当以最长的功能段执行时间为准.
7． 若X 是后序线索二叉树中的叶结点, 且X 存在左兄弟结点Y , 则X 的右线索指向的是 （ ）
A.X 的父结点
B. 以Y 为根的子树的最左下结点
C.X 的左兄弟结点Y
D. 以Y 为根的子树的最右下结点
【答案】A
【解析】根据后续线索二叉树的定义, X 结点为叶子结点且有左兄弟, 那么这个结点为右孩子结点, 利用后续遍历的方式可知X 结点的后继是其父结点, 即其右线索指向的是父结点。
8． 元素a , b , c , d , e 依次进入初始为空的栈中, 若元素进栈后可停留、可出栈, 直到所有元素都出栈, 则在所有可能的出栈序列中, 以元素d 开头的序列个数是（ ）。
A.3
B.4
C.5
D.6
【答案】B
【解析】d 首先出栈后的状态如下图所示。
此时可有以下4种操作:
(1)e进栈后出栈, 出栈序列为decba 。
(2)c出栈, e 进栈后出栈, 出栈序列为dceba 。
(3)cb出栈, e 进栈后出栈, 出栈序列为dcbea 。
(4)cba出栈, e 进栈后出栈, 出栈序列为dcbae 。
9． 对序列{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。
10．假定变量i 、f 和d 的数据类型分为int 、float 和double(int用补码表示, float 和double 分别用IEEE754单精度和双精度浮点数格式表示) , 已知
器中执行下列关系表达式, 则结果为“真”的是（ ）。
(Ⅰ)
(Ⅱ)
(Ⅲ)
(Ⅳ)
A. 仅Ⅰ和Ⅱ
B. 仅Ⅰ和Ⅲ
C. 仅Ⅱ和Ⅲ
D. 仅Ⅲ和Ⅳ
【答案】B
【解析】数据类型不同的数据在运算之前需要进行数据类型的转换。Ⅱ中, f 的数据类型从float 转换为int 时, 小数点后面4位会丢失, 故Ⅱ的结果不为真; Ⅳ中, d+f时需要对阶, 对阶后f 的尾数有效位被舍去而变为0, 故d+f仍然为d , 再减去d 后结果为0, 故Ⅳ的结果也不为真。
Ⅰ和Ⅱ进行数据类型的转换的时候并没有改变其值。
11．下列选项中, 会导致用户进程从态切换到内核的操作是（ ）
Ⅰ. 整数除以零
Ⅱ.sin （ ）函数调用
Ⅲ.read 系统调用
A. 仅Ⅰ、Ⅱ
B. 仅Ⅰ、Ⅲ
C. 仅Ⅱ、Ⅲ
D. Ⅰ、Ⅱ和Ⅲ
【答案】B
【解析】对于Ⅰ, 系统发生异常, 需要进入内核态由操作系统进行处理, 而read 系统调用函数也是在内核态执行, sin （ ）就是普通的用户函数, 在用户态执行, 故答案为C 。
12．假定基准程序A 在某计算机上的运行时间为100秒, 其中90秒为CPU 时间, 其余为若CPU 速度提高
A.55秒
B.60秒
C.65秒
D.70秒
【答案】D 。
。若在32位机 时间。, 速度不变, 则运行基准程序A 所耗费的时间是（ ）。