2017年河北大学电子信息工程学院929数据结构(电)考研题库
● 摘要
一、选择题
1． 下列选项中，描述浮点数操作速度指标的是（ ）。
A.MIPS B.CPI C.IPC
D.MFLOPS 【答案】D
【解析】
表示每秒执行多少百万次浮点
. 表示每秒执行多少百万条指令。对于一个给定的程序，
MIPS 定义为
这里所说的指令一般是指加、减运算这类短指令。
就是每条指令执行所用的时钟周期数。由于不同指令的功能不同，
造成指令执行时间不同，也即指令执行所用的时钟数不同，所以CPI 是一个平均值。
每个时钟周期执行的指令数。
2． —
组记录的关键码为
准得到的一次划分结果为（ ）。
【答案】C
【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。
第一次比较：46比84小，不交换； 第二次比较：40比46小，交换，此时为第三次比较：46比79小，交换，此时为第四次比较：38比46小，交换，此时为第五次比较：56比46大，交换，此时为一次划分结束。
则利用快速排序的方法，以第一个记录为基
运算，用来描述计算机的浮点运算速度，适用于衡量处理机的性能。
3． 排序算法的稳定性是指（ ）。
A. 经过排序之后，能使值相同的数据保持原顺序中的相对位置不变 B. 经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变 C. 算法的排序性能与被排序元素的数量关系不大 D. 算法的排序性能与被排序元素的数量关系密切 【答案】A
【解析】假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，
且在之前，而在排序后的序列中，仍在
之前，则称这种排序算法是稳定的；否则称为不稳定的。
4． 下列选项中，在用户态执行的是（ ）。
A. 命令解释程序 B. 缺页处理程序 C. 进程调度程序 D. 时钟中断处理程序 【答案】A
【解析】题目是问用户态执行，可见是有关操作系统基本概念的问题。四个选项中，用户唯一能面对的是命令解释程序，缺页处理程序和时钟中断都属于中断，在核心态执行，而进城调度属于系统调用在核心态执行。只有命令解释程序属于命令接口，可以运行在用户态，接受用户的命令操作控制。
5． 给定二叉树如下图所示。设N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树，若遍历后的节点序列为3，1，7，5，6，2，4，则其遍历方式是（ ）
A.LRN B.NRL C.RLN
D.RNL
图
【答案】D
【解析】对“二叉树”而言，一般有三条搜索路径； ①先上后下的按层次遍历；
②先左（子树）后右（子树）的遍历； ③先右（子树）后左（子树）的遍历；
其中第1种路径的搜索方式就是常见的层次遍历，第2种搜索路径方式包括常见的NLR 、中序遍历LNR 、后序遍历LRN , 第3种搜索路径方式则是不常使用的NRL 、RNL 、RLN 。本题考查的是第3种搜索路径方式的一种情况。根据遍历的序列以及树的结构图，可以分析出该遍历的顺序是先右子树再跟结点最后左子树，故答案为D 。
6． 某同步总线采用数据线和地址线复用方式。其中地址数据线有8根，总线时钟频率为66MHZ , 每个时钟同期传送两次数据。（上升沿和下降沿各传送一次数据）该总线的最大数据传输率是（总线带宽）（ ） ：
A. B. C. D. 【答案】C
【解析】总线带宽=总线工作频率X （总线宽度/8）, 由于地址线与数据线复用，所以在两次数据传输过程中总线上数据一共传输了8次，那么总线带宽为
7． 下列关于USB 总线特性的描述中，错误的是（ ）。
A. 可实现外设的即插即用和热插拔 B. 可通过级联方式连接多台外设 C. 是一种通信总线，可连接不同外设 D. 同时可传输2位数据，数据传输率高 【答案】D 。
【解析】USB 总线即通用串行总线，它的特点有：（1）即插即用；（2）热插拔；（3）有很强的链接能力能将所有外设链接起来，且不损失带宽；（4）有很好的可扩展性；（5）高速传输，速度可达480Mbps 。所有A , B, C都符合USB 总线的特点。对于选项D , USB 是串行总线，不能同时传输两位数据，所以答案为D 。
8． 下列选项中，对正确接收到的数据帧进行确认的MAC 协议是（ ）。
A.CSMA B.CDMA C.CSMA/CD D.CSMA/CA 【答案】D
【解析】可采用排除法。CDMA 是码分多址复用，是物理层的内容；CSMA/CD即带冲突检测的载波监听多 路访问，接收方并不需要确认；CSMA/CD是CSMA 的加强版，故CSMA 也无确定；CSMA/CD是802.11中的 协议，其利用ACK 信号来避免冲突的发生，也就是说，只有当 客户端收到网络上返回的ACK 信号后才确认送 出的数据已经正确到达目的地址，因此答案是D 。
所以选C