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

2025年10月自考02323数据结构真题一、单项选择题（本大题共15小题，每小题2分，共30分。在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分）1.若线性表采用顺序存储结构，删除第i个元素（1≤i≤n）需要移动的元素个数为（）。A.n-iB.iC.n-i+1D.n-i-12.已知一棵完全二叉树共有765个结点，则其叶子结点数为（）。A.382B.383C.384D.3853.对n个元素进行快速排序，最坏情况下时间复杂度为（）。A.O(n)B.O(nlogn)C.O(n²)D.O(logn)4.若图的邻接矩阵为对称矩阵，则该图一定是（）。A.有向图B.无向图C.强连通图D.弱连通图5.在带头结点的单链表L中，判断表空的条件是（）。A.L==NULLB.L->next==NULLC.L->next==LD.L!=NULL6.对长度为m的顺序表进行二分查找，则查找失败时最多比较次数为（）。A.⌊B.⌊C.⌈D.⌈7.已知循环队列存储在一维数组A[0…m-1]中，队头指针front指向队头元素的前一个位置，队尾指针rear指向队尾元素，则当前队列长度为（）。A.(rear-front+m)%mB.(rear-front+m+1)%mC.rear-frontD.rear-front+18.对关键字序列{12,2,16,30,8,28,4,10}进行一趟希尔排序（增量d=4），排序后结果为（）。A.{12,2,16,30,8,28,4,10}B.{8,2,4,10,12,28,16,30}C.{8,2,16,10,12,28,4,30}D.{12,2,4,10,8,28,16,30}9.若一棵二叉树的中序序列为DBEAFC，后序序列为DEBFCA，则其先序序列为（）。A.ABDECFB.ABCDEFC.ABDCEFD.ADBCEF10.对n个关键字建立二叉排序树，若输入序列为降序排列，则生成的二叉排序树形态为（）。A.完全二叉树B.平衡二叉树C.单支树D.满二叉树11.下列排序算法中，不稳定的是（）。A.冒泡排序B.归并排序C.堆排序D.基数排序12.若用邻接表存储有向图G，则计算顶点v的入度时间复杂度为（）。A.O(1)B.O(n)C.O(e)D.O(n+e)13.对长度为n的线性表，采用链式存储结构，则按值查找操作的时间复杂度为（）。A.O(1)B.O(n)C.O(logn)D.O(n²)14.已知广义表LS=(a,(b,c),((d)))，则其表尾为（）。A.(b,c),((d))B.((b,c),((d)))C.(b,c)D.(c),((d))15.对初始大顶堆执行一次删除堆顶元素操作后，需进行筛选调整，其时间复杂度为（）。A.O(1)B.O(logn)C.O(n)D.O(nlogn)二、填空题（本大题共10小题，每小题2分，共20分。请在每小题的空格中填上正确答案，错填、不填均无分）16.若顺序表采用动态分配，则插入元素时需判断______，若不足则重新分配更大空间。17.一棵深度为k的满二叉树，其结点总数为______。18.对稀疏矩阵进行压缩存储，常用的三元组顺序表需存储______、列标、元素值三个字段。19.在快速排序中，若每次划分均产生长度为1与n-1的子序列，则递归深度为______。20.对n个顶点e条边的无向图，采用邻接矩阵存储，则矩阵中非零元素个数为______。21.若循环链表L中p指向最后一个结点，则判断表空的条件可写为______。22.对关键字序列{5,3,8,2,9}构造初始小顶堆，堆化后根结点值为______。23.对长度为n的顺序表进行逆置算法，所需辅助空间为______。24.若哈夫曼树中共有m个叶子结点，则总结点数为______。25.在并查集路径压缩优化后，查找操作均摊时间复杂度接近______。三、解答题（本大题共4小题，每小题8分，共32分）26.已知一棵二叉树采用二叉链表存储，结点结构为{lchild,data,rchild}。设计算法intCountSingle(BiTreeT)，统计二叉树中度为1的结点个数，要求给出递归模型并写出完整C语言函数。27.对关键字序列{27,13,55,10,8,32,70,25}，按增量序列{4,2,1}进行希尔排序，写出每一趟排序后的序列，并计算总移动次数（一次元素赋值计一次移动）。28.带权无向图G的边集如下：(A,B,3),(A,C,2),(B,C,1),(B,D,4),(C,D,5),(C,E,6),(D,E,7)。从顶点A出发，使用Prim算法构造最小生成树，按生长顺序写出依次加入的边，并计算最小生成树权值。29.设哈希表长m=13，哈希函数H(key)=key%13，采用链地址法处理冲突。给定关键字{19,14,23,1,68,20,84,27}，画出最终哈希表，并计算成功查找的平均查找长度ASL。四、算法设计题（本大题共2小题，每小题9分，共18分）30.已知单链表L带头结点且结点数据域为int型，设计算法voidSplit(LinkListL,LinkList&A,LinkList&B)，将L拆分为A与B两个链表，使得A中仅保留值为奇数的结点，B中仅保留值为偶数的结点，要求保持原相对次序，且不能申请新结点空间，仅通过修改指针完成。31.设图G采用邻接表存储，设计算法intHasCycleDFS(ALGraphG)，判断无向图G中是否存在环，若存在返回1，否则返回0。要求给出visited数组与父结点标记策略，并写出完整DFS函数。五、综合应用题（本大题共1小题，共10分）32.某系统需管理海量日志记录，每条日志包含时间戳（long型）与内容串（char[128]）。现要求实现一种数据结构，支持以下操作：32.某系统需管理海量日志记录，每条日志包含时间戳（long型）与内容串（char[128]）。现要求实现一种数据结构，支持以下操作：(1)按时间戳升序插入日志；(2)删除最早日志；(3)查询时间戳位于区间[t1,t2]内的日志条数。请完成以下任务：①选择并说明所采用的数据结构（需兼顾插入、删除、区间查询效率）；②给出数据结构的C语言定义；③写出插入、删除、区间查询三个核心算法的伪代码，并分析时间复杂度；④若日志条数上限为1亿条，估算所需内存空间（假设指针8字节，long8字节，内容串平均占用64字节，忽略对齐浪费）。【答案与解析】一、选择题1.A2.B3.C4.B5.B6.B7.B8.B9.A10.C11.C12.C13.B14.B15.B解析：2.完全二叉树叶子数=⌈n6.二分查找失败最多比较次数=⌊l8.增量4分组{12,8},{2,28},{16,4},{30,10}，组内排序得{8,12},{2,28},{4,16},{10,30}，序列变为{8,2,4,10,12,28,16,30}。9.后序最后为根A，中序分左右，递归可得先序ABDECF。二、填空题16.存储空间是否已满17.−18.行标19.n20.2e21.p->next==L22.223.O(1)24.2m-125.O(α(n))（反阿克曼函数）三、解答题26.递归模型：若T为空，返回0；若(T->lchild!=NULL)+(T->rchild!=NULL)==1，返回1+左+右；否则返回左+右。C函数：intCountSingle(BiTreeT){if(!T)return0;intl=CountSingle(T->lchild);intr=CountSingle(T->rchild);if((T->lchild!=NULL)+(T->rchild!=NULL)==1)return1+l+r;elsereturnl+r;}27.初：271355108327025d=4：分组后组内排序→81341027327025，移动6次d=2：分组排序→81041327322570，移动8次d=1：直接插入→48101325273270，移动10次总移动24次。28.Prim序：(A,C,2),(C,B,1),(B,D,4),(A,B,3)已含，下条(C,E,6)，总权2+1+4+6=13。29.链地址表：0:1:1→14→272:3:4:5:6:197:208:9:2310:6811:8412:ASL=(1+2+3+1+1+1+2+1)/8=12/8=1.5四、算法设计题30.思路：遍历L，奇数尾插A，偶数尾插B，原L头结点作A头，申请新头给B。voidSplit(LinkListL,LinkList&A,LinkList&B){A=L;B=(LNode)malloc(sizeof(LNode));B->next=NULL;A=L;B=(LNode)malloc(sizeof(LNode));B->next=NULL;LNodep=A->next,ra=A,rb=B;LNodep=A->next,ra=A,rb=B;while(p){if(p->data&1){ra->next=p;ra=p;}else{rb->next=p;rb=p;}p=p->next;}ra->next=NULL;rb->next=NULL;}31.无向图环检测：DFS中若遇到已访问且非父结点则存在环。intHasCycleDFS(ALGraphG){intvisited[MAXV]={0};for(inti=0;i<G.n;i++)if(!visited[i]&&dfs(G,i,-1,visited))return1;return0;}intdfs(ALGraphG,intv,intparent,intvisited[]){visited[v]=1;for(ArcNodep=G.vertices[v].firstarc;p;p=p->next){for(ArcNodep=G.vertices[v].firstarc;p;p=p->next){intw=p->adjvex;if(!visited[w]){if(dfs(G,w,v,visited))return1;}elseif(w!=parent)return1;}return0;}五、综合应用题32.①采用“隐式树状数组+平衡二叉搜索树”方案：以时间戳为key，维护一棵Treap/Splay，支持插入、删除最小、区间计数。②C定义：typedefstructLogNode{longts;charcontent[128];structLogNodel,r;struct