2023陜西省數(shù)據(jù)要領(lǐng)基礎(chǔ)

1、1、我們用l代表最長(zhǎng)平臺(tái)的長(zhǎng)度，用k指示最長(zhǎng)平臺(tái)在數(shù)組b中的起始位置下標(biāo)。用j記住局部平臺(tái)的起始位置，用i指示掃描b數(shù)組的下標(biāo)，i從0開始，依次和后續(xù)元素比較，假設(shè)局部平臺(tái)長(zhǎng)度i-j大于l時(shí)，那么修改最長(zhǎng)平臺(tái)的長(zhǎng)度kl=i-j和其在b中的起始位置k=j，直到b數(shù)組結(jié)束，l即為所求。void Platform (int b , int N) /求具有N個(gè)元素的整型數(shù)組b中最長(zhǎng)平臺(tái)的長(zhǎng)度。l=1;k=0;j=0;i=0;while(in-1)while(il) l=i-j+1;k=j; /局部最長(zhǎng)平臺(tái)i+; j=i; /新平臺(tái)起點(diǎn)printf(“最長(zhǎng)平臺(tái)長(zhǎng)度%d，在b數(shù)組中起始下標(biāo)為%d，l，k)

2、；/ Platform2、給定n個(gè)村莊之間的交通圖，假設(shè)村莊i和j之間有道路，那么將頂點(diǎn)i和j用邊連接，邊上的Wij表示這條道路的長(zhǎng)度，現(xiàn)在要從這n個(gè)村莊中選擇一個(gè)村莊建一所醫(yī)院，問這所醫(yī)院應(yīng)建在哪個(gè)村莊，才能使離醫(yī)院最遠(yuǎn)的村莊到醫(yī)院的路程最短?試設(shè)計(jì)一個(gè)解答上述問題的算法，并應(yīng)用該算法解答如下列圖的實(shí)例。20分void Hospital(AdjMatrix w,int n) /在以鄰接帶權(quán)矩陣表示的n個(gè)村莊中，求醫(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+)

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

4、1所示的連通網(wǎng)G，請(qǐng)用Prim算法構(gòu)造其最小生成樹每選取一條邊畫一個(gè)圖。3、將頂點(diǎn)放在兩個(gè)集合V1和V2。對(duì)每個(gè)頂點(diǎn)，檢查其和鄰接點(diǎn)是否在同一個(gè)集合中，如是，那么為非二部圖。為此，用整數(shù)1和2表示兩個(gè)集合。再用一隊(duì)列結(jié)構(gòu)存放圖中訪問的頂點(diǎn)。 int BPGraph (AdjMatrix g) /判斷以鄰接矩陣表示的圖g是否是二部圖。 int s; /頂點(diǎn)向量，元素值表示其屬于那個(gè)集合值1和2表示兩個(gè)集合 int Q;/Q為隊(duì)列，元素為圖的頂點(diǎn)，這里設(shè)頂點(diǎn)信息就是頂點(diǎn)編號(hào)。 int f=0,r,visited; /f和r分別是隊(duì)列的頭尾指針,visited是訪問數(shù)組 for (i=1;i=n;i

5、+) visitedi=0;si=0; /初始化，各頂點(diǎn)未確定屬于那個(gè)集合 Q1=1; r=1; s1=1;/頂點(diǎn)1放入集合S1while(fr) v=Q+f; if (sv=1) jh=2; else jh=1;/準(zhǔn)備v的鄰接點(diǎn)的集合號(hào) if (!visitedv) visitedv=1; /確保對(duì)每一個(gè)頂點(diǎn)，都要檢查與其鄰接點(diǎn)不應(yīng)在一個(gè)集合中for (j=1,j0個(gè)人按順時(shí)針方向圍坐成一圈，現(xiàn)從第s個(gè)人開始按順時(shí)針方向報(bào)數(shù)，數(shù)到第m個(gè)人出列，然后從出列的下一個(gè)人重新開始報(bào)數(shù)，數(shù)到第m的人又出列，如此重復(fù)直到所有的人全部出列為止。現(xiàn)要求采用循環(huán)鏈表結(jié)構(gòu)設(shè)計(jì)一個(gè)算法，模擬此過程。#includ

6、etypedef int datatype;typedef struct nodedatatype data; struct node *next;listnode;typedef listnode *linklist;void jose(linklist head,int s,int m)linklist k1,pre,p; int count=1; pre=NULL; k1=head; /*k1為報(bào)數(shù)的起點(diǎn)*/ while (count!=s) /*找初始報(bào)數(shù)起點(diǎn)*/ pre=k1; k1=k1-next; count+; while(k1-next!=k1) /*當(dāng)循環(huán)鏈表中的結(jié)點(diǎn)個(gè)數(shù)大

7、于1時(shí)*/ p=k1; /*從k1開始報(bào)數(shù)*/ count=1; while (count!=m) /*連續(xù)數(shù)m個(gè)結(jié)點(diǎn)*/ pre=p; p=p-next; count+; pre-next=p-next; /*輸出該結(jié)點(diǎn)，并刪除該結(jié)點(diǎn)*/ printf(%4d,p-data); free(p); k1=pre-next; /*新的報(bào)數(shù)起點(diǎn)*/ printf(%4d,k1-data); /*輸出最后一個(gè)結(jié)點(diǎn)*/ free(k1);main()linklist head,p,r; int n,s,m,i; printf(n=); scanf(%d,&n); printf(s=); scanf(%

8、d,&s); printf(m=,&m); scanf(%d,&m); if (n1) printf(ndata=n; r=head; for (i=n-1;i0;i-) /*建立剩余n-1個(gè)結(jié)點(diǎn)*/ p=(linklist)malloc(sizeof(listnode); p-data=i; p-next=head; head=p; r-next=head; /*生成循環(huán)鏈表*/ jose(head,s,m); /*調(diào)用函數(shù)*/ 6、有一種簡(jiǎn)單的排序算法，叫做計(jì)數(shù)排序count sorting。這種排序算法對(duì)一個(gè)待排序的表(用數(shù)組表示)進(jìn)行排序，并將排序結(jié)果存放到另一個(gè)新的表中。必須注意的是

9、，表中所有待排序的關(guān)鍵碼互不相同，計(jì)數(shù)排序算法針對(duì)表中的每個(gè)記錄，掃描待排序的表一趟，統(tǒng)計(jì)表中有多少個(gè)記錄的關(guān)鍵碼比該記錄的關(guān)鍵碼小，假設(shè)針對(duì)某一個(gè)記錄，統(tǒng)計(jì)出的計(jì)數(shù)值為c，那么，這個(gè)記錄在新的有序表中的適宜的存放位置即為c。 (1) (3分)給出適用于計(jì)數(shù)排序的數(shù)據(jù)表定義; (2) (7分)使用Pascal或C語(yǔ)言編寫實(shí)現(xiàn)計(jì)數(shù)排序的算法； (3) (4分)對(duì)于有n個(gè)記錄的表，關(guān)鍵碼比較次數(shù)是多少? (4) (3分)與簡(jiǎn)單項(xiàng)選擇擇排序相比較，這種方法是否更好?為什么?7、給出折半查找的遞歸算法，并給出算法時(shí)間復(fù)雜度性分析。8、連通圖的生成樹包括圖中的全部n個(gè)頂點(diǎn)和足以使圖連通的n-1條邊，最小

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

11、gei.i ,&edgei.j ,&edgei.w); for (i=2;i=e;i+) /按邊上的權(quán)值大小，對(duì)邊進(jìn)行逆序排序。 edge0=edgei; j=i-1;while (edgej.w=n) /破圈，直到邊數(shù)e=n-1. if (connect(k) /刪除第k條邊假設(shè)仍連通。 edgek.w=0; eg-; /測(cè)試下一條邊edgek，權(quán)值置0表示該邊被刪除k+; /下條邊 /while /算法結(jié)束。 connect()是測(cè)試圖是否連通的函數(shù)，可用圖的遍歷實(shí)現(xiàn)，9、設(shè)T是一棵滿二叉樹，編寫一個(gè)將T的先序遍歷序列轉(zhuǎn)換為后序遍歷序列的遞歸算法。10、設(shè)從鍵盤輸入一整數(shù)的序列：a1, a

12、2, a3，an,試編寫算法實(shí)現(xiàn)：用棧結(jié)構(gòu)存儲(chǔ)輸入的整數(shù)，當(dāng)ai-1時(shí)，將ai進(jìn)棧；當(dāng)ai=-1時(shí)，輸出棧頂整數(shù)并出棧。算法應(yīng)對(duì)異常情況入棧滿等給出相應(yīng)的信息。設(shè)有一個(gè)背包可以放入的物品重量為S，現(xiàn)有n件物品，重量分別為W1，W2，.，Wn。問能否從這n件物品中選擇假設(shè)干件放入背包，使得放入的重量之和正好是S。設(shè)布爾函數(shù)Knap(S，n)表示背包問題的解，Wi(i=1,2,.，n)均為正整數(shù)，并已順序存儲(chǔ)地在數(shù)組W中。請(qǐng)?jiān)谝韵滤惴ǖ南聞澗€處填空，使其正確求解背包問題。Knap(S，n)假設(shè)S=0那么Knaptrue否那么假設(shè)S0且n1)個(gè)整數(shù)存放到一維數(shù)組R中。設(shè)計(jì)一個(gè)盡可能高效時(shí)間、空間的算

13、法，將R中保存的序列循環(huán)左移p0pn個(gè)位置，即將R中的數(shù)據(jù)x0, x1, x2, xn-1，變換為(xp， xp1, , xn-1 ,x0 , x1, xp-1)。11、假設(shè)第n件物品能放入背包，那么問題變?yōu)槟芊裨購(gòu)膎-1件物品中選出假設(shè)干件放入背包這時(shí)背包可放入物品的重量變?yōu)閟-wn。假設(shè)第n件物品不能放入背包，那么考慮從n-1件物品選假設(shè)干件放入背包這時(shí)背包可放入物品仍為s。假設(shè)最終s=0,那么有一解；否那么，假設(shè)s0但物品數(shù)n1,那么無(wú)解。1s-wn,n-1 /Knap(s-wn,n-1)=true2s,n-1 / KnapKnap(s,n-1)12、假設(shè)第n件物品能放入背包，那么問題變

14、為能否再?gòu)膎-1件物品中選出假設(shè)干件放入背包這時(shí)背包可放入物品的重量變?yōu)閟-wn。假設(shè)第n件物品不能放入背包，那么考慮從n-1件物品選假設(shè)干件放入背包這時(shí)背包可放入物品仍為s。假設(shè)最終s=0,那么有一解；否那么，假設(shè)s0但物品數(shù)n1,那么無(wú)解。1s-wn,n-1 /Knap(s-wn,n-1)=true2s,n-1 / KnapKnap(s,n-1)13、編程實(shí)現(xiàn)單鏈表的就地逆置。23在數(shù)組 A1.n中有n個(gè)數(shù)據(jù)，試建立一個(gè)帶有頭結(jié)點(diǎn)的循環(huán)鏈表，頭指針為h，要求鏈中數(shù)據(jù)從小到大排列，重復(fù)的數(shù)據(jù)在鏈中只保存一個(gè).14、假設(shè)以鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)，編寫算法判別在給定的有向圖中是否存在一個(gè)簡(jiǎn)單有

15、向回路，假設(shè)存在，那么以頂點(diǎn)序列的方式輸出該回路找到一條即可。注：圖中不存在頂點(diǎn)到自己的弧有向圖判斷回路要比無(wú)向圖復(fù)雜。利用深度優(yōu)先遍歷，將頂點(diǎn)分成三類：未訪問；已訪問但其鄰接點(diǎn)未訪問完;已訪問且其鄰接點(diǎn)已訪問完。下面用0，1，2表示這三種狀態(tài)。前面已提到，假設(shè)dfsv結(jié)束前出現(xiàn)頂點(diǎn)u到v的回邊，那么圖中必有包含頂點(diǎn)v和u的回路。對(duì)應(yīng)程序中v的狀態(tài)為1，而u是正訪問的頂點(diǎn)，假設(shè)我們找出u的下一鄰接點(diǎn)的狀態(tài)為1，就可以輸出回路了。void Print(int v,int start ) /輸出從頂點(diǎn)start開始的回路。for(i=1;i=n;i+) if(gvi!=0 & visitedi=1

16、 ) /假設(shè)存在邊v,i，且頂點(diǎn)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) 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;i1) 層上葉子結(jié)點(diǎn)個(gè)數(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ì)尾指針, leaf是葉子結(jié)點(diǎn)數(shù)int last=1,level=1; Q1=p; /last是二叉樹同層最右結(jié)