數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題目及答案

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

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

3、表的每個元素占8個存儲單元。第1個單元的存儲地址是100，則第6個元素占用的最后一個存儲單元的地址為 。A. 139 B. 140 C. 147 D. 1483在線性鏈表存儲結(jié)構(gòu)下，插入操作算法 。A. 需要判斷是否表滿 B. 需要判斷是否表空 C. 不需要判斷表滿 D. 需要判斷是否表空和表滿 4在一個單鏈表中，若刪除p所指結(jié)點的后繼結(jié)點，則執(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將長度為n的單鏈表接在長度為m的單鏈表之后的算法時間復(fù)雜度為 。 A. O(n) B. O(1) C. O(m) D. O(m+n)6需要預(yù)分較大空間，插入和刪除不需要移動元素的線性表，其存儲結(jié)構(gòu)是 。 A. 單鏈表 B. 靜態(tài)鏈表 C. 線性鏈表 D. 順序存儲方式ACCABB填空題1在帶表頭結(jié)點的單鏈表中，當(dāng)刪除某一指定結(jié)點時，必須找到該結(jié)點的_結(jié)點。2在單鏈表中，指針p所指結(jié)點為最后一個結(jié)點的條件是 。3將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是 。 4在一個長度為n的順序表中第i個元素（1in）之前插入一個元素時，需

5、向后移動元素的個數(shù)是 。5在長度為n的順序表中插入一個元素的時間復(fù)雜度為 。1前驅(qū) 2 p->next=NULL3.14. n-i+15. O(n)例題解析【例2-1】 編寫一個算法將一個單鏈表逆轉(zhuǎn)，要求在原表上進(jìn)行，不允許重新建鏈表。 解：該算法可以在遍歷原表的時候?qū)⒏鹘Y(jié)點的指針逆轉(zhuǎn)，從原表的第一個結(jié)點開始，頭結(jié)點的指針在最后修改成指向原表的最后一個結(jié)點，即新表的第一個結(jié)點。實現(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】 編寫一算法將兩個按元素值遞增有序排列的單鏈表A和B歸并成一個按元素值遞增有序排列的單鏈表C。解：對于兩個或兩個以上的，結(jié)點按元素值有序排列的單鏈表進(jìn)行操作時，應(yīng)采用“指針平行移動，依次掃描完成”的方法。從兩表的第一個結(jié)點開始順鏈表逐個將對應(yīng)數(shù)據(jù)元素進(jìn)行比較，復(fù)制小的并插入c表尾。當(dāng)兩表中之一已到表尾，則復(fù)制另一個鏈表的剩余部分，插入到c表尾。設(shè)pa、pb分別指向兩表當(dāng)前結(jié)點，p指向c表的當(dāng)前表尾結(jié)點。若設(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)實現(xiàn)本題功能的函數(shù)如下：Lnode *hb(Lnode *pa,Lnode *pb)Lnode *p,*q,*pc; pc=(Lnode*)malloc(sizeof(Lnode); /*建立表c 的頭結(jié)點pc*/ p=pc; /*p指向C表頭結(jié)點*/ while(pa!=NULL&&pb!=NULL) q=(Lnode*)malloc(sizeof(Lnode); /*建立新結(jié)點q*/ if(pb

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

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

10、*/return (pc); 此算法的時間復(fù)雜度為O(m+n)，其中m，n分別是兩個被合并表的表長。第三章 棧和隊列單項選擇題1在初始為空的堆棧中依次插入元素f，e，d，c，b，a以后，連續(xù)進(jìn)行了三次刪除操作，此時棧頂元素是 。 A. B.C. D. 2若某堆棧的輸入序列是1，2，3，.，n，輸出序列的第一個元素為n，則第i個輸出元素為 。A. i B. n-i C. n-i+1 D. 哪個元素?zé)o所謂3向一個棧頂指針為h的帶頭結(jié)點鏈棧中插入指針s所指的結(jié)點時，應(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一個棧的入棧序列是 a，b，c，d，e，則棧的不可能的輸出序列是 。 A. edcba B. decba C. dceab D. abcde5棧和隊列的共同點是 。A. 都是先進(jìn)后出 B. 都是先進(jìn)先出 C. 只允許在端點處插入和刪除元素 D. 沒有共同點6對于循環(huán)隊列 。A. 無法判斷隊列是否為空 B. 無法判斷隊列是否為滿 C. 隊列不可能滿 D. 以上說法都不是7. 若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前隊尾指針rear和隊頭指針front的值分別為0和3。當(dāng)從隊列中刪除一個

12、元素，再加入兩個元素后，rear和front的值分別為 。A. 1和5 B. 2和4 C. 4和2 D. 5和18. 判定一個循環(huán)隊列 QU（最多元素為 m0）為滿隊列的條件是 。A. QU->front=QU->rear B. QU->front!=QU->rearC. QU->front=(QU->rear+1) % m0 D. QU->front!=(QU->rear+1) % m0 9.判定一個循環(huán)隊列 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è)有一個空棧，現(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表示出棧操作，若元素入棧順序為1234，為了得到1342出棧順序，相應(yīng)的S、X操作串為 。5

14、用一個大小為1000的數(shù)組來實現(xiàn)循環(huán)隊列，當(dāng)前rear和front的值分別為0和994，若要達(dá)到隊滿的條件，還需要繼續(xù)入隊的元素個數(shù)是 。1.棧2. 2 3 43. 棧4. s.top=s.base, s.top-s.base>=s.stacksize SXSSXSXX5. 993例題解析【例3-1】 編程實現(xiàn)：用除法把十進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)。 解：算法思想：用初始十進(jìn)制數(shù)除以2把余數(shù)記錄下來并且若商不為0則再用商去除以2直到商為0，這時把所有的余數(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ù)的過程由題意可知，我們可以用一個棧來保存所有的余數(shù)，當(dāng)商為0時則讓棧里的所有余數(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);第四章 串單項選擇題1串是一種特殊的線性表，其特殊性體現(xiàn)在 。A. 可以順序存儲 B. 數(shù)據(jù)元素是一個字符 C. 可以鏈接存儲 D. 數(shù)據(jù)元素可以是多個字符 2設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作 。 A. 連接 B. 模式匹配 C. 求子串 D. 求串長3串是一個 B 的序列。A. 不少于一個字母

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

18、concat(subString(s,1,3),substring(s,7,1)第五章 數(shù)組與廣義表單項選擇題1常對數(shù)組進(jìn)行的兩種操作是 。A. 建立與刪除 B. 索引和修改 C. 查找和修改 D. 查找與索引 2假設(shè)8行10列的二維數(shù)組a1.8, 1.10分別以行序為主序和以列序為主序順序存儲時，其首地址相同，那么以行序為主序時元素a35的地址與以列序為主序時元素 _ _的地址相同。A. a53 B. a83 C. a14 D. 答案A、B、C均不對 3將一個A1.100,1.100的三對角矩陣以行序為主序存入一維數(shù)組B1.298中，元素A66，65在B數(shù)組中的位置k等于_ _。A. 198

19、 B. 197 C. 196 D. 1954稀疏矩陣一般的壓縮存儲方法有兩種，即 。 A. 二維數(shù)組和三維數(shù)組 B. 三元組和散列C. 三元組和十字鏈表 D. 散列和十字鏈表5. 一個非空廣義表的表頭_ _。 A. 不可能是子表 B. 只能是子表 C. 只能是原子 D. 可以是原子或子表6. 設(shè)head(L)、tail(L)分別為取廣義表表頭、表尾操作，則從廣義表L=(x,y,z),a,(u,v,w)中取出原子u的運算為_ _。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的下三角部分逐行地存儲到起始地址為1000的內(nèi)存單元中，已知每個元素占四個單元，則元素A7,5的地址為 。 2二維數(shù)組A0.9,0.19采用行序為主方式存儲，每個元素占一個存儲單元，并且元素A0,0的存儲地址是200，則元素A6,12的地址是 。 3二維數(shù)組A10.20,5.10采用行序為主方式存儲，每個元素占4個存儲單元，并且元素A10,5的存儲地址是1000，則元素A18,9的地址是 。4有一個10階對

21、稱矩陣A，采用壓縮存儲方式（以行序為主序存儲，且元素A0,0地址為1），則元素A8,5的地址是 。5設(shè)HAEDp為求廣義表p的表頭函數(shù)，TAILp為求廣義表p的表尾函數(shù)，其中 是函數(shù)的符號，給出下列廣義表的運算結(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 以下說法錯誤的是 。A.樹形結(jié)構(gòu)的特點是一個結(jié)點可以有多個直接前趨B.線性結(jié)構(gòu)中的一個結(jié)點至多只有一個直接后繼C.樹形結(jié)構(gòu)可以表達(dá)(組織)更復(fù)雜的數(shù)據(jù)D.樹(及一切樹形結(jié)構(gòu))是一種"分支層次"結(jié)構(gòu)2. 如圖6-2所示的 4 棵二叉樹中， 不是完全二叉樹。圖6-2 4 棵二叉樹3. 以下說法錯誤的是 。A.完全二叉樹上結(jié)點之間的父子關(guān)系可由它們編號之間的關(guān)系來表達(dá)B.在三叉鏈表上，二叉樹的求雙親運算很容易實現(xiàn)C.在二叉鏈表上，求根，求左、右孩子等很容易實現(xiàn)D.在二叉鏈表上，求雙親運算

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

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

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

26、 2 4. 具有n個結(jié)點的完全二叉樹的深度為 。5. 哈夫曼樹是帶權(quán)路徑度_的樹，通常權(quán)值較大的結(jié)點離根_。最短 較近6在_遍歷二叉樹的序列中，任何結(jié)點的子樹上的所有結(jié)點，都是直接跟在該結(jié)點之后。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）該二叉樹對應(yīng)的森林是 。圖6-1 1棵二

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

28、父結(jié)點，其左、右孩子。解： （1）該二叉樹如圖 6-9 所示。圖 6-9 1棵二叉樹（2）本題二叉樹的各種遍歷結(jié)果如下： 前序遍歷：eadcbjfghi 中序遍歷：abcdjefhgi 后序遍歷：bcjdahigfa （3）c 的父結(jié)點為 d，左孩子為 j，沒有右孩子。 2有一份電文中共使用 5 個字符：a、b、c、d、e，它們的出現(xiàn)頻率依次為 4、7、5、2、9，試畫出對應(yīng)的哈夫曼樹（請按左子樹根結(jié)點的權(quán)小于等于右子樹根結(jié)點的權(quán)的次序構(gòu)造），并求出每個字符的哈夫曼編碼。 解：依題意，本題對應(yīng)的哈夫曼樹如圖 6-15 所示。各字符對應(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)路徑長度 WPL。 解：本題的哈夫曼樹如圖 6-16 所示。圖6-16 一棵哈夫曼樹其加權(quán)路徑長度 WPL=7×2+8×2+4×3+2×4+3×4+9×2=80 4. 已知一棵二叉樹的中序序列為 cbedahgijf，后序序列為cedbhjigfa，畫出該二叉樹的先序線索二叉樹。解：由后序序列的最后一個結(jié)點 a 可推出該二叉樹的樹根為 a，由中序序列可推出 a的左子樹由 cbed 組成，右子樹由 hgijf 組成，又

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

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

32、8已知一有向圖的鄰接表存儲結(jié)構(gòu)如圖 7-2 所示。（1）根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點 v1 出發(fā)，所得到的頂點序列是 。 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)先遍歷算法，從頂點 v1 出發(fā)，所得到的頂點序列是 。 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一個有向圖的鄰接表存儲結(jié)構(gòu)9. 判定一個有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以利

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

34、從第 i 個結(jié)點出發(fā)的邊的方法是 。6在有向圖的鄰接矩陣上，由第i行可得到第_個結(jié)點的出度，而由第j列可得到第_ _個結(jié)點的入度。i j7. 在無向圖中，如果從頂點v到頂點v有路徑，則稱v和v是_的。如果對于圖中的任意兩個頂點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】對m個頂點的無向圖G，采用鄰接矩陣，如何判別下列有關(guān)問題：（1） 圖中有多少條邊？（2） 任意兩個頂點i和j是否有邊相連？（3） 任意一個

35、頂點的度是多少？解：鄰接矩陣非零元素個數(shù)的總和除以2。當(dāng)A i,j 0時，表示兩頂點i,j之間有邊相連。計算鄰接矩陣上頂點對應(yīng)行上非零元素的個數(shù)。綜合題1給出如圖 7-4 所示的無向圖G的鄰接矩陣和鄰接表兩種存儲結(jié)構(gòu)。圖7-4 無向圖G解：圖 G 對應(yīng)的鄰接矩陣和鄰接表兩種存儲結(jié)構(gòu)分別如圖所示。2用廣度優(yōu)先搜索和深度優(yōu)先搜索對如圖 7-5 所示的圖 G 進(jì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章 查找單項選擇題1.順序查找法適合于存儲結(jié)構(gòu)為 的線性表。 A. 散列存儲 B. 順序存儲或鏈接存儲 C. 壓縮存儲 C. 索引存儲 2.對線性表進(jìn)行折半查找時，要求線性表的存儲方式是 。A. 順序存儲 B. 鏈接存儲C. 以關(guān)鍵字有序排序的順序存儲D. 以關(guān)鍵

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

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

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

40、(key) d=( d+j*j) % m d=( d-j*j) % m； j=1，2，. 其計算函數(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)鍵字的記錄對應(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，請畫出分別用拉鏈法和線性探查法處理沖突時所構(gòu)造的散列表，并求出在等概率情況下，這兩種方法查找成功和查找失敗時的平均查找長度。解 用散列函數(shù) H（key）= key% 13計算出鍵值序列的散列地址。并用探查次數(shù)表示待查鍵值需對散列表中鍵值比較次數(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在等概率的情況下，查找成功的平均查找長度ASL=（1×6+2×2+3×1+9×1）/10=2.2設(shè)待查鍵值 k不在散列表中：若 H（k）= k% 13= d，則從 i=d開始順次與 Ti位置的鍵值進(jìn)行比較，直到遇到空位，才確定其查找失敗，同時累計 k鍵值的比較次數(shù)，例如若 k% 13= 0，則必須將 k與 T0、

44、T1、T8中的鍵值進(jìn)行比較之后，發(fā)現(xiàn) T8為空，比較次數(shù)為 9、類似地可對 k% 13=1，2，3，12進(jìn)行分析可得查找失敗的平均查找長度。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)造的散列表在等概率的情況下查找成功的平均查找長度：ASL=（1×7+2×2+3×1）/10=1.4設(shè)待查鍵值 k不在散列表中，若 k% 13= d。則需在 d鏈表中查找鍵值為 k的結(jié)點，直到表尾，若不存在則查找失敗，設(shè) d鏈表中有 i個結(jié)點，則 k需與表中鍵值比較 i次，查找失敗的平均長度為：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