2018年福建师范大学光电与信息工程学院841计算机专业基础综合之数据结构考研基础五套测试题
● 摘要
一、单项选择题
1． 对于栈操作数据的原则是（ ）
A. 先进先出
B. 后进先出
C. 后进后出
D. 不分顺序
【答案】B
【解析】先进先出是队列操作数据的原则。先进后出是栈操作数据的原则，栈限定在表尾进行插入和删除。
2． 假定编译器将赋值语句“x=x+3; ”转换为指令”add xaddt, 3”, 其中xaddt 是x 对应的存储单元地址, 若执行该指令的计算机采用页式虚拟存储管理方式, 并配有相应的TLB , 且Cache 使用直写(Write Through)方式, 则完成该指令功能需要访问主存的次数至少是（ ）。
A.0
B.1
C.2
D.3
【答案】C
【解析】采用页式虚拟存储管理方式时, 若页表全部放在内存中, 则存取一个数据最少要访问两次内存:第一次是访问页表, 得到所存取的数据或指令的物理地址; 第二次根据该地址存取数据或指令。在配有TLB 的页式虚拟管理方式中, 如果给出的地址在TLB 中, 则直接根据该地址取数据或指令, 仅需要一次访问内存。Cache 使用直写方式时, 计算完需要将数据写回到内存中, 因此完成整个指令功能至少需要访问主存2次。
3． 下列关于图的叙述中, 正确的是（ ）。
Ⅰ. 回路是简单路径
Ⅱ. 存储稀疏图, 用邻接矩阵比邻接表更省空间
Ⅲ. 若有向图中存在拓扑序列, 则该图不存在回路
A. 仅Ⅱ
B. 仅Ⅰ、Ⅱ
C. 仅Ⅲ
D. 仅Ⅰ、Ⅲ
【答案】C
【解析】第一个顶点和最后一个顶点相同的路径称为回路; 序列中顶点不重复出现的路径称为简单路径; 回路显然不是简单路径, 所以选项Ⅰ错误。稀疏图用邻接表表示比邻接矩阵节省存储空间, 稠密图适合用邻接矩阵的存储表示, 所以选项Ⅱ错误。利用拓扑排序算法可以判断图中是否存在回路, 即在拓扑排序输出结束后所余下的顶点都有前驱, 则说明了只得到了部分顶点的拓扑有序序列, 图中存在回路。所以选项Ⅲ正确。
4． 某以太网拓扑及交换机当前转发表如下图所示, 主机后, 向主机
A.
C.
D. 和和 B.{2, 3}和{1} 和
{1}
向主机发送1个数据帧, 主机收到该帧发送一个确认帧, 交换机对这两个帧的转发端口分别是（ ）
【答案】B
【解析】
第一次交换机没有
这个数据报源MAC 地址的信息的信息, 只能选择从其他端口全部发送, 同时记录, 确认帧发送时已经有的信息了所以只用从1端口转发。
5． 若对n 阶对称矩阵A 以行序为主序方式将其下三角形的元素(包括主对角线上所有元素) 依次存放于一维数组B[l...(n(n＋1))/2]中，则在B 中确定a ij (i＜j) 的位置k 的关系为（ ）。
A.i*(i﹣1)/2＋j
B.j*(j﹣1)/2＋i
C.i*(i＋1)/2＋j
D.j*(j＋1)/2＋i
【答案】B
【解析】将n 阶对称矩阵存人一维数组中，一维数组的大小需为n(n＋1)/2。对n 阶对称矩阵
A 以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)
依次存放于一维数组
中，当i ＜j 时，i 与k 的关系为j*(j﹣1)/2＋i 。
6． 执行（ ）操作时，需要使用队列做辅助存储空间。
A. 查找哈希(Hash)表
B. 广度优先搜索网
C. 前序(根) 遍历二叉树
D. 深度优先搜索网
【答案】B
【解析】查找哈希表不需要辅助存储空间，前序遍历二叉树和深度优先搜索网需要使用栈做辅助存储空间，广度优先搜索树需要队列做辅助存储空间。
7． 某计算机的指令流水线由4个功能段组成，指令流经各功能段的时间(忽略各功能段之间的缓存时间) 分别为90ns 、80ns 、70ns 和60ns ，则该计算机的CPU 时钟周期至少是（ ）.
A.90ns
B.80ns
C.70ns
D.60ns
【答案】A
【解析】对于各功能段执行时间不同的指令流水线，计算机的CPU 时钟周期应当以最长的功能段执行时间为准.
8． 若一个有向图具有拓扑排序序列，那么它的邻接矩阵必定为（ ）。
A. 对称矩阵
B. 稀疏矩阵
C. 三角矩阵
D. —般矩阵
【答案】C
【解析】在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为改图的一个拓扑排序:①每个顶点出现且出现一次；②若顶点在序列中排在顶点B 的前面，则在图
中不存在从顶点B 到顶点A 的路径。由拓扑排序的性质知，有向图的邻接矩阵必定为三角矩阵。
9． 设计一个判别表达式中左、右括号是否配对出现的算法，采用（ ）数据结构最佳。
A. 线性表的顺序存储结构
B. 队列
C. 线性表的链式存储结构
D. 栈
【答案】D