數(shù)據(jù)結構復習題目與答案

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

2、時間復雜度進行估計的時候，下列最佳的時間復雜度是。A. n2 B. nlogn C. nD. logn7 .設使用某算法對n個元素進行處理，所需的時間是T(n)=100nlog2n+200n+2000,則該算法的漸近時間復雜度為。A. O(1) B. O(n) C. O(200n) D. O(nlog2n)CDCBBDD第二章線性表單項選擇題1 .鏈表不具有的特點是。A.可隨機訪問任一元素B.插入和刪除時不需要移動元素C.不必事先估計存儲空間D.所需空間與線性表的長度正比2 .設順序表的每個元素占8個存儲單元。第1個單元的存儲地址是100,則第6個元素占用的最后一個存儲單元的地址為 。A.13

3、9B.140C. 147D. 1483 .在線性鏈表存儲結構下，插入操作算法 。A.需要判斷是否表滿B.需要判斷是否表空C.不需要判斷表滿D.需要判斷是否表空和表滿4 .在一個單鏈表中，若刪除p所指結點的后繼結點，則執(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 .將長度為n的單鏈表接在長度為m的單鏈表之后的算法時間復雜度為 。A. O(n) B. O(1) C. O(m)D. O(m+n)6 .需要預分較大空間，插入和刪除不需要移動

4、元素的線性表，其存儲結構是 。A.單鏈表B.靜態(tài)鏈表C.線性鏈表D.順序存儲方式ACCABB填空題1 .在帶表頭結點的單鏈表中，當刪除某一指定結點時，必須找到該結點的 結點。2 .在單鏈表中，指針 p所指結點為最后一個結點的條件是 。3 .將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是。4 .在一個長度為n的順序表中第i個元素(1wiwn)之前插入一個元素時，需向后移動元 素的個數(shù)是。5 .在長度為n的順序表中插入一個元素的時間復雜度為 。1前驅2 ,p-next=NULL3.14.n-i+15.O(n)例題解析【例2-1】 編寫一個算法將一個單鏈表逆轉，要求在原表上進行，不允

5、許重新建鏈表。解：該算法可以在遍歷原表的時候將各結點的指針逆轉，從原表的第一個結點開始，頭結點的指針在最后修改成指向原表的最后一個結點，即新表的第一個結點。實現(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;/* 逆轉指針 */q=s;/*指針前移*/s=p;h-next=q;/*頭指針h的后繼是p*/【例2-2】 編寫一算法將兩個按元素值遞增有序排列的單鏈表A和B歸并成一個按元素值遞增有序排列的單鏈表Co解：對于兩個或兩個以上的，結點按

6、元素值有序排列的單鏈表進行操作時，應采用“指 針平行移動，依次掃描完成”的方法。從兩表的第一個結點開始順鏈表逐個將對應數(shù)據(jù)元素 進行比較，復制小的并插入 c表尾。當兩表中之一已到表尾，則復制另一個鏈表的剩余部分，插入到c表尾。設pa、pb分別指向兩表當前結點，p指向c表的當前表尾結點。若設 A中 當前所指的元素為a, B中當前所指的元素為 b,則當前應插入到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)實現(xiàn)本題功能的函數(shù)如下：Lnode *hb(Lnode *pa,Lnode *p

7、b)/*建立表c的頭結點pc*/Lnode * p,* q,*pc;pc=(Lnode*)malloc(sizeof(Lnode);p=pc;/*p指向C表頭結點*/while(pa!=NULL&pb!=NULL)(q=(Lnode*)malloc(sizeof(Lnode);/*建立新結點 q*/if(pb-datadata) /*比較A、B表中當前結點的數(shù)據(jù)域值的大小*/q-data=pb-data;/*B中結點值小，將其值賦給q的數(shù)據(jù)域*/pb=pb-next;/*B 中指針 pb 后移 */elseq-data=pa-data;/* 相反,pa=pa-next;p-next=q;p=q

8、;將A結點值賦給q的數(shù)據(jù)域*/*A中指針pa后移*/*將q接在p的后面*/*p始終指向C表當前尾結點*/while(pa!=NULL)/*若表A比B長，將A余下的結點鏈在 C表尾*/q=(Lnode*)malloc(sizeof(Lnode);q-data=pa-data;pa=pa-next;p-next=q;p=q;while(pb!=NULL)/*若表B比A長，將B余下的結點鏈在 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的頭結點pc

9、*/pc=p-next;/*改變指針狀態(tài)，使 pc指向p的后繼*/free(p);/* 釋放 p 空間 */return (pc);此算法的時間復雜度為 O(m+n),其中m, n分別是兩個被合并表的表長。第三章棧和隊列單項選擇題1 .在初始為空的堆棧中依次插入元素f, e, d, c, b, a以后，連續(xù)進行了三次刪除操作,此時棧頂元素是A. cB. dC. bD. e2 .若某堆棧的輸入序列是1, 2, 3, ., n,輸出序列的第一個元素為n,則第i個輸出元素為。A. iB. n-i C. n-i+1D.哪個元素無所謂3 .向一個棧頂指針為h的帶頭結點鏈棧中插入指針s所指的結點時，應執(zhí)行

10、B. s-next = h;A. h-next = s;C. s-next = h; h = h-next;D. s-next = h-next; h-next=s;4. 一個棧的入棧序列是A. edcba5 .棧和隊列的共同點是A.都是先進后出C.只允許在端點處插入和刪除元素6 .對于循環(huán)隊列。A.無法判斷隊列是否為空C.隊列不可能滿a, b, c, d, e,則棧的不可能的輸出序列是B. decba oC. dceabD. abcdeB.都是先進先出D.沒有共同點B.無法判斷隊列是否為滿D.以上說法都不是7.若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前隊尾指針rear和隊頭指針front的

11、值分別為0和3。當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為 。A. 1 和 5B. 2 和 48.判定一個循環(huán)隊列 QU (最多元素為A. QU-front=QU-rearC. QU-front=(QU-rear+1) % m09.判定一個循環(huán)隊列QU (最多元素為A. QU-front=QU-rearC. QU-front=(QU-rear+1) % m0C. 4 和 2D. 5 和 1m0)為滿隊列的條件是 B. QU-front!=QU-rearD. QU-front!=(QU-rear+1) % m0 m0)為空的條件是。B. QU-front!=QU-r

12、earD. QU-front!=(QU-rear+1) % m0BCDCCDACA填空題1 .在求表達式值的算符優(yōu)先算法中使用的主要數(shù)據(jù)結構是 。2 .設有一個空棧，現(xiàn)輸入序列為1, 2, 3, 4, 5。經(jīng)過 push, push, pop, push, pop, push,pop, push后，輸出序歹U是 。3 .僅允許在同一端進行插入和刪除的線性表稱為 。7 .在順序棧s中，棧為空的條件是 ,棧為滿的條件是 。4 .用S表示入棧操作，X表示出棧操作，若元素入棧順序為1234,為了得到1342出棧順序，相應的S、X操作串為。5 .用一個大小為1000的數(shù)組來實現(xiàn)循環(huán)隊列，當前 rear和

13、front的值分別為0和994,若 要達到隊滿的條件，還需要繼續(xù)入隊的元素個數(shù)是 。1.棧2.2 3 43.棧4.s.top=s.base, s.top-s.base=s.stacksize SXSSXSXX 5.993例題解析【例3-1】 編程實現(xiàn)：用除法把十進制數(shù)轉換成二進制數(shù)。解：算法思想：用初始十進制數(shù)除以 2把余數(shù)記錄下來并且若商不為0則再用商去除以2直到商為0,這時把所有的余數(shù)按出現(xiàn)的逆序排列起來（先出現(xiàn)的余數(shù)排在后面，后出現(xiàn) 的余數(shù)排在前面）就得到了相應的二進制數(shù)，如把十進制數(shù)35轉換成二進制數(shù)的過程如圖3-1所示。35余數(shù) 結果：1001117圖3-1十進制數(shù)轉換成二進制數(shù)的過

14、程由題意可知，我們可以用一個棧來保存所有的余數(shù)，當商為0時則讓棧里的所有余數(shù)出棧則可以得到正確的二進制數(shù)，算法可描述如下：void conversion()Stack S;int n;InitStack(&S);printf(Input a number to convert:n);scanf(%d,&n);if(n1)層最多有 個結點；一棵有 n (n0)個結點的滿二叉 樹共有 個葉子和 個非終端結點。1 1o log no logn答：22214 .具有n個結點的完全二叉樹的深度為 。5 .哈夫曼樹是帶權路徑度 的樹，通常權值較大的結點離根 。最短較近6 .在 遍歷二叉樹的序列中，任何結點

15、的子樹上的所有結點，都是直接跟在該結點之后。k6 k11 .答：k1 k2 k5 k7 k4 2 3 4 k5,2 .3 .4 .floor(log 2n)+15 .6 . 先根例題解析【例6-1】由如圖6-1所示的二叉樹，回答以下問題。(1)其中序遍歷序列為;(2)其前序遍歷序列為;(3)其后序遍歷序列為；(4)該二叉樹的中序線索二叉樹為;(5)該二叉樹的后序線索二叉樹為；(6)該二叉樹對應的森林是。圖6-1 1棵二叉樹解：中序遍歷序列為 dgbaechif 前序遍歷序列為 abdgcefhi 后序遍歷序列為 gdbeihfca 該二叉樹的中序線索二叉樹如圖 該二叉樹的后序線索二叉樹如圖6-

16、1-1 (b)所示 該二叉樹對應白森林如圖6-1-2所示6.1.1(a)所示圖6-1-1二叉樹的中序線索二叉樹和后序線索二叉樹圖6-1-2二叉樹對應的森林綜合題1.二叉樹結點數(shù)值采用順序存儲結構，如表 6-2所示。表6-2二叉樹的順序存儲結構12345678910 11 12 13 14 15 16 17 18 19 20eafdgcjhib(1)畫出二叉樹表示；(2)寫出前序遍歷，中序遍歷和后序遍歷的結果;(3)寫出結點值 c的父結點，其左、右孩子。解：(1)該二叉樹如圖6-9所示。圖6-9 1棵二叉樹(2)本題二叉樹的各種遍歷結果如下:前序遍歷:eadcbjfghi中序遍歷:后序遍歷:(3

17、) c的父結點為abcdjefhgibcjdahigfad,左孩子為j,沒有右孩子。2.有一份電文中共使用9,試畫出對應的哈夫曼樹5個字符：a、b、c、d、e,它們的出現(xiàn)頻率依次為4、 7、 5、 2、(請按左子樹根結點的權小于等于右子樹根結點的權的次序構造)并求出每個字符的哈夫曼編碼。解：依題意，本題對應的哈夫曼樹如圖 各字符對應的哈夫曼編碼如下：6-15所示。a：001b：10c：01d：000e： 11圖6-15 一棵哈夫曼樹3.設給定權集 w=2 , 3, 4, 7, 8, 9,試構造關于 w的一棵哈夫曼樹，并求其加權路徑 長度WPL。圖6-16 一棵哈夫曼樹其加權路徑長度 WPL=7

18、 X 2+8 X 2+4 X 3+2 X 4+3 乂 4+9 乂 2=804,已知一棵二叉樹的中序序列為 線索二叉樹。解：由后序序列的最后一個結點 的左子樹由 cbed組成，右子樹由cbedahgijf,后序序列為 cedbhjigfa ,畫出該二叉樹的先序a可推出該二叉樹的樹根為a,由中序序列可推出hgijf組成，又由cbed在后序序列中的順序可推出該子樹的根結點為 b, 其右子樹為結點 樹的先序序列為：其左子樹只有一個結點 c,右子樹由ed組成，顯然這里的 e是根結點, d,這樣可得到根結點 a的左子樹的先序序列為： bcde;再依次推出右子fghij。因此該二叉樹如圖6-17所示。圖6-

19、17二叉樹設二叉樹的先序線索鏈表如圖6-18所示。圖6-18二叉樹的先序線索鏈表第7章圖單項選擇題1 .在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的 倍。A. 1/2B. 1C. 2D. 42 .在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的 B 倍。A. 1/2B. 1C. 2D. 43 .具有 4個頂點的無向完全圖有 條邊。A. 6B.12C. 16D. 204 .具有6個頂點的無向圖至少應有 條邊才能確保是一個連通圖。A. 5B. 6C. 7D. 85 .在一個具有 n個頂點的無向圖中，要連通全部頂點至少需要 條邊。A. nB. n+1 C. n-1D. n/26 .對于一個

20、具有 n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是 。A. nB. (n-1)2 C. n-1D. n27 .對于一個具有 n個頂點和e條邊的無向圖，若采用鄰接表表示，則所有鄰接表中的結 點總數(shù)是。A. e/2B. eC. 2eD. n+e8 .已知一有向圖的鄰接表存儲結構如圖7-2所示。(1)根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點 v1出發(fā)，所得到的頂點序列是 。A. v1 , v2 , v3, v5, v4B. v1 , v2 , v3, v4, v5C. v1 , v3, v4, v5 , v2D. v1 , v4 , v3, v5, v2(2)根據(jù)有向圖的廣度優(yōu)先遍歷算法，從頂

21、點 v1出發(fā)，所得到的頂點序列是 A. v1 , v2 , v3, v4, v5B. v1 , v3, v2, v4, v5C. v1 , v2, v3, v5, v4D. v1 , v4, v3, v5, v2圖7-2 一個有向圖的鄰接表存儲結構9.判定一個有向圖是否存在回路除了可以利用拓撲排序方法外，還可以利用 。A.求關鍵路徑的方法B.求最短路徑的 Dijkstra方法C.廣度優(yōu)先遍歷算法D.深度優(yōu)先遍歷算法1-5.CBAAC6-9 DCCBD填空題1 . n個頂點的連通圖至少 條邊。2 .在無向圖 G的鄰接矩陣 A中，若 Aij等于1,則A皿i等于。3 .已知圖G的鄰接表如圖 7-3所

22、示，其從頂點v1出發(fā)的深度優(yōu)先搜索序列為 ,其從 頂點v1出發(fā)的廣度優(yōu)先搜索序列為 。圖7-3 G的鄰接表4 .設x,y是圖G中的兩頂點，則(x,y)與(y,x)被認為 邊，但x,y與y,x是的兩條弧。答：無向，有向5 .已知一個圖的鄰接矩陣表示，刪除所有從第i個結點出發(fā)的邊的方法是 。6 .在有向圖的鄰接矩陣上，由第i行可得到第 個結點的出度，而由第j列可得到第個結點的入度。ij7 .在無向圖中，如果從頂點v到頂點v有路徑，則稱v和v是 的。如果對于圖中的任意兩個頂點vi,vj C V,且vi和vj都是連通的，則稱 G為。連通，連通圖1 .n-12 .13 .答： v1, v2 , v3,

23、v6, v5, v4 v1 , v2, v5 , v4, v3, v64 .5 .將矩B車第i行全部置為 06 .7 .例題解析【例7-1】對m個頂點的無向圖 G,采用鄰接矩陣，如何判別下列有關問題:(1)圖中有多少條邊？(2)任意兩個頂點i和j是否有邊相連？(3)任意一個頂點的度是多少？解：鄰接矩陣非零元素個數(shù)的總和除以2。當A i,j W0時，表示兩頂點i,j之間有邊相連。計算鄰接矩陣上頂點對應行上非零元素的個數(shù)。綜合題1 .給出如圖7-4所示的無向圖G的鄰接矩陣和鄰接表兩種存儲結構。圖7-4無向圖G7-5所示的圖G進行遍歷（從頂點1出發(fā)），給1, 2, 3, 6, 4, 5, 8, 7,

24、深度優(yōu)先搜索的序列解：圖G對應的鄰接矩陣和鄰接表兩種存儲結構分別如圖所示。鄰撞柜眸如下：0 1 0 1 0 Op 001010* 口 0 (W 3 0 100100 0 0 0 0 Qp0 0 0 0 102 .用廣度優(yōu)先搜索和深度優(yōu)先搜索對如圖 出遍歷序列。解：搜索本題圖的廣度優(yōu)先搜索的序列為: 為：1, 2, 6, 4, 5, 7, 8, 3。圖7-5無向圖G3 .使用普里姆算法構造出如圖7-6所示白圖G的一棵最小生成樹。圖7-6無向圖G解：使用普里姆算法構造棵最小生成樹的過程如圖7-11所示。14(a)(b )1(d)(c)圖 7-11普里姆算法構造最小生成樹的過程4 .使用克魯斯卡爾算

25、法構造出如圖7-7所示的圖G的一棵最小生成樹。7-12所示。解：使用克魯斯卡爾算法構造棵最小生成樹的過程如圖(a)7-12克魯斯卡爾算法構造最小生成樹的過程(d)(e)第8章查找單項選擇題1.順序查找法適合于存儲結構為的線性表。A.散列存儲B.順序存儲或存儲C.壓縮存儲C.索引存儲2.對線性表進行折半查找時,要求線性表的存儲方式是A.順序存儲B.存儲C.以關鍵字有序排序的順序存儲D.以關鍵字有序排序的存儲3 .對有18個元素的有序表作二分（折半）查找，則查找 A3的比較序列的下標為A. 1.2.3 B. 9.5.2.3 C. 9.5.3 D. 9.4.2.3查找方4 .如果要求一個線性表既能較

26、快地查找，又能適應動態(tài)變化的要求， 可以采用法。A.分塊 B, 順序 C. 二分 D. 散列5 .有一個有序表為2, 5, 7, 11, 22 , 45, 49, 62, 71 , 77, 90, 93, 120,當折半查找值 為90的結點時，經(jīng)過 次比較后查找成功。A. 1 B. 2 C. 4 D, 86,設哈希表長 m=14,哈希函數(shù) H(key)=key % 11。表中已有 4 個結點：addr(14)=3 ,addr(38)=5 , addr(61)=6 , addr(85)=8 ,其余地址為空，如用線性探測再散列處理沖突，關鍵字為49的結點的地址是。A. 7 B. 3 C. 5 D,

27、 47.在采用法處理沖突的開散列表上，假定裝填因子 找長度為。A. 3B,3.5C.4D,2.51-4 BCDA5-7CAA填空題1.在各種查找方法中，平均查找長度與結點個數(shù)2,二分查找的存儲結構僅限于 。3,在散列存儲中，裝填因子”的值越大，則 存取元素時發(fā)生沖突的可能性就越大a的值為4 ,則查找任一元素的平均查n無關的查法方法是 。；a的值越小，則 。存取元素時發(fā)生沖突的可能性就越小4,對于二叉排序樹的查找，若根結點元素的鍵值大于被查元素的鍵值，則應該在二叉樹的上繼續(xù)查找。5,高度為8的平衡二叉樹至少有 個結點。6.在散列函數(shù) H(key)=key % p 中，p應取。1. 散列表查找2.

28、 有序的順序存儲結構3. 4. 左子樹5. 546. 素數(shù)例題解析【例 8-1】設有一組關鍵字19 , 01, 23, 14, 55, 20, 84, 27, 68, 11, 10, 77,采 用哈希函數(shù)：H(key)=key %13 ,采用開放地址法的二次探測再散列方法解決沖突，試在018的散列地址空間中對該關鍵字序列構造哈希表。解：依題意，m=19,二次探測再散列的下一地址計算公式為：d 1 =H(key)d2j=( d 1 +j*j) % md 2j i =( d 1 -j*j) % m ; j=1 , 2,.其計算函數(shù)如下：H(19)=19 % 13=6H(01)=01 % 13=1H

29、(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

30、+1*1) % 19=11 (仍沖突)H(10)=(10-1*1) % 19=9H(77)=77 % 13=12因此：各關鍵字的記錄對應的地址分配如下: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其他地址為空。綜合題28,1 .設散列表為T 0.12 ,散列函數(shù)為 H (key) = key%13,給定鍵值序列是 39, 36, 38, 44, 15, 42, 12, 06, 25,請畫出分別用

31、拉鏈法和線性探查法處理沖突時所構造的散 列表，并求出在等概率情況下，這兩種方法查找成功和查找失敗時的平均查找長度。并用探查次數(shù)表示待查鍵解 用散列函數(shù)H (key) = key% 13計算出鍵值序列的散列地址。 值需對散列表中鍵值比較次數(shù)。鍵值序列：39, 36, 28, 38, 44, 15, 42, 12 , 06, 25散列地址： 0, 10, 2, 12, 5, 2, 3, 12, 6, 12(1)線性探查法處理沖突用線性探查法處理沖突構造的散列表見表8-1所示。表8-1用線性探查法處理沖突構造的散列表下標101112T 0.12 查找成功探查次數(shù)3912281542440625363

32、810查找失敗探查次數(shù)在等概率的情況下，查找成功的平均查找長度ASL= (1X6+2X 2+3X 1+9X 1) /10=2.2設待查鍵值k不在散列表中：若 H (k) = k% 13= d,則從i=d開始順次與T i位置k鍵值的比較次數(shù)，例如的鍵值進行比較，直到遇到空位，才確定其查找失敗，同時累計若k% 13= 0 ,則必須將k與T 0、T 1、T 8中的鍵值進行比較之后，發(fā)現(xiàn) T 8為空，比較次數(shù)為 9、類似地可對k% 13=1, 2, 3,，12進行分析可得查找失敗的平均查找長度。ASL = (9+8+7+6+5+4+3+2+1+1+10) /13 = 59/13 = 4.54(2)拉鏈

33、法處理沖突用拉鏈法處理沖突構造的散列表見圖8-2所示。T(C .12)01234567Xy101112圖8-2拉鏈法處理沖突構造的散列表在等概率的情況下查找成功的平均查找長度：ASL= (1X7+2X 2+3X 1) /10=1.4設待查鍵值k不在散列表中，若 k% 13= d。則需在d鏈表中查找鍵值為 k的結點，直 到表尾，若不存在則查找失敗，設 d鏈表中有i個結點，則k需與表中鍵值比較i次，查 找失敗的平均長度為：ASL= (1+ 0+ 2+ 1+ 0+ 1+ 1+ 0+0+0+1+0+3) /13=10/13 = 0.772 .線性表的關鍵字集合87 , 25, 310, 08, 27,

34、 132 , 68, 95, 187, 123, 70, 63, 7,共 有13個元素，已知散列函數(shù)為：H(k) = k % 13,采用拉鏈法處理沖突。設計出這種鏈表結構，并計算該表的成功查找的平均查找長度。解：依題意，得到：H(87)=87 % 13=9H(25)=25 % 13=12H(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=5H(63)=63 % 1

35、3=11H(47)=47 % 13=8采用拉鏈法處理沖突的表如圖8-3所示。成功查找的平均查找長度:ASL=(1X 10+2 X3)/13=16/13=1 13圖8.3處理沖突的鏈接表0123456789101112第9章排序單項選擇題1 .在所有排序方法中，關鍵字比較的次數(shù)與記錄的初始排列次序無關的是 。A.希爾排序B.起泡排序C.插入排序D.選擇排序2 .設有10000個無序的元素，希望用最快的速度挑選出其中前10個最大的元素，排序方法最好選用。A.起泡排序B.快速排序C.堆排序 D.基數(shù)排序3 .在待排序的元素序列基本有序的前提下，效率最高的排序方法是 。A.插入排序B.選擇排序C.快速

36、排序D.歸并排序4 . 一組記錄的排序碼為(46 , 79, 56, 38, 40, 84),則利用堆排序的方法建立的初始堆為 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)下列情況：在最后一趟開始之前，所有的元素 都不在其最終的位置上。A.堆排序 B .冒泡排序C .插入排序 D.快速排序6 .一組記錄的關鍵碼為(46, 79, 56, 38, 40, 84),則利用快速排序的方法，以第一個記錄 為基準得到的一次劃分結果為

37、 。A. 38 , 40, 46, 56, 79, 84 B. 40, 38, 46, 79, 56, 84C.40 , 38, 46, 56, 79, 84D. 40, 38, 46, 84, 56, 797 .一組記錄的排序碼為(48, 16, 79 , 35, 82, 23, 36, 72),按歸并排序的方法對該序列 進行一趟歸并后的結果為 。A. 16 48 35 79 23 82 36 72 B. 16 35 48 79 82 23 36 72C. 16 48 35 79 82 23 36 72 D. 16 35 48 79 23 36 72 828 .排序方法中，從未排序序列中依次

38、取出元素與已排序序列(初始時為空)中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為 。A.希爾排序B.起泡排序C.插入排序D.選擇排序9 .排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列(初始時為空)的一 端的方法，稱為。A.希爾排序B.歸并排序C.插入排序D.選擇排序6-9 CACD填空題1 .在對一組記錄(54, 38, 96, 23, 15, 72, 60, 45, 83)進行直接插入排序時，當把第 8個 記錄45插入到有序表時，為尋找插入位置需比較 、次。2 .對于關鍵字序列(12, 13, 11 , 18, 60, 15, 7, 20, 25, 100),用

39、篩選法建堆，必須從 鍵值為 的關鍵字開始。3 .對n個記錄的表r1.n進行簡單選擇排序，所需進行的關鍵字間的比較次數(shù)為 4 .在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用 ;若初始數(shù)據(jù)基本反序則選用。插入排序選擇排序5 .對n個元素的序列進行起泡排序時，最少的比較次數(shù)是 。6 . 排序不需要進行記錄關鍵字間的比較。1. 52. 603. n(n-1)/24. 5. n-16. 基數(shù)綜合題1 .已知序列49. 38, 65, 97, 76, 13, 27,請給出采用起泡排序對該序列作升序排列的每一 趟的結果。2 .已知序列503 , 87, 512, 61 , 908, 170, 897, 2

40、75, 653, 462,采用快速排序法對該序 列作升序排序時的每一趟的結果。3 .已知序列265, 301 , 751, 129, 937, 863, 742, 694, 076, 438,采用基數(shù)排序法對該 序列作升序排序時的每一趟的結果。4 .已知序列503, 17, 512, 908, 170, 897, 275, 653, 426, 154, 509, 612, 677, 765, 703, 94,請給出采用希爾排序法(d1=8)對該序列作升序排序時的每一趟的結果。5 .已知序列35, 89, 61 , 135, 78, 29, 50,請給出采用插入排序法對該序列作升序排序 時的每一

41、趟的結果。6 .已知序列11 ,18, 4, 3, 6, 15, 1, 9, 18, 8,請給出采用歸并排序法對該序列作升序 排序時的每一趟的結果。1 .解：根據(jù)起泡排序法的基本思想，比較無序區(qū)中相鄰關鍵字。按照大小關系調整其位置，本題的解法是，通過比較已知序列中相鄰關鍵字，并根據(jù)需要調整其位置、重復此過程直到?jīng)]有關鍵字的位置交換為止，結果正好是關鍵字的升序排列。依題意，采用起泡排序法排序的各趟的結果如下:初始：49, 38、65, 97, 76, 13, 27第一趟；38496576132797第二趟：38496513277697第二趟：3849.1327657697第四趟：38132749657697第五趟：1327384965.7697用八趟：13273849657697第六題無兀素交換,排序結束.D2 .依題意，采用快速排序法排序的各趟的結果如下：初始：503, 87, 512, 61, 908, 170, 897, 275, 653, 462第1趟趟：462,87, 275, 61,170 503 897908