2023青海省數(shù)據(jù)結(jié)構(gòu)分析深入

1、1、設一棵二叉樹的結(jié)點結(jié)構(gòu)為 (LLINK,INFO,RLINK),ROOT為指向該二叉樹根結(jié)點的指針，p和q分別為指向該二叉樹中任意兩個結(jié)點的指針，試編寫一算法ANCESTORROOT，p,q,r,該算法找到p和q的最近共同祖先結(jié)點r。2、設有一個數(shù)組中存放了一個無序的關鍵序列K1、K2、Kn?，F(xiàn)要求將Kn放在將元素排序后的正確位置上，試編寫實現(xiàn)該功能的算法，要求比較關鍵字的次數(shù)不超過n。51. 借助于快速排序的算法思想，在一組無序的記錄中查找給定關鍵字值等于key的記錄。設此組記錄存放于數(shù)組rl.h中。假設查找成功，那么輸出該記錄在r數(shù)組中的位置及其值，否那么顯示“not find信息。請

2、編寫出算法并簡要說明算法思想。3、設從鍵盤輸入一整數(shù)的序列：a1, a2, a3，an,試編寫算法實現(xiàn)：用棧結(jié)構(gòu)存儲輸入的整數(shù)，當ai-1時，將ai進棧；當ai=-1時，輸出棧頂整數(shù)并出棧。算法應對異常情況入棧滿等給出相應的信息。設有一個背包可以放入的物品重量為S，現(xiàn)有n件物品，重量分別為W1，W2，.，Wn。問能否從這n件物品中選擇假設干件放入背包，使得放入的重量之和正好是S。設布爾函數(shù)Knap(S，n)表示背包問題的解，Wi(i=1,2,.，n)均為正整數(shù)，并已順序存儲地在數(shù)組W中。請在以下算法的下劃線處填空，使其正確求解背包問題。Knap(S，n)假設S=0那么Knaptrue否那么假設

3、S0且n1)個整數(shù)存放到一維數(shù)組R中。設計一個盡可能高效時間、空間的算法，將R中保存的序列循環(huán)左移p0p0個人按順時針方向圍坐成一圈，現(xiàn)從第s個人開始按順時針方向報數(shù)，數(shù)到第m個人出列，然后從出列的下一個人重新開始報數(shù)，數(shù)到第m的人又出列，如此重復直到所有的人全部出列為止。現(xiàn)要求采用循環(huán)鏈表結(jié)構(gòu)設計一個算法，模擬此過程。5、給定n個村莊之間的交通圖，假設村莊i和j之間有道路，那么將頂點i和j用邊連接，邊上的Wij表示這條道路的長度，現(xiàn)在要從這n個村莊中選擇一個村莊建一所醫(yī)院，問這所醫(yī)院應建在哪個村莊，才能使離醫(yī)院最遠的村莊到醫(yī)院的路程最短?試設計一個解答上述問題的算法，并應用該算法解答如下列圖

4、的實例。20分6、有一種簡單的排序算法，叫做計數(shù)排序count sorting。這種排序算法對一個待排序的表(用數(shù)組表示)進行排序，并將排序結(jié)果存放到另一個新的表中。必須注意的是，表中所有待排序的關鍵碼互不相同，計數(shù)排序算法針對表中的每個記錄，掃描待排序的表一趟，統(tǒng)計表中有多少個記錄的關鍵碼比該記錄的關鍵碼小，假設針對某一個記錄，統(tǒng)計出的計數(shù)值為c，那么，這個記錄在新的有序表中的適宜的存放位置即為c。 (1) (3分)給出適用于計數(shù)排序的數(shù)據(jù)表定義; (2) (7分)使用Pascal或C語言編寫實現(xiàn)計數(shù)排序的算法； (3) (4分)對于有n個記錄的表，關鍵碼比較次數(shù)是多少? (4) (3分)與

5、簡單項選擇擇排序相比較，這種方法是否更好?為什么?7、對二叉樹的某層上的結(jié)點進行運算，采用隊列結(jié)構(gòu)按層次遍歷最適宜。int LeafKlevel(BiTree bt, int k) /求二叉樹bt 的第k(k1) 層上葉子結(jié)點個數(shù)if(bt=null | k1) return(0); BiTree p=bt,Q; /Q是隊列，元素是二叉樹結(jié)點指針,容量足夠大int front=0,rear=1,leaf=0; /front 和rear是隊頭和隊尾指針, leaf是葉子結(jié)點數(shù)int last=1,level=1; Q1=p; /last是二叉樹同層最右結(jié)點的指針，level 是二叉樹的層數(shù)whi

6、le(frontlchild & !p-rchild) leaf+; /葉子結(jié)點 if(p-lchild) Q+rear=p-lchild; /左子女入隊 if(p-rchild) Q+rear=p-rchild; /右子女入隊 if(front=last) level+; /二叉樹同層最右結(jié)點已處理,層數(shù)增1 last=rear; /last移到指向下層最右一元素if(levelk) return (leaf); /層數(shù)大于k 后退出運行 /while /結(jié)束LeafKLevel8、冒泡排序算法是把大的元素向上移氣泡的上浮，也可以把小的元素向下移氣泡的下沉請給出上浮和下沉過程交替的冒泡排序算

7、法。48.有n個記錄存儲在帶頭結(jié)點的雙向鏈表中，現(xiàn)用雙向起泡排序法對其按上升序進行排序，請寫出這種排序的算法。注：雙向起泡排序即相鄰兩趟排序向相反方向起泡9、假設以鄰接矩陣作為圖的存儲結(jié)構(gòu)，編寫算法判別在給定的有向圖中是否存在一個簡單有向回路，假設存在，那么以頂點序列的方式輸出該回路找到一條即可。注：圖中不存在頂點到自己的弧有向圖判斷回路要比無向圖復雜。利用深度優(yōu)先遍歷，將頂點分成三類：未訪問；已訪問但其鄰接點未訪問完;已訪問且其鄰接點已訪問完。下面用0，1，2表示這三種狀態(tài)。前面已提到，假設dfsv結(jié)束前出現(xiàn)頂點u到v的回邊，那么圖中必有包含頂點v和u的回路。對應程序中v的狀態(tài)為1，而u是正

8、訪問的頂點，假設我們找出u的下一鄰接點的狀態(tài)為1，就可以輸出回路了。void Print(int v,int start ) /輸出從頂點start開始的回路。for(i=1;i=n;i+) if(gvi!=0 & visitedi=1 ) /假設存在邊v,i，且頂點i的狀態(tài)為1。 printf(“%d,v); if(i=start) printf(“n); else Print(i,start);break;/if /Printvoid dfs(int v) visitedv=1;for(j=1;j=n;j+ ) if (gvj!=0) /存在邊(v,j) if (visitedj!=1)

9、if (!visitedj) dfs(j); /if else cycle=1; Print(j,j); visitedv=2;/dfsvoid find_cycle() /判斷是否有回路，有那么輸出鄰接矩陣。visited數(shù)組為全局變量。 for (i=1;i=n;i+) visitedi=0; for (i=1;i=n;i+ ) if (!visitedi) dfs(i);/find_cycle10、有向圖G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7，E=,寫出G的拓撲排序的結(jié)果。G拓撲排序的結(jié)果是：V1、V2、V4、V3、V5、V6、V7 11、連通圖的生成樹包括圖中

10、的全部n個頂點和足以使圖連通的n-1條邊，最小生成樹是邊上權(quán)值之和最小的生成樹。故可按權(quán)值從大到小對邊進行排序，然后從大到小將邊刪除。每刪除一條當前權(quán)值最大的邊后，就去測試圖是否仍連通，假設不再連通，那么將該邊恢復。假設仍連通，繼續(xù)向下刪；直到剩n-1條邊為止。 void SpnTree (AdjList g) /用“破圈法求解帶權(quán)連通無向圖的一棵最小代價生成樹。typedef struct int i,j,wnode; /設頂點信息就是頂點編號，權(quán)是整型數(shù) node edge; scanf( %d%d,&e,&n) ; /輸入邊數(shù)和頂點數(shù)。 for (i=1;i=e;i+) /輸入e條邊：頂

11、點，權(quán)值。 scanf(%d%d%d ,&edgei.i ,&edgei.j ,&edgei.w); for (i=2;i=e;i+) /按邊上的權(quán)值大小，對邊進行逆序排序。 edge0=edgei; j=i-1;while (edgej.w=n) /破圈，直到邊數(shù)e=n-1. if (connect(k) /刪除第k條邊假設仍連通。 edgek.w=0; eg-; /測試下一條邊edgek，權(quán)值置0表示該邊被刪除k+; /下條邊 /while /算法結(jié)束。 connect()是測試圖是否連通的函數(shù)，可用圖的遍歷實現(xiàn)，12、證明由二叉樹的中序序列和后序序列，也可以唯一確定一棵二叉樹。29. 試

12、找出滿足以下條件的二叉樹1先序序列與后序序列相同 2中序序列與后序序列相同3先序序列與中序序列相同 4中序序列與層次遍歷序列相同13、因為后序遍歷棧中保存當前結(jié)點的祖先的信息，用一變量保存棧的最高棧頂指針，每當退棧時，棧頂指針高于保存最高棧頂指針的值時，那么將該棧倒入輔助棧中，輔助棧始終保存最長路徑長度上的結(jié)點，直至后序遍歷完畢，那么輔助棧中內(nèi)容即為所求。void LongestPath(BiTree bt)/求二叉樹中的第一條最長路徑長度BiTree p=bt,l,s; /l, s是棧，元素是二叉樹結(jié)點指針，l中保存當前最長路徑中的結(jié)點 int i，top=0,tag,longest=0;

13、while(p | top0) while(p) s+top=p；tagtop=0; p=p-Lc; /沿左分枝向下 if(tagtop=1) /當前結(jié)點的右分枝已遍歷 if(!stop-Lc & !stop-Rc) /只有到葉子結(jié)點時，才查看路徑長度if(toplongest) for(i=1;i0) tagtop=1; p=stop.Rc; /沿右子分枝向下 /while(p!=null|top0)/結(jié)束LongestPath14、由二叉樹的前序遍歷和中序遍歷序列能確定唯一的一棵二叉樹，下面程序的作用是實現(xiàn)由某二叉樹的前序遍歷和中序遍歷序列，生成一棵用二叉鏈表表示的二叉樹并打印出后序遍歷序

14、列，請寫出程序所缺的語句。#define MAX 100typedef struct Nodechar info; struct Node *llink, *rlink; TNODE;char predMAX,inodMAX; main(int argc,int *argv) TNODE *root;if(argc3) exit 0;strcpy(pred,argv1); strcpy(inod,argv2);root=restore(pred,inod,strlen(pred);postorder(root);TNODE *restore(char *ppos,char *ipos,int

15、n) TNODE *ptr； char *rpos; int k;if(ninfo=(1)_;for(2)_ ; rposllink=restore(ppos+1, (4)_,k );ptr-rlink=restore (5)_+k,rpos+1,n-1-k);return ptr;postorder(TNODE*ptr) if(ptr=NULL) return; postorder(ptr-llink); postorder(ptr-rlink); printf(“%c,ptr-info); 15、后序遍歷最后訪問根結(jié)點，即在遞歸算法中，根是壓在棧底的。采用后序非遞歸算法，棧中存放二叉樹結(jié)點

16、的指針，當訪問到某結(jié)點時，棧中所有元素均為該結(jié)點的祖先。此題要找p和q 的最近共同祖先結(jié)點r ,不失一般性，設p在q的左邊。后序遍歷必然先遍歷到結(jié)點p，棧中元素均為p的祖先。將?？饺肓硪惠o助棧中。再繼續(xù)遍歷到結(jié)點q時，將棧中元素從棧頂開始逐個到輔助棧中去匹配，第一個匹配即相等的元素就是結(jié)點p 和q的最近公共祖先。typedef struct BiTree t;int tag;/tag=0 表示結(jié)點的左子女已被訪問，tag=1表示結(jié)點的右子女已被訪問stack;stack s,s1;/棧，容量夠大BiTree Ancestor(BiTree ROOT,p,q,r)/求二叉樹上結(jié)點p和q的最近的共同祖先結(jié)點r。top=0; bt=ROOT; while(bt!=null |top0)while(bt!=null & bt!=p & bt!=q) /結(jié)點入棧s+top.t=bt; stop.tag=0; bt=bt-lchild; /沿左分枝向下if(bt=p) /不失一般性，假定p在q的左側(cè),遇結(jié)點p時，