為了方便計算機等級試,特意整理出來(lái)的。
第一章 數據結構與算法 1 算法是解題方案的準確而完整的描述,它不等于程序,也不等于計算方法。 基本特征:可行性、確定性、有窮性、擁有足夠的情報。
2 算法復雜度主要包括時(shí)間復雜度和空間復雜度。 時(shí)間復雜度:用來(lái)衡量算法執行過(guò)程中所需要的基本運算次數。
空間復雜度:用來(lái)衡量算法執行過(guò)程中所需要的存儲空間。 3 數據結構研究的主要內容: (1)數據的邏輯結構 (2)數據的存儲結構 (3)對各種數據結構進(jìn)行的運算 4 研究數據結構的主要目的:提高數據處理的效率。
5 數據結構的定義:指相互關(guān)聯(lián)的數據元素的集合。 6 數據的邏輯結構反映數據元素之間的邏輯關(guān)系,數據的存儲結構是數據的邏輯結構在計算機存儲空間的存放形式。
同一種邏輯結構可以采用不同存儲結構,但影響數據處理效率。 7 數據結構分為兩大類(lèi)型:線(xiàn)性結構與非線(xiàn)性結構 常見(jiàn)線(xiàn)性結構:線(xiàn)性表、棧、隊列、線(xiàn)性鏈表 常用非線(xiàn)性結構:樹(shù)、二叉樹(shù)、圖 8 線(xiàn)性表示由n(n>=0)個(gè)相同類(lèi)型的數據元素構成的有限序列。
結構特征: (1)數據元素在表中的位置由序號決定,數據元素之間的相對位置是線(xiàn)性的 (2)對于一個(gè)非空線(xiàn)性表,有且只有一個(gè)根節點(diǎn)a1,它無(wú)前件,有且只有一個(gè)終端結點(diǎn)an,它無(wú)后件,除根結點(diǎn)與終端結點(diǎn)外,其他所有結點(diǎn)有且只有一個(gè)前件,也有且只有一個(gè)后件。 基本存儲結構: (1)順序存儲 (2)鏈式存儲 9 順序表的插入運算時(shí)需要移動(dòng)元素,在等概率情況下,平均需要移動(dòng) n/2 個(gè)元素。
10 進(jìn)行順序表的刪除運算時(shí)也需要移動(dòng)元素,在等概率情況下,平均移動(dòng)(n-1)/2 個(gè)元素。 11 棧只能在棧頂插入或刪除元素,是一種先進(jìn)后出FILO(或稱(chēng)為后入先出LIFO)的線(xiàn)性表。
12 隊列是只能從隊尾插入元素,在隊頭刪除元素,是一種先進(jìn)先出FIFO(或后入后出LILO)的線(xiàn)性表。 13 線(xiàn)性鏈表不能隨機存取。
14 在線(xiàn)性鏈表中插入元素時(shí),不需要移動(dòng)數據元素,只需要修改相關(guān)結點(diǎn)指針即可,也不會(huì )出現“上溢”現象。 15 在線(xiàn)性鏈表中刪除元素時(shí),也不需要移動(dòng)數據元素,只需要修改相關(guān)結點(diǎn)指針即可。
16 循環(huán)鏈表實(shí)單鏈表基礎上增加了一個(gè)表頭結點(diǎn),其插入和刪除運算與單鏈表相同,可以從任意結點(diǎn)出發(fā)來(lái)訪(fǎng)問(wèn)表中其他所有結點(diǎn),并實(shí)現空表與非空表的運算。 17 一般二叉樹(shù)通常采用鏈式存儲結構,對于滿(mǎn)二叉樹(shù)與完全二叉樹(shù)來(lái)說(shuō),可以按層序進(jìn)行順序存儲。
18 二分查找知識用于順序存儲的線(xiàn)性表,對于無(wú)序線(xiàn)性表和線(xiàn)性表的鏈式存儲結構只能用順序查找。 19 冒泡排序是每一趟都會(huì )把較小的元素先前移動(dòng),最壞比較次數是 n(n-1)/2 。
20 簡(jiǎn)單插入排序法是將無(wú)序序列中的各元素依次插入到已經(jīng)有序的線(xiàn)性表中,最壞比較次數為 n(n-1)/2。 21 希爾排序法的基本思想:將無(wú)序序列劃分成若干個(gè)子序列(又相隔某個(gè)增量h的元素組成)分別進(jìn)行直接插入排序,待整個(gè)序列中的元素基本有序(增量足夠小)時(shí),在對全體元素進(jìn)行一次直接插入排序。
因為直接插入排序在元素基本有序的情況下(接近最好情況),效率是很高的。 22 選擇排序每一趟都是找出無(wú)序序列中的最小一個(gè)元素,最壞比較次數為 n(n-1)/2。
23 排序技術(shù): (1)交換排序法:冒泡排序、快速排序 (2)插入排序法:簡(jiǎn)單插入排序法、希爾排序 (3)選擇排序法:簡(jiǎn)單選擇排序法、堆排序法。
一、基本數據結構與算法
1.算法的基本概念;算法復雜度的概念和意義(時(shí)間復雜度與空間復雜度)。
2.數據結構的定義;數據的邏輯結構與存儲結構;數據結構的圖形表示;線(xiàn)性結構與非線(xiàn)性結構的概念。
3.線(xiàn)性表的定義;線(xiàn)性表的順序存儲結構及其插入與刪除運算。
4.棧和隊列的定義;棧和隊列的順序存儲結構及其基本運算。
5.線(xiàn)性單鏈表、雙向鏈表與循環(huán)鏈表的結構及其基本運算。
6.樹(shù)的基本概念;二叉樹(shù)的定義及其存儲結構;二叉樹(shù)的前序、中序和后序遍歷。
7.順序查找與二分法查找算法;基本排序算法(交換類(lèi)排序,選擇類(lèi)排序,插入類(lèi)排序)。
二、程序設計基礎
1.程序設計方法與風(fēng)格。
2.結構化程序設計。
3.面向對象的程序設計方法,對象,方法,屬性及繼承與多態(tài)性。
三、軟件工程基礎
1.軟件工程基本概念,軟件生命周期概念,軟件工具與軟件開(kāi)發(fā)環(huán)境。
2.結構化分析方法,數據流圖,數據字典,軟件需求規格說(shuō)明書(shū)。
3.結構化設計方法,總體設計與詳細設計。
4.軟件測試的方法,白盒測試與黑盒測試,測試用例設計,軟件測試的實(shí)施,單元測試、集成測試和系統測試。
5.程序的調試,靜態(tài)調試與動(dòng)態(tài)調試。
四、數據庫設計基礎
1.數據庫的基本概念:數據庫,數據庫管理系統,數據庫系統。
2.數據模型,實(shí)體聯(lián)系模型及E-R圖,從E-R圖導出關(guān)系數據模型。
3.關(guān)系代數運算,包括集合運算及選擇、投影、連接運算,數據庫規范化理論。
4.數據庫設計方法和步驟:需求分析、概念設計、邏輯設計和物理設計的相關(guān)策略。
這些你可以到未來(lái)教育網(wǎng)上詳細看看!
計算機二級公共基礎知識總結
數據結構與算法
1.1 算法
算法:是指解題方案的準確而完整的描述。
算法不等于程序,也不等計算機方法,程序的編制不可能優(yōu)于算法的設計。
算法的基本特征:是一組嚴謹地定義運算順序的規則,每一個(gè)規則都是有效的,是明確的,此順序將在有限的次數下終止。特征包括:
(1)可行性;
(2)確定性,算法中每一步驟都必須有明確定義,不充許有模棱兩可的解釋?zhuān)辉试S有多義性;
(3)有窮性,算法必須能在有限的時(shí)間內做完,即能在執行有限個(gè)步驟后終止,包括合理的執行時(shí)間的含義;
(4)擁有足夠的情報。
算法的基本要素:一是對數據對象的運算和操作;二是算法的控制結構。
指令系統:一個(gè)計算機系統能執行的所有指令的集合。
基本運算和操作包括:算術(shù)運算、邏輯運算、關(guān)系運算、數據傳輸。
算法的控制結構:順序結構、選擇結構、循環(huán)結構。
算法基本設計方法:列舉法、歸納法、遞推、遞歸、減斗遞推技術(shù)、回溯法。
算法復雜度:算法時(shí)間復雜度和算法空間復雜度。
算法時(shí)間復雜度是指執行算法所需要的計算工作量。
算法空間復雜度是指執行這個(gè)算法所需要的內存空間。
1.2 數據結構的基本基本概念
數據結構研究的三個(gè)方面:
(1)數據集合中各數據元素之間所固有的邏輯關(guān)系,即數據的邏輯結構;
(2)在對數據進(jìn)行處理時(shí),各數據元素在計算機中的存儲關(guān)系,即數據的存儲結構;
(3)對各種數據結構進(jìn)行的運算。
數據結構是指相互有關(guān)聯(lián)的數據元素的集合。
數據的邏輯結構包含:
(1)表示數據元素的信息;
(2)表示各數據元素之間的前后件關(guān)系。
數據的存儲結構有順序、鏈接、索引等。等等
【【上 學(xué) 吧】】 有詳細的資料 自己去看看
1、算法問(wèn)題處理方案的正確而完整的描述稱(chēng)為【算法】。
算法分析的目的是,分析算法的效率以求改進(jìn)。算法的基本特征是【可行性】、【確定性】、【有窮性】和擁有足夠情報。
算法的有窮性是指:算法程序的運行時(shí)間是有限的。算法的復雜度是衡量算法好壞的度量,分為【時(shí)間復雜度】和【空間復雜度】。
時(shí)間復雜度是指執行算法所需要的【計算工作量】;算法的空間復雜度是指算法執行過(guò)程中所需的【存儲空間】。算法時(shí)間復雜度或空間復雜度中的一項的值,沒(méi)有辦法推出另一項的值。
2、數據結構索引屬于存儲結構(物理結構)。循環(huán)隊列屬于【存儲結構】。
數據的存儲結構又稱(chēng)為物理結構,是數據的邏輯結構在計算機存儲空間中的存放形式。一個(gè)邏輯結構可以有多種存儲結構,且各種存儲結構影響數據處理的效率。
程序執行的效率與數據的存儲結構密切相關(guān)。數據結構分為線(xiàn)性結構和非線(xiàn)性結構,帶鏈的隊列屬于【線(xiàn)性結構】。
線(xiàn)性表的存儲結構主要分為順序存儲結構和鏈式存儲結構。順序存儲結構的存儲一定是連續的,鏈式存儲的存儲空間不一定是連續的。
有序線(xiàn)性表既可以采用順序存儲結構,也可以采用鏈式存儲結構。隊列是一種特殊的線(xiàn)性表,循環(huán)隊列按照【先進(jìn)先出】原則組織數據。
循環(huán)隊列是隊列的【順序】存儲結構。數據的獨立性分為【物理獨立】性和【邏輯獨立性】。
當數據的存儲結構改變時(shí),其邏輯結構可以不變,因此,基于邏輯結構的應用程序可以不用修改,稱(chēng)為【物理獨立性】。3、棧和隊列棧是一種特殊的線(xiàn)性表,是只能在一端進(jìn)行插入和刪除的線(xiàn)性表,特點(diǎn)是先進(jìn)后出棧是【先進(jìn)后出】的線(xiàn)性表;棧具有記憶作用;對棧的插入與刪除操作中,不需要改變【棧底指針】。
假定讓元素1、2、3、A、B依次入棧,則出棧的順序是:B、A、3、2、1。棧與隊列都是線(xiàn)性結構,樹(shù)是非線(xiàn)性結構。
支持子程序調用的數據結構是【棧】。棧與隊列的共同點(diǎn)是,都只允許在【端點(diǎn)處】插入和刪除元素。
棧只能順序存儲的描述是錯誤的。棧可以有【順序和鏈式】?jì)煞N存儲方式。
隊列是允許在一段插入,在另一端進(jìn)行刪除的線(xiàn)性表,其特點(diǎn)是【先進(jìn)先出】。循環(huán)隊列中元素的個(gè)數是由隊頭指針和隊尾指針共同決定。
循環(huán)隊列的頭指針為front,尾指針為rear,容量為maxSize,則循環(huán)隊列中元素的個(gè)數是【 (rear-front+maxSize) mod maxSize】。4、線(xiàn)性鏈表線(xiàn)性鏈表是線(xiàn)性表的鏈式存儲結構。
用鏈表表示線(xiàn)性表的優(yōu)點(diǎn)是【便于插入和刪除操作】。線(xiàn)性鏈表的存儲空間不一定連續,且個(gè)元素的存儲順序是任意的。
5、樹(shù)與二叉樹(shù)在樹(shù)結構中,一個(gè)結點(diǎn)所擁有的后件(繼)的個(gè)數稱(chēng)為該結點(diǎn)的度,所有結點(diǎn)中最大的度稱(chēng)為樹(shù)的度。二叉樹(shù)各結點(diǎn)的度只可能取值0、1、2,不可能是其它值。
換言之,知道了度為1結點(diǎn)數量的前提下,葉子結點(diǎn)或度為2的結點(diǎn)中知道其一,就可以求出總的結點(diǎn)數。上述的計算公式,關(guān)鍵要能夠應用,例如,深度為7的滿(mǎn)二叉樹(shù),度為2的結點(diǎn)數量是多少?既然是滿(mǎn)二叉樹(shù),葉子結點(diǎn)的數量就是第7層的結點(diǎn)數量,也就是26,可以算出葉子結點(diǎn)為64,因此度為2的結點(diǎn)數是63(葉子結點(diǎn)數減去1)。
二叉樹(shù)的前序遍歷、中序遍歷、后續遍歷:前中后三個(gè)詞是相對于根來(lái)講的,前序是【根-->左-->右】,中序是【左-->根-->右】,后續是【左-->右-->根】。具體操作為:先序遍歷(D L R): 訪(fǎng)問(wèn)根結點(diǎn),按先序遍歷左子樹(shù),按先序遍歷右子樹(shù)。
中序遍歷(L D R): 按中序遍歷左子樹(shù),訪(fǎng)問(wèn)根結點(diǎn),按中序遍歷右子樹(shù)。后序遍歷(L R D): 按后序遍歷左子樹(shù),按后序遍歷右子樹(shù),訪(fǎng)問(wèn)根結點(diǎn)。
下面以中序遍歷為例,來(lái)講解實(shí)際的解題方法:對一棵樹(shù),將根結點(diǎn)下的左子樹(shù)用一個(gè)橢圓圈起來(lái),右子樹(shù)也用一個(gè)橢圓圈起來(lái)。之后,在左子樹(shù)上標記上1,在根結點(diǎn)標記上2,在右子樹(shù)上標記上3。
對在左邊橢圓內的左子樹(shù),現在把它單獨拿出來(lái)分析。把它的左子樹(shù)圈起來(lái)標上1.1,根結點(diǎn)標記上1.2,右子樹(shù)標上1.3。
按照上述方法依次往下,直到樹(shù)不能拆分,然后按照“左-->根--->右”的順序寫(xiě)出結點(diǎn)的訪(fǎng)問(wèn)先后即可。6、查找技術(shù)對于長(cháng)度為n的線(xiàn)性表,順序查找最壞情況下需要比較n次。
(對數據是否有序沒(méi)有要求)。◆ 順序查找最好情況下查詢(xún)次數是1,最壞情況下是n,平均為(1+n)/2。
對于長(cháng)度為n的有序線(xiàn)性表,二分法最壞情況下只需要比較log2n次。(數據必須有序)能用二分法進(jìn)行查找的是【順序存儲的有序線(xiàn)性表】。
7、排序技術(shù)對于長(cháng)度為n的線(xiàn)性表,【冒泡排序、快速排序、簡(jiǎn)單插入排序、簡(jiǎn)單選擇排序】這四種排序方式在最壞情況下的比較次數相同,都是【n(n-1)/2】。堆排序的效率最高,是【nlog2n】。
★★ 希爾排序最壞情況下需要次比較【n1.5】。希爾排序屬于【插入類(lèi)排序法】。
已知數據表A中每個(gè)元素距最終位置不遠,為節省時(shí)間,應該采用的算法是【直接插入排序】。選擇排序、插入排序、快速排序、歸并排序中對內存要求最大的是【歸并排序】。
第二部分 軟件工程基礎 1、軟件工程基本概念軟件是包括【程序】、【數據】及【相關(guān)文檔】的完整集合,軟件是一種邏輯產(chǎn)品。軟件工程三要素包括【方法、工具。
計算機等級考試二級必須考公共基礎知識,計算機二級考核計算機基礎知識和使用一種高級計算機語(yǔ)言編寫(xiě)程序以及上機調試的基本技能。
考試科目:語(yǔ)言程序設計(C、C++、Java、VisualBasic、WEB)、數據庫程序設計(VisualFoxPro、Access、MySQL)、辦公軟件(MSOffice高級應用)共九個(gè)科目。新增"MySQL數據庫程序設計"、"WEB程序設計"、"MSOffice高級應用"三個(gè)科目。二級Delphi科目將從2013年上半年開(kāi)始停考,不再接受新考生報名,該次只接受補考考生報名,從第38次全國計算機等級考試(2013年9月)起,不再開(kāi)考。
考試形式:完全采取上機考試形式,各科上機考試時(shí)間均為120分鐘,滿(mǎn)分100分。總分達到60分,可以獲得合格證書(shū),沒(méi)有獲得合格證書(shū)的考生,不再安排補考,需以新考生身份報名參加考試。參加2013年3月全國計算機等級考試二級7個(gè)科目補考的老考生,仍按照傳統模式參加補考。
獲證條件:通過(guò)二級科目考試。
考核內容:二級定位為程序員,考核內容包括公共基礎知識和程序設計。所有科目對基礎知識作統一要求,使用統一的公共基礎知識考試大綱和教程。二級公共基礎知識在各科考試選擇題中體現。程序設計部分,主要考查考生對程序設計語(yǔ)言使用和編程調試等基本能力,在選擇題和操作題中加以體現。
題型及分值比例:①選擇題40題,40%;②程序設計題3題,60%。
上機考試環(huán)境及使用的軟件:全國計算機等級考試二級上機考試環(huán)境為Windows7簡(jiǎn)體中文版。各科目使用的軟件如下:
聲明:本網(wǎng)站尊重并保護知識產(chǎn)權,根據《信息網(wǎng)絡(luò )傳播權保護條例》,如果我們轉載的作品侵犯了您的權利,請在一個(gè)月內通知我們,我們會(huì )及時(shí)刪除。
蜀ICP備2020033479號-4 Copyright ? 2016 學(xué)習?shū)B(niǎo). 頁(yè)面生成時(shí)間:3.767秒