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

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

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

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

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

5、復(fù)雜度為，最壞情況下的時間復(fù)雜度為。三、運算題 (每小題 6 分，共 24 分) 1假定一棵二叉樹廣義表表示為a(b(c ，d)，c( ，8) ，分別寫出對它進行先序、中序、后序和后序遍歷的結(jié)果。先序：中序；后序： 2已知一個帶權(quá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 ，則求出該圖的最小生成樹的權(quán)。最小生成樹的權(quán)； 3假定一組記錄的排序碼為(46，79，56，38，40，84，50，42) ，則利用堆排序方法建立的初始堆為。 4有 7 個帶權(quán)結(jié)

6、點，其權(quán)值分別為3，7，8，2，6，10，14，試以它們?yōu)槿~子結(jié)點生成一棵哈夫曼樹，求出該樹的帶權(quán)路徑長度、高度、雙分支結(jié)點數(shù)。帶權(quán)路徑長度：高度：雙分支結(jié)點數(shù)：。四、閱讀算法，回答問題(每小題 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í)行后，得到的線性表l 為： 2void ag(

7、queue&q) 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 2 頁，共 38 頁 - - - - - - - - - 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é)果為：五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容( 每

8、小題 6 分，共 12 分) 1從一維數(shù)組 an) 中二分查找關(guān)鍵字為k 的元素的遞歸算法，若查找成功則返回對應(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é)點的層號為1 向子樹中查找x 結(jié)點 else int clnodelevel(bt 一left ，x)； if(cl1)return cl+1; int c2； if；若樹中不存在x結(jié)點則返回 o else ret

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

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

11、，46，50，38) 6 分 4帶權(quán)路徑長度： 131 3 分高度：5 2 分雙分支結(jié)點數(shù)： 6 1 分四、閱讀算法，回答問題(每小題 8 分，共 16 分) 評分標(biāo)準(zhǔn)：每小題正確得 8 分，出現(xiàn)一處錯誤扣 4 分，兩處及以上錯誤不得分。 1(36，12，8，50，25，5，15) 25 15 8 6 20 28 五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容( 每小題 6 分，共 12 分) 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 4 頁，共 38 頁 - - - - - - - - - 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 分六、編寫算法 (8 分) 評分標(biāo)準(zhǔ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)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guā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ù)的存儲結(jié)構(gòu)和數(shù)據(jù)的運算精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 5 頁，共 38 頁 - - - - - - - - -這三個方面的內(nèi)容。4. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是線性結(jié)構(gòu)和非線性結(jié)構(gòu)。5. 線性結(jié)構(gòu)中元素之間存在一對一關(guān)系，樹形結(jié)構(gòu)

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

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

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

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

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

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

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

21、結(jié)點的無向圖最多有條邊。 a14 b. 28 c. 56 d. 112 （c）21. 有 8 個結(jié)點的有向完全圖有條邊。 a14 b. 28 c. 56 d. 112 （b）22在表長為的鏈表中進行線性查找，它的平均查找長度為. ; . （）; 精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 14 頁，共 38 頁 - - - - - - - - -. 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對 22 個記錄的有序表作折半查找，當(dāng)查找失敗時，至少需要比較次關(guān)鍵字。a3 b4 c5 d 6 （a）25. 鏈表適用于查找a順序 b二分法 c順序，也能二分法 d隨機數(shù)據(jù)結(jié)構(gòu)與算法復(fù)習(xí)題一、選擇題。1在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為 c 。a動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) b緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)c 線性結(jié)構(gòu)和非線性結(jié)構(gòu) d內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)2數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的表示是指 a 。a數(shù)據(jù)的存儲結(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)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的 a 結(jié)構(gòu)。a邏輯 b存儲 c邏輯和

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

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

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

26、 帶頭結(jié)點的雙循環(huán)鏈表17需要分配較大空間，插入和刪除不需要移動元素的線性表，其存儲結(jié)構(gòu)是b 。a單鏈表 b 靜態(tài)鏈表 c線性鏈表 d順序存儲結(jié)構(gòu)18非空的循環(huán)單鏈表head 的尾結(jié)點（由 p 所指向）滿足 c 。ap-next = null bp = null c p-next =head dp = head 19在循環(huán)雙鏈表的p 所指的結(jié)點之前插入s 所指結(jié)點的操作是 d 。精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 18 頁，共 38 頁 - - - - - - - - -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 個結(jié)點及其前驅(qū)，則采用 d 存儲方式最節(jié)省時間。a單鏈表 b 雙鏈表 c單循環(huán)鏈表 d 順序表21在一個具有 n 個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然保持有

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

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

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

31、a訪問第 i （1=i=n）個結(jié)點和求第 i 個結(jié)點的直接前驅(qū)（ 1i=n）b在第 i （1=i=n）個結(jié)點后插入一個新結(jié)點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線性表的順序存儲結(jié)構(gòu)是一種 a 。a隨機存取的存儲結(jié)構(gòu) b順序存取的存儲結(jié)構(gòu)c索引存取的存儲結(jié)構(gòu) dhash存取的存儲結(jié)構(gòu)37棧的特點是 b ，隊列的特點是 a 。a先進先出 b先進后出38棧和隊列的共同點是 c 。a都是先進后出 b都是先進先出c 只允

32、許在端點處插入和刪除元素 d沒有共同點39一個棧的進棧序列是a，b，c，d，e，則棧的不可能的輸出序列是 c 。aedcba bdecba c dceab dabcde 40設(shè)有一個棧，元素依次進棧的順序為a、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 不是隊列的基本運算？精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 22 頁，共 38 頁 - - - - - - - - -a從隊尾插入一個新元素 b從隊列中刪除第i 個元素c 判斷一個隊列是否

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

34、的入隊序列是1，2，3，4，則隊列的輸出序列是 b 。a4，3，2，1 b1，2，3，4 c 1，4，3，2 d3，2，4，1 46判定一個循環(huán)隊列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 頁，共 38 頁 - - - - - - - - -47在循環(huán)隊列中，若front與 rear 分別表

35、示對頭元素和隊尾元素的位置，則判斷循環(huán)隊列空的條件是 c 。afront=rear+1 brear=front+1 c front=rear dfront=0 48 向一個棧頂指針為h 的帶頭結(jié)點的鏈棧中插入指針s 所指的結(jié)點時， 應(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時，經(jīng)過的棧操作為 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若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間v1 m ，top1 、top2 分別代表第 1 和第 2 個棧的棧頂， 棧 1 的底在 v1 ，棧 2 的底在 vm，則棧滿的條件是b 。a |top2-top1|=0 btop1+1=top2 ctop1+top2=m d top1=top2 51設(shè)計一個判別表達(dá)式中左、右括號是否配對出現(xiàn)的算法，采用 d 數(shù)據(jù)結(jié)構(gòu)最佳。a線性表的順序存儲結(jié)構(gòu) b隊列 c 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) d棧52允許對隊列進行的操作有 d 。精品學(xué)習(xí)資料 可選擇p d f - - -

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

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

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

40、內(nèi)，該數(shù)組按行存放，元素a85的起始地址為 c 。asa 141 b sa144 csa 222 dsa 225 63數(shù)組 a中，每個元素的長度為3 個字節(jié)，行下標(biāo)i 從 1 到 8，列下標(biāo) j 從 1 到10，從首地址 sa開始連續(xù)存放的存儲器內(nèi)，該數(shù)組按行存放，元素a58的起始精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 26 頁，共 38 頁 - - - - - - - - -地址為 c 。asa 141 b sa180 csa 222 dsa 225 64若聲明一個浮點數(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 按行存儲在數(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有一個 10090 的稀疏矩陣，非 0 元素有 10，設(shè)每個整型數(shù)占2 個字節(jié)，則用三元組表示該矩陣時，所需的字節(jié)數(shù)是 b 。a20 b 66 c18 000 d33 67數(shù)組 a0 4 ，-1 -3 ，5 7 中含有的元素個數(shù)是 a 。a55 b 45 c36 d16 68對矩陣進行

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

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

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

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

46、第 29 頁，共 38 頁 - - - - - - - - -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已知一個圖，如圖所示，若從頂點a 出發(fā)按深度搜索法進行遍歷，則可能得到的一種頂點序列為_d_； 按廣度搜索法進行遍歷，則可能得到的一種頂點序列為_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采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的_a_ 。a先序遍歷 b中序遍歷 c后序遍歷 d按層遍歷86采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的_d_ 。a先序遍歷 b中序遍歷 c后序遍歷 d按層遍歷87具有 n 個結(jié)點的連通圖至少有 a 條邊。 a n-1 b n c n(n-1)/2 d 2n abcdef精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 30 頁，共 38 頁 - - - - - - - - -88廣義表（a） ，a）的表頭是 c ，表尾是 c 。aa b （） c （a）

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

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

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

51、泡排序 c插入排序 d。選擇排序精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - - - - - - 第 32 頁，共 38 頁 - - - - - - - - -99在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是d 。a希爾排序 b冒泡排序 c直接插入排序 d直接選擇排序100堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。下列關(guān)鍵碼序列 d 是一個堆。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、表中進行操作比在順序表中進行操作效率高。a順序查找 b折半查找 c 分塊查找 d插入103直接選擇排序的時間復(fù)雜度為 d 。 （n 為元素個數(shù)）ao （n) bo(log2n) co(nlog2n) d o(n2) 二、填空題。1數(shù)據(jù)邏輯結(jié)構(gòu)包括線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)三種類型，樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱非線性結(jié)構(gòu)。2數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)4 種。3在線性結(jié)構(gòu)中， 第一個結(jié)點沒有 前驅(qū)結(jié)點， 其余每個結(jié)點有且只有 1 個前驅(qū)結(jié)點；最后一個結(jié)點沒有后續(xù)結(jié)點，其余每個結(jié)點有且只有 1 個后續(xù)結(jié)點。精品學(xué)習(xí)資料 可選擇p d f - - - - - - - - - -

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

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

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

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

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