1、第一章知識點：1.基本概念： 數據結構分類、特點等：如線性結構，是數據元素之間存在一種（ 一對一關系）數據元素的概念（數據項）2.時空復雜度1、設有數據結構（D，R），其中D=d1,d2,d3,d4,d5,d6,R=r ,r=(d1,d2),(d2,d3),(d3,d4),(d2,d5),(d3,d5)試按照圖論中的畫法畫出其邏輯結構圖。d1d2d31d5d4d62、稱算法的時間復雜度為O(f(n)，其含義是指算法的執行時間和_【1】_的數量級相同。 3. 計算下面程序段的時間復雜度。 x=0;for(i=1; in; i+) for (j=1; j=(y+1)*(y+1) y+;1. 解：設

2、執行了t(n)次，則(t(n)+1)2=n，推出t(n)=n1/2-1。所以時間復雜度為O（n1/2）.5. 分析下面各程序段的時間復雜度 （1） O(n*m) (2) O(log3n) 1）for (i=0; in; i+)for (j=0; jm; j+)Aij=0; 2） i=1; while(inext=qB. p-next=q-nextC. p=q-nextD. p-next=q-next-next2、在一個頭指針為head的帶頭結點單鏈表中，要向表頭插入一個由指針p指向的結點,則應執行 【4】p-next=head-next; 、 【5】head-next=p 。 4.在雙鏈表中，

3、在指針P所指結點前面插入一個結點S時的語句序列是：S-next=P;S-prior=P-prior;P-prior=S;_ S-prior-next=S _；3. 在雙向鏈表指針p的結點前插入一個指針q的結點操作是（C ）。A. p-Prior=q;q-Next=p;p-Prior-Next=q;q-Prior=p-Prior;B. p-Prior=q;p-Prior-Next=q;q-Next=p;q-Prior=p-Prior;C. q-Next=p;q-Prior=p-Prior;p-Prior-Next=q;p-Prior=q;D. q-Prior=p-Prior;q-Next=p;p

4、-Prior=q;p-Prior-Next=q;4. 已知p結點是某雙向鏈表的中間結點，要刪除p結點的直接后繼結點的語句序列是：DA. p-next-next-prior=p; p-next= p-next-next; q=p-next; free(q);B. q=p-next; p-next= p-next-next; p-next-next-prior=p; free(q);C. q=p-next; p-next-prior=p; p-next= p-next-next; free(q);D. q=p-next; p-next= p-next-next; p-next -prior=p;

5、free(q);5.設r指向單鏈表的最后一個結點，要在最后一個結點之后插入s所指的結點，需執行的三條語句是_ P-next= = NULL _；r=s; r-next=null;。6.在單鏈表中，指針p所指結點為最后一個結點的條件是_Ls= =NULL 、ls=ls-link 。7 對于一個具有n個結點的單鏈表，在已知的結點*p后插入一個新結點的時間復雜度為 O(1) ,在給定值為x的結點后插入一個新結點的時間復雜度為 O(n) _。8. 在順序表中訪問任意一結點的時間復雜度均為 O(1) ，因此順序表也稱為隨機存取 的數據結構。（ A ）1. 在n個結點的順序表中，算法的時間復雜度是O（1）

6、的操作是：（E） 訪問第i個結點（1in）和求第i個結點的直接前驅（2in） （F） 在第i個結點后插入一個新結點（1in）（G） 刪除第i個結點（1in）（H） 將n個結點從小到大排序9、線性鏈表不具有的特點是（ A ）。A隨機訪問 B不必事先估計所需存儲空間大小C插入與刪除時不必移動元素 D所需空間與線性表長度成正比10.若某鏈表最常用的操作是在最后一個結點之后插入一個結點和刪除最后一個結點，則采用( C )存儲方式最節省時間。推薦精選 A.單鏈表B.雙鏈表 C.帶頭結點的雙循環鏈表D.單循環鏈表11.帶頭結點的雙循環鏈表L為空表的條件是_ L-next=L-prior 或 L-next=

7、L _。12. 不帶頭結點的單鏈表head為空的判定條件是 head=NULL 。 13一個帶表頭結點的單循環鏈表，指針P指向鏈的某一個結點，若P-next-next-next = = P，則此鏈表的長度可能是 0或2 。14. 向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動（B ）個元素A. 8 B. 63.5 C. 63 D. 715.對于長度為n的順序表執行刪除操作，則其結點的移動次數（C）A.最少為0，最多為n B.最少為1，最多為nC.最少為0，最多為n-1 D.最少為1，最多為n-116.線性表的長度是線性表所占用的存儲空間的大小。( F )17.雙循環

8、鏈表中，任意一結點的后繼指針均指向其邏輯后繼。( T )18、線性表在 B 情況下適用于使用鏈式結構實現。、需經常修改中的結點值 、需不斷對進行刪除插入 、中含有大量的結點 、中結點結構復雜19若某線性表中最常用的操作是取第i 個元素和找第i個元素的前趨元素，則采用（ ）存儲方式最節省時間。單鏈表 雙鏈表 單向循環 順序表1. 假設線性表 L=(a1,a2,an) 用帶頭結點的單鏈表存儲表示，試編寫算法對其實現就地逆置，即利用原鏈表中每一個結點存儲空間，使得元素的邏輯次序改變為(an, a2,a1)。2試編寫算法，以統計帶頭結點單鏈表的元素個數。3. 設某單鏈表的結點結構為data |next

9、,試編寫算法判斷該鏈表的元素是否是遞增的。4. 已知單鏈表L是一個遞增有序表，試寫一高效算法，刪除表中值大于min且小于max的結點(若表中有這樣的結點)，同時釋放被刪結點的空間，這里min和max是兩個給定的參數。請分析你的算法的時間復雜度。推薦精選第3章 棧和隊列知識點：棧、循環隊列 考點：出入棧操作、棧和隊列特點、循環隊列操作（元素個數、隊頭隊尾指針）、應用 1一個棧的入棧序列是1、2、3、4，若第二個出棧的元素是4，則最后出棧的元素可能是或。2.一個棧的輸入序列為1 2 3 4 5，則下列序列中不可能是棧的輸出序列的是( B ) A. 2 3 4 1 5B. 5 4 1 3 2 C.

10、2 3 1 4 5D. 1 5 4 3 23.在對鏈隊列作出隊操作時，不會改變front指針的值。( T )4.若一個棧的輸入序列為123n，其輸出序列的第一個元素為n，則其輸出序列的每個元素ai一定滿足ai=n-i+1(i=1,2.,n)( T )5. 棧是一種特殊的線性表，允許插入和刪除運算的一端稱為 棧頂 , 不允許插入和刪除運算的一端稱為 棧底 。6、如果入棧序列是1，3，5，97，99，且出棧序列的第一個元素為99，則出棧序列中第30個元素為_41 _。 7有5 個元素，其入棧次序為：A，B，C，D，E，在各種可能的出棧次序中，以元素C，D最先出棧（即C第一個且D第二個出棧）的次序有

11、哪幾個？答：三個：CDEBA，CDBEA，CDBAE8、向順序棧中壓入新元素時，應當（ A ）。 A先移動棧頂指針，再存入元素 B先存入元素，再移動棧頂指針C先后次序無關緊要 D同時進行9.設一個鏈棧的棧頂指針是ls，棧中結點格式為info | link ,棧空的條件是_.如果棧不為空，則退棧操作為p=ls；_ Ls= =NULL 、ls=ls-link._；free(p);。10.如果以鏈表作為棧的存儲結構，則退棧操作時（ ） 必須判別棧是否滿 對棧不作任何判別 必須判別棧是否空 判別棧元素的類型11. 判定一個棧ST（最多元素為m0）為空的條件是BST-top0 ST-top=0 ST-t

12、opm0 ST-top=m0（ D ）12數組用來表示一個循環隊列，為當前隊列頭元素的前一位置，為隊尾元素的位置，假定隊列中元素的個數小于，計算隊列中元素的公式為（）rf; （）（nfr）% n; （）nrf; （）（nrf）% n13. 判定一個隊列QU（最多元素為m0）為滿隊列的條件是AAQU-rear QU-front = = m0 BQU-rear QU-front 1= = m0 CQU-front = = QU-rear DQU-front = = QU-rear+1推薦精選14. 設循環隊列的容量為40 （序號從0到39），現經過一系列的入隊和出隊運算后，有 front=11，r

13、ear=19; front=19，rear=11；問在這兩種情況下，循環隊列中各有元素多少個？答： L=（401911）% 40=8 L=（401119）% 40=3215、假設為循環隊列分配的向量空間為Q20，若隊列的長度和隊頭指針值分別為13和17，則當前尾指針的值為_10_。 16.設數組Data0.m作為循環隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執行出隊操作的語句為（ ）front=front+1 front=(front+1)% mrear=(rear+1)%m front=(front+1)%(m+1) 12. 在按層次遍歷二叉樹的算法中，需要借助的輔助數

14、據結構是（A）A隊列 B棧C線性表 D有序表13. 用鄰接表表示圖進行深度優先遍歷時，通常是采用 C 來實現算法的。A 樹 B. 隊列 C. 棧 D. 圖 17. 簡述以下算法的功能（棧和隊列的元素類型均為int）。void algo3(Queue &Q)Stack S; int d;InitStack(S);while(!QueueEmpty(Q) DeQueue (Q,d); Push(S,d);while(!StackEmpty(S) Pop(S,d); EnQueue (Q,d); 答：該算法的功能是：利用堆棧做輔助，將隊列中的數據元素進行逆置。推薦精選第4章 串知識點：定義、串的基本

15、操作、根據KMP算法原理，分別求出它們的Next函數值作業1.串是任意有限個（ ）符號構成的序列 符號構成的集合字符構成的序列 字符構成的集合2、設有兩個串p和q，求q在p中首次出現的位置的運算稱作：（） 連接 模式匹配 求子串 求串長3、串是一種特殊的線性表，其特殊性體現在： （ ） 可以順序存儲 數據元素是一個字符 可以鏈式存儲 數據元素可以是多個字符 5、 設S=“A;/document/Mary.doc”，則strlen(s)= 20 。6. 設目標T=”abccdcdccbaa”，模式P=“cdcc”，則第 6 次匹配成功。7.設串s1=ABCDEFG，s2=PQRST，函數con(

16、x,y)返回x和y串的連接串，subs(s, i, j)返回串s的從序號i開始的j個字符組成的子串，len(s)返回串s的長度，則con(subs(s1, 2, len(s2), subs(s1, len(s2), 2)的結果串是 BCDEFEF 。8. 設串sl=Data Structures with Java,s2=it，則子串定位函數index(s1,s2)的值為（D）A15 B16 C17 D189. 令t=abcaabcab，根據KMP算法原理，分別求出它們的Next函數值。i123456789串tabcaabcabNext(i)推薦精選第5章 數組和廣義表知識點：二維數組的存儲、

17、特殊矩陣、廣義表作業P31-331. 假設有二維數組A68，每個元素用相鄰的6個字節存儲，存儲器按字節編址。已知A的起始存儲位置（基地址）為1000，則數組A的體積（存儲量）為 288 ；末尾元素A57的第一個字節地址為 1282 ；若按行存儲時，元素A14的第一個字節地址為 1072 ；若按列存儲時，元素A47的第一個字節地址為 1276 。（ ）2. 假設有60行70列的二維數組a160, 170以列序為主序順序存儲，其基地址為1000，每個元素占2個存儲單元，那么第32行第58列的元素a32,58的存儲地址為()。（無第0行第0列元素） ()4454 ()6904 ()7902 ()答案

18、A, B, C均不對3數組A的每個元素占5個單元，將其按行優先次序存儲在起始地址為1000的連續的內存單元中，則元素A，的地址為( A ) A. 1140B. 1145 C. 1120D. 11254.二維數組A1520采用按行為主序的存儲方式，每個元素占4個存儲單元，若A00的存儲地址為300，則A1010的地址為（D）A.700B.1120C.1180D.11405寫出廣義表操作的結果：GetTail【GetHead【GetTail【(a,b),(x,y)】= (y) 。5.取出廣義表A=(x,(a,b,c,d)中原子x的函數是_ head(A)_。7. 下列各三元組表分別表示一個稀疏矩陣

19、，試寫出它們的稀疏矩陣。 ijv7661472183594276537318、設有一個10階的對稱矩陣A1010，采用壓縮存儲方式按行將矩陣中下三角部分的元素存入一維數組B 中，A00存入B0中，則A85在B 中（ C ）位置。A32 B33 C41 D65 推薦精選9、假設有100行200列的二維數組a100200以列序為主序順序存儲，其基地址為10000，每個元素占2個存儲單元，那么第45行第67列的元素a4466的存儲地址為 23288 。10、已知廣義表L=（a），b），（），d），（e，f），（1）寫出廣義表L的頭、尾；（2）計算L的深度；（3）畫出L的頭尾鏈表存儲結構圖。11. 設

20、矩陣A是一個對稱矩陣，為了節省存儲，將其下三角部分（如下圖所示）按行序存放在一維數組B中（注：B下標從0開始），求矩陣中任一元素ai,j(ij)和一維數組B中下標k的對應關系。解：對應關系如下：推薦精選第6章 二叉樹知識點： 樹、二叉樹（完全二叉樹）、森林基本概念（度、），存儲結構，遍歷，轉換，線索1、設F是一個森林，B是由F轉換得到的二叉樹，F中有n個非葉結點，則B中右指針域為空的結點有（ C ）個。An-1 Bn Cn+1 Dn+22 已知一棵度為3的樹有2個度為1的結點，3個度為2的結點，4個度為3的結點，則該樹中有_12_ 個葉子的結點。3 樹有三種常用的存儲結構，即孩子鏈表法、孩子兄

21、弟鏈表法和_雙親表示法。4. 把一棵樹轉換為二叉樹后，這棵二叉樹的形態是 A 。A. 唯一的 B. 有多種C. 有多種，但根結點都沒有左孩子 D. 有多種，但根結點都沒有右孩子5、若一棵二叉樹中度為2的結點數是10，則葉子結點數為 11 個。10、3個結點可構成 2 棵不同形態的樹。5棵不同形態的二叉樹。6.深度為6（根的層次為1）的二叉樹至多有（ ）結點。 64 32 31 637.將含100個結點的完全二叉樹從根這一層開始，每層上從左到右依次對結點編號，根結點的編號為1。編號為49的結點X的雙親編號為（ ）24 25 23 無法確定8.設一棵完全二叉樹具有1000個結點，則此完全二叉樹有5

22、00 個葉子結點；有 499 個度為2的結點，有 1 個度為1的結點。9. 一棵具有個結點的完全二叉樹，它的深度為 9 。10、已知完全二叉樹的第8層有8個結點，則其葉子結點數是68。11. 在完全的二叉樹中，若一個結點沒有 A ，則它必定是葉結點。A. 左子結點 B. 右子結點 C. 左子結點或者沒有右子結點 D. 兄弟12.某二叉樹的先序序列和后序序列正好相同，則該二叉樹一定是( .A )的二叉樹。 A.空或只有一個結點B.高度等于其結點數 C.任一結點無左孩子D.任一結點無右孩子13.在有n個結點的二叉鏈表中，值為非空的鏈域的個數為( A ) A. n-1B. 2n-1 C. n+1D.

23、 2n+114.一棵左右子樹均不空的二叉樹在先序線索化后，其空指針域數為(.B ) A. 0B. 1 C. 2D.不確定15.DFS算法的時間復雜度為( C )推薦精選 A. O(n)B. O(n3) C. O(n2)D. O(n+e)16、有n個葉子結點的哈夫曼（Huffman）樹所具有的結點數為2n-117.判斷線索二叉樹中某結點指針P所指結點有左孩子的條件是_P-ltag=1_。18、二叉樹在線索化后，仍不能有效求解的問題是（D ）。A.先序線索二叉樹中求先序后繼B.中序線索二叉樹中求中序后繼C.中序線索二叉樹中求中序前驅D.后序線索二叉樹中求后序后繼 19、將下圖中的樹用孩子-兄弟鏈表

24、來表示。 （1）畫出該二叉鏈表；（2）對該二叉鏈表進行何種遍歷方式可實現樹的后根遍歷？寫出后根序列。20. 求出下圖的一棵最小生成樹。21. 指出下面函數FS的功能。其中，p指向先序線索二叉樹的某個結點。 typedef enumLINK，THERADflag; typedef char DataType; typedef struct node DataType data; flag ltag，rtag; struct node * lchild， * rchild; BinNode; BinNode * FS(BinNode *p) if(p-ltag=LINK) return p-lch

25、ild; else return p-rchild; 推薦精選函數功能：在先序線索二叉樹中查找某結點的后繼。22. 給定二叉樹的兩種遍歷序列，分別是：中序遍歷序列：DCBGEAHFIJK；后序遍歷序列：DCEGBFHKJIA。（1） 請畫出該樹。（2） 畫出與（1）求得的二叉樹對應的森林。23. 假設用于通信的電文僅由8個字母組成，字母在電文中出現的頻率分別為abcdefgh0.070.190.020.060.320.030.210.10要求：（1） 為這8個字母設計哈夫曼編碼，并畫出哈夫曼樹。（2） 求該哈夫曼樹的帶權路徑長度。24樹的后根遍歷方法是：若樹非空則（1）依據次后根遍歷根的各個子

26、樹，m;（2）訪問根結點。對下圖所示的樹，用后根遍歷方法進行遍歷，請寫出遍歷所得到的結點訪問序列。ABACADAEAFAGAHAIJKA25. 假設一棵二叉樹的先序序列為 EBADCFHGIKJ 和中序序列為 ABCDEFGHIJK。i. 請畫出該樹。ii. 畫出與（1）求得的二叉樹對應的森林。26.已知一樹的雙親表示法如下，其中各兄弟結點是依次出現的，畫出該樹及對應的二叉樹。123456789101112131415dataABCDEFGHIJKLMNOparent011122334456678推薦精選1.計算二叉樹的深度的算法Int deepTree(p) / P為指向二叉樹之根 If(p

27、=NULL) return t; Else If(deepTree(p-Lchild)deepTree(p-Rchild) Return deepTree(p-Lchild)+1; Else Return deepTree(p-Rchild)+1;2、讀程序二叉樹以二叉鏈表作為存儲結構，其定義如下：TypedefstructNodechardata;StructNode*lc,*rc;/*lc,rc分別指向左，右子樹*/BiTNode,*BiTree;Intn=0;二叉樹如右圖，根的地址為root，請給出：（1）下列函數的功能（2）調用語句prek(root,5);輸出結果是什么？Voidpr

28、ek(BiTreeT,intk)if(T&nlc,k);Prek(T-rc,k);N+;printf(“%c”,T-data);3、編寫遞歸算法，計算二叉樹中葉子結點的數目。 4設二叉樹以二叉鏈表為存儲結構，結點結構為lchild |data |rchild 。設計一個算法，求在前根序列中處于第k個位置的結點Bitreptr search(bitreptr t ,int k)if (t!=null) count+;if (count= =k)return (t); else search(t-lchild,k); search(t-rchild,k); 推薦精選 5. 以線索鏈表作為存儲結構，

29、寫出后序線索樹中查找 *p的后序前驅的算法。推薦精選第七章 圖知識點：基本概念（度、完全圖、連通子圖、生成樹、最小生成樹），圖的存儲（鄰接矩陣、鄰接表），圖的遍歷，最小生成樹，拓撲排序，最短路徑，關鍵路徑1 求最短路徑的DIJKSTRA算法的時間復雜度為( C ) A. O(n)B. O(n+e) C. O(n2)D. O(ne)2.有向圖用鄰接矩陣表示后，頂點i的入度等于鄰接矩陣中第i列的非零元個數。( T )3.有向圖的鄰接表和逆鄰接表中的結點數一定相同。( T )4.圖G的拓撲序列唯一，則其弧數必為n-1(其中n為G的頂點數)。( F )5. 在一個圖中，所有頂點的度數之和等于圖的邊數的

30、 C 倍。 A1/2 B. 1 C. 2 D. 4 6. 在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的 B 倍。 A1/2 B. 1 C. 2 D. 4 7. 已知圖的鄰接表如下圖1所示，根據算法，則從頂點0出發按深度優先遍歷的結點序列是DA0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 38有n個頂點的強連通有向圖G至少有 n 條弧。 9、設有向圖有n個頂點和e條邊，采用鄰接表作為其存儲表示，在進行拓撲排序時，總的計算時間為（ B ）。AO（nlog2e） BO（n+e）CO(ne) DO(n2)10、求最短路徑的FLOYD算法的時間復雜度為（D

31、）。A.O(n)B.O(n+e)C.O(n2)D.O(n3)11、若要求一個稀疏圖G的最小生成樹，最好用 A 算法來求解。 A克魯斯卡爾(Kruskal) B. 普里姆(Prim) C迪杰斯特拉（Dijkstra） D. 以上均可，沒有區別12設有一個無向圖G=（V，E）和G=（V，E）如果G為G的生成樹，則下面不正確的說法是（ ）G為G 的子圖 G為G 的邊連通分量推薦精選G為G的極小連通子圖且V=V G為G的一個無環子圖13一個有向圖G中若有弧、和, 則在圖G的拓撲序列中，頂點vi,vj和vk的相對位置為_i,j,k_。14. 有8個結點的有向圖最多有 56 條邊。15. 用普里姆(Pri

32、m)算法求具有n個頂點e條邊的圖的最小生成樹的時間復雜度為 O(n2) ；用克魯斯卡爾(Kruskal)算法的時間復雜度是 O(elog2e) 。（ A ）16用鄰接表表示圖進行廣度優先遍歷時，通常是采用 來實現算法的。(A)隊列 (B). 棧 (C). 樹 (D). 圖 17. 用鄰接表表示圖進行深度優先遍歷時，通常是采用 C 來實現算法的。A 樹 B. 隊列 C. 棧 D. 圖 1、請對下圖的無向帶權圖：（1） 寫出它的鄰接矩陣；（2） 寫出它的鄰接表；（3） 設起點為a，按普里姆算法或克魯斯卡爾算法求其最小生成樹。 2. 已知圖的鄰接矩陣，根據算法，分別求從頂點0出發按深度和廣度優先遍歷

33、的結點序列。解：按深度優先遍歷的結點序列是0134256；按廣度優先遍歷的結點序列是0123465。3. 對于下圖所示的AOE網絡，計算各活動弧的e(ai)和l(aj)的函數值，各事件（頂點）的ve(vi)和vl(vj)函數值，列出各條關鍵路徑。推薦精選v2v4v1v5v3v6162111143361918654 下圖表示一個地區的交通網，頂點表示城市，邊表示連結城市間的公路，邊上的權表示修建公路花費的代價。怎樣選擇能夠溝通每個城市且總造價最省的n-1條公路，畫出所有可能的方案。求最小生成樹，兩種方案5. 已知某有向圖的鄰接矩陣如右圖所示，要求：（1） 確定圖中每個頂點的入/出度；（2） 畫出

34、該圖；（3） 畫出該圖的鄰接表（4） 畫出該圖的逆鄰接表。6 利用Dijkstra算法求圖中從頂點a到其他各頂點間的最短路徑，寫出執行算法過程中各步的狀態。 推薦精選第8章 查找知識點：折半查找過程，堆概念，二叉排序樹，哈希查找，平衡二叉樹。1.對有18個元素的有序表作二分查找，則查找A3的比較序列的下標依次為(D ) A. 1，2，3B. 9，5，2，3 C. 9，5，3D. 9，4，2，32、對表長為900的索引順序表進行分塊查找，假設每一塊的長度均為15，且以順序查找確定塊，則在各記錄的查找概率均相等的情況下，其查找成功的平均查找長度為_38.5_。 3. 在表長為的鏈表中進行線性查找，

35、它的平均查找長度為 ()/ 。 4. 在各種查找方法中，平均查找長度與結點個數n無關的查找方法是 散列查找 。（ ）5在對有6400個記錄的索引順序表進行查找，最理想的塊長為 .(). 64 (). 100 () 80 () log26400 6、在平衡二叉樹中插入一個結點后造成了不平衡，設最低的不平衡點為A，并已知A的左孩子的平衡因子為-1，右孩子的平衡因子為0，則做（B ）型調整以使其平衡。 A. LLB.LRC.RLD.RR7、）假定對有序表：（3，4，5，7，24，30，42，54，63，72，87，95）進行折半查找。（1） 畫出描述折半查找過程的判定樹；（2） 若查找元素54，需依

36、次與哪些元素比較？（3） 若查找元素90，需依次與哪些元素比較？（4） 假定每個元素的查找概率相等，求查找成功時的平均查找長度。8、設哈希（Hash）表的地址范圍為015，哈希函數為：H（Key）Key mod 13。Key為關鍵字，用線性探測法再散列法處理沖突，輸入關鍵字序列： （10，24，32，17，31，30，46，48，41，65，49）造出Hash表，試回答下列問題：（1） 畫出哈希表的示意圖；（2） 若查找關鍵字30，需要依次與哪些關鍵字進行比較？(3) 計算填充因子；(4) 假定每個關鍵字的查找概率相等，求查找成功時的平均查找長度。9.已知長度為12的表：（Jan, Feb,

37、Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）(1) 試按表中元素的順序依次插入一棵初始為空的二叉排序樹，畫出插入完成之后的二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。(2) 按表中元素順序構造一棵平衡二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。10在一棵空的二叉查找樹中依次插入關鍵字序列為12，7，17，11，16，2，13，9，21，4，請畫出所得到的二叉查找樹，并求出其平均查找長度。推薦精選11、有一個40000項的表,要采用等分區間順序查找的索引 (分塊)查找法,問:(1)每塊理想長度是多少?(2)最理

38、想的塊數是多少?(3)計算平均查找長度ASL。(4)若每塊長度為100,計算ASL。12.下面是將鍵值為x 的結點插入到二叉排序樹中的算法，請在劃線處填上適當的內容。typedef struct pnode int key; struct pnode *left, *right; pnode;void searchinsert(int x, pnode t ) /*t為二叉排序樹根結點的指針*if ( )p=malloc(size);p-key=x;p-lchild=null; p-rchild=null;t=p; else if (xkey) searchinsert(x,t-lchild)

39、 else_;13設n個元素的有序表為，為一個給定的值，二分查找算法如下： int binsearch(sqlist R, keytype K) j=1;h=n ;suc=0; while(j=h)&(!suc) mid =(j+h)/2; switch case K=Rmid.key: suc=1; break; case KRmid.key: j=mid+1 if (suc) return(mid); else return(0);將上述算法中劃線語句改為：KRmid.key: h=mid.（1）改動后，算法能否正常工作？請說明原因。（2）若算法不能正常工作，給出一個查找序列和一個出錯情況

40、的查找鍵值；若能正常工作，請給出一個查找序列和查找某個鍵值的比較次數。14. 從空樹起，依次插入關鍵字37，50，42，18，12，56，30，23，構造一棵二叉排序樹。（1） 畫出該二叉排序樹。（2） 畫出從（1）所得樹中刪除關鍵字為37的結點之后的二叉排序樹。推薦精選15. 已知某哈希表的裝載因子小于1，哈希函數H(key)為關鍵字（標識符）的第一個字母在字母表中的序號，處理沖突的方法為線性探測開放定址法。試編寫一個按第一個字母的順序輸出哈希表中所有關鍵字的算法。第九章 排序知識點：堆的判定，排序算法的穩定性，各類排序算法執行過程、復雜性分析，1. 下列關鍵字序列中， 是堆。. 16, 7

41、2, 31, 23, 94, 53 . 94, 23, 31, 72, 16, 53 . 16, 53, 23, 94，31, 72 . 16, 23, 53, 31, 94, 722 以下排序方法中穩定的是：. 希爾排序 . 快速排序 . 歸并排序 . 堆排序3.設表中元素的初始狀態是按鍵值遞增的，分別用堆排序、快速排序、冒泡排序和歸并排序方法對其進行（按遞增排序），冒泡排序最省時間，快速排序最費時間。4. 堆是一個鍵值序列k1,k2, kn,對i=1,2,|_n/2_|,滿足( )kik2ik2i+1 kik2i+1k2ikik2i且kik2i+1(2i+1n) kik2i 或kik2i+1(2i+1n) 5、堆是一種 排序。. 插入 .選擇 . 交換 . 歸并6、若一組記錄的排序碼為（46, 79, 56, 38, 40, 84），則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結果為. 38, 40, 46, 56, 79, 84 . 40, 38, 46 , 79, 56, 84. 40, 38，46, 56, 79, 84 . 40, 38, 46, 84, 56, 797、設要將序列（