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

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