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ī)無(wú)關(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)系是通過(guò)_ _體現(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ī)訪問(wèn)任一元素 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 = p-next-next; 5將長(zhǎng)度為n的單鏈表接在長(zhǎng)度為m的單鏈表

4、之后的算法時(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í)，需向后移動(dòng)元素的個(gè)數(shù)是 。5在長(zhǎng)度為n的順序表中插入一個(gè)元素的時(shí)間復(fù)雜度為 。1前驅(qū) 2

5、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-next; s-next=q; /*逆轉(zhuǎn)指針*/ q=s; /*指針前移*/ s=p; h-next=q; /*頭指

6、針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)前所指的元素為b，則當(dāng)前應(yīng)插入到 C中的元素c為 例如：A=(3,5,8,11) B=(2,6,8,9,11,15,20)則 C=

7、(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-datadata) /*比較A、B表中當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)域值的大小*/ q-data=pb-data; /*B中結(jié)點(diǎn)值小，將其值賦給q的數(shù)據(jù)域*/

8、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*)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*)m

9、alloc(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空間*/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è)元

10、素為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-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. 沒(méi)有共同點(diǎn)6對(duì)

11、于循環(huán)隊(duì)列 。A. 無(wú)法判斷隊(duì)列是否為空 B. 無(wú)法判斷隊(duì)列是否為滿 C. 隊(duì)列不可能滿 D. 以上說(shuō)法都不是7. 若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前隊(duì)尾指針rear和隊(duì)頭指針front的值分別為0和3。當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(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)

12、% m0 9.判定一個(gè)循環(huán)隊(duì)列 QU（最多元素為 m0）為空的條件是 。A. QU-front=QU-rear B. QU-front!=QU-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)過(guò)push，push，pop，push，pop，push，pop，push后，輸出序列是 。3僅允許在同一端進(jìn)行插入和刪除的線性表稱為 。7在順序棧s中，棧為空的條件是 ，棧為滿的條件是_。4用S表示

13、入棧操作，X表示出棧操作，若元素入棧順序?yàn)?234，為了得到1342出棧順序，相應(yīng)的S、X操作串為 。5用一個(gè)大小為1000的數(shù)組來(lái)實(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ù)記錄下來(lái)并且若商不為0則再用商去除以2直到商為0，這時(shí)把所有的余數(shù)按出現(xiàn)的逆序排列起來(lái)（先出現(xiàn)的余數(shù)排在后面，

14、后出現(xiàn)的余數(shù)排在前面）就得到了相應(yīng)的二進(jìn)制數(shù)，如把十進(jìn)制數(shù)35轉(zhuǎn)換成二進(jìn)制數(shù)的過(guò)程如圖3-1所示。35178421011001余數(shù)結(jié)果：10011 圖3-1 十進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)的過(guò)程由題意可知，我們可以用一個(gè)棧來(lái)保存所有的余數(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(n0）個(gè)結(jié)點(diǎn)的滿二叉樹共有 個(gè)葉子和 個(gè)非終端結(jié)點(diǎn)。 答： 2 4. 具有n個(gè)結(jié)點(diǎn)的完全二叉

15、樹的深度為 。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 所示的二叉樹，回答以下問(wèn)題。 （1）其中序遍歷序列為 ； （2）其前序遍歷序列為 ； （3）其后序遍歷序列為 ； （4）該二叉樹的中序線索二叉樹為 ； （5）該二叉樹的后序線索二叉樹為 ； （6）該二叉樹對(duì)應(yīng)的森林是 。圖6-1 1棵二叉樹解： 中序遍歷序列為dgbae

16、chif 前序遍歷序列為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 的父結(jié)點(diǎn)，其左、右孩子。解： （1）

17、該二叉樹如圖 6-9 所示。圖 6-9 1棵二叉樹（2）本題二叉樹的各種遍歷結(jié)果如下： 前序遍歷：eadcbjfghi 中序遍歷：abcdjefhgi 后序遍歷：bcjdahigfa （3）c 的父結(jié)點(diǎn)為 d，左孩子為 j，沒(méi)有右孩子。 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：000 e：11圖6-15 一棵哈夫曼

18、樹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=72+82+43+24+34+92=80 4. 已知一棵二叉樹的中序序列為 cbedahgijf，后序序列為cedbhjigfa，畫出該二叉樹的先序線索二叉樹。解：由后序序列的最后一個(gè)結(jié)點(diǎn) a 可推出該二叉樹的樹根為 a，由中序序列可推出 a的左子樹由 cbed 組成，右子樹由 hgijf 組成，又由 cbed 在后序序列中的順序可推出該子樹的根結(jié)點(diǎn)為 b，其左子樹只有一個(gè)結(jié)點(diǎn) c，右子樹由 ed 組成

19、，顯然這里的 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 D. 4 3具有 4 個(gè)頂點(diǎn)的無(wú)向完全圖有 條邊。A. 6 B. 12 C. 16 D. 20 4具有 6

20、 個(gè)頂點(diǎn)的無(wú)向圖至少應(yīng)有 條邊才能確保是一個(gè)連通圖。A. 5 B. 6 C. 7 D. 8 5在一個(gè)具有 n 個(gè)頂點(diǎn)的無(wú)向圖中，要連通全部頂點(diǎn)至少需要 條邊。 A. n B. n+1 C. n-1 D. n/2 6對(duì)于一個(gè)具有 n 個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣表示，則該矩陣的大小是 。 A. n B. (n-1)2 C. n-1 D. n2 7對(duì)于一個(gè)具有 n 個(gè)頂點(diǎn)和 e 條邊的無(wú)向圖，若采用鄰接表表示，則所有鄰接表中的結(jié)點(diǎn)總數(shù)是 。 A. e/2 B. e C. 2e D. n+e 8已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如圖 7-2 所示。（1）根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點(diǎn) v1 出發(fā)，

21、所得到的頂點(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ù)渑判蚍椒ㄍ猓€可以利用 。 A. 求關(guān)鍵路徑的方法 B. 求最短路徑的 Dijkstra 方法 C. 廣度優(yōu)先遍歷算法 D.

22、深度優(yōu)先遍歷算法 1-5.CBAAC6-9 DCCBD填空題1n 個(gè)頂點(diǎn)的連通圖至少 條邊。2在無(wú)向圖 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)為_邊，但與是_的兩條弧。答：無(wú)向，有向 5.已知一個(gè)圖的鄰接矩陣表示，刪除所有從第 i 個(gè)結(jié)點(diǎn)出發(fā)的邊的方法是 。6在有向圖的鄰接矩陣上，由第i行可得到第_個(gè)結(jié)點(diǎn)的出度，而由第j列可得到第_ _個(gè)結(jié)點(diǎn)的入度。i j7. 在無(wú)向圖

23、中，如果從頂點(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)的無(wú)向圖G，采用鄰接矩陣，如何判別下列有關(guān)問(wèn)題：（1） 圖中有多少條邊？（2） 任意兩個(gè)頂點(diǎn)i和j是否有邊相連？（3） 任意一個(gè)頂點(diǎn)的度是多少？解：鄰接矩陣非零元素個(gè)數(shù)的總和除以2。當(dāng)A i,j 0時(shí)，表示兩頂點(diǎn)i,j之間有邊相連。計(jì)算鄰接矩陣上頂點(diǎn)對(duì)應(yīng)行上非零元素的個(gè)數(shù)。綜合

24、題1給出如圖 7-4 所示的無(wú)向圖G的鄰接矩陣和鄰接表兩種存儲(chǔ)結(jié)構(gòu)。圖7-4 無(wú)向圖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無(wú)向圖G3使用普里姆算法構(gòu)造出如圖 7-6 所示的圖 G 的一棵最小生成樹。 圖7-6無(wú)向圖G解：使用普里姆算法構(gòu)造棵最小生成樹的過(guò)程如圖 7-11所示。圖 7-11 普里姆算法構(gòu)造最小生成樹的過(guò)程4使用克魯斯卡爾算法構(gòu)

25、造出如圖 7-7 所示的圖 G 的一棵最小生成樹。 圖7-7 無(wú)向圖G解：使用克魯斯卡爾算法構(gòu)造棵最小生成樹的過(guò)程如圖 7-12所示。圖 7-12 克魯斯卡爾算法構(gòu)造最小生成樹的過(guò)程第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)鍵字有序排序的鏈接存儲(chǔ)3.對(duì)有 18 個(gè)元素的有序表作二分（折半）查找，則查找A3的比較序列的下標(biāo)為 。A. 1.2.3 B. 9.5.2.3 C. 9

26、.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)過(guò) 次比較后查找成功。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(14)=3， addr(38)=5，addr(61)=6，addr(85)=8，其余地址為空，如用線性探測(cè)再散列處理沖突，關(guān)鍵字為 49 的結(jié)點(diǎn)的地

27、址是 。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 無(wú)關(guān)的查法方法是 。 2.二分查找的存儲(chǔ)結(jié)構(gòu)僅限于 。3.在散列存儲(chǔ)中，裝填因子的值越大，則 ；的值越小，則 。 存取元素時(shí)發(fā)生沖突的可能性就越大 存取元素時(shí)發(fā)生沖突的可能性就越小4.對(duì)于二叉排序樹的查找，若根結(jié)點(diǎn)元素的鍵值大于被查元素的鍵值，則應(yīng)該在二叉樹的_上繼續(xù)查找。5.高度為8的平衡二叉樹至少有_個(gè)結(jié)點(diǎn)。6. 在散列函

28、數(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(key) d=( d+j*j) % m d=( d-j*j) % m； j=1，2，. 其計(jì)算函數(shù)如下： H(19)=19 % 13=6 H(01)

29、=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-1) % 19=0 H(68)=68 % 13=3 (沖突) H(68)=(3+1*1) % 19=4 H(11)=11 % 13=11 H(10)=

30、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)=11 addr(77)=12 其他地址為空。綜合題1.設(shè)散列表為 T0.12，散列函數(shù)為 H（key）= key%13，給定鍵值序列是39，36，28

31、，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）線性探查法處理沖突用線性探查法處理沖突構(gòu)造的散列表見(jiàn)表8-1所示。表8-1 用線性探查法處理沖突構(gòu)造的散列表下標(biāo)0123456789101112T0.12391228154244

32、06253638查找成功探查次數(shù)1312211911查找失敗探查次數(shù)98765432112110在等概率的情況下，查找成功的平均查找長(zhǎng)度ASL=（16+22+31+91）/10=2.2設(shè)待查鍵值 k不在散列表中：若 H（k）= k% 13= d，則從 i=d開始順次與 Ti位置的鍵值進(jìn)行比較，直到遇到空位，才確定其查找失敗，同時(shí)累計(jì) k鍵值的比較次數(shù)，例如若 k% 13= 0，則必須將 k與 T0、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）

33、/13 = 59/13 = 4.54（2）拉鏈法處理沖突用拉鏈法處理沖突構(gòu)造的散列表見(jiàn)圖8-2所示。圖8-2 拉鏈法處理沖突構(gòu)造的散列表在等概率的情況下查找成功的平均查找長(zhǎng)度：ASL=（17+22+31）/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，27，132，68，95，18

34、7，123，70，63，7，共有 13 個(gè)元素，已知散列函數(shù)為：H(k) = k % 13 ，采用拉鏈法處理沖突。設(shè)計(jì)出這種鏈表結(jié)構(gòu)，并計(jì)算該表的成功查找的平均查找長(zhǎng)度。解：依題意，得到：H(87)=87 % 13=9 H(25)=25 % 13=12 H(310)=310 % 13=11 H(08)=08 % 13=8 H(27)=27 % 13=1H(132)=132 % 13=2 H(68)=68 % 13=3 H(95)=95 % 13=4 H(187)=187 % 13=5 H(123)=123 % 13=6 H(70)=70 % 13=5 H(63)=63 % 13=11 H(47)=47 % 13=8 采用拉