当前位置：问答库＞考研试题

一、应用题

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． 设有6个有序表A 、B 、C 、D 、E 、F , 分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列。要求通过5次两两合并，将6个表最终合并成1个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题。

（1）给出完整的合并过程，并求出最坏情况下比较的总次数。

（2）根据你的合并过程，描述

n

【答案】

（1）6个表的合并顺序如下图所示。 个不等长升序表的合并策略，并说明理由。

对应于合并过程的哈夫曼树

根据上图中的哈夫曼树，6个序列的合并过程为：

第1次合并：表A 与表B 合并，生成含45个元素的表AB ;

第2次合并：表AB 与表C 合并，生成含85个元素的表ABC ;

第3次合并：表D 与表E 合并，生成含110个元素的表DE ;

第4次合并：表ABC 与表DE 合并，生成含195个元素的表ABCDE ;

第5次合并：表ABCDE 与表F 合并，生成含395个元素的最终表。

由于合并两个长度分别为m 和n 的有序表，最坏情况下需要比较m+n-1次，故最坏情况下比较的总次数计算如下：

第1次合并：最多比较次数= 10+35-1=44;

第2次合并：最多比较次数=45+40-1 = 84;

第3次合并：最多比较次数=50+60-1 = 109;

第4次合并：最多比较次数=85+110-1 = 194;

第5次合并：最多比较次数= 195+200-1 = 394; 比较的总次数最多为：44+84+109+194+394 = 825。

（2）各表的合并策略是：在对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖于表的合并次序。可以借用哈夫曼树的构造思想，依次选择最短的两个表进行合并，可以获得最坏情况下最佳的合并效率。

3． 设度为m 的树采用多重链表存储，毎个结点有m+1个域，其中有1个数据域，m 个指向孩子的指针。 则空指针的数目是多少？说明这种存储方式的利弊。

【答案】（1）空指针数目：n （n>0）个结点的m 度树共有nm 个链域，除根结点外，每个结点均有一个指针所指，故该树的空链域有nm-（n-1）=n（m-l ）+1个。

（2）利弊：这种存储结构统一，便于处理但空链域造成存储效率低。

4． 数据类型和抽象数据类型是如何定义的? 二者有何相同和不同之处? 抽象数据类型的主要特点是什么? 使用抽象数据类型的主要好处是什么？

【答案】（1）数据类型的定义

数据类型是程序设计语言中的一个概念，它是一个值的集合和操作的集合。如c 语言中的整

，其操作有加、减、乘、除、型、实型、字符型等。整型值的范围（对具体机器都应有整数范围）