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