2018年桂林理工大学信息科学与工程学院878数据结构及程序设计之数据结构考研仿真模拟五套题
● 摘要
一、单项选择题
1． 在一棵度为4的树T 中, 若有20个度为4的结点, 10个度为3的结点, 1个度为2的结点, 10个度为1的结点, 则树T 的叶结点个数是（ ）。
A.41
B.82
C.113
D.122
【答案】B
【解析】根据二叉树的性质3的推广公式:
式, 即
。
树T 的叶子结点的个数是82。
2． 某磁盘的转速为10, 000转/分, 平均寻道时间是6ms , 磁盘传输速率是
为, 读取一个4KB 的扇区所需平均时间约为（ ）
A.9ms B.
C.12ms D.
【答案】B
【解析】磁盘转速是10000转/分钟, 平均转一转的时间是6ms , 因此平均查询扇区的时间是3ms , 平均寻道时间是6ms , 读取4KB
扇区信息的时间为
。
3． 已知循环队列存储在一维数组
的值分别是（ ）。
A.0, 0
B.0, n-1
C.n-1, 0
D.n-1, n-1
【答案】B
【解析】题目要求队列非空时front 和rear 分别指向队头元素和队尾元素, 若初始时队列为空,
第 2 页，共 62 页 可直接在将数据带入公, 磁盘控制器延迟
, 信息延迟的时间为0.2ms ,
总时间为中, 且队列非空时front 和rear 分别指向队头元素和处, 则初始时front 和rear 队尾元素。若初始时队列为空, 且要求第1个进入队列的元素存储在
且要求第1个进入队列的元素存储在A[0]处, 则此时front 和rear 的值都为0。由于进队操作要执
行, 则初始时front 的值为0、rear 的值为n-1。
时间比例 4． 某系统正在执行三个进程P1、P2和P3, 各进程的计算(CPUCPUCPU)时间和
如下表所示。
为提高系统资源利用率, 合理的进程优先级设置应（ ） A. B. C. D.
【答案】B
【解析】为了合理地设置进程优先级, 应该将进程的CPU 利用时间和
答案选B 。
5． 下列关于AOE 网的叙述中，不正确的是（ ）。
A. 关键活动不按期完成就会影响整个工程的完成时间
B. 任何一个关键活动提前完成，那么整个工程将会提前完成
C. 所有的关键活动提前完成，那么整个工程将会提前完成
D. 某些关键活动若提前完成，那么整个工程将会提前完成
【答案】B
【解析】关键路径是指从有向图的源点到汇点的最长路径。某些关键活动提前完成，那么整个工程将会提前完成，但不是任何一个关键活动提前完成，就能保证整个工程将会提前完成。
6． 某容量为256M 的存储器, 由若干4M*8位的DRAM 芯片构成, 该DRAM 芯片的地址引脚和数据引脚总数是:（ ）
A.19
B.22
C.30
D.36
【答案】A
【解析】DREAM 地址线复用, 4M 为2的22次方, 因此除2为11根, 数据线8根。因此地址引脚和数据引脚总数为19根
7． 在有向图G 的拓扑序列中，若顶点在顶点之前，则下列情形不可能出现的是（ ）。
A.G 中有弧
第 3 页，共 62 页 时间做综合考虑, 故
B.G 中有一条从到的路径
C.G 中没有弧
【答案】D
【解析】若想实现图的一个拓扑排序，需要满足的一个条件为:若顶点A 在序列中排在顶点B 的前面，则在图中不存在从顶点B 到顶点A 的路径。又因为若G 中有一条从到的路径，则在拓扑序列中不可能在前。
8． 若一棵二叉树的前序遍历序列和后序遍历序列分别为1, 2, 3, 4和4, 3, 2, 1, 则该二叉树的中序遍历序列不会是（ ）。
A.1, 2, 3, 4
B.2, 3, 4, 1
C.3, 2, 4, 1
D.4, 3, 2, 1
【答案】C
【解析】题目中的二叉树的先序序列和后序序列正好相反, 这样的二叉树每层只有一个结点。该二叉树的形态如下图所示。
D.G 中有一条从到的路径
从左至右, 这8棵二叉树的中序序列分别为:
(1)4, 3, 2, 1,
(2)3, 4, 2, 1
(3)2, 4, 3, 1
(4)2, 3, 4, 1
(5)1, 4, 3, 2
(6)1, 3, 4, 2
(7)1, 2, 4, 3
(8)1, 2, 3, 4
显然选项C 的中序序列不会出现。
9． 采用开址定址法解决冲突的哈希查找中，发生集聚的原因主要是（ ）。
A. 数据元素过多
B. 负载因子过大
C. 哈希函数选择不当
D. 解决冲突的算法选择不好
第 4 页，共 62 页
相关内容
相关标签