為了方便計(jì)算機(jī)等級(jí)試,特意整理出來(lái)的。
第一章 數(shù)據(jù)結(jié)構(gòu)與算法 1 算法是解題方案的準(zhǔn)確而完整的描述,它不等于程序,也不等于計(jì)算方法。 基本特征:可行性、確定性、有窮性、擁有足夠的情報(bào)。
2 算法復(fù)雜度主要包括時(shí)間復(fù)雜度和空間復(fù)雜度。 時(shí)間復(fù)雜度:用來(lái)衡量算法執(zhí)行過(guò)程中所需要的基本運(yùn)算次數(shù)。
空間復(fù)雜度:用來(lái)衡量算法執(zhí)行過(guò)程中所需要的存儲(chǔ)空間。 3 數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容: (1)數(shù)據(jù)的邏輯結(jié)構(gòu) (2)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) (3)對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算 4 研究數(shù)據(jù)結(jié)構(gòu)的主要目的:提高數(shù)據(jù)處理的效率。
5 數(shù)據(jù)結(jié)構(gòu)的定義:指相互關(guān)聯(lián)的數(shù)據(jù)元素的集合。 6 數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系,數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間的存放形式。
同一種邏輯結(jié)構(gòu)可以采用不同存儲(chǔ)結(jié)構(gòu),但影響數(shù)據(jù)處理效率。 7 數(shù)據(jù)結(jié)構(gòu)分為兩大類(lèi)型:線性結(jié)構(gòu)與非線性結(jié)構(gòu) 常見(jiàn)線性結(jié)構(gòu):線性表、棧、隊(duì)列、線性鏈表 常用非線性結(jié)構(gòu):樹(shù)、二叉樹(shù)、圖 8 線性表示由n(n>=0)個(gè)相同類(lèi)型的數(shù)據(jù)元素構(gòu)成的有限序列。
結(jié)構(gòu)特征: (1)數(shù)據(jù)元素在表中的位置由序號(hào)決定,數(shù)據(jù)元素之間的相對(duì)位置是線性的 (2)對(duì)于一個(gè)非空線性表,有且只有一個(gè)根節(jié)點(diǎn)a1,它無(wú)前件,有且只有一個(gè)終端結(jié)點(diǎn)an,它無(wú)后件,除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外,其他所有結(jié)點(diǎn)有且只有一個(gè)前件,也有且只有一個(gè)后件。 基本存儲(chǔ)結(jié)構(gòu): (1)順序存儲(chǔ) (2)鏈?zhǔn)酱鎯?chǔ) 9 順序表的插入運(yùn)算時(shí)需要移動(dòng)元素,在等概率情況下,平均需要移動(dòng) n/2 個(gè)元素。
10 進(jìn)行順序表的刪除運(yùn)算時(shí)也需要移動(dòng)元素,在等概率情況下,平均移動(dòng)(n-1)/2 個(gè)元素。 11 棧只能在棧頂插入或刪除元素,是一種先進(jìn)后出FILO(或稱(chēng)為后入先出LIFO)的線性表。
12 隊(duì)列是只能從隊(duì)尾插入元素,在隊(duì)頭刪除元素,是一種先進(jìn)先出FIFO(或后入后出LILO)的線性表。 13 線性鏈表不能隨機(jī)存取。
14 在線性鏈表中插入元素時(shí),不需要移動(dòng)數(shù)據(jù)元素,只需要修改相關(guān)結(jié)點(diǎn)指針即可,也不會(huì)出現(xiàn)“上溢”現(xiàn)象。 15 在線性鏈表中刪除元素時(shí),也不需要移動(dòng)數(shù)據(jù)元素,只需要修改相關(guān)結(jié)點(diǎn)指針即可。
16 循環(huán)鏈表實(shí)單鏈表基礎(chǔ)上增加了一個(gè)表頭結(jié)點(diǎn),其插入和刪除運(yùn)算與單鏈表相同,可以從任意結(jié)點(diǎn)出發(fā)來(lái)訪問(wèn)表中其他所有結(jié)點(diǎn),并實(shí)現(xiàn)空表與非空表的運(yùn)算。 17 一般二叉樹(shù)通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),對(duì)于滿(mǎn)二叉樹(shù)與完全二叉樹(shù)來(lái)說(shuō),可以按層序進(jìn)行順序存儲(chǔ)。
18 二分查找知識(shí)用于順序存儲(chǔ)的線性表,對(duì)于無(wú)序線性表和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只能用順序查找。 19 冒泡排序是每一趟都會(huì)把較小的元素先前移動(dòng),最壞比較次數(shù)是 n(n-1)/2 。
20 簡(jiǎn)單插入排序法是將無(wú)序序列中的各元素依次插入到已經(jīng)有序的線性表中,最壞比較次數(shù)為 n(n-1)/2。 21 希爾排序法的基本思想:將無(wú)序序列劃分成若干個(gè)子序列(又相隔某個(gè)增量h的元素組成)分別進(jìn)行直接插入排序,待整個(gè)序列中的元素基本有序(增量足夠小)時(shí),在對(duì)全體元素進(jìn)行一次直接插入排序。
因?yàn)橹苯硬迦肱判蛟谠鼗居行虻那闆r下(接近最好情況),效率是很高的。 22 選擇排序每一趟都是找出無(wú)序序列中的最小一個(gè)元素,最壞比較次數(shù)為 n(n-1)/2。
23 排序技術(shù): (1)交換排序法:冒泡排序、快速排序 (2)插入排序法:簡(jiǎn)單插入排序法、希爾排序 (3)選擇排序法:簡(jiǎn)單選擇排序法、堆排序法。
公共基礎(chǔ)知識(shí)
基本要求
1.掌握算法的基本概念。
2.掌握基本數(shù)據(jù)結(jié)構(gòu)及其操作。
3.掌握基本排序和查找算法。
4.掌握逐步求精的結(jié)構(gòu)化程序設(shè)計(jì)方法。
5.掌握軟件工程的基本方法,具有初步應(yīng)用相關(guān)技術(shù)進(jìn)行軟件開(kāi)發(fā)的能力。
6.掌握數(shù)據(jù)庫(kù)的基本知識(shí),了解關(guān)系數(shù)據(jù)庫(kù)的設(shè)計(jì)。
考試內(nèi)容
一、基本數(shù)據(jù)結(jié)構(gòu)與算法
1.算法的基本概念;算法復(fù)雜度的概念和意義(時(shí)間復(fù)雜度與空間復(fù)雜度)。
2.數(shù)據(jù)結(jié)構(gòu)的定義;數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu);數(shù)據(jù)結(jié)構(gòu)的圖形表示;線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。
3.線性表的定義;線性表的順序存儲(chǔ)結(jié)構(gòu)及其插入與刪除運(yùn)算。
4.棧和隊(duì)列的定義;棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算。
5.線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。
6.樹(shù)的基本概念;二叉樹(shù)的定義及其存儲(chǔ)結(jié)構(gòu);二叉樹(shù)的前序、中序和后序遍歷。
7.順序查找與二分法查找算法;基本排序算法(交換類(lèi)排序,選擇類(lèi)排序,插入類(lèi)排序)。
二、程序設(shè)計(jì)基礎(chǔ)
1.程序設(shè)計(jì)方法與風(fēng)格
2.結(jié)構(gòu)化程序設(shè)計(jì)。
3.面向?qū)ο蟮某绦蛟O(shè)計(jì)方法,對(duì)象,方法,屬性及繼承與多態(tài)性。
三、軟件工程基礎(chǔ)
1.軟件工程基本概念,軟件生命周期概念,軟件工具與軟件開(kāi)發(fā)環(huán)境。
2.結(jié)構(gòu)化分析方法,數(shù)據(jù)流圖,數(shù)據(jù)字典,軟件需求規(guī)格說(shuō)明書(shū)。
3.結(jié)構(gòu)化設(shè)計(jì)方法,總體設(shè)計(jì)與詳細(xì)設(shè)計(jì)。
4.軟件測(cè)試的方法,白盒測(cè)試與黑盒測(cè)試,測(cè)試用例設(shè)計(jì),軟件測(cè)試的實(shí)施,單元測(cè)試、集成測(cè)試和系統(tǒng)測(cè)試。
5.程序的調(diào)試,靜態(tài)調(diào)試與動(dòng)態(tài)調(diào)試。
四、數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)
1.數(shù)據(jù)庫(kù)的基本概念:數(shù)據(jù)庫(kù),數(shù)據(jù)庫(kù)管理系統(tǒng),數(shù)據(jù)庫(kù)系統(tǒng)。
2.數(shù)據(jù)模型,實(shí)體聯(lián)系模型及E―R圖,從E―R圖導(dǎo)出關(guān)系數(shù)據(jù)模型。
3.關(guān)系代數(shù)運(yùn)算,包括集合運(yùn)算及選擇、投影、連接運(yùn)算,數(shù)據(jù)庫(kù)規(guī)范化理 論。
4.數(shù)據(jù)庫(kù)設(shè)計(jì)方法和步驟:需求分析、概念設(shè)計(jì)、邏輯設(shè)計(jì)和物理設(shè)計(jì)的相關(guān)策略。
考試方式
1.公共基礎(chǔ)知識(shí)的考試方式為筆試,與C語(yǔ)言程序設(shè)計(jì)(C++語(yǔ)言程序設(shè)計(jì)、Java語(yǔ)言程序設(shè)計(jì)、Visual Basic語(yǔ)言程序設(shè)計(jì)、Visual FoxPro數(shù)據(jù)庫(kù)程序設(shè)計(jì)或Access數(shù)據(jù)庫(kù)程序設(shè)計(jì))的筆試部分合為一張?jiān)嚲恚不A(chǔ)知識(shí)部分占全卷的30分。
2.公共基礎(chǔ)知識(shí)有l(wèi)0道選擇題和5道填
第一章數(shù)據(jù)結(jié)構(gòu)與算法1.1 算法算法:是指解題方案的準(zhǔn)確而完整的描述。
算法不等于程序,也不等計(jì)算機(jī)方法,程序的編制不可能優(yōu)于算法的設(shè)計(jì)。算法的基本特征:是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則,每一個(gè)規(guī)則都是有效的,是明確的,此順序?qū)⒃谟邢薜拇螖?shù)下終止。
特征包括:(1)可行性;(2)確定性,算法中每一步驟都必須有明確定義,不充許有模棱兩可的解釋?zhuān)辉试S有多義性;(3)有窮性,算法必須能在有限的時(shí)間內(nèi)做完,即能在執(zhí)行有限個(gè)步驟后終止,包括合理的執(zhí)行時(shí)間的含義;(4)擁有足夠的情報(bào)。算法的基本要素:一是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作;二是算法的控制結(jié)構(gòu)。
指令系統(tǒng):一個(gè)計(jì)算機(jī)系統(tǒng)能執(zhí)行的所有指令的集合。基本運(yùn)算和操作包括:算術(shù)運(yùn)算、邏輯運(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ù)、回溯法。
算法復(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ù)集合中各數(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)算。
數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。數(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):不滿(mǎn)足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。1.3 線性表及其順序存儲(chǔ)結(jié)構(gòu)線性表由一組數(shù)據(jù)元素構(gòu)成,數(shù)據(jù)元素的位置只取決于自己的序號(hào),元素之間的相對(duì)位置是線性的。
在復(fù)雜線性表中,由若干項(xiàng)數(shù)據(jù)元素組成的數(shù)據(jù)元素稱(chēng)為記錄,而由多個(gè)記錄構(gòu)成的線性表又稱(chēng)為文件。非空線性表的結(jié)構(gòu)特征:(1)且只有一個(gè)根結(jié)點(diǎn)a1,它無(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稱(chēng)為線性表的長(zhǎng)度,當(dāng)n=0時(shí),稱(chēng)為空表。線性表的順序存儲(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)算:插入、刪除。
(詳見(jiàn)14--16頁(yè))1.4 棧和隊(duì)列棧是限定在一端進(jìn)行插入與刪除的線性表,允許插入與刪除的一端稱(chēng)為棧頂,不允許插入與刪除的另一端稱(chēng)為棧底。棧按照“先進(jìn)后出”(FILO)或“后進(jìn)先出”(LIFO)組織數(shù)據(jù),棧具有記憶作用。
用top表示棧頂位置,用bottom表示棧底。棧的基本運(yùn)算:(1)插入元素稱(chēng)為入棧運(yùn)算;(2)刪除元素稱(chēng)為退棧運(yùn)算;(3)讀棧頂元素是將棧頂元素賦給一個(gè)指定的變量,此時(shí)指針無(wú)變化。
隊(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è)元素。
循環(huán)隊(duì)列:s=0表示隊(duì)列空,s=1且front=rear表示隊(duì)列滿(mǎn)1.5 線性鏈表數(shù)據(jù)結(jié)構(gòu)中的每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)存儲(chǔ)單元,這種存儲(chǔ)單元稱(chēng)為存儲(chǔ)結(jié)點(diǎn),簡(jiǎn)稱(chēng)結(jié)點(diǎn)。結(jié)點(diǎn)由兩部分組成:(1)用于存儲(chǔ)數(shù)據(jù)元素值,稱(chēng)為數(shù)據(jù)域;(2)用于存放指針,稱(chēng)為指針域,用于指向前一個(gè)或后一個(gè)結(jié)點(diǎn)。
在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中,存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù),各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致,而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來(lái)確定的。鏈?zhǔn)酱鎯?chǔ)方式即可用于表示線性結(jié)構(gòu),也可用于表示非線性結(jié)構(gòu)。
線性鏈表,HEAD稱(chēng)為頭指針,HEAD=NULL(或0)稱(chēng)為空表,如果是兩指針:左指針(Llink)指向前件結(jié)點(diǎn),右指針(Rlink)指向后件結(jié)點(diǎn)。線性鏈表的基本運(yùn)算:查找、插入、刪除。
1.6 樹(shù)與二*樹(shù)樹(shù)是一種簡(jiǎn)單的非線性結(jié)構(gòu),所有元素之間具有明顯的層次特性。在樹(shù)結(jié)構(gòu)中,每一個(gè)結(jié)點(diǎn)只有一個(gè)前件,稱(chēng)為父結(jié)點(diǎn),沒(méi)有前件的結(jié)點(diǎn)只有一個(gè),稱(chēng)為樹(shù)的根結(jié)點(diǎn),簡(jiǎn)稱(chēng)樹(shù)的根。
每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件,稱(chēng)為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒(méi)有后件的結(jié)點(diǎn)稱(chēng)為葉子結(jié)點(diǎn)。
在樹(shù)結(jié)構(gòu)中,一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱(chēng)為該結(jié)點(diǎn)的度,所有結(jié)點(diǎn)中最大的度稱(chēng)為樹(shù)的度。樹(shù)的最大層次稱(chēng)為樹(shù)的深度。
二*樹(shù)的特點(diǎn):(1)非空二*樹(shù)只有一個(gè)根結(jié)點(diǎn);(2)每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù),且分別稱(chēng)為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)。二*樹(shù)的基本性質(zhì):(1)在二*樹(shù)的第k層上,最多有2k-1(k≥1)個(gè)結(jié)點(diǎn);(2)深度為m的二*樹(shù)最多有2m-1個(gè)結(jié)點(diǎn);(3)度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè);(4)具有n個(gè)結(jié)點(diǎn)的二*樹(shù),其深度至少為[log2n]+1,其中[。
計(jì)算機(jī)等級(jí)考試二級(jí)必須考公共基礎(chǔ)知識(shí),計(jì)算機(jī)二級(jí)考核計(jì)算機(jī)基礎(chǔ)知識(shí)和使用一種高級(jí)計(jì)算機(jī)語(yǔ)言編寫(xiě)程序以及上機(jī)調(diào)試的基本技能。
考試科目:語(yǔ)言程序設(shè)計(jì)(C、C++、Java、VisualBasic、WEB)、數(shù)據(jù)庫(kù)程序設(shè)計(jì)(VisualFoxPro、Access、MySQL)、辦公軟件(MSOffice高級(jí)應(yīng)用)共九個(gè)科目。新增"MySQL數(shù)據(jù)庫(kù)程序設(shè)計(jì)"、"WEB程序設(shè)計(jì)"、"MSOffice高級(jí)應(yīng)用"三個(gè)科目。二級(jí)Delphi科目將從2013年上半年開(kāi)始停考,不再接受新考生報(bào)名,該次只接受補(bǔ)考考生報(bào)名,從第38次全國(guó)計(jì)算機(jī)等級(jí)考試(2013年9月)起,不再開(kāi)考。
考試形式:完全采取上機(jī)考試形式,各科上機(jī)考試時(shí)間均為120分鐘,滿(mǎn)分100分。總分達(dá)到60分,可以獲得合格證書(shū),沒(méi)有獲得合格證書(shū)的考生,不再安排補(bǔ)考,需以新考生身份報(bào)名參加考試。參加2013年3月全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)7個(gè)科目補(bǔ)考的老考生,仍按照傳統(tǒng)模式參加補(bǔ)考。
獲證條件:通過(guò)二級(jí)科目考試。
考核內(nèi)容:二級(jí)定位為程序員,考核內(nèi)容包括公共基礎(chǔ)知識(shí)和程序設(shè)計(jì)。所有科目對(duì)基礎(chǔ)知識(shí)作統(tǒng)一要求,使用統(tǒng)一的公共基礎(chǔ)知識(shí)考試大綱和教程。二級(jí)公共基礎(chǔ)知識(shí)在各科考試選擇題中體現(xiàn)。程序設(shè)計(jì)部分,主要考查考生對(duì)程序設(shè)計(jì)語(yǔ)言使用和編程調(diào)試等基本能力,在選擇題和操作題中加以體現(xiàn)。
題型及分值比例:①選擇題40題,40%;②程序設(shè)計(jì)題3題,60%。
上機(jī)考試環(huán)境及使用的軟件:全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)上機(jī)考試環(huán)境為Windows7簡(jiǎn)體中文版。各科目使用的軟件如下:
計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)是計(jì)算機(jī)中綜合性知識(shí),占30分。
包含的科目有數(shù)據(jù)結(jié)構(gòu),軟件工程,算法設(shè)計(jì)與分析,數(shù)據(jù)庫(kù)設(shè)計(jì)等。而這些科目都屬于計(jì)算機(jī)專(zhuān)業(yè)必修課,也是一個(gè)程序員的必備理論基礎(chǔ)。
我們知道二級(jí)的目標(biāo)定位就是程序員的水平,所以這些科目都是必考內(nèi)容。 那么如何備考呢?實(shí)際上很簡(jiǎn)單,只要買(mǎi)一本教育部考試中心出版的計(jì)算機(jī)二級(jí)考試公共基礎(chǔ)知識(shí)大綱級(jí)指導(dǎo)書(shū)(一定是教育部出版發(fā)行的那種),回來(lái)抽個(gè)時(shí)間仔細(xì)研讀一番就可以了,而且無(wú)須做大量練習(xí)題,因?yàn)槎?jí)要求不高,停留在概念的階段。
復(fù)習(xí)時(shí),不要將其看的太重,因?yàn)榇蠹业乃蕉疾畈欢啵怯?jì)算機(jī)專(zhuān)業(yè)的。 ========================================== 全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)考試大綱 基本要求 1。
掌握算法的基本概念。 2。
掌握基本數(shù)據(jù)結(jié)構(gòu)及其操作。 3。
掌握基本排序和查找算法。 4。
掌握逐步求精的結(jié)構(gòu)化程序設(shè)計(jì)方法。 5。
掌握軟件工程的基本方法,具有初步應(yīng)用相關(guān)技術(shù)進(jìn)行軟件開(kāi)發(fā)的能力。 6。
掌握數(shù)據(jù)的基本知識(shí),了解關(guān)系數(shù)據(jù)庫(kù)的設(shè)計(jì)。 考試內(nèi)容 一、基本數(shù)據(jù)結(jié)構(gòu)與算法 1。
算法的基本概念;算法復(fù)雜度的概念和意義(時(shí)間復(fù)雜度與空間復(fù)雜度)。 2。
數(shù)據(jù)結(jié)構(gòu)的定義;數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu);數(shù)據(jù)結(jié)構(gòu)的圖形表示;線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。 3。
線性表的定義;線性表的順序存儲(chǔ)結(jié)構(gòu)及其插入與刪除運(yùn)算。 4。
棧和隊(duì)列的定義;棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算。 5。
線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。 6。
樹(shù)的基本概念;二叉樹(shù)的定義及其存儲(chǔ)結(jié)構(gòu);二叉樹(shù)的前序、中序和后序遍歷。 7。
順序查找與二分法查找算法;基本排序算法(交換類(lèi)排序,選擇類(lèi)排序,插入類(lèi)排序)。 二、程序設(shè)計(jì)基礎(chǔ) 1。
程序設(shè)計(jì)方法與風(fēng)格。 2。
結(jié)構(gòu)化程序設(shè)計(jì)。 3。
面向?qū)ο蟮某绦蛟O(shè)計(jì)方法,對(duì)象,方法,屬性及繼承與多態(tài)性。 三、軟件工程基礎(chǔ) 1。
軟件工程基本概念,軟件生命周戎概念,軟件工具與軟件開(kāi)發(fā)環(huán)境。 2。
結(jié)構(gòu)化分析方法,數(shù)據(jù)流圖,數(shù)據(jù)字典,軟件需求規(guī)格說(shuō)明書(shū)。 3。
結(jié)構(gòu)化設(shè)計(jì)方法,總體設(shè)計(jì)與詳細(xì)設(shè)計(jì)。 4。
軟件測(cè)試的方法,白盒測(cè)試與黑盒測(cè)試,測(cè)試用例設(shè)計(jì),軟件測(cè)試的實(shí)施,單元測(cè)試、集成測(cè)試和系統(tǒng)測(cè)試。 5。
程序的調(diào)試,靜態(tài)調(diào)試與動(dòng)態(tài)調(diào)試。 四、數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ) 1。
數(shù)據(jù)庫(kù)的基本概念:數(shù)據(jù)庫(kù),數(shù)據(jù)庫(kù)管理系統(tǒng),數(shù)據(jù)庫(kù)系統(tǒng)。 2。
數(shù)據(jù)模型,實(shí)體聯(lián)系模型及E-R圖,從E-R圖導(dǎo)出關(guān)系數(shù)據(jù)模型。 3。
關(guān)系代數(shù)運(yùn)算,包括集合運(yùn)算及選擇、投影、連接運(yùn)算,數(shù)據(jù)庫(kù)規(guī)范化理論。 4。
數(shù)據(jù)庫(kù)設(shè)計(jì)方法和步驟:需求分析、概念設(shè)計(jì)、邏輯設(shè)計(jì)和物理設(shè)計(jì)的相關(guān)策略。 。
計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)總結(jié)
數(shù)據(jù)結(jié)構(gòu)與算法
1.1 算法
算法:是指解題方案的準(zhǔn)確而完整的描述。
算法不等于程序,也不等計(jì)算機(jī)方法,程序的編制不可能優(yōu)于算法的設(shè)計(jì)。
算法的基本特征:是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則,每一個(gè)規(guī)則都是有效的,是明確的,此順序?qū)⒃谟邢薜拇螖?shù)下終止。特征包括:
(1)可行性;
(2)確定性,算法中每一步驟都必須有明確定義,不充許有模棱兩可的解釋?zhuān)辉试S有多義性;
(3)有窮性,算法必須能在有限的時(shí)間內(nèi)做完,即能在執(zhí)行有限個(gè)步驟后終止,包括合理的執(zhí)行時(shí)間的含義;
(4)擁有足夠的情報(bào)。
算法的基本要素:一是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作;二是算法的控制結(jié)構(gòu)。
指令系統(tǒng):一個(gè)計(jì)算機(jī)系統(tǒng)能執(zhí)行的所有指令的集合。
基本運(yùn)算和操作包括:算術(shù)運(yùn)算、邏輯運(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ù)、回溯法。
算法復(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ù)集合中各數(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)算。
數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。
數(shù)據(jù)的邏輯結(jié)構(gòu)包含:
(1)表示數(shù)據(jù)元素的信息;
(2)表示各數(shù)據(jù)元素之間的前后件關(guān)系。
數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等。等等
【【上 學(xué) 吧】】 有詳細(xì)的資料 自己去看看
基本要求
1. 掌握算法的基本概念。
2. 掌握基本數(shù)據(jù)結(jié)構(gòu)及其操作。
3. 掌握基本排序和查找算法。
4. 掌握逐步求精的結(jié)構(gòu)化程序設(shè)計(jì)方法。
5. 掌握軟件工程的基本方法,具有初步應(yīng)用相關(guān)技術(shù)進(jìn)行軟件開(kāi)發(fā)的能力。
6. 掌握數(shù)據(jù)的基本知識(shí),了解關(guān)系數(shù)據(jù)庫(kù)的設(shè)計(jì)。
考試內(nèi)容
一、基本數(shù)據(jù)結(jié)構(gòu)與算法
1. 算法的基本概念;算法復(fù)雜度的概念和意義(時(shí)間復(fù)雜度與空間復(fù)雜度)。
2. 數(shù)據(jù)結(jié)構(gòu)的定義;數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu);數(shù)據(jù)結(jié)構(gòu)的圖形表示;線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。
3. 線性表的定義;線性表的順序存儲(chǔ)結(jié)構(gòu)及其插入與刪除運(yùn)算。
4. 棧和隊(duì)列的定義;棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算。
5. 線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。
6. 樹(shù)的基本概念;二叉樹(shù)的定義及其存儲(chǔ)結(jié)構(gòu);二叉樹(shù)的前序、中序和后序遍歷。
7. 順序查找與二分法查找算法;基本排序算法(交換類(lèi)排序,選擇類(lèi)排序,插入類(lèi)排序)。
二、程序設(shè)計(jì)基礎(chǔ)
1. 程序設(shè)計(jì)方法與風(fēng)格。
2. 結(jié)構(gòu)化程序設(shè)計(jì)。
3. 面向?qū)ο蟮某绦蛟O(shè)計(jì)方法,對(duì)象,方法,屬性及繼承與多態(tài)性。
三、軟件工程基礎(chǔ)
1. 軟件工程基本概念,軟件生命周戎概念,軟件工具與軟件開(kāi)發(fā)環(huán)境。
2. 結(jié)構(gòu)化分析方法,數(shù)據(jù)流圖,數(shù)據(jù)字典,軟件需求規(guī)格說(shuō)明書(shū)。
3. 結(jié)構(gòu)化設(shè)計(jì)方法,總體設(shè)計(jì)與詳細(xì)設(shè)計(jì)。
4. 軟件測(cè)試的方法,白盒測(cè)試與黑盒測(cè)試,測(cè)試用例設(shè)計(jì),軟件測(cè)試的實(shí)施,單元測(cè)試、集成測(cè)試和系統(tǒng)測(cè)試。
5. 程序的調(diào)試,靜態(tài)調(diào)試與動(dòng)態(tài)調(diào)試。
四、數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)
1. 數(shù)據(jù)庫(kù)的基本概念:數(shù)據(jù)庫(kù),數(shù)據(jù)庫(kù)管理系統(tǒng),數(shù)據(jù)庫(kù)系統(tǒng)。
2. 數(shù)據(jù)模型,實(shí)體聯(lián)系模型及E-R圖,從E-R圖導(dǎo)出關(guān)系數(shù)據(jù)模型。
3. 關(guān)系代數(shù)運(yùn)算,包括集合運(yùn)算及選擇、投影、連接運(yùn)算,數(shù)據(jù)庫(kù)規(guī)范化理論。
4. 數(shù)據(jù)庫(kù)設(shè)計(jì)方法和步驟:需求分析、概念設(shè)計(jì)、邏輯設(shè)計(jì)和物理設(shè)計(jì)的相關(guān)策略。
考試方式
1、公共基礎(chǔ)的考試方式為筆試,與C語(yǔ)言(VisualBASIC、Visual FoxPro、Java、Access、Visual C++)的筆試部分合為一張?jiān)嚲怼9不A(chǔ)部分占全卷的30分。
2、公共基礎(chǔ)知識(shí)有10道選擇題和5道填空題。
您好,中公教育為您服務(wù)。
全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)考試大綱(2013年版) 基本要求 1. 掌握算法的基本概念。 2. 掌握基本數(shù)據(jù)結(jié)構(gòu)及其操作。
3. 掌握基本排序和查找算法。 4. 掌握逐步求精的結(jié)構(gòu)化程序設(shè)計(jì)方法。
5. 掌握軟件工程的基本方法,具有初步應(yīng)用相關(guān)技術(shù)進(jìn)行軟件開(kāi)發(fā)的能力。 6. 掌握數(shù)據(jù)庫(kù)的基本知識(shí),了解關(guān)系數(shù)據(jù)庫(kù)的設(shè)計(jì)。
考試內(nèi)容 一、基本數(shù)據(jù)結(jié)構(gòu)與算法 1. 算法的基本概念;算法復(fù)雜度的概念和意義(時(shí)間復(fù)雜度與空間復(fù)雜度)。 2. 數(shù)據(jù)結(jié)構(gòu)的定義;數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu);數(shù)據(jù)結(jié)構(gòu)的圖形表示;線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。
3. 線性表的定義;線性表的順序存儲(chǔ)結(jié)構(gòu)及其插入與刪除運(yùn)算。 4. 棧和隊(duì)列的定義;棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算。
5. 線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。 6. 樹(shù)的基本概念;二叉樹(shù)的定義及其存儲(chǔ)結(jié)構(gòu);二叉樹(shù)的前序、中序和后序遍歷。
7. 順序查找與二分法查找算法;基本排序算法(交換類(lèi)排序,選擇類(lèi)排序,插入類(lèi)排序)。 二、程序設(shè)計(jì)基礎(chǔ) 1. 程序設(shè)計(jì)方法與風(fēng)格。
2. 結(jié)構(gòu)化程序設(shè)計(jì)。 3. 面向?qū)ο蟮某绦蛟O(shè)計(jì)方法,對(duì)象,方法,屬性及繼承與多態(tài)性。
三、軟件工程基礎(chǔ) 1. 軟件工程基本概念,軟件生命周期概念,軟件工具與軟件開(kāi)發(fā)環(huán)境。 2. 結(jié)構(gòu)化分析方法,數(shù)據(jù)流圖,數(shù)據(jù)字典,軟件需求規(guī)格說(shuō)明書(shū)。
3. 結(jié)構(gòu)化設(shè)計(jì)方法,總體設(shè)計(jì)與詳細(xì)設(shè)計(jì)。 4. 軟件測(cè)試的方法,白盒測(cè)試與黑盒測(cè)試,測(cè)試用例設(shè)計(jì),軟件測(cè)試的實(shí)施,單元測(cè)試、集成測(cè)試和系統(tǒng)測(cè)試。
5. 程序的調(diào)試,靜態(tài)調(diào)試與動(dòng)態(tài)調(diào)試。 四、數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ) 1. 數(shù)據(jù)庫(kù)的基本概念:數(shù)據(jù)庫(kù),數(shù)據(jù)庫(kù)管理系統(tǒng),數(shù)據(jù)庫(kù)系統(tǒng)。
2. 數(shù)據(jù)模型,實(shí)體聯(lián)系模型及E-R圖,從E-R圖導(dǎo)出關(guān)系數(shù)據(jù)模型。 3. 關(guān)系代數(shù)運(yùn)算,包括集合運(yùn)算及選擇、投影、連接運(yùn)算,數(shù)據(jù)庫(kù)規(guī)范化理論。
4. 數(shù)據(jù)庫(kù)設(shè)計(jì)方法和步驟:需求分析、概念設(shè)計(jì)、邏輯設(shè)計(jì)和物理設(shè)計(jì)的相關(guān)策略。考試方式 1. 公共基礎(chǔ)知識(shí)不單獨(dú)考試,與其他二級(jí)科目組合在一起,作為二級(jí)科目考核內(nèi)容的一部分。
2. 考試方式為上機(jī)考試,10道選擇題,占10分。如有疑問(wèn),歡迎向中公教育企業(yè)知道提問(wèn)。
聲明:本網(wǎng)站尊重并保護(hù)知識(shí)產(chǎn)權(quán),根據(jù)《信息網(wǎng)絡(luò)傳播權(quán)保護(hù)條例》,如果我們轉(zhuǎn)載的作品侵犯了您的權(quán)利,請(qǐng)?jiān)谝粋€(gè)月內(nèi)通知我們,我們會(huì)及時(shí)刪除。
蜀ICP備2020033479號(hào)-4 Copyright ? 2016 學(xué)習(xí)鳥(niǎo). 頁(yè)面生成時(shí)間:3.851秒