【正文】 144 Olog2(n)`0145 10B1 要查的索引文件時(shí),首先要查找_________,然后要查找__________.~0145 索引表 主文件`0146 09F2 寫出在有序表A上進(jìn)行非遞歸形式的折半查找的算法,其中給定值K為待查元素的關(guān)鍵字,若查找成功則返回該元素的下標(biāo),否則返回零值 .~0146 int binsearch(Sqlist s。int low。int high。keytype K){flag=0。while(lowhigh) {swich { case [mid].keyK:low=mid+1。break。 case [mid].keyK:high=mid1。break。 case [mid].key=K:flag=1。break。 default:。 } }}`0147 03E2 寫出棧的順序存儲(chǔ)結(jié)構(gòu)(即順序棧)的類型定義.~0147 順序棧的結(jié)構(gòu):typedef int datatype。define maxsize 64typedef struct{datatype data[maxsize]。int top}seqstack。seqstack *s。`0148 03A1 寫出隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)(順序隊(duì)列)的類型定義.~0148 順序隊(duì)列的結(jié)構(gòu):typedef struct{datatype data[maxsize]int front rear。}sequeue。sequeue *sq。`0149 03F3 ,將一個(gè)通常書寫正確的表達(dá)式轉(zhuǎn)換為逆波蘭式.~0149 change(E,A){setnull(S2)。push(S2,39。@39。)。i=1。j=1。ch=E[i]。while ch39。@39。{ if (ch in op1 ) { while(ch in op1) {S[j]=ch。j=j+1。i=i+1。ch\E[i]} A[j]=39。 39。j=j+1。 } if (ch in op2) { w=readop(S2)。 while(precede(w,ch)=39。39。 A[j]=w。j=j+1。pop(S2)。w=readtop(S2)。} if precede(w,ch)=39。39。 push(S2,ch) else pop(S2)。 }w=pop(S2)。 while w39。@39。 {A[j]=w。j=j+1。w=pop(S2)}A[j]=39。@39。}`0150 03B2 帶有頭結(jié)點(diǎn)的鏈隊(duì)列q,隊(duì)頭指針front,隊(duì)尾指針rear,則置空隊(duì)的算法描述為: qfront=malloc(sizeof(linklist))。 ________________ 。 ________________ 。~0150 qfrontnext=NULL qrear=qfront。`0151 06B2 深度為６的完全二叉樹至多有___個(gè)結(jié)點(diǎn),至有___個(gè)結(jié)點(diǎn)。~0151 63。32`0152 06B1 二叉樹的子樹有___之分，次序___任意顛倒。~0152 左右，不能`0153 06C2 已知完全二叉樹有２８?jìng)€(gè)結(jié)點(diǎn)，則整個(gè)二叉樹有( )個(gè)度為１的結(jié)點(diǎn)。 A、 0。 B、 1。 C、 2。 D、 不確定~0153 B`0154 06D2 樹的度是指樹內(nèi)結(jié)點(diǎn)的度。( )~0154 錯(cuò)`0155 06D1 滿二叉樹是完全二叉樹的特例.( )~0155 對(duì)`0156 04A2 已知S=(syz)* T=(s+z)*y試?yán)寐?lián)接(strcat(s1,s2),求子串(substr(s,i,j)和置換replace(s1,i,)等 基本運(yùn)算將S轉(zhuǎn)換為T.~0156 S1=SUBSTR(S,3,1) S=REPLACE(S,3,1,+) T=STRCAT(S,S1)`0157 06D1 二叉樹是樹。( )~0157 對(duì)`0158 06E1 已知一棵二叉樹如圖,試分別寫出按中序、先序、后序遍歷得到的結(jié)點(diǎn)序列。~0158 中序：16,24,35,42,53,57,60,84,88,92 先序：60,35,24,16,53,42,57,92,84,88 后序：16,24,42,57,53,35,88,84,92,60`0159 03B2 帶表頭結(jié)點(diǎn)的空循環(huán)雙向鏈表的長(zhǎng)度等于 。~0159 0`0160 06F2 以二叉鏈表作存儲(chǔ)結(jié)構(gòu),試編寫二叉樹的高度算法.~0160 求二叉樹高度算法int HIGH(bintree)bintree *tree。{int m=0。k=0。l=0 if (tree==NULL) m=0 else m=1 if (treelchild!=NULL) k=HIGH(treelchild)。 if (treerchild!=NULL) l=HIGH(treerchild)。 if (kl) m=k+1。 else m=l+1 return(m)。}`0161 06B2 二叉樹是空的,或者由一個(gè)根結(jié)點(diǎn)和兩棵______分別稱為左子樹和右子樹的_____組成。~0161 互不相交的；二叉樹`0162 06D1 不存在有偶數(shù)個(gè)結(jié)點(diǎn)的滿二叉樹。( )~0162 對(duì)`0163 04D2 空白串即為空串。( )~0163 錯(cuò)`0164 06D1 深度為K的二樹至多有2k11 結(jié)點(diǎn)。( )~0164 錯(cuò)`0165 06E3 已知一棵二叉樹中序和后序序列為分別為:BDCEAFHG和DECBHGFA畫出這棵二叉樹~0165`0166 06F2 已知一棵以鏈表結(jié)構(gòu)存貯的二叉樹,如欲從根結(jié)點(diǎn)起,由上而下,逐層打印各結(jié)點(diǎn)的數(shù)據(jù),同一層的結(jié)點(diǎn)自左而右打印,試寫其算法 (隊(duì)列的出隊(duì)和入隊(duì)算法已知)~0166 bintree *t,*rootsequeue *sqt=rootprintf(tdata)。while(tlchild!=NULL||trchild!=NULL)if(tlchild!=NULL)printf(tlchild)。ENQUENE(sq,tlchild)。if(trchild!=NULL){printf(trchild)。ENQUENE(trchild)。}t=DEQUEUE(sq)。}`0167 06E1 已知一棵樹如圖,請(qǐng)回答下列問題:(1)樹的度為多少?結(jié)點(diǎn)G的度為多少?(2)樹的深度為多少?哪些是葉子結(jié)點(diǎn)?(3)結(jié)點(diǎn)G的祖先有哪些?(4)結(jié)點(diǎn)B的兄弟有哪些?孩子有哪些?~0167 １、3。2２、4。３、E,F,I,J,N４、A,C５、C,D。E,F`0168 06D1 哈夫曼樹的帶權(quán)路徑長(zhǎng)度WPL等于葉子結(jié)點(diǎn)的權(quán)值之和。( )~0168 對(duì)`0169 06E3 已知二叉樹的先序、中序、后序序列分別如下,但其中有一些已模糊不清,構(gòu)造出該二叉樹.先序: _23_5_78中序: 3_41_789后序: _42__651~0169`0170 03D1 棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。 （ ） ~0170 X`0171 06D3 由二叉樹的先序序列和中序序列能唯一確定一棵二叉樹。( )~0171 對(duì)`0172 06B3 在有N(N0)個(gè)結(jié)點(diǎn)的二叉鏈表中，空鏈域的個(gè)數(shù)是：_____。~0172 N+1`0173 06D2 樹是一種特殊形式的圖。( )~0173 對(duì)`0174 06E2 滿足下列性質(zhì)之一的二叉樹是否存在？若有舉例，若無說明原因：１先序遍歷和中序遍歷結(jié)果相同。２先序遍歷和后序遍歷結(jié)果相同。３中序遍歷和后序遍歷結(jié)果相同。~0174`0175 06D2 不存在有偶數(shù)個(gè)結(jié)點(diǎn)的完全二叉樹。( )~0175 錯(cuò)`0176 06E1 根據(jù)二叉樹的定義，二叉樹有幾種基本形式。圖示之。~0176 有五種。`0177 06E2 畫出圖Ａ中森林轉(zhuǎn)化為二叉樹及圖Ｂ中由二叉樹轉(zhuǎn)為對(duì)應(yīng)的森林。~0177`0178 06F1 以二叉鏈表作存貯結(jié)構(gòu)，試寫出中序遍歷二叉樹的算法。~0178 INORDER()bitree *t。{if(t) {INORDER(tlchild)。 printf(|t%c|n,tdata)。 INORDER(trchild)。 }}`0179 06F3 設(shè)二叉樹以二叉鏈表存貯,root指向根結(jié)點(diǎn)寫出中序遍二叉樹的非遞歸算法。~0179 MIDBINTREE(p)bintree *root,*pseqstack *swhile(plchild!=NULL){printf(pdata) if(prchild!=NULL) PUSH(s,p)。 p=plchild。}printf(pdata)。while(EMPTY(s)!=NULL) p=pop(s)。{while(plchild!=NULL) {print(pdata)。 if(prchild!=NULL) PUSH(s,p)。 p=plchild。}printf(pdata)。}}`0180 06F2 遞歸算法，將二叉樹所有結(jié)點(diǎn)的左、右子樹交換。~0180 *t EXBINTREE(bintree)bintree *t,*root,*s{t=root。s=trchild。trchild=tlchild。tlchild=s。EXBINTREE(tlchild)。EXBINTREE(trchild)。}`0181 06B2 具有N個(gè)結(jié)點(diǎn)的完全二叉樹的深度為_________。~0181 └log2 n+1┘+1 或┌l(fā)og2(n+1)┐`0182 06D1 二叉樹的結(jié)點(diǎn)必須有兩棵子樹。( )~0182 錯(cuò)`0183 04D1 由空格組成的串稱空串。( )~0183 錯(cuò)`0184 06A2 何謂哈夫曼樹?何謂完全二叉樹,它具有哪些特點(diǎn)?~0184 哈夫曼樹：帶權(quán)路徑WPL最小的二叉樹稱最優(yōu)二叉樹或哈夫曼樹。完全二叉樹：若一棵二叉樹至多只有最下面的兩層上結(jié)點(diǎn)的度數(shù)可以小于２，并且最下一層上的結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則此二叉樹為完全二叉樹。特點(diǎn)：１只有最下面兩層有葉子。 ２如果一個(gè)結(jié)點(diǎn)無左子樹，那它一定是葉子。 ３完全二叉樹中任一個(gè)結(jié)點(diǎn)的左子樹深度為Ｔ，其右子樹深度為Ｔ或Ｔ－１。`0185 06C1 深度為K的二叉樹,所含葉子的個(gè)數(shù)最多為_____. A 、 2k B 、 K。 C 、 2k1 D、 2k1 ~0185 D`0186 06D2 存在著這樣的二叉樹,對(duì)它采用任何次序遍歷,其結(jié)點(diǎn)訪問序列均相同。( )~0186 對(duì)`0187 06D3 樹和二叉樹都是森林。( )~0187 對(duì)`0188 06B1 在一棵非空的樹中,有且僅有一個(gè)結(jié)點(diǎn)沒有______,這個(gè)結(jié)點(diǎn)稱為______.~0188 前趨（雙親）；根`0189 03D1 一個(gè)棧的輸入序列是12345，則棧的輸出序列不可能是12345。（ ） ~0189 X`0190 06E3 已知二叉樹的中序和先序序列分別為:中序序列:DEBAFCHG先序序列:ABDEC