2022福建省C卷加強(qiáng)

1、假設(shè)K1，…，Kn是n個(gè)關(guān)鍵詞，試解答：試用二叉查找樹的插入算法建立一棵二叉查找樹，即當(dāng)關(guān)鍵詞的插入次序?yàn)镵1，K2，…，Kn時(shí)，用算法建立一棵以LLINK/RLINK鏈接表示的二叉查找樹。2、兩棵空二叉樹或僅有根結(jié)點(diǎn)的二叉樹相似；對(duì)非空二叉樹，可判左右子樹是否相似，采用遞歸算法。intSimilar(BiTreep,q)//判斷二叉樹p和q是否相似{if(p==null&&q==null)return(1);elseif(!p&&q||p&&!q)return(0);elsereturn(Similar(p->lchild,q->lchild)&&Similar(p->rchild,q->rchild))}//結(jié)束Similar3、設(shè)從鍵盤輸入一整數(shù)的序列：a1,a2,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件物品中選擇若干件放入背包，使得放入的重量之和正好是S。設(shè)布爾函數(shù)Knap(S，n)表示背包問題的解，Wi(i=1,2,...，n)均為正整數(shù)，并已順序存儲(chǔ)地在數(shù)組W中。請(qǐng)?jiān)谙铝兴惴ǖ南聞澗€處填空，使其正確求解背包問題。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è)有一個(gè)順序棧S，元素s1,s2,s3,s4,s5,s6依次進(jìn)棧，如果6個(gè)元素的出棧順序?yàn)閟2,s3,s4,s6,s5,s1，則順序棧的容量至少應(yīng)為多少？畫出具體進(jìn)棧、出棧過程。假定采用帶頭結(jié)點(diǎn)的單鏈表保存單詞，當(dāng)兩個(gè)單詞有相同的后綴時(shí)，則可共享相同的后綴存儲(chǔ)空間。例如：設(shè)str1和str2是分別指向兩個(gè)單詞的頭結(jié)點(diǎn)，請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡可能的高效算法，找出兩個(gè)單詞共同后綴的起始位置，分析算法時(shí)間復(fù)雜度。將n(n>1)個(gè)整數(shù)存放到一維數(shù)組R中。設(shè)計(jì)一個(gè)盡可能高效（時(shí)間、空間）的算法，將R中保存的序列循環(huán)左移p（0<p<n）個(gè)位置，即將R中的數(shù)據(jù)（x0,x1,x2,…,xn-1），變換為(xp，xp＋1,…,xn-1,x0,x1,…,xp-1)。4、我們可用“破圈法”求解帶權(quán)連通無向圖的一棵最小代價(jià)生成樹。所謂“破圈法”就是“任取一圈，去掉圈上權(quán)最大的邊”，反復(fù)執(zhí)行這一步驟，直到?jīng)]有圈為止。請(qǐng)給出用“破圈法”求解給定的帶權(quán)連通無向圖的一棵最小代價(jià)生成樹的詳細(xì)算法，并用程序?qū)崿F(xiàn)你所給出的算法。注：圈就是回路。5、根據(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；//中序遍歷的第一個(gè)結(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é)束6、二路插入排序是將待排關(guān)鍵字序列r[1..n]中關(guān)鍵字分二路分別按序插入到輔助向量d[1..n]前半部和后半部（注:向量d可視為循環(huán)表），其原則為，先將r[l]賦給d[1]，再從r[2]記錄開始分二路插入。編寫實(shí)現(xiàn)二路插入排序算法。7、(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)stack[top]=p->rchild(3)top++(4)stack[top]=p->lchild27.(1)*ppos//根結(jié)點(diǎn)（2）rpos=ipos(3)rpos–ipos(4)ipos(5)ppos+18、設(shè)有一個(gè)數(shù)組中存放了一個(gè)無序的關(guān)鍵序列K1、K2、…、Kn?，F(xiàn)要求將Kn放在將元素排序后的正確位置上，試編寫實(shí)現(xiàn)該功能的算法，要求比較關(guān)鍵字的次數(shù)不超過n。51.借助于快速排序的算法思想，在一組無序的記錄中查找給定關(guān)鍵字值等于key的記錄。設(shè)此組記錄存放于數(shù)組r[l..h]中。若查找成功，則輸出該記錄在r數(shù)組中的位置及其值，否則顯示“notfind”信息。請(qǐng)編寫出算法并簡(jiǎn)要說明算法思想。9、證明由二叉樹的中序序列和后序序列，也可以唯一確定一棵二叉樹。當(dāng)n=1時(shí)，只有一個(gè)根結(jié)點(diǎn)，由中序序列和后序序列可以確定這棵二叉樹。設(shè)當(dāng)n=m-1時(shí)結(jié)論成立，現(xiàn)證明當(dāng)n=m時(shí)結(jié)論成立。設(shè)中序序列為S1，S2，…，Sm,后序序列是P1,P2,…，Pm。因后序序列最后一個(gè)元素Pm是根，則在中序序列中可找到與Pm相等的結(jié)點(diǎn)（設(shè)二叉樹中各結(jié)點(diǎn)互不相同）Si(1≤i≤m)，因中序序列是由中序遍歷而得，所以Si是根結(jié)點(diǎn)，S1，S2，…，Si-1是左子樹的中序序列，而Si+1,Si+2,…,Sm是右子樹的中序序列。typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}listnode;typedeflistnode*linklist;voidjose(linklisthead,ints,intm){linklistk1,pre,p;intcount=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ù)大于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(){linklisthead,p,r;intn,s,m,i;printf("n=");scanf("%d",&n);printf("s=");scanf("%d",&s);printf("m=",&m);scanf("%d",&m);if(n<1)printf("n<0");else{/*建表*/head=(linklist)malloc(sizeof(listnode));/*建第一個(gè)結(jié)點(diǎn)*/head->data=n;r=head;for(i=n-1