2018年哈尔滨师范大学计算机科学与信息工程学院801计算机基础理论之数据结构考研强化五套模拟题
● 摘要
一、单项选择题
1． 若一棵二叉树的前序遍历序列为a , e , b , d , c , 后序遍历序列为b , c , d , e , a , 则根结点的孩子结点（ ）。
A. 只有e
B. 有e 、b
C. 有e 、c
D. 无法确定
【答案】A 。
【解析】由题目可知, 若一棵二叉树的前序遍历序列为a , e , b , d , c , 后序遍历序列为b , c , d , e , a , 其中a 为这棵二叉树的根结点, 接下来, 在前序遍历的第二个结点为e , 而后序遍历的倒数第二个结点为e , 说明a 的孩子结点只有e 。
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
【解析】在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为改图的一个拓扑排序:①每个顶点出现且出现一次；②若顶点在序列中排在顶点B 的前面，则在图
中不存在从顶点B 到顶点A 的路径。由拓扑排序的性质知，有向图的邻接矩阵必定为三角矩阵。
4． 某网络的IP 地址空间为采用定长子网划分，子网掩码为则该网络的最大子网个数、每个子网内的最大可分配地址个数分别是（ ）.
A.32， 8
B.32， 6
C.8， 32
D.8， 30
【答案】B
【解析】子网号为5位，在CIDR 中可以表示2＝32个子网，主机号为3位，除去全0和全5
1的情况可以表示6个主机地址，答案为B.
5． 对于100Mbps 的以太网交换机, 当输出端口无排队直通(
太网帧(不包括前导码) 时, 引入的转发延迟至少是（ ） A. B. C. D.
【答案】B ) 方式转发一个以
【解析】直通交换方式是指以太网交换机可以在各端口间交换数据。它在输入端口检测到一个数据包时, 检查该包的包头, 获取包的目的地址, 启动内部的动态查找表转换成相应的输出端口, 在输入与输出交叉处接通, 把数据包直通到相应的端口, 实现交换功能。通常情况下, 直通交换方式只检查数据包的包头即前14个字节, 由于不需要考虑前导码, 只需要检测目的地址的6B , 所以最短的传输延迟是。
6． 下列关于IP 路由器功能的描述中, 正确的是（ ）。
Ⅰ. 运行路由协议, 设置路由表;
Ⅱ. 监测到拥塞时, 合理丢弃IP 分组;
Ⅲ. 对收到的IP 分组头进行差错校验, 确保传输的IP 分组不丢失;
Ⅳ. 根据收到的IP 分组的目的IP 地址, 将其转发到合适的输出线路上。
A. 仅Ⅲ、Ⅳ
B. 仅Ⅰ、Ⅱ、Ⅲ
C. 仅Ⅰ、Ⅱ、Ⅳ
D. Ⅰ、Ⅱ、Ⅲ、Ⅳ
【答案】C 。
【解析】路由器的主要功能是路由和转发, 因此Ⅰ和Ⅳ是正确的, 而针对Ⅱ和Ⅲ, 可以从ICMP 协议的差错控制出发, 注意检测到拥塞时, 合理丢弃IP 分组, 并回传ICMP 源抑制报文, Ⅱ是正确的, 而Ⅲ对收到的IP 分组头进行差错校验, 确保传输的IP 分组不丢失, 差错校验是正确的, 但网络层不
保证IP 分组不丢失, 也就是不可靠的, 因此Ⅲ的说法错误, 正确的说法仅Ⅰ、Ⅱ、Ⅳ, 因此答案是C 。
7． 有向带权图如下图图所示, 若采用迪杰斯特拉(Dijkstta)算法求从源点a 到其他各顶点的最短路径, 则得到的第一条最短路径的目标顶点是b , 第二条最短路径的目标顶点是c , 后续得到的其佘各最短路径的目标顶点依次是（ ）。
图 有向带权图
A.d , e , f
B.e , d , f
C.f , d , e
D.f , e , d
【答案】C 。
【解析】本题主要考查Dijkstta 算法的思想和解题步骤。题目执行算法过程中各步的状态如下表所示。执行Dijkstta 算法过程中各步的状态表, 故后续目标顶点依次为f , d , e 。
8． 已知一棵有2011个结点的树, 其叶结点个数为116, 该树对应的二叉树中无右孩子的结点个数是（ ）。
A.115
B.116
C.1895
D.1896
【答案】D
【解析】每个非终端结点转换成二叉树后都对应一个无右孩子的结点(因为一个非终端结点至