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

東北農(nóng)業(yè)大學(xué)網(wǎng)絡(luò)教育學(xué)院數(shù)據(jù)結(jié)構(gòu)專(zhuān)升本作業(yè)題作業(yè)題（一）一、單項(xiàng)選擇題1.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（C）兩大類(lèi)。A．動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B．順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)C．線(xiàn)性結(jié)構(gòu)、非線(xiàn)性結(jié)構(gòu)D．初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)2.鏈表不具有的特點(diǎn)是（B）A．插入、刪除不需要移動(dòng)元素B．可隨機(jī)訪(fǎng)問(wèn)任一元素C．不必事先估計(jì)存儲(chǔ)空間D．所需空間與線(xiàn)性長(zhǎng)度成正比3.下面程序段的時(shí)間復(fù)雜度的量級(jí)為（D）。For(i=1;i<=n;i++)For(j=1;j<=I;j++)For(k=1;k<=j;k++)X=x+1;A．O(1)B．O(n)C．O(n2)D．O(n3)4.在一個(gè)帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表中，若要在p所指向的結(jié)點(diǎn)之前插入一個(gè)新結(jié)點(diǎn)，則需要相繼修改（B）個(gè)指針域的值。A．2B3C．4D．65、一個(gè)順序存儲(chǔ)線(xiàn)性表的第一個(gè)元素的存儲(chǔ)地址是90，每個(gè)元素的長(zhǎng)度是2，則第6個(gè)元素的存儲(chǔ)地址是（D）。A．98B．100C．102D．1066、鑒定一個(gè)棧s（最多元素為m0）為空的條件是（B）。A．s-〉top!=0B．s-〉top==0C．s-〉top!=m0D．s-〉top==m07、循環(huán)隊(duì)列用數(shù)組A[m]（下標(biāo)從0到m-1）存放其元素值，已知其頭尾指針?lè)謩e是front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是（）。A．（rear-front+m）%mB．rear-front+1C．rear-front-1D．rear-front8、設(shè)有兩個(gè)串S1與S2，求串S2在S1中初次出現(xiàn)位置的運(yùn)算稱(chēng)作（）。A．連接B．求子串C．模式匹配D．判子串9、設(shè)串S1='ABCDEFG'，S2='PQRST'，函數(shù)con（x，y）返回x和y串的連接串，subs(s,i,j)返回串S的的從序號(hào)i的字符開(kāi)始的j個(gè)字符組成的子串，len(s)返回串S的長(zhǎng)度，則con(subs(S1,2,len(S2)),subs(S1,len(S2),2))的結(jié)果是（）。A．BCDEF B．BCDEFGC．BCPQRSTD．BCDEFEF10、數(shù)組常用的兩種基本操作是（）。A．建立與查找B．刪除與查找C．插入與索引D．查找與修改二、填空題1.所謂稀疏矩陣指的是________且分布沒(méi)有規(guī)律。2.隊(duì)列是________的線(xiàn)性表，其運(yùn)算遵循________的原則。3.空格串是________________________________。4.簡(jiǎn)樸選擇排序和起泡排序中比較次數(shù)與序列初態(tài)無(wú)關(guān)的算法有________。5、設(shè)圖G有n個(gè)頂點(diǎn)和e條邊，則對(duì)用鄰接矩陣表達(dá)的圖進(jìn)行深度或廣度優(yōu)先搜索遍歷時(shí)的時(shí)間復(fù)雜度為，而對(duì)用鄰接表表達(dá)的圖進(jìn)行深度或廣度優(yōu)先搜索遍歷時(shí)的時(shí)間復(fù)雜度為，圖的深度或廣度優(yōu)先搜索遍歷時(shí)的空間復(fù)雜度均為。6、一個(gè)圖的表達(dá)法是唯一的，而表達(dá)法是不唯一的。三、算法設(shè)二叉樹(shù)采用二叉鏈表結(jié)構(gòu)，試設(shè)計(jì)一個(gè)算法記錄給定二叉樹(shù)中的一度結(jié)點(diǎn)數(shù)目。四、應(yīng)用題1、對(duì)關(guān)鍵字無(wú)序序列(36，25，48，12，65，43，20，58)進(jìn)行直接選擇排序，請(qǐng)寫(xiě)出每一趟排序的結(jié)果。（10分）2、對(duì)無(wú)向帶權(quán)圖，用克魯斯卡爾算法構(gòu)造最小生成樹(shù)。（10分）20A3920A39D4FCB8D4FCB81E651E65G2G23、已知記錄關(guān)鍵字集合為（53,17,19,61,98,75,79,63,46,49）規(guī)定散列到地址區(qū)間（100,101,102,103,104,105,106,107,108,109）內(nèi)，若產(chǎn)生沖突用開(kāi)型尋址法的線(xiàn)性探測(cè)法解決。規(guī)定寫(xiě)出選用的散列函數(shù)；形成的散列表；計(jì)算出查找成功時(shí)平均查找長(zhǎng)度與查找不成功的平均查找長(zhǎng)度。（設(shè)等概率情況）4、設(shè)被查找文獻(xiàn)有4095個(gè)記錄，對(duì)每個(gè)記錄查找記錄概率相等，若采用順序查找，成功查找平均比較次數(shù)為多少？作業(yè)題（二）、單項(xiàng)選擇題1.有六個(gè)元素6，5，4，3，2，1的順序進(jìn)棧，問(wèn)下列哪一個(gè)不是合法的出棧序列？（）A.543612B.453126C.346521D.2341562.棧和隊(duì)都是（）A．順序存儲(chǔ)的線(xiàn)性結(jié)構(gòu)B.鏈?zhǔn)酱鎯?chǔ)的非線(xiàn)性結(jié)構(gòu)C.限制存取點(diǎn)的線(xiàn)性結(jié)構(gòu)D.限制存取點(diǎn)的非線(xiàn)性結(jié)構(gòu)3、順序查找法適合于存儲(chǔ)結(jié)構(gòu)為（）的線(xiàn)形表。A．散列存儲(chǔ) B．順序存儲(chǔ)或鏈接存儲(chǔ)C．壓縮存儲(chǔ) D．索引存儲(chǔ)4、分別以下列序列構(gòu)造二叉排序樹(shù)，與用其它三個(gè)序列所構(gòu)造的結(jié)果不同的是()。A．（100，80，90，60，120，110，130） B．（100，120，110，130，80，60，90）C．（100，60，80，90，120，110，130） D．(100，80，60，90，120，130，110)5、折半查找的平均比較次數(shù)為（）。A．n B．n/2C．log2n D．log2(n+1)6、當(dāng)在一個(gè)有序的順序存儲(chǔ)表上查找一個(gè)數(shù)據(jù)時(shí)，即可用折半查找，也可用順序查找，但前者比后者的查找速度（）A．必然快 B．不一定C．在大部分情況下要快 D．取決于表遞增還是遞減7、已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下圖如示。根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點(diǎn)v1出發(fā)，所得到的頂點(diǎn)序列是（）。A．v1，v2，v3，v5，v4 B．v1，v2，v3，v4，v5C．v1，v3，v4，v5，v2 D．v1，v4，v3，v5，v28、為了方便地對(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．s B．s-1C．s+1 D．n10、如圖所示，給出由7個(gè)頂點(diǎn)組成的無(wú)向圖。從頂點(diǎn)A出發(fā)，對(duì)它進(jìn)行深度優(yōu)先搜索得到的頂點(diǎn)序列是（）。A．AECDBFG B．AGBFDECC．ACEDBGF D．ABDGFEC二、填空題1.設(shè)n0為哈夫曼樹(shù)的葉子結(jié)點(diǎn)數(shù)目，則該哈夫曼樹(shù)共有________個(gè)結(jié)點(diǎn)。2.有數(shù)據(jù)WG={7，19，2，6，32，3，21，10}，則所建Huffman樹(shù)的樹(shù)高是________，帶權(quán)途徑長(zhǎng)度WPL為_(kāi)_______。3.設(shè)一棵完全二叉樹(shù)葉子結(jié)點(diǎn)數(shù)為k,最后一層結(jié)點(diǎn)數(shù)>2，則該二叉樹(shù)的高度為_(kāi)_______________。4.采用分塊查找時(shí)，若線(xiàn)性表中共有625個(gè)元素，查找每個(gè)元素的概率相同，假設(shè)采用順序查找來(lái)擬定結(jié)點(diǎn)所在的塊時(shí)，每塊應(yīng)分個(gè)結(jié)點(diǎn)最佳。5、設(shè)G為具有N個(gè)頂點(diǎn)的無(wú)向連通圖，則G中至少有條邊。6、哈夫曼樹(shù)（HuffmanTree）又稱(chēng)。它是n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹(shù)中，帶權(quán)途徑長(zhǎng)度WPL。7、樹(shù)的先序遍歷過(guò)程如下：若樹(shù)為空，則進(jìn)行空操作；若樹(shù)非空，則訪(fǎng)問(wèn)樹(shù)的；依次先序遍歷樹(shù)的。三、應(yīng)用題1、給定權(quán)值集合{1,4,2,6,9,},構(gòu)造相應(yīng)的哈夫曼樹(shù),并計(jì)算它的帶權(quán)途徑長(zhǎng)度。2、對(duì)關(guān)鍵字序列{10，6，3，2，5，4}，構(gòu)造一棵平衡二叉（排序）樹(shù)并畫(huà)圖（規(guī)定畫(huà)出建樹(shù)過(guò)程）。3、設(shè)有一個(gè)有序文獻(xiàn)，其中各記錄的關(guān)鍵字為（1，2，3，4，5，6，7，8，9，10，11，12，13，14，15），當(dāng)用折半查找算法查找關(guān)鍵字為3，8，19時(shí)，其比較次數(shù)分別為多少？4、對(duì)有五個(gè)結(jié)點(diǎn){A,B,C,D,E}的圖的鄰接矩陣，（1）．畫(huà)出邏輯圖；（2）．畫(huà)出圖的十字鏈表存儲(chǔ)；（3）．基于鄰接矩陣寫(xiě)出圖的深度、廣度優(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[i,j]，數(shù)組的每個(gè)元素長(zhǎng)度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內(nèi)存首地址BA開(kāi)始順序存放，當(dāng)用以列為主存放時(shí)，元素A[5，8]的存儲(chǔ)首地址為()。A.BA+141B.BA+180C.BA+222D.BA+2253．算法分析的兩個(gè)重要方面是（）。A．空間復(fù)雜性和時(shí)間復(fù)雜性B．對(duì)的性和簡(jiǎn)明性C．可讀性和文檔性D．?dāng)?shù)據(jù)復(fù)雜性和程序復(fù)雜性4．算法分析的目的是（）。A．找出數(shù)據(jù)結(jié)構(gòu)的合理性B．研究算法中的輸入和輸出的關(guān)系C．分析算法的效率以求改善D．分析算法的易懂性和文檔性5.下面程序段的時(shí)間復(fù)雜性的量極為（）。Intfun(intn){inti=1,s=1;While(s<n)S+=++I;ReturnI;}A．O(n/2)B．O(lbn)C．O(n)D．O()6.線(xiàn)性表是（）。A．一個(gè)有限序列，可認(rèn)為空B．一個(gè)有限序列，不能為空C．一個(gè)無(wú)限序列，可認(rèn)為空D．一個(gè)無(wú)限序列，不能為空7.帶頭結(jié)點(diǎn)的單鏈表L為空的鑒定條件是（）。A．L==NULLB．L-〉next==NULLC．L-〉next==LD．L!=NULL8.在一個(gè)長(zhǎng)度為n的線(xiàn)性表中，刪除值為x的元素時(shí)需要比較元素和移動(dòng)元素的總次數(shù)為（）。A．（n+1）/2B．n/2C．nD．n+19.一個(gè)順序存儲(chǔ)線(xiàn)性表的第一個(gè)元素的存儲(chǔ)地址是90，每個(gè)元素的長(zhǎng)度是2，則第6個(gè)元素的存儲(chǔ)地址是（）。A．98B．100C．102D．10610.假如某鏈表中最常用的操作是取第i個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用（）存儲(chǔ)方式最節(jié)省時(shí)間。A．單鏈表B．雙向鏈表C．單循環(huán)鏈表D．順序表二、填空題1.高度為2的二叉樹(shù)的結(jié)點(diǎn)數(shù)至少有________個(gè)，高度為3的二叉樹(shù)的結(jié)點(diǎn)數(shù)至少有________個(gè)。2.在順序表（8,11,15,19,25,26,30,33,42,48,50）中，用折半查找關(guān)鍵字值20，需做的關(guān)鍵字比較次數(shù)為_(kāi)_______。3.在有n個(gè)頂點(diǎn)的無(wú)向圖中，每個(gè)頂點(diǎn)的度最大可達(dá)________。4．已知廣義表A=（（a，b，c），（d，e，f）），則廣義表運(yùn)算head（tail（tail（A）））=。5、數(shù)組（Array）是n（n≥1）個(gè)的有序組合，數(shù)組中的數(shù)據(jù)是按順序存儲(chǔ)在一塊的存儲(chǔ)單元中。6.采用順序存儲(chǔ)結(jié)構(gòu)表達(dá)三元組表（TripleTable），來(lái)實(shí)現(xiàn)對(duì)稀疏矩陣的一種壓縮存儲(chǔ)形式，就稱(chēng)為，簡(jiǎn)稱(chēng)表。7.運(yùn)算是矩陣運(yùn)算中最基本的一項(xiàng)，它是將一個(gè)mxn的矩陣變成此外一個(gè)nxm的矩陣，同時(shí)使本來(lái)矩陣中元素的行和列的位置互換而值保持不變。三、應(yīng)用題1、對(duì)于下圖所示的二叉樹(shù)，畫(huà)出二叉鏈表存儲(chǔ)結(jié)構(gòu)圖。2、請(qǐng)畫(huà)出下圖所示的樹(shù)所相應(yīng)的二叉樹(shù)。AABCDE3.已知一個(gè)無(wú)向圖如下圖所示，規(guī)定分別用Prim和Kruskal算法生成最小樹(shù)（假設(shè)以①為起點(diǎn)，試畫(huà)出構(gòu)造過(guò)程）。4.已知完全二叉樹(shù)的第8層有8個(gè)結(jié)點(diǎn)，則其葉子結(jié)點(diǎn)是多少？5.畫(huà)出如圖所示中樹(shù)的二叉樹(shù)的表達(dá)形式。作業(yè)題（四）一、單項(xiàng)選擇題1.將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少得比較次數(shù)是（）。A．nB．2n-1C．2nD．n-12.一個(gè)有n個(gè)頂點(diǎn)的無(wú)向連通圖，它所包含的連通分量個(gè)數(shù)為（）。A．0 B．1C．n D．n+13.數(shù)據(jù)文獻(xiàn)的基本操作中最重要的操作是（）。A．插入 B．刪除C．修改 D．檢索4.對(duì)關(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個(gè)元素組成的序列中第5個(gè)最小元素之前的部分排序的序列，用（）方法最快。A．堆排序 B．快速排序C．插入排序 D．歸并排序6．算法分析的目的是（）。A．找出數(shù)據(jù)結(jié)構(gòu)的合理性B．研究算法中的輸入和輸出的關(guān)系C．分析算法的效率以求改善D．分析算法的易懂性和文檔性7.二叉樹(shù)的第I層上最多具有結(jié)點(diǎn)數(shù)為（）A．2IB．2I-1-1C．2I-1D．2I-18．循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A中，長(zhǎng)度為m，則入隊(duì)時(shí)的操作為（）。A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)9.廣義表滿(mǎn)足Head(A)=Tail(A)，則A為（）。A．（）B．（（））C．（（），（））D．（（），（），（））10.在一棵度為3的樹(shù)中，度為3的結(jié)點(diǎn)數(shù)為2個(gè)，度為2的結(jié)點(diǎn)數(shù)為1個(gè)，度為1的結(jié)點(diǎn)數(shù)為2個(gè)，則度為0的結(jié)點(diǎn)數(shù)為（）個(gè)。A．3B．4C．5D．6二、填空題1.在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的_________。2.數(shù)組中每一個(gè)數(shù)據(jù)通常稱(chēng)為，用下標(biāo)區(qū)分，其中下標(biāo)的個(gè)數(shù)由數(shù)組的決定。3.一個(gè)圖的表達(dá)法是唯一的，而表達(dá)法是不唯一的。4.在一個(gè)10階的B-樹(shù)上，每個(gè)數(shù)根結(jié)點(diǎn)中所含的關(guān)鍵字?jǐn)?shù)目最多允許個(gè)，最少允許個(gè)5.對(duì)關(guān)鍵字序列（52，80，63，44，48，91）進(jìn)行一趟快速排序之后的得到結(jié)果為。10.高度為1的平衡二叉樹(shù)的結(jié)點(diǎn)數(shù)至少有________個(gè)，高度為2的平衡二叉樹(shù)的結(jié)點(diǎn)數(shù)至少有________個(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ú)向圖的最小生成樹(shù)必是唯一的。（）4.B-樹(shù)和B+樹(shù)都可用于文獻(xiàn)的索引結(jié)構(gòu)。（）5.在用堆排序算法排序時(shí)，假如要進(jìn)行增序排序，則需要采用"大根堆"。（）四、應(yīng)用題1.模式串p="abaabcac"的next函數(shù)值序列為多少？2.設(shè)二維數(shù)組A[5][6]的每個(gè)元素占4個(gè)字節(jié)，已知LOC（a0,0）=1000，A共占多少個(gè)字節(jié)？A的終端結(jié)點(diǎn)a4,5的起始地址為多少？按行和按列優(yōu)先存儲(chǔ)時(shí)，a2,5的起始地址分別為多少？3.設(shè)a,b,c,d,e五個(gè)字符的編碼分別為1,2,3,4,5，并設(shè)標(biāo)記符依以下順序出現(xiàn)：ac,bd,aa,be,ab,ad,cd,bc,ae,ce。規(guī)定用哈希（Hash）方法將它們存入具有10個(gè)位置的表中。（1）將上述關(guān)鍵字（標(biāo)記符）構(gòu)造一個(gè)哈希函數(shù)，使得發(fā)生沖突盡也許地少；（2）線(xiàn)性探測(cè)再散列法解決沖突。寫(xiě)出上述各關(guān)鍵字在表中位置。4.給定一個(gè)關(guān)鍵字序列{24，19，32，43，38，6，13，22}，請(qǐng)寫(xiě)出快速排序第一趟的結(jié)果；堆排序時(shí)所建的初始堆；歸并排序的全過(guò)程。然后回答上述三中排序方法中那一種方法使用的輔助空間最少？在最壞情況下那種方法的時(shí)間復(fù)雜度最差？作業(yè)題（五）一、單項(xiàng)選擇題1.一組記錄的關(guān)鍵碼為（46，79，56，38，40，84），則運(yùn)用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(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(GetTail(GetHead(GetTail(GetTail(A)))))A.(g)B.(d)C.cD.d3．對(duì)于有n個(gè)結(jié)點(diǎn)的二叉樹(shù),其高度為（）A．nlog2nB．log2nC．?log2n?+1D．不擬定4.如圖所示，給出由7個(gè)頂點(diǎn)組成的無(wú)向圖。從頂點(diǎn)1出發(fā)，對(duì)它進(jìn)行深度優(yōu)先搜索得到的頂點(diǎn)序列是（）。A．1354267 B．1347625C．1534276 D．12476535.采用鄰接表存儲(chǔ)的圖，其深度優(yōu)先遍歷類(lèi)似于二叉樹(shù)的（）。A．中序遍歷 B．先序遍歷C．后序遍歷 D．按層次遍歷6.已知有向圖G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓?fù)湫蛄惺牵ǎ?。A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V77.順序查找法合用于查找順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)的線(xiàn)性表，平均比較次數(shù)為（）。在此假定N為線(xiàn)性表中結(jié)點(diǎn)數(shù)，且每次查找都是成功的。A．N+1 B．2log2NC．log2N D．N8.下面關(guān)于m階B樹(shù)說(shuō)法對(duì)的的是（）。①每個(gè)結(jié)點(diǎn)至少有兩棵非空子樹(shù)；②樹(shù)中每個(gè)結(jié)點(diǎn)至多有m一1個(gè)關(guān)鍵字；③所有葉子在同一層上；④當(dāng)插入一個(gè)數(shù)據(jù)項(xiàng)引起B(yǎng)樹(shù)結(jié)點(diǎn)分裂后，樹(shù)長(zhǎng)高一層。A．①②③ B．②③C．②③④ D．③9.已知一個(gè)線(xiàn)性表（38，25，74，63，52，48），假定采用h(k)=k%7計(jì)算Hash地址進(jìn)行散列存儲(chǔ)，若運(yùn)用鏈地址法解決沖突，則在該Hash表上進(jìn)行查找的平均查找長(zhǎng)度為（）。A．1.0 B．7/6C．4/3 D．3/210.在排序算法的實(shí)行過(guò)程中，使用輔助存儲(chǔ)空間為O（1）的有（）。A．簡(jiǎn)樸排序法 B.快速排序法C．歸并排序法 D.基數(shù)排序法二、填空題1.n（n大于1）個(gè)結(jié)點(diǎn)的各棵樹(shù)中，其中深度最大的那棵樹(shù)的深度是n，它共有________個(gè)葉子結(jié)點(diǎn)和________個(gè)非葉子結(jié)點(diǎn)。2.設(shè)一棵后序線(xiàn)索樹(shù)的高是50，結(jié)點(diǎn)x是樹(shù)中的一個(gè)結(jié)點(diǎn)，其雙親是結(jié)點(diǎn)y,y的右子樹(shù)高度是60，x是y的左孩子。則擬定x的后繼最多需通過(guò)________中間結(jié)點(diǎn)（不含后繼及x自身）3.高度為2（第2層為葉子）的3階B-樹(shù)中，最多有________個(gè)關(guān)鍵字。4.分別采用堆排序，快速排序，冒泡排序和歸并排序，對(duì)初態(tài)為無(wú)序的表，則平均情況下最省時(shí)間的是________算法。5.簡(jiǎn)樸選擇排序和起泡排序中比較次數(shù)與序列初態(tài)無(wú)關(guān)的算法有________。6.串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是將存儲(chǔ)區(qū)域提成一系列大小相同的結(jié)點(diǎn),每個(gè)結(jié)點(diǎn)有兩個(gè)域域和域。其中域用于用于存放數(shù)據(jù)，域用于存放下一個(gè)結(jié)點(diǎn)的指針三．判斷1.順序存儲(chǔ)的線(xiàn)性表可以隨機(jī)存取。（）2.即使對(duì)不含相同元素的同一輸入序列進(jìn)行兩組不同的、合法的入棧和出棧組合操作，所得的輸出序列也一定相同。（）3.十字鏈表是無(wú)向圖的一種存儲(chǔ)結(jié)構(gòu)。（）4.折半查找方法合用于排列連續(xù)順序文獻(xiàn)的查找。（）5.在執(zhí)行某個(gè)排序算法過(guò)程中，出現(xiàn)了排序碼朝著最終排序序列位置相反方向移動(dòng)，則該算法是不穩(wěn)定的。（）四、應(yīng)用題1.用十字鏈表表達(dá)一個(gè)有k個(gè)非零元素的mxn的稀疏矩陣，則其總的結(jié)點(diǎn)數(shù)為多少？2.G=(V,E)是一個(gè)帶有權(quán)的連通圖,則：（1）．請(qǐng)回答什么是G的最小生成樹(shù)；（2）．G為下圖所示,請(qǐng)找出G的所有最小生成樹(shù)。3.請(qǐng)分別敘述在一個(gè)連續(xù)順序文獻(xiàn)中采用順序查找法，折半查找法和分塊查找法查找一個(gè)記錄，該文獻(xiàn)中記錄應(yīng)當(dāng)滿(mǎn)足什么條件？4.設(shè)待排序文獻(xiàn)之排序碼為（88，33，22，55，99，11，66），采用順序存儲(chǔ)。請(qǐng)用直接選擇排序算法對(duì)上述文獻(xiàn)進(jìn)行排序，用圖示說(shuō)明排序過(guò)程。東北農(nóng)業(yè)大學(xué)網(wǎng)絡(luò)教育學(xué)院數(shù)據(jù)結(jié)構(gòu)專(zhuān)升本作業(yè)題參考答案作業(yè)題一參考答案：一、單項(xiàng)選擇題1、C2、B3、D4、C5、B6、B7、A8、C9、D10、D二、填空題1、非零元很少2、操作受限（或限定僅在表尾進(jìn)行插入和限定僅在表頭進(jìn)行刪除操作或限制存取點(diǎn)或特殊），先進(jìn)先出(或后進(jìn)后出)3、簡(jiǎn)樸選擇排序4、O(n2)，O(e)，O(n)5、鄰陣矩陣，鄰接表三、算法答：intcount=0;voidonechild(Btreet){if(t!=NULL){onechild(t->lchild);onechild(t->rchild);if(t->lchild!=NULL&&(t->rchild!=NULL||t->lchild!=NULL&&t->rchild==NULL)count++;}}四、應(yīng)用題1、答：2、答：（1） （2）CC11C11C2FGGG3AD3AD3AD11C2FG1C1C4422FG（5） （6）33ADEBEB561C61C441CB543A1CB543AD2FG2FG 3、答：由于地址空間為10，且從100開(kāi)始，故散列函數(shù)選為H（key）=key%7+100。用線(xiàn)性探測(cè)再散列解決沖突，ASLsucc=27/104、答：成功查找平均比較查找長(zhǎng)度為：（n+1）/n[log2（n+1）]-1。作業(yè)題二參考答案：一、單項(xiàng)選擇題1、C2、C3、B4、C5、D6、C7、C8、B9、A10、C二、填空題1、2n0-12、6，2613、élog2kù+14、255、N-16、最優(yōu)二叉樹(shù)，最小的二叉樹(shù)7、根結(jié)點(diǎn)，各子樹(shù)三、應(yīng)用題 1、41241263713922此樹(shù)的帶權(quán)途徑長(zhǎng)度WPL=9*1+6*2+4*3+(1+2)*4=452、答：6（1）插入10 (2)插入6 (3)插入3 (4)61010 1010103調(diào)整610103調(diào)整61066 （5）插入2 （6）插入5 （7）插入4 （8）65365324101063210632調(diào)整106325調(diào)整106325553、答：當(dāng)關(guān)鍵字為3時(shí)，比較次數(shù)為4；當(dāng)關(guān)鍵字為8時(shí)，比較次數(shù)為1；當(dāng)關(guān)鍵字為19時(shí)，查找不成功；4、答：（2）略（3）深度優(yōu)先遍歷序列：ABCDE廣度優(yōu)先遍歷序列：ABCED（4）關(guān)鍵途徑A--B（長(zhǎng)100）作業(yè)題三參考答案：一、單項(xiàng)選擇題1、D2、B3、A4、C5、D6、A7、B8、C9、B10、D二、填空題1、2，32、43、n-14、e5、相同類(lèi)型數(shù)據(jù)，地址連續(xù)6.三元組順序表，三元組7.矩陣轉(zhuǎn)置三、應(yīng)用題1、答： 二叉鏈表∧∧∧∧∧∧∧∧∧∧⑧⑨⑦⑥⑤④③②① ∧∧∧∧∧∧∧∧∧∧⑧⑨⑦⑥⑤④③②① (2 2、答：A ACDBCDB EE 3.答：Prim算法構(gòu)造最小生成樹(shù)的環(huán)節(jié)如24題所示，為節(jié)省篇幅，這里僅用Kruskal算法，構(gòu)造最小生成樹(shù)過(guò)程如下：（下圖也可選(2,4)代替(3,4),(5,6)代替(1,5)）即：4.答：由完全二叉樹(shù)的定義可知，除最后一層外，其他各層的結(jié)點(diǎn)是滿(mǎn)的。設(shè)該完全二叉樹(shù)有d層，則除最后一層外各層的結(jié)點(diǎn)個(gè)數(shù)分別為：1，2，4，8，16，32，…，即第i層的結(jié)點(diǎn)個(gè)數(shù)為2i-1。這里第8層有8個(gè)結(jié)點(diǎn)，顯然第8/層是最后的一層，那么第7層的結(jié)點(diǎn)個(gè)數(shù)為27-1=64個(gè)，其中的4個(gè)結(jié)點(diǎn)有8個(gè)葉子結(jié)點(diǎn)，余下的為葉子結(jié)點(diǎn)，個(gè)數(shù)為64-4=60，所以該完全二叉樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)為60+8=68個(gè)。5.答：相應(yīng)的二叉樹(shù)形式如圖所示：作業(yè)題四參考答案：一、單項(xiàng)選擇題1.A