2017年中国传媒大学软件工程技术9066程序设计复试之数据结构(C语言版)复试仿真模拟三套题
● 摘要
一、应用题
1． 设
阶稀疏矩阵A 有t 个非零元素，其三元组表示为
表示A 才有意义？ 的
个存储单元，用二维数组存储时占用
个单元，
只有当试问：非零元
素的个数t 达到什么程度时用，共占用三元组表
元组）
时，用
【答案】稀疏矩阵A 有t 个非零元素，加上行数mu 、列数皿和非零元素个数tu （也算一个三
表示A 才有意义。解不等式得
2． 将下列出三棵树组成的森林转换为二叉树（只要求给出转换结果）。
图1
【答案】森林转换为二叉树分以下三步：
（1）连线（将兄弟结点相连，各树的根看作兄弟）。
（2）切线（保留最左边子女为独生子女，将其他子女分支切掉）。 （3）旋转（以最左边树的根为轴. 顺时针向下旋转45度）。 所以由上面三棵树转换得到的二叉树如图2所示：
图2
3． 已知n 阶下三角矩阵A （即当时，有，按照压缩存储的思想，可以将其主对角线以）
下所有元素（包括主对角线上元素）依次存放于一维数组B 中，请写出从第一列开始采用列序为主序分配方式时在B 中确定元素的存放位置的公式。
【答案】2
阶下三角矩阵元素第1列到第
列是梯形，元素数为
第1列有n 个元素，第j 列有而在第j 列上的位置是为
4． 设二叉树BT 的存储结构如表：
表 二叉树BT 的存储结构
其中BT 为树根结点的指针，其值为6, Lchild 、Rchild 分別为结点的左、右孩子指针域data 为结点的数据域。试完成下列各题：
（1）画出二叉树BT 逻辑结构；
（2）写出按前序、中序、后序遍历该二叉树所得到的结点序列： （3）画出二叉树的后序线索树。
【答案】（1）二叉树的逻辑结构如图1所示：
个元素，所以n
阶下三角矩阵A 按列存储，其元素在一维数组B 中的存储位置k 与i 和j 的关系为：
图1
（2）前序序列：ABCEDFHGIJ 中序序列：ECBHFDJIGA 后序序列：ECHFJIGDBA
（3）:二叉树的后续线索树如图2所示：
图2
5． 某主机的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 图所示。