【简答题】电路图绘制
【单选题】已知二叉树树形如 ,其后序遍历序列为 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)?

哈夫曼树的带权路径长度是什么？
1．树的路径长度
树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。
2．树的带权路径长度(Weighted Path Length of Tree，简记为WPL)
结点的权：在一些应用中，赋予树中结点的一个有某种意义的实数。
结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。
树的带权路径长度(Weighted Path Length of Tree)：定义为树中所有叶结点的带权路径长度之和，通常记为：
其中：
n表示叶子结点的数目
wi和li分别表示叶结点ki的权值和根到结点ki之间的路径长度。
树的带权路径长度亦称为树的代价。
3．最优二叉树或哈夫曼树
在权为wl，w2，…，wn的n个叶子所构成的所有二叉树中，带权路径长度最小(即代价最小)的二叉树称为最优二叉树或哈夫曼树。
【例】给定4个叶子结点a，b，c和d，分别带权7，5，2和4.构造如下图所示的三棵二叉树(还有许多棵)，它们的带权路径长度分别为：
(a)WPL=7*2+5*2+2*2+4*2=36
(b)WPL=7*3+5*3+2*1+4*2=46
(c)WPL=7*1+5*2+2*3+4*3=35
其中(c)树的WPL最小，可以验证，它就是哈夫曼树。
注意：
① 叶子上的权值均相同时，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树。
② 最优二叉树中，权越大的叶子离根越近。
③ 最优二叉树的形态不唯一，WPL最小
怎么求哈夫曼的带权路径长度
【问题描述】
已知输入两行正整数，第二行正整数之间用空格键分开，请建立一个哈夫曼树，以输入的数字为叶节点，求这棵哈夫曼树的带权路径长度。
【输入形式】
首先第一行为输入正整数的个数，然后接下来的一行正整数，代表叶结点，正整数个数不超过1000个
【输出形式】
输出相应的权值
【样例输入】
5
4 5 6 7 8
【样例输出】
69
关于哈夫曼树——
1、 路径长度
从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称做路径长度。
1、 树的路径长度
路径长度就是从树根到每一结点的路径长度之和。
1、 哈夫曼树：
带权路径长度WPL(Weighted Path Length)最小的二叉树，也称为最优二又树。
例： 上图的WPL=1*5 + 2*15 + 3*40 + 4*30 + 4*10= 315
先了解通过刚才的步骤，我们可以得出构造哈夫曼树的算法描述。
1、根据给定的n个权值{w［1］，w［2］，…，w［n］}构成n棵二叉树的集合F={T［1］，T［2］，…T［n］}， 其中每棵二叉树T［i］;中只有一个带权为w［i］的根结点，其左右子树均为空。
2、在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的。二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和，
3、在F中删除这两棵树，同时将新得到的二义树加入F中。
4重复2和3步骤，直到F只含一棵树为止。这棵树便是哈夫曼树。
结合例题说明一下这个算法
那么可以由上面的哈夫曼树计算出最小带权路径长度
WPL = 1*9 + 2*5 + 3*2 + 4*1 + 4*2 =37
另外还可以有另外一个方法，结合算法描述仔细观察发现最小带权路径长度为非叶子结点的和 ，即
WPL= 19 + 10 +5 +3=37
至于算法的正确性，一下子也想不到什么好的办法来证明，不过应该是可以逻辑推导过来的。
那么要实现这段程序，由上面的算法描述图我们已经知道差不多了，主要分为三步：
一、排序，直到数组中只有一个数则退出
二、最小两个数加起来，即为非叶子节点，累加到累加器中
三、把最小两个数加起来作为一个新的值保存在数组中，去掉最小两个值，跳回第一步
#include《stdio.h》
#include《stdlib.h》 //qsort();
#define N 1010
int rising(const void *a， const void *b)
{
return *(int*)a - *(int*)b;
}
int main()
{
int leaf［N］ = {0}， n， i， sum = 0;
scanf(“%d”， &n);
for(i=0; i《n; i++)
scanf(“%d”， leaf+i);
for(i=0; i《n-1; i++)
{
qsort(leaf+i， n-i， sizeof(leaf［0］)， rising); //排序并剔除已使用的叶结点
leaf［i+1］ += leaf［i］; //合并两个最小的叶结点成一新的节点(放在leaf［i+1］中)
sum += leaf［i+1］; //总路径长 = 所有非叶结点之和
}
printf(“%d\n”， sum);
return 0;
}
打开APP阅读更多精彩内容
点击阅读全文

计算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上记录自己的学习到的一些零碎。
前人栽树，后人乘凉。我也要努力成为一个前人！不做一个只会伸手的懒虫！
欢迎大家指出我的不足！【作揖】

二叉树计算带权路径长度（WPL）的算法

更多内容请访问点击我的主页


题目 :

二叉树的带权路径长度是二叉树中所有叶子结点的带权路径长度之和。给定二叉链表的存储的结点结构为




left
weight
right





weight存储的是叶子结点的非负权值。设计算法求二叉树的带权路径长度WPL。
WPL = ∑ 叶子结点的权值 × 结点到根结点的分支个数 


例如：


非递归算法

算法思想：根据公式，需要记录每个结点到根结点的分支个数，这个过程通过对树进行广度遍历（借助队列）进行记录。

在非叶子结点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。 ↩︎