2017年广州大学计算机科学与教育软件学院915数据结构[专业硕士]考研仿真模拟题
● 摘要
目录
2017年广州大学计算机科学与教育软件学院915数据结构[专业硕士]考研仿真模拟题（一） . 2 2017年广州大学计算机科学与教育软件学院915数据结构[专业硕士]考研仿真模拟题（二）14 2017年广州大学计算机科学与教育软件学院915数据结构[专业硕士]考研仿真模拟题（三）26 2017年广州大学计算机科学与教育软件学院915数据结构[专业硕士]考研仿真模拟题（四）37 2017年广州大学计算机科学与教育软件学院915数据结构[专业硕士]考研仿真模拟题（五）47
一、选择题
1． 图中有关路径的定义正确的是（ ）。
A. 由顶点和相邻顶点构成的边所形成的序列 B. 由不同顶点所形成的序列 C. 由不同边所形成的序列 D. 上述定义都不是 【答案】A
【解析】顶点Vp 到顶点Vq 之间的一条路径是指顶点序列
的数目称为路径的长度。
2． 对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（ ）。
，路径上边
A.4
B.3 C.2 D.1
【答案】B
【解析】拓扑排序的步骤为：
（1）在有向图中选一个没有前驱的顶点并且输出它；
（2）从图中删除该顶点和以它为尾的弧。重复上述两步，直至全部顶点均已输出。由于没有前驱的顶点可能不唯一，所以拓扑排序的结果也不唯一。题中所给图有三个不同的拓扑棑序序列，分别为abced ，abecd ，aebcd 。
3． 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A. 顺序表 B. 双链表
C. 带头结点的双循环链表 D. 单循环链表
【答案】A
【解析】线性表采用顺序表，便于进行存取任一指定序号的元素；线性表采用链表，便于进 行插入和删除操作。但该题是在最后进行插入和删除运算，所以利用顺序表存储方式最节省时间。
4． 如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用下列哪一种查找方法。
A. 分块 B. 顺序 C. 折半 D. 哈希 【答案】A
【解析】分块查找，把线形表分成若干块，块间是顺序存储的，所以查找速度较快。在每一块中的数据元素的存储顺序是任意的，所以便于线性表的动态变化。
5． 若下图为lOBaseT 网卡接收到的信号波形，则该比特串是（ ）
A.00110110 B.10101101 C.01010010 D.11000101 【答案】A
【解析】以太网采用曼彻斯特编码，其将一个码元分成两个相等的间隔，前一个间隔为高电平而后一个间隔为低电平表示1，反之则表示0。故根据波形图，可得答案为A 。
6． 下述文件中适合于磁带存储的是（ ）。
A. 顺序文件 B. 索引文件 C. 哈希文件 D. 多关键字文件 【答案】A
【解析】磁带存储是一种顺序存储，
顺序文件序文件适合磁带存储。
是记录按其在文件中的逻辑顺序
依次进入存储介质而建立的，即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的。因此顺
7． 设系统缓冲区和用户工作均采单，从外读入1个数据块到系统缓冲区的时间为100, 从系统缓冲区读入1个数据块到用户工作区的时间为5, 对用户工作区中的1个数据块行分析的时间为90 （如下图所示）。进程从外设读入并分析2个数据块的最短时间是（ ）
A.200
B.295 C.300 D.390
【答案】C
【解析】数据块1从外设到用户工作区的总时间为105, 在这段时间中数据块2没有进行操作。在数据块1进行分析处理时, 数据块2从外设到用户工作区的总时间为105, 这段时间是并行的。再加上数据块2进行处理的时间90, 总共是300, 故答案为C 。
8． 某磁盘的转速为10, 000转/分，平均寻道时间是磁盘传输速率是为
读取一个4KB 的扇区所需平均时间约为（ ）
A.9ms B.9.4ms C.12ms D.12.4ms 【答案】B
【解析】磁盘转速是10 000转/分钟，平均转一转的时间是6ms ，因此平均查询扇区的时间是3ms ，平均寻道时间是6ms ，读取4KB 扇区信息的时间为0.2ms ，信息延迟的时间为0.2ms ，总时 间为
9． 对有2个顶点e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（ ）。
A. B. C. D. 【答案】C 。
【解析】遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时，查找每个顶点的邻接点所需时间
为
其中n 为图中顶点数。而当以邻接表作图的存储结构时，找邻接点所需时间为
磁盘控制器延迟
其