【正文】 作業(yè)覆蓋教材第35章的內(nèi)容）一、單項選擇題1．若讓元素1，2，3依次進(jìn)棧，則出棧順序不可能為（ ）。則隊列的輸出序列是（ ）。A．先移動棧頂指針，再存入元素 B．先存入元素，再移動棧頂指針 C．先后次序無關(guān)緊要 D．同時進(jìn)行4．在一個棧頂指針為top的鏈棧中，將一個p指針?biāo)傅慕Y(jié)點(diǎn)入棧，應(yīng)執(zhí)行（ ）。 B．pnext=topnext。C．pnext=top。 D．pnext=topnext。5．在一個棧頂指針為top的鏈棧中刪除一個結(jié)點(diǎn)時，用 x保存被刪結(jié)點(diǎn)的值，則執(zhí)行（ ）。top=topnext。C．top=topnext。 D．x=topdata。6．一般情況下，將遞歸算法轉(zhuǎn)換成等價的非遞歸算法應(yīng)該設(shè)置（ ）。 A．a(chǎn)bcd*+ B．a(chǎn)bc+*d C．a(chǎn)bc*++d D．+*abcd8．判斷一個順序隊列sq（最多元素為m0）為空的條件是（ ）。 A．Qfront==Qrear B．Qfront!=Qrear C．Qfront==(Qrear+1)% m0 D．Qfront!= (Qrear+1)%m0 10．判斷一個循環(huán)隊列Q（最多元素為m0）為空的條件是（ ）。 A．stop==0 B．stop!=0 C．stop==n1 D．stop!=n1 12．一個隊列的入隊順序是a,b,c,d，則離隊的順序是（ ）。 A．必須判斷棧是否滿 B．判斷棧元素類型 C．必須判斷棧是否空 D．對棧不作任何判斷14．在解決計算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入緩沖區(qū)中，而打印機(jī)則從緩沖區(qū)中取出數(shù)據(jù)打印，該緩沖區(qū)應(yīng)該是一個（ ）結(jié)構(gòu)。A．遞歸部分 B．終止條件和遞歸部分 C．迭代部分 D．終止條件和迭代部分16．從一個棧頂指針為top的鏈棧中刪除一個結(jié)點(diǎn)時，用變量x保存被刪結(jié)點(diǎn)的值，則執(zhí)行（ ）。 top=topnext。 C．top=topnext。 D．top=topnext。17．在一個鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，則刪除一個結(jié)點(diǎn)的運(yùn)算為（ ）。 B．r=rnext。 D．f=rnext。 A．fnext=s。 B．rnext=s。 C．snext=r。 D．snext=f。（ ）。A．求子串 B．連接 C．匹配 D．求串長 21．串是（ ）。A．串中所含不同字母的個數(shù) B．串中所含字符的個數(shù)C．串中所含不同字符的個數(shù) D．串中所含非空格字符的個數(shù)23. 若串S==“English”，其子串的個數(shù)是（ ）。A．串是字符的有限序列 B．空串是由空格構(gòu)成的串 C．模式匹配是串的一種重要運(yùn)算 D．串即可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯? 25．串與普通的線性表相比較，它的特殊性體現(xiàn)在（ ）。A．相同 B．不相同 C．可能相同 D．無法確定27．兩個字符串相等的條件是（ ）。則應(yīng)該采用（ ）存儲比較合適（ ）。A．64 B．28C．70 D．9030．稀疏矩陣采用壓縮存儲的目的主要是（ ）。 A．不可能是原子 B．只能是子表 C．只能是原子 D．可以是子表或原子 32．常對數(shù)組進(jìn)行的兩種基本操作是（ ）。 A．1140 B．1145 C． 1120 D．112534．設(shè)有一個20階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素a9,2在一維數(shù)組B中的下標(biāo)是（ ）。A．不可能是子表 B．只能是子表 C．只能是原子 D．可以是子表或原子二、填空題1．棧是限定在表的一端進(jìn)行插入和刪除操作的線性表，又稱為 。3．往棧中插入元素的操作方式是：先 ，后 。5．循環(huán)隊列隊頭指針在隊尾指針 位置，隊列是“滿”狀態(tài)6．在隊列的順序存儲結(jié)構(gòu)中，當(dāng)插入一個新的隊列元素時，尾指針 ，當(dāng)刪除一個元素隊列時，頭指針 。8．向順序棧插入新元素分為三步：第一步進(jìn)行 判斷，判斷條件是 ；第二步是修改 ；第三步是把新元素賦給 。第二步是把 ；第三步 。10．一個遞歸算法必須包括 和 。12．在將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式和計算后綴表達(dá)式的算法中，都需要使用棧，對于前者，進(jìn)入棧中的元素為表達(dá)式中的 ，而對于后者，進(jìn)入棧的元素為 ，中綴表達(dá)式(a+b)/c(fd/c)所對應(yīng)的后綴表達(dá)式是 。操作。和________。 (結(jié)點(diǎn)的指針域為next)19．在一個鏈隊中，設(shè)f和r分別為隊頭和隊尾指針，則刪除一個結(jié)點(diǎn)的操作為________。21．串的兩種最基本的存儲方式是 和 。23．需要壓縮存儲的矩陣可分為 矩陣和 矩陣兩種。25．廣義表A（（a,b,c）,(d,e,f)）的表尾為 。27．設(shè)有n階對稱矩陣A，用數(shù)組s進(jìn)行壓縮存儲，當(dāng)i179。（數(shù)組元素的下標(biāo)從1開始）28．對稀疏矩陣進(jìn)行壓縮存儲，矩陣中每個非零元素對應(yīng)的三元組包括該元素的_______、_______和_______三項信息。2．簡述隊列和一般線性表的區(qū)別。（2）如果輸入序列由A，B，C，D組成，試給出全部可能的輸出序列和不可能的輸出序列。四、程序填空題1．在下面空格處填寫適當(dāng)?shù)恼Z句，以使下面的循環(huán)隊列的入隊和出隊算法完整。define FALSE 0。typedef charelemtype。 int front,rear。Sequeuetype Q。return(FALSE)。 }} /*encqueue*/elemtype del_cqueue(sequeuetype *Q){ if ( (4) ) { Printf(〝The queue is empty !\n〞) return(NULL)。 }} /*del_cqueue*/ ，以使下面的鏈?zhǔn)疥犃腥〕鲈氐乃惴ㄍ暾? if (qfront==qrear)　 /*隊空*/ {printf(“underflow”)。} while (qfrontnext != NULL) {p=qfrontnext。 (2) } （3） 。（2）入隊列enqueue(Q,x):將元素x插入到隊列Q中。（4）取隊首元素gethead(Q):返回當(dāng)前隊首元素。（6）顯示隊列中元素：dispqueue(Q)。數(shù)據(jù)結(jié)構(gòu)（本）課程作業(yè)作業(yè)3（本部分作業(yè)覆蓋教材第67章的內(nèi)容）一、單項選擇題，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30，則葉子結(jié)點(diǎn)數(shù)為（ ）。 A．2k B．2k1 C．2k1 D．2k1 3．二叉樹的深度為k,則二叉樹最多有（ ）個結(jié)點(diǎn)。 A．a(chǎn)bdec B．debac C．debca D．a(chǎn)bedc5．樹最適合于用來表示（ ）。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}的四個結(jié)點(diǎn)構(gòu)成的哈夫曼樹的帶權(quán)路徑長度是（ ）。A．33 B．34 C．35 D．369．如果將給定的一組數(shù)據(jù)作為葉子數(shù)值，所構(gòu)造出的二叉樹的帶權(quán)路徑長度最小，則該樹稱為（ ）。A．二叉樹中度為0的結(jié)點(diǎn)的個數(shù)等于度為2的結(jié)點(diǎn)的個數(shù)加1B．二叉樹中結(jié)點(diǎn)個數(shù)必大于0C．完全二叉樹中，任何一個結(jié)點(diǎn)的度，或者為0或者為2 D．二叉樹的度是211．在一棵度為3的樹中，度為3的結(jié)點(diǎn)個數(shù)為2，度為2的結(jié)點(diǎn)個數(shù)為1，則度為0的結(jié)點(diǎn)個數(shù)為（ ）。A．31 B．32 C．33 D．1613. 利用n個值作為葉結(jié)點(diǎn)的權(quán)生成的哈夫曼樹中共包含有( )個結(jié)點(diǎn)。 A. n B. n1 C. n+1 D. 2*n1 15. 利用12這四個值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫曼樹，該樹中所有葉子的最長帶權(quán)路徑長度為( )。A．分支結(jié)點(diǎn) B．葉結(jié)點(diǎn) C．樹根結(jié)點(diǎn) D．空結(jié)點(diǎn)17．在一棵二叉樹中，若編號為i的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號為（ ）。 A．n B．n1 C．n+1 D．2n19．設(shè)一棵有n個葉結(jié)點(diǎn)的二叉樹，除葉結(jié)點(diǎn)外每個結(jié)點(diǎn)度數(shù)都為2，則該樹共有（ ）個結(jié)點(diǎn)。 A．20 B．21 C．23 D．3021．在一個圖G中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)之和的（ ）倍。 A．鄰接矩陣表示法 B．鄰接表表示法 C．逆鄰接表表示法 D．鄰接表和逆鄰接表 23．在圖的存儲結(jié)構(gòu)表示中，表示形式唯一的是（ ）。 A．n（n1） B．n（n+1） C． n（n1）/2 D． n（n+1）/225．一個具有n個頂點(diǎn)的有向完全圖包含（ ）條邊。 A．n B．n2 C．n1 D．（n1）227．對于一個具有n個頂點(diǎn)和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為（ ）。 A．n B．e C．2n D．2e29．在有向圖的鄰接表中，每個頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有（ ）鄰接點(diǎn)。 A．入邊 B．出邊 C．入邊和出邊 D．不是入邊也不是出邊31．鄰接表是圖的一種（ ）。 A．完全圖 B．連通圖 C．有回路 D．一棵樹33．下列有關(guān)圖遍歷的說法不正確的是（ ）。 A．對稱矩陣 B． 零矩陣 C．上三角矩陣 D．對角矩陣35．圖的深度優(yōu)先遍歷算法類似于二叉樹的（ ）遍歷。 A．V1V2V4V8V3V5V6V7 B．V1V2V4V5V8V3V6V7 C．V1V2V4V8V5V3V6V7 D．V1V3V6V7V2V4V5V8V6V7V1V2V3V8V4V5　　　二、填空題1．結(jié)點(diǎn)的度是指結(jié)點(diǎn)所擁有的 。3．度大于0的結(jié)點(diǎn)稱作 或 。5．在一棵樹中，每個結(jié)點(diǎn)的 或者說每個結(jié)點(diǎn)的 稱為