-
2021-01-30 15:06:53
【简答题】电路图绘制
【单选题】已知二叉树树形如 ,其后序遍历序列为 e,a,c,b,d,g,f ,在二叉树中与 b 同层次的结点是( )。
【单选题】在一个顺序存储的循环队列中,若队尾指针指向队尾元素的后一个位置,则队头指针一般指向队头元素的( )。
【单选题】一个广义表为 ( a, (b, c), d, (), ((f, g), h) ),则该广义表的长度与深度分别为()。
【单选题】先序遍历图示二叉树的结果为
【单选题】深度为4的满二叉树的结点数为()。
【单选题】下面的叙述正确的是( )。
【单选题】二维数组A中,每个元素A的长度为3个字节,行下标i从0到7,列下标j从0到9,从首地址SA开始连续存放在存储器内,该数组按列存放时,元素A[4][7]的起始地址为()。提示:是按列存放。
【单选题】设栈S的初始状态为空,元素abcdefg依次进入栈S。若出栈顺序为bdcfeag,则栈S的容量至少是 ( )。
【单选题】栈和队列的共同点( )。
【单选题】已知二叉树树形如 ,其后序遍历序列为 e,a,c,b,d,g,f ,在二叉树中与 d 同层次的结点是( )。
【单选题】一棵二叉树的先序序列: abdfcegh,中序序列:bfdagehc。后序遍历序列为( )。
【单选题】如图 所示二叉树的中序遍历序列是( )。
【单选题】在栈中存取数据的原则是( )。
【单选题】已知入栈序列为1 2 3 4 5 6 7。出栈操作可以随意进行(只要栈不为空),且栈最多可容纳3个元素。则下列合法的出栈序列是
【单选题】二维数组A中,每个元素A的长度为3个字节,行下标i从0到7,列下标j从0到9,从首地址SA开始连续存放在存储器内,该数组按行存放时,数组元素A[7][4]的起始地址为( )。
【单选题】设有一个空栈,现有输入序列为1、2、3、4、5, 经过push,push,pop,push,pop,push,push后,输出序列是( ) 。
【单选题】设森林T中有4棵树,第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后,根结点的右子树上有( )个结点。
【单选题】若一棵二叉树的后序遍历序列是{ 1, 3, 2, 6, 5, 7, 4 },中序遍历序列是{ 1, 2, 3, 4, 5, 6, 7 },则下列哪句是错的?
【单选题】92 、给定二叉树如下图 所示。设 N 代表二叉树的根, L 代表根结点的左子树, R 代表根结点的右子树。若遍历后的结点序列为 3 、 1 、 7 、 5 、 6 、 2 、 4 ,则其遍历方式是:
【单选题】若已知一队列用单向链表表示,该单向链表的当前状态(含3个对象)是:1->>3,其中x->y表示x的下一节点是y。此时,如果将对象4入队,然后队列头的对象出队,则单向链表的状态是:
【单选题】假设有六列火车,按编号1,2,3,4,5,6的顺序开进一个栈式结构的站台,问下列序列中,哪个是可能的出站序列。( )
【单选题】设森林T中有4棵树,第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后,根结点的左子树上有( )个结点。
【简答题】电容式传感器电路图绘刺
【单选题】设一个栈的输入序列是1、2、3、4、5,则下列序列中,是栈的合法输出序列的是?
【单选题】已知二叉树树形如 ,其后序遍历序列为 e,a,c,b,d,g,f ,在二叉树中与 c 同层次的结点是( )。
【单选题】将线性表La和Lb头尾连接,要求时间复杂度为O(1),且占用辅助空间尽量小。应该使用哪种结构?
【单选题】字符A,B,C依次进入一个栈,按出栈的先后顺序组成不同的字符串,则至多可以组成( )个不同的字符串。
【单选题】已知权值集合为{5,7,2,3,6,1,4},计算带权路径长度WPL()。
【单选题】以下说法正确的是( )。
【单选题】如果对线性表的运算只有4种,即删除第一个元素,删除最后一个元素,在第一个元素前面插入新元素,在最后一个元素的后面插入新元素,则最好使用()。
【单选题】如果对线性表的运算只有2种,即删除第一个元素,在最后一个元素的后面插入新元素,则最好使用()。
【单选题】已知二叉树树形如 ,其后序遍历序列为 e,a,c,b,d,g,f ,在二叉树中与 a 同层次的结点是( )。
【单选题】设有A、B、C、D四个元素顺序进栈,在进栈过程可以出栈,出栈次序错误的排列是
【单选题】下列关于线性表,栈和队列叙述,错误的是( )。
【单选题】稀疏矩阵是一种特殊矩阵,其特点为()。
【单选题】对于一个具有N个结点的单链表,在给定值为x的结点后插入一个新结点的时间复杂度为
【单选题】以下叙述中正确的是( )。
【单选题】以下说法正确的是( )。
【单选题】在N个结点的顺序表中,算法的时间复杂度为O(1)的操作是:
【单选题】一棵n个结点的完全二叉树从根结点这一层开始按从上往下,从左到右的顺序把结点依次存储在数组A[1..n]中。设某个结点在数组中的位置为i, 则若它有右孩子,则右孩子结点的位置是()。
【单选题】阅读下列程序,其功能是()。 typedef struct { ElemType *list; int size; intMaxSize; }SeqList; void fun1(SeqList&L) { int i, j; ElemType temp; for (i=0, j= L.size-1; i
【单选题】在循环顺序队列中,假设以少用一个存储单元的方法来区分队列判满和判空的条件,front和rear分别为队首和队尾指针,它们分别指向队首元素和队尾元素的下一个存储单元,队列的最大存储容量为maxSize,则队列的长度是( )。
【单选题】在一个用数组表示的完全二叉树中,如果根结点下标为1,那么下标为17和19这两个结点的最近公共祖先结点是( )(数组下标)。
【单选题】在具有N个结点的单链表中,实现下列哪个操作,其算法的时间复杂度是O(N)?____。
【单选题】若用大小为6的数组来实现循环队列,且当前front和rear的值分别为0和4。当从队列中删除两个元素,再加入两个元素后,front和rear的值分别为多少?
【单选题】若用一个大小为6的数组来实现循环队列,且当前rear和fornt的值分别为0和3。从当前队列中删除一个元素,再加入两个元素后,rear和front的值分别为( )。
【单选题】以下不是栈的基本运算的是( )。
【单选题】对于容量为n的循环队列Q,队尾指针是Q.rear,队头指针是Q.front,则出队时头尾指针需要进行的操作为 ( )
【单选题】在具有N个结点的单链表中,实现下列哪个操作,其算法的时间复杂度是O(N)?
更多相关内容 -
二叉树的带权路径长度WPL算法实现
2021-10-19 18:26:01二叉树的带权路径长度WPL是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树,采用二叉链表存储,叶子结点的weight域为该结点的权值。请设计一个算法,求二叉树的带权路径长度。 算法思想 可以使用先序遍历...题目描述
二叉树的带权路径长度WPL是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树,采用二叉链表存储,叶子结点的weight域为该结点的权值。请设计一个算法,求二叉树的带权路径长度。
算法思想
可以使用先序遍历或层次遍历解决问题。
<1>算法思想一:基于先序递归遍历。
用一个static变量记录WPL,把每个结点的深度作为递归函数的一个参数传递。- 若该结点是叶结点,则变量WPL加上该结点的深度与权值之和。
- 若该结点是非叶结点,则左子树不为空时,对左子树调用递归算法,右子树不为空时,对右子树调用递归算法,深度参数均为本结点的深度参数加1。
<2>算法思想二:基于层序遍历。
使用队列进行层次遍历,并记录当前的层数。- 当遍历到叶结点时,累计WPL。
- 当遍历到非叶结点时,把该结点的子树加入队列。
- 当某结点为该层最后一个结点时,层数自增1。
- 队列空时遍历结束,返回WPL。
实现代码
<1> 算法一的函数代码实现:
int WPL_PreOrder(BTree root, int deep){ static int wpl = 0; if(root->lchild==NULL && root->rchild==NULL){ //若为叶结点,累积 wpl += deep*root->weight; } if(root->lchild != NULL){ //若左子树不空,对左子树递归遍历 WPL_PreOrder(root->lchild, deep+1); } if(root->rchild != NULL){ //若右子树不空,对右子树递归遍历 WPL_PreOrder(root->rchild, deep+1); } return wpl; }
<2>算法二的函数代码实现:
int WPL_Level(BTree root){ queue<BNode *> treenode; //队列 int wpl = 0; int deep = 0; //初始化深度 BNode *lastNode; //记录当前最后一个结点 BNode *newlastNode; //记录下一层最后一个结点 lastNode = root; //初始化为根结点 newlastNode = NULL; //初始化为空 treenode.push(root); //根结点入队 while(!treenode.empty()){ //栈不空时循环 BNode *top = treenode.front(); //取出队首元素 treenode.pop(); if(top->lchild==NULL && top->rchild==NULL){ wpl += deep*top->weight; }//若为叶结点,累加 if(top->lchild != NULL){ //若为非叶结点则把左孩子结点入队 treenode.push(top->lchild); newlastNode = top->lchild; //设置下一层最后一个结点 } if(top->rchild != NULL){ //右孩子结点入队 treenode.push(top->rchild); newlastNode = top->rchild; } if(top == lastNode){ //若该结点为本层最后一个结点 lastNode = newlastNode; //更新 deep+=1; //深度加1 } } return wpl; }
-
C++二叉树计算带权路径长度(WPL)的算法
2019-11-03 08:20:44二叉树计算带权路径长度(WPL)的算法 更多内容请访问点击我的主页 题目 : 二叉树的带权路径长度是二叉树中所有叶子结点的带权路径长度之和。给定二叉链表的存储的结点结构为 left weight right weight...二叉树计算带权路径长度(WPL)的算法
更多内容请访问点击我的主页
-
题目 :
-
二叉树的带权路径长度是二叉树中所有叶子结点的带权路径长度之和。给定二叉链表的存储的结点结构为
left weight right -
weight存储的是叶子结点的非负权值。设计算法求二叉树的带权路径长度WPL。
WPL = ∑ 叶子结点的权值 × 结点到根结点的分支个数 1
例如:
非递归算法
- 算法思想:根据公式,需要记录每个结点到根结点的分支个数,这个过程通过对树进行广度遍历(借助队列)进行记录。
在非叶子结点weight初值为-1,叶子结点初值设为非负权值。
最后对队列进行逐个访问,如果weight != -1,那就计算该点。
wpl += (Q[i].p->weigth) * (Q[i].p->lno - 1); //WPL公式代码
这里改造队列的结点结构
typedef struct { LBTree* p; //树的结点 int lno; //结点深度 }Queue;
- 伪代码
typedef struct { LBTree* p; int lno; }Queue; int WPL(LBTree* lbt) { Queue Q[maxSize]; int front,rear; front = rear = 0; int Lno = 1; LBTree* q = lbt; Q[rear].p = q; Q[rear].lno = Lno; rear++; while (front != rear) { q = Q[front].p; Lno = Q[front].lno; front++; if (q->lchild != NULL) { Q[rear].p = q->lchild; Q[rear].lno = Lno + 1; rear++; } if (q->rchild != NULL) { Q[rear].p = q->rchild; Q[rear].lno = Lno + 1; rear++; } } int wpl = 0; for (int i = 0; i < rear; i++) { if (Q[i].p->weigth != -1) wpl += (Q[i].p->weigth) * (Q[i].p->lno - 1); } return wpl; }
递归算法 (推荐)
- 算法描述:本算法采用的是统计叶子结点算法基础上改造而来的。只是在参数列表定义了结点到根的分支个数。进行一个递归计算。统计结点数在个人主页有相关算法。
- 代码如下:
int WPLrec(LBTree* lbt,int n) { int wpl = 0; if (lbt != NULL) { if (lbt->lchild == NULL && lbt->rchild == NULL) wpl += n * lbt->weigth; wpl += WPLrec(lbt->lchild, n + 1); wpl += WPLrec(lbt->rchild, n + 1); } return wpl; }
结点到根结点的分支个数 = 该结点的深度 - 1。 ↩︎
-
-
使用取巧的方式计算Huffman树的带权路径长度WPL
2020-03-18 21:41:10计算Huffman树的带权路径长度WPL 编程背景 Huffman编码是通信系统中常用的一种不等长编码,它的特点是:能够使编码之后的电文长度最短。 输入:第一行为要编码的符号数量n,第二行~第n+1行为每个符号出现的频率 ...计算Huffman树的带权路径长度WPL
编程背景
Huffman编码是通信系统中常用的一种不等长编码,它的特点是:能够使编码之后的电文长度最短。
- 输入:第一行为要编码的符号数量n,第二行~第n+1行为每个符号出现的频率
- 输出:对应哈夫曼树的带权路径长度WPL
- 测试用例举例:
思路
因为要完成对应的输入输出,我首先想到的就是通过最简单的一维数组的方式。因为本题只要求计算WPL,观察其输入输出,故我并没有考虑使用链表。
借鉴
通过网站上浏览资料,发现一个好技巧:
WPL 为所有叶节点的带权路径长度之和,同时也是所有非叶子结点的权值之和。
详细解释见:哈夫曼树的WPL值的计算程序实现
m函数:返回一维数组S中最小的数,并将其从数组中剔出
int m(){ int min, position=0; min = S[0]; int i=0; for(i=0; i<len; i++){ if(min > S[i]){ min = S[i]; position = i; } } for(i=position; i<len-1;i++) S[i] = S[i+1]; S[(len--)-1]=0; return min; }
main函数
int main(){ int n; int i, temp; scanf("%d", &n); len = n; for(i=0; i<n; i++) scanf("\n%d", &S[i]); while(len>1){ temp = m() + m(); WPL += temp; S[len++] = temp; } printf("WPL=%d\n",WPL); return 0; }
后记
- 作为一个步入C殿堂不久的小白,如今开始在CSDN上记录自己的学习到的一些零碎。
- 前人栽树,后人乘凉。我也要努力成为一个前人!不做一个只会伸手的懒虫!
- 欢迎大家指出我的不足!【作揖】
-
哈夫曼树带权路径长度怎么计算
2021-01-17 13:41:582.树的带权路径长度(Weighted Path Length of Tree,简记为WPL)结点的权:在一些应用中,赋予树中结点的一个有某种意义的实数。结点的带权路径长度:结点到树根之间的路径长度与该结点上权的乘积。树的带权路径长度... -
设计算法求二叉树的带权路径长度(WPL)
2020-04-22 20:58:22设计算法求二叉树的带权路径长度(WPL) 二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。 队列的基本操作以严蔚敏编写的教材为准。 基于层次遍历的算法: int WPL_LevelOrder (BiTree T) { ... -
哈夫曼树 带权路径长度WPL
2016-03-20 00:25:43这是定义的计算WPL的方式,然后我们看一下另一个奇妙的结果20 + 9 + 11 + 5 = 45; 证明如下:(证明并不充分 详细点的证明和讲解 ) 如果知道了这个结论,这种题目的难度完全降没了。接下来就贴代码了... -
【哈夫曼树】带权路径长度WPL
2020-07-26 17:29:55long long x,y,temp,wpl; while(scanf("%d", &n) != EOF){ //多组输入 wpl = 0; //初始化权值 while(!q.empty()) q.pop(); //初始化队列 for(i = 0; i ; i++){ scanf("%lld", &temp); q.push(temp); } while(q.size... -
哈夫曼树的带权路径长度总结wpl
2022-03-03 11:28:34//哈夫曼树的带权路径长度 //总结 //法一:①先对权值从小到大排序。 //②选两个最小的加起来成为一个新结点,而这两个最小的值是新结点的左右子结点。 //③两个老的结点去掉,新的结点放入再次排序然后重复过程②。... -
解决关于哈夫曼编码计算带权路径长度问题
2021-05-26 01:38:34这是在做一道编程提示遇到的,学习了一位博主的编码,其中有些问题未能理解,分析解决掉。首先什么是哈夫曼树:哈夫曼树,又称最优二叉树,是一类带权路径长度最短的树。...树的带权路径长度记为WPL= (W1*... -
哈夫曼树的构造算法以及计算加权路径长度WPL
2020-04-18 21:50:19只有知道路径长度才能计算带权路径长度 方法有很多,这里采用后序遍历的非递归算法来实现。 如果不懂后序遍历的非递归算法,可以参考下面这个博文的对应内容: 二叉树遍历全面总结(先,中,后序,层序,递归及非... -
【数据结构笔记16】哈夫曼树,带权路径长度(WPL),哈夫曼编码
2019-09-28 11:28:28哈夫曼树是WPL(带权路径长度)最小的二叉树。使用这种思想,提出哈夫曼编码,节省空间。 -
哈夫曼树带权路径长度求解(C语言实现)
2021-03-02 12:32:40需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出哈夫曼树的带权路径长度(WPL)。 输入格式: 第一行输入一个数n,第二行输入n个叶结点(叶结点权值不超过1000,2<=n&... -
计算WPL·哈夫曼树构建及带权路径长计算
2020-11-06 14:18:07计算WPL·哈夫曼树构建及带权...对应哈夫曼树的带权路径长度WPL 测试样例 测试样例1 5 7 5 2 4 9 WPL=60 测试样例2 5 2 4 2 3 3 WPL=32 解答 想法 假设我们给定a,b,c,d,e,f的权值分别为9,12,6,3,5,15 1、首先, -
哈夫曼编码以及带权路径长度的计算
2019-09-30 19:36:26在使用WPL=(W1*L1+W2*L2+W3*L3+…+Wn*Ln)计算带权路径长度 实现: 构造哈夫曼树: 每次取出最小的两个数构造第一层,在给出的哈夫曼编码中是2和4 246 接下来是6和5 245611 接下来是 7 和 9 7916 下一步是 11 和 12 ... -
哈夫曼树结构和带权路径长度计算
2017-11-08 13:55:38哈夫曼树是一种带权路径长度最短的二叉树,也称为最优二叉树。下面用一幅图来说明。 它们的带权路径长度分别为: 图a: WPL=5*2+7*2+2*2+13*2=54 图b: WPL=5*3+2*3+7*2+13*1=48 可见,... -
求二叉树的带权路径长度
2021-08-09 21:24:27二叉树的带权路径长度: 每个叶结点的深度与权值之积德总和。 方法:先序遍历或层次遍历 结点类型定义: typedef struct BiTNode{ int weight; struct BiTNode *lchild,*rchild; }BiTNode,BiTree; 基于先序: ... -
计算二叉树带权路径和(WPL)
2020-06-26 23:54:03二叉树的带权路径和,指的是二叉树的所有叶子节点的权值 * 其深度 之和。 本次因为是完整的程序,所以包含 1)输入前序、中序序列 创建二叉树 2)层序遍历打印出二叉树 3)计算WPL 数据结构定义 typedef struct ... -
绘制哈夫曼树 及 计算其带权路径长度
2020-04-28 12:14:38文章目录 3, 5, 7, 8 , 11, 14, 23, 29 83+113+143+74+35+55+232+292 = 271 -
哈夫曼编码计算带权路径长度问题
2017-10-26 10:09:39哈夫曼树,又称最优二叉树,是一类带权路径长度最短的树。 也就是根节点到节点的中的长度最小,当然条件就是,每条路径都是...树的带权路径长度记为WPL= (W1*L1+W2*L2+W3*L3+…+Wn*Ln) 此时WPL=32×1+24×2+ -
【题解】【AcWing】3766. 二叉树的带权路径长度
2021-07-20 22:54:03二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和,也就是每个叶结点的深度与权值之积的总和。 给定一棵二叉树 TTT ,请你计算并输出它的WPL。 注意,根节点的深度为 000 。 样例 输入:二叉树[8,... -
哈夫曼树(带权路径长度+树的带权路径长度+哈夫曼树定义+构造哈夫曼树+哈夫曼树性质+哈夫曼编码+计算平均...
2020-04-19 18:22:45树的带权路径长度WPL 哈夫曼树构造 哈夫曼树性质 哈夫曼编码 试题 -
2014 计算二叉树的带权路径长度
2022-04-15 21:42:331) 思想: 设置全局变量sum统计权值之和 ...//带权路径长度 int sum; int WPL(Tree T,int deep){ if(T->left==NULL&&T->right==NULL) { sum+=deep*(T->weight); //为根结... -
树的带权路径长度和哈夫曼树
2021-11-09 00:09:09树的所有叶子结点的带权路径长度之和,称为树的带权路径长度,英文缩写为 `WPL`,从百度百科中得到的信息为 “树的带权路径长度(weighted path length of tree)是2018年公布的计算机科学技术名词”,这就有点奇怪... -
Huffman树的带权路径长度
2020-10-21 20:35:13给定n个权值(权值均是大于0的正整数),构造赫夫曼树HT,并求出赫夫曼树HT的带权路径长度。 注意:构造赫夫曼树HT时,在将2棵二叉树合并成一棵新的二叉树时,将根结点权值小的用作左子树! 输入 先输入权值的个数n(n... -
哈夫曼树-创建,编码,解码,带权路径长度(含全部代码)
2019-02-04 10:56:06void WPL() 计算带权路径长度 所选实例: 所选实例 创建哈夫曼树 步骤: 假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为: (1) 将w1、w2、...