大學數(shù)據(jù)結構期末考試題

1、下載可編輯“數(shù)據(jù)結構”期末考試試題一、 單選題(每小題 2 分，共 12 分)1.在一個單鏈表 HL 中，若要向表頭插入一個由指針p 指向的結點，則執(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 個頂點的強連通圖中至少含有()。A.n l 條有向邊 B.n 條有向邊C.n(n 1) /2 條有向邊 D.n(n 1)條有向邊3.從一棵二叉搜索樹中查找一個元素時，其時間復雜度大致為()。A.0(1)B.0( n)C.0(1

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

3、構中，單元素結點與表元素結點有一個域對應不同，各自分別為一一域和一一域。3.中綴表達式 3 十 x*(2.4 /5 6)所對應的后綴表達式為-。4 .在一棵高度為 h 的 3 叉樹中，最多含有一一結點。5 .假定一棵二叉樹的結點數(shù)為18,則它的最小深度為一一，最大深度為6.在一棵二叉搜索樹中，每個分支結點的左子樹上所有結點的值一定一一該結點的值，右子樹上所 有結點的值一定一一該結點的值。7.當向一個小根堆插入一個具有最小值的元素時，該元素需要逐層- 調整，直到被調整到- 位置為止。8 .表示圖的三種存儲結構為- 、- 和-。9.對用鄰接矩陣表示的具有n 個頂點和 e 條邊的圖進行任一種遍歷時，

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

5、情況下的時間復雜度為一一，最壞情況下的時間復雜度為一一。三、運算題(每小題 6 分，共 24 分)1.假定一棵二叉樹廣義表表示為a(b(c , d), c( , 8)，分別寫出對它進行先序、中序、后序和后下載可編輯序遍歷的結果。先序：.專業(yè).整理.下載可編輯.專業(yè).整理.中序; 后序:2已知一個帶權圖的頂點集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,則求出該圖的最小生成樹的權。最小生成樹的權；

6、3假定一組記錄的排序碼為(46, 79 , 56 , 38 , 40 , 84 , 50 , 42),則利用堆排序方法建立的初始堆為- 。4有 7 個帶權結點，其權值分別為3 ,乙 8 , 2 , 6 , 10 , 14，試以它們?yōu)槿~子結點生成一棵哈夫曼樹，求出該樹的帶權路徑長度、高度、雙分支結點數(shù)。帶權路徑長度：一一 高度：一一雙分支結點數(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);該算法被調用執(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該算法被調用后得到的輸出結果為：五、算法填空，在畫有橫線的地方填寫合適的容K 的元素的遞歸算法，若查找成功則返回對應元素的下標,否則返回一 1IntBinsch(ElemTypeA, Intlow , int high , KeyTypeK)if(low= high)int mid= (low+high) /2;if(K = = Amid.key)- ;else if (Kdata = = X)return 1;/根結點的層號為 1/向子樹中查找 x 結點elseint cl = NodeLevel(BT 一 left , X)； if(cl = 1)return cl+1

9、;int c2 =:/若樹中不存在 X 結點則返回 oelse return 0:六、編寫算法(8 分)按所給函數(shù)聲明編寫一個算法，從表頭指針為 函數(shù)返回，若單鏈表為空則中止運行。ElemType MaxValue(LNOde*HL);“數(shù)據(jù)結構”期末考試試題答案一、單選題(每小題 2 分，共 12 分)評分標準；選對者得 2 分，否則不得分。1. B 2. B 3. C 4 . D 5 . B 6. A二、填空題(每空 1 分，共 28 分)1順序結構 結構索引結構散列結構(次序無先后)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)三、運算題(每小題 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 .最小生成樹的權：31/ 6 分3. (84 , 79, 56, 42, 40, 46, 50, 38)/ 6 分4.帶權路徑長度：131/ 3 分HL

11、的單鏈表中查找出具有最大值的結點，該最大值由下載可編輯.專業(yè).整理.高度：5/ 2 分雙分支結點數(shù)：6/ 1 分四、 閱讀算法，回答問題(每小題 8 分，共 16 分)評分標準：每小題正確得8 分，出現(xiàn)一處錯誤扣 4 分，兩處及以上錯誤不得分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 分)評分標準：請參考語句后的注釋，或根據(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 分數(shù)據(jù)結構復習資料一、填空題1.

13、數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中計算機的操作對象以及它們之間的關系和運算等的學科。2.數(shù)據(jù)結構被形式地定義為（D, R ）,其中 D 是數(shù)據(jù)元素的有限集合,R 是 D 上的 關系 有限集合。3.數(shù)據(jù)結構包括數(shù)據(jù)的_邏輯結構、數(shù)據(jù)的_存儲結構和數(shù)據(jù)的運算這三個方面的容。4.數(shù)據(jù)結構按邏輯結構可分為兩大類，它們分別是_線性結構和_非線性結構 _。5.線性結構中元素之間存在一對一關系，樹形結構中元素之間存在一對多關系，圖形結構中元素之間存 在多對多關系。6.在線性結構中，第一個結點 _沒有_前驅結點，其余每個結點有且只有1 個前驅結點；最后一個結點沒有_后續(xù)結點，其余每個結點有且只有1

14、個后續(xù)結點。7.在樹形結構中，樹根結點沒有 前驅一結點，其余每個結點有且只有 1個前驅結點；葉子結點沒有后續(xù) 結點，其余每個結點的后續(xù)結點數(shù)可以任意多個 _。8.在圖形結構中，每個結點的前驅結點數(shù)和后續(xù)結點數(shù)可以_任意多個 _。9.數(shù)據(jù)的存儲結構可用四種基本的存儲方法表示，它們分別是順序、鏈式、索引和散列。下載可編輯.專業(yè).整理.10. 數(shù)據(jù)的運算最常用的有 5 種，它們分別是 插入、刪除、修改、 查找、排序。11. 一個算法的效率可分為 _時間_效率和 _空間_效率。12. 在順序表中插入或刪除一個元素，需要平均移動_表中一半元素，具體移動的元素個數(shù)與表長和該元素在表中的位置 _有關。13.

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

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

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

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

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

20、 。解：顯然，平均查找長度= O （loggn） 5 次（25）。但具體是多少次，則不應當按照公式ASL口log2(n 1)來計算(即(21 X log221) /20 = 4.6 次并不正確！)。因為這是在假設 n = 2 匸 的情況下n推導出來的公式。應當用窮舉法羅列：全部元素的查找次數(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、查找方法中，平均查找長度與結點個數(shù)n 無關的查找方法是散列查找 _。36. 散列法存儲的基本思想是由 _關鍵字的值_ 決定數(shù)據(jù)的存儲地址。二、判斷正誤(在正確的說法后面打勾，反之打叉 (X ) 1.鏈表的每個結點中都恰好包含一個指針。答：錯誤。鏈表中的結點可含多個指針域，分別存放多個指針。例如，雙向鏈表中的結點可以含有兩個指 針域，分別存放指向其直接前趨和直接后繼結點的指針。(X ) 2.鏈表的物理存儲結構具有同鏈表一樣的順序。錯，鏈表的存儲結構特點是無序，而鏈表的示意圖有序。(X ) 3.鏈表的刪除算法很簡單，因為當刪除鏈中某個結點后，計算機會自動地將后續(xù)的各個單元向 前移動。錯，鏈表的結點

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

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

24、的每個結點可以是一個復雜類型。錯，線性表是邏輯結構概念，可以順序存儲或鏈式存儲，與元素數(shù)據(jù)類型無關。(X ) 12.在表結構中最常用的是線性表，棧和隊列不太常用。錯，不一定吧？調用子程序或函數(shù)常用，CPU 中也用隊列。(V ) 13.棧是一種對所有插入、刪除操作限于在表的一端進行的線性表，是一種后進先出型結構。(V ) 14.對于不同的使用者，一個表結構既可以是棧，也可以是隊列，也可以是線性表。正確，都是線性邏輯結構，棧和隊列其實是特殊的線性表，對運算的定義略有不同而已。X ) 15.棧和鏈表是兩種不同的數(shù)據(jù)結構。錯，棧是邏輯結構的概念，是特殊殊線性表，而鏈表是存儲結構概念，二者不是同類項。(

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

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

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

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

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

30、條件是C. ST-topvmOD. ST-top=mO下載可編輯.專業(yè).整理.C.線性結構和非線性結構D .部結構和外部結構2 .數(shù)據(jù)結構在計算機存中的表示是指 _A_ 。下載可編輯.專業(yè).整理.A.數(shù)據(jù)的存儲結構 B 數(shù)據(jù)結構 C 數(shù)據(jù)的邏輯結構 D 數(shù)據(jù)元素之間的關系 3在數(shù)據(jù)結構中，與所使用的計算機無關的是數(shù)據(jù)的_A結構。A.邏輯 B 存儲 C 邏輯和存儲D 物理4 在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要存儲_C_。A.數(shù)據(jù)的處理方法B.數(shù)據(jù)元素的類型C.數(shù)據(jù)元素之間的關系D 數(shù)據(jù)的存儲方法5 在決定選取何種存儲結構時，一般不考慮A_ 。A.各結點的值如何B 結點個數(shù)的多少

31、C.對數(shù)據(jù)有哪些運算D 所用的編程語言實現(xiàn)這種結構是否方便。6 以下說法正確的是 _D_。A. 數(shù)據(jù)項是數(shù)據(jù)的基本單位B. 數(shù)據(jù)元素是數(shù)據(jù)的最小單位C. 數(shù)據(jù)結構是帶結構的數(shù)據(jù)項的集合D. 一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結構7算法分析的目的是_C_，算法分析的兩個主要方面是_A_(1)A. 找出數(shù)據(jù)結構的合理性B.研究算法中的輸入和輸出的關系C. 分析算法的效率以求改進C.分析算法的易讀性和文檔性A. 空間復雜度和時間復雜度B.正確性和簡明性C可讀性和文檔性D.數(shù)據(jù)復雜性和程序復雜性s =0;for( I =0; ivn; i+)for(j=0;jv n;j+) s+=Bij;sum

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

33、單鏈表 B .靜態(tài)鏈表 C .線性鏈表 D .順序存儲結構18 .非空的循環(huán)單鏈表 head 的尾結點（由 p 所指向）滿足_C_A. p- next = NULL B . p = NULLC. p-n ext =head D . p = head20 .如果最常用的操作是取第 i 個結點及其前驅，則采用 D 存儲方式最節(jié)省時間 A.單鏈表 B .雙鏈表 C .單循環(huán)鏈表 D .順序表21 .在一個具有 n 個結點的有序單鏈表中插入一個新結點并仍然保持有序的時間復雜度是B_。A. O (1)B . O(n)C . O(n2)D . O(nIog2n )22 .在一個長度為 n (n1)的單鏈表

34、上，設有頭和尾兩個指針，執(zhí)行_B_操作與鏈表的長度有關。A. 刪除單鏈表中的第一個元素B. 刪除單鏈表中的最后一個元素C. 在單鏈表第一個元素前插入一個新元素D. 在單鏈表最后一個元素后插入一個新元素13鏈表不具備的特點是A.可隨機訪問任一結點C.不必事先估計存儲空間15.帶頭結點的單鏈表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 所指的結點之前插入 s 所指結點的操作是_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)點之一是_DA. 插入、刪除操作更簡單B. 可以進行隨機訪問C. 可以省略表頭指針或表尾指針D. 順序訪問相鄰結點更靈活24.如果對線性表的操作只有兩種，即刪除第一個元素，

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

37、D 刪除運算方便28 .下面關于線性表的敘述中，錯誤的是哪一個？_B_ 。A 線性表采用順序存儲，必須占用一片連續(xù)的存儲單元 B 線性表采用順序存儲，便于進行插入和刪除操作。C 線性表采用鏈式存儲，不必占用一片連續(xù)的存儲單元D 線性表采用鏈式存儲，便于進行插入和刪除操作。29 .線性表是具有 n 個_B_的有限序列。A.字符 B .數(shù)據(jù)元素C .數(shù)據(jù)項 D .表元素30 .在 n 個結點的線性表的數(shù)組實現(xiàn)中，算法的時間復雜度是0( 1)的操作是 A_ 。A .訪問第 i (1=i=n )個結點和求第 i 個結點的直接前驅(1i=n )B .在第 i (1=i=n )個結點后插入一個新結點C.

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

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

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

41、編輯.專業(yè).整理.46.判定一個循環(huán)隊列 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)隊列中，若 front 與 rear 分別表示對頭元素和隊尾元素的位置，貝 V 判斷循環(huán)隊列空的條件是C_。A. front=rear+1B . rear=front+1C . front=rearD . front=048 .向一個棧頂指針為 h 的帶頭結點的鏈棧中插入指針

42、s 所指的結點時，應執(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 .若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間V1 m , top1、top2分別代表第 1 和第 2 個棧的棧頂，棧 1 的底在 V1，棧 2 的底在 Vm，則棧滿的條件是B 。A. |top2-top1|=0 B. top1+1=top2 C . top1+top2=m D . top1=top251 .設計一個判別表達式中左、右括號是否配對出現(xiàn)的算法，采用54 .若用一個大小為 6 的數(shù)值來實

43、現(xiàn)循環(huán)隊列，且當前 rear 和 front 的值分別為 0 和 3,當從隊列中刪除一個元素，再加入兩個元素后，rear 和 front 的值分別為_B_。A. 1 和 5 B . 2 和 4 C . 4 和 2 D . 5 和 155 .隊列的“先進先出”特性是指_D_。A.最早插入隊列中的元素總是最后被刪除B .當同時進行插入、刪除操作時，總是插入操作優(yōu)先C. 每當有刪除操作時，總是要先做一次插入操作D. 每次從隊列中刪除的總是最早插入的元素56 .和順序棧相比，鏈棧有一個比較明顯的優(yōu)勢是_A_ 。A.通常不會出現(xiàn)棧滿的情況B .通常不會出現(xiàn)棧空的情況C.插入操作更容易實現(xiàn)D .刪除操作更

44、容易實現(xiàn)57 .用不帶頭結點的單鏈表存儲隊列，其頭指針指向隊頭結點，尾指針指向隊尾結點，貝恠進行出隊操作ABC 可以變?yōu)?CBA 時，經(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.線性表的順序存儲結構B .隊列 C .線性表的鏈式存儲結構D .棧52.允許對隊列進行的操作有A .對隊列中的元素排序D_ 。B .取出最近進隊的元素C

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

46、可以是多個字符61.設有兩個串 p 和 q,求 q 在 p 中首次出現(xiàn)的位置的運算稱為BA.連接 B .模式匹配C .求子串D .求串長62數(shù)組 A 中，每個元素的長度為 3 個字節(jié)，行下標 i 從 1 到 8,列下標 j 從 1 到 10，從首地址 SA 開始 連續(xù)存放的存儲器，該數(shù)組按行存放，元素A85的起始地址為 C 。A. SA+141 B . SA +144 C . SA+ 222 D . SA 22563數(shù)組 A 中，每個元素的長度為 3 個字節(jié)，行下標 i 從 1 到 8,列下標 j 從 1 到 10，從首地址 SA 開始 連續(xù)存放的存儲器，該數(shù)組按行存放，元素A58的起始地址為

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

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

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

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

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

52、素之間具有分支層次關系的數(shù)據(jù)三元組和散列散列和十字鏈表.無序數(shù)據(jù)元素D .元素之間無聯(lián)系的數(shù)據(jù)下載可編輯.專業(yè).整理.83.已知一算術表達式的中綴形式為A+ B *C- D/E,后綴形式為 ABb+DE/ -,其前綴形式為D85.采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的_AA.先序遍歷B .中序遍歷 C .后序遍歷 D .按層遍歷86.采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的DA.先序遍歷 B .中序遍歷 C .后序遍歷 D .按層遍歷87.具有 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.順序查找法適合于存儲結構為B 的線性表。A 散列存儲B順序存儲或鏈式存儲C壓縮存儲D索引存儲91.對線性表進行折半查找時，要求線性表必須_B以順序方式存儲，且結點按關鍵字有序排列 以鏈式方式存儲，且結點按關鍵字有序排列93.有一個有序表為1, 3, 9, 12, 32, 41, 45, 62,75,77,82,95, 100,當折半查找值為82 的結點時，_C_ 次比較后查找成功。A.11 B 5C 4 D 894.二叉樹為二叉排序樹的充分必要條件是其任一結點的值均大

54、于其左孩子的值、小于其右孩子的值。這種說法 B。A 正確B錯誤A. A+B*C/DEB . - A+B*CD/EC +*ABC/DED. +A*BC/DE84.已知一個圖，如圖所示，若從頂點a 出發(fā)按深度搜索能得到的一種頂點序列為 一種頂點序列為_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_；按廣度搜索法進行遍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 以順序方式存儲BC 以鏈式方式存儲D92

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

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

57、 .直接選擇排序100.堆是一種有用的數(shù)據(jù)結構。下列關鍵碼序列D是一個堆101 .堆排序是一種B 排序。A.插入 B .選擇C .交換D .歸并102. D在鏈表中進行操作比在順序表中進行操作效率高A.順序查找B .折半查找 C .分塊查找 D .插入103 .直接選擇排序的時間復雜度為 _D_o (n 為元素個數(shù))2A. O (n) B . O(log2n) C . O(nlog2n) D . O(n )二、填空題。1 .數(shù)據(jù)邏輯結構包括線性結構、樹形結構 和 圖狀結構 三種類型，樹形結構和圖狀結構合稱非線性結構。2 .數(shù)據(jù)的邏輯結構分為集合、線性結構、 樹形結構 和 圖狀結構 4 種。3

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

59、間復雜度兩個方面考察。9.算法的 5 個重要特性是有窮性 、 確定性、 可行性 、輸入和輸出。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 .在一個長度為 n 的順序表中刪除第 i 個元素時，需向前移動 n-i-1個元素。11 .在單鏈表中，要刪除某一指定的結點，必須找到該結點的前驅 結點。12 .在雙鏈表中，每個結點有兩個指針域，一個指向前驅結點，另一個指向 后繼結點。13 .在順序表中插入或刪除一個數(shù)據(jù)元素，需要平均移動_n_個數(shù)據(jù)元素，移動數(shù)據(jù)元素的個數(shù)與位置

60、有關。14 當線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表的元 素是，應采用 順序存儲結構。15 根據(jù)線性表的鏈式存儲結構中每一個結點包含的指針個數(shù)，將線性鏈表分成_單鏈表和雙鏈表。16順序存儲結構是通過下標表示元素之間的關系的；鏈式存儲結構是通過指針 表示元素之間的關系的。17.帶頭結點的循環(huán)鏈表 L 中只有一個元素結點的條件是L-next-next=L_ 。18.棧 是限定僅在表尾進行插入或刪除操作的線性表，其運算遵循后進先出的原則。19空串是 零個字符的串，其長度等于 零。空白串是由一個或多個空格字符組成的串，其長度等于其 _包含的空格個數(shù)。20.組成串的數(shù)據(jù)元素只能是單個