【正文】 用二叉鏈表存儲包含n個結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)共有2n個鏈域。（應(yīng)2i1）（ √ ）（linkrlink）存儲包含n個結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的2n個指針區(qū)域中有n+1個為空指針。 （ ），如果不存在非空左子樹，則不存在非空右子樹。 （ ）（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值，且小于其右非空子樹（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值。 （ √ ）。第6章 樹和二叉樹 自測卷解答 姓名 班級 題號一二三四五六總分題分101511202024100得分一、下面是有關(guān)二叉樹的敘述，請判斷正誤（每小題1分，共10分）（ √ ）1. 若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個結(jié)點(diǎn)的二叉樹鏈表中只有n—1個非空指針域。 //求串的長度strcpy是串復(fù)制(copy)函數(shù)：char *strcpy(char to,char from)。若i≥strlen(S)，則沒有字符被刪除；若i+m≥strlen(S)，則將S中從位置i開始直至末尾的字符均被刪去。 }// 循環(huán)右移一步 A[i]=temp。 j=l。 temp=A[l]。temp=A[i]。i++) { j=i。//求n和k的最大公約數(shù)p for(i=0。amp。i=k。 StrAssign(r,Concat(r,c))。i。)。r)//求s的逆串r { StrAssign(r,39。else printf(pdata)。printf(“%c”, pdata)}如果當(dāng)前串長為0,則return(1)否則開始遞歸：if 串沒有到末尾，則P=Pnext。Invert(stringlistnode *p){if(!p)return(0)。DLR(rootrchild)。printf(“%d”,rootdata)。,則省掉i+=Strlen(V)。, V=39。, T=39。這一句是必需的,則在某些情況下, 會引起不希望的后果,:設(shè)S=39。 }//if return n。 //當(dāng)前指針跳到插入串以后 n++。 StrAssign(S,Concat(S,tail))。 StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)iStrlen(T)+1))。i=Strlen(S)Strlen(T)+1。S,Stringtype T,Stringtype V)。S, T, V)的算法。所以（1）可列表為： （2）可列表為：8866416225943565353233685467858124. （P60 419）下列各三元組表分別表示一個稀疏矩陣，試寫出它們的稀疏矩陣。寫出模式串的nextval函數(shù)值，并由此畫出KMP算法匹配的全過程。四、計(jì)算題（每題5分，共20分）1. 設(shè)s=’I AM A STUDENT’, t=’GOOD’, q=’WORKER’, 求Replace(s,’STUDENT’,q) 和Concat(SubString(s,6,2), Concat(t,SubString(s,7,8)))。時間復(fù)雜度與樣本個數(shù)n有關(guān)，是指最深層的執(zhí)行語句耗費(fèi)時間，而遞歸算法與非遞歸算法在最深層的語句執(zhí)行上是沒有區(qū)別的，循環(huán)的次數(shù)也沒有太大差異。供選擇的答案A～D：①12 ② 66 ③ 72 ④ 96 ⑤ 114 ⑥ 120 ⑦ 156 ⑧ 234 ⑨ 276 ⑩ 282 （11）283 （12）288答案：ABCD=12, 10, 3, 9三、簡答題（每小題5分，共15分）1. KMP算法的設(shè)計(jì)思想是什么？它有什么優(yōu)點(diǎn)？2. （軟件技術(shù)？）已知二維數(shù)組Am,m采用按行優(yōu)先順序存放，每個元素占K個存儲單元，并且第一個元素的存儲地址為Loc(a11)，請寫出求Loc(aij)的計(jì)算公式。若按行存儲，則A[2,4]的第一個字節(jié)的地址是 C 。那么，這個數(shù)組的體積是 A 個字節(jié)。供選擇的答案A～E：①28 ② 44 ③ 76 ④ 92 ⑤ 108⑥ 116 ⑦ 132 ⑧ 176 ⑨ 184 ⑩ 188答案：ABCDE=8, 3, 5, 1, 67.【94程P12】 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。若按行存儲，則A[3,5]和A[5,3]的第一個字節(jié)的地址分別是 B 和 C 。假設(shè)存儲數(shù)組元素A[0,1]的第一個字節(jié)的地址是0。有一個二維數(shù)組A，行下標(biāo)的范圍是0到8，列下標(biāo)的范圍是1到5，每個數(shù)組元素用相鄰的4個字節(jié)存儲。（無第0行第0列元素） Ａ．16902 Ｂ．16904 Ｃ．14454 Ｄ．答案A, B, C均不對答：（57列60行＋31行）2字節(jié)＋10000=16902(A)( B )5. 設(shè)矩陣A是一個對稱矩陣，為了節(jié)省存儲，將其下三角部分（如下圖所示）按行序存放在一維數(shù)組B[ 1, n(n1)/2 ]中，對下三角部分中任一元素ai,j(i≤j), 在一維數(shù)組B中下標(biāo)k的值是：Ａ．i(i1)/2+j1 Ｂ．i(i1)/2+j Ｃ．i(i+1)/2+j1 Ｄ．i(i+1)/2+j解：注意B的下標(biāo)要求從1開始。 subs(s1, len(s2), 2)＝subs(s1, 5, 2)=’ EF’。（4） GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== （d） 。 //頭元素不必加括號（2） GetHead【GetTail【((a,b),(c,d))】】=== (c,d) 。答：考慮0行0列，（58列61行＋32行）2字節(jié)＋基址2048=9188？？9. 三元素組表中的每個結(jié)點(diǎn)對應(yīng)于稀疏矩陣的一個非零元素，它包含有三個數(shù)據(jù)項(xiàng)，分別表示該元素的 行下標(biāo) 、 列下標(biāo) 和 元素值 。已知A的起始存儲位置（基地址）為1000，則數(shù)組A的體積（存儲量）為 288 B ；末尾元素A57的第一個字節(jié)地址為 1282 ；若按行存儲時，元素A14的第一個字節(jié)地址為 (8+4)6+1000=1192 ；若按列存儲時，元素A47的第一個字節(jié)地址為 (67＋4)6＋1000）＝1276 。6. 若n為主串長，m為子串長，則串的古典（樸素）匹配算法最壞的情況下需要比較字符的總次數(shù)為 (nm+1)*m 。4. 子串的定位運(yùn)算稱為串的模式匹配； 被匹配的主串 稱為目標(biāo)串， 子串 稱為模式。（①，簡答題：簡述空串和空格串的區(qū)別）2. 設(shè)S=“A。return OK。}DeQueue(Q,b))。EnQueue(Q,c)。39。InitQueue(Q)。3.【③】試寫一個算法判別讀入的一個以‘’為結(jié)束符的字符序列是否是“回文”。試編寫相應(yīng)的入隊(duì)和出隊(duì)的算法。 }//AllBrackets_Test 2. 【統(tǒng)考書P60 415】假設(shè)一個數(shù)組squ[m]存放循環(huán)隊(duì)列的元素。 //必須與當(dāng)前棧頂括號匹配 } }//for if(!StackEmpty(s)) return ERROR。{39。amp。}39。) return ERROR。c!=39。amp。 if(*p==39。(39。amp。)39。 pop(s,c)。}39。]39。)39。) push(s,*p)。||*p==39。||*p==39。p++) { if(*p==39。 for(p=str。}if(top0)tag=0。else tag=0。else tag=0。else tag=0。st[top]=exp[i]。amp。tag=1。{char st[m0]。編程后的整個函數(shù)如下（李書P31—32）define m0 100 /*m0為算術(shù)表達(dá)式中最多字符個數(shù)*/correct(exp,tag)char exp[m0]。答：用堆棧st進(jìn)行判定，將 ( 、 [ 或 { 入棧，當(dāng)遇到 } 、 ] 或 ) 時，檢查當(dāng)前棧頂元素是否是對應(yīng)的( 、 [ 或 {，若是則退棧，否則返回表示不配對。六、算法設(shè)計(jì)（每小題5分，共15分。 EnQueue (Q,d)。}。while(!QueueEmpty(Q)){ DeQueue (Q,d)。 int d。void algo3(Queue amp。}答：輸出為“char”。 }。 while(!QueueEmpty(Q)){ DeQueue (Q,y)。 DeQueue (Q,x)。DeQueue (Q,x)。 EnQueue (Q,’r’)。 y=’c’。 Init Queue (Q)。3. 【②】寫出下列程序段的輸出結(jié)果（隊(duì)列中的元素類型QElem Type為char）。Printf(x)。printf(y)。 Push(S,’s’)。 Push(S,x)。Pop(S,x)。 Push(S,’a’)。y=’k’。InitStack(S)。void main( ){Stack S。 ② front=19，rear=11；問在這兩種情況下，循環(huán)隊(duì)列中各有元素多少個？答：用隊(duì)列長度計(jì)算公式： (N＋r－f)% N① L=（40＋19－11）% 40=8 ② L=（40＋11－19）% 40=32五、閱讀理解（每小題5分，共20分。我們常采用法②，即隊(duì)頭指針、隊(duì)尾指針中有一個指向?qū)嵲?，而另一個指向空閑元素。另外，解決隊(duì)滿隊(duì)空的辦法有三：① 設(shè)置一個布爾變量以區(qū)別隊(duì)滿還是隊(duì)空；② 浪費(fèi)一個元素的空間，用于區(qū)別隊(duì)滿還是隊(duì)空。4. 【統(tǒng)考書P60 413】順序隊(duì)的“假溢出”是怎樣產(chǎn)生的？如何知道循環(huán)隊(duì)列是空還是滿？答：一般的一維數(shù)組隊(duì)列的尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊(duì)操作，但其實(shí)數(shù)組中還有空位置，這就叫“假溢出”。若正文在機(jī)內(nèi)已是順序存儲，則直接用線性表從后往前讀取即可，或?qū)⒍褩ｍ旈_到數(shù)組末尾，然后直接用POP動作實(shí)現(xiàn)。假設(shè)一字符序列已存入計(jì)算機(jī)，請分析用線性表、堆棧和隊(duì)列等方式正確輸出其回文的可能性？答：線性表是隨機(jī)存儲，可以實(shí)現(xiàn)，靠循環(huán)變量（j）從表尾開始打印輸出；堆棧是后進(jìn)先出，也可以實(shí)現(xiàn)，靠正序入棧、逆序出棧即可；隊(duì)列是先進(jìn)先出，不易實(shí)現(xiàn)。劉答：至少有14種。② 用途不同，堆棧用于子程調(diào)用和保護(hù)現(xiàn)場，隊(duì)列用于多道作業(yè)處理、指令寄存及其他運(yùn)算等等。都可以用順序存儲或鏈表存儲；棧和隊(duì)列是兩種特殊的線性表，即受限的線性表，只是對插入、刪除運(yùn)算加以限制。供選擇的答案：A，B：①空 ② 滿 ③ 上溢 ④ 下溢C： ①n1 ② n ③ n+1 ④ n/2D： ① 長度 ②深度 ③ 棧頂 ④ 棧底E：①兩個棧的棧頂同時到達(dá)?？臻g的中心點(diǎn) ②其中一個棧的棧頂?shù)竭_(dá)棧空間的中心點(diǎn) ③兩個棧的棧頂在達(dá)?？臻g的某一位置相遇 ④兩個棧均不空，且一個棧的棧頂?shù)竭_(dá)另一個棧的棧底答案：ABCDE＝2, 1, 2, 4, 3四、簡答題（每小題4分，共20分）1. 【①①】說明線性表、棧與隊(duì)的異同點(diǎn)。當(dāng)棧中元素為n個，做進(jìn)棧運(yùn)算時發(fā)生上溢，則說明該棧的最大容量為 C 。8. 【91初程P77】 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。設(shè)?？諘r，有輸入序列a，b，c，經(jīng)過PUSH，POP，PUSH，PUSH，POP操作后，從棧中彈出的元素的序列是 D ，變量T的值是 E 。設(shè)用一維數(shù)組A[1,…,n]來表示一個棧，A[n]為棧底，用整型變量T指示當(dāng)前棧頂位置，A[T]為棧頂元素。供選擇的答案：A～D：①a1 ②a2 ③ a3 ④a4E： ①1 ②2 ③ 3 ④ 0答：ABCDE＝2, 4, 1, 2, 27. 【94初程P75】 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。現(xiàn)要進(jìn)行的棧操作是進(jìn)棧兩次，出棧一次，再進(jìn)棧兩次，出棧一次；這時，第一次出棧得到的元素是 A ，第二次出棧得到的元素是 B 是；類似地，考慮對這四個數(shù)據(jù)元素進(jìn)行的隊(duì)操作是進(jìn)隊(duì)兩次，出隊(duì)一次，再進(jìn)隊(duì)兩次，出隊(duì)一次；這時，第一次出隊(duì)得到的元素是 C ，第二次出隊(duì)得到的元素是 D 。在進(jìn)?；蜻M(jìn)隊(duì)操作時，按aaaa4次序每次進(jìn)入一個元素。 （Ｄ）（n＋r－f）% n6. 【98初程P71】 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號寫在答卷的對應(yīng)