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

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

2、繼修改() 個指針域的值。A. 2B 3C4D65、一個順序存儲線性表的第一個元素的存儲地址是90,每個元素的長度是2,則第6個元素的存儲地址 是()。A. 98B 100C. 102D. 1066、判泄一個棧s (最多元素為為空的條件是()。A. s-) top! =0B s-> top= =0C s-> top! =m0D s-) top= =m07、循環(huán)隊列用數(shù)組Am(下標從0到m-1)存放英元素值，已知其頭尾指針分別是front和rear,則當 前隊列中的元素個數(shù)是()。A. (reafront+m) %mB rear-front+1C rear-front-1D rear

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

4、、填空題1.所謂稀疏知陣指的是且分布沒有規(guī)律,>2.隊列是的線性表，其運算遵循的原則。3. 空格串是o4. 簡單選擇排序和起泡排序中比較次數(shù)與序列初態(tài)無關(guān)的算法有o5、設(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,

5、 58）進行直接選擇排序，請寫岀每一趟排序的結(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）,若產(chǎn)生沖突用開型尋址法的線性探測法解決。要求寫出 選用的散列函數(shù)：形成的散列表；計算出查找成功時平均查找長度與查找不成功的平均查找長度。（設(shè)等 概率情況）4、設(shè)被查找文件有4095個記錄，對每個記錄査找記錄概率相等，若釆用順序査找，成功查找平均比較次 數(shù)為多少？作業(yè)題（二）、單項選擇題

6、1. 有六個元素6, 5, 4, 3, 2, 1的順序進棧，問下列哪一個不是合法的出棧序列？（）A. 54 3 6 122.棧和隊都是（B. 4 5 3 1 2 6 C 3 46 5 2 1 D 2 3 4 1 5 6)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,

7、 130, 80, 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. Iog2(n+1)6、當在一個有序的順序存儲表上查找一個數(shù)據(jù)時，即可用折半査找，也可用順序査找，但前者比后者的查找速度（）A.必建快B.不一定C.在大部分情況下要快D.取決于表遞增還是遞減7、已知一有向圖的鄰接表存儲結(jié)構(gòu)如下圖如示。根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點W出發(fā)，所得到的頂點序列是（ ）oB. v1, v2, v3, v4, v5C v3, v4&

8、#187; v5, v2D v1, v4, v3, v5, v2A. v1, v2, v3, v5, v48、為了方便地對圖狀結(jié)構(gòu)的數(shù)據(jù)進行存取操作，則其中數(shù)據(jù)存儲結(jié)構(gòu)宜采用（）。A.順序存儲B.鏈式存儲C.索引存儲D.散列存儲9、在一個具有n個頂點的有向圖中，若所有頂點的出度之和為s,則所有頂點的入度之和為（）。A. sB. s-1D. nA. AECDBFGC ACEDBGFB AGBFDECD AB DG FEC10. 如圖所示，給岀由7個頂點組成的無向圖。從頂點A出發(fā)，對它進行深度優(yōu)先搜索得到的頂點序列是二. 填空題1. 設(shè)n°為哈夫曼樹的葉子結(jié)點數(shù)目，則該哈夫曼樹共有個結(jié)點

9、。2. 有數(shù)據(jù)WG二7, 19. 2, 6, 32, 3, 21, 10,則所建Huffman樹的樹髙是,帶權(quán)路徑長度WPL 為o3. 設(shè)一棵完全二叉樹葉子結(jié)點數(shù)為k,最后一層結(jié)點數(shù)2,則該二叉樹的高度為。4. 采用分塊查找時，若線性表中共有625個元素，査找每個元素的概率相同，假設(shè)采用順序查找來確左 結(jié)點所在的塊時，每塊應分個結(jié)點最佳。5. 設(shè)G為具有N個頂點的無向連通圖，則G中至少有條邊。6. 哈夫曼樹（Huffman Tree）又稱。它是n個帶權(quán)葉子結(jié)點構(gòu)成的所有二叉樹中，帶權(quán)路徑長度WPL7. 樹的先序遍歷過程如下：若樹為空，則進行空操作；若樹非空，則訪問樹的:依次先序遍歷樹的J三.

10、應用題仁給定權(quán)值集1,4, 2, 6, 9,構(gòu)造相應的哈夫曼樹,并計算它的帶權(quán)路徑長度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的圖的鄰接矩陣，010030001()00000000C0060020QC00100000C000000500（1）.畫出邏借圖：（2）.畫岀圖的十

11、字鏈表存儲；（3）.基于鄰接矩陣寫出圖的深度、廣度優(yōu)先遍歷序列:（4）.計算圖的關(guān)鍵路徑。作業(yè)題（三）一. 單項選擇題1. 串的長度是指（）B.串中所含非空格字符的個數(shù)D.串中所含字符的個數(shù)A.串中所含不同字母的個數(shù)C串中所含不同字符的個數(shù)2. 設(shè)有數(shù)組Ai,j，數(shù)組的每個元素長度為3字節(jié)，i的值為1到8 , j的值為1到10,數(shù)組從內(nèi)存首 地址BA開始順序存放，當用以列為主存放時，元素A5, 8的存儲首地址為（）。A. BA+141B. BA+1803. 算法分析的兩個主要方而是（A.空間復雜性和時間復雜性C.可讀性和文檔性4. 算法分析的目的是（）oC. BA+222 D. BA+225O

12、B. 正確性和簡明性D.數(shù)據(jù)復雜性和程序復雜性A.找岀數(shù)據(jù)結(jié)構(gòu)的合理性C. 分析算法的效率以求改進5. 下面程序段的時間復雜性的量極為(Int fun(int n)int i=1,s=1;While(svn)S+= +I;Return I;A. 0(n/2)C- 0(n)6. 線性表是()oA. 一個有限序列，可以為空C. 一個無限序列，可以為空7. 帶頭結(jié)點的單鏈表L為空的判泄條件是(A. L= =NULLC L-> next= =LB研究算法中的輸入和輸出的關(guān)系D.分析算法的易懂性和文檔性B O(lbn)D. 0()B. 一個有限序列，不能為空D. 一個無限序列，不能為空)。B. L

13、-> next= =NULLD. L! =NULL&在一個長度為n的線性表中，刪除值為x的元素時需要比較元素和移動元素的總次數(shù)為()。B. n/2A. (n+1) /2CnDn+19. 一個順序存儲線性表的第一個元素的存儲地址是90,每個元素的長度是2,則第6個元素的存儲地址 是()。A. 98B. 100C.102D.10610. 如果某鏈表中最常用的操作是取第i個結(jié)點及英前驅(qū)，則采用()存儲方式最節(jié)省時間。A.單鏈表B.雙向鏈表C.單循環(huán)鏈表D.順序表二、填空題1. 高度為2的二叉樹的結(jié)點數(shù)至少有個，高度為3的二叉樹的結(jié)點數(shù)至少有個。2. 在順序表(8,11,15,19,25

14、,26,30,33,4238,50) 用折半査找關(guān)鍵字值20,需做的關(guān)鍵字比較次數(shù)為3在有n個頂點的無向圖中，每個頂點的度最大可達04. 已知廣義表 A二(a, b, c), (d, e, f),則廣義表運算 head (tail (tail (A) =_。5. 數(shù)組(Array)是n 521)個的有序組合，數(shù)組中的數(shù)據(jù)是按順序存儲在一塊的存儲單元中。6. 采用順序存儲結(jié)構(gòu)表示三元組表(Triple Table),來實現(xiàn)對稀疏矩陣的一種壓縮存儲形式，就稱為，簡稱表。7. 運算是矩陣運算中最基本的一項，它是將一個n】xn的矩陣變成另外一個nxm的矩陣，同時使原來矩陣中元素的行和列的位宜互換而值保

15、持不變。三、應用題仁 對于下圖所示的二叉樹.畫出二叉鏈表存儲結(jié)構(gòu)圖。kszl2、請畫岀下圖所示的樹所對應的二叉樹。3. 已知一個無向圖如下圖所示，要求分別用Prim和Kruskal算法生成最小樹（假設(shè)以為起點，試畫出 構(gòu)適過程4. 已知完全二叉樹的第8層有8個結(jié)點，則其葉子結(jié)點是多少?5畫出如圖所示中樹的二叉樹的表示形式。(a)(b)Q)作業(yè)題(四)一、單項選擇題1. 將兩個各有n個元素的有序表歸并成一個有序表，苴最少得比較次數(shù)是()。A. nB2n-1C2nD2. 一個有n個頂點的無向連通圖，它所包含的連通分量個數(shù)為()。A0B1CnDn+13. 數(shù)據(jù)文件的基本操作中最重要的操作是()。A.

16、插入B.刪除C.修改D.檢索4. 對關(guān)鍵碼序列28, 16, 32, 12, 60, 2, 5, 72快速排序，從小到大一次劃分結(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)的合理性B.研究算法中的輸入和輸出的關(guān)系C.分析算法的效率以求改進D.分析

17、算法的易懂性和文檔性7. 二叉樹的第I層上最多含有結(jié)點數(shù)為()A. 2'B. 2M-1 C. 2MD. 2* -1&循環(huán)隊列存儲在數(shù)組A中，長度為則入隊時的操作為()。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. ()B.()C. (), ()D.(),(),()10. 在一棵度為3的樹中，度為3的結(jié)點數(shù)為2個，度為2的結(jié)點數(shù)為1個，度為1的結(jié)點數(shù)為2個，則度為0的 結(jié)點數(shù)為()個。A

18、. 3B. 4C. 5D. 6二、填空題1. 在一個循環(huán)隊列中，隊首指針指向隊首元素的。2. 數(shù)組中每一個數(shù)據(jù)通常稱為用下標區(qū)分，其中下標的個數(shù)由數(shù)組的決定。3. 一個圖的表示法是唯一的，而表示法是不唯一的。4. 在一個10階的B-樹上，每個數(shù)根結(jié)點中所含的關(guān)鍵字數(shù)目最多允許個，最少允許個5. 對關(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. 即使對不含相同元素的同一輸入序列進行兩組不同的、合法的入

19、棧和出棧組合操作，所得的輸出序列也一定相同。（）3. 帶權(quán)無向圖的最小生成樹必是唯一的。（）4. B-樹和B+樹都可用于文件的索引結(jié)構(gòu)。（）5. 在用堆排序算法排序時，如果要進行增序排序，則需要采用"大根堆"。（）四、應用題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è)標識符

20、依以下次序出現(xiàn)： ac,bd,aa,be,ab,ad,cd,bc,ae,ce。要求用哈希（Hash）方法將它們存入具有10個位巻的表中。（1）將上述關(guān)鍵字（標識符）構(gòu)造一個哈希函數(shù)，使得發(fā)生沖突盡可能地少：（2）線性探測再散列法解 決沖突。寫出上述各關(guān)鍵字在表中位置。4. 給定_個關(guān)犍字序列24, 19, 32, 43, 38, 6, 13, 22,請寫出快速排序第一趟的結(jié)果:堆排序時 所建的初始堆：歸并排序的全過程。然后回答上述三中排序方法中那一種方法使用的輔助空間最少？在最 壞情況下那種方法的時間復雜度最差？作業(yè)題（五）一. 單項選擇題1. 一組記錄的關(guān)鍵碼為（46, 79, 56, 38

21、, 40, 84）,則利用快速排序的方法，以第一個記錄為基準得到 的一次劃分結(jié)果為（）。A. (38,40,46,56,79,84)B(40,38,46,79,56,84)C(40,38,46,56,79,84)D(40,38,46,84,56,79)2 廣義表 A=(a,b,(c,d),(e,(f,g),則下而式子的值為 ()。GetHead(GetTan(GetHead(GetIail(Getlan(A)A. （g） B. （d）C. cD. d3. 對于有n個結(jié)點的二叉樹，貝高度為（）A nlog2n B lon C Llog2nJ+1 D不確定4. 如圖所示，給岀由7個頂點組成的無向圖

22、。從頂點1出發(fā)，對它進行深度優(yōu)先搜索得到的頂點序列是()oB 1 3 476 2 5D 1 2476 5 3A. 1 3 54 2 6 7C 1 5 34 2 765. 采用鄰接表存儲的圖，其深度優(yōu)先遍歷類似于二叉樹的（）。A.中序遍歷B.先序遍歷C.后序遍歷D.按層次遍歷6. 已 知 有 向 圖 G=(V,E), 其 中 V=V1,V2,V3,V4,V5,V6,V7, E=<Vi,V2>,<Vi,V3>,<Vi,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>

23、,<V6,V7>,G的拓撲序列是( )o A. Vi,V3,V4,V6,V2,V5,V7B. Vi,V3,V2,V6,V4,V5,V7c. vbv3,v4,v5,v2,v6,v7d.7. 順序查找法適用于査找順序存儲或鏈式存儲的線性表，平均比較次數(shù)為（）。在此假定N為線性表中結(jié)點數(shù)，且每次査找都是成功的。A. N+1B. 2log2NC. logzND. N&下而關(guān)于m階B樹說法正確的是（每個結(jié)點至少有兩棵非空子樹；）。樹中每個結(jié)點至多有m4個關(guān)鍵字:所有葉子在同一層上;A. C.當插入一個數(shù)據(jù)項引起B(yǎng)樹結(jié)點分裂后，樹長髙一層。B. D.9. 已知一個線性表（38, 25,

24、 74, 63, 52, 48）,假定采用h（k）=k%7計算Hash地址進行散列存儲,若利用鏈地址法處理沖突，則在該Hash表上進行查找的平均查找長度為（）。A.1.0B. 7/6C. 4/3D. 3/210. 在排序算法的實施過程中，使用輔助存儲空間為0 （1）的有（）。A.簡單排序法B.快速排序法C.歸并排序法D.基數(shù)排序法二、填空題1. n （n大于1）個結(jié)點的各棵樹中，其中深度最大的那棵樹的深度是n,它共有個葉子結(jié)點和個非葉子結(jié)點。2. 設(shè)一棵后序線索樹的高是50,結(jié)點x是樹中的一個結(jié)點，其雙親是結(jié)點y,y的右子樹髙度是60, x是y的左孩子。則確泄x的后繼最多需經(jīng)過中間結(jié)點（不含后

25、繼及x本身）3. 高度為2 （第2層為葉子）的3階B-樹中，最多有個關(guān)鍵字。4. 分別采用堆排序，快速排序，冒泡排序和歸并排序，對初態(tài)為無序的表，則平均情況下最省時間的是 算法。5. 簡單選擇排序和起泡排序中比較次數(shù)與序列初態(tài)無關(guān)的算法有°6. 串的鏈式存儲結(jié)構(gòu)是將存儲區(qū)域分成一系列大小相同的結(jié)點，每個結(jié)點有兩個域域和域。其中域用于用于存放數(shù)據(jù)，域用于存放下一個結(jié)點的指針三. 判斷1. 順序存儲的線性表可以隨機存取。（）2. 即使對不含相同元素的同一輸入序列進行兩組不同的、合法的入棧和出棧組合操作，所得的輸出序列也一定相同。（）3. 十字鏈表是無向圖的一種存儲結(jié)構(gòu)。（）4. 折半查找

26、方法適用于排列連續(xù)順序文件的查找。（）5. 在執(zhí)行某個排序算法過程中，岀現(xiàn)了排序碼朝著最終排序序列位置相反方向移動，則該算法是不穩(wěn)上 的。()四、應用題1. 用十字鏈表表示一個有k個非零元素的mxn的稀疏矩陣，則其總的結(jié)點數(shù)為多少？2. G=(V,E)是一個帶有權(quán)的連通圖，則：(1) .請回答什么是G的最小生成樹：(2) . G為下圖所示，請找出G的所有最小生成樹。3請分別敘述在一個連續(xù)順序文件中采用順序査找法，折半查找法和分塊査找法查找一個記錄，該文件 中記錄應該滿足什么條件？4.設(shè)待排序文件之排序碼為(88. 33, 22, 55, 99, 11, 66),采用順序存儲。請用直接選擇排序算

27、法 對上述文件進行排序，用圖示說明排序過程。作業(yè)題一參考答案：一、單項選擇題仁 C 2、B 3、D4. C 5、B6、B 7、A8、C 9. D 10. D二、填空題1、非零元很少2、操作受限(或限怎僅在表尾進行插入和限左僅在表頭進行刪除操作或限制存取點或特殊)，先進先出(或 后進后出)3、簡單選擇排序4、O(n2), 0(e), O(n)5、鄰陣矩陣，鄰接表三、算法答：int count = 0;void onechild ( Btree t)訐(t!二NULL) onechild (t->lchild );onechild (t->rchild );if (t>lchil

28、d!二NULL && (t->rchUd!=NULL | | t>lchild!二NULL && t->rchild=NULL )count+;四、應用題仁答：(0)率254812 t65432058(1)12吟483665432058122048仁36654325 豐58122025366543485812202536654348581_f122025364365 48 t_58(6)1220253643486558t_i(7)12202536434858652、答:(2)(1)kszl(3)(4)(E)©2©散列地址10

29、0101102103104105106107108109關(guān)鍵字98637917531961754649比較次數(shù)12111123510用線性探測再散列解決沖突，ASLsucc=27/104、答：成功査找平均比較査找長度為:(n+1) /nlog2 (n+1)卜仁作業(yè)題二參考答案: 一、單項選擇題 仁 C2、C3、B4. C5、D6、C7、C8、B9、A 10. C二、填空題仁 2no-12、6, 2613、log2k+14、255、N-16、最優(yōu)二叉樹，最小的二叉樹7、根結(jié)點，各子樹三、應用題仁答：不唯一，型對即可13此樹的帶權(quán)路徑長度WPL =9*1+6*2+4*3+(1+2)*4=45 2、

30、答：插入6插入3(1) 插入103、答：當關(guān)鍵字為3時，比較次數(shù)為4：當關(guān)鍵字為8時，比較次數(shù)為1：當關(guān)鍵字為19時，查找不成功：(3) 深度優(yōu)先遍歷序列：ABCDE r度優(yōu)先遍歷序列：ABCED (4)關(guān)鍵路徑AB (長100)作業(yè)題三參考答案:一、單項選擇題仁 D2. B3、A4. C5、D6、A7、B 8、C 9. B 10. D二、填空題仁2, 32、43、n-14、e5、相同類型數(shù)據(jù)，地址連續(xù)6、三元組順序表，三元組7、矩陣轉(zhuǎn)宜三、應用題仁答：3. 答：Prim算法構(gòu)造最小生成樹的步驟如24題所示，為巧省篇幅，這里僅用Kruskal算法，構(gòu)造最小生成 樹過程如下：(下圖也可選(2,4

31、)代替(3,4),(5,6)代替(1,5)4. 答：由完全二叉樹的宦義可知，除最后一層外，其他層的結(jié)點是滿的。設(shè)該完全二叉樹有d層，則除 最后一層外各層的結(jié)點個數(shù)分別為：1, 2, 4, 8, 16, 32,，即第i層的結(jié)點個數(shù)為21-10這里第8層有8 個結(jié)點，顯然第8/層是最后的一層，那么第7層的結(jié)點個數(shù)為27-1=64個，英中的4個結(jié)點有8個葉子結(jié)點， 余下的為葉子結(jié)點，個數(shù)為64-4=60,所以該完全二叉樹的葉子結(jié)點個數(shù)為60+8=68個。kszl5答：對應的二叉樹形式如圖所示:作業(yè)題四參考答案:一.單項選擇題1. A 2. B 3. D4. B 5. D6、C7、C8. C9、B 1

32、0、D、填空題1.答：前一個位置2.答：數(shù)組元素，數(shù)組元素.維數(shù)3. 答：鄰陣矩陣，鄰接表4. 答：9, 45答：48 44 52 64 80 916、1, 2三.判斷1.答:J2.答:X3.答:X4.答:J5.答:J四、應,用1. 答：模式p的next函數(shù)值如下:bmai 図ttAS5«to 的睡 x巳行30中文(中田)IDZ:文樣妳© us(yp掖入心格式© 工且林® fiDQP 軌bQPCJ SCMtW®. 4or - « 自i±B« (u)、匚)O U如& 血/ 少工 A 三丟三»廠 型I

33、JIM辿第去至d0c - Mi c |胡3務坐&心鄉(xiāng)10:06J簡述一個字符申中子串的柚成。各一個宇符牢中任看連繕:t宇符蛆戍的子序列稱為宇符串的子飢空串和空格串有何區(qū)別？字暮串中空格符有何意酬 空串在串的處理中有何作用？答，不含任何字符的雖族刃空串其.爭去威為零，僅含有空奮字符職鍛墮軟品它的長度 為中空恪符的個叛 空格符在字符雖中可用未分廂一般的字符.便于阿諛和識別.空恪符會 占用有效串長°空串在處理過程中可用于作為任意字符串的子卷| 董茶圭的.長度小于一個常數(shù)，則釆用何種存倨方式城節(jié)省空間？答，采用順序串$節(jié)省空何.因為頂序串與城雖相匕 不需要指針域。模式串p="皺妙磁"的next函數(shù)值序列為多少？答，擺式D的加Xt函數(shù)值如下ji01234567俱武串)abaabcacnext：-10011201算法設(shè)廿題(9杓)釆用煩序結(jié)構(gòu)存鰭串"編寫一個函數(shù)冊躲s中第字符開緇的j個字符。答« s.txin8 * .妙.(航ring * s, lai lai J)臉k；2. 答：A共120個字節(jié)。