国开电大2025年春季期末考试《数据结构》试题及答案

国开电大2025年春季期末考试《数据结构》试题及答案一、单项选择题（每题2分，共20分）1.若某线性表最常用的操作是存取第i个元素及其前驱，则采用（）存储方式最节省时间。A.单链表  B.双链表  C.顺序表  D.循环单链表答案：C2.一棵完全二叉树共有1234个结点，其中叶子结点的个数为（）。A.615  B.616  C.617  D.618答案：C3.对n个元素进行快速排序，最坏情况下时间复杂度为（）。A.O(n)  B.O(nlogn)  C.O(n²)  D.O(logn)答案：C4.若用邻接矩阵存储有向图，则判断任意两顶点间是否存在边的时间复杂度为（）。A.O(1)  B.O(n)  C.O(e)  D.O(n+e)答案：A5.下列排序算法中，平均情况下空间复杂度最低的是（）。A.归并排序  B.快速排序  C.堆排序  D.希尔排序答案：C6.若栈的输入序列为1,2,3,4,5，则不可能得到的输出序列是（）。A.2,1,3,4,5  B.5,4,3,2,1  C.1,3,2,5,4  D.4,5,1,3,2答案：D7.对长度为m的顺序表进行折半查找，则查找失败时最多比较次数为（）。A.⌊log₂(m+1)⌋  B.⌈log₂(m+1)⌉  C.⌊log₂m⌋+1  D.⌈log₂m⌉+1答案：B8.下列关于B树的叙述，错误的是（）。A.根结点至少有2棵子树B.所有叶子结点都在同一层C.每个非根内部结点至少有⌈m/2⌉棵子树D.插入操作必然导致树高增加答案：D9.对稀疏矩阵进行压缩存储，通常采用（）。A.三元组顺序表  B.十字链表  C.邻接矩阵  D.A和B均可答案：D10.在AOE网中，关键路径是指（）。A.从源点到汇点的最短路径B.从源点到汇点的最长路径C.权值之和最小的路径D.经过顶点数最多的路径答案：B二、填空题（每空2分，共20分）11.若循环队列用数组Q[0…m-1]存储，队头指针front指向队首元素的前一位置，队尾指针rear指向队尾元素，则队列长度为________。答案：(rear−front+m)%m12.已知一棵二叉树的后序序列为DCEFBHGA，中序序列为DCBEFAGH，则其先序序列为________。答案：ABCDEGFH13.对长度为12的有序表进行折半查找，判定树的高度为________。答案：414.若哈希表长为13，哈希函数H(key)=key%13，采用线性探测法处理冲突，则关键字29第3次冲突后的地址为________。答案：015.对序列{48,36,65,97,76,15,29}进行一趟希尔排序（增量为3）后的结果为________。答案：29,36,15,48,76,65,9716.若用孩子兄弟表示法存储森林，则森林中任意一棵树的根结点没有________。答案：右兄弟17.对n个顶点e条边的无向图采用邻接表存储，则求全部顶点度数的算法时间复杂度为________。答案：O(n+e)18.在快速排序的划分过程中，若待划分区间长度为k，则经过一次划分后，左区间长度可能为0到________。答案：k−119.对平衡二叉树插入新结点后，发生RL型失衡，则需做的调整是________。答案：先右旋后左旋20.若广义表LS=((a,b),c,(d,(e)))，则其深度为________。答案：3三、判断题（每题1分，共10分，正确打“√”，错误打“×”）21.顺序表支持随机存取，链表不支持随机存取。答案：√22.哈夫曼树中任意非叶子结点的权值等于其左右子树根结点权值之和。答案：√23.拓扑排序结果唯一时，对应有向图必定是无环图。答案：√24.堆排序是一种稳定的排序算法。答案：×25.对连通图进行广度优先搜索，必能访问到所有顶点。答案：√26.在循环链表中，头指针为NULL表示链表为空。答案：×27.对任意二叉树，若其先序序列与后序序列相反，则该二叉树高度等于结点数。答案：√28.采用邻接矩阵存储图时，求顶点vi的入度需遍历第i列。答案：√29.折半查找适用于有序的双向链表。答案：×30.在AOE网中，缩短任一关键活动均可缩短整个工期。答案：×四、简答题（每题6分，共30分）31.给定稀疏矩阵A如下（行列下标从1开始），写出其三元组顺序表，并说明采用十字链表存储时结点结构。0005002000000074000000900答案：三元组顺序表（行，列，值）：(1,4,5),(2,2,2),(3,5,7),(4,1,4),(5,3,9)十字链表结点结构：structOLNode{introw,col;ElemTypevalue;OLNoderight,down;};32.简述循环队列牺牲一个单元区分队空与队满的原理，并给出队空、队满条件。答案：设数组容量为m，头指针front指向队首元素前一位置，尾指针rear指向队尾元素。牺牲Q[front]单元，使队列最多存放m−1个元素。队空：front==rear队满：(rear+1)%m==front33.对关键字序列{12,23,34,45,56,67,78,89}构造一棵3阶B树，依次插入12到89，画出最终树形，并说明插入56时是否发生分裂。答案：3阶B树每个结点最多2个关键字，最少⌈3/2⌉−1=1个关键字。依次插入：12├─1223├─122334├─122334→分裂根：23├─12 ├─3445├─12 ├─344556├─12 ├─344556→分裂根：2345├─12 ├─34 ├─5667├─12 ├─34 ├─566778├─12 ├─34 ├─566778→分裂根：234567├─12 ├─34 ├─56 ├─7889├─12 ├─34 ├─5689 ├─78最终树高为2。插入56时，结点“344556”超限，发生分裂。34.说明Dijkstra算法求最短路径时为何不能处理负权边，并举反例。答案：Dijkstra按路径长度递增顺序确定最短路径，一旦顶点被标记“已确定”，其最短距离不再更新。若存在负权边，后续可能出现更短路径，导致错误。反例：顶点集{V0,V1,V2}，边<V0,V1>权3，<V0,V2>权4，<V1,V2>权−2。Dijkstra先确定V0→V1为3，标记V1已确定，不再更新，得到V0→V2为4，实际最短为V0→V1→V2=1。35.给出将二叉搜索树转为有序双向链表的递归算法思想，并说明时间复杂度。答案：采用中序遍历，递归将左子树转为双向链表，返回链表头尾指针；将当前根结点与左链表尾、右链表头链接；递归处理右子树。算法保持指针：prev记录中序前驱，head记录链表头。时间复杂度：访问每个结点一次，O(n)，辅助栈空间O(h)，h为树高。五、算法设计题（每题10分，共30分）36.编写算法，判断带头结点的单链表是否为回文链表，要求O(n)时间、O(1)辅助空间。答案：步骤：1.快慢指针找中间结点；2.反转后半段；3.前后半段逐一比较；4.恢复链表（可选）。代码（C语言）：```cboolisPalindrome(LinkListL){if(!L->next||!L->next->next)returntrue;LNodeslow=L->next,fast=L->next;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}LNodeprev=NULL,cur=slow,tmp;while(cur){tmp=cur->next;cur->next=prev;prev=cur;cur=tmp;}LNodep=L->next,q=prev;boolans=true;while(q){if(p->data!=q->data)ans=false;p=p->next;q=q->next;}//恢复cur=prev;prev=NULL;while(cur){tmp=cur->next;cur->next=prev;prev=cur;cur=tmp;}returnans;}```37.设计算法，求无向图G中距离顶点v的最短路径长度为k的所有顶点，图采用邻接表存储。答案：采用广度优先搜索，记录层号。```cvoidBFS_K(GraphG,intv,intk){intvisited[MAXV]={0};intlevel[MAXV];SqQueueQ;InitQueue(Q);visited[v]=1;level[v]=0;EnQueue(Q,v);while(!QueueEmpty(Q)){intu;DeQueue(Q,u);if(level[u]==k){printf("%d",u);continue;}ArcNodep=G.vertices[u].firstarc;while(p){intw=p->adjvex;if(!visited[w]){visited[w]=1;level[w]=level[u]+1;EnQueue(Q,w);}p=p->nextarc;}}}```时间复杂度O(n+e)，空间O(n)。38.实现一个最小堆支持的优先级队列，包含初始化、入队、出队、查看队首操作，并给出堆调整细节。答案：```cdefineMAXSIZE1000typedefstruct{intheap[MAXSIZE+1];intsize;}MinHeap;voidinit(MinHeap&H){H.size=0;}voidsiftUp(MinHeap&H,inti){while(i>1&&H.heap[i]<H.heap[i/2]){swap(H.heap[i],H.heap[i/2]);i/=2;}}voidsiftDown(MinHeap&H,inti){intflag=0;while(i2<=H.size&&flag==0){intt=i2;if(t+1<=H.size&&H.heap[t+1]<H.heap[t])t++;if(H.heap[i]>H.heap[t]){swap(H.heap[i],H.heap[t]);i=t;}elseflag=1;}}boolenqueue(MinHeap&H,intx){if(H.size==MAXSIZE)returnfalse;H.heap[++H.size]=x;siftUp(H,H.size);returntrue