大學(xué)數(shù)據(jù)結(jié)構(gòu)期末考試題

1、下載可編輯“數(shù)據(jù)結(jié)構(gòu)”期末考試試題一、 單選題(每小題 2 分，共 12 分)1.在一個(gè)單鏈表 HL 中，若要向表頭插入一個(gè)由指針p 指向的結(jié)點(diǎn)，則執(zhí)行()。A. HL = ps p 一 next = HLB. p 一next= HL; HL= p3C. p 一next = Hl; p= HL;D. p 一next= HL 一next;HL 一next = p；2. n 個(gè)頂點(diǎn)的強(qiáng)連通圖中至少含有()。A.n l 條有向邊 B.n 條有向邊C.n(n 1) /2 條有向邊 D.n(n 1)條有向邊3.從一棵二叉搜索樹中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為()。A.0(1)B.0( n)C.0(1

2、0gz n) D.O( n2)4 .由權(quán)值分別為 3, 8, 6, 2, 5 的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長(zhǎng)度為()。A . 24 B . 48C.72 D .535 .當(dāng)一個(gè)作為實(shí)際傳遞的對(duì)象占用的存儲(chǔ)空間較大并可能需要修改時(shí)，應(yīng)最好把它說明為()參數(shù)，以節(jié)省參數(shù)值的傳輸時(shí)間和存儲(chǔ)參數(shù)的空間。A.整形 B.引用型C.指針型 D.常值引用型6向一個(gè)長(zhǎng)度為 n 的順序表中插人一個(gè)新元素的平均時(shí)間復(fù)雜度為()。A . O(n) B . O(1)C . O(n2) D . O(10g2n)二、 填空題(每空 1 分，共 28 分)1.- 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)被分為、和四種。2.在廣義表的存儲(chǔ)結(jié)

3、構(gòu)中，單元素結(jié)點(diǎn)與表元素結(jié)點(diǎn)有一個(gè)域?qū)?yīng)不同，各自分別為一一域和一一域。3.中綴表達(dá)式 3 十 x*(2.4 /5 6)所對(duì)應(yīng)的后綴表達(dá)式為-。4 .在一棵高度為 h 的 3 叉樹中，最多含有一一結(jié)點(diǎn)。5 .假定一棵二叉樹的結(jié)點(diǎn)數(shù)為18,則它的最小深度為一一，最大深度為6.在一棵二叉搜索樹中，每個(gè)分支結(jié)點(diǎn)的左子樹上所有結(jié)點(diǎn)的值一定一一該結(jié)點(diǎn)的值，右子樹上所 有結(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í)，

4、其時(shí)間復(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)度 n= 144 的線性表進(jìn)行索引順序查找，并假定每個(gè)子表的長(zhǎng)度均為，則進(jìn)行索引順序查找的平均查找長(zhǎng)度為，時(shí)間復(fù)雜度為-12. 一棵 B樹中的所有葉子結(jié)點(diǎn)均處在上。13.每次從無序表中順序取出一個(gè)元素，把這插入到有序表中的適當(dāng)位置，此種排序方法叫做一一排序；每次從無序表中挑選出一個(gè)最小或最大元素，把它交換到有序表的一端，此種排序方法叫做 排序。14.快速排序在乎均

5、情況下的時(shí)間復(fù)雜度為一一，最壞情況下的時(shí)間復(fù)雜度為一一。三、運(yùn)算題(每小題 6 分，共 24 分)1.假定一棵二叉樹廣義表表示為a(b(c , d), c( , 8)，分別寫出對(duì)它進(jìn)行先序、中序、后序和后下載可編輯序遍歷的結(jié)果。先序：.專業(yè).整理.下載可編輯.專業(yè).整理.中序; 后序:2已知一個(gè)帶權(quán)圖的頂點(diǎn)集V 和邊集 G 分別為：V = 0 , 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)；

6、3假定一組記錄的排序碼為(46, 79 , 56 , 38 , 40 , 84 , 50 , 42),則利用堆排序方法建立的初始堆為- 。4有 7 個(gè)帶權(quán)結(jié)點(diǎn)，其權(quán)值分別為3 ,乙 8 , 2 , 6 , 10 , 14，試以它們?yōu)槿~子結(jié)點(diǎn)生成一棵哈夫曼樹，求出該樹的帶權(quán)路徑長(zhǎng)度、高度、雙分支結(jié)點(diǎn)數(shù)。帶權(quán)路徑長(zhǎng)度：一一 高度：一一雙分支結(jié)點(diǎn)數(shù)：一一。四、閱讀算法，回答問題(每小題 8 分，共 16 分)1 VOIdAC(List&L)In itList(L) ；In sertRear(L;25) ;InsertFront(L, 50);IntaL4 = 5 , 8 , 12 , 15

7、, 36;for(i nti = 0; i5; i+)if (ai% 2 = = 0)I nsertFr on t(L , ai);elsel nsertRear(L, ai);該算法被調(diào)用執(zhí)行后，得到的線性表L 為:2 void AG(Queue&Q)Ini tQueue(Q);inta5= 6 , 12 , 5 , 15 , 8;for(i nt i= 0;i5; i+)QI nsert(Q, ai)Qinsert(Q, QDelete(Q);Qinsert(Q, 20);Qinsert(Q, QDelete(Q)十 16);while(!QueueEmpty(Q)coutvvQD

8、elete(Q)vv該算法被調(diào)用后得到的輸出結(jié)果為：五、算法填空，在畫有橫線的地方填寫合適的容K 的元素的遞歸算法，若查找成功則返回對(duì)應(yīng)元素的下標(biāo),否則返回一 1IntBinsch(ElemTypeA, Intlow , int high , KeyTypeK)if(low= high)int mid= (low+high) /2;if(K = = Amid.key)- ;else if (Kdata = = X)return 1;/根結(jié)點(diǎn)的層號(hào)為 1/向子樹中查找 x 結(jié)點(diǎn)elseint cl = NodeLevel(BT 一 left , X)； if(cl = 1)return cl+1

9、;int c2 =:/若樹中不存在 X 結(jié)點(diǎn)則返回 oelse return 0:六、編寫算法(8 分)按所給函數(shù)聲明編寫一個(gè)算法，從表頭指針為 函數(shù)返回，若單鏈表為空則中止運(yùn)行。ElemType MaxValue(LNOde*HL);“數(shù)據(jù)結(jié)構(gòu)”期末考試試題答案一、單選題(每小題 2 分，共 12 分)評(píng)分標(biāo)準(zhǔn)；選對(duì)者得 2 分，否則不得分。1. B 2. B 3. C 4 . D 5 . B 6. A二、填空題(每空 1 分，共 28 分)1順序結(jié)構(gòu) 結(jié)構(gòu)索引結(jié)構(gòu)散列結(jié)構(gòu)(次序無先后)2.值(或 data) 子表指針(或 sublist)3. 3 x 2 . 4 5 / 6 一 * 十4.

10、 (3h一 1) / 25.5186.小于大于(或大于等于)7.向上堆頂8.鄰接矩陣鄰接表邊集數(shù)組(次序無先后)9. 0( n2) O(e)10.1 311. 130()12.同一層13.插人 選擇14. 0(nlog2n) 0(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 .最小生成樹的權(quán)：31/ 6 分3. (84 , 79, 56, 42, 40, 46, 50, 38)/ 6 分4.帶權(quán)路徑長(zhǎng)度：131/ 3 分HL

11、的單鏈表中查找出具有最大值的結(jié)點(diǎn)，該最大值由下載可編輯.專業(yè).整理.高度：5/ 2 分雙分支結(jié)點(diǎn)數(shù)：6/ 1 分四、 閱讀算法，回答問題(每小題 8 分，共 16 分)評(píng)分標(biāo)準(zhǔn)：每小題正確得8 分，出現(xiàn)一處錯(cuò)誤扣 4 分，兩處及以上錯(cuò)誤不得分1. (36 , 12, 8, 50, 25, 5, 15)2. 5 15 8 6 20 28五、 算法填空，在畫有橫線的地方填寫合適的容(每小題 6 分，共 12 分)1. feturn mid/ 2 分returnBinsch(A, low , mid 一 1 , K) /2 分returnBmsch(A , mid+1 , high , K) / 2

12、 分2. NodeLevel(BT right , X) / 3 分(c2=1)returnc2 十 1/ 3 分六、 編寫算法(8 分)評(píng)分標(biāo)準(zhǔn)：請(qǐng)參考語(yǔ)句后的注釋，或根據(jù)情況酌情給分。ElemType MaxValue(LNodeO* HL 。) if (HL= =NUIL)/ 2 分cerrLinked llst is empty!” data ;/ 3 分LNOde*p=HI next ;/ 4 分while(P! : NULL) / 7 分 if(maxdata)max = p 一 data ； p = p 一next ；returnmax ；/ 8 分?jǐn)?shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料一、填空題1.

13、數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(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)算這三個(gè)方面的容。4.數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是_線性結(jié)構(gòu)和_非線性結(jié)構(gòu) _。5.線性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對(duì)多關(guān)系，圖形結(jié)構(gòu)中元素之間存 在多對(duì)多關(guān)系。6.在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn) _沒有_前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1 個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)沒有_后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1

14、個(gè)后續(xù)結(jié)點(diǎn)。7.在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有 前驅(qū)一結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有后續(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)健⑺饕蜕⒘?。下載可編輯.專業(yè).整理.10. 數(shù)據(jù)的運(yùn)算最常用的有 5 種，它們分別是 插入、刪除、修改、 查找、排序。11. 一個(gè)算法的效率可分為 _時(shí)間_效率和 _空間_效率。12. 在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)_表中一半元素，具體移動(dòng)的元素個(gè)數(shù)與表長(zhǎng)和該元素在表中的位置 _有關(guān)。13.

15、 線性表中結(jié)點(diǎn)的集合是有限_的，結(jié)點(diǎn)間的關(guān)系是 _一對(duì)一_ 的。14. 向一個(gè)長(zhǎng)度為 n 的向量的第 i元素（1 i n+1）之前插入一個(gè)元素旺 需向后移動(dòng)_n-i+1 _個(gè)元素。15. 向一個(gè)長(zhǎng)度為 n 的向量中刪除第 i 個(gè)元素（1 i n）時(shí)，需向前移動(dòng)_n-i _個(gè)元素。16. 在順序表中訪問任意一結(jié)點(diǎn)的時(shí)間復(fù)雜度均為 0（1） _,因此，順序表也稱為隨機(jī)存取_的數(shù)據(jù)結(jié)構(gòu)。 17順序表中邏輯上相鄰的元素的物理位置 _必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置 不一定 相鄰。18在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由_其直接前驅(qū)結(jié)點(diǎn)的鏈域的值 _指示。19.在 n 個(gè)結(jié)點(diǎn)的單

16、鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p，需找到它的前驅(qū)結(jié)點(diǎn)的地址，其時(shí)間復(fù)雜度為 0 （n）。20. 向量、棧和隊(duì)列都是線性 _結(jié)構(gòu)，可以在向量的任何_位置插入和刪除元素；對(duì)于棧只能在棧頂_插入和刪除元素；對(duì)于隊(duì)列只能在 _隊(duì)尾_ 插入和_隊(duì)首_刪除元素。21. 棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為二棧頂二。不允許插入和刪除運(yùn)算的一端稱為_ 棧底_。22. _隊(duì)列_是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。23. _不包含任何字符（長(zhǎng)度為 0）的串_稱為空串；_ 由一個(gè)或多個(gè)空格（僅由空格符）組成的串_ 稱為空白串。24. 子串的定位運(yùn)算稱為串的模式匹配；_被匹配

17、的主串 _稱為目標(biāo)串，子串_稱為模式。25.假設(shè)有二維數(shù)組Ax8，每個(gè)元素用相鄰的 6 個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知A 的起始存儲(chǔ)位置（基地址）為 1000,則數(shù)組 A 的體積（存儲(chǔ)量）為 288 B;末尾元素 A57的第一個(gè)字節(jié)地址為1282;若按行存儲(chǔ)時(shí)，元素 Au 的第一個(gè)字節(jié)地址為（8+4） X 6+1000=1072;若按列存儲(chǔ)時(shí)，元素 A47的第一個(gè)字節(jié)地址為（6 X 7+ 4） X 6+ 1000）= 1276。26.由 3 個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹有 _5_種形態(tài)。27.一棵深度為 6 的滿二叉樹有_m+n2=0+ n2= n。-仁 31 _個(gè)分支結(jié)點(diǎn)和_26-1=32個(gè)葉子

18、。注：滿二叉樹沒有度為 1 的結(jié)點(diǎn)，所以分支結(jié)點(diǎn)數(shù)就是二度結(jié)點(diǎn)數(shù)。28.一棵具有 2 5 7個(gè)結(jié)點(diǎn)的完全二叉樹，它的深度為9_ 。（注：用 log2（n） +1= 8.xx +仁 929設(shè)一棵完全二叉樹有 700 個(gè)結(jié)點(diǎn)，則共有_ 350 個(gè)葉子結(jié)點(diǎn)。答：最快方法：用葉子數(shù)=n/2 = 35030.設(shè)一棵完全二叉樹具有1000 個(gè)結(jié)點(diǎn)，則此完全二叉樹有 _500_個(gè)葉子結(jié)點(diǎn)，有_499_個(gè)度為 2的結(jié)點(diǎn)，有1個(gè)結(jié)點(diǎn)只有非空左子樹，有 _0_ 個(gè)結(jié)點(diǎn)只有非空右子樹。答：最快方法：用葉子數(shù)=n/2 = 500 , n2=no-1=499。另外，最后一結(jié)點(diǎn)為 2i 屬于左葉子，右葉子是 空的，所以有

19、1 個(gè)非空左子樹。完全二叉樹的特點(diǎn)決定不可能有左空右不空的情況，所以非空右子樹數(shù)=0.31.在數(shù)據(jù)的存放無規(guī)律而言的線性表中進(jìn)行檢索的最佳方法是_順序查找（線性查找） _。32. 線性有序表（a1, a2, a3,，a256）是從小到大排列的，對(duì)一個(gè)給定的值k,用二分法檢索表中與 k 相等的元素，在查找不成功的情況下，最多需要檢索_8 _次。設(shè)有 100 個(gè)結(jié)點(diǎn)，用二分法查找時(shí)，最大比下載可編輯.專業(yè).整理.較次數(shù)是_7_ 。33. 假設(shè)在有序線性表 a20上進(jìn)行折半查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)為1;比較兩次查找成功的結(jié)點(diǎn)數(shù)為_ 2;比較四次查找成功的結(jié)點(diǎn)數(shù)為_ 8 ;平均查找長(zhǎng)度為3.7

20、 。解：顯然，平均查找長(zhǎng)度= O （loggn） 5 次（25）。但具體是多少次，則不應(yīng)當(dāng)按照公式ASL口log2(n 1)來計(jì)算(即(21 X log221) /20 = 4.6 次并不正確！)。因?yàn)檫@是在假設(shè) n = 2 匸 的情況下n推導(dǎo)出來的公式。應(yīng)當(dāng)用窮舉法羅列：全部元素的查找次數(shù)為=(1 + 2X 2+ 4X 3+ 8X 4+ 5X 5)= 74; ASL = 74/20=3.7!34._ 折半查找有序表(4, 6, 12, 20, 28, 38, 50, 70, 88, 100),若查找表中元素 20,它將依次與表 中元素 _ 28 , 6, 12, 20比較大小。35. 在各種

21、查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n 無關(guān)的查找方法是散列查找 _。36. 散列法存儲(chǔ)的基本思想是由 _關(guān)鍵字的值_ 決定數(shù)據(jù)的存儲(chǔ)地址。二、判斷正誤(在正確的說法后面打勾，反之打叉 (X ) 1.鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針。答：錯(cuò)誤。鏈表中的結(jié)點(diǎn)可含多個(gè)指針域，分別存放多個(gè)指針。例如，雙向鏈表中的結(jié)點(diǎn)可以含有兩個(gè)指 針域，分別存放指向其直接前趨和直接后繼結(jié)點(diǎn)的指針。(X ) 2.鏈表的物理存儲(chǔ)結(jié)構(gòu)具有同鏈表一樣的順序。錯(cuò)，鏈表的存儲(chǔ)結(jié)構(gòu)特點(diǎn)是無序，而鏈表的示意圖有序。(X ) 3.鏈表的刪除算法很簡(jiǎn)單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算機(jī)會(huì)自動(dòng)地將后續(xù)的各個(gè)單元向 前移動(dòng)。錯(cuò)，鏈表的結(jié)點(diǎn)

22、不會(huì)移動(dòng)，只是指針容改變。(X ) 4.線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。錯(cuò)，混淆了邏輯結(jié)構(gòu)與物理結(jié)構(gòu)，鏈表也是線性表！且即使是順序表，也能存放記錄型數(shù)據(jù)。(X ) 5順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。錯(cuò)，正好說反了。順序表才適合隨機(jī)存取，鏈表恰恰適于“順藤摸瓜”(X ) 6.順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。錯(cuò)，前一半正確，但后一半說法錯(cuò)誤，那是鏈?zhǔn)酱鎯?chǔ)的優(yōu)點(diǎn)。順序存儲(chǔ)方式插入、刪除運(yùn)算效率較低，在 表長(zhǎng)為 n的順序表中，插入和刪除一個(gè)數(shù)據(jù)元素，平均需移動(dòng)表長(zhǎng)一半個(gè)數(shù)的數(shù)據(jù)元素。(X ) 7.線性表在物理存儲(chǔ)空

23、間中也一定是連續(xù)的。錯(cuò)，線性表有兩種存儲(chǔ)方式，順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。后者不要求連續(xù)存放。(X ) 8.線性表在順序存儲(chǔ)時(shí)，邏輯上相鄰的元素未必在存儲(chǔ)的物理位置次序上相鄰。錯(cuò)誤。線性表有兩種存儲(chǔ)方式，在順序存儲(chǔ)時(shí)，邏輯上相鄰的元素在存儲(chǔ)的物理位置次序上也相鄰。(X ) 9.順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。錯(cuò)誤。順序存儲(chǔ)方式不僅能用于存儲(chǔ)線性結(jié)構(gòu)，還可以用來存放非線性結(jié)構(gòu)，例如完全二叉樹是屬于非線 性結(jié)構(gòu)，但其最佳存儲(chǔ)方式是順序存儲(chǔ)方式。(后一節(jié)介紹)(X ) 10.線性表的邏輯順序與存儲(chǔ)順序總是一致的。錯(cuò)，理由同 7。鏈?zhǔn)酱鎯?chǔ)就無需一致。(X ) 11.線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表

24、的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。錯(cuò)，線性表是邏輯結(jié)構(gòu)概念，可以順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)，與元素?cái)?shù)據(jù)類型無關(guān)。(X ) 12.在表結(jié)構(gòu)中最常用的是線性表，棧和隊(duì)列不太常用。錯(cuò)，不一定吧？調(diào)用子程序或函數(shù)常用，CPU 中也用隊(duì)列。(V ) 13.棧是一種對(duì)所有插入、刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。(V ) 14.對(duì)于不同的使用者，一個(gè)表結(jié)構(gòu)既可以是棧，也可以是隊(duì)列，也可以是線性表。正確，都是線性邏輯結(jié)構(gòu)，棧和隊(duì)列其實(shí)是特殊的線性表，對(duì)運(yùn)算的定義略有不同而已。X ) 15.棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。錯(cuò)，棧是邏輯結(jié)構(gòu)的概念，是特殊殊線性表，而鏈表是存儲(chǔ)結(jié)構(gòu)概念，二者不是同類項(xiàng)。(

25、X ) 16.棧和隊(duì)列是一種非線性數(shù)據(jù)結(jié)構(gòu)。下載可編輯.專業(yè).整理.錯(cuò)，他們都是線性邏輯結(jié)構(gòu)，棧和隊(duì)列其實(shí)是特殊的線性表，對(duì)運(yùn)算的定義略有不同而已。(V ) 17.棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是方式。(V ) 18.兩個(gè)棧共享一片連續(xù)存空間時(shí)，為提高存利用率，減少溢出機(jī)會(huì)，應(yīng)把兩個(gè)棧的棧底分別 設(shè)在這片存空間的兩端。(X ) 19.隊(duì)是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。 錯(cuò)，后半句不對(duì)。(X )20. 一個(gè)棧的輸入序列是 12345,則棧的輸出序列不可能是12345。錯(cuò)，有可能。V) 21.若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n 個(gè)結(jié)點(diǎn)的二叉樹鏈表中只

26、有 n1 個(gè)非空指針域。X ) 22.二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹的高度差等于1。V) 23.二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹是有序的。(X ) 24.二叉樹中每個(gè)結(jié)點(diǎn)有兩棵非空子樹或有兩棵空子樹。(X ) 25. 二叉樹中每個(gè)結(jié)點(diǎn)的關(guān)鍵字值大于其左非空子樹(若存在的話)所有結(jié)點(diǎn)的關(guān)鍵字值，且小于其右非空子樹(若存在的話)所有結(jié)點(diǎn)的關(guān)鍵字值。(應(yīng)當(dāng)是二叉排序樹的特點(diǎn))X ) 26. 二叉樹中所有結(jié)點(diǎn)個(gè)數(shù)是 2k-1-1，其中 k 是樹的深度。(應(yīng) 2i-1 )X ) 27. 二叉樹中所有結(jié)點(diǎn)，如果不存在非空左子樹，則不存在非空右子樹。(X ) 28.對(duì)于一棵非空二叉樹，它的根結(jié)點(diǎn)作為第一層，則它的第i

27、 層上最多能有 2i 1 個(gè)結(jié)點(diǎn)。(應(yīng)2i-1)(V ) 29.用二叉鏈表法(link-rlink)存儲(chǔ)包含 n 個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的 2n 個(gè)指針區(qū)域中有 n+1 個(gè)為空指針。(V ) 30.具有 12 個(gè)結(jié)點(diǎn)的完全二叉樹有 5 個(gè)度為 2 的結(jié)點(diǎn)。三、單項(xiàng)選擇題(B ) 1.非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種：A) 對(duì)多關(guān)系B )多對(duì)多關(guān)系C )多對(duì)一關(guān)系 D ) 一對(duì)一關(guān)系(C ) 2.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的 _ 結(jié)構(gòu)；A)存儲(chǔ) B) 物理 C) 邏輯D)物理和存儲(chǔ)(C ) 3.算法分析的目的是：A)找出數(shù)據(jù)結(jié)構(gòu)的合理性B)研究算法中的輸入和輸出的關(guān)系C)分析算法的效

28、率以求改進(jìn)D)分析算法的易懂性和文檔性(A ) 4.算法分析的兩個(gè)主要方面是：A)空間復(fù)雜性和時(shí)間復(fù)雜性B)正確性和簡(jiǎn)明性C)可讀性和文檔性D)數(shù)據(jù)復(fù)雜性和程序復(fù)雜性(C ) 5.計(jì)算機(jī)算法指的是：A)計(jì)算方法B) 排序方法 C)解決問題的有限運(yùn)算序列D)調(diào)度方法(B ) 6.計(jì)算機(jī)算法必須具備輸入、輸出和 _等 5 個(gè)特性。A)可行性、可移植性和可擴(kuò)充性B)可行性、確定性和有窮性C)確定性、有窮性和穩(wěn)定性D)易讀性、穩(wěn)定性和安全性(C ) 7數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱之為：(A)存儲(chǔ)結(jié)構(gòu)(B)邏輯結(jié)構(gòu)(C)順序存儲(chǔ)結(jié)構(gòu)(D)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(B ) 8. 一

29、個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100,每個(gè)元素的長(zhǎng)度為 2,則第 5 個(gè)元素的地址是 _(A)110(B) 108(C) 100(D) 120(A ) 9.在 n 個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是0( 1)的操作是：(A)訪問第 i 個(gè)結(jié)點(diǎn)(1 i n)和求第 i 個(gè)結(jié)點(diǎn)的直接前驅(qū)(2 i n)(B)在第 i 個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)(K i n)(C)刪除第 i 個(gè)結(jié)點(diǎn)(K i top0B. n=iC. n-i+1判定一個(gè)棧 ST (最多元素為B. ST-top=0C.?？談t進(jìn)D.棧滿則出1 , 2, 3,，n,其輸出序列為 p1, p2, p3，pn,若 p1= n.D.不確定m0 為空的

30、條件是C. ST-topvmOD. ST-top=mO下載可編輯.專業(yè).整理.C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D .部結(jié)構(gòu)和外部結(jié)構(gòu)2 .數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)存中的表示是指 _A_ 。下載可編輯.專業(yè).整理.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ī)無關(guān)的是數(shù)據(jù)的_A結(jié)構(gòu)。A.邏輯 B 存儲(chǔ) C 邏輯和存儲(chǔ)D 物理4 在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ)_C_。A.數(shù)據(jù)的處理方法B.數(shù)據(jù)元素的類型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ù)的多少

31、C.對(duì)數(shù)據(jù)有哪些運(yùn)算D 所用的編程語(yǔ)言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便。6 以下說法正確的是 _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)7算法分析的目的是_C_，算法分析的兩個(gè)主要方面是_A_(1)A. 找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入和輸出的關(guān)系C. 分析算法的效率以求改進(jìn)C.分析算法的易讀性和文檔性A. 空間復(fù)雜度和時(shí)間復(fù)雜度B.正確性和簡(jiǎn)明性C可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性s =0;for( I =0; ivn; i+)for(j=0;jv n;j+) s+=Bij;sum

32、 = s ;9 下面程序段的時(shí)間復(fù)雜度是for( i =0; in; i+)for(j=0;jm;j+)Aij= 0;10 下面程序段的時(shí)間復(fù)雜度是i = 0 ;while (i=n )i = i * 311 在以下的敘述中，正確的是 _B next =NULLC. head- next =head D head!=NULL16 .若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)，則采用D_存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A.單鏈表 B .給出表頭指針的單循環(huán)鏈表C .雙鏈表 D .帶頭結(jié)點(diǎn)的雙循環(huán)鏈表17 .需要分配較大空間，插入和刪除不需要移動(dòng)元素的線性表，其存儲(chǔ)結(jié)構(gòu)是_BA.

33、單鏈表 B .靜態(tài)鏈表 C .線性鏈表 D .順序存儲(chǔ)結(jié)構(gòu)18 .非空的循環(huán)單鏈表 head 的尾結(jié)點(diǎn)（由 p 所指向）滿足_C_A. p- next = NULL B . p = NULLC. p-n ext =head D . p = head20 .如果最常用的操作是取第 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)并仍然保持有序的時(shí)間復(fù)雜度是B_。A. O (1)B . O(n)C . O(n2)D . O(nIog2n )22 .在一個(gè)長(zhǎng)度為 n (n1)的單鏈表

34、上，設(shè)有頭和尾兩個(gè)指針，執(zhí)行_B_操作與鏈表的長(zhǎng)度有關(guān)。A. 刪除單鏈表中的第一個(gè)元素B. 刪除單鏈表中的最后一個(gè)元素C. 在單鏈表第一個(gè)元素前插入一個(gè)新元素D. 在單鏈表最后一個(gè)元素后插入一個(gè)新元素13鏈表不具備的特點(diǎn)是A.可隨機(jī)訪問任一結(jié)點(diǎn)C.不必事先估計(jì)存儲(chǔ)空間15.帶頭結(jié)點(diǎn)的單鏈表A. head = NULLhead 為空的判定條件是B head- next =NULLC. head-n ext =headD head!=NULL19 .在循環(huán)雙鏈表的A.B.C.D.p-prior = sp-prior = ss-n ext = pp 所指的結(jié)點(diǎn)之前插入 s 所指結(jié)點(diǎn)的操作是_D;s-

35、next = p ; p-prior-next = s;p-prior-next = s;s-prior = p-prior;s-prior = p-prior;s-next = p;p-prior = s;p-prior-next = so;s-prior = p-prior;s-prior = p-prior;p-prior-next = s;p-prior = s下載可編輯.專業(yè).整理.23 .與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是_DA. 插入、刪除操作更簡(jiǎn)單B. 可以進(jìn)行隨機(jī)訪問C. 可以省略表頭指針或表尾指針D. 順序訪問相鄰結(jié)點(diǎn)更靈活24.如果對(duì)線性表的操作只有兩種，即刪除第一個(gè)元素，

36、在最后一個(gè)元素的后面插入新元素，則最好使用 B_。A. 只有表頭指針沒有表尾指針的循環(huán)單鏈表B. 只有表尾指針沒有表頭指針的循環(huán)單鏈表C. 非循環(huán)雙鏈表D. 循環(huán)雙鏈表25.在長(zhǎng)度為n 的順序表的第 i 個(gè)位置上插入一個(gè)元素(K i n+1),元素的移動(dòng)次數(shù)為：AA. n - i + 1 B. n- i C . iD. i - 126 .對(duì)于只在表的首、尾兩端進(jìn)行插入操作的線性表，宜采用的存儲(chǔ)結(jié)構(gòu)為CA.順序表B.用頭指針表示的循環(huán)單鏈表C.用尾指針表示的循環(huán)單鏈表D .單鏈表27 .下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？_C_。A 插入運(yùn)算方便 B 可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示C 存儲(chǔ)密度大

37、D 刪除運(yùn)算方便28 .下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？_B_ 。A 線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元 B 線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。C 線性表采用鏈?zhǔn)酱鎯?chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元D 線性表采用鏈?zhǔn)酱鎯?chǔ)，便于進(jìn)行插入和刪除操作。29 .線性表是具有 n 個(gè)_B_的有限序列。A.字符 B .數(shù)據(jù)元素C .數(shù)據(jù)項(xiàng) D .表元素30 .在 n 個(gè)結(jié)點(diǎn)的線性表的數(shù)組實(shí)現(xiàn)中，算法的時(shí)間復(fù)雜度是0( 1)的操作是 A_ 。A .訪問第 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.

38、刪除第 i (1=inext=s ； s-next=p-nextBC. p-next=s ; p-next=s-nextD37.棧的特點(diǎn)是 B，隊(duì)列的特點(diǎn)是 AA.先進(jìn)先出 B先進(jìn)后出38棧和隊(duì)列的共同點(diǎn)是_C_。A.都是先進(jìn)后出B都是先進(jìn)先出C.只允許在端點(diǎn)處插入和刪除元素D 沒有共同點(diǎn)39. 一個(gè)棧的進(jìn)棧序列是 a, b, c, d, e,貝惟的不可能的輸出序列是 _C_A. edcba B . decba C . dceab D . abcde40.設(shè)有一個(gè)棧，元素依次進(jìn)棧的順序?yàn)锳. A,B,C,D,E B . B,C,D,E,A C41 .以下_B_不是隊(duì)列的基本運(yùn)算？A.從隊(duì)尾插入

39、一個(gè)新元素B.從隊(duì)列中刪除第 i 個(gè)元素C.判斷一個(gè)隊(duì)列是否為空D.讀取隊(duì)頭元素的值42 .若已知一個(gè)棧的進(jìn)棧序列是1,2,3, n,其輸出序列為 p1,p2,p3,，pn,若 pl = n,則 pi 為 _A. i B . n i C . n i +1 D .不確定s 的結(jié)點(diǎn)，正確的操作是Bs-next=p-next; p-next=s;p-next=s-next ； p-next=s36.線性表的順序存儲(chǔ)結(jié)構(gòu)是一種A.隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)A_ 。B順序存取的存儲(chǔ)結(jié)構(gòu)D. Hash 存取的存儲(chǔ)結(jié)構(gòu)A B、C、D E。下列 C是不可能的出棧序列E,A,B,C,D D . E,D,C,B,A下載可

40、編輯.專業(yè).整理.43 .判定一個(gè)順序棧st (最多元素為 MaxSize)為空的條件是A. st-top != -1B. st-top = -1C. st-top != MaxSize Dst-top = MaxSize44 .判定一個(gè)順序棧st (最多元素為 MaxSize)為滿的條件是A. st-top != -1Bst-top = -1C. st-top != MaxSize Dst-top = MaxSize45 . 一個(gè)隊(duì)列的入隊(duì)序列是1, 2, 3, 4,則隊(duì)列的輸出序列是A. 4, 3, 2, 1 B1, 2, 3, 4C. 1 , 4, 3, 2 D3, 2, 4, 1下載可

41、編輯.專業(yè).整理.46.判定一個(gè)循環(huán)隊(duì)列 qu （最多元素為 MaxSize）為空的條件是_C_。A. qu-rear - qu-front =MaxSize B. qu-rear - qu-front -1=MaxSizeC. qu-rear =qu-frontD. qu-rear =qu-front -147. 在循環(huán)隊(duì)列中，若 front 與 rear 分別表示對(duì)頭元素和隊(duì)尾元素的位置，貝 V 判斷循環(huán)隊(duì)列空的條件是C_。A. front=rear+1B . rear=front+1C . front=rearD . front=048 .向一個(gè)棧頂指針為 h 的帶頭結(jié)點(diǎn)的鏈棧中插入指針

42、s 所指的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行_D_操作A. h-n ext=s ; B . s-n ext=h;C. s-n ext=h ;h =s ; D . s-n ext=h- n ext;h-n ext=s;50 .若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間V1 m , top1、top2分別代表第 1 和第 2 個(gè)棧的棧頂，棧 1 的底在 V1，棧 2 的底在 Vm，則棧滿的條件是B 。A. |top2-top1|=0 B. top1+1=top2 C . top1+top2=m D . top1=top251 .設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對(duì)出現(xiàn)的算法，采用54 .若用一個(gè)大小為 6 的數(shù)值來實(shí)

43、現(xiàn)循環(huán)隊(duì)列，且當(dāng)前 rear 和 front 的值分別為 0 和 3,當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear 和 front 的值分別為_B_。A. 1 和 5 B . 2 和 4 C . 4 和 2 D . 5 和 155 .隊(duì)列的“先進(jìn)先出”特性是指_D_。A.最早插入隊(duì)列中的元素總是最后被刪除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)棧滿的情況B .通常不會(huì)出現(xiàn)棧空的情況C.插入操作更容易實(shí)現(xiàn)D .刪除操作更

44、容易實(shí)現(xiàn)57 .用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列，其頭指針指向隊(duì)頭結(jié)點(diǎn)，尾指針指向隊(duì)尾結(jié)點(diǎn)，貝恠進(jìn)行出隊(duì)操作ABC 可以變?yōu)?CBA 時(shí)，經(jīng)過的棧操作為_B_。push, pop, push, pop B . push, push, push, .push,pop, push,49 .輸入序列為A. push, pop,C. push, push, pop, pop , push, pop Dpop, pop ,push, pop,poppopA.線性表的順序存儲(chǔ)結(jié)構(gòu)B .隊(duì)列 C .線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D .棧52.允許對(duì)隊(duì)列進(jìn)行的操作有A .對(duì)隊(duì)列中的元素排序D_ 。B .取出最近進(jìn)隊(duì)的元素C

45、 .在隊(duì)頭元素之前插入元素D .刪除隊(duì)頭元素53.對(duì)于循環(huán)隊(duì)列 D。A.無法判斷隊(duì)列是否為空B .無法判斷隊(duì)列是否為滿.以上說法都不對(duì)D數(shù)據(jù)結(jié)構(gòu)最佳下載可編輯時(shí) _C_ 。A.僅修改隊(duì)頭指針B.僅修改隊(duì)尾指針C.隊(duì)頭、隊(duì)尾指針都可能要修改D隊(duì)頭、隊(duì)尾指針都要修改58.右串 S= software ,其子串的數(shù)目是B。9A. 8 B . 37 C . 36D.59.串的長(zhǎng)度是指 B。A.串中所含不同字母的個(gè)數(shù)B.串中所含字符的個(gè)數(shù)C.串中所含不同字符的個(gè)數(shù)D.串中所含非空格字符的個(gè)數(shù)60.串是一種特殊的線性表，其特殊性體現(xiàn)在BA.可以順序存儲(chǔ)C.可以鏈?zhǔn)酱鎯?chǔ)B .數(shù)據(jù)元素是一個(gè)字符D .數(shù)據(jù)元素

46、可以是多個(gè)字符61.設(shè)有兩個(gè)串 p 和 q,求 q 在 p 中首次出現(xiàn)的位置的運(yùn)算稱為BA.連接 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 開始 連續(xù)存放的存儲(chǔ)器，該數(shù)組按行存放，元素A85的起始地址為 C 。A. SA+141 B . SA +144 C . SA+ 222 D . SA 22563數(shù)組 A 中，每個(gè)元素的長(zhǎng)度為 3 個(gè)字節(jié)，行下標(biāo) i 從 1 到 8,列下標(biāo) j 從 1 到 10，從首地址 SA 開始 連續(xù)存放的存儲(chǔ)器，該數(shù)組按行存放，元素A58的起始地址為

47、 C 。A. SA+141 B . SA +180 C . SA+ 222 D . SA 22564.若聲明一個(gè)浮點(diǎn)數(shù)數(shù)組如下：froat average=new float30;假設(shè)該數(shù)組的存起始位置為200, average15的存地址是 C 。A. 214 B . 215 C . 260 D . 25665.設(shè)二維數(shù)組 A1m,1n按行存儲(chǔ)在數(shù)組 B 中，則二維數(shù)組元素 Ai,j在一維數(shù)組 B 中的下標(biāo)為 A_。A. n*(i-1)+j B . n*(i-1)+j-1 C . i*(j-1) D . j*m+i-166._ 有一個(gè) 100X 90 的稀疏矩陣，非 0 元素有 10,設(shè)每個(gè)

48、整型數(shù)占 2 個(gè)字節(jié)，則用三元組表示該矩陣時(shí)， 所需的字節(jié)數(shù)是_B。A. 20 B .66 C . 18 000 D . 3367 .數(shù)組 A04 , -1-3 , 57中含有的元素個(gè)數(shù)是上_。A. 55 B .45 C . 36 D . 1668 .對(duì)矩陣進(jìn)行壓縮存儲(chǔ)是為了D。A.方便運(yùn)算 B .方便存儲(chǔ)C .提高運(yùn)算速度 D .減少存儲(chǔ)空間69 .設(shè)有一個(gè) 10 階的對(duì)稱矩陣 A,采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a1,1為第一個(gè)元素，其存儲(chǔ)地址為 1，每個(gè)元素占 1 個(gè)地址空間，則 a8,5的地址為 B 。.專業(yè).整理.下載可編輯.專業(yè).整理.A. 13 B .33 C . 18 D .

49、 4070.稀疏矩陣一般的壓縮存儲(chǔ)方式有兩種，即C72 深度為 5 的二叉樹至多有_C_個(gè)結(jié)點(diǎn)A. 16 B . 32 C .31 C .1073 .對(duì)一個(gè)滿二叉樹，m 個(gè)葉子，n 個(gè)結(jié)點(diǎn)，深度為 h,則_D_A. n = h+m B h+m = 2n C m = h-1 D n = 2h-174 .任何一棵叉樹的葉子結(jié)點(diǎn)在前序、中序和后序遍歷序列中的相對(duì)次序AA.不發(fā)生改變B .發(fā)生改變 C .不能確定D .以上都不對(duì)75 .在線索化樹中，每個(gè)結(jié)點(diǎn)必須設(shè)置一個(gè)標(biāo)志來說明它的左、右鏈指向的是樹結(jié)構(gòu)信息，還是線索化信息，若 0 標(biāo)識(shí)樹結(jié)構(gòu)信息，1 標(biāo)識(shí)線索，對(duì)應(yīng)葉結(jié)點(diǎn)的左右鏈域，應(yīng)標(biāo)識(shí)為_D _

50、 oA. 00B. 01C . 10D. 1176 .在下述論述中，正確的是 _D_o只有一個(gè)結(jié)點(diǎn)的二叉樹的度為0;二叉樹的度為 2;二叉樹的左右子樹可任意交換；深度為 K 的順序二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹。A. B . C . D .77 .設(shè)森林 F 對(duì)應(yīng)的二叉樹為 B,它有 m 個(gè)結(jié)點(diǎn)，B 的根為 p, p 的右子樹的結(jié)點(diǎn)個(gè)數(shù)為 n,森林 F 中第棵樹的結(jié)點(diǎn)的個(gè)數(shù)是AoA. m-n B . m-n-1 C . n+1 D .不能確定78 .若一棵二叉樹具有 10 個(gè)度為 2 的結(jié)點(diǎn)，5 個(gè)度為 1 的結(jié)點(diǎn)，則度為 0 的結(jié)點(diǎn)的個(gè)數(shù)是 B oA. 9 B . 11 C .

51、 15 D .不能確定79 .具有 10 個(gè)葉子結(jié)點(diǎn)的二叉樹中有 _B_個(gè)度為 2 的結(jié)點(diǎn)。A. 8 B . 9 C . 10 D . 1180 .在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的_C_ 倍。A. 1/2 B 1 C 2 D 481 .在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的_B倍。A. 1/2 B 1 C 2 D 482 .某二叉樹結(jié)點(diǎn)的中序序列為 ABCDEF,后序序列為 BDCAFQE 則其左子樹中結(jié)點(diǎn)數(shù)目為：_CA. 3B . 2C. 4D. 5A.二維數(shù)組和三維數(shù)組B .C.三元組和十字鏈表D .71樹最適合用來表示 _C oA.有序數(shù)據(jù)元素BC.元

52、素之間具有分支層次關(guān)系的數(shù)據(jù)三元組和散列散列和十字鏈表.無序數(shù)據(jù)元素D .元素之間無聯(lián)系的數(shù)據(jù)下載可編輯.專業(yè).整理.83.已知一算術(shù)表達(dá)式的中綴形式為A+ B *C- D/E,后綴形式為 ABb+DE/ -,其前綴形式為D85.采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于二叉樹的_AA.先序遍歷B .中序遍歷 C .后序遍歷 D .按層遍歷86.采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類似于二叉樹的DA.先序遍歷 B .中序遍歷 C .后序遍歷 D .按層遍歷87.具有 n 個(gè)結(jié)點(diǎn)的連通圖至少有 _A_條邊A .n-1BnC .n(n-1)/2D. 2n88.廣義表(a),a)的表頭是 C ，表尾

53、是 C 。A. a B()C(a)D(a)89.廣義表(a)的表頭卜是 C，表尾是 B 。A. a B()C(a)D(a)90.順序查找法適合于存儲(chǔ)結(jié)構(gòu)為B 的線性表。A 散列存儲(chǔ)B順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)C壓縮存儲(chǔ)D索引存儲(chǔ)91.對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須_B以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列 以鏈?zhǔn)椒绞酱鎯?chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列93.有一個(gè)有序表為1, 3, 9, 12, 32, 41, 45, 62,75,77,82,95, 100,當(dāng)折半查找值為82 的結(jié)點(diǎn)時(shí)，_C_ 次比較后查找成功。A.11 B 5C 4 D 894.二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點(diǎn)的值均大

54、于其左孩子的值、小于其右孩子的值。這種說法 B。A 正確B錯(cuò)誤A. A+B*C/DEB . - A+B*CD/EC +*ABC/DED. +A*BC/DE84.已知一個(gè)圖，如圖所示，若從頂點(diǎn)a 出發(fā)按深度搜索能得到的一種頂點(diǎn)序列為 一種頂點(diǎn)序列為_A_；1A.a,b, e, c, d, fC .a,e, b, c, f, d,2A.a,b, c, e, d, fC .a,e, b, c, f, d,D_；按廣度搜索法進(jìn)行遍B.a,c, f,e, b, dD.a,e, d,f, c, bB.a,b, c, e, f, dD.a,c, f,d, e, bA 以順序方式存儲(chǔ)BC 以鏈?zhǔn)椒绞酱鎯?chǔ)D92

55、.采用折半查找法查找長(zhǎng)度為2A O(n ) B 0(nlog2n)n 的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為C 0(n) D O(log2n)法進(jìn)行遍歷，則可歷，則可能得到的下載可編輯.專業(yè).整理.95.下面關(guān)于 B 樹和 B+樹的敘述中，不正確的結(jié)論是 _A下載可編輯.專業(yè).整理.A B 樹和 B+樹都能有效的支持順序查找B B 樹和 B+樹都能有效的支持隨機(jī)查找C B 樹和 B+樹都是平衡的多叉樹D B樹和 B+樹都可用于文件索引結(jié)構(gòu)96.以下說法錯(cuò)誤的是 BoA. 散列法存儲(chǔ)的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲(chǔ)地址B. 散列表的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息，不包含指針。C. 負(fù)載因子是散列表

56、的一個(gè)重要參數(shù)，它反映了散列表的飽滿程度。D. 散列表的查找效率主要取決于散列表構(gòu)造時(shí)選取的散列函數(shù)和處理沖突的方法。97 .查找效率最高的二叉排序樹是 _C_ oA. 所有結(jié)點(diǎn)的左子樹都為空的二叉排序樹。B. 所有結(jié)點(diǎn)的右子樹都為空的二叉排序樹。C. 平衡二叉樹。D. 沒有左子樹的二叉排序樹。98 .排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為C oA.希爾排序 B 。冒泡排序 C 插入排序D。選擇排序99.在所有的排序方法中， 關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是_D_ oA.希爾排序 B.冒泡排序C.直接插入排序D

57、 .直接選擇排序100.堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。下列關(guān)鍵碼序列D是一個(gè)堆101 .堆排序是一種B 排序。A.插入 B .選擇C .交換D .歸并102. D在鏈表中進(jìn)行操作比在順序表中進(jìn)行操作效率高A.順序查找B .折半查找 C .分塊查找 D .插入103 .直接選擇排序的時(shí)間復(fù)雜度為 _D_o (n 為元素個(gè)數(shù))2A. O (n) B . O(log2n) C . O(nlog2n) D . O(n )二、填空題。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

58、.在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn) 沒有 前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)前驅(qū)結(jié)點(diǎn):最后一個(gè)結(jié)點(diǎn) 沒 有 后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 J個(gè)后續(xù)結(jié)點(diǎn)。4.線性結(jié)構(gòu)中元素之間存在一對(duì)一 關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對(duì)多 關(guān)系，圖形結(jié)構(gòu)中元素之間存在 多對(duì)多 關(guān)系。5 .在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有 前驅(qū) 結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有 J個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有 后 續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以任意多個(gè)o6 .數(shù)據(jù)結(jié)構(gòu)的基本存儲(chǔ)方法是順序、鏈?zhǔn)健?索引和 散列存儲(chǔ)。7.衡量一個(gè)算法的優(yōu)劣主要考慮正確性、可讀性、健壯性和時(shí)間復(fù)雜度與 空間復(fù)雜度。&評(píng)估一個(gè)算法的優(yōu)劣，通常從時(shí)間復(fù)雜度和空

59、間復(fù)雜度兩個(gè)方面考察。9.算法的 5 個(gè)重要特性是有窮性 、 確定性、 可行性 、輸入和輸出。A. 94,31,53,23,16,72 B94,53,31,72,C. 16,53,23,94,31,72 D16,31,23,94,53,72下載可編輯.專業(yè).整理.10 .在一個(gè)長(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ù)與位置

60、有關(guān)。14 當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表的元 素是，應(yīng)采用 順序存儲(chǔ)結(jié)構(gòu)。15 根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù)，將線性鏈表分成_單鏈表和雙鏈表。16順序存儲(chǔ)結(jié)構(gòu)是通過下標(biāo)表示元素之間的關(guān)系的；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過指針 表示元素之間的關(guān)系的。17.帶頭結(jié)點(diǎn)的循環(huán)鏈表 L 中只有一個(gè)元素結(jié)點(diǎn)的條件是L-next-next=L_ 。18.棧 是限定僅在表尾進(jìn)行插入或刪除操作的線性表，其運(yùn)算遵循后進(jìn)先出的原則。19空串是 零個(gè)字符的串，其長(zhǎng)度等于 零?？瞻状怯梢粋€(gè)或多個(gè)空格字符組成的串，其長(zhǎng)度等于其 _包含的空格個(gè)數(shù)。20.組成串的數(shù)據(jù)元素只能是單個(gè)