2018年北京师范大学政府管理学院986软件基础数据结构考研基础五套测试题
● 摘要
一、应用题
1． 对于后序线索二叉树，怎样查找任意结点的直接后继? 对于中序线索二叉树，怎样查找任意结点的直接前驱？
【答案】(1)后序线索树中结点的后继的方法如下:根结点无后继；当结点的rtag=1时，其右线索指向后继；当结点的rtag=0且是其双亲的右孩子，或是双亲的左孩子且双亲无右孩子时，其双亲是该结点的后继；当结点是其双亲的左孩子且双亲有右孩子时，其双亲结点右子树中最左下的叶结点是其后继。
(2)对中序线索二叉树的某结点，若其左标记等于1，则左孩子为线索，指向直接前驱；否则，其前驱是其左子树上按中序遍历的最后一个结点。
2． 某主机的MAC 地址为, :IP 地址为(私有地址) 。图a 是网络拓扑, 图b 是该主机进行Web 请求的1个以太网数据帧前80个字节的十六进制及ASC Ⅱ码内容。
图a 网络拓扑
图b 以太网数据帧(前80字节)
请参考图中的数据回答以下问题。
(1)Web服务器的IP 地址是什么? 该主机的默认网关的MAC 地址是什么？
(2)该主机在构造图b 的数据帧时, 使用什么协议确定目的MAC 地址? 封装该协议请求报文的以太网帧的目的MAC 地址是什么？
(3)假设协议以持续的非流水线方式工作, 以此请求一响应时间为页面引用了5个JPEG 小图像,
则从发出图b 中的Web 请求开始到浏览器收到全部内容为止, 需要多少个RTT?
(4)该帧所封装的IP 分组经过路由器R 转发时, 需修改IP 分组头中的哪些字段? 注:以太网数据帧结构和IP 分组头结构分别如图c 、图d 所示。
图c 以太网帧结构
图d IP分组头结构
【答案】(1)以太网的数据部分是IP 数据报, 只要找出相应字段所在的字节即可。根据图c 可知以太网头部有6+6+2=14字节, 根据图d 可知IP 地址有16字节, 从图b 第一个字节开始数14+16=30字节, 得目的IP 地址为是目的MAC 地址, 即为主机的默认网关即。而以太网帧的前6字节端口的MAC 地址。
(2)该主机在构造题b 图的数据帧时, 使用ARP 协议确定目的MAC 地址。封装该协议请求报文的以太网帧的目的MAC 地址是广播地址即FF-FF-FF-FF-FF-FF 。
(3)假设HTTP/1.1协议以持续的非流水线方式工作, 客户机在收到前一个请求的响应后才能发出下一个请求。第一个RTT 用于请求Web 页面, 客户机收到第一个请求的响应后, 每访问一次对象就需一个页面引用了5个JPEG 小图像, 则从发出图b 中的Web 请求开始到浏览开始到浏览器受到全部内容为止, 故共需1+5=6个RTT 后浏览器收到全部内容。
(4)私有地址要和Internet 上的主机通信时, 须由NA T 路由器进行网络地址转换, 转换为一个全
IP 数据报没经过一个路由器, 生存时间TTL 值就减少1, 并重新计算首部校验和。球IP 地址。所以
需修改的信息有源IP 地址, 头部校验和, 生存时间。
3． 设有n 个元素采用起泡排序法进行排序，通常需要进行多少趟排序? 对于第J 趟起泡通常需要进行多少次关键字比较? 在程序设计中如何设置判断条件，有可能使起泡趟数可以减少并且能完成排序。
【答案】n 个元素采用起泡排序法进行排序，通常需要进行n －1趟排序。第j 趟起泡排序要进行n －j 次比较。在一趟排序中，若没有记录交换，则表示排序完成。因而，可通过设标记来控制排序结束，下面语句段说明了标记flag 的使用。
用作控制标记
是起泡排序趟数，最多n －1趟
设标记，若本趟不发生交换，本趟起泡排序后，算法结束
发生了交换，还要进行下
趟
4． 以归并算法为例，比较内部排序和外部排序的不同，说明外部排序如何提高操作效率。
【答案】(1)内部排序中的归并排序是在内存中进行的归并排序，辅助空间为O(n)。外部归并排序是将外存中的多个有序子文件合并成一个有序子文件，将每个子文件中记录读入内存后的排序方法可采用多种内排序方法。外部排序的效率主要取决于读写外存的次数，即归并的趟数。
(2)因为归并的趟数，其中，m 是归并段个数，k 是归并路数。增大k 和减少m 都可减少归并趟数。应用中通过败者树进行多(k)路平衡归并和置换一选择排序减少m ，来提高外部排序的效率。
5． 一个ISAM 文件除了主索引外，还包括哪两级索引？
【答案】ISAM 文件有三级索引:磁盘组、柱面和磁盘，柱面索引存放在某个柱面上，若柱面索引较大，占多个磁道时，可建立柱面索引的索引——主索引。故还包括的两级索引是盘组和磁道。
6． 试证明:同一棵二又树的所有叶结点，在前序序列、对称序序列以及后序序列中都按相同的相对位置出现(即先后顺序相同) ，例如前序，后序，对称序。
【答案】前序遍历是“根左右”，中序遍历是“左根右”，后序遍历是“左右根”。三种遍历中只是访问“根”结点的时机不同，对左右子树均是按左右顺序来遍历的，因此所有叶子都按相同的相对位置出现。
7． 将下列由三棵树组成的森林转换为二叉树(只要求给出转换结果) 。
【答案】森林转换为二叉树分以下三步:
(1)连线(将兄弟结点相连，各树的根看作兄弟) 。
(2)切线(保留最左边子女为独生子女，将其他子女分支切掉) 。
(3)旋转(以最左边树的根为轴，顺时针向下旋转45度) 。
所以由上面三棵树转换得到的二叉树如图所示: