2011二級公共基礎(chǔ)

2011年全國計(jì)算機(jī)等級考試二級公共基礎(chǔ)知識(shí)要點(diǎn)1.根基數(shù)據(jù)結(jié)構(gòu)與算法1.1算法算法：是指解題方案的切確而完整的描述。算法不等于軌范，也不等計(jì)較機(jī)體例，軌范的編制不成能優(yōu)于算法的設(shè)計(jì)。算法的根基特征：是一組嚴(yán)謹(jǐn)?shù)亟缏枾踪怂惆ご蔚能墑t，每一個(gè)軌則都是有用的，是明晰的，此挨次將在有限的次數(shù)下終止。特征搜羅：（1）可行性；（2）確定性，算法中每一軌范都必需有明晰界說，不充許有迷糊其詞的詮釋，不許可有多義性；（3）有窮性，算法必需能在有限的時(shí)刻內(nèi)做完，即能在執(zhí)行有限個(gè)軌范后終止，搜羅合理的執(zhí)行時(shí)刻的寄義；（4）擁有足夠的情報(bào)。算法的根基要素：一是對數(shù)據(jù)對象的運(yùn)算和操作；二是算法的節(jié)制結(jié)構(gòu)。指令系統(tǒng)：一個(gè)計(jì)較機(jī)系統(tǒng)能執(zhí)行的所有指令的集結(jié)。根基運(yùn)算和操作搜羅：算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)鮮ё偎算、數(shù)據(jù)傳輸。算法的節(jié)制結(jié)構(gòu)：挨次結(jié)構(gòu)、選擇結(jié)構(gòu)、輪回結(jié)構(gòu)。算法根基設(shè)計(jì)體例：列舉法、歸納法、遞推、遞歸、減斗遞推手藝、回溯法。算法復(fù)雜度：算法時(shí)刻復(fù)雜度和算法空間復(fù)雜度。算法時(shí)刻復(fù)雜度是指執(zhí)行算法所需要的計(jì)較工作量。算法空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。1.2數(shù)據(jù)結(jié)構(gòu)的根基概念數(shù)據(jù)結(jié)構(gòu)研究的三個(gè)方面：（1）數(shù)據(jù)集結(jié)中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；（2）在對數(shù)據(jù)進(jìn)行措置時(shí)，各數(shù)據(jù)元素在計(jì)較機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)；（3）對各類數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。數(shù)據(jù)結(jié)構(gòu)是指彼此有聯(lián)系關(guān)系的數(shù)據(jù)元素的集結(jié)。數(shù)據(jù)的邏輯結(jié)構(gòu)包含：（1）暗示數(shù)據(jù)元素的信息；（2）暗示各數(shù)據(jù)元素之間的前后件關(guān)系。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有挨次、鏈接、索引等。線性結(jié)構(gòu)前提：（1）有且只有一個(gè)根結(jié)點(diǎn)；（2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。非線性結(jié)構(gòu)：不知足線性結(jié)構(gòu)前提的數(shù)據(jù)結(jié)構(gòu)。1.3線性表及其挨次存儲(chǔ)結(jié)構(gòu)線性表由一組數(shù)據(jù)元素組成，數(shù)據(jù)元素的位置只取決于自己的序號(hào)，元素之間的相對位置是線性的。在復(fù)雜線性表中，由若干項(xiàng)數(shù)據(jù)元素組成的數(shù)據(jù)元素稱為記實(shí)，而由多個(gè)記實(shí)組成的線性表又稱為文件。非空線性表的結(jié)構(gòu)特征：（1）且只有一個(gè)根結(jié)點(diǎn)a1，它無前件；（2）有且只有一個(gè)終端結(jié)點(diǎn)an，它無后件；（3）除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且只有一個(gè)后件。結(jié)點(diǎn)個(gè)數(shù)n稱為線性表的長度，當(dāng)n=0時(shí)，稱為空表。線性表的挨次存儲(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ù)。挨次表的運(yùn)算：插入、刪除。1.4棧和隊(duì)列棧是限制在一端進(jìn)行插入與刪除的線性表，許可插入與刪除的一端稱為棧頂，不許可插入與刪除的另一端稱為棧底。棧按照“前進(jìn)前輩后出”（FILO）或“后進(jìn)先出”（LIFO）組織數(shù)據(jù)，棧具有記憶浸染。用top暗示棧頂位置，用bottom暗示棧底。棧的根基運(yùn)算：（1）插入元素稱為入棧運(yùn)算；（2）刪除元素稱為退棧運(yùn)算；（3）讀棧頂元素是將棧頂元素賦給一個(gè)指定的變量，此時(shí)指針無轉(zhuǎn)變。隊(duì)列是指許可在一端（隊(duì)尾）進(jìn)入插入，而在另一端（隊(duì)頭）進(jìn)行刪除的線性表。Rear指針指向隊(duì)尾，front指針指向隊(duì)頭。隊(duì)列是“前進(jìn)前輩行出”（FIFO）或“后進(jìn)后出”（LILO）的線性表。隊(duì)列運(yùn)算搜羅（1）入隊(duì)運(yùn)算：年夜隊(duì)尾插入一個(gè)元素；（2）退隊(duì)運(yùn)算：年夜隊(duì)頭刪除一個(gè)元素。輪回隊(duì)列：s=0暗示隊(duì)列空，s=1且front=rear暗示隊(duì)列滿2.軌范設(shè)計(jì)基本2.1軌范設(shè)計(jì)設(shè)計(jì)體例和氣概精采的軌范設(shè)計(jì)氣概：1、源軌范文檔化；2、數(shù)據(jù)聲名的體例；3、語句的結(jié)構(gòu)；4、輸入和輸出。注釋分序言性注釋和功能性注釋，語句結(jié)構(gòu)清楚第一、效率第二。2.2結(jié)構(gòu)化軌范設(shè)計(jì)結(jié)構(gòu)化軌范設(shè)計(jì)體例的四條原則是：1.自頂向下；2.慢慢求精；3.模塊化；4.限制使用goto語句。結(jié)構(gòu)化軌范的根基結(jié)構(gòu)和特點(diǎn)：（1）挨次結(jié)構(gòu)：一種簡單的軌范設(shè)計(jì)，最根基、最常用的結(jié)構(gòu)；（2）選擇結(jié)構(gòu)：又稱分支結(jié)構(gòu)，搜羅簡單選擇和多分支選擇結(jié)構(gòu)，可按照前提，判定應(yīng)鈣揭捉擇哪一條分支來執(zhí)行響應(yīng)的語句序列；（3）一再結(jié)構(gòu)：又稱輪回結(jié)構(gòu)，可按照給定前提，判定是否需要一再執(zhí)行某一不異軌范段。2.3面向?qū)ο蟮能壏对O(shè)計(jì)面向?qū)ο蟮能壏对O(shè)計(jì)：以60年月末挪威奧斯陸年夜學(xué)和挪威計(jì)較機(jī)中心研制的SIMULA說話為標(biāo)識(shí)表記標(biāo)幟。面向?qū)ο篌w例的利益：1、與人類習(xí)慣的思維體例一致；2、不變性好；3、可重用性好；4、易于開發(fā)年夜型軟件產(chǎn)物；5、可維護(hù)性好。對象是面向?qū)ο篌w例中最根基的概念，可以用來暗示客不美觀世角逐的任何實(shí)體，對象是實(shí)體的抽象。面向?qū)ο蟮能壏对O(shè)計(jì)體例中的對象是系統(tǒng)賭暌姑來描述客不美觀事物的一個(gè)實(shí)體，是組成系統(tǒng)的一個(gè)根基單元，由一組暗示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。屬性即對象所包含的信息，操作描述了對象執(zhí)行的功能，操作也稱為體例或處事。對象的根基特點(diǎn)：1、標(biāo)識(shí)惟一性；2、分類性；3、多態(tài)性；4、封裝性；5、模塊自力性好。類是指具有配合屬性、配合體例的對象的集結(jié)。所以類是對象的抽象，對象是對應(yīng)類的一個(gè)實(shí)例。動(dòng)靜是一個(gè)實(shí)例與另一個(gè)實(shí)例之間傳遞的信息。動(dòng)靜的組成搜羅：1、領(lǐng)受動(dòng)靜的對象的名稱；2、動(dòng)靜標(biāo)識(shí)符，也稱動(dòng)靜名；3、零個(gè)或多個(gè)參數(shù)。擔(dān)任是指能夠直接獲得已有的性質(zhì)和特征，而不必一再界說他們。擔(dān)任分單擔(dān)任和多重?fù)?dān)任。單擔(dān)任指一個(gè)類只許可有一個(gè)父類，多重?fù)?dān)任指一個(gè)類許可有多個(gè)父類。多態(tài)性是指同樣的動(dòng)靜被分歧的對象接管時(shí)可導(dǎo)致完全分歧的步履的現(xiàn)象。3.軟件工程基本3.1軟件工程根基概念計(jì)較機(jī)軟件是搜羅軌范、數(shù)據(jù)及相關(guān)文檔的完整集結(jié)。軟件的特點(diǎn)搜羅：（1）軟件是一種邏輯實(shí)體；（2）軟件的出產(chǎn)與硬件分歧，它沒有較著的建造過程；（3）軟件在運(yùn)行、使用時(shí)代不存在磨損、老化問題；（4）軟件的開發(fā)、運(yùn)行對計(jì)較機(jī)系統(tǒng)具有依靠性，受計(jì)較機(jī)系統(tǒng)的限制，這導(dǎo)致了軟件移植的問題；（5）軟件復(fù)雜性高，成本昂貴；（6）軟件開發(fā)涉及諸多的社會(huì)身分。軟件按功能分為應(yīng)用軟件、系統(tǒng)軟件、支撐軟件（或工具軟件）。軟件危機(jī)首要默示在成本、質(zhì)量、出產(chǎn)率等問題。軟件工程是應(yīng)用于計(jì)較機(jī)軟件的界說、開發(fā)和維護(hù)的一整套體例、工具、文檔、實(shí)踐尺度和工序。軟件工程搜羅3個(gè)要素：體例、工具和過程。軟件工程過程是把軟件轉(zhuǎn)化為輸出的一組彼此相關(guān)的資本和勾當(dāng)，包含4種根基勾當(dāng)：（1）P—∨敉件規(guī)格聲名；（2）D—∨敉件開發(fā)；（3）C—∨敉件確認(rèn)；（4）A—∨敉件演進(jìn)。軟件周期Ｅ敉件產(chǎn)物年夜提出、實(shí)現(xiàn)、使用維護(hù)到遏制使用退役的過程。軟件生命周期三個(gè)階段:軟件界說、軟件開發(fā)、運(yùn)行維護(hù)，首要勾當(dāng)階段是：1、可行性研究與打算擬定；2、需求剖析；3、軟件設(shè)計(jì)；4、軟件實(shí)現(xiàn)；5、軟件測試；6、運(yùn)行和維護(hù)。軟件工程的方針和與原則：方針：在給定成本、進(jìn)度的前提下，開發(fā)出具有有用性、靠得住性、可理解性、可維護(hù)性、可重用性、可順應(yīng)性、可移植性、可追蹤性和可互操作性且知足用戶需求的產(chǎn)物。根基方針：支出較低的開發(fā)成本；達(dá)到要求的軟件功能；取得較好的軟件機(jī)能；開發(fā)軟件易于移植；需要較低的費(fèi)用；能按時(shí)完成開發(fā)，實(shí)時(shí)交付使用。根基原則：抽象、信息隱藏、模塊化、局部化、確定性、一致性、完整性和可驗(yàn)證性。軟件工程的理論和手藝性研究的內(nèi)容首要搜羅Ｅ敉件開起身術(shù)和軟件工程打點(diǎn)。軟件開起身術(shù)搜羅Ｅ敉件開發(fā)體例學(xué)、開發(fā)過程、開發(fā)工具和軟件工程情形。軟件工程打點(diǎn)搜羅Ｅ敉件打燈揭捉、軟件工程經(jīng)計(jì)揭捉、軟件心理學(xué)等內(nèi)容。軟件打燈揭捉搜羅人員組織、進(jìn)度放置、質(zhì)量保證、設(shè)置裝備擺設(shè)打點(diǎn)、項(xiàng)目打算等。軟件工程原則搜羅抽象、信息隱藏、模塊化、局部化、確定性、一致性、完整性和可驗(yàn)證性。3.2結(jié)構(gòu)化剖析體例結(jié)構(gòu)化體例的焦點(diǎn)和基本是結(jié)構(gòu)化軌范設(shè)計(jì)理論。需求剖析體例有：1、結(jié)構(gòu)化需求剖析體例；2、面向?qū)ο蟮钠饰龅捏w例。年夜需求剖析成立的模子的特征來分：靜態(tài)剖析和動(dòng)態(tài)剖析。結(jié)構(gòu)化剖析體例的本色：著眼于數(shù)據(jù)流，自頂向下，逐層分化，成立系統(tǒng)的措置流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為首要工具,成立系統(tǒng)的邏輯模子。結(jié)構(gòu)化剖析的常用工具：1、數(shù)據(jù)流圖；2、數(shù)據(jù)字典；3、剖斷樹；4、剖斷表。數(shù)據(jù)流圖：描述數(shù)據(jù)措置過程的工具，是需求理解的邏輯模子的圖形暗示，它直接撐持系統(tǒng)功能建模。數(shù)據(jù)字典：對所有與系統(tǒng)相關(guān)的數(shù)據(jù)元素的一個(gè)有組織的列表，以及切確的、嚴(yán)酷的界說，使得用戶和系統(tǒng)剖析員對于輸入、輸出、存儲(chǔ)成分和中心計(jì)較結(jié)不美觀有配合的理解。剖斷樹：年夜問題界說的文字描述平分清哪些是剖斷的前提，哪些是剖斷的結(jié)論，按照描述充溢中的毗連詞找出剖斷前提之間的隸屬關(guān)系、并列關(guān)系、選擇關(guān)系，按照它們機(jī)關(guān)剖斷樹。剖斷表：與剖斷輔弼似，當(dāng)數(shù)據(jù)流圖中的加工要依靠于多個(gè)邏輯前提的取值，即完成該加工的一組動(dòng)作是因?yàn)槟骋唤M前提取值的組合而激發(fā)的，使用剖斷表描述斗勁適宜。數(shù)據(jù)字典是結(jié)構(gòu)化剖析的焦點(diǎn)。軟件需求規(guī)格仿單的特點(diǎn)：1、正確性；2、無岐義性；3、完整性；4、可驗(yàn)證性；5、一致性；6、可理解性；7、可追蹤性。4.數(shù)據(jù)庫設(shè)計(jì)基本4.1數(shù)據(jù)庫系統(tǒng)的根基概念數(shù)據(jù)：現(xiàn)實(shí)上就是描述事物的符號(hào)記實(shí)。數(shù)據(jù)的特點(diǎn)：有必然的結(jié)構(gòu)，有型與值之分，如整型、實(shí)型、字符星勻。而數(shù)據(jù)的值給出了合適定型的值，如整型值15。數(shù)據(jù)庫：是數(shù)據(jù)的集結(jié)，具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲(chǔ)介質(zhì)內(nèi)，是多種應(yīng)用數(shù)據(jù)的集成，并可被各個(gè)應(yīng)用軌范共享。數(shù)據(jù)庫存放數(shù)據(jù)是按數(shù)據(jù)所供給的數(shù)據(jù)模式存放的，具有集成與共享的特點(diǎn)。數(shù)據(jù)庫打點(diǎn)系統(tǒng)：一種系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)庫中的數(shù)據(jù)組織、數(shù)據(jù)獨(dú)霸、數(shù)據(jù)維護(hù)、節(jié)制及呵護(hù)和數(shù)據(jù)處事等，是數(shù)據(jù)庫的焦點(diǎn)。數(shù)據(jù)庫打點(diǎn)系統(tǒng)功能：（1）數(shù)據(jù)模式界說：即為數(shù)據(jù)庫構(gòu)建其數(shù)據(jù)框架；（2）數(shù)據(jù)存取的物理構(gòu)建：為數(shù)據(jù)模式的物理存取與構(gòu)建供給有用的存取體例與手段；（3）數(shù)據(jù)獨(dú)霸：為用戶使用數(shù)據(jù)庫的數(shù)據(jù)供給便利，如發(fā)芽、插入、改削、刪除等以及簡單的算術(shù)運(yùn)算及統(tǒng)計(jì)；（4）數(shù)據(jù)的完整性、安素性界說與搜檢；（5）數(shù)據(jù)庫的并發(fā)節(jié)制與故障恢復(fù)；（6）數(shù)據(jù)的處事：如拷貝、轉(zhuǎn)存、重組、機(jī)能監(jiān)測、剖析等。為完成以上六個(gè)功能，數(shù)據(jù)庫打點(diǎn)系統(tǒng)供給以下的數(shù)據(jù)說話：（1）數(shù)據(jù)界說說話：負(fù)責(zé)數(shù)據(jù)的模式界說與數(shù)據(jù)的物理存取構(gòu)建；（2）數(shù)據(jù)獨(dú)霸說話：負(fù)責(zé)數(shù)據(jù)的獨(dú)霸，如發(fā)芽與增、刪、改等；（3）數(shù)據(jù)節(jié)制說話：負(fù)責(zé)數(shù)據(jù)完整性、平安性的界說與搜檢以及并發(fā)節(jié)制、故障恢復(fù)等。數(shù)據(jù)說話按其使用體例具有兩種結(jié)構(gòu)形式：交互式呼吁(又稱自含型或自立型說話)宿主型說話（一般可嵌入某些宿主說話中）。數(shù)據(jù)庫打點(diǎn)員：對數(shù)據(jù)庫進(jìn)行規(guī)劃、設(shè)計(jì)、維護(hù)、看管等的專業(yè)打點(diǎn)人員。數(shù)據(jù)庫系統(tǒng)：由數(shù)據(jù)庫（數(shù)據(jù)）、數(shù)據(jù)庫打點(diǎn)系統(tǒng)（軟件）、數(shù)據(jù)庫打點(diǎn)員（人員）、硬件平臺(tái)（硬件）、軟件平臺(tái)（軟件）五個(gè)部門組成的運(yùn)行實(shí)體。數(shù)據(jù)庫應(yīng)用系統(tǒng)：由數(shù)據(jù)庫系統(tǒng)、應(yīng)用軟件及應(yīng)用界面龐者組成。文件系統(tǒng)階段：供給了簡單的數(shù)據(jù)共享與數(shù)據(jù)打點(diǎn)能力，可是它無法供給完整的、統(tǒng)一的、打點(diǎn)和數(shù)據(jù)共享的能力。條理數(shù)據(jù)庫與網(wǎng)狀數(shù)據(jù)庫系統(tǒng)階段：為統(tǒng)一與共享數(shù)據(jù)供給了有力支撐。