全國計算機二級內(nèi)容學習

全國計算機等級考試二級公共基礎(chǔ)知識數(shù)據(jù)結(jié)構(gòu)與算法一、基本概念：數(shù)據(jù)(Data識別、存儲和加工處理的物理符號。包括和多媒體類型的數(shù)據(jù)(如：聲音、動畫、圖像)。數(shù)據(jù)元素(DataElement)：是數(shù)據(jù)的基本單位，有時也稱為元素、結(jié)點、頂點、記錄，可以有若干個數(shù)據(jù)項（字段、域、屬性）組成。數(shù)據(jù)結(jié)構(gòu)（DataStructure：指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。其包括三個部分：1、邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系2、存儲結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計算機存儲器內(nèi)的表示。3、數(shù)據(jù)的運算（算法操作數(shù)據(jù)的邏輯結(jié)構(gòu)有兩大類：第1頁，共36頁全國計算機等級考試二級公共基礎(chǔ)知識1、線性結(jié)構(gòu)：例：一維數(shù)組、鏈表、棧、隊列、串2、非線性結(jié)構(gòu)：接后繼。例：多維數(shù)組、廣義表、樹、圖1、順序存儲方法：該方法是將邏輯上相鄰的結(jié)點存儲在物理數(shù)組來實現(xiàn)的。2、鏈接存儲方法：該方法不要求邏輯上相鄰的結(jié)點在物理位3、索引存儲方法：該方法通常是在存儲結(jié)點信息的同時，還建第2頁，共36頁全國計算機等級考試二級公共基礎(chǔ)知識4、散列存儲方法：該方法的基本思想是根據(jù)結(jié)點的關(guān)鍵字直列函數(shù)算法的基本特征：1、可行性(Effectiveness)：針對實際問題而設(shè)計的算法，執(zhí)行后能夠得到滿意的結(jié)果。2、確定性(Definiteness)：算法中的每一義性。3、有窮性(Finiteness)：算法必須在有限終止。n第3頁，共36頁全國計算機等級考試二級公共基礎(chǔ)知識空間，它也是問題規(guī)模n的函數(shù)。二、線性表：線性表(Linearn(n>=0)個數(shù)據(jù)元素(結(jié)點)a1

,a,···,a2 3

組成的有限序列。對于非空的線性表，有且僅有

，它沒有直接前趨；有且1

，它沒有直接后繼；n其余的結(jié)點有且僅有一個直接前趨結(jié)點和一個直接后繼結(jié)點。線性表的存儲結(jié)構(gòu)：1、順序存儲(SequentialList的結(jié)點按邏輯次序依次存放在一組地址連2、鏈式存儲(LinkedList)：邏輯上相鄰的結(jié)點，物理上也相鄰，存儲單元可以是連續(xù)的，也可以是不連續(xù)的，在存儲每個結(jié)點值的同時，還存儲指向其后繼結(jié)點的地址，用這種方法存儲的線性表稱為鏈表。常見的運算有：表的初始化、求表的長度、取表中的第i第4頁，共36頁全國計算機等級考試二級公共基礎(chǔ)知識順序表和鏈表的比較：1、基于空間的考慮：A、順序表的存儲空間是靜態(tài)分配的，而鏈表的存儲空間是動態(tài)分配的。B、順序表占的存儲空間必須是連續(xù)的，而鏈表占的存儲空間可以是連續(xù)的，也可是不連續(xù)的C12、基于時間的考慮：AB、順序表是隨機存取結(jié)構(gòu)，它的存取時間為O(1)，而鏈表需從頭結(jié)點順著鏈掃描鏈表?？傊?，當線性表的長度變化不大，易于事先確定其大小時，為了節(jié)約存儲空間，宜第5頁，共36頁全國計算機等級考試二級公共基礎(chǔ)知識例：關(guān)于線性表的描述中，錯誤的是（ A、線性表是線性結(jié)構(gòu)B、線性表的順序存儲結(jié)構(gòu)必須占用一片連續(xù)的存儲單元C、線性表是單鏈表 D、線性表的鏈存儲結(jié)構(gòu)，不必占用一片連續(xù)的存儲單用數(shù)組表示線性表的優(yōu)點是（ ）A、便于插入和刪除操作 B、于隨機存取C、可以動態(tài)地分配存儲空間 D、需要占用一片連續(xù)的存儲空間三、棧：棧(Stack)：是限制僅在表的一端進行插入和刪除運算的線性表，通常稱插入、刪第6頁，共36頁全國計算機等級考試二級公共基礎(chǔ)知識除的這一端為棧頂(Top)，另一端稱為棧底(Bottom)。當表中沒有元素時稱為空棧。是一種后進先出的線性表，又稱為LIFO表。棧的基本運算有：棧的初始化、判?？?、判棧滿、進棧、出棧等棧的存儲：順序存儲、鏈式存儲例：若進棧的輸入序列是ABCD并且在它們進棧的過程中可以進行出棧操作，則不可能出現(xiàn)的出棧序列是（ ）A、EDCBA B、DECBA C、DCEAB D、ABCDE四、隊列：隊列(Queue)：也是一種運算受限的線性頭(Front)(Rear（類似于生活中的購物排隊第7頁，共36頁全國計算機等級考試二級公共基礎(chǔ)知識FIFO隊列的基本運算：隊列的初始化、判隊空、判隊滿、入隊、出隊隊列的存儲實現(xiàn)：順序存儲、鏈式存儲例：一個隊列的入隊序列是1，2，3，4，則隊列的輸出序列是（ ）A、4，3，2，1 B、1，2，3，C、1，4，3，2 D、3，2，4，1五、串：串限序列。串中所包含的字符個數(shù)稱為該串的長度。串中任意個連續(xù)字符組成的子序列稱為注：空串是任意串的子串，任意串是其自身的子串串有串常量、串變量之分：1、串常量在程序中只能被引用但不能改第8頁，共36頁全國計算機等級考試二級公共基礎(chǔ)知識變其值，即只能讀不能寫。2、串變量其值是可以改變的。串的基本運算：求串長、串復(fù)制、串聯(lián)接、串比較、字符定位、六、樹（非線性結(jié)構(gòu)：樹n(n>=0T(n=01、有且僅有一個特定的稱為根(Root)的結(jié)點2m(m>=0T1，T2，…….，Tm，其中每個子集本身又是一棵樹，并稱其為根的子樹(Subtree)。表示的，結(jié)點的名字一般是寫在圓圈旁邊，有時亦可寫在圓圈內(nèi)。度該結(jié)點的度。一棵樹的度是指該樹中結(jié)點的最大度數(shù)。第9頁，共36頁全國計算機等級考試二級公共基礎(chǔ)知識葉子端結(jié)點分支結(jié)點支結(jié)點。樹中某個結(jié)點的子樹之根稱為該結(jié)點的孩子(Child)結(jié)點或子結(jié)點，相應(yīng)的該結(jié)(Parents父結(jié)點。(Sibling)(Level)層數(shù)為1,其余結(jié)點的層數(shù)等于其雙親結(jié)1.樹中結(jié)點的最大層數(shù)稱為樹的高度(Height)或深度(Depth).森林(Forestm(m>=0)棵互不相交的就變?yōu)橐豢脴洹６鏄?Binaryn(n>=0(n=0)，或者由第10頁，共36頁全國計算機等級考試二級公共基礎(chǔ)知識一個根結(jié)點及兩棵互不相交的、分別稱作這個根的左子樹和右子樹的二叉樹組成。二叉樹中，每個結(jié)點最多只能有兩棵子樹，并且有左右之分。二叉樹的五種基本形態(tài)：例：具有3個結(jié)點的二叉樹有幾種形態(tài)。滿二叉樹(FullBinary為k2k-1完全二叉樹(CompleteBinary一棵二叉樹至多只有最下面的兩層上結(jié)2，并且最下一層上的則此二叉樹稱為完全二叉樹。二叉樹的性質(zhì)：1i2i-1(i>=1)k2k-1點(k>=1)3：在任意一棵二叉樹中，若終端結(jié)點第11頁，共36頁全國計算機等級考試二級公共基礎(chǔ)知識的個數(shù)為n

20

2

=n+10 24n為[lgn]+1(取下整)或[lg(n+1)](整)。18最小高度215點數(shù)二叉樹的遍歷：遍歷(Traversal)：是指沿著某條搜索路線，依次對樹中每個結(jié)點均做一次且僅做一次訪問。（又稱為先序遍歷、先根遍歷）1、訪問根結(jié)點；2、前序遍歷左子樹；3、前序遍歷右子樹。（又稱為中根遍歷）1、中序遍歷左子樹；第12頁，共36頁全國計算機等級考試二級公共基礎(chǔ)知識2、訪問根結(jié)點；3、中序遍歷右子樹。（又稱為后根遍歷）1、后序遍歷左子樹；2、后序遍歷右子樹；3、訪問根結(jié)點。例：已知一棵二叉樹的中序遍歷序列是：FDGBACHE，其后序遍歷序列是：FGDBHECA求其前序遍歷序列。ABDGCFK，DGBAFCK，則結(jié)點的后序遍歷序列是（）A、ACFKDBG B、GDBFKCA C、KCFAGDB D、ABCDFKG七、排序(Sort)：所謂排序，就是指整理文件中的記錄，使（或遞減冒泡排序(BubbleSorting)：通過對待排序序列從后向前或從前向后第13頁，共36頁全國計算機等級考試二級公共基礎(chǔ)知識較大的元素逐漸從前部移向后部或較小的（從下標較大的單元移向下標較小的單元。直接選擇排序(SelectionSorting)：直接插入排序(InsertionSorting)：每次將一個待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子文件中的適當位置，直到全部記錄插入完成為止?？焖倥判?QuickSorting)個元素)，通過一趟排序，將待排元素分至整個序列有序。各種內(nèi)部排序方法的比較第14頁，共36頁排序方法直接插入直接選擇冒泡快速堆排序方法直接插入直接選擇冒泡快速堆時間復(fù)雜度間間間雜度O(n)O(n2)O(n2)O(1)O(n2)O(n2)O(n2)O(1)O(n)O(n2)O(n2)O(1)O(nlgn)O(nlgn)O(n2)O(lgn)O(nlgn)O(nlgn)O(nlgn)O(1)n序，在最壞情況下，要進行交換的次數(shù)是（）A、n(n+1)/2 B、n(n-1)/2 C、第15頁，共36頁全國計算機等級考試二級公共基礎(chǔ)知識n*n/2 D、n(n+1)/2-1對n個元素進行冒泡排序過程中最好況下的時間復(fù)雜性為（ ）AO(1) BD、O(n)

n) CO(n2)2n情況下的時間復(fù)雜性為（ ）A、O(1) B、O(lgn) CO(n2) D、O(nlgn)八、查找(Searching)：KnK順序查找(SequentialSearch)KKK第16頁，共36頁全國計算機等級考試二級公共基礎(chǔ)知識序查找即適用順序存儲結(jié)構(gòu)，又適用鏈式存儲結(jié)構(gòu)。目)(1+2+3+4+··+n)/n=(n+1)/2二分查找(BinarySearch要求線性表是有序表目)nn

lg(n1當nlg(n+1)-1表示軟件工程基礎(chǔ)第17頁，共36頁全國計算機等級考試二級公共基礎(chǔ)知識一、基本概念：軟件(Software產(chǎn)品)，指的是計算機中程序及其說明程文字或圖形資料。軟件危機的表現(xiàn)：1、軟件需求的增長得不到滿足2、軟件開發(fā)成本和進度無法控制3、軟件質(zhì)量難以保證4、軟件不可維護或維護程度非常低5、軟件成本不斷提高6、軟件開發(fā)生產(chǎn)效率的提高趕不上硬件的發(fā)展和應(yīng)用需求的增長軟件工程(SoftwareEngineering程化的方法、科學知識和技術(shù)原理來定義、開發(fā)、維護軟件的一門學科。軟件工程的目標：付出較低的開發(fā)成本；達到要求的軟件功能；取得較好的軟件性能；開發(fā)的軟件易第18頁，共36頁全國計算機等級考試二級公共基礎(chǔ)知識于移植；需要較低的維護費用；能按時完成開發(fā)任務(wù)，及時交付使用；開發(fā)的軟件可靠性高。軟件工程研究的主要內(nèi)容是軟件開發(fā)技術(shù)和軟件開發(fā)管理兩個方面。要求開始直到該軟件報廢(停止運行)為止的整個時期。中各種活動如何執(zhí)行的模型。的模型瀑布模型是將軟件生存周期各個活動規(guī)定測試和維護幾個階段。例：下列描述中正確的是（）A、程序就是軟件 B軟件開不受計算機系統(tǒng)的限制C、軟件既是邏輯實體，又是物理實體第19頁，共36頁全國計算機等級考試二級公共基礎(chǔ)知識D、軟件是程序、數(shù)據(jù)與相關(guān)文檔的集合二、軟件可行性研究與項目開發(fā)計劃：在盡可能短的時間內(nèi)確定該軟件項目是否能夠開發(fā)，是否值得去開發(fā)?？尚行匝芯康娜蝿?wù)：A、技術(shù)可行性B、經(jīng)濟可行性C、社會可行性（法律可行性）1、確定項目規(guī)模和目標2、研究正在運行的系統(tǒng)3、建立新系統(tǒng)的高層邏輯模型4、導出和評價各種方案5、推薦可行的方案6、編寫可行性研究報告三、軟件需求分析：需求分析是指開發(fā)人員要準確理解用戶第20頁，共36頁全國計算機等級考試二級公共基礎(chǔ)知識形式的需求陳述轉(zhuǎn)化為完整的需求定義，再由需求定義轉(zhuǎn)換到相應(yīng)的形式功能規(guī)約（需求規(guī)格說明）的過程。需求分析的基本任務(wù)：1、問題識別ABCD、用戶界面需求2、分析與綜合，導出軟件的邏輯模型3、編寫文檔(需求規(guī)格說明書)需求分析的方法：1、結(jié)構(gòu)化分析(StructuredAnalysis面向數(shù)據(jù)流進行需求分析的方法。SA方法利用圖形等半形式化的描述方式表達需求，主要描述工具：A、數(shù)據(jù)流圖(DFDSAB、數(shù)據(jù)字典(DD)：用以定義數(shù)據(jù)流圖中的各個成分的具體含義，為系統(tǒng)的分析、設(shè)計及維護提供了有關(guān)元素的一致的定義和詳?shù)?1頁，共36頁全國計算機等級考試二級公共基礎(chǔ)知識細的描述。C、描述加工邏輯的結(jié)構(gòu)化語言、判定表、判定樹2IDEFICAMDefinition是一種用于進行復(fù)雜系統(tǒng)分析和設(shè)計的提出來的。3、面向?qū)ο蠓治龇椒?OOP)：封裝和多態(tài)性等特征。例：軟件開發(fā)的結(jié)構(gòu)化分析方法中，常用的描述軟件功能需求的工具是（ ）A、業(yè)務(wù)流程圖、處理說明 B軟件流程圖、模塊說明C、數(shù)據(jù)流程圖、數(shù)據(jù)字典 D系統(tǒng)流程圖、程序編碼四、軟件概要設(shè)計：將軟件需求轉(zhuǎn)換為軟件表示的過程。軟件概要設(shè)計的基本任務(wù)：1、設(shè)計軟件系統(tǒng)結(jié)構(gòu)第22頁，共36頁全國計算機等級考試二級公共基礎(chǔ)知識2、數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫設(shè)計（邏輯設(shè)計、物理設(shè)計：3、編寫概要設(shè)計文檔：4、評審：軟件設(shè)計的方法：模塊化：模塊在程序中是數(shù)據(jù)說明、可執(zhí)子程序等。模塊獨立性指每個模塊只完成系統(tǒng)要求和內(nèi)聚性各模塊間相互聯(lián)系緊密程度的一種度量。模塊之間聯(lián)系越緊密，其耦合性就越強，模塊的獨立性則越差。間、程序段之間)彼此結(jié)合的緊密程度的度量。第23頁，共36頁全國計算機等級考試二級公共基礎(chǔ)知識低耦合。例：為了使模塊盡可能獨立，要求（）A的耦合程序要盡量強B、模塊的內(nèi)聚程序要盡量高，且各模塊間的耦合程序要盡量弱C的耦合程序要盡量弱D的耦合程序要盡量強五、軟件詳細設(shè)計：主要確定每個模塊具體執(zhí)行過程軟件詳細設(shè)計的基本任務(wù)：1、為每個模塊進行詳細的算法設(shè)計：2、為模塊內(nèi)的數(shù)據(jù)結(jié)構(gòu)進行設(shè)計：3、對數(shù)據(jù)庫進行物理設(shè)計：4、輸入、輸出格式設(shè)計5、編寫詳細設(shè)計說明書：6、評審：詳細設(shè)計常用三種工具：第24頁，共36頁全國計算機等級考試二級公共基礎(chǔ)知識PAD表格(判定表)、語言(過程設(shè)計語言，又稱為偽碼)六、軟件編碼：主要是將詳細設(shè)計得到的處理過程描述轉(zhuǎn)換為基于某種計算機語言的程序常用的計算機語言：PascalC、C++、Java七、軟件測試：軟件測試的目的：1、軟件測試是為了盡可能多地發(fā)現(xiàn)程序中的錯誤而執(zhí)行程序的過程。2、一個好的測試用例能夠發(fā)現(xiàn)至今尚未發(fā)現(xiàn)的錯誤。3、一個成功的測試是發(fā)現(xiàn)了至今尚未發(fā)現(xiàn)的錯誤的測試。軟件測試的原則：第25頁，共36頁全國計算機等級考試二級公共基礎(chǔ)知識1、測試用例應(yīng)由輸入數(shù)據(jù)和預(yù)期的輸出數(shù)據(jù)兩部分組成。2、測試用例不僅選用合理的輸入數(shù)據(jù)，還要選擇不合理的輸入數(shù)據(jù)3、除了檢查程序是否做了它應(yīng)該做的事4、應(yīng)制定測試計劃并嚴格執(zhí)行，排除隨意性5、長期保留測試用例6、對發(fā)現(xiàn)錯誤較多的程序段，應(yīng)進行更深入的測試7、程序員避免測試自己的程序軟件測試方法：1、靜態(tài)測試：是指被測試程序不在機器上運行，而是采用人工檢測和計算機輔助靜態(tài)分析的手段對程序進行檢測。2、動態(tài)測試：是指通過運行程序發(fā)現(xiàn)錯誤A、黑盒測試法(功能測試)：第26頁，共36頁全國計算機等級考試二級公共基礎(chǔ)知識B、白盒測試法(結(jié)構(gòu)測試)：判定覆蓋等軟件測試的實施：1、單元測試：單元測試是對軟件設(shè)計的最小單位——模塊(程序單元)進行正確性檢驗測試，主要針對模塊的以下五個基本特征進行測試：A、模塊接口B、局部數(shù)據(jù)結(jié)構(gòu)：CD、錯誤處理測試：E、邊界條件：2、集成測試：集成測試是指在單元測試的基礎(chǔ)上，將所有模塊按照設(shè)計要求組裝成一個完整的系統(tǒng)進行的測試，故也稱組裝測試或聯(lián)合測試。主要方法有兩種：非漸增式測試：首先對每個模塊分別進行第27頁，共36頁全國計算機等級考試二級公共基礎(chǔ)知識組裝在一起進行測試。漸增式測試：逐個把未經(jīng)過測試的模塊組裝到已經(jīng)過測試的模塊上去，進行集成測試，每加入一個新模塊進行一次集成測試，重復(fù)此過程直至程序組裝完畢。3、確認測試：查軟件的功能與性能是否與需求規(guī)格說明是確認測試的基礎(chǔ)。4、系統(tǒng)測試：系統(tǒng)測試是通過測試確認的軟件作為整程序調(diào)試：調(diào)試是在進行了成功的測試之后才開始的工作，目的是確定錯誤的原因和位置，并改正錯誤，又稱為糾錯。第28頁，共36頁全國計算機等級考試二級公共基礎(chǔ)知識例：軟件測試的目的是（ ）AB、找出軟件系統(tǒng)中存在的所有錯誤CD、證明軟件系統(tǒng)中存在錯誤試法主要是用于測試（）A、結(jié)構(gòu)合理性BC、程序正確性D邏輯八、軟件維護：進去；環(huán)境的變化對程序進行變動等。軟件維護的內(nèi)容有四類：1、校正性維護：為了識別和糾正錯誤，修改軟件性能上的第29頁，共36頁全國計算機等級考試二級公共基礎(chǔ)知識2、適應(yīng)性維護：件、數(shù)據(jù))的變化而修改軟件的過程稱為適25%3、完善性維護：增加軟件功能、增強軟件性能、提高軟件運行效率而進行的維護活動稱為完善性維護，其占整個維護工作的50%4、預(yù)防性維護：為了提高軟件的可維護性和可靠性而對軟件進行的修改稱為預(yù)防性維護，其占整個維護工作的4%例：軟件維護是指（ ）A、維護軟件正常運行 B軟件的置更新CD、軟件開發(fā)期的一個階段軟件生命周期中所花費用最多的階段是（）A、詳細設(shè)計 B、軟件編碼第30頁，共36頁全國計算機等級考試二級公共基礎(chǔ)知識C、軟件測試 D、軟件維護數(shù)據(jù)庫原理基礎(chǔ)一、基本概念：存儲、檢索和維護提供操作手段其經(jīng)歷了以下階段：1、人工管理2、文件系統(tǒng)3、數(shù)據(jù)庫系統(tǒng)4、分布式數(shù)據(jù)庫系統(tǒng)階段5、面向?qū)ο蟮臄?shù)據(jù)庫系統(tǒng)階段數(shù)據(jù)庫僅包括數(shù)據(jù)本身，還包括事物之間的聯(lián)系。第31頁，共36頁全國計算機等級考試二級公共基礎(chǔ)知識數(shù)據(jù)庫應(yīng)用系統(tǒng)某一類實際應(yīng)用的應(yīng)用軟件系統(tǒng)。(DBMS)：對數(shù)據(jù)庫的建立、使用和維護進行管理和配置的軟件系統(tǒng)。是數(shù)據(jù)庫系統(tǒng)的核心數(shù)據(jù)庫系統(tǒng)(DBS)合、數(shù)據(jù)庫管理系統(tǒng)及相關(guān)軟件、數(shù)據(jù)庫管理員和用戶組成。數(shù)據(jù)庫系統(tǒng)的特點：采用特定的數(shù)據(jù)模型統(tǒng)一的數(shù)據(jù)控制功能實體：客觀存在并且可以相互區(qū)別的事物稱為實體。的屬性。實體集：同類型的實體的集合稱為實體集。稱為實體型。第32頁，共36頁全國計算機等級考試二級公共基礎(chǔ)知識例：數(shù)據(jù)庫管理系統(tǒng)能實現(xiàn)對數(shù)據(jù)庫中數(shù)據(jù)的查詢、插入、修改和刪除，這類功能稱為（）A、數(shù)據(jù)定義功能BC、數(shù)據(jù)操縱功能D、數(shù)據(jù)控制功能聯(lián)系的類型:1、一對一聯(lián)系：表現(xiàn)為主表中的每一條記錄只與相關(guān)表中的一條記錄相關(guān)聯(lián)。例如：班級與班長，學校與校長2記錄與相關(guān)表中的多條記錄相關(guān)聯(lián)。3、多對多聯(lián)系：表現(xiàn)