全國(guó)計(jì)算機(jī)等級(jí)考試--二級(jí)公共基礎(chǔ)知識(shí)(ppt-100)(編輯修改稿)
2025-09-01 02:45 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 4 2 8 65 1 7 3 1 6 9 4 2 8 61 5 3 1 6 7 4 2 8 6 91 5 3 1 6 7 4 2 8 6 91 1 5 3 2 6 7 4 6 8 91 1 5 3 2 6 7 4 6 8 91 1 3 2 5 6 4 6 7 8 91 1 3 2 5 6 4 6 7 8 91 1 2 3 4 5 6 6 7 8 9第一遍 (從前向后 ) 第一遍 (從后向前 ) 第二遍 (從前向后 ) 第二遍 (從后向前 ) 快速排序 ? 基本思想：從線性表中選取一個(gè)元素，設(shè)為 T，將線性表后面小于 T的元素移動(dòng)到前面，將前面大于 T的元素移動(dòng)到后面，將線性表分為兩個(gè)部分 (子表 )， T放到分界線的位置，這個(gè)過(guò)程稱(chēng)為線性表的分割，通過(guò)一次分割，就以 T為分界將線性表分為兩個(gè)子表，前面的子表中的所有元素均不大于 T，而后面子表中的元素均不小于 T。按照上述原則對(duì)子表繼續(xù)進(jìn)行分割，直到子表為空，則整個(gè)線性表有序。 無(wú)序線性表分 割≤ T≥ TT分 割分 割? ? ? ? 快速排序 ? 操作步驟： ? 首先，在表的第一個(gè)元素、最后一個(gè)元素和中間元素中選取一個(gè)中值，設(shè)為 P(k)，并將 P(k)賦值給 T，再將表中的第一個(gè)元素移到 P(k) 的位置。設(shè)兩個(gè)指針 i， j分別指向表的起始和最后位置，反復(fù)操作以下兩步： ① 將 j逐漸減小，并逐次比較 P(j)和 T，直到發(fā)現(xiàn)一個(gè) P(j)T為止，并將 P(j)移到 P(i)的位置上。 ② 將 i逐漸增大，并逐次比較 P(i)和 T，直到發(fā)現(xiàn)一個(gè) P(i)T為止，并將 P(i)移到 P(j)的位置上。 ? 上述兩步操作交替進(jìn)行，直到 i和 j指向同一個(gè)位置，再將T移動(dòng)到 P(i)的位置上，完成一次分割。 31 68 45 90 23 39 54 12 87 76 31 暫存樞軸記錄 T： low high high high 12 12 low 68 68 high high high 23 23 low 45 45high high 31 31 快速排序的一次分割過(guò)程 31 插入類(lèi)排序 ? 簡(jiǎn)單插入排序 ? 基本思想：將待排序列表分成兩部分：已排序部分和未排序部分。每次掃描將未排序列表中的第一個(gè)元素取出并插入到已排序列表中的合適位置。包含 n個(gè)元素的列表最多需要 n1次掃描。 簡(jiǎn)單插入排序示例 原始序列 第 1趟 第 2趟 第 3趟 第 4趟 第 5趟 希爾排序 ? 基本思想：將整個(gè)無(wú)序序列分割成若干個(gè)小的子序列分別進(jìn)行插入排序。 ? 子序列的分割方法：將相隔某個(gè)增量 h的元素構(gòu)成一個(gè)子序列，在排序過(guò)程中，逐次減小這個(gè)增量，最后當(dāng) h減到 1時(shí)，進(jìn)行一次插入排序，排序完成。 ? 增量序列一般取 ht=n/2k(k=1,2… [log2n]) 希爾排序 7 1 9 2 4 1 3 3 1 8 8 2 1 8 4 4 6 3 5 2 97 1 8 2 4 1 3 5 8 8 2 1 9 4 4 6 3 3 1 2 97 5 8 1 3 1 8 2 4 6 3 1 9 2 9 8 2 3 1 4 45 7 8 1 3 1 8 1 9 2 4 2 9 3 1 4 4 6 3 8 2h=6 h=1 h=3 完成 選擇類(lèi)排序 ? 簡(jiǎn)單選擇排序 ? 基本思想：將待排序列表分成兩部分：已排序部分和未排序部分。找到未排序部分中的最小元素并把它和未排序部分中的第一個(gè)元素進(jìn)行交換。經(jīng)過(guò)一次選擇和交換，列表中已排序部分增加一個(gè)元素，未排序部分減少一個(gè)元素。每次把一個(gè)元素從未排序部分移動(dòng)到已排序部分稱(chēng)為完成一次 分類(lèi)掃描 或稱(chēng)為 一趟排序 。 ? 一個(gè)包含 n個(gè)元素的列表需要進(jìn)行 n1次掃描完成排序。 簡(jiǎn)單選擇排序示例 原始序列 第 1趟 第 2趟 第 3趟 第 4趟 第 5趟 第二章 程序設(shè)計(jì)基礎(chǔ) (15%) ? 考試大綱 ? 1. 程序設(shè)計(jì)方法與風(fēng)格。 2. 結(jié)構(gòu)化程序設(shè)計(jì)。 3. 面向?qū)ο蟮某绦蛟O(shè)計(jì)方法，對(duì)象，方法，屬性及繼承與多態(tài)性。 知識(shí)點(diǎn)歸納 ? 程序設(shè)計(jì)方法 ? 程序設(shè)計(jì)是一門(mén)技術(shù)，需要相應(yīng)的理論、方法和工具來(lái)支持。就程序設(shè)計(jì)方法和技術(shù)的發(fā)展而言，主要經(jīng)歷了結(jié)構(gòu)化的程序設(shè)計(jì)和面向?qū)ο蟮某绦蛟O(shè)計(jì)階段。 ? 在程序設(shè)計(jì)中，通常采用 “ 自頂向下，逐步求精 ” 的方法，即把一個(gè)模塊的功能逐步分解，細(xì)化為一系列具體的步驟，進(jìn)而轉(zhuǎn)換成一系列用某種程序設(shè)計(jì)語(yǔ)言編寫(xiě)的程序。 程序設(shè)計(jì)風(fēng)格 ? 除了程序設(shè)計(jì)設(shè)計(jì)方法和技術(shù)之外，程序風(fēng)格也是非常重要的。良好的程序設(shè)計(jì)風(fēng)格概括起來(lái)包括以下及格方面： ? 源程序文檔化 ? 數(shù)據(jù)說(shuō)明的方法 ? 語(yǔ)句的結(jié)構(gòu) ? 輸入和輸出 程序設(shè)計(jì)風(fēng)格 ? 源程序文檔化 ? 標(biāo)識(shí)符的命名 ? 程序的注釋 ? 序言性注釋 ? 功能性注釋 ? 程序的視覺(jué)組織 ? 數(shù)據(jù)的說(shuō)明 ? 數(shù)據(jù)說(shuō)明的次序應(yīng)該規(guī)范化 ? 說(shuō)明語(yǔ)句中變量的安排有序化 ? 使用注釋說(shuō)明復(fù)雜的數(shù)據(jù)結(jié)構(gòu) 程序設(shè)計(jì)風(fēng)格 ? 語(yǔ)句結(jié)構(gòu) ? 在一行內(nèi)只寫(xiě)一條語(yǔ)句 ? 程序編寫(xiě)應(yīng)優(yōu)先考慮清晰性 ? 除非對(duì)效率有特殊要求，程序編寫(xiě)要做到清晰第一，效率第二 ? 首先要保證程序正確，然后才要求提高速度 ? 避免使用臨時(shí)變量而使程序的可讀性下降 ? 避免不必要的轉(zhuǎn)移 ? 盡可能使用庫(kù)函數(shù) ? 避免使用復(fù)雜的條件語(yǔ)句 ? 盡量減少使用 “ 否定 ” 條件的條件語(yǔ)句 ? 數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡(jiǎn)化 ? 要模塊化，使模塊功能盡可能單一化 ? 利用信息隱蔽，確保每一個(gè)模塊的獨(dú)立性 ? 從數(shù)據(jù)出發(fā)構(gòu)造程序 ? 不要修補(bǔ)不好的程序，要重寫(xiě)編寫(xiě) 程序設(shè)計(jì)風(fēng)格 ? 輸入和輸出 ? 對(duì)所有輸入數(shù)據(jù)檢驗(yàn)合法性 ? 檢查輸入項(xiàng)的各種重要組合的合法性 ? 輸入格式要簡(jiǎn)單，以使輸入的步驟和操作盡可能簡(jiǎn)單 ? 輸入數(shù)據(jù)時(shí)，應(yīng)允許使用自由格式 ? 應(yīng)允許缺省值 ? 輸入一批數(shù)據(jù)時(shí)，最好使用輸入結(jié)束標(biāo)志 ? 在以交互式輸入 /輸出方式進(jìn)行輸入時(shí)，要在屏幕上使用提示符明確提示輸入的請(qǐng)求，同時(shí)在數(shù)據(jù)輸入結(jié)束時(shí)，應(yīng)在屏幕上給出狀態(tài)信息 ? 當(dāng)程序設(shè)計(jì)語(yǔ)言對(duì)輸入格式有嚴(yán)格要求時(shí)，應(yīng)保持輸入格式與輸入語(yǔ)句的一致性；給所有的輸出加注釋?zhuān)⒃O(shè)計(jì)輸出報(bào)表格式。 結(jié)構(gòu)化程序設(shè)計(jì) ? 結(jié)構(gòu)化程序設(shè)計(jì)的原則 ? 自頂向下。程序設(shè)計(jì)時(shí)，應(yīng)先考慮總體，后考慮細(xì)節(jié)；先考慮全局目標(biāo)，后考慮局部目標(biāo)。不要一開(kāi)始就過(guò)多追求細(xì)節(jié)，先從最上層總目標(biāo)開(kāi)始設(shè)計(jì)，逐步使問(wèn)題具體化。 ? 逐步求精。對(duì)復(fù)雜的問(wèn)題，應(yīng)設(shè)計(jì)一些子目標(biāo)過(guò)渡，逐步細(xì)化。 ? 模塊化。一個(gè)復(fù)雜問(wèn)題肯定是有若干簡(jiǎn)單問(wèn)題構(gòu)成。模塊化是把程序要解決的總目標(biāo)分解為分目標(biāo)，再進(jìn)一步分解為具體的小目標(biāo)，每個(gè)小目標(biāo)成為一個(gè)模塊。 ? 嚴(yán)格限制 GOTO語(yǔ)句的使用。 結(jié)構(gòu)化程序設(shè)計(jì)的基本結(jié)構(gòu)和特點(diǎn) ? 程序由一些基本結(jié)構(gòu)組成，任何一個(gè)程序都可以用三種基本控制結(jié)構(gòu)組成：順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)，并且具有如下特點(diǎn)：?jiǎn)稳肟?、單出口、結(jié)構(gòu)中無(wú)死循環(huán)，程序中三種基本控制結(jié)構(gòu)之間形成順序執(zhí)行關(guān)系。 ? 一個(gè)大型程序應(yīng)按功能分割成一些模塊，并把這些模塊按層次關(guān)系進(jìn)行組織。 ? 在程序設(shè)計(jì)時(shí)應(yīng)采用自頂向下、逐步細(xì)化的實(shí)施方法。 面向?qū)ο蟪绦蛟O(shè)計(jì) ? 面向?qū)ο蠓椒ǖ幕靖拍? 、類(lèi)和屬性 在面向?qū)ο蟪绦蛟O(shè)計(jì)中，對(duì)象是程序的基本單位。對(duì)象可以表示客觀世界中的任何實(shí)體，是對(duì)問(wèn)題域中某個(gè)實(shí)體的抽象。每個(gè)對(duì)象可以用它本身的一組屬性和它可以執(zhí)行的一組操作來(lái)定義。類(lèi)是對(duì)一組具有共同屬性和相似行為的對(duì)象的一種抽象，描述了屬于該類(lèi)的所有對(duì)象的性質(zhì)。 方法有稱(chēng)為操作或服務(wù)，它描述了對(duì)象執(zhí)行的功能，若通過(guò)消息傳遞，還可為其他對(duì)象使用。 面向?qū)ο蠓椒ǖ幕靖拍? ：繼承是對(duì)象方法的一個(gè)重要特征。指一個(gè)類(lèi) (子類(lèi) )直接使用另一個(gè)類(lèi) (父類(lèi) )的所有屬性和方法。它可以減少相
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號(hào)-1