《數(shù)據(jù)結(jié)構(gòu)習題集答案》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)習題集答案（10頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、數(shù)據(jù)結(jié)構(gòu)習題第一章 緒論1.1數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的_ 以及它們之間的_ 和運算等的學科。A.數(shù)據(jù)元素 B.計算方法 C.邏輯存儲 D.數(shù)據(jù)映像A.結(jié)構(gòu) B.關(guān)系 C.運算 D.算法1.2 算法分析的目的是_ ，算法分析的兩個主要方面是_ 。 A.找出數(shù)據(jù)結(jié)構(gòu)的合理性 B.研究算法中的輸入和輸出的關(guān)系C.分析算法的效率 以求該進 D.分析算法的易懂性和文檔性 A.空間復(fù)雜度和時間復(fù)雜度 B.正確性和簡明性C.可讀性和文檔性 D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性1.3 計算機算法指的是_ ，它必須具備輸入、輸出和_ 等5個重要特性。 A.計算方法 B.排序方法C.解決問題的有
2、限運算序列 D.調(diào)度方法 A.可讀性、可移植性和可擴展性 B. 可讀性、可移植性和有窮性C.確定性、有窮性和可行性 D.易讀性、穩(wěn)定性 和安全性1.4數(shù)據(jù)元素是數(shù)據(jù)處理的 基本單位；數(shù)據(jù)項是數(shù)據(jù)處理的_最小單位。1.5數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的 邏輯結(jié)構(gòu)_和_物理結(jié)構(gòu)_，并對這種結(jié)構(gòu)定義相適應(yīng)的運算，設(shè)計出相應(yīng)的算法，分析算法的效率。算法的效率包括時間和空間兩個方面，分別稱為_空間復(fù)雜度和時間復(fù)雜度。數(shù)據(jù)的邏輯結(jié)構(gòu)是指_數(shù)據(jù)元素之間的關(guān)系_；包括線性結(jié)構(gòu)、 樹形結(jié)構(gòu)和 圖形結(jié)構(gòu) 三種類型,其中樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱為_非線性結(jié)構(gòu)_。1.6 線性結(jié)構(gòu)中元素之間存在_一對一_ 關(guān)系，樹形結(jié)構(gòu)中元素之間存
3、在_一對多_ 關(guān)系，圖狀結(jié)構(gòu)中元素之間存在_多對多_ 關(guān)系。1.7 數(shù)據(jù)結(jié)構(gòu) 在計算機中的表示稱為數(shù)據(jù)的物理（或存儲）結(jié)構(gòu)，數(shù)據(jù)的物理結(jié)構(gòu)可以采用_順序存儲和_鏈式存儲_兩種存儲方法。1.8順序存儲方法是把邏輯上相鄰的元素 存儲在物理位置 相鄰的內(nèi)存單元中 ；鏈式存儲方法中元素間的關(guān)系是由_指針來表示_的。第二章 線性表2.1 鏈表不具備的特點是 _ 。 A.可隨機訪問任一結(jié)點 B.插入刪除不需移動元素C.不必事先估計存儲空間 D.所需空間與其長度成正比2.2 不帶頭結(jié)點的單鏈表head 為空的判定條件是_。A. head=null B. head->next=nullC. head-&
4、gt;next=head D. head !=null2.3帶頭結(jié)點的單鏈表head 為空的判定條件是_。A. head=null B. head->next=nullC. head->next=head D. head!=null2.4 非空的循環(huán)單鏈表head 的尾結(jié)點（由p所指向）滿足_。A. p->next=null B. p=null C. p->next=head D. p=head2.5 在一個具有n 個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然保持有序的時間復(fù)雜度是_。A. O(1) B. O(n) C. O(n2) D. O(nlog2n)2.6線性鏈表中
5、各個結(jié)點之間的地址 不一定 連續(xù)。2.7線性表中數(shù)據(jù)元素之間具有_一對一_，除第一個和最后一個元素外，其他數(shù)據(jù)元素有且只有_一個后繼和前趨。2.8若頻繁地對線性表進行插入和刪除操作，該線性表采用 鏈式 存儲結(jié)構(gòu)比較合適。2.9 在一個單鏈表中p所指結(jié)點之后插入一個s所指結(jié)點時，應(yīng)執(zhí)行s->next=_p->next_和p->next=_s_的操作。2.10 已知具有n個元素的一維數(shù)組采用順序存儲結(jié)構(gòu)，每個元素占k個存儲單元，第一個元素的地址為LOC(a1)，那么，LOC(ai)=_ LOC(a1)+（i-1）*k_。2.12 若線性表采用順序存儲結(jié)構(gòu)，每個數(shù)據(jù)元素占用3個存儲
6、單元，第11個數(shù)據(jù)元素的存儲地址為130，則第1個數(shù)據(jù)元素的存儲地址是 100 。2.12 若線性表采用順序存儲結(jié)構(gòu)，線性表的最大長度為1000，每個數(shù)據(jù)元素占3個存儲單元，則要分配給該線性表_3000_存儲單元，若第一個數(shù)據(jù)元素的存儲地址是2000，則第11個元素的存儲地址是_2030_。2.13 以head為頭結(jié)點循環(huán)雙鏈表為空時，應(yīng)滿足head->llink= head ，head->rlink= head 。 2.14 在單鏈表中，指針p指向元素為x的結(jié)點，實現(xiàn)“刪除x的后繼”的語句是 。A.p=p->next; B.p->next=p->next->
7、;next; C.p->next=p; D.p=p->next->next; 2.15 在單鏈表中，已知q指的結(jié)點是p指的結(jié)點的直接前驅(qū)結(jié)點，若在q和p指的結(jié)點之間插入一個由s指的結(jié)點，則需執(zhí)行_。 A. s->next=p->next;p->next=s B. q->next=s;s->next=pC. p->next=s->next;s->next=p D.p->next=s;s->next=q2.16 用鏈表表示線性表的優(yōu)點是（）A便于隨機存儲 B.便于進行插入和刪除操作C. 占用的存儲空間較順序表少 D.元素
8、的物理順序與邏輯順序相同2.17 下面關(guān)于線性表的敘述中，錯誤的是（）A. 線性表采用順序存儲必須占用一片連續(xù)的存儲單元B. 線性表采用順序存儲便于進行插入和刪除操作C. 線性表采用鏈式存儲不必占用一片連續(xù)的存儲單元D. 線性表采用鏈式存儲便于進行插入和刪除操作2.18 線性表是具有n個（）的有限序列A. 數(shù)據(jù)項 B. 數(shù)據(jù)元素 C. 表元素 D. 字符 2.19長度為n的線性表采用鏈式存儲結(jié)構(gòu)，訪問其第i個元素的算法時間復(fù)雜度為（） A. O（1） B.O（n） C. O（n2） D.O（log2n）2.20 在長度為n的順序表刪除第i（1in）個元素，則需要向前移動元素的次數(shù)為（） A.
9、i B. n-i C. n-i+1 D.n-i-12.21 在長度為n的順序表中第i（1in）個位置上插入一個元素時，為留出插入位置所需要移動元素的次數(shù)為（） A. n-i B. i C. n-i-1 D. n-i+12.22 以下對單鏈表的敘述錯誤的是（）A. 單鏈表中的每一個結(jié)點都由存放結(jié)點值的數(shù)據(jù)域和存放直接后繼結(jié)點地址信息的指針域兩部分組成B.從單鏈表的第i 個結(jié)點出發(fā)，可以訪問到鏈表中的任何一個結(jié)點C.在單鏈表結(jié)構(gòu)中加入頭結(jié)點可以簡化結(jié)點的插入和刪除操作D.單鏈表尾結(jié)點的指針域應(yīng)置為空指針2.23 以下記敘中正確的是 （）A. 線性表的鏈式存儲結(jié)構(gòu)優(yōu)先于順序存儲結(jié)構(gòu)B. 線性表的存儲
10、結(jié)構(gòu)不影響其各種運算的實現(xiàn)C. 選擇線性表的存儲結(jié)構(gòu)就是要保證存儲其各個元素的值D.順序存儲屬于靜態(tài)結(jié)構(gòu)，鏈式存儲屬于動態(tài)結(jié)構(gòu) 第三章 棧與隊列一、選擇題3.1 棧的特點是_B_ ，隊列的特點是_A_ 。A.先進先出 B.先進后出3.2 棧和隊列的共同點時_。A.都是先進后出 B.都是先進先出C.只允許在端點處插入和刪除元素 D.沒有共同點3.3 一個棧的進棧序列是a,b,c,d,e,則棧的不可能的輸出序列是_ 。A. edcba B. decba C. dceab D. abcde3.4 判定一個棧ST（最多元素MaxSize）為空的條件是_ 。A.ST->top!=-1 B. ST-
11、>top=-1C.ST->top!= MaxSize D. ST->top=MaxSize-13.5 判定一個棧ST（最多元素MaxSize）為棧滿的條件是_ 。A.ST->top!=-1 B. ST->top=-1C.ST->top!= MaxSize D. ST->top=MaxSize-13.6 循環(huán)隊列用數(shù)組A0，m-1存放其元素值，已知其頭尾指針分別是front和 rear,則當前隊列中的元素個數(shù)是_。A.（rear-front+m）%m B. rear-front+1C. rear-front-1 D. rear-front3.7 在一個鏈
12、隊中，假設(shè)f和r 分別是隊頭和隊尾指針，則插入一個s結(jié)點的運算時_。 A. f->next=s; f=s; B. r->next=s; r=s;C. s->next=r; r=s; D. s->next=f; f=s;3.8在一個鏈隊中，假設(shè)f和r 分別是隊頭和隊尾指針，則刪除一個結(jié)點的運算時_。 A. r=f->next; B. r=r->next; C. f=f->next; D. f=r->next;3.9若進棧序列為a，b，c，進棧過程中允許出棧，則以下_是不可能得到的出棧序列。A. a,b,c B. b,a,c C. c,a,b D.
13、c,b,a3.10一個最多能容納m個元素的順序存儲的循環(huán)隊列Q，其頭尾指針分別為front和rear，則判定該隊列為滿的條件是_A. (Q.rear+1)%m= =Q.front B. Q.front= =Q.rearC. Q.rear+1= =Q.front D. (Q.front+1)%m= =Q.rear3.11一個最多能容納m個元素的順序存儲的循環(huán)隊列Q，其頭尾指針分別為front和rear，則判定該隊列為空的條件是_A. (Q.rear+1)%m= =Q.front B. Q.front = = Q.rearC. Q.rear+1= =Q.front D. (Q.front+1)%m
14、= =Q.rear3.12若進棧序列為 1，2，3，4，進棧過程中可以出棧，則以下不可能的出棧序列是（）A. 1，4，3，2 B.2，3，4，1 C. 3，1，4，2 D.3，4，2，13.13一個隊列的入隊序列是1，2，3，4，則隊列的輸出序列是_。A. 4,3,2,1 B. 1,2,3,4 C. 1,4,3,2 D. 3,2,4,13.14 若用一個可容納6個元素的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別是0和4，當執(zhí)行2次出隊和1次入隊操作后 ，rear和front 的值分別為（）A.1和0 B.0和2 C.2和5 D.1和5第四章 串和數(shù)組4.1串是一種特殊的線形表，其特
15、殊性體現(xiàn)在_A. 可以順序存儲 B. 數(shù)據(jù)元素是一個字符 C. 可以鏈接存儲 D. 數(shù)據(jù)元素可以是多個字符4.2 串的兩種最基本的存儲方式是_順序和鏈式_。4.3兩個串相等的充分必要條件是: 長度相等_且_對應(yīng)位置上的字符相等_。4.4 如下陳述中正確的是_。A串是一種特殊的線性表 B串的長度必須大于零 C串中元素只能是字母 D空串就是空白串4.5 不含任何字符的串稱為_空串_,其長度為_長度等于零_。4.6 設(shè)有字符串S=“ABC123XYZ”，問該串的長度為（）A.9 B.10 C.11 D.124.7已
16、知二維數(shù)組Amn采用行序為主方式存儲，每個元素占k個存儲單元，并且第一個元素的存儲地址是LOC（A00），則Aij的地址是_loc(a00)+(n*i+j)*k。4.8二維數(shù)組有兩種存儲方式，第一種是以_行 為主序的存儲方式，第二種是以_列_為主序的存儲方式。設(shè)有二維數(shù)組A1020，其中每個元素占2個字節(jié)，數(shù)組按行優(yōu)先順序存儲，第一個元素的存儲地址為100，那么元素A812的存儲地址為_100+（20*8+12）*2 4.9對于稀疏矩陣的壓縮存儲，通常用一個三元組表示非零元素的信息，其中包括非零元素的值、 行、 列 。這些信息可用一個三元組 數(shù)組表示，也稱此為 三元組順序表 。4.10設(shè)有一個
17、10階的對稱矩陣A，采用壓縮存儲方式，以行序為主序存儲，a0,0為第一個元素，其存儲地址為1，每個元素占1個字節(jié)，則a8,5的地址為_。A. 13 B. 33 C. 18 D. 42第五章 樹與二叉樹5.1 采用二叉鏈表存儲結(jié)構(gòu),具有n 個結(jié)點的二叉樹中,一共有_2n_個指針域,其中有_n-1_個指針域指向孩子結(jié)點，有_n+1_個指針域為空.5.2 一棵非空二叉樹,其第i層上最多有_2i-1_結(jié)點。5.3 滿二叉樹是一棵深度為k且恰有_2k-1_結(jié)點的二叉樹.5.4 一棵哈夫曼樹有個m葉子結(jié)點,則其結(jié)點總數(shù)為_2m-1_.5.5 三個結(jié)點的二叉樹，最多有_5_種形狀。5.6 將一棵完全二叉樹按
18、層次編號,對任一編號為i的結(jié)點有:如有左孩子,則其編號為_2i_; 如有右孩子,則其編號為_2i+1.5.7深度為k的非空二叉樹最多有 2k-1個結(jié)點，最少有 k 個結(jié)點，其第i層最多有_2i-1 個結(jié)點。5.8 樹最適合用來表示_。A. 有序數(shù)據(jù)元素 B.無序數(shù)據(jù)元素C. 數(shù)據(jù)之間具有分支層次關(guān)系的數(shù)據(jù) D. 元素之間無聯(lián)系的數(shù)據(jù)5.9 在下列存儲形式中，不是樹的存儲形式的是_。A雙親表示法 B.孩子表示法 C.孩子雙親表示法 D.孩子兄弟表示法5.10 一棵高度為h的滿二叉樹中結(jié)點的個數(shù)為_。 A. 2h B. 2h-1 C. 2h-1 D.2h+15.11 已知一棵二叉樹的先序遍歷序列為
19、ABCDEFG,中序遍歷序列為:CBDAFEG,則該二叉樹的后序遍歷序列是()ACDBFGEA BCDFGBEA CCDBAFGE DCDBFEGA5.12具有100個結(jié)點的完全二叉樹，其中含有_個度為1的結(jié)點。A.1 B. 0 C. 2 D. 不確定5.13 已知一棵二叉樹的先序遍歷序列為EFHIGJK,中序遍歷序列為:HFIEJGK,則該二叉樹的右子樹的根是()A B C D5.14 如下左圖所示二叉樹的中序遍歷序列是_A. abcdgef B. dfebagc C. dbaefcg D. defbagc 5.15 一棵二叉樹如上右圖所示，其中序遍歷的序列為_Aabdgcefh Bdgba
20、echf Cgdbehfca Dabcdefgh5.16在非空二叉樹的中序遍歷序列中，二叉樹的根結(jié)點的左邊應(yīng)該 ( ) A.只有左子樹上的所有結(jié)點 B.只有左子樹上的部分結(jié)點 C.只有右子樹上的所有結(jié)點 D.只有右子樹上的部分結(jié)點5.17 在一非空二叉樹的中序遍歷序列中，根結(jié)點的右邊應(yīng)該_。A. 只有右子樹上的所有結(jié)點 B.只有右子樹上的部分結(jié)點C. 只有左子樹上的部分結(jié)點 D. 只有左子樹上的所有結(jié)點5.18 有一棵樹如下左圖所示，回答下列問題：這棵樹的根結(jié)點是_k1_; 這棵樹的葉子結(jié)點是_k2,k4,k5,k7_結(jié)點k3的度為_2_; 這棵樹的度為_3_這棵樹的深度為_4_; 結(jié)點k3的
21、孩子結(jié)點是_ k5,k6_結(jié)點k3的雙親結(jié)點是_ k1_ 5.19 由上右圖所示的二叉樹，回答以下問題。 其中序遍歷序列為_ 其先序遍歷序列為_ 其后序遍歷序列為_ (4) 該二叉樹對應(yīng)得森林是_5.20某二叉樹的先序遍歷序列為abdgcefh,中序遍歷序列是dgbaechf, 請畫出該二叉樹并給出其后序遍歷序列。gdbehfca5.21 如下左圖所示 ,以數(shù)據(jù)集4，5，6，7，10，12，18為結(jié)點權(quán)值所構(gòu)成的二叉樹為_哈夫曼樹_，其帶權(quán)路徑長度為_165_。 5.22對如上右圖所示的樹，該樹的高度為_，該樹的度為_，結(jié)點E的層次為_，結(jié)點H的雙親為_，結(jié)點H的兄弟為_，結(jié)點B的度為_。5.
22、23若二叉樹中度為2的結(jié)點有15個，該二叉樹則有 16 個葉結(jié)點。5.24若深度為6的完全二叉樹的第6層有3個葉結(jié)點，則該二叉樹一共有 34 個結(jié)點。5.25二叉樹的前序遍歷序列為A，B，C，E，F(xiàn)，D，G，H，中序遍歷序列為A，E，C，F(xiàn)，B，G，D，H，其后序遍歷序列為 。5.26一個深度為k的二叉樹，當具有2k-1個結(jié)點時稱之為_滿二叉樹。5.27下面關(guān)于哈夫曼樹的說法，不正確的是 ( ) A.對應(yīng)于一組權(quán)值構(gòu)造出的哈夫曼樹一般不是唯一的 B.哈夫曼樹具有最小帶權(quán)路徑長度 C.哈夫曼樹中沒有度為1的結(jié)點 D.哈夫曼樹中除了度為1的結(jié)點外，還有度為2的結(jié)點和葉結(jié)點5.28在如圖所示的表達式
23、二叉樹中，按中序遍歷得到的序列為_。第六章 圖6.1 一個具有n個頂點的無向連通圖至少有_n-1_條邊，所有頂點的度數(shù)之和等于所有邊數(shù)的2_倍。6.2 在有向圖的鄰接矩陣中，第i行中1的個數(shù)為第i個頂點的_出度_。第i列中1的個數(shù)為第i個頂點的_入度_。6.3 一個無向圖有n個頂點和e條邊，則所有頂點的度的和為_2e。具有n個頂點的無向完全圖的邊數(shù)為_n(n-1)/2_。具有n個頂點的有向完全圖的弧個數(shù)為_ n(n-1)_。6.4 設(shè)連通圖G的頂點數(shù)為n，則G的生成樹的邊數(shù)為_ n-1 。6.5 若無向圖中有e條邊，則表示該無向圖的鄰接表中就有_2e 個結(jié)點。6.6 Dijkstra算法是按_
24、路徑長序依次遞增_的次序產(chǎn)生一點到其余各頂點最短路徑的算法。6.7 可以進行拓撲排序的有向圖一定是_無環(huán)的_。在拓撲排序序列中第一個頂點一定是_入度為零_的頂點。6.8 設(shè)一個無向圖為如下左圖所示，畫出該圖的鄰接表和鄰接矩陣；寫出從頂點A出發(fā)進行深度優(yōu)先和廣度優(yōu)先搜索得到的頂點序列。 6.9 設(shè)一個無向圖為G=(V,E),其中V=v1,v2,v3,v4，v5,v6,v7 ，E=(v1,v2),(v1,v3),(v2,v4),(v2,v5), (v3,v6),(v3,v7),(v6,v7),畫出該無向圖，畫出其鄰接表和鄰接矩陣，寫出從頂點v1出發(fā)進行深度優(yōu)先和廣度優(yōu)先搜索得到的頂點序列。6.10
25、 設(shè)一個無向圖為G=(V,E),其中V=v1,v2,v3,v4，v5,v6 ，其鄰接矩陣如上右圖所示：(1)畫出該無向圖;(2)畫出其鄰接表和鄰接矩陣;(3)寫出從頂點v1出發(fā)進行深度優(yōu)先和廣度優(yōu)先搜索得到的頂點序列;(4)分別用Prim和Kruskal算法,從頂點v1頂點出發(fā)，寫出求該網(wǎng)的最小生成樹的產(chǎn)生過程。6.11 設(shè)一個圖為G=(V,E),其中V=a,b,c,d,e,f，E=<a,b>,<a,d>,<a,e>,<d,e>，<e,b>，<c,b>，<c,e>，<c,f>,<f,e>
26、(1)畫出該圖;(2)畫出其鄰接矩陣和鄰接表;(3)寫出從頂點a出發(fā)進行深度優(yōu)先和廣度優(yōu)先搜索得到的頂點序列;6.15對如下無向圖，分別用Prim和Kruskal算法,分別從頂點1和頂點a出發(fā)，寫出求該網(wǎng)的最小生成樹的產(chǎn)生過程。62174112191010836 6.16 對下圖，寫出拓撲有序序列？A1a11B2D4C3E5F66.17 對下圖所示的帶權(quán)有向圖，利用Dijstra算法求出從源點A到其余各頂點的最短路徑及其長度。A11B2D4C3E5F251083167210124第七章 查找8.1用順序查找法在具有各結(jié)點的線性表中查找一個結(jié)點所需的平均查找時間為（）。(n) B.O(nlog2
27、n) C.O(n) D.O(log2n)8.2 使用折半查找，線性表必須（）。、一順序方式存儲、以鏈式方式存儲，且元素已按值排好序、以鏈式方式存儲、以順序方式存儲，且元素已按值排好序8.3 采用順序查找法查找長度為n的線性表時，每個元素的平均查找長度為_。 A. n B. n/2 C. （n+1）/2 D. (n-1)/2 8.4 順序查找法適合于存儲結(jié)構(gòu)為_ 的線性表。A散列存儲 B. 順序存儲或鏈式存儲 C. 壓縮存儲 D. 索引存儲8.5采用折半查找法查找長度為n的線性表時，每個元素的平均查找長度為_。 A. O(n2) B. O(nlog2n) C. O(n) D. O(log2n)8
28、.6采用順序查找法檢索長度為n的線性表，則檢索每個元素的平均比較次數(shù)為_n-i+1_。8.7有一個有序表為：(1,3,9,12,32,41,45,62,75,77,82,95,100),當折半查找值82的結(jié)點時，經(jīng)過_次比較后查找成功。A. 1 B. 2 C. 4 D. 88.8折半查找有序表6,15,30,37,65,70,72,89,99,若要查找元素37，需要依次與表中元素_進行比較。A. 65，15，37 B. 68，30，37 C. 65，15，30 D. 65，15，30，378.9 已有序表為（20，18，24，35，47，50，62，83，90，115，134），當用折半法查找
29、90時，需要進行_2_ 次查找可確定成功。查找47時需進行_4_ 次查找可確定成功，查找100時，需進行_4_ 次查找才能確定不成功。8.10 按序列60,17，38，40，7，32，73，65，85的輸入順序建立一顆二叉排序樹.（1）畫出該二叉排序樹；（2）在（1）的基礎(chǔ)上插入結(jié)點80后，畫出對應(yīng)的二叉排序樹;(3) 在（2）的基礎(chǔ)上刪除結(jié)點38后，畫出對應(yīng)的二叉排序樹。8.11按序列（53，49，26，78，63，35，19，99）的輸入順序建立一顆二叉排序樹.（1）畫出該二叉排序樹；（2）在（1）的基礎(chǔ)上插入結(jié)點50后，畫出對應(yīng)的二叉排序樹;(3) 在（2）的基礎(chǔ)上刪除結(jié)點26后，畫出對
30、應(yīng)的二叉排序樹。8.12 已知一組關(guān)鍵字序列為（75，33，52，41，12，88，66，27），請按哈希函數(shù)H(key)=key MOD 7，分別用線性探測和二次探測處理沖突方法構(gòu)造一個表長為10的哈希表。8.13 已知一組關(guān)鍵字為（17，12，21，01，66，35，82，37），請按哈希函數(shù)H(key)=key MOD 13，分別用線性探測和二次探測處理沖突方法構(gòu)造一個表長為14的哈希表。8.14 已知：哈希表長為10，哈希函數(shù)H(key)=key MOD 9，給出關(guān)鍵字序列為（23，45，14，17，9，29,37，18，25,41,33），采用鏈地址法解決沖突，請畫出哈希表。第八章
31、排序9.1 對于給定的12個整數(shù)：23，37，7，79，29，43，73，19，31，61，23，47，分別寫出用直接插入序、冒泡和直接選擇、快速、歸并排序的各趟結(jié)果。9.2排序可分為_和_兩類；衡量排序算法的兩個主要性能指標分別是:_、_。9.3假設(shè)待排序數(shù)據(jù)元素序列為 ，應(yīng)用快速排序方法按遞增序排序，得到第一次劃分后的結(jié)果為_2_3_4_6_5_ 。9.4 排序算法的穩(wěn)定性是指_相同的紀錄經(jīng)過排序后的_是否發(fā)生變化，不發(fā)生變化的排序算法，就是_;否則就是_。9.5 排序算法的基本操作是_和_。9.6 排序算法的_取決于關(guān)鍵字的比較和記錄的移動等基本操作的次數(shù)。9.7排序算法的空間效率取決于
32、算法所占用的_的大小。9.8 下面排序算法的平均時間復(fù)雜度最小的是_。A直接插入排序 B簡單選擇排序 C冒泡排序 D快速排序9.9以下排序方法中，穩(wěn)定的排序方法是_。A. 直接插入排序和冒泡排序 B. 簡單選擇排序和歸并排序 C. 堆排序和快速排序 D. 冒泡排序和快速排序9.11 一組紀錄的關(guān)鍵碼為（46，79，56，38，40，84）則利用快速排序的方法，以第一個記錄為基準得到一次劃分結(jié)果為_。 A. 38，40，46，56，79，84 B. 40，38，46，79，56，84C. 40，38，46，56，79，84 D. 40，38，46，84，56，799.12快速排序方法在_ 情況下
33、最不利于發(fā)揮其長處。 A.要排序得數(shù)據(jù)量太大 B. 要排序得數(shù)據(jù)種含有多個相同值C.要排序的數(shù)據(jù)已基本有序 D. 要排序的數(shù)據(jù)個數(shù)為奇數(shù)9.13 已知序列53，87，12，61，98，17，87，27，63，46，畫出與該序列對應(yīng)的完全二叉樹；判斷該序列是否為堆，如果不是，請調(diào)整為大根（頂）堆。914已知序列27，10，14，55，39，19，84，68，11，23，85，畫出與該序列對應(yīng)的完全二叉樹；判斷該序列是否為堆，如果不是，請調(diào)整為大根（頂）堆。915已知序列20，15，4，18，9，6，25，12，3，22，畫出與該序列對應(yīng)的完全二叉樹；判斷該序列是否為堆，如果不是，請調(diào)整為小根（頂）堆。
數(shù)據(jù)結(jié)構(gòu)習題集答案
