【正文】 。4．度等于0的結(jié)點(diǎn)稱作 或 。2．樹的度是指 。A．先序 B． 中序 C．后序 D．層次36．已知下圖所示的一個(gè)圖，若從頂點(diǎn)V1出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（ ）。A．連通圖的深度優(yōu)先搜索是一個(gè)遞歸過程B．圖的廣度優(yōu)先搜索中鄰接點(diǎn)的尋找具有“先進(jìn)先出”的特征C．非連通圖不能用深度優(yōu)先搜索法D．圖的遍歷要求每一頂點(diǎn)僅被訪問一次 34．無向圖的鄰接矩陣是一個(gè)（ ）。 A．順序存儲(chǔ)結(jié)構(gòu) B．鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) C．索引存儲(chǔ)結(jié)構(gòu) D．散列存儲(chǔ)結(jié)構(gòu) 32．如果從無向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問所有頂點(diǎn)，則該圖一定是（ ）。 A．入邊 B． 出邊 C．入邊和出邊 D． 不是入邊也不是出邊 30．在有向圖的逆鄰接表中，每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有（ ）鄰接點(diǎn)。 A．n B．e C．2n D．2e28．對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，若采用鄰接表表示，則所有頂點(diǎn)鄰接表中的結(jié)點(diǎn)總數(shù)為（ ）。 A．n（n1） B．n（n+1） C． n（n1）/2 D． n（n+1）/226．對(duì)于具有n個(gè)頂點(diǎn)的圖，若采用鄰接矩陣表示，則該矩陣的大小為（ ）。 A．n B．n+1 C．n1 D．n/224．一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖包含（ ）條邊。 A．1/2 B．1 C．2 D．4 22．在一個(gè)有像圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（ ）倍。 A．2n B．2n1 C．2n+1 D．2n+2 20．一棵完全二叉樹共有5層，且第5層上有六個(gè)結(jié)點(diǎn)，該樹共有（ ）個(gè)結(jié)點(diǎn)。 A．2i B．2i1 D．2i+1 C．2i+2 18．設(shè)一棵哈夫曼樹共有n個(gè)葉結(jié)點(diǎn)，則該樹有（ ）個(gè)非葉結(jié)點(diǎn)。 A. 18 B. 16 C. 12 D. 3016．在一棵樹中，（ ）沒有前驅(qū)結(jié)點(diǎn)。 A. n B. n+1 C. 2*n D. 2*n1 14. 利用n個(gè)值作為葉結(jié)點(diǎn)的權(quán)生成的哈夫曼樹中共包含有( )個(gè)雙支結(jié)點(diǎn)。A．4 B．5 C．6 D．712．在一棵度具有5層的滿二叉樹中結(jié)點(diǎn)總數(shù)為（ ）。A．哈夫曼樹 B．平衡二叉樹 C．二叉樹 D．完全二叉樹10．下列有關(guān)二叉樹的說法正確的是（ ）。A．18 B．28 C．19 D．298．將含有150個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為69的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為（ ）。A．線性結(jié)構(gòu)的數(shù)據(jù) B．順序結(jié)構(gòu)的數(shù)據(jù) C．元素之間無前驅(qū)和后繼關(guān)系的數(shù)據(jù) D．元素之間有包含和層次關(guān)系的數(shù)據(jù) 6．設(shè)a,b為一棵二叉樹的兩個(gè)結(jié)點(diǎn)，在后續(xù)遍歷中，a在b前的條件是（ ）。A．2k B．2k1C．2k1 D．2k14. 設(shè)某一二叉樹先序遍歷為abdec，中序遍歷為dbeac，則該二叉樹后序遍歷的順序是（ ）。A．15 B．16 C．17 D．472．二叉樹第k層上最多有（ ）個(gè)結(jié)點(diǎn)。六、完成：實(shí)驗(yàn)2――棧、隊(duì)列、遞歸程序設(shè)計(jì)根據(jù)實(shí)驗(yàn)要求（見教材P203）認(rèn)真完成本實(shí)驗(yàn)，并提交實(shí)驗(yàn)報(bào)告。（5）判斷隊(duì)列是否為空：emptyqueue(Q)。（3）出隊(duì)列delqueue(Q):從隊(duì)列Q中退出一個(gè)元素。　 /*隊(duì)空時(shí)，頭尾指針指向頭結(jié)點(diǎn)*/ } 五、綜合題 1．設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1,e2,e3,e4,e5和e6依次通過S，一個(gè)元素出棧后即進(jìn)隊(duì)列Q，若6個(gè)元素出隊(duì)的序列是e2,e4,e3,e6,e5,e1，則棧S的容量至少應(yīng)該是多少？ 2．假設(shè)用循環(huán)單鏈表實(shí)現(xiàn)循環(huán)隊(duì)列，該隊(duì)列只使用一個(gè)尾指針rear，其相應(yīng)的存儲(chǔ)結(jié)構(gòu)和基本算法如下；（1）初始化隊(duì)列initqueue(Q):建立一個(gè)新的空隊(duì)列Q。 (1) printf(“%4d”,pdata)。 exit(0)。 int write(LinkQueue *q) {QueueNode *p。 } else { (5) Return(Qqueue[Q＞front])。}else{ (2) (3) return(TRUE)。int encqueue(sequeuetype*Q,elemtype x){if ( ( 1 ) ){Printf(〝The cicular queue is full!\n〞)。 }sequeuetype。typedef struct{ Elemtype queue [MAXSIZE]。define MAXSIZE 100。define TRUE 1。5．用S表示入棧操作，X表示出棧操作，若元素入棧順序?yàn)?234，為了得到1342出棧順序，相應(yīng)的S和X操作串是什么？6．有5個(gè)元素，其入棧次序?yàn)椋篈、B、C、D、E，在各種可能的出棧次序中，以元素C、D最先的次序有哪幾個(gè)？7．寫出以下運(yùn)算式的后綴算術(shù)運(yùn)算式⑴ 3x2+x1/x+5⑵ (A+B)*CD/(E+F)+G8．在什么情況下可以用遞歸解決問題？在寫遞歸程序時(shí)應(yīng)注意什么？9． 簡(jiǎn)述廣義表和線性表的區(qū)別和聯(lián)系。3．鏈棧中為何不設(shè)頭結(jié)點(diǎn)？4．利用一個(gè)棧，則：（1）如果輸入序列由A，B，C組成，試給出全部可能的輸出序列和不可能的輸出序列。三、問答題1．簡(jiǎn)述棧和一般線性表的區(qū)別。j時(shí)，A的數(shù)組元素aij相應(yīng)于數(shù)組s的數(shù)組元素的下標(biāo)為__ _____。26．兩個(gè)串相等的充分必要條件是_______ ___。24．設(shè)廣義表L=（（），（）），則表頭是 ，表尾是 ，L的長(zhǎng)度是 。22．空串的長(zhǎng)度是 ；空格串的長(zhǎng)度是 。 (結(jié)點(diǎn)的指針域?yàn)閚ext) 20．串是一種特殊的線性表，其特殊性表現(xiàn)在組成串的數(shù)據(jù)元素都是 。(結(jié)點(diǎn)的指針域?yàn)閚ext)18．在一個(gè)鏈隊(duì)中，設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的操作為________和r=s。(結(jié)點(diǎn)的指針域?yàn)閚ext)17．從一個(gè)棧頂指針為h的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪結(jié)點(diǎn)的值，可執(zhí)行x=hdata。 16．向一個(gè)棧頂指針為h的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，可執(zhí)行________和h=s。11．判斷一個(gè)循環(huán)隊(duì)列LU（最多元素為m0）為空的條件是 。9．假設(shè)以S和X分別表示入棧和出棧操作，則對(duì)輸入序列a,b,c,d,e一系列棧操作SSXSXSSXXX之后，得到的輸出序列為 。同樣從順序棧刪除元素分為三步：第一步進(jìn)行 判斷，判斷條件是 。7．循環(huán)隊(duì)列的引入，目的是為了克服 。4．刪除棧中元素的操作方式是：先 ，后 。2．隊(duì)列的特性是 。A．41 B．32 C．18 D．3835．一個(gè)非空廣義表的表頭（ ）。A．建立與刪除 B．索引與、和修改C．查找和修改 D．查找與索引33. 設(shè)二維數(shù)組A[5][6]按行優(yōu)先順序存儲(chǔ)在內(nèi)存中，已知A[0][0] 起始地址為1000，每個(gè)數(shù)組元素占用5個(gè)存儲(chǔ)單元，則元素A[4][4]的地址為（ ）。A．表達(dá)變得簡(jiǎn)單 B．對(duì)矩陣元素的存取變得簡(jiǎn)單 C．去掉矩陣中的多余元素 D．減少不必要的存儲(chǔ)空間的開銷31．一個(gè)非空廣義表的表頭（ ）。A．鏈?zhǔn)? B． 順序 C．堆結(jié)構(gòu) D．無法確定 ，每個(gè)元素占用6個(gè)字節(jié)，第6個(gè)元素的存儲(chǔ)地址為100，則該數(shù)組的首地址是（ ）。 A．兩串的長(zhǎng)度相等 B．兩串包含的字符相同 C．兩串的長(zhǎng)度相等，并且兩串包含的字符相同 D．兩串的長(zhǎng)度相等，并且對(duì)應(yīng)位置上的字符相同28．在實(shí)際應(yīng)用中，要輸入多個(gè)字符串，且長(zhǎng)度無法預(yù)定。A．順序的存儲(chǔ)結(jié)構(gòu) B．鏈接的存儲(chǔ)結(jié)構(gòu) C．?dāng)?shù)據(jù)元素是一個(gè)字符 D．?dāng)?shù)據(jù)元素可以任意26．空串與空格串（ ）。 A．9 B．16 C． 36 D．2824．下面關(guān)于串的敘述中，不正確的是（ ）。 A．不少于一個(gè)字母的序列 B．任意個(gè)字母的序列 C．不少于一個(gè)字符的序列 D．有限個(gè)字符的序列 22．串的長(zhǎng)度是指（ ）。A．串是一種特殊的線性表 B．串的長(zhǎng)度必須大于零C．串中元素只能是字母 D．空串就是空白串20．設(shè)有兩個(gè)串p和q，其中q是p的子串，q在p中首次出現(xiàn)的位置的算法稱為（ ）。f=s。r=s。r=s。 f=s。18．在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的運(yùn)算為（ ）。 C．f=fnext。 A．r=fnext。 x=data。 x=topdata。 B．x=topdata。 A．x=topdata。A．堆棧 B．隊(duì)列 C．?dāng)?shù)組 D．先性表15．一個(gè)遞歸算法必須包括（ ）。 A．a(chǎn),d,cb B．a(chǎn),b,c,d C．d,c,b,a D．c,b,d,a13．如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則退棧操作時(shí)（ ）。 A．Qfront==Qrear B．Qfront!=Qrear C．Qfront==(Qrear+1)% m0 D．Qfront!= (Qrear+1)% m0 11．判斷棧S滿（元素個(gè)數(shù)最多n個(gè)）的條件是（ ）。 A．sqrearsqfront== m0 B．sqrearsqfront1= = m0 C．sqfront==sqrear D．sqfront==sqrear+19．判斷一個(gè)循環(huán)隊(duì)列Q（最多元素為m0）為空的條件是（ ）。A．棧 B．隊(duì)列C．堆棧或隊(duì)列 D．?dāng)?shù)組7．表達(dá)式a*(b+c)d的后綴表達(dá)式是（ ）。 top=topnext。 x=topdata。 B．x=topdata。A．x=top。 top=topnext。 top=p。 topnext=p。A．topnext=p。A．4，3，2，1 B．1，2，3