目录
2017年东南大学5h1专业综合测试1之数据结构考研复试核心题库（一） ........................... 2 2017年东南大学5h1专业综合测试1之数据结构考研复试核心题库（二） ......................... 10 2017年东南大学5h1专业综合测试1之数据结构考研复试核心题库（三） ......................... 18 2017年东南大学5h1专业综合测试1之数据结构考研复试核心题库（四） ......................... 23 2017年东南大学5h1专业综合测试1之数据结构考研复试核心题库（五） ......................... 29
第 1 页，共 36 页
2017年东南大学5h1专业综合测试1之数据结构考研复试核心题库（一）
说明：本资料为学员内部使用，整理汇编了2017考研复试重点题及历年复试常考题型。 ————————————————————————————————————————
一、应用题
1． 主机H通过快速以太网连接Internet, IP地址为
题 a表
服务器S的IP地址为211.68.71.80。
H与S使用TCP通信时，在H上捕获的其中5个IP分组如题a表所示。
请回答下列问题。
（1）题a表中的IP分组中，哪几个是由H发送的?哪几个完成了TCP连接建立过程?哪几个在通过快速以太网传输时进行了填充？
（2）根据题a表中的IP分组，分析S已经收到的应用层数据字节数是多少？
（3）若题a表中的某个IP分组在S发出时的前40字节如题b表所列，则该IP分组到达H时经过了多少个路由器？
题 b表
注：IP分组头和TCP段头结构分别如题a图、题b图所示：
题a图IP分组头结构
第 2 页，共 36 页
题b图TCP段头结构
【答案】（1）由于题a表中1、3、4号分组的源IP地址（第13?16字节）均为192.168.0.8 ，所 以1、3、4号分组是由H发送的。 （coa80008H）
，seq=846b41c5H, 2题a表中1号分组封装的TCP段的FLAG为02H （即SYN=1，ACK=0）
，seq=e059 9feffl，ack=846b41c6H，号分组封装的TCP 段的 FLAG为12H （即 SY=1, ACK=1）
3号分组封装的TCP 段的FLAG为10H （即 ACK=1）seq=846b41c6H, ack=e059 9ff0H，，所以 1、2、3号分组完成了 TCP 连接建立过程。
5号分组的总长度为40由于快速以太网数据帧有效载荷的最小长度为46字节，表中3、（28H）字节，小于46字节，其余分组总长度均大于46字节，所以3、5号分组在通过快速以太网传输时进行了填充。
（2）由3号分组封装的TCP段可知，发送应用层数据初始序号为846b 41c6H,由5号分组封装的TCP段可知，ack为846b 所以5号已经收到的应用层数据的字节数为
（3）由于S发出的IP分组的标识=6811H，所以该分组所对应的是题47-a表中的5号分组。S发出的IP 分组的TTL=40H=64,5号分组的TTL=31H=49, 64-49=15。所以，可以推断该IP分组到达H时经过了15个路由器。 2． 假设以S和X分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由S和X生成的序列表示（如SXSX）。
（1）试指出判别给定序列是否合法的一般规则；
（2）两个不同合法序列（对同一输入序列）能否得到相同的输出元素序列?如能得到，请举列说明。
【答案】（1）通常有两条规则。第一是给定序列中S的个数和X的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，S的个数要大于或等于X的个数。
（2）可以得到相同的输出元素序列。例如，输入元素为A,B,C,则两个输入的合法序列ABC和BAC均可得到输出元素序列ABC。对于合法序列ABC，使用SXSXSX操作序列；对于合法序列BAC，使用SSXXSX操作序列。
第 3 页，共 36 页
3． 某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号 机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：
请添加必要的信号量和P、V （或wait（ ）、signal（ ））操作，实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。
【答案】（1）互斥资源：取机号，故设一个互斥信号量mutex。
（2）同步问题：顾客需要获得空座位等待叫号，当营业员空闲时，将选取一位顾客为其服务。空座位的有、 无影响等待顾客数量，顾客的有、无决定两营业员是否能开始服务。另外，顾客获得空座位后，需要等待叫号和被服务，顾客与营业员就服务何时开始有同步关系。设信号量teller，customer和mutex初值分别为0，0和1，设waiting为整型量，表示排队的储户数量，其初始为0,表示顾客初始时为0,最大不超过10 （10把座椅），各进程的具体实现如下所示：
//座椅数，也是最多排队的储户数 //定义信号量
//储户进程
//先获得排队机 //若还有座椅则取号 //取号，占用座椅等待叫号 //告知系统储户加1 //释放排队机
第 4 页，共 36 页
//等待储户的柜员资源 //排队等待服务的储户数量 //对排队机操作的互斥量 //在座椅上休息等待的储户数