2017年兰州大学数据结构考研复试核心题库
● 摘要
一、应用题
1． 下图是5阶B 树，画出删去P 后的B 树，再画出删去D 后的B 树。
【答案】删除P 后
删除D 后
2． 有A 、B 两人通过信箱进行辩论，每人都从自己的信箱中取得对方的问题。将答案和向对方B 的信箱最多放N 提出的新问题组成一个邮件放入对方的邮箱中，设A 的信箱最多放M 个邮件，个邮件。初始时 A 的信箱中有x 个邮件邮件数减1. 。
A 、B 两人操作过程：
从A 的信箱中取出一个邮件； 回答问题并提出一个新问题； 将新邮件放入B 的信箱；
第 2 页，共 38 页
B 中有y 个辩论者每取出一个邮件，
从B 的信箱中取出一个邮件； 回答问题并提出一个新问题； 将新邮件放入A 的信箱；
当信箱不为空时，辩论者才能从信箱中取邮件，否则等待。 当信箱不满时，辩论者才能将新邮件放入信箱，否则等待。
请添加必要的信号量和P 、V （或wait signed ）操作，以实现上述过程的同步，要求写出完整过程，并说明信号量的含义和初值。
【答案】首先定义两个互斥信号量：mutexA 和mutexB , 初始时为1，分别用来实现对A 的邮箱和B 的邮箱的互斥使用；然后针对A 的邮箱再定义两个信号量emptyA 和fullA ，
初值分别为
和X ，分别表示信箱中仍能存放信的数量和已经存放的信的数量，同理设置emptyB 和fullB , 初值为
和y 。
通信代码：
从A 的信箱中取出一个邮件；
回答问题并提出一个新问题；
将新邮件放入B 的信箱；
从B 的信箱中取出一个邮件；
第 3 页，共 38 页
初始代码：
回答问题并提出一个新问题；
将新邮件放入A 的信箱；
3． 设将n （n ＞l ）个整数存放到一维数组R 中。试设计一个在时间和空间两方面都尽可能高效的算法，将R 中存有的序列循环左移P （0＜P ＜n ）个位置，即将R 中的数据由
变换为
（1）给出算法的基本设计思想。 （2）根据设计思想，采用C 或
或JA V A 语言描述算法，关键之处给出注释。
原地逆置，
得到
（3）说明你所设计算法的时间复杂度和空间复杂度。 【答案】（1）算法的基本设计思想：先将n
个数据由然后再将数组R 中的前
，
（2）用C 语言算法描述如下：
（3）说明算法的复杂性：上述算法中3个Reverse 函数的的时间复杂度分别
为
为O
故算法的时间复杂度为
，算法的空间复杂度为0（1）。
4． 某网络中的路由器运行0SPF 路由协议，如表是路由器R1维护的主要链路状态信息（LSI ），如图是根据表及R1的接口名构造出来的网络拓扑。
表R1所维护的LSI
个数和后P 个数分别原地逆置，
最终得到结果
要求：
第 4 页，共 38 页
相关内容
相关标签