2026年客观题高频考点真题及答案

2026年客观题高频考点真题及答案一、单项选择题（本大题共20小题，每小题1.5分，共30分。在每小题给出的四个选项中，只有一项是最符合题目要求的）1.某算法的时间复杂度表达式为T(n)A.OB.OC.OD.O【答案】C【解析】根据递推关系式展开：T(n)=T2.设栈的输入序列为`1,2,3,4`，则以下哪个序列不可能是栈的输出序列？（）A.`1,2,3,4`B.`2,1,4,3`C.`3,1,2,4`D.`4,3,2,1`【答案】C【解析】栈的特性是“后进先出”。对于选项C，若要输出3，则需先将1、2、3入栈，此时栈顶为3，出栈得到3。此时栈内剩余元素为1、2（2在栈顶，1在栈底），下一个出栈的只能是2，而不可能是1，因此`3,1,2,4`是不可能的输出序列。3.深度为k（根节点深度为1）的完全二叉树至少有（）个节点。A.B.C.−D.−【答案】A【解析】深度为k的完全二叉树，最少节点的情况是第k层只有1个节点，此时前k−1层是一棵满二叉树。满二叉树前k−1层的节点总数为−14.在一个长度为n的有序顺序表中，采用折半查找法查找一个存在的元素，则查找过程中元素比较次数最多为（）。A.nB.⌊C.nD.⌈【答案】B【解析】折半查找的过程可以用判定树来描述，判定树是一棵平衡二叉树。具有n个结点的判定树的深度为⌊l5.下列关于图的邻接矩阵存储结构的描述中，正确的是（）。A.无向图的邻接矩阵是对称矩阵，且对角线元素全为1B.有向图的邻接矩阵中，第i行非零元素个度为顶点i的入度C.无向图的邻接矩阵中，第i行非零元素个数为顶点i的度D.邻接矩阵只适用于存储稠密图，且无法表示带权图【答案】C【解析】无向图的邻接矩阵是对称的，且对角线元素为0（因为没有自环），A错。有向图的邻接矩阵中，第i行非零元素个数为顶点i的出度，第i列非零元素个数为入度，B错。邻接矩阵可以存储带权图（权重代替1），也可以存储稀疏图（只是空间利用率低），D错。C选项正确描述了无向图邻接矩阵的性质。6.对一棵二叉排序树进行中序遍历，得到的结点序列是一个（）。A.无序序列B.递增有序序列C.递减有序序列D.堆序列【答案】B【解析】二叉排序树的性质是：对于任意非叶子结点，其左子树上所有结点的值均小于该结点，右子树上所有结点的值均大于该结点。因此对其进行中序遍历（左-根-右）时，得到的必然是一个递增的有序序列。7.下列排序算法中，在最坏情况下时间复杂度为O(nlA.快速排序B.归并排序C.堆排序D.冒泡排序【答案】C【解析】快速排序最坏时间复杂度为O()，空间复杂度为O(logn)；归并排序时间复杂度为O(8.已知一个哈希函数为H(A.1B.2C.3D.4【答案】C【解析】计算各关键字哈希地址：19%13=6，放入6号位。14%13=1，放入1号位。23%13=10，放入10号位。1%13=1，发生冲突，线性探测2号位，2号位为空，放入2号位。68%13=3，放入3号位。20%13=7，放入7号位。查找20时，直接定位到7号位，比较1次即可。（更正：题目应改为查找关键字1，若查找1：H(1)=1，比较14(1次)，探测2号位比较23(2次)，探测3号位比较68(3次)，探测4号位找到1(4次)。若坚持原题查找20则为1次。为高频考点考察冲突探测，此处题目设定为查找关键字1）。假设题目意图为查找关键字1，则比较次数为4次。若按字面查找20，答案为A。本解析基于标准考察意图，按查找存在冲突的元素为例。此处假定题干改为查找关键字`1`，答案应为D。由于原题干为20，严格按原题计算，20的哈希地址为7，无冲突，比较1次。故选A。9.设循环队列的存储空间为Q[A.`(rear-front+M)%M`B.`rear-front`C.`rear-front+1`D.`(front-rear+M)%M`【答案】A【解析】循环队列中，由于`rear`可能小于`front`（即队尾绕回了数组头部），直接相减可能产生负数。因此需要加上M再对M取模，以确保结果在0到M−10.在一棵度为4的树中，有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点。则该树中叶子结点的个数为（）。A.41B.82C.113D.122【答案】B【解析】设树中结点总数为n，叶子结点数为。根据树的性质，n=+同时，所有结点的度数之和等于结点总数减1（即分支数），公式为：n−代入已知条件：n=n−所以n=123。代入n=+4111.下列关于树和二叉树的叙述中，正确的是（）。A.二叉树是树的特殊情形B.树和二叉树都可以为空C.树转换为二叉树后，原树中兄弟结点的关系变为父子关系D.二叉树的度一定为2【答案】C【解析】树和二叉树的概念不同，二叉树区分左右子树，而树不区分子树次序，A错。在数据结构定义中，二叉树可以为空，但树通常要求至少有一个根结点，B错。二叉树的度可以为0或1，不一定是2，D错。树转二叉树的规则是“左孩子右兄弟”，因此原树中的兄弟结点在二叉树中会变为父子的链接关系，C正确。12.无向图的邻接表中，顶点v的边表中结点的个数等于（）。A.顶点v的度B.顶点v的入度C.顶点v的出度D.图中所有顶点的度之和【答案】A【解析】在无向图的邻接表表示中，顶点v对应的链表中每个结点都代表一条与v相连的边。因此，链表的长度即为顶点v的度数。对于有向图，顶点v的链表长度表示出度。13.对n个元素的序列进行快速排序，如果初始序列已经有序，则快速排序的时间复杂度为（）。A.OB.OC.OD.O【答案】C【解析】当初始序列有序时，快速排序每次选择的基准元（如取第一个元素）都会将数组划分为一个空区间和一个长度为n−1的区间。此时递归树退化为单链，深度为n，每层划分需比较n−i次，总比较次数约为14.下列关于分块查找的描述，错误的是（）。A.分块查找又称为索引顺序查找B.索引表必须是有序的C.块内元素可以是有序的，也可以是无序的D.分块查找的效率一定高于折半查找【答案】D【解析】分块查找结合了顺序查找和折半查找的特点。其索引表是有序的，可以对索引表进行折半查找；块内元素可以无序，只能在块内进行顺序查找。分块查找的效率介于折半查找和顺序查找之间，并不一定高于折半查找，只有当索引表和块内结构适合时才能达到较好效果，故D错误。15.下列关于平衡二叉树（AVL树）的叙述中，正确的是（）。A.平衡二叉树中任意结点的左右子树高度差的绝对值不超过1B.平衡二叉树的平均查找长度低于理想的平衡二叉树（满二叉树）C.插入结点导致平衡破坏时，必须进行全局重构D.平衡二叉树是一棵完全二叉树【答案】A【解析】平衡二叉树的定义就是任意结点的左子树和右子树的高度差的绝对值不超过1，A正确。AVL树的平均查找长度与满二叉树接近，但不可能低于它，B错。插入结点导致失衡时，只需找到最小不平衡子树进行局部旋转（LL、RR、LR、RL型）即可恢复平衡，无需全局重构，C错。AVL树不一定是完全二叉树，D错。16.在数据结构中，数据的逻辑结构与（）无关。A.数据元素的内容B.数据元素之间的关系C.数据元素的个数D.数据的存储方式【答案】D【解析】数据的逻辑结构是指数据元素之间的逻辑关系，如线性结构、树形结构、图状结构等。它与数据元素的具体内容、个数和关系有关，但与数据在计算机中的存储方式（物理结构/存储结构）无关。存储结构才是逻辑结构在计算机中的映射。17.设有一个10阶对称矩阵A，采用压缩存储方式按行优先存放其下三角阵元素到一维数组B[1…55]A.8B.12C.13D.14【答案】C【解析】对称矩阵按行优先存放主对角线及以下元素。对于元素A[i][j]（代入i=5,18.下列关于最小生成树的描述中，正确的是（）。A.最小生成树是唯一的B.普里姆算法和克鲁斯卡尔算法的时间复杂度总是相同的C.若图中所有边权值均不相同，则最小生成树唯一D.最小生成树的边数一定等于顶点数【答案】C【解析】最小生成树不一定是唯一的，如果存在权值相同的边，可能有多棵最小生成树，A错。Prim算法适合稠密图（邻接矩阵O()），Kruskal适合稀疏图（堆+并查集O(19.对含有n个互不相同元素的数组进行排序，下列哪种排序算法在最坏情况下的比较次数与初始序列的排列顺序无关？（）A.冒泡排序B.简单选择排序C.快速排序D.直接插入排序【答案】B【解析】简单选择排序无论初始序列如何，每次都要在未排序部分进行n−i−20.如果将一个大小为n的数组循环左移k位，要求时间复杂度为O(n)A.每次移动一位，移动k次B.使用求最大公约数的交替交换法C.三次逆置法（整体逆置，前段逆置，后段逆置）D.借助辅助数组一次性完成移动【答案】C【解析】选项A时间复杂度为O(nk)，不符要求。选项B虽然能实现O(n)时间和O(1)空间，但实现较为复杂。选项D空间复杂度为O(二、多项选择题（本大题共10小题，每小题2分，共20分。在每小题给出的四个选项中，至少有两个选项是符合题目要求的，多选、少选或错选均不得分）21.下列算法中，属于稳定的排序算法的有（）。A.快速排序B.归并排序C.冒泡排序D.基数排序【答案】BCD【解析】稳定排序是指在排序过程中，相等元素的相对次序保持不变。快速排序是不稳定的，因为在划分过程中可能会改变相同元素的相对顺序。归并排序、冒泡排序和基数排序都是稳定的排序算法。22.关于链表和顺序表，下列说法正确的有（）。A.顺序表支持随机访问，而链表不支持B.链表在进行插入和删除操作时，不需要大量移动元素C.顺序表的存储密度一定等于1D.链表的存储空间是动态分配的，不需要预先分配最大容量【答案】ABD【解析】顺序表采用数组实现，支持O(23.在图的遍历算法中，广度优先搜索（BFS）和深度优先搜索（DFS）常使用的数据结构分别是（）。A.栈B.队列C.优先队列D.递归调用栈【答案】AB（或ABD，视题目严谨性而定，标准考试通常为AB）【解析】广度优先搜索（BFS）按照层次遍历，通常借助队列来实现。深度优先搜索（DFS）是一条路走到黑再回退，显式实现需要使用栈，隐式实现则是通过递归调用栈来完成的。故选A（用于DFS）和B（用于BFS）。24.下列关于树与二叉树的说法，正确的有（）。A.哈夫曼树中没有度为1的结点B.一棵完全二叉树一定是一棵满二叉树C.二叉树第i层上最多有个结点（i≥1D.哈夫曼树的带权路径长度（WPL）是所有可能的二叉树中最小的【答案】ACD【解析】哈夫曼树在构造过程中每次都是将两棵树合并，因此所有非叶子结点的度均为2，不存在度为1的结点，A对。满二叉树是完全二叉树的特例，完全二叉树不一定是满二叉树，B错。根据二叉树性质，第i层最多有个结点，C对。哈夫曼树就是最优二叉树，其带权路径长度最小，D对。25.在解决计算机科学中的实际问题时，下列哪些场景最适合使用队列结构？（）A.操作系统中管理打印机任务的排队B.消除递归算法中的递归调用C.广度优先搜索算法中的待访问节点管理D.撤销操作（Undo）功能的实现【答案】AC【解析】队列具有“先进先出”的特点。打印机任务排队和广度优先搜索都严格按照先到先处理的顺序，AC正确。消除递归通常使用栈（后进先出），B错。撤销操作通常使用栈来保存历史状态，D错。26.下列关于哈希（散列）查找的说法，正确的有（）。A.哈希函数的构造越复杂，查找效率越高B.装填因子α越大，发生冲突的可能性越大C.解决冲突的开放定址法在删除元素时需进行逻辑删除，不能直接物理删除D.哈希表的平均查找长度（ASL）与哈希函数本身无关，只与装填因子和冲突处理策略有关【答案】BC【解析】哈希函数应尽量简单且分布均匀，过于复杂反而增加计算哈希地址的时间，A错。装填因子α=，α27.在一棵非空的二叉树中，若叶子结点数为，度为2的结点数为，度为1的结点数为，则下列等式成立的有（）。A.=B.=C.nD.n=2+【答案】ACD【解析】根据二叉树的性质：1.总结点数n=2.分支数总和等于度为1和2结点的和：B=+23.联立得n−1=+24.将=−1代入n=++28.下列关于贪心算法和动态规划的说法，正确的有（）。A.贪心算法总是做出在当前看来最好的选择B.动态规划会保存子问题的解，避免重复计算C.贪心算法一定能求得全局最优解D.动态规划和贪心算法通常都需要满足最优子结构性质【答案】ABD【解析】贪心算法自顶向下做选择，不从整体最优考虑，只做局部最优选择，A对。动态规划通过备忘录或表格保存子问题解，B对。贪心算法并不总能得到全局最优解，只有在具有贪心选择性质的特定问题中才适用，C错。两者的基础都建立在最优子结构性质上，D对。29.下列哪些图的最短路径算法可以处理图中存在负权边的情况？（）A.Dijkstra算法B.Floyd算法C.Bellman-Ford算法D.SPFA算法【答案】BCD【解析】Dijkstra算法基于贪心策略，要求每次扩展的路径长度非递减，因此不能处理负权边，A错。Floyd算法基于动态规划，可以处理负权边（但不能处理负权回路），B对。Bellman-Ford和SPFA算法都是基于动态松弛策略，专门设计用于处理带负权边的图，CD对。30.关于森林转换为二叉树，下列说法正确的有（）。A.转换规则为“左孩子，右兄弟”B.森林中第一棵树的根结点作为二叉树的根结点C.森林中第一棵树的子树森林转换为二叉树的左子树D.森林中除第一棵树外的其他树组成的森林转换为二叉树的右子树【答案】ABCD【解析】森林转二叉树的标准规则是：将所有兄弟结点连起来，保留第一个孩子连线，其余孩子连线断开，然后旋转。逻辑上等价于：第一棵树的根作为二叉树根；第一棵树的子树森林转为左子树；剩余树的森林转为右子树。这符合“左孩子，右兄弟”法则，ABCD均正确。三、填空题（本大题共10小题，每小题2分，共20分）31.在一个长度为n的顺序表中删除第i个元素，需要向前移动________个元素。**【答案】n【解析】删除第i个元素后，其后的n−i个元素（从i+32.已知一棵完全二叉树的第6层有8个叶子结点，则该完全二叉树最多有________个结点。**【答案】111【解析】完全二叉树第6层有8个叶子节点，说明第6层并未满。若第6层是最后一层，则前5层是满的，共有−1第6层最多有=32个节点。有8个叶子节点，说明有32这些非叶子节点在第7层最多有24×此时总节点数为：前5层（31）+第6层节点（32）+第7层孩子节点（48）=111。33.在一个双链表中，要在指针`p`所指结点之后插入一个新结点`s`，其关键操作顺序为：`s->next=p->next;s->prior=p;if(p->next)p->next->prior=s;`最后一步是`________=s;`。**【答案】`p->next`【解析】双链表插入操作的最后一步需要更新前驱结点`p`的`next`指针，使其指向新插入的结点`s`，即`p->next=s;`。34.拓扑排序主要是为了检查有向图中是否存在________。**【答案】环（或回路）【解析】拓扑排序是对有向无环图（DAG）的顶点进行线性排序。如果图中存在环，则无法完成所有顶点的拓扑排序。因此拓扑排序常用于检测图是否存在回路。35.堆排序是一种基于________数据结构的排序算法，其最坏情况下的时间复杂度为O(**【答案】完全二叉树【解析】堆在逻辑上是一棵完全二叉树，其性质是父结点的值大于（或小于）其子结点的值。堆排序正是利用了这种结构特性来快速选取最值并完成排序的。36.在一棵度为m的树中，若有个度为1的结点，个度为2的结点，...，个度为m的结点，则该树的叶子结点数等于________。**【答案】1【解析】根据树的分支数公式：总结点数n=++…+；分支数B37.折半查找的判定树本质上是一棵________二叉树，若表中有100个元素，则查找不成功时的最大比较次数为________次。**【答案】平衡；7【解析】折半查找的判定树形态是一棵平衡二叉树。对于n=100，树的高度38.设有一个10阶对称矩阵A，采用压缩存储方式按列优先存放其下三角阵元素到一维数组B[1…55]**【答案】18【解析】按列优先存储下三角阵时，元素A[i][j]（i≥j）在B中的位置k=+i。代入i=5,j=3，计算得k=+5=3+5=8？**（注意：此处按列优先存储下三角时，公式k=+i是正确的。但A[5][3]表示第5行第3列。按列优先，前两列元素个数为=3，第3列包含元素39.在一个无向图中，所有顶点的度数之和等于所有边数的________倍。**【答案】2【解析】在无向图中，每条边连接两个顶点，在计算顶点度数时，每条边会被其两端的顶点各计算一次，因此度数之和为边数的2倍。40.任何一棵二叉树中，度为0的结点数等于度为2的结点数加________。**【答案】1【解析】这是二叉树的基本性质之一，即=+四、判断题（本大题共10小题，每小题1分，共10分。正确的打“√”，错误的打“×”）41.数据元素是数据的最小单位。（）**【答案】×【解析】数据项是数据不可分割的最小单位；数据元素是数据的基本单位。例如一个学生记录是数据元素，而学号、姓名等是数据项。42.在栈的顺序存储结构中，只要栈不满，就可以执行入栈操作。（）**【答案】√【解析】栈的操作原则是后进先出。只要栈顶指针未达到栈的最大容量上限（即栈未满），入栈操作就可以正常进行。43.哈夫曼树的带权路径长度（WPL）是唯一的，因此哈夫曼树的形态也一定是唯一的。（）**【答案】×【解析】当存在权值相同的结点时，由于合并顺序的不同，可能会构造出形态不同但WPL相同的哈夫曼树。所以WPL是唯一的，但形态不一定唯一。44.广度优先搜索（BFS）遍历图的过程类似于树的层次遍历。（）**【答案】√【解析】BFS从某个顶点出发，依次访问其所有未访问的邻接点，然后再按这些邻接点被访问的先后次序依次访问它们的邻接点，这完全类似于树的按层次遍历过程。45.归并排序是一种稳定的排序算法，且在最坏情况下的时间复杂度也为O(**【答案】√【解析】归并排序在合并两个有序子表时，如果遇到相等的元素，总是先将左边的元素放入结果集中，因此是稳定的。其时间复杂度恒为O(46.有向图的邻接矩阵一定是不对称的。（）**【答案】×【解析】如果有向图中的每一条边都存在对应的反向边，即该图实际上是一个无向图或有向完全图的某种特例，其邻接矩阵就是对称的。不过一般的单向有向图矩阵不对称，但“一定”二字过于绝对。47.一个具有n个顶点的无向连通图，最少有n条边。（）**【答案】×【解析】无向连通图最少有n−48.在二叉搜索树（BST）中，新插入的结点总是成为叶子结点。（）**【答案】√【解析】在二叉搜索树插入时，总是从根结点开始比较，找到合适的空位置插入。插入操作不会重新调整树的结构，因此新结点必然作为叶子结点挂在树的最底端。49.求解图的单源最短路径的Dijkstra算法可以用于带有负权边的图。（）**【答案】×【解析】Dijkstra算法基于贪心策略，其前提是路径长度非递减。负权边会破坏这一前提，导致已经确定最短路径的顶点可能被后续更短的带负权的路径覆盖，算法失效。50.折半查找法既适用于顺序存储的有序表，也适用于链式存储的有序表。（）**【答案】×【解析】折半查找需要通过下标快速定位中间元素，这要求存储结构支持随机访问能力。链表不支持随机访问，因此折半查找只适用于顺序存储的有序表。五、简答题（本大题共5小题，每小题4分，共20分）51.简述栈和队列在逻辑结构上的主要区别及其各自的典型应用场景。【答案】（1）区别：栈和队列都是操作受限的线性表。栈只允许在一端（栈顶）进行插入和删除操作，遵循后进先出（LIFO）原则；队列只允许在一端（队尾）插入，在另一端（队头）删除，遵循先进先出（FIFO）原则。（2）典型应用场景：栈：常用于函数调用栈、递归算法的执行机制、表达式求值（如中缀转后缀）、括号匹配检测以及浏览器的后退功能等。队列：常用于操作系统中的任务调度（如打印机任务队列）、广度优先搜索（BFS）遍历图或树、消息缓冲区管理等。52.什么是哈夫曼树？简述其构造过程，并说明其在数据压缩中的应用原理。【答案】（1）定义：哈夫曼树又称最优二叉树，它是带权路径长度（WPL）最小的二叉树，即所有叶子结点的权值乘以其到根结点路径长度之和最小。（2）构造过程：①将给定的n个权值构造为n棵只有根结点的二叉树，构成森林。②在森林中选取两棵根结点权值最小的树合并，作为左右子树生成一棵新树，新树根的权值为左右子树根权值之和。③将选中的两棵树从森林中删除，将新树加入森林。④重复②③步骤，直到森林中只剩一棵树，即为哈夫曼树。（3）应用原理：在数据压缩中，将出现频率高的字符赋予较小权值，频率低的字符赋予较大权值。通过哈夫曼树对字符进行编码（左分支记0，右分支记1），频率高的字符离根近，编码短；频率低的字符离根远，编码长。这保证了总编码长度最短，实现了无损压缩。53.简述B树和B+树在结构上的主要区别。【答案】（1）关键字存储：在B树中，所有结点（包括内部结点和叶子结点）都存储关键字和对应的数据记录；而在B+树中，所有数据记录都存储在叶子结点中，内部结点仅存储用于索引的关键字信息。（2）叶子结点连接：B树的叶子结点相互独立；而B+树的叶子结点通过指针连接成一个有序链表，支持高效的范围查询和遍历。（3）查找路径：在B树中，查找可能在任何一层结点中命中并结束；而在B+树中，无论内部结点是否匹配关键字，查找最终必须走到叶子结点才能获取到完整的数据记录。54.简述快速排序的基本思想及其时间复杂度和空间复杂度分析。【答案】（1）基本思想：快速排序基于分治法。首先在待排序序列中选取一个元素作为基准（pivot），通过一趟排序将序列划分为两部分，使得左边部分所有元素均小于等于基准，右边部分所有元素均大于等于基准。然后递归地对左右两部分进行同样的操作，直到整个序列有序。（2）时间复杂度分析：最优情况：每次划分都能将序列均分为两半，递归树深度为logn，每层划分比较n最坏情况：序列已有序，每次划分极度不平衡（一边n−1，一边为空），退化为冒泡排序，时间复杂度为平均时间复杂度：O(（3）空间复杂度分析：快速排序是原地排序，不需要额外辅助空间。但由于递归调用需要消耗栈空间，最优和平均空间复杂度为O(logn55.什么是哈希冲突？简述解决哈希冲突的两种常用方法（开放定址法和链地址法）及其优缺点。【答案】（1）定义：哈希冲突是指两个不同的关键字通过哈希函数计算得到了相同的哈希地址的现象。（2）开放定址法：原理：当发生冲突时，在哈希表中寻找下一个空闲的哈希地址（如线性探测、二次探测）并填入。优点：不需要额外的存储空间，所有元素都在表内，存储利用率较高。缺点：容易产生“聚集”现象（特别是线性探测），导致查找效率下降；删除操作困难，通常只能进行逻辑删除，否则会中断探测序列。（3）链地址法（拉链法）：原理：将所有哈希地址相同的关键字链接在同一个单链表中，哈希表存储各个链表的头指针。优点：处理冲突简单，无聚集现象；删除操作方便，直接在链表中删除结点即可；装填因子α可以大于1。缺点：需要额外的指针域空间，存储开销略大；当链表过长时，查找效率会降低（可结合红黑树优化）。六、综合应用题（本大题共3小题，每小题10分，共30分。要求写出详细的计算和分析过程）56.已知一个无向带权图的邻接矩阵表示如下，顶点集合为,,,,，其中∈邻接矩阵A：(04【答案】使用Prim算法，从顶点开始，逐步选择连接已选顶点集合与未选顶点集合之间权值最小的边。初始状态：U=，V−U第一步：从出发的边有：(,)权值4，(最小权值边为(,将加入U。U=,，T第二步：当前U=从：(,)从：(,)权值6，(最小权值边为(,将加入U。U=,,，第三步：当前U=从：(,)权值3，(从：(,)最小权值边为(,将加入U。U=,,,第四步：当前U=从：(,)从：(,)从：(,)最小权值边为(,将加入U。U=,,,至此，所有顶点均已加入，最小生成树构造完毕。加入边的顺序为：(,对应权值依次为：2,4,3,1。总权值W=57.给定一组关键字序列`49,38,65,97,76,13,27,49`，请以第一个关键字`49`为基准，写出快速排序的第一趟划分过程。要求详细标出指针移动、元素交换的过程及每一步数组的状态。最终写出第一趟划分结束后的序列及基准元素的最终位置。【答案】初始序列：`[49,38,65,97,76,13,27,49]`设两个指针`i`和`j`，初始时`i`指向数组首元素（下标0，值为49），`j`指向数组尾元素（下标7，值为49）。基准`pivot=49`。为了区分相同的数值，我们将末尾的49标记为`49'`。初始状态：`49(i),38,65,97,76,13,27(j),49'`（注：通常快速排序先将基准元素备份，然后形成空位。此处按双指针交换法演示）第一步：从右向左（`j`指针左移）寻找第一个小于`pivot(49)`的元素。`j`当前指向49'，不小于49，`j--`。`j`指向27，27<49，停止`j`的移动。此时`i<j`，将`A[i]`与`A[j]`交换。交换后序列：`[27,38,65,97,76,13,49(i/j),49']`（27换到了前面，指针此时处于49的位置）（注：实际双指针交换法中，i指向刚才放入27的位置。即`A[0]=27,A[6]=49`，`i`仍为0，`j`为6。为了清晰，按值表示位置：）数组变为：`27,38,65,97,76,13,49,49'`。`i`在0，`j`在6。第二步：从左向右（`i`指针右移）寻找第一个大于`pivot(49)`的元素。`i`指向27，27<49，`i++`。`i`指向38，38<49，`i++`。`i`指向65，65>49，停止`i`的移动。此时`i<j`，将`A[i]`与`A[j]`交换。交换元素65和49。数组变为：`[27,38,49(i/j),97,76,13,65,49']`。`i`在2，`j`在6。第三步：再次从右向左寻找小于49的元素。`j`当前指向49（下标6），不小于49，`j--`。`j`指向13（下标5），13<49，停止`j`的移动。将`A[i]`与`A[j]`交换。交换元素49和13。数组变为：`[27,38,13(i),97,76,49(j),65,49']`。`i`在2，`j`在5。第四步：再次从左向右寻找大于49的元素。`i`当前指向13，13<49，`i++`。`i`指向97（下标3），97>49，停止`i`的移动。此时`i<j`，将`A[i]`与`A[j]`交换。交换元素97和49。数组变为：`[27,38,13,49(i),76,97(j),65,49']`。`i`在3，`j`在5。第五步：再次从右向左寻找小于49的元素。`j`当前指向97，97>49，`j--`。`j`指向76，76>49，`j--`。`j`移动到下标3，此时`i`也在下标3。`i==j`，循环结束。最后，将基准元素49放入相遇位置（该位置的值实际上已经是基准元素本身或可以直接覆盖为基准元素）。最终第一趟划分结束后的序列为：`[27,38,13,49,76,97,65,49']`。基准元素49的最终位置为下标3（即数组的第4个位置）。58.给定一组字符及其出现频率：`A:5,B:2,C:7,D:4,E:9`。请构造哈夫曼树，要求左分支权值不大于右分支权值。写出各字符的哈夫曼编码，并计算该编码方案的带权路径长度（WPL）。【答案】（1）构造哈夫曼树：初始森林中结点权值集合为F=第一步：选取权值最小的两个结点2(B)和4(D)合并，生成新结点，权值为2+4左孩子为B(2)，右孩子为D(4)。森林更新为：5(第二步：选取权值最小的两个结点5(A)和6()合并，生成新结点，权值为5+6=左孩子为A(5)，右孩子为(6)。森林更新为：7(第三步：选取权值最小的两个结点7(C)和9(E)合并，生成新结点，权值为7+9左孩子为C(7)，右孩子为E(9)。森林更新为：11(第四步：将最后两个结点11()和16()合并，生成根结点R，权值为11+16=左孩子为(11)，右孩子为(16)。哈夫曼树构造完毕。（2）各字符的哈夫曼编码：规定左分支编码为`0`，右分支编码为`1`。从根结点R开始寻找：A：路径为R→B：路径为R→D：路径为R→C：路径为R→E：路径为R→各字符哈夫曼编码汇总：A：00B：010C：10D：011E：11（3）计算带权路径长度（WPL）：W其中为字符频率，为编码长度（即叶子结点在树中的深度）。A的深度为2，B的深度为3，C的深度为2，D的深度为3，E的深度为2。WWW（或者通过计算所有非叶子结点的权值之和来验证：WPL=6+11+16+27？不对，非叶子结点权值之和应等于等一下，计算过程出现了矛盾。重新验证WPL：频率：A:5,B:2,C:7,D:4,E:9。总频率5+WPL公式展开：WP非叶子结点权值之和：(6为什么不相等？因为根结点R的权值27并没有参与构建。实际上，每次合并产生的新结点，其权值是左右孩子权值之和。所有“作为内部结点”的权值之和等于WP合并1：B(2)+D(4)=N1(6)。6是B和D的贡献。合并2：A(5)+N1(6)=N2(11)。11是A,B,D的贡献。合并3：C(7)+E(9)=N3(16)。16是C,E的贡献。合并4：N2(11)+N3(16)=R(27)。27是所有的贡献。WPL等于所有内部结点（N1,N2,N3,R）的权值之和减去最后一次合并的根结点权值？不。WPL等于所有内部结点（非叶子结点）权值之和：N1+N所以WPL=所有内部结点（包括根）权值之和=6+11+正确结论：WPL等于所有非叶子结点（不含根）权值之和？刚才算出来是33。错误在于：WPL=所有分支结点（非叶子结点）的权值之和。这里分支结点是N1,N2,N3,R。计算N1+N2+N3+R=6+11+16+27=60。注意，R的权值27等于所有叶子结点权值之和。如果把R算进去，相当于每个叶子结点都被计算了两次（一次在父结点，一次在根）。真正的快速计算公式：WPL=所有内部结点（不含最顶层根，但包括子树的根）权值之和。实际上：WPL=N1+N2+N3=6+11+16=33？？等一下，A是深度2，深度2等于经过了2次合并。叶子结点被加到其所有祖先结点中。A(5)被加到了N2和R，共2次，5*2=10。B(2)被加到了N1,N2