完整word版計算機軟件練習題匯總

1、軟件工程與數(shù)據(jù)庫部分： 一、填空題 1. 軟件是計算機程序、方法和規(guī)則相關的 以及在計算機上運行它時所必須的數(shù)據(jù)。 軟件是計算機程序、方法和規(guī)則相關的文檔以及在計算機上運行它時所必須的 。 2. 軟件是 、方法和規(guī)則相關的文檔以及在計算機上運行它時所必須的數(shù)據(jù)。3. 軟件工程是從技術和 兩方面研究如何更好地開發(fā)和維護計算機軟件的一門學4. 科。 5. 結(jié)構(gòu)化方法由 、 、 構(gòu)成，是一種面向數(shù)據(jù)流的開發(fā)方法。 6. 需求分析階段產(chǎn)生的最重要的文檔之一是 。 7. 數(shù)據(jù)流圖中的箭頭表示 。 二、單項選擇題 1. 在數(shù)據(jù)流圖中，（圓圈）代表（ ）。 A、源點 B、終點 C、加工 D、模塊 2. 在數(shù)

2、據(jù)流圖中，使用雙線表示（ ）。 A、源點和終點 B、數(shù)據(jù)存儲 C、加工 D、模塊 3. 軟件設計階段一般分為兩步：（ ）。 A、邏輯設計與功能設計 B、總體設計與詳細設計 C、概念設計與物理設計 D、模型設計與程序設計 4. 軟件生存周期可劃分為三個時期：計劃期、開發(fā)期和（ ）。 A、調(diào)研期 B、可行性分析期 C、 運行期 D、測試期 5. 軟件工程的出現(xiàn)主要是由于( )。 A、程序設計方法學的影響 B、其它工程科學的影響 C、軟件危機的出現(xiàn) D、計算機的發(fā)展 6. 軟件生存周期可劃分為計劃期、開發(fā)期及運行期三個階段，下列工作（ ）屬于計劃期階段。 A、程序設計 B、問題定義及可行性研究 C、

3、軟件測試 D、需求分析 7. 軟件生存周期可劃分為計劃期、開發(fā)期及運行期三個階段，下列工作（ ）屬于運行期階段。 A、維護 B、可行性分析 C、測試 D、問題定義 8. 在需求分析階段，系統(tǒng)分析人員采用數(shù)據(jù)流圖和（ ）來表達自己對問題域用戶需求的理解。 A、程序流程圖 B 、判定表或判定樹 C、數(shù)據(jù)字典（DD） D、加工 9. 在基于結(jié)構(gòu)化分析與設計的軟件開發(fā)方法中，系統(tǒng)分析人員在需求分析階段應采用（）和數(shù)據(jù)字典來表達自己對問題域用戶需求的理解。 A、程序流程圖 B、數(shù)據(jù)流圖（DFD） C、數(shù)據(jù)流 D、加工 10. 軟件測試的目的是（ ）。 A、要證明程序無錯誤 B、發(fā)現(xiàn)軟件中存在的錯誤 C、

4、找出編程中的錯誤并設法改正 D、檢查軟件的結(jié)構(gòu)設計是否合理 11. 軟件測試方法中，黑盒、白盒測試法是常用的方法，其中白盒測試主要用于測試（ ）。 A、結(jié)構(gòu)合理性 B、軟件外部功能 C、程序正確性 D、程序內(nèi)部邏輯 三、判斷題 1. （ ）軟件就是程序。 2. （ ）在設計軟件測試用例時不僅需選擇對被測軟件的預期功能是合理的輸入數(shù)據(jù)，而且還應該選擇不合理的輸入數(shù)據(jù)。 3. （ ）軟件測試中設計測試用例時只需選擇對被測軟件的預期功能是合理的輸入數(shù)據(jù)，而不選擇不合理的輸入數(shù)據(jù)。 4. （ ）軟件測試分為模塊測試、組裝測試和確認測試三個階段。 5. （ ）黑盒測試不僅需要考慮程序的功能，還需要知道程

5、序的內(nèi)部細節(jié)、結(jié)構(gòu)和實現(xiàn)方式。 6. （ ）黑盒測試只需要考慮程序的功能，不需要知道程序的內(nèi)部細節(jié)、結(jié)構(gòu)和實現(xiàn)方式。 7. （ ）白盒測試中的測試用例的設計需要考慮覆蓋程序內(nèi)部的邏輯結(jié)構(gòu)。 8. （ ）白盒測試中的測試用例設計只需要考慮覆蓋程序內(nèi)部的邏輯結(jié)構(gòu)，不需要考慮程序的預期功能。 9. （ ）模塊測試能發(fā)現(xiàn)詳細設計階段和編（碼）程階段的錯誤。 10. （ ）組裝測試能發(fā)現(xiàn)與模塊接口有關的問題。 11. （ ）確認測試主要采用白盒測試方法。 12. （ ）軟件總體設計的根本任務就是確定每個程序模塊的內(nèi)部特征，即確定模塊內(nèi)部的執(zhí)行過程。 13. （ ）軟件測試與軟件調(diào)試的目的完全相同。 14

6、. （ ）信息是人們用來對客觀世界直接進行描述、可在人們之間進行傳遞的知識。 15. （ ）目前，在數(shù)據(jù)庫技術中廣泛應用的數(shù)據(jù)模型是層次模型。 16. （ ）軟件詳細設計的根本任務就是確定每個模塊的內(nèi)部特征，即確定模塊內(nèi)部的執(zhí)行過程。 17. （ ）軟件測試的目的是發(fā)現(xiàn)程序中的錯誤，然后找出錯誤的原因并加以糾正。 四、簡答題 1. 軟件測試包括哪些步驟？說明這些步驟的測試對象是什么？ 2. 數(shù)據(jù)庫系統(tǒng)的定義是什么？它由哪幾部分組成？ 線性數(shù)據(jù)結(jié)構(gòu)部分： 一、填空題 1. 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、 和數(shù)據(jù)的運算三個方面。 數(shù)據(jù)結(jié)構(gòu)包括 2. 、數(shù)據(jù)的存儲結(jié)構(gòu)和數(shù)據(jù)的運算三個方面。 在算法“正

7、確”的前提下，評價算法主要有兩個指標是：時間復雜度和 。 3. 在算法“正確”的前提下，衡量算法效率的主要指標是： 4. 及空間復雜度。 線性數(shù)據(jù)結(jié)構(gòu)的邏輯特征是有且僅有一個5. 和一個終端結(jié)點， 且所有結(jié)點都最 多只有一個直接前趨和一個 。 6. 線性數(shù)據(jù)結(jié)構(gòu)的邏輯特征是有且僅有一個開始結(jié)點和一個終端結(jié)點，且所有結(jié)點都最多只有一個 和一個直接后繼。 7. 數(shù)據(jù)的存儲結(jié)構(gòu)包含有 、 、 和 等四種基本的映像方法。 8. 數(shù)據(jù)存儲結(jié)構(gòu)的四種基本形式是： 存儲結(jié)構(gòu)、 存儲結(jié)構(gòu)、索引存儲結(jié)構(gòu)以 及散列存儲結(jié)構(gòu)。 9. 若頻繁地對線性表進行插入與刪除操作，該線性表應采用 存儲結(jié)構(gòu)。 10. 線性鏈表中

8、數(shù)據(jù)元素的組成：一是數(shù)據(jù)元素的值，二是直接后繼元素的 ， 這兩部分信息組成數(shù)據(jù)元素的存儲映像，即結(jié)點。 11. 帶頭結(jié)點的單向鏈表L為空的判定條件是 。 12. 在一個單鏈表中p所指結(jié)點之后插入s所指結(jié)點時,應執(zhí)行s-next= 和 p-next= 的操作。 13. 要在一個單鏈表中p所指結(jié)點之后插入一個子鏈表，子鏈表第一個結(jié)點的地址為s，子鏈表最后一個結(jié)點的地址為t, 則應執(zhí)行操作： 和 。 14. 單鏈表的結(jié)點的數(shù)據(jù)類型是： typedef struct node int data; /*數(shù)據(jù)部分*/ struct node *next；/*指向下一個結(jié)點的指針*/ LinkList; L

9、inkList *p, *q; 如果要求將由指針變量q所指向的表外結(jié)點插入到單鏈表中由p所指向的結(jié)點之后，則應執(zhí)行的語句是：(1) (2) 。要將p所指向的結(jié)點的數(shù)據(jù)部分修改為25， 應執(zhí)行的語句是： 。 15. 插入和刪除只允許在表的同一端進行的線性表稱為 ，它具有 的特性。 16. 將插入操作限定在表的一端而刪除操作限定在表的另一端的線性表稱為 ，它具 有 的特性。 17. 對于一個以順序存儲實現(xiàn)的循環(huán)隊列Q0.10,隊頭、隊尾的位置指示器分別是front,rear,初始時都被設置為-1，則在該循環(huán)隊列中實現(xiàn)出隊操作時,判空的條件是： ；入隊操作時.判滿的條件是： 。 18. 二維數(shù)組A1

10、020采用列序為主方式存儲，每個元素占10個存儲單元，且A00的存儲地址是2000，則A612的地址是 。 19. 已知二維數(shù)組A2010采用行序為主方式存儲,每個元素占2個存儲單元,并且A105的存儲地址是1000,則A189的存儲地址是 。 20. 線性表的三種基本查找方法是：順序查找、 查找和 查找。 二、單項選擇題 1. 線性表中（ ）稱為線性表的長度。 A、元素的長度 B、數(shù)據(jù)項的數(shù)目 C、數(shù)據(jù)的長度 D、元素的個數(shù) 2. 不屬于線性表基本運算的是：（ ）。 A、刪除運算 B、指針運算 C、取結(jié)點運算 D、插入運算 3. 在下列關于線性表的敘述中，錯誤的是：( )。 A、采用順序存儲

11、的線性表，必須占用一片連續(xù)的存儲單元 B、采用順序存儲的線性表，便于進行插入和刪除操作 C、采用鏈式存儲的線性表，不必占用一片連續(xù)的存儲單元 D、采用鏈式存儲的線性表，便于進行插入和刪除操作 4. 當線性表選擇鏈表作為存儲結(jié)構(gòu)時，不具有的特點是：( )。 、插入、刪除時不需要移動大量元素 B、可隨機訪問任一元素AC、不必事先估計存儲空間 D、所需空間與線性表的長度成正比 5. 算法具有“確定性”等5個特性，下面對另外4個特性的描述中錯誤的是( )。 A、可行性 B、有零個或多個輸入 C、有窮性 D、有零個或多個輸出 6. 衡量一個算法的質(zhì)量除了正確性之外，最重要的是要考查（ ）。 A、可行性

12、B、有窮性 C、時間復雜度和空間復雜度 D、輸入和輸出 7. 在長度為n的線性表中，在第i個元素之前插入一個新的元素x，需要移動（ ）個元素。 A、n B、n-i+1 C、n-i D、i+1 8. 假設p是指向線性表中第i個數(shù)據(jù)元素結(jié)點的指針，則p-next是指向第i+1個數(shù)據(jù)元素結(jié)點的指針，若p-data=a, 則p-next-data=a+1，那么p-next-next指向的是ii第（ ）個結(jié)點。 A、i B、i+1 C、i+2 D、i+3 9. 以下哪一個不是隊列的基本運算？ A、從隊尾插入一個新元素 B、從隊列中刪除第i個元素 C、判斷一個隊列是否為空 D、讀取隊頭元素的值 10. 在

13、初始為空的隊列中順序插入元素a,b,c,d以后，緊接著作了兩次刪除操作，此時的隊尾元素是（ ）。 A、a B、b C、c D、d 11. 隊列的順序存儲方式中判斷循環(huán)隊列為滿的條件是（ ）。 A、front= =rear B、front= =（rear+1）%（maxsize+1） C、front= =（rear+1）% maxsize D、front= =rear % maxsize 12. 單鏈表Head中，在指針q所指結(jié)點后面插入一個由指針P所指結(jié)點，則執(zhí)行( )。 A、q-nextp-next；p-nextq； B、p-nextq-next；qp； C、q-nextp-next；p-n

14、extq； D、p-nextq-next；q-nextp； 13. 一個棧的輸入序列是1，2，3，4，則下列序列中不可能是棧的輸出序列的是( )。 A、1234 B、4321 C、2341 D、4123 14. 設在棧中，由頂向下已存放元素c，b，a，在第四個元素d入棧前，棧中元素可以出棧。試問在d入棧后，不可能的出棧序列是：( )。 A、d c b a B、c b d a C、c a d b D、c d b a 15. 棧S最多能容納4個元素?，F(xiàn)有6個元素按A、B、C、D、E、F的順序進棧, 問下列哪一個序列是可能的出棧序列? ( ) A、E D C B A F B、B C E F A D

15、C、C B E D A F D、A D F E B C 16. 設一個棧的入棧序列是abcde，則在下列輸出序列中不可能的出棧序列是：( ) A、e d c b a B、d e c b a C、d c e a b D、a b c d e 17. 若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3。當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為（ ）。 A、1和5 B、2和4 C、4和2 D、5和1 18. 設有9個數(shù)據(jù)記錄組成的線性表，它們的排序鍵碼字的取值分別是（11，15，20，27，30，35，46，88，120），已經(jīng)將它們按照排

16、序碼遞增有序的方式存放在一維結(jié)構(gòu)數(shù)組a0.8中從下標0開始到下標8結(jié)束的位置，則當采用折半查找算法查找關鍵字值等于20的數(shù)據(jù)記錄時，所需比較的元素的下標依次是：( )。（注：計算中間位置時取下整） A、0，1，2 B、4，1，2 C、4，2 D、4，3，2 。( )采用折半查找方法進行查找的數(shù)據(jù)文件應滿足的條件是： 19.A、順序存儲 B、鏈式存儲 C、順序存儲且已排序 D、鏈式存儲且已排序 三、判斷題 1. （ ）單鏈表從任何一個結(jié)點出發(fā)，都能訪問到所有結(jié)點。 （ ）2. 順序表是一種隨機存取的存儲結(jié)構(gòu)。 （ ）線性表的邏輯順序與存儲順序總是一致的。 3. （ 4.）線性表的鏈式存儲結(jié)構(gòu)優(yōu)于

17、順序存儲結(jié)構(gòu)。 （5. ）數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)在存儲單元中的表示形式。 （ ）6. 程序的執(zhí)行效率與數(shù)據(jù)存儲結(jié)構(gòu)的選擇沒有直接的關系。 （ ）線性表的長度是指線性表所占存儲空間的大小。7. （ 8. ）線性表的長度決定了線性表所占存儲空間的大小，但它不等于線性表所占存儲空間的大小。 9. （ ）在采用鏈式存儲結(jié)構(gòu)的線性表上查找某個元素的平均效率比在采用順序存儲結(jié)構(gòu)的線性表上查找的平均效率高。 10. （ ）鏈式存儲結(jié)構(gòu)的線性表適用于對數(shù)據(jù)進行頻繁的查找操作，而順序存儲結(jié)構(gòu)的線性表則適宜于進行頻繁地插入、刪除操作。 11. （ ）在單鏈表中，給定任一結(jié)點的地址p，則可用下述語句將新結(jié)點

18、s插入結(jié)點p的后面：p-next = s; s-next = p-next; 12. （ ）二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表。 13. （ ）N（N1）維數(shù)組可以看作是線性表的推廣。 14. （ ）循環(huán)隊列也存在空間溢出問題。 15. （ ）隊列和棧都是運算受限的線性表，插入或者刪除運算只允許在表的同一端進行。 16. （ ）從數(shù)據(jù)元素插入、刪除的規(guī)則來看，隊列的本質(zhì)特征是LIFO,棧的本質(zhì)特征是FIFO。 17. （ ）所有插入排序算法均是穩(wěn)定的。 18. （ ）順序存儲方式只能用于存儲線性結(jié)構(gòu)。 19. （ ）程序的執(zhí)行效率只決定于算法設計的技巧，與程序設計中所采用的數(shù)據(jù)的表示方式及數(shù)

19、據(jù)邏輯模型的實際存儲形式無關。 20. （ ）線性表的特點是每個元素都有一個前驅(qū)結(jié)點和一個后繼結(jié)點。 21. （ ）鏈表的每個結(jié)點中都包含一個指針。 22. （ ）算法一定要有輸入和輸出。 23. （ ）順序查找算法可以用在順序存儲結(jié)構(gòu)表示的線性表上查找數(shù)據(jù)元素，但不可以用在鏈式存儲結(jié)構(gòu)的線性表上查找數(shù)據(jù)元素。 24. （ ）折半查找方法只能用在采用順序存儲結(jié)構(gòu)的有序線性表中來實現(xiàn)對某一數(shù)據(jù)項的快速查找。 25. （ ）折半查找方法可以用在采用單向鏈表形式存儲的有序線性表中實現(xiàn)對某一數(shù)據(jù)項的快速查找。 26. （ ）判斷某個排序方法的穩(wěn)定性可以通過一次或幾次輸入數(shù)據(jù)序列，看排序結(jié)果是否改變了原

20、始待排數(shù)據(jù)序列中關鍵字值相同的數(shù)據(jù)是否發(fā)生了相對次序的改變，從而作出該排序算法是否穩(wěn)定的結(jié)論。 四、簡答題 1. 什么是算法？具有哪些特性？如何衡量一個算法的好壞？算法與程序有何不同？ 線性表順序存儲結(jié)構(gòu)的優(yōu)缺點是什么？ 2. 線性結(jié)構(gòu)與非線性結(jié)構(gòu)有何差別？3. 4. 簡述順序表和鏈表之間的差異。 什么是排序方法的穩(wěn)定性？5. 6. 什么叫棧？它有哪些基本操作？各個基本操作的含義是什么？ 什么叫隊列？它有哪些基本操作？各個基本操作的含義是什么？7. 五、綜合題 A的三元組表示法的存儲模型。1. 給出下列稀疏矩陣 33 0 22 0 -150 0 0 3 0 0 0 A = 0 0 0 -12

21、0 0 0 0 0 0 -10 0 0 0 0 0 0 0 0 0 0 0 0 2 2. 給出下列稀疏矩陣所對應的三元組表示方法存儲模型。 00129000?0000000?000?30014?00000240?00001800?0?0150700? 3. 給出下列稀疏矩陣A的三元組表示法的存儲模型。 4. 設單鏈表的結(jié)點為： typedef struct node int data; struct node *next LinkList; LinkList *p,q; 如果要求將由指針變量q所指向的結(jié)點插入到單向鏈接表中p所指向的結(jié)點之后，則應執(zhí)行的語句是什么？要將p所指向的結(jié)點的數(shù)據(jù)部分修

22、改為23，應執(zhí)行的語句是什么？ 5. 對于給定的一組關鍵字:503,087,512,067,908,170,889,276,675,453；請按關鍵字遞減排序，寫出直接插入排序、冒泡排序的各趟運行結(jié)果。 其中記錄的關鍵鍵碼值,的位置中90的有序表存儲于一維結(jié)構(gòu)數(shù)組中下標10某長度為 6.依次是：5,10,18,21,33,47,48,55,80，125，現(xiàn)要查找關鍵碼值為18及83的記錄，現(xiàn)規(guī)定在中間位置計算時采用“向下取整”的方法，寫出折半查找的過程及查找結(jié)果。 7. 有序表中關鍵字序列為：5，10，19，21，31，37，42，48，55，150，現(xiàn)要查找k為37及32的記錄，寫出其折半查

23、找過程。 8. 設待排序的記錄共7個，關鍵碼分別為8，3，2，5，9，1，6。試用直接插入、直接選擇兩種方法，以關鍵碼的變化描述排序全過程（動態(tài)過程），要求按遞減順序排序。 9. 設待排序文件共有12個記錄，其關鍵字依次分別是28，55，06，33，161，81，91，11，25，55，57，02，請按選擇排序的思想寫出降序排序的全過程。 10. 設有待排序的8個數(shù)據(jù)記錄，其排序用關鍵字的取值依次是14，35，18，5，7，21，35，8，請用簡單選擇排序法寫出降序排序的每一趟結(jié)果。 11. 設有待排序的8個數(shù)據(jù)記錄，其排序用關鍵字的取值依次是68，45，20，90，15，10，50，8，請按

24、直接選擇排序的思想寫出升序及降序排序的每一趟結(jié)果。 12. 假設待排序的一批記錄的關鍵字序列為14，35，18，5，7，21，請給出按照簡單選擇排序方法依據(jù)關鍵字取值升序和降序兩種情況下的排序過程。 13. 一個有序表的一批記錄的關鍵字序列為（7，11，15，20，32，45，63，70，82，91），存放在一個采用順序存儲結(jié)構(gòu)表示的線性表中，其中數(shù)組元素的下標為0，9的位置上分別對應存儲有序表的第一元素直到最后一個元素。在折半查找中，中間位置指示器的計算式子中采用取下整的方法，請給出查找關鍵字值為82和關鍵字值為13的記錄的查找過程。 14. 某長度為10的有序表存儲于一維結(jié)構(gòu)數(shù)組中下標09

25、的位置中，其中記錄的關鍵碼值依次是：5,10,18,21,33,47,48,55,80,125，現(xiàn)要查找關鍵碼值為18及83的記錄，現(xiàn)規(guī)定在中間位置計算時采用“取下整”的方法，寫出折半查找的過程及查找結(jié)果。 15. 設有待排序的8個數(shù)據(jù)記錄，其排序用關鍵字的取值依次是68，45，20，90，15，10，50，8，請用冒泡排序法寫出升序排序的每一趟結(jié)果。 16. 對于給定的一組關鍵字: 50,38,27,16,97,76,53,66；按關鍵字遞減排序，寫出冒泡排序的各趟運行結(jié)果。 六、算法分析與設計題 1. 下面給出的算法的功能是在順序存儲結(jié)構(gòu)表示的線性表中插入一個數(shù)據(jù)元素，請畫出算法的流程圖，

26、在算法中對各個分支給出功能性注釋。 #define Null 0 #define MaxSize 1024 typedef int DataType; typedef struct node DataType dataMaxSize; int last; SequenList; int Insert(SequenList *L,DataType x,int i) SequenList *p; int j; p=L; if(p-last=(MaxSize-1) printf(線性表已經(jīng)滿了，無法再加入!); return Null; else if( (i(p-last+1) ?牰湩晴尨所給插入

27、位置不在有效范圍之內(nèi)!); return Null; else for(j=L-last;j=i-1;j-) L-dataj+1=L-dataj; L-datai-1=x; L-last=L-last+1; return (1); 2. 現(xiàn)要求完成同類型的兩個線性表的合并運算，該運算將給定第二個線性表的元素追加到第一個線性表的最后一個元素之后，假定不會產(chǎn)生因空間不足而上溢的現(xiàn)象，運算完成后應修改第一個線性表的last分量以反映新的表長，運算不破壞第二個線性表。預期的功能用下面的計算示例及算法流程圖表示。請將下列給定的算法設計填寫完整。 算法功能描述：計算前 L1=1,3,5,7,9, L2=2

28、,4,6,8 計算后： L1=1,3,5,7,9,2,4,6,8,L2=2,4,6,8 線性表的順序存儲結(jié)構(gòu)定義： #define MaxSize 1024 /*允許的最大數(shù)據(jù)元素數(shù)目*/ typedef int DataType; /*數(shù)據(jù)元素的類型*/ typedef struct node DataType dataMaxSize; /*存儲線性表中數(shù)據(jù)元素用的數(shù)組*/ int last; /*存儲表的最后一個元素存放在data數(shù)組中的下標號*/ SequenList; 計算前： 在L1表的存儲結(jié)構(gòu)體變量中， data0=1,data1=3,data2=5,data3=7,data4=9

29、 last=4; 在L2表的存儲結(jié)構(gòu)體變量中，計算前： data0=2,data1=4,data2=6,data3=8 last=3 計算后： 在L1表的存儲結(jié)構(gòu)體變量中， data0=1,data1=3,data2=5,data3=7,data4=9,data5=2, data6=4,data7=6,data8=8 last=8; 在L2表的存儲結(jié)構(gòu)體變量中，計算前： data0=2,data1=4,data2=6,data3=8 last=3 待完成的算法如下： void MergeList(SequenList *L1,Sequenlist *L2) /*算法進入時：L1指向第一個線性表

30、的結(jié)構(gòu)體變量 L2指向第二個線性表的結(jié)構(gòu)體變量 算法退出后：L1指向第一個線性表的結(jié)構(gòu)體變量，其內(nèi)容為合并后的表。 L2指向第二個線性表的結(jié)構(gòu)體變量，其內(nèi)容未變。 */ int i,j; /*分別表示第一個表及第二個表的當前位置指示器*/ int k; /*循環(huán)控制變量*/ int n1,n2; /*分別用于存放表L1及表L2的長度*/ DataType x; /*存放從表L2中讀出的數(shù)據(jù)元素*/ n1=L1-last+1; n2=L2-last+1; i=L1-last+1; j=0; for(k=0;kdatai=x; i+; j+; =n1+n2-1; return; 開算法流程圖 n1

31、-的長 n2-的長 i的最后元素的下一空位 j的第一個元素位 k=0 nkn2 y last-n1+n2-1表datajx-2 datai-x退出 i-i+1 j-j+1 ktop=-1; return; int Push(S *s,datatype ch) if(s-top=maxsize-1) printf( stack overflow!n); return NULL; else s-top+; s-elementss-top=ch; return(1); int Pop(S *s) if(s-toptop-; return(s-top+1); main() char ch1; S *s

32、; int f1=f2=1; s=malloc(sizeof(S); IniStack(s); scanf(%c,&ch1); while(ch1!=$) if(ch1=() f1=Push(s,ch1); if(ch1=) f2=Pop(s); scanf(%c,&ch1); if(s-top=-1&f1!=-1&f2!=-1) printf(Brackets match rightlyn); else printf(The expression is wrong.n); getch(); 4. 閱讀下面的算法程序，繪制出算法流程圖，并說明本算法程序?qū)崿F(xiàn)的功能。 #define NULL 0

33、 typedef int datatype; typedef struct node datatype data; struct node *next; linklist; INSERT(linklist *L, datatype x) linklist *p,*q, *s; s=(linklist *)malloc(sizeof(linklist); s-data=x; p=L; q=L-next; while(q-datanext!=NULL) p=q; q=q-next; if(q-next=NULL) q-next=s; s-next=NULL; else p-next=s; s-ne

34、xt=q; 5. 下面的自定義類型SeqQueue表示循環(huán)隊列的一種順序存儲結(jié)構(gòu)實現(xiàn)方法，（1）請將相關的入隊和出隊運算（操作）函數(shù)填寫完整；（2）寫出測試程序的執(zhí)行結(jié)果；（3）給程序加分析注釋。 /*-文件myqueue.h的內(nèi)容如下-*/ #define MaxLength 1024 typedef int datatype; typedef struct sequeue datatype dataMaxLength; int front,rear; SeqQueue; SeqQueue *p) void SETNULLQS( if(p=NULL) return; else p-front

35、=MaxLength-1; p-rear=MaxLength-1; return; int ENQUEUEQS(SeqQueue *p, datatype x) int tail; if(p-front= (p-rear+1) ) printf(“n隊已經(jīng)滿啦!n”); return (0); else p-rear= ; tail=p-rear; p-datatail=x; return (1); int DEQUEUEQS(SeqQueue *p,datatype *px) datatype Member1; if(p-front=p-rear) printf(“n隊列空啦！n”);ret

36、urn （; ）0else p-front= ; Member1=p-datap-front; *px= ; return (1); myqueue.h*/ /*文件*/ 測試程序部分/*#include #include myqueue.h; void main() int i,abc10=9,8,7,6,5,4,3,2,1,10; datatype in1,out1; SeqQueue myQue,*pQ; pQ=&myQue; SETNULLQS(pQ); ); “進入隊列的元素依次是：n”printf(for(i=1;i=10;i+) ,abci-1); %dt”printf(“in1

37、=abci-1; ENQUEUEQS(pQ,in1); ); “n從隊列中刪除的元素依次是：”nprintf(for(i=1;i=10;i+) in1=abci-1; DEQUEUEQS(pQ,&out1); ,out1); printf(%dt“” 6. 下面一段程序的功能是完成線性表的插入操作運算(要在線性表的第i個位置插入元素)請仔細閱讀程序，完成兩個要求： (1) 在畫線空白處填入合適的語句，使得整個程序完整； (2) 請畫出以下程序的流程圖。 #define Maxlen 1024 struct sqlisttp int elemmaxlen; int last; sqlisttp;

38、 int Insert(sqlisttp L, int i, int x) int k; if(iv.last+1) printf(“插入位置不合適！n”) else if(v.lat=maxlen-1) printf(“線性表已滿！n”) else for(k=v.last; k=i; k-) ； ； ； 非線性數(shù)據(jù)結(jié)構(gòu)部分： 一、填空題 1. 不考慮順序的3個結(jié)點可構(gòu)成 種不同形態(tài)的樹， 種不同形態(tài)的二叉樹。 2. 已知某棵完全二叉樹的第4層有5個結(jié)點，則該完全二叉樹葉子結(jié)點的總數(shù)為： 。 3. 已知一棵完全二叉樹的第5層有3個結(jié)點，其葉子結(jié)點數(shù)是 。 4. 一棵具有110個結(jié)點的完全二叉

39、樹，若i54，則結(jié)點i的雙親編號是 ；結(jié)點i 的左孩子結(jié)點的編號是 ，結(jié)點i的右孩子結(jié)點的編號是 。 5. 一棵具有48個結(jié)點的完全二叉樹，若i20，則結(jié)點i的雙親編號是_；結(jié)點i的左孩子結(jié)點編號是_，右孩子結(jié)點編號是_。 。_樹中，總的結(jié)點數(shù)是：Huffman個葉子結(jié)點的n在有 6.7. 圖是一種非線性數(shù)據(jù)結(jié)構(gòu)，它由兩個集合V(G)和E(G)組成，V(G)是_的非空有限集合，E(G)是_的有限集合。 8. 遍歷圖的基本方法有 優(yōu)先搜索和 優(yōu)先搜索兩種方法。 9. 圖的遍歷基本方法中 是一個遞歸過程。 10. n個頂點的有向圖最多有 條??；n個頂點的無向圖最多有 條邊。 11. 在二叉樹的二叉

40、鏈表中，判斷某指針p所指結(jié)點是葉子結(jié)點的條件是 。 12. 在無向圖G的鄰接矩陣A中，若Ai,j等于1，則Aj,i等于 。 二、單項選擇題 1. 樹型結(jié)構(gòu)的特點是：任意一個結(jié)點：（ ） A、可以有多個直接前趨 B、可以有多個直接后繼 C、至少有1個前趨 D、只有一個后繼 2. 如下圖所示的4棵二叉樹中，（ ）不是完全二叉樹。 D C A B 深度為5的二叉樹至多有（ ）個結(jié)點。3. 10 D、32 C、31 BA、16 、 （ ）。4. 64個結(jié)點的完全二叉樹的深度為：5 、 D C、6 、A、8 B7 每一層從左到右依次對結(jié)點進行編個結(jié)點的完全二叉樹從根這一層開始，將一棵有1005. 。 ）

41、號，根結(jié)點編號為1，則編號為49的結(jié)點的左孩子的編號為：（48 D、C、50 、A98 B、99 ）倍。6. 在一個無向圖中，所有頂點的度之和等于邊數(shù)的（4 、2 D1 A、1/2 B、 C、 個結(jié)點。Huffman樹，則該Huffman樹中共有( ) 7.設有13個值，用它們組成一棵25 D、 B、12 C、26 A、13 ，它的雙親結(jié)個結(jié)點的完全二叉樹按層編號，則對于編號為7的結(jié)點x8. 若對一棵有16 點及右孩子結(jié)點的編號分別為( )。3,15 、 D、2,15 C、3,14 A、2,14 B，它的雙親結(jié)的結(jié)點x 9.若對一棵有20個結(jié)點的完全二叉樹按層編號，則對于編號為5 ( )。點及

42、左孩子結(jié)點的編號分別為3,10 、3,9 D A、2,11 B、2,10 C每一層從左到右依次對結(jié)點進行編 10.將一棵有100個結(jié)點的完全二叉樹從根這一層開始， 號，根結(jié)點編號為1，則編號最大的非葉結(jié)點的編號為：51 D、 C、50 、 A、48 B49 。無向圖的鄰接矩陣是一個11. ( ) 、對角矩陣DC、零矩陣A、對稱矩陣 B 、上三角矩陣 。( ) 12.由64個結(jié)點構(gòu)成的完全二叉樹，其深度為：5 7 C、6 D、A8 B，它的雙親結(jié)x的結(jié)點7個結(jié)點的完全二叉樹按層編號，則對于編號為16若對一棵有 13. ( )。點及右孩子結(jié)點的編號分別為3,15 3,14 D、2,14 B、2,1

43、5 C、A ）14. 圖示二叉樹的中序遍歷序列是：（ a bc gd e f defbagc dbaefcg D、dfebagc C、A、abcdgef B ） 圖示二叉樹的后序遍歷序列是：（15. A C B E D G F H HGFEDCBA 、DBFHGECA D、ABCDEFGH B、BDAFEHGC CA ）。16. 鄰接表是圖的一種（ D、散列存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu) C、索引存儲結(jié)構(gòu)A、順序存儲結(jié)構(gòu) B 。（ ）17. 給定有向圖如右圖所示，則該圖的一個強連通分量是： A,B,C,F 、AB,C,F 、BB,C,D,F 、CC,D,E,F 、D 個結(jié)點發(fā)出的邊，應該： 已知一個有

44、向圖的鄰接矩陣表示，要刪除所有從第i18.0 行元素全部置為ii、將鄰接矩陣的第行刪除 B、將鄰接矩陣的第A0 列元素全部置為i、將鄰接矩陣的第 D列刪除i、將鄰接矩陣的第C三、判斷題 1. （ ）非線性數(shù)據(jù)結(jié)構(gòu)可以順序存儲，也可以鏈接存儲。 （2. ）非線性數(shù)據(jù)結(jié)構(gòu)只能用鏈接方式才能表示其中數(shù)據(jù)元素的相互關系。 （ 3. ）完全二叉樹一定是滿二叉樹。 （ ）在平衡二叉樹中，任意結(jié)點左右子樹的高度差（絕對值）不超過1。 4.（5. ）若一棵二叉樹的任意一個非葉子結(jié)點的度為2 ，則該二叉樹為滿二叉樹。 （ ）度為6. 1的有序樹與度為1的二叉樹是等價的。 （7. ）二叉樹的先序遍歷序列中，任意一

45、個結(jié)點均排列在其孩子結(jié)點的前面。 （8. ）已知一棵二叉樹的先序序列和后序序列，就一定能構(gòu)造出該二叉樹。 （ 9. ）在霍夫曼樹中，權值最小的結(jié)點離根結(jié)點最近。 ( )對任意一個圖，10. 從它的某個頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先遍歷可訪問到該圖的每個頂點。 11. （ ）線性數(shù)據(jù)結(jié)構(gòu)可以采用順序存儲結(jié)構(gòu)或鏈式存儲結(jié)構(gòu)，而非線性數(shù)據(jù)結(jié)構(gòu)只能采用鏈式存儲結(jié)構(gòu)。 12. （ ）二叉樹中的葉子結(jié)點就是二叉樹沒有左、右子樹的結(jié)點。 13. （ ）如果一棵樹中某結(jié)點的度為1，則該結(jié)點僅有一棵子樹。 14. （ ）在有向圖中，若存在有向邊,則一定存在有向邊。 15. （ ）對任意一個圖，從它的某個頂點

46、出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先遍歷后，并不一定能訪問到該圖的每個頂點。 16. （ ）用鄰接矩陣法存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中結(jié)點個數(shù)有關，而與圖的邊數(shù)無關。 四、簡答題 1. 什么叫有序樹？什么叫無序樹？有序樹和二叉樹的差別是什么？ 2. 什么叫完全二叉樹？什么叫滿二叉樹？它們之間的關系是什么？ 3. 什么情況下二叉排序樹的查找性能較好？什么情況下二叉排序樹的查找性能最差？ 五、綜合題 1. 如圖所示的兩棵二叉樹，分別給出它們的順序存儲結(jié)構(gòu)。 A C B E D G F I K J 1 第棵樹 ABCEDFIJ 第2棵樹 2. 已知一棵二叉樹的中序、后序序列分別如下： 中序：D C E F B H G A K J L I M