1、全國計算機(jī)等級考試指導(dǎo)教程（二級）公共基礎(chǔ)知識編著 黃海軍2013年9月目 錄前言4二級考試中的公共基礎(chǔ)知識的備考4歷年公共基礎(chǔ)知識考點(diǎn)統(tǒng)計與分析6第一章數(shù)據(jù)結(jié)構(gòu)與算法71.1算法71.2數(shù)據(jù)結(jié)構(gòu)的基本概念81.3線性表及其順序存儲結(jié)構(gòu)101.4棧和隊列111.5線性鏈表131.6樹與二叉樹151.7查找技術(shù)191.8排序技術(shù)20第二章 程序設(shè)計基礎(chǔ)222.1程序設(shè)計設(shè)計方法和風(fēng)格222.2結(jié)構(gòu)化程序設(shè)計（面向過程的程序設(shè)計方法）232.3面向?qū)ο蟮某绦蛟O(shè)計24第三章 軟件工程基礎(chǔ)273.1 軟件工程基本概念273.2 結(jié)構(gòu)化分析方法313.3 結(jié)構(gòu)化設(shè)計方法323.4 軟件測試363.5 程

2、序的調(diào)試39第四章 數(shù)據(jù)庫設(shè)計基礎(chǔ)414.1 數(shù)據(jù)庫系統(tǒng)的基本概念414.2 數(shù)據(jù)模型454.3關(guān)系代數(shù)474.4 數(shù)據(jù)庫設(shè)計與管理50計算機(jī)等級考試二級指導(dǎo)教程公共基礎(chǔ)知識前言二級考試中的公共基礎(chǔ)知識的備考從2005年初開始，教育部對全國計算機(jī)等級考試進(jìn)行了較大調(diào)整。二級考試的筆試包括基礎(chǔ)知識和程序設(shè)計兩部分，其中基礎(chǔ)知識占30分。這次改革的思想就是將基礎(chǔ)知識的內(nèi)容由計算機(jī)常識（一級難度）調(diào)整為程序開發(fā)基礎(chǔ)（三級難度），如果這部分知識內(nèi)容沒有掌握好，難以在等級考試中取得好成績。因此，必須引起我們足夠的重視，這部分因涉及四門課程知識，要求面廣。實(shí)際上只要掌握了一定的備考技巧過關(guān)也不難的。大綱的

3、二級基礎(chǔ)知識分為數(shù)據(jù)結(jié)構(gòu)與算法、程序設(shè)計基礎(chǔ)、軟件工基礎(chǔ)、數(shù)據(jù)庫設(shè)計基礎(chǔ)四部分，下面分別說一下學(xué)習(xí)重點(diǎn)和方法：（1） 數(shù)據(jù)結(jié)構(gòu)與算法本章的知識用于提高程序的效率以及對較復(fù)雜的問題進(jìn)行求解。本章內(nèi)容在計算機(jī)專業(yè)基礎(chǔ)課中也屬于比較難的一門，學(xué)習(xí)本章的內(nèi)容必須進(jìn)行理解，死記硬背是無效的。對于等級考試，本章重點(diǎn)的考核點(diǎn)主要在二叉樹，同時這也是本章的難點(diǎn)，考核形式主要為二叉樹的遍歷問題（如給圖求遍歷序列、給前序、中序遍歷求后序遍歷等）、二叉樹的結(jié)點(diǎn)問題（如給出一些條件然后求葉子結(jié)點(diǎn)個數(shù)）；還有排序和查找考試中也經(jīng)常會涉及到，排序主要以計算時間復(fù)雜度的形式考核，查找主要以計算最佳/最壞比較次數(shù)的方式考核。

4、其余的知識點(diǎn)主要以概念的形式考察，考生需要仔細(xì)看書并理解。（2） 程序設(shè)計基礎(chǔ)與軟件工程基礎(chǔ)這兩章以概述的形式簡介了規(guī)范化開發(fā)軟件的方法。與數(shù)據(jù)結(jié)構(gòu)不同，這兩章內(nèi)容主要是記憶性的知識點(diǎn)。程序設(shè)計基礎(chǔ)的內(nèi)容與大綱改革前添加了面向?qū)ο蟪绦蛟O(shè)計的內(nèi)容，考生可以對本章進(jìn)行幾次細(xì)讀后了解即可；軟件工程基礎(chǔ)這章主要考核內(nèi)容為結(jié)構(gòu)化分析及結(jié)構(gòu)化設(shè)計方法（即SA及SD，約占50%），信息量較大，其次是軟件測試（約占20%），考生需要將相關(guān)的概念及規(guī)則背誦，在以后有機(jī)會進(jìn)行程序開發(fā)時這些知識可以得到深刻理解。（3） 數(shù)據(jù)庫設(shè)計基礎(chǔ)數(shù)據(jù)庫是當(dāng)前軟件處理的信息核心，目前大部分軟件都是基于數(shù)據(jù)庫的，因此學(xué)習(xí)一下數(shù)據(jù)庫

5、知識對程序開發(fā)也是很有幫助的。本章主要的考核點(diǎn)是關(guān)系模型、關(guān)系代數(shù)及數(shù)據(jù)庫系統(tǒng)的基本概念，其余的知識點(diǎn)了解即可，其中數(shù)據(jù)庫的設(shè)計和管理可以結(jié)合著軟件工程來看，考生會發(fā)現(xiàn)這兩者有很多相似之處。除了關(guān)系代數(shù)會考一些簡單的計算問題外，其余的都是以概念題的形式考核，考生需要仔細(xì)的閱讀。以上為復(fù)習(xí)二級公共基礎(chǔ)的方法，順便提及一點(diǎn)考生在選購教材的時候應(yīng)當(dāng)特別注意，應(yīng)當(dāng)購買最近版的二級公共基礎(chǔ)知識教程（指定教材由高等教育出版社出版），還有考生在備考時，除了應(yīng)完成教材中的習(xí)題外還應(yīng)當(dāng)做一下近幾年的真題，并且用其估計一下自己的知識欠缺以便更好的進(jìn)行查漏補(bǔ)缺。 歷年公共基礎(chǔ)知識考點(diǎn)統(tǒng)計與分析章節(jié)知識點(diǎn)2012下2

6、012上2011下2011上2010下2010上2009下2009上2008下2008上2007下2007上2006下2006上2005下2005上數(shù)據(jù)結(jié)構(gòu)與算法算法220020420+22+2數(shù)據(jù)結(jié)構(gòu)的基本概念0200040002+22線性表及順序存儲0002+20000000棧和隊列4442+20200+4242線性鏈表00000000202樹與二叉樹20+2220+22+24+2204+20+2查找技術(shù)20020002002排序技術(shù)002022000+220程序設(shè)計基礎(chǔ)程序設(shè)計方法與風(fēng)格00000004000結(jié)構(gòu)化程序設(shè)計020+202000200面向?qū)ο蟪绦蛟O(shè)計0002020+200+

7、200+2軟件工程基礎(chǔ)軟件工程基本概念4+22+222+2602404+22結(jié)構(gòu)化分析方法20+20200+400000結(jié)構(gòu)化設(shè)計方法02202022022軟件測試00+22+20+20+20+22+200+202程序調(diào)試20000200+2220+2數(shù)據(jù)庫設(shè)計基礎(chǔ)數(shù)據(jù)庫的基本概念22+20+220+422+24+22+22+22數(shù)據(jù)模型2+222+22+222+2204+202+2關(guān)系代數(shù)22202022020數(shù)據(jù)庫設(shè)計與管理2020+20+2002020第一章數(shù)據(jù)結(jié)構(gòu)與算法1.1算法1、算法：是指解題方案的準(zhǔn)確而完整的描述。v 算法不等于程序，也不等于計算機(jī)方法，程序的編制不可能優(yōu)于算法的

8、設(shè)計。2、算法的基本特征（1）可行性；針對實(shí)際問題而設(shè)計的算法，執(zhí)行后能夠得到滿意的結(jié)果。（2）確定性，算法中每一步驟都必須有明確定義，不允許有模棱兩可的解釋，不允許有多義性；（3）有窮性，算法必須能在有限的時間內(nèi)做完，取能在執(zhí)行有限個步驟后終止，包括合理的執(zhí)行時間的含義；（4）擁有足夠的情報。v 綜上所述，所謂算法就是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，每一個規(guī)則都是有效的，是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。3、算法復(fù)雜度主要包括算法時間復(fù)雜度和算法空間復(fù)雜度。（1）算法時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量?？梢杂脠?zhí)行算法的過程中所需基本運(yùn)算的執(zhí)行次數(shù)來度量。（2）算法空間復(fù)雜度是指執(zhí)行這

9、個算法所需要的內(nèi)存空間?！菊骖}練習(xí)】（2011年9月）下列敘述中正確的是( )。A.算法就是程序B.設(shè)計算法時只需要考慮數(shù)據(jù)結(jié)構(gòu)的設(shè)計C.設(shè)計算法時只需要考慮結(jié)果的可靠性D.以上三種說法都不對（2010年3月）算法的時間復(fù)雜度是指( )。A）算法的執(zhí)行時間 B）算法所處理的數(shù)據(jù)量C）算法程序中的語句或指令條數(shù) D）算法在執(zhí)行過程中所需要的基本運(yùn)算次數(shù)（2009年9月）算法的空間復(fù)雜度是指( )。A）算法在執(zhí)行過程中所需要的計算機(jī)存儲空間 B）算法所處理的數(shù)據(jù)量C）算法程序中的語句或指令條數(shù) D）算法在執(zhí)行過程中所需要的臨時工作單元數(shù)（2007年4月）下列敘述中正確的是（ ）。A）算法的效率只與

10、問題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)B）算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量C）數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是一一對應(yīng)的D）算法的時間復(fù)雜度與空間復(fù)雜度一定相關(guān)（2008年3月）算法的有窮性是指( )。 A）算法程序的運(yùn)行時間是有限的 B）算法程序所處理的數(shù)據(jù)量是有限的 C）算法程序的長度是有限的 D）算法只能被有限的用戶使用（2007年4月）在算法中，對需要執(zhí)行的每一步操作，必須給出清楚、嚴(yán)格的規(guī)定。這屬于算法的（ ）。A）正當(dāng)性 B）可行性 C）確定性 D）有窮性（2006年9月）下列敘述中正確的是（ ）。A）一個算法的空間復(fù)雜度大，則其時間復(fù)雜度也必定大B）一個算法的空間復(fù)雜度大

11、，則其時間復(fù)雜度必定小C）一個算法的時間復(fù)雜度大，則其空間復(fù)雜度必定小D）上述三種說法都不對（2005年9月）算法復(fù)雜度主要包括時間復(fù)雜度和【2】復(fù)雜度。（2005年4月）算法具有5 個特性，下列選項中不屬于算法特性的是（ ）。A）有窮性 B）簡潔性 C）可行性 D）確定性（2005年4月）問題處理方案正確而完整的描述稱為【5】。1.2數(shù)據(jù)結(jié)構(gòu)的基本概念1、數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。2、數(shù)據(jù)結(jié)構(gòu)研究的三個方面：數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、運(yùn)算。（1）數(shù)據(jù)集合中和數(shù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)的邏輯結(jié)構(gòu)包含：1）表示數(shù)據(jù)元素的信息；2）表示各數(shù)據(jù)元素之間的前后件關(guān)

12、系。（2）在對數(shù)據(jù)進(jìn)行處理時，各數(shù)據(jù)元素在計算機(jī)中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)；數(shù)據(jù)的存儲結(jié)構(gòu)有順序、鏈接、索引等。1）順序存儲。它是把邏輯上相鄰的結(jié)點(diǎn)存儲在物理位置相鄰的存儲單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。2）鏈接存儲。它不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲表示稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)。3）索引存儲：除建立存儲結(jié)點(diǎn)信息外，還建立附加的索引表來標(biāo)識結(jié)點(diǎn)的地址。（3）對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。v 數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系，數(shù)據(jù)的存儲結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）是數(shù)據(jù)的邏輯結(jié)

13、構(gòu)在計算機(jī)存儲空間中的存放形式。同一種邏輯結(jié)構(gòu)的數(shù)據(jù)可以采用不同的存儲結(jié)構(gòu)，但影響數(shù)據(jù)處理效率。3、數(shù)據(jù)結(jié)構(gòu)的圖形表示一個數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外，還可以直觀地用圖形表示。在數(shù)據(jù)結(jié)構(gòu)的圖形表示中，對于數(shù)據(jù)集合D中的每一個數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示，一般稱之為數(shù)據(jù)結(jié)點(diǎn)，并簡稱為結(jié)點(diǎn)；為了進(jìn)一步表示各數(shù)據(jù)元素之間的前后件關(guān)系，對于關(guān)系R中的每一個二元組，用一條有向線段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)。4、數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。（1）線性結(jié)構(gòu)（非空的數(shù)據(jù)結(jié)構(gòu)）條件：1）有且只有一個根結(jié)點(diǎn)；2）每一個結(jié)點(diǎn)最多有一個前件，也最多有一個后件。 v 常見的線性結(jié)構(gòu)有線性表、棧、隊列和

14、線性鏈表等。（2）非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。v 常見的非線性結(jié)構(gòu)有樹、二叉樹和圖等?！菊骖}練習(xí)】(2011年9月)數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)與非線性結(jié)構(gòu)，帶鏈的棧屬于 【1】 (2009年9月)下列數(shù)據(jù)結(jié)構(gòu)中，屬于非線性結(jié)構(gòu)的是（ ）。A）循環(huán)隊列 B) 帶鏈隊列 C) 二叉樹 D）帶鏈棧(2007年9月)下列敘述中正確的是（ ）。A）程序執(zhí)行的效率與數(shù)據(jù)的存儲結(jié)構(gòu)密切相關(guān)B）程序執(zhí)行的效率只取決于程序的控制結(jié)構(gòu)C）程序執(zhí)行的效率只取決于所處理的數(shù)據(jù)量D）以上三種說法都不對(2007年9月)下列敘述中正確的是（ ）。A）數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)必定是一一對應(yīng)的B）由于計算機(jī)存儲空間是

15、向量式的存儲結(jié)構(gòu)，因此，數(shù)據(jù)的存儲結(jié)構(gòu)一定是線性結(jié)構(gòu)C）程序設(shè)計語言中的數(shù)組一般是順序存儲結(jié)構(gòu)，因此，利用數(shù)組只能處理線線結(jié)構(gòu)D）以上三種說法都不對（2005年9月）下列敘述中正確的是（ ）。A）一個邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲結(jié)構(gòu)B）數(shù)據(jù)的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，存儲結(jié)構(gòu)屬于非線性結(jié)構(gòu)C）一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)不影響數(shù)據(jù)處理的效率D）一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)影響數(shù)據(jù)處理的效率（2005年9月）數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，循環(huán)隊列屬于【5】結(jié)構(gòu)。（2005年4月）數(shù)據(jù)的存儲結(jié)構(gòu)是指（ ）。A）存儲在外存中的數(shù)據(jù) B）數(shù)據(jù)所占的存儲空間量C）

16、數(shù)據(jù)在計算機(jī)中的順序存儲方式 D）數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的表示1.3線性表及其順序存儲結(jié)構(gòu)1、線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號，元素之間的相對位置是線性的。線性表是由n(n0)個數(shù)據(jù)元素組成的一個有限序列。在復(fù)雜線性表中，由若干數(shù)據(jù)元素組成的數(shù)據(jù)元素稱為記錄，而由多個記錄構(gòu)成的線性表又稱為文件。非空線性表的結(jié)構(gòu)特征：（1）且只有一個根結(jié)點(diǎn)a ，它無前件；（2）有且只有一個終端點(diǎn)a ，它無后件；（3）除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個前件，也有且只有一個后件。結(jié)點(diǎn)個數(shù)n稱為線性表的長度，當(dāng)n=0時，稱為空表。2、線性表的順序儲結(jié)構(gòu)具有以下兩個基本特點(diǎn)：（1

17、）線性表中所有元素的所占的存儲空間是連續(xù)的；（2）線性表中各數(shù)元素在存儲空間中是按邏輯順序依次存放的。a 的存儲地址為：ADR（a ）=ADR(a )+（i-1）k，ADR（a ）為第一個元素的地址，k代表每個元素占的字節(jié)數(shù)。v 由此可以看出，在線性表的順序存儲結(jié)構(gòu)中，其前后件兩個元素在存儲空間中是緊鄰的，且前件元素一定存儲在后件元素的前面，可以通過計算機(jī)直接確定第i個結(jié)點(diǎn)的存儲地址。3、順序表的運(yùn)算：插入、刪除。（1）順序表的插入運(yùn)算：在一般情況下，要在第i（1in）個元素之前插入一個新元素時，首先要從最后一個（即第n個）元素開始，直到第i個元素之間共n-i+1個元素依次向后移動一個位置，移

18、動結(jié)束后，第i個位置就被空出，然后將新元素插入到第i項。插入結(jié)束后，線性表的長度就增加了1。v 順性表的插入運(yùn)算時需要移動元素，在等概率情況下，平均需要移動n/2個元素。（2）順序表的刪除運(yùn)算：在一般情況下，要刪除第i（1in）個元素時，則要從第i+1個元素開始，直到第n個元素之間共n-i個元素依次向前移動一個位置。刪除結(jié)束后，線性表的長度就減小了1。v 進(jìn)行順性表的刪除運(yùn)算時也需要移動元素，在等概率情況下，平均需要移動（n-1）/2個元素。插入、刪除運(yùn)算不方便?！菊骖}練習(xí)】（2012年3月）將長度為n的順序存儲在線性表中刪除一個元素，最壞情況下需要移動表中的元素個數(shù)為（ ）。（2011年9月

19、）在長度為n的順序存儲的線性表中插入一個元素，最壞情況下需要移動表中 【2】 .（2008年9月）下列敘述中正確的是（ ）。A）順序存儲結(jié)構(gòu)的存儲一定是連續(xù)的，鏈?zhǔn)酱鎯Y(jié)構(gòu)的存儲空間不一定是連續(xù)的B）順序存儲結(jié)構(gòu)只針對線性結(jié)構(gòu)，鏈?zhǔn)酱鎯Y(jié)構(gòu)只針對非線性結(jié)構(gòu)C）順序存儲結(jié)構(gòu)能存儲有序表，鏈?zhǔn)酱鎯Y(jié)構(gòu)不能存儲有序表D）鏈?zhǔn)酱鎯Y(jié)構(gòu)比順序存儲結(jié)構(gòu)節(jié)省存儲空間（2008年9月）線性表的存儲結(jié)構(gòu)主要分為順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu).隊列是一種特殊的線性表,循環(huán)隊列是隊列的3存儲結(jié)構(gòu)1.4棧和隊列1、棧及其基本運(yùn)算（1）棧是限定在一端進(jìn)行插入與刪除的線性表，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另

20、一端稱為棧底。棧按照“先進(jìn)后出”（FILO）或“后進(jìn)先出”（LIFO）組織數(shù)據(jù)，棧具有記憶作用。用top表示棧頂位置，用bottom表示棧底。（2）棧的基本運(yùn)算：1）插入元素稱為入棧運(yùn)算；2）刪除元素稱為退棧運(yùn)算；3）讀棧頂元素是將棧頂元素給一個指定的變量，此時指針無變化。棧的存儲方式和線性表類似，也有兩種，即順序棧和鏈?zhǔn)綏！?、隊列及其基本運(yùn)算(1)隊列是指允許在一端（隊尾）進(jìn)入插入，而在另一端（隊頭）進(jìn)行刪除的線性表。Rear指針指向隊尾，front指針指向隊頭。隊列是“先進(jìn)先出”（FIFO）或“后進(jìn)后出”（LILO）的線性表。(2)隊列運(yùn)算包括1）入隊運(yùn)算：從隊尾插入一個元素；2）退隊運(yùn)

21、算：從隊頭刪除一個元素。(3) 循環(huán)隊列及其運(yùn)算：所謂循環(huán)隊列，就是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間，供隊列循環(huán)使用。在循環(huán)隊列中，用隊尾指針rear指向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置，因此，從頭指針front指向的后一個位置直到隊尾指針rear指向的位置之間，所有的元素均為隊列中的元素。v 循環(huán)隊列是隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)，循環(huán)隊列中元素的個數(shù)=rear-front。【真題練習(xí)】（2012年3月）下列敘述中正確的是：A、循環(huán)隊列是隊列的一種順序存儲結(jié)構(gòu) B、循環(huán)隊列是隊列的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)C、循環(huán)隊列是非線性結(jié)構(gòu) D、循環(huán)隊列是一直

22、邏輯結(jié)構(gòu)（2012年3月）下列敘述中正確的是A、棧是一種先進(jìn)先出的線性表 B、隊列是一種后進(jìn)先出的線性表C、棧和隊列都是非線性結(jié)構(gòu) D、以上三種說法都不對（2012年3月）設(shè)循環(huán)隊列的存儲空間為Q(1:3),初始狀態(tài)為front=rear=30?，F(xiàn)經(jīng)過一系列入隊與退隊運(yùn)算后，front=16，rear=15，則循環(huán)隊列中有（ ）個元素。（2010年3月）一個隊列的初始狀態(tài)為空?，F(xiàn)將元素A，B，C，D，E，F(xiàn)，5，4，3，2，1依次入隊，然后再依次退隊，則元素退隊的順序為【】。（2010年3月）設(shè)某循環(huán)隊列的容量為50，如果頭指針front45（指向隊頭元素的前一位置），尾指針rear10（指向

23、隊尾元素），則該循環(huán)隊列中共有【】個元素。（2009年9月）下列數(shù)據(jù)結(jié)果中，能夠按照“先進(jìn)后出”原則存取數(shù)據(jù)的是（ ）。A) 循環(huán)隊列 B) 棧 C)隊列 D)二叉樹（2009年9月）對于循環(huán)隊列，下列敘述中正確的是（ ）。A）隊頭指針是固定不變的 B）隊頭指針一定大于隊尾指針C）隊頭指針一定小于隊尾指針 D）隊頭指針可以大于隊尾指針，也可以小于隊尾指針（2009年3月）下列敘述中正確的是（ ）。A）棧是“先進(jìn)先出”的線性表 B）隊列是“先進(jìn)先出”的線性表C）循環(huán)隊列是非線性結(jié)構(gòu)D）有序性表既可以采用順序存儲結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)（2009年3月）支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是（ ）。A）棧

24、 B）樹 C）隊列 D）二叉樹（2009年3月）假設(shè)一個長度為50的數(shù)組（數(shù)組元素的下標(biāo)從0到49）作為棧的存儲空間，棧底指針bottom指向棧底元素，棧頂指針top指向棧頂元素，如果bottom=49，top=30（數(shù)組下標(biāo)），則棧中具有【1】個元素。（2008年9月）一個棧的初始狀態(tài)為空?，F(xiàn)將元素1、2、3、4、5、A、B、C、D、E 依次入棧，然后再依次出棧，則元素出棧的順序是（ ）。A）12345ABCDE B）EDCBA54321 C）ABCDE12345 D）54321EDCBA（2008年9月）下列敘述中正確的是（ ）。A）循環(huán)隊列有隊頭和隊尾兩個指針，因此，循環(huán)隊列是非線性結(jié)構(gòu)

25、B）在循環(huán)隊列中，只需要隊頭指針就能反映隊列中元素的動態(tài)變化情況C）在循環(huán)隊列中，只需要隊尾指針就能反映隊列中元素的動態(tài)變化情況D）循環(huán)隊列中元素的個數(shù)是由隊頭指針和隊尾指針共同決定（2008年3月）下列關(guān)于棧的敘述正確的是（ ）。 A）棧按“先進(jìn)先出”組織數(shù)據(jù) B)棧按“先進(jìn)后出”組織數(shù)據(jù) C）只能在棧底插入數(shù)據(jù) D）不能刪除數(shù)據(jù)（2008年3月）設(shè)某循環(huán)隊列的容量為50，頭指針front=5（指向隊頭元素的前一位置），尾指針rear=29（指向隊尾元素），則該循環(huán)隊列中共有【3】個元素。（2007年4月）下列對隊列的敘述正確的是（ ）。A）隊列屬于非線性表 B）隊列按“先進(jìn)后出”原則組織數(shù)

26、據(jù)C）隊列在隊尾刪除數(shù)據(jù) D）隊列按“先進(jìn)先出”原則組織數(shù)據(jù)（2006年9月）按“后進(jìn)后出”原則組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是 4。（2006年9月）數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，帶鏈的隊列屬于 5 。（2006年4月）按照“后進(jìn)先出”原則組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是（ ）。A）隊列 B）棧 C）雙向鏈表 D）二叉樹（2005年9月）下列數(shù)據(jù)結(jié)構(gòu)中，能用二分法進(jìn)行查找的是（ ）。A）順序存儲的有序線性表 B）線性鏈表 C）二叉鏈表 D）有序線性鏈表（2005年9月）下列關(guān)于棧的描述正確的是（ ）。A）在棧中只能插入元素而不能刪除元素 B）在棧中只能刪除元素而不能插入元素C）棧是特殊的線性表，只能在一端插入或

27、刪除元素D）棧是特殊的線性表，只能在一端插入元素，而在另一端刪除元素（2005年4月）下列關(guān)于棧的描述中錯誤的是（ ）。A）棧是先進(jìn)后出的線性表 B）棧只能順序存儲 C）棧具有記憶作用D）對棧的插入與刪除操作中，不需要改變棧底指針1.5線性鏈表1、線性表順序存儲的缺點(diǎn)：（1）插入或刪除的運(yùn)算效率很低。在順序存儲的線性表中，插入或刪除數(shù)據(jù)元素時需要移動大量的數(shù)據(jù)元素；（2）線性表的順序存儲結(jié)構(gòu)下，線性表的存儲空間不便于擴(kuò)充；（3）線性表的順序存儲結(jié)構(gòu)不便于對存儲空間的動態(tài)分配。2、線性鏈表：線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表，是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈

28、表中的指針鏈接來實(shí)現(xiàn)的。數(shù)據(jù)結(jié)構(gòu)中的每一個結(jié)點(diǎn)對應(yīng)于一個存儲單元，這種存儲單元稱為存儲結(jié)點(diǎn)，簡稱結(jié)點(diǎn)。結(jié)點(diǎn)由兩部分組成：（1）用于存儲據(jù)元素值，稱為數(shù)據(jù)域；（2）用于存放指針，稱為指針域，用于指向前一個或后一個結(jié)點(diǎn)。在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。鏈?zhǔn)酱鎯Ψ绞郊纯捎糜诒硎揪€性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。線性鏈表分為單鏈表、雙向鏈表和循環(huán)鏈表三種類型。在單鏈表中，每一個結(jié)點(diǎn)只有一個指針域，由這個指針只能找到其后件結(jié)點(diǎn)，而不能找到其前件結(jié)點(diǎn)。因此，在某些應(yīng)用中，對于線性鏈表中的

29、每個結(jié)點(diǎn)設(shè)置兩個指針，一個稱為左指針，指向其前件結(jié)點(diǎn)；另一個稱為右指針，指向其后件結(jié)點(diǎn)，這種鏈表稱為雙向鏈表。線性鏈表，HEAD稱為頭指針，HEAD=NULL（或0）稱為空表，如果是兩指針：左指針（Llink）指向前件結(jié)點(diǎn)，右指針（Rlink）指向后件結(jié)點(diǎn)。3、線性鏈表的基本運(yùn)算：查找、插入、刪除。（1）在線性鏈表中包含指定元素的結(jié)點(diǎn)之前插入一個新元素。v 在線性鏈表中插入元素時，不需要移動數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點(diǎn)指針即可，也不會出現(xiàn)“上溢”現(xiàn)象。（2）在線性鏈表中刪除包含指定元素的結(jié)點(diǎn)。v 在線性鏈表中刪除元素時，也不需要移動數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點(diǎn)指針即可。（3）將兩個線性鏈表按要

30、求合并成一個線性鏈表。（4）將一個線性鏈表按要求進(jìn)行分解。（5）逆轉(zhuǎn)線性鏈表。（6）復(fù)制線性鏈表。（7）線性鏈表的排序。（8）線性鏈表的查找。v 線性鏈表不能隨機(jī)存取。4、循環(huán)鏈表及其基本運(yùn)算：在線性鏈表中，其插入與刪除的運(yùn)算雖然比較方便，但還存在一個問題，在運(yùn)算過程中對于空表和對第一個結(jié)點(diǎn)的處理必須單獨(dú)考慮，使空表與非空表的運(yùn)算不統(tǒng)一。為了克服線性鏈表的這個缺點(diǎn)，可以采用另一種鏈接方式，即循環(huán)鏈表。與前面所討論的線性鏈表相比，循環(huán)鏈表具有以下兩個特點(diǎn)：1）在鏈表中增加了一個表頭結(jié)點(diǎn)，其數(shù)據(jù)域為任意或者根據(jù)需要來設(shè)置，指針域指向線性表的第一個元素的結(jié)點(diǎn)，而循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)；2）循環(huán)

31、鏈表中最后一個結(jié)點(diǎn)的指針域不是空，而是指向表頭結(jié)點(diǎn)。即在循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)成了一個環(huán)狀鏈。循環(huán)鏈表的優(yōu)點(diǎn)主要體現(xiàn)在兩個方面：一是在循環(huán)鏈表中，只要指出表中任何一個結(jié)點(diǎn)的位置，就可以從它出發(fā)訪問到表中其他所有的結(jié)點(diǎn)，而線性單鏈表做不到這一點(diǎn)；二是由于在循環(huán)鏈表中設(shè)置了一個表頭結(jié)點(diǎn)，在任何情況下，循環(huán)鏈表中至少有一個結(jié)點(diǎn)存在，從而使空表與非空表的運(yùn)算統(tǒng)一。v 循環(huán)鏈表是在單鏈表的基礎(chǔ)上增加了一個表頭結(jié)點(diǎn)，其插入和刪除運(yùn)算與單鏈表相同。但它可以從任一結(jié)點(diǎn)出發(fā)來訪問表中其他所有結(jié)點(diǎn)，并實(shí)現(xiàn)空表與非空表的運(yùn)算的統(tǒng)一?！菊骖}練習(xí)】（2011年9月）下列關(guān)于線性鏈表的敘述中，正確的是（ ）。A）各

32、數(shù)據(jù)結(jié)點(diǎn)的存儲空間可以不連續(xù)，但它們的存儲順序與邏輯順序必須一致B）各數(shù)據(jù)結(jié)點(diǎn)的存儲順序與邏輯順序可以不一致，但它們的存儲空間必須連續(xù)C）進(jìn)行插入與刪除時，不需要移動表中的元素D）以上三種說法都不對（2006年4月）下列敘述中正確的是（ ）。A）線性鏈表是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) B）棧與隊列是非線性結(jié)構(gòu)C）雙向鏈表是非線性結(jié)構(gòu) D）只有根結(jié)點(diǎn)的二叉樹是線性結(jié)構(gòu)（2005年4月）下列對于線性鏈表的描述中正確的是（ ）。A）存儲空間不一定是連續(xù)，且各元素的存儲順序是任意的B）存儲空間不一定是連續(xù)，且前件元素一定存儲在后件元素的前面C）存儲空間必須連續(xù)，且前件元素一定存儲在后件元素的前面D）存儲空間必

33、須連續(xù)，且各元素的存儲順序是任意的1.6樹與二叉樹1、樹的基本概念樹是一種簡單的非線性結(jié)構(gòu)，所有元素之間具有明顯的層次特性。在樹結(jié)構(gòu)中，每一個結(jié)點(diǎn)只有一個前件，稱為父結(jié)點(diǎn)，沒有前件的結(jié)點(diǎn)只有一個，稱為樹的根結(jié)點(diǎn)，簡稱樹的根。每一個結(jié)點(diǎn)可以有多個后件，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。在樹結(jié)構(gòu)中，一個結(jié)點(diǎn)所擁有的后件的個數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱為樹的度。樹的最大層次稱為樹的深度。(二叉樹的層數(shù))2、二叉樹及其基本性質(zhì)（1）什么是二叉樹二叉樹是一種很有用的非線性結(jié)構(gòu)，它具有以下兩個特點(diǎn)：1）非空二叉樹只有一個根結(jié)點(diǎn)；2）每一個結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹

34、與右子樹。v 根據(jù)二叉樹的概念可知，二叉樹的度可以為0（葉結(jié)點(diǎn)）、1（只有一棵子樹）或2（有2棵子樹）。（2）二叉樹的基本性質(zhì)：性質(zhì)1 在二叉樹的第k層上，最多有2k-1個結(jié)點(diǎn)；性質(zhì)2 深度為m的二叉樹最多有2 m-1個結(jié)點(diǎn)；性質(zhì)3 度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個；性質(zhì)4 具有n個結(jié)點(diǎn)的二叉樹，其深度至少為log2 n+1，其中l(wèi)og2 n表示取log2 n的整數(shù)部分；3、滿二叉樹與完全二叉樹滿二叉樹是指除最后一層外，每一層上的所有結(jié)點(diǎn)有兩個子結(jié)點(diǎn)，則k層上有2k-1 個結(jié)點(diǎn)，深度為m的滿二叉樹有2m -1個結(jié)點(diǎn)。v 根據(jù)完全二叉樹的定義可得出：度為1的結(jié)點(diǎn)的個數(shù)為0或1。

35、完全二叉樹是指除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上只缺少右邊的若干結(jié)點(diǎn)。性質(zhì)5 具有n個結(jié)點(diǎn)的完全二叉樹的深度為log2 n+1；性質(zhì)6 設(shè)完全二叉樹共有n個結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開始，按層序（每一層從左到右）用自然數(shù)1，2，n給結(jié)點(diǎn)進(jìn)行編號（k=1,2n），有以下結(jié)論：若k=1,則結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒有父結(jié)點(diǎn)；若k1,則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號為INT（k/2）；若2k n,則編號為k的結(jié)點(diǎn)左子編號為2k；否則該結(jié)點(diǎn)無左子結(jié)點(diǎn)（也無右子結(jié)點(diǎn)）；若2k+1 n,則編號為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號為2k+1；否則該結(jié)點(diǎn)無右子結(jié)點(diǎn)。4、二叉樹的存儲結(jié)構(gòu)在計算機(jī)中，二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。與

36、線性鏈表類似，用于存儲二叉樹中各元素的存儲結(jié)點(diǎn)也由兩部分組成：數(shù)據(jù)域和指針域。但在二叉樹中，由于每一個元素可以有兩個后件（即兩個子結(jié)點(diǎn)），因此，用于存儲二叉樹的存儲結(jié)點(diǎn)的指針域有兩個：一個用于指向該結(jié)點(diǎn)的左子結(jié)點(diǎn)的存儲地址，稱為左指針域；另一個用于指向該結(jié)點(diǎn)的右子結(jié)點(diǎn)的存儲地址，稱為右指針域。v 二叉樹存儲結(jié)構(gòu)采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，對于滿二叉樹與完全二叉樹可以按層序進(jìn)行順序存儲。5、二叉樹的遍歷：指不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn)。（1）前序遍歷（DLR），首先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹；（2）中序遍歷（LDR），首先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹；（3）后序遍歷（LRD

37、），首先遍歷左子樹，然后訪問遍歷右子樹，最后訪問根結(jié)點(diǎn)?！菊骖}練習(xí)】（2012年3月）一棵二叉樹共有25個節(jié)點(diǎn)，其中5個時子節(jié)點(diǎn)，那么度為1的節(jié)點(diǎn)數(shù)為（ ）。A、4 B、6 C、10 D、16（2011年9月）下列關(guān)于二叉樹的敘述中，正確的是（ ）。 A.葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)少一個B.葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個C.葉子結(jié)點(diǎn)數(shù)是度為2的結(jié)點(diǎn)數(shù)的兩倍D.度為2的結(jié)點(diǎn)數(shù)是度為1的結(jié)點(diǎn)數(shù)的兩倍（2011年9月）某系統(tǒng)總體結(jié)構(gòu)圖如下圖所示：該系統(tǒng)總體結(jié)構(gòu)圖的深度是 A.7B.6C.3D.2（2009年9月）在深度為7 的滿二叉樹中，度為2 的結(jié)點(diǎn)個數(shù)為【1】。（2010年3月）設(shè)二叉樹如下：

38、AB C D F E G H 對該二叉樹進(jìn)行后序遍歷的結(jié)果為【】。（2009年3月）某二叉樹有5個度為2的結(jié)點(diǎn)，則該二叉樹中的葉子結(jié)點(diǎn)數(shù)是（ ）。A）10 B）8 C）6 D）4（2008年9月）對下列二叉樹進(jìn)行中序遍歷的結(jié)果 【1】 。ABCDEFXYZY（2008年4月）深度為5的滿二叉樹有【2】個葉子結(jié)點(diǎn)。（2007年9月）一棵二叉樹中共有70個葉子結(jié)點(diǎn)與80個度為1的結(jié)點(diǎn)，則該二叉樹中的總結(jié)點(diǎn)數(shù)為（ ）。A）219 B）221 C）229 D）231（2007年9月）對下列二叉樹進(jìn)行中序遍歷的結(jié)果為4。FCEADBGHP（2007年4月）下列二叉樹進(jìn)行前序遍歷的結(jié)果為（ ）。ABCDE

39、FYXZA）DYBEAFCZX B）YDEBFZXCA C）ABDYECFXZ D）ABCDEFXYZ（2007年4月）某二叉樹中有n 個度為2 的結(jié)點(diǎn)，則該二叉樹中的葉子結(jié)點(diǎn)數(shù)為（ ）。A）n+1 B）n-1 C）2n D）n/2（2007年4月）在深度為7 的滿二叉樹中，度為2 的結(jié)點(diǎn)個數(shù)為【1】。（2006年9月）對下列二叉樹：ABDECF、G 進(jìn)行中序遍歷的結(jié)果是_。A）ACBDFEG B）ACBDFGE C）ABDCGEF D）FCADBEG（2005年9月）對如下二叉樹FEDBCA進(jìn)行后序遍歷的結(jié)果為（ ）。A）ABCDEF B）DBEAFC C）ABDECF D）DEBFCA（2

40、005年9月）在深度為7 的滿二叉樹中，葉子結(jié)點(diǎn)的個數(shù)為（ ）。A）32 B）31 C）64 D）63（2005年9月）一棵二叉樹第六層（根結(jié)點(diǎn)為第一層）的結(jié)點(diǎn)數(shù)最多為【4】個。（2005年4月）某二叉樹中度為2 的結(jié)點(diǎn)有18 個，則該二叉樹中有【1】個葉子結(jié)點(diǎn)。1.7查找技術(shù)查找：根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素。查找結(jié)果：（查找成功：找到；查找不成功：沒找到。）平均查找長度：查找過程中關(guān)鍵字和給定值比較的平均次數(shù)。1、順序查找基本思想：從表中的第一個元素開始，將給定的值與表中逐個元素的關(guān)鍵字進(jìn)行比較，直到兩者相符，查到所要找的元素為止。否則就是表中沒有要找的

41、元素，查找不成功。在平均情況下，利用順序查找法在線性表中查找一個元素，大約要與線性表中一半的元素進(jìn)行比較，最壞情況下需要比較n次。順序查找一個具有n個元素的線性表，其平均復(fù)雜度為O（n）。下列兩種情況下只能采用順序查找：1）如果線性表是無序表（即表中的元素是無序的），則不管是順序存儲結(jié)構(gòu)還是鏈?zhǔn)酱鎯Y(jié)構(gòu)，都只能用順序查找。2）即使是有序線性表，如果采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，也只能用順序查找。2、二分法查找思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認(rèn)找不到該記錄為止。前提：必須在具有順序存儲結(jié)構(gòu)的有序表中進(jìn)行。查找過程：1）若中間項的值等于x，則說明已查到；2）若x小于中間項的值，

42、則在線性表的前半部分查找；3）若x大于中間項的值，則在線性表的后半部分查找。特點(diǎn)：比順序查找方法效率高。最壞的情況下，需要比較log2n次。v 二分法查找只適用于順序存儲的線性表，且表中元素必須按關(guān)鍵字有序（升序，但允許相鄰元素值相等）排列。對于無序線性表和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)只能用順序查找。在長度為n的有序線性表中進(jìn)行二分法查找，其時間復(fù)雜度為O（log2n）。【真題練習(xí)】（2010年3月）下列敘述中正確的是_。A）對長度為的有序鏈表進(jìn)行查找，最壞情況下需要的比較次數(shù)為B）對長度為的有序鏈表進(jìn)行對分查找，最壞情況下需要的比較次數(shù)為（n/2）C）對長度為的有序鏈表進(jìn)行對分查找，最壞情況下需要的

43、比較次數(shù)為（log2n）D）對長度為的有序鏈表進(jìn)行對分查找，最壞情況下需要的比較次數(shù)為（log2n）（2008年9月）在長度為n 的有序線性表中進(jìn)行二分查找，最壞情況下需要比較的次數(shù)是（ ）。A）O(n) B）O(n2) C）O(log2n) D）O(nlog2n) （2006年9月）在長為64 的有序線性表中進(jìn)行順序查找，最壞情況下需要比較的次數(shù)為_。A）63 B）64 C）6 D）7（2005年4月）對于長度為n 的線性表進(jìn)行順序查找，在最壞情況下所需要的比較次數(shù)為（ ）。A）log2n B）n/2 C）n D）n+11.8排序技術(shù)排序是指將一個無序序列整理成按值的有序表，對于長度為n的有

44、序線性表，最壞情況只需比較n次。交換類排序法：（1）冒泡排序法，需要比較的次數(shù)為n(n-1)/2；（2）快速排序法。插入類排序法：（1）簡單插入排序法，最壞情況需要n(n-1)/2次比較；（2）希爾排序法，最壞情況需要O（n ）次比較。選擇類排序法：（1）簡單選擇排序法，最壞情況需要n(n-1)/2次比較；（2）堆排序法，最壞情況需要O（nlog n）次比較?！菊骖}練習(xí)】（2009年3月）下列排序方法中，最壞情況下比較次數(shù)最少的是_。A）冒泡排序 B）簡單選擇排序 C）直接插入排序 D）堆排序（2008年3月）對長度為n的線性表排序，在最壞情況下，比較次數(shù)不是n(n-1)/2的排序方法是（ ）

45、。 A）快速排序 B）冒泡排序 C）直接插入排序 D）堆排序（2007年9月）冒泡排序在最壞情況下的比較次數(shù)是（ ）。A）n（n+1）/2 B）nlog2n C）n（n-1）/2 D）n/2（2006年4月）對長度為10 的線性表進(jìn)行冒泡排序，最壞情況下需要比較的次數(shù)為 【1】 。（2005年9月）對于長度為n 的線性表，在最壞情況下，下列各排序法所對應(yīng)的比較次數(shù)中正確的是（ ）。A）冒泡排序n/2 B）冒泡排序為n C）快速排序為n D）快速排序為n(n-1)/2本章應(yīng)考點(diǎn)撥：本章內(nèi)容在筆試中會出現(xiàn)5-6個題目，是公共基礎(chǔ)知識部分出題量比較多的一章，所占分值也比較大，約10分。第二章 程序設(shè)

46、計基礎(chǔ)2.1程序設(shè)計設(shè)計方法和風(fēng)格程序設(shè)計的風(fēng)格主要強(qiáng)調(diào)：“清晰第一，效率第二”。主要應(yīng)注重和考慮下述一些因素：（1）源程序文檔化1）符號名的命名。符號名能反映它所代表的實(shí)際東西，應(yīng)有一定的實(shí)際含義。2）程序的注釋。分為序言性注釋和功能性注釋。序言性注釋：位于程序開頭部分，包括程序標(biāo)題、程序功能說明、主要算法、接口說明、程序位置、開發(fā)簡歷、程序設(shè)計者、復(fù)審者、復(fù)審日期及修改日期等。功能性注釋：嵌在源程序體之中，用于描述其后的語句或程序的主要功能。3）視覺組織。利用空格、空行、縮進(jìn)等技巧使程序?qū)哟吻逦?。?）數(shù)據(jù)說明 1）數(shù)據(jù)說明的次序規(guī)范化；2）說明語句中變量安排有序化；3）使用注釋來說明復(fù)雜

47、數(shù)據(jù)的結(jié)構(gòu)。（3）語句的結(jié)構(gòu)。1）在一行內(nèi)只寫一條語句；2）程序編寫應(yīng)優(yōu)先考慮清晰性；3）程序編寫要做到清晰第一，效率第二；4）在保證程序正確的基礎(chǔ)上再要求提高效率；5）避免使用臨時變量而使程序的可讀性下降；6）避免不必要的轉(zhuǎn)移；7）盡量使用庫函數(shù)；8）避免采用復(fù)雜的條件語句；9）盡量減少使用“否定”條件語句；10）數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡化；11）要模塊化，使模塊功能盡可能單一化；12）利用信息隱蔽，確保每一個模塊的獨(dú)立性；13）從數(shù)據(jù)出發(fā)去構(gòu)造程序；14）不要修補(bǔ)不好的程序，要重新編寫。（4）輸入和輸出。1）對輸入數(shù)據(jù)檢驗數(shù)據(jù)的合法性；2）檢查輸入項的各種重要組合的合法性；3）輸入格式要簡

48、單，使得輸入的步驟和操作盡可能簡單；4）輸入數(shù)據(jù)時，應(yīng)允許使用自由格式；5）應(yīng)允許缺省值；6）輸入一批數(shù)據(jù)時，最好使用輸入結(jié)束標(biāo)志；7）在以交互式輸入/輸出方式進(jìn)行輸入時，要在屏幕上使用提示符明確提示輸入的請求，同時在數(shù)據(jù)輸入過程中和輸入結(jié)束時，應(yīng)在屏幕上給出狀態(tài)信息；8）當(dāng)程序設(shè)計語言對輸入格式有嚴(yán)格要求時，應(yīng)保持輸入格式與輸入語句的一致性；給所有的輸出加注釋，并設(shè)計輸出報表格式?！菊骖}練習(xí)】（2011年9月）常見的軟件開發(fā)方法有結(jié)構(gòu)化方法和面向?qū)ο蠓椒?，對某?yīng)用系統(tǒng)經(jīng)過需求分析建立數(shù)據(jù)流圖（DFD），則應(yīng)采用 【3】 方法。（2007年9月）下列敘述中，不符合良好程序設(shè)計風(fēng)格的是（ ）。A

49、）程序的效率第一，清晰第二 B）程序的可讀性好C）程序中有必要的注釋 D）輸入數(shù)據(jù)前要有提示信息（2007年9月）下列選項中不符合良好程序設(shè)計風(fēng)格的是（ ）。A）源程序要文檔化 B）數(shù)據(jù)說明的次序要規(guī)范化C）避免濫用goto 語句 D）模塊設(shè)計要保證高耦合、高內(nèi)聚（2006年9月）下列選項中不符合良好程序設(shè)計風(fēng)格的是_。A）源程序要文檔化 B）數(shù)據(jù)說明的次序要規(guī)范化 C）避免濫用goto語句 D）模塊設(shè)計要保證高耦合，高內(nèi)聚（2006年9月）以下敘述中正確的是_。A）程序設(shè)計的任務(wù)就是編寫程序代碼并上機(jī)調(diào)試B）程序設(shè)計的任務(wù)就是確定所用數(shù)據(jù)結(jié)構(gòu)C）程序設(shè)計的任務(wù)就是確定所用算法D）以上三種說法

50、都不完整2.2結(jié)構(gòu)化程序設(shè)計（面向過程的程序設(shè)計方法）1、結(jié)構(gòu)化程序設(shè)計方法的四條原則是：1、自頂向下；2、逐步求精；3、模塊化； 4、限制使用goto語句。（1）自頂向下。程序設(shè)計時，應(yīng)先考慮總體，后考慮細(xì)節(jié)；先考慮全局目標(biāo)，后考慮局部目標(biāo)。不要一開始就過多追求眾多的細(xì)節(jié)，先從最上層總目標(biāo)開始設(shè)計，逐步使問題具體化。（2）逐步求精。對復(fù)雜問題，應(yīng)設(shè)計一些子目標(biāo)作過渡，逐步細(xì)化。（3）模塊化。一個復(fù)雜問題，肯定是由若干稍簡單的問題構(gòu)成。模塊化是把程序要解決的總目標(biāo)分解為分目標(biāo)，再進(jìn)一步分解為具體的小目標(biāo)，把每個小目標(biāo)稱為一個模塊。（4）限制使用goto語句。2、結(jié)構(gòu)化程序的基本結(jié)構(gòu)：順序結(jié)構(gòu)，

51、選擇結(jié)構(gòu)，重復(fù)結(jié)構(gòu)。（1）順序結(jié)構(gòu)：一種簡單的程序設(shè)計，即按照程序語句行的自然順序，一條語句一條語句地執(zhí)行程序，它是最基本、最常用的結(jié)構(gòu)；（2）選擇結(jié)構(gòu)：又稱分支結(jié)構(gòu)，包括簡單選擇和多分支選擇結(jié)構(gòu)，可根據(jù)條件，判斷應(yīng)該選擇哪一條分支來執(zhí)行相應(yīng)的語句序列；（3）重復(fù)結(jié)構(gòu)：又稱循環(huán)結(jié)構(gòu)，可根據(jù)給定條件，判斷是否需要重復(fù)執(zhí)行某一相同程序段。僅僅使用順序、選擇和循環(huán)三種基本控制結(jié)構(gòu)就足以表達(dá)各種其他形式結(jié)構(gòu)，從而實(shí)現(xiàn)任何單入口/單出口的程序?！菊骖}練習(xí)】（2009年9月）下列選項中不屬于結(jié)構(gòu)化程序設(shè)計原則的是（ ）。A) 可封裝 D) 自頂向下 C) 模塊化 D) 逐步求精（2009年3月）符合結(jié)構(gòu)化

52、原則的三種基本控制結(jié)構(gòu)是：選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)和【3】。（2008年4月）結(jié)構(gòu)化程序設(shè)計的基本原則不包括（ ）。 A）多態(tài)性 B）自頂向下 C）模塊化 D）逐步求精（2006年4月）下列選項中不屬于結(jié)構(gòu)化程序設(shè)計方法的是（ ）。A）自頂向下 B）逐步求精 C）模塊化 D）可復(fù)用2.3面向?qū)ο蟮某绦蛟O(shè)計面向?qū)ο蟮某绦蛟O(shè)計：以60年代末挪威奧斯陸大學(xué)和挪威計算機(jī)中心研制的simula語言為標(biāo)志?？陀^世界中任何一個事物都可以被看成是一個對象，面向?qū)ο蠓椒ǖ谋举|(zhì)就是主張從客觀世界固有的事物出發(fā)來構(gòu)造系統(tǒng)，提倡人們在現(xiàn)實(shí)生活中常用的思維來認(rèn)識、理解和描述客觀事物，強(qiáng)調(diào)最終建立的系統(tǒng)能夠映射問題域。也就是說，系統(tǒng)中的對象及對象之間的關(guān)系能夠如實(shí)地反映問題域中固有的事物及其關(guān)系。面向?qū)ο蠓椒ǖ膬?yōu)點(diǎn)：（1）與人類習(xí)慣的思維方法一致； （2）穩(wěn)定性好； （3）可重用性好； （4）易于開發(fā)大型軟件產(chǎn)品； （5）可維護(hù)性好。v 面向?qū)ο蟮某绦蛟O(shè)計主要考慮的是提高軟件的可重用性。對象是面向?qū)ο蠓椒ㄖ凶罨镜母拍?，可以用來表示客觀世界中的任何實(shí)體，對象是實(shí)體的抽象。面向?qū)ο蟮某绦蛟O(shè)計方法中的對象是系統(tǒng)中用來描述客觀事物的一個實(shí)體，是構(gòu)成系統(tǒng)的一個基本單位，由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。v 對象是屬性和方法的封裝體。屬性即對象包含的信息，操作描述了對象執(zhí)行的功能，操作也稱為方法或服