2017年重庆师范大学计算机与信息科学学院数据结构(加试)考研复试核心题库
● 摘要
一、应用题
1． 在某程序中，有两个栈共享一个一维数组空间
的栈底。
（1）对栈1、栈2, 试分别写出（元素x ）入栈的主要语句和出栈的主要语句。
（2）对栈1、栈2, 试分别写出栈满、栈空的条件。
【答案】（1）入栈主要语句
出栈主要语句
分别是两个栈
（2）
2． 在模试匹配KMP 算法中所用失败函数的定义中，为何要求
真子串？且为最大真子串？
【答案】失败函数（即next ）的值只取决于模式串自身，若第j 个字符与主串第i 个字符失配时，假定主串不回溯，模式串用第k （即next[j]个字符与第i 个相比，有为了不因模式串右移与主串第i 个字符比较而丢失可能的匹配，对于上式中可能存在的多个k 值，应取其中最大的一个。这样，因j-k 最小，即模式串向右滑动的位数最小，避免因右移造成可能匹配的丢失。
3． 请求分页管理系统中，假设某进程的页表内容如下表所示:
两头匹配的
页面大小为4KB ，一次内存的访问时间是100ns ，一次快表（TLB ）的访问时间是10ns ，处
，进程的驻留集大小固定为2, 采理一次缺页的平均时间为108ns （已含更新TLB 和页表的时间）
用最近最少使用置换算法（LRU ）和局部淘汰策略。假设①TLB 初始为空；②地址转换时先访问TLB , 若TLB 未命中，再访问页表（忽略访问页表之后的TLB 更新时间）；③有效位为0表示页
面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列请问：
（1）依次访问上述三个虚地址，各需多少时间? 给出计算过程。
（2）基于上述访问序列，虚地址1565H 的物理地址是多少? 请说明理由。
【答案】⑴
页面大小为4KB ，因此，虚地址的低12位是页内偏移，其余高位是页号。
访问虚地址2362H , 虚页号为2，页内偏移362H 。查找TLB , TLB 初始为空，未命中，耗时10ns ; 访问页表，2号页面所在页框号为254H ，耗时100ns ; 计算得到的物理地址254362H ，访问内存，耗时100ns 。因此，总共用时
访问虚地址1565H ，虚页号为1, 页内偏移565H 。查找TLB ，未命中，耗时10ns ; 访问页表，有效位是0，未命中，耗时100m ; 产生缺页中断，进行缺页中断处理，耗时108m ; 采用LRU 置换算法，虚页1装入页帧号101H , 缺页中断处理完后，再次访问页表，命中，耗时100m ; 计算得到物理地址101565H ，再次访问内存，耗时100ns 。因此，总共用时
访问虚地址25A5H ，虚页号为2, 页内偏移5A5H 。查找TLB , 命中，耗时10ns ; 虚页2对应的页帧为254H ，因此计算得物理地址为2545A5H , 访问内存，耗时100ns 。因此，
总共用时
（2）当访问虚地址1565H 时，产生缺页中断，合法驻留集为2, 必须从页表中淘汰一个页面，根据题目的置换算法，应淘汰0号页面，因此1565H 的对应的页框号为101H ，故可知虚地址1565H 的物理地址为101565H 。
4． 请回答下列关于图（Graph ）的一些问题：
（1）有n 个顶点的有向强连通图最多有多少条边? 最少有多少条边？
（2）表示一个有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素? 是否稀疏矩阵？
（3）对于一个有向图，不用拓扑排序，如何判断图中是否存在环？
【答案】⑴最多有n （n-l ）条边；最少有n 条边。
（2） 有有个矩阵元素；不一定是稀疏矩阵（稀疏矩阵的定义是非零元素个数远小于该矩阵元素个数，且分 布无规律）。
（3）使用深度优先遍历，按退出DFS 过程的先后顺序记录下的顶点是逆向拓扑有序序列。如果在执行DFS （V ） 未退出前，出现顶点u 到v 的回边，则说明存在包含顶点v 和顶点u 的环。
5．
某局域网采用协议实现介质访问控制，
数据传输率为主机甲和主机乙之间的距离为2km ，信号传播速度是200000km/S。请回答下列问题，要求说明理由或写出计算过程。
（1）若主机甲和主机乙发送数据时发生冲突，则从开始发送数据时刻起，到两台主机均检测到冲突时刻止，最短需经过多长时间? 最长需经过多长时间？（假设主机甲和主机乙发送数据过程
中，其他主机不发送数据）
（2）若网络不存在任何冲突与差错，主机甲总是以标准的最长以太网数据帧（1518字节）向主机乙发送数据，主机乙每成功收到一个数据帧后立即向主机甲发送一个64字节的确认帧，主机甲收到确认帧后方可发送下一个数据帧，此时主机甲的有效数据传输速率是多少？（不考虑以太网帧的前导码）
【答案】（1）当甲乙两台主机同时向对方发送数据时，两台主机均检测到冲突的时间最短
：=
（lkm/200000km/s）×2=10j×s ; 当一台主机发送的数据就要到达另一台主机时，另一台主机才发送数据，两台主机均检测到冲突的时间最长：
=1500B=1500×8bit=12000bit; 发送1518B 的发送时间=1518×8/10Mbps=
间=2km/200000km/s
=确认帧的发送时间=64×
8/10Mbps=; 确认帧的传播时间
=2km/200000km/s=; 发送1518B 所用的总时间为
1285.6μs=9.33Mbps。
6． 画出同时满足下列两个条件的两棵不同的二叉树。
（1）按前序遍历二叉树的顺序为ABCDE 。
（2）高度为5其对应的树（森林）的高度最大为4。
【答案】（1）满足条件的二叉树如图1所示：
主机甲的有效数据传输率为12000bit ／ 数据帧的传播时（2）有效数据传输速率=发送的有效数据/发送有效数据所用的总时间。发送的有效数据
图1
（2）满足条件的二叉树如图2所示：