2017年中国传媒大学计算机软件与理论9066程序设计复试之数据结构(C语言版)考研复试核心题库
● 摘要
一、应用题
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 页，共 40 页
B 中有y 个辩论者每取出一个邮件，
初始代码：
通信代码：
从A 的信箱中取出一个邮件；
回答问题并提出一个新问题；
将新邮件放入B 的信箱；
从B 的信箱中取出一个邮件；
回答问题并提出一个新问题；
将新邮件放入A 的信箱；
2． 用单链表保存m 个整数，节点的结构为（data , link ）, 且点而删除其余绝对值相等的节点。
例如若给定的单链表head 如下
（n 为正整数）。现要求
设计一个时间复杂度尽可能高效地算法，对于链表中绝对值相等的节点，仅保留第一次出现的节
删除节点后的head 为
第 3 页，共 40 页
要求
（1）给出算法的基本思想 （2）使用c 或
语言，给出单链表节点的数据类型定义。
语言描述算法，关键之处给出注释。
（3）根据设计思想，采用c 或【答案】（1）算法思想：
定义一个大小为n 的布尔数组flag ，初始时所有的元素都赋值为false , 用来标识遍历过程中是否出现元素绝对值为flag 的节点。然后遍历链表，遍历过程中，每一个当前结点data 域的绝对值，则将flag 位置为真（true ）所对应的flag 位：若为真，则删除该结点；若为假（false ）。
（2）节点的数据结构定义如下：
（3）
全局数组标志节点的绝对值是否出现过
如果此绝对值已经在节点值的绝对值中出现过则删除该节点
否则，将flag 中对应的位置置为true ，并将指针指向下一个元素
，申请大小（4）只遍历一次链表，所以时间复杂度为0 （m ） （m 为单链表中元素的个数）
（4）说明所涉及算法的时间复杂度和空间复杂度。
为n 的数组，所以空间复杂度为0 （n ） （n 为节点绝对值的最大值）。
第 4 页，共 40 页