家具公司网站建设,运用虚拟机建设网站,学校网站建设需求文档,企业网站模板建立流程41. (13分#xff09;二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。
给定一棵二叉树T,采用二叉链表存储#xff0c;结点结构如下#xff1a; 其中叶结点的weight域保存该结点的非负权值。 设root为指向T的根结点的指针#xff0c; 请设计求T
的WPL…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(rootNULL)return 0;if(root-leftNULLroot-rightNULL)return (root-weight)*deep;Afun(root-left,deep1);Bfun(root-right,deep1);return AB;
}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)计算结果如下所示
