2017年南京工业大学数据结构(同等学力加试)复试仿真模拟三套题
● 摘要
一、应用题
1． 某主机的MAC 地址为00-15-C5-C1-5E-28, IP 地址为10.2.128.100 （私有地址）。题a 图是网络拓扑，题b 图是该主机进行Web 请求的1个以太网数据帧前80个字节的十六进制及ASCII 码内容。
题a 图网络拓扑
题b 图以太网数据帧（前80字节）
请参考图中的数据回答以下问题。
（1）Web 服务器的IP 地址是什么? 该主机的默认网关的MAC 地址是什么？
（2）该主机在构造题47-b 图的数据帧时，使用什么协议确定目的MAC ±也址? 封装该协议请求报文的以太网帧的目的MAC 地址是什么？
（3）假设HTTP/1.1协议以持续的非流水线方式工作，以此请求一响应时间为RTT ，rfc.html 页面引用了5个JPEG 小图像，则从发出题b 图中的Web 请求开始到浏览器收到全部内容为止，需要多少个RTT?
（4）该帧所封装的IP 分组经过路由器R 转发时，需修改IP 分组头中的哪些字段? 注：以太网数据帧结构和IP 分组头结构分别如题c 图、题d 图所示。
题c 图以太网帧结构
题d 图IP 分组头结构
【答案】（1）以太网的数据部分是IP 数据报，只要找出相应字段所在的字节即可。根据图47-c 可知以太网头部 有6+6+2=14字节，根据图47-d 可知IP 地址有16字节，从图47-b 第一个字节开始数14+16 = 30字节，得目的IP 地址为40.aa.62.20即64.170.98.32。而以太网帧的前6字节00-21-27-21-51-ee 是目的MAC 地址，即为主机的 默认网关10.2.128.1端口的MAC 地址。
（2）该主机在构造题47-b 图的数据帧时，使用ARP 协议确定目的MAC 地址。封装该协议请求报文的以太网帧的目的MAC 地址是广播地址即FF-FF-FF-FF-FF-FF 。
（3）假设HTTP/1.1协议以持续的非流水线方式工作，客户机在收到前一个请求的响应后才能发出下一个请求。第一个RTT 用于请求Web 页面，客户机收到第一个请求的响应后，每访问一次对象就需一个RTT 。rfc.html 页面引用了5个JPEG 小图像，则从发出题47-b 图中的Web 请求开始到浏览开始到浏览器受到全部内容为止，故共需1+5 = 6个RTT 后浏览器收到全部内容。
（4）私有地址要和Internet 上的主机通信时，须由NAT 路由器进行网络地址转换，转换为一
IP 数据报没经过一个路由器，个全球IP 地址。生存时间TTL 值就减少1，并重新计算首部校验和。
所以需修改的信息有源IP 地址，头部校验和，生存时间。
2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专此基础综合真题及详解
2． 设哈希（Hash ）表的地址范围为0～17，哈希函数为：
造出哈希表，试回答下列问题：
（1）画出哈希表示意图；
（2）若查找关键字63，需要依次与哪些关键字比较？
（3）若查找关键字60，需要依次与哪些关键字比较？
（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。
【答案】（1）哈希表示意图如表所示：
表 哈希示意图
（2）查找关键字63时，由于
63比较。
（3）查找关键字60时，由于
（4） 哈希地址12内为空，查找失败。 所以需要依次与31，46，47，32，17，为关键字，用线性探测再散列法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49）
3． 若森林共有n 个结点和b 条边（b 【答案】森林的n 个结点开始可看做是n 个连通分量，加入一条边将减少一个连通分量。因 为树可以定义为无环的图，故加入b 条边将减少b 个连通分量，因而n 个结点b 条边的森林有n-b 棵树。 4． 用单链表保存m 个整数，节点的结构为（data , link ）, 且 点而删除其余绝对值相等的节点。 例如若给定的单链表head 如下 删除节点后的head 为 要求 （1）给出算法的基本思想 （2）使用c 或语言，给出单链表节点的数据类型定义。 语言描述算法，关键之处给出注释。 （3）根据设计思想，采用c 或 【答案】（1）算法思想： 定义一个大小为n 的布尔数组flag ，初始时所有的元素都赋值为false , 用来标识遍历过程中是否出现元素绝对值为flag 的节点。然后遍历链表，遍历过程中，每一个当前结点data 域的绝对值 ，则将flag 位置为真（true ）所对应的flag 位：若为真，则删除该结点；若为假（false ）。 （2）节点的数据结构定义如下： （3） 全局数组标志节点的绝对值是否出现过 如果此绝对值已经在节点值的绝对值中出现过 则删除该节点 （n 为正整数）。现要求设计一个时间复杂度尽可能高效地算法，对于链表中绝对值相等的节点，仅保留第一次出现的节（4）说明所涉及算法的时间复杂度和空间复杂度。