【2014年数据结构真题】
41. (13分）二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。
给定一棵二叉树T,采用二叉链表存储，结点结构如下：
其中叶结点的weight域保存该结点的非负权值。 设root为指向T的根结点的指针， 请设计求T
的WPL的算法， 要求：
-
给出算法的基本设计思想。
-
使用C或C++语言， 给出二叉树结点的数据类型定义。
-
根据设计思想， 采用C或C++语言描述算法， 关键之处给出注释。
最优解
此题比较简单，直接用最优解
typedef struct BTNode{int weight;struct BTNode *left,*right;
}BTNode;int fun(BTNode *root,int deep){int A,B;if(root==NULL)return 0;if(root->left==NULL&&root->right==NULL)return (root->weight)*deep;A=fun(root->left,deep+1);B=fun(root->right,deep+1);return A+B;
}void main(BTNode *root){fun(root,0);
}
42. (10分）某网络中的路由器运行OSPF路由协议， 题42表是路由器R1维护的主要链路状态信息(LSI),题42图是根据题42表及R1的接口名构造出来的网络拓扑。
题42表 R1 所维护的 LSI
题 42 图 Rl 构造的网络拓扑
请回答下列问题。
-
本题中的网络可抽象为数据结构中的哪种逻辑结构？
-
针对题42表中的内容， 设计合理的链式存储结构， 以保存题 42表中的链路状态信息
(LSI)。要求给出链式存储结构的数据类型定义，并画出对应 题42表的链式存储结构示意图（示意图中可仅以ID标识结点）。
3)按照迪杰斯特拉( Dijksta)算法 r 的策略， 依次给出R1到达题42图中子网192.1.x.x的
最短路径及费用。
解；
(1) 题中的网络是简单的网络拓扑图，可以抽象理解为无向图
(2) 链式存储结构如下图所示
第二问考试的时候能跳就跳吧
(3)计算结果如下所示
