2010安徽省數(shù)據(jù)簡介入門

1、本題要求建立有序的循環(huán)鏈表。從頭到尾掃描數(shù)組A，取出A[i]（0<=i<n）,然后到鏈表中去查找值為A[i]的結(jié)點(diǎn)，若查找失敗，則插入。LinkedListcreat(ElemTypeA[],intn)//由含n個數(shù)據(jù)的數(shù)組A生成循環(huán)鏈表，要求鏈表有序并且無值重復(fù)結(jié)點(diǎn){LinkedListh;h=(LinkedList)malloc(sizeof(LNode));//申請結(jié)點(diǎn)h->next=h;//形成空循環(huán)鏈表for(i=0;i<n;i++){pre=h;p=h->next;while(p!=h&&p->data<A[i]){pre=p;p=p->next;}//查找A[i]的插入位置if(p==h||p->data!=A[i])//重復(fù)數(shù)據(jù)不再輸入{s=(LinkedList)malloc(sizeof(LNode));s->data=A[i];pre->next=s;s->next=p;//將結(jié)點(diǎn)s鏈入鏈表中}}//forreturn(h);}算法結(jié)束2、二部圖（bipartitegraph）G=（V，E）是一個能將其結(jié)點(diǎn)集V分為兩不相交子集V1和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是否是二部圖，并分析程序的時間復(fù)雜度。設(shè)G用二維數(shù)組A來表示，大小為n*n（n為結(jié)點(diǎn)個數(shù)）。請在程序中加必要的注釋。若有必要可直接利用堆?；蜿犃胁僮??！?、根據(jù)二叉排序樹中序遍歷所得結(jié)點(diǎn)值為增序的性質(zhì)，在遍歷中將當(dāng)前遍歷結(jié)點(diǎn)與其前驅(qū)結(jié)點(diǎn)值比較，即可得出結(jié)論，為此設(shè)全局指針變量pre（初值為null）和全局變量flag，初值為true。若非二叉排序樹，則置flag為false。#definetrue1#definefalse0typedefstructnode{datatypedata;structnode*llink,*rlink;}*BTree;voidJudgeBST（BTreet,intflag）//判斷二叉樹是否是二叉排序樹，本算法結(jié)束后，在調(diào)用程序中由flag得出結(jié)論。{if（t!=null&&flag）{Judgebst（t->llink,flag）；//中序遍歷左子樹if（pre==null）pre=t；//中序遍歷的第一個結(jié)點(diǎn)不必判斷elseif（pre->data<t->data）pre=t；//前驅(qū)指針指向當(dāng)前結(jié)點(diǎn)else{flag=flase；}//不是完全二叉樹Judgebst（t->rlink,flag）；//中序遍歷右子樹}//JudgeBST算法結(jié)束4、數(shù)組A和B的元素分別有序，欲將兩數(shù)組合并到C數(shù)組，使C仍有序，應(yīng)將A和B拷貝到C，只要注意A和B數(shù)組指針的使用，以及正確處理一數(shù)組讀完數(shù)據(jù)后將另一數(shù)組余下元素復(fù)制到C中即可。voidunion(intA[],B[],C[],m,n)//整型數(shù)組A和B各有m和n個元素，前者遞增有序，后者遞減有序，本算法將A和B歸并為遞增有序的數(shù)組C。{i=0;j=n-1;k=0;//i，j，k分別是數(shù)組A,B和C的下標(biāo)，因用C描述，下標(biāo)從0開始while(i<m&&j>=0)if(a[i]<b[j])c[k++]=a[i++]elsec[k++]=b[j--];while(i<m)c[k++]=a[i++];while(j>=0)c[k++]=b[j--];}算法結(jié)束4、要求二叉樹按二叉鏈表形式存儲。15分（1）寫一個建立二叉樹的算法。（2）寫一個判別給定的二叉樹是否是完全二叉樹的算法。BiTreeCreat()//建立二叉樹的二叉鏈表形式的存儲結(jié)構(gòu){ElemTypex；BiTreebt;scanf(“%d”,&x);//本題假定結(jié)點(diǎn)數(shù)據(jù)域?yàn)檎蚷f(x==0)bt=null;elseif(x>0){bt=(BiNode*)malloc(sizeof(BiNode));bt->data=x;bt->lchild=creat();bt->rchild=creat();}elseerror(“輸入錯誤”)；return(bt);}//結(jié)束BiTreeintJudgeComplete(BiTreebt)//判斷二叉樹是否是完全二叉樹,如是，返回1，否則，返回0{inttag=0;BiTreep=bt,Q[];//Q是隊列，元素是二叉樹結(jié)點(diǎn)指針，容量足夠大if(p==null)return(1);QueueInit(Q);QueueIn(Q,p);//初始化隊列，根結(jié)點(diǎn)指針入隊while(!QueueEmpty(Q)){p=QueueOut(Q);//出隊if(p->lchild&&!tag)QueueIn(Q,p->lchild);//左子女入隊else{if(p->lchild)return0;//前邊已有結(jié)點(diǎn)為空，本結(jié)點(diǎn)不空elsetag=1;//首次出現(xiàn)結(jié)點(diǎn)為空if(p->rchild&&!tag)QueueIn(Q,p->rchild);//右子女入隊elseif(p->rchild)return0;elsetag=1;}//whilereturn1;}//JudgeComplete5、給定n個村莊之間的交通圖，若村莊i和j之間有道路，則將頂點(diǎn)i和j用邊連接，邊上的Wij表示這條道路的長度，現(xiàn)在要從這n個村莊中選擇一個村莊建一所醫(yī)院，問這所醫(yī)院elsetag=1;//首次出現(xiàn)結(jié)點(diǎn)為空if(p->rchild&&!tag)QueueIn(Q,p->rchild);//右子女入隊elseif(p->rchild)return0;elsetag=1;}//whilereturn1;}//JudgeComplete8、設(shè)從鍵盤輸入一整數(shù)的序列：a1,a2,a3，…，an,試編寫算法實(shí)現(xiàn)：用棧結(jié)構(gòu)存儲輸入的整數(shù)，當(dāng)ai≠-1時，將ai進(jìn)棧；當(dāng)ai=-1時，輸出棧頂整數(shù)并出棧。算法應(yīng)對異常情況（入棧滿等）給出相應(yīng)的信息。設(shè)有一個背包可以放入的物品重量為S，現(xiàn)有n件物品，重量分別為W1，W2，...，Wn。問能否從這n件物品中選擇若干件放入背包，使得放入的重量之和正好是S。設(shè)布爾函數(shù)Knap(S，n)表示背包問題的解，Wi(i=1,2,...，n)均為正整數(shù)，并已順序存儲地在數(shù)組W中。請在下列算法的下劃線處填空，使其正確求解背包問題。Knap(S，n)若S=0則Knap←true否則若（S<0）或(S>0且n<1)則Knap←false否則若Knap(1),_=true則print(W[n])；Knap←true否則Knap←Knap(2)_,_設(shè)有一個順序棧S，元素s1,s2,s3,s4,s5,s6依次進(jìn)棧，如果6個元素的出棧順序?yàn)閟2,s3,s4,s6,s5,s1，則順序棧的容量至少應(yīng)為多少？畫出具體進(jìn)棧、出棧過程。假定采用帶頭結(jié)點(diǎn)的單鏈表保存單詞，當(dāng)兩個單詞有相同的后綴時，則可共享相同的后綴存儲空間。例如：設(shè)str1和str2是分別指向兩個單詞的頭結(jié)點(diǎn)，請設(shè)計一個盡可能的高效算法，找出兩個單詞共同后綴的起始位置，分析算法時間復(fù)雜度。將n(n>1)個整數(shù)存放到一維數(shù)組R中。設(shè)計一個盡可能高效（時間、空間）的算法，將R中保存的序列循環(huán)左移p（0<p<n）個位置，即將R中的數(shù)據(jù)（x0,x1,x2,…,xn-1），變換為(xp，xp＋1,…,xn-1,x0,x1,…,xp-1)。9、連通圖的生成樹包括圖中的全部n個頂點(diǎn)和足以使圖連通的n-1條邊，最小生成樹是邊上權(quán)值之和最小的生成樹。故可按權(quán)值從大到小對邊進(jìn)行排序，然后從大到小將邊刪除。每刪除一條當(dāng)前權(quán)值最大的邊后，就去測試圖是否仍連通，若不再連通，則將該邊恢復(fù)。若仍連通，繼續(xù)向下刪；直到剩n-1條邊為止。voidSpnTree(AdjListg)//用“破圈法”求解帶權(quán)連通無向圖的一棵最小代價生成樹。{typedefstruct{inti,j,w}node;//設(shè)頂點(diǎn)信息就是頂點(diǎn)編號，權(quán)是整型數(shù)nodeedge[];scanf("%d%d",&e,&n);//輸入邊數(shù)和頂點(diǎn)數(shù)。for(i=1;i<=e;i++)//輸入e條邊：頂點(diǎn)，權(quán)值。scanf("%d%d%d",&edge[i].i,&edge[i].j,&edge[i].w);for(i=2;i<=e;i++)//按邊上的權(quán)值大小，對邊進(jìn)行逆序排序。{edge[0]=edge[i];j=i-1;while(edge[j].w<edge[0].w)edge[j+1]=edge[j--];edge[j+1]=edge[0];}//fork=1;eg=e;while(eg>=n)//破圈，直到邊數(shù)e=n-1.{if(connect(k))//刪除第k條邊若仍連通。{edge[k].w=0;eg--;}//測試下一條邊edge[k]，權(quán)值置0表示該邊被