2011年2月二級公共基礎(chǔ)知識講義

1、1,內(nèi)部資料,2011年3月計算機等級考試 二級公共基礎(chǔ)知識培訓(xùn)講義 理工大樓915,2,二級Access考試介紹,一、考試方式1筆試：90 分鐘，滿分100 分，其中含公共基礎(chǔ)知識部分30分 2上機操作：90 分鐘，滿分100 分 二、筆試題型及分值（根據(jù)考試大綱及往年試題) 1選擇題70 分（每小題2分，共3 5題）2填空題30 分（每空2 分，共15題） 三、上機操作1基本操作（30 分）2簡單應(yīng)用（40 分）3綜合應(yīng)用（30 分）,3,我們的目標,通過二級考試,4,基礎(chǔ)知識部分：30分,設(shè)有10道選擇題和5道填空題,5,第一章 數(shù)據(jù)結(jié)構(gòu)與算法,1.1 算法 1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念

2、1.3 線性表及其順序存儲結(jié)構(gòu) 1.4 棧和隊列 1.5 線性鏈表 1.6 樹與二叉樹 1.7 查找技術(shù) 1.8 排序技術(shù),6,數(shù)據(jù)結(jié)構(gòu)與算法歷年試題分數(shù)分布,7,11 算法,1.1.1 算法的基本概念 算法：是指解題方案的準確而完整的描述。 算法不等于程序，也不等于計算機方法，程序的編制不可能優(yōu)于算法的設(shè)計。 算法的基本特征：是一組嚴謹?shù)囟x運算順序的規(guī)則，每一個規(guī)則都是有效的，是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。特征包括： （1） 可行性（effectiveness）：針對實際問題而設(shè)計的算法，執(zhí)行后能夠得到滿意的結(jié)果。 （2） 確定性（definiteness）：算法中的每一個步驟都必

3、須有明確的定義，不允許有模棱兩可的解釋和多義性。 （3） 有窮性（finiteness）：算法必須的有限時間內(nèi)做完，即算法必須能在執(zhí)行有限個步驟之后終止。 （4） 擁有足夠的情報：要使算法有效必須為算法提供足夠的情報。當算法擁有足夠的情報時，此算法才是有效的；當提供的情報不夠時，算法可能無效。 綜上所述，算法是一組嚴謹?shù)囟x運算順序的規(guī)則，并且每一個規(guī)則都是有效的，同時是明確的，此順序?qū)⒃谟邢薜拇螖?shù)后終止。,8,11 算法,2.算法的基本要素： 算法的基本要素：一是對數(shù)據(jù)對象的運算和操作；二是算法的控制結(jié)構(gòu)。 指令系統(tǒng)：一個計算機系統(tǒng)能執(zhí)行的所有指令的集合。 基本運算和操作包括：算術(shù)運算、邏輯

4、運算、關(guān)系運算、數(shù)據(jù)傳輸。 算法的控制結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。 算法基本設(shè)計方法：列舉法、歸納法、遞推、遞歸、減半遞推技術(shù)、回溯法。,9,1.1.2 算法復(fù)雜度,算法的復(fù)雜度主要包括時間復(fù)雜度和空間復(fù)雜度。 1.時間復(fù)雜度：指執(zhí)行算法所需要的計算工作量 或(算法在執(zhí)行過程中所需基本運算的執(zhí)行次數(shù)) 2. 空間復(fù)雜度：執(zhí)行這個算法所需要的內(nèi)存空間,10,算法的歷年考題,2004.9 （1）下面敘述正確的是 A）算法的執(zhí)行效率與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān) B）算法的空間復(fù)雜度是指算法程序中指令（或語句）的條數(shù) C）算法的有窮性是指算法必須能在執(zhí)行有限個步驟之后終止 D）以上三種描述都不對 （1

5、）算法的復(fù)雜度主要包括_復(fù)雜度和空間復(fù)雜度。 2005.4 （5）問題處理方案的正確而完整的描述稱為_。 2005.9 （2）算法復(fù)雜度主要包括時間復(fù)雜度和_復(fù)雜度。,11,算法的歷年考題,2006.9 （7）下列敘述中正確的是 A）一個算法的空間復(fù)雜度大，則其時間復(fù)雜度也必定大 B）一個算法的空間復(fù)雜度大，則其時間復(fù)雜度必定小 C）一個算法的時間復(fù)雜度大，則其空間復(fù)雜度必定小 D）上述三種說法都不對 2007.4 （1）下列敘述中正確的是 A）算法的效率只與問題的規(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

6、）算法的時間復(fù)雜度與空間復(fù)雜度一定相關(guān) 2008.4 （1）算法的有窮性是指 A)算法程序的運行時間是有限的 B) 算法程序所處理的數(shù)據(jù)量是有限的 C)算法程序的長度是有限的 D)算法只能被有限的用戶使用,12,1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念,利用計算機進行數(shù)據(jù)處理是計算機應(yīng)用的一個重要領(lǐng)域。在進行數(shù)據(jù)處理時，實現(xiàn)需要處理的數(shù)據(jù)元素一般很多，而這些大量的數(shù)據(jù)元素都需要存放在計算機中，因此，大量的數(shù)據(jù)元素在計算機中如何組織，以便提高數(shù)據(jù)處理的效率，并且節(jié)省計算機的存儲空間，這是進行數(shù)據(jù)處理的關(guān)鍵問題。,13,1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念,數(shù)據(jù)結(jié)構(gòu)作為計算機的一門學(xué)科，主要研究和討論以下三個方面的問題。

7、 （1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)； （2）在對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)； （3）對各種數(shù)據(jù)結(jié)構(gòu)進行的運算。,14,1.2.1 什么是數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。 更通俗地說，數(shù)據(jù)結(jié)構(gòu)是指帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。在此，所謂結(jié)構(gòu)實際上就是指數(shù)據(jù)元素之間的前后件關(guān)系。 由上所述，一個數(shù)據(jù)結(jié)構(gòu)應(yīng)包含以下兩方面的信息： 1）表示數(shù)據(jù)元素的信息； 2）表示各數(shù)據(jù)元素之間的前后件關(guān)系。,15,數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu),數(shù)據(jù)的邏輯結(jié)構(gòu)：是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。 數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存

8、放形式稱為數(shù)據(jù)的存儲結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)） 常用的存儲結(jié)構(gòu)有順序、鏈接、索引等。 采用不同的存儲結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。,16,1.2.2 數(shù)據(jù)結(jié)構(gòu)的圖形表示,在數(shù)據(jù)結(jié)構(gòu)中，沒有前件的結(jié)點稱為根結(jié)點；沒有后件的結(jié)點稱為終端結(jié)點（也稱為葉子結(jié)點），其他稱為內(nèi)部結(jié)點。,插入和刪除是對數(shù)據(jù)結(jié)構(gòu)的兩種基本運算。此外對數(shù)據(jù)結(jié)構(gòu)的運算還有查找、分類、合并、分解、復(fù)制和修改等。,17,1.2.3 線性結(jié)構(gòu)與非線性結(jié)構(gòu),線性結(jié)構(gòu)條件： 1）有且只有一個根結(jié)點； 2）每一個結(jié)點最多有一個前件，也最多有一個后件。 3）在一個線性結(jié)構(gòu)中插入或刪除任何一個結(jié)點后還應(yīng)該是線性結(jié)構(gòu)。 非線性結(jié)構(gòu)：不滿足線性結(jié)

9、構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。,18,NCRE考題,2004.9 （2）以下數(shù)據(jù)結(jié)構(gòu)中不屬于線性數(shù)據(jù)結(jié)構(gòu)的是 A）隊列 B）線性表 C）二叉樹 D）棧 （2）數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式稱為數(shù)據(jù)的_。 2005.4 （1）數(shù)據(jù)的存儲結(jié)構(gòu)是指 A）存儲在外存中的數(shù)據(jù) B）數(shù)據(jù)所占的存儲空間量 C）數(shù)據(jù)在計算機中的順序存儲方式 D）數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示,19,NCRE考題,2005.9 （4）下列敘述中正確的是 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）

10、一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)影響數(shù)據(jù)處理的效率 2007.9 （5）下列敘述中正確的是 A)程序執(zhí)行的效率與數(shù)據(jù)的存儲結(jié)構(gòu)密切相關(guān) B)程序執(zhí)行的效率只取決于程序的控制結(jié)構(gòu) C)程序執(zhí)行的效率只取決于所處理的數(shù)據(jù)量 D)以上三種說法都不對,20,1.3線性表及其順序存儲結(jié)構(gòu),1.3.1 線性表的基本概念 線性表是最簡單、最常用的一種數(shù)據(jù)結(jié)構(gòu) 線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號，元素之間的相對位置是線性的。 在復(fù)雜線性表中，由若干項數(shù)據(jù)元素組成的數(shù)據(jù)元素稱為記錄，而由多個記錄構(gòu)成的線性表又稱為文件。 非空線性表的結(jié)構(gòu)特征： （1）且只有一個根結(jié)點a1

11、，它無前件； （2）有且只有一個終端結(jié)點an，它無后件； （3）除根結(jié)點與終端結(jié)點外，其他所有結(jié)點有且只有一個前件，也有且只有一個后件。結(jié)點個數(shù)n稱為線性表的長度，當n=0時，稱為空表。,21,1.3.2 線性表的順序存儲結(jié)構(gòu),在計算機中存放線性表，一種最簡單的方法是順序存儲，也稱為順序分配。 線性表的順序存儲結(jié)構(gòu)具有以下兩個基本特點： 1）線性表中所有元素的所占的存儲空間是連續(xù)的； 2）線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。 ai的存儲地址為：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)為第一個元素的地址，k代表每個元素占的字節(jié)數(shù)。 例：一個矢量第一個元素的

12、存儲地址是100，每個元素的長度為2，則第5個元素的地址是 。,22,1.3.3 順序表的插入運算,在i的位置上插入x,23,1.3.4 順序表的刪除運算,（a）刪除ai前 （b）刪除ai后,24,這里省去260張ppt,25,寫在最后 二級考試公共知識部分考題特點及復(fù)習(xí)建議,考題特點 1涉及面廣，但難度小 考試中有關(guān)公共知識部分的題目共有15道，涉及算法及數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計基礎(chǔ)、軟件工程基礎(chǔ)和數(shù)據(jù)庫設(shè)計基礎(chǔ)等四門學(xué)科，但是從整體上分析，考核內(nèi)容的難度不大，考點也相對集中些。 2.考核重點為基本概念、基本方法和基本運算。 3.考試中涉及的題目都是基本概念、基本方法和基本運算，考核以概念和認識性內(nèi)容為主，理解性、應(yīng)用性內(nèi)容極少。,26,復(fù)習(xí)建議,考生的復(fù)習(xí)必須遵守：“80/20的原則” 二級考試的公共知識部分的覆蓋面廣，至少涵蓋了計算機應(yīng)用專業(yè)的四門核心課程：算法及數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計基礎(chǔ)、軟件工程基礎(chǔ)和數(shù)據(jù)庫。事實上，這些