數(shù)據(jù)結(jié)構(gòu)算法應(yīng)用題

1、一、舉例說明二分查找的基本思想，并用類一、舉例說明二分查找的基本思想，并用類C語言設(shè)計(jì)算法實(shí)現(xiàn)二分查找語言設(shè)計(jì)算法實(shí)現(xiàn)二分查找(折半查找折半查找)。解：二分法查找的過程是：首先確定待查記錄的范圍，然后逐步縮小范圍到直到找到或找不到該記錄為止。例如：已知11個(gè)數(shù)據(jù)元素的有序表，（關(guān)鍵字為數(shù)據(jù)元素的值）：（05，13，19，21，37，56，64，75，80，88，92），現(xiàn)在查找關(guān)鍵字為21的數(shù)據(jù)元素。設(shè)指針low指向下界，high指向上

2、界，=（lowhigh）」2指向中間區(qū)域。所以此例種設(shè)low=1，則high=11，=6。首先取所指元素ST.elem[].key與給定值key=21比較，因?yàn)?621，說明所查key=21一定在56的左側(cè)，則令high=1，所以所查元素在[low，1]之間即[1，5]范圍，求出=（lowhigh）」2=3，取所指元素19再與key的值21比較，因?yàn)?9high的情況，因此當(dāng)lowhigh說明查找不成功。算法如下：IntSearch_B

3、in(SSTableSTKeyTypekey)在有序表ST中查找值為key的元素，若找到，則函數(shù)值為該元素在表中的位置，否則為0low=1high=ST.length置區(qū)間初值while(lownext；pb=Lbnext；分別指向第一個(gè)結(jié)點(diǎn)Lc=pc=La；用La的頭節(jié)點(diǎn)作為Lc的頭節(jié)點(diǎn)while(pap=Twhile(p||!StackEmpty(S))if(p)Push(Sp)p=plchild根指針進(jìn)棧，遍歷左子樹else根指針

4、退棧，遍歷右子樹Pop(Sp)if(!visit(pdata))returnERRp=prchildReturnOK五、設(shè)二叉樹以二叉鏈表形式存放。利用循環(huán)隊(duì)列，用類五、設(shè)二叉樹以二叉鏈表形式存放。利用循環(huán)隊(duì)列，用類C語言設(shè)計(jì)算法實(shí)現(xiàn)二叉樹的按語言設(shè)計(jì)算法實(shí)現(xiàn)二叉樹的按層次遍歷。層次遍歷。算法：typedefstructBiTnode用二叉鏈表存儲(chǔ)二叉樹TElemTypedatastructBiTnodelchildrchildBiTn

5、odeBiTreeStatusInderTraverse(BiTreerootStatus(visit)(TElemType2))層次遍歷算法InitStack(S)初始化?？臻gBiTNodep=rootwhile(p!=NULL||!StackEmpty(S))不是空樹if(p)Push(Sp)p=plchildelsePop(Sp)Visist(pdata)p=prchildelsewhilereturnOKInderTravers

6、e六、六、（1）什么是完全二叉樹）什么是完全二叉樹(2)畫出畫出6個(gè)頂點(diǎn)的完全二叉樹。個(gè)頂點(diǎn)的完全二叉樹。(3)設(shè)二叉樹以二又鏈表形式設(shè)二叉樹以二又鏈表形式存放，用類存放，用類C語言設(shè)計(jì)算法判斷一棵二又樹是否為完全二叉樹。語言設(shè)計(jì)算法判斷一棵二又樹是否為完全二叉樹。（1）深度為k的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中的編號(hào)從1到n一一對(duì)應(yīng)時(shí)，稱為完全二叉樹。（2）略（3）intiscompletetree(