数据结构大题目

1一、算法阅读题1．如图所示，利用同一循环向量空间实现两个队列，其类型Queue2定义如下：typedefstruct{DataTypedata[MaxSize];intfront[2],length[2];};Queue2对于i=0或1,front[i]和length[i]分别为第i个队列的头指针和长度域。请在空缺处填入合适的内容，实现第i个循环队列的入队操作。intEnQueue(Queue2*Q,inti,DataTypex){//若第i个队列不满，则元素x入队列，并返回1，否则返回0if(i0||i1)return0;if((1))return0;Q-data[(2)]=x;Q-length[(3)]++return1;}2．阅读下列函数algo,并回答问题。（1）假设整型数组A[1..8]中的元素依次为(3，8，9，1，7，4，2，6)。执行函数调用algo(A,8)时，外层while的循环体执行多少次?函数的返回值是多少?（2）简述函数algo(L,n)的功能。intalgo(intL[],intn){inti=0,j,s=1,t=n;while(i!=(n+1)/2){intx=L[s]；i=s;j=t;while(ij){while(ij&&L[j]=x)j--;L[i]=L[j];while(ij&&L[i]=x)i++;L[j]=L[i];}2L[i]=x;if(i(n+1)/2)s=i+1;elset=i-1;}if(i==0)return0;elsereturnL[i];}3．在下面冒泡排序算法中（1）～（4）处填入适当内容，以使该算法在发现有序时能及时停止。bubble（RectypeR［］，intn）{inti，j，exchang；Rectypetemp；i=1；do{exchang=false；for（j=n；j（1）；j--）if（R［j］R［j-1］）{temp=R［j-1］；R［j-1］=R［j］；R［j］=temp；exchang=（2）；}（3）；}while（exchang=（4））；}4．下列函数是在无向图的邻接表中删除一条边的算法，请在（1）～（4）处填入适当内容加以完善。Voiddeledge（ALGraph*G，inti，intj）{EdgeNode*p，*q；3p=G→adjlist［i］.firstedge；if（p→adjvex==j）{G→adjlist［i］.firstedge=p→next；free（p）；}else{while（p→next→adjvex!=j&&p→next）____（1）；if（p→next!=NULL）{q=p→next；___（2）___；free（q）；}}p=G→adjlist［j］.firstedge；if（p→adjvex==i）{G→adlist［j］.firstedge=p→next；free（q）；}else{while（p→next→adjvex!=i&&p→next）__（3）；if（p→next!=NULL）{q=p→next；（4）；free（q）；}}}5．阅读下列函数algo,并回答问题：（1）假设队列q中的元素为(2,4,5,7,8),其中“2”为队头元素。写出执行函数调用algo(&q)后的队列q；（2）简述算法algo的功能。voidalgo(Queue*Q){StackS;InitStack(&S);while(!QueueEmpty(Q))Push(&S,;DeQueue(Q));while(!StackEmpty(&S))ＥnQueue(Q,Pop(&S));}6．阅读下列函数F，并回答问题：4（1）已知如图所示的二叉树以二叉链表作存储结构，rt为指向根结点的指针。写出执行函数调用F(rt)的输出结果。（2）说明函数F的功能。voidF(BinTreeT){StackS;if(T){InitStack(&S);Push(&S,NULL);while(T){printf(%c,T-data);if(T-rchild)Push(&S,T-rchild);if(T-lchild)T=T-lchild;elseT=Pop(&S);}}}7.以下函数中h是带头结点的双向循环链表的头指针（1）说明程序的功能；（2）当链表中结点数分另为1和6（不包括头结点时），请写出程序中while循环体的次数。intf(DlistNode*h){DlistNode*p,*q;intj=1;p=h-next;q=h-piror;while(p!=q&&p-piror!=q)if(p-data==q-data){p=p-next;q=q-prior;}elsej=0;returnj;}8.（1）该算法采用何种策略排序？（2）算法中的R[n+1]的作用是什么？typedefstruct{KeyTypekey;infoTypeotherinfor;}nodeType;TypedefnodeTypeSqlist[MAXLEN];5voidSort(SqlistR,intn){//n小于MAXLEN-1intk,i;for(k=n-1;k=1;k--)if(R[k].keyR[k+1].key){R[n+1]=R[k];For(i=k+1;R[i].keyR[k+1].key;i++)R[i-1]=R[i];R[i-1]=R[n-1];}}9.设栈S=(1,2,3,4,5,6,7)其中7为栈顶元素。请写出调用algo(&S)后栈S的状态voidalgo(Stack*S){inti=0;QueueQ;StackT;InitQueue(&Q);InitStack(&T);While(!StackEmpty(S)){if((i=!i)!=0)Push(&T,Pop(&S));elseEnQueue(&Q,Pop(&S));}while(!QueueEmpty(Q))Push(&S,DeQueue(&Q));While(!StackEmpty(T))Push(&S,Pop(&T));}10.阅读下面的算法LinkListmynote(LinkListL){//L是不带头结点的单链表的头指针if(L&&Lnext){q=L；L=L－next；p=L；S1：while(p－next)p=p－next；S2：p－next=q；q－next=NULL；}returnL；}请回答下列问题：（1）说明语句S1的功能；（2）说明语句组S2的功能；6（3）设链表表示的线性表为（a1,a2,…,an）,写出算法执行后的返回值所表示的线性表。11.已知图的邻接表表示的形式说明如下：#defineMaxNum50//图的最大顶点数typedefstructnode{intadjvex;//邻接点域structnode*next;//链指针域}EdgeNode;//边表结点结构描述typedefstruct{charvertex;//顶点域EdgeNode*firstedge;//边表头指针}VertexNode;//顶点表结点结构描述typedefstruct{VertexNodeadjlist［MaxNum］;//邻接表intn,e;//图中当前的顶点数和边数}ALGraph;//邻接表结构描述下列算法输出图G的深度优先生成树(或森林)的边。阅读算法，并在空缺处填入合适的内容，使其成为一个完整的算法。typedefenum{FALSE,TRUE}Boolean;Booleanvisited［MaxNum］;voidDFSForest(ALGraph*G){inti;for(i=0;iG-n;i++)visited［i］=(1);for(i=0;iG-n;i++)if(!visited［i］)DFSTree(G,i);}voidDFSTree(ALGraph*G,inti){EdgeNode*p;visited［i］=TRUE;p=G-adjlist［i］.firstedge;while(p!=NULL){if(!visited［p-adjvex］){printf(″%c,%c″,G-adjlist［i］.vertex,G-adjlist［p-adjvex］.vertex);(2);}(3);}}12．阅读下列算法，并回答问题：(1)假设数组L［8］={3,0,5,1,6,4,2,7}，写出执行函数调用f32(L，8)后的L；(2)写出上述函数调用过程中进行元素交换操作的总次数。voidf32(intR［］,intn){7inti,t;for(i=0;in-1;i++)while(R［i］!=i){t=R［R［i］］;R［R［i］］=R［i］;R［i］=t;}}13.以下函数中，h是带头结点的双向循环链表的头指针。(1)说明程序的功能；(2)当链表中结点数分别为1和6(不包括头结点)时，请写出程序中while循环体的执行次数。intf(DListNode*h){DListNode*p,*q;intj=1;p=h-next;q=h-prior;while(p!=q&&p-prior!=q)if(p-data==q-data){p=p-next;q=q-prior;}elsej=0;returnj;}14.（1）设数组L[1..8]的初值为（4，-3，7，-1，-2，2，5，-8），写出执行函数调用f30(L,8)之后的L[1..8]中的元素值；（2）简述函数f33的功能。voidf30(intR[],intn){intx=R[1];intlow=1,high=n;while(lowhigh){while(lowhigh&&R[high]=0)high--;if(lowhigh){R[low++]=R[high];while(lowhigh&&R[low]0)low++;R[high--]=R[low];8}}R[low]=x;}15.下列算法的功能是比较两个链串的大小，其返回值为：comstr(s1,s2)=请在空白处填入适当的内容。intcomstr(LinkStrings1,LinkStrings2){//s1和s2为两个链串的头指针while(s1&&s2){if(s1-dates2-date)return-1；if(s1-dates2-date)return1；（1）；（2）；}if(（3）)return-1；if(（4）)return1；（5）；}二、算法设计题1．假设以带头结点的单链表表示有序表，单链表的类型定义如下：typedefstructnode{DataTypedata;structnode*next}LinkNode,*LinkList;编写算法，从有序表A中删除所有和有序表B中元素相同的结点。2．假设以带头结点的单循环链表作非递减有序线性表的存储结构。请设计一个时间复杂度为O(n)的算法，删除表中所有数值相同的多余元素，并释放结点空间。例如：(7，10，10，21，30，42，42，42，51，70)经算法操作后变为(7，10，21，30，42，51，70)3．设线性表A=(a1,a2,a3,…,an)以带头结点的单链表作为存储结构。编写一个函数，对A进行调整，使得当n为奇数时A=(a2,a4,…,an-1,a1,a3,…,an)，当n为偶数时A=(a2,a4,…,an,a1,a3,…,an-1)。94.设有一个3×4的矩阵如下所示，设计一个子函数，实现矩阵的转置。12341595678转置后矩阵2610910111237114812主函数如下：（写出其中的子函数trans()）main(){inta[][4]={1,2,3,4,5,6,7,8,9,10,11,12};inti,j,b[4][3];for(i=0;i3;i++){for(j=0;j4;j++)printf(“%d”,a[i][j]);p