【文章內(nèi)容簡(jiǎn)介】 8．在什么情況下可以用遞歸解決問題？在寫遞歸程序時(shí)應(yīng)注意什么？9． 簡(jiǎn)述廣義表和線性表的區(qū)別和聯(lián)系。四、程序填空題1．在下面空格處填寫適當(dāng)?shù)恼Z句，以使下面的循環(huán)隊(duì)列的入隊(duì)和出隊(duì)算法完整。define TRUE 1。define FALSE 0。define MAXSIZE 100。typedef charelemtype。typedef struct{ Elemtype queue [MAXSIZE]。 int front,rear。 }sequeuetype。Sequeuetype Q。int encqueue(sequeuetype*Q,elemtype x){if ( ( 1 ) ){Printf(〝The cicular queue is full!\n〞)。return(FALSE)。}else{ (2) (3) return(TRUE)。 }} /*encqueue*/elemtype del_cqueue(sequeuetype *Q){ if ( (4) ) { Printf(〝The queue is empty !\n〞) return(NULL)。 } else { (5) Return(Qqueue[Q＞front])。 }} /*del_cqueue*/ ，以使下面的鏈?zhǔn)疥?duì)列取出元素的算法完整。 int write(LinkQueue *q) {QueueNode *p。 if (qfront==qrear)　 /*隊(duì)空*/ {printf(“underflow”)。 exit(0)。} while (qfrontnext != NULL) {p=qfrontnext。 (1) printf(“%4d”,pdata)。 (2) } （3） ?！? /*隊(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。（2）入隊(duì)列enqueue(Q,x):將元素x插入到隊(duì)列Q中。（3）出隊(duì)列delqueue(Q):從隊(duì)列Q中退出一個(gè)元素。（4）取隊(duì)首元素gethead(Q):返回當(dāng)前隊(duì)首元素。（5）判斷隊(duì)列是否為空：emptyqueue(Q)。（6）顯示隊(duì)列中元素：dispqueue(Q)。六、完成：實(shí)驗(yàn)2――棧、隊(duì)列、遞歸程序設(shè)計(jì)根據(jù)實(shí)驗(yàn)要求（見教材P203）認(rèn)真完成本實(shí)驗(yàn)，并提交實(shí)驗(yàn)報(bào)告。數(shù)據(jù)結(jié)構(gòu)（本）課程作業(yè)作業(yè)3（本部分作業(yè)覆蓋教材第67章的內(nèi)容）一、單項(xiàng)選擇題，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30，則葉子結(jié)點(diǎn)數(shù)為（ ）。A．15 B．16 C．17 D．472．二叉樹第k層上最多有（ ）個(gè)結(jié)點(diǎn)。 A．2k B．2k1 C．2k1 D．2k1 3．二叉樹的深度為k,則二叉樹最多有（ ）個(gè)結(jié)點(diǎn)。A．2k B．2k1C．2k1 D．2k14. 設(shè)某一二叉樹先序遍歷為abdec，中序遍歷為dbeac，則該二叉樹后序遍歷的順序是（ ）。 A．a(chǎn)bdec B．debac C．debca D．a(chǎn)bedc5．樹最適合于用來表示（ ）。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．a(chǎn)在b上方 B．a(chǎn)在b下方 C．a(chǎn)在b左方 D．a(chǎn)在b右方7．權(quán)值為{1，2，6，8}的四個(gè)結(jié)點(diǎn)構(gòu)成的哈夫曼樹的帶權(quán)路徑長(zhǎng)度是（ ）。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．33 B．34 C．35 D．369．如果將給定的一組數(shù)據(jù)作為葉子數(shù)值，所構(gòu)造出的二叉樹的帶權(quán)路徑長(zhǎng)度最小，則該樹稱為（ ）。A．哈夫曼樹 B．平衡二叉樹 C．二叉樹 D．完全二叉樹10．下列有關(guān)二叉樹的說法正確的是（ ）。A．二叉樹中度為0的結(jié)點(diǎn)的個(gè)數(shù)等于度為2的結(jié)點(diǎn)的個(gè)數(shù)加1B．二叉樹中結(jié)點(diǎn)個(gè)數(shù)必大于0C．完全二叉樹中，任何一個(gè)結(jié)點(diǎn)的度，或者為0或者為2 D．二叉樹的度是211．在一棵度為3的樹中，度為3的結(jié)點(diǎn)個(gè)數(shù)為2，度為2的結(jié)點(diǎn)個(gè)數(shù)為1，則度為0的結(jié)點(diǎn)個(gè)數(shù)為（ ）。A．4 B．5 C．6 D．712．在一棵度具有5層的滿二叉樹中結(jié)點(diǎn)總數(shù)為（ ）。A．31 B．32 C．33 D．1613. 利用n個(gè)值作為葉結(jié)點(diǎn)的權(quán)生成的哈夫曼樹中共包含有( )個(gè)結(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. n B. n1 C. n+1 D. 2*n1 15. 利用12這四個(gè)值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫曼樹，該樹中所有葉子的最長(zhǎng)帶權(quán)路徑長(zhǎng)度為( )。 A. 18 B. 16 C. 12 D. 3016．在一棵樹中，（ ）沒有前驅(qū)結(jié)點(diǎn)。A．分支結(jié)點(diǎn) B．葉結(jié)點(diǎn) C．樹根結(jié)點(diǎn) D．空結(jié)點(diǎn)17．在一棵二叉樹中，若編號(hào)為i的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號(hào)為（ ）。 A．2i B．2i1 D．2i+1 C．2i+2 18．設(shè)一棵哈夫曼樹共有n個(gè)葉結(jié)點(diǎn)，則該樹有（ ）個(gè)非葉結(jié)點(diǎn)。 A．n B．n1 C．n+1 D．2n19．設(shè)一棵有n個(gè)葉結(jié)點(diǎn)的二叉樹，除葉結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)度數(shù)都為2，則該樹共有（ ）個(gè)結(jié)點(diǎn)。 A．2n B．2n1 C．2n+1 D．2n+2 20．一棵完全二叉樹共有5層，且第5層上有六個(gè)結(jié)點(diǎn)，該樹共有（ ）個(gè)結(jié)點(diǎn)。 A．20 B．21 C．23 D．3021．在一個(gè)圖G中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)之和的（ ）倍。 A．1/2 B．1 C．2 D．4 22．在一個(gè)有像圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（ ）倍。 A．鄰接矩陣表示法 B．鄰接表表示法 C．逆鄰接表表示法 D．鄰接表和逆鄰接表 23．在圖的存儲(chǔ)結(jié)構(gòu)表示中，表示形式唯一的是（ ）。 A．n B．n+1 C．n1 D．n/224．一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖包含（ ）條邊。 A．n（n1） B．n（n+1） C． n（n1）/2 D． n（n+1）/225．一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖包含（ ）條邊。 A．n（n1） B．n（n+1） C． n（n1）/2 D． n（n+1）/226．對(duì)于具有n個(gè)頂點(diǎn)的圖，若采用鄰接矩陣表示，則該矩陣的大小為（ ）。 A．n B．n2 C．n1 D．（n1）227．對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為（ ）。 A．n B．e C．2n D．2e28．對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，若采用鄰接表表示，則所有頂點(diǎn)鄰接表中的結(jié)點(diǎn)總數(shù)為（ ）。 A．n B．e C．2n D．2e29．在有向圖的鄰接表中，每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有（ ）鄰接點(diǎn)。 A．入邊 B． 出邊 C．入邊和出邊 D． 不是入邊也不是出邊 30．在有向圖的逆鄰接表中，每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有（ ）鄰接點(diǎn)。 A．入邊 B．出邊 C．入邊和出邊 D．不是入邊也不是出邊31．鄰接表是圖的一種（ ）。 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．一棵樹33．下列有關(guān)圖遍歷的說法不正確的是（ ）。A．連通圖的深度優(yōu)先搜索是一個(gè)遞歸過程B．圖的廣度優(yōu)先搜索中鄰接點(diǎn)的尋找具有“先進(jìn)先出”的特征C．非連通圖不能用深度優(yōu)先搜索法D．圖的遍歷要求每一頂點(diǎn)僅被訪問一次 34．無向圖的鄰接矩陣是一個(gè)（ ）。 A．對(duì)稱矩陣 B． 零矩陣 C．上三角矩陣 D．對(duì)角矩陣35．圖的深度優(yōu)先遍歷算法類似于二叉樹的（ ）遍歷。A．先序 B． 中序 C．后序 D．層次36．已知下圖所示的一個(gè)圖，若從頂點(diǎn)V1出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（ ）。 A．V1V2V4V8V3V5V6V7 B．V1V2V4V5V8V3V6V7 C．V1V2V4V8V5V3V6V7 D．V1V3V6V7V2V4V5V8V6V7V1V2V3V8V4V5　　　二、填空題1．結(jié)點(diǎn)的度是指結(jié)點(diǎn)所擁有的 。2．樹的度是指 。3．度大于0的結(jié)點(diǎn)稱作 或 。4．度等于0的結(jié)點(diǎn)稱作 或 。5．在一棵樹中，每個(gè)結(jié)點(diǎn)的 或