数据结构和算法分析填空题100道及解析

数据结构与算法分析期末填空题100题附解析1. 数据结构是指数据元素之间的相互关系包括数据的__________、__________和数据运算。答案逻辑结构、存储结构解析数据结构研究数据的组织方式其核心是数据元素间的逻辑关系逻辑结构以及这种关系在计算机内存中的具体实现方式存储结构也称物理结构并定义在这些结构上的一组操作数据运算。2. 顺序存储结构通过__________来表示数据元素之间的逻辑关系。答案元素在存储器中的相对位置解析顺序存储结构将数据元素存放在地址连续的存储单元中逻辑上相邻的元素在物理位置上也相邻因此逻辑关系通过物理位置的邻接关系来体现。3. 链式存储结构通过__________来表示数据元素之间的逻辑关系。答案指针解析链式存储结构中数据元素的存储位置可以任意逻辑关系通过附加的指针字段来表示指针指示了直接后继或前驱元素的存储地址。4. 在单链表中除了首元结点外任一结点的存储位置由其__________结点的指针域指示。答案前驱解析单链表中每个结点包含数据域和指向下一个结点后继的指针域。要访问一个结点必须从头指针出发顺着指针链依次找到其前驱结点才能获得其地址。5. 在双向链表中每个结点包含两个指针域分别指向其__________和__________。答案前驱结点、后继结点解析双向链表克服了单链表只能单向遍历的缺点每个结点包含指向前驱结点和后继结点的两个指针使得双向查找成为可能。6. 栈是一种限定仅在__________进行插入和删除操作的线性表。答案表尾解析栈是一种后进先出的线性表允许插入和删除的一端称为栈顶另一端称为栈底。所有操作都在栈顶进行。7. 队列是一种限定在__________插入、在__________删除的线性表。答案队尾、队头解析队列是一种先进先出的线性表。在队尾进行插入操作入队在队头进行删除操作出队。8. 循环队列是为了解决顺序队列的__________问题而提出的。答案假溢出解析在顺序队列中进行多次入队和出队后队头指针前会留下空位置但队尾指针可能已达到数组末端导致“队满”假象即“假溢出”。循环队列通过将数组视为首尾相接的环来解决此问题。9. 设栈S和队列Q的初始状态为空元素a,b,c,d,e,f依次通过栈S一个元素出栈后即进入队列Q。若6个元素出队的序列是b,d,c,f,e,a则栈S的容量至少应该是__________。答案3解析分析出队序列即入队序列也即出栈序列为b,d,c,f,e,a。模拟过程a,b入栈容量2b出栈c,d入栈容量3d出栈c出栈e,f入栈容量3f出栈e出栈a出栈。过程中栈内最多同时有3个元素故容量至少为3。10. 串是一种特殊的线性表其数据元素限定为__________。答案字符解析串字符串是由零个或多个字符组成的有限序列是内容受限的线性表。11.假设有二维数组A[6][8]每个元素占6个存储单元已知A的起始地址为1000则按行优先存储时元素A[3][4]的地址是__________。答案1228解析按行优先存储LOC(A[3][4]) LOC(A[0][0]) (i * n j) * size 1000 (3 * 8 4) * 6 1000 28 * 6 1228。12. 对稀疏矩阵进行压缩存储常用的两种方法是__________和十字链表。答案三元组顺序表解析稀疏矩阵压缩存储是为了节省空间。三元组顺序表存储非零元素的行、列、值十字链表适用于矩阵的非零元素个数和位置在操作中变化较大的情况。13. 一棵深度为5的满二叉树其结点总数为__________。答案31解析深度为k的满二叉树结点总数为2^k1。因此2^51 31。14. 一棵完全二叉树有1001个结点其中叶子结点的个数是__________。答案501解析在完全二叉树中叶子结点数 n0 floor(n/2) (n % 2) 或 n0 n2 1。对于结点数n1001由于是奇数说明没有度为1的结点。设叶子结点数为n0度为2的结点数为n2则 n n0 n2且 n0 n2 1。联立解得 n0 (n1)/2 501。15. 若二叉树的前序遍历序列是ABDECF中序遍历序列是DBEAFC则其后序遍历序列是__________。答案DEBFCA解析前序确定根A中序划分左右子树左DBE右FC。递归求解左子树前序为BDE中序为DBE确定根B左子为D右子为E右子树前序为CF中序为FC确定根C左子为F。最终树结构为A左子树为B(D, E)右子树为C(F, null)。后序遍历顺序为左子树 - 右子树 - 根即 DEB FCA。16. 在二叉排序树中__________子树上的所有结点值均小于根结点的值。答案左解析二叉排序树BST的性质左子树上所有结点的值均小于根结点的值右子树上所有结点的值均大于根结点的值左右子树也分别是二叉排序树。17. 对二叉排序树进行__________遍历可以得到一个递增的有序序列。答案中序解析根据BST的性质中序遍历左-根-右会先访问所有小于根的值再访问根最后访问所有大于根的值从而得到一个升序序列。18. 具有n个结点的二叉树采用二叉链表存储空指针域的个数为__________。答案n1解析n个结点的二叉树总共有2n个指针域每个结点有2个指向左右孩子。除根结点外每个结点都有一个指针指向它即使用了n-1个指针域。所以空指针域数为 2n - (n-1) n1。19. 图的深度优先搜索遍历类似于树的__________遍历。答案先序解析图的深度优先搜索DFS从某个顶点出发访问其第一个邻接点然后以该邻接点为新起点递归进行这个过程类似于树的先序遍历根-左-右的递归思想。20. 图的广度优先搜索遍历类似于树的__________遍历。答案层次解析图的广度优先搜索BFS使用队列从起始点开始依次访问其所有邻接点再按顺序访问这些邻接点的邻接点这个过程类似于树的层次遍历。21. 一个具有n个顶点的无向完全图其边的总数为__________。答案n(n-1)/2解析无向完全图中任意两个顶点之间都存在一条边。从n个顶点中任选两个的组合数即为边数C(n,2) n(n-1)/2。22. 在AOV网Activity On Vertex network中顶点表示__________边表示__________。答案活动、活动间的优先关系解析AOV网是用顶点表示活动、用有向边表示活动之间优先关系的有向无环图。边Vi, Vj表示活动Vi必须先于活动Vj进行。23. 拓扑排序是对__________进行排序的算法。答案AOV网或有向无环图/DAG解析拓扑排序是将AOV网中所有顶点排成一个线性序列使得对图中任意一条有向边u, vu在线性序列中都出现在v之前。该算法仅适用于有向无环图。24. 顺序查找法适合于存储结构为__________的线性表。答案顺序存储或链式存储解析顺序查找对表的存储结构没有要求既可以是顺序表也可以是链表。它从表的一端开始逐个比较直到找到目标或遍历完整个表。25. 对长度为n的有序顺序表进行折半查找查找成功时最多比较次数为__________。答案⌊log₂n⌋ 1解析折半查找的过程可以用一棵判定树来描述。树的高度h ⌊log₂n⌋ 1而查找成功时比较次数最多不会超过判定树的高度。26. 在哈希表中__________是指不同的关键字映射到同一哈希地址的现象。答案冲突或碰撞解析哈希表通过哈希函数将关键字映射到存储地址。理想情况下不同关键字映射到不同地址但实际中常出现多个关键字对应同一地址的情况即冲突。27. 处理哈希冲突的开放定址法中常用的方法有线性探测法、平方探测法和__________。答案再哈希法或双散列法解析开放定址法在发生冲突时寻找下一个空的哈希地址。除了线性探测依次查看下一个单元和平方探测查看偏移量为1², -1², 2², -2²...的单元再哈希法使用第二个哈希函数计算新的探测地址也是常用方法。28. 直接插入排序是稳定的排序算法其平均时间复杂度为__________。答案O(n²)解析直接插入排序的基本操作是将一个记录插入到已排好序的有序表中。在平均情况下需要比较和移动的次数约为 n²/4时间复杂度为 O(n²)。该算法是稳定的。29. 希尔排序是对__________排序的一种改进又称为缩小增量排序。答案直接插入解析希尔排序将整个待排记录序列分割成若干子序列分别进行直接插入排序。待整个序列中的记录“基本有序”时再对全体记录进行一次直接插入排序。它是不稳定的排序算法。30. 快速排序在平均情况下的时间复杂度为__________在最坏情况下的时间复杂度为__________。答案O(n log n)、O(n²)解析快速排序采用分治策略。平均情况下每次划分将序列分为大小相近的两部分递归深度为O(log n)每层划分总比较次数为O(n)故平均时间复杂度为O(n log n)。最坏情况序列已有序或逆序下每次划分只得到一个子序列递归深度为O(n)时间复杂度退化为O(n²)。31. 堆排序是一种__________选择排序其时间复杂度为__________。答案树形、O(n log n)解析堆排序利用堆一种完全二叉树这种数据结构进行排序。无论最好、最坏还是平均情况其时间复杂度均为 O(n log n)。它是一种不稳定的排序算法。32. 归并排序是一种稳定的排序算法其时间复杂度为__________空间复杂度为__________。答案O(n log n)、O(n)解析归并排序采用分治思想将序列递归分成两半分别排序然后合并。合并过程需要与原始序列等长的辅助空间因此空间复杂度为 O(n)。时间复杂度在各种情况下均为 O(n log n)。33. 基数排序不是基于比较的排序而是基于__________的排序。答案关键字各位的值或多关键字解析基数排序根据关键字各位的值通过“分配”和“收集”过程进行排序。它可以分为最高位优先和最低位优先两种方法。它是稳定的排序算法。34. 算法的时间复杂度是对算法__________的度量。答案执行时间增长率或基本操作执行次数解析时间复杂度是问题规模n的函数它定性描述算法执行时间随n增长的变化趋势通常用大O记号表示关注的是增长率而不是具体的执行时间。35. 算法的空间复杂度是对算法__________的度量。答案临时占用存储空间大小解析空间复杂度是算法在运行过程中临时占用存储空间大小的量度也是问题规模n的函数。36. 在单链表中要删除指针p所指结点的后继结点需执行的语句序列是q p-next;__________;free(q);。答案p-next q-next;或p-next p-next-next;解析要删除p的后继结点q需要将p的指针域指向q的后继结点然后释放q所占用的内存。37. 在双向链表中删除指针p所指结点需要修改__________个指针域。答案2解析设p的前驱结点为prior后继结点为next。删除p需要修改两个指针prior-next p-next;和next-prior p-prior;。38. 表达式求值是__________的典型应用。答案栈解析在表达式求值如中缀表达式转后缀表达式、后缀表达式求值过程中需要使用栈来暂存运算符和操作数利用栈的后进先出特性来处理运算符的优先级和括号。39. 树的度是指树内各结点的度的__________。答案最大值解析结点的度是指结点拥有的子树数。树的度是树内各结点的度的最大值。40. 由3个结点可以构成__________种不同形态的二叉树。答案5解析这是卡特兰数问题。n个结点能构成的不同形态的二叉树数为 C(2n, n) / (n1)。当n3时C(6,3)/4 20/4 5。41. 在具有n个叶子结点的哈夫曼树中其结点总数为__________。答案2n - 1解析哈夫曼树是带权路径长度最短的二叉树且只有度为0和2的结点。设叶子结点数为n则度为2的结点数为 n-1。所以总结点数为 n (n-1) 2n - 1。42. 图的邻接矩阵表示法中对于无向图第i行或第i列非零元素的个数等于顶点i的__________。答案度解析在无向图的邻接矩阵中顶点i的度等于第i行或第i列中非零元素或非∞元素的个数。43. 图的邻接表表示法适用于__________图。答案稀疏解析邻接表用链表存储每个顶点的邻接点对于边数远少于顶点数平方的稀疏图可以节省大量存储空间。44. Prim算法和Kruskal算法都是用于求解__________的算法。答案最小生成树解析Prim算法和Kruskal算法是求解加权连通无向图最小生成树的两种经典贪心算法。Prim算法从某个顶点开始逐步扩展树Kruskal算法按权值从小到大选择边。45. Dijkstra算法用于求解__________最短路径问题要求图中边的权值__________。答案单源、非负解析Dijkstra算法解决从一个源点到图中所有其他顶点的最短路径问题。该算法基于贪心策略要求所有边的权值均为非负否则可能无法得到正确结果。46. 在折半查找中要求查找表必须采用__________存储结构且关键字必须__________。答案顺序、有序按关键字有序解析折半查找的核心是通过比较中间元素将查找区间对半分这要求查找表能够随机访问顺序存储并且表中的元素按关键字有序排列。47. 平衡二叉树AVL树中任一结点的左子树与右子树的高度之差的绝对值不超过__________。答案1解析平衡二叉树是一种特殊的二叉排序树其中每个结点的左右子树高度差平衡因子的绝对值不超过1通过旋转操作维持平衡以保证查找效率为O(log n)。48. B树是一种平衡的__________查找树适用于__________查找系统。答案多路、磁盘等外存解析B树是一种自平衡的多路搜索树一个结点可以拥有多个子结点。它通过减少树的高度来减少磁盘I/O次数广泛应用于数据库和文件系统的索引。49.在排序过程中不涉及数据的内、外存交换的排序称为__________排序。答案内部解析内部排序是指待排序记录全部存放在内存中进行排序的过程。若排序过程中数据量过大需要在内、外存之间多次交换数据则称为外部排序。50. 在冒泡排序中若某一趟排序过程中没有发生任何元素交换则说明__________。答案序列已经有序解析冒泡排序的基本思想是两两比较相邻元素逆序则交换。如果某一趟没有发生交换说明所有相邻元素都已有序即整个序列已经有序排序可以提前结束。51. 数据的__________结构是面向问题的__________结构是面向计算机的。答案逻辑、物理或存储解析逻辑结构描述数据元素之间的逻辑关系是独立于计算机的抽象模型。物理存储结构描述数据在计算机中的具体存储方式是逻辑结构在计算机中的实现。52. 线性表、栈和队列都是__________结构可以在线性表的__________位置插入和删除元素。答案线性、任意解析线性表、栈和队列的逻辑结构都是线性的。栈和队列是操作受限的线性表栈限定在表尾操作队列限定在表尾插入、表头删除。只有线性表允许在任意位置进行插入和删除。53. 在循环队列中队满的条件是__________队空的条件是__________。设front为队头指针rear为队尾指针MAXSIZE为队列容量答案(rear 1) % MAXSIZE front、front rear解析为了区分队满和队空循环队列通常牺牲一个存储单元。队满条件为(rear 1) % MAXSIZE front。队空条件为front rear。54. 两个串相等的充分必要条件是__________和__________。答案长度相等、对应位置的字符都相同解析串的比较是从第一个字符开始逐个字符比较其ASCII码值。只有当两个串的长度相等且每个对应位置的字符都相同时才称两个串相等。55.数组通常采用__________存储结构因此可以通过__________直接访问任意元素。答案顺序、下标或索引解析数组在内存中占用一片连续的存储空间属于顺序存储结构。由于元素类型相同可以通过基地址加上下标乘以元素大小的偏移量来直接计算任意元素的地址实现随机访问。56. 广义表((a,b), c, (d,(e,f)))的长度是__________深度是__________。答案3、3解析广义表的长度是指最外层包含的元素个数。该表最外层有三个元素(a,b)、c、(d,(e,f))故长度为3。深度是指括号嵌套的最大层数。(d,(e,f))中嵌套了(e,f)共3层括号故深度为3。57. 树转换为二叉树时其对应二叉树的根结点__________右子树。答案没有或为空解析树转换为二叉树采用“左孩子右兄弟”法。树的根结点作为二叉树的根结点根结点的第一个孩子作为二叉树根结点的左孩子该孩子的兄弟依次作为其右孩子。因此原树的根结点在转换后没有兄弟故其对应的二叉树根结点没有右子树。58. 线索二叉树是利用二叉链表中的__________指针域来存放指向该结点在某种遍历次序下的前驱和后继结点的指针。答案空解析在n个结点的二叉链表中有n1个空指针域。线索化就是利用这些空指针域按照某种遍历次序分别指向该结点的前驱和后继结点。59. 有向图G的强连通分量是指__________。答案G的极大强连通子图解析在有向图中如果从顶点vi到vj和从vj到vi都有路径则称vi和vj是强连通的。有向图的极大强连通子图称为强连通分量。60.在AOE网Activity On Edge network中从源点到汇点的最长路径称为__________。答案关键路径解析AOE网用边表示活动边上的权值表示活动持续时间。从源点入度为0到汇点出度为0的具有最大路径长度的路径称为关键路径它决定了整个工程的最短完成时间。61. 静态查找表是指在查找过程中查找表__________。答案不发生变化或结构不变解析静态查找表只进行查找操作而不涉及插入和删除。动态查找表在查找过程中可以插入不存在的数据元素或删除已存在的数据元素。62. 在二叉排序树上查找关键字key若查找成功则查找路径上涉及到的结点个数最多等于该树的__________。答案高度或深度解析在二叉排序树上查找时从根结点开始比较若key小于结点值则进入左子树查找若大于则进入右子树查找。查找路径是从根到某个叶子结点或目标结点其长度不会超过树的高度。63. 哈希表的查找效率主要取决于三个因素哈希函数、__________和装填因子。答案处理冲突的方法解析哈希表的平均查找长度与哈希函数是否均匀、处理冲突的方法以及哈希表的装填因子α表中记录数/表长密切相关。64. 在直接插入排序中当待排序序列基本有序时其时间复杂度接近__________。答案O(n)解析直接插入排序的基本操作是将一个记录插入到已排好序的有序表中。如果序列基本有序则每次插入时比较和移动的次数都很少时间复杂度接近O(n)。65. 快速排序的一次划分过程其目标是确定一个基准元素的__________。答案最终位置解析快速排序的划分操作Partition以某个元素为基准将序列中小于基准的元素移到其左边大于基准的元素移到其右边。划分结束后该基准元素就位于其最终排序的正确位置上。66. 堆排序中构建初始堆的时间复杂度是__________。答案O(n)解析将无序序列构建成一个堆大顶堆或小顶堆的过程是从最后一个非叶子结点开始向上调整。这个建堆过程的时间复杂度为O(n)。67. 若一组记录的关键字序列为(50, 40, 95, 20, 15, 70, 60, 45)对其进行直接插入排序当把第5个元素15插入到前面有序表时为寻找插入位置需要比较__________次。答案4解析前4个元素已排好序为(20, 40, 50, 95)。插入15时从后向前比较1595比较1次1550比较2次1540比较3次1520比较4次然后插入到20之前。共比较4次。68. 在归并排序中若当前需合并的两个有序子序列长度分别为m和n则合并操作的最坏时间复杂度为__________。答案O(mn)解析归并排序的合并操作需要依次比较两个子序列的元素将较小的放入结果序列。最坏情况是两个序列的元素交替大小需要比较 mn-1 次移动 mn 次因此时间复杂度为 O(mn)。69. 算法必须满足的五个重要特性是输入、输出、__________、确定性和可行性。答案有穷性解析一个算法除了必须有零个或多个输入、一个或多个输出外还必须具备有穷性算法在执行有限步后必须终止、确定性每条指令含义明确和可行性算法中描述的操作可以通过已实现的基本运算执行有限次来实现。70. 在链栈中若栈顶指针为top则判断栈空的条件是__________。答案top NULL或top nullptr解析链栈通常不设头结点栈顶指针直接指向栈顶元素结点。当栈为空时栈顶指针应为空指针。71. 用S表示入栈操作X表示出栈操作。若元素入栈顺序为1,2,3,4则不可能得到的出栈序列是__________。举一例答案3,1,4,2或其他不可能序列解析这是栈的合法输出序列问题。对于入栈序列1,2,3,43,1,4,2是不可能的。因为若3第一个出栈则1和2必须在3之前入栈且仍在栈中顺序为1,2,3。出栈3后栈顶是2接下来只能出栈2或入栈4不可能直接出栈1。72. 一棵二叉树的先序遍历序列和中序遍历序列相同则该二叉树一定是__________。答案所有结点都没有左子树的二叉树或右斜树解析先序是“根左右”中序是“左根右”。要使两者相同则要求对于所有结点其“左”子树必须为空即每个结点都没有左孩子整棵树呈右斜状。73. 有10个叶子结点的哈夫曼树其高度最大可以是__________最小可以是__________。答案10、5或 ⌈log₂10⌉1解析哈夫曼树的形态不唯一。最坏情况下每次合并都选择当前权值最小的两个结点可能导致树的高度很高极端情况下可达n10。最好情况下合并过程比较均衡树的高度最小为⌈log₂10⌉1415。74. 用邻接矩阵存储有n个顶点和e条边的无向图其矩阵大小为__________其中非零元素或1的个数有__________个。答案n×n、2e解析邻接矩阵是n阶方阵。对于无向图边(vi, vj)会在矩阵的(i,j)和(j,i)两个位置各记录一次因此非零元素个数是边数的两倍即2e。75. 对图进行深度优先搜索遍历时通常需要借助__________来记录已访问过的顶点以避免重复访问。答案访问标志数组或visited数组解析在DFS或BFS遍历中需要用一个布尔数组如visited[]来标记每个顶点是否已被访问过确保每个顶点只被访问一次。76. 在有向图的邻接表表示中第i个链表中的结点个数等于顶点i的__________。答案出度解析在有向图的邻接表中第i个链表存储的是所有以顶点i为尾的弧即从顶点i出发的边链表中的结点个数就等于顶点i的出度。77. 对长度为n的顺序表进行顺序查找查找失败时平均查找长度为__________。答案n1或n解析顺序查找失败时需要将整个表遍历一遍比较n次然后才能确定查找失败。在查找判定树中失败结点有n1个对应n1个区间但具体计算平均查找失败长度时通常考虑与关键字比较的次数为n或n1取决于实现细节如是否包含与“哨兵”的比较。更常见的表述是查找失败时需比较n1次包含与表尾之后位置的比较。78. 在分块查找中若索引表采用顺序查找则其平均查找长度不仅与表长n有关还与每块的长度s和块数b有关。当s取__________时平均查找长度最小。答案√n解析分块查找的平均查找长度 ASL ASL(索引表) ASL(块内)。若索引表和块内均用顺序查找则 ASL (b1)/2 (s1)/2。又因为 n b * s代入得 ASL (n/s s)/2 1。由数学知识可知当 s √n 时ASL取得最小值 √n 1。79. 在平衡二叉树中插入一个新结点后若造成不平衡则需要从__________结点开始向上回溯找到第一个不平衡的结点进行调整。答案插入位置解析在AVL树中插入结点后可能会破坏平衡性。调整方法是从新插入的结点开始沿着通向根的路径回溯找到第一个平衡因子绝对值变为2的祖先结点即最小不平衡子树根结点对其进行旋转调整。80. m阶B树中除根结点外的所有非叶子结点至少有__________棵子树。答案⌈m/2⌉解析m阶B树定义每个结点最多有m棵子树除根结点和叶子结点外每个结点至少有⌈m/2⌉棵子树根结点至少有两棵子树除非它本身是叶子结点。81. 在排序过程中主要进行的两种基本操作是__________和__________。答案比较、移动或交换解析排序算法主要通过比较两个关键字的大小以及根据比较结果移动或交换记录的位置来使记录序列按关键字有序。82. 对n个记录进行简单选择排序所需进行记录移动操作的最少次数约为__________。答案0或3(n-1)解析简单选择排序每趟在未排序序列中选择最小元素交换到已排序序列末尾。移动次数与序列初始状态无关。每次交换需要移动3次记录tempa; ab; btemp。共需n-1趟因此最少移动次数是初始序列已有序时无需交换为0次。但若问的是“记录移动操作次数”通常指必须发生的移动最少为0若问“数据移动次数”则每次交换算3次移动最少为3(n-1)当每次选择的最小元素恰好在正确位置时仍需交换实际上如果序列已有序算法仍会执行交换将元素与自身交换移动次数为3(n-1)。但有些优化实现会检查是否为自己避免不必要的移动此时为0。标准算法通常不检查故常答3(n-1)。更严谨答案3(n-1)解析简单选择排序无论序列初始状态如何都需要进行 n-1 次交换操作将第i小的元素交换到第i个位置。每次交换涉及3次记录移动。因此总的记录移动次数固定为 3(n-1)。83. 若用冒泡排序对序列(18, 12, 10, 9, 6)进行升序排序所需进行的比较次数最多是__________。答案10解析对n个元素进行冒泡排序最坏情况下序列逆序总比较次数为 n(n-1)/2。当n5时5*4/210。84. 在快速排序中若每次划分都能将序列均匀地分割为长度大致相等的两个子序列则此时快速排序的效率__________。答案最高或最好解析快速排序的性能取决于划分的平衡性。如果每次划分都能将序列分成两个长度相近的子序列则递归深度为O(log n)此时时间复杂度为O(n log n)是效率最好的情况。85. 堆排序中输出堆顶元素后通常将__________元素移至堆顶然后对其进行__________操作以重新调整成堆。答案堆的最后一个、向下调整或筛选解析堆排序输出堆顶最大或最小元素后将堆的最后一个元素放到堆顶此时堆的性质被破坏需要从堆顶开始进行一次自上而下的调整称为“筛选”或“堆化”使其重新成为一个堆。86. 若将两个长度分别为m和n的有序表归并成一个有序表最少的比较次数是__________。答案min(m, n)解析归并过程中比较次数最少的情况是一个表的所有元素都小于另一个表的所有元素。此时只需比较 min(m, n) 次即较短表的元素逐个与较长表的第一个元素比较后直接放入然后将较长表剩余部分直接放入。87. 基数排序是稳定的排序算法它按__________位依次进行排序。答案关键字位或个位、十位、百位...解析基数排序基于关键字各位的值进行排序。可以按最低位优先或最高位优先。对于整数通常从个位开始依次对十位、百位...进行稳定的排序如计数排序或桶排序。88. 在链队列中若队头指针为front队尾指针为rear则判断队空的条件是__________。答案front rear或front NULL取决于实现解析链队列通常带有头结点队头指针front指向头结点队尾指针rear指向最后一个元素结点。当队列为空时有front rear均指向头结点。若不设头结点则队空时front NULL。89. 一个递归算法必须包括__________和__________两个部分。答案递归出口或基线条件、递归体或递归调用解析递归算法由两部分构成递归出口即不再递归调用、直接得到结果的条件递归体即包含调用自身的部分将问题分解为规模更小的子问题。90. 在双向循环链表中在指针p所指结点前插入一个由指针s所指的新结点需要修改__________个指针。答案4解析设p的前驱结点为q。插入s在q和p之间。需要修改的指针有s-prior q;s-next p;q-next s;p-prior s;。共4个指针。91. 空串的长度是__________空白串空格串的长度是__________。答案0、空格字符的个数解析空串是不含任何字符的串长度为0。空白串是由一个或多个空格字符组成的串其长度为空格字符的个数。92. 已知广义表A(a, (b, c), d)则head(tail(A))的结果是__________。答案(b, c)**解析**广义表运算tail(A)取A的表尾即去掉第一个元素后的子表((b, c), d)。head()取该子表的表头即第一个元素(b, c)。93. 一棵有124个叶子结点的完全二叉树最多有__________个结点。答案248解析在完全二叉树中叶子结点数n0 n2 1且n1为0或1。总结点数N n0 n1 n2 n0 n1 (n01) 2n0 n11。要使N最大应取n11。因此N_max 2*124 1 - 1 248。94. 有n个顶点的有向强连通图至少含有__________条边。答案n解析有向强连通图要求任意两个顶点之间双向可达。至少需要n条边构成一个环每个顶点出度和入度均为1即可满足强连通条件。95. 在AOV网中如果存在环则说明__________。答案存在循环依赖或工程不可行解析AOV网中边表示活动间的优先关系。如果图中存在环则意味着存在循环依赖例如活动A必须在B之前完成B必须在C之前完成C必须在A之前完成这将导致工程无法顺利进行无法进行拓扑排序。96. 对长度为n的顺序表建立初始堆大顶堆时对序号为__________的结点开始进行向下调整。答案⌊n/2⌋解析完全二叉树中最后一个非叶子结点的序号是⌊n/2⌋。建堆过程是从最后一个非叶子结点开始从后向前依次对每个结点进行向下调整筛选。97. 在哈希查找中平均查找长度与__________无关而与__________有关。答案表中元素个数n、装填因子α和处理冲突的方法解析哈希表的平均查找长度不直接依赖于表中元素个数n而是取决于哈希表的装填因子αα n / 表长、哈希函数的均匀性以及处理冲突的方法。98. 在m阶B树中插入一个关键字若插入后结点关键字个数超过__________则需要进行结点分裂。答案m-1解析m阶B树中每个结点最多包含m-1个关键字。插入新关键字后如果某个结点的关键字数等于m则超过了上限需要将该结点分裂成两个结点并将中间关键字上移到父结点。99. 外部排序的两个主要阶段是__________和__________。答案生成初始归并段或置换选择排序、多路归并解析外部排序因数据量太大无法全部装入内存需要借助外存。第一阶段利用内存和内部排序方法生成若干个有序的初始归并段第二阶段将这些归并段进行多路归并最终得到一个完整的有序文件。100. 算法分析中O(1)表示__________时间复杂度。答案常数解析大O记号表示算法的渐近时间复杂度。O(1)表示算法的执行时间是一个常数不随问题规模n的增长而增长这是效率最高的时间复杂度。参考来源数据结构与算法期末考试题及详细答案.docx-原创力文档算法与数据结构2025年考试试题及答案.docx - 人人文库数据结构期末考试题及答案含详细解析.docx-原创力文档数据结构与算法分析—期末复习题及答案_人人文库网算法与数据结构期末考试题及详细答案.docx-原创力文档