2017年西安工程大学924数据结构复试实战预测五套卷
● 摘要
一、应用题
1． 外排序中为何采用k 一路
么？
【答案】外排序用路归并是因为k 越小，归并趟数越多，读写外存次数越多，时间效率越低，故一般应大于最少的2-路归并。若将k-路归并的败者树思想单纯用于内排序，因其由胜者树改进而来，且辅助空间大，完全可由堆排序取代，故将其用于内排序效率并不高。
2． 某主机的MAC 地址为00-15-C5-C1-5E-28, IP 地址为10.2.128.100 （私有地址）。题a 图是网络拓扑，题b 图是该主机进行Web 请求的1个以太网数据帧前80个字节的十六进制及ASCII 码内容。
题a 图网络拓扑
合并而不用2—路合并? 这种技术用于内排序有意义吗? 为什
题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年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专此基础综合真题及详解
3． 试证明：同一棵二叉树的所有叶结点，在前序序列、对称序序列以及后序序列中都按相同的
，例如前序后序运对称序。 相对位置出现（即先后顺序相同）
，中序遍历是“左根右”，后序遍历是“左右根”【答案】前序遍历是“根左右”。三种遍历中
只是访问 " 根”结点的时机不同，对左右子树均是按左右顺序来遍历的，因此所有叶子都按相同的相对位罝出现。
4． 已知两个各包含IV 和M 个记录的排好序的文件能在时间内合并为一个包含个记录的排好序的文件。当有多于两个排好序的文件要被合并在一起时，只需重复成对地合并便可完成。合并的步骤不同，所需花费的记录移动次数也不同。现有文件，FI ，F2，F3，F4，F5，各有记录数为20，30，10，5和30，试找出记录移动次数最少的合并步骤。
，【答案】类似最优二叉树（哈夫曼树）可先合并含较少记录的文件，后合并较多记录的文件，
使移动次数减少，如图所示的哈夫曼树。
图
5． 请回答下列关于图（Graph ）的一些问题：
（1）有n 个顶点的有向强连通图最多有多少条边? 最少有多少条边？
（2）表示一个有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素? 是否稀疏矩阵？
（3）对于一个有向图，不用拓扑排序，如何判断图中是否存在环？
【答案】⑴最多有n （n-l ）条边；最少有n 条边。
（2） 有有个矩阵元素；不一定是稀疏矩阵（稀疏矩阵的定义是非零元素个数远小于该矩阵元素个数，且分 布无规律）。
（3）使用深度优先遍历，按退出DFS 过程的先后顺序记录下的顶点是逆向拓扑有序序列。如果在执行DFS （V ） 未退出前，出现顶点u 到v 的回边，则说明存在包含顶点v 和顶点u 的环。
6． 假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading ”和“being ”的存储映像如图所示。
图 存储映像7K 意图
设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为
符i 所在结点的位置p ）。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C 或
【答案】
（1）算法的基本设计思想：
①分别求出strl 和str2所指的两个链表的长度m 和n ;
②将两个链表以表尾对齐：令指针p 、q 分别指向strl 和str2的头结点，若
表中的第个结点；若则使q 指向链表中的第
请设计一个时间上尽可能高效的算法，找出由strl 和str2所指的两个链表共同后缀的起始位置（如图中字或JA V A 语言描述算法，关键之处给出注释。 （3）说明你所设计算法的时间复杂度。 则使p 指向链个结点，即使指针p 和q 所指的结点到