全國(guó)計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)復(fù)習(xí)(編輯修改稿)
2025-05-13 22:12 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 位置，直到全部記錄插入為止。(1) 直接插入排序 快速排序的基本思想：請(qǐng)查看相關(guān)資料。 對(duì)于長(zhǎng)度為n的線性表：在最壞情況下，直接插入排序比較次數(shù)為n(n1)/2。算法的時(shí)間復(fù)雜度為O(n2)。(2) 希爾排序 希爾排序的基本思想：請(qǐng)查看相關(guān)資料。 對(duì)于長(zhǎng)度為n的線性表：在最壞情況下希爾排序比較次數(shù)為O()。 選擇排序 選擇排序的基本思想是：每一遍在ni+1(i=1,2,…,n1)個(gè)待排序記錄中選取關(guān)鍵字最小的記錄作為有序序列中第i個(gè)記錄，直到全部記錄排完為止。(1) 直接選擇排序 選擇排序的基本思想：參見“C語(yǔ)言程序設(shè)計(jì)”或“VB程序設(shè)計(jì)”課件的相應(yīng)內(nèi)容動(dòng)畫。 在最壞情況下，直接選擇排序比較次數(shù)為n(n1)/2。(2) 堆排序 希爾排序的基本思想：請(qǐng)查看相關(guān)資料。 在最壞情況下，堆排序比較次數(shù)為O(nlog2n)。習(xí)題：（一）選擇題(單選)1. 下列敘述中正確的是( D )A）棧是“先進(jìn)先出”的線性表B）隊(duì)列是“先進(jìn)后出”的線性表C）循環(huán)隊(duì)列是非線性結(jié)構(gòu)D）有序線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2. 下列關(guān)于棧的敘述中正確的是( A )A) 棧頂元素最先被刪除 B) 棧頂元素最后才能被刪除C) 棧底元素永遠(yuǎn)不能被刪除 D) 以上三種說(shuō)法都不對(duì)3. 下列敘述中正確的是( B )A) 有一個(gè)以上根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不一定是非線性結(jié)構(gòu)B) 只有一個(gè)根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不一定是線性結(jié)構(gòu)C) 循環(huán)鏈表是非線性結(jié)構(gòu)D) 雙向鏈表是非線性結(jié)構(gòu)4. 支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是( A )A) 棧 B) 樹 C) 隊(duì)列 D) 二叉樹5. 某二叉樹有5個(gè)度為2的結(jié)點(diǎn)，則該二叉樹中的葉子結(jié)點(diǎn)數(shù)是( C )A）10 B）8 C）6 D）4提示：在任意二叉樹中，若度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2，則：n0= n2+1 即 n0(葉子結(jié)點(diǎn)數(shù))=5+1=66. 某二叉樹共有7個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)只有1個(gè)，則該二叉樹的深度為(假設(shè)根結(jié)點(diǎn)在第一層)( D )A) 3 B) 4 C) 6 D)77. 下列排序方法中，最壞情況下比較次數(shù)最少的是( D )A）冒泡排序 B）簡(jiǎn)單選擇排序 C）直接插入排序 D）堆排序8. 下列敘述中正確的是( A )A) 對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行查找，最壞的情況下需要的比較次數(shù)為nB) 對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行對(duì)分查找，最壞的情況下需要的比較次數(shù)為（n/2）C) 對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行對(duì)分查找，最壞的情況下需要的比較次數(shù)為(log2n)D) 對(duì)長(zhǎng)度為n的有序鏈表進(jìn)行對(duì)分查找，最壞的情況下需要的比較次數(shù)為(nlog2n)(二) 填空題1. 假設(shè)用一個(gè)長(zhǎng)度為50的數(shù)組（數(shù)組元素的下標(biāo)從0到49）作為棧的存儲(chǔ)空間，棧底指針bottom指向棧底元素，棧頂指針top指向棧頂元素，如果bottom=49,top=30(數(shù)組下標(biāo))，則棧中具有________個(gè)元素。 答案：202. 一個(gè)隊(duì)列的初始狀態(tài)為空?，F(xiàn)將元素A、B、C、D、E、F、1一次入隊(duì)，然后再一次退隊(duì)，則元素退隊(duì)的順序?yàn)開_______________________。答案：A、B、C、D、E、F、13. 設(shè)某循環(huán)隊(duì)列的容量為50，如果頭指針front=45(指向隊(duì)頭元素的前一個(gè)位置)，尾指針rear=10（指向隊(duì)尾元素），則該循環(huán)隊(duì)列中共有_____個(gè)元素。答案：154. 設(shè)二叉樹如下：ABCDEFGH對(duì)該二叉樹進(jìn)行后序遍歷的結(jié)果為________________________。答案：E、D、B、G、H、F、C、A5. 一棵二叉樹的中序遍歷結(jié)果為DBEAFC，前序遍歷結(jié)果為ABDECF，則后序遍歷結(jié)果為_________。答案：DEBFCA6. 有序線性表能進(jìn)行二分查找的前提是該線性表必須是________存儲(chǔ)。答案：順序二、軟件工程基礎(chǔ)計(jì)算機(jī)軟件是計(jì)算機(jī)系統(tǒng)中與硬件相互依存的另一部分，是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。軟件由兩部分組成：一是機(jī)器可執(zhí)行的程序和數(shù)據(jù)；二是機(jī)器不可執(zhí)行的，與軟件開發(fā)、運(yùn)行、維護(hù)、使用等有關(guān)的文檔。軟件的分類 軟件按功能可以分為：應(yīng)用軟件、系統(tǒng)軟件、支撐軟件(或工具軟件)。 應(yīng)用軟件：是為解決特定領(lǐng)域的應(yīng)用而開發(fā)的軟件。 系統(tǒng)軟件：是計(jì)算機(jī)管理自身資源，提高計(jì)算機(jī)使用效率并為計(jì)算機(jī)用戶提供各種服務(wù)的軟件。支撐軟件：是介于系統(tǒng)軟件和應(yīng)用軟件之間，協(xié)助用戶開發(fā)軟件的工具性軟件。軟件生命周期通常將軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過(guò)程稱為軟件生命周期。參見下圖： 結(jié)構(gòu)化分析方法結(jié)構(gòu)化分析的常用工具：數(shù)據(jù)流圖(DFD)：是描述數(shù)據(jù)處理過(guò)程的工具，是需求理解的邏輯模型的圖形表示，它直接支持系統(tǒng)的功能建模。數(shù)據(jù)字典(DD)：是結(jié)構(gòu)化分析方法的核心。判定樹判定表結(jié)構(gòu)化設(shè)計(jì)方法常見的過(guò)程設(shè)計(jì)工具：圖形工具：程序流程圖，NS圖，PAD圖(問(wèn)題分析圖)，HIPO表格工具：判定表。語(yǔ)言工具：PDL(偽碼)軟件設(shè)計(jì)的基本原理 1) 抽象：是一種思維工具，就是把事物本質(zhì)的共同特性提取出來(lái)而不考慮其他細(xì)節(jié)。 2) 模塊化：是指把一個(gè)待開發(fā)的軟件分解成若干小的簡(jiǎn)單的部分。如高級(jí)語(yǔ)言中的過(guò)程、函數(shù)、子程序等。每個(gè)模塊可以完成一個(gè)特定的子功能，各個(gè)模塊可以按一定的方法組裝起來(lái)成為一個(gè)整體，從而實(shí)現(xiàn)整個(gè)系統(tǒng)的功能。 3) 信息隱蔽：是指在一個(gè)模塊內(nèi)包含的信息(過(guò)程或數(shù)據(jù))，對(duì)于不需要這些信息的其他模塊來(lái)說(shuō)是不能訪問(wèn)的。4) 模塊獨(dú)立性：是指每個(gè)模塊只完成系統(tǒng)要求的獨(dú)立的子功能，并且與其他模塊的聯(lián)系最少且接口簡(jiǎn)單。模塊的獨(dú)立程度是評(píng)價(jià)設(shè)計(jì)好壞的重要度量標(biāo)準(zhǔn)。衡量軟件的模塊獨(dú)立性使用耦合性和內(nèi)聚性兩個(gè)定性的度量標(biāo)準(zhǔn)。內(nèi)聚性：是一個(gè)模塊內(nèi)部各個(gè)元素間彼此結(jié)合的緊密程度的度量。內(nèi)聚是從功能角度來(lái)度量模塊內(nèi)的聯(lián)系。內(nèi)聚性是信息隱蔽和局部化概念的自然擴(kuò)展。一個(gè)模塊的內(nèi)聚性越強(qiáng)則該模塊的模塊獨(dú)立性越強(qiáng)。作為軟件結(jié)構(gòu)設(shè)計(jì)的設(shè)計(jì)原則，要求每一個(gè)模塊的內(nèi)部都具有很強(qiáng)的內(nèi)聚性，它的各個(gè)組成部分彼此都密切相關(guān)。耦合性：耦合性是模塊間相互連接的緊密程度的度量。一個(gè)模塊與其他模塊的耦合性越強(qiáng)則該模塊的模塊獨(dú)立性越弱。原則上講，模塊化設(shè)計(jì)總是希望模塊間的耦合表現(xiàn)為非直接耦合方式。但是，由于問(wèn)題所固有的復(fù)雜性和結(jié)構(gòu)化設(shè)計(jì)的原則，非直接耦合往往是不存在的。耦合性與內(nèi)聚性是模塊獨(dú)立性的兩個(gè)定性標(biāo)準(zhǔn)，耦合性與內(nèi)聚性是相互聯(lián)系的。在程序結(jié)構(gòu)中，各模塊的內(nèi)聚性越強(qiáng)，則耦合性越弱。一般優(yōu)秀的軟件設(shè)計(jì)，應(yīng)盡量做到高內(nèi)聚，低耦合，即減弱模塊之間的耦合性和提高模塊內(nèi)的的內(nèi)聚性，有利于提高模塊的獨(dú)立性。軟件測(cè)試軟件測(cè)試是在軟件投入運(yùn)行前對(duì)軟件需求、設(shè)計(jì)、編碼的最后審核。軟件測(cè)試是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過(guò)程。軟件測(cè)試應(yīng)當(dāng)制定明確的測(cè)試計(jì)劃并按計(jì)劃執(zhí)行。軟件測(cè)試的目的：是發(fā)現(xiàn)錯(cuò)誤。軟件測(cè)試方法和技術(shù)：若從是否需要執(zhí)行被測(cè)軟件的角度，可以分為靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試方法。若按照功能劃分可以分為白盒測(cè)試和黑盒測(cè)試方法。靜態(tài)測(cè)試：包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量等。靜態(tài)測(cè)試不實(shí)際運(yùn)行軟件，主要通過(guò)人工進(jìn)行。動(dòng)態(tài)測(cè)試：是基于計(jì)算機(jī)的測(cè)試，是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過(guò)程。需要精心設(shè)計(jì)一批測(cè)試用例，并利用這些測(cè)試用例去運(yùn)行程序，以發(fā)現(xiàn)程序錯(cuò)誤的過(guò)程。測(cè)試用例的格式為： [
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1