必看數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)題及部分答案解析

0一．是非題1.數(shù)據(jù)結(jié)構(gòu)(應(yīng)該是抽象數(shù)據(jù)類型)可用三元式表示〔D，S，P〕。其中：D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系，P是對(duì)D的根本操作集。(f)2簡單地說,數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。(t)3判斷帶頭結(jié)點(diǎn)的非空循環(huán)單鏈表〔頭指針為L〕中指針p所指結(jié)點(diǎn)是最后一個(gè)元素結(jié)點(diǎn)的條件是：p->next==L。(t)4線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)具有可直接存取?表中任一元素的優(yōu)點(diǎn)。(f)5線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。(f)6.在單鏈表P指針?biāo)附Y(jié)點(diǎn)之后插入S結(jié)點(diǎn)的操作是：P->next=S;S->next=P->next;。(順序弄反了)(f)7對(duì)于插入、刪除而言，線性表的鏈?zhǔn)酱鎯?chǔ)優(yōu)于順序存儲(chǔ)。(t)8.順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。(f)9.棧和隊(duì)列是操作上受限制的線性表。(t)10.隊(duì)列是與線性表完全不同的一種數(shù)據(jù)結(jié)構(gòu)。棧和隊(duì)列是操作上受限制的線性表(f)11.隊(duì)列是一種操作受限的線性表，凡對(duì)數(shù)據(jù)元素的操作僅限一端進(jìn)行。對(duì)列不是(f)12.棧和隊(duì)列也是線性表。如果需要，可對(duì)它們中的任一元素進(jìn)行操作。(f)13.棧是限定僅在表頭進(jìn)行插入和表尾進(jìn)行刪除運(yùn)算的線性表。(f)14.二叉樹中每個(gè)結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，而對(duì)一般的樹，那么無此限制，所以，二叉樹是樹的特殊情形。(f)15二叉樹是一棵結(jié)點(diǎn)的度最大為二的樹二叉樹和樹相互獨(dú)立。(f)16赫夫曼樹中結(jié)點(diǎn)個(gè)數(shù)一定是奇數(shù)。(t)17在二叉樹的中序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其左孩子結(jié)點(diǎn)的后面。(t)18假設(shè)B是一棵樹，B′是對(duì)應(yīng)的二叉樹。那么B的后根遍歷相當(dāng)于B′的后序遍歷后根遍歷相當(dāng)于中序遍歷。(f)19.通常，二叉樹的第i層上有2i-1個(gè)結(jié)點(diǎn)。應(yīng)該為1~2i-1個(gè)(f)20.中序線索二叉樹的優(yōu)點(diǎn)是便于在中序下查找直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)。(t)21二叉樹的先序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其孩子結(jié)點(diǎn)的前面。(t)22由樹結(jié)點(diǎn)的先根序列和后根序列可以唯一地確定一棵樹。(t)23鄰接多重表可以用以表示無向圖，也可用以表示有向圖。只能表示無向圖，有向圖用十字鏈表(f)24可從任意有向圖中得到關(guān)于所有頂點(diǎn)的拓?fù)浯涡驇Лh(huán)圖沒有。(f)25有向圖的十字鏈表是將鄰接表和逆鄰接表合二為一的鏈表表示形式。(t)26關(guān)鍵路徑是AOE網(wǎng)中源點(diǎn)到匯點(diǎn)的最短路徑。(f)27連通圖G的生成樹是一個(gè)包含G的所有n個(gè)頂點(diǎn)和n-1條邊的子圖。(f)28一個(gè)無向圖的連通分量是其極大的連通子圖。(t)29十字鏈表可以表示無向圖，也可用以表示有向圖。(f)30鄰接表可以表示有向圖，也可以表示無向圖?！瞭〕31.二叉排序樹的平均查找長度為O(logｎ)。(t)32.二叉排序樹的最大查找長度與〔LOG2N〕同階。(f)33選用好的HASH函數(shù)可防止沖突。哈希函數(shù)有幾種處理沖突的方法(f)34折半查找不適用于有序鏈表的查找。(t)35.對(duì)于目前所知的排序方法，快速排序具有最好的平均性能。(t)36對(duì)于任何待排序序列來說，快速排序均快于冒泡排序。(f)37在最壞情況下，堆排序的時(shí)間性能是O(nlogn),比快速排序好(t)38快速排序具有最好的平均時(shí)間性能，它在任何時(shí)候的時(shí)間復(fù)雜度都是O〔nlogn〕。(f)39.字符串是數(shù)據(jù)對(duì)象特定的線性表。(t)40.空串與空格串是相同的。(f)41.對(duì)于一棵m階的B-樹.樹中每個(gè)結(jié)點(diǎn)至多有m個(gè)關(guān)鍵字.除根之外的所有非終端結(jié)點(diǎn)至少有┌m/2┐個(gè)關(guān)鍵字。(f)42.當(dāng)二叉排序樹是一棵平衡二叉樹時(shí)，其平均查找長度為O(log2n)。(t)43.廣義表的表頭和表尾都是廣義表。(f)44二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表。(t)選擇題。1從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成(c)。A.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.順序組織和鏈接組織C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D.根本類型和組合類型2線性表L在(b)情況下適于使用鏈表結(jié)構(gòu)實(shí)現(xiàn)。A.不需修改L的結(jié)構(gòu)B.需不斷對(duì)L進(jìn)行刪除、插入C.需經(jīng)常修改L中結(jié)點(diǎn)值D.L中含有大量結(jié)點(diǎn)3帶頭結(jié)點(diǎn)的單鏈表L為空的判斷條件是b。帶頭結(jié)點(diǎn)的循環(huán)鏈表L為空的判斷條件是c。A.L==nullB.L->next==nullC.L->next==LD.L!=null4假設(shè)順序表中各結(jié)點(diǎn)的查找概率不等，那么可用如下策略提高順序查找的效率：假設(shè)找到指定的結(jié)點(diǎn)，將該結(jié)點(diǎn)與其后繼〔假設(shè)存在〕結(jié)點(diǎn)交換位置，使得經(jīng)常被查找的結(jié)點(diǎn)逐漸移至表尾。以下為據(jù)此策略編寫的算法，請(qǐng)選擇適當(dāng)?shù)膬?nèi)容，完成此功能。順序表的存儲(chǔ)結(jié)構(gòu)為：typedefstruct{ElemType*elem;//數(shù)據(jù)元素存儲(chǔ)空間，0號(hào)單元作監(jiān)視哨intlength;//表長度}SSTable;intsearch_seq(SSTableST,KeyTypekey){//在順序表ST中順序查找關(guān)鍵字等于key的數(shù)據(jù)元素。//假設(shè)找到，那么將該元素與其后繼交換位置，并返回其在表中的位置，否那么為0。ST.elem[0].key=key;i=ST.length;while(ST.elem[i].key!=key)f;if(G){ST.elem[i]←→ST.elem[i+1]；e；}returni;}A.i>0B.i>=0C.i<ST.lengthD.i<=ST.lengthE.i++F.i--G.A和C同時(shí)滿足H.B和D同時(shí)滿足5假設(shè)入棧順序?yàn)锳、B、C、D、E，那么以下(d)出棧序列是不可能的。A．A、B、C、D、EB．B、C、D、A、EC．C、D、B、E、AD．D、E、C、A、B6遞歸程序可借助于(c)轉(zhuǎn)化為非遞歸程序。a.線性表b.隊(duì)列c:棧d.數(shù)組7在以下數(shù)據(jù)結(jié)構(gòu)中(c)具有先進(jìn)先出〔FIFO〕特性，(b)具有先進(jìn)后出(FILO〕特性。a．線性表b．棧c．隊(duì)列d．廣義表8假設(shè)對(duì)編號(hào)為1，2，3的列車車廂依次通過扳道棧進(jìn)行調(diào)度，不能得到(e)的序列。a:1,2,3b:1,3,2c:2,1,3d:2,3,1e:3,1,2f:3,2,19在計(jì)算遞歸函數(shù)時(shí)，如不用遞歸過程，應(yīng)借助于(b)這種數(shù)據(jù)結(jié)構(gòu)。A.線性表B.棧C.隊(duì)列D.雙向隊(duì)列10假設(shè)帶頭結(jié)點(diǎn)的鏈表只設(shè)尾結(jié)點(diǎn)指針。以下選擇中〔c〕最適用于隊(duì)列。A〕單鏈表B〕雙向鏈表C循環(huán)單鏈表D〕雙向循環(huán)鏈表11棧和隊(duì)列的一個(gè)共同點(diǎn)是(c)。A.都是先進(jìn)先出B.都是先進(jìn)后出C.只允許在端點(diǎn)處插入和刪除元素D.沒有共同點(diǎn)12循環(huán)隊(duì)列用數(shù)組A[0..m-1]存放其元素值，設(shè)頭尾指針分別為front和rear，那么當(dāng)前隊(duì)列中的元素個(gè)數(shù)是(c)。A.rear-front-1B.Rear-front+1C.(rear-front+m)%mD.Rear-front13如下關(guān)于串的陳述中，正確的選項(xiàng)是(a,c)。A.串是數(shù)據(jù)元素類型特殊的線性表B.串中的元素是字母C.串中假設(shè)干個(gè)元素構(gòu)成的子序列稱為子串D.空串即為空格串14對(duì)字符串s=’data-structure’執(zhí)行操作replace(s,substring(s,6,8),’bas’)的結(jié)果是(b)。a:‘database’b:‘data-base’c:‘bas’d:‘data-basucture’15設(shè)有二維數(shù)組A5x7,每一元素用相鄰的4個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址.A的起始地址為100。那么按行存儲(chǔ)時(shí)，元素A06的第一個(gè)字節(jié)的地址是〔d〕按列存儲(chǔ)時(shí)，元素A06的第一個(gè)字節(jié)的地址是〔a〕a:220b:200c:140d:12416對(duì)廣義表A=〔〔a,(b)〕,(c,()),d〕執(zhí)行操作gettail(gethead(gettail(A)))的結(jié)果是：〔b〕。a:〔〕b:〔〔〕〕c:dd:(d)17假設(shè)用于通訊的電文僅由6個(gè)字符組成，字母在電文中出現(xiàn)的頻率分別為7,19,22,6,32,14。假設(shè)為這6個(gè)字母設(shè)計(jì)哈夫曼編碼〔設(shè)生成新的二叉樹的規(guī)那么是按給出的次序從左至右的結(jié)合，新生成的二叉樹總是插入在最右〕，那么頻率為7的字符編碼是〔g〕，頻率為32的字符編碼是〔c〕。a:00b:01c:10d:11e:011f:110g:1110h:111118對(duì)二叉排序樹〔c〕可得到有序序列。a:按層遍歷b:前序遍歷c:中序遍歷d:后序遍歷19設(shè)一棵二叉樹BT的存儲(chǔ)結(jié)構(gòu)如下:12345678lchild23006000dataABCDEFGHrchild05408700其中l(wèi)child，rchild分別為結(jié)點(diǎn)的左、右孩子指針域，data為結(jié)點(diǎn)的數(shù)據(jù)域。那么該二叉樹的高度為(d)；第3層有(a)個(gè)結(jié)點(diǎn)〔根結(jié)點(diǎn)為第1層〕。A．2B.3C.4D.520先序遍歷圖示二叉樹可得到〔a〕的序列。(A)／＼(B)(C)／＼＼(H)(D)(G)／＼(E)(F)＼(I)a) ABHDEFICGb) HBEDFIACGc)HEIFDBGCA21在有n個(gè)結(jié)點(diǎn)的二叉樹的二叉鏈表表示中，空指針數(shù)為n+1;非空指針樹為n-1;〔b〕。a.不定b.n+1c.nd.n-122假設(shè)某二叉樹有20個(gè)葉子結(jié)點(diǎn)，有20個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，那么該二叉樹的總結(jié)點(diǎn)數(shù)是(c)。度為2的節(jié)點(diǎn)n2=n0–1;其中no表示度為0的節(jié)點(diǎn)A．40B.55C.59D.6123某二叉樹的先序遍歷次序?yàn)閍bcdefg中序遍歷次序?yàn)閎adcgfe，那么該二叉樹的后序遍歷次序?yàn)椤瞔〕。層次遍歷次序?yàn)椤瞐〕。a:abcdefgb:cdebgfac:bdgfecad:edcgfba.24圖示的三棵二叉樹中(c)為最優(yōu)二叉樹。A)B)C)ca27abcddb752445abcd752425某二叉樹的后序遍歷和中序遍歷次序分別為DBFGECA和BDACFEG。那么其先序遍歷次序?yàn)椤瞓〕，層次遍歷次序?yàn)椤瞐〕。a:abcdefgb:abdcefgc:abcdfegd:abcdegf26某樹的先根遍歷次序?yàn)閍bcdefg后根遍歷次序?yàn)閏debgfa。假設(shè)將該樹轉(zhuǎn)換為二叉樹,其后序遍歷次序?yàn)椤瞕〕。a:abcdefgb:cdebgfac:cdegbfad:edcgfba27設(shè)x和y是二叉樹中的任意兩個(gè)結(jié)點(diǎn)，假設(shè)在先根序列中x在y之前，而在后根序列中x在y之后，那么x和y的關(guān)系是(c)。

A.x是y的左兄弟B.x是y的右兄弟

C.x是y的祖先D.x是y的子孫28用三叉鏈表作二叉樹的存儲(chǔ)結(jié)構(gòu)，當(dāng)二叉樹中有n個(gè)結(jié)點(diǎn)時(shí)，有(d)個(gè)空指針。A.n-1B.nC.n+1D.n+229對(duì)一棵完全二叉樹進(jìn)行層序編號(hào)。那么編號(hào)為n的結(jié)點(diǎn)假設(shè)存在右孩子,其位序是(d)。編號(hào)為n的結(jié)點(diǎn)假設(shè)存在雙親,其位置是(a)。a:n/2b:2nc:2n-1d:2n+1e:nf:2(n+1)30設(shè)森林F中有三棵樹，第一、第二和第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為m1、m2和m3，那么與森林F對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是(d)。A.m1B.m1+m2C.m3D.m2+m331以下二叉樹中，(a)可用于實(shí)現(xiàn)符號(hào)不等長高效編碼。a:最優(yōu)二叉樹b:次優(yōu)查找樹c:二叉平衡樹d:二叉排序樹32鄰接表存儲(chǔ)結(jié)構(gòu)以下圖的深度優(yōu)先遍歷算法類似于二叉樹的(a)遍歷。A.先根B.中根C.后根D.層次33設(shè)無向圖G=(V,E)和G’=(V’,E’)，假設(shè)G’是G的生成樹，那么下面不正確的說法是(b)。A.G’是G的子圖

B.G’是G的連通分量〔極大連通子圖稱為連通分量〕C.G’是G的無環(huán)子圖

D.G’是G的極小連通子圖且V’=V34任何一個(gè)連通圖的最小生成樹(b)。最小生成樹其實(shí)是最小權(quán)重生成樹的簡稱A．只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在efef35深度優(yōu)先遍歷圖使用了數(shù)據(jù)結(jié)構(gòu)〔b〕，而廣度優(yōu)先遍歷圖使用了數(shù)據(jù)結(jié)構(gòu)〔c〕。A〕數(shù)組B〕棧C〕隊(duì)列D〕線性表36某有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下圖。0E21∧1D034∧2C40E21∧1D034∧2C43B120∧4A2∧根據(jù)存儲(chǔ)結(jié)構(gòu)依教材中的算法其深度優(yōu)先遍歷次序?yàn)椤瞕〕。廣度優(yōu)先遍歷此序?yàn)椤瞔〕。各強(qiáng)連通分量的頂點(diǎn)集為〔h〕。有向圖的極大強(qiáng)連通子圖，稱為強(qiáng)連通分量a:abcde.b:edcba.c:ecdab.d:ecadb.e:abc及edf:bc及aedg:ab及cedh:ac及bed37以下查找方法中〔a〕適用于查找單鏈表。A〕順序查找B〕折半查找C〕分塊查找D〕hash查找38以下算法中〔c普利姆算法〕適用于求圖的最小代價(jià)生成樹?！瞓〕能對(duì)圖作廣度優(yōu)先遍歷。A〕DFS算法B〕BFS算法C〕Prim算法D〕Dijkstra算法39關(guān)鍵路徑是指在只有一個(gè)源點(diǎn)和一個(gè)匯點(diǎn)的有向無環(huán)網(wǎng)中源點(diǎn)至匯點(diǎn)〔c〕的路徑。a:弧的數(shù)目最多b:弧的數(shù)目最少c:權(quán)值之和最大d:權(quán)值之和最小40希表的查找效率取決于〔d〕。a:哈希函數(shù)b:處理沖突的方法。c:哈希表的裝填因子。d:以上都是41在Hash函數(shù)H(k)=kMODm中，一般來說，m應(yīng)取(c)。A.奇數(shù)B.偶數(shù)C.素?cái)?shù)D.充分大的數(shù)42在順序表查找中，為防止查找過程中每一步都檢測(cè)整個(gè)表是否查找完畢，可采用a方法。A.設(shè)置監(jiān)視哨B.鏈表存貯C.二分查找D.快速查找43靜態(tài)查找表和動(dòng)態(tài)查找表的區(qū)別在于(b)。A.前者是順序存儲(chǔ)，而后者是鏈?zhǔn)酱鎯?chǔ)B.前者只能進(jìn)行查找操作，而后者可進(jìn)行查找、插入和刪除操作C.前者只能順序查找，而后者只能折半查找D.前者可被排序，而后者不能被排序44在一個(gè)含有n個(gè)元素的有序表上進(jìn)行折半查找，找到一個(gè)元素最多要進(jìn)行(b)次元素比擬。A．log2(n)B.log2(n)+1C.log2(n+1)D.log2(n+1)+145設(shè)輸入序列為20,45,30,89,70,38,62，19依次插入到一棵2-3樹中(初始狀態(tài)為空)，該B-樹為〔b〕。再刪除38，該B-樹為〔f〕?！?062〕〔45〕〔19，20〕〔3845〕〔70，89〕〔30〕〔70〕〔1920〕〔38〕〔62〕〔89〕a:b:〔4570〕〔45〕〔20〕〔62〕〔89〕〔20〕〔70〕〔19〕〔30〕〔19〕(30,38〕〔62〕〔89〕c:d:〔3070〕〔45〕〔19，20〕〔4562〕〔89〕〔20〕〔70〕〔19〕〔30〕〔62〕〔89〕e:f:46根據(jù)插入次序〔80，90，100，110，85，70，75，60，72〕建立二叉排序樹。圖〔a〕是最終變化的結(jié)果。假設(shè)仍以該插入次序建立平衡二叉樹。圖〔c〕是最終變化的結(jié)果。8080709075906075851006070851007211072110a:b:9090751008010070801107570851106072856072c:d:47假設(shè)有序表中關(guān)鍵字序列為：14，20，25，32，34，45，57，69，77，83，92。畫出二叉判定樹計(jì)算，關(guān)鍵字在第幾層，就經(jīng)過幾次比擬對(duì)其進(jìn)行折半查找，那么在等概率情況下，查找成功時(shí)的平均查找長度是(c)。查找32時(shí)需進(jìn)行(c)次比擬。A.1B.2C.3D.448哈希表地址空間為A[9]，哈希函數(shù)為H(k)=kmod7，采用線性探測(cè)再散列處理沖突指加數(shù)為1。假設(shè)依次將數(shù)據(jù)序列：76,45,88,21,94,77,17存入該散列表中，那么元素17存儲(chǔ)的下標(biāo)為(h)；在等概率情況下查找成功的平均查找長度為(c)。A.0B.1C.2D.3E.4F.5G.6H.749假設(shè)從二叉樹的根結(jié)點(diǎn)到其它任一結(jié)點(diǎn)的路徑上所經(jīng)過的結(jié)點(diǎn)序列按其關(guān)鍵字遞增有序，那么該二叉樹是(c)。A.二叉排序樹B.赫夫曼樹C.堆D.平衡二叉樹50當(dāng)待排序序列的關(guān)鍵字次序?yàn)榈剐驎r(shí)，假設(shè)需為之進(jìn)行正序排序，以下方案中(d)為佳。A.起泡排序B.快速排序C.直接插入排序D.簡單項(xiàng)選擇擇排序51以下排序算法中，(d)算法可能會(huì)出現(xiàn)：初始數(shù)據(jù)有序時(shí)，花費(fèi)的時(shí)間反而最多。A.堆排序B.起泡排序C.歸并排序D.快速排序52在以下排序方法中，〔c快速排序〕方法平均時(shí)間復(fù)雜度為0(nlogn)，最壞情況下時(shí)間復(fù)雜度為0(n2)；〔d〕方法所有情況下時(shí)間復(fù)雜度均為0(nlogn)。a.插入排序b.希爾排序c.快速排序d.堆排序53一組待排序的記錄關(guān)鍵字初始排列如下：56,26,86,35,75,19,77,58,48,42以下選擇中〔d〕是快速排序一趟排序的結(jié)果?！瞔〕是希爾排序〔初始步長為3〕一趟排序的結(jié)果?！瞐〕是初始堆〔大堆頂〕。A〕86,75,77,58,42,19,56,35,48,26.B〕26,56,35,75,19,77,58,48,42,86.C〕35,26,19,42,58,48,56,75,86,77.D〕42,26,48,35,19,56,77,58,75,86.三．填空題1數(shù)據(jù)結(jié)構(gòu)通常有以下4類根本結(jié)構(gòu)：集合、線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖型結(jié)構(gòu)。2設(shè)單鏈表中結(jié)點(diǎn)形式為datanext，假設(shè)單鏈表長度大于等于2，指針p指向表中某個(gè)結(jié)點(diǎn)且p->next非空，此時(shí)假設(shè)要?jiǎng)h除指針p所指的結(jié)點(diǎn)，可以通過如下方法進(jìn)行：將p所指結(jié)點(diǎn)的后繼的元素值復(fù)制到該結(jié)點(diǎn)，然后刪除其后繼結(jié)點(diǎn)。相應(yīng)的語句序列為：p->data=p->next->data;p->next=p->next->next;free(p->next)換指針的同時(shí)還要交換數(shù)據(jù)3線性表的順序存儲(chǔ)結(jié)構(gòu)是以數(shù)組下標(biāo)來表示數(shù)據(jù)元素之間的邏輯關(guān)系的。4P是單鏈表中某一結(jié)點(diǎn)的指針，P既不是首元結(jié)點(diǎn)也不是尾元結(jié)點(diǎn)，Q是P的前驅(qū)結(jié)點(diǎn)指針。當(dāng)刪除P結(jié)點(diǎn)時(shí)，鏈表的鏈接可用語句〔q->netx=p->next〕實(shí)現(xiàn)。5某樹的先根遍歷次序?yàn)閍bcdefg后根遍歷次序?yàn)閏debgfa。假設(shè)將該樹轉(zhuǎn)換為二叉樹,其后序遍歷次序?yàn)椤病场哟伪闅v次序?yàn)椤病场?某二叉樹的先序遍歷次序?yàn)閍fbcdeg后序遍歷次序?yàn)閏edbgfa。其后序遍歷次序?yàn)椤病场哟伪闅v次序?yàn)椤病场?在二叉樹的第i層上至少有_____1____個(gè)結(jié)點(diǎn),至多有___2__個(gè)結(jié)點(diǎn),深度為k的二叉樹至多有_2_-1_______個(gè)結(jié)點(diǎn).8對(duì)樹的遍歷有先序遍歷樹和后序遍歷樹。假設(shè)以二叉鏈表作樹的存儲(chǔ)結(jié)構(gòu),那么樹的先序遍歷可借用二叉樹的遍歷算法來實(shí)現(xiàn),而樹的后序遍歷可借用二叉樹的中序遍歷遍歷算法來實(shí)現(xiàn)。9設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，那么此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少是2*h-1，至多是滿樹。10對(duì)任何一棵二叉樹T,假設(shè)其終端結(jié)點(diǎn)數(shù)為n0.度為2的結(jié)點(diǎn)為n2,那么n0與n2的關(guān)系為(n0=n2+1)。11如果對(duì)完全二叉樹中結(jié)點(diǎn)從1開始按層進(jìn)行編號(hào)，設(shè)最大編號(hào)為n；那么，可以斷定編號(hào)為i(i>1)的結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為(i/2向下取整)；所有編號(hào)〔i>n/2〕的結(jié)點(diǎn)為葉子結(jié)點(diǎn)。12n個(gè)頂點(diǎn)的連通圖至少有條邊，至多有n*(n-1)/2條邊，此時(shí)即是完全圖條邊。13對(duì)于圖的存儲(chǔ)結(jié)構(gòu)有〔數(shù)組表示法〕、〔鄰接表法〕(十字鏈表法)(鄰接多重表法)等方法。14在一個(gè)無向圖的鄰接表中，假設(shè)表結(jié)點(diǎn)的個(gè)數(shù)是m，那么圖中邊的條數(shù)是____m/2________條。15假設(shè)有序表中關(guān)鍵字序列為：12，22，33，44，55，66，77，88，99對(duì)其進(jìn)行折半查找，那么在等概率情況下，查找成功時(shí)的平均查找長度是〔〕。查找99時(shí)需進(jìn)行〔〕次比較。16在哈希表中，處理沖突的方法有開放定址法，再哈希表法，鏈地址法等。17在二叉樹的第i層上至少有_____個(gè)結(jié)點(diǎn),至多有_____個(gè)結(jié)點(diǎn),深度為k的二叉樹至多有個(gè)結(jié)點(diǎn).18對(duì)于一棵高度為K的二叉排序樹，結(jié)點(diǎn)數(shù)最少可有個(gè)，最多可有個(gè)。19用中序遍歷遍歷對(duì)二叉排序樹進(jìn)行訪問可得到有序序列。20Hash函數(shù)為H〔K〕=Kmod13，散列地址為0--14，用二次探測(cè)再散列處理沖突，關(guān)鍵字〔23，34，56，24，75，12，49,52，36，92〕的分布如圖，那么平均成功的查找長度為〔〕、平均失敗的查找長度為〔〕。012345678910111213145236925634232475124921一棵ｍ階的Ｂ-樹，第一層至少有一個(gè)結(jié)點(diǎn)；第二層至少有2個(gè)結(jié)點(diǎn)，除根之外的所有非終端結(jié)點(diǎn)至少有〔〕棵子樹，樹中每個(gè)結(jié)點(diǎn)至多有〔〕棵子樹。22在哈希表中，處理沖突的方法有開放定址法，，,。23哈希表的查找效率取決于〔①哈希函數(shù)是否均勻；

②處理沖突的方法；

③哈希表的裝填因子〕。24高度為4(包含不帶關(guān)鍵字的葉子結(jié)點(diǎn)層)的7階B樹最少有個(gè)關(guān)鍵字，最多有_________個(gè)關(guān)鍵字；如果其中的某結(jié)點(diǎn)正好有2個(gè)兒子，那么，該結(jié)點(diǎn)必定是結(jié)點(diǎn)。25對(duì)n個(gè)元素的序列進(jìn)行內(nèi)部排序，假設(shè)用起泡排序法，最少的比擬次數(shù)是n-1，最多的比擬次數(shù)是n(n-1)/2。25(算法填空)StatusPreordertraverse(BitreeT,Status(*Visit)(Telemtypee)){//先序非遞歸遍歷二叉樹。Initstack(S);Push(S,T);While(!stackempty(S)){While(gettop(S,p)&&________p_________){if(!Visit(p->data))returnERROR;___________push(s,p->lchild)__________;}Pop(S,p);if(_____(!stackempty(s)__________){_____pop(S,p);push(S,p->rchild);}}returnok;}26(算法填空)以下算法試圖完成在數(shù)組A中搜索有無關(guān)鍵字key，假設(shè)有，返回?cái)?shù)組下標(biāo),假設(shè)無，返回-1。在“”處填上適宜的內(nèi)容,完成該算法。intBinarySearch(keytypeA[],intlow,inthigh,keytypekey){while(low<=high) middle=(low+high)/2;if(A[middle]==key) returnmiddle; if(key<A[middle]) high=middle-1; elselow=middle+1;}return-1;}//endofBinarySearch27(算法填空)以下函數(shù)為堆排序中的堆調(diào)整過程〔調(diào)整H.r[s]的關(guān)鍵字，使H.r[s..m]成為一小頂堆〕。請(qǐng)?jiān)凇啊碧幪钌线m宜的內(nèi)容,完成該算法。Voidheapadjust(heaptype@H,ints,intm){rc=H.r[s];for(j=2*s;j<=m;j*=2){if(j<m&&r[j+1]>r[j])++j;if(rc>H.r[j])break;H.r[s]=H.r[j];s=j;}H.R[s]=rc;}//heapadjust圖示結(jié)構(gòu)題1在電文中只出現(xiàn)頻率為(5,26,7,23,20,19)的６個(gè)字符，畫出你建的哈夫曼樹，并給出其哈夫曼編碼。2.某二叉樹的后序遍歷和中序遍歷次序分別為DBFGECA和BDACFEG請(qǐng)畫出該二叉樹，并為之建立先序線索沒有左子樹，那么建立該節(jié)點(diǎn)的前驅(qū)，假設(shè)沒有右子樹，這指向該節(jié)點(diǎn)的后繼。3某二叉樹的先序遍歷次序?yàn)椋篴,b,c,d,e,f,g.中序遍歷次序?yàn)椋篵,a,d,f,e,g,c畫出該二叉樹，并在該二叉樹上建立中序線索。4某二叉樹的中序遍歷次序?yàn)锽EGFDAC，先序遍歷次序?yàn)锳BDEFGC。試畫出該二叉樹，并為之建立中序線索〔圖示之〕。5某二叉樹的后序遍歷和中序遍歷次序分別為FBEDGCA和FBADECG，請(qǐng)構(gòu)造并畫出該二叉樹。6設(shè)某一電文只出現(xiàn)a,b,c,d,e,f,g7個(gè)字母；出現(xiàn)頻率分別為30%,10%,05%,04%,13%,18%及20%，請(qǐng)給出各字母的哈夫曼編碼。7將圖示森林轉(zhuǎn)換為二叉樹，并對(duì)該二叉樹先序全序線索化。hdahdajibfecjibfecmlkgmlkg8將圖示森林轉(zhuǎn)換為二叉樹，并對(duì)該二叉樹中序全序線索化。5615619783297832449某二叉樹的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)表示如下：012345678910111213141516171819ABC

D

E

F

GH

I〔1〕試畫出此二叉樹的圖形表示?！?〕將此二叉樹看作森林的二叉樹表示，試將它復(fù)原為森林。10某有向圖如下圖：aa1〕給出其十字鏈表存儲(chǔ)結(jié)構(gòu)2〕給出其深度優(yōu)先遍歷次序。3〕給出其廣度優(yōu)先遍歷次序。cbcb4〕給出各強(qiáng)連通分量。eded11設(shè)輸入序列為20,45,30,89,70,38,62,19，依次插入到一棵2-3樹中(初始狀態(tài)為空)，請(qǐng)畫出該B-樹。右圖為一棵3階B－樹?！?0，25〕1)畫出在該樹上插入元素15／│＼后的B－樹。(10，14)〔21〕〔35〕2)接著，再刪除元素35，畫出刪除后的B－樹。13Hash函數(shù)為H〔K〕=Kmod13，散列地址為0--14，用線性探測(cè)再散列處理沖突，給出關(guān)鍵字〔56，34，68，23，16，70，48，35，83，12，14，57〕在散列地址的分布。并指出平均成功的查找長度是多少?0123456789101112131414根據(jù)插入次序〔20，30，70，60，10，100，110，90，80?！辰⑵胶獾亩媾判驑洹?5設(shè)哈希表長為16，哈希函數(shù)為H(key)=keymod13，用開放定址法的二次探測(cè)再散列處理沖突〔di=12，-12，22，-22，32，-32……〕。依次存入12個(gè)元素：56，82，17,24,36,21,83,96,13,34,57,50。請(qǐng)畫出它們?cè)诒碇械姆植记樾巍?6待排序序列為：25,12,9,20,7,31,24,35,17,10，試寫出：(1).堆排序初始建堆(大頂堆)的結(jié)果；(2).以第一個(gè)元素為樞軸的快速排序一趟掃描的結(jié)果；(3).希爾排序第一趟(增量為5)的結(jié)果。算法設(shè)計(jì)題1設(shè)有一個(gè)帶頭結(jié)點(diǎn)、元素按值遞增有序的單鏈表，結(jié)點(diǎn)的類型定義如下：typedefstructLNode{intdata;struct