2023河南省數(shù)據(jù)庫入門深入

1、1、對一般二叉樹，僅根據(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é)點的下標(biāo)。if(h1=l1)posth2=prel1; /根結(jié)點half=(h1-l1)/2; /左或右子樹的結(jié)點數(shù)PreToPost(pre,post,l1+1,l1+half,l2,l2+half-1) /將左子

2、樹先序序列轉(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é)點從左到右鏈成一個單鏈表，表頭指針為head if(bt)InOrd

3、er(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)2、4、void LinkList_reverse(Linklist &L) /鏈表的就

4、地逆置;為簡化算法,假設(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=p;s-next=q;L-next=s;/LinkList_reverse3、此題要求建立有序的循環(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=(LinkedL

5、ist)malloc(sizeof(LNode); s-data=Ai; pre-next=s; s-next=p;/將結(jié)點s鏈入鏈表中/for return(h);算法結(jié)束4、兩棵空二叉樹或僅有根結(jié)點的二叉樹相似；對非空二叉樹，可判左右子樹是否相似，采用遞歸算法。 int Similar(BiTree p,q) /判斷二叉樹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-

6、rchild)/結(jié)束Similar5、對一般二叉樹，僅根據(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é)點的下標(biāo)。if(h1=l1)posth2=prel1; /根結(jié)點half=(h1-l1)/2; /左或右子樹的結(jié)點數(shù)PreToPost(pre,post,l1+1,l1+half,l

7、2,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é)點從左到右鏈成一個單鏈表，表頭指針

8、為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)6、#define maxsize ?？臻g容量 voi

9、d InOutS(int smaxsize)/s是元素為整數(shù)的棧，本算法進行入棧和退棧操作。 int top=0; /top為棧頂指針，定義top=0時為?？?。 for(i=1; i=n; i+) /n個整數(shù)序列作處理。 scanf(“%d,&x); /從鍵盤讀入整數(shù)序列。 if(x!=-1) / 讀入的整數(shù)不等于-1時入棧。 if(top=maxsize-1)printf(“棧滿n);exit(0);else s+top=x; /x入棧。 else /讀入的整數(shù)等于-1時退棧。 if(top=0)printf(“?？課);exit(0); else printf(“出棧元素是%dn,stop

10、-)； /算法結(jié)7、編寫一個過程，對一個nn矩陣，通過行變換，使其每行元素的平均值按遞增順序排列。8、假設(shè)以鄰接矩陣作為圖的存儲結(jié)構(gòu)，編寫算法判別在給定的有向圖中是否存在一個簡單有向回路，假設(shè)存在，那么以頂點序列的方式輸出該回路找到一條即可。注：圖中不存在頂點到自己的弧有向圖判斷回路要比無向圖復(fù)雜。利用深度優(yōu)先遍歷，將頂點分成三類：未訪問；已訪問但其鄰接點未訪問完;已訪問且其鄰接點已訪問完。下面用0，1，2表示這三種狀態(tài)。前面已提到，假設(shè)dfsv結(jié)束前出現(xiàn)頂點u到v的回邊，那么圖中必有包含頂點v和u的回路。對應(yīng)程序中v的狀態(tài)為1，而u是正訪問的頂點，假設(shè)我們找出u的下一鄰接點的狀態(tài)為1，就可以

11、輸出回路了。void Print(int v,int start ) /輸出從頂點start開始的回路。for(i=1;i=n;i+) if(gvi!=0 & visitedi=1 ) /假設(shè)存在邊v,i，且頂點i的狀態(tài)為1。 printf(“%d,v); if(i=start) printf(“n); else Print(i,start);break;/if /Printvoid dfs(int v) visitedv=1;for(j=1;j=n;j+ ) if (gvj!=0) /存在邊(v,j) if (visitedj!=1) if (!visitedj) dfs(j); /if e

12、lse cycle=1; Print(j,j); visitedv=2;/dfsvoid find_cycle() /判斷是否有回路，有那么輸出鄰接矩陣。visited數(shù)組為全局變量。 for (i=1;i=n;i+) visitedi=0; for (i=1;ij)printf(“序列非法n)；exit(0); i+; /不管Ai是I或O，指針i均后移。 if(j!=k) printf(“序列非法n)；return(false); else printf(“序列合法n)；return(true); /算法結(jié)束。10、連通圖的生成樹包括圖中的全部n個頂點和足以使圖連通的n-1條邊，最小生成樹是

13、邊上權(quán)值之和最小的生成樹。故可按權(quán)值從大到小對邊進行排序，然后從大到小將邊刪除。每刪除一條當(dāng)前權(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條邊：頂點，權(quán)值。 scanf(%d%d%d ,&edgei.

14、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)，11、設(shè)從鍵盤輸入一整數(shù)的序列：a1, a2, a3，an,試編寫算法實現(xiàn)：用棧結(jié)構(gòu)存儲輸入的整數(shù)，當(dāng)ai-1時，將ai進棧；當(dāng)a

15、i=-1時，輸出棧頂整數(shù)并出棧。算法應(yīng)對異常情況入棧滿等給出相應(yīng)的信息。設(shè)有一個背包可以放入的物品重量為S，現(xiàn)有n件物品，重量分別為W1，W2，.，Wn。問能否從這n件物品中選擇假設(shè)干件放入背包，使得放入的重量之和正好是S。設(shè)布爾函數(shù)Knap(S，n)表示背包問題的解，Wi(i=1,2,.，n)均為正整數(shù)，并已順序存儲地在數(shù)組W中。請在以下算法的下劃線處填空，使其正確求解背包問題。Knap(S，n)假設(shè)S=0那么Knaptrue否那么假設(shè)S0且n1)個整數(shù)存放到一維數(shù)組R中。設(shè)計一個盡可能高效時間、空間的算法，將R中保存的序列循環(huán)左移p0pn個位置，即將R中的數(shù)據(jù)x0, x1, x2, xn-

16、1，變換為(xp， xp1, , xn-1 ,x0 , x1, xp-1)。12、我們用l代表最長平臺的長度，用k指示最長平臺在數(shù)組b中的起始位置下標(biāo)。用j記住局部平臺的起始位置，用i指示掃描b數(shù)組的下標(biāo)，i從0開始，依次和后續(xù)元素比較，假設(shè)局部平臺長度i-j大于l時，那么修改最長平臺的長度kl=i-j和其在b中的起始位置k=j，直到b數(shù)組結(jié)束，l即為所求。void Platform (int b , int N) /求具有N個元素的整型數(shù)組b中最長平臺的長度。l=1;k=0;j=0;i=0;while(in-1)while(il) l=i-j+1;k=j; /局部最長平臺i+; j=i; /

17、新平臺起點printf(“最長平臺長度%d，在b數(shù)組中起始下標(biāo)為%d，l，k)；/ Platform13、設(shè)有一個數(shù)組中存放了一個無序的關(guān)鍵序列K1、K2、Kn?，F(xiàn)要求將Kn放在將元素排序后的正確位置上，試編寫實現(xiàn)該功能的算法，要求比較關(guān)鍵字的次數(shù)不超過n。51. 借助于快速排序的算法思想，在一組無序的記錄中查找給定關(guān)鍵字值等于key的記錄。設(shè)此組記錄存放于數(shù)組rl.h中。假設(shè)查找成功，那么輸出該記錄在r數(shù)組中的位置及其值，否那么顯示“not find信息。請編寫出算法并簡要說明算法思想。14、此題要求建立有序的循環(huán)鏈表。從頭到尾掃描數(shù)組A，取出Ai0=inext=h; /形成空循環(huán)鏈表for(i=0;