2017年中国民航大学数据结构复试仿真模拟三套题
● 摘要
一、应用题
1． 某博物馆最多可容纳500人同时参观，有一个出入口，该出入口一次仅允许个通过。参观者的活动描述如下：
参观者进程i :
进门；
参观;
出门；
coend
请添加必要的信号量和P 、
V 的互斥与同步。
要求写出完整的过程，说明信号量含义并赋初值。 【答案】 定义两个信号量
博物馆可以容纳的最多人数
用于出入口资源的控制
参观者进程i :
进门；
2． 证明任一结点个数为n 的二叉树的高度至少为0 （logn ）。
【答案】最低高度二叉树的特点是，除最下层结点个数不满外，其余各层的结点数都应达到
第 2 页，共 19 页
操作，以实现上述操作过程中
各层的最大值。设n 个结点的二叉树的最低高度是h ，则n 应满足。解此不等式，并考
虑h 是整数. 则有即任一结点个数为n 的二叉树的高度至少为
3． 设度为m 的树采用多重链表存储，毎个结点有m+1个域，其中有1个数据域，m 个指向孩子的指针。 则空指针的数目是多少？说明这种存储方式的利弊。
【答案】（1）空指针数目：n （n>0）个结点的m 度树共有nm 个链域，除根结点外，每个结点均有一个指针所指，故该树的空链域有nm-（n-1）=n（m-l ）+1个。
（2）利弊：这种存储结构统一，便于处理但空链域造成存储效率低。
4． 下面程序段的时间复杂度是什么？
【答案】赋值语句一共被执行了m*n次，所以该程序段的时间复杂度是O （m*n）。 5． 已知两个各包含IV 和M 个记录的排好序的文件能在时间内合并为一个包含
个
记录的排好序的文件。当有多于两个排好序的文件要被合并在一起时，只需重复成对地合并便可完成。合并的步骤不同，所需花费的记录移动次数也不同。现有文件，FI ，F2，F3，F4，F5，各有记录数为20，30，10，5和30，试找出记录移动次数最少的合并步骤。
，【答案】类似最优二叉树（哈夫曼树）可先合并含较少记录的文件，后合并较多记录的文件，使移动次数减少，如图所示的哈夫曼树。
图
6． 主机H 通过快速以太网连接Internet , IP地址为
题 a 表
服务器S 的IP 地址为211.68.71.80。
H 与S 使用TCP 通信时，在H 上捕获的其中5个IP 分组如题a 表所示。
第 3 页，共 19 页
请回答下列问题。
（1）题a 表中的IP 分组中，哪几个是由H 发送的? 哪几个完成了TCP 连接建立过程? 哪几个在通过快速以太网传输时进行了填充？
（2）根据题a 表中的IP 分组，分析S 已经收到的应用层数据字节数是多少？
（3）若题a 表中的某个IP 分组在S 发出时的前40字节如题b 表所列，则该IP 分组到达H 时经过了多少个路由器？
题 b 表
注：IP 分组头和TCP 段头结构分别如题a 图、题b 图所示：
题a 图IP 分组头结构
题b 图TCP 段头结构
【答案】（1）由于题a 表中1、3、4号分组的源IP 地址（第13〜16字节）均为192.168.0.8 ，所 以1、3、4号分组是由H 发送的。 （coa80008H ）
第 4 页，共 19 页
相关内容
相关标签