安徽大学2025-2026-2-A-数据结构试卷.pdf

该【安徽大学2025-2026-2-A-数据结构试卷 】是由【小屁孩】上传分享，文档一共【6】页，该文档可以免费在线阅读，需要了解更多关于【安徽大学2025-2026-2-A-数据结构试卷 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..穷则独善其身,达则兼善天下。——《孟子》安徽大学2020—2021学年第2学期《数据结构》考试试卷(A卷)线--(闭卷时间120分钟)--------考场登记表序号--------题号一二三四五六七总分-----得分--号--阅卷人-学-------得分-一、算法分析题(每小题5分,共20分)-------。订-----voidFunction(intn)-----{inti=1,j;--名线---if(n==1)return;姓------for(i=1;i<=n;i++){订-----for(j=1;j<=n;j++){---装--printf(“*”);-----break;超------}-勿----}---业题--}----专---答---------,回答问题。-------LNode*Function(LinkListL)//L为带头结点的单链表-----{LNode*ptr1,*ptr2;装-级--inti=0;年---ptr1=ptr2=L->next;--while(ptr1->next!=NULL){--if(i==0){--ptr1=ptr1->next;i=1;---}--elseif(i==1){-系-ptr1=ptr1->next;ptr2=ptr2->next;i=0;-/--}院--}--returnptr2;--}---(1)请指出Function(L)算法的功能。-(2)当L={1,3,5,7,9,11,13}时,执行Function(L)后,ptr2->data的值是多少?:..穷则独善其身,达则兼善天下。——《孟子》,回答问题。intFunction(BiTree*root)//root为二叉链表存储的二叉树{BiTNode*temp;intn=0;QueueQ;//队列Qif(!root)return0;InitQueue(Q);//InitQueue(&Q)为队列的初始化操作EnQueue(Q,root);//EnQueue(&Q,e)为队列的入队操作while(!IsEmptyQueue(Q)){//IsEmptyQueue(Q)为队列的判空操作,若Q空则返回真,否则返回假DeQueue(Q,temp);if(!temp->lchild&&temp->rchild||temp->lchild&&!temp->rchild)n++;if(temp->lchild)EnQueue(Q,temp->lchild);if(temp->rchild)EnQueue(Q,temp->rchild);}DestroyQueue(Q);//DestroyQueue(&Q)为队列的销毁操作returnn;}(1)请分析上述Function(root)算法的功能。(2)若root=(A(B(D,E),C(F,G))),则执行Function(root)后,n等于多少?,回答问题。KeyTypeFunction(RecTypeR[],ints,intt,intk){inti=s,j=t;RecTypetmp;if(s<t){tmp=R[s];while(i<j){while(j>i&&R[j].key>=)j--;if(i<j){R[i]=R[j];i++;}while(i<j&&R[i].key<)i++;if(i<j){R[j]=R[i];j--}}R[i]=tmp;if(k-1==i)returnR[i].key;elseif(k-1<i)returnFunction(R,s,i-1,k);elsereturnFunction(R,i+1,t,k);}elseif(s==t&&s==k-1)returnR[k-1].key;elsereturn-1;}(1)请分析上述Function(RecTypeR[],ints,intt,intk)算法的功能。(2)若R[0..9]序列中的关键字为{35,40,38,11,13,34,48,75,6,19},执行Function(R,0,9,4)后,其结果为多少(函数的返回值)?:..勿以恶小而为之,勿以善小而不为。——刘备得分二、计算题(每小题5分,共10分)=((a,b),(c,d)),请计算Tail(Head(Tail(L)))的运算结果。线---------------------[0..7,0..8,0..9]采用按行序优先存储,数组的起始地址是1000,每个元素占----用4个字节,请计算元素a[2,5,6]的起始地址。号---学---------------订------------名线-得分--姓----三、应用题(每小题10分,共40分)--订---,中序遍历序列为ABCDEFGHIJK,-----装--请画出该二叉树。-----超-------勿-------业题------专---答---------------------装-级--年-------(45,62,35,55,60,50,77,58,15,35*,98),请给出每一趟快--速排序结束后关键字序列的状态。-------系-/-院-----------:..天行健,君子以自强不息。地势坤,君子以厚德载物。——《周易》(Key)=Key%7,散列地址空间为0-9,对关键字序列(8,38,20,12,27,23),采用线性探测法处理冲突。构造散列表。试回答下列问题:(1)画出散列表示意图。(2)分别计算等概率情况下,查找成功和查找不成功时的平均查找长度。,如下图所示,试用Prim算法,从顶点1出发,求其最小生成树。1326752343145564得分四、算法设计题(每小题10分,共30分)={A,A,…,A}和List2={B,B,…,B},请设计一个算法12n12m合并它们得到一个新链表,新链表形如:如果n>=m,那么新链表为{A,B,A,B,…,A,B,A,…,A};1122mmm+1n如果n<=m,那么新链表为{A,B,A,B,…,A,B,B,…,B}。1122nnn+1m:..其身正,不令而行;其身不正,虽令不从。——《论语》线-------------------------号---学---------------订-----,其类型定义如下:-----typedefstructBiTNode{--名线---TElemTypedata;姓------structBiTNode*lchild,*rchild;订-----}BiTNode,*BiTree;---装--请设计下列算法,(1)删除一棵二叉树;(2)求二叉树的高度(或深度)。-----超-------勿-------业题------专---答---------------------装-级--年----------------系-/-院-----------:..好学近乎知,力行近乎仁,知耻近乎勇。——《中庸》,并且只设一个指针指向队尾元素结点(注意:不设头指针),其类型定义如下:typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrrear;}LinkQueue;请设计队列的以下算法:(1)初始化操作/*voidInitQueue(LinkQueue&Q)*/(2)入队操作/*voidEnQueue(LinkQueue&Q,QElemTypee)*/(3)出队操作/*voidDeQueue(LinkQueue&Q,QElemType&e)*/