数据逻辑结构包括①（集合结构）、②（线性结构）和③（树形结构）三种类型,树形结构和图形结构合称为④（非线性结构）.
集合结构：集合中任何两个数据元素之间都没有逻辑关系,组织形式松散.
线性结构：结点按逻辑关系依次排列形成一个“锁链”.
树形结构：树形结构具有分支、层次特性,其形态有点像自然界中的树.

2.数据结构的存储结构：顺序、链式、索引、哈希

顺序存储结构：循环队列

该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。

由此得到的存储表示称为顺序存储结构（Sequential Storage Structure ），通常借助程序语言的数组描述。

该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。

链式存储结构：链表

该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构（Linked Storage Structure）, 通常借助于程序语言的指针类型描述。

索引存储方法：

该方法通常在储存结点信息的同时，还建立附加的索引表。索引表由若干索引项组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（Dense Index ）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引(Spare Index)。索引项的一般形式是：(关键字、地址)

关键字是能唯一标识一个结点的那些数据项。稠密索引中索引项的地址指示结点所在的存储位置；稀疏索引中索引项的地址指示一组结点的起始存储位置。

散列存储方法：哈希表

该方法的基本思想是：根据结点的关键字直接计算出该结点的存储地址。

题1：以下与数据的存储结构无关的术语是（）。（答案在上面找）

A.循环队列 B.链表 C.哈希表 D.栈

题2：以下哪个数据结构不是多型数据类型（）

A.栈 B.广义表 C.有向图 D.字符串

题3：数据的物理结构包括（）的表示和（）的表示。

题4：对于给定的n个元素，可以构造出的逻辑结构有：四种

题5：数据的逻辑结构是指____, 一个数据结构在计算机中的__称为存储结构。

题6：抽象数据类型的定义取决于它的一组____,而与____无关，即不论其内部结构如何变化，只要它的__不变，都不影响其外部使用。

solution2：数据结构中的“多型数据类型”是什么？_百度知道

solution3：数据元素数据元素间的关系

solution4：集合、线性结构、树形结构、图状结构

solution5：计算机的组织形式标识（映像）

solution6：逻辑特性在计算机内部如何表示和实现数学特性

算法

算法：是对特定问题求解步骤的一种描述，它是指令的有限序列。每条指令表示一个或多个操作。

特性：有穷性、确定性、可行性、输入、输出。（有穷确定可行、输出输入）

要求（目标）：正确性、可读性、健壮性、好的时空效率。（正读《健壮效率》）

第二章线性表

线性表是具有n个数据元素的有限序列n>0

题：

1.若线性表最常用的操作是存取第I个元素及其前驱和后继元素的值，应采用（）存储方式

A 单链表 B 双向链表 C 单循环链表 D顺序表

2.在链式存储结构中，数据之间的关系是通过（）体现的。

A指示数据元素的指针 B指针

3.(1)静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关(2)静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。(3)静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动

错误的是____。

4.长度为n的线性表采用顺序存储，插入一个结点的移动节点的平均次数为

A n B n/2 C (n-1)/2 D (n+1)/2

5.线性表(a1,a2,…,an)以链接方式存储时,访问第i位置元素的时间复杂性为()

A O(i) B O(1) C O(n) D O(i-1)

6.单向链表长度为n，链接到单向链表长度为m的后，所需时间复杂性为（）

7.线性表的实现方法中元素必须是

A 整数 B字符 C 相同类型 D 结构类型

解：

1.D 2.B 3.(1) 4.B 5.D 6.O(m) 7.C

填空题

1. 对长度为n的线性表采用顺序查找,在等概率的条件下,查找成功的平均检索长度为____。在长度为n的顺序表中删除第i (1≤i≤n)个数据元素需要移动____个数据元素。在长度为n的顺序表中的第i (1≤i≤n)个数据元素之前插入一个新元素，需要移动____个数据元素。

2. 线性表L=(a1, a2,…, an)用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是____

3. 在单链表中设置头结点的作用是____

4. 循环单链表的最大优点是:____

5. 顺序存储结构是通过____表示元素之间的关系的;链式存储结构是通过____表示元素之间的关系的。

6. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共____个,单链表为____个

7. 带头结点的双循环链表L为空表的条件是____

8.判断带头结点的单循环链表L仅有一个元素结点的条件是____

9.带头结点的双循环链表L中只有一个元素结点的条件是____

解：

(n+1)/2、n-i、n-i+1 （特殊值法也可带具体值判断推出的结果是否正确）
(n-1)/2
有头结点后，插入元素和删除元素的算法统一了，不再需要判断是否在第一个元素之前插入和删除第一个元素。另外，不论链表是否为空，链表指针不变。减少错误，方便编程。牛客
从任一结点出发都可访问到链表中每一个元素
结点物理上相邻、结点指针
4、2
L->next == L && L->prior == L
L->next->next == L && L->next != L
L->next->next == L && L->prior->prior == L && L->next != L

第三章栈和队列

中缀表达式转前、后缀表达式：1.括号法2.栈内栈外优先级3.图解

题：

1.已知循环队列存储在一维数组A[0..n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是（)。

A.0,0 B.0, n-1 C n-1, 0 D.n-1, n-1

2.已知操作符包括‘+’，‘-’，‘*’，‘/’，‘(’、‘)’ 。将中缀表达式a+b-a*((c+d)/e-f)+g转化为等价的后缀表达式ab+acd+e/f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是（）

A. 5 B. 7 C. 8 D. 11

3.一个栈的入栈序列为1,2,3，…,n，其出栈序列是p1,p2, p3，…,pn。若p2=3，则p3可能取值的个数是（）。
A.n-3 B.n-2 C.n-1 D.无法确定

4.假设栈初始为空，将中缀表达式a/b+(c*d-e*f)/g转化为等价的后缀表达式的过程中，当扫描到f时，栈中的元素依次是（）

A. +(*- B. +(-* C. /+(*-* D. /+-*

5.一个栈的输入序列为1,2,3，…, n，若输出序列的第一个元素是n，输出第i (1≤i≤n)个元素是（）。

A.不确定 B.n-i C.i D.n-i+1

6.利用栈求表达式的值时，设立操作数栈OPND，设OPND只有两个存储单元，在下列表达式中，不发生上溢的是（）。
A.A-B*(C-D) B.(A-B)*C-D C.(A-B*C)-D D.(A-B)*(C-D)

7.(多选）若已知一个栈的入栈序列是1,2,3,4，其出栈序列为p1, p2, p3, p4，则p2, p4可能为()。
A.2、4 B.2、1 C.4、3 D.3、4

8.4个圆盘的Hanoi塔,总的移动次数为()

A.7 B.8 C.15 D.16

9.在带头结点的链队列中,队头指针指向链表的()

A.最后一个元素结点 B.第一个元素结点 C.头结点 D.都不是

10.下列更合适表示队列的链表结构是（）。

A.单向链表 B.单向循环链表 C.双向链表 D.双向循环链表

11.队列的“先进先出”特性是指（）。

A.最后插入队列中的元素总是最后被删除 B.当同时进行插入、删除操作时，总是插入操作优先

C.每当有删除操作时，总要先做一次插入操作 D.每次从队中删除的总是最早插入的元素

12.执行（）操作时,需要使用队列作辅助存储空间。

A．查找哈希(Hash)表 B.广度优先搜索网 C.先序(根)遍历二叉树 D.深度优先搜索网

13.向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行
A. h->next=s; B.S->next=h; C.s->next=h; h->next=s; D.s->next=h->next; h->next=s;

14.已知输入序列为abcd，经过输出受限的双向队列后能得到的输出序列有
A.dacb B.cadb C.dbca D.bdac E.以上答案都不对

设一个双端队列，元素进入该队列的次序为a，b，c，d。求既不能由输入受限的双端队列得到，又不能由输出受限的双端队列得到的输出序列。

15.字符序列t3_作为下图(如图3-1)输入时，输出长度为3的，且可作C语言标识符的序列的有()。

解：

队列的入队在队尾，答案中B和D入队((n-1)+1)%n的结果为0，因为要求第1个进入队列的元素存储在A[0]处，且 front和rear分别指向队头元素和队尾元素，故选B。循环队列有取%操作。博文第四题
博文第三题，这题想错了一开始我还以为一直入知道遇到）才弹出选了B。。。好久没学忘太快啦。
1，2先于3已入栈，且其中有一个已出栈，另一个在3入栈并出栈后可立即出栈。从4到n,任何一个都可以入栈后立即出栈。因此，p3可能的取值有n-1个，故选C。就是除了1不能出栈其他都有可能。
博文第四题
注意此处输出是从后输出一开始想成第i个就是输出第i个实际应该n-i+1 （看不懂可以用1234 输出第2个试试看 4-2+1=3 ）其他解释
A -*( 错误 C (-* 错误 D (- 遇到 ) 全部弹出 *(- 错误 B自己试试看结合上面的博文
答案ABD 仅解释BC选项 B 3241 C 4第二个弹出 3只能第一个或第三个弹出
总的移动次数 $2^{n}-1$ 链接
C
B 插入把待插结点->头结点，尾指针->待插结点，更新尾指针的位置. 删除直接->next->next即可图片来源
答案A是正确的。若队列不空，每次删除的是队头元素，D的错误在于“最早”。其他解释
广度优先搜索网详解图的拓扑排序、深度优先、关键路径算法用的栈辅助；树的层次遍历、图的广度优先遍历用的队列辅助
D 头插法先指向栈头防止丢失在更新栈头
解释1 解释2可能题对不上但是思路还是一致的
注意C语言标识符即可

填空题

1. 在栈的ADT定义中，除初始化操作外，其他基本操作的初始条件都要求____

2. 多个栈共存时,最好用____作为存储结构。

3. 已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是____

4. 区分循环队列的满与空,只有两种方法,它们是____ 和____

5. 已知一循环队列的存储空间为[m..n]，其中n>m，队头和队尾指针分别为front 和 rear，则此循环队列判满的条件是____

6. 浙大程序填空题

7. 下面的程序将一个整数e压入堆栈S，实现堆栈的入栈操作，请在空格处填上适当的语句实现该操作。其中堆栈S的定义如下：

typedef struct{
  int  *base;
  int  *top;
  int stacksize;
 }SqStack;

 int Push(SqStack S,int e)
 {
     if ( ____ ){ 
            S.base=(int *) realoc(S.base,(S.stacksize+1)*sizeof(int));
            if( ____ ){
                printf("Not Enough Memory!\n");
                return(0);
             }              
             S.top=____; 
             S.stacksize=____;  
         }
     ____;    
     return 1;

 }

填空解：

栈存在。
链式存储结构
new(s); s->data=x; s->next=r->next; r->next=s; r=s;
牺牲一个存储单元、设标记。(还有设立计数器等方法）
(rear+1)%(n-m+1)==front（比较不常规）
随便看看就好
(1) S.top - S.base >= S.stacksize-1 (2) !S.base(3 ) S.base+S.stacksize-1
(4) S.stacksize+1
(5)*(++S.top)=e （此题就是双端栈）

第四章串

串是一种特殊的线性表，特殊性体现在数据元素是一个字符
两个字符串相等的充分必要条件是：串的长度相等并且两串对应字符相等。或者说两个串的串值相等
设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为O(m+n)

串的基本操作：

StrAssign(T,chars):赋值操作。把串T赋值为chars
StrCopy(&T,S): 复制操作。由串S复制得到串T
StrEmpty(S): 判空操作。若S为空串,则返回TRUE,否则返回FALSE
Strcompare (S,T): 比较操作。若S>T,则返回值>0;若s=T,则返回值=0;若s<T,则返回值<0
StrLength(S): 求串长。返回串S的元素个数
SubString(&Sub,S,pos,len): 求子串。用Sub返回串S的第pos个字符起长度为len的子串 Sub(a, 10, 5)=第十个字符(不是下标)，往后数五个包括这个字符。
Concat(&T,S1,S2): 串联接。用T返回由S1和S2联接而成的新串
Index ( S,T ): 定位操作。若主串S中存在与串T值相同的子串,则返回它在主串S中第一次出现的位置;否则函数值为0
clearString(&S): 清空操作。将S清为空串
DestroyString(&S): 销毁串。将串S销毁

视频讲解（这个讲解不适合考研即求next数组但相对于来说更容易理解不考研可以放心看考研还是算了会混乱）图解（下面的代码就是视频讲解中的考研请忽略！）

求next 和 nextval 默认下标为1

KMP(T, nt, p, np){        //伪代码
    int i=0, j=0;
    while (i < nt){
        if (T[i] == P[j]){
            i++;
            j++; 
            if ( j == np) 找到了下标从i-np/i-j 开始的字串;  
        }
        else
            if (j > 0) j = D[j-1];
            else i++;    //此时j = 0
    }
}

题：

1. 已知字符串s为"abaabaabacacaabaabcc"，模式串t为"abaabc"，采用KMP算法进行匹配，第一次出现失配（s[i] ≠ t[j]）时, i=j=5，则下次开始匹配时, i和j的值分别是（）

A. i=1,j=0 B. i=5,j=0 C. i=5,j=2 D. i=6,j=2

2. 串'ababaaababaa'的next 数组为（）

A.012345678999 B.012121111212 C.011234223456 D.012301232234

3. 字符串'ababaabab'的nextval 为（）

A.(0,1,0,1,0,4,1,0,1) B.(0, 1,0,1,0, 2,1,0,1) C.(0,1,0,1,0,0,0,1,1) D.(0,1,0,1, 0,1,0,1,1 )

4. 若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2)))其结果为

A.ABC#H#G0123 B.ABCD##2345 C.ABC##G2345 D.ABCHI#2345 E.ABC#H#G1234 F.ABCD##1234 G.ABC###01234

5. 若串S='software'，其子串的数目是（）

A.8 B.37 C.36 D.9

6. 设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身)的个数为()。

A.2n-1 B.n2 C.(n^2/2)+(n/2) D. (n^2/2)+(n/2)-1 E. (n^2/2)-(n/2)-1 F.其他情况

7.13．在下列表述中，（）是错误的。
A.含有一个或多个空格字符的串称为空格串 B.对n(n>0)个顶点的网,求出权最小的n-1条边便可构成其最小生成树

C.选择排序算法是不稳定的 D.平衡二叉树的左右子树的结点数之差的绝对值不超过1

8. 其他类常见错题，别人整理的杂七杂八的错题

9. 一个字符串中____称为该串的子串。

10. 字符运算Index(S, T, pos)的返回值是____

11. 设目标串 T='abccdcdccbaa'，模式P='cdcc'，则第____次匹配成功。

12. 设T和Р是两个给定的串，在T中寻找等于P的子串的过程称为____，又称P为____.

13. 使用“求子串”subString(S, pos , len)和“联结” concat(S1, S2)的串操作，可从串 s='conduction'中的字符得到串t="cont"，则求t的串表达式为____
14. 已知U=‘xyxyxyxxyxy’；t=‘xxy’；ASSIGN(S，U)；ASSIGN(V，SUBSTR(S，INDEX(s，t)，LENCt)+1)),ASSIGN(m，‘ww’)求REPLACE(S，y，m)=____

解：

C 这个是视频讲解的做法考研方法
C 求next 四分钟解决这里犯了个错误视频中到aba的时候因为受到以前看的kmp解析最大公共前后缀以为aba 匹配所以（匹配字+1=2）。实际是看第二个a前面的有无匹配串，即ab，无则0+1=1.具体参见视频，多看看就懂了。本章最下面有稍微提到求next （此外选择题的技巧就是不用全算完）
A注意公式或者四分钟解决（四分钟解决仅适用于求next和nextval！！）本章最下面有图解

E 解析

①substr(S1,length(S2),length(S3))=>substr('ABCDEFG',4,3)=>取到DEF;
②replace((S1,取到DEF),S3)=>replace((ABCDEFG,取到DEF),###)=>'ABC###G';
③substr(S4,index(S2,'8'),length(S2))=>substr('012345',index('9898','8'),4)=>substr('012345',2,4)=>取到1234;
concat(replace(S1,①),S3),③)=>concat(②,③)=>ABC###G1234

串中任意个连续字符组成的子序列称为该串的子串。 （必连续）；
所谓的子序列就是在原来序列中找出一部分组成的序列, （可不连续）；
子串的定义是:串中任意个连续的字符组成的子序列，并规定空串是任意串的子串，任意串是其自身的子串。
若字符串长度为n(n>0)，长为n的子串有1个，长为n-1的子串有2个，长为n-2的子串有3个，……，长为1的子串有n个。
设串中字符数为n，则其子串数目为：s=(1+n)*n/2+1
由于空串是任何串的子串，所以本题的答案为:8*(1+8)/2+1=37。故选B。
但有的教科书上认为“空串是任意串的子串”无意义，所以认为选C。
https://www.cnblogs.com/anliux/p/10522135.html
https://ac.nowcoder.com/discuss/424436

D (n^2/2)+(n/2)-1= (1+n)*n/2-1 选择题还可以代入法
B D
无
任意个连续的字符组成的子序列
子串T在主串S的第pos个字符之后第一次出现的位置，若没出现，返回0
6 推荐看这个从直观看的话因为abccdcdccbaa黑色字体没有公共前后缀所以退化成BF算法一共匹配5次到目标位置+1匹配成功若有公共前后缀则如视频一开始那样直接跳。（本方法只适用求匹配次数，同时因为本人只遇到过一次求匹配次数所以方法可能有错误之处）这个视频讲了很多（未涉及到算法代码，~~才不是因为是小姐姐才放上去😝~~）
模式匹配、模式串
t=concat(subString(s,1,3), subString(s,7,1))
'xyxyxywwy' assign为赋值操作

第三题图，做熟练了就能看懂这图了建议先看完视频再看这里（红色部分其实没必要但Windows画图工具修改太蛋疼就放着了。前三步都是一样的根据next来找对应的字母看是否相等，不相等直接于next等值，相等则找到next对应的下标的next值）

第五章数组和广义表

Draw a picture is important to understand-----by Lu Xun🍻

数组常用两种操作是：查找和修改。

矩阵压缩存储为了减少存储空间。

稀疏矩阵(定义: 非零元很少且分布不规律)一般用三元组和十字链表存储。

数组元素的地址计算公式（题中有详解）

(1) 按行优先顺序存储的二维数组Amn地址计算公式
LOC(aij)=LOC(a11)+[(i-1)×n+j-1]×d

(2) 按列优先顺序存储的二维数组Amn地址计算公式
LOC(aij)=LOC(a11)+[(j-1)×m+i-1]×d

其中：
LOC(a11)是开始结点的存放地址（即基地址）
d为每个元素所占的存储单元数由地址计算公式可得，数组中任一元素可通过地址公式在相同时间内存取。即顺序存储的数组是随机存取结构。

咱也看不懂，咱也不敢说啥。

无广义表内容

题：

1. 数组A[0..5，0..6]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是（）。

A.1175 B.1180 C.1205 D.1210

2. 若6行5列的数组以列序为主序顺序存储，基地址为1000，每个元素占2个存储单元，则第3行第4列的元素（假定无第0行第0列)的地址是（）。

A.1040 B.1042 C.1026 D.备选答案A，B，C都不对

3. 设二维数组A[1..m，1..n](即m行n列)按行存储在数组B[1.m*n]中，则二维数组元素A[i,j]在一维数组B中的下标为( )。

A.(i-1)*n+j B.(i-1)*n+j-1 C.i*(j-1) D.j*m+i-1

4. 二维数组A[10..20][5..10]采用行序为主序存储,每个元素占4个存储单元,并且A[10][5]的存储地址是1000,则A[18][9]的地址是多少?

5. 对于数组A n*n 其元素a ij 按行优先与按列优先存储时地址之差为？

6. 设有一个n行n列的对称矩阵A,将其下三角部分按行存放在一个一维数组B中,A[0][0]存放于B[0]中,那么第i行的对角元素A[i][i]存放于B中()处

A.(i+3)*i/2 B.(i+1)*i/2 C. (2n-i+1)*i/2 D.(2n-i-1)*i/2

7. 设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为( )

A．i(i-1)/2+j B．j(j-1)/2+i C．j(j-1)/2+i-1 D．i(i-1)/2+j-1

8. 上三角矩阵压缩的下标对应关系为___。

9. 将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1..298]中，A中元素A6665(即该元素下标i=66，j=65)，在B数组中的位置K为()。
A.198 B.195 C.197 D.196

10. 三维数组a[4][5][6](下标从0开始计，a有4*5*6个元素)，每个元素的长度是2，则a[2][3][4]的地址是？

11. 有一个10阶对称矩阵A，采用压缩存储方式（以行序为主存储，且A[0][0]=1)，则A[8][5]的地址是______。

12. 用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j] (1≤i≤n,i-2≤j≤i+2),B中的第8个元素是A 中的第___行，第___列的元素。

13. 数组A[0..4, -1..-3, 5..7]中含有元素的个数?

14. n阶对称矩阵采用压缩存储,需存储的数据元素个数是?

15. 有一个100*90的稀疏矩阵,非零元素有10个,设元素为整型,每个整型数占2字节,则用三元组存储该矩阵时,所需的字节数是多少?

16. 二维数组A的元素都是6个字符组成的串,行下标i的范围从0到8,列下标j的范围从1到10.从供选择的答案中选出应填入下列关于数组存储叙述中（）内的正确答案.

(1) 存放A至少需要( )个字节;
(2) A的第8列和第5行共占( )个字节;
(3) 若A按行存放，元素A[8，5]的起始地址与A按列存放时的元素( )的起始地址一致。

(1) A.90 B.180 C.240 D.270 E.540
(2) A.108 B.114 C.54 D.60 E.150
(3) A. A[8,5] B. A[3,10] C. A[5,8] D. A[0,9]

17. 设数组A[0..8,1..10],数组中任一元素A[i,j]均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么
（1）存放该数组至少需要的单元数是_______;
（2）存放数组的第8列的所有元素至少需要的单元数是_______;
（3）数组按列存储时，元素A[5,8]的起始地址是_______。

18. 稀疏矩阵的三元组存储方法（)。
A. 实现转置运算很简单，只需将每个三元组的行标和列标交换
B. 是一种链式存储方法
C. 矩阵的非零元个数和位置在操作过程中变化不大时较有效
D. 比十字链表法更高效

19. 在稀疏矩阵的快速转置算法中,num[col]表示源矩阵M中( )。

A.第col行中非零元的个数 B.第col行中零元的个数
C.第col列中非零元的个数 D.第col列中零元的个数

20. 用数组r存储静态链表,结点的next域指向后继,工作指针j指向链中结点,使j沿链移动的操作为()

A.j = r[j].next B.j = j+1 C.j = j->next D.j = r[j]->next

解：

（这下标我没学好下面可能有误但不想重新修改了 建议画图理解然后推公式。数组从0开始存但里面有1个元素了，这就是下标之间的关系；如果从1开始则一一对应）

（造孽啊不应该整理题目顺序的我的时间没了😭，可能会对你的学习有帮助吧。数组真是磨人的小妖精👿，因为重新整理了题目，可能答案会错，抱歉了，可以私信or留言）

如表格所示。按列存储，则先存储满前5(下标：'0' - '4')列，5*6；然后存储5('0' - '5')个格子；30+5=35个单元。1000+35*5=1175（表格法更形象虽然慢了一点，公式法抽象但快速。ps可以用表格法推公式，即按列存储必须先存满A[5,5]的前 '4' 列（下标从0开始），再存到该列的的前一个位置。（注意该列的当前位置，需要-1，不信你可以试试A[1,0]的地址，它在该列的第2个，but 地址：1000+5而不是1000+10。）最后就是公式了：A[i, j]所在位置=(j-1)*行数+i-1，（注意此处i，j是实际行，列数即你数一下它在第几行第几列，[5,5]就是第六行第六列）用表格理解更清晰，自己再试着推一下并辅之题目。

0，0 0，1 0，2 0，3 0，4 0，5 0，6

1，0

2，0

3，0

4，0

5，0 here
你敢选D？？？答案A。1000 + (3*6+2)*2 = 自己算懒死你
B 题目问的是下标不是地址此外注意矩阵下标
（存满前18-10=8行*(10-5+1)数组列数+存满到第9-5=4列）+1000=52*4 +1000= 1208。（熟悉后可以直接用公式解了行优先：(i-1)*列数+j-1 主要注意行存储*列数，列存储*行数然后换掉相应的即可）
(i-j) × (n-1)。根据最上面的公式（注意矩阵n*n）：(j-1)×m+i-1，(i-1)×n+j-1，则[ j×n+i ] - [ i×n+j ] = (i-j) × (n-1)
A (链接中还有上三角。选择题特殊值法不多说了吧) A[i][i]是第i+1行第i+1列元素,是第1+2+...+(i+1)=[(i+1)*(i+2)/2]个元素，又因为起始坐标是0。所以存放在[(i+1)*(i+2)/2]-1=[ (i+3)*i/2 ]处

个数

(1,1) 1

(2,1) (2,2) 2

(3,1) (3,2) (3,3) 3

(4,1)
(4,2) (4,3) (4,4) 4
B 具体看里面的特殊值法和类推法
上三角矩阵中，主对角线上第r (1≤r≤n)行有n-r+1个元素，aij所在行的元素数是j-i+1。所以，按行序存储的元素在一维数组的下标k和二维数组下标的关系:k=((i-1)*(2n-i+2)/2+(j-i+1)=(i-1)(2n-i)/2+j (i≤j)
三对角矩阵，第一行元素是两个，其他行是三个，资料见三元组因此答案是 2+64*3+1=195.画图就能理解了

（1）主对角线即i=j；
（2）主对角线之下的对角线（称低对角线）即i=j+1；
（3）主对角线之上的对角线（称高对角线）即i=j-1。因此最后+1
就是一个长5宽6高4的长方体。最底下第0层,前第2层都放满,那就是2×5×6个元素；这时,剩[3][4]的元素个数没有计算,那就是放满了三行(/排)（0、1、2）,共3×6个元素；这时剩5个元素,把这三个数加起来,Loc=1000+(60+18+5-1)×2=1164。(原本想画图给你们的越画越乱，心态爆炸你们自己加油吧。就相当于底下两层已经满了，在第三层放了三排，第四排放了5个，大概是这样子。心态爆炸ing。)
题目要求A[8][5]，所以采用下三角存储，因为是行序，所以1+2+...+8+5 = 41 （+5而不是+6就不多赘述了，地址要-1 下标则取6）或直接带公式 (k=i(i-1)/2+j) (1≤i,j≤n) 9×8÷2+5=41 （下标是0）
第一行第三列。五对角矩阵。(注意下标1≤i≤n,i-2≤j≤i+2 三对角i-1≤j≤i+1 注意区分)此外列存储所以第八个是a13.

a11 a12 a13

a21 a22 a23 a24

a31 a32 a33 a34 a35

a42 a43 a44 a45 a46

a53 a54 a55 ......
纯粹下标转化 (4-0+1)*(3-1+1)*(7-5+1)=45
只要存对角线（含）以上的部分就行了，所以是1+2+...+n=n(n+1)/2，如第8的上三角
每个元素要用行号、列号、元素值来表示,在用三元组表示稀疏矩阵,还要三个成员来记住,矩阵的行数、列数、总的元素数,所以所需的字节数是10*（1+1+1）*2+3*2=66
(8-0+1)*(10-1+1)*6 = 540 (下标没学好一直弄不懂为什么+1) 、9+10-1=18*6=108、画表格理解按行存放时A[8,5]是第8*10+4个元素=84（行存公式：自己推，优先存满前几行的数据再加上当前行的前几列减1，注意下标不要眼瞎）所以列存为9*9+3=84
90×(48/16)=270、9×3=27、2000+(7×9+5)×3=2204 虽然答案错的但是过程值得借鉴
C
C 稀疏矩阵的快速转置原理及其算法
A

第六章树和二叉树

树的基础概念

n个结点的正则二叉树(只有度为0和2)的叶子结点为(n+1)/2
有n个结点，并且高度为n的二叉树的数目为
有n (n>0)个结点的二叉树的深度的最小值（=完全二叉树）是 =
有n (n>0)个分支结点的满二叉树的深度是
一棵树高为k的完全二叉树至少有个结点（-1+1）
一棵树高为k的完全二叉树至多有 $2^{k}-1$ 个结点，即满二叉树
有n (n>0)个结点的满二叉树的高度为 ${log_{2}}^{n+1}$
深度为h的满m叉树的第k层有个结点
深度为h的满3叉树的结点数为

树的存储形式：双亲表示法、孩子链表表示法、孩子兄弟表示法、~~顺序存储表示法×~~。附解释（好文）

树和森林的遍历与二叉树遍历的关系：

树	森林	二叉树
先根遍历	先序遍历	先序遍历
后根遍历	中序遍历	中序遍历

树和森林的表示方法+树和森林的遍历

线索二叉树为了能方便地找到双亲。是物理存储结构。n个结点的线索二叉树上含有的线索数为n+1（第36题的解析二有用到这个）。

$\frac{1}{n+1}\times \frac{(2n)!}{(n!)^{2}}$ ：求二叉树能够构造多少不同的二叉树公式。（底下也可以写成n!*(n+1)!）

一个很好的根据中序、后序遍历的方法，也适用于前序中序

（待更新：上取整和下取整即求树的高度的等同形式、ps其实求结点根据2^k-1即可）

题：

题目分类：

~~①求二叉树结点个数：1.、②求叶子结点：4、18③ ：④ ：（后续填坑记录）~~

1. 已知一棵完全二叉树的第 6 层（设根为第 1 层）有 8 个叶结点，则完全二叉树的结点个数最多是 ( )。

2.将森林转换为对应的二叉树，若在二叉树中，结点 u 是结点 v 的父结点的父结点，则在原来的森林中，u 和 v 可能具有的关系是（）

I．父子关系 II.兄弟关系 III. u 的父结点与 v 的父结点是兄弟关系

A．只有Ⅱ B．Ⅰ和Ⅱ C．Ⅰ和Ⅲ D．Ⅰ、Ⅱ和Ⅲ

3. 在一棵度为4的树T中，若有20个度为4的节点，10个度为3的节点，1个度为2的节点，10个度为1的节点，则树T的叶节点个数？同（16.）

4. 若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是()。建议和第18题一起联系

5. 若一棵二叉树的前序遍历序列和后序遍历序列分别为1，2，3，4和4，3，2，1。则该二叉树的中序遍历序列不会是（）

A.1234 B.2341 C.3241 D.4321

6. 已知一棵有2011个结点的树,其叶结点个数为116，该树对应的二叉树无右孩子的结点个数为（）。

7. 若一棵二叉树的前序遍历序列为a, e, b, d, c，后序遍历序列为b, c, d, e, a，则根结点的孩子结点（）

A.e B.有e、b C.有e、c D.无法确定

8. 已知三叉树T 中 6 个叶结点的权分别是 2，3，4，5，6，7， T 的带权（外部）路径长度最小是（）

A.27 B.46 C.54 D.56

9. 先序序列为a, b,c,d的不同二叉树的个数是（）。

A.13 B.14 C.15 D.16

10. 若X是后序线索二叉树中的叶结点，且X存在左兄弟结点Y，则X的右线索指向的是

A．X的父结点 B．以Y为根的子树的最左下结点

C．X的左兄弟结点Y D．以Y为根的子树的最右下结点

11. 将森林F转换为对应的二叉树T，F中叶结点的个数等于（）

A.T中叶结点的个数 B.T中度为1的结点个数

C.T中左孩子指针为空的结点个数 D.T中右孩子指针为空的结点个数

12. 下列选项给出的从根分别到两个叶子结点路径上的权值序列，能属于同一棵哈夫曼树的是：

A.24, 10, 5 和24, 10, 7 B. 24, 10, 5和24, 12, 7
C. 24, 10, 10和24, 14, 11 D. 24, 10, 5和24, 14, 6

13. 二叉树就是度为2的树 T/F

14. 正确的有：
①只有一个结点的二叉树的度为0;
②二叉树的度为2;
③二叉树的左右子树可任意交换;
④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。

15. 算术表达式a+b*(c+d/e)转为后缀表达式后为()。

16. 设有一个度为3的树，其叶结点数为n0，度为1的结点数为n1，度为2的结点数为n2，度为3的结点数为n3，则n0 与n1,n2,n3满足关系（）。
A.n0=n2+1 B.n0=n2+2*n3+1
C.n0=n2+n3+1 D.n0=n1+n2+n3

17. 正确的是：
A.完全二叉树中，叶结点的双亲的左兄弟（如果存在)一定不是叶结点
B.任何一棵二叉树，终端结点数为度为2的结点数减1
C.二叉树不适合用顺序结构存储
D.结点按层序编号的二叉树，第i个结点的左孩子（如果存在)的编号为2i

18. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）
A. 250 B.500 C.254 D.505
E.以上答案都不对

19. 具有300个结点的二叉树,其高度至少应为( )。

一个具有1025个结点的二叉树的高h为()。

20. 当结点数目一定时,具有最小深度的二叉树是( )。

A.满二叉树 B.完全二叉树 C.线索二叉树 D.二叉排序树

21. 从树根(第0层)起，自上到下，逐层从左到右给二叉树的所有结点从1开始编号，则完全二叉树的第h层的从左到右第k个结点的编号为()。

A.2^h+k-1 B.2^h-k+1 C.2^h +k+1 D.2^h -k-1

22. 下列判断中，()是正确的。
A.深度为k的二叉树最多有2^k-1个结点(k≥1)，最少有k个结点
B.二叉树中不存在度大于2的结点
C.对二叉树遍历是指先序、中序或后序遍历中的一种
D.构造线索二叉树是为能方便找到每个结点的双亲

23. 若某完全二叉树的结点个数为100，则第60个结点的度为

A.0 B.1 C.2 D.不确定

24. 若用一维数组表示一个深度为5、结点个数为10的二叉树，数组的长度至少为

A.10 B.16 C.31 D.64

25. 任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（）。

A.不发生改变 B.发生改变 C.不能确定 D.以上都不对

26. 父结点大于孩子结点编号、左孩子的编号小于其右孩子的编号，可采用（）次序、交换其所有分支结点左、右子树的位置可采用（）次序

27. 先序、中序、后序、层序遍历中只要加上其中哪一种就可以唯一地确定一棵二叉树。

28. 一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A[1..n]中，则二叉树中第i个结点(i从1开始用上述方法编号）的右孩子在数组A中的位置是

A.A[2i](2i≤n) B.A[2i+1](2i+1≤n) C.A[i-2] D.条件不充分，无法确定

29. 一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是

A.CABDEFG B.ABCDEFG C. DACEFBG D.ADCFEG

30. （有问题）设m、n为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是:

A.n在m右方 B.n是m祖先 C.n在m左方 D.n是m子孙

31. 二叉树的先序和中序遍历序列分别是ABCDEFGH,CBEDFAGH,则后序遍历序列是()

A.HGFEDACB B.GHEDFCBA
C.CEFDBHGA D. HGAFDEBC

某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E，则前序序列是()

A.E,G,F,A,C, D, B B.E,A,C,B,D,G, F
C.E,A,G,C,F,B,D D.上面的都不对

32. 某二叉树结点的中序序列为BDAECF，后序序列为DBEFCA，则该二叉树对应的森林包括（）棵树。

A.1 B.2 C.3 D.4

高度为h(h>0)的满二叉树对应的森林由( )棵树构成

A.1 B.log2h C.h/2 D.h

33. 前序遍历和后序遍历结果相同的二叉树为((1))
前序遍历和中序遍历结果相同的二叉树为((2))
中序遍历和后序遍历结果相同的二叉树为((3))

A.一般二叉树
B.空树或根结点无左孩子的二叉树
C.空树或只有根结点的二叉树
D.空树或根结点无右孩子的二叉树
E.空树或缺左子树的单支二叉树
F.空树或缺右子树的单支二叉树

34. 一棵非空的二叉树的前序序列和后序序列正好相反,则该二叉树一定满足()
A.其中任意一个结点均无左孩子 B.其中任意一个结点均无右孩子
C.其中只有一个叶结点 D.其中度为2的结点最多为一个

35. 某二叉树的前序序列和中序序列正好相反，则该二叉树一定具有（）的特征
A.二叉树为空或只有一个结点
B.若二叉树不为空，则任一结点不能同时拥有左孩子和右孩子
C.若二叉树不为空，则任一结点没有左孩子
D.若二叉树不为空，则任一结点没有右孩子

36. 一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是（），若左右子树都不为空，则（）（填空题也考过）

A.不确定 B.0 C.1 D.2

37. 若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（）

A.X的双亲 B.X的右子树中最左的结点
C.X的左子树中最右结点 D.X的左子树中最右叶结点

38. ()的遍历仍需要栈的支持

A.前序线索树 B.中序线索树 C.后序线索树

39. 二叉树在线索化后,仍不能有效求解的问题是()

A.前序线索二叉树中求前序后继 B.中序线索二叉树中求中序后继

C.中序线索二叉树中求中序前驱 D.后序线索二叉树中求后序后继

每个结点通过线索都可以直接找到它的前驱和后继（T/F）

40. 树用孩子兄弟表示法，每个结点有两个指针域，分别指向“第一个孩子”和“下一个兄弟”。若指向“下一个兄弟”的指针有n个为空，则该树有（）个非终端结点。

A.[n/2] B.n-1 C.n D.n+1

41. 设森林F对应的二叉树为B,它有m个结点,B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是()

A.m-n B.m-n-1 C.n+1 D.条件不足,无法确定

42. 设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有多少个

A. n-1 B.n C.n+1 D.n+2

43. 如果T1是由有序树T转换而来的二叉树，那么T中结点的先序序列就是T1中结点的（）序列

A.先序 B.中序 C.后序 D.层次序

44. 由3个结点可以构造出多少种不同的有向树?()

A.2 B.3 C.4 D.5

45. 由3个结点可以构造出多少种不同的二叉树?

46. 一棵共有n个结点的树,其中所有分支结点的度均为k，则该树中叶子结点的个数为()

A.n(k-1)/k B.n/k C.(n+1)/k D.(nk-n+1)/k

47. 下述二叉树中，哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序()。
A.二叉排序树 B.哈夫曼树 C.AVL树 D.堆
48. 在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树，该说法 T/F

49. 一棵 Huffman树共有215个结点，对其进行Huffman编码，共能得到( )个不同的码

A. 107 B.108 C.214 D.215

50. 设哈夫曼编码的长度不超过4，若已对两个字符编码为1和01，则还可以对( )字符编码。

A.2 B.3 C.4 D.5

51. 若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为
A. $n-1$ B. $\left \lfloor n/m \right \rfloor -1$
C. $\left \lceil (n-1)/(m-1) \right \rceil$ D. $\left \lceil n/(m-1) \right \rceil -1$
E. $\left \lceil (n+1)/(m+1) \right \rceil -1$

52.有5个字符，根据其使用频率设计对应的哈夫曼编码，以下( )是可能的哈夫曼编码。
A.000, 001,010,011,1 B.0000,0001, 001, 01, 1
C.000,001,01,10,11 D.00,100,101,110,111

53. 一棵完全二叉树又是一棵（）

A.平衡二叉树 B.堆 C.二叉排序树 D.哈夫曼树

54. 在下列情况中，可称为二叉树的是（）

A.每个结点至多有两棵子树的树 B.哈夫曼树

C.每个结点至多有两棵子树的有序树 D.每个结点只有一棵右子树

E.以上答案都不对

55. 若把堆看成是一棵完全二叉树,则该树一定是一棵二叉排序树() T/F

56. 某二叉树T有n个结点,设按某种顺序对T中的每个结点进行编号,编号为1,2,…,n,且有如下性质:T中任一结点V,其编号等于左子树上的最小编号减1,而V的右子树的结点中,其最小编号等于V左子树上结点的最大编号加1。这时是按( )编号的
A.中序遍历序列 B.前序遍历序列
C.后序遍历序列 D.层次遍历序列

解：

~~还是树的相关资料多，终于不用手动了😄~~

解析注意并不是最后一层有叶子结点即可，别跟满二叉树想混了。（知识补充：完全二叉树必须跟满二叉树是一一对应的关系，不能隔个结点加结点）
如图，另附详解
总度数=总结点数+1：(20×4+10×3+1×2+10×1) - (20+10+1+10+1) = 81 详解
384。因为n=n0+n1+n2，n2=n0-1，所以n=2n0+n1-1。在完全二叉树中，n1取1或0。这里n=768,n只能为1（n为0则n0为奇数），故选C。在完全二叉树结点计算中，仅知一个量（总结点数，叶子数，度为2的结点数）求其他量，一般就利用该公式。另附详解
C。前序遍历序列和后序遍历序列相反的二叉树是高度等于结点数的二叉树，或说只有一个叶子结点的二叉树，或说每个分支结点至多只有左子女或只有右子女的二叉树。中序遍历的第一个结点是二叉树最左面的结点。A是分支结点只有右子树的二叉树，D是分支结点只有左子树的二叉树，B是以1为根，2是1的左子女，3是2的右子女，4是3的右子女。另附详解，图源牛客网。
1896. 树与二叉树的对应关系（时间紧张，没有细究如有错误，原文留言）另附详解（有点忘记树和二叉树的转换了，左孩右兄）
前序遍历第一个肯定是e，其次根据先序遍历若e在右边则必定只有一个结点，所以判断e在右边，根据BC进行排除，B的b在a的右边显然错误，画一下图就知道了。C
B 另附详解。模拟霍夫曼最优二叉树的编码方法，考虑到最后一步编码应当是三个元素一起编码，因此编码开始之前在最底层添加一个权为"0"的节点，从下至上以三元组编码，最后可得该最优三叉树，注意：节点偶数要加个0，奇数个就不用直接按照二叉树哈夫曼的那种方法。解析源于博文第十五题。（哈夫曼树构造的前缀编码必不会出现前缀相同，如10，100 ❌）
Catalan数+其可解决的问题、解析1、解析2
写出后序遍历即可，根据Y父X 可得遍历为YX父因为X的右边是父即右线索是父结点。这种求左右线索，根据遍历序列的前后关系即可得出。
C 左孩子右兄弟，左边为空则无孩子即叶子结点。另附详解
D。这个考察哈夫曼树挺深的另附详解
F （牛客网挺好的，如果找不到题目可以去牛客网找找解析）
1、4
{a+[b*(c+(d/e))]} 扩起括号则后序就右移运算符到第一个括号后，前序就左移运算符即可。1.{a[b(c(de)/)+]*}+ 2.abcde/+*+
n1 + 2n2 + 3n3 + 1 = n0 + n1 + n2 + n3 => B （树(泛指所有树)的总结点数+1=树的总结点数）
A 。A完全二叉树叶子结点的双亲是最后一个分支结点时，其双亲的右兄弟（如果存在）肯定是叶子，其左兄弟肯定是分支结点，不可能是叶子。B任何二叉树，终端（叶子）结点数为度为2的结点数加1。公式：n0 = n2+1 C用顺序存储结构可以存储二叉树，特别是完全二叉树;D只有完全二叉树顺序存储时双亲结点和子女结点的存储位置（下标)间才存在确定关系。
E（~~蒙题的人，没想到吧~~），也可以用第4题的套路
具有n个结点的完全二叉树的深度为二叉树为至少的情况，至多就是串串。此外还可以用求二叉树的结点数来算2^k-1 求k即可比如2^8-1=255 < 300 所以k=9。11至1025之间 注意题目问的是高为不是至少至多。
设结点数目是n。n个结点未必是满二叉树，A错。C和D明显错误（~~然鹅我选了D😂~~）。
特殊值法取第一层第二个即可。然后记住答案在填空题里小心
AB
根据完全二叉树的性质可知前k层必为满二叉树，所以第60个在32-64之间即第6层即叶子层，所以0。另附详解。
用一维数组存储二叉树要按完全二叉树的格式存储，一般二叉树要加“虚结点”，使之成为完全二叉树的形状。深度为5的完全二叉树至多有2^5-1=31个结点，所以数组长度要31，和题中给的结点个数为10关系不大，只要结点个数在5至31之间，分配的数组长度都一样。
A
后序、中序
中序遍历可以搭配其他三种，唯一确定一棵二叉树。
别问问就踩坑。D
判断原则:前序序列第一个元素是根，在中序序列中根结点把序列分成左右子树，再看前序第二个元素，到中序的左右子树中找。答案A根左面是C，答案C根左面是D，答案D根左面为空，都不是前序序列的第二个元素B。只有答案B正确。另附详解1、详解2。（此外mark根据二叉树遍历确定一个树，我记得有个通俗易懂的带我考完再细说）
C 题目有漏洞，反例。
这两题都可以快速解出来，首先第一题前序第一个是根节点A则中序划分成{CBEDF}A{GH},后序遍历左子树倒数第二输出A最后输出，所以凡是GH不靠近A的全是错的，且A为序列最后一个所以C。第二题由后序可知E为根结点，所以{A,B,C,D},E,{F,G},由FG为左子树可知，前序序列GH必须在最后面且贴近（左子树就这两个），所以B。第二题所确定的二叉树
C。二叉树根结点和根结点的右子女，右子女的右子女，等等，是二叉树转成森林后树的根。因此，只要找到根结点A，根结点的右子女C，右子女的右子女F，就可以判定3棵树，不必画出整棵二叉树。（左孩右兄，找二叉树的右斜子树（就前面文字那个意思））D同类型的题。
CEF。（1）、（2）：因为前序遍历：|T|L|R|，中序遍历：|L|T|R|，如果要相同，首先没有左子树，答案只能从CE选，而构造一个缺左子树的二叉树，可得出前中序相同，即可排除C。（3）：中序和后序正好反着来，所以选F。这道题必须对前中后序有比较深刻的理解，且脑子里几何要好，能构造二叉树。前序遍历是"根(T)-左(L)-右(R)”，中序遍历是“左-根-右”，后序遍历是“左-右-根”。(图就不用画了把，单支树也好想。)
C
前序遍历和后序遍历相同，只有二叉树是一条链的情况下，一条链时，二叉树有下列特点：(源自牛客网：kktb)
1）任一结点无左孩子或者任一结点无右孩子
2）结点的个数等于树的高度
该类题型笔记整理:
1.前序序列和后序序列正好相反，高度等于其结点数或二叉树只有一个叶子结点。
2.前序序列和中序序列正好相反，任一结点无右孩子。
3.前序序列和中序序列正好相同，所有节点只有右子树。
4.中序序列和后序序列正好相反，任一结点无左孩子。
5.中序序列和后序序列正好相同，所有节点只有左子树。
该题解释：没啥好解释的画一下树排除一下就好了❤
D、C。二叉树线索化1、二叉树线索化2。第一个D另外一种解法
C
C
D。先序线索二叉树求先序前驱也不能有效求解。F ，后序的根节点的两个指针域都指向左右孩子，所以不能通过线索查找。
B.我的理解是n个为空说明有n个指向孩子的结点，类似于一串，所以只有最后一个是叶子结点。
A .左孩右兄（解树跟二叉树结点关系的关键，比如森林中三棵树，分别M1、M2、M3个结点，则二叉树右子树几个结点：M2+M3）。右子树为森林中的其他树
C。牛客解释。另外从评论中得知一个特例，一个根节点的时候可知右指针域为1所以0+1=1
B。原文中有有序树定义，这里就不另放了。
A. 从原文中整理出来：
满足下列条件的有向图被称为有向树。
（1）有且仅有一个结点的入度为0；
（2）除树根外的结点入度为1；
（3）从树根到任一节点有一条有向通路。
（1）、（2）这也是为什么最后一个树不为有向树。被那个图片中略去有向边还是一颗树误导了，虽然最后一个略去有向边是一颗树，但是根节点入度为2所以是错的。
$\frac{1}{n+1}\times \frac{(2n)!}{(n!)^{2}}$ = 1/4*(6!)/(3!*3!)=5.求二叉树的构造数，套公式即可
2个结点，度为1，叶子节点为1.选D。推导过程
D。哈夫曼树，非叶节点不存储关键字信息。（路径长度最短选他）
F。~~我也不知道为啥选错了，可能是不知道最优二叉树是啥吧🙃~~
B。本题的关键在于哈夫曼树是满二叉树，只有度为2的结点和度为0的结点 。权值只有叶节点才有。 又度为0的结点比度为2的结点多1（常考）。设度为0的结点为x，则x+（x-1）=215，解得x=108.（搬运）
D。前缀编码的意思是任何一个编码不是另外一个的前缀，所以已经有0和10的情况下，其他的只能是11开头了，考虑到最多只有四位，而这个前缀已经占了2位（二进制位），剩下2位可能的编码数为2的2次方，也就是4个。
C。m=2，n=3，可得。详解。
ABC. 前缀编码的意思是任何一个编码不是另外一个的前缀。~~是不是以为单选题😂~~
B.~~突然忘了为什么把53、54放在最后面😥。~~完全二叉树的叶子至多在下面两层上，且一个结点若无左子树，绝不能有右子树。平衡二叉树任何结点的左右子树的高度差的绝对值不超过1，但其结点的值符合二叉排序树的定义。平衡二叉树（包括二叉排序树)的树形不一定是完全二叉树。堆是一个序列，有大堆和小堆，编号为i的结点，其父结点、左右子女结点之间位置的关系，符合完全二叉树父结点、左右子女结点之间的关系，从这点上说，可以把堆看成完全二叉树。哈夫曼树是二叉树，但树形不一定满足完全二叉树的定义。
B。本题考核二叉树的定义，但是编者认为题目叙述不够严格。二叉树和树都属于树形结构，但是二叉树不是树的特例。选择答案A和C明显错误。D错误在于“每个结点只有一棵右子树”，这样会有无限个结点。选择答案B接近正确，因为二叉树可以得到前缀码，哈夫曼二叉树可以得到最优的前缀码（即哈夫曼编码)。在本科数据结构的教学中，一提哈夫曼树都是指带权路径长度最小的最优二叉树。但是哈夫曼树并非都是二叉树。（~~原来是字多的原因~~，摘自解析）
F。
B.害根据结点大小来看更快一点画图慢了

填空题

1. 中缀式a+b*3+4*(c-d)对应的前缀式为____,若a=1, b=2,c=3, d=4,则后缀式db/cc*a-b*+的运算结果为____。

2. 树在计算机内的表示方式有____、____、____

3. 一棵有n个结点的二叉树，叶子结点的数量为n0，度为2的结点数量为n2，则n0与n2的关系是____﹔如果用二叉链表存储该二叉树，则空指针数量为____

4. 已知完全二叉树的第8层（根结点的层次为0)有240个结点，则整个完全二叉树的叶子结点数是____

5. 深度为H的完全二叉树至少有____个结点;至多有____个结点;H和结点总数N之间的关系是:____

6. 已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有____个叶子结点。

7. 设高为h的二叉树只有度为0和2的结点，则此类二叉树的结点至少为____;至多满二叉树。

8. 在完全二叉树中，编号为i和j的两个结点在同一层的条件是

9. 完全二叉树结点的平衡因子取值只可能为____

10. 高度为K的完全二叉树至少有____个叶子结点。

11. 已知二叉树中有50个叶子结点，则该二叉树的总结点数至少是____

12. 设根的层次为1，则有64个结点的完全二叉树的深度为____

13. 若按层次顺序将一颗有n个结点的完全二叉树的所有结点从1到n编号，那么结点i没有右兄弟的条件为____

14. 对于非空满k叉树，其分支结点数目为n，则其叶子结点数目为____

15. 设一颗完全二叉树叶子结点数为K,最后一层结点数>2,则该二叉树高度为多少?

16. 将一棵有100个结点的完全二叉树从根这一层开始,每一层上从左到右依次对结点进行编号，根结点编号为0，则编号为50的结点的右孩子编号为____

17. 若按层次顺序给二叉树各结点从1开始编号，则含n个结点的完全二叉树中叶结点的最小编号是（）。

18. n(n大于1)个结点的各棵树中，其深度最小的那棵树的深度是____。它共有____个叶子结点和____个非叶子结点，其中深度最大的那棵树的深度是____，它共有____个叶子结点和____个非叶子结点。

19. 在树的孩子兄弟表示法中，二叉链表的左指针指向____

20. 设F是由T1、T2、T3三棵树组成的森林，与F对应的二叉树为B，已知T1、T2、T3的结点数分别为n1、n2和n3，则二叉树B的左子树中有____个结点

21. 一个深度为k的，具有最少结点数的完全二叉树按层次，(同层次从左到右)用自然数依此对结点编号，则编号最小的叶子的序号是____﹔编号是i的结点所在的层次号是____（根所在的层次号规定为1层)。

22. （有问题）前序遍历树林正好等同于按____遍历对应的二叉树，后序遍历树林正好等同于按____遍历对应的二叉树。

23. 二叉树的先序序列和中序序列相同的条件是____

24. 设二叉树中每个结点均用一个字母表示，若一个结点的左子树或右子树为空，用“.”表示,现前序遍历二叉树，访问的结点的序列为ABD.G...CE.H..F.. ,则中序遍历二叉树时，访问的结点序列为____﹔后序遍历二叉树时，访问的结点序列为____。

25. 现有按中序遍历二叉树的结果为abc，问有____种不同的二叉树可以得到这一遍历结果,这些二叉树分别是____。

26. 在一棵存储结构为三叉链表的二叉树中，若有一个结点是它的双亲的左子女，且它的双亲有右子女，则这个结点在后序遍历中的后继结点是____

27. 设一棵后序线索树的高是50，结点x是树中的一个结点，其双亲是结点y, y的右子树高度是31, x是y的左孩子。则确定x的后继最多需经过____中间结点(不含后继及x本身)。

28. 若以{4, 5, 6, 7, 8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是____

29. 设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有____个结点。

30.

31.

填空题解

~~mark（计算公式的推导过程）~~

中缀转前缀移步选择题15，or 链接中的表达式转换-人工法。++a*b3*4-cd。18. 栈法、画二叉树法。另外给前缀计算的话，只用跟后缀相反即可，比如前面的空。cd放入，遇到-弹出计算c-d，放入栈中。。。即可（还未实验其他题目，可以试试）
(1)双亲链表表示法、(2)孩子链表表示法、(3)孩子兄弟表示法
n0=n2+1、n+1. 第二空：空链域：2n0+n1；n0=n2+1；则n0 + n2 +1 +n1 = n+1 ，其他方法
由第八层2^8>240可知240个为叶子层的结点数，又240/2=120个上层父亲结点且度为2，所以上层上下128-120=8个叶子，即248个叶子.不要记混了（2^(k-1)是k层结点数，2^k-1是总共至多结点数）。也可以用公式法：首先总的结点数为128+240=368；n=2n0-1+n1 且（n1为1，否则总结点数为奇数），所以368/2=128.参见选择题4
不会的往上翻，树的开头底下。
跟选择题16重复，纯粹忘了+1😓，12
2h-1，除了第一层为1，每一层都是2
log₂i下取整与log₂j下取整相等，代码就是不断/2看是否同一祖先
-1，0，1
$2^{K-2}$ .设根节点为1，则第K-1层共 $2^{K-2}-1$ 个结点，则再加上一个第K层的结点即为最少叶子节点。
99. n2=n0-1 ；最少即没有度为1的结点，50+49=99。另附错误想法。看到叶子结点个数或度为2的个数应立马想到他们之间的关系。
这道题的结点数有点巧妙，正好是2的6次方，如果对公式不熟悉，就6了。答案7
2*i+1>n。但我感觉这个n%2==0也可以
n(k-1)+1。
$\left \lceil {log_{2}}^{k} \right \rceil+1$ 。完全二叉树高度推导。~~对这个上取整下取整搞不拎清，留坑or等大佬~~
102。假定编号为i的结点的左右孩子存在，左孩子的编号是2*i+1，右孩子的编号是2*i+2。从0开始编号
.找最后一个的父结点。+1就变成叶子结点了。具体画图理会一下。~~没做过还真想不出来~~
2、n-1、1、n、1、n-1。深度最小是n叉树，一个根节点，n-1个叶子；深度最大是单支树
结点的第一个孩子。
n1-1.减去根节点
、。第一个空：(第k层1个结点,总结点个数是2^k-1，其双亲是2^k-1/2=2^(k-2)). 也可以这样分析:深度为k且具有最少结点数的完全二叉树，第k层只有一个结点，第k-1层是满的，最左边的结点度为1，其右兄弟就是编号最小的叶子结点。而第k-2层最右边结点的编号是2^(k-2)-1。所以，最小叶子结点的编号是(2^(k-2)-1)+2=。
先序、中序。这里第二问有问题。树林不就是森林吗。森林的先序遍历和中序遍历与二叉树的先序遍历和中序遍历的序列相同。我感觉题目应该是问树而不是树林。另外关于树的给结点求遍历序列就不放了，知道对应关系比较简单。树、森林、二叉树前序遍历一致，后序遍历中除了树是中序遍历，其他一致。
选择题34、35、36可以记忆一下，可能会出现在填空题。answer：任何结点至多只有右子女的二叉树
这题还比较新颖，掌握遍历也还好。 .D.G.B.A.E.H.C.F. 、 ...GD.B...HE..FCA （不要漏了' . '）
5种。
双亲的右子树中最左下的叶子结点. 这题知道下面的就知道了
31 想错了我还以为还经过y，实际上是左右根所以31.(x的后继是经x的双亲y的右子树中最左下的叶结点)
带权路径长度是算结点到树根之间的路径长度与该结点上权的乘积。WPL=(4+5)*3 + (8+7+6)*2 = 69. ~~一开始想成（1*2+2*4+3*2）= 16😂~~
2n0-1;哈夫曼树只有度为2和度为0；n=n0+n2(n0-1)=2n0-1，另外本题应该默认为二叉树（原文中涉及到的题目为本文选择题51）。另外说明一下哈夫曼没有左小右大的规则，编码时默认左边为0 右边为1