數(shù)據(jù)結(jié)構(gòu)專升本模擬題及參考答案匯總

1、、單項選擇題1. 從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為(A.動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)C.線性結(jié)構(gòu)、非線性結(jié)構(gòu)2. 鏈表不具有的特點是(A插入、刪除不需要移動元素C.不必事先估計存儲空間D .3. 下面程序段的時間復雜度的量級為For(i=1;i<=n;i+)For(j=1;j<=I;j+)For(k=1;k<=j;k+)X=x+1;A O(1)C O(n2)4. 在一個帶頭結(jié)點的雙向循環(huán)鏈表中，個指針域的值。A2C4作業(yè)題(一)兩大類。順序結(jié)構(gòu)、鏈式結(jié)構(gòu)初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)B .可隨機訪問任一 元素所需空間與線性長度成正比)。 O(n) O(n3)若要在 p 所指向的結(jié)點之前插入一個新結(jié)點，

2、 則需要相繼修改 ()365、一個順序存儲線性表的第一個元素的存儲地址是90，每個元素的長度是 2，則第 6 個元素的存儲地址是()。A98 100C102 1066、判定一個棧s (最多元素為 m0為空的條件是()。A. s- top! =0s- top= =0C. s- top! =m0s-top= =m07、循環(huán)隊列用數(shù)組 Am(下標從0到m-1)存放其元素值，已知其頭尾指針分別是front和 rear ，則當前隊列中的元素個數(shù)是()。A.( rear-front+m) %m. rear-front+1C. rear-front-1D. rear-front設(shè)有兩個串S1與S2,求串S2

3、在S1中首次出現(xiàn)位置的運算稱作(A.連接B求子串C.模式匹配D判子串設(shè)串S1='ABCDEFG； S2='PQRST'，函數(shù)con (x, y)返回x和y串的連接串,從 序 號 i 的 字 符 開 始 的 j 個 字 符 組 成 的 子 串 ， len(s) 返 con(subs(S1,2,len(S2),subs(S1,len(S2),2)的結(jié)果是( )。8、9、)。subs(s,i,j) 回 串 S返回串 S 的 的 長 度 ， 則A. BCDEFB . BCDEFGC. BCPQRST.BCDEFEF10、數(shù)組常用的兩種基本操作是（A.建立與查找C.插入與索引二、

4、填空題1. 所謂稀疏矩陣指的是 刪除與查找查找與修改且分布沒有規(guī)律。2. 隊列是的線性表，其運算遵循的原則。3.空格串是4.簡單選擇排序和起泡排序中比較次數(shù)與序列初態(tài)無關(guān)的算法有5、設(shè)圖G有n個頂點和e條邊，則對用鄰接矩陣表示的圖進行深度或廣度優(yōu)先搜索遍歷時的時間復雜度，而對用鄰接表表示的圖進行深度或廣度優(yōu)先搜索遍歷時的時間復雜度為，圖的深度或廣度優(yōu)先搜索遍歷時的空間復雜度均為6、一個圖的三、算法設(shè)二叉樹采用二叉鏈表結(jié)構(gòu)，試設(shè)計一個算法統(tǒng)計給定二叉樹中的一度結(jié)點數(shù)目。四、應用題表示法是唯一的，而表示法是不唯一的。1對關(guān)鍵字無序序列（36, 25, 48, 12, 65, 43, 20, 58）

5、進行直接選擇排序,請寫出每一趟排序的結(jié)果。（10 分）2、對無向帶權(quán)圖，用克魯斯卡爾算法構(gòu)造最小生成樹。（10 分）3、已知記錄關(guān)鍵字集合為（53,17,19,61,98,75,79,63,46,49要求散列到地址區(qū)間（100,101,102,103,104,105,106,107,108,109）內(nèi)，若產(chǎn)生沖突用開型尋址法的線性探測法解決。要求（設(shè)寫出選用的散列函數(shù)；形成的散列表；計算出查找成功時平均查找長度與查找不成功的平均查找長度。等概率情況）4、設(shè)被查找文件有4095 個記錄，對每個記錄查找記錄概率相等，若采用順序查找，成功查找平均比較次數(shù)為多少？作業(yè)題（二）、單項選擇題1. 有六個元

6、素 6，5， 4， 3，2，1 的順序進棧，問下列哪一個不是合法的出棧序列？（A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1 D. 2 3 4 1 5 62. 棧和隊都是（A.順序存儲的線性結(jié)構(gòu)B.鏈式存儲的非線性結(jié)構(gòu)C. 限制存取點的線性結(jié)構(gòu)D.限制存取點的非線性結(jié)構(gòu)3、順序查找法適合于存儲結(jié)構(gòu)為（）的線形表。A.散列存儲B. 順序存儲或鏈接存儲C. 壓縮存儲D.索引存儲4、分別以下列序列構(gòu)造二叉排序樹，與用其它三個序列所構(gòu)造的結(jié)果不同的是A . ( 100， 80， 90， 60， 120 ，110，130)B.100，120，110，130，80，

7、60 ， 90 )C. ( 100， 60， 80， 90， 120 ，110，130)D.(100 ，80， 60 ，90，120 ， 130， 110)5、折半查找的平均比較次數(shù)為（）。A. nB.n/2C. log2nD.log2(n+1)6、當在一個有序的順序存儲表上查找一個數(shù)據(jù)時，即可用折半查找，也可用順序查找，但前者比后者的查找速度（A. 必定快B.不一定C.在大部分情況下要快D. 取決于表遞增還是遞減7、已知一有向圖的鄰接表存儲結(jié)構(gòu)如下圖如示。根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點v1 出發(fā)，所得到的頂點序列是（）。A. v1, v2, v3, v5, v4C. v1, v3, v

8、4, v5, v212A34ASB. v1, v2, v3, v4 , v5D. v1, v4, v3, v5 , v2B.鏈式存儲D.散列存儲A. sB.s-1C. s+1D.10、如圖所示，給出由7個頂點組成的無向圖。從頂點A出發(fā)，對它進行深度優(yōu)先搜索得到的頂點序列是A. A E C D B F GB. A G B F D E CC. A C E D B G FD. A B D G F E C二、填空題1.設(shè)no為哈夫曼樹的葉子結(jié)點數(shù)目則該哈夫曼樹共有個結(jié)點。2.有數(shù)據(jù) WG=7 19, 2, 6, 32,3, 21, 10，則所建 Huffman樹的樹高是，帶權(quán)路徑長度WPL8、為了方便

9、地對圖狀結(jié)構(gòu)的數(shù)據(jù)進行存取操作，則其中數(shù)據(jù)存儲結(jié)構(gòu)宜采用（A.順序存儲C.索引存儲9、在一個具有n個頂點的有向圖中，若所有頂點的出度之和為S,則所有頂點的入度之和為（為。3、設(shè)一棵完全二叉樹葉子結(jié)點數(shù)為4、采用分塊查找時，若線性表中共有k,最后一層結(jié)點數(shù)2,則該二叉樹的高度為625個元素，查找每個元素的概率相同，假設(shè)采用順序查找來確定結(jié)點所在的塊時，每塊應分 _個結(jié)點最佳。5、 設(shè)G為具有N個頂點的無向連通圖，貝y G中至少有條邊。6、哈夫曼樹（Huffman Tree ）又稱。它是n個帶權(quán)葉子結(jié)點構(gòu)成的所有二叉樹中，帶權(quán)路徑長度WPL。;依次先序遍歷樹7、樹的先序遍歷過程如下：若樹為空，則進

10、行空操作；若樹非空，則訪問樹的 的三、應用題2、對關(guān)鍵字序列10, 6, 3, 2, 5, 4，構(gòu)造一棵平衡二叉（排序）樹并畫圖（要求畫出建樹過程）3、設(shè)有一個有序文件，其中各記錄的關(guān)鍵字為（1 , 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 , 13, 14, 15）,當用折半查找算法查找關(guān)鍵字為3, 8, 19時，其比較次數(shù)分別為多少?4、對有五個結(jié)點 A,B, C, D, E的圖的鄰接矩陣,01003010"300CC306002030100贋5010(1).畫出邏輯圖（2）.畫出圖的十字鏈表存儲;（3）.基于鄰接矩陣寫出圖的深度、廣度優(yōu)先遍歷序列;（

11、4）.計算圖的關(guān)鍵路徑。作業(yè)題（三）一、單項選擇題1 .串的長度是指（A.串中所含不同字母的個數(shù)B .串中所含非空格字符的個數(shù)C.串中所含不同字符的個數(shù)D .串中所含字符的個數(shù)2. 設(shè)有數(shù)組Ai,j，數(shù)組的每個元素長度為3字節(jié)，i的值為1到8 , j的值為1到10,數(shù)組從內(nèi)存首地址BA開始順序存放，當用以列為主存放時,元素 A5, 8的存儲首地址為（）。A. BA+141 B. BA+180 C. BA+222D. BA+2253. 算法分析的兩個主要方面是（A.空間復雜性和時間復雜性.正確性和簡明性C.可讀性和文檔性.數(shù)據(jù)復雜性和程序復雜性4. 算法分析的目的是（A.找出數(shù)據(jù)結(jié)構(gòu)的合理性.研

12、究算法中的輸入和輸出的關(guān)系c.分析算法的效率以求改進.分析算法的易懂性和文檔性5. 下面程序段的時間復雜性的量極為Int fun (i nt n) int i=1,s=1;While(s <n)S+= +I;Return I;.O(lbn).O()A. O(n/2)C. 0(n)6.線性表是(A. 個有限序列,可以為空.一個有限序列，不能為空7.C. 一個無限序列,可以為空 一個無限序列，不能為空帶頭結(jié)點的單鏈表L為空的判定條件是(A. L= =NULL.L-next= =NULLC. L-next= =L.I_! =NULL8.在一個長度為n的線性表中，刪除值為x的元素時需要比較元素和

13、移動元素的總次數(shù)為(A. (n+1) /2.n/2C. n.n+19.一個順序存儲線性表的第一個元素的存儲地址是90,每個元素的長度是2,則第6個元素的存儲地址A . 98.100C. 102.10610.如果某鏈表中最常用的操作是取第i個結(jié)點及其前驅(qū)，則采用(。存儲方式最節(jié)省時間。A.單鏈表.雙向鏈表C .單循環(huán)鏈表二、填空題1.高度為2的二叉樹的結(jié)點數(shù)至少有.順序表個，高度為3的二叉樹的結(jié)點數(shù)至少有個。2.在順序表(8,11,15,19,25,26,30,33,42,48,50。中，用折半查找關(guān)鍵字值 20,需做的關(guān)鍵字比較次數(shù) 為3. 在有n個頂點的無向圖中，每個頂點的度最大可達4. 已

14、知廣義表 A= (a, b, c), ( d, e, f),則廣義表運算 head (tail (tail(A) =。5. 數(shù)組(Array )是n(n> 1)個的有序組合，數(shù)組中的數(shù)據(jù)是按順序存儲在一塊 存儲單元中。6. 采用順序存儲結(jié)構(gòu)表示三元組表( Triple Table ),來實現(xiàn)對稀疏矩陣的一種壓縮存儲形式，就稱7.為，簡稱表。m x n的矩陣變成另外一個nx m的矩陣，同時.運算是矩陣運算中最基本的一項，它是將一個使原來矩陣中元素的行和列的位置互換而值保持不變。三、應用題1對于下圖所示的二叉樹，畫出二叉鏈表存儲結(jié)構(gòu)圖。2、請畫出下圖所示的樹所對應的二叉樹。3.已知一個無向圖

15、如下圖所示，要求分別用Prim 和 Kruskal算法生成最小樹（假設(shè)以為起點，試畫出構(gòu)造過程）。4.已知完全二叉樹的第 8層有8個結(jié)點,則其葉子結(jié)點是多少?5.畫出如圖所示中樹的二叉樹的表示形式。AC作業(yè)題（四）1.2.3.、單項選擇題將兩個各有n個元素的有序表歸并成一個有序表，其最少得比較次數(shù)是（A. nC. 2n.2n-1.n-1一個有n個頂點的無向連通圖，它所包含的連通分量個數(shù)為（A. 0C. n數(shù)據(jù)文件的基本操作中最重要的操作是（A.插入C.修改B.D.B.D.n+1刪除檢索2.3.4.4.對關(guān)鍵碼序列 28, 16, 32, 12, 60, 2,5, 72快速排序，從小到大一次劃分

16、結(jié)果為（A.(2,5,12,16)26(60,32,72)B. (5,16,2,12)28(60,32,72)C.(2,16,12,5)28(60,32,72)D. (5,16,2,12)28(32,60,72)5.如果只想得到1000個元素組成的序列中第5個最小元素之前的部分排序的序列，用（）方法最快。A.堆排序B.快速排序C.插入排序D.歸并排序6.算法分析的目的是（A.找出數(shù)據(jù)結(jié)構(gòu)的合理性.研究算法中的輸入和輸出的關(guān)系C.分析算法的效率以求改進.分析算法的易懂性和文檔性7.二叉樹的第I層上最多含有結(jié)點數(shù)為（II-1A. 2 B . 2-1 C . 2I-1D . 2I -1循環(huán)隊列存儲在

17、數(shù)組 A中，長度為m則入隊時的操作為（A. rear=rear+1B. rear=(rear+1) mod (m-1)C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1)9.廣義表滿足Head（A）=Tail（A），則A為（A.()(0)C. （0,（）10.在一棵度為3的樹中，度為3的結(jié)點數(shù)為2個,（0 , （） , 0）度為2的結(jié)點數(shù)為1個，度為1的結(jié)點數(shù)為2個，則度為0的結(jié)點數(shù)為（。個。C. 5二、填空題1.在一個循環(huán)隊列中，隊首指針指向隊首元素的 數(shù)組中每一個數(shù)據(jù)通常稱為 ,一個圖的表示法是唯一的，而 _用下標區(qū)分， 表示法是不唯一的。其中下標

18、的個數(shù)由數(shù)組的決定。個,5.在一個10階的B-樹上，每個數(shù)根結(jié)點中所含的關(guān)鍵字數(shù)目最多允許 最少允許對關(guān)鍵字序列（52, 80, 63, 44, 48, 91）進行一趟快速排序之后的得到結(jié)果為10.高度為 1 的平衡二叉樹的結(jié)點數(shù)至少有個，高度為 2 的平衡二叉樹的結(jié)點數(shù)至少有個。三 判斷1. 順序存儲結(jié)構(gòu)屬于靜態(tài)結(jié)構(gòu)，鏈式結(jié)構(gòu)屬于動態(tài)結(jié)構(gòu)。2. 即使對不含相同元素的同一輸入序列進行兩組不同的、合法的入棧和出棧組合操作， 所得的輸出序列也一定相同。3. 帶權(quán)無向圖的最小生成樹必是唯一的。 （4. B-樹和B+樹都可用于文件的索引結(jié)構(gòu)。（5. 在用堆排序算法排序時，如果要進行增序排序， 四、應用

19、題則需要采用"大根堆"。（ ）1.模式串p="abaabcac"的next函數(shù)值序列為多少?2. 設(shè)二維數(shù)組 A56 的每個元素占 4個字節(jié)，已知 LOC（a0,0） =1000， A 共占多少個字節(jié)? A 的終端結(jié) 點a4,5的起始地址為多少？按行和按列優(yōu)先存儲時，a2,5的起始地址分別為多少？3.設(shè)a,b,c,d,e五個字符的編碼分別為1,2,3,4,5,并設(shè)標識符依以下次序出現(xiàn):要求用哈希（Hash）方法將它們存入具有10個位置的表中。ac,bd,aa,be,ab,ad,cd,bc,ae,ce。1）將上述關(guān)鍵字（標識符）構(gòu)造一個哈希函數(shù)，使得發(fā)生沖

20、突盡可能地少；2）線性探測再散列法解決沖突。寫出上述各關(guān)鍵字在表中位置。4. 給定一個關(guān)鍵字序列 24，19，32，43，38，6，13，22，請寫出快速排序第一趟的結(jié)果；堆排序時所建的初始堆；歸并排序的全過程。然后回答上述三中排序方法中那一種方法使用的輔助空間最少?在最壞情況下那種方法的時間復雜度最差?作業(yè)題（五）一、單項選擇題1. 一組記錄的關(guān)鍵碼為（46, 79, 56, 38, 40,84）,則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結(jié)果為（A. (38,40,46,56,79,84)B.(40,38,46,79,56,84)C. (40,38,46,56,79,84)廣義

21、表 A=(a,b,(c,d),(e,(f,g),D.（40,38,46,84,56,79）則下面式子的值為 （GetHead(GetTail(GetHead(GetTail(GetTail(A)A. (g) B. (d) C. c D. d3.對于有n個結(jié)點的二叉樹，其高度為（A. nlog 2n B . log 2nC . log 2n_+1不確定4.如圖所示，給出由7個頂點組成的無向圖。從頂點1出發(fā)，對它進行深度優(yōu)先搜索得到的頂點序列是B. 1 3 4 7 6 2 5C.D. 1 2 4 7 6 5 35.采用鄰接表存儲的圖，其深度優(yōu)先遍歷類似于二叉樹的（A.中序遍歷B.先序遍歷C.后序遍

22、歷D.按層次遍歷6.已 知 有 向 圖 G=（V,E）中 V=V 1,V2,V3,V4,V5,V6,V7E=<V 1,V2><V1,V3><V1,V4><V2,V5><V3,V5><V3,V6><V4,V6><V5,V7><V6,V7>,G 的拓撲 序列是C.7.V1,V3,V4,V6,V2,V5,V7V1,V3,V4,V5,V2,V6,V7B. V1,V3,V2,V6,V4,V5,V7D. V1,V2,V5,V3,V4,V6,V7順序查找法適用于查找順序存儲或鏈式存儲的線性表，平均比較

23、次數(shù)為（）。在此假定N為線性表中結(jié)點數(shù)，且每次查找都是成功的。N+1B. 2log2NC.log2ND. NF面關(guān)于m階B樹說法正確的是（每個結(jié)點至少有兩棵非空子樹;樹中每個結(jié)點至多有 m 1個關(guān)鍵字;所有葉子在同一層上;當插入一個數(shù)據(jù)項引起 B樹結(jié)點分裂后，樹長高一層。A .B.C.D.9.已知一個線性表（38, 25, 74,63, 52, 48），假定采用h（k）=k%7計算Hash地址進行散列存儲，若利用鏈地址法處理沖突，則在該Hash表上進行查找的平均查找長度為（A. 1.0B. 7/6C. 4/3D. 3/210.在排序算法的實施過程中，使用輔助存儲空間為0（ 1）的有（A .簡單

24、排序法B.快速排序法D.基數(shù)排序法C.歸并排序法二、填空題1. n （n大于1）個結(jié)點的各棵樹中，其中深度最大的那棵樹的深度是 個非葉子結(jié)點。n,它共有個葉子結(jié)點和2. 設(shè)一棵后序線索樹的高是50,結(jié)點x是樹中的一個結(jié)點，其雙親是結(jié)點y,y的右子樹咼度是60, x是y的左孩子。則確定 x的后繼最多需經(jīng)過中間結(jié)點（不含后繼及x本身）個關(guān)鍵字。3. 高度為2 （第2層為葉子）的3階B-樹中，最多有4. 分別采用堆排序，快速排序，冒泡排序和歸并排序，對初態(tài)為無序的表，則平均情況下最省時間的是算法。5. 簡單選擇排序和起泡排序中比較次數(shù)與序列初態(tài)無關(guān)的算法有6.串的鏈式存儲結(jié)構(gòu)是將存儲區(qū)域分成一系列大

25、小相同的結(jié)點,每個結(jié)點有兩個域域和域。其中三.判斷域用于用于存放數(shù)據(jù),域用于存放下一個結(jié)點的指針1. 順序存儲的線性表可以隨機存取。2. 即使對不含相同元素的同一輸入序列進行兩組不同的、合法的入棧和出棧組合操作，所得的輸出序列也一定相同。3.十字鏈表是無向圖的一種存儲結(jié)構(gòu)。（）4.折半查找方法適用于排列連續(xù)順序文件的查找。5.在執(zhí)行某個排序算法過程中，出現(xiàn)了排序碼朝著最終排序序列位置相反方向移動，則該算法是不穩(wěn)定的。()四、應用題1. 用十字鏈表表示一個有k個非零元素的m x n的稀疏矩陣，則其總的結(jié)點數(shù)為多少?2. G=(V,E)是一個帶有權(quán)的連通圖,則:(1).請回答什么是G的最小生成樹;

26、(2). G為下圖所示，請找出G的所有最小生成樹。3. 請分別敘述在一個連續(xù)順序文件中采用順序查找法，折半查找法和分塊查找法查找一個記錄，該文 件中記錄應該滿足什么條件?4.設(shè)待排序文件之排序碼為(88, 33, 22, 55, 99, 11 , 66),采用順序存儲。請用直接選擇排序算法 對上述文件進行排序，用圖示說明排序過程。作業(yè)題一參考答案: 一、單項選擇題 1、C 2、B 3、D 4、C 5、B 6、B 7、A 8、C 9、D 10、D二、填空題1、非零元很少,先進先出(或2、操作受限(或限定僅在表尾進行插入和限定僅在表頭進行刪除操作或限制存取點或特殊) 后進后出)3、簡單選擇排序4、

27、0(n2), 0(e), 0(n)5、鄰陣矩陣，鄰接表三、算法答: int count = 0;void on echild ( Btree t) if ( t!=NULL) on echild ( t->lchild );on echild ( t->rchild );if ( t->lchild!=NULL && (t->rchild!=NULL | t->lchild!=NULL && t->rchild=NULL )coun t+;四、應用題 1、 答:(0)33t25<012 t65432053(1)12吟43

28、36es4320 t53122043 t36654325 t5312202536654348531220253665t43 t48531220253643ES5 t48 +531220253643143J3553 t(T)122025304343L581es2、 答:散列地址10010110210310410510610710S109關(guān)鍵字98637917531961754649比較次數(shù)111113510由于地址空間為 10,且從100開始，故散列函數(shù)選為 H （key） =key%7+100。3、答:用線性探測再散列解決沖突，ASLsucc=27/104、答：成功查找平均比較查找長度為：（n

29、+1） /nlog2 （ n+1）-1。作業(yè)題二參考答案:一、單項選擇題1、C 2、C 3、B 4、C 5、D6、C 7、C 8、B 9、A 10、C二填空題1、2n 0-12、6, 2613、flog 2k 平14、255、N-16、最優(yōu)二叉樹，最小的二叉樹7、根結(jié)點，各子樹三、應用題1、 答：不唯一，型對即可此樹的帶權(quán)路徑長度WPL =9*1+6*2+4*3+(1+2)*4=452、答:插入10CD插入6CD插入3調(diào)整插入2(6)插入5(7)插入(8)42co3、答：當關(guān)鍵字為3時，比較次數(shù)為4;當關(guān)鍵字為8時，比較次數(shù)為1 ；當關(guān)鍵字為19時,查找不成功;(2)略(3)深度優(yōu)先遍歷序列:

30、ABCD曠度優(yōu)先遍歷序列： ABCE( 4 )關(guān)鍵路徑 A-B(長 100)作業(yè)題三參考答案:一、單項選擇題 1、D 2、B 3、A 4、C 5、D 6、A 7、B 8、C 9、B 10、D 二、填空題 1、2、3、n-14、e5、相同類型數(shù)據(jù)，地址連續(xù)6. 三元組順序表，三元組7. 矩陣轉(zhuǎn)置 三、應用題 1、答:二叉鏈表AA AA I(2H|a II a| A3. 答:Prim算法構(gòu)造最小生成樹的步驟如24題所示，為節(jié)省篇幅，這里僅用Kruskal算法,構(gòu)造最小生成樹過程如下：(下圖也可選(2,4)代替(3,4),(5,6)代替(1,5)4.答：由完全二叉樹的定義可知,除最后一層外，其他各層

31、的結(jié)點是滿的。設(shè)該完全二叉樹有d層，則除。這里第8層有最后一層外各層的結(jié)點個數(shù)分別為：1, 2, 4, 8, 16, 32,，即第i層的結(jié)點個數(shù)為2i-1 8個結(jié)點，顯然第8/層是最后的一層，那么第 7層的結(jié)點個數(shù)為27-1=64個，其中的4個結(jié)點有8個葉子結(jié)點,余下的為葉子結(jié)點，個數(shù)為64-4=60 ,所以該完全二叉樹的葉子結(jié)點個數(shù)為60+8=68個。5.答:對應的二叉樹形式如圖所示:作業(yè)題四參考答案:一、單項選擇題1. A 2. B 3. D4.B 5.6、C 7、C 8、C 9、B 10、二、填空題1.答：前一個位置2.答：數(shù)組元素，數(shù)組元素，維數(shù)3.答：鄰陣矩陣，鄰接表4.答：9, 4

32、答：48 44 52 64 80 911 , 2三.判斷5.6、1.2.答：X3.答：X答：V答：V四、應用題4.5.1.答：模式P的next函數(shù)值如下:丈件d）鏑輯th）現(xiàn)宙jifiA d） 幅皿 工具 現(xiàn)心 口俎）S助 :倒譯匡英中旦日中出中英困取消設(shè)gfl _«l I a I I EJEl I JBl 涉 D *2 4-4 1 i4fii ME 百簡述一個字荷串中子串的枸威.智:一個字荷串中任慝連乘化宇符組成的子序測稱為字精串子串?？沾涂崭翊泻螀^(qū)別亍字符串中空格苻有何意義？空串在串的址理中有何作用?巻:不含任何字符的電魅菱空串甚雖檢廈為零i僅含有空格字符曲齟訓串-它的長度

33、為申空格苻的個數(shù)?？崭褴拊谧址锌捎脕矸指粢话愕淖趾墒褂诼勛x和識別-空格苻會 占用有串長.空串在處理過程中可用于作対任S字符串的子串I 煮基雖曲長度小于一個常數(shù)，則采用何聊存循方式最節(jié)省空間？答，采用順序串最節(jié)省空間，因為順序串惡硼比，喬需要指怦罐。模式串p="共勰"的next圃數(shù)值序列対多少？客 模式口的next國數(shù)值如下ji0L模式串，abneslE-L0算袪設(shè)計題（9+4）5 3 4 5 a a b C0 112采閘匝停結(jié)構(gòu)存儲帶S,騙寫一個藺教刪除3中第iJt宇符開始的j個字瓶智；蚯1顯 * .Uj（31 ring * 5. Lal t i.tii Dtj.nl k；ifIcn）Ui q m IJ 申 _ I_a館s* -f gjsmof)- 、 o 匕|風舊闔左I* M r i ” = 兩 S 4兇益 押五第型21心3/Efte. 5. zS米宙爵傍-J數(shù)老蕪杓2.答：A共120個字節(jié)。6行刃甜一 ：丁中