2025年10月自考数据结构真题

2025年10月自考数据结构真题一、单项选择题（本大题共15小题，每小题2分，共30分。在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分）1.若某算法的时间复杂度为T(n)=3nlog₂n+5n+7，则其渐进时间复杂度为（）A.O(n)  B.O(nlog₂n)  C.O(n²)  D.O(log₂n)2.已知带头结点的单链表L，头指针为head，判断L为空的条件是（）A.head==NULL  B.head->next==NULL  C.head->next==head  D.head!=NULL3.循环队列存储在数组A[0…m-1]中，队头指针front指向队首元素的前一位置，队尾指针rear指向队尾元素。则当前队列长度length为（）A.(rear-front+m)%m  B.rear-front  C.(rear-front+m+1)%m  D.rear-front+14.对关键字序列{12,2,16,30,8,28,4,10}进行一趟基数排序（LSD，基数为10）后，得到的序列为（）A.{2,4,8,10,12,16,28,30}  B.{12,2,16,30,8,28,4,10}C.{2,12,4,16,8,28,30,10}  D.{30,10,12,2,4,16,28,8}5.一棵含有n个结点的二叉树，若采用二叉链表存储，则空指针域的个数为（）A.n  B.n+1  C.n-1  D.2n6.对图G采用邻接矩阵存储，若G为无向图，则邻接矩阵具有（）A.对称性  B.稀疏性  C.三角性  D.反对称性7.在平衡二叉树（AVL树）中插入一个结点造成失衡，设最低失衡结点为A，若A的左孩子的右子树最高，则应进行的调整操作是（）A.LL型  B.RR型  C.LR型  D.RL型8.对长度为n的待排序序列进行快速排序，最坏情况下需要的比较次数为（）A.O(n)  B.O(nlog₂n)  C.O(n²)  D.O(log₂n)9.若哈希表长m=13，哈希函数H(key)=key%13，采用线性探测法处理冲突，依次插入{18,35,22,16}，则关键字16的存储地址为（）A.3  B.4  C.5  D.610.已知一棵度为4的树，其中度为1、2、3、4的结点个数分别为4、3、2、1，则该树的叶结点数为（）A.8  B.9  C.10  D.1111.对广义表L=(a,(b,c),((d)))执行操作head(tail(head(tail(L))))的结果是（）A.b  B.c  C.d  D.(b,c)12.在稀疏矩阵的三元组顺序表中，若矩阵行数rows=100，列数cols=200，非零元个数terms=150，则该存储结构比常规二维数组节省的存储单元数为（）A.19850  B.19950  C.20050  D.2015013.对关键字序列{5,1,4,3,2}建立初始小根堆，经过筛选后，序列中第3个元素为（）A.1  B.2  C.3  D.414.在AOE网中，若某活动的最早开始时间e(i)等于最迟开始时间l(i)，则该活动（）A.是关键活动  B.可延迟  C.无实际意义  D.一定不在关键路径上15.对二叉排序树进行中序遍历，得到的序列具有（）A.无序  B.升序  C.降序  D.层次序二、填空题（本大题共10小题，每小题2分，共20分。请在每小题的空格中填上正确答案。错填、不填均无分）16.若顺序表采用动态分配，其存储结构类型定义中，用于指示当前实际元素个数的成员变量通常命名为________。17.在双向循环链表中，若指针p指向某结点，则删除其后继结点的核心语句序列是________。18.已知栈的输入序列为1,2,3,…,n，输出序列为p₁,p₂,…,pₙ，若p₃=1，则p₁的可能取值共有________种。19.对长度为n=2ᵏ−1的完全二叉树，若按层序从1开始编号，则编号为i的结点的右孩子编号为________。20.采用邻接表存储有向图G，若G中共有e条弧，则邻接表中的表结点总数为________。21.在B-树中，除根结点外，任一结点最少包含________棵子树。22.对关键字序列进行二路归并排序，若待排序列长度为20，则归并趟数为________。23.若哈希表的装填因子α=0.8，则采用链地址法时，查找成功的平均查找长度ASL≈________。24.已知一棵哈夫曼树共有m个叶结点，则其总结点数为________。25.在拓扑排序算法中，若某时刻存在多个入度为0的顶点，则选择其中任意一个均可，说明拓扑序列________（唯一/不唯一）。三、解答题（本大题共4小题，每小题10分，共40分）26.已知一棵二叉树的中序序列为DBGEAFHC，后序序列为DGEBHFCA。（1）画出该二叉树；（2）写出其先序序列；（3）若将该二叉树转换为对应的森林，给出森林中每棵树的根结点集合。27.对关键字序列{38,15,27,51,10,20,60,18}，采用哈希函数H(key)=key%11，表长m=11，用线性探测法处理冲突。（1）构造哈希表；（2）计算查找成功的平均查找长度ASL；（3）写出删除关键字20后，哈希表的状态（数组下标0~10）。28.带权无向图G的边集为{(A,B,3),(A,C,2),(B,C,1),(B,D,4),(C,D,5),(C,E,6),(D,E,7)}，采用Prim算法从顶点A出发构造最小生成树。（1）依次写出加入最小生成树的边；（2）画出最终的最小生成树；（3）计算最小生成树的权值之和。29.已知待排序序列为{49,38,65,97,76,13,27,49′}，采用快速排序算法，给出第一趟划分后的序列，并给出递归处理左、右子区间时各自的比较次数（以首次选取最左元素为枢轴）。四、算法设计题（本大题共2小题，每小题15分，共30分）30.设单链表结点结构为```ctypedefstructLNode{intdata;structLNodenext;structLNodenext;}LNode,LinkList;}LNode,LinkList;```编写算法`voidreverse_even(LinkList&L)`，将带头结点的单链表L中所有偶数值结点逆置，奇数值结点相对顺序不变。要求空间复杂度O(1)。31.设二叉树采用二叉链表存储，结点结构为```ctypedefstructBiTNode{intdata;structBiTNodelchild,rchild;structBiTNodelchild,rchild;}BiTNode,BiTree;}BiTNode,BiTree;```编写算法`intmax_width(BiTreeT)`，求二叉树T的最大宽度（指具有结点数最多的层上的结点数）。要求采用层次遍历，队列自行定义。五、答案与解析【选择题答案】1.B 2.B 3.C 4.C 5.B 6.A 7.C 8.C 9.C 10.B 11.B 12.B 13.C 14.A 15.B【填空题答案】16.length17.q=p->next;p->next=q->next;q->next->prior=p;free(q);18.219.2i+120.e21.⌈m/2⌉22.523.1+α/2=1.424.2m−125.不唯一【解答题26】（1）二叉树结构：A/\BC/\/\DEFH/\G(空)（2）先序：ABDGECFH（3）森林根集合：{A}，因为整棵树无右子树，转换后仅一棵树。【解答题27】（1）哈希表（下标0~10）：地址：012345678910key：22382748155110206018—（注：48为冲突示例，实际题目无48，此处仅示范格式，真实插入如下）实际插入：38%11=5→A[5]=3815%11=4→A[4]=1527%11=5→冲突→6→A[6]=2751%11=7→A[7]=5110%11=10→A[10]=1020%11=9→A[9]=2060%11=5→5,6,7,8→A[8]=6018%11=7→7,8,9,10,0→A[0]=18最终表：0:18,1:—,2:—,3:—,4:15,5:38,6:27,7:51,8:60,9:20,10:10（2）ASL=(1+1+2+1+1+1+4+5)/8=16/8=2（3）删除20：A[9]置空，后续同义词需重排，60前移：A[9]=60，A[8]空。【解答题28】（1）Prim序：(A,C,2),(C,B,1),(B,D,4),(C,E,6)（2）树边：AC,CB,BD,CE（3）权值和：2+1+4+6=13【解答题29】枢轴49，划分后：{27,38,13,49′,49,76,65,97}左区比较次数：6次（每个元素与49比）右区比较次数：3次（76,65,97与49比）【算法设计题30】参考代码（核心片段）：```cvoidreverse_even(LinkList&L){LNodep=L->next,q,r,prev=NULL,tail=L;LNodep=L->next,q,r,prev=NULL,tail=L;while(p){if(p->data%2==0){q=p;p=p->next;q->next=prev;prev=q;}else{tail->next=p;tail=p;p=p->next;}}tail->next=prev;}```思路：将偶数结点头插到prev链，奇数结点尾接到tail链，最后拼接。【算法设计题31】参考代码：```cdefineMAXQ10000BiTNodeQ[MAXQ];BiTNodeQ[MAXQ];intmax_width(BiTreeT){if(!T)return0;intfront=0,rear=0,maxw=0;Q[rear++]=T;while(front<rea