2017年西南民族大学计算机导论之数据结构(C语言版)复试仿真模拟三套题
● 摘要
一、应用题
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 分组头结构
题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． 设目标为模式为
（1）计算模式p 的nextval 函数值；
（2）不写出算法，只画出利用KMP 算法进行模式匹配时每一趟的匹配过程。
【答案】（1）P 的nextval 函数值为0110132（P 的next 函数值为0111232）。
（2）利用KMP （改进的nextval ）算法，每趟匹配过程如下：
第一趟匹配：
abcab （i=5, j=5）
第二趟匹配：
abc （i=7，j=3）
第三趟匹配：
a （i=7，j=l）
第四趟匹配：
（成功）abcabaa （i=15，j=8）
3． 文件F 由200条记录组成，记录从1开始编号，用户打开文件后，欲将内存中的一条记录插入文件F 中，作为其第30条记录，请回答下列问题，并说明理由。
（1）若文件系统为顺序分配方式，每个存储块存放一条记录，文件F 的存储区域前后均有足够空闲的存储空间，则要完成上述操作最少要访问多少存储块？ F 的文件控制区内容会有哪些改变？
（2）若文件系统为链接分配方式，每个存储块存放的一条记录和一个链接指针，则要完成上述操作最少要 访问多少存储块？若每个存储块大小为1KB ，其中4个字节存放指针，则该系统支撑文件的最大长度是多少？
【答案】（1）因为要最少访问，所以选择将前29块前移一个存储块单元，然后将要写入的记录写入到当前的第30条的位置上。由于前移都要先访问原存储块将数据读出，再访问目标存储块将数据写入，所以最少需要访问
块存储块
F 的文件区的文件长度加1，起始块号减1
（2）采用链接方式则需要顺序访问前29块存储块，然后将新纪录的存储块插入链中即可，把新的块存入磁盘要1次访存，然后修改第29
块的链接地址存回磁盘又一次访存。一共就是
次。
4个字节的指针的地址范围为 所以此系统支撑文件的最大长度为
4． 对于具有n 个叶结点且所有非叶结点都有左、右孩子的二叉树。
（1）试问这种二叉树的结点总数是多少？
（2）试证明 。其中：表示第i 个叶结点所在的层号（设根结点所在层号为1）。
【答案】（1）根据二叉树中度为2的结点个数等于叶结点个数减1的性质，故具有n 个叶结点且非叶子结点均有左子树的二叉树的结点数是2n-l 。
（2）证明：当i=l时，
成立。
设某叶结点的层号为t ，当将该结点变为内部结点，从而再增加两个叶结点时，这两个叶结点的层号都是t+1, 对于公式的变化，是减少了一个原来的叶结点，増加了两个新叶结点，反映到公
，所以结果不变，这就证明当i=n时公式仍成立。证毕。 式中. 因为
5． 某计算机的CPU 主频为500MHz ，CPI 为5（即执行每条指令平均需要5个时钟周期）。假定某外设的数据传输率为0.5MB/S，采用中断方式与主机进行数据传送，以32位为传输单位，对应的中断服务程序包含18条指令，中断服务的其他开销相当于2条指令的执行时间。请回答下列问题，要求给出计算过程。
（1）在中断方式下，CPU 用于该外设I/O的时间占整个CPU 时间的百分比是多少？
, 公式成立。设当i=n-1时公式成立，证明当i=n时公式仍
相关内容
相关标签