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

2、. 事前分析估算的方法 C. 事后統計的方法 D. 事后分析估算的方法6在對算法的時間復雜度進行估計的時候，下列最佳的時間復雜度是_ _。 A. n2 B. nlogn C. n D. logn 7設使用某算法對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設順序

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

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

7、所指的元素為b，則當前應插入到 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)實現本題功能的函數如下：Lnode *hb(Lnode *pa,Lnode *pb)Lnode *p,*q,*pc; pc=(Lnode*)malloc(sizeof(Lnode); /*建立表c 的頭結點pc*/ p=pc; /*p指向C表頭結點*/ while(pa!=NULL&&pb!=NULL) q=(Lnode*)malloc(sizeof(Lnode); /*建立新結點q*/ if(pb

8、->data<pa->data) /*比較A、B表中當前結點的數據域值的大小*/ q->data=pb->data; /*B中結點值小，將其值賦給q的數據域*/ pb=pb->next; /*B中指針pb后移*/ else q->data=pa->data; /*相反，將A結點值賦給q的數據域*/ pa=pa->next; /*A中指針pa后移*/ p->next=q; /*將q接在p的后面*/p=q; /*p始終指向C表當前尾結點*/while(pa!=NULL) /*若表A比B長，將A余下的結點鏈在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余下的結點鏈在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*/pc=p->next; /*改變指針狀態，使pc指向p的后繼*/free(p); /*釋放p空間

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

12、元素，再加入兩個元素后，rear和front的值分別為 。A. 1和5 B. 2和4 C. 4和2 D. 5和18. 判定一個循環隊列 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.判定一個循環隊列 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在求表達式值的算符優先算法中使用的主要數據結構是 。2設有一個空棧，現輸入序列為1，2，3，4，5。經過push，push，pop，push，pop，push，pop，push后，輸出序列是 。3僅允許在同一端進行插入和刪除的線性表稱為 。7在順序棧s中，棧為空的條件是 ，棧為滿的條件是_。4用S表示入棧操作，X表示出棧操作，若元素入棧順序為1234，為了得到1342出棧順序，相應的S、X操作串為 。5

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

15、。35178421011001余數結果：10011 圖3-1 十進制數轉換成二進制數的過程由題意可知，我們可以用一個棧來保存所有的余數，當商為0時則讓棧里的所有余數出棧則可以得到正確的二進制數，算法可描述如下：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串是一種特殊的線性表，其特殊性體現在 。A. 可以順序存儲 B. 數據元素是一個字符 C. 可以鏈接存儲 D. 數據元素可以是多個字符 2設有兩個串p和q，求q在p中首次出現的位置的運算稱作 。 A. 連接 B. 模式匹配 C. 求子串 D. 求串長3串是一個 B 的序列。A. 不少于一個字母

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

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

19、 B. 197 C. 196 D. 1954稀疏矩陣一般的壓縮存儲方法有兩種，即 。 A. 二維數組和三維數組 B. 三元組和散列C. 三元組和十字鏈表 D. 散列和十字鏈表5. 一個非空廣義表的表頭_ _。 A. 不可能是子表 B. 只能是子表 C. 只能是原子 D. 可以是原子或子表6. 設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的內存單元中，已知每個元素占四個單元，則元素A7,5的地址為 。 2二維數組A0.9,0.19采用行序為主方式存儲，每個元素占一個存儲單元，并且元素A0,0的存儲地址是200，則元素A6,12的地址是 。 3二維數組A10.20,5.10采用行序為主方式存儲，每個元素占4個存儲單元，并且元素A10,5的存儲地址是1000，則元素A18,9的地址是 。4有一個10階對

21、稱矩陣A，采用壓縮存儲方式（以行序為主序存儲，且元素A0,0地址為1），則元素A8,5的地址是 。5設HAEDp為求廣義表p的表頭函數，TAILp為求廣義表p的表尾函數，其中 是函數的符號，給出下列廣義表的運算結果： HEAD(a，b，c)的結果是 。 TAIL(a，b，c)的結果是 。 HEAD(a)，(b)的結果是 。 TAIL(a)，(b)的結果是 。 HEADTAIL(a，b，c)的結果是 。TAILHEAD(a，b)，(c，d)的結果是 。 HEADHEAD(a，b)，(c，d)的結果是 。 TAILTAIL(a，(c，d)的結果是 。 a；(b，c)；(a)；(b)；b；(b)；a

22、；( )1. 11002. 3323. 12084. 42 5. 第6章 樹和二叉樹選擇題1 以下說法錯誤的是 。A.樹形結構的特點是一個結點可以有多個直接前趨B.線性結構中的一個結點至多只有一個直接后繼C.樹形結構可以表達(組織)更復雜的數據D.樹(及一切樹形結構)是一種"分支層次"結構2. 如圖6-2所示的 4 棵二叉樹中， 不是完全二叉樹。圖6-2 4 棵二叉樹3. 以下說法錯誤的是 。A.完全二叉樹上結點之間的父子關系可由它們編號之間的關系來表達B.在三叉鏈表上，二叉樹的求雙親運算很容易實現C.在二叉鏈表上，求根，求左、右孩子等很容易實現D.在二叉鏈表上，求雙親運算

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

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

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

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

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

28、父結點，其左、右孩子。解： （1）該二叉樹如圖 6-9 所示。圖 6-9 1棵二叉樹（2）本題二叉樹的各種遍歷結果如下： 前序遍歷：eadcbjfghi 中序遍歷：abcdjefhgi 后序遍歷：bcjdahigfa （3）c 的父結點為 d，左孩子為 j，沒有右孩子。 2有一份電文中共使用 5 個字符：a、b、c、d、e，它們的出現頻率依次為 4、7、5、2、9，試畫出對應的哈夫曼樹（請按左子樹根結點的權小于等于右子樹根結點的權的次序構造），并求出每個字符的哈夫曼編碼。 解：依題意，本題對應的哈夫曼樹如圖 6-15 所示。各字符對應的哈夫曼編碼如下： a：001 b：10 c：01 d：00

29、0 e：11圖6-15 一棵哈夫曼樹3設給定權集 w=2，3，4，7，8，9，試構造關于 w 的一棵哈夫曼樹，并求其加權路徑長度 WPL。 解：本題的哈夫曼樹如圖 6-16 所示。圖6-16 一棵哈夫曼樹其加權路徑長度 WPL=7×2+8×2+4×3+2×4+3×4+9×2=80 4. 已知一棵二叉樹的中序序列為 cbedahgijf，后序序列為cedbhjigfa，畫出該二叉樹的先序線索二叉樹。解：由后序序列的最后一個結點 a 可推出該二叉樹的樹根為 a，由中序序列可推出 a的左子樹由 cbed 組成，右子樹由 hgijf 組成，又

30、由 cbed 在后序序列中的順序可推出該子樹的根結點為 b，其左子樹只有一個結點 c，右子樹由 ed 組成，顯然這里的 e 是根結點，其右子樹為結點 d，這樣可得到根結點 a 的左子樹的先序序列為：bcde；再依次推出右子樹的先序序列為：fghij。因此該二叉樹如圖 6-17所示。圖 6-17 二叉樹設二叉樹的先序線索鏈表如圖 6-18所示。圖 6-18 二叉樹的先序線索鏈表第7章 圖單項選擇題1在一個圖中，所有頂點的度數之和等于所有邊數的 倍。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 個頂點的無向圖至少應有 條邊才能確保是一個連通圖。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 條邊的無向圖，若采用鄰接表表示，則所有鄰接表中的結點總數是 。 A. e/2 B. e C. 2e D. n+e

32、8已知一有向圖的鄰接表存儲結構如圖 7-2 所示。（1）根據有向圖的深度優先遍歷算法，從頂點 v1 出發，所得到的頂點序列是 。 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）根據有向圖的廣度優先遍歷算法，從頂點 v1 出發，所得到的頂點序列是 。 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一個有向圖的鄰接表存儲結構9. 判定一個有向圖是否存在回路除了可以利用拓撲排序方法外，還可以利

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

34、從第 i 個結點出發的邊的方法是 。6在有向圖的鄰接矩陣上，由第i行可得到第_個結點的出度，而由第j列可得到第_ _個結點的入度。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，采用鄰接矩陣，如何判別下列有關問題：（1） 圖中有多少條邊？（2） 任意兩個頂點i和j是否有邊相連？（3） 任意一個

35、頂點的度是多少？解：鄰接矩陣非零元素個數的總和除以2。當A i,j 0時，表示兩頂點i,j之間有邊相連。計算鄰接矩陣上頂點對應行上非零元素的個數。綜合題1給出如圖 7-4 所示的無向圖G的鄰接矩陣和鄰接表兩種存儲結構。圖7-4 無向圖G解：圖 G 對應的鄰接矩陣和鄰接表兩種存儲結構分別如圖所示。2用廣度優先搜索和深度優先搜索對如圖 7-5 所示的圖 G 進行遍歷（從頂點1出發），給出遍歷序列。解：搜索本題圖的廣度優先搜索的序列為：1，2，3，6，4，5，8，7，深度優先搜索的序列為：1，2，6，4，5，7，8，3。 圖7-5無向圖G3使用普里姆算法構造出如圖 7-6 所示的圖 G 的一棵最小生

36、成樹。 圖7-6無向圖G解：使用普里姆算法構造棵最小生成樹的過程如圖 7-11所示。圖 7-11 普里姆算法構造最小生成樹的過程4使用克魯斯卡爾算法構造出如圖 7-7 所示的圖 G 的一棵最小生成樹。 圖7-7 無向圖G解：使用克魯斯卡爾算法構造棵最小生成樹的過程如圖 7-12所示。圖 7-12 克魯斯卡爾算法構造最小生成樹的過程第8章 查找單項選擇題1.順序查找法適合于存儲結構為 的線性表。 A. 散列存儲 B. 順序存儲或鏈接存儲 C. 壓縮存儲 C. 索引存儲 2.對線性表進行折半查找時，要求線性表的存儲方式是 。A. 順序存儲 B. 鏈接存儲C. 以關鍵字有序排序的順序存儲D. 以關鍵

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

38、(14)=3， addr(38)=5，addr(61)=6，addr(85)=8，其余地址為空，如用線性探測再散列處理沖突，關鍵字為 49 的結點的地址是 。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.在各種查找方法中，平均查找長度與結點個數 n 無關的查法方法是 。 2.二分查找的存儲結構僅限于 。3.在散列存儲中，裝填因子的值越大，則 ；的值越小，則 。 存取元素時發生沖突的可能性就越大 存取元素時發生沖突的可能性就越

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

40、(key) d=( d+j*j) % m d=( d-j*j) % m； j=1，2，. 其計算函數如下： 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 因此：各關鍵字的記錄對應的地址分配如下： 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.設散列表為 T0.12，散列函數為 H（key）= key%13，給定鍵值序列是39，36，28，38，44，15，42，12，06，25，請畫出分別用拉鏈法和線性探查法處理沖突時所構造的散列表，并求出在等概率情況下，這兩種方法查找成功和查找失敗時的平均查找長度。解 用散列函數 H（key）= key% 13計算出鍵值序列的散列地址。并用探查次數表示待查鍵值需對散列表中鍵值比較次數。鍵值序列：39，36，28，38，44，15，42，12，06，25散列地址： 0，10，2，12，5，2，3，12，6，12（1）線性探查法處理沖突用線性探查

43、法處理沖突構造的散列表見表8-1所示。表8-1 用線性探查法處理沖突構造的散列表下標0123456789101112T0.1239122815424406253638查找成功探查次數1312211911查找失敗探查次數98765432112110在等概率的情況下，查找成功的平均查找長度ASL=（1×6+2×2+3×1+9×1）/10=2.2設待查鍵值 k不在散列表中：若 H（k）= k% 13= d，則從 i=d開始順次與 Ti位置的鍵值進行比較，直到遇到空位，才確定其查找失敗，同時累計 k鍵值的比較次數，例如若 k% 13= 0，則必須將 k與 T0、

44、T1、T8中的鍵值進行比較之后，發現 T8為空，比較次數為 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）拉鏈法處理沖突用拉鏈法處理沖突構造的散列表見圖8-2所示。圖8-2 拉鏈法處理沖突構造的散列表在等概率的情況下查找成功的平均查找長度：ASL=（1×7+2×2+3×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