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

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

2、對(duì)算法的時(shí)間復(fù)雜度進(jìn)行估計(jì)的時(shí)候，下列最佳的時(shí)間復(fù)雜度是_ 。2A.nB.nlognC.nD.logn7. 設(shè)使用某算法對(duì) n 個(gè)元素進(jìn)行處理，所需的時(shí)間是T(n)=100nlog2n+200n+2000，則該算法的漸近時(shí)間復(fù)雜度為_(kāi)。A.0B.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è)順序表的每個(gè)元素占8 個(gè)存儲(chǔ)單元。第1 個(gè)單元的存儲(chǔ)地址是 100，則第 6 個(gè)元素占用的最后一個(gè)存儲(chǔ)單元的地址為。A.139B.

3、140C.147D.1483.在線性鏈表存儲(chǔ)結(jié)構(gòu)下，插入操作算法A.需要判斷是否表滿(mǎn)C.不需要判斷表滿(mǎn)B.需要判斷是否表空D.需要判斷是否表空和表滿(mǎn)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-n ext;p-n ext=p-n ext-n ext;5.將長(zhǎng)度為 n 的單鏈表接在長(zhǎng)度為m 的單鏈表之后的算法時(shí)間復(fù)雜度為A.O(n)B.0C.O(m)D.O(m+n)6.需要預(yù)分較大空間，插入和刪除不需要移動(dòng)元素的線性表，其存儲(chǔ)結(jié)構(gòu)是A.單鏈表B.靜態(tài)鏈表C.線性鏈表D.順

4、序存儲(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è)元素(1 i next=NULL3.14. n-i+15.0(n)例題解析【例 2-1】編寫(xiě)一個(gè)算法將一個(gè)單鏈表逆轉(zhuǎn)，要求在原表上進(jìn)行，不允許重新建鏈表。解：該算法可以在遍歷原表的時(shí)候?qū)⒏鹘Y(jié)點(diǎn)的指針逆轉(zhuǎn)，從原表的第一個(gè)結(jié)點(diǎn)開(kāi)始，頭結(jié)點(diǎn)的指針在最后修改成指向原表的最后一個(gè)結(jié)點(diǎn)，即新表的第一個(gè)結(jié)點(diǎn)。實(shí)現(xiàn)本題功能的函數(shù)如下：void

5、inverse(Lnode*h)s=h-next;if(s=NULL) return;q=NULL;p=s;while(p!=NULL)p=p-n ext;/*逆轉(zhuǎn)指s-n ext=q;針 */*指針前移q=s;*/s=p;/*頭指針 h 的后繼是h-n ext=q;p*/【例 2-2】編寫(xiě)一算法將兩個(gè)按元素值遞增有序排列的單鏈表A 和 B 歸并成一個(gè)按元素值遞增有序排列的單鏈表Co解：對(duì)于兩個(gè)或兩個(gè)以上的，結(jié)點(diǎn)按元素值有序排列的單鏈表進(jìn)行操作時(shí)，應(yīng)采用“指針平行移動(dòng)，依次掃描完成”的方法。從兩表的第一個(gè)結(jié)點(diǎn)開(kāi)始順鏈表逐個(gè)將對(duì)應(yīng)數(shù)據(jù)元 素進(jìn)行比較，復(fù)制小的并插入c 表尾。當(dāng)兩表中之一已到表尾，

6、則復(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 為aabcbab例如：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*/while(pa!=NULL&am

7、p;pb!=NULL)q=(Lnode*)malloc(sizeof(Lnode);q=(Lnode*)malloc(sizeof(Lnode);q-data=pa-data;pa=pa-n ext;p-n ext=q;p=q;q=(Lnode*)malloc(sizeof(Lnode);q-data=pb-data;pb=pb-n ext;p-n ext=q;P=PC；/*p 指向 C 表頭結(jié)點(diǎn)*/if(pb-datadata)值的大小q-data=pb-data;pb=pb-next;elseq-data=pa-data;pa=pa-next;p-next=q;p=q;while(pa!=

8、NULL)*/*B 中結(jié)點(diǎn)值小，將其值賦給/*比較 A、B 表中當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)域q 的數(shù)據(jù)域*/*B 中指針 pb 后移*/*相反，將 A 結(jié)點(diǎn)值賦給 q 的數(shù)據(jù)域*/*A/*/*p中指針 pa 后移*/將 q 接在 p 的后面*/始終指向 C 表當(dāng)前尾結(jié)點(diǎn)*/*若表 A 比 B 長(zhǎng)，將 A 余下的結(jié)點(diǎn)鏈在 C 表尾*/*建立新結(jié)點(diǎn) q*/while(pb!=NULL)/*若表 B 比 A 長(zhǎng)，將 B 余下的結(jié)點(diǎn)鏈在C 表尾*/p=q;p-next=NULL;/*p 指向表 C 的頭結(jié)點(diǎn) pc*/pc=p-next;/*改變指針狀態(tài)，使pc 指向 p 的后繼*/p=pc;/*釋放 p 空間*/

9、return(pc);O(m+n)，其中 m，n 分別是兩個(gè)被合并表的表長(zhǎng)。free(p);此算法的時(shí)間復(fù)雜度為第三章棧和隊(duì)列單項(xiàng)選擇題1 .在初始為空的堆棧中依次插入元素f, e, d, c, b, a 以后，連續(xù)進(jìn)行了三次刪除操作，此時(shí)棧頂元素是。A.cB.dC.bD.e2.若某堆棧的輸入序列是1, 2, 3, . , n,輸出序列的第一個(gè)元素為n,則第 i 個(gè)輸出元素為。A.iB.n-iC.n-i+1D.哪個(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;D.s-next=h-next;h-next=s;a,

10、b, c, d, e,則棧的不可能的輸出序列是5. 棧和隊(duì)列的共同點(diǎn)是A.都是先進(jìn)后出6. 對(duì)于循環(huán)隊(duì)列C.s-next=h;h=h-next;4.一個(gè)棧的入棧序列是A.edcbaB.decbaC.dceabD.abcdeC.只允許在端點(diǎn)處插入和刪除元素D.沒(méi)有共同點(diǎn)B.都是先進(jìn)先出A.無(wú)法判斷隊(duì)列是否為空B. 無(wú)法判斷隊(duì)列是否為C.隊(duì)列不可能滿(mǎn)D.以上說(shuō)法都不是7.若用一個(gè)大小為6 的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前隊(duì)尾指針rear 和隊(duì)頭指針 front 的值分rear 和 front 的值分別為A.1 和 5B.2 和 4C.4 和 2D.5 和 18.判m0）為滿(mǎn)隊(duì)列的條件是A. QU-fr

11、ont=QU-rearB. QU-front!=QU-rearC. QU-front=(QU-rear+1)%mOD. QU-front!=(QU-rear+1)%mO9.判定一個(gè)循環(huán)隊(duì)列QU（最多元素為m0 為空的條件是A. QU-front=QU-rearB. QU-front!=QU-rearC. QU-front=(QU-rear+1)%mOD. QU-front!=(QU-rear+1)%mOBCDCCDACA填空題_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 ,

12、pop, push,pop, push 后，輸出序列是。-3. 僅允許在同一端進(jìn)行插入和刪除的線性表稱(chēng)為。7.在順序棧 s 中，棧為空的條件是，棧為滿(mǎn)的條件是 _ 。4.用 S 表示入棧操作， 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ì)滿(mǎn)的條件，還需要繼續(xù)入隊(duì)的元素個(gè)數(shù)是_ 。1. 棧2.2343. 棧4.s.top=s.base,s.top-s.base=s.stacksizeSXSSXSXX5.993例題解析【例

13、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ù)排在后面，后出現(xiàn)的余數(shù)排在前面）就得到了相應(yīng)的二進(jìn)制數(shù)，如把十進(jìn)制數(shù)35 轉(zhuǎn)換成二進(jìn)制數(shù)的過(guò)程如圖3-1 所示。351784210余數(shù)結(jié)果：10011圖 3-1十進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)的過(guò)程由題意可知，我們可以用一個(gè)棧來(lái)保存所有的余數(shù)，當(dāng)商為 棧則可以得到正確的二進(jìn)制數(shù)，算法可描述如下：voidconversion()Stacks；intn;InitStack(&S);printf(lnput

14、anumbertoconvert:n);scanf(%d,&n);if(n 1)層最多有 -個(gè)結(jié)點(diǎn)；一棵有 n (n0)個(gè)結(jié)點(diǎn)的滿(mǎn)二叉樹(shù)共有個(gè)葉子和個(gè)非終端結(jié)點(diǎn)。答： 2i 12logn2logn14.具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 _5哈夫曼樹(shù)是帶權(quán)路徑度 _的樹(shù)，通常權(quán)值較大的結(jié)點(diǎn)離根 _。最短較近6._ 在遍歷二叉樹(shù)的序列中，任何結(jié)點(diǎn)的子樹(shù)上的所有結(jié)點(diǎn)，都是直接跟在該結(jié)點(diǎn)之后。2k2k5k7k4234k5, k6k14. floor(log2n)+15.6.先根例題解析所示的二叉樹(shù)，回答以下問(wèn) 【例 6-1】由如圖 6-1題。1) 其中序遍歷序列為；2) 其前序遍歷序列為；

15、(3)其后序遍歷序列為-1.答： k123.4) 該二叉樹(shù)的中序線索二叉樹(shù)-為_(kāi)；5) 該二叉樹(shù)的后序線索二叉樹(shù)為；(6)該二叉樹(shù)對(duì)應(yīng)的森林是。12中序遍歷序列為dgbaechif前序遍歷序列為 abdgcefhi解:i圖 6-11 棵二叉樹(shù)后序遍歷序列為gdbeihfca6.1.1(a)所示 該二叉樹(shù)的中序線索二叉樹(shù)如圖dd圖 6-1-2 二叉樹(shù)對(duì)應(yīng)的森林13綜合題1 .二叉樹(shù)結(jié)點(diǎn)數(shù)值采用順序存儲(chǔ)結(jié)構(gòu)，如表6-2 所示。表 6-2二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)1 6 | 7p8-q p9q r0q-20q4-*-g-cjLh-JL il-（1） 畫(huà)出二叉樹(shù)表示；（2） 寫(xiě)出前序遍歷，中序遍歷和后序遍歷

16、的結(jié)果;（3） 寫(xiě)出結(jié)點(diǎn)值 c 的父結(jié)點(diǎn)，其左、右孩子。解：（1）該二叉樹(shù)如圖 6-9 所示。圖 6-91 棵二叉樹(shù)（2） 本題二叉樹(shù)的各種遍歷結(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,試畫(huà)出對(duì)應(yīng)的哈夫曼樹(shù)（請(qǐng)按左子樹(shù)根結(jié)點(diǎn)的權(quán)小于等于右子樹(shù)根結(jié)點(diǎn)的權(quán)的次序構(gòu)造）并求出每個(gè)字符的哈夫曼編碼。15解：依題意，本題對(duì)應(yīng)的哈夫曼樹(shù)如圖6-15 所示各字符對(duì)應(yīng)的哈夫曼編碼如下:a: 001b： 1

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

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

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

20、v5C.vl，v3， v4，v5， v2 D.v1，v4， v3，v5， v2(2) 根據(jù)有向圖的廣度優(yōu)先遍歷算法，從頂點(diǎn)A.v1， v2， v3， v4， v5圖 7-2 一個(gè)有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)9.判定一個(gè)有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以利用A.求關(guān)鍵路徑的方法B. 求最短路徑的 Dijkstra方法C.廣度優(yōu)先遍歷算法D.深度優(yōu)先遍歷算法1- 5.CBAAC6-9DCCBD填空題1. n 個(gè)頂點(diǎn)的連通圖至少條邊。2. 在無(wú)向圖 G 的鄰接矩陣A 中，若Aij等于1,則Aji等于A.e/2B.eC.2eD.n+e所示。出發(fā)，所得到的頂點(diǎn)序列v1是C.vl， v2，v3

21、，B.v1，v3， v2，v4， v5v5，3. 已知圖 G 的鄰接表如圖7-3 所示，其從頂點(diǎn)v1 出發(fā)的深度優(yōu)先搜索序列為，其從頂點(diǎn) v1 出發(fā)的廣度優(yōu)先搜索序列為圖 7-3G 的鄰接表4. 設(shè) x,y 是圖 G 中的兩頂點(diǎn)，貝 U( x,y )與(y,x )被認(rèn)為 _邊，但x,y與y,x是_的兩條弧。答：無(wú)向，有向5. 已知一個(gè)圖的鄰接矩陣表示，刪除所有從第i 個(gè)結(jié)點(diǎn)出發(fā)的邊的方法是。6.在有向圖的鄰接矩陣上，_ 由第 i 行可得到第個(gè)結(jié)點(diǎn)的出度，而由第 j 列可得到第_ 個(gè)結(jié)點(diǎn)的入度。ij7. 在無(wú)向圖中，如果從頂點(diǎn) v 到頂點(diǎn) v有路徑，則稱(chēng) v 和 v是_ 的。如果對(duì)于圖中的任意兩

22、個(gè)頂點(diǎn) vi,vj V 且 vi 和 vj 都是連通的，則稱(chēng)G 為_(kāi)。連通，連通圖1.n-12.13. 答： v1 , v2 , v3 , v6, v5, v44.5. 將矩陣第 i 行全部置為 05.6.v2v3v4Av5v6A v1 , v2, v5 , v4, v3 , v6v1v2v5v4例題解析【例 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) Ai,j工 0 時(shí)，表示兩頂點(diǎn)i,j 之間有邊相連。計(jì)算鄰接矩陣上頂點(diǎn)對(duì)應(yīng)行

23、上非零元素的個(gè)數(shù)。綜合題1.給出如圖 7-4 所示的無(wú)向圖G 的鄰接矩陣和鄰接表兩種存儲(chǔ)結(jié)構(gòu)。圖 7-4 無(wú)向圖 G解：圖 G 對(duì)應(yīng)的鄰接矩陣和鄰接表兩種存儲(chǔ)結(jié)構(gòu)分別如圖所示。鄰接刪如 E嘟2.用廣度優(yōu)先搜索和深度優(yōu)先搜索對(duì)如圖出遍歷序列。解：搜索本題圖的廣度優(yōu)先搜索的序列為:為：1, 2, 6, 4, 5, 7, 8, 3。7-5 所示的圖 G 進(jìn)行遍歷(從頂點(diǎn)1 出發(fā))，給1, 2, 3, 6, 4, 5, 8, 7,深度優(yōu)先搜索的序列0 1 0 1 0餌I0 0 1 0 1 Oi *10 0 0 0 2nQ 1 0 0 1 0*nsQ D 0 0040 0 0 1q J圖 7-6 無(wú)向圖

24、 G7-11 所解：使用普里姆算法構(gòu)造棵最小生成樹(shù)的過(guò)程如圖示。3.使用普里姆算法構(gòu)造出如圖216563(d)(e)72515106204圖 7-7 無(wú)向圖 G解：使用克魯斯卡爾算法構(gòu)造棵最小生成樹(shù)的過(guò)程如圖7-12 所示。22圖 7-12 克魯斯卡爾算法構(gòu)造最小生成樹(shù)的過(guò)程8 章查找單項(xiàng)選擇題1順序查找法適合于存儲(chǔ)結(jié)構(gòu)為A.散列存儲(chǔ)B.C.壓縮存儲(chǔ)C.2. 對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表的存儲(chǔ)方式是A.順序存儲(chǔ)B.鏈接存儲(chǔ)C.以關(guān)鍵字有序排序的順序存儲(chǔ)D.以關(guān)鍵字有序排序的鏈接存儲(chǔ)3. 對(duì)有 18 個(gè)元素的有序表作二分（折半）查找，則查找A.1.2.3B.9.5.2.3C.9.5.3D.

25、9.4.2.34.如果要求一個(gè)線性表既能較快地查找，法。又能適應(yīng)動(dòng)態(tài)變化的要求，可以采用查找方的線性表。順序存儲(chǔ)或鏈接存儲(chǔ)A3的比較序列的下標(biāo)為23A.分塊 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.1B.2C.4D.86. 設(shè)哈希表長(zhǎng)m=14,哈希函數(shù) H(key)=key%11 。表中已有 4個(gè)結(jié)點(diǎn)：addr(14)=3,add(38)=,，其余地址為空，如用線性探測(cè)再散列處理沖突，5addr(61)=6addr(85)=

26、8 關(guān)鍵字為 49 的結(jié)點(diǎn)的地址是A.7B.3C.5D.47. 在采用鏈接法處理沖突的開(kāi)散列表上，假定裝填因子a 的值為 4,則查找任一元素的平均查找長(zhǎng)度為。A.3B.3.5C.4D.2.51- 4BCDA5-7CAA填空題_1在各種查找方法中，平均查找長(zhǎng)_.個(gè)數(shù)n 無(wú)關(guān)的查法方法是。2.二分查找的存儲(chǔ)結(jié)構(gòu)僅限于。3在散列存儲(chǔ)中，裝填因子a的值越大，.貝 U；a的值越小，則。存取元素時(shí)發(fā)生沖突的可能性就越大存取元素時(shí)發(fā)生沖突的可能性就越小4. 對(duì)于二叉排序樹(shù)的查找，若根結(jié)點(diǎn)元素的鍵值大于被查元素的鍵值，則應(yīng)該在二叉樹(shù)的上繼續(xù)查找。5. 高度為 8 的平衡二叉樹(shù)至少有 _ 個(gè)結(jié)點(diǎn)。6. 在散列函

27、數(shù) H(key)=key%p 中，p 應(yīng)取。1.散列表查找2.有序的順序存儲(chǔ)結(jié)構(gòu)3.4.左子樹(shù)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,采用開(kāi)放地址法的二次探測(cè)再散列方法解決沖突，試在018 的散列地址空間中對(duì)該關(guān)鍵字序列構(gòu)造哈希表。解：依題意，m=19，二次探測(cè)再散列的下一地址計(jì)算公式為：d1=H(key)d2j=(d1+j*j)%m24d2ji=(di-j*j)%m; j=1 , 2,.其計(jì)算函數(shù)如下：H(19)=19%13=6H(01)=0

28、1%13=1H(23)=23%13=10H(14)=14%13=1(沖突)H(14)=(1+1*1)%19=2H(55)=55%13=3H(20)=20%13=7H(84)=84%13=6(沖突)H(84)=(6+1*1)%19=7( 仍沖突)H(84)=(6-1*1)%19=5H(27)=27%13=1(沖突)H(27)=(1+1*1)%19=2( 沖突)H(27)=(1 -1)%19=0H(68)=68%13=3(沖突)H(68)=(3+1*1)%19=4H(11)=11%13=11H(10)=10%13=10(沖突)H(10)=(10+1*1)%19=11(仍沖突)H(10)=(10-1

29、*1)%19=9H(77)=77%13=12因此：各關(guān)鍵字的記錄對(duì)應(yīng)的地址分配如下:addr(27)=0addr(01)=1addr(14)=2addr(55)=3addr(68)=4addr(84)=5addr(19)=6addr(20)=7addr(10)=9addr(23)=10addr(11)=11addr(77)=12其他地址為空。25綜合題1. 設(shè)散列表為 T : 0.12 ，散列函數(shù)為 H (key) =key%13,給定鍵值序列是 39, 36, 28,38, 44, 15, 42, 12, 06, 25,請(qǐng)畫(huà)出分別用拉鏈法和線性探查法處理沖突時(shí)所構(gòu)造的散 列表，并求出在等概率

30、情況下，這兩種方法查找成功和查找失敗時(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 所示。用線性探查法處理沖突構(gòu)造的表 8-1 散列表下標(biāo)0123456789101112T :0.12 39122815424406253638查找成功探查次數(shù)1312211911查找失敗探查次

31、數(shù)9876543211 2 110在等概率的情況下，查找成功的平均查找長(zhǎng)度ASL=(1X6+2X2+3X1+9X1)/10=2.2設(shè)待查鍵值 k 不在散列表中：若H (k) =k%13=d 則從 i=d開(kāi)始順次與 T i 位置的鍵值進(jìn)行比較，直到遇到空位，才確定其查找失敗，同時(shí)累計(jì)k 鍵值的比較次數(shù)，例如若 k%13=0 則必須將k 與 T : 0、T : 1 、，、T :8中的鍵值進(jìn)行比較之后，發(fā)現(xiàn)T:8為空，比較次數(shù)為 9、類(lèi)似地可對(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/1

32、3=4.54(2)拉鏈法處理沖突用拉鏈法處理沖突構(gòu)造的散列表見(jiàn)圖8-2 所示。在等概率的情況下查找成功的平均查找長(zhǎng)度：ASL=(1X7+2X2+3X1)/10=1.4設(shè)待查鍵值 k 不在散列表中，若k%13=c。則需在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, 187,123, 70, 63, 7，共 有 13

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

34、=(1X10+2X3)/13=16/13=11301234567891011圖 8.3 處理沖突的鏈接表28第 9 章 排序單項(xiàng)選擇題在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無(wú)關(guān)1. 的是A.起泡排序B.快速排序C.堆排序D.基數(shù)排序在待排序的兀素序列基本有序的前提下，效率最咼的排序方法3. 是進(jìn)行一趟歸并后的結(jié)果 為A.希爾排序B.起泡排序C.插入排序D.選擇排序2.設(shè)有 10000個(gè)無(wú)序的兀素, 希望用最快的速度挑選出其中前10 個(gè)最大的元素，排序方A.插入排序B.選擇排序C.快速排序D.歸并排序4. 一組記錄的排序碼為（46 , 79,56,38 , 40, 84），則利用

35、堆排序的方法建立的初始堆為A.79 , 46 , 56 , 38 , 40 , 80B.84,79, 56, 38,40, 46C.84 , 79 , 56 , 46 , 40 , 38D.84,56, 79, 40,46 , 385.在下列算法中, 都不在其最終的位置上。算法可能出現(xiàn)下列情況: 在最后一趟開(kāi)始之前，所有的元素A.堆排序 B .冒泡排序6. 一組記錄的關(guān)鍵碼為（46 ,C.插入排序 D.快速排序84）,則利用快速排序的方法，以第一個(gè)記錄79, 56, 38, 40,為基準(zhǔn)得到的一次劃分結(jié)果為A.38 , 40, 46, 56, 79, 84B.40,38,C.40 , 38, 46, 56, 79, 847. 一組記錄的排序碼為(48 , 16,D.40, 38, 46, 84, 56, 7923 , 36 , 72),按歸并排序的方法對(duì)該序列A.1648357923823672B. 163548798