2017年中国传媒大学软件工程技术9066程序设计复试之数据结构(C语言版)复试实战预测五套卷
● 摘要
一、应用题
1． 二叉树的带权路径长度（WPL ）是二叉树中所有叶结点的带权路径长度之和，给定一棵二叉树T ，采用二叉链表存储，节点结构为：
其中叶节点的weight 域保存该结点的非负权值。设root 为指向T 的根节点的指针，设计求T 的WPL 的算法。要求：
（1）给出算法的基本设计思想；
（2）使用C 或C++语言，给出二叉树结点的数据类型定义；
（3）根据设计思想，采用C 或C++语言描述算法，关键之处给出注释。
【答案】（1）算法的基本思路是利用利用递归的思想来求解二叉树的带权路径长度，如果当前节点不是叶子节点，那么当前节点为根的树的带权路径长度便等于它的子树的带权路径长度之和，对于此函数要传入一个当前节点的树高的形参，那么递归调用孩子节点时只需要将这个形参加一即可。
（2）
typedef struct BiNode
（3）具体算法实现如下：
如果当前节点为空节点
//如果当前节点的左右孩子节点都为空，即当前节点为叶子节点，直接返回当前节点的
WPL
//如果当前节点不是叶子节点，则对当前节点的左右子树进行递归，返回左右子树WPL 之和
2． 已知一个带有表头结点的单链表，结点结构为datalink , 假设该链表只给出了头指针list 。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k 个位置上的结点（k 为正整数）。若查找成功，算法输出该结点的data 域的值，并返回1; 否则，只返回0。要求：
（1）描述算法的基本设计思想； （2）描述算法的详细实现步骤；
（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C 或，关键之处请给出简要注释。 现）
【答案】（1）算法的基本设计思想定义两个指针变量p 和q ，初始时均指向头结点的下一个结点。p 指针沿链表移动；当p 指针移动到第k 个结点时，q 指针开始与p 指针同步移动；当p 指针移动到链表最后一个结点时，因为p 和q 相隔k ，故q 指针所指元素为倒数第k 个结点。以上过程对链表仅进行一遍扫描。
（2）算法的详细实现步骤
①count=0, p 和q 指向链表表头结点的下一个结点； ②若p 为空，转⑤; ，
③若count 等于k ，则q 指向下一个结点；否则，count=count+l; ④p 指向下一个结点，转步骤②；
⑤若count 等于k ，则查找成功，输出该结点的data 域的值，返回1; 否则，查找失败，返回0;
⑥算法结束。 （3）算法实现
3． 已知有6个顶点（顶点编号为0--5）的有向带权图G , 其邻接矩阵A 为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。
要求：
或JA V A 语言实
（1）写出图G 的邻接矩阵A 。 （2）画出有向带权图G 。
（3）求图G 的关键路径，并计算该关键路径的长度。
【答案】（1）由题可以画出待定上三角矩阵的结构图如下（图中? 为待定元素）：
可以看出，第一行至第五行主对角线上方的元素分别为5, 4, 3, 2, 1个，由此可以画出压缩存储数组中的元素所属行的情况，如下图所示：
将各元素填入各行即得邻接矩阵：
（2）根据第一步所得矩阵A 容易做出有向带权图G , 如下：
（3）下图中粗线箭头所标识的4个活动组成图G 的关键路径。
由上图容易求得图的关键路径长度为：4+5+4+3 = 16。
4． 为什么文件的倒排表比多重表组织方式节省空间？
【答案】倒排表有两项，一是次关键字值，二是具有相同次关键字值的物理记录号，这些记录号有序且顺序存储，不使用多重表中的指针链接，因而节省了空间。