2017年常州大学数据结构(同等学力加试)考研复试核心题库
● 摘要
一、应用题
1． 有A 、B 两人通过信箱进行辩论，每人都从自己的信箱中取得对方的问题。将答案和向对方B 的信箱最多放N 提出的新问题组成一个邮件放入对方的邮箱中，设A 的信箱最多放M 个邮件，个邮件。初始时 A 的信箱中有x 个邮件邮件数减1. 。
A 、B 两人操作过程：
从A 的信箱中取出一个邮件； 回答问题并提出一个新问题； 将新邮件放入B 的信箱；
从B 的信箱中取出一个邮件； 回答问题并提出一个新问题； 将新邮件放入A 的信箱；
当信箱不为空时，辩论者才能从信箱中取邮件，否则等待。 当信箱不满时，辩论者才能将新邮件放入信箱，否则等待。
请添加必要的信号量和P 、V （或wait signed ）操作，以实现上述过程的同步，要求写出完整过程，并说明信号量的含义和初值。
【答案】首先定义两个互斥信号量：mutexA 和mutexB , 初始时为1，分别用来实现对A 的邮箱和B 的邮箱的互斥使用；然后针对A 的邮箱再定义两个信号量emptyA 和fullA ，
初值分别为
和X ，分别表示信箱中仍能存放信的数量和已经存放的信的数量，同理设置emptyB 和fullB , 初值为
和y 。
通信代码：
第 2 页，共 41 页
B 中有y 个辩论者每取出一个邮件，
初始代码：
从A 的信箱中取出一个邮件；
回答问题并提出一个新问题；
将新邮件放入B 的信箱；
从B 的信箱中取出一个邮件；
回答问题并提出一个新问题；
将新邮件放入A 的信箱；
2． 写出下面算法中带标号语句的频度。
第 3 页，共 41 页
设k 的初值等于1。
【答案】（1）这是一个递归调用，因k 初值为1，由语句（6）知，每次调用k 增1，故第（1）语句执行n 次，所以频度是n 。
（2）这是FOR 循环语句，在满足（1）的条件下执行，该语句进入循环体（3）n 次，加上最后一次判断出界，故执彳丁了n ＋1次，所以频度是n ＋1。
（3）这是循环体语句，共执行了n 次，所以频度是n 。
，k=2时判断n 次，最后（4）这是循环语句，当k=l时判断n ＋1次（进入循环体（5）n 次）
一次k=n－l 时判断3次，故执行次数是（n ＋1）＋n ＋... ＋3=（n ＋4）（n －1）/2次，所以频度是（n ＋4）（n －1）/2。
（5）语句（5）是（4）的循环体，每次比（4）少一次判断，故执行次数是n ＋（n －1）＋... ＋2=（n ＋2）（n －1）/2次，所以频度是（n ＋2）（n －1）/2。
（6）这是循环体语句，共执行了n －1次，所以频度是n －1。
3． 某请求分页系统的局部页面置换策略如下：系统从0时刻开始扫描，每隔5个时间单位扫描，本轮没有被访问过的页框将被系统回收，并放入到空闲页框链一轮驻留集（扫描时间忽略不计）
尾，其中内容在下一次被分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页框链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。假设不考虑其他进程的影响和系统开销，初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为32、15、21、41。进程
（1）访问（2）访问（3）访问【答案】
（1）页框号为21。因为起始驻留集为空，而0页对应的页框为空闲链表中的第三个空闲页框，其对应的页框号为21。
（2）页框号为32。理由：因11>10故发生第三轮扫描，页号为1、3的页框32、15在第二轮已处于空闲页框链表中，此刻1页又被重新访问，因此应被重新放回到驻留集中。其页框号为32。
（3）页框号为41。理由：因为第2页从来没有被访问过，它不在驻留集中，因此从空闲页框链表中取出链表头的页框41，页框号为41。
（4）适合。理由：如果程序的时间局部性越好，从空闲页框链表中重新取回的机会越大，该策略的优势越明显。
第 4 页，共 41 页
P 依次访问的<虚拟页号，访问时刻>是
：
请回答下列问题。
时，对应的页框号是什么？
时，对应的页框号是什么? 说明理由。 . 时，对应的页框号是什么? 说明理由。
（4）该策略是否适合于时间局部性好的程序? 说明理由。