2022年數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版期末考試試題

1、“數(shù)據(jù)結(jié)構(gòu)”期末考試試題一、單選題 (每小題 2 分，共 12 分) 1在一個(gè)單鏈表 hl中，若要向表頭插入一個(gè)由指針p 指向的結(jié)點(diǎn)，則執(zhí)行 ( )。 a hl ps p 一nexthl b p 一nexthl ；hl p3 c p 一nexthl；phl； d p 一nexthl一next;hl 一next p； 2n 個(gè)頂點(diǎn)的強(qiáng)連通圖中至少含有( )。 a.nl 條有向邊 b.n條有向邊 c.n(n1) 2 條有向邊 d.n(n一 1)條有向邊 3.從一棵二叉搜索樹(shù)中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為( )。 a.o(1) b.o(n) c.o(1ogzn) d.o(n2) 4由權(quán)值分別為

2、 3，8，6，2，5 的葉子結(jié)點(diǎn)生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為( )。 a24 b48 c 72 d 53 5當(dāng)一個(gè)作為實(shí)際傳遞的對(duì)象占用的存儲(chǔ)空間較大并可能需要修改時(shí)，應(yīng)最好把它說(shuō)明為 ( )參數(shù)，以節(jié)省參數(shù)值的傳輸時(shí)間和存儲(chǔ)參數(shù)的空間。 a.整形 b.引用型 c.指針型 d.常值引用型6向一個(gè)長(zhǎng)度為 n 的順序表中插人一個(gè)新元素的平均時(shí)間復(fù)雜度為( )。 ao(n) bo(1) co(n2) do(10g2n) 二、填空題 (每空 1 分，共 28 分) 1數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)被分為、和四種。 2在廣義表的存儲(chǔ)結(jié)構(gòu)中， 單元素結(jié)點(diǎn)與表元素結(jié)點(diǎn)有一個(gè)域?qū)?yīng)不同，各自分別為域和域。3中綴表達(dá)式

3、 3 十 x*(2.4 56) 所對(duì)應(yīng)的后綴表達(dá)式為。 4 在一棵高度為 h 的 3 叉樹(shù)中，最多含有結(jié)點(diǎn)。5假定一棵二叉樹(shù)的結(jié)點(diǎn)數(shù)為18，則它的最小深度為，最大深度為 6在一棵二叉搜索樹(shù)中， 每個(gè)分支結(jié)點(diǎn)的左子樹(shù)上所有結(jié)點(diǎn)的值一定該結(jié)點(diǎn)的值，右子樹(shù)上所有結(jié)點(diǎn)的值一定該結(jié)點(diǎn)的值。 7當(dāng)向一個(gè)小根堆插入一個(gè)具有最小值的元素時(shí)，該元素需要逐層調(diào)整，直到被調(diào)整到位置為止。 8 表示圖的三種存儲(chǔ)結(jié)構(gòu)為、和。 9對(duì)用鄰接矩陣表示的具有n 個(gè)頂點(diǎn)和 e 條邊的圖進(jìn)行任一種遍歷時(shí)， 其時(shí)間精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 1 頁(yè)，共 38 頁(yè) - -

4、 - - - - - - -復(fù)雜度為， 對(duì)用鄰接表表示的圖進(jìn)行任一種遍歷時(shí)，其時(shí)間復(fù)雜度為。 10 從有序表 (12，18，30，43，56，78，82，95)中依次二分查找 43 和 56 元素時(shí)，其查找長(zhǎng)度分別為和 11 假定對(duì)長(zhǎng)度 n144的線(xiàn)性表進(jìn)行索引順序查找， 并假定每個(gè)子表的長(zhǎng)度均為，則進(jìn)行索引順序查找的平均查找長(zhǎng)度為，時(shí)間復(fù)雜度為 12一棵 b樹(shù)中的所有葉子結(jié)點(diǎn)均處在上。 13每次從無(wú)序表中順序取出一個(gè)元素，把這插入到有序表中的適當(dāng)位置，此種排序方法叫做排序；每次從無(wú)序表中挑選出一個(gè)最小或最大元素，把它交換到有序表的一端，此種排序方法叫做排序。 14 快速排序在乎均情況下的時(shí)間

5、復(fù)雜度為，最壞情況下的時(shí)間復(fù)雜度為。三、運(yùn)算題 (每小題 6 分，共 24 分) 1假定一棵二叉樹(shù)廣義表表示為a(b(c ，d)，c( ，8) ，分別寫(xiě)出對(duì)它進(jìn)行先序、中序、后序和后序遍歷的結(jié)果。先序：中序；后序： 2已知一個(gè)帶權(quán)圖的頂點(diǎn)集v和邊集 g分別為： v0 ，1，2，3，4，5 ； e=(0，1)8，(0 ，2)5，(0，3)2，(1，5)6，(2，3)25，(2 ，4)13，(3，5)9，(4 ，5)10 ，則求出該圖的最小生成樹(shù)的權(quán)。最小生成樹(shù)的權(quán)； 3假定一組記錄的排序碼為(46，79，56，38，40，84，50，42) ，則利用堆排序方法建立的初始堆為。 4有 7 個(gè)帶權(quán)結(jié)

6、點(diǎn)，其權(quán)值分別為3，7，8，2，6，10，14，試以它們?yōu)槿~子結(jié)點(diǎn)生成一棵哈夫曼樹(shù)，求出該樹(shù)的帶權(quán)路徑長(zhǎng)度、高度、雙分支結(jié)點(diǎn)數(shù)。帶權(quán)路徑長(zhǎng)度：高度：雙分支結(jié)點(diǎn)數(shù)：。四、閱讀算法，回答問(wèn)題(每小題 8 分，共 16 分) 1voldac(list&l) initlist(l)； insertrear(l;25)； insertfront(l，50) ； intal45，8，12，15，36; for(inti0; i5; i+) if (ai20)insertfront(l，ai)； elselnsertrear(l，ai)； 該算法被調(diào)用執(zhí)行后，得到的線(xiàn)性表l 為： 2void ag(

7、queue&q) 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 2 頁(yè)，共 38 頁(yè) - - - - - - - - - initqueue(q)； inta56，12，5，15，8 ； for(int i0;i5; i+)qinsert(q，ai)； qinsert(q，qdelete(q) ； qinsert(q，20) ； qinsert(q，qdelete(q) 十 16)； while(!queueempty(q)coutqdelete(q)” ； 該算法被調(diào)用后得到的輸出結(jié)果為：五、算法填空，在畫(huà)有橫線(xiàn)的地方填寫(xiě)合適的內(nèi)容( 每

8、小題 6 分，共 12 分) 1從一維數(shù)組 an) 中二分查找關(guān)鍵字為k 的元素的遞歸算法，若查找成功則返回對(duì)應(yīng)元素的下標(biāo)，否則返回一1。 intbinsch(elemtypea，intlow ，int high，keytypek) if(lowhigh) int mid(low+high) 2； if(kamid.key)； else if (kdatax)return 1; 根結(jié)點(diǎn)的層號(hào)為1 向子樹(shù)中查找x 結(jié)點(diǎn) else int clnodelevel(bt 一left ，x)； if(cl1)return cl+1; int c2； if；若樹(shù)中不存在x結(jié)點(diǎn)則返回 o else ret

9、urn 0； 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 3 頁(yè)，共 38 頁(yè) - - - - - - - - - 六、編寫(xiě)算法 (8 分) 按所給函數(shù)聲明編寫(xiě)一個(gè)算法， 從表頭指針為 hl的單鏈表中查找出具有最大值的結(jié)點(diǎn)，該最大值由函數(shù)返回，若單鏈表為空則中止運(yùn)行。 eiemtype maxvalue(lnode*hl); “數(shù)據(jù)結(jié)構(gòu)”期末考試試題答案一、單選題 (每小題 2 分，共 12 分) 評(píng)分標(biāo)準(zhǔn)；選對(duì)者得2 分，否則不得分。 1b 2b 3c 4d 5b 6a 二、填空題 (每空 1 分，共 28 分) 1順序結(jié)構(gòu)鏈接結(jié)構(gòu)索引結(jié)構(gòu)散列

10、結(jié)構(gòu) (次序無(wú)先后 ) 2值(或 data) 子表指針 ( 或 sublist) 33 x 2 4 5 6 一*十 4(3h一 1) 2 5 5 18 6小于大于( 或大于等于 ) 7向上堆頂 8鄰接矩陣鄰接表邊集數(shù)組 ( 次序無(wú)先后 ) 9o(n2) o(e) 10 1 3 1113 o() 12同一層 13插人選擇 14o(nlog2n) o(n2) 三、運(yùn)算題 (每小題 6 分，共 24 分) 1先序： a，b，c，d，e，f ，e 2 分中序：c，b，d，a，f，8，e 2 分后序：c，d，b，e，f，e，a 2 分 2 最小生成樹(shù)的權(quán)： 31 6 分 3(84，79，56，42，40

11、，46，50，38) 6 分 4帶權(quán)路徑長(zhǎng)度： 131 3 分高度：5 2 分雙分支結(jié)點(diǎn)數(shù)： 6 1 分四、閱讀算法，回答問(wèn)題(每小題 8 分，共 16 分) 評(píng)分標(biāo)準(zhǔn)：每小題正確得 8 分，出現(xiàn)一處錯(cuò)誤扣 4 分，兩處及以上錯(cuò)誤不得分。 1(36，12，8，50，25，5，15) 25 15 8 6 20 28 五、算法填空，在畫(huà)有橫線(xiàn)的地方填寫(xiě)合適的內(nèi)容( 每小題 6 分，共 12 分) 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 4 頁(yè)，共 38 頁(yè) - - - - - - - - - 1feturn mid 2 分 returnbinsc

12、h(a，low，mid 一 1，k) 2 分 returnbmsch(a，mid+1，high ，k) 2 分 2nodelevel(bt 一right ，x) 3 分 (c2=1)returnc2十 1 3 分六、編寫(xiě)算法 (8 分) 評(píng)分標(biāo)準(zhǔn)：請(qǐng)參考語(yǔ)句后的注釋?zhuān)蚋鶕?jù)情況酌情給分。 elemtype maxvalue(lnodeo* hl。) if (hl=null) 2 分 cerrlinked llst is empty!”data；3 分 lnode*p=hi一next；4 分 while(p!：null) 7 分 if(maxdata)maxp 一data； pp 一next；

13、returnmax；8 分 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料一、填空題1. 數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和運(yùn)算等的學(xué)科。2. 數(shù)據(jù)結(jié)構(gòu)被形式地定義為（d, r） ，其中d 是數(shù)據(jù)元素的有限集合， r是 d上的關(guān)系有限集合。3. 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 5 頁(yè)，共 38 頁(yè) - - - - - - - - -這三個(gè)方面的內(nèi)容。4. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類(lèi)，它們分別是線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)。5. 線(xiàn)性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系，樹(shù)形結(jié)構(gòu)

14、中元素之間存在一對(duì)多 關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對(duì)多關(guān)系。6 在線(xiàn)性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)沒(méi)有 前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)沒(méi)有后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1 個(gè)后續(xù)結(jié)點(diǎn)。7. 在樹(shù)形結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)數(shù)可以任意多個(gè)。8. 在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以任意多個(gè)。9數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用四種基本的存儲(chǔ)方法表示，它們分別是 順序、 鏈?zhǔn)?、 索引和散列。10. 數(shù)據(jù)的運(yùn)算最常用的有5 種，它們分別是 插入 、 刪除、修改、 查找 、排序。11. 一個(gè)算法的效

15、率可分為時(shí)間效率和空間效率。12. 在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)表中一半 元素，具體移動(dòng)的元素個(gè)數(shù)與表長(zhǎng)和該元素在表中的位置有關(guān)。13. 線(xiàn)性表中結(jié)點(diǎn)的集合是有限的，結(jié)點(diǎn)間的關(guān)系是一對(duì)一的。14. 向一個(gè)長(zhǎng)度為n 的向量的第 i 個(gè)元素 (1 i n+1)之前插入一個(gè)元素時(shí)，需向后移動(dòng) n-i+1 個(gè)元素。15. 向一個(gè)長(zhǎng)度為n 的向量中刪除第i 個(gè)元素 (1 i n) 時(shí)，需向前移動(dòng)n-i 個(gè)元素。16. 在順序表中訪(fǎng)問(wèn)任意一結(jié)點(diǎn)的時(shí)間復(fù)雜度均為 o(1)，因此，順序表也稱(chēng)為隨機(jī)存取的數(shù)據(jù)結(jié)構(gòu)。精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - -

16、- 第 6 頁(yè)，共 38 頁(yè) - - - - - - - - -17. 順序表中邏輯上相鄰的元素的物理位置必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置不一定 相鄰。18在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由其直接前驅(qū)結(jié)點(diǎn)的鏈域的值指示。19 在 n 個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p，需找到它的 前驅(qū)結(jié)點(diǎn)的地址 ，其時(shí)間復(fù)雜度為 o （n） 。20. 向量、棧和隊(duì)列都是線(xiàn)性結(jié)構(gòu)，可以在向量的任何位置插入和刪除元素；對(duì)于棧只能在棧頂插入和刪除元素； 對(duì)于隊(duì)列只能在隊(duì)尾插入和隊(duì)首刪除元素。21. 棧是一種特殊的線(xiàn)性表，允許插入和刪除運(yùn)算的一端稱(chēng)為棧頂。不允許插入和刪除運(yùn)算的一端稱(chēng)為棧底。

17、22. 隊(duì)列是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線(xiàn)性表。23. 不包含任何字符 （長(zhǎng)度為 0）的串稱(chēng)為空串；由一個(gè)或多個(gè)空格 （僅由空格符） 組成的串稱(chēng)為空白串。24. 子串的定位運(yùn)算稱(chēng)為串的模式匹配；被匹配的主串稱(chēng)為目標(biāo)串，子串稱(chēng)為模式。25. 假設(shè)有二維數(shù)組a68，每個(gè)元素用相鄰的6 個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知 a的起始存儲(chǔ)位置（基地址）為 1000， 則數(shù)組 a的體積 （存儲(chǔ)量）為 288 b ；末尾元素 a57的第一個(gè)字節(jié)地址為 1282 ；若按行存儲(chǔ)時(shí)，元素a14的第一個(gè)字節(jié)地址為 (8+4)6+1000=1072 ；若按列存儲(chǔ)時(shí)，元素a47的第一

18、個(gè)字節(jié)地址為 (6 74)61000）1276 。26 由個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹(shù)有5種形態(tài)。27. 一棵深度為6 的滿(mǎn)二叉樹(shù)有n1+n2=0+ n2= n0-1=31 個(gè)分支結(jié)點(diǎn)和26-1 =32精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 7 頁(yè)，共 38 頁(yè) - - - - - - - - -個(gè)葉子。注：滿(mǎn)二叉樹(shù)沒(méi)有度為1 的結(jié)點(diǎn)，所以分支結(jié)點(diǎn)數(shù)就是二度結(jié)點(diǎn)數(shù)。28 一棵具有個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，它的深度為9。（ 注：用 log2(n) +1= 8.xx +1=929設(shè)一棵完全二叉樹(shù)有700 個(gè)結(jié)點(diǎn)，則共有 350個(gè)葉子結(jié)點(diǎn)。答：最快方法：用葉子數(shù)

19、n/2 350 30 設(shè)一棵完全二叉樹(shù)具有1000 個(gè)結(jié)點(diǎn)，則此完全二叉樹(shù)有500個(gè)葉子結(jié)點(diǎn)，有499個(gè)度為 2 的結(jié)點(diǎn)，有1個(gè)結(jié)點(diǎn)只有非空左子樹(shù)，有0個(gè)結(jié)點(diǎn)只有非空右子樹(shù)。答：最快方法：用葉子數(shù)n/2 500 ，n2=n0-1=499。 另外，最后一結(jié)點(diǎn)為2i屬于左葉子，右葉子是空的，所以有1 個(gè)非空左子樹(shù)。完全二叉樹(shù)的特點(diǎn)決定不可能有左空右不空的情況，所以非空右子樹(shù)數(shù)0.31在數(shù)據(jù)的存放無(wú)規(guī)律而言的線(xiàn)性表中進(jìn)行檢索的最佳方法是順序查找（線(xiàn)性查找）。32. 線(xiàn)性有序表（ a1，a2，a3，a256)是從小到大排列的，對(duì)一個(gè)給定的值k，用二分法檢索表中與k 相等的元素，在查找不成功的情況下，

20、最多需要檢索8 次。設(shè)有 100 個(gè)結(jié)點(diǎn)，用二分法查找時(shí)，最大比較次數(shù)是7。33. 假設(shè)在有序線(xiàn)性表a20 上進(jìn)行折半查找， 則比較一次查找成功的結(jié)點(diǎn)數(shù)為1；比較兩次查找成功的結(jié)點(diǎn)數(shù)為 2；比較四次查找成功的結(jié)點(diǎn)數(shù)為 8；平均查找長(zhǎng)度為3.7。解：顯然，平均查找長(zhǎng)度 o （log2n）top0 st-top=0 st-topm0 st-top=m0 （c ）18. 在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的倍。 a1/2 b. 1 c. 2 d. 4 （b）19. 在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的倍。 a1/2 b. 1 c. 2 d. 4 （b）20. 有 8 個(gè)

21、結(jié)點(diǎn)的無(wú)向圖最多有條邊。 a14 b. 28 c. 56 d. 112 （c）21. 有 8 個(gè)結(jié)點(diǎn)的有向完全圖有條邊。 a14 b. 28 c. 56 d. 112 （b）22在表長(zhǎng)為的鏈表中進(jìn)行線(xiàn)性查找，它的平均查找長(zhǎng)度為. ; . （）; 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 14 頁(yè)，共 38 頁(yè) - - - - - - - - -. n; . （）（a）23折半查找有序表（ 4，6，10，12，20，30，50，70，88，100） 。若查找表中元素 58，則它將依次與表中比較大小，查找結(jié)果是失敗。a20，70，30，50 b30

22、，88，70，50 c20，50 d30，88，50 （c）24對(duì) 22 個(gè)記錄的有序表作折半查找，當(dāng)查找失敗時(shí)，至少需要比較次關(guān)鍵字。a3 b4 c5 d 6 （a）25. 鏈表適用于查找a順序 b二分法 c順序，也能二分法 d隨機(jī)數(shù)據(jù)結(jié)構(gòu)與算法復(fù)習(xí)題一、選擇題。1在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為 c 。a動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) b緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)c 線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu) d內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)2數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指 a 。a數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) b數(shù)據(jù)結(jié)構(gòu) c數(shù)據(jù)的邏輯結(jié)構(gòu) d 數(shù)據(jù)元素之間的關(guān)系3在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的 a 結(jié)構(gòu)。a邏輯 b存儲(chǔ) c邏輯和

23、存儲(chǔ) d物理4在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ) c 。a數(shù)據(jù)的處理方法 b數(shù)據(jù)元素的類(lèi)型精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 15 頁(yè)，共 38 頁(yè) - - - - - - - - -c 數(shù)據(jù)元素之間的關(guān)系 d數(shù)據(jù)的存儲(chǔ)方法5在決定選取何種存儲(chǔ)結(jié)構(gòu)時(shí)，一般不考慮 a 。a各結(jié)點(diǎn)的值如何 b結(jié)點(diǎn)個(gè)數(shù)的多少c 對(duì)數(shù)據(jù)有哪些運(yùn)算 d所用的編程語(yǔ)言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便。6以下說(shuō)法正確的是 d 。a數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位b數(shù)據(jù)元素是數(shù)據(jù)的最小單位c 數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)項(xiàng)的集合d 一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)

24、7算法分析的目的是 c ，算法分析的兩個(gè)主要方面是 a 。（1）a找出數(shù)據(jù)結(jié)構(gòu)的合理性 b研究算法中的輸入和輸出的關(guān)系c分析算法的效率以求改進(jìn) c分析算法的易讀性和文檔性（2）a空間復(fù)雜度和時(shí)間復(fù)雜度 b正確性和簡(jiǎn)明性 c可讀性和文檔性 d數(shù)據(jù)復(fù)雜性和程序復(fù)雜性8下面程序段的時(shí)間復(fù)雜度是 o(n2) 。s =0; for( i =0; in; i+) for(j=0;jn;j+) s +=bij; sum = s ; 9下面程序段的時(shí)間復(fù)雜度是 o(n*m) 。精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 16 頁(yè)，共 38 頁(yè) - - - - -

25、 - - - -for( i =0; in; i+) for(j=0;jm;j+) aij 0; 10下面程序段的時(shí)間復(fù)雜度是 o(log3n) 。i 0 ；while （inext =null c head-next =head d head!=null 15帶頭結(jié)點(diǎn)的單鏈表head 為空的判定條件是 b 。ahead = null b head-next =null c head-next =head d head!=null 16 若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)，則采用 d 存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。a單鏈表 b 給出表頭指針的單循環(huán)鏈表 c雙鏈表 d

26、 帶頭結(jié)點(diǎn)的雙循環(huán)鏈表17需要分配較大空間，插入和刪除不需要移動(dòng)元素的線(xiàn)性表，其存儲(chǔ)結(jié)構(gòu)是b 。a單鏈表 b 靜態(tài)鏈表 c線(xiàn)性鏈表 d順序存儲(chǔ)結(jié)構(gòu)18非空的循環(huán)單鏈表head 的尾結(jié)點(diǎn)（由 p 所指向）滿(mǎn)足 c 。ap-next = null bp = null c p-next =head dp = head 19在循環(huán)雙鏈表的p 所指的結(jié)點(diǎn)之前插入s 所指結(jié)點(diǎn)的操作是 d 。精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 18 頁(yè)，共 38 頁(yè) - - - - - - - - -ap-prior = s；s-next = p；p-prior-ne

27、xt = s；s-prior = p-prior bp-prior = s；p-prior-next = s；s-next = p；s-prior = p-prior c s-next = p；s-prior = p-prior；p-prior = s；p-prior-next = s d s-next = p；s-prior = p-prior；p-prior-next = s；p-prior = s 20 如果最常用的操作是取第i 個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用 d 存儲(chǔ)方式最節(jié)省時(shí)間。a單鏈表 b 雙鏈表 c單循環(huán)鏈表 d 順序表21在一個(gè)具有 n 個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然保持有

28、序的時(shí)間復(fù)雜度是 b 。ao （1） b o （n） co （n2） do （nlog2n ）22在一個(gè)長(zhǎng)度為 n（n1）的單鏈表上，設(shè)有頭和尾兩個(gè)指針，執(zhí)行 b 操作與鏈表的長(zhǎng)度有關(guān)。a刪除單鏈表中的第一個(gè)元素b刪除單鏈表中的最后一個(gè)元素c 在單鏈表第一個(gè)元素前插入一個(gè)新元素d 在單鏈表最后一個(gè)元素后插入一個(gè)新元素23與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是 d 。a插入、刪除操作更簡(jiǎn)單b可以進(jìn)行隨機(jī)訪(fǎng)問(wèn)c 可以省略表頭指針或表尾指針d 順序訪(fǎng)問(wèn)相鄰結(jié)點(diǎn)更靈活精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 19 頁(yè)，共 38 頁(yè) - - - - - - -

29、 - -24如果對(duì)線(xiàn)性表的操作只有兩種，即刪除第一個(gè)元素，在最后一個(gè)元素的后面插入新元素，則最好使用 b 。a只有表頭指針沒(méi)有表尾指針的循環(huán)單鏈表b只有表尾指針沒(méi)有表頭指針的循環(huán)單鏈表c 非循環(huán)雙鏈表d 循環(huán)雙鏈表25在長(zhǎng)度為 n 的順序表的第 i 個(gè)位置上插入一個(gè)元素（ 1 i n+1） ，元素的移動(dòng)次數(shù)為： a 。an i + 1 bn i ci di 1 26 對(duì)于只在表的首、尾兩端進(jìn)行插入操作的線(xiàn)性表， 宜采用的存儲(chǔ)結(jié)構(gòu)為 c 。a順序表 b 用頭指針表示的循環(huán)單鏈表c 用尾指針表示的循環(huán)單鏈表 d單鏈表27下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？ c 。a插入運(yùn)算方便 b可方便地用于各種邏輯

30、結(jié)構(gòu)的存儲(chǔ)表示c存儲(chǔ)密度大 d刪除運(yùn)算方便28下面關(guān)于線(xiàn)性表的敘述中，錯(cuò)誤的是哪一個(gè)？ b 。a線(xiàn)性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元b線(xiàn)性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。c線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元d線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)，便于進(jìn)行插入和刪除操作。精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 20 頁(yè)，共 38 頁(yè) - - - - - - - - -29線(xiàn)性表是具有 n 個(gè) b 的有限序列。a字符 b數(shù)據(jù)元素 c數(shù)據(jù)項(xiàng) d表元素30 在 n個(gè)結(jié)點(diǎn)的線(xiàn)性表的數(shù)組實(shí)現(xiàn)中， 算法的時(shí)間復(fù)雜度是o （1） 的操作是 a 。

31、a訪(fǎng)問(wèn)第 i （1=i=n）個(gè)結(jié)點(diǎn)和求第 i 個(gè)結(jié)點(diǎn)的直接前驅(qū)（ 1i=n）b在第 i （1=i=n）個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)c刪除第 i （1=inext=s ；s-next=p-next b s-next=p-next ；p-next=s; cp-next=s ；p-next=s-next dp-next=s-next；p-next=s 36線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)是一種 a 。a隨機(jī)存取的存儲(chǔ)結(jié)構(gòu) b順序存取的存儲(chǔ)結(jié)構(gòu)c索引存取的存儲(chǔ)結(jié)構(gòu) dhash存取的存儲(chǔ)結(jié)構(gòu)37棧的特點(diǎn)是 b ，隊(duì)列的特點(diǎn)是 a 。a先進(jìn)先出 b先進(jìn)后出38棧和隊(duì)列的共同點(diǎn)是 c 。a都是先進(jìn)后出 b都是先進(jìn)先出c 只允

32、許在端點(diǎn)處插入和刪除元素 d沒(méi)有共同點(diǎn)39一個(gè)棧的進(jìn)棧序列是a，b，c，d，e，則棧的不可能的輸出序列是 c 。aedcba bdecba c dceab dabcde 40設(shè)有一個(gè)棧，元素依次進(jìn)棧的順序?yàn)閍、b、c、d、e。下列 c 是不可能的出棧序列。 aa,b,c,d,e bb,c,d,e,a ce,a,b,c,d de,d,c,b,a 41以下 b 不是隊(duì)列的基本運(yùn)算？精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 22 頁(yè)，共 38 頁(yè) - - - - - - - - -a從隊(duì)尾插入一個(gè)新元素 b從隊(duì)列中刪除第i 個(gè)元素c 判斷一個(gè)隊(duì)列是否

33、為空 d讀取隊(duì)頭元素的值42若已知一個(gè)棧的進(jìn)棧序列是1，2，3， ，n，其輸出序列為 p1，p2，p3，pn，若 p1n，則 pi 為 c 。ai bni cni 1 d 不確定43判定一個(gè)順序棧st （最多元素為 maxsize）為空的條件是 b 。ast-top != -1 bst-top = -1 c st-top != maxsize d st-top = maxsize 44判定一個(gè)順序棧st （最多元素為 maxsize）為滿(mǎn)的條件是 d 。ast-top != -1 bst-top = -1 c st-top != maxsize dst-top = maxsize 45一個(gè)隊(duì)列

34、的入隊(duì)序列是1，2，3，4，則隊(duì)列的輸出序列是 b 。a4，3，2，1 b1，2，3，4 c 1，4，3，2 d3，2，4，1 46判定一個(gè)循環(huán)隊(duì)列qu（最多元素為 maxsize）為空的條件是 c 。aqu-rear qu-front =maxsize bqu-rear qu-front -1=maxsize c qu-rear =qu-front d qu-rear =qu-front -1 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 23 頁(yè)，共 38 頁(yè) - - - - - - - - -47在循環(huán)隊(duì)列中，若front與 rear 分別表

35、示對(duì)頭元素和隊(duì)尾元素的位置，則判斷循環(huán)隊(duì)列空的條件是 c 。afront=rear+1 brear=front+1 c front=rear dfront=0 48 向一個(gè)棧頂指針為h 的帶頭結(jié)點(diǎn)的鏈棧中插入指針s 所指的結(jié)點(diǎn)時(shí)， 應(yīng)執(zhí)行 d 操作。ah-next=s ; bs-next=h ; c s-next=h ;h =s ; ds-next=h-next ;h-next=s ; 49輸入序列為 abc ，可以變?yōu)?cba時(shí)，經(jīng)過(guò)的棧操作為 b 。apush，pop，push，pop，push，pop bpush，push，push，pop， pop， pop c push，push，p

36、op， pop，push，pop dpush，pop，push，push，pop， pop 50若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間v1 m ，top1 、top2 分別代表第 1 和第 2 個(gè)棧的棧頂， 棧 1 的底在 v1 ，棧 2 的底在 vm，則棧滿(mǎn)的條件是b 。a |top2-top1|=0 btop1+1=top2 ctop1+top2=m d top1=top2 51設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對(duì)出現(xiàn)的算法，采用 d 數(shù)據(jù)結(jié)構(gòu)最佳。a線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu) b隊(duì)列 c 線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) d棧52允許對(duì)隊(duì)列進(jìn)行的操作有 d 。精品學(xué)習(xí)資料 可選擇p d f - - -

37、 - - - - - - - - - - - 第 24 頁(yè)，共 38 頁(yè) - - - - - - - - -a對(duì)隊(duì)列中的元素排序 b取出最近進(jìn)隊(duì)的元素c在隊(duì)頭元素之前插入元素 d刪除隊(duì)頭元素53對(duì)于循環(huán)隊(duì)列 d 。a無(wú)法判斷隊(duì)列是否為空 b無(wú)法判斷隊(duì)列是否為滿(mǎn)c隊(duì)列不可能滿(mǎn) d以上說(shuō)法都不對(duì)54若用一個(gè)大小為 6 的數(shù)值來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列， 且當(dāng)前 rear 和 front的值分別為 0和 3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和 front的值分別為b 。a1 和 5 b2 和 4 c4 和 2 d5 和 1 55隊(duì)列的“先進(jìn)先出”特性是指 d 。a最早插入隊(duì)列中的元素總是最后被

38、刪除b當(dāng)同時(shí)進(jìn)行插入、刪除操作時(shí)，總是插入操作優(yōu)先c每當(dāng)有刪除操作時(shí)，總是要先做一次插入操作d每次從隊(duì)列中刪除的總是最早插入的元素56和順序棧相比，鏈棧有一個(gè)比較明顯的優(yōu)勢(shì)是 a 。a通常不會(huì)出現(xiàn)棧滿(mǎn)的情況 b 通常不會(huì)出現(xiàn)?？盏那闆rc插入操作更容易實(shí)現(xiàn) d刪除操作更容易實(shí)現(xiàn)57用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列，其頭指針指向隊(duì)頭結(jié)點(diǎn)，尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行出隊(duì)操作時(shí) c 。精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 25 頁(yè)，共 38 頁(yè) - - - - - - - - -a僅修改隊(duì)頭指針 b僅修改隊(duì)尾指針c隊(duì)頭、隊(duì)尾指針都可能要修改 d隊(duì)頭、

39、隊(duì)尾指針都要修改58若串 s=software ，其子串的數(shù)目是 b 。a8 b37 c36 d9 59串的長(zhǎng)度是指 b 。a串中所含不同字母的個(gè)數(shù) b串中所含字符的個(gè)數(shù)c串中所含不同字符的個(gè)數(shù) d串中所含非空格字符的個(gè)數(shù)60串是一種特殊的線(xiàn)性表，其特殊性體現(xiàn)在 b 。a可以順序存儲(chǔ) b數(shù)據(jù)元素是一個(gè)字符c 可以鏈?zhǔn)酱鎯?chǔ) d數(shù)據(jù)元素可以是多個(gè)字符61設(shè)有兩個(gè)串 p 和 q，求 q 在 p 中首次出現(xiàn)的位置的運(yùn)算稱(chēng)為 b 。a連接 b 模式匹配 c 求子串 d求串長(zhǎng)62數(shù)組 a中，每個(gè)元素的長(zhǎng)度為3 個(gè)字節(jié)，行下標(biāo)i 從 1 到 8，列下標(biāo) j 從 1 到10，從首地址 sa開(kāi)始連續(xù)存放的存儲(chǔ)器

40、內(nèi)，該數(shù)組按行存放，元素a85的起始地址為 c 。asa 141 b sa144 csa 222 dsa 225 63數(shù)組 a中，每個(gè)元素的長(zhǎng)度為3 個(gè)字節(jié)，行下標(biāo)i 從 1 到 8，列下標(biāo) j 從 1 到10，從首地址 sa開(kāi)始連續(xù)存放的存儲(chǔ)器內(nèi)，該數(shù)組按行存放，元素a58的起始精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 26 頁(yè)，共 38 頁(yè) - - - - - - - - -地址為 c 。asa 141 b sa180 csa 222 dsa 225 64若聲明一個(gè)浮點(diǎn)數(shù)數(shù)組如下： froat average=new float30; 假設(shè)

41、該數(shù)組的內(nèi)存起始位置為200， average15的內(nèi)存地址是 c 。a214 b215 c260 d256 65 設(shè)二維數(shù)組 a1 m,1 n 按行存儲(chǔ)在數(shù)組 b中，則二維數(shù)組元素 ai,j在一維數(shù)組 b中的下標(biāo)為 a 。an*(i-1)+j b n*(i-1)+j-1 ci*(j-1) dj*m+i-1 66有一個(gè) 10090 的稀疏矩陣，非 0 元素有 10，設(shè)每個(gè)整型數(shù)占2 個(gè)字節(jié)，則用三元組表示該矩陣時(shí)，所需的字節(jié)數(shù)是 b 。a20 b 66 c18 000 d33 67數(shù)組 a0 4 ，-1 -3 ，5 7 中含有的元素個(gè)數(shù)是 a 。a55 b 45 c36 d16 68對(duì)矩陣進(jìn)行

42、壓縮存儲(chǔ)是為了 d 。a方便運(yùn)算 b 方便存儲(chǔ) c提高運(yùn)算速度 d 減少存儲(chǔ)空間69設(shè)有一個(gè) 10 階的對(duì)稱(chēng)矩陣 a，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a1，1為第一個(gè)元素，其存儲(chǔ)地址為1，每個(gè)元素占 1 個(gè)地址空間，則a8，5的地址為 b 。a13 b 33 c18 d40 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 27 頁(yè)，共 38 頁(yè) - - - - - - - - -70稀疏矩陣一般的壓縮存儲(chǔ)方式有兩種，即 c 。a二維數(shù)組和三維數(shù)組 b三元組和散列c 三元組和十字鏈表 d散列和十字鏈表71樹(shù)最適合用來(lái)表示 c 。a有序數(shù)據(jù)元素 b無(wú)序

43、數(shù)據(jù)元素c 元素之間具有分支層次關(guān)系的數(shù)據(jù) d元素之間無(wú)聯(lián)系的數(shù)據(jù)72深度為 5 的二叉樹(shù)至多有 c 個(gè)結(jié)點(diǎn)。a16 b 32 c 31 c 10 73對(duì)一個(gè)滿(mǎn)二叉樹(shù)， m個(gè)葉子， n 個(gè)結(jié)點(diǎn)，深度為h，則 d 。an = h+m b h+m = 2n c m = h-1 d n = 2h-1 74 任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在前序、 中序和后序遍歷序列中的相對(duì)次序 a 。a不發(fā)生改變 b發(fā)生改變 c不能確定 d以上都不對(duì)75在線(xiàn)索化樹(shù)中，每個(gè)結(jié)點(diǎn)必須設(shè)置一個(gè)標(biāo)志來(lái)說(shuō)明它的左、右鏈指向的是樹(shù)結(jié)構(gòu)信息，還是線(xiàn)索化信息，若0 標(biāo)識(shí)樹(shù)結(jié)構(gòu)信息， 1 標(biāo)識(shí)線(xiàn)索，對(duì)應(yīng)葉結(jié)點(diǎn)的左右鏈域，應(yīng)標(biāo)識(shí)為 _ d _

44、 。a00 b01 c10 d11 76在下述論述中，正確的是 d 。精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 28 頁(yè)，共 38 頁(yè) - - - - - - - - -只有一個(gè)結(jié)點(diǎn)的二叉樹(shù)的度為0；二叉樹(shù)的度為2；二叉樹(shù)的左右子樹(shù)可任意交換；深度為 k的順序二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿(mǎn)二叉樹(shù)。a b c d77設(shè)森林 f對(duì)應(yīng)的二叉樹(shù)為 b，它有 m個(gè)結(jié)點(diǎn)， b的根為 p，p 的右子樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為 n，森林 f中第一棵樹(shù)的結(jié)點(diǎn)的個(gè)數(shù)是 a 。am-n bm-n-1 cn+1 d 不能確定78若一棵二叉樹(shù)具有10 個(gè)度為 2 的結(jié)點(diǎn)，5

45、 個(gè)度為 1 的結(jié)點(diǎn)，則度為 0 的結(jié)點(diǎn)的個(gè)數(shù)是 b 。a9 b11 c15 d 不能確定79具有 10 個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)中有 b 個(gè)度為 2 的結(jié)點(diǎn)。a8 b9 c10 d 11 80在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的 c 倍。a1/2 b 1 c 2 d 4 81在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的 b 倍。a1/2 b 1 c 2 d 4 82某二叉樹(shù)結(jié)點(diǎn)的中序序列為abcdefg，后序序列為 bdcafge，則其左子樹(shù)中結(jié)點(diǎn)數(shù)目為： c a3 b2 c4 d5 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - -

46、第 29 頁(yè)，共 38 頁(yè) - - - - - - - - -83已知一算術(shù)表達(dá)式的中綴形式為ab *cd/e，后綴形式為 abc *+de/，其前綴形式為 d 。a a+b*c/de b a+b*cd/e c +*abc/de d +a*bc/de 84已知一個(gè)圖，如圖所示，若從頂點(diǎn)a 出發(fā)按深度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為_(kāi)d_； 按廣度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為_(kāi)a_ ；aa，b，e，c，d，f ba，c，f ，e，b，d c a，e，b，c，f ，d， da，e，d，f ，c，b aa，b，c，e，d，f ba，b，c，e，f ，d c a，e，b，c，f

47、 ，d， da，c，f ，d，e，b 85采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的_a_ 。a先序遍歷 b中序遍歷 c后序遍歷 d按層遍歷86采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的_d_ 。a先序遍歷 b中序遍歷 c后序遍歷 d按層遍歷87具有 n 個(gè)結(jié)點(diǎn)的連通圖至少有 a 條邊。 a n-1 b n c n(n-1)/2 d 2n abcdef精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 30 頁(yè)，共 38 頁(yè) - - - - - - - - -88廣義表（a） ，a）的表頭是 c ，表尾是 c 。aa b （） c （a）

48、 d （ （a） ）89廣義表（a） ）的表頭是 c ，表尾是 b 。aa b （） c （a） d （ （a） ）90順序查找法適合于存儲(chǔ)結(jié)構(gòu)為 b 的線(xiàn)性表。a 散列存儲(chǔ) b 順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ) c 壓縮存儲(chǔ) d 索引存儲(chǔ)91對(duì)線(xiàn)性表進(jìn)行折半查找時(shí)，要求線(xiàn)性表必須 b 。a 以順序方式存儲(chǔ) b 以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列c 以鏈?zhǔn)椒绞酱鎯?chǔ) d 以鏈?zhǔn)椒绞酱鎯?chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列92采用折半查找法查找長(zhǎng)度為n 的線(xiàn)性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為d 。a o(n2) b o(nlog2n) c o(n) d o(log2n) 93有一個(gè)有序表為 1，3，9，12，32，41，

49、45，62，75，77，82，95，100 ，當(dāng)折半查找值為 82 的結(jié)點(diǎn)時(shí)， c 次比較后查找成功。a 11 b 5 c 4 d 8 94二叉樹(shù)為二叉排序樹(shù)的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說(shuō)法 b 。a 正確 b 錯(cuò)誤精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 31 頁(yè)，共 38 頁(yè) - - - - - - - - -95下面關(guān)于 b樹(shù)和 b+ 樹(shù)的敘述中，不正確的結(jié)論是 a 。a b 樹(shù)和 b+樹(shù)都能有效的支持順序查找 b b樹(shù)和 b+ 樹(shù)都能有效的支持隨機(jī)查找c b 樹(shù)和 b+樹(shù)都是平衡的多叉樹(shù) d

50、b樹(shù)和 b+ 樹(shù)都可用于文件索引結(jié)構(gòu)96以下說(shuō)法錯(cuò)誤的是 b 。a散列法存儲(chǔ)的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲(chǔ)地址b散列表的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息，不包含指針。c 負(fù)載因子是散列表的一個(gè)重要參數(shù)，它反映了散列表的飽滿(mǎn)程度。d 散列表的查找效率主要取決于散列表構(gòu)造時(shí)選取的散列函數(shù)和處理沖突的方法。97查找效率最高的二叉排序樹(shù)是 c 。a所有結(jié)點(diǎn)的左子樹(shù)都為空的二叉排序樹(shù)。b所有結(jié)點(diǎn)的右子樹(shù)都為空的二叉排序樹(shù)。c 平衡二叉樹(shù)。d 沒(méi)有左子樹(shù)的二叉排序樹(shù)。98排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱(chēng)為 c 。a希爾排序 b。冒

51、泡排序 c插入排序 d。選擇排序精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 32 頁(yè)，共 38 頁(yè) - - - - - - - - -99在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無(wú)關(guān)的是d 。a希爾排序 b冒泡排序 c直接插入排序 d直接選擇排序100堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。下列關(guān)鍵碼序列 d 是一個(gè)堆。a94,31,53,23,16,72 b94,53,31,72,16,23 c 16,53,23,94,31,72 d16,31,23,94,53,72 101堆排序是一種b 排序。a插入 b選擇 c 交換 d歸并102 d 在鏈

52、表中進(jìn)行操作比在順序表中進(jìn)行操作效率高。a順序查找 b折半查找 c 分塊查找 d插入103直接選擇排序的時(shí)間復(fù)雜度為 d 。 （n 為元素個(gè)數(shù)）ao （n) bo(log2n) co(nlog2n) d o(n2) 二、填空題。1數(shù)據(jù)邏輯結(jié)構(gòu)包括線(xiàn)性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和圖狀結(jié)構(gòu)三種類(lèi)型，樹(shù)形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱(chēng)非線(xiàn)性結(jié)構(gòu)。2數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合、線(xiàn)性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和圖狀結(jié)構(gòu)4 種。3在線(xiàn)性結(jié)構(gòu)中， 第一個(gè)結(jié)點(diǎn)沒(méi)有 前驅(qū)結(jié)點(diǎn)， 其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)沒(méi)有后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)后續(xù)結(jié)點(diǎn)。精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - -

53、- - - - 第 33 頁(yè)，共 38 頁(yè) - - - - - - - - -4 線(xiàn)性結(jié)構(gòu)中元素之間存在一對(duì)一 關(guān)系， 樹(shù)形結(jié)構(gòu)中元素之間存在一對(duì)多 關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對(duì)多關(guān)系。5在樹(shù)形結(jié)構(gòu)中， 樹(shù)根結(jié)點(diǎn)沒(méi)有前驅(qū) 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以任意多個(gè)。6數(shù)據(jù)結(jié)構(gòu)的基本存儲(chǔ)方法是順序、鏈?zhǔn)?、索引和散列存?chǔ) 。7衡量一個(gè)算法的優(yōu)劣主要考慮正確性、可讀性、健壯性和時(shí)間復(fù)雜度與空間復(fù)雜度 。8評(píng)估一個(gè)算法的優(yōu)劣，通常從時(shí)間復(fù)雜度和空間復(fù)雜度兩個(gè)方面考察。9算法的 5 個(gè)重要特性是有窮性、確定性 、可行性、輸入和輸出。10在一個(gè)

54、長(zhǎng)度為 n 的順序表中刪除第i 個(gè)元素時(shí)，需向前移動(dòng) n-i-1 個(gè)元素。11在單鏈表中，要?jiǎng)h除某一指定的結(jié)點(diǎn)，必須找到該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。12在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向前驅(qū) 結(jié)點(diǎn)，另一個(gè)指向后繼結(jié)點(diǎn) 。13在順序表中插入或刪除一個(gè)數(shù)據(jù)元素，需要平均移動(dòng) n 個(gè)數(shù)據(jù)元素， 移動(dòng)數(shù)據(jù)元素的個(gè)數(shù)與位置 有關(guān)。14當(dāng)線(xiàn)性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線(xiàn)性表的元素是，應(yīng)采用順序存儲(chǔ)結(jié)構(gòu)。15根據(jù)線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù)，將線(xiàn)性鏈表分成單鏈表和 雙鏈表 。16 順序存儲(chǔ)結(jié)構(gòu)是通過(guò)下標(biāo)表示元素之間的關(guān)系的； 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過(guò)指針

55、 表示元素之間的關(guān)系的。17帶頭結(jié)點(diǎn)的循環(huán)鏈表l 中只有一個(gè)元素結(jié)點(diǎn)的條件是 l-next-next=l 。18棧是限定僅在表尾進(jìn)行插入或刪除操作的線(xiàn)性表，其運(yùn)算遵循后進(jìn)先出精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 34 頁(yè)，共 38 頁(yè) - - - - - - - - -的原則。19空串是零個(gè)字符的串，其長(zhǎng)度等于零?？瞻状怯梢粋€(gè)或多個(gè)空格字符組成的串，其長(zhǎng)度等于其包含的空格個(gè)數(shù)。20組成串的數(shù)據(jù)元素只能是單個(gè)字符。21一個(gè)字符串中任意個(gè)連續(xù)字符構(gòu)成的部分稱(chēng)為該串的子串。22子串 ”str ” 在主串 ”datastructure” 中的位置

56、是 5 。23二維數(shù)組 m的每個(gè)元素是 6 個(gè)字符組成的串，行下標(biāo)i 的范圍從 0 到 8，列下標(biāo) j 的范圍從 1 到 10， 則存放 m至少需要 540 個(gè)字節(jié)； m的第 8 列和第 5 行共占 108個(gè)字節(jié)。24稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即三元組表和十字鏈表。25廣義表（a） ， （ （b） ，c） ， （ （ （d） ） ） ）的長(zhǎng)度是 3 ，深度是 4 。26在一棵二叉樹(shù)中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為n0，度為 2 的結(jié)點(diǎn)的個(gè)數(shù)為n2，則有 n0 n2+1 。27在有 n 個(gè)結(jié)點(diǎn)的二叉鏈表中，空鏈域的個(gè)數(shù)為_(kāi)n+1_。28一棵有 n 個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)共有_2n-1_個(gè)結(jié)點(diǎn)。29

57、深度為 5 的二叉樹(shù)至多有 31 個(gè)結(jié)點(diǎn)。30若某二叉樹(shù)有 20 個(gè)葉子結(jié)點(diǎn)，有 30 個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，則該二叉樹(shù)的總結(jié)點(diǎn)個(gè)數(shù)為 69 。31某二叉樹(shù)的前序遍歷序列是abdgcefh，中序序列是dgbaechf，其后序序列為gdbehfca 。32線(xiàn)索二叉樹(shù)的左線(xiàn)索指向其遍歷序列中的前驅(qū)，右線(xiàn)索指向其遍歷序列中的后繼。33在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n 無(wú)關(guān)的查找方法是散列查找精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 35 頁(yè)，共 38 頁(yè) - - - - - - - - -法。34 在分塊索引查找方法中， 首先查找索引表， 然后查找相應(yīng)的塊表。35 一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一棵二叉排序樹(shù)而變成一個(gè)有序序列， 構(gòu)造樹(shù)的過(guò)程即為對(duì)無(wú)序序列進(jìn)行排序的過(guò)程。36具有 10 個(gè)頂點(diǎn)的無(wú)向圖，邊的總數(shù)最多為_(kāi)45_。37已知圖g 的鄰接表