1、數(shù)據(jù)結(jié)構(gòu)-C語(yǔ)言版第一章 緒論單項(xiàng)選擇題1在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的基本單位是_ _。A. 數(shù)據(jù)項(xiàng) B. 數(shù)據(jù)類型 C. 數(shù)據(jù)元素 D. 數(shù)據(jù)變量 2數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系被稱為_ _。 A. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) B. 數(shù)據(jù)的基本操作 C. 程序的算法 D. 數(shù)據(jù)的邏輯結(jié)構(gòu)3在數(shù)據(jù)結(jié)構(gòu)中，與所使用計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的_ _。 A. 存儲(chǔ)結(jié)構(gòu) B. 邏輯和物理結(jié)構(gòu) C. 邏輯結(jié)構(gòu) D. 物理結(jié)構(gòu) 4在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，數(shù)據(jù)之間的關(guān)系是通過_ _體現(xiàn)的。A. 數(shù)據(jù)在內(nèi)存的相對(duì)位置 B. 指示數(shù)據(jù)元素的指針C. 數(shù)據(jù)的存儲(chǔ)地址 D. 指針5計(jì)算算法的時(shí)間復(fù)雜度是屬于一種_ _。A. 事前統(tǒng)計(jì)的方法 B

2、. 事前分析估算的方法 C. 事后統(tǒng)計(jì)的方法 D. 事后分析估算的方法6在對(duì)算法的時(shí)間復(fù)雜度進(jìn)行估計(jì)的時(shí)候，下列最佳的時(shí)間復(fù)雜度是_ _。 A. n2 B. nlogn C. n D. logn 7設(shè)使用某算法對(duì)n個(gè)元素進(jìn)行處理，所需的時(shí)間是T(n)=100nlog2n+200n+2000，則該算法的漸近時(shí)間復(fù)雜度為_ _。A. O(1) B. O(n) C. O(200n) D. O(nlog2n)CDCBBDD第二章 線性表單項(xiàng)選擇題1鏈表不具有的特點(diǎn)是_ _。 A. 可隨機(jī)訪問任一元素 B. 插入和刪除時(shí)不需要移動(dòng)元素C. 不必事先估計(jì)存儲(chǔ)空間 D. 所需空間與線性表的長(zhǎng)度正比 2設(shè)順序

3、表的每個(gè)元素占8個(gè)存儲(chǔ)單元。第1個(gè)單元的存儲(chǔ)地址是100，則第6個(gè)元素占用的最后一個(gè)存儲(chǔ)單元的地址為 。A. 139 B. 140 C. 147 D. 1483在線性鏈表存儲(chǔ)結(jié)構(gòu)下，插入操作算法 。A. 需要判斷是否表滿 B. 需要判斷是否表空 C. 不需要判斷表滿 D. 需要判斷是否表空和表滿 4在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行 。 A. p->next = p->next->next; B. p->next = p->next; C. p = p->next->next; D. p = p->next; p->next

4、 = p->next->next; 5將長(zhǎng)度為n的單鏈表接在長(zhǎng)度為m的單鏈表之后的算法時(shí)間復(fù)雜度為 。 A. O(n) B. O(1) C. O(m) D. O(m+n)6需要預(yù)分較大空間，插入和刪除不需要移動(dòng)元素的線性表，其存儲(chǔ)結(jié)構(gòu)是 。 A. 單鏈表 B. 靜態(tài)鏈表 C. 線性鏈表 D. 順序存儲(chǔ)方式ACCABB填空題1在帶表頭結(jié)點(diǎn)的單鏈表中，當(dāng)刪除某一指定結(jié)點(diǎn)時(shí)，必須找到該結(jié)點(diǎn)的_結(jié)點(diǎn)。2在單鏈表中，指針p所指結(jié)點(diǎn)為最后一個(gè)結(jié)點(diǎn)的條件是 。3將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是 。 4在一個(gè)長(zhǎng)度為n的順序表中第i個(gè)元素（1in）之前插入一個(gè)元素時(shí)，需

5、向后移動(dòng)元素的個(gè)數(shù)是 。5在長(zhǎng)度為n的順序表中插入一個(gè)元素的時(shí)間復(fù)雜度為 。1前驅(qū) 2 p->next=NULL3.14. n-i+15. O(n)例題解析【例2-1】 編寫一個(gè)算法將一個(gè)單鏈表逆轉(zhuǎn)，要求在原表上進(jìn)行，不允許重新建鏈表。 解：該算法可以在遍歷原表的時(shí)候?qū)⒏鹘Y(jié)點(diǎn)的指針逆轉(zhuǎn)，從原表的第一個(gè)結(jié)點(diǎn)開始，頭結(jié)點(diǎn)的指針在最后修改成指向原表的最后一個(gè)結(jié)點(diǎn)，即新表的第一個(gè)結(jié)點(diǎn)。實(shí)現(xiàn)本題功能的函數(shù)如下： void inverse(Lnode *h) s=h->next; if(s=NULL) return; q=NULL; p=s; while(p!=NULL) p=p->ne

6、xt; s->next=q; /*逆轉(zhuǎn)指針*/ q=s; /*指針前移*/ s=p; h->next=q; /*頭指針h的后繼是p*/【例2-2】 編寫一算法將兩個(gè)按元素值遞增有序排列的單鏈表A和B歸并成一個(gè)按元素值遞增有序排列的單鏈表C。解：對(duì)于兩個(gè)或兩個(gè)以上的，結(jié)點(diǎn)按元素值有序排列的單鏈表進(jìn)行操作時(shí)，應(yīng)采用“指針平行移動(dòng)，依次掃描完成”的方法。從兩表的第一個(gè)結(jié)點(diǎn)開始順鏈表逐個(gè)將對(duì)應(yīng)數(shù)據(jù)元素進(jìn)行比較，復(fù)制小的并插入c表尾。當(dāng)兩表中之一已到表尾，則復(fù)制另一個(gè)鏈表的剩余部分，插入到c表尾。設(shè)pa、pb分別指向兩表當(dāng)前結(jié)點(diǎn)，p指向c表的當(dāng)前表尾結(jié)點(diǎn)。若設(shè)A中當(dāng)前所指的元素為a，B中當(dāng)前

7、所指的元素為b，則當(dāng)前應(yīng)插入到 C中的元素c為 例如：A=(3,5,8,11) B=(2,6,8,9,11,15,20)則 C=(2,3,5,6,8,8,9,11,11,15,20)實(shí)現(xiàn)本題功能的函數(shù)如下：Lnode *hb(Lnode *pa,Lnode *pb)Lnode *p,*q,*pc; pc=(Lnode*)malloc(sizeof(Lnode); /*建立表c 的頭結(jié)點(diǎn)pc*/ p=pc; /*p指向C表頭結(jié)點(diǎn)*/ while(pa!=NULL&&pb!=NULL) q=(Lnode*)malloc(sizeof(Lnode); /*建立新結(jié)點(diǎn)q*/ if(pb

8、->data<pa->data) /*比較A、B表中當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)域值的大小*/ q->data=pb->data; /*B中結(jié)點(diǎn)值小，將其值賦給q的數(shù)據(jù)域*/ pb=pb->next; /*B中指針pb后移*/ else q->data=pa->data; /*相反，將A結(jié)點(diǎn)值賦給q的數(shù)據(jù)域*/ pa=pa->next; /*A中指針pa后移*/ p->next=q; /*將q接在p的后面*/p=q; /*p始終指向C表當(dāng)前尾結(jié)點(diǎn)*/while(pa!=NULL) /*若表A比B長(zhǎng)，將A余下的結(jié)點(diǎn)鏈在C表尾*/ q=(Lnode*)

9、malloc(sizeof(Lnode); q->data=pa->data; pa=pa->next; p->next=q; p=q; while(pb!=NULL) /*若表B比A長(zhǎng)，將B余下的結(jié)點(diǎn)鏈在C表尾*/ q=(Lnode*)malloc(sizeof(Lnode); q->data=pb->data; pb=pb->next; p->next=q; p=q; p->next=NULL;p=pc; /*p指向表C的頭結(jié)點(diǎn)pc*/pc=p->next; /*改變指針狀態(tài)，使pc指向p的后繼*/free(p); /*釋放p空間

10、*/return (pc); 此算法的時(shí)間復(fù)雜度為O(m+n)，其中m，n分別是兩個(gè)被合并表的表長(zhǎng)。第三章 棧和隊(duì)列單項(xiàng)選擇題1在初始為空的堆棧中依次插入元素f，e，d，c，b，a以后，連續(xù)進(jìn)行了三次刪除操作，此時(shí)棧頂元素是 。 A. B.C. D. 2若某堆棧的輸入序列是1，2，3，.，n，輸出序列的第一個(gè)元素為n，則第i個(gè)輸出元素為 。A. i B. n-i C. n-i+1 D. 哪個(gè)元素?zé)o所謂3向一個(gè)棧頂指針為h的帶頭結(jié)點(diǎn)鏈棧中插入指針s所指的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行 。 A. h->next = s; B. s->next = h; C. s->next = h; h = h

11、->next; D. s->next = h->next; h->next=s; 4一個(gè)棧的入棧序列是 a，b，c，d，e，則棧的不可能的輸出序列是 。 A. edcba B. decba C. dceab D. abcde5棧和隊(duì)列的共同點(diǎn)是 。A. 都是先進(jìn)后出 B. 都是先進(jìn)先出 C. 只允許在端點(diǎn)處插入和刪除元素 D. 沒有共同點(diǎn)6對(duì)于循環(huán)隊(duì)列 。A. 無法判斷隊(duì)列是否為空 B. 無法判斷隊(duì)列是否為滿 C. 隊(duì)列不可能滿 D. 以上說法都不是7. 若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前隊(duì)尾指針rear和隊(duì)頭指針front的值分別為0和3。當(dāng)從隊(duì)列中刪除一個(gè)

12、元素，再加入兩個(gè)元素后，rear和front的值分別為 。A. 1和5 B. 2和4 C. 4和2 D. 5和18. 判定一個(gè)循環(huán)隊(duì)列 QU（最多元素為 m0）為滿隊(duì)列的條件是 。A. QU->front=QU->rear B. QU->front!=QU->rearC. QU->front=(QU->rear+1) % m0 D. QU->front!=(QU->rear+1) % m0 9.判定一個(gè)循環(huán)隊(duì)列 QU（最多元素為 m0）為空的條件是 。A. QU->front=QU->rear B. QU->front!=QU-

13、>rear C. QU->front=(QU->rear+1) % m0 D. QU->front!=(QU->rear+1) % m0 BCDCCDACA填空題1在求表達(dá)式值的算符優(yōu)先算法中使用的主要數(shù)據(jù)結(jié)構(gòu)是 。2設(shè)有一個(gè)空棧，現(xiàn)輸入序列為1，2，3，4，5。經(jīng)過push，push，pop，push，pop，push，pop，push后，輸出序列是 。3僅允許在同一端進(jìn)行插入和刪除的線性表稱為 。7在順序棧s中，棧為空的條件是 ，棧為滿的條件是_。4用S表示入棧操作，X表示出棧操作，若元素入棧順序?yàn)?234，為了得到1342出棧順序，相應(yīng)的S、X操作串為 。5

14、用一個(gè)大小為1000的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，當(dāng)前rear和front的值分別為0和994，若要達(dá)到隊(duì)滿的條件，還需要繼續(xù)入隊(duì)的元素個(gè)數(shù)是 。1.棧2. 2 3 43. 棧4. s.top=s.base, s.top-s.base>=s.stacksize SXSSXSXX5. 993例題解析【例3-1】 編程實(shí)現(xiàn)：用除法把十進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)。 解：算法思想：用初始十進(jìn)制數(shù)除以2把余數(shù)記錄下來并且若商不為0則再用商去除以2直到商為0，這時(shí)把所有的余數(shù)按出現(xiàn)的逆序排列起來（先出現(xiàn)的余數(shù)排在后面，后出現(xiàn)的余數(shù)排在前面）就得到了相應(yīng)的二進(jìn)制數(shù)，如把十進(jìn)制數(shù)35轉(zhuǎn)換成二進(jìn)制數(shù)的過程如圖3-1所示

15、。35178421011001余數(shù)結(jié)果：10011 圖3-1 十進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)的過程由題意可知，我們可以用一個(gè)棧來保存所有的余數(shù)，當(dāng)商為0時(shí)則讓棧里的所有余數(shù)出棧則可以得到正確的二進(jìn)制數(shù)，算法可描述如下：void conversion()Stack S; int n; InitStack(&S); printf("Input a number to convert:n");scanf("%d",&n); if(n<0) printf("nThe number must be over 0."); retur

16、n;if(n=0) Push(S,0); while(n!=0) Push(S,n%2); n=n/2; printf("the result is: "); while(!StackEmpty(*S) printf("%d", Pop(S);第四章 串單項(xiàng)選擇題1串是一種特殊的線性表，其特殊性體現(xiàn)在 。A. 可以順序存儲(chǔ) B. 數(shù)據(jù)元素是一個(gè)字符 C. 可以鏈接存儲(chǔ) D. 數(shù)據(jù)元素可以是多個(gè)字符 2設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作 。 A. 連接 B. 模式匹配 C. 求子串 D. 求串長(zhǎng)3串是一個(gè) B 的序列。A. 不少于一個(gè)字母

17、 B. 有限個(gè)字符 C. 不少于一個(gè)字符 D. 空格或字母 4已知串s=ABCDEFGH，則s的所有不同子串的個(gè)數(shù)為 。 A. 8 B. 9 C. 36 D. 37BBBD填空題1兩個(gè)串相等的充分必要條件是 。2空格串是 ,其長(zhǎng)度等于 。3在串S=tuition中，以t為首字符且值不相同的子串有 個(gè)。4. 使用“求子串”substring(S,pos,len)和“聯(lián)接”concat(S1,S2)的串操作，可從串s=conduction中的字符得到串t=cont，則求t的串表達(dá)式為 。1. 兩個(gè)串的長(zhǎng)度相等且對(duì)應(yīng)位置的字符相同2. 由一個(gè)或多個(gè)空格字符組成的串 其包含的空格個(gè)數(shù)3. 10 4.

18、concat(subString(s,1,3),substring(s,7,1)第五章 數(shù)組與廣義表單項(xiàng)選擇題1常對(duì)數(shù)組進(jìn)行的兩種操作是 。A. 建立與刪除 B. 索引和修改 C. 查找和修改 D. 查找與索引 2假設(shè)8行10列的二維數(shù)組a1.8, 1.10分別以行序?yàn)橹餍蚝鸵粤行驗(yàn)橹餍蝽樞虼鎯?chǔ)時(shí)，其首地址相同，那么以行序?yàn)橹餍驎r(shí)元素a35的地址與以列序?yàn)橹餍驎r(shí)元素 _ _的地址相同。A. a53 B. a83 C. a14 D. 答案A、B、C均不對(duì) 3將一個(gè)A1.100,1.100的三對(duì)角矩陣以行序?yàn)橹餍虼嫒胍痪S數(shù)組B1.298中，元素A66，65在B數(shù)組中的位置k等于_ _。A. 198

19、 B. 197 C. 196 D. 1954稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即 。 A. 二維數(shù)組和三維數(shù)組 B. 三元組和散列C. 三元組和十字鏈表 D. 散列和十字鏈表5. 一個(gè)非空廣義表的表頭_ _。 A. 不可能是子表 B. 只能是子表 C. 只能是原子 D. 可以是原子或子表6. 設(shè)head(L)、tail(L)分別為取廣義表表頭、表尾操作，則從廣義表L=(x,y,z),a,(u,v,w)中取出原子u的運(yùn)算為_ _。A. head(tail(tail(head(L) B. tail(head(head(tail(L) C. head(tail(head(tail(L) D. hea

20、d(head(tail(tail(L)7廣義表(a,(b,(c,d,(e,f),g)的深度為_ _。 A. 3 B. 4 C. 5 D. 6CDDCDDC填空題1將下三角矩陣A1.8,1.8的下三角部分逐行地存儲(chǔ)到起始地址為1000的內(nèi)存單元中，已知每個(gè)元素占四個(gè)單元，則元素A7,5的地址為 。 2二維數(shù)組A0.9,0.19采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占一個(gè)存儲(chǔ)單元，并且元素A0,0的存儲(chǔ)地址是200，則元素A6,12的地址是 。 3二維數(shù)組A10.20,5.10采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占4個(gè)存儲(chǔ)單元，并且元素A10,5的存儲(chǔ)地址是1000，則元素A18,9的地址是 。4有一個(gè)10階對(duì)

21、稱矩陣A，采用壓縮存儲(chǔ)方式（以行序?yàn)橹餍虼鎯?chǔ)，且元素A0,0地址為1），則元素A8,5的地址是 。5設(shè)HAEDp為求廣義表p的表頭函數(shù)，TAILp為求廣義表p的表尾函數(shù)，其中 是函數(shù)的符號(hào)，給出下列廣義表的運(yùn)算結(jié)果： HEAD(a，b，c)的結(jié)果是 。 TAIL(a，b，c)的結(jié)果是 。 HEAD(a)，(b)的結(jié)果是 。 TAIL(a)，(b)的結(jié)果是 。 HEADTAIL(a，b，c)的結(jié)果是 。TAILHEAD(a，b)，(c，d)的結(jié)果是 。 HEADHEAD(a，b)，(c，d)的結(jié)果是 。 TAILTAIL(a，(c，d)的結(jié)果是 。 a；(b，c)；(a)；(b)；b；(b)；a

22、；( )1. 11002. 3323. 12084. 42 5. 第6章 樹和二叉樹選擇題1 以下說法錯(cuò)誤的是 。A.樹形結(jié)構(gòu)的特點(diǎn)是一個(gè)結(jié)點(diǎn)可以有多個(gè)直接前趨B.線性結(jié)構(gòu)中的一個(gè)結(jié)點(diǎn)至多只有一個(gè)直接后繼C.樹形結(jié)構(gòu)可以表達(dá)(組織)更復(fù)雜的數(shù)據(jù)D.樹(及一切樹形結(jié)構(gòu))是一種"分支層次"結(jié)構(gòu)2. 如圖6-2所示的 4 棵二叉樹中， 不是完全二叉樹。圖6-2 4 棵二叉樹3. 以下說法錯(cuò)誤的是 。A.完全二叉樹上結(jié)點(diǎn)之間的父子關(guān)系可由它們編號(hào)之間的關(guān)系來表達(dá)B.在三叉鏈表上，二叉樹的求雙親運(yùn)算很容易實(shí)現(xiàn)C.在二叉鏈表上，求根，求左、右孩子等很容易實(shí)現(xiàn)D.在二叉鏈表上，求雙親運(yùn)算

23、的時(shí)間性能很好4. 如圖6-3所示的 4 棵二叉樹， 是平衡二叉樹。 圖6-3 4 棵二叉樹5. 如圖6-4所示二叉樹的中序遍歷序列是 。 A. abcdgef B. dfebagc C. dbaefcg D. defbagc圖6-4 1 棵二叉樹6. 某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序是 abdgcefh，中序遍歷的結(jié)點(diǎn)訪問順序是dgbaechf，則其后序遍歷的結(jié)點(diǎn)訪問順序是 。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 7. 將含有83個(gè)結(jié)點(diǎn)的完全二叉樹從根結(jié)點(diǎn)開始編號(hào)，根為1號(hào)，后面按從上到下、從左到右的順序?qū)Y(jié)點(diǎn)編號(hào)，那么編號(hào)為41的雙

24、親結(jié)點(diǎn)編號(hào)為 。A.42 B.40 C.21 D.208. 一棵二叉樹如圖6-5所示，其后序遍歷的序列為 。 A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh圖6-5 1 棵二叉樹9. 深度為 5 的二叉樹至多有 個(gè)結(jié)點(diǎn)。A. 16 B. 32 C.31 D.10 10. 設(shè)深度為k的二叉樹上只有度為0和度為2的節(jié)點(diǎn)，則這類二叉樹上所含結(jié)點(diǎn)總數(shù)至少有 個(gè)。A.k+1 B.2k C.2k-1 D.2k+111. 對(duì)含有 B 個(gè)結(jié)點(diǎn)的非空二叉樹，采用任何一種遍歷方式，其結(jié)點(diǎn)訪問序列均相同。A.0 B.1 C.2 D.不存在這樣的二叉樹1-5 ACDBB

25、6-10 DDCCC填空題1. 有一棵樹如圖6-7 所示，回答下面的問題：圖6-7 1 棵二叉樹（1）這棵樹的根結(jié)點(diǎn)是 ； （2）這棵樹的葉子結(jié)點(diǎn)是 ； （3）結(jié)點(diǎn) k3 的度是 ； （4）這棵樹的度為 ； （5）這棵樹的深度是 ； （6）結(jié)點(diǎn) k3 的孩子是 ； （7）結(jié)點(diǎn) k3 的雙親結(jié)點(diǎn)是 。 2. 深度為 k 的完全二叉樹至少有 個(gè)結(jié)點(diǎn)，至多有 個(gè)結(jié)點(diǎn)，若按自上而下，從左到右次序給結(jié)點(diǎn)編號(hào)（從 1 開始），則編號(hào)最小的葉子結(jié)點(diǎn)的編號(hào)是 。答：2 2-1 2+13. 一棵二叉樹的第 i（i1）層最多有 個(gè)結(jié)點(diǎn)；一棵有 n（n>0）個(gè)結(jié)點(diǎn)的滿二叉樹共有 個(gè)葉子和 個(gè)非終端結(jié)點(diǎn)。 答：

26、 2 4. 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 。5. 哈夫曼樹是帶權(quán)路徑度_的樹，通常權(quán)值較大的結(jié)點(diǎn)離根_。最短 較近6在_遍歷二叉樹的序列中，任何結(jié)點(diǎn)的子樹上的所有結(jié)點(diǎn)，都是直接跟在該結(jié)點(diǎn)之后。1. 答： k1 k2 k5 k7 k4 2 3 4 k5，k6 k12. 3. 4. floor(log2n)+15. 6. 先根例題解析【例6-1】由如圖 6-1 所示的二叉樹，回答以下問題。 （1）其中序遍歷序列為 ； （2）其前序遍歷序列為 ； （3）其后序遍歷序列為 ； （4）該二叉樹的中序線索二叉樹為 ； （5）該二叉樹的后序線索二叉樹為 ； （6）該二叉樹對(duì)應(yīng)的森林是 。圖6-1 1棵二

27、叉樹解： 中序遍歷序列為dgbaechif 前序遍歷序列為abdgcefhi 后序遍歷序列為gdbeihfca 該二叉樹的中序線索二叉樹如圖 6.1.1(a)所示 該二叉樹的后序線索二叉樹如圖6-1-1 (b)所示 該二叉樹對(duì)應(yīng)的森林如圖6-1-2所示圖6-1-1 二叉樹的中序線索二叉樹和后序線索二叉樹圖6-1-2 二叉樹對(duì)應(yīng)的森林 綜合題1二叉樹結(jié)點(diǎn)數(shù)值采用順序存儲(chǔ)結(jié)構(gòu)，如表6-2所示。表6-2 二叉樹的順序存儲(chǔ)結(jié)構(gòu)1234567891011121314151617181920eafdgcjhib（1）畫出二叉樹表示； （2）寫出前序遍歷，中序遍歷和后序遍歷的結(jié)果； （3）寫出結(jié)點(diǎn)值 c 的

28、父結(jié)點(diǎn)，其左、右孩子。解： （1）該二叉樹如圖 6-9 所示。圖 6-9 1棵二叉樹（2）本題二叉樹的各種遍歷結(jié)果如下： 前序遍歷：eadcbjfghi 中序遍歷：abcdjefhgi 后序遍歷：bcjdahigfa （3）c 的父結(jié)點(diǎn)為 d，左孩子為 j，沒有右孩子。 2有一份電文中共使用 5 個(gè)字符：a、b、c、d、e，它們的出現(xiàn)頻率依次為 4、7、5、2、9，試畫出對(duì)應(yīng)的哈夫曼樹（請(qǐng)按左子樹根結(jié)點(diǎn)的權(quán)小于等于右子樹根結(jié)點(diǎn)的權(quán)的次序構(gòu)造），并求出每個(gè)字符的哈夫曼編碼。 解：依題意，本題對(duì)應(yīng)的哈夫曼樹如圖 6-15 所示。各字符對(duì)應(yīng)的哈夫曼編碼如下： a：001 b：10 c：01 d：00

29、0 e：11圖6-15 一棵哈夫曼樹3設(shè)給定權(quán)集 w=2，3，4，7，8，9，試構(gòu)造關(guān)于 w 的一棵哈夫曼樹，并求其加權(quán)路徑長(zhǎng)度 WPL。 解：本題的哈夫曼樹如圖 6-16 所示。圖6-16 一棵哈夫曼樹其加權(quán)路徑長(zhǎng)度 WPL=7×2+8×2+4×3+2×4+3×4+9×2=80 4. 已知一棵二叉樹的中序序列為 cbedahgijf，后序序列為cedbhjigfa，畫出該二叉樹的先序線索二叉樹。解：由后序序列的最后一個(gè)結(jié)點(diǎn) a 可推出該二叉樹的樹根為 a，由中序序列可推出 a的左子樹由 cbed 組成，右子樹由 hgijf 組成，又

30、由 cbed 在后序序列中的順序可推出該子樹的根結(jié)點(diǎn)為 b，其左子樹只有一個(gè)結(jié)點(diǎn) c，右子樹由 ed 組成，顯然這里的 e 是根結(jié)點(diǎn)，其右子樹為結(jié)點(diǎn) d，這樣可得到根結(jié)點(diǎn) a 的左子樹的先序序列為：bcde；再依次推出右子樹的先序序列為：fghij。因此該二叉樹如圖 6-17所示。圖 6-17 二叉樹設(shè)二叉樹的先序線索鏈表如圖 6-18所示。圖 6-18 二叉樹的先序線索鏈表第7章 圖單項(xiàng)選擇題1在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的 倍。A. 1/2 B. 1 C. 2 D. 4 2在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的 B 倍。 A. 1/2 B. 1 C. 2

31、D. 4 3具有 4 個(gè)頂點(diǎn)的無向完全圖有 條邊。A. 6 B. 12 C. 16 D. 20 4具有 6 個(gè)頂點(diǎn)的無向圖至少應(yīng)有 條邊才能確保是一個(gè)連通圖。A. 5 B. 6 C. 7 D. 8 5在一個(gè)具有 n 個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要 條邊。 A. n B. n+1 C. n-1 D. n/2 6對(duì)于一個(gè)具有 n 個(gè)頂點(diǎn)的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是 。 A. n B. (n-1)2 C. n-1 D. n2 7對(duì)于一個(gè)具有 n 個(gè)頂點(diǎn)和 e 條邊的無向圖，若采用鄰接表表示，則所有鄰接表中的結(jié)點(diǎn)總數(shù)是 。 A. e/2 B. e C. 2e D. n+e

32、8已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如圖 7-2 所示。（1）根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點(diǎn) v1 出發(fā)，所得到的頂點(diǎn)序列是 。 A. v1，v2，v3，v5，v4 B. v1，v2，v3，v4，v5 C. v1，v3，v4，v5，v2 D. v1，v4，v3，v5，v2 （2）根據(jù)有向圖的廣度優(yōu)先遍歷算法，從頂點(diǎn) v1 出發(fā)，所得到的頂點(diǎn)序列是 。 A. v1，v2，v3，v4，v5 B. v1，v3，v2，v4，v5 C. v1，v2，v3，v5，v4 D. v1，v4，v3，v5，v2 圖7-2一個(gè)有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)9. 判定一個(gè)有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ猓€可以利

33、用 。 A. 求關(guān)鍵路徑的方法 B. 求最短路徑的 Dijkstra 方法 C. 廣度優(yōu)先遍歷算法 D. 深度優(yōu)先遍歷算法 1-5.CBAAC6-9 DCCBD填空題1n 個(gè)頂點(diǎn)的連通圖至少 條邊。2在無向圖 G 的鄰接矩陣 A 中，若 Aij等于 1，則 Aji等于 。 3已知圖G的鄰接表如圖 7-3 所示，其從頂點(diǎn) v1 出發(fā)的深度優(yōu)先搜索序列為 ，其從頂點(diǎn) v1 出發(fā)的廣度優(yōu)先搜索序列為 。圖7-3 G的鄰接表4設(shè)x,y是圖G中的兩頂點(diǎn)，則（x,y）與（y,x）被認(rèn)為_邊，但<x,y>與<y,x>是_的兩條弧。答：無向，有向 5.已知一個(gè)圖的鄰接矩陣表示，刪除所有

34、從第 i 個(gè)結(jié)點(diǎn)出發(fā)的邊的方法是 。6在有向圖的鄰接矩陣上，由第i行可得到第_個(gè)結(jié)點(diǎn)的出度，而由第j列可得到第_ _個(gè)結(jié)點(diǎn)的入度。i j7. 在無向圖中，如果從頂點(diǎn)v到頂點(diǎn)v有路徑，則稱v和v是_的。如果對(duì)于圖中的任意兩個(gè)頂點(diǎn)vi,vjV，且vi和vj都是連通的，則稱G為_。連通，連通圖1. n-12. 13. 答： v1，v2，v3，v6，v5，v4 v1，v2，v5，v4，v3，v64. 5. 將矩陣第 i 行全部置為 05. 6. 例題解析【例7-1】對(duì)m個(gè)頂點(diǎn)的無向圖G，采用鄰接矩陣，如何判別下列有關(guān)問題：（1） 圖中有多少條邊？（2） 任意兩個(gè)頂點(diǎn)i和j是否有邊相連？（3） 任意一個(gè)

35、頂點(diǎn)的度是多少？解：鄰接矩陣非零元素個(gè)數(shù)的總和除以2。當(dāng)A i,j 0時(shí)，表示兩頂點(diǎn)i,j之間有邊相連。計(jì)算鄰接矩陣上頂點(diǎn)對(duì)應(yīng)行上非零元素的個(gè)數(shù)。綜合題1給出如圖 7-4 所示的無向圖G的鄰接矩陣和鄰接表兩種存儲(chǔ)結(jié)構(gòu)。圖7-4 無向圖G解：圖 G 對(duì)應(yīng)的鄰接矩陣和鄰接表兩種存儲(chǔ)結(jié)構(gòu)分別如圖所示。2用廣度優(yōu)先搜索和深度優(yōu)先搜索對(duì)如圖 7-5 所示的圖 G 進(jìn)行遍歷（從頂點(diǎn)1出發(fā)），給出遍歷序列。解：搜索本題圖的廣度優(yōu)先搜索的序列為：1，2，3，6，4，5，8，7，深度優(yōu)先搜索的序列為：1，2，6，4，5，7，8，3。 圖7-5無向圖G3使用普里姆算法構(gòu)造出如圖 7-6 所示的圖 G 的一棵最小生

36、成樹。 圖7-6無向圖G解：使用普里姆算法構(gòu)造棵最小生成樹的過程如圖 7-11所示。圖 7-11 普里姆算法構(gòu)造最小生成樹的過程4使用克魯斯卡爾算法構(gòu)造出如圖 7-7 所示的圖 G 的一棵最小生成樹。 圖7-7 無向圖G解：使用克魯斯卡爾算法構(gòu)造棵最小生成樹的過程如圖 7-12所示。圖 7-12 克魯斯卡爾算法構(gòu)造最小生成樹的過程第8章 查找單項(xiàng)選擇題1.順序查找法適合于存儲(chǔ)結(jié)構(gòu)為 的線性表。 A. 散列存儲(chǔ) B. 順序存儲(chǔ)或鏈接存儲(chǔ) C. 壓縮存儲(chǔ) C. 索引存儲(chǔ) 2.對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表的存儲(chǔ)方式是 。A. 順序存儲(chǔ) B. 鏈接存儲(chǔ)C. 以關(guān)鍵字有序排序的順序存儲(chǔ)D. 以關(guān)鍵

37、字有序排序的鏈接存儲(chǔ)3.對(duì)有 18 個(gè)元素的有序表作二分（折半）查找，則查找A3的比較序列的下標(biāo)為 。A. 1.2.3 B. 9.5.2.3 C. 9.5.3 D. 9.4.2.3 4.如果要求一個(gè)線性表既能較快地查找，又能適應(yīng)動(dòng)態(tài)變化的要求，可以采用 查找方法。 A. 分塊 B. 順序 C. 二分 D. 散列 5.有一個(gè)有序表為2，5，7，11，22，45，49，62，71，77，90，93，120，當(dāng)折半查找值為 90 的結(jié)點(diǎn)時(shí)，經(jīng)過 次比較后查找成功。A. 1 B. 2 C. 4 D. 8 6.設(shè)哈希表長(zhǎng) m=14，哈希函數(shù) H(key)=key % 11。表中已有 4 個(gè)結(jié)點(diǎn)：addr

38、(14)=3， addr(38)=5，addr(61)=6，addr(85)=8，其余地址為空，如用線性探測(cè)再散列處理沖突，關(guān)鍵字為 49 的結(jié)點(diǎn)的地址是 。A. 7 B. 3 C. 5 D. 4 7.在采用鏈接法處理沖突的開散列表上，假定裝填因子a 的值為 4，則查找任一元素的平均查找長(zhǎng)度為 。A. 3 B.3.5 C.4 D.2.51-4 BCDA5-7CAA填空題1.在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù) n 無關(guān)的查法方法是 。 2.二分查找的存儲(chǔ)結(jié)構(gòu)僅限于 。3.在散列存儲(chǔ)中，裝填因子的值越大，則 ；的值越小，則 。 存取元素時(shí)發(fā)生沖突的可能性就越大 存取元素時(shí)發(fā)生沖突的可能性就越

39、小4.對(duì)于二叉排序樹的查找，若根結(jié)點(diǎn)元素的鍵值大于被查元素的鍵值，則應(yīng)該在二叉樹的_上繼續(xù)查找。5.高度為8的平衡二叉樹至少有_個(gè)結(jié)點(diǎn)。6. 在散列函數(shù) H(key)=key % p 中，p 應(yīng)取 。1. 散列表查找2. 有序的順序存儲(chǔ)結(jié)構(gòu) 3. 4. 左子樹5. 546. 素?cái)?shù)例題解析【例8-1】設(shè)有一組關(guān)鍵字19，01，23，14，55，20，84，27，68，11，10，77，采用哈希函數(shù)：H(key)=key % 13 ,采用開放地址法的二次探測(cè)再散列方法解決沖突，試在 018 的散列地址空間中對(duì)該關(guān)鍵字序列構(gòu)造哈希表。 解：依題意，m=19，二次探測(cè)再散列的下一地址計(jì)算公式為：d=H

40、(key) d=( d+j*j) % m d=( d-j*j) % m； j=1，2，. 其計(jì)算函數(shù)如下： H(19)=19 % 13=6 H(01)=01 % 13=1 H(23)=23 % 13=10 H(14)=14 % 13=1 (沖突) H(14)=(1+1*1) % 19=2H(55)=55 % 13=3 H(20)=20 % 13=7 H(84)=84 % 13=6 (沖突) H(84)=(6+1*1) % 19=7 (仍沖突) H(84)=(6-1*1) % 19=5 H(27)=27 % 13=1 (沖突)H(27)=(1+1*1) % 19=2 (沖突) H(27)=(1-

41、1) % 19=0 H(68)=68 % 13=3 (沖突) H(68)=(3+1*1) % 19=4 H(11)=11 % 13=11 H(10)=10 % 13=10 (沖突) H(10)=(10+1*1) % 19=11 (仍沖突) H(10)=(10-1*1) % 19=9 H(77)=77 % 13=12 因此：各關(guān)鍵字的記錄對(duì)應(yīng)的地址分配如下： addr(27)=0 addr(01)=1 addr(14)=2 addr(55)=3 addr(68)=4 addr(84)=5 addr(19)=6 addr(20)=7 addr(10)=9 addr(23)=10 addr(11)=

42、11 addr(77)=12 其他地址為空。綜合題1.設(shè)散列表為 T0.12，散列函數(shù)為 H（key）= key%13，給定鍵值序列是39，36，28，38，44，15，42，12，06，25，請(qǐng)畫出分別用拉鏈法和線性探查法處理沖突時(shí)所構(gòu)造的散列表，并求出在等概率情況下，這兩種方法查找成功和查找失敗時(shí)的平均查找長(zhǎng)度。解 用散列函數(shù) H（key）= key% 13計(jì)算出鍵值序列的散列地址。并用探查次數(shù)表示待查鍵值需對(duì)散列表中鍵值比較次數(shù)。鍵值序列：39，36，28，38，44，15，42，12，06，25散列地址： 0，10，2，12，5，2，3，12，6，12（1）線性探查法處理沖突用線性探查

43、法處理沖突構(gòu)造的散列表見表8-1所示。表8-1 用線性探查法處理沖突構(gòu)造的散列表下標(biāo)0123456789101112T0.1239122815424406253638查找成功探查次數(shù)1312211911查找失敗探查次數(shù)98765432112110在等概率的情況下，查找成功的平均查找長(zhǎng)度ASL=（1×6+2×2+3×1+9×1）/10=2.2設(shè)待查鍵值 k不在散列表中：若 H（k）= k% 13= d，則從 i=d開始順次與 Ti位置的鍵值進(jìn)行比較，直到遇到空位，才確定其查找失敗，同時(shí)累計(jì) k鍵值的比較次數(shù)，例如若 k% 13= 0，則必須將 k與 T0、

44、T1、T8中的鍵值進(jìn)行比較之后，發(fā)現(xiàn) T8為空，比較次數(shù)為 9、類似地可對(duì) k% 13=1，2，3，12進(jìn)行分析可得查找失敗的平均查找長(zhǎng)度。ASL =（9+8+7+6+5+4+3+2+1+1+10）/13 = 59/13 = 4.54（2）拉鏈法處理沖突用拉鏈法處理沖突構(gòu)造的散列表見圖8-2所示。圖8-2 拉鏈法處理沖突構(gòu)造的散列表在等概率的情況下查找成功的平均查找長(zhǎng)度：ASL=（1×7+2×2+3×1）/10=1.4設(shè)待查鍵值 k不在散列表中，若 k% 13= d。則需在 d鏈表中查找鍵值為 k的結(jié)點(diǎn)，直到表尾，若不存在則查找失敗，設(shè) d鏈表中有 i個(gè)結(jié)點(diǎn)，則 k需與表中鍵值比較 i次，查找失敗的平均長(zhǎng)度為：ASL=（1+ 0+ 2+ 1+ 0+ 1+ 1+ 0+0+0+1+0+3）/13=10/13 = 0.772.線性表的關(guān)鍵字集合87，25，310，08