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

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

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

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

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

5、）算法的復(fù)雜度主要包括_復(fù)雜度和空間復(fù)雜度。 2005.4 （5）問(wèn)題處理方案的正確而完整的描述稱為_(kāi)。 2005.9 （2）算法復(fù)雜度主要包括時(shí)間復(fù)雜度和_復(fù)雜度。,11,算法的歷年考題,2006.9 （7）下列敘述中正確的是 A）一個(gè)算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度也必定大 B）一個(gè)算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度必定小 C）一個(gè)算法的時(shí)間復(fù)雜度大，則其空間復(fù)雜度必定小 D）上述三種說(shuō)法都不對(duì) 2007.4 （1）下列敘述中正確的是 A）算法的效率只與問(wèn)題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān) B）算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量 C）數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)是一一對(duì)應(yīng)的 D

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

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

8、放形式稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)） 常用的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等。 采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。,16,1.2.2 數(shù)據(jù)結(jié)構(gòu)的圖形表示,在數(shù)據(jù)結(jié)構(gòu)中，沒(méi)有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn)；沒(méi)有后件的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)（也稱為葉子結(jié)點(diǎn)），其他稱為內(nèi)部結(jié)點(diǎn)。,插入和刪除是對(duì)數(shù)據(jù)結(jié)構(gòu)的兩種基本運(yùn)算。此外對(duì)數(shù)據(jù)結(jié)構(gòu)的運(yùn)算還有查找、分類、合并、分解、復(fù)制和修改等。,17,1.2.3 線性結(jié)構(gòu)與非線性結(jié)構(gòu),線性結(jié)構(gòu)條件： 1）有且只有一個(gè)根結(jié)點(diǎn)； 2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。 3）在一個(gè)線性結(jié)構(gòu)中插入或刪除任何一個(gè)結(jié)點(diǎn)后還應(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）隊(duì)列 B）線性表 C）二叉樹 D）棧 （2）數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱為數(shù)據(jù)的_。 2005.4 （1）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指 A）存儲(chǔ)在外存中的數(shù)據(jù) B）數(shù)據(jù)所占的存儲(chǔ)空間量 C）數(shù)據(jù)在計(jì)算機(jī)中的順序存儲(chǔ)方式 D）數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示,19,NCRE考題,2005.9 （4）下列敘述中正確的是 A）一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲(chǔ)結(jié)構(gòu) B）數(shù)據(jù)的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)屬于非線性結(jié)構(gòu) C）一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)不影響數(shù)據(jù)處理的效率 D）

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

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

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