1. 您所在位置：首页 > 给排水规范 > 设计规范 > 《数据结构(含上机实训)》课后题答案.doc

《数据结构(含上机实训)》课后题答案.doc 35页

  • 254.00 KB
  • 2022-04-22 11:31:59 发布

《数据结构(含上机实训)》课后题答案.doc

  • 35页
  • 当前文档由用户上传发布，收益归属用户
  1. 1、本文档共5页，可阅读全部内容。
  2. 2、本文档内容版权归属内容提供方，所产生的收益全部归内容提供方所有。如果您对本文有版权争议，可选择认领，认领后既往收益都归您。
  3. 3、本文档由用户上传，本站不保证质量和数量令人满意，可能有诸多瑕疵，付费之前，请仔细先通过免费阅读内容等途径辨别内容交易风险。如存在严重挂羊头卖狗肉之情形，可联系本站下载客服投诉处理。
  4. 文档侵权举报电话：19940600175。
'课后习题答案第1章数据结构导论一、填空题1．集合结构，线性结构，树形结构，图状结构2．顺序存储结构，链式存储结构3．有限性，确定性，可行性，输入，输出4．时间复杂度，空间复杂度二、分析下面程序段的时间复杂度。1．O(m*n)2．O(n2)三、上机操作题1．解答：#includevoidmain(){floata[10];inti,n;floats=0;printf("输入数组中元素的个数n：");scanf("%d",&n);for(i=0;ivoidmain(){intx,y,z,t;printf("请依次输入x、y和z的值：n");scanf("%d%d%d",&x,&y,&z);if(xnext;//p为链表中第二个结点r=*list;while(p!=NULL){if(p->data>q->data){q=p;//保存当前最大值结点s=r;//保存当前最大值结点的前驱}r=p;//保存p所指结点位置p=p->next;//p指向下一结点}if(q==*list)//链表中第一个结点为最大值结点*list=(*list)->next;//删除第一个结点else//最大值结点不是链表的第一个结点s->next=q->next;//删除q所指结点free(q);//释放q所指结点的空间}33 课后习题答案3．解答：voidDeleteItem(DLinkList*list,ElemTypeitem){DNode*q;q=(*list)->next;//q指向头结点的后继while(q!=*list){if(q->data==item)//q所指结点的值为item{q->prior->next=q->next;//删除q所指结点q->next->prior=q->prior;free(q);//释放q所指结点的空间}q=q->next;//q指向下一结点}}4．解答：voidInsertItem(DLinkListq,ElemTypeitem){DLinkListp;p=(DLinkList)malloc(sizeof(DNode));//生成新结点p->data=item;//新结点的数据域赋值p->prior=q;//将新结点插入到q所指结点之后p->next=q->next;//修改p所指结点的指针域q->next=p;//修改q所指结点的后继p->next->prior=p;//修改p的后继结点的前驱}第3章栈和队列一、填空题1．线性2．栈顶，队尾，队头3．后进先出，先进先出4．数组，指示栈顶元素的位置5．将栈顶指针后移一个位置，将被插入元素放在修改后的栈顶指针所指出的位置6．链式33 课后习题答案二、选择题1．C2．D3．C4．C5．B6．A7．B8．D9．C10．D三、上机操作题1．解答：表3-1算术表达式求值的过程步骤OPTR栈OPND栈当前读入字符步骤OPTR栈OPND栈当前读入字符1#358#－/355022#35－9#－/35502＋3#－35510#－3525＋4#－355*11#10＋5#－*3551012#＋1056#－*35510/13#＋105#7#－3550/14#15#2．解答：charop[7]={"+","-","*","/","(",")","#"};//算符数组charcmp[7][7]={{">",">","<","<","<",">",">"},{">",">","<","<","<",">",">"},{">",">",">",">","<",">",">"},{">",">",">",">","<",">",">"},{"<","<","<","<","<","=",""},{">",">",">",">","",">",">"},{"<","<","<","<","<","","="}};//算符优先关系数组//输入字符是否属于运算符集合，如果是，返回它在数组中的位置；否则，返回-1intIsoperator(charch){inti;for(i=0;i<7;i++){if(ch==op[i])returni;33 课后习题答案}return-1;}//比较两个运算符的优先级charCompare(charch1,charch2){intm,n;m=Isoperator(ch1);n=Isoperator(ch2);returncmp[m][n];}//将中缀表达式转换为后缀表达式intTransExpression(char*str1,char*str2){inti=0,k=0;charx,theta;SeqStackOPTR//定义运算符栈IniStack(&OPTR);//初始化运算符栈Push(&OPTR,"#");//将"#"压入栈底while(str1[i]!="#"||GetTop(OPTR)!="#"){if(str1[i]>="0"&&str1[i]<="9")//如果读入字符为数则复制到str2中str2[k++]=str1[i++];else{if(Isoperator(str1[i])==-1)//如果读入字符不是操作符，则出错returnERROR;switch(Compare(GetTop(OPTR),str[i]))//比较操作符优先级高低{case"<"://读入字符优先级高于栈顶字符优先级Push(&OPTR,str[i]);//操作符进栈i++;break;case"="://读入字符优先级等于栈顶字符优先级Pop(&OPTR,x);//栈顶元素出栈i++;break;case">"://读入字符优先级低于栈顶字符优先级Pop(&OPTR,&theta);//栈顶元素出栈33 课后习题答案str2[k++]=theta;//出栈元素复制到str2中break;}}}returnOK;}3．解答：intIsHuiwen(char*S){SeqStackT;inti,len;chart;InitStack(&T);len=StrLength(S);//求字符串长度for(i=0;i0&&n==0)returnACK(m-1,1);if(m<>0&&n<>0)returnACK(m-1,ACK(m,n-1));}6．解答：知道了尾指针和元素个数，当然就能知道队头元素了。算法如下：//判队满,队中元素个数等于空间大小intFullQueue(SeqQueue*Q){returnQ->quelen==MAXSIZE;}33 课后习题答案//进队voidEnQueue(SeqQueue*Q,ElemTypee){if(FullQueue(Q))printf("队已满，无法进队");Q->elem[Q->rear]=e;//将e插入队尾Q->rear=(Q->rear+1)%MAXSIZE;//队尾指针在循环意义上的加1Q->quelen++;//队长增1}//出队voidDeQueue(SeqQueue*Q,ElemType*e){inttmpfront;//设一个临时队头指针if(Q->quelen==0)Error("队已空，无元素可出队");if(Q->rear>Q->quelen)//计算头指针位置tmpfront=Q->rear-Q->quelen;elsetmpfront=Q->rear+MAXSIZE–Q->quelen;quelen--;*e=Q->elem[tmpfront];//用e返回队头元素}第4章串和数组一、填空题1．串中的元素为字符型数据2．两个串的长度相等，并且各个对应位置的字符都相等3．定长顺序存储，堆存储，块链存储，堆存储4．11005．行号，列号，元素值6．三元组，十字链表链式7．元素，表二、选择题1．D2．CD3．A33 课后习题答案4．C三、上机操作题1．解答：//将串S的内容复制到串T中voidStrCopy(SString*T,SStringS){inti;for(i=0;ich[i]=S.ch[i];T->ch[i]="";T->length=S.length;}//在字符串S中查找串T，并删除voidStrDelete(SString*S,SStringT){SStringtemp;inti,j,flag,k=0;if(StrLength(*S)>=StrLength(T))//开始查找{for(i=0;ich[i+j]!=T.ch[j]){flag=0;//与串T不相等，则未查找成功break;}}elseflag=0;if(flag==1)//若查找成功，则跳过串T{for(j=0;jch[i];33 课后习题答案k++;i++;}}}StrCopy(S,temp);//将temp复制到S中}2．解答：//比较串S和串T，若S=T，则返回1；否则返回0intStrCompare(BLStringS,BLStringT){Block*p,*q;inti=0;p=S;q=T;while(p&&q&&p->ch==q->ch){p=p->next;q=q->next;i++;}if(i#includetypedefcharSeqString[27];//定义串类型#defineMaxlen100//以下两句设置加密及解密映射表SeqStringOriginal="abcdefghijklmnopqrstuvwxyz";SeqStringCipher="ngzqtcobmuhelkpdawxfyivrsj";//串匹配(子串只有一个字符)intStrMatch(SStringS,charc)33 课后习题答案{inti;for(i=0;i=0;i--)//将第1个至第n-1个元素依次后移一个位置A[i+1]=A[i];A[0]=temp;//将temp中元素赋予数组的第1个元素}}5．解答：#defineMaxN100ElemTypeSaddle(ElemTypeA[][MaxN],intm,intn){ElemTypemina,maxa;inti,j,ii,jj;for(i=0;i=A[ii][jj])ii++;if(ii>m-1)//找到鞍点A[i][jj]returnA[i][jj];}printf("nThereisnosaddle!n");//不存在鞍点，给出提示信息}6．解答：#defineMaxN100voidTransForm(ElemTypeA[][MaxN],intm,intn,ElemTypeTA[][3]){33 课后习题答案inti,j,t=0;TA[0][0]=m;//记录稀疏矩阵总行数TA[0][1]=n;//记录稀疏矩阵总列数for(i=0;i#defineMaxSize10typedefintDatatype;//定义三元组typedefstruct{inti,j;Datatypev;}TriTupleNode;//定义三元组表typedefstruct{TriTupleNodedata[MaxSize];intm,n,t;//矩阵行，列及三元组表长度}TriTupleTable;//输出稀疏矩阵voidshowMatrix(TriTupleTable*a){intp,q;33 课后习题答案intt=0;for(p=0;pm;p++){for(q=0;qn;q++){if(a->data[t].i==p&&a->data[t].j==q){printf("%d",a->data[t].v);t++;}elseprintf("0");}printf("n");}}///////////////////以下为矩阵加算法////////////voidAddTriTuple(TriTupleTable*A,TriTupleTable*B,TriTupleTable*C){//三元组表表示的矩阵A,B相加intp,q,k,l;C->m=A->m;//矩阵行数C->n=A->n;//矩阵列数C->t=0;//三元组表长度C->data[C->t].v=0;//三元组元素初值k=0;l=0;for(p=0;pm;p++)//行for(q=0;qn;q++)//列if(A->data[k].i==p&&A->data[k].j==q){//如果该元素在A表中有C->data[C->t].v=0;//初始化三元组值C->data[C->t].i=p;C->data[C->t].j=q;C->data[C->t].v+=A->data[k].v;if(B->data[l].i==p&&B->data[l].j==q){//同时在B中也有C->data[C->t].v+=B->data[l].v;l++;//指向B表下一元素}k++;33 课后习题答案C->t++;//指向A表下一元素，C表长增1}elseif(B->data[l].i==p&&B->data[l].j==q){//若A中无，而B中有该元素C->data[C->t].v=0;//初始化三元组值C->data[C->t].i=p;C->data[C->t].j=q;C->data[C->t].v+=B->data[l].v;l++;C->t++;//指向B表下一元素，C表长增1}}//以下为测试程序//主程序voidmain(){TriTupleTableA={1,3,4,2,2,4,2,4,3,3,3,9};TriTupleTableB={2,3,4,2,4,5};TriTupleTableC;A.m=5;A.n=5;A.t=4;B.m=5;B.n=5;B.t=2;printf("TheMatrixA:nn");showMatrix(&A);printf("TheMatrixB:nn");showMatrix(&B);AddTriTuple(&A,&B,&C);printf("TheMatrixC:nn");showMatrix(&C);}33 课后习题答案第5章树与二叉树一、填空题1．根结点2．31，8，163．n0－1，n－2n0＋14．，2i，2i＋15．2n，n－1，n＋16．先序遍历，中序遍历，后序遍历，层次遍历7．HIDJEBFGCA8．前驱9．最优二叉树，带权路径长度WPL最短的二叉树，越近10．ABDCEGF，DBAEGCF，DBGEFCA二、选择题1．C2．B3．B4．C5．A三、解答题1．解答：前序遍历序列为：ABCEGDFH，该二叉树如图5-1所示。2．解答：WPL＝3×4＋6×4＋7×3＋11×2＋15×2＋20×2＝149622636111516209763ABDCEFGH图5-1第1题图5-2第2题3．哈夫曼树如图5-3所示。33 课后习题答案图5-3第3题根据上图可得编码表：a:0010b:10c:00000d:0001e:01f:00001g:11h:0011四、上机操作题1．解答：要交换各结点的左右子树，最方便的办法是用后序遍历算法，每访问一个结点时把两棵子树的指针进行交换，最后一次访问是交换根结点的子树。//交换子树voidChangeBinTree(BinTree*T){if(*T){//这里以指针为参数使得交换在实参的结点上进行//后序遍历BinTreetemp;ChangeBinTree(&(*T)->lchild);ChangeBinTree(&(*T)->rchild);temp=(*T)->lchild;33 课后习题答案(*T)->lchild=(*T)->rchild;(*T)->rchild=temp;}}//以前序序列打印结点数据voidPrintNode(BinTreeT){if(T){printf("%c",T->data);PrintNode(T->lchild);PrintNode(T->rchild);}}//测试程序voidmain(){BinTreeroot;CreatBinTree(&root);//建立二叉链表PrintNode(root);//输出原表printf("n");ChangeBinTree(&root);//交换子树PrintNode(root);//输出新表printf("n");}2．解答：以向量为存储结构的完全二叉树，其存储在向量中的结点其实是按层次遍历的次序存放的。#includetypedefcharDataType;//设结点数据类型为char#defineM100//设结点数不超过100typedefDataTypeBinTree[M];//以向量结构建立完全二叉树voidCreatBinTree(BinTree*T){intn;inti;printf("输入结点个数及结点值:");scanf("%d",&n);//输入结点个数33 课后习题答案(*T)[0]=n;//下标为0的结点存储结点个数for(i=1;i<=n;i++){//输入每个结点数据(*T)[i]=getchar();}}voidPrintTree(BinTreeT){inti;for(i=1;i<=T[0];i++)printf("%c",T[i]);}//前序遍历算法voidPreorder(BinTreeT){intn=T[0];charp[M];//设置一队列存放结点值inti,j;for(i=1;i<=n;i++){if(i==1)//根结点j=1;elseif(2*j<=n)//左子树j=2*j;elseif(j%2==0&&j1&&(j/2)%2==0)//双亲之右兄弟j=j/2+1;elseif(j>1&&(j/2)%2!=0)//双亲的双亲之右兄弟j=j/2/2+1;p[i]=T[j];//入队printf("%c",p[i]);//打印结点值}}voidmain(){BinTreeT;CreatBinTree(&T);PrintTree(T);33 课后习题答案printf("n");Preorder(T);//前序遍历}3．解答：#defineNodeNum100voidPreOrder(BTreeT){BTreestack[NodeNum],p=T;inttop=-1;if(T!=NULL)do{while(p!=NULL){visit(p);//访问当前p所指结点stack[++top]=p;//当前p所指结点进栈p=p->lchild;//p指向其左孩子}p=stack[top--];//栈顶元素出栈p=p->rchild;//p指向其右孩子}while(p!=NULL||top!=-1);}第6章图一、填空题1．邻接矩阵，邻接表，十字链表2．邻接矩阵，邻接表，邻接多重表3．2m4．出度，入度5．16．无回路的有向图7．活动，活动之间的优先关系二、选择题1．B2．D3．C33 课后习题答案4．B5．A6．A三．解答题1．解答：邻接矩阵如图6-1（a）所示，邻接表如图6-1（b）所示。DABC013∧5∧2EF45∧0∧014∧（a）（b）图6-1第1题2．解答：深度优先遍历序列为：ABDFEGC广度优先遍历序列为：ABCDEFG3．解答：最小生成树如图6-2所示。图6-2第3题4．解答：线路图如图6-3所示。v2v0v42520v1v3v5252510图6-3第4题33 课后习题答案5．解答：表6-1第5题a1a2a3a4a5a6a7a8a9a10a11a12a13a14ee0569121614131921le0969121714171921e00566999121216141319l4096691313131219141719存在两条关键路径，如图6-4所示。v9v6v8v0v2v4a2a10a12a14v3a4a6v9v6v8v0v2v4a5a10a12a14a2图6-4第5题完成该工程的最短时间为21个时间单位。四．上机操作题1．解答：#defineMaxVNum100voidALGraphToMGraph(ALGraphGL,MGraph*GM,intn){inti,j;ArcNode*p;for(i=0;iarcs[i][j]=0;for(i=0;iarcs[i][p->adjvex]=1;p=p->next;}}}2．解答：//广度优先判断有向图G中顶点vi到顶点vj是否有路径,是则返回1,否则返回0intExistPath(ALGraphG,inti,intj)33 课后习题答案{QueueQ;intvisited[MAXSIZE];InitQueue(&Q);EnQueue(&Q,i);while(!QueueEmpty(Q)){DeQueue(&Q,&u);visited[u]=1;for(p=G.vertex[i].firstarc;p;p=p->next){k=p->adjvex;if(k==j)return1;if(!visited[k])EnQueue(&Q,k);}//for}//whilereturn0;}第7章查找一、填空题1．顺序，数据元素按值有序排列2．关键字项，指针项3．34．中序5．哈希函数，处理冲突的方法，哈希表的装填因子二、选择题1．D2．B3．C4．D5．A6．A三．解答题1．解答：33 课后习题答案（1）生成的二叉排序树如图7-1所示，中序遍历序列为：15，20，30，37，45，56，69，70。（2）判定树如图7-2所示，ASL＝(1＋2×2＋3×4＋4)/8≈2.615205637307045691520704537305669图7-1第1题（1）图7-2第1题（2）（3）平衡二叉树如图7-3所示。2．解答：散列表如图7-4所示。30152069453756700123456TUETHUWEDFRISUNSATMON图7-3第1题（3）图7-4第2题四．上机操作题1．解答：先利用折半查找法找到被插入元素k的合适位置，然后将表的最后那个元素至该合适位置之间的所有元素（包括最后那个元素与合适位置的那个元素）都依次后移一个位置，最后将被插入元素k插入到该位置，同时修改表的长度加1。voidBinInsert(intA[],intn,intk){intj,low=1;high=n,mid;while(low<=high)//利用折半查找法查找合适位置{mid=(low+high)/2;//计算当前查找区间的中间位置if(k=low;j--)//查找位置后的元素后移一个位置A[j+1]=A[j];A[low]=k;//将k插入查找位置n++;//表长加1}2．解答：[提示]：检验中序遍历序列是否递增有序？[方法1]：用非递归中序遍历算法，设双指针pre,p一旦pre->data>p->data则返回假[方法2]：用递归中序遍历算法，设全局指针pre，（参中序线索化算法）一旦pre->data>p->data则返回假[方法3]：用递归（中序或后序）算法（1）空树是（2）单根树是（3）左递归真（4）右递归真（5）左子树的右端小于根（6）右子树的左端大于根//返回二叉排序树T中所有结点的最大值TelemTypeMaxv(BitreeT){for(p=T;p->rchild;p=p->rchild);returnp->data;}//返回二叉排序树T中所有结点的最小值TelemTypeMinv(BitreeT){for(p=T;p->lchild;p=p->lchild);returnp->data;}//判别T是否为二叉排序树StatusIsBST(BitreeT){if(!T)returnOK;elseif((!T->lchild)||((T->lchild)&&(IsBST(T->lchild)&&(Maxv(T->lchild)data)))&&((!T->rchild)||((T->rchild)&&(IsBST(T->rchild)&&(Minv(T->rchild)>T->data)))returnOKelsereturnERROR;}3．解答：typedefstruct{33 课后习题答案intmaxkey;intfirstloc;}Index;typedefstruct{int*elem;intlength;Indexidx[MAXBLOCK];//每块起始位置和最大元素,其中idx[0]不利用,//其内容初始化为{0,0}以利于折半查找intblknum;//块的数目}IdxSqList;//索引顺序表类型//分块查找,用折半查找法确定记录所在块,块内采用顺序查找法intSearch_IdxSeq(IdxSqListL,intkey){if(key>L.idx[L.blknum].maxkey)returnERROR;//超过最大元素low=1;high=L.blknum;found=0;while(low<=high&&!found)//折半查找记录所在块号mid{mid=(low+high)/2;if(key<=L.idx[mid].maxkey&&key>L.idx[mid-1].maxkey)found=1;elseif(key>L.idx[mid].maxkey)low=mid+1;elsehigh=mid-1;}i=L.idx[mid].firstloc;//块的下界j=i+blksize-1;//块的上界temp=L.elem[i-1];//保存相邻元素L.elem[i-1]=key;//设置监视哨for(k=j;L.elem[k]!=key;k--);//顺序查找L.elem[i-1]=temp;//恢复元素if(kL.r[j+1].key)j++;//沿关键字较小的孩子结点向下筛选if(L.r[0].key0;i--)//初始化建堆HeapAdjust(L,i,L.len);//从最后一个非终端结点进行调整for(i=L.len;i>1;i--){L.r[0]=L.r[1];//将堆顶数据元素和最后一个数据元素交换L.r[1]=L.r[i];L.r[i]=L.r[0];HeapAdjust(L,1,i-1);//将L.r[1…i-1]重新调整为大顶堆}}2．解答：（1）//计数排序算法，将a中记录排序放入b中voidCountSort(SeqList*L,b[],intn){for(i=0;i

您可能关注的文档

相关文档

最近下载