大学《算法数据结构》复习试题及答案

《大学《算法数据结构》复习试题及答案》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、大学《算法数据结构》复习试题及答案　　　　数据结构是主体通用算法是附属(仅是查找,排序等)以下是由阳光网小编整理关于大学《算法数据结构》复习试题的内容希望大家喜欢　　　　算法设计题(每小题6分.共12分)　　　　1.请写出在循环队列上进行插入操作的算法要求若插入成功则返目true否则返回else.　　　　循环队列定义如下：　　　　struetCyclicQueue{　　　　ElemTy[aeelem[M];//M为已定义过的整型常量表示队列数组空间长度　　　　intrear,front;//rear指向队尾元素后一个位置front指向队头元索　　　　inttag;　　　

2、　};　　　　注意：当front=rear且tag=0时队列空当front=rear且tag=1时队列满即队列中已有M个元素.　　　　boolEnCQueue(CyclicQueueQ,ElemTypex){{/*编写该函数体/}　　　　//在下面编写函数体　　　　2.已知二又树中的结点类型Bin·rreeNode定义为：　　　　slructBinTreeNode{chardata;BinTreeNode*left,*right;};　　　　其中data为结点值域left和righ~分别为指向左、右子女结点的指针域根据下面函数声明编写出求一棵二叉树中结点总数的递归算法该

3、总数值由函数返回.假定BT初始指　　　　向这棵二又树的根结点.　　　　intBTreeCount(BinTreeNode*BT);　　　　答案　　　　算法设计题(2小题每小题6‘分共12分)　　　　1.分步给分　　　　if(Q.rear=Q,frontQtag==1)returnfalse;　　　　Q.elem[Q,rear]=x;　　　　Q.rtar=(Q.rear+1)%M;　　　　if(Q.rear==Q.front)Q.tag=1;　　　　returntrue;　　　　2.分步给分　　　　intBTreeCount(BinTreeNode*BT)　　　　(　　　

4、　if(BT==NULL)　　　　returnO;　　　　else　　　　returnBTreeCount(BT>left)+BTreeCount(BT>fight)+l;　　　　1.设字符串类String具有下列操作：　　　　intLength()const;//计算字符串的长度　　　　chargetData(k);//提取字符串第k个字符的值　　　　若字符串Tar的值为“ababcabcacbab“的值为‘abcac”时　　　　(1)给出下面算法执行后返回的结果　　　　(2)给出下面算法的功能　　　　includeString,h　　　　intunknown(Str

5、ingTar,strlngPat)coast　　　　{　　　　for(inti　　　　ihtj=O;　　　　while(j　　　　if(Tar.getOata(i+j)==Pat.getData(j))j++　　　　elsebreak;　　　　if(j==Pat.Length())returni;　　　　return–1;　　　　}　　　　返回结果：　　　　算法功能：　　　　2已知二叉树中的结点类型BinTrceNode定义为：　　　　structBinTreeNode{ElemTypedata;BinTreeNode*left,*right;}　　　　其中data为结

6、点值域left和right分别为指向左、右子女结点的指针域.下面函数的功能是返回二又树BT中值为X的结点所在的层号.根据题意按标号把合适的内容填写到算法后面相应标号的位置.　　　　intNodeLevel(BinTreeNode*BT,ElemTypeX)　　　　if(BT==NULL)return1;//空树的层号为一1　　　　elseif(BT>data==X)return0;//根结点的层号为o　　　　//向于树中查找X结点　　　　else{　　　　imcl=NodeLevel(BT>left,X);　　　　if(cl>=0)(1)　　　　ihte2=(2);　　

7、　　if((3))returnc2+1;　　　　//若树中不存在K结点则返回一l　　　　elsereturn1　　　　}　　　　}　　　　(1)　　　　(2)　　　　(3)　　　　3.假定一个有向无权图采用邻接矩阵存储请指出F面算法的功能　　　　Template　　　　voidGraph::unknown(inti)　　　　{　　　　intd,j;　　　　d=0;　　　　for(j=0;j　　　　if(Edge[i][j]){d++;Edge[i][j]=0;}　　　　if(Edge[j][i]){d++;Edge[j][i]=0;}