完整word版計(jì)算機(jī)軟件練習(xí)題匯總

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

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

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

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

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

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

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

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

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

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

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

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

13、初始為空的隊(duì)列中順序插入元素a,b,c,d以后，緊接著作了兩次刪除操作，此時(shí)的隊(duì)尾元素是（ ）。 A、a B、b C、c D、d 11. 隊(duì)列的順序存儲(chǔ)方式中判斷循環(huán)隊(duì)列為滿(mǎn)的條件是（ ）。 A、front= =rear B、front= =（rear+1）%（maxsize+1） C、front= =（rear+1）% maxsize D、front= =rear % maxsize 12. 單鏈表Head中，在指針q所指結(jié)點(diǎn)后面插入一個(gè)由指針P所指結(jié)點(diǎn)，則執(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. 一個(gè)棧的輸入序列是1，2，3，4，則下列序列中不可能是棧的輸出序列的是( )。 A、1234 B、4321 C、2341 D、4123 14. 設(shè)在棧中，由頂向下已存放元素c，b，a，在第四個(gè)元素d入棧前，棧中元素可以出棧。試問(wèn)在d入棧后，不可能的出棧序列是：( )。 A、d c b a B、c b d a C、c a d b D、c d b a 15. 棧S最多能容納4個(gè)元素。現(xiàn)有6個(gè)元素按A、B、C、D、E、F的順序進(jìn)棧, 問(wèn)下列哪一個(gè)序列是可能的出棧序列? ( ) 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. 設(shè)一個(gè)棧的入棧序列是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. 若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3。當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為（ ）。 A、1和5 B、2和4 C、4和2 D、5和1 18. 設(shè)有9個(gè)數(shù)據(jù)記錄組成的線(xiàn)性表，它們的排序鍵碼字的取值分別是（11，15，20，27，30，35，46，88，120），已經(jīng)將它們按照排

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

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

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

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

20、始待排數(shù)據(jù)序列中關(guān)鍵字值相同的數(shù)據(jù)是否發(fā)生了相對(duì)次序的改變，從而作出該排序算法是否穩(wěn)定的結(jié)論。 四、簡(jiǎn)答題 1. 什么是算法？具有哪些特性？如何衡量一個(gè)算法的好壞？算法與程序有何不同？ 線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)是什么？ 2. 線(xiàn)性結(jié)構(gòu)與非線(xiàn)性結(jié)構(gòu)有何差別？3. 4. 簡(jiǎn)述順序表和鏈表之間的差異。 什么是排序方法的穩(wěn)定性？5. 6. 什么叫棧？它有哪些基本操作？各個(gè)基本操作的含義是什么？ 什么叫隊(duì)列？它有哪些基本操作？各個(gè)基本操作的含義是什么？7. 五、綜合題 A的三元組表示法的存儲(chǔ)模型。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. 給出下列稀疏矩陣所對(duì)應(yīng)的三元組表示方法存儲(chǔ)模型。 00129000?0000000?000?30014?00000240?00001800?0?0150700? 3. 給出下列稀疏矩陣A的三元組表示法的存儲(chǔ)模型。 4. 設(shè)單鏈表的結(jié)點(diǎn)為： typedef struct node int data; struct node *next LinkList; LinkList *p,q; 如果要求將由指針變量q所指向的結(jié)點(diǎn)插入到單向鏈接表中p所指向的結(jié)點(diǎn)之后，則應(yīng)執(zhí)行的語(yǔ)句是什么？要將p所指向的結(jié)點(diǎn)的數(shù)據(jù)部分修

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

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

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

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

26、在算法中對(duì)各個(gè)分支給出功能性注釋。 #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(線(xiàn)性表已經(jīng)滿(mǎn)了，無(wú)法再加入!); 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)要求完成同類(lèi)型的兩個(gè)線(xiàn)性表的合并運(yùn)算，該運(yùn)算將給定第二個(gè)線(xiàn)性表的元素追加到第一個(gè)線(xiàn)性表的最后一個(gè)元素之后，假定不會(huì)產(chǎn)生因空間不足而上溢的現(xiàn)象，運(yùn)算完成后應(yīng)修改第一個(gè)線(xiàn)性表的last分量以反映新的表長(zhǎng)，運(yùn)算不破壞第二個(gè)線(xiàn)性表。預(yù)期的功能用下面的計(jì)算示例及算法流程圖表示。請(qǐng)將下列給定的算法設(shè)計(jì)填寫(xiě)完整。 算法功能描述：計(jì)算前 L1=1,3,5,7,9, L2=2

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

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

30、的結(jié)構(gòu)體變量 L2指向第二個(gè)線(xiàn)性表的結(jié)構(gòu)體變量 算法退出后：L1指向第一個(gè)線(xiàn)性表的結(jié)構(gòu)體變量，其內(nèi)容為合并后的表。 L2指向第二個(gè)線(xiàn)性表的結(jié)構(gòu)體變量，其內(nèi)容未變。 */ int i,j; /*分別表示第一個(gè)表及第二個(gè)表的當(dāng)前位置指示器*/ int k; /*循環(huán)控制變量*/ int n1,n2; /*分別用于存放表L1及表L2的長(zhǎng)度*/ 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; 開(kāi)算法流程圖 n1

31、-的長(zhǎng) n2-的長(zhǎng) i的最后元素的下一空位 j的第一個(gè)元素位 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. 閱讀下面的算法程序，繪制出算法流程圖，并說(shuō)明本算法程序?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. 下面的自定義類(lèi)型SeqQueue表示循環(huán)隊(duì)列的一種順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)方法，（1）請(qǐng)將相關(guān)的入隊(duì)和出隊(duì)運(yùn)算（操作）函數(shù)填寫(xiě)完整；（2）寫(xiě)出測(cè)試程序的執(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隊(duì)已經(jīng)滿(mǎn)啦!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隊(duì)列空啦！n”);ret

36、urn （; ）0else p-front= ; Member1=p-datap-front; *px= ; return (1); myqueue.h*/ /*文件*/ 測(cè)試程序部分/*#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); ); “進(jìn)入隊(duì)列的元素依次是：n”printf(for(i=1;i=10;i+) ,abci-1); %dt”printf(“in1

37、=abci-1; ENQUEUEQS(pQ,in1); ); “n從隊(duì)列中刪除的元素依次是：”nprintf(for(i=1;i=10;i+) in1=abci-1; DEQUEUEQS(pQ,&out1); ,out1); printf(%dt“” 6. 下面一段程序的功能是完成線(xiàn)性表的插入操作運(yùn)算(要在線(xiàn)性表的第i個(gè)位置插入元素)請(qǐng)仔細(xì)閱讀程序，完成兩個(gè)要求： (1) 在畫(huà)線(xiàn)空白處填入合適的語(yǔ)句，使得整個(gè)程序完整； (2) 請(qǐng)畫(huà)出以下程序的流程圖。 #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(“線(xiàn)性表已滿(mǎn)！n”) else for(k=v.last; k=i; k-) ； ； ； 非線(xiàn)性數(shù)據(jù)結(jié)構(gòu)部分： 一、填空題 1. 不考慮順序的3個(gè)結(jié)點(diǎn)可構(gòu)成 種不同形態(tài)的樹(shù)， 種不同形態(tài)的二叉樹(shù)。 2. 已知某棵完全二叉樹(shù)的第4層有5個(gè)結(jié)點(diǎn)，則該完全二叉樹(shù)葉子結(jié)點(diǎn)的總數(shù)為： 。 3. 已知一棵完全二叉樹(shù)的第5層有3個(gè)結(jié)點(diǎn)，其葉子結(jié)點(diǎn)數(shù)是 。 4. 一棵具有110個(gè)結(jié)點(diǎn)的完全二叉

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

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

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

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

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

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

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

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