2026年数据结构自考试题及答案

2026年数据结构自考试题及答案一、单项选择题（每小题1分，共20分）1.若线性表采用顺序存储结构，删除第i个元素（1≤i≤n）需要移动的元素个数为A.n-i  B.n-i+1  C.i  D.i-1答案：A2.带头结点的单链表L为空的判定条件是A.L==NULL  B.L->next==NULL  C.L->next==L  D.L!=NULL答案：B3.栈和队列的共同点是A.只允许在端点处插入和删除  B.都是先进后出C.都是先进先出  D.没有共同点答案：A4.循环队列存储在数组A[0..m-1]中，队头指针front指向队首元素，队尾指针rear指向队尾元素的下一个位置，则当前队列长度是A.(rear-front+m)%m  B.rear-front  C.(rear-front+1)%m  D.rear-front+1答案：A5.一棵完全二叉树有1001个结点，其中叶子结点的个数为A.500  B.501  C.250  D.251答案：B6.对n个记录进行简单选择排序，其关键字比较次数为A.O(n)  B.O(nlogn)  C.O(n²)  D.O(logn)答案：C7.若图的邻接矩阵为对称矩阵，则该图一定A.是有向图  B.是无向图  C.是强连通图  D.是欧拉图答案：B8.对二叉排序树进行中序遍历得到的序列是A.升序  B.降序  C.无序  D.无法确定答案：A9.哈希表采用链地址法处理冲突，若哈希地址为i的单链表长度为k，则查找任一元素的最坏时间复杂度为A.O(1)B.O(k)  C.O(n)  D.O(logk)答案：B10.下列排序算法中，平均时间复杂度为O(nlogn)且稳定的是A.快速排序  B.堆排序  C.归并排序  D.希尔排序答案：C11.对稀疏矩阵进行压缩存储的目的是A.便于进行矩阵运算  B.降低运算时间C.节省存储空间  D.便于输入输出答案：C12.一棵高度为h的AVL树，其最少结点数S(h)的递推关系为A.S(h)=S(h-1)+S(h-2)+1  B.S(h)=2S(h-1)C.S(h)=S(h-1)+1  D.S(h)=S(h-1)+S(h-2)答案：A13.对长度为n的顺序表进行折半查找，判定树的高度为A.⌈log₂(n+1)⌉  B.⌊log₂n⌋  C.⌈log₂n⌉  D.⌊log₂(n+1)⌋答案：A14.若一棵二叉树的后序序列和中序序列相同，则该二叉树满足A.只有根结点  B.任意二叉树C.只有左子树  D.只有右子树答案：D15.对n个顶点的无向连通图，其生成树边数为A.n  B.n-1  C.n+1  D.2n答案：B16.下列关于B树和B+树的叙述，正确的是A.B+树支持顺序查找，B树不支持B.B树所有关键字都在叶子结点C.B+树不支持范围查找D.B树叶子结点之间用指针链接答案：A17.快速排序在最坏情况下时间复杂度为A.O(n)  B.O(nlogn)  C.O(n²)  D.O(logn)答案：C18.对n个元素进行堆排序，其辅助空间复杂度为A.O(n)  B.O(1)C.O(logn)  D.O(nlogn)答案：B19.若用邻接表存储有向图，计算顶点v的出度需要A.遍历整个邻接表  B.遍历v的边链表C.遍历所有顶点  D.无法计算答案：B20.下列算法中，不能求无向图最小生成树的是A.Prim  B.Kruskal  C.Dijkstra  D.以上均可答案：C二、多项选择题（每小题2分，共10分；每题至少有两个正确答案，多选少选均不得分）21.下列关于串的叙述正确的有A.串是字符的有限序列  B.串长度指字符个数C.空串与空格串相同  D.串值可以为NULL答案：A、B22.适用于拓扑排序的图必须满足A.有向图  B.无环  C.连通  D.无向图答案：A、B23.下列排序算法中，属于不稳定排序的有A.快速排序  B.堆排序  C.归并排序  D.希尔排序答案：A、B、D24.关于散列查找，正确的有A.装填因子越大冲突概率越高B.链地址法不会产生二次聚集C.线性探测易产生堆积D.散列函数越复杂越好答案：A、B、C25.下列存储结构中，可用于实现队列的有A.循环单链表  B.顺序循环队列  C.链栈  D.双端队列答案：A、B、D三、填空题（每空1分，共15分）26.若一棵二叉树有n个叶子，采用二叉链表存储，则空指针域数量为________。答案：n+127.对长度为20的顺序表进行折半查找，最多比较次数为________。答案：528.已知广义表LS=(a,(b,c),d)，其表尾为________。答案：((b,c),d)29.若用邻接矩阵存储n个顶点的无向图，则矩阵上三角部分（不含对角线）非零元素个数为________。答案：e（边数）30.一棵3阶B树，除根外每个结点最少包含________棵子树。答案：231.对n个元素进行二路归并排序，归并趟数为________。答案：⌈log₂n⌉32.若循环队列数组大小为M，队头指针front，队尾指针rear，则队列满的条件为________。答案：(rear+1)%M==front33.快速排序的partition函数返回的基准最终位置满足其左侧元素均________基准值。答案：小于等于34.对稀疏矩阵采用三元组表存储，若矩阵有t个非零元素，则三元组表行数为________。答案：t+1（含表头行）35.在堆排序中，初始建堆的时间复杂度为________。答案：O(n)36.若二叉树中序序列为DCBA，后序序列为DCBA，则先序序列为________。答案：ABCD37.对n个顶点e条边的有向图采用邻接表存储，拓扑排序算法时间复杂度为________。答案：O(n+e)38.哈希函数H(key)=key%p，p最好取________。答案：质数39.一棵高度为5的满二叉树，结点总数为________。答案：6340.在Prim算法中，每次选择加入生成树的边应满足连接________与________且权值最小。答案：已选顶点集；未选顶点集四、简答题（共25分）41.（封闭型，5分）给出线索二叉树中序线索化的目的，并说明如何区分线索指针与孩子指针。答案：目的：加快中序遍历，避免栈开销。区分：增设标志位ltag、rtag，0表示孩子，1表示线索。42.（开放型，6分）比较顺序表与链表在插入、删除、随机访问三方面的性能差异，并指出各自适用场景。答案：顺序表：插入删除O(n)，随机访问O(1)，适用于频繁查找、静态数据；链表：插入删除O(1)（已知指针），随机访问O(n)，适用于频繁插入删除、动态数据。43.（封闭型，5分）写出AVL树插入新结点后失衡的四种型态，并给出对应的调整方法名称。答案：LL——右单旋；RR——左单旋；LR——左右双旋；RL——右左双旋。44.（开放型，9分）说明Dijkstra算法与Floyd算法在求解最短路径问题时的核心思想、时间复杂度及适用场景差异。答案：Dijkstra：单源、非负权、贪心策略，O(n²)（数组）或O(elogn)（堆），适合稀疏图；Floyd：多源、动态规划、允许负权（无负环），O(n³)，适合稠密图、需全源结果。五、应用题（共30分）45.（计算类，8分）已知关键字序列{25,17,36,9,24,42,18,12}，哈希表长11，H(key)=key%11，采用线性探测处理冲突。（1）依次插入，画出最终哈希表；（2）计算查找成功的平均查找长度ASL。答案：（1）地址：0:421:122:243:364:175:256:187:98:空9:空10:空（2）各关键字比较次数：25:117:136:19:224:242:118:312:2ASL=(1+1+1+2+2+1+3+2)/8=13/8=1.62546.（分析类，7分）对下图无向带权图（n=6，边集{(A,B,2),(A,C,3),(B,C,1),(B,D,1),(C,D,4),(C,E,5),(D,E,3),(D,F,2),(E,F,2)}），从A出发用Prim算法构造最小生成树，写出依次加入的边序列及最终权值和。答案：边序列：(A,B,2)(B,C,1)(B,D,1)(D,F,2)(D,E,3)权值和：2+1+1+2+3=947.（综合类，15分）设计算法将一棵二叉排序树转换为双向循环链表，要求“in-place”且时间复杂度O(n)，给出算法思想、核心伪代码及C语言关键代码片段，并分析复杂度。答案：思想：中序递归，全局指针pre指向当前子树转换后链表尾，root为当前根，递归左子树，将root与pre双向链接，更新pre，递归右子树。伪代码：```pre=NULL;head=NULL;voidconvert(Noderoot){voidconvert(Noderoot){if(!root)return;convert(root->left);if(pre){pre->right=root;root->left=pre;}elsehead=root;pre=root;convert(root->right);}```主函数最后令head->left=pre;pre->right=head;形成循环。C关键代码同上。时间复杂度：每个结点访问一次，O(n)；空间复杂度：递归栈O(h)，h为树高。六、算法设计题（共20分）48.（综合类，20分）给定一个长度为n的整数序列，设计算法找出其中第k小元素（1≤k≤n），要求平均时间复杂度O(n)，最坏O(n²)，空间O(1)。（1）描述算法思想（快速选择）；（2）给出完整C语言实现；（3）证明平均复杂度；（4）说明若需最坏O(n)可采用的算法名称（BFPRT）及核心策略。答案：（1）快速选择：仿快排partition，每次只递归含k的一侧。（2）代码：```cintpartition(inta[],intl,intr){intpivot=a[r],i=l-1;for(intj=l;j<r;j++)if(a[j]<=pivot)swap(&a[++i],&a[j]);swap(&a[i+1],&a[r]);returni+1;}intquickselect(inta[],intl,intr,intk){if(l==r)returna[l];intp=partition(a,l,r);intrank=p-l+1;if(k==rank)returna[p];if(k<rank)returnquickselect(a,l,p-1,k);elsereturnquickselect(a,p+1,r,k-rank);}```（3）平均复杂度：T(n)=T(n/2)+O(n)→O(n)（主定理）。（4）BFPRT：通过median-of-medians策略选取优质基准，保证每次递归规模≤7n/10，最坏O(n)。七、附加综合题（共20分）49.文件系统采用B+树索引，假设每个磁盘块可存4个关键字和5个指针，现对含10⁷条记录的文件建立B+树索引。（1）计算3层B+树最多可索引的记录数；（2）若记录关键字为64位整数，指针6字节，块大小4096字节，验证上述“4关键字5指针”是否可行；（3）若查询某关键字平均需读盘次数；（4）若采用哈希索引，简述其在范围查询上的劣势。答案：（1）根：4关键字→5子；第二层：5结点×5子=25；第三层叶子：25×5=125叶子；每叶子4关键字→4记录；共125×4=500记录。若叶子链指针不计入关键字上限，则叶子可存更多记录：设每叶子存m个关键字，则m×8+(m+1)×6≤4096→m≤244；则三层：根4→5子，第二层5结点每结点244子→1220叶子，每叶子244记录→1220×244=297680记录；若仍不足，需四层。题目给定“4关键字5指针”为内部结点限制，故叶子按4记录计，三层最多5×5×4=100记录，显然需更多层。重新按内部结点“4关键字5指针”计