2021年四川省C#語(yǔ)言綱要

1、2021年四川省c#語(yǔ)言綱要 2021年四川省c#語(yǔ)言綱要 1、二部圖（bipartite graph） g=（v，e）是一個(gè)能將其結(jié)點(diǎn)集v分為兩不相交子集v 1和v2=v-v1的無(wú)向圖，使得：v1中的任何兩個(gè)結(jié)點(diǎn)在圖g中均不相鄰，v2中的任何結(jié)點(diǎn)在圖g中也均不相鄰。 （1）請(qǐng)各舉一個(gè)結(jié)點(diǎn)個(gè)數(shù)為5的二部圖和非二部圖的例子。 （2）請(qǐng)用c或pascal編寫一個(gè)函數(shù)bipartite推斷一個(gè)連通無(wú)向圖g是否是二部圖，并分析程序的時(shí)間簡(jiǎn)單度。設(shè)g用二維數(shù)組a來(lái)表示，大小為n*n（n為結(jié)點(diǎn)個(gè)數(shù)）。請(qǐng)?jiān)诔绦蛑屑颖匾慕忉?。若有必要可直接利用堆棧或?duì)列操作。【 2、有一種簡(jiǎn)潔的排序算法，叫做計(jì)數(shù)排序（co

2、unt sorting）。這種排序算法對(duì)一個(gè)待排序的表(用數(shù)組表示)進(jìn)行排序，并將排序結(jié)果存放到另一個(gè)新的表中。必需留意的是，表中全部待排序的關(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)潔選擇排序相比較，這種方法是否更好?為什么? 3、我

3、們可用“破圈法”求解帶權(quán)連通無(wú)向圖的一棵最小代價(jià)生成樹(shù)。所謂“破圈法”就是“任取一圈，去掉圈上權(quán)最大的邊”，反復(fù)執(zhí)行這一步驟，直到?jīng)]有圈為止。請(qǐng)給出用“破圈法”求解給定的帶權(quán)連通無(wú)向圖的一棵最小代價(jià)生成樹(shù)的具體算法，并用程序?qū)崿F(xiàn)你所給出的算法。注：圈就是回路。 4、本題要求建立有序的循環(huán)鏈表。從頭到尾掃描數(shù)組a，取出ai（0=in）,然后到鏈表中去查找值為ai的結(jié)點(diǎn)，若查找失敗，則插入。 linkedlist creat(elemtype a,int n) /由含n個(gè)數(shù)據(jù)的數(shù)組a生成循環(huán)鏈表，要求鏈表有序并且無(wú)值重復(fù)結(jié)點(diǎn) linkedlist h; h=(linkedlist)malloc(s

4、izeof(lnode);/申請(qǐng)結(jié)點(diǎn) h-next=h; /形成空循環(huán)鏈表 for(i=0;in;i+) pre=h; p=h-next; while(p!=h p-dataai) pre=p; p=p-next; /查找ai的插入位置 if(p=h | p-data!=ai) /重復(fù)數(shù)據(jù)不再輸入 s=(linkedlist)malloc(sizeof(lnode); s-data=ai; pre-next=s; s-next=p;/將結(jié)點(diǎn)s鏈入鏈表中 /for return(h); 算法結(jié)束 5、兩棵空二叉樹(shù)或僅有根結(jié)點(diǎn)的二叉樹(shù)相像；對(duì)非空二叉樹(shù)，可判左右子樹(shù)是否相像，采納遞歸算法。 202

5、1年四川省c#語(yǔ)言綱要 int similar(bitree p,q) /推斷二叉樹(shù)p和q是否相像 if(p=null q=null) return (1); else if(!p q | p !q) return (0); else return(similar(p-lchild,q-lchild) similar(p-rchild,q-rchild) /結(jié)束similar 6、對(duì)二叉樹(shù)的某層上的結(jié)點(diǎn)進(jìn)行運(yùn)算，采納隊(duì)列結(jié)構(gòu)按層次遍歷最相宜。 int leafklevel(bitree bt, int k) /求二叉樹(shù)bt 的第k(k1) 層上葉子結(jié)點(diǎn)個(gè)數(shù) if(bt=null | k1) r

6、eturn(0); bitree p=bt,q; /q是隊(duì)列，元素是二叉樹(shù)結(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是二叉樹(shù)同層最右結(jié)點(diǎn)的指針，level 是二叉樹(shù)的層數(shù) while(front=rear) p=q+front; if(level=k !p-lchild !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+; /二叉樹(shù)同層最右結(jié)點(diǎn)已處理,層數(shù)增