《数据结构》期末考试试题及答案

《数据结构》期末考试试题及答案一、选择题（共15题，每题2分，共30分）设某算法的时间复杂度函数为T(n)=2T(n/2)+n，采用主定理计算其渐进时间复杂度为（）

A.O(解析：主定理的核心是将递归式与nlogba比较，本题中a=2，b=2，f带头节点的单链表L为空的判定条件是（）A.L==NULL

B.L−>ne解析：带头节点的单链表中，头节点本身不存储有效数据，空表的判定标准是头节点的后继指针为空；选项A是不带头节点的单链表空表判定条件，选项C是循环单链表的空表判定条件。若进栈序列为a,b,c,d，进栈过程中允许出栈，则以下不可能出现的出栈序列是（）A.d,c,b,aB.b,c,d,aC.c,a,d,bD.a,b,c,d答案：C解析：栈遵循后进先出的规则，若c先出栈，说明此时a、b均已入栈且位于栈中，后续出栈顺序必然是b早于a，因此c,a,d,b的序列不可能出现。循环队列用数组A[0..m−1]存储元素，设队头指针front指向队头元素的前一个位置，队尾指针rear指向队尾元素的实际位置，当前队列元素个数为（）

A.(rear−f解析：该约定下，队列元素个数的计算需要考虑指针回绕的情况，加m后取模可以避免rear<front时出现负数，因此正确计算公式为(r已知串$S="datastructure"$，其所有子串的个数是（）

A.13B.91C.92D.182答案：C解析：长度为n的串，非空子串的个数为n(n+一棵有1025个节点的二叉树，其高度的最小值为（）A.10B.11C.12D.9答案：B解析：完全二叉树的高度最小，高度为h的完全二叉树最多有2h−1某二叉树的先序遍历序列为ABDECF，中序遍历序列为DBEAFC，则后序遍历序列为（）A.DEBFCAB.DBEFCAC.DEABCFD.DFEBCA答案：A解析：先序遍历的第一个节点为根节点A，结合中序遍历可知左子树包含节点D、B、E，右子树包含节点F、C；左子树先序序列为BDE，根为B，中序为DBE，可知D为B的左孩子、E为B的右孩子；右子树先序为CF，根为C，中序为FC，可知F为C的左孩子，因此后序遍历序列为DEBFCA。有5个权值{3,2,4,5,1}，构造的哈夫曼树的带权路径长度为（）A.32B.33C.34D.35答案：B解析：哈夫曼树构造过程为：先合并权值1和2得到权值3，合并两个权值3得到6，合并4和5得到9，合并6和9得到根节点15；带权路径长度WPL为所有叶子节点的权值乘以其到根节点的路径长度之和，即1*对于一个具有n个顶点e条边的无向图，采用邻接表存储时，所有顶点的边表节点总数为（）A.nB.eC.2eD.n+e答案：C解析：无向图的每条边会在两个关联顶点的边表中各存储一次，因此所有边表节点的总数为2e。以下关于深度优先遍历（DFS）和广度优先遍历（BFS）的说法错误的是（）A.DFS适合查找路径类问题，BFS适合查找无权图最短路径类问题B.两种遍历方式都需要使用辅助队列存储已访问节点C.对于连通图，两种遍历都能访问到所有顶点D.两种遍历的时间复杂度与存储结构有关，邻接表存储时为O(n+e解析：DFS使用栈（递归栈或手动栈）存储遍历路径，BFS使用队列存储待访问节点，因此选项B错误。以下排序算法中，不稳定的是（）A.冒泡排序B.直接插入排序C.快速排序D.归并排序答案：C解析：稳定排序的定义是关键字相同的元素排序后相对位置不变，快速排序的分区过程会交换跨基准的元素，可能打乱相同关键字的相对位置，因此是不稳定排序。以下排序算法中，最坏情况下时间复杂度为O(nlogn)的是（B.冒泡排序C.堆排序D.直接选择排序答案：C解析：快速排序最坏情况下时间复杂度为O(n2)，冒泡排序、直接选择排序的最坏时间复杂度均为长度为16的有序表（下标从1开始），采用折半查找，查找第5个元素的比较序列下标为（）A.8,4,6,5B.16,8,5C.8,6,4,5D.16,4,6,5答案：A解析：初始查找区间low=1、high=16，第一次mid=(1+16)/2=8，8>5，调整high=7；第二次mid=(1+7)/2=4，4<5，调整low=5；第三次mid=(5+7)/2=6，6>5，调整high=5；第四次mid=5，查找成功，因此比较序列为8,4,6,5。散列函数为H(key)B.6C.7D.8答案：C解析：各关键字的散列值计算如下：15%7=1，23%7=2，36%7=1（冲突，探测位置3），48%7=6，59%7=3（冲突，探测位置4），62%7=6（冲突，探测位置7），因此62的存储位置为7。以下关于二叉排序树的说法正确的是（）A.二叉排序树的中序遍历序列是有序的B.构造二叉排序树的时间复杂度总是O(nlogD.平衡二叉树的左右子树的高度差的绝对值不超过2答案：A解析：二叉排序树的定义决定了其中序遍历序列必然为升序序列；选项B错误，若输入序列本身有序，构造的二叉排序树为单支树，时间复杂度为O(n2)；选项C错误，单支二叉排序树的查找时间复杂度为二、填空题（共10题，每题2分，共20分）算法的五个基本特性分别是有穷性、确定性、可行性、______、输出。答案：输入解析：算法可以有0个或多个输入，但必须有至少1个输出，输入是算法处理的数据源。长度为n的顺序表，在第i个位置（1≤i≤n+1）插入一个元素，需要移动______个元素。答案：n−i+1链栈的栈顶指针为top，执行入栈操作时，新节点s的next指针应指向______，再将top指向s。答案：top解析：入栈操作需要将新节点接在原栈顶的上方，因此新节点的后继指针指向原栈顶节点，再更新栈顶指针为新节点。广义表A=(a解析：广义表的深度为最内层括号的嵌套层数，元素d的外层嵌套了3层括号，因此广义表的深度为3。高度为h的满二叉树，其叶子节点的个数为______。答案：2h−1

解析：满二叉树的第k层节点数为2具有n个顶点的无向完全图，其边的总数为______。答案：n(n−1对于一个AOE网，关键路径是从源点到汇点的______的路径。答案：长度最长解析：关键路径决定了整个工程的最短完成时间，是AOE网中路径长度（权值和）最大的路径。对长度为n的序列进行冒泡排序，最坏情况下需要进行______趟排序。答案：n−1折半查找的前提条件是查找表必须采用顺序存储结构，且______。答案：元素按关键字有序排列解析：折半查找依赖有序性每次将查找区间缩小一半，因此要求查找表必须是有序的顺序存储结构。在堆排序的过程中，构建初始堆的时间复杂度为______。答案：O(n)

三、判断题（共10题，每题1分，共10分）数据的逻辑结构与数据的存储结构是一一对应的。答案：×解析：一种逻辑结构可以对应多种存储结构，例如线性表既可以用顺序存储（数组）实现，也可以用链式存储（链表）实现。栈和队列都是限制存取位置的线性表。答案：√解析：栈仅允许在栈顶进行插入、删除操作，队列仅允许在队尾插入、队头删除，均属于存取位置受限的线性结构。KMP算法的优势在于当模式串存在大量重复前缀时，能够减少主串指针的回溯次数。答案：×解析：KMP算法的核心是主串指针完全不回溯，仅调整模式串的匹配位置，适合处理流式输入的主串。完全二叉树一定不存在度为1的节点。答案：×解析：节点总数为偶数的完全二叉树可以存在1个度为1的节点，即最后一个叶子节点的父节点仅存在左孩子。哈夫曼树中不存在度为1的节点。答案：√解析：哈夫曼树构造过程中每次合并两个节点生成父节点，因此所有非叶子节点的度均为2，不存在度为1的节点。有向图的邻接矩阵中，第i行非零元素的个数等于第i个顶点的入度。答案：×解析：有向图邻接矩阵第i行非零元素的个数为第i个顶点的出度，第i列非零元素的个数为入度。无向图的邻接矩阵一定是对称矩阵。答案：√解析：无向图中若顶点i和j之间存在边，则邻接矩阵中A[归并排序的空间复杂度为O(1)解析：归并排序需要额外的辅助数组存储归并后的结果，空间复杂度为O(折半查找的查找效率只和查找表的长度有关，和关键字的分布无关。答案：×解析：折半查找的比较次数与待查找元素的位置相关，若查找的元素多集中在前半区间，平均查找长度会明显小于理论平均值。散列查找的平均查找长度基本不随表长的增加而增加，这是散列查找最大的优势。答案：√解析：散列查找通过散列函数直接定位存储位置，理想情况下时间复杂度为O(四、简答题（共4题，每题5分，共20分）请分别说明顺序存储结构和链式存储结构的优缺点，以及各自的适用场景。答案：顺序存储结构的优点：①支持随机访问，可通过下标在O(1)时间内访问任意位置的元素；②存储密度高，无需存储额外的指针信息，所有空间均用于存储数据；③实现简单，编程语言普遍提供数组原生支持。缺点：①插入、删除操作效率低，平均需要移动一半元素，时间复杂度为O(n)；②需要预先分配连续的内存空间，分配过大易造成空间浪费，分配过小易出现溢出；③扩容成本高，存储空间不足时需要重新分配更大的连续空间并迁移全部数据。

链式存储结构的优点：①插入、删除操作效率高，找到目标位置后仅需修改指针即可，无需移动元素，时间复杂度为O(1)；②无需预先分配内存，可根据需求动态申请、释放节点，内存利用率高，不存在溢出问题；③扩容方便，新增节点无需迁移原有数据。缺点：①请简述快速排序的基本思想，以及其时间复杂度和空间复杂度的情况，说明快速排序不稳定的原因。答案：快速排序的基本思想是分治：在待排序序列中选择一个基准元素，通过一趟分区操作将序列划分为两部分，左侧所有元素小于等于基准，右侧所有元素大于等于基准，此时基准元素处于最终排序位置；之后递归对左右两个子序列执行快速排序，直到子序列长度为0或1，整个序列完成排序。时间复杂度：最好情况下，每次基准都将序列划分为长度接近的两个子序列，时间复杂度为O(nlogn)；最坏情况下，每次基准为序列的最大/最小值，子序列长度为0和n-1，时间复杂度退化为O(n2)，通常出现在序列基本有序的场景；平均时间复杂度为O(nlogn)，是所有O(nlogn)请简述图的最小生成树的概念，以及Prim算法和Kruskal算法的基本思想和适用场景。答案：最小生成树的概念：带权连通无向图的所有生成树中，边的权值之和最小的生成树称为最小生成树（MST），包含图的所有n个顶点，且仅有n-1条边，不存在环。Prim算法的基本思想：从任意一个顶点出发，初始化最小生成树的顶点集合为该顶点，每次选择顶点集合内顶点到集合外顶点的权值最小的边，将边和外部顶点加入生成树，重复操作直到所有顶点都被加入集合。Prim算法邻接矩阵存储的时间复杂度为O(n2)，邻接表结合优先队列优化的时间复杂度为O(elog请简述平衡二叉树（AVL树）的概念，以及插入节点后调整平衡的四种旋转情况。答案：平衡二叉树是特殊的二叉排序树，定义为树中每个节点的左右子树高度差的绝对值不超过1，且左右子树均为平衡二叉树，节点的平衡因子为左子树高度减右子树高度，平衡二叉树的平衡因子只能是-1、0、1。插入节点后若节点平衡因子绝对值大于1，需要进行旋转调整，共四种情况：①LL型（左左）：新节点位于失衡节点的左子树的左子树，执行一次右旋转，将失衡节点的左孩子提升为根，失衡节点作为其右子树，左孩子原有的右子树作为失衡节点的左子树；②RR型（右右）：新节点位于失衡节点的右子树的右子树，执行一次左旋转，将失衡节点的右孩子提升为根，失衡节点作为其左子树，右孩子原有的左子树作为失衡节点的右子树；③LR型（左右）：新节点位于失衡节点的左子树的右子树，先对失衡节点的左子树执行左旋转转为LL型，再对失衡节点执行右旋转；④RL型（右左）：新节点位于失衡节点的右子树的左子树，先对失衡节点的右子树执行右旋转转为RR型，再对失衡节点执行左旋转。五、论述题（共1题，20分）请结合数据结构中常见的查找算法（顺序查找、折半查找、二叉排序树查找、散列查找），分别分析其基本原理、时间复杂度、优缺点和适用场景，并针对以下两个场景给出最合适的查找算法选择并说明理由：场景1：某电商平台的订单查询系统，订单总量为1亿条，订单编号按生成顺序递增存储，用户查询时通常输入完整的订单编号进行精确查询，要求查询响应时间不超过10ms，订单数据不会频繁修改，仅每天凌晨批量新增前一天的订单数据。场景2：某社交平台的用户昵称查重系统，用户注册时输入昵称后需要实时判断该昵称是否已经存在，用户总量为5000万，每天新增用户10万，昵称长度为2-16个字符，支持用户随时修改昵称，要求查重响应时间不超过50ms。答案：一、四种查找算法特性分析顺序查找：基本原理为从查找表的第一个元素开始，依次与待查找关键字比较，找到相等元素则查找成功，遍历完成未找到则失败。时间复杂度最好为O(1)，最坏为O折半查找：基本原理为要求查找表为顺序存储且关键字有序，每次取查找区间的中间元素与待查找关键字比较，相等则成功，大于关键字则在左半区间继续查找，小于则在右半区间继续查找，直到找到目标或区间为空。时间复杂度最好为O(1)二叉排序树查找：基本原理为二叉排序树的左子树所有节点关键字小于根，右子树所有节点关键字大于根，查找时从根节点开始比较