2017年江苏省培养单位苏州纳米技术与纳米仿生研究所866计算机原理之数据结构考研题库
● 摘要
一、选择题
1． 下列排序算法中元素的移动次数和关键字的初始排列次序无关的是（ ）。
A. 直接插入排序
B. 起泡排序
C. 基数排序
D. 快速排序
【答案】C
【解析】C 项，基数排序是采用分配和收集实现的，不需要进行关键字的比较。ABD 三项都依赖关键字的比较，不同的初始排列次序下元素移动的次数有很大变化，最好情况元素正序，则不用移动，最坏情况元素反序，则需要移动n （n-1） /2次（为元素个数）。
2． 下列选项中，能缩短程序执行时间的措施是（ ）。
I. 提高CPU 时钟频率
II. 优化数据通路结构
III. 对程序进行编译优化
A. 仅I 和II
B. 仅I 和III
C. 仅II 和III
D.I 、II 和III
【答案】D
【解析】一般说来，CPU 时钟频率（主频）越高，CPU 的速度就越快；优化数据通路结构，可以有效提高计算机系统的吞吐量；编译优化可得到更优的指令序列。所以I 、II 、III 都是有效措施。
3． 若磁盘转速为7200转/分，平均寻道时间为8ms , 每个磁道包含1000个扇区，则访问一个扇区的平均存取时间大约是（ ）。 A. B. C. D.
【答案】B
【解析】磁盘的平均寻址时间包括平均寻道时间和平均等待时间。平均寻道时间为8ms , 平均等待时间与磁盘转速有关，
为
第 2 页，共 61 页 磁盘的存取一个扇区的时间为
因此总的时间为：
4． 下列有关
B. 接口的叙述中错误的是：（ ） 端口
端口 A. 状态端口和控制端口可以合用同一寄存器 接口中CPU 可访问寄存器，称为C. 采用独立编址方式时，
【答案】D
【解析】采用统一编码方式，存储器和端口共用统一的地址空间，不需要专用的指令，任何对存储器数据进行操作的指令都可用于端口的数据操作。所以D 错误
5． 有个分支结点的满二叉树的深度是（ ）。 A. B. C. D.
【答案】C
【解析】满二叉树的结点总数=分支的结点总数+非分支的结点总数。由于此树为满二叉树，所以非分支的结点总数为1，所以满二叉树共有个结点，所以满二叉树的深度为
6． 在OSI 参考模型中，直接为会话层提供服务的是（ ）
A. 应用层
B. 表示层
C. 传输层
D. 网络层
【答案】C
【解析】OSI 参考模型中，下层直接为上层提供服务，而会话层的下层为传输层。
7． 若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（ ）。
A.257
B.258
C.384
D.385
【答案】C
【解析】由
：
_则和
__可知
，
即显然
384, 所以二叉树的叶结点个数是384。还可以根据完全二叉树的另一个 端口地址和主存地址可能相同 D. 采用统一编址方式时，CPU 不能用访存指令访问性质：最后一个分支结点的序号为[768/2], 故非叶子结点数为384, 而叶子结点的个数为768-384=384。（[x]表示不大于x 的最大整数，比如[3.14] =3）。
第 3 页，共 61 页
8． 某CPU 主频为1.03GHz , 采用4级指令流水线，每个段的执行需要1个时钟周期。假定CPU
执行了100条指令，在其执行过程中没有发生任何流水线阻塞，此时流水线的吞吐率为（ ）
A.
B.
C.
D.
【答案】C
【解析】采用4级流水线执行100条指令，在执行过程中共用
条指令/秒，故答案为C 。
9． 下面关于求关键路径的说法不正确的是（ ）。
A. 求关键路径是以拓扑排序为基础的
B. —个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C. 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D. 关键活动一定位于关键路径上
【答案】C
【解析】一个事件的最迟开始事件是这个事件能够拖到的最晚时间，从这个时刻开始做完这个事件不影响其后续事件的开始时间。
10．串是一种特殊的线性表，其特殊性体现在（ ）。
A. 数据元素是一个字符
B. 可以顺序存储
C. 数据元素可以是多个字符
D. 可以链接存储
【答案】A
11．对任意一棵树，设它有n 个结点，这n 个结点的度数之和为（ ）。
A.n B. C. D.
【答案】C
【解析】每个结点（除根节点外）都是一个分支，即所有结点的度数之和等于分支个数等于总的结点数减一，即n-1。
个时钟周期。CPU 的主频是1.03GHz , 也就是说每秒钟有1.03G 个时钟周期。流水线的吞吐率
为条指令/秒 条指令/秒 条指令/秒 条指令/秒
第 4 页，共 61 页
相关内容
相关标签