2026年专升本《数据结构》试题及答案

2026年专升本《数据结构》试题及答案一、单项选择题（每题2分，共30分）1.若某算法的时间复杂度为T(n)=3n²+2nlog₂n+5，则其渐进时间复杂度为A.O(n)  B.O(nlogn)  C.O(n²)  D.O(n³)2.已知带头结点的单链表L，头指针为head，判断L为空的条件是A.head==NULL  B.head->next==NULL  C.head->next==head  D.head!=NULL3.将递归算法转换为非递归时，通常借助的数据结构是A.队列  B.栈  C.树  D.图4.一棵完全二叉树共有767个结点，其叶子结点数为A.383  B.384  C.385  D.3865.对n个元素进行快速排序，最坏情况下需要的辅助空间为A.O(1)B.O(logn)  C.O(n)  D.O(n²)6.若用邻接矩阵存储有向图G，则判断顶点i到j是否存在边的时间复杂度为A.O(1)B.O(n)  C.O(e)  D.O(n²)7.下列排序算法中，平均时间复杂度为O(nlogn)且稳定的是A.堆排序  B.归并排序  C.快速排序  D.希尔排序8.已知循环队列存储在数组A[0..m-1]中，队头指针front指向队首元素，队尾指针rear指向队尾元素的下一个位置，则队列长度为A.(rear-front+m)%m  B.rear-front  C.(front-rear+m)%m  D.(rear-front+1)%m9.对长度为n的顺序表进行折半查找，查找失败时最多比较次数为A.⌊log₂n⌋  B.⌈log₂(n+1)⌉  C.⌊log₂(n+1)⌋  D.⌈log₂n⌉+110.若一棵二叉树的中序序列为DBEAFC，后序序列为DEBFCA，则其先序序列为A.ABDECF  B.ABCDEF  C.ABDCEF  D.ADBCEF11.对稀疏矩阵进行压缩存储的主要目的是A.提高访问速度  B.节省存储空间  C.便于矩阵运算  D.降低算法复杂度12.在AOE网中，关键路径是指A.从源点到汇点的最短路径  B.从源点到汇点的最长路径  C.回路中最短的路径  D.回路中最长的路径13.对n个关键字建立二叉排序树，若输入序列已经有序，则树高为A.n  B.⌈log₂(n+1)⌉  C.⌊log₂n⌋  D.n/214.下列关于B树的叙述正确的是A.所有叶子在同一层  B.叶子结点包含关键字  C.非叶子结点不含关键字  D.插入必导致树高增加15.对图进行广度优先搜索时，通常使用的辅助数据结构是A.栈  B.队列  C.堆  D.树二、填空题（每空3分，共30分）16.若顺序表长度为n，删除第i个元素(1≤i≤n)需移动________个元素。17.已知一棵度为4的树，其中度为1、2、3、4的结点个数分别为4、3、2、1，则该树的叶子结点数为________。18.对长度为12的有序表进行折半查找，判定树的高度为________。19.用邻接表存储无向图G，若G有n个顶点e条边，则所需表头结点和表结点总数为________。20.若循环队列Q采用数组实现，容量为MAX，当前rear=8，front=3，则队列中元素个数为________。21.快速排序的一次划分过程中，若基准元素最终位于第k个位置，则其左区间元素个数为________。22.对二叉树进行________遍历，可得到结点的降序序列（假设二叉排序树）。23.在堆排序的初始建堆阶段，对n个元素，最坏情况下需进行________次关键字比较。24.若哈希表长m=13，哈希函数H(key)=key%13，采用线性探测法解决冲突，则关键字25的首次探测地址为________。25.对n个顶点、e条边的有向图进行拓扑排序，若采用邻接表存储，算法时间复杂度为________。三、解答题（共40分）26.（10分）已知关键字序列{12,5,9,20,6,15,18}，请：(1)构造一棵二叉排序树，画出最终树形；(2)给出在等概率情况下成功查找的平均查找长度ASL。27.（10分）对关键字序列{35,28,15,42,12,30,45}进行堆排序：(1)建立初始大根堆，画出初始堆的树形与顺序存储；(2)写出第一次交换并筛选后的序列状态。28.（10分）带权无向图G的边集如下：(A,B,3),(A,C,2),(B,C,1),(B,D,4),(C,D,5),(C,E,6),(D,E,7)。(1)用Prim算法从顶点A出发构造最小生成树，给出依次加入的边；(2)计算最小生成树的权值和。29.（10分）设哈希表长m=11，哈希函数H(k)=k%11，采用链地址法处理冲突。依次插入关键字{18,25,47,36,22,19,40}：(1)画出最终的链地址哈希表；(2)计算装载因子α；(3)求等概率下成功查找的平均查找长度ASL。四、算法设计题（共30分）30.（15分）已知带头结点的单链表L，结点结构为(data,next)。设计算法voidreverse_print(LinkListL)，要求逆序输出链表所有元素，且算法空间复杂度必须为O(1)，时间复杂度O(n)，不得改变原链表结构。31.（15分）设二叉树采用二叉链表存储，结点结构为(lchild,data,rchild)。设计算法intis_balanced(BiTreeT)，判断二叉树T是否为平衡二叉树（AVL树），若是返回1，否则返回0。要求算法时间复杂度O(n)，空间复杂度O(h)，h为树高。五、综合应用题（共30分）32.（15分）某系统需管理海量整数，支持以下操作：Ⅰ.插入一个整数x；Ⅱ.删除一个整数x（保证x存在）；Ⅲ.查询当前所有整数的中位数。请设计一种数据结构，使三种操作的单次均摊时间复杂度均不超过O(logn)，要求：(1)说明所选数据结构及核心思想；(2)给出插入、删除、查询中位数的伪代码；(3)分析各操作的时间复杂度。33.（15分）图G有n个顶点，边权均为正整数。现需找出一条从源点s到汇点t的路径，使得该路径上最大边权与最小边权之差最小。(1)形式化描述问题；(2)设计算法并给出伪代码；(3)分析算法时间复杂度与正确性。——————————答案与解析——————————一、选择题1.C 2.B 3.B 4.B 5.C 6.A 7.B 8.A 9.B 10.A 11.B 12.B 13.A 14.A 15.B二、填空题16.n−i17.1018.419.n+2e20.521.k−122.右子树-根-左子树（RDL）23.2n−224.1225.O(n+e)三、解答题26.(1)二叉排序树：12/\520\/\91518\6(2)成功查找长度：查找路径长度分别为1,2,3,2,3,3,3，ASL=(1+2+3+2+3+3+3)/7=17/7≈2.43。27.(1)初始大根堆（顺序存储）：[42,35,45,28,12,15,30](2)第一次交换42与30，筛选后：[35,30,15,28,12,42,45]28.(1)Prim依次加入边：(A,C,2),(B,C,1),(A,B,3),(B,D,4)(2)权值和=2+1+3+4=1029.(1)链地址表：0:→1:→47→362:→3:→25→194:→18→405:→226–10:→(2)α=7/11≈0.636(3)ASL=(1+1+1+2+1+2+2)/7=10/7≈1.43四、算法设计题30.```cvoidreverse_print(LinkListL){LinkListp=L->next,q,r;if(!p)return;//就地逆置指针方向（仅逆置指针，不交换数据）q=NULL;while(p){r=p->next;p->next=q;q=p;p=r;}//q为新头p=q;while(p){printf("%d",p->data);p=p->next;}//恢复链表q=NULL;while(p){r=p->next;p->next=q;q=p;p=r;}}```空间O(1)，时间O(n)。31.```cintis_balanced(BiTreeT){returnheight_and_check(T)!=-2;}intheight_and_check(BiTreeT){if(!T)return0;intlh=height_and_check(T->lchild);if(lh==-2)return-2;intrh=height_and_check(T->rchild);if(rh==-2)return-2;if(abs(lh-rh)>1)return-2;returnmax(lh,rh)+1;}```返回-2表示不平衡，否则返回树高。五、综合应用题32.(1)采用双堆法：大根堆L存较小一半，小根堆R存较大一半，保持|L|−|R|∈{0,1}。(2)伪代码：插入x：若x≤L.top()或L为空：L.push(x);否则R.push(x);平衡：若|L|>|R|+1:R.push(L.pop());若|R|>|L|:L.push(R.pop());删除x：若x≤L.top()：从L中删除x（借助哈希表定位+堆删除）；否则从R删除；重新平衡同上；查询中位数：若|L|>|R|：returnL.top();elsereturn(L.top()+R.top())/2;(3)各操作均摊O(logn)。33