2023海南省數(shù)據(jù)簡介加強

1、1、由二叉樹的前序遍歷和中序遍歷序列能確定唯一的一棵二叉樹，下面程序的作用是實現(xiàn)由某二叉樹的前序遍歷和中序遍歷序列，生成一棵用二叉鏈表表示的二叉樹并打印出后序遍歷序列，請寫出程序所缺的語句。#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、對一般二叉樹，僅根據(jù)一個先序、中序、后序遍歷，不能確定另一個遍歷序列。但對于滿二叉樹，任一結(jié)點的左右子樹均含有數(shù)量相等的結(jié)點，根據(jù)此性質(zhì)，可將任一遍歷序列轉(zhuǎn)為另一遍歷序列即任一遍歷序列均可確定一棵二叉樹。void PreToPost(ElemType pre ,post,int l1,h1,l2,h2)/將滿二叉樹的先序序列轉(zhuǎn)為后序序列，l1,h1,l2,h2是序列初始和最后結(jié)點的下標。if(h1=l1)posth2=prel1; /根結(jié)點half=(h1-l1)/2; /左或右子樹的結(jié)點數(shù)PreToPost(pre,post

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

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

6、中的全部n個頂點和足以使圖連通的n-1條邊，最小生成樹是邊上權(quán)值之和最小的生成樹。故可按權(quán)值從大到小對邊進行排序，然后從大到小將邊刪除。每刪除一條當前權(quán)值最大的邊后，就去測試圖是否仍連通，假設(shè)不再連通，那么將該邊恢復(fù)。假設(shè)仍連通，繼續(xù)向下刪；直到剩n-1條邊為止。 void SpnTree (AdjList g) /用“破圈法求解帶權(quán)連通無向圖的一棵最小代價生成樹。typedef struct int i,j,wnode; /設(shè)頂點信息就是頂點編號，權(quán)是整型數(shù) node edge; scanf( %d%d,&e,&n) ; /輸入邊數(shù)和頂點數(shù)。 for (i=1;i=e;i+) /輸入e條邊：

7、頂點，權(quán)值。 scanf(%d%d%d ,&edgei.i ,&edgei.j ,&edgei.w); for (i=2;i=e;i+) /按邊上的權(quán)值大小，對邊進行逆序排序。 edge0=edgei; j=i-1;while (edgej.w=n) /破圈，直到邊數(shù)e=n-1. if (connect(k) /刪除第k條邊假設(shè)仍連通。 edgek.w=0; eg-; /測試下一條邊edgek，權(quán)值置0表示該邊被刪除k+; /下條邊 /while /算法結(jié)束。 connect()是測試圖是否連通的函數(shù)，可用圖的遍歷實現(xiàn)，4、假設(shè)第n件物品能放入背包，那么問題變?yōu)槟芊裨購膎-1件物品中選出假設(shè)干

8、件放入背包這時背包可放入物品的重量變?yōu)閟-wn。假設(shè)第n件物品不能放入背包，那么考慮從n-1件物品選假設(shè)干件放入背包這時背包可放入物品仍為s。假設(shè)最終s=0,那么有一解；否那么，假設(shè)s0但物品數(shù)n1,那么無解。1s-wn,n-1 /Knap(s-wn,n-1)=true2s,n-1 / KnapKnap(s,n-1)5、有一個帶頭結(jié)點的單鏈表，每個結(jié)點包括兩個域，一個是整型域info，另一個是指向下一個結(jié)點的指針域next。假設(shè)單鏈表已建立，設(shè)計算法刪除單鏈表中所有重復(fù)出現(xiàn)的結(jié)點，使得info域相等的結(jié)點只保存一個。#include typedef char datatype;typedef

9、struct node datatype data; struct node * next; listnode;typedef listnode* linklist;/*-*/* 刪除單鏈表中重復(fù)的結(jié)點 */*-*/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é)點值相同的結(jié)點*/ 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é)點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個元素，前者遞增有序，后者遞減有序，本算法將A和B歸并為遞增有序的數(shù)組C。i=0; j=n-1; k=0;/ i，j，k分別是數(shù)組A,B和C的下標，因用C描述，下標從0開始while(i=0) if(aibj) ck+=ai+ else ck+=bj-;while(i=0) ck+=bj-;算法結(jié)束4、要求二叉樹按二叉鏈表形式存儲。15分1寫一個建立二叉樹的算法。2寫一個判別給定的二叉樹是否是完全二叉樹的算法。BiTree Creat() /建立二叉

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

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

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

15、點。隊列中元素的數(shù)據(jù)結(jié)構(gòu)定義如下：typedef struct int lvl; /層次序列指針，總是指向當前“根結(jié)點在層次序列中的位置int l,h; /中序序列的下上界int f; /層次序列中當前“根結(jié)點的雙親結(jié)點的指針int lr; / 1雙親的左子樹 2雙親的右子樹qnode; BiTree Creat(datatype in,level,int n)/由二叉樹的層次序列l(wèi)eveln和中序序列inn生成二叉樹。 n是二叉樹的結(jié)點數(shù)if (ndata=level0; p-lchild=null; p-rchild=null; /填寫該結(jié)點數(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é)點無右子樹，遍歷序列的1n-1是左子樹p-rchild=null; s.lvl=+R; s.l=1; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s); else /根結(jié)點有左子樹和右子樹s.lvl=+R; s.l=0; s.h=i-1; s.f=p; s.lr=1;enqueue(Q,s);/左子樹有關(guān)信息入隊列s.lvl=+R; s.l=i+1;s.h=n-1;s.f=p; s.lr=2;enqueue(Q,s)

17、;/右子樹有關(guān)信息入隊列while (!empty(Q) /當隊列不空，進行循環(huán)，構(gòu)造二叉樹的左右子樹 s=delqueue(Q); father=s.f; for (i=s.l; idata=levels.lvl; p-lchild=null; p-rchild=null; /填寫該結(jié)點數(shù)據(jù) if (s.lr=1) father-lchild=p; else father-rchild=p； /讓雙親的子女指針指向該結(jié)點 if (i=s.l) p-lchild=null; /處理無左子女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; /處理無右子女 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);/左子樹有關(guān)信息入隊列 s.lvl=+R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); /右子樹有關(guān)信息入隊列 /結(jié)束while (!empty(Q)return(p);/算法結(jié)束9、假設(shè)K1，Kn是n個關(guān)鍵詞，試解答：試用二叉查找樹的插入算法建立一棵二叉查找樹，即當關(guān)鍵詞的插入次序為K1，K2，Kn

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

20、=p;s-next=q;L-next=s;/LinkList_reverse12、請設(shè)計一個算法，要求該算法把二叉樹的葉子結(jié)點按從左到右的順序連成一個單鏈表，表頭指針為head。二叉樹按二叉鏈表方式存儲，鏈接時用葉子結(jié)點的右指針域來存放單鏈表指針。分析你的算法的時、空復(fù)雜度。13、對二叉樹的某層上的結(jié)點進行運算，采用隊列結(jié)構(gòu)按層次遍歷最適宜。int LeafKlevel(BiTree bt, int k) /求二叉樹bt 的第k(k1) 層上葉子結(jié)點個數(shù)if(bt=null | k1) return(0); BiTree p=bt,Q; /Q是隊列，元素是二叉樹結(jié)點指針,容量足夠大int fr

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