哈希游戏作为一种新兴的区块链应用，它巧妙地结合了加密技术与娱乐，为玩家提供了全新的体验。万达哈希平台凭借其独特的彩票玩法和创新的哈希算法，公平公正-方便快捷!万达哈希,哈希游戏平台,哈希娱乐,哈希游戏顺序表、哈希表和单链表是三种不同的数据结构，既描述逻辑结构，又描述存储结构和数据运算。而

　　数据的存储结构有顺序存储、链式存储、索引存储和散列存储。A选项循环队列是用顺序表实现的队列，是一种数据结构。D选项栈是一种抽象数据类型，可采用顺序存储或链式存储，只表示逻辑结构。数据的逻辑结构独立于其存储结构。

　　5.程序段如下：(王道书上这题的代码有误，不能实现冒泡排序，我进行了修正)

　　该程序段实现的是冒泡排序。冒泡排序是一种稳定的排序方法，其平均时间复杂度为O(n^2)，最坏情况下的时间复杂度也为O(n^2)。

　　7.[2011真题] 设n是描述问题规模的非负整数，下面的程序片段的时间复杂度是(A)。

　　8.[2012真题] 求整数n(n ≥ 0) 的阶乘的算法如下，其时间复杂度是(B)。

　　这是一个简单的递归函数，整个程序的基础操作只有递归处的乘法运算，n次嵌套递归会进行n次压栈，每次递归都执行一次乘法，所以共执行n次乘法。∴T(n) = O(n)。

　　9.[2013真题] 已知两个长度分别为m和n的升序链表，若将它们合并为长度为 m + n 的一个降序链表，则最坏情况下的时间复杂度是(D)。

　　类似于“归并排序”的思想，每次从两个升序链表中取出两个元素进行比较（已经选出去的元素不会再进行比较），∵要建立一个降序链表，∴每次将两个元素之中更小的那个元素利用头插法插入到新的降序链表中；若其中一个链表已经没有元素可以比较（全比完了），则直接将另一个链表剩余的元素依次头插到新链表中即可。在最坏情况下，比如两个链表的元素大小交替出现时（eg : A链表——1，3，5；B链表——2，4，6），比较的次数会达到m + n - 1次。而由题设条件可知有不等式2max(m,n) m+n-1，因此T(n) = O(max{m,n})。

　　此题比较特殊，外层for循环和内层for循环没有关系（循环变量没有关联），所以可以分别单独计算内外层的时间复杂度，相乘即是最终结果。先算内层，设count++;执行了t次，由内层for的循环判断条件语句可知，t = n；再算外层，同样，由外层for循环的判断条件语句可知，t = log[2]n，所以总的时间复杂度为O(nlog[2]n)。

　　12.[2019真题] 设n是描述问题规模的非负整数，下列程序段的时间复杂度是(B)。

　　A.随机存取的存储结构 B.顺序存取的存储结构C.索引存取的存储结构 D.散列存取的存储结构

　　Note :此题“存取方式”指的是读写方式。顺序表是一种支持随机存取的存储结构，只要根据

　　随机存取，而不需要进行链表的遍历，且在顺序表最后进行增删操作时，不需要移动任何元素，因此时间开销小。

　　Note :注意题干中说的是“删除”操作，所以要移动n-i个元素。Δ注意：线性表中元素的位序是从

　　Ⅰ.输出第i (1 ≤ i ≤ n) 个元素值Ⅱ.交换第3个元素和第4个元素的值Ⅲ.顺序输出这n个元素的值

　　Note :对于Ⅰ和Ⅱ，由于顺序表具有“随机存取”的特性，因此在顺序表上实现“改查”效率更高。对于Ⅲ，要求遍历整个线性表，因此顺序表上和链表上时间复杂度相同。

　　Ⅰ.顺序存储方式只能用于存储线性结构Ⅱ.取线性表的第i个元素的时间与i的大小有关Ⅲ.静态链表需要分配较大的连续空间，插入和删除不需要移动元素

　　Ⅳ.在一个长度为n的有序单链表中插入一个新结点并仍保持有序的时间复杂度为O(n)

　　Note :对于Ⅰ，顺序存储方式同样可以存储树和图（比如一棵只有树干的树）；对于Ⅱ，取出线性表中的第i个元素所需要的时间应该考虑线性表的存储方式，以及所取的元素在表中的位置；如果是顺序存储，由于顺序表满足“随机存取”的特性，因此不管i多大，取出一个元素的时间复杂度都是O(1)；而如果是链式存储，越靠后的元素，取出所需的时间越长（遍历链表）。

　　Note :若先建立单链表，然后通过直接插入排序从前往后查找元素的位置并依次插入，直接插入排序算法的时间复杂度为O(n^2)；若先对数组进行排序，再建立对应的单链表，对数组进行排序最好的时间复杂度是O(nlog[2]n)，而建立单链表的时间复杂度是O(n)，根据时间复杂度计算的加法原则【

　　Note :由于题中没有提到m链表设有尾指针，因此要先遍历m链表，找到该单链表的尾结点，故时间复杂度为O(n)。

　　A.删除单链表中的第一个元素B.删除单链表中的最后一个元素C.在单链表第一个元素前插入一个新元素

　　Note :注意，在408统考中，当提到一个链表具有头结点时，这通常隐含了该链表有一个指向头结点的头指针。对于B选项，删除单链表中最后一个元素时，需要修改其前驱的next指针域，以及修改尾指针r的指向。

　　Note :假设单链表是递增有序，先找到大于x的结点的直接前驱p，在p之后插入该结点。故T(n) = O(n) + O(1) = O(n)。

　　A.只有尾结点指针没有头结点指针的循环单链表B.只有尾结点指针没有头结点指针的非循环双链表C.只有头结点指针没有尾结点指针的循环双链表

　　Note :重点关注“删除最后一个元素”的操作，对于A和D，如果要删除最后一个元素，必须修改其直接前驱的指针域和尾结点指针，因此需要遍历整个链表，时间复杂度为O(n)。对于B，删除第一个元素时，需要通过结点的prior指针依次往前找到链表的头结点，时间复杂度为O(n)。对于C，四种操作的时间复杂度均为O(1)。

　　Note :当q和p指向相同时，该非空单循环链表只有一个元素（只有首结点），因此在free(q)之前需要修改尾指针的指向，令其指向头结点，这样free(q)之后整个链表为空。

　　Note :根据栈“先进后出”的特性，当输出序列的第一个元素是n时，表明之前的n - 1个元素已经按顺序依次入栈，∴此时得到的输出序列一定是原序列的逆序列，而n, n-1, ..., 3, 2, 1序列中，第i个元素为n - i + 1。

　　Note :由题设条件可知，P3是第一个出栈的元素；根据栈“先进后出的特性，可知当P3出栈时，P1,P2一定还在栈中，所以下一个出栈的元素不可能是P1，而下一个输出的元素是2，所以P1不可能是2。

　　Note :对于C选项，当P2 = 4，P3 = 3时，可知P1只能为1或2，不论P1是1还是2，当P2出栈的时候，3一定还在栈中，而出栈序列下一个元素是P3，所以P4不可能为3。

　　Note :由栈“先进后出”的特性可知，P3可以取到大于3的任何数；进一步分析可知P3亦可取到1和2，所以P3只取不到3，即P3可能取值的个数是n - 1。

　　Ⅰ.采用非递归方式重写递归程序时必须使用栈Ⅱ.函数调用时，系统要用栈保存必要的信息Ⅲ.只要确定了入栈次序，即可确定出栈次序

　　1）从S1 中依次弹出两个操作数a 和 b。2）从S2 中弹出一个运算符op。3）执行相应的运算b op a。

　　假定S1 中的操作数依次是5, 8, 3, 2（2在栈顶），S2 中的运算符依次是*、-、+（+在栈顶）。调用3次F()后，S1栈顶保存的值是(B)。

　　Note :循环队列，默认front指向队头元素，rear指向队尾元素的下一个元素。可知数组A的最大容量是6，且当前队列中有2个元素A[5]和A[0]，其中队头元素是A[5]，队尾元素是A[0]；删除一个元素后，front指向从5变成0；加入两个元素后，rear指向从1变成3。

　　A.仅修改头指针 B.仅修改尾指针C.头尾指针都要修改 D.头尾指针可能都要修改

　　Note :注意是“删除”操作，若删除的队头元素不是队列中唯一一个元素，则仅需要修改头指针；若删除的元素是队列中唯一一个元素，则头尾指针都需要进行修改，删除后队列为空，即令rear = front。

　　Note :队头在链表尾，说明队尾在链表头，而队列的“进队/入队”操作是在队尾进行的，对应于此题即在链表头进行；又因为该循环单链表只设了头指针，所以删除表头结点的操作本身只需要O(1)的时间复杂度，但是删除后要维护链表“循环”的特性，因此需要遍历链表找到链表表尾结点，故总的时间复杂度T(n) = O(1) + O(n) = O(n)。

　　Note :结论记住即可，C选项，输入或者输出受限的双端队列都得不到该输出序列。B选项，输入受限可得输出受限不可得。D选项，输出受限可得输入受限不可得。

　　Note :对于“输出”受限的双端队列，求出队序列时，只需要关心能不能通过

　　Note :注意，此题中rear的指向与默认的循环队列不同，此题中rear直接指向了队尾元素，这意味着在进行“入队”操作时，

　　“送值”和“指针移动”的顺序会发生改变；在默认的循环队列中，rear指向队尾元素的下一个位置，那么在入队时，需要先送值再进行指针移动(即rear指针顺时针移动1位)，而在此题中，需要先令rear指针 + 1，再送值。因此，若想第一个进入队列的元素存储再A[0]处，由于是先移动指针再送值，rear在初始队列为空时必须指向A[0]之前的一个位置，而根据循环队列的特性，A[0]再往前就是数组的末尾了，即n - 1。而由于入队操作不修改front指针，所以front指针直接指向0处。

　　PS :注意此题中对队列的判空条件为——（Q.rear + 1)%MAX_SIZE== Q.front；对队列的判满条件为——（Q.rear + 2)%MAX_SIZE == Q.front。可以看到，与一般情况（rear指向队尾元素的下一个元素）相比，判空和判满的条件都多加了一个“1”。一般情况下

　　Note :由题设条件可知，这是一个标准的默认循环队列，此题中，end1代表front，end2表示rear。显然选A。关于“队满”条件的判定，联系取余运算mod引入的原因，以及顺序存储的队列——数据结构的定义[宏定义MaxSize]。

　　Note :若要使乱序驶入的火车以“1~9”的顺序依次驶出，需要满足两个条件——①每条轨道上的列车都是降序排列（每条轨道上都是编号小的列车先出来）；

　　Note :根据队列“先进先出”的特性，若没有栈S参与，队列Q的出队序列是唯一的，即1,2,3,4,5,6顺序输出；因此，若想让队列前面的元素之后再输出，就必须让这些元素先进栈，之后再出栈。对于C选项，由于输出序列的第一个元素为3，可知元素1,2此时一定在栈中，根据

　　栈“先进后出”的特性，可知2一定比1先出栈，所以不可能得到C选项中的序列。

　　Note :注意，栈中存放的是还不能确定运算次序的操作符，即，当一个运算符已经确定了运算次序时，它就要出栈。中缀表达式从左往后看，第一个+号（a+b）很快就确定了运算次序，因此，第一个+号不会停留在栈中；继续，-, *, (, (, +，一直到扫描到d之前，这五个操作符都没有确定运算次序，因此这五个运算符都还停留在栈中，∴选A。

　　Note :由于中缀表达式的运算符位于操作数的中间，因此，当扫描到中缀表达式中的运算符时，还无法确定该操作符的运算次序（还不能输出），所以需要一个栈来存放这些还不能确定的操作符。依然是中缀表达式从左往后看，第一个/号很快就确定了运算次序a/b，当扫描到b时第一个/号出栈，不会在栈中停留；继续，+，(，这两个运算符也不能确定次序，依次压栈；继续，c*d次序确定，因此第一个*号不会在栈中停留；继续，-，*，依次压栈。所以，在扫描到f时，栈中的元素依次是+, (, -, *四个运算符。

　　Note :由题设条件可知，矩阵下标从[1][1]开始，并且对应存储的数组B下标也是从[1]开始。注意三对角矩阵的特点，除了第一行和最后一行只有2个非零元素外，每一行都存放有3个非零元素。具体解题方法同上一题，算就完事儿（A[66][65]前面有194个元素，∴它自己的位置就是194 + 1 = 195）。

　　Note :仍然注意到矩阵A 和 数组B的下标范围。假设B[k]个元素位于矩阵的第j列，由于矩阵采取“列优先”进行存储，所以前面j-1列共j(j-1)/2个元素，而B[k]位于第j列的第i行，由下标关系可知，B[k]是第j列的第i个元素，所以B[k]本身的行列下标和数组下标的关系就是在j(j-1)/2的基础上加上一个i。

　　Note :认真计算即可，注意计算元素个数时，元素m也包含在内，因为题干问的就是元素m在数组中的下标。同时注意矩阵和数组下标的表示范围。

　　A.三元组表和十字链表 B.三元组表和邻接矩阵C.十字链表和二叉链表 D.邻接矩阵和十字链表

　　Note :十字链表将行单链表和列单链表结合起来存储稀疏矩阵。二叉链表又名左孩子右兄弟表示法，可用于表示树或森林。

　　Note :①“上三角部分”包括主对角线元素，区分于“上三角区”的概念。②C语言一维数组，下标默认从0开始。本题对称矩阵下标从1开始。③m[6,6] 在本题的对称矩阵中，是第6行第一个元素（对角线线对称矩阵M的上三角部分的元素m[i,j]（1 = i = j = 10）按列优先存入C语言的一维数组N中，元素m[7,2] 在N中的下标是(C)。

　　利用对称矩阵的特性，m[7,2] 实则就是存储m[2,7]，从而计算即可（注意是列优先）。62.[2021真题] 二维数组A 按行优先方式存储，每个元素占用1个存储单元。若元素A[0][0]的存储地址是100，A[3][3]的存储地址是220，则元素A[5][5]的存储地址是(B)。

　　注意到，S[]下标从0开始。由于采用KMP算法进行匹配，因此主串S的指针i不变，∴i = 5；模式串t的指针回退到相同前缀处进行比较，∴j = 2。64.[2019真题] 设主串T = abaabaabcabaabc，模式串S = abaabc，采用KMP算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是(B)。

　　当第一次出现“失配”时，比较了6次（第6次时失配），主串指针保持不变，模式串从第三个字符开始比较，因此再比较4次，共10次。五、树与二叉树5.1 树的基本概念

　　65.树的路径长度是从树根到每个结点的路径长度的(A)。A.总和 B.最小值 C.最大值 D.平均值

　　“树的路径长度” 概念，要区分于哈夫曼树的带权路径长度。WPL = 树中所有叶结点的带权路径长度(经过的边数 * 该结点权值)之和。66.对于一棵具有n个结点、度为4的树来说，(A)。

　　要想让已知结点数的树尽可能地高，就必须让这棵树尽可能地瘦长（即每层结点数尽可能的少），设树高为h，根据题设条件可知h + 3 = n，∴h = n - 3。对于D选项，应该是某个结点正好有四个结点，而不是某一层。67.[2010线个度为2的结点，10个度为1的结点，则树T的叶结点个数是(B)。

　　画图，已知高度h，题干问“结点数至少”，因此二叉树要尽可能地瘦高；可知除了根结点所在的第一层外，每一层都是2个结点，∴总的结点数 = 2(h - 1) + 1 = 2h - 1，所以选B。69.设二叉树有2n个结点，且m n，则不可能存在(C)的结点。

　　①“排除法”，设n = 3，即构造一棵有6个结点的二叉树（画图），由题干条件可知，m = 1或m = 2，排除(A)(B)(D)。②“直接法”，利用二叉树的性质1可求。70.设二叉树只有度为0和度为2的结点，其结点个数为15，则该二叉树的最大深度为(C)。

　　解法同68题。设二叉树深度为h，得2h - 1 = 15，∴h = 8。71.高度为h的完全二叉树最少有(C)个结点。

　　“排除法”，画一棵完全二叉树，最下面一层只有最左面一个左孩子结点，秒了。72.一棵有124个叶子结点的完全二叉树，最多有(B)个结点。

　　∵有124个叶子结点，∴二叉树至少有8层(2^7)，而124个叶子结点可以分布在最后一层(即第8层) 和 倒数第二层(第7层)。注意，由于是完全二叉树，最后一层每删除两个连续叶子结点，上一层就会暴露出一个叶子结点(注意这个叶子结点本身是完全二叉树本就有的结点)，∴为了使完全二叉树整体有最多的结点，并且还要满足124个叶子结点的要求，可知最后一层应该删除7个结点，这样第8层共121个叶子结点，加上上一层暴露出来的3个结点，正好是124个叶子结点，而这么做的线个结点——即最后一层的左孩子结点。由于前面7层加起来有127个结点，所以结点总数 = 127 + 121 = 248。73.已知一棵有2011个结点的树，其叶结点个数是116，该树对应的二叉树中无右孩子的结点个数是(D)。

　　“特值法”秒了。由于2011 - 116 = 1895，画图，前面1895层每层一个结点，最后一层有116个叶结点，根据普通树转化为二叉树的原则，只有最后一行的前115个结点有右孩子，其他所有结点均没有右孩子。74.[2009真题] 已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是(C)。

　　注意，第6层有8个叶结点，会有两种情况——①第6层就是最后一层，最后一层共有8个叶结点；②第6层不是最后一层，8个叶结点是最后一层删除连续的叶结点后，上一层所暴露出来的叶结点。题干问整棵树的结点个数最多，所以考虑第二种情况。1~6层共有2^6 - 1 = 63个结点。而第7层（最后一层）的叶结点个数，是第7层总的叶结点数 - 删除的叶结点数 = 2^6 - 8*2 = 64 - 16 = 48。所以整棵树的结点总数 = 63 + 48 = 111个。

　　75.[2011真题] 若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是(C)。

　　768个结点，∴至少有10层（10层全满为2^10 - 1 = 1023个结点）。前面9层一共有2^9 - 1 = 511个结点，所以第10层（最后一层）一共有768 - 511 = 257个结点（叶结点）。又因为257是奇数，所以第9层存在一个只有左孩子的非叶结点。第10层全满有2^9 = 512个结点，∴第9层由于删除而暴露出的叶结点的个数 = (512 - 257 - 1) / 2 = 254 / 2 = 127。∴该二叉树总的叶结点个数 = 257 + 127 = 384。76.[2018真题] 设一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结点都有2个子结点。若T有k个叶结点，则T的结点总数是(A)。

　　由题设条件可知，这是一棵满二叉树，且最后一层有k个结点（叶结点）。由二叉树的性质1可知，k = n2 + 1，得：n2 = k - 1，∴结点总数 = n0 + n2 = k + (k - 1) = 2k - 1。77.[2020真题] 对于任意一棵高度为5且有10个结点的二叉树，若采用顺序存储结构保存，每个结点占1个存储单元（仅存放结点的数据信息），则存放该二叉树需要的存储单元至少是(A)。

　　尤其注意题干中“任意”这两个字。由于二叉树已经限定是5层，所以存储的结点数的范围是(2^4 - 1) + 1 到 2^5 - 1，即16 到 31，又因为题干问的是“至少”，即满足任意性的所有可能的二叉树，所以是31。（如果问的是最少，则为16）。

　　5.3 二叉树的遍历和线.设n，m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是(C)。A.n在m右方 B.n是m祖先 C.n在m左方 D.n是m子孙

　　根据中序遍历“左根右”的特点，要想让n在m之前遍历，需要满足以下三种情况之一：①n在m的左子树上；②

　　③m在n的右子树上。可知，以上三种情况均满足“n在m左方”。79.设n，m为一棵二叉树上的两个结点，在后序遍历时，n在m前的条件是(D)。

　　后序遍历的特点是“左右根”，因此只要满足n是m子孙，n一定会在m之前遍历。

　　后序特性“左右根”，因此BC在A的左右子树的情况都要考虑到（可直接画出）。

　　81.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足(C)。

　　A.所有的结点均无左孩子 B.所有的结点均无右孩子C.只有一个叶结点 D.是任意一棵二叉树

　　83.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为(C)。

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

　　中序遍历，又因为X有左孩子，所以X的前驱一定为其左子树的遍历序列中最后的一个结点。其左子树的遍历仍然满足“左根右”的特性，注意，X的左子树中最右的结点可能是一个右孩子（最右的叶结点），也可能是一个只有左孩子的分支结点。

　　A.前序线索树 B.中序线索树 C.后序线索树 D.所有线索树Note :

　　后序遍历“左右根”，最后访问根结点，但由于根结点的右孩子不一定为空（，所以需要一个栈来保存相关信息。

　　85.[2009真题] 给定二叉树如下图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列是3175624，则其遍历方式是(D)。

　　86.[2010真题] 下列线索二叉树中（用虚线表示线索），符后后序线索树定义的是(D)。

　　87.[2011真题] 一棵二叉树的前序遍历序列和后序遍历序列分别是1,2,3,4 和 4,3,2,1，该二叉树的中序遍历序列不会是(C)。

　　由先序“根左右”，后序“左右根”的特性可知，a为根结点，e一定为a的左孩子或右孩子，假设e为a的左孩子，则只需要判断a是否有右孩子，又因为后序遍历序列中e后面紧接着遍历a，可知a的孩子结点只有e。

　　89.[2013真题] 若X是后序线索二叉树中的叶结点，且X存在左兄弟结点Y，则X的右线索指向的是(A)。

　　A.X的父结点 B.以Y为根的子树的最左下结点C.X的左兄弟结点Y D.以Y为根的子树的最右下结点

　　90.[2014真题] 若对下图所示的二叉树进行中序线索化，则结点X的左、右线索指向的结点分别是(D)。

　　91.[2015真题] 先序序列为a,b,c,d 的不同二叉树的个数是(B)。

　　①技巧——先序序列和中序序列的关系：相当于以先序序列为入栈次序，以中序序列为出栈次序。根据卡特兰数(1/n+1)*C[2n,n]，将n = 4代入可得14。②亦可直接手动写出所有可能结果：先假设b,c,d均在A的左子树上，有5种可能，根据对称关系，可知b,c,d都在A的左子树或右子树上的情况共有10种可能。再写出b,c,d不在同一棵子树下的情况，共4种可能（注意，当A既有左孩子又有右孩子时，不存在对称情况，因为要满足先序遍历“根左右”的特性，左右子树不能随便交换）。

　　92.[2017真题] 某二叉树的树形如下图所示，其后序序列为e,a,c,b,d,g,f，树中与结点a同层的结点是(B)。

　　93.[2017真题] 要使一棵非空二叉树的先序序列与中序序列相同，其所有非叶结点须满足的条件是(B)。

　　先序“根左右”，中序“左根右”，当树中所有分支结点都没有左孩子时，可知两序列相同。此题亦可通过画图的方式用排除法。对于C选项，并不是充分条件。

　　94.利用二叉链表存储森林时，根结点的右指针是(D)。A.指向最左兄弟 B.指向最右兄弟 C.一定为空 D.不一定为空

　　AB选项表述不清楚。但D选项一定对。森林转换为二叉树，当森林中只有一棵树时，根结点的右指针域为空；当森林中出现第二棵树时，根结点的右指针将指向原先第二棵树的根结点。

　　95.设F是一个森林，B是由F变换来的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有(C)个。

　　对于F中的非终端结点，其所有孩子结点在转换之后，最后一个孩子结点的右指针域一定为空，所以森林中的n个非终端结点对应到二叉树中会出现n个右指针域为空的结点。又因为森林中最后一棵树的根结点，转换到二叉树中是二叉树根结点的最右孩子结点，其右指针域也为空。所以总的右指针域为空的结点有n + 1个。结论

　　——树转换为二叉树时，对应二叉树中无右孩子的结点个数 = 分支结点数 + 1。

　　96.[2009真题] 将森林转换为对应的二叉树，若在二叉树中，结点u 是结点v 的父结点的父结点，则在原来的森林中，u 和 v可能具有的关系是(B)。

　　二叉树中可能出现的情况：对于Ⅰ，u的左孩子的右孩子是v；对于Ⅱ，u的右孩子的右孩子是v；对于Ⅲ，直接证明不太好证，想到“反证法”

　　，假设Ⅲ成立，则无法得到“结点u 是结点v 的父结点的父结点”的题目条件，所以假设不成立，Ⅲ不成立。

　　98.[2014真题] 将森林F转换为对应的二叉树T，F中叶结点的个数等于(C)。

　　A.T中叶结点的个数 B.T中度为1的结点个数C.T中左孩子指针为空的结点个数 D.T中右孩子指针为空的结点个数

　　森林中的叶结点，若其有右兄弟，则转为二叉树后其右指针不为空；但转为二叉树后其左指针一定为空。

　　——由于一棵树中，除根结点外，每个结点都有唯一确定的双亲(父结点)，所以，除根结点外每个结点唯一对应有一条边；∴

　　在n个结点的树中有n - 1条边，即每棵树的结点数比边数多1。对应于此题，25 - 15 = 10，结点数共比边数多10，所以森林中有10棵树。100.[2019真题] 若将一棵树T转化为对应的二叉树BT，则下列对BT的遍历中，其遍历序列与T的后根遍历序列相同的是(B)。

　　A.先序遍历 B.中序遍历 C.后序遍历 D.按层遍历101.[2020真题] 已知森林F及与之对应的二叉树T，若F的先根遍历序列是a,b,c,d,e,f，中根遍历序列是b,a,d,f,e,c，则T的后根遍历序列是(C)。

　　103.设哈夫曼编码的长度不超过4，若已对两个字符编码为1 和 01，则还最多可对(C)个字符编码。A.2 B.3 C.4 D.5

　　哈夫曼编码属于前缀编码，而前缀编码的特点是“没有一个编码是另一个编码的前缀”，由此特性可知，若想进行最多的编码，应该从长度更长的编码开始考虑，因此得到0000，0001，0010，0011四个。

　　在哈夫曼编码（Huffman Coding）中，“不同的码字”（unique code words）指的是代表不同字符或符号的、互不相同的编码。

　　105.若度为m的哈夫曼树中，叶子结点个数为n，则非叶子结点的个数为(C)。

　　回顾——在n个结点的树中有n - 1条边，即每棵树的边的个数总是等于结点数减去1

　　由一般哈夫曼树(二叉树)的定义可知，度为m的哈夫曼树中只有度为0和度为m的结点，设度为m的结点（即非叶子结点）的个数为x，每个度为m的结点都贡献了m条边；根据树的性质，边的个数也等于总结点数 - 1，因此可列出等式：mx = n + x - 1，移项化简可得：x = ⌈(n - 1)/(m - 1)⌉。

　　106.下列关于并查集的叙述中，(D)是错误的。A.并查集是用双亲表示法存储的树

　　B.并查集可用于实现克鲁斯卡尔算法C.并查集可用于判断无向图的连通性D.在长度为n的并查集中进行查找操作的时间复杂度为O(log[2]n)

　　107.[2010线）个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是(A)。

　　A.该树一定是一棵完全二叉树B.树中一定没有度为1的结点C.树中两个权值最小的结点一定是兄弟结点D.树中任一非叶结点的权值一定不小于下一层任一结点的权值

　　109.[2015真题] 下列选项中给出的是从根分别到达两个叶结点路径上的权值序列，属于同一棵哈夫曼树的是(D)。

　　根据首尾译码，可排除AB，又因为中间连续两个“001”，即连续两个e，所以选D。

　　111.[2018真题] 已知字符集{a,b,c,d,e,f}，若各字符出现的次数分别为6,3,8,2,10,4，则对应字符集中各字符的哈夫曼编码可能是(A)。

　　由前缀编码的特点，首先排除BC，构造哈夫曼树可知，根结点到6的路径为2，所以排除D。

　　112.[2019真题] 对n个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有115个结点，则n的值是(C)。

　　回顾——树的WPL的定义：树中所有叶结点的带权路径长度之和称为该树的带权路径长度。

　　六、图 七、查找 八、排序每次写博文写到2万字左右，CSDN的编辑器就开始一卡一卡的，可能是我的网络有点拉。没办法，第六章“图”的习题带有大量图片，如果继续在这篇博文里面写，“图、查找、排序”都完成预计一共有4万字左右，估计要卡爆了。人不能让尿憋死，还是老方法，剩余的“图、查找、排序”的内容单独另开一篇博文作为补充，可不是因为我能再氵一篇博文(。