【2014年数据结构真题】

41. (13分）二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。

给定一棵二叉树T,采用二叉链表存储，结点结构如下：

其中叶结点的weight域保存该结点的非负权值。 设root为指向T的根结点的指针， 请设计求T

的WPL的算法， 要求：

1. 给出算法的基本设计思想。

2. 使用C或C++语言， 给出二叉树结点的数据类型定义。

3. 根据设计思想， 采用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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

42. (10分）某网络中的路由器运行OSPF路由协议， 题42表是路由器R1维护的主要链路状态信息(LSI),题42图是根据题42表及R1的接口名构造出来的网络拓扑。

题42表 R1 所维护的 LSI

题 42 图 Rl 构造的网络拓扑

请回答下列问题。

1. 本题中的网络可抽象为数据结构中的哪种逻辑结构？

2. 针对题42表中的内容， 设计合理的链式存储结构， 以保存题 42表中的链路状态信息
   (LSI)。要求给出链式存储结构的数据类型定义，并画出对应 题42表的链式存储结构示意图（示意图中可仅以ID标识结点）。

3)按照迪杰斯特拉( Dijksta)算法 r 的策略， 依次给出R1到达题42图中子网192.1.x.x的

最短路径及费用。

解；

(1) 题中的网络是简单的网络拓扑图，可以抽象理解为无向图

(2) 链式存储结构如下图所示

第二问考试的时候能跳就跳吧

(3)计算结果如下所示