2018年河北大学计算机科学与技术学院893数据结构(含C语言)(计)[专业硕士]考研基础五套测试题
● 摘要
一、单项选择题
1． 下列措施中, 能加快虚实地址转换的是1增大快表(TLB)2让页表常驻内存3增大交换区（ ）
A. 仅1
B. 仅2
C. 仅1, 2
D. 仅2, 3
【答案】C
【解析】加大快表能增加快表的命中率, 即减少了访问内存的次数; 让页表常驻内存能够使cpu 不用访问内存找页表, 从也加快了虚实地址转换。而增大交换区只是对内存的一种扩充作用, 对虚实地址转换并无影响
2． 下列关于SMTP 协议的叙述中, 正确的是（ ）
Ⅰ. 只支持传输7比特ASC Ⅱ码内容
Ⅱ. 支持在邮件服务器之间发送邮件
Ⅲ. 支持从用户代理向邮件服务器发送邮件
Ⅳ. 支持从邮件服务器向用户代理发送邮件
A. 仅Ⅰ、Ⅱ和Ⅲ
B. 仅Ⅰ、Ⅱ和Ⅳ
C. 仅Ⅰ、Ⅲ和Ⅳ
D. 仅Ⅱ、Ⅲ和Ⅳ
【答案】A
【解析】根据下图可知, SMTP 协议支持在邮件服务器之间发送邮件, 也支持从用户代理向邮件服务器发送信息。SMTP 协议只支持传输7比特的ASC Ⅱ码内容
图
3． 在下列存储形式中，哪一个不是树的存储形式？（ ）
A. 双亲表示法
B. 孩子链表表示法
C. 孩子兄弟表示法
D. 顺序存储表示法
【答案】D
【解析】顺序存储就是利用一段连续的存储单元依次存储线性表中的元素。树中某个结点的孩子可以有多个，这就意味着，无论用哪种顺序将树中所有的结点存储到数组中，结点的存储位置都无法直接反映逻辑关系。因此简单的顺序存储表示不能满足树的基本要求。常用的三种树的表示法为:双亲表示法、孩子链表示法、孩子兄弟表示法。
4． 下列选项中, 不会引起指令流水线阻塞的是（ ）。
A. 数据旁路(转发)
B. 数据相关
C. 条件转移
D. 资源冲突
【答案】A
【解析】由于采用流水线方式, 相邻或相近的两条指令可能会因为存在某种关联, 后一条指令不能按照原指定的时钟周期运行, 从而使流水线断流。有三种相关可能引起指令流水线阻塞:
①结构相关, 又称资源相关;
②数据相关;
③控制相关, 又称指令相关, 主要由转移指令引起。
5． 下列选项中, 能缩短程序执行时间的措施是（ ）。
Ⅰ. 提高CPU 时钟频率
Ⅱ. 优化数据通路结构
Ⅲ. 对程序进行编译优化
A. 仅Ⅰ和Ⅱ
b. 仅Ⅰ和Ⅲ
c. 仅Ⅱ和Ⅲ
d. Ⅰ、Ⅱ和Ⅲ
【答案】D
【解析】一般说来, CPU 时钟频率(主频) 越高, CPU 的速度就越快; 优化数据通路结构, 可以有效提高计算机系统的吞吐量; 编译优化可得到更优的指令序列。所以Ⅰ、Ⅱ、Ⅲ都是有效措施。
6． 假设某计算机按字编址, Cache 有4个行, Cache 和主存之间交换的块大小为1个字。若Cache 的内容初始为空, 采用2路组相联映射方式和LRU 替换算法, 当访问的主存地址依次为0, 4, 8, 2, 0, 6, 8, 6, 4, 8时, 命中Cache 的次数是（ ）。
A.1
B.2
C.3
D.4
【答案】C 。
【解析】Cache 有4个行, 2路组相联, 即Cache 被分成2组, 每组2行。主存地址为0〜1、4〜5、8〜9可映射到第0组Cache 中, 主存地址为2〜3、6〜7可映射到第1组Cache 中。Cache 初始为空, 采用LRU 替换算法, 当访问主存的10个地址依次为0, 4, 8, 2, 0, 6, 8, 6, 4, 8时, 命中Cache 的次数共有3次, 分别发生在第7、8和10步时。
7． 下列二叉排序树中查找效率最高的是（ ）。
A. 平衡二叉树
B. 二叉查找树
C. 没有左子树的二叉排序树
D. 没有右子树的二叉排序树
【答案】A
【解析】平衡二叉树的左子树和右子树的深度之差的绝对值不超过1。这就保证了二叉树的深度是级别的。二叉查找树或者是一颗空数；或者是具有下列性质的二叉树:①若左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若右子树不空，则右子树上所有结点的值均大于它的根结点的值；③左、右子树也分别为二叉排序树。B 、C 、D 三项均不能保证左子树和右子树的深度之差的绝对值不超过1, 甚至很大，因此查找效率低。
8． —次总线事物中, 主设备只需给出一个首地址, 从设备就能从首地址开始的若干连续单元格读出或写入的个数, 这种总线事务方式称为（ ）
A. 并行传输
B. 串行传输
C. 突发
D. 同步
【答案】C
【解析】猝发数据传输方式:在一个总线周期内传输存储地址连续的多个数据字的总线传输方式
9． 二叉树在线索化后，仍不能有效求解的问题是（ ）。
A. 前序线索二叉树中求前序后继