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

1、“數(shù)據(jù)結(jié)構(gòu)”期末考試試題一、單選題(每小題2分，共12分) 1在一個單鏈表HL中，若要向表頭插入一個由指針p指向的結(jié)點，則執(zhí)行( )。 A HLps p一>nextHL B p一>nextHL；HLp3 C p一>nextHl；pHL； D p一>nextHL一>next;HL一>nextp； 2n個頂點的強連通圖中至少含有( )。 A.nl條有向邊 B.n條有向邊 C.n(n1)2條有向邊 D.n(n一1)條有向邊 3.從一棵二叉搜索樹中查找一個元素時，其時間復雜度大致為( )。 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 B48C 72 D 535當一個作為實際傳遞的對象占用的存儲空間較大并可能需要修改時，應最好把它說明為( )參數(shù)，以節(jié)省參數(shù)值的傳輸時間和存儲參數(shù)的空間。 A.整形 B.引用型 C.指針型 D.常值引用型·6向一個長度為n的順序表中插人一個新元素的平均時間復雜度為( )。 AO(n) BO(1) CO(n2) DO(10g2n)二、填空題(每空1分，共28分)1數(shù)據(jù)的存儲結(jié)構(gòu)被分為、和四種。 2在廣義表的存儲結(jié)構(gòu)中，單元素結(jié)點與表元素結(jié)點有一個域?qū)煌?，各自分別為域和域。3中綴表達式 3十x*(2.4

3、56)所對應的后綴表達式為。 4在一棵高度為h的3叉樹中，最多含有結(jié)點。5假定一棵二叉樹的結(jié)點數(shù)為18，則它的最小深度為，最大深度為· 6在一棵二叉搜索樹中，每個分支結(jié)點的左子樹上所有結(jié)點的值一定該結(jié)點的值，右子樹上所有結(jié)點的值一定該結(jié)點的值。 7當向一個小根堆插入一個具有最小值的元素時，該元素需要逐層調(diào)整，直到被調(diào)整到位置為止。 8表示圖的三種存儲結(jié)構(gòu)為、和。 9對用鄰接矩陣表示的具有n個頂點和e條邊的圖進行任一種遍歷時，其時間復雜度為，對用鄰接表表示的圖進行任一種遍歷時，其時間復雜度為。 10從有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素時

4、，其查找長度分別為和· 11假定對長度n144的線性表進行索引順序查找，并假定每個子表的長度均為，則進行索引順序查找的平均查找長度為，時間復雜度為· 12一棵B樹中的所有葉子結(jié)點均處在上。 13每次從無序表中順序取出一個元素，把這插入到有序表中的適當位置，此種排序方法叫做排序；每次從無序表中挑選出一個最小或最大元素，把它交換到有序表的一端，此種排序方法叫做排序。 14快速排序在乎均情況下的時間復雜度為，最壞情況下的時間復雜度為。 三、運算題(每小題6分，共24分) 1假定一棵二叉樹廣義表表示為a(b(c，d)，c(，8)，分別寫出對它進行先序、中序、后序和后序遍歷的結(jié)果。

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

6、16分) 1VOldAC(List&L) InitList(L)； InsertRear(L;25)； InsertFront(L，50)； IntaL45，8，12，15，36; for(inti0; i<5; i+) if (ai20)InsertFront(L，ai)； elselnsertRear(L，ai)； 該算法被調(diào)用執(zhí)行后，得到的線性表L為： 2void AG(Queue&Q) InitQueue(Q)； inta56，12，5，15，8； for(int i0;i<5; i+)QInsert(Q，ai)； QInsert(Q，QDelete(Q)；

7、 QInsert(Q，20)； QInsert(Q，QDelete(Q)十16)； while(!QueueEmpty(Q)cout<<QDelete(Q)<<”； 該算法被調(diào)用后得到的輸出結(jié)果為：五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容(每小題6分，共12分) 1從一維數(shù)組An)中二分查找關(guān)鍵字為K的元素的遞歸算法，若查找成功則返回對應元素的下標，否則返回一1。 IntBinsch(ElemTypeA，Intlow，int high，KeyTypeK) if(low<high) int mid(low+high)2； if(KAmid.key)； else

8、if (K<Amid.key)； else ； else returnl； 2已知二叉樹中的結(jié)點類型BinTreeNode定義為： structBinTreeNodeElemType data；BinTreeNode*left，*right； 其中data為結(jié)點值域，left和right分別為指向左、右子女結(jié)點的指針域。下面函數(shù)的功能是返回二叉樹BT中值為x的結(jié)點所在的層號，請在劃有橫線的地方填寫合適內(nèi)容。 Int NodeLevel(BinTreeNode * BT，ElemType X) if(BT：NULL)return 0； 空樹的層號為0 else if(BT一>data

9、X)return 1; 根結(jié)點的層號為1 向子樹中查找x結(jié)點 else int clNodeLevel(BT一>left，X)； if(cl>1)return cl+1; int c2 ； if； 若樹中不存在X結(jié)點則返回o else return 0； 六、編寫算法(8分) 按所給函數(shù)聲明編寫一個算法，從表頭指針為HL的單鏈表中查找出具有最大值的結(jié)點，該最大值由函數(shù)返回，若單鏈表為空則中止運行。 EIemType MaxValue(LNOde*HL);  “數(shù)據(jù)結(jié)構(gòu)”期末考試試題答案 一、單選題(每小題2分，共12分) 評分標準；選對者得2分，否則不得分。 1

10、B 2B 3C 4D 5B 6A 二、填空題(每空1分，共28分) 1順序結(jié)構(gòu) 鏈接結(jié)構(gòu) 索引結(jié)構(gòu) 散列結(jié)構(gòu)(次序無先后) 2值(或data) 子表指針(或sublist) 33 x 24 56一*十 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

11、最小生成樹的權(quán)：31 6分 3(84，79，56，42，40，46，50，38) 6分 4帶權(quán)路徑長度：131 3分 高度：5 2分 雙分支結(jié)點數(shù)：6 1分四、閱讀算法，回答問題(每小題8分，共16分) 評分標準：每小題正確得8分，出現(xiàn)一處錯誤扣4分，兩處及以上錯誤不得分。 1(36，12，8，50，25，5，15) 25 15 8 6 20 28五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容(每小題6分，共12分) 1feturn mid 2分 returnBinsch(A，low，mid一1，K) 2分 returnBmsch(A，mid+1，high，K) 2分 2NodeLevel(BT

12、一>right，X) 3分 (c2>=1)returnc2十1 3分六、編寫算法(8分) 評分標準：請參考語句后的注釋，或根據(jù)情況酌情給分。 ElemType MaxValue(LNodeO* HL。) if (HL=NUlL) 2分 cerr<<"Linked llst is empty!”<<endl； exit(1)； ElemTypemax：HL一>data； 3分 LNOde*p=HI一>next； 4分 while(P!：NULL) 7分 if(max<p一>data)maxp一>data； pp一>

13、next； returnmax； 8分  數(shù)據(jù)結(jié)構(gòu)復習資料 一、填空題1. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設計問題中計算機的 操作對象 以及它們之間的 關(guān)系 和運算等的學科。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ù)的 運算 這三個方面的內(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)中元素之間存在一對多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系。6 在線性結(jié)構(gòu)中，第一個結(jié)點 沒有

14、 前驅(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)可用四種基本的存儲方法表示，它們分別是順序 、 鏈式 、 索引 和 散列 。10. 數(shù)據(jù)的運算最常用的有5種，它們分別是插入 、 刪除、修改、 查找 、排序。11. 一個算法的效率可分為 時間 效率和 空間 效率。12. 在順序表中插入或刪除一個元素，

15、需要平均移動 表中一半元素，具體移動的元素個數(shù)與 表長和該元素在表中的位置 有關(guān)。13. 線性表中結(jié)點的集合是 有限 的，結(jié)點間的關(guān)系是 一對一 的。14. 向一個長度為n的向量的第i個元素(1in+1)之前插入一個元素時，需向后移動 n-i+1 個元素。15. 向一個長度為n的向量中刪除第i個元素(1in)時，需向前移動 n-i 個元素。16. 在順序表中訪問任意一結(jié)點的時間復雜度均為 O(1) ，因此，順序表也稱為 隨機存取 的數(shù)據(jù)結(jié)構(gòu)。17. 順序表中邏輯上相鄰的元素的物理位置 必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置 不一定 相鄰。18在單鏈表中，除了首元結(jié)點外，任一結(jié)點的存儲位置

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

17、子串的定位運算稱為串的模式匹配； 被匹配的主串 稱為目標串， 子串 稱為模式。25. 假設有二維數(shù)組A6×8，每個元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。已知A的起始存儲位置（基地址）為1000，則數(shù)組A的體積（存儲量）為 288 B ；末尾元素A57的第一個字節(jié)地址為 1282 ；若按行存儲時，元素A14的第一個字節(jié)地址為 (8+4)×6+1000=1072 ；若按列存儲時，元素A47的第一個字節(jié)地址為 (6×74)×61000）1276 。26 由個結(jié)點所構(gòu)成的二叉樹有 5 種形態(tài)。 27. 一棵深度為6的滿二叉樹有 n1+n2=0+ n2= n

18、0-1=31 個分支結(jié)點和 26-1 =32 個葉子。注：滿二叉樹沒有度為1的結(jié)點，所以分支結(jié)點數(shù)就是二度結(jié)點數(shù)。28 一棵具有個結(jié)點的完全二叉樹，它的深度為 9 。（ 注：用ë log2(n) û+1= ë 8.xx û+1=929設一棵完全二叉樹有700個結(jié)點，則共有 350 個葉子結(jié)點。答：最快方法：用葉子數(shù)n/2350 30 設一棵完全二叉樹具有1000個結(jié)點，則此完全二叉樹有 500 個葉子結(jié)點，有 499 個度為2的結(jié)點，有 1 個結(jié)點只有非空左子樹，有 0 個結(jié)點只有非空右子樹。答：最快方法：用葉子數(shù)n/2500 ，n2=n0-1=499。

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

20、.7 。解：顯然，平均查找長度O（log2n）<5次（25）。但具體是多少次，則不應當按照公式來計算（即（21×log221）/204.6次并不正確！）。因為這是在假設n2m-1的情況下推導出來的公式。應當用窮舉法羅列：全部元素的查找次數(shù)為（12×24×38×45×5）74； ASL74/20=3.7 ！34折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它將依次與表中元素 28，6，12，20 比較大小。35. 在各種查找方法中，平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法是 散列查找 。36.

21、 散列法存儲的基本思想是由 關(guān)鍵字的值 決定數(shù)據(jù)的存儲地址。二、判斷正誤（在正確的說法后面打勾，反之打叉）（ × ）1. 鏈表的每個結(jié)點中都恰好包含一個指針。 答：錯誤。鏈表中的結(jié)點可含多個指針域，分別存放多個指針。例如，雙向鏈表中的結(jié)點可以含有兩個指針域，分別存放指向其直接前趨和直接后繼結(jié)點的指針。（ × ）2. 鏈表的物理存儲結(jié)構(gòu)具有同鏈表一樣的順序。錯，鏈表的存儲結(jié)構(gòu)特點是無序，而鏈表的示意圖有序。（ × ）3. 鏈表的刪除算法很簡單，因為當刪除鏈中某個結(jié)點后，計算機會自動地將后續(xù)的各個單元向前移動。錯，鏈表的結(jié)點不會移動，只是指針內(nèi)容改變。（ ×

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

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

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

25、，棧是邏輯結(jié)構(gòu)的概念，是特殊殊線性表，而鏈表是存儲結(jié)構(gòu)概念，二者不是同類項。（ × ）16. 棧和隊列是一種非線性數(shù)據(jù)結(jié)構(gòu)。 錯，他們都是線性邏輯結(jié)構(gòu)，棧和隊列其實是特殊的線性表，對運算的定義略有不同而已。（ ）17. 棧和隊列的存儲方式既可是順序方式，也可是鏈接方式。 （ ）18. 兩個棧共享一片連續(xù)內(nèi)存空間時，為提高內(nèi)存利用率，減少溢出機會，應把兩個棧的棧底分別設在這片內(nèi)存空間的兩端。 （ × ）19. 隊是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進后出型結(jié)構(gòu)。 錯，后半句不對。（ × ）20. 一個棧的輸入序列是12345，則棧的輸出序列不可能

26、是12345。 錯，有可能。（ ）21. 若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個結(jié)點的二叉樹鏈表中只有n1個非空指針域。（ × ）22.二叉樹中每個結(jié)點的兩棵子樹的高度差等于1。 （ ）23.二叉樹中每個結(jié)點的兩棵子樹是有序的。 （ × ）24.二叉樹中每個結(jié)點有兩棵非空子樹或有兩棵空子樹。 （ × ）25.二叉樹中每個結(jié)點的關(guān)鍵字值大于其左非空子樹（若存在的話）所有結(jié)點的關(guān)鍵字值，且小于其右非空子樹（若存在的話）所有結(jié)點的關(guān)鍵字值。 （應當是二叉排序樹的特點）（ × ）26.二叉樹中所有結(jié)點個數(shù)是2k-1-1，其中k是樹的深度。（應2i-1） （ &#

27、215; ）27.二叉樹中所有結(jié)點，如果不存在非空左子樹，則不存在非空右子樹。 （ × ）28.對于一棵非空二叉樹，它的根結(jié)點作為第一層，則它的第i層上最多能有2i1個結(jié)點。（應2i-1）（ ）29.用二叉鏈表法（link-rlink）存儲包含n個結(jié)點的二叉樹，結(jié)點的2n個指針區(qū)域中有n+1個為空指針。（ ）30.具有12個結(jié)點的完全二叉樹有5個度為2的結(jié)點。三、單項選擇題（ B ）1. 非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種：A）一對多關(guān)系 B）多對多關(guān)系 C）多對一關(guān)系 D）一對一關(guān)系（ C ）2. 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的 結(jié)構(gòu)；A) 存儲 B) 物理 C) 邏輯

28、D) 物理和存儲（ C ）3. 算法分析的目的是：A) 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B) 研究算法中的輸入和輸出的關(guān)系C) 分析算法的效率以求改進 D) 分析算法的易懂性和文檔性（ A ）4. 算法分析的兩個主要方面是：A) 空間復雜性和時間復雜性 B) 正確性和簡明性C) 可讀性和文檔性 D) 數(shù)據(jù)復雜性和程序復雜性（ C ）5. 計算機算法指的是：A) 計算方法 B) 排序方法 C) 解決問題的有限運算序列 D) 調(diào)度方法（ B ）6. 計算機算法必須具備輸入、輸出和 等5個特性。A) 可行性、可移植性和可擴充性 B) 可行性、確定性和有窮性C) 確定性、有窮性和穩(wěn)定性 D) 易讀性、穩(wěn)定性和安

29、全性（ C ）7數(shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為：（A）存儲結(jié)構(gòu) （B）邏輯結(jié)構(gòu) （C）順序存儲結(jié)構(gòu) （D）鏈式存儲結(jié)構(gòu)（ B ）8.一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是 （A）110 （B）108 （C）100 （D）120（ A ）9. 在n個結(jié)點的順序表中，算法的時間復雜度是O（1）的操作是：（A） 訪問第i個結(jié)點（1in）和求第i個結(jié)點的直接前驅(qū)（2in） （B） 在第i個結(jié)點后插入一個新結(jié)點（1in）（C） 刪除第i個結(jié)點（1in）（D） 將n個結(jié)點從小到大排序（ B ）10. 向一個有127個元素的順序

30、表中插入一個新元素并保持原來順序不變，平均要移動 個元素（A）8 （B）63.5 （C）63 （D）7（ A ）11. 鏈接存儲的存儲結(jié)構(gòu)所占存儲空間：（A） 分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針（B） 只有一部分，存放結(jié)點值(C） 只有一部分，存儲表示結(jié)點間關(guān)系的指針（D） 分兩部分，一部分存放結(jié)點值，另一部分存放結(jié)點所占單元數(shù)（ B ）12. 鏈表是一種采用 存儲結(jié)構(gòu)存儲的線性表；（A）順序 （B）鏈式 （C）星式 （D）網(wǎng)狀（ D ）13. 線性表若采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址:（A）必須是連續(xù)的 （B）部分地址必須是連續(xù)的（C）一定是不連續(xù)的

31、 （D）連續(xù)或不連續(xù)都可以（ B ）14 線性表在 情況下適用于使用鏈式結(jié)構(gòu)實現(xiàn)。（）需經(jīng)常修改中的結(jié)點值 （）需不斷對進行刪除插入 （）中含有大量的結(jié)點 （）中結(jié)點結(jié)構(gòu)復雜（ B ）15.棧中元素的進出原則是 先進先出 后進先出 ?？談t進 棧滿則出（ C ）16. 若已知一個棧的入棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1=n，則pi為 i n=i n-i+1 不確定（ B ）17. 判定一個棧ST（最多元素為m0）為空的條件是 ST->top<>0 ST->top=0 ST->top<>m0 ST->top=m0（ C

32、 ）18. 在一個圖中，所有頂點的度數(shù)之和等于圖的邊數(shù)的 倍。 A1/2 B. 1 C. 2 D. 4 （ B ）19. 在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的 倍。 A1/2 B. 1 C. 2 D. 4 （ B ）20. 有8個結(jié)點的無向圖最多有 條邊。 A14 B. 28 C. 56 D. 112 （ C ）21. 有8個結(jié)點的有向完全圖有 條邊。 A14 B. 28 C. 56 D. 112 （ B ）22在表長為的鏈表中進行線性查找，它的平均查找長度為. ; . （）; . ; . （）（ A ）23折半查找有序表（4，6，10，12，20，30，50，70，88

33、，100）。若查找表中元素58，則它將依次與表中 比較大小，查找結(jié)果是失敗。A20，70，30，50 B30，88，70，50 C20，50 D30，88，50（ C ）24對22個記錄的有序表作折半查找，當查找失敗時，至少需要比較 次關(guān)鍵字。A3 B4 C5 D 6（ A ）25. 鏈表適用于 查找A順序 B二分法 C順序，也能二分法 D隨機數(shù)據(jù)結(jié)構(gòu)與算法復習題一、選擇題。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ù)的邏輯

34、結(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邏輯和存儲 D物理4在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要存儲 C 。A數(shù)據(jù)的處理方法 B數(shù)據(jù)元素的類型 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)7算法分析的目的是 C ，算法分析的兩個主要方面

35、是 A 。（1）A找出數(shù)據(jù)結(jié)構(gòu)的合理性 B研究算法中的輸入和輸出的關(guān)系C分析算法的效率以求改進 C分析算法的易讀性和文檔性（2）A空間復雜度和時間復雜度 B正確性和簡明性 C可讀性和文檔性 D數(shù)據(jù)復雜性和程序復雜性8下面程序段的時間復雜度是 O(n2) 。 s =0;for( I =0; i<n; i+) for(j=0;j<n;j+)s +=Bij;sum = s ;9下面程序段的時間復雜度是 O(n*m) 。for( i =0; i<n; i+) for(j=0;j<m;j+)Aij 0;10下面程序段的時間復雜度是 O(log3n) 。i 0；while（i<

36、;=n）i = i * 3；11在以下的敘述中，正確的是 B 。A線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)B二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C棧的操作方式是先進先出D隊列的操作方式是先進后出12通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著 B 。A數(shù)據(jù)元素具有同一特點B不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應的數(shù)據(jù)項的類型要一致C每個數(shù)據(jù)元素都一樣D數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等13鏈表不具備的特點是 A 。A可隨機訪問任一結(jié)點 B插入刪除不需要移動元素C不必事先估計存儲空間 D所需空間與其長度成正比14不帶頭結(jié)點的單鏈表head為空的判定條件是 A 。Ahead

37、= NULL B head->next =NULL Chead->next =head D head!=NULL15帶頭結(jié)點的單鏈表head為空的判定條件是 B 。Ahead = NULL B head->next =NULL Chead->next =head D head!=NULL16若某表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點或刪除最后一個結(jié)點，則采用 D 存儲方式最節(jié)省運算時間。A單鏈表 B給出表頭指針的單循環(huán)鏈表 C雙鏈表 D帶頭結(jié)點的雙循環(huán)鏈表17需要分配較大空間，插入和刪除不需要移動元素的線性表，其存儲結(jié)構(gòu)是 B 。A單鏈表 B靜態(tài)鏈表 C線性鏈表

38、 D順序存儲結(jié)構(gòu)18非空的循環(huán)單鏈表head的尾結(jié)點（由p所指向）滿足 C 。Ap->next = NULL Bp = NULLCp->next =head Dp = head19在循環(huán)雙鏈表的p所指的結(jié)點之前插入s所指結(jié)點的操作是 D 。Ap->prior = s；s->next = p；p->prior->next = s；s->prior = p->priorBp->prior = s；p->prior->next = s；s->next = p；s->prior = p->priorCs->nex

39、t = p；s->prior = p->prior；p->prior = s；p->prior->next = sDs->next = p；s->prior = p->prior；p->prior->next = s；p->prior = s20如果最常用的操作是取第i個結(jié)點及其前驅(qū)，則采用 D 存儲方式最節(jié)省時間。A單鏈表 B雙鏈表 C單循環(huán)鏈表 D 順序表21在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然保持有序的時間復雜度是 B 。AO（1） BO（n） CO（n2） DO（nlog2n）22在一個長度為n（n>

40、;1）的單鏈表上，設有頭和尾兩個指針，執(zhí)行 B 操作與鏈表的長度有關(guān)。A刪除單鏈表中的第一個元素B刪除單鏈表中的最后一個元素C在單鏈表第一個元素前插入一個新元素D在單鏈表最后一個元素后插入一個新元素23與單鏈表相比，雙鏈表的優(yōu)點之一是 D 。A插入、刪除操作更簡單 B可以進行隨機訪問C可以省略表頭指針或表尾指針D順序訪問相鄰結(jié)點更靈活24如果對線性表的操作只有兩種，即刪除第一個元素，在最后一個元素的后面插入新元素，則最好使用 B 。A只有表頭指針沒有表尾指針的循環(huán)單鏈表B只有表尾指針沒有表頭指針的循環(huán)單鏈表C非循環(huán)雙鏈表D循環(huán)雙鏈表25在長度為n的順序表的第i個位置上插入一個元素（1 i n+

41、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可方便地用于各種邏輯結(jié)構(gòu)的存儲表示C存儲密度大 D刪除運算方便28下面關(guān)于線性表的敘述中，錯誤的是哪一個？ B 。A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元B線性表采用順序存儲，便于進行插入和刪除操作。C線性表采用鏈式存儲，不必占用一片連續(xù)的存儲單元D線性表采用鏈式存儲，便于進行插入和刪除操作。29線性表是

42、具有n個 B 的有限序列。A字符 B數(shù)據(jù)元素 C數(shù)據(jù)項 D表元素30在n個結(jié)點的線性表的數(shù)組實現(xiàn)中，算法的時間復雜度是O（1）的操作是 A 。A訪問第i（1<=i<=n）個結(jié)點和求第i個結(jié)點的直接前驅(qū)（1<i<=n）B在第i（1<=i<=n）個結(jié)點后插入一個新結(jié)點C刪除第i（1<=i<=n）個結(jié)點D以上都不對31若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間復雜度為 C 。AO(0) BO(1) CO(n) DO(n2)32對于順序存儲的線性表，訪問結(jié)點和增加、刪除結(jié)點的時間復雜度為 C 。AO(n) O(n) BO

43、(n) O(1) CO(1) O(n) DO(1) O(1)33線性表（a1,a2, ,an）以鏈式方式存儲，訪問第i位置元素的時間復雜度為 C 。AO(0) BO(1) CO(n) DO(n2)34單鏈表中，增加一個頭結(jié)點的目的是為了 C 。A使單鏈表至少有一個結(jié)點 B標識表結(jié)點中首結(jié)點的位置C方面運算的實現(xiàn) D說明單鏈表是線性表的鏈式存儲35在單鏈表指針為p的結(jié)點之后插入指針為s的結(jié)點，正確的操作是 B 。Ap->next=s；s->next=p->next B s->next=p->next ；p->next=s;Cp->next=s；p->

44、;next=s->next Dp->next=s->next；p->next=s36線性表的順序存儲結(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只允許在端點處插入和刪除元素 D沒有共同點39一個棧的進棧序列是a，b，c，d，e，則棧的不可能的輸出序列是 C 。Aedcba Bdecba Cdceab Dabcde40設有一個棧，元素依次進棧的順序為A、B、C、D、E。下列 C 是不可能

45、的出棧序列。 AA,B,C,D,E BB,C,D,E,A CE,A,B,C,D DE,D,C,B,A41以下 B 不是隊列的基本運算？A從隊尾插入一個新元素 B從隊列中刪除第i個元素C判斷一個隊列是否為空 D讀取隊頭元素的值42若已知一個棧的進棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1n，則pi為 C 。Ai Bni Cni1 D不確定43判定一個順序棧st（最多元素為MaxSize）為空的條件是 B 。Ast->top != -1 Bst->top = -1 Cst->top != MaxSize D st->top = MaxSize 44判

46、定一個順序棧st（最多元素為MaxSize）為滿的條件是 D 。Ast->top != -1 Bst->top = -1 Cst->top != MaxSize Dst->top = MaxSize 45一個隊列的入隊序列是1，2，3，4，則隊列的輸出序列是 B 。A4，3，2，1 B1，2，3，4C1，4，3，2 D3，2，4，146判定一個循環(huán)隊列qu（最多元素為MaxSize）為空的條件是 C 。Aqu->rear qu->front =MaxSize Bqu->rear qu->front -1=MaxSize Cqu->rear

47、=qu->front D qu->rear =qu->front -147在循環(huán)隊列中，若front與rear 分別表示對頭元素和隊尾元素的位置，則判斷循環(huán)隊列空的條件是 C 。 Afront=rear+1 Brear=front+1 Cfront=rear Dfront=048向一個棧頂指針為h的帶頭結(jié)點的鏈棧中插入指針s所指的結(jié)點時，應執(zhí)行 D 操作。Ah->next=s  Bs->next=h Cs->next=h h =s  Ds->next=h->next h->next=s 49輸入序列為ABC，可以變?yōu)镃BA時，經(jīng)過的棧操作為 B 。Apush，pop，push，pop，push，pop Bpush，push，push，pop， pop， pop Cpush，push，pop， pop，push，pop Dpush，pop，push，push，pop， pop50若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空