数据结构习题(有答案)

第1章绪1.1有下列几种二元组表示的数据结构，试画出它们分别对应的图形表示，并指出它们分别属于何种结构。(1)A=(D，R)，其中，D={a1，a2，a3，a4}，R={}(2)B=(D，R)，其中，D={a，b，c，d，e}，R={(a，b)，(b，c)，(c，d)，(d，e)}(3)C=(D，R)，其中，D={a，b，c，d，e，f，g}，R={(d，b)，(d，g)，(b，a)，(b，c)，(g，e)，(e，f)}(4)K=(D，R)，其中，D={1，2，3，4，5，6}，R={1，2，2，3，2，4，3，4，3，5，3，6，4，5，4，6}(1)集合(2)线性表abcde(3)树fgabcde(4)图1453621.2设n为正整数，求下列各程序段中的下划线语句的执行次数。(1)i=1;k=0while(i=n-1){k+=10*i;i++;}(2)for(inti=1;i=n;i++)for(intj=1;j=n;j++){c[i][j]=0;for(intk=1;k=n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j]}解：(1)n-1(2)ninjnkn11131(3)x=0;y=0;for(inti=1;i=n;i++)for(intj=1;j=i;j++)for(intk=1;k=j;k++)x=x+y;(3)62)1)(nn(n21)(216)12)(1(2121212)1(1112111111nnnnniiiijnininiijjkniijni1.3指出下列个算法的功能，并求其时间复杂度。(1)intsum1(intn){intp=1,s=0;for(inti=1;i=n;i++){p*=i;s+=p;}returns;}(2)intsum2(intn){ints=0;for(inti=1;i=n;i++){intp=1;for(intj=1;j=i;j++)p*=j;s+=p;}returns;}解：(1)n1ii!,T(n)=O(n)(2)n1ii!,T(n)=O(n2)1.4算法设计有3枚硬币，其中有1枚是假的，伪币与真币重量略有不同。如何借用一架天平，找出伪币？以流程图表示算法。上机练习题要求：给出问题分析、算法描述、源程序及运行截图，在线提交。1.设a,b,c为3个整数，求其中位于中间值的整数。开始A=B？A=C？A是伪币C是伪币B是伪币结束是是否否第2章线性表1.设计算法：在顺序表中删除值为e的元素，删除成功，返回1；否则，返回0。intSqlistT::DeleteElem(Te){for(i=1;i=length;i++)//按值顺序查找*i可从0开始if(elem[i-1]==e)//找到，进行删除操作{for(j=i;jlength;j++)//ai至an依次前移Elem[j-1]=elem[j];length--;//表长减一return1;//删除成功，返回1}return0;//未找到，删除不成功，返回0}2.分析顺序表中元素定位算法intSqListT::Locate(Te)的时间复杂度。解：设表长为n，等概率下，每个元素被定位的概率为：p=1/n定位成功第i个元素，需比较i次212)1(111)(11nnnnininnfnini3.对于有头结点的单链表，分别写出定位成功时，实现下列定位语句序列。(1)定位到第i个结点ai；p=head;j=0;while(p&&ji){p=p-next;j++;}(2)定位到第i个结点的前驱ai-1；p=head;j=0;while(p&&ji-1){p=p-next;j++;}(3)定位到尾结点；p=head;while(p-next)p=p-next;(4)定位到尾结点的前驱。p=head;while(p-next-next)p=p-next;4.描述一下三个概念的区别：头指针，头结点，首元结点。并给予图示。头指针：是一个指针变量，里面存储的是链表中首结点的地址，并以此来标识一个链表。头结点：附加在第一个元素结点之前的一个结点，头指针指向头结点。首元结点：指链表中的第一个元素结点。头结点a1a2…...an^a1a2…...an^首(元)结点尾(元)结点头指针5.对于无头结点单链表，给出删除第i个结点的算法描述。templatecalssTTLinkListT::Delete(inti)templatecalssTTLinkListT::Delete(inti){//在单链表上删除第i个数据元素if(head==NULL)throw“表空!”;//空表，不能删elseif(i==1){//删除第1个元素p=Head;x=p-data;//保存被删元素值Head=p-next;deletep;}else{//元素定位到第ai-1p=Head;j=1;//定位查找起始位置while{p-next&&ji-1}{p=p-next;j++;}if(!p-next||ji-1);//定位失败throw“删除位置不合理”;else{//定位成功，进行结点删除q=p-next;x=pdata;p-next=q-next;deleteq;}retrunx;//返回被删除元素值}//#6.用教材定义的顺序表的基本操作实现下列操作：templatecalssTintDeleteElem(SqListL,Te)#include“SqList.h“templatecalssTintDeleteElem(SqListL,Te){//i=L.LocateElem(e);//按值查找if(!i)//未找到return0;else//找到delete(i);//删除被找到的元素}7.已知L是有表头结点的单链表，且P结点既不是首元结点，也不是尾结点，试写出实现下列功能的语句序列。(1)在P结点后插入S结点；(2)在P结点前插入S结点；(3)在表首插入S结点；(4)在表尾插入S结点.【解】(1)s-next=p-next;p-next=s;(2)q=L;while(q-next!=p)q=q-next;s-next=p或q-next;q-next=s;(3)s-next=L-next;L-next=s;(3)q=L;while(q-next!=NULL)q=q-next;s-next=q-next;q-next=s;上机练习题要求：给出问题分析、算法描述、源程序及运行截图，在线提交。编程实现：删除单链表中值为e的元素。第3章栈与队列1.铁路进行列车调度时,常把站台设计成栈式结构的站台，如右图所示。试问：若进站的六辆列车顺序如上所述,那么是否能够得到325641和154623的出站序列,如果不能,说明为什么不能;如果能,说明如何得到(即写出进栈或出栈的序列)。解：325641可以154623不可以。1234562.简述以下算法的功能（栈的元素类型为int）。(1)statusalgo_1(SqStackS){inti,n,A[255];n=0;while(!S.StackEmpty()){n++;A[n]=S.Pop();}for(i=1;i=n;i++)S.Push(A[i]);}(2)statusalgo_2(SqStackS,inte){SqStackT;intd;while(!S.tackEmpty()){d=S.Pop();if(d!=e)T.Push(d);}while(!T.StackEmpty()){d=T.Pop();T.Push(d);}}解：(1)借助一个数组，将栈中的元素逆置。(2)借助栈T，将栈S中所有值为e的数据元素删除之。3.编写一个算法，将一个非负的十进制整数N转换为B进制数，并输出转换后的结果。当N=248D，B分别为8和16时，转换后的结果为多少？#include“stack.h”intNumTrans(intN,intB){//十进制整数N转换为B进制数stackintS;//建立一个栈while(N!=0){//N非零i=N%B;//从低到高，依次求得各位N=N/B;S.push(i);}//各位入栈while(!S.StackEmpty()){//栈不空{i=S.pop();If(i9)i=’A’+10-i;coutS.pop();}//依次出栈，得到从高到低的输出结果}}//#4借且栈，设计算法：假设一个算术表达式中包含“(”、“)”括号，对一个合法的数学表达式来说，括号“(”和“)”应是相互匹配的。若匹配，返回1；否则，返回0。解：以字符串存储表达式，也可以边输入边判断。顺序扫描表达式，左括号，入栈；右括号，如果此时栈空，表示多右括号，不匹配；如果栈不空，出栈一个左括号。扫描结束，如果栈空，表示括号匹配；否则，括号不匹配，多左括号。intblank_match(char*exp){用字符串存表达式SqStackchars;//创建一个栈char*p=exp;//工作指针p指向表达式首while(*p!=’=’){//不是表达式结束符switch(p){case’(’://左括号，入栈s.push(ch);break;case’)’//右括号if(s.StackEmpty())return0;//栈空，不匹配，多右括号else{s.Pop();break;}//左括号出栈}//switchp++;//取表达式下一个字符}//whileif(!s.StackEmpty())//表达式结束，栈不空return0;//不匹配，多左括号elsereturn1;//匹配}//#5.简述栈和队列的逻辑特点，各举一个应用实例。6.写出下列中缀表达式的后缀表达式。(1)-A+B-C+D(2)(A+B)*D+E/(F+A*D)+C(3)A&&B||!(EF)(1)A-B+C-D+(2)AB+D*EFAD*+/+C+(3)AB&&EF!||7.计算后缀表达式：45*32+-的值。解：158.将下列递推过程改写为递归过程。voidrecursion(intn){inti=n;while(i1){couti;i--;}}解：voidrecurision(intj){if(j1){courj;recurision(j-1);}}9..将下列递归过程改写为非递归过程。voidtest(int&sum){intx;cinx;if(x==0)sum=0;else{test(sum);sum+=x;}coutsum;}解：voidtest(int&sum){stackS;//借助一个栈intx;cinx;while(x){S.push(x);cinx;}sum=0;coutsum;while(x=S.pop()){sum+=x;coutsum;}}//10.简述以下算法的功能（栈和队列的元素类型均为int）。解：利用栈，将队列中的元素逆置voidalgo(Queue&Q){StackS;//创建一个栈intd;while(!Q.QueueEmpty()){d=DeQueue(Q);S.Push(d);}while(!S.StackEmpty()){d=S.Pop();Q.EnQueue(d);}}12.假设以数组se[m]存放循环队列的元素，同时设变量rear和front分别作为队首、队尾指针，且队首指针指向队首前一个位置，队尾指针指向队尾元素处，初始时，rear==fornt==-1。写出这样设计的循环队列入队、出队的算法。解：采用教材队空与队满判别方法。为了区分队空与队满条件，牺牲一个元素空间。即：rear==front，为队空；rear==(front+1)%m，为队满。templatecalssTvo