2023河南省數(shù)據(jù)分析深入

1、1、在有向圖G中，如果r到G中的每個結(jié)點(diǎn)都有路徑可達(dá)，那么稱結(jié)點(diǎn)r為G的根結(jié)點(diǎn)。編寫一個算法完成以下功能：1建立有向圖G的鄰接表存儲結(jié)構(gòu)；2判斷有向圖G是否有根，假設(shè)有，那么打印出所有根結(jié)點(diǎn)的值。2、對二叉樹的某層上的結(jié)點(diǎn)進(jìn)行運(yùn)算，采用隊(duì)列結(jié)構(gòu)按層次遍歷最適宜。int LeafKlevel(BiTree bt, int k) /求二叉樹bt 的第k(k1) 層上葉子結(jié)點(diǎn)個數(shù)if(bt=null | k1) return(0); BiTree p=bt,Q; /Q是隊(duì)列，元素是二叉樹結(jié)點(diǎn)指針,容量足夠大int front=0,rear=1,leaf=0; /front 和rear是隊(duì)頭和隊(duì)尾指針

2、, leaf是葉子結(jié)點(diǎn)數(shù)int last=1,level=1; Q1=p; /last是二叉樹同層最右結(jié)點(diǎn)的指針，level 是二叉樹的層數(shù)while(frontlchild & !p-rchild) leaf+; /葉子結(jié)點(diǎn) if(p-lchild) Q+rear=p-lchild; /左子女入隊(duì) if(p-rchild) Q+rear=p-rchild; /右子女入隊(duì) if(front=last) level+; /二叉樹同層最右結(jié)點(diǎn)已處理,層數(shù)增1 last=rear; /last移到指向下層最右一元素if(levelk) return (leaf); /層數(shù)大于k 后退出運(yùn)行 /whi

3、le /結(jié)束LeafKLevel3、(1)p-rchild (2)p-lchild (3)p-lchild (4)ADDQ(Q,p-lchild) (5)ADDQ(Q,p-rchild)25. (1)t-rchild!=null (2)t-rchild!=null (3)N0+ (4)count(t-lchild) (5)count(t-rchild)26. .(1)top+ (2) stacktop=p-rchild (3)top+ (4)stacktop=p-lchild27. (1)*ppos / 根結(jié)點(diǎn)2rpos=ipos (3)rposipos (4)ipos (5)ppos+14、

4、編寫一個過程，對一個nn矩陣，通過行變換，使其每行元素的平均值按遞增順序排列。5、給定n個村莊之間的交通圖，假設(shè)村莊i和j之間有道路，那么將頂點(diǎn)i和j用邊連接，邊上的Wij表示這條道路的長度，現(xiàn)在要從這n個村莊中選擇一個村莊建一所醫(yī)院，問這所醫(yī)院應(yīng)建在哪個村莊，才能使離醫(yī)院最遠(yuǎn)的村莊到醫(yī)院的路程最短?試設(shè)計(jì)一個解答上述問題的算法，并應(yīng)用該算法解答如下列圖的實(shí)例。20分void Hospital(AdjMatrix w,int n) /在以鄰接帶權(quán)矩陣表示的n個村莊中，求醫(yī)院建在何處，使離醫(yī)院最遠(yuǎn)的村莊到醫(yī)院的路徑最短。 for (k=1;k=n;k+) /求任意兩頂點(diǎn)間的最短路徑 for (i

5、=1;i=n;i+) for (j=1;j=n;j+) if (wik+wkjwij) wij=wik+wkj; m=MAXINT; /設(shè)定m為機(jī)器內(nèi)最大整數(shù)。 for (i=1;i=n;i+) /求最長路徑中最短的一條。 s=0; for (j=1;j=n;j+) /求從某村莊i1=is) s=wij; if (s=m) m=s; k=i;/在最長路徑中，取最短的一條。m記最長路徑，k記出發(fā)頂點(diǎn)的下標(biāo)。 Printf(“醫(yī)院應(yīng)建在%d村莊，到醫(yī)院距離為%dn,i,m); /for/算法結(jié)束對以上實(shí)例模擬的過程略。各行中最大數(shù)依次是9，9，6，7，9，9。這幾個最大數(shù)中最小者為6，故醫(yī)院應(yīng)建在

6、第三個村莊中,離醫(yī)院最遠(yuǎn)的村莊到醫(yī)院的距離是6。1、對圖1所示的連通網(wǎng)G，請用Prim算法構(gòu)造其最小生成樹每選取一條邊畫一個圖。6、二部圖bipartite graph G=V，E是一個能將其結(jié)點(diǎn)集V分為兩不相交子集V 1和V2=V-V1的無向圖，使得：V1中的任何兩個結(jié)點(diǎn)在圖G中均不相鄰，V2中的任何結(jié)點(diǎn)在圖G中也均不相鄰。1請各舉一個結(jié)點(diǎn)個數(shù)為5的二部圖和非二部圖的例子。2請用C或PASCAL編寫一個函數(shù)BIPARTITE判斷一個連通無向圖G是否是二部圖，并分析程序的時(shí)間復(fù)雜度。設(shè)G用二維數(shù)組A來表示，大小為n*nn為結(jié)點(diǎn)個數(shù)。請?jiān)诔绦蛑屑颖匾淖⑨?。假設(shè)有必要可直接利用堆?；蜿?duì)列操作?！?/p>

7、7、有向圖G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7，E=,寫出G的拓?fù)渑判虻慕Y(jié)果。G拓?fù)渑判虻慕Y(jié)果是：V1、V2、V4、V3、V5、V6、V7 8、設(shè)有一個數(shù)組中存放了一個無序的關(guān)鍵序列K1、K2、Kn?，F(xiàn)要求將Kn放在將元素排序后的正確位置上，試編寫實(shí)現(xiàn)該功能的算法，要求比較關(guān)鍵字的次數(shù)不超過n。51. 借助于快速排序的算法思想，在一組無序的記錄中查找給定關(guān)鍵字值等于key的記錄。設(shè)此組記錄存放于數(shù)組rl.h中。假設(shè)查找成功，那么輸出該記錄在r數(shù)組中的位置及其值，否那么顯示“not find信息。請編寫出算法并簡要說明算法思想。9、將頂點(diǎn)放在兩個集合V1和V2。對每個

8、頂點(diǎn)，檢查其和鄰接點(diǎn)是否在同一個集合中，如是，那么為非二部圖。為此，用整數(shù)1和2表示兩個集合。再用一隊(duì)列結(jié)構(gòu)存放圖中訪問的頂點(diǎn)。 int BPGraph (AdjMatrix g) /判斷以鄰接矩陣表示的圖g是否是二部圖。 int s; /頂點(diǎn)向量，元素值表示其屬于那個集合值1和2表示兩個集合 int Q;/Q為隊(duì)列，元素為圖的頂點(diǎn)，這里設(shè)頂點(diǎn)信息就是頂點(diǎn)編號。 int f=0,r,visited; /f和r分別是隊(duì)列的頭尾指針,visited是訪問數(shù)組 for (i=1;i=n;i+) visitedi=0;si=0; /初始化，各頂點(diǎn)未確定屬于那個集合 Q1=1; r=1; s1=1;/頂

9、點(diǎn)1放入集合S1while(fr) v=Q+f; if (sv=1) jh=2; else jh=1;/準(zhǔn)備v的鄰接點(diǎn)的集合號 if (!visitedv) visitedv=1; /確保對每一個頂點(diǎn)，都要檢查與其鄰接點(diǎn)不應(yīng)在一個集合中for (j=1,j=n;j+) if (gvj=1)if (!sj) sj=jh; Q+r=j; /鄰接點(diǎn)入隊(duì)列 else if (sj=sv) return(0); /非二部圖 /if (!visitedv)/while return(1); /是二部圖算法討論 題目給的是連通無向圖，假設(shè)非連通，那么算法要修改。10、連通圖的生成樹包括圖中的全部n個頂點(diǎn)和足

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

11、nf(%d%d%d ,&edgei.i ,&edgei.j ,&edgei.w); for (i=2;i=e;i+) /按邊上的權(quán)值大小，對邊進(jìn)行逆序排序。 edge0=edgei; j=i-1;while (edgej.w=n) /破圈，直到邊數(shù)e=n-1. if (connect(k) /刪除第k條邊假設(shè)仍連通。 edgek.w=0; eg-; /測試下一條邊edgek，權(quán)值置0表示該邊被刪除k+; /下條邊 /while /算法結(jié)束。 connect()是測試圖是否連通的函數(shù)，可用圖的遍歷實(shí)現(xiàn)，11、設(shè)一棵二叉樹的結(jié)點(diǎn)結(jié)構(gòu)為 (LLINK,INFO,RLINK),ROOT為指向該二叉樹根

12、結(jié)點(diǎn)的指針，p和q分別為指向該二叉樹中任意兩個結(jié)點(diǎn)的指針，試編寫一算法ANCESTORROOT，p,q,r,該算法找到p和q的最近共同祖先結(jié)點(diǎn)r。12、#define maxsize ?？臻g容量 void InOutS(int smaxsize) /s是元素為整數(shù)的棧，本算法進(jìn)行入棧和退棧操作。 int top=0; /top為棧頂指針，定義top=0時(shí)為?？铡?for(i=1; i=n; i+) /n個整數(shù)序列作處理。 scanf(“%d,&x); /從鍵盤讀入整數(shù)序列。 if(x!=-1) / 讀入的整數(shù)不等于-1時(shí)入棧。 if(top=maxsize-1)printf(“棧滿n);exi

13、t(0);else s+top=x; /x入棧。 else /讀入的整數(shù)等于-1時(shí)退棧。 if(top=0)printf(“?？課);exit(0); else printf(“出棧元素是%dn,stop-)； /算法結(jié)13、給定n個村莊之間的交通圖，假設(shè)村莊i和j之間有道路，那么將頂點(diǎn)i和j用邊連接，邊上的Wij表示這條道路的長度，現(xiàn)在要從這n個村莊中選擇一個村莊建一所醫(yī)院，問這所醫(yī)院應(yīng)建在哪個村莊，才能使離醫(yī)院最遠(yuǎn)的村莊到醫(yī)院的路程最短?試設(shè)計(jì)一個解答上述問題的算法，并應(yīng)用該算法解答如下列圖的實(shí)例。20分void Hospital(AdjMatrix w,int n) /在以鄰接帶權(quán)矩陣表

14、示的n個村莊中，求醫(yī)院建在何處，使離醫(yī)院最遠(yuǎn)的村莊到醫(yī)院的路徑最短。 for (k=1;k=n;k+) /求任意兩頂點(diǎn)間的最短路徑 for (i=1;i=n;i+) for (j=1;j=n;j+) if (wik+wkjwij) wij=wik+wkj; m=MAXINT; /設(shè)定m為機(jī)器內(nèi)最大整數(shù)。 for (i=1;i=n;i+) /求最長路徑中最短的一條。 s=0; for (j=1;j=n;j+) /求從某村莊i1=is) s=wij; if (s=m) m=s; k=i;/在最長路徑中，取最短的一條。m記最長路徑，k記出發(fā)頂點(diǎn)的下標(biāo)。 Printf(“醫(yī)院應(yīng)建在%d村莊，到醫(yī)院距離

15、為%dn,i,m); /for/算法結(jié)束對以上實(shí)例模擬的過程略。各行中最大數(shù)依次是9，9，6，7，9，9。這幾個最大數(shù)中最小者為6，故醫(yī)院應(yīng)建在第三個村莊中,離醫(yī)院最遠(yuǎn)的村莊到醫(yī)院的距離是6。1、對圖1所示的連通網(wǎng)G，請用Prim算法構(gòu)造其最小生成樹每選取一條邊畫一個圖。14、#define maxsize ?？臻g容量 void InOutS(int smaxsize) /s是元素為整數(shù)的棧，本算法進(jìn)行入棧和退棧操作。 int top=0; /top為棧頂指針，定義top=0時(shí)為棧空。 for(i=1; i=n; i+) /n個整數(shù)序列作處理。 scanf(“%d,&x); /從鍵盤讀入整數(shù)序列。 if(x!=-1) / 讀入的整數(shù)不等于-1時(shí)入棧。 if(top=maxs