2023海南省數(shù)據(jù)簡(jiǎn)介加強(qiáng)

1、1、由二叉樹(shù)的前序遍歷和中序遍歷序列能確定唯一的一棵二叉樹(shù)，下面程序的作用是實(shí)現(xiàn)由某二叉樹(shù)的前序遍歷和中序遍歷序列，生成一棵用二叉鏈表表示的二叉樹(shù)并打印出后序遍歷序列，請(qǐng)寫(xiě)出程序所缺的語(yǔ)句。#define MAX 100typedef struct Nodechar info; struct Node *llink, *rlink; TNODE;char predMAX,inodMAX; main(int argc,int *argv) TNODE *root;if(argc3) exit 0;strcpy(pred,argv1); strcpy(inod,argv2);root=restor

2、e(pred,inod,strlen(pred);postorder(root);TNODE *restore(char *ppos,char *ipos,int n) TNODE *ptr； char *rpos; int k;if(ninfo=(1)_;for(2)_ ; rposllink=restore(ppos+1, (4)_,k );ptr-rlink=restore (5)_+k,rpos+1,n-1-k);return ptr;postorder(TNODE*ptr) if(ptr=NULL) return; postorder(ptr-llink); postorder(pt

3、r-rlink); printf(“%c,ptr-info); 2、對(duì)一般二叉樹(shù)，僅根據(jù)一個(gè)先序、中序、后序遍歷，不能確定另一個(gè)遍歷序列。但對(duì)于滿二叉樹(shù)，任一結(jié)點(diǎn)的左右子樹(shù)均含有數(shù)量相等的結(jié)點(diǎn)，根據(jù)此性質(zhì)，可將任一遍歷序列轉(zhuǎn)為另一遍歷序列即任一遍歷序列均可確定一棵二叉樹(shù)。void PreToPost(ElemType pre ,post,int l1,h1,l2,h2)/將滿二叉樹(shù)的先序序列轉(zhuǎn)為后序序列，l1,h1,l2,h2是序列初始和最后結(jié)點(diǎn)的下標(biāo)。if(h1=l1)posth2=prel1; /根結(jié)點(diǎn)half=(h1-l1)/2; /左或右子樹(shù)的結(jié)點(diǎn)數(shù)PreToPost(pre,post

4、,l1+1,l1+half,l2,l2+half-1) /將左子樹(shù)先序序列轉(zhuǎn)為后序序列PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1) /將右子樹(shù)先序序列轉(zhuǎn)為后序序列 /PreToPost32. .葉子結(jié)點(diǎn)只有在遍歷中才能知道，這里使用中序遞歸遍歷。設(shè)置前驅(qū)結(jié)點(diǎn)指針pre，初始為空。第一個(gè)葉子結(jié)點(diǎn)由指針head指向，遍歷到葉子結(jié)點(diǎn)時(shí)，就將它前驅(qū)的rchild指針指向它，最后葉子結(jié)點(diǎn)的rchild為空。LinkedList head,pre=null; /全局變量LinkedList InOrder(BiTree bt)/中序遍歷二叉樹(shù)bt，將葉子結(jié)點(diǎn)從

5、左到右鏈成一個(gè)單鏈表，表頭指針為head if(bt)InOrder(bt-lchild); /中序遍歷左子樹(shù) if(bt-lchild=null & bt-rchild=null) /葉子結(jié)點(diǎn) if(pre=null) head=bt; pre=bt; /處理第一個(gè)葉子結(jié)點(diǎn) elsepre-rchild=bt; pre=bt; /將葉子結(jié)點(diǎn)鏈入鏈表 InOrder(bt-rchild); /中序遍歷左子樹(shù) pre-rchild=null; /設(shè)置鏈表尾 return(head); /InOrder時(shí)間復(fù)雜度為O(n),輔助變量使用head和pre,?？臻g復(fù)雜度O(n)3、連通圖的生成樹(shù)包括圖

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

7、頂點(diǎn)，權(quán)值。 scanf(%d%d%d ,&edgei.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)，4、假設(shè)第n件物品能放入背包，那么問(wèn)題變?yōu)槟芊裨購(gòu)膎-1件物品中選出假設(shè)干

8、件放入背包這時(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)5、有一個(gè)帶頭結(jié)點(diǎn)的單鏈表，每個(gè)結(jié)點(diǎn)包括兩個(gè)域，一個(gè)是整型域info，另一個(gè)是指向下一個(gè)結(jié)點(diǎn)的指針域next。假設(shè)單鏈表已建立，設(shè)計(jì)算法刪除單鏈表中所有重復(fù)出現(xiàn)的結(jié)點(diǎn)，使得info域相等的結(jié)點(diǎn)只保存一個(gè)。#include typedef char datatype;typedef

9、struct node datatype data; struct node * next; listnode;typedef listnode* linklist;/*-*/* 刪除單鏈表中重復(fù)的結(jié)點(diǎn) */*-*/linklist deletelist(linklist head) listnode *p,*s,*q; p=head-next; while(p) s=p; q=p-next; while(q) if(q-data=p-data) s-next=q-next;free(q); q=s-next; else s=q; /*找與P結(jié)點(diǎn)值相同的結(jié)點(diǎn)*/ q=q-next; p=p-n

10、ext; return head; 6、此題要求建立有序的循環(huán)鏈表。從頭到尾掃描數(shù)組A，取出Ai0=inext=h; /形成空循環(huán)鏈表for(i=0;inext; while(p!=h & p-datanext; /查找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é)束7、數(shù)組A和B的元素分別有序，欲將兩數(shù)組合并到C數(shù)組，使C仍有序，應(yīng)將A和B拷貝到C，只要注意A和B數(shù)組指針

11、的使用，以及正確處理一數(shù)組讀完數(shù)據(jù)后將另一數(shù)組余下元素復(fù)制到C中即可。void union(int A,B,C,m,n)/整型數(shù)組A和B各有m和n個(gè)元素，前者遞增有序，后者遞減有序，本算法將A和B歸并為遞增有序的數(shù)組C。i=0; j=n-1; k=0;/ i，j，k分別是數(shù)組A,B和C的下標(biāo)，因用C描述，下標(biāo)從0開(kāi)始while(i=0) if(aibj) ck+=ai+ else ck+=bj-;while(i=0) ck+=bj-;算法結(jié)束4、要求二叉樹(shù)按二叉鏈表形式存儲(chǔ)。15分1寫(xiě)一個(gè)建立二叉樹(shù)的算法。2寫(xiě)一個(gè)判別給定的二叉樹(shù)是否是完全二叉樹(shù)的算法。BiTree Creat() /建立二叉

12、樹(shù)的二叉鏈表形式的存儲(chǔ)結(jié)構(gòu)ElemType x；BiTree bt;scanf(“%d,&x); /此題假定結(jié)點(diǎn)數(shù)據(jù)域?yàn)檎蚷f(x=0) bt=null;else if(x0) bt=(BiNode *)malloc(sizeof(BiNode);bt-data=x; bt-lchild=creat(); bt-rchild=creat(); else error(“輸入錯(cuò)誤)；return(bt);/結(jié)束 BiTreeint JudgeComplete(BiTree bt) /判斷二叉樹(shù)是否是完全二叉樹(shù),如是，返回1，否那么，返回0int tag=0; BiTree p=bt, Q; /

13、Q是隊(duì)列，元素是二叉樹(shù)結(jié)點(diǎn)指針，容量足夠大if(p=null) return (1);QueueInit(Q); QueueIn(Q,p); /初始化隊(duì)列，根結(jié)點(diǎn)指針入隊(duì)while (!QueueEmpty(Q)p=QueueOut(Q); /出隊(duì) if (p-lchild & !tag) QueueIn(Q,p-lchild); /左子女入隊(duì) else if (p-lchild) return 0; /前邊已有結(jié)點(diǎn)為空，本結(jié)點(diǎn)不空 else tag=1; /首次出現(xiàn)結(jié)點(diǎn)為空 if (p-rchild & !tag) QueueIn(Q,p-rchild); /右子女入隊(duì) else if (p

14、-rchild) return 0; else tag=1; /whilereturn 1; /JudgeComplete8、二叉樹(shù)的層次遍歷序列的第一個(gè)結(jié)點(diǎn)是二叉樹(shù)的根。實(shí)際上，層次遍歷序列中的每個(gè)結(jié)點(diǎn)都是“局部根。確定根后，到二叉樹(shù)的中序序列中，查到該結(jié)點(diǎn)，該結(jié)點(diǎn)將二叉樹(shù)分為“左根右三局部。假設(shè)左、右子樹(shù)均有，那么層次序列根結(jié)點(diǎn)的后面應(yīng)是左右子樹(shù)的根；假設(shè)中序序列中只有左子樹(shù)或只有右子樹(shù)，那么在層次序列的根結(jié)點(diǎn)后也只有左子樹(shù)的根或右子樹(shù)的根。這樣，定義一個(gè)全局變量指針R，指向?qū)哟涡蛄写幚碓亍Ｋ惴ㄖ邢忍幚砀Y(jié)點(diǎn)，將根結(jié)點(diǎn)和左右子女的信息入隊(duì)列。然后，在隊(duì)列不空的條件下，循環(huán)處理二叉樹(shù)的結(jié)

15、點(diǎn)。隊(duì)列中元素的數(shù)據(jù)結(jié)構(gòu)定義如下：typedef struct int lvl; /層次序列指針，總是指向當(dāng)前“根結(jié)點(diǎn)在層次序列中的位置int l,h; /中序序列的下上界int f; /層次序列中當(dāng)前“根結(jié)點(diǎn)的雙親結(jié)點(diǎn)的指針int lr; / 1雙親的左子樹(shù) 2雙親的右子樹(shù)qnode; BiTree Creat(datatype in,level,int n)/由二叉樹(shù)的層次序列l(wèi)eveln和中序序列inn生成二叉樹(shù)。 n是二叉樹(shù)的結(jié)點(diǎn)數(shù)if (ndata=level0; p-lchild=null; p-rchild=null; /填寫(xiě)該結(jié)點(diǎn)數(shù)據(jù)for (i=0; ilchild=null

16、; s.lvl=+R; s.l=i+1; s.h=n-1; s.f=p; s.lr=2; enqueue(Q,s); else if (i=n-1) /根結(jié)點(diǎn)無(wú)右子樹(shù)，遍歷序列的1n-1是左子樹(shù)p-rchild=null; s.lvl=+R; s.l=1; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s); else /根結(jié)點(diǎn)有左子樹(shù)和右子樹(shù)s.lvl=+R; s.l=0; s.h=i-1; s.f=p; s.lr=1;enqueue(Q,s);/左子樹(shù)有關(guān)信息入隊(duì)列s.lvl=+R; s.l=i+1;s.h=n-1;s.f=p; s.lr=2;enqueue(Q,s)

17、;/右子樹(shù)有關(guān)信息入隊(duì)列while (!empty(Q) /當(dāng)隊(duì)列不空，進(jìn)行循環(huán)，構(gòu)造二叉樹(shù)的左右子樹(shù) s=delqueue(Q); father=s.f; for (i=s.l; idata=levels.lvl; p-lchild=null; p-rchild=null; /填寫(xiě)該結(jié)點(diǎn)數(shù)據(jù) if (s.lr=1) father-lchild=p; else father-rchild=p； /讓雙親的子女指針指向該結(jié)點(diǎn) if (i=s.l) p-lchild=null; /處理無(wú)左子女s.lvl=+R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); else

18、if (i=s.h) p-rchild=null; /處理無(wú)右子女 s.lvl=+R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s); elses.lvl=+R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s);/左子樹(shù)有關(guān)信息入隊(duì)列 s.lvl=+R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); /右子樹(shù)有關(guān)信息入隊(duì)列 /結(jié)束while (!empty(Q)return(p);/算法結(jié)束9、假設(shè)K1，Kn是n個(gè)關(guān)鍵詞，試解答：試用二叉查找樹(shù)的插入算法建立一棵二叉查找樹(shù)，即當(dāng)關(guān)鍵詞的插入次序?yàn)镵1，K2，Kn

19、時(shí)，用算法建立一棵以LLINK / RLINK 鏈接表示的二叉查找樹(shù)。10、在有向圖G中，如果r到G中的每個(gè)結(jié)點(diǎn)都有路徑可達(dá)，那么稱結(jié)點(diǎn)r為G的根結(jié)點(diǎn)。編寫(xiě)一個(gè)算法完成以下功能：1建立有向圖G的鄰接表存儲(chǔ)結(jié)構(gòu)；2判斷有向圖G是否有根，假設(shè)有，那么打印出所有根結(jié)點(diǎn)的值。11、4、void LinkList_reverse(Linklist &L) /鏈表的就地逆置;為簡(jiǎn)化算法,假設(shè)表長(zhǎng)大于2 p=L-next;q=p-next;s=q-next;p-next=NULL; while(s-next) q-next=p;p=q; q=s;s=s-next; /把L的元素逐個(gè)插入新表表頭 q-next

20、=p;s-next=q;L-next=s;/LinkList_reverse12、請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，要求該算法把二叉樹(shù)的葉子結(jié)點(diǎn)按從左到右的順序連成一個(gè)單鏈表，表頭指針為head。二叉樹(shù)按二叉鏈表方式存儲(chǔ)，鏈接時(shí)用葉子結(jié)點(diǎn)的右指針域來(lái)存放單鏈表指針。分析你的算法的時(shí)、空復(fù)雜度。13、對(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) return(0); BiTree p=bt,Q; /Q是隊(duì)列，元素是二叉樹(shù)結(jié)點(diǎn)指針,容量足夠大int fr

21、ont=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(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+; /二叉樹(shù)同層最右結(jié)點(diǎn)已處理,層數(shù)增1 last=rear; /last移到指向下層最右一元素if(levelk) return (leaf); /層數(shù)大于k 后退出運(yùn)行 /while /結(jié)束LeafKLevel14、假設(shè)以鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)，編寫(xiě)算法判別在給定的有向圖中是否存在一個(gè)簡(jiǎn)單有向回路，假設(shè)存在，那么以頂點(diǎn)序列的方式輸出該回路找到一條即可。注：圖中不存在頂點(diǎn)到自己的弧有向圖判斷回路要比無(wú)向圖復(fù)雜。利用深度優(yōu)先遍歷，將頂點(diǎn)分成三類(lèi)：未訪問(wèn)；已訪問(wèn)但其鄰接點(diǎn)未訪問(wèn)完;已訪問(wèn)且其鄰接點(diǎn)已訪問(wèn)完。下面用0，1，2表示這三種狀態(tài)。前面已提到，假設(shè)dfsv結(jié)束前出現(xiàn)頂點(diǎn)u到v的回邊，那么圖中必有包含頂點(diǎn)