數(shù)據(jù)結(jié)構(gòu)習(xí)題集

PAGEPAGE9數(shù)據(jù)結(jié)構(gòu)習(xí)題集第一章緒論1.1數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的數(shù)據(jù)元素以及它們之間的關(guān)系和運(yùn)算等的學(xué)科。1.2算法分析的目的是分析算法的效率以求該進(jìn)，算法分析的兩個(gè)主要方面是空間復(fù)雜度和時(shí)間復(fù)雜度。1.3計(jì)算機(jī)算法指的是解決問題的有限運(yùn)算序列，它必須具備輸入、輸出和確定性、有窮性和可行性等5個(gè)重要特性。第二章線性表2.32下面關(guān)于線性表的敘述中，錯(cuò)誤的是（B）A.線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)單元B.線性表采用順序存儲(chǔ)便于進(jìn)行插入和刪除操作C.線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)單元D.線性表采用鏈?zhǔn)酱鎯?chǔ)便于進(jìn)行插入和刪除操作第三章棧與隊(duì)列一、選擇題3.1棧的特點(diǎn)是先進(jìn)后出，隊(duì)列的特點(diǎn)是先進(jìn)先出。3.4判定一個(gè)棧ST（最多元素MaxSize）為空的條件是ST->top==-1。3.8一個(gè)隊(duì)列的入隊(duì)序列是1，2，3，4，則出隊(duì)列的輸出序列是1，2，3，4。3．16一個(gè)隊(duì)列的入隊(duì)序列是1，2，3，4，則隊(duì)列的輸出序列是1,2,3,4。3.18若進(jìn)棧序列為1，2，3，4，，進(jìn)棧過程中可以出棧，則以下不可能的出棧序列是3，1，4，23.1棧和隊(duì)列的區(qū)別僅在于____。3.2通常元素進(jìn)棧的操作是____。3.3通常元素退棧的操作是____。3.4一個(gè)棧的輸入序列是12345，則棧的輸出序列43512是____。3.5一個(gè)棧的輸入序列是12345，則棧的輸出序列12345是____。第四章串4.1串是一種特殊的線形表，其特殊性體現(xiàn)在___B_A.可以順序存儲(chǔ)B.數(shù)據(jù)元素是一個(gè)字符C.可以鏈接存儲(chǔ)D.數(shù)據(jù)元素可以是多個(gè)字符4.2串的兩種最基本的存儲(chǔ)方式是順序和鏈?zhǔn)健?.3兩個(gè)串相等的充分必要條件是:長(zhǎng)度相等且對(duì)應(yīng)位置上的字符相等。4.4空串是____，其長(zhǎng)度等于____.4.5串的三種機(jī)內(nèi)表示方法是________、________、和___________。4.6如下陳述中正確的是___A___。A．串是一種特殊的線性表

B．串的長(zhǎng)度必須大于零

C．串中元素只能是字母

D．空串就是空白串

4.7串是一種特殊的線性表，其特殊性表現(xiàn)在（）A.串中允許有空串B.串可以順序存儲(chǔ)C.串可以鏈?zhǔn)酱鎯?chǔ)D.數(shù)據(jù)元素是一個(gè)字符4.8不含任何字符的串稱為空串,其長(zhǎng)度為長(zhǎng)度等于零0。4.9設(shè)有字符串S=“ABC123XYZ”，問該串的長(zhǎng)度為（A）A.9B.10C.11D.124.10設(shè)有字符串S=“windows”，其子串的數(shù)目是（）A.25個(gè)B.26個(gè)C.27個(gè)D.28個(gè)4.11假設(shè)有兩個(gè)字符串S1和S2，其中S1=”ABCDXYZ”,S2=”REST”，那么如果進(jìn)行了下面的運(yùn)算StrCat(SubStr(S1,3,2),SubStr(S1,StrLen(S2)，3))，其結(jié)果應(yīng)是（）A.“CDXYZ”B.“CDDXY”C.“CDREST”D.“CDRES”第五章數(shù)組5.1二維數(shù)組M的成員是6個(gè)字符（每個(gè)字符占一個(gè)字節(jié)）組成的串，行下標(biāo)i的范圍從0到8，列下標(biāo)j的范圍從1到10，則存放M至少需要___①__個(gè)字節(jié)；M的第8列和第5行共占__②__個(gè)字節(jié)；若M按行優(yōu)先式存儲(chǔ)，元素M[8][5]的起始地址與當(dāng)M按列優(yōu)先方式存儲(chǔ)時(shí)的__③__元素的起始地址一致。①A.90B.180C.240D.540②A.108B.114C.54D.60③A.M[8][5]B.M[3][10]C.M[5][8]D.M[0][9]5.2數(shù)組A中，每個(gè)元素A的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)，元素A[8][5]的起始地址為____。A．SA+141B．SA+144C．SA+222D．SA+2255.3數(shù)組A中，每個(gè)元素A的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按列存放時(shí)，元素A[5][8]的起始地址為____。A．SA+141B．SA+180C．SA+222D．SA+2255.4設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a1，1為第一個(gè)元素，其存儲(chǔ)地址為1，每個(gè)元素占1個(gè)地址空間，則a8，5的地址為____。A.13B.33C.18D.405.5一個(gè)n*n的對(duì)稱矩陣，如果以行或列為主序放入內(nèi)存，則容量為____。A.n*nB.n*n/2C.n*（n+1）/2D.（n+1）*（n+1）/25.6稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即____。A.二維數(shù)組和三維數(shù)組B.三元組和散列C.三元組和十字鏈表D.散列和十字鏈表5.7已知二維數(shù)組A[m][n]采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占k個(gè)存儲(chǔ)單元，并且第一個(gè)元素的存儲(chǔ)地址是LOC（A[0][0]），則A[i][j]的地址是loc(a[0][0]+(n*i+j)*k。5.8二維數(shù)組A[10][20]采用以行為主序的方式存儲(chǔ)，每個(gè)元素占4個(gè)存儲(chǔ)單元，并且A[0][0]的存儲(chǔ)地址是200，則A[6][12]的地址是____。5.9二維數(shù)組A[10..20][5..10]采用以列為主序的方式存儲(chǔ)，每個(gè)元素占4個(gè)存儲(chǔ)單元，并且A[10][5]的存儲(chǔ)地址是1000，則A[18][9]的地址是____。5.10有一個(gè)10階對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式（以行序?yàn)橹鞔鎯?chǔ)，且A[0][0]=1），則A[8][5]的地址是____。5．11二維數(shù)組可看成是這樣一個(gè)線性表：它的每個(gè)數(shù)據(jù)元素都是一個(gè)。其中任一數(shù)據(jù)元素即可以是一個(gè)的線性表，也可以是一個(gè)的線性表。5.12二維數(shù)組有兩種存儲(chǔ)方式，第一種是以行為主序的存儲(chǔ)方式，第二種是以列為主序的存儲(chǔ)方式。在一個(gè)6行5列的二維數(shù)組中，假設(shè)第一個(gè)元素的存儲(chǔ)地址是1000，每個(gè)元素占2個(gè)存儲(chǔ)單元，則在第一種存儲(chǔ)方式下，第4行第3列元素的存儲(chǔ)地址為__________。5．13假如某矩陣多為零元素，且零元素分布沒有任何規(guī)律，則此矩陣稱為。5．14若矩陣中的非零元素只在矩陣的左下三角出現(xiàn)(包括對(duì)角線)，而右上三角中均為零元素，此矩陣稱為，若對(duì)該矩陣進(jìn)行壓縮存儲(chǔ)，采用以為主序的壓縮存儲(chǔ)方式，訪問矩陣元素時(shí)，下標(biāo)計(jì)算比較方便。在該存儲(chǔ)方式下訪問矩陣元素aij的公式是。5．15對(duì)稱陣的壓縮存儲(chǔ)一般采用以主序壓縮存儲(chǔ)方式，存儲(chǔ)其下三角，此時(shí)訪問矩陣元素aij的公式為。5．16對(duì)于稀疏矩陣的壓縮存儲(chǔ)，通常用一個(gè)三元組表示非零元素的信息，其中包括非零元素的值、行、列。這些信息可用一個(gè)三元組數(shù)組表示，也稱此為三元組順序表。5.17設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹餍虼鎯?chǔ)，a0,0為第一個(gè)元素，其存儲(chǔ)地址為1，每個(gè)元素占1個(gè)字節(jié)，則a8,5的地址為__B_____。A.13B.33C.18D.425.18數(shù)組是相同類型值的集合（）5.19設(shè)有二維數(shù)組A[10][20]，其中每個(gè)元素占2個(gè)字節(jié)，數(shù)組按行優(yōu)先順序存儲(chǔ)，第一個(gè)元素的存儲(chǔ)地址為100，那么元素A[8][12]的存儲(chǔ)地址為（D）100+（20*8+12）*2A．262B．284C．402D.4445.20設(shè)有一個(gè)10階的對(duì)稱矩陣A采用壓縮存儲(chǔ)方式，以行優(yōu)先順序存儲(chǔ)a11位第一個(gè)元素，其存儲(chǔ)地址為1，且每一個(gè)元素占1個(gè)地址空間，則a75的地址為（）A.26B.17C.33D.235.21設(shè)有二維數(shù)組A[10][10]，其每個(gè)元素占2個(gè)字節(jié)，數(shù)組按列優(yōu)先順序存儲(chǔ)，第一個(gè)元素的存儲(chǔ)地址為100，那么元素A[6][6]的存儲(chǔ)地址為_____。第六章樹與二叉樹6.1采用二叉鏈表存儲(chǔ)結(jié)構(gòu),具有n個(gè)結(jié)點(diǎn)的二叉樹中,一共有__2n___個(gè)指針域,其中有n+1個(gè)指針域?yàn)榭?有n-1個(gè)指針域指向孩子結(jié)點(diǎn)6.2一棵非空二叉樹,其第i層上最多有2的i次方-1結(jié)點(diǎn)。2的1次方-16.3滿二叉樹是一棵深度為k且恰有2的k次方-1結(jié)點(diǎn)的二叉樹.6.4森林的前序遍歷序列等同于該森林對(duì)應(yīng)的二叉樹的________遍歷序列.6.5一棵哈夫曼樹有個(gè)m葉子結(jié)點(diǎn),則其結(jié)點(diǎn)總數(shù)為2m-1.6.6將一棵完全二叉樹按層次編號(hào),對(duì)任一編號(hào)為i的結(jié)點(diǎn)有:如有左孩子,則其編號(hào)為2i;如有右孩子,則其編號(hào)為2i+1.6.7一棵深度為5的二叉樹最多有____結(jié)點(diǎn)，最少有____結(jié)點(diǎn)。6.8樹最適合用來表示__C_。A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.數(shù)據(jù)之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)6.9在下列存儲(chǔ)形式中，不是樹的存儲(chǔ)形式的是_C__。A．雙親表示法B.孩子表示法C.孩子雙親表示法D.孩子兄弟表示法6.10在線索化二叉樹中，t所指結(jié)點(diǎn)沒有左子樹的充要條件____。A.t->left==NULLB.t->ltag==1C.t->ltag==1且t->left=NULLD.以上都不對(duì)6.11設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為____。A.2hB.2h-1C.2h+1D.h+16.12一棵高度為h的滿二叉樹中結(jié)點(diǎn)的個(gè)數(shù)為_B_。A.2hB.2h-1C.2h-1D.2h+16.13已知一棵二叉樹的先序遍歷序列為ABCDEFG,中序遍歷序列為:CBDAFEG,則該二叉樹的后序遍歷序列是(A)．A．CDBFGEAB．CDFGBEAC．CDBAFGED．CDBFEGA6.14設(shè)電文中出現(xiàn)的字母為Ａ，Ｂ，Ｃ，Ｄ，Ｅ，每一個(gè)字母在電文中出現(xiàn)的次數(shù)分別為6、23、3、5、12，按哈夫曼編碼，則字母Ｃ的編碼應(yīng)是（）A．10B．110C．1110D．11116.15樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里，我們把由樹轉(zhuǎn)化得到二叉樹叫做這棵樹對(duì)應(yīng)的二叉樹。結(jié)論____是正確的。A．樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹先序遍歷序列相同B．樹的后根遍歷序列與其對(duì)應(yīng)的二叉樹后序遍歷序列相同C．樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹中序遍歷序列相同D．以上都不對(duì)6.16已知一棵二叉樹的先序遍歷序列為EFHIGJK,中序遍歷序列為:HFIEJGK,則該二叉樹的右子樹的根是()．A．ＥB．ＦC．ＧD．Ｊ6.17線索二叉樹是一種____結(jié)構(gòu)A.邏輯B.邏輯和存儲(chǔ)C.物理D.線性6.18如下左圖所示二叉樹的中序遍歷序列是_B__abcdgefB.dfebagcC.dbaefcgD.defbagc6.19一棵二叉樹如上右圖所示，其中序遍歷的序列為_B__A．a(chǎn)bdgcefhB．dgbaechfC．gdbehfcaD．a(chǎn)bcdefgh6.20在非空二叉樹的中序遍歷序列中，二叉樹的根結(jié)點(diǎn)的左邊應(yīng)該(B)A.只有左子樹上的所有結(jié)點(diǎn)B.只有左子樹上的部分結(jié)點(diǎn)C.只有右子樹上的所有結(jié)點(diǎn)D.只有右子樹上的部分結(jié)點(diǎn)6.21在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊應(yīng)該_B_。A.只有右子樹上的所有結(jié)點(diǎn)B.只有右子樹上的部分結(jié)點(diǎn)C.只有左子樹上的部分結(jié)點(diǎn)D.只有左子樹上的所有結(jié)點(diǎn)6.22有一棵樹如下左圖所示，回答下列問題：⑴這棵樹的根結(jié)點(diǎn)是K1;⑵這棵樹的葉子結(jié)點(diǎn)是K2,K4,K5,K7⑶結(jié)點(diǎn)k3的度為2;⑷這棵樹的度為3⑸這棵樹的深度為4;⑺結(jié)點(diǎn)k3的孩子結(jié)點(diǎn)是K5,K6⑻結(jié)點(diǎn)k3的雙親結(jié)點(diǎn)是K16.23由上右圖所示的二叉樹，回答以下問題。⑴其中序遍歷序列為____⑵其先序遍歷序列為____⑶其后序遍歷序列為____⑷該二叉樹的中序線索二叉樹為____⑸該二叉樹對(duì)應(yīng)得森林是____6.24指出樹和二叉樹的三個(gè)主要差別____，____，____。6.25在一棵二叉樹中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2，則有n0=____。6.26一棵二叉樹的第i（i＞=1）層最多有____個(gè)結(jié)點(diǎn)；一棵有n（n＞0）個(gè)結(jié)點(diǎn)的滿二叉樹共有____個(gè)葉子節(jié)點(diǎn)和____個(gè)非葉子結(jié)點(diǎn)。6.27如果某二叉樹的先序遍歷為stuwv,中序遍歷序列為uwtvs,請(qǐng)畫出該二叉樹并給出該二叉樹的后序遍歷序列。6.28某二叉樹的先序遍歷序列為abdgcefh,中序遍歷序列是dgbaechf,請(qǐng)畫出該二叉樹并給出其后序遍歷序列。gdbehfca6.29有一份電文中共使用5個(gè)字符：a,b,c,d,e,他們的出現(xiàn)頻率依次為4，7，5，2，9，試畫出對(duì)應(yīng)的哈夫曼樹（請(qǐng)安左子樹根結(jié)點(diǎn)的權(quán)小于等于右子樹根結(jié)點(diǎn)的權(quán)的次序構(gòu)造），并求出每個(gè)字符的哈夫曼編碼。6.30設(shè)給定權(quán)集W={2，3，4，7，8，9}，試構(gòu)造關(guān)于w的一棵哈夫曼樹，并求其加權(quán)路徑長(zhǎng)度WPL.6.31如下左圖所示,以數(shù)據(jù)集{4，5，6，7，10，12，18}為結(jié)點(diǎn)權(quán)值所構(gòu)成的哈夫曼樹為二叉樹，其帶權(quán)路徑長(zhǎng)度為165。6.32對(duì)如上右圖所示的樹，該樹的高度為__________，該樹的度為__________，結(jié)點(diǎn)E的層次為__________，結(jié)點(diǎn)H的雙親為__________，結(jié)點(diǎn)H的兄弟為__________，結(jié)點(diǎn)B的度為__________。6.33若二叉樹中度為2的結(jié)點(diǎn)有15個(gè)，該二叉樹則有16個(gè)葉結(jié)點(diǎn)。6.34若深度為6的完全二叉樹的第6層有3個(gè)葉結(jié)點(diǎn)，則該二叉樹一共有34個(gè)結(jié)點(diǎn)。6.35若某完全二叉樹的深度為h，則該完全二叉樹中至少有______個(gè)結(jié)點(diǎn)。6.36二叉樹的前序遍歷序列為A，B，C，E，F(xiàn)，D，G，H，中序遍歷序列為A，E，C，F(xiàn)，B，G，D，H，其后序遍歷序列為。6.37若二叉樹中葉子結(jié)點(diǎn)數(shù)為20個(gè)，則該二叉樹有__________個(gè)度為2的結(jié)點(diǎn)。6.38深度為h且有2的k次方-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。6.39一棵含180個(gè)結(jié)點(diǎn)的二叉樹的高度至少為___________。6.40用樹中空的指針指向該結(jié)點(diǎn)的前趨結(jié)點(diǎn)，空的指針指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)，我們稱這種專門的指針為線索.6.41一個(gè)深度為k的二叉樹，當(dāng)具有2k-1個(gè)結(jié)點(diǎn)時(shí)稱之為__________。6.42下面關(guān)于哈夫曼樹的說法，不正確的是(D)A.對(duì)應(yīng)于一組權(quán)值構(gòu)造出的哈夫曼樹一般不是唯一的B.哈夫曼樹具有最小帶權(quán)路徑長(zhǎng)度C.哈夫曼樹中沒有度為1的結(jié)點(diǎn)D.哈夫曼樹中除了度為1的結(jié)點(diǎn)外，還有度為2的結(jié)點(diǎn)和葉結(jié)點(diǎn)6.43對(duì)于含有n個(gè)結(jié)點(diǎn)的二叉樹，若采用二叉鏈表結(jié)構(gòu)來存儲(chǔ)它，則含有__________個(gè)空指針域A.n+1B.n-1C.nD.不確定6.44具有100個(gè)結(jié)點(diǎn)的完全二叉樹，其中含有__________個(gè)度為1的結(jié)點(diǎn)。A.1B.0C.2D.不確定6.45已知某二叉樹的先序遍歷序列為A，B，D，G，C，E，F(xiàn)，H，中序遍歷序列為D，G，B，A，E，C，H，F(xiàn)。請(qǐng)畫出該二叉樹并寫出后根遍歷序列。6.48設(shè)二叉樹根結(jié)點(diǎn)的層次為1，一棵深度為h的滿二叉樹中的結(jié)點(diǎn)個(gè)數(shù)是（）A．2hB.2h-1C.2h-1D.2h+16.49設(shè)有一棵二叉樹，其1度結(jié)點(diǎn)有m個(gè)，2度結(jié)點(diǎn)有n個(gè)，則該二叉樹的結(jié)點(diǎn)總數(shù)為（）A．m+nB.2*m+nC.m+2*nD.m+2*n+16.50設(shè)電文中出現(xiàn)的字母為A，B，C，D和E，每個(gè)字母在電文中出現(xiàn)的次數(shù)分別是6，23，3，5，和12，按哈夫曼編碼，則字母C的編碼應(yīng)是（）A．10B.110C.1110D.11116.51已知一棵二叉樹的先序遍歷序列為EFHIGJK，中序遍歷序列為FIEJGK，則該二叉樹根的右子樹的根是（）。A．EB.FC.GD.J6.52如果對(duì)給定的一組數(shù)值，能夠構(gòu)造出帶權(quán)路徑長(zhǎng)度最小的二叉樹，則該樹稱為_______________。6.53在下列存儲(chǔ)形式中，不是樹的存儲(chǔ)形式的是（）A．雙親表示法B．孩子鏈表表示法C．孩子兄弟鏈表表示法D．順序存儲(chǔ)表示法6.54采用二叉鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，具有n個(gè)結(jié)點(diǎn)的二叉樹中，一共有_____個(gè)指針域，其中_____個(gè)指針域?yàn)榭铡?.55一棵非空的二叉樹，其第i層上最多有_____個(gè)結(jié)點(diǎn)。6.56滿二叉樹是一棵深度為k的且恰好有_____個(gè)結(jié)點(diǎn)的二叉樹。6.57森林的前序遍歷序列等同于該森林對(duì)應(yīng)的二叉樹的_____遍歷序列。6.58設(shè)一棵哈夫曼樹有m個(gè)葉子結(jié)點(diǎn)，則其結(jié)點(diǎn)總數(shù)為_____。6.59將一棵完全二叉樹按層次編號(hào)，對(duì)任一編碼為i的結(jié)點(diǎn)有：如該結(jié)點(diǎn)有左孩子，則其編號(hào)為_____。如該結(jié)點(diǎn)有右孩子，則其編碼是_____。6.60在如圖所示的表達(dá)式二叉樹中，按中序遍歷得到的序列為__________。第八章查找8.1用順序查找法在具有ｎ各結(jié)點(diǎn)的線性表中查找一個(gè)結(jié)點(diǎn)所需的平均查找時(shí)間為（C）。ＡＯ(n)B.O(nlog2n)C.O(n)D.O(log2n)8.2使用折半查找，線性表必須（D）。Ａ、一順序方式存儲(chǔ)Ｂ、以鏈?zhǔn)椒绞酱鎯?chǔ)，且元素已按值排好序Ｃ、以鏈?zhǔn)椒绞酱鎯?chǔ)Ｄ、以順序方式存儲(chǔ)，且元素已按值排好序8.3采用折半查找算法搜索一個(gè)線性表時(shí)，此線性表必須是__[1]____8.4順序查找法適合于存儲(chǔ)結(jié)構(gòu)為_B_的線性表。A．散列存儲(chǔ)B.順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)C.壓縮存儲(chǔ)D.索引存儲(chǔ)8.5對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須為____。A.以順序方式存儲(chǔ)B.以鏈接方式存儲(chǔ)C.以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列D.以鏈接方式存儲(chǔ)且結(jié)點(diǎn)按關(guān)鍵字有序排列8.6采用順序查找法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為_C_。A.nB.n/2C.（n+1）/2D.(n-1)/28.7采用折半查找法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為_D_。A.O(n2)B.O(nlog2n)C.O(n)D.O(log2n)8.9在n個(gè)記錄的有序順序表中進(jìn)行折半查找，最大的比較次數(shù)是____。8.10折半查找的存儲(chǔ)結(jié)構(gòu)僅限于____，且是____。8.11在分塊查找方法中首先查找____，然后在查找相應(yīng)的____。8.12已有序表為（20，18，24，35，47，50，62，83，90，115，134），當(dāng)用折半法查找90時(shí)，需要進(jìn)行____次查找可確定成功。查找47時(shí)需進(jìn)行____次查找可確定成功，查找100時(shí)，需進(jìn)行____次查找才能確定不成功。8.13若按查找目的分類,查找可分為______________、______________；對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須_____________且為______________存儲(chǔ)結(jié)構(gòu)。8.14有一個(gè)有序表為：(1,3,9,12,32,41,45,62,75,77,82,95,100),當(dāng)折半查找值82的結(jié)點(diǎn)時(shí)，經(jīng)過__C__次比較后查找成功。A.1B.2C.4D.88．15折半查找有序表{6,15,30,37,65,70,72,89,99},若要查找元素37，需要依次與表中元素__D__進(jìn)行比較。A.65，15，37B.68，30，37C.65，15，30D.65，15，30，37第九章排序9.1對(duì)于給定的12個(gè)整數(shù)：23，37，7，79，29，43，73，19，31，61，23，47，分別寫出用直接插入排序、冒泡排序和直接選擇排序的各趟結(jié)果。9.2一個(gè)有序序列中，隨機(jī)插入一個(gè)元素，即該元素的位置是隨機(jī)的，這是采用什么排序方法對(duì)其排序，效率較高（）A直接插入B直接選擇C冒泡D快速9.3排序算法__[1]___和__[2]__。9.4排序算法的穩(wěn)定性是指__[1]__相同的紀(jì)錄經(jīng)過排序后的_[2]_是否發(fā)否發(fā)生變化，永不發(fā)生變化的排序算法，就是_[3]__;否則就是_[4]__。9.5排序算法的基本操作是__[1]__和__[2]__。9.6排序算法的____取決于關(guān)鍵字的比較和記錄的移動(dòng)等基本操作的次數(shù)。9.7排序算法的空間效率取決于算法所占用的_____的大小。9.8假設(shè)待排序數(shù)據(jù)元素排列為[3，1，4，2，6]，應(yīng)用快速排序方法按遞增序排序，得到第一次劃分的結(jié)果為_____。9.9設(shè)關(guān)鍵字序列｛１７，８，３，２５，１６，１，１３，１９，１８，４，６，２４｝，用希爾排序法按遞增序排序，用初始增量４進(jìn)行一遍掃描的結(jié)果為______。9.10假設(shè)待排序數(shù)據(jù)元素序列為[４，５，３，２，１]，應(yīng)用_____排序方法按遞增序排序，得到第一趟的結(jié)果為[４，３，２，１，５]。9.11假設(shè)待排序數(shù)據(jù)元素序列為[４，６，３，２，５]，應(yīng)用快速排序方法按遞增序排序，得到第一次劃分后的結(jié)果為________。9.12排序方法中，從未排序序列中依次取出元素與已排序序列（初始時(shí)為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為____。A.希爾排序B.冒泡排序C.插入排序D.選擇排序9.13在文件“局部有序”或文件長(zhǎng)度較小的情況下，最佳內(nèi)排序方法是____。A.直接插入排序B.冒泡排序C.直接選擇排序D.歸并排序9.14在待排序的元素列基本有序的前提下，效率最高的排序方法是____。A.插入排序B.選擇排序C.快速排序D.歸并排序9.15對(duì)記錄的關(guān)鍵字為{50，26，38，80，70，90，8，30，40，20}進(jìn)行排序，各趟排序結(jié)束時(shí)的結(jié)果為：5026388070908304020508304020902638807026830402080503890708202630384050708090其使用的排序方法是____。A.快速排序B.基數(shù)排序C.希爾排序D.歸并排序9.16一組紀(jì)錄的關(guān)鍵碼為（46，79，56，38，40，84）則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到一次劃分結(jié)果為_C__。A.38，40，46，56，79，84B.40，38，46，79，56，84C.40，38，46，56，79，84D.40，38，46，84，56，799.17用某種排序方法對(duì)線性表（25，84，21，47，15，27，68，35，20）進(jìn)行排序時(shí)，元素序列的變化情況如下：⑴25，84，21，47，15，27，68，35，20⑵20，15，21，25，47，27，68，35，84⑶15，20，21，25，35，27，47，68，84⑷15，20，21，25，27，35，47，68，84A.選擇排序B.希爾排序C.歸并排序D.快速排序9.18快速排序方法在_C_情況下最不利于發(fā)揮其長(zhǎng)處。A.要排序得數(shù)據(jù)量太大B.要排序得數(shù)據(jù)種含有多個(gè)相同值C.要排序的數(shù)據(jù)已基本有序D.要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù)9.19如果對(duì)n個(gè)元素進(jìn)行直接選擇排序，則進(jìn)行任一趟排序的過程中，為尋找最小值元素所需要的時(shí)間復(fù)雜度為____。A.O(1)B.O(log2n)C.O(n2)D.O(n)9.20在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是____。A.希爾排序B.冒泡排序C.插入排序D.選擇排序9.21排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列的一端的方法，稱為____。A.希爾排序B.歸并排序C.插入排序D.選擇排序9.22在對(duì)一組紀(jì)錄（54，38，96，23，15，72，60，45，83）進(jìn)行直接插入排序時(shí)，當(dāng)把7個(gè)記錄60插入到有序表時(shí)，為尋找插入的位置需比較____。9.23每次從無序子表中取出一個(gè)元素，把它插入到有序子表中的適當(dāng)位置，此種排序方法叫做____排序，每次從無序子表中挑選出一個(gè)最小或最大元素，把它交換到有序表的一端，此種排序方法叫做____排序。9.24每次直接或通過基準(zhǔn)元素間接比較兩個(gè)元素，若出現(xiàn)逆序排列時(shí)就交換他們的位置，此種排序方法叫做____排序；每次是兩個(gè)相鄰的有序表合并成一個(gè)有序表的方法叫做____排序。9.25在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用____；若初始數(shù)據(jù)反序，則選用____。9.26設(shè)有關(guān)鍵序列（Q,H,C,Y,Q,A,M,S,R,D,F,X）,要按照關(guān)鍵碼值遞增的次序進(jìn)行排序，若采用初始步長(zhǎng)為4的希爾排序法，則一趟掃描的結(jié)果是____；若采用以第一個(gè)元素為分界元素的快速排序法，則一趟掃描的結(jié)果是____。9.27在插入排序，希爾排序，選擇排序，快速排序，堆排序，歸并排序和基數(shù)排序中，排序是不穩(wěn)定的有____。9.28已知序列{17，18，60，40，7，32，73，65，85}，請(qǐng)給出采用冒泡排序法對(duì)該序列做升序排列時(shí)的每一趟的結(jié)果。9.29已知序列{503，87，512，61，908，170，897，275，653，462}，請(qǐng)給出采用快速排序法對(duì)該序排序時(shí)的每一趟的結(jié)果。9.30在對(duì)一組記錄（54，38，96，23，15，72，60，45，83）進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄60插入到有序表時(shí)，為尋找插入位置需比較次。9.31對(duì)n個(gè)元素的序列進(jìn)行冒泡排序時(shí)，最少的比較次數(shù)是，最多的比較次數(shù)是。9.32在直接插入排序、折半插入排序、冒泡排序、快速排序、簡(jiǎn)單選擇排序和歸并排序這幾種算法中，排序和排序是不穩(wěn)定的。9.33對(duì)序列（80，31，27，86，11，42，92）進(jìn)行排序，使用直接插入排序方法的比較次數(shù)為；使用冒泡排序法的比較次數(shù)為；使用直接選擇排序法的比較次數(shù)為；使用快速排序方法的比較次數(shù)為。9.34一組記錄的關(guān)鍵字為(46，79，56，38，40，84)，則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)，得到的一次劃分的結(jié)果為。A.38，40，46，56，79，84B.40，38，46，79，56，84C.40，38，46，56，79，84D.40，38，46，84，56，799.35排序可分為__________和_____________兩類；衡量排序算法的兩個(gè)主要性能指標(biāo)分別是:______________、______________。9．36一組記錄的關(guān)鍵字為（46，79，56，38，40，84），則利用快速排序的方法，以第一個(gè)記錄為樞軸，得到的一次劃分的結(jié)果為__________。A.38，40，46，56，79，84B.40，38，46，79，5