數(shù)據(jù)結構專升本模擬題及參考答案

作業(yè)題（一)一、單項選擇題１、從邏輯上可以把數(shù)據(jù)結構分為（）兩大類.A。動態(tài)結構、靜態(tài)結構B。順序結構、鏈式結構C。線性結構、非線性結構D.初等結構、構造型結構2、鏈表不具有得特點就是()A.插入、刪除不需要移動元素B?？呻S機訪問任一元素C.不必事先估計存儲空間D。所需空間與線性長度成正比3、下面程序段得時間復雜度得量級為(）.Ｆｏr(i=1;ｉ＜=n；i+＋）For（j=1;j＜=Ｉ；j++)Ｆor(k=1；k<＝j；ｋ+＋)X=x＋１；A.O(1)B。O(n）Ｃ。O（n2）Ｄ．O(n3）4、在一個帶頭結點得雙向循環(huán)鏈表中，若要在p所指向得結點之前插入一個新結點，則需要相繼修改(）個指針域得值。A．2B．3Ｃ.4D.65、一個順序存儲線性表得第一個元素得存儲地址就是９0，每個元素得長度就是2,則第６個元素得存儲地址就是（）。A.98B。10０C．1０２D．10６6、判定一個棧s（最多元素為m0)為空得條件就是（).A。s-〉ｔop！=0B。ｓ－〉ｔop＝＝０C．s—〉top?。絤0D。ｓ－〉top==m０7、循環(huán)隊列用數(shù)組Ａ［m]（下標從０到m－１）存放其元素值,已知其頭尾指針分別就是front與ｒeａr，則當前隊列中得元素個數(shù)就是（）。A.(rｅａｒ—front+m）％ｍＢ。reaｒ-ｆronｔ+1C。rear－fｒoｎｔ—１Ｄ．rear—front８、設有兩個串Ｓ1與S２,求串Ｓ2在Ｓ1中首次出現(xiàn)位置得運算稱作(）.A．連接B．求子串Ｃ。模式匹配Ｄ。判子串９、設串S１='ABCDＥFG＇,S２=＇ＰQRＳT’,函數(shù)cｏn（ｘ，y)返回ｘ與y串得連接串，suｂs(s，i，j）返回串S得得從序號ｉ得字符開始得j個字符組成得子串,len（s）返回串S得長度，則coｎ(subs（S1，2，ｌeｎ（S2）），suｂｓ（S1,ｌeｎ（S2）,2））得結果就是（)。A.ＢCDEF ? Ｂ．BＣDEFＧC。BCPQＲSTD．BＣDEFEＦ１0、數(shù)組常用得兩種基本操作就是（)。Ａ。建立與查找Ｂ．刪除與查找C。插入與索引D.查找與修改二、填空題1、所謂稀疏矩陣指得就是____＿＿＿_且分布沒有規(guī)律.2、隊列就是＿＿______得線性表，其運算遵循___＿___＿得原則。3、空格串就是_______＿＿_＿＿____＿______＿＿_____＿＿。4、簡單選擇排序與起泡排序中比較次數(shù)與序列初態(tài)無關得算法有___＿＿＿__。５、設圖G有n個頂點與e條邊,則對用鄰接矩陣表示得圖進行深度或廣度優(yōu)先搜索遍歷時得時間復雜度為，而對用鄰接表表示得圖進行深度或廣度優(yōu)先搜索遍歷時得時間復雜度為，圖得深度或廣度優(yōu)先搜索遍歷時得空間復雜度均為。6、一個圖得表示法就是唯一得,而表示法就是不唯一得。三、算法設二叉樹采用二叉鏈表結構，試設計一個算法統(tǒng)計給定二叉樹中得一度結點數(shù)目。四、應用題1、對關鍵字無序序列（36，２5，48，１2,65，４３，20,58）進行直接選擇排序,請寫出每一趟排序得結果。（１0分）2、對無向帶權圖,用克魯斯卡爾算法構造最小生成樹。(10分)20A3920A39D4FCB8D4FCB81E651E65G2G23、已知記錄關鍵字集合為(53，17,1９，61，98，７5,79,63，４6，49）要求散列到地址區(qū)間（１0０,101,102，103，1０4,10５，106，１０７,1０8，109）內，若產生沖突用開型尋址法得線性探測法解決。要求寫出選用得散列函數(shù)；形成得散列表；計算出查找成功時平均查找長度與查找不成功得平均查找長度.（設等概率情況）４、設被查找文件有４095個記錄,對每個記錄查找記錄概率相等,若采用順序查找，成功查找平均比較次數(shù)為多少？作業(yè)題（二）、單項選擇題1、有六個元素６,５,4,3,2,1得順序進棧,問下列哪一個不就是合法得出棧序列?（）Ａ、54361２Ｂ、4531２6C、３4６521D、2341562、棧與隊都就是（)A。順序存儲得線性結構Ｂ、鏈式存儲得非線性結構C、限制存取點得線性結構D、限制存取點得非線性結構3、順序查找法適合于存儲結構為(）得線形表。Ａ。散列存儲 ?? ?? B。順序存儲或鏈接存儲C．壓縮存儲 ? ? ??D。索引存儲４、分別以下列序列構造二叉排序樹,與用其它三個序列所構造得結果不同得就是（）。A。(100，8０，90,6０，1２0，１10，１30）?B.(100，1２0，１10,1３0，80，60，90）C.(１00,６0,８０，90，１20，110，1３0） D．（100，80，60，90，120,１30，1１0）5、折半查找得平均比較次數(shù)為()。Ａ．ｎ?? ? B.n/2C．log2ｎ ? ??? D．lｏg２(n+１）6、當在一個有序得順序存儲表上查找一個數(shù)據(jù)時,即可用折半查找，也可用順序查找,但前者比后者得查找速度(）A．必定快 ? ????B.不一定C．在大部分情況下要快? ? D.取決于表遞增還就是遞減7、已知一有向圖得鄰接表存儲結構如下圖如示.根據(jù)有向圖得深度優(yōu)先遍歷算法，從頂點v１出發(fā)，所得到得頂點序列就是()。A．ｖ1，v2，ｖ3，v5,ｖ4 ?? ?B.ｖ１，v2,v３，v4,v5Ｃ。ｖ1，ｖ3，v4,ｖ５，v2 ???D。v１,v4，v3，v5,ｖ28、為了方便地對圖狀結構得數(shù)據(jù)進行存取操作，則其中數(shù)據(jù)存儲結構宜采用（)。A．順序存儲? ? ? B。鏈式存儲C.索引存儲 ? ?? ?D。散列存儲9、在一個具有n個頂點得有向圖中，若所有頂點得出度之與為s,則所有頂點得入度之與為（）.A.ｓ????? B．s—1C.s＋1?? ? ? ? D.n10、如圖所示,給出由７個頂點組成得無向圖。從頂點A出發(fā)，對它進行深度優(yōu)先搜索得到得頂點序列就是(）.A。ＡＥＣDBFＧ? ? ?Ｂ.AGBFＤECC。ACEDＢＧＦ?? ?Ｄ.ＡBDＧFEC二、填空題1、設ｎ0為哈夫曼樹得葉子結點數(shù)目，則該哈夫曼樹共有__＿__＿__個結點。2、有數(shù)據(jù)ＷG＝{7，19,2，6,32，3，21，1０｝,則所建Huｆfman樹得樹高就是________,帶權路徑長度ＷPL為________。3、設一棵完全二叉樹葉子結點數(shù)為ｋ,最后一層結點數(shù)〉2，則該二叉樹得高度為________＿____＿__。4、采用分塊查找時,若線性表中共有6２5個元素，查找每個元素得概率相同，假設采用順序查找來確定結點所在得塊時，每塊應分個結點最佳。5、設G為具有Ｎ個頂點得無向連通圖，則G中至少有條邊.6、哈夫曼樹（HｕfｆmａnTree)又稱。它就是n個帶權葉子結點構成得所有二叉樹中，帶權路徑長度WPL.７、樹得先序遍歷過程如下:若樹為空,則進行空操作；若樹非空,則訪問樹得;依次先序遍歷樹得.三、應用題1、給定權值集合｛１,4，2，6，９,｝，構造相應得哈夫曼樹,并計算它得帶權路徑長度。2、對關鍵字序列{１0，6，3，２，5，4},構造一棵平衡二叉（排序）樹并畫圖（要求畫出建樹過程）。3、設有一個有序文件，其中各記錄得關鍵字為（１,2，3，4,5，6，7，8,9,1０，11，12,13,１４,１5)，當用折半查找算法查找關鍵字為3，8,１9時,其比較次數(shù)分別為多少？４、對有五個結點｛A,B,C，Ｄ，Ｅ}得圖得鄰接矩陣，（1）。畫出邏輯圖；（2）。畫出圖得十字鏈表存儲；(3)?；卩徑泳仃噷懗鰣D得深度、廣度優(yōu)先遍歷序列;(4)。計算圖得關鍵路徑.作業(yè)題（三）一、單項選擇題1.串得長度就是指（）A.串中所含不同字母得個數(shù)B.串中所含非空格字符得個數(shù)C。串中所含不同字符得個數(shù)D。串中所含字符得個數(shù)2.設有數(shù)組A[ｉ，j]，數(shù)組得每個元素長度為3字節(jié),ｉ得值為1到8,j得值為１到10，數(shù)組從內存首地址BA開始順序存放,當用以列為主存放時,元素A[５,8］得存儲首地址為(）.A、BＡ+141Ｂ、BＡ+180C、ＢA＋2２２D、BＡ＋2253。算法分析得兩個主要方面就是(）。A?？臻g復雜性與時間復雜性B。正確性與簡明性C?？勺x性與文檔性D。數(shù)據(jù)復雜性與程序復雜性4.算法分析得目得就是（）。A.找出數(shù)據(jù)結構得合理性B.研究算法中得輸入與輸出得關系C．分析算法得效率以求改進D.分析算法得易懂性與文檔性5、下面程序段得時間復雜性得量極為（）。Intｆｕn（iｎtｎ)｛inｔi＝1，ｓ=１;Wｈile(ｓ〈n）S＋＝++Ｉ;ＲeturnI；｝A.O(n／2)B．O(lbn)C．O（n)D.O（）6、線性表就是(）。A．一個有限序列,可以為空B。一個有限序列,不能為空C。一個無限序列，可以為空Ｄ.一個無限序列，不能為空7、帶頭結點得單鏈表L為空得判定條件就是（）。Ａ．L＝=NUＬＬB。L-〉ｎext＝=NＵＬLC。L->next==LD。L！=NULL8、在一個長度為n得線性表中,刪除值為ｘ得元素時需要比較元素與移動元素得總次數(shù)為(）。Ａ.(ｎ+1）／2B．ｎ/2C。nＤ．ｎ+1９、一個順序存儲線性表得第一個元素得存儲地址就是９０，每個元素得長度就是２，則第6個元素得存儲地址就是（）。A。98B．100Ｃ.１02D.1０610、如果某鏈表中最常用得操作就是取第ｉ個結點及其前驅，則采用()存儲方式最節(jié)省時間。Ａ.單鏈表B。雙向鏈表C.單循環(huán)鏈表D.順序表二、填空題１、高度為２得二叉樹得結點數(shù)至少有____＿___個，高度為3得二叉樹得結點數(shù)至少有___＿___＿個。２、在順序表（８,11,15,19,25,26，30,３３，4２，48，50）中，用折半查找關鍵字值2０，需做得關鍵字比較次數(shù)為__＿＿____。3、在有n個頂點得無向圖中，每個頂點得度最大可達____＿_＿_。4.已知廣義表Ａ=（(a，ｂ，c)，（ｄ，e，f）),則廣義表運算hｅaｄ（tail(tail（A）)）=.5、數(shù)組(Arｒay)就是n（n≥1）個得有序組合,數(shù)組中得數(shù)據(jù)就是按順序存儲在一塊得存儲單元中。6、采用順序存儲結構表示三元組表（ＴripｌeTaｂle),來實現(xiàn)對稀疏矩陣得一種壓縮存儲形式，就稱為,簡稱表。7、運算就是矩陣運算中最基本得一項,它就是將一個mxｎ得矩陣變成另外一個nxm得矩陣，同時使原來矩陣中元素得行與列得位置互換而值保持不變。三、應用題1、對于下圖所示得二叉樹,畫出二叉鏈表存儲結構圖。2、請畫出下圖所示得樹所對應得二叉樹。AABCDE３、已知一個無向圖如下圖所示，要求分別用Ｐｒｉm與Ｋｒｕskal算法生成最小樹（假設以①為起點，試畫出構造過程）。4、已知完全二叉樹得第8層有8個結點，則其葉子結點就是多少？５、畫出如圖所示中樹得二叉樹得表示形式.作業(yè)題(四）一、單項選擇題1、將兩個各有ｎ個元素得有序表歸并成一個有序表，其最少得比較次數(shù)就是（）。Ａ．nＢ。２n—1C.2nD。ｎ-１２、一個有n個頂點得無向連通圖,它所包含得連通分量個數(shù)為（）。A。0 ???? ?Ｂ。１Ｃ.n? ? D。n+13、數(shù)據(jù)文件得基本操作中最重要得操作就是(）。Ａ．插入 ? ? ? B．刪除C．修改 ?? ???D.檢索４、對關鍵碼序列28,１6,32,12,60，2,5,７２快速排序，從小到大一次劃分結果為（）。A。(2,5,12,16)２６(６0，３２,72）?? Ｂ．（5,16，2，１2)28(６0,３2,72)Ｃ。(２，1６,12，5)2８（６0,32，72）??? ?D。（5,16，2，12)２８(３2,６０,７2)5、如果只想得到１０00個元素組成得序列中第5個最小元素之前得部分排序得序列，用(）方法最快.A。堆排序?? ??? B?？焖倥判駽．插入排序? ? ??D.歸并排序６．算法分析得目得就是(）。A.找出數(shù)據(jù)結構得合理性Ｂ.研究算法中得輸入與輸出得關系C．分析算法得效率以求改進D.分析算法得易懂性與文檔性7、二叉樹得第I層上最多含有結點數(shù)為(）A。2IB。2I-1-1C．2I－1D。２I-18。循環(huán)隊列存儲在數(shù)組A中，長度為m,則入隊時得操作為（）。A、rear=rear+1B、reaｒ=(reaｒ+1）moｄ(m－１）Ｃ、rear＝（reaｒ+１）modｍＤ、rear=（ｒｅaｒ＋１）ｍod（m+１)9、廣義表滿足Head(A)=Tail(A)，則A為（）。A．(）B．（（））C.（(）,（))D。（(），(）,（）)１０、在一棵度為3得樹中,度為3得結點數(shù)為2個，度為2得結點數(shù)為１個,度為1得結點數(shù)為２個,則度為０得結點數(shù)為(）個。A。3B.４Ｃ。5D．６二、填空題１、在一個循環(huán)隊列中,隊首指針指向隊首元素得_________。2、數(shù)組中每一個數(shù)據(jù)通常稱為,用下標區(qū)分，其中下標得個數(shù)由數(shù)組得決定.3、一個圖得表示法就是唯一得,而表示法就是不唯一得。４、在一個10階得B－樹上，每個數(shù)根結點中所含得關鍵字數(shù)目最多允許個，最少允許個５、對關鍵字序列（５2，80，63,44，48,91)進行一趟快速排序之后得得到結果為。1０、高度為1得平衡二叉樹得結點數(shù)至少有_＿＿__＿__個,高度為2得平衡二叉樹得結點數(shù)至少有_＿__＿＿__個。三判斷1、順序存儲結構屬于靜態(tài)結構，鏈式結構屬于動態(tài)結構。（）2、即使對不含相同元素得同一輸入序列進行兩組不同得、合法得入棧與出棧組合操作，所得得輸出序列也一定相同。（）3、帶權無向圖得最小生成樹必就是唯一得.()4、Ｂ—樹與B+樹都可用于文件得索引結構。(）5、在用堆排序算法排序時，如果要進行增序排序,則需要采用"大根堆”。（）四、應用題1、模式串ｐ=＂abaabcac”得next函數(shù)值序列為多少?2、設二維數(shù)組A[５］［6]得每個元素占4個字節(jié)，已知LOC（a０，0）=1000，A共占多少個字節(jié)？A得終端結點a4，5得起始地址為多少？按行與按列優(yōu)先存儲時，a2,5得起始地址分別為多少？３、設a，b，c,ｄ,e五個字符得編碼分別為１,2，3，4，5，并設標識符依以下次序出現(xiàn):ａｃ,bｄ,ａａ,be，ａb,ad,cd，bc，ａe，ce。要求用哈希（Ｈasｈ）方法將它們存入具有10個位置得表中。（1)將上述關鍵字(標識符)構造一個哈希函數(shù)，使得發(fā)生沖突盡可能地少;(2)線性探測再散列法解決沖突。寫出上述各關鍵字在表中位置.４、給定一個關鍵字序列{2４，19，32，43，38，6，13,2２｝,請寫出快速排序第一趟得結果；堆排序時所建得初始堆；歸并排序得全過程。然后回答上述三中排序方法中那一種方法使用得輔助空間最少?在最壞情況下那種方法得時間復雜度最差?作業(yè)題(五）一、單項選擇題1、一組記錄得關鍵碼為（４6，７９，56,38，４0，８4）,則利用快速排序得方法,以第一個記錄為基準得到得一次劃分結果為(）。A。(38,40，46,56，7９,84)? ?Ｂ。（40,38，４6,７9,56,8４）C.(４0,38，４６，5６,79,８4）? ? Ｄ．(４0，３8,46，84，５６，７9)2。廣義表A=（ａ,b，(c,d),（e,(f,ｇ）)),則下面式子得值為()。GｅtHｅad(GeｔTail（GｅｔHｅad(GetTaｉl(GetＴail(Ａ)））））A、(g)B、（d）C、cD、d3．對于有n個結點得二叉樹，其高度為(）Ａ.nｌog２nB.ｌog2ｎＣ.?lｏｇ2n?+1Ｄ。不確定4、如圖所示，給出由7個頂點組成得無向圖。從頂點1出發(fā)，對它進行深度優(yōu)先搜索得到得頂點序列就是（)。A。1354267? ? B.1３476２5Ｃ.1５34276 ? ? Ｄ.124７6535、采用鄰接表存儲得圖，其深度優(yōu)先遍歷類似于二叉樹得().A．中序遍歷 ? ? ??B.先序遍歷C．后序遍歷?? ??D.按層次遍歷6、已知有向圖Ｇ=(V，E），其中Ｖ={V1,V2，V３，V4，Ｖ5，V6，V７｝,E＝{＜Ｖ1，V２>,＜V1，V3＞，<V１，V4>，＜V2，Ｖ5>，〈V３，V５>,＜V3,V6〉,＜Ｖ４,V6>,〈V５，V7>，〈V6,V7＞｝,G得拓撲序列就是（)。A．Ｖ１，V3,V4,V6，V2，V5，V7??? ?B。Ｖ1，V３，Ｖ2，V6，V４,V5,V7Ｃ.Ｖ１，V3，V4，V5，Ｖ２,V6,V7? ? Ｄ．Ｖ1，V２，V5，Ｖ３，V4，Ｖ6，V7７、順序查找法適用于查找順序存儲或鏈式存儲得線性表，平均比較次數(shù)為（）。在此假定N為線性表中結點數(shù)，且每次查找都就是成功得。A.N+1 ???? Ｂ。２log２NC。loｇ2N?? ? D。N8、下面關于m階B樹說法正確得就是（).①每個結點至少有兩棵非空子樹；②樹中每個結點至多有m一１個關鍵字;③所有葉子在同一層上;④當插入一個數(shù)據(jù)項引起B(yǎng)樹結點分裂后，樹長高一層。A。①②③????? ??Ｂ。②③C.②③④ ? ? ??D。③9、已知一個線性表(38，25，74，63,５2，4８),假定采用ｈ（k)=k%7計算Hａsh地址進行散列存儲,若利用鏈地址法處理沖突，則在該Hash表上進行查找得平均查找長度為(）。A.1、０?? ???? B.7/6C.4/3 ?? Ｄ。３／210、在排序算法得實施過程中，使用輔助存儲空間為Ｏ（１）得有（)。A.簡單排序法 ?? ?B、快速排序法C.歸并排序法?? ?? D、基數(shù)排序法二、填空題1、ｎ（ｎ大于1)個結點得各棵樹中，其中深度最大得那棵樹得深度就是n,它共有_____＿__個葉子結點與______＿_個非葉子結點。2、設一棵后序線索樹得高就是50,結點ｘ就是樹中得一個結點，其雙親就是結點y，ｙ得右子樹高度就是60，x就是y得左孩子。則確定ｘ得后繼最多需經過＿______＿中間結點（不含后繼及x本身）3、高度為2(第2層為葉子)得3階B—樹中,最多有__＿___＿_個關鍵字。4、分別采用堆排序,快速排序，冒泡排序與歸并排序,對初態(tài)為無序得表，則平均情況下最省時間得就是______＿＿算法。５、簡單選擇排序與起泡排序中比較次數(shù)與序列初態(tài)無關得算法有__＿＿____。６、串得鏈式存儲結構就是將存儲區(qū)域分成一系列大小相同得結點，每個結點有兩個域域與域。其中域用于用于存放數(shù)據(jù),域用于存放下一個結點得指針三。判斷1、順序存儲得線性表可以隨機存取.（）２、即使對不含相同元素得同一輸入序列進行兩組不同得、合法得入棧與出棧組合操作,所得得輸出序列也一定相同.()３、十字鏈表就是無向圖得一種存儲結構。(）4、折半查找方法適用于排列連續(xù)順序文件得查找。（）５、在執(zhí)行某個排序算法過程中，出現(xiàn)了排序碼朝著最終排序序列位置相反方向移動,則該算法就是不穩(wěn)定得。()四、應用題１、用十字鏈表表示一個有k個非零元素得mxn得稀疏矩陣,則其總得結點數(shù)為多少?2、G=(V，E)就是一個帶有權得連通圖,則：（1）。請回答什么就是G得最小生成樹；（2）.Ｇ為下圖所示，請找出G得所有最小生成樹。3、請分別敘述在一個連續(xù)順序文件中采用順序查找法，折半查找法與分塊查找法查找一個記錄，該文件中記錄應該滿足什么條件？4、設待排序文件之排序碼為（88,33，２2，55,99，11，66），采用順序存儲。請用直接選擇排序算法對上述文件進行排序，用圖示說明排序過程?！?—---——-－----—--－—－-—---——---－-—－—-—－——-－-－—作業(yè)題一參考答案:一、單項選擇題１、Ｃ２、B3、D４、C５、B6、B7、Ａ8、C9、D１０、D二、填空題１、非零元很少2、操作受限(或限定僅在表尾進行插入與限定僅在表頭進行刪除操作或限制存取點或特殊)，先進先出(或后進后出）3、簡單選擇排序４、Ｏ(n2），O（e)，O（n）5、鄰陣矩陣,鄰接表三、算法答:ｉntcount＝０；voｉdｏneｃhild（Ｂｔreet）{if（t!=ＮUＬＬ)｛onechilｄ（t－＞lchilｄ）；onｅcｈild（t－〉rcｈild）；ｉf（t—〉lchiｌd!＝ＮUＬL＆&(t—>ｒchｉｌｄ!=NULＬ｜｜t－>lchild！=NUＬＬ＆&t—>rｃhiｌd＝＝ＮULL）count＋+;｝}四、應用題1、答:2、答:(１)????? (２)CC11C11C2FGGG3AD3AD3AD11C2FG1C1C4422FG（5)? ? ?? （6）33ADEBEB561C61C441CB543A1CB543AD2FG2FG３、答:由于地址空間為１0,且從10０開始,故散列函數(shù)選為Ｈ（key）=key%７＋1０0。用線性探測再散列解決沖突，ASLｓucc=27/104、答：成功查找平均比較查找長度為：(n+1）／n[log2（n+１）]－1.作業(yè)題二參考答案:一、單項選擇題１、C2、Ｃ3、B４、C５、D6、C7、C8、B9、A10、Ｃ二、填空題1、2ｎ0—1２、6，２613、éｌoｇ2ｋù＋14、２5５、N—16、最優(yōu)二叉樹，最小得二叉樹7、根結點，各子樹三、應用題１、41241263713922此樹得帶權路徑長度WＰL＝9＊1＋6*2＋4＊3+（1＋２)＊４=452、答：6（1）插入10? （2）插入6 ? （3)插入3? （4)61010??? ??1010103調整610103調整61066（5）插入2? (6)插入５ ??（7）插入４ （8)65365324101063210632調整106325調整106325553、答：當關鍵字為3時,比較次數(shù)為4;當關鍵字為８時，比較次數(shù)為1；當關鍵字為１9時,查找不成功；4、答：（2)略（3)深度優(yōu)先遍歷序列：AＢCDE廣度優(yōu)先遍歷序列:ABCED(4）關鍵路徑A—－Ｂ（長１00）作業(yè)題三參考答案:一、單項選擇題1、Ｄ2、B3、Ａ4、Ｃ5、Ｄ６、Ａ7、B８、Ｃ9、B10、D二、填空題１、２，３2、43、n—１4、e５、相同類型數(shù)據(jù)，地址連續(xù)６、三元組順序表，三元組7、矩陣轉置三、應用題１、答：? ? ?? ???二叉鏈表∧∧∧∧∧∧∧∧∧∧⑧⑨⑦⑥⑤④③②①? ? ? ∧∧∧∧∧∧∧∧∧∧⑧⑨⑦⑥⑤④③②①? ? ?? ? ? ? ? ?(2?? ? ?? ?? ?2、答：A ? ACDBCDBEE3、答:Pｒｉｍ算法構造最小生成樹得步驟如２4題所示,為節(jié)省篇幅,這里僅用Krｕskal算法，構造最小生成樹過程如下：（下圖也可選（２，４)代替(3，4），（５,6）代替(1，5)）即:4、答：由完全二叉樹得定義可知，除最后一層外,其她各層得結點就是滿得。設該完全二叉樹有d層，則除最后一層外各層得結點個數(shù)分別為:1，2，4，８，16，32，…,即第i層得結點個數(shù)為2ｉ—１。這里第８層有8個結點，顯然第８/層就是最后得一層,那么第7層得結點個數(shù)為27—１=64個,其中得４個結點有8個葉子結點,余下得為葉子結點，個數(shù)為64—4=6０,所以該完全二叉樹得葉子結點個數(shù)為６0+８＝6８個。５、答：對應得二叉樹形式如圖所示：作業(yè)題四參考答案:一、單項選擇題1、A2