數據結構考研復習算法設計單考

數據結構復習-算法設計題1、判斷兩棵樹是否相似intBitree_Sim(BitreeB1,BitreeB2){//判斷兩棵樹是否相似的遞歸算法

if(!B1&&!B2)return1;

elseif(B1&&B2&&Bitree_Sim(B1->lchild,B2->lchild)&&Bitree_Sim(B1->rchild,B2->rchild))

return1;

elsereturn0;}//Bitree_Sim2、設二叉樹為二叉鏈表為存儲結構，設計算法將二叉樹中各結點的左右孩子位置交換。voidBitree_Revolute(BitreeT){//交換所有結點的左右子樹

p=T->lchild;T->rchild=T->lchild;T->rchild=p;//交換左右子樹

if(T->lchild)Bitree_Revolute(T->lchild);

if(T->rchild)Bitree_Revolute(T->rchild);//左右子樹再分別交換各自的左右子樹

}//Bitree_Revolute3-1、求二叉樹中以值為x的結點為根的子樹深度intGet_Sub_Depth(BitreeT,intx){//求二叉樹中以值為x的結點為根的子樹深度

if(T->data==x)

{

printf("%d\n",Get_Depth(T));//找到了值為x的結點,求其深度

exit1;

}

else

{

if(T->lchild)Get_Sub_Depth(T->lchild,x);

if(T->rchild)Get_Sub_Depth(T->rchild,x);//在左右子樹中繼續(xù)尋找

}

}//Get_Sub_DepthintGet_Depth(BitreeT){//求子樹深度的遞歸算法

if(!T)return0;

else

{

m=Get_Depth(T->lchild);

n=Get_Depth(T->rchild);

return(m>n?m:n)+1;

}

}//Get_Depth3-2、假設一棵平衡二叉樹的每個結點都標明了平衡因子bf,試設計一個算法，求平衡二叉樹的高度。intHeight_Bf（BSTreeT）//求平衡二叉樹T的高度{level=0；p=T；while（p）{level++；//樹的高度增1if（p->bf<0）p=p->rchild；//bf=-1沿右分枝向下elsep=p->lchild；//bf>=0沿左分枝向下}//whilereturnlevel；//平衡二叉樹的高度}//Height_Bf3-3、設二叉樹結點結構為平衡二叉樹結點結構，設計一遞歸算法計算并填寫二叉樹中每個結點的平衡因子，同時返回二叉樹中不平衡結點的個數。intGet_BF(BitreeT,int&count){//求各結點的平衡因子

if(T)

{

Get_BF(T->lchild);//遍歷左子樹

Get_BF(T->rchild);//遍歷右子樹

m=Get_Depth(T->lchild);

n=Get_Depth(T->rchild);

T->bf=m-n;if(T->bf>1||T->bf<-1)count++;

}//if

}//Get_BF4、已知一個二叉樹的先序序列和中序序列分別存儲與兩個一維數組中，設計算法建立二叉樹的二叉鏈表結構。BiTreeIntoPost{(ElemTypein[],post[],intl1,h1,l2,h2)//l1,h1,l2,h2分別是兩序列第一和最后結點的下標T=(BiTree)malloc(sizeof(BiNode));//申請結點T->data=post[h2];//后序遍歷序列最后一個元素是根結點數據for(i=l1;i<=h1;i++)if(in[i]==post[h2])break;//在中序序列中查找根結點if(i==l1)T->lchild=null;//處理左子樹elseT->lchild=IntoPost(in,post,l1,i-1,l2,l2+i-l1-1)；if(i==h1)T->rchild=null;//處理右子樹elseT->rchild=IntoPost(in,post,i+1,h1,l2+i-l1,h2-1);returnT;}//IntoPost5、已知二叉樹的順序存儲結構建立二叉鏈表結構boolCreateBitree_SqList(Bitree&T,SqListsa){//根據順序存儲結構建立二叉鏈表

Bitreeptr[sa.last+1];//該數組儲存與sa中各結點對應的樹指針

if(!sa.last)

{

T=NULL;//空樹

returntrue;

}

ptr[1]=(BTNode*)malloc(sizeof(BTNode));

ptr[1]->data=sa.elem[1];//建立樹根

T=ptr[1];

for(i=2;i<=sa.last;i++)

{

if(!sa.elem[i])returnfalse;//順序錯誤

ptr[i]=(BTNode*)malloc(sizeof(BTNode));

ptr[i]->data=sa.elem[i];

j=i/2;//找到結點i的雙親j

if(i-j*2)ptr[j]->rchild=ptr[i];//i是j的右孩子

elseptr[j]->lchild=ptr[i];//i是j的左孩子

}

returntrue;

}//CreateBitree_SqList6、二叉樹層次遍歷voidLayerOrder(BitreeT){//層次遍歷二叉樹

InitQueue(Q);//建立工作隊列

EnQueue(Q,T);

while(!QueueEmpty(Q))

{

DeQueue(Q,p);

visit(p);

if(p->lchild)EnQueue(Q,p->lchild);

if(p->rchild)EnQueue(Q,p->rchild);

}}//LayerOrder7、判斷二叉樹是否完全二叉樹（1）應用隊列intIsFull_Bitree(BitreeT){//判斷二叉樹是否完全二叉樹,是則返回1,否則返回0

InitQueue(Q);

flag=0;

EnQueue(Q,T);//建立工作隊列

while(!QueueEmpty(Q))

{

DeQueue(Q,p);

if(!p)flag=1;

elseif(flag)return0;

else

{

EnQueue(Q,p->lchild);

EnQueue(Q,p->rchild);//不管孩子是否為空,都入隊列

}

}//while

return1;

}//IsFull_Bitree（2）應用層次遍歷intJudgeComplete(BiTreeT){//判斷二叉樹是否是完全二叉樹,如是，返回1，否則，返回0inttag=0;p=T;if(!p)return1;InitQueue(Q);EnQueue(Q,p);//初始化隊列，根結點指針入隊while(!QueueEmpty(Q)){DeQueue(Q,p);//出隊if(p->lchild&&!tag)EnQueue(Q,p->lchild);//左子女入隊else{if(p->lchild)return0;//前邊已有結點為空，本結點不空elsetag=1;//首次出現結點為空if(p->rchild&&!tag)EnQueue(Q,p->rchild);//右子女入隊elseif(p->rchild)return0;elsetag=1;}//whilereturn1;}//JudgeComplete8、設二叉樹以二叉鏈表為存儲結構，設計算法通過一次遍歷求二叉樹寬度并輸出這一層上的所有的葉子結點的算法。所謂寬度是指二叉樹的各層上，具有結點數最多的那一層上的結點總數。（二叉樹采用二叉鏈表為存儲結構，設計算法求出二叉樹中第i層和第i+1葉子結點個數之和。）（1）使用數組typedefstruct{

BTNodenode;

intlayer;

}BTNRecord;//包含結點所在層次的記錄類型intWidth1(BitreeT){//求一棵二叉樹的寬度

intcountd;//count數組存放每一層的結點數

InitQueue(Q);//Q的元素為BTNRecord類型

EnQueue(Q,{T,0});

while(!QueueEmpty(Q))

{

DeQueue(Q,r);

count[r.layer]++;

if(r.node->lchild)EnQueue(Q,{r.node->lchild,r.layer+1});

if(r.node->rchild)EnQueue(Q,{r.node->rchild,r.layer+1});

}//利用層序遍歷來統(tǒng)計各層的結點數

for(maxn=count[0],i=1;count[i];i++)

if(count[i]>maxn)maxn=count[i];//求層最大結點數

returnmaxn;}//Width1（2）使用變量intWidth2(BiTreeT){//求二叉樹bt的最大寬度if(!T)return0;//空二叉樹寬度為0else{BiTreeQ[];//Q是隊列，元素為二叉樹結點指針，容量足夠大 front=1;rear=1;last=1;//front隊頭指針,rear隊尾指針,last同層最右結點在隊列中的位置 temp=0;maxw=0;//temp記局部寬度,maxw記最大寬度 Q[rear]=T;//根結點入隊列 while(front<=last){ p=Q[front++];temp++;//同層元素數加1 if(p->lchild)Q[++rear]=p->lchild;//左子女入隊if(p->rchild)Q[++rear]=p->rchild;//右子女入隊 if(front>last){//一層結束， last=rear;if(temp>maxw)maxw=temp;//last指向下層最右元素,更新當前最大寬度 temp=0;}//if}//while return(maxw);}//width29、假設一個僅包含二元運算符的算術表達式以二叉鏈表形式存放于二叉樹T中，設計算法后序遍歷計算表達式的值。floatPostEval(BiTreeT){//以后序遍歷算法求以二叉樹表示的算術表達式的值floatlv,rv;if(T){lv=PostEval(T->lchild);//求左子樹表示的子表達式的值rv=PostEval(T->rchild);//求右子樹表示的子表達式的值switch(T->optr){case‘+’:value=lv+rv;break;case‘-’:value=lv-rv;break;case‘*’:value=lv*rv;break;case‘/’:value=lv/rv;}//switch}//ifreturn(value);}//PostEval10、設計算法利用葉子結點中的空指針域將所有葉子結點鏈接為一個帶有頭結點的雙鏈表，算法返回頭結點的地址。voidCreatLeafList(BiTreeT){//將BiTree樹中所有葉子結點鏈成帶頭結點的雙鏈表，if（T）{CreatLeafList（bt->lchild）;//中序遍歷左子樹if(!T->lchild&&!T->rchildl)//葉子結點if(!L){//第一個葉子結點L=(BiTree)malloc(sizeof(BiNode));//生成頭結點L->lchild=null;L->rchild=T;//頭結點的左鏈為空,右鏈指向第一個葉子結點T->lchild=L;pre=T;//第一個葉子結點左鏈指向頭結點，pre指向當前葉子結點}//ifelse{//已不是第一個葉子結點pre->rchild=T;T->lchild=pre;pre=T;}//當前葉子結點鏈入雙鏈表CreatLeafList(T->rchild);//中序遍歷右子樹pre->rchild=null;//最后一個葉子結點的右鏈置空（鏈表結束標記）}//if(T)}//CreatLeafList11、給出中序線索二叉樹的結點結構，試編寫在不使用棧和遞歸的情況下先序遍歷中序線索二叉樹的算法。voidPreorder_InThreat(BiThrTreeT)//按先序遍歷帶頭結點的中序線索二叉樹T{p=T->lchild;//設p指向二叉樹的根結點while(p){while(p->ltag==0){printf(p->data);p=p->lchild;//遍左printf(p->data);//準備右轉while(p->rtag==1&&p->rchild!=T)p=p->rchild;//回溯if(p->rchild!=T)p=p->rchild;//遍右}//while(p)}//Preorder_In12、非遞歸不用棧中序遍歷帶有雙親指針的三叉鏈表的二叉樹typedefstruct{intdata;PBTNode*lchild;PBTNode*rchild;PBTNode*parent;}PBTNode,PBitree;//有雙親指針域的二叉樹結點類型voidInorder_Nonrecursive(PBitreeT){//不設棧非遞歸遍歷有雙親指針的二叉樹p=T;while(p->lchild)p=p->lchild;//向左走到盡頭while(p){visit(p);if(p->rchild){//尋找中序后繼:當有右子樹時p=p->rchild;while(p->lchild)p=p->lchild;//后繼就是在右子樹中向左走到盡頭}elseif(p->parent->lchild==p)p=p->parent;//當自己是雙親的左孩子時后繼就是雙親else{p=p->parent;while(p->parent&&p->parent->rchild==p)p=p->parent;p=p->parent;}//當自己是雙親的右孩子時后繼就是向上返回直到遇到自己是在其左子樹中的祖先}//while}//Inorder_Nonrecursive13、設有向G圖有n個頂點,e條邊,設計算法根據其鄰接表生成其逆鄰接表,要求算法復雜性為O(n+e)。voidInvertAdjList(AdjListgin,gout）//將有向圖的出度鄰接表改為按入度建立的逆鄰接表{for(i=1;i<=n;i++)//設有向圖有n個頂點，建逆鄰接表的頂點向量。{gin[i].vertex=gout[i].vertex;gin.firstarc=null;}for(i=1;i<=n;i++)//鄰接表轉為逆鄰接表。{p=gout[i].firstarc;//取指向鄰接表的指針。while(p!=null){j=p->adjvex;s=(ArcNode*)malloc(sizeof(ArcNode));//申請結點空間。s->adjvex=i;s->next=gin[j].firstarc;gin[j].firstarc=s;p=p->next;//下一個鄰接點。}//while}//for}//InvertAdjList14、寫出從圖的鄰接表表示轉換成鄰接矩陣表示的算法。voidAdjListToAdjMatrix(AdjListgl,AdjMatrixgm)//將圖的鄰接表表示轉換為鄰接矩陣表示。{for(i=1;i<=n;i++)//設圖有n個頂點，鄰接矩陣初始化。for(j=1;j<=n;j++)gm[i][j]=0;for(i=1;i<=n;i++){p=gl[i].firstarc;//取第一個鄰接點。while(p!=null){gm[i][p->adjvex]=1;p=p->next;}//下一個鄰接點}//for}//AdjListToAdjMatrix15、試寫一算法，判斷以鄰接表方式存儲的有向圖中是否存在由頂點Vi到頂點Vj的路徑（i<>j）。設一全程變量flag。初始化為0，若有通路，則flag=1。intvisited[]=0;//全局變量，訪問數組初始化intdfs_path(AdjListg,vi)//以鄰接表為存儲結構的有向圖g，判斷頂點Vi到Vj是否有通路{visited[vi]=1;//visited是訪問數組，設頂點的信息就是頂點編號。p=g[vi].firstarc;//第一個鄰接點。while(p!=null){j=p->adjvex;if(vj==j){flag=1;return（1）;}//vi和vj有通路。if(visited[j]==0)dfs(g,j);p=p->next；}//whileif(!flag)return(0);}//dfs_path16、再有向圖g中，如果r到g中的每個節(jié)點都有路徑可達，則稱結點r為g的根結點，編寫一個算法完成下列功能：（1）建立有向圖的鄰接表存儲結構；（2）判斷有向圖g是否有根，若有，則打印出所有的根結點的值。intnum=0，visited[]=0//num記訪問頂點個數,訪問數組visited初始化。constn=用戶定義的頂點數;AdjListg;//用鄰接表作存儲結構的有向圖g。voiddfs(v){visited[v]=1;num++;//訪問的頂點數＋1if(num==n){printf(“%d是有向圖的根。\n”,v);num=0;}//ifp=g[v].firstarc;while(p){if(visied[p->adjvex]==0)dfs(p->adjvex);p=p->next;}//whilevisited[v]=0;num--;//恢復頂點v}//dfsvoidJudgeRoot()//判斷有向圖是否有根，有根則輸出之。{staticinti;for(i=1;i<=n;i++)//從每個頂點出發(fā)，調用dfs()各一次。{num=0;visited[1..n]=0;dfs(i);}}//JudgeRoot17、圖的D_搜索類似與BFS,不同之處在于使用棧代替BFS中的隊列,入出隊列的操作改為入出棧的操作，即當一個頂點的所有鄰接點被搜索之后,下一個搜索出發(fā)點應該是最近入棧(棧頂)的頂點。（1）．用鄰接表做存儲結構,寫一個D_搜索算法；（2）．用D_搜索方法的訪問次序和相應的生成樹，當從某頂點出發(fā)搜索它的鄰接點，請按鄰接點序號遞增序搜索，以使答案唯一。voidD_BFS(AdjListg,vertypev0)//從v0頂點開始，對以鄰接表為存儲結構的圖g進行D_搜索。{ints[],top=0;//棧，棧中元素為頂點，仍假定頂點用編號表示。for(i=1,i<=n;i++)visited[i]=0;//圖有n個頂點，visited數組為全局變量。for(i=1,i<=n;i++)//對n個頂點的圖g進行D_搜索。if(visited[i]==0){s[++top]=i;visited[i]=1;printf("%3d",i);while(top>0){i=s[top--];//退棧p=g[i].firstarc;//取第一個鄰接點while(p!=null)//處理頂點的所有鄰接點{j=p->adjvex;if(visited[j]==0)//未訪問的鄰接點訪問并入棧。{visited[j]=1;printf("%3d",i);s[++top]=j;}51p=p->next;5132432467}//while(top>0)}//if}//D_BFS（2）D_搜索序列：1234675，生成樹如圖：18、假設一個有向圖G已經以十字鏈表形式存儲在內存中，試寫一個判斷該有向圖中是否有環(huán)（回路）的算法。intTopsor(OrthListg)//判斷以十字鏈表為存儲結構的有向圖g是否存在環(huán)路{inttop=0;//用作棧頂指針for(i=1;i<=n;i++)//求各頂點的入度。設有向圖g有n個頂點，初始時入度域均為0{p=g[i].firstin;//設頂點信息就是頂點編號，否則，要進行頂點定位while(p){g[i].indegree++;//入度域增1if(p->headvex==i)p=p->headlink;elsep=p->taillink;//找頂點i的鄰接點}//while(p)}//forfor(i=1;i<=n;i++)//建立入度為0的頂點的棧if(g[i].indegree==0){g[i].indegree=top;top=i;}m=0;//m為計數器，記輸出頂點個數while(top<>0){i=top;top=g[top].indegree;m++;//top指向下一入度為0的頂點p=g[i].firstout;while(p)//處理頂點i的各鄰接點的入度{if(p->tailvex==i)k=p->headvex;elsek=p->tailvex;}//找頂點i的鄰接點g[k].indegree--;//鄰接點入度減1if(g[k].indegree==0){g[k].indegree=top;top=k;}//入度為0的頂點再入棧if(p->headvex==i)p=p->headlink;elsep=p->taillink;//找頂點i的下一鄰接點}//while(p)}//while(top<>0)if(m<n)retun(1);//有向圖存在環(huán)路elsereturn(0);//有向圖無環(huán)路}//Topsor19、無向圖G按鄰接矩陣存儲，試設計算法刪除從頂點v到頂點w之間的一條邊。StatusDelete_Arc(MGraph&G,charv,charw)//在鄰接矩陣表示的圖G上刪除邊(v,w)

{

if((i=LocateVex(G,v))<0)returnERROR;

if((j=LocateVex(G,w))<0)returnERROR;

if(G.arcs[i][j].adj)

{

G.arcs[i][j].adj=0;

G.arcnum--;

}

returnOK;

}//Delete_Arc20、求鄰接表方式存儲的有向圖G的頂點i到j之間長度為len的簡單路徑條數

intGetPathNum_Len(ALGraphG,inti,intj,intlen)//求鄰接表方式存儲的有向圖G的頂點i到j之間長度為len的簡單路徑條數

{

if(i==j&&len==0)return1;//找到了一條路