2018年中国传媒大学脑科学与智能媒体研究院821数据结构与计算机网络之数据结构考研核心题库
● 摘要
一、单项选择题
1． 一个具有1025个结点的二叉树的高h 为（ ）。
A.11
B.10
C.11至1025之间
D.10至1024之间
【答案】C
【解析】当一棵树是完全二叉树时，其高度最低，此时高度为11，当一棵树的结点在一条线上时，此时最高，这时二叉树的高度是1025。
2． 某容量为256M 的存储器, 由若干4M*8位的DRAM 芯片构成, 该DRAM 芯片的地址引脚和数据引脚总数是:（ ）
A.19
B.22
C.30
D.36
【答案】A
【解析】DREAM 地址线复用, 4M 为2的22次方, 因此除2为11根, 数据线8根。因此地址引脚和数据引脚总数为19根
3． 在有向图G 的拓扑序列中，若顶点在顶点之前，则下列情形不可能出现的是（ ）。
A.G 中有弧
C.G 中没有弧
【答案】D
【解析】若想实现图的一个拓扑排序，需要满足的一个条件为:若顶点A 在序列中排在顶点B 的前面，则在图中不存在从顶点B 到顶点A 的路径。又因为若G 中有一条从到的路径，则在拓扑序列中不可能在前。
4． 对有2个顶点e 条边且使用邻接表存储的有向图进行广度优先遍历, 其算法时间复杂度是（ ）。 A.
第 2 页，共 51 页 B.G 中有一条从到的路径 D.G 中有一条从到的路径
B. C. D.
【答案】C 。
【解析】遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时,
查找每个顶点的邻接点所需时间为
, 其中n 为图中顶点数。而当以邻接表作图的存储结构时, 找邻接点所需时间为0(e), 其中e 为无向图中边的数或有向图中弧的数。由此, 当以邻接表作存储结构时, 深度优先搜索遍历图的时间复杂度为。即可得出正确答案。
5． 分区分配内存管理方式的主要保护措施是（ ）.
A. 界地址保护
B. 程序代码保护
C. 数据保护
D. 栈保护
【答案】A
【解析】对于连续分配算法，无论固定分区或动态分区方法，程序都必须全部调入内存，不同的进程放于不同的内存块中，相互之间不可越界，因此需要进行界地址保护. 通常的界地址保护方法采用软硬件结合的方法. 考生要注意本题与虚拟存储方法的区别.
6． 下列关于管道(Pipe)通信的叙述中, 正确的是（ ）
A. —个管道可实现双向数据传输
B. 管道的容量仅受磁盘容量大小限制
C. 进程对管道进行读操作和写操作都可以被阻塞
D. —个管道只能有一个读写进程或一个写进程对其操作
【答案】C
【解析】只有写进程才能对管道写入数据, 读进程对管道进行读取数据, 只能半双工通信, 即某一时刻只能单向传输。管道为空, 则读操作被堵塞, 而如果有写操作对管道进行写的话那就要堵塞了。那么C 正确
7． 下列有关接口的叙述中错误的是:（ ）
A. 状态端口和控制端口可以合用同一寄存器 B. 接口中CPU 可访问寄存器, 称为端口
端口
指令, C. 采用独立编址方式时, 【答案】D 【解析】采用统一编码方式,
存储器和端口共用统一的地址空间, 不需要专用的端口地址和主存地址可能相同 D. 采用统一编址方式时, CPU 不能用访存指令访问
第 3 页，共 51 页
任何对存储器数据进行操作的指令都可用于端口的数据操作。所以D 错误
8． 排序过程中, 对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中, 每一趟排序结束时都至少能够确定一个元素最终位置的方法是（ ）。
Ⅰ. 简单选择排序
Ⅱ. 希尔排序
Ⅲ. 快速排序
Ⅳ. 堆排
Ⅴ. 二路归并排序
A. 仅Ⅰ、Ⅲ、Ⅳ
B. 仅Ⅰ、Ⅱ、Ⅲ
C. 仅Ⅱ、Ⅲ、Ⅳ
D. 仅Ⅲ、Ⅳ、Ⅴ
【答案】A 。
【解析】其中简单选择排序、堆排序属于选择类排序, 每一趟排序结束时将确定最大(或最小) 关键字所在的位置。快速排序每一趟排序结束时将确定基准关键字所在的位置。希尔排序、二路归并排序每一趟排序结束时不一定能确定一个元素的最终位置。
9． 下列关于闪存(FlashMemory)的叙述中, 错误的是（ ）。
A. 信息可读可写, 并且读、写速度一样快
B. 存储元由MOS 管组成, 是一种半导体存储器
C. 掉电后信息不丢失, 是一种非易失性存储器
D. 采用随机访问方式, 可替代计算机外部存储器
【答案】A 。
【解析】考查闪存的特性, 闪存是EEPROM 的进一步发展, 可读可写, 用MOS 管的浮栅上有无电荷来存储信息, 它依然是ROM 的一种, 故写速度比读速度要慢不少。闪存是一种非易失性存储器, 它采用随机访问方式, 现在常见的SSD 固态硬盘就是由flash 芯片组成的, 故答案为A 。
10．主机甲通过1个路由器个路由器(存储转发方式) 与主机乙互联, 两段链路的数据传输速率均为10Mbps , 主机甲分别采用报文交换和组大小为10kb 的分组交换向主机乙发送1个大小为8Mb(1M=106)的报文。若忽略链路传播延迟、分组头开销和拆装时间, 则两种交换方式完成该报文传输所需的总时间分别为（ ）
A.800ms>1600ms
B.801ms 、1600ms
C.1600ms 、800ms
D.1600ms 、801ms
第 4 页，共 51 页