2018年福建师范大学教育学院620计算机基础之数据结构考研核心题库
● 摘要
一、单项选择题
1． 某机器字长16位，主存按字节编址，转移指令采用相对寻址，由两个字节组成，第1字节为操作码字段，第2字节为相对位移量字段. 假定取指令时，每取一个字节PC 自动加1. 若某转移指令所在主存地址为2000H ，相对位移量字段的内容为06H ，则该转移指令成功转移后的目标地址是（ ）.
A.2006H B.2007H C.2008H D.2009H 【答案】C
【解析】相对寻址方式的有效地址EA ＝(PC)＋D ，其中PC 为程序计数器，D 为相对偏移量. 主存按字节编址，取指令时，每取一个字节PC 值自动加1. 由于转移指令由两个字节组成，取出这条转移指令之后的PC 值自动加2，为2002H ，故转移的目标地址为2002H ＋06H ＝2008H.
2． 求整数阶乘的算法如下, 其时间复杂度是（ ）。
A. B.0(n) C.
2
D.O(n)
【答案】B 。
【解析】设fact(n)的运行时间函数是T(n)。
该函数中语句①的运行时间是0(1), 语句②的运行时间是算的时间。
因此, 当则,
, 其中O(1)为乘法运
时
, ;
。
当11>1时,
即fact(n)的时间复杂度为O(n)。
通过上表可以看出, 显然转换过程中同时保存在栈中的操作符的最大个数是5。
3． 在含有n 个关键字的小根堆(堆顶元素最小) 中，关键字最大的记录有可能存储在（ ）位置上。
A. B. C.1 D. 【答案】D
【解析】小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于Ln/2」的结点上。
4． 某同步总线采用数据线和地址线复用方式。其中地址数据线有8根, 总线时钟频率为66MHZ , 每个时钟同期传送两次数据。(上升沿和下降沿各传送一次数据) 该总线的最大数据传输率是(总线带宽) :（ ）
A.132MB/S B.264MB/S C.528MB/S D.1056MB/S 【答案】C
【解析】总线带宽=总线工作频率X(总线宽度/8), 由于地址线与数据线复用, 所以在两次数据传输过程中总线上数据一共传输了8次, 那么总线带宽为
5． 下列叙述中，不符合m 阶B 树定义要求的是（ ）.
A. 根结点最多有m 棵子树 B. 所有叶结点都在同一层上 C. 各结点内关键字均升序或降序排列 D. 叶结点之间通过指针链接 【答案】D 【解析】B 树就是指
树.
根据
树的定义，m
阶
树中每个结点最多有m 个分支，因此，
树
根结点最多有m 棵子树，A 项正确；
树中所有叶结点都在最底层，位于同一层，B 项正确；
, 所以选C
结点内各关键字互不相等且有序排列，C 项正确. 但是，所有叶子结点之间通过指针链接，是
的定义，而树中没有. 因此，D 项是错误的.
6． 设系统缓冲区和用户工作均采单, 从外读入1个数据块到系统缓冲区的时间为100, 从系统缓冲区读入1个数据块到用户工作区的时间为5, 对用户工作区中的1个数据块行分析的时间为90(如下图所示) 。进程从外设读入并分析2个数据块的最短时间是（ ）
图
A.200 B.295 C.300 D.390