【文章內(nèi)容簡介】 ? 交換類排序法： ? （ 1）冒泡排序法，需要比較的次數(shù)為 n(n1)/2； ? （ 2）快速排序法。 ? 插入類排序法： ? （ 1）簡單插入排序法，最壞情況需要 n(n1)/2次比較； ? （ 2）希爾排序法，最壞情況需要 O()次比較。 ? 選擇類排序法： ? （ 1）簡單選擇排序法 , 最壞情況需要 n(n1)/2次比較； ? （ 2）堆排序法，最壞情況需要 O(nlog2n)次比較。 1. 基本數(shù)據(jù)結(jié)構(gòu)與算法 ? 排序與查找試題分析 ? 選擇題 ? 在待排序的元素序列基本有序的前提下，效 率最高的排序方法是 () A)冒泡排序 B)選擇排序 C)快速排序 D)歸并排序 A 1. 基本數(shù)據(jù)結(jié)構(gòu)與算法 ? 希爾排序法屬于哪一種類型的排序法 ( ) A. 交換類排序法 B. 插入類排序法 C. 選擇類排序法 D. 建堆排序法 B 1. 基本數(shù)據(jù)結(jié)構(gòu)與算法 ? 對長度為 N的線性表進行順序查找，在最壞情況下所需要的比較次數(shù)為（ ） A. N+1 B. N C. (N+1)/2 D. N/2 B 1. 基本數(shù)據(jù)結(jié)構(gòu)與算法 ? 在下列幾種排序方法中，要求內(nèi)存量最大的是（ ） A. 插入排序 B. 選擇排序 C. 快速排序 D. 歸并排序 D 1. 基本數(shù)據(jù)結(jié)構(gòu)與算法 ? 已知數(shù)據(jù)表 A中每個元素距其最終位置不遠，為節(jié)省時間，應采用的算法是（ ） A. 堆排序 B. 直接插入排序 C. 快速排序 D. 直接選擇排序 B 1. 基本數(shù)據(jù)結(jié)構(gòu)與算法 ? 在最壞情況下，堆排序需要比較的次數(shù)為______。 （ O(nlog2n) ） ? 在最壞情況下，冒泡排序的時間復雜度為______。 （ n(n1)/2n*(n1)/2O(n(n1)/2)O(n*(n1)/2) ） 其他 ? n個頂點的強連通圖的邊數(shù)至少有（） A. n1 B. n(n1) C. n D. n+1 C 2. 程序設(shè)計基礎(chǔ) ? 程序設(shè)計設(shè)計方法和風格 ? 良好的程序設(shè)計風格： ? 源程序文檔化； ? 數(shù)據(jù)說明的方法； ? 語句的結(jié)構(gòu)； ? 輸入和輸出。 ? 注釋分序言性注釋和功能性注釋，語句結(jié)構(gòu)清晰第一、效率第二。 2. 程序設(shè)計基礎(chǔ) ? 結(jié)構(gòu)化程序設(shè)計 ? 結(jié)構(gòu)化程序設(shè)計方法的四條原則是： 1. 自頂向下； 2. 逐步求精； ； goto語句。 ? 結(jié)構(gòu)化程序的基本結(jié)構(gòu)和特點： ? （ 1）順序結(jié)構(gòu)：一種簡單的程序設(shè)計，最基本、最常用的結(jié)構(gòu)； ? （ 2）選擇結(jié)構(gòu)：又稱分支結(jié)構(gòu)，包括簡單選擇和多分支選擇結(jié)構(gòu)，可根據(jù)條件，判斷應該選擇哪一條分支來執(zhí)行相應的語句序列； ? （ 3）重復結(jié)構(gòu)：又稱循環(huán)結(jié)構(gòu)，可根據(jù)給定條件，判斷是否需要重復執(zhí)行某一相同程序段。 2. 程序設(shè)計基礎(chǔ) ? 面向?qū)ο蟮某绦蛟O(shè)計 ? 面向?qū)ο蟮某绦蛟O(shè)計：以 60年代末挪威奧斯陸大學和挪威計算機中心研制的 SIMULA語言為標志。 ? 面向?qū)ο蠓椒ǖ膬?yōu)點： ? 與人類習慣的思維方法一致； ? 穩(wěn)定性好； ? 可重用性好； ? 易于開發(fā)大型軟件產(chǎn)品； ? 可維護性好。 ? 對象是面向?qū)ο蠓椒ㄖ凶罨镜母拍?，可以用來表示客觀世界中的任何實體，對象是實體的抽象。 ? 面向?qū)ο蟮某绦蛟O(shè)計方法中的對象是系統(tǒng)中用來描述客觀事物的一個實體，是構(gòu)成系統(tǒng)的一個基本單位，由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。 2. 程序設(shè)計基礎(chǔ) ? 屬性即對象所包含的信息，操作描述了對象執(zhí)行的功能，操作也稱為方法或服務。 ? 對象的基本特點： ? 標識惟一性； ? 分類性； ? 多態(tài)性； ? 封裝性； ? 模塊獨立性好。 ? 類是指具有共同屬性、共同方法的對象的集合。所以類是對象的抽象，對象是對應類的一個實例。 2. 程序設(shè)計基礎(chǔ) ? 消息是一個實例與另一個實例之間傳遞的信息。 ? 消息的組成包括： ? 接收消息的對象的名稱； ? 消息標識符，也稱消息名； ? 零個或多個參數(shù)。 ? 繼承是指能夠直接獲得已有的性質(zhì)和特征，而不必重復定義他們。 ? 繼承分單繼承和多重繼承。單繼承指一個類只允許有一個父類，多重繼承指一個類允許有多個父類。 ? 多態(tài)性是指同樣的消息被不同的對象接受時可導致完全不同的行動的現(xiàn)象。 2. 程序設(shè)計基礎(chǔ) ? 程序設(shè)計試題及分析 ? 選擇題 ? 下面對對象概念描述錯誤的是 () A)任何對象都必須有繼承性 B)對象是屬性和方法的封裝體 C)對象間的通訊靠消息傳遞 D)操作是對象的動態(tài)屬性 A 2. 程序設(shè)計基礎(chǔ) ? 在設(shè)計程序時，應采納的原則之一是 ( ) A)不限制 goto語句的使用 B)減少或取消注解行 C)程序越短越好 D)程序結(jié)構(gòu)應有助于讀者理解 D 2. 程序設(shè)計基礎(chǔ) ? 結(jié)構(gòu)化程序設(shè)計的一種基本方法是 () A)篩選法 B)遞歸法 C)歸納法 D)逐步求精法 D 2. 程序設(shè)計基礎(chǔ) ? 下面描述中，符合結(jié)構(gòu)化程序設(shè)計風格的是 （） A. 使用順序、選擇和重復（循環(huán)）三種基本控制結(jié)構(gòu)表示程序的控制邏輯 B. 模塊只有一個入口，可以有多個出口 C. 注重提高程序的執(zhí)行效率 D. 不使用 goto語句 A 2. 程序設(shè)計基礎(chǔ) ? 下列敘述中，不屬于結(jié)構(gòu)化分析方法的是 () A)面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法 B)面向數(shù)據(jù)結(jié)構(gòu)的 Jackson方法 C)面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開發(fā)方法 D)面向?qū)ο蟮姆治龇椒? D 2. 程序設(shè)計基礎(chǔ) ? 結(jié)構(gòu)化程序設(shè)計主要強調(diào)的是 （） A. 程序的規(guī)模 B. 程序的易讀性 C. 程序的執(zhí)行效率 D. 程序的可移植性 B 2. 程序設(shè)計基礎(chǔ) ? 對建立良好的程序設(shè)計風格，下面描述正確的是（） A. 程序應簡單、清晰、可讀性好 B. 符號名的命名要符合語法 C. 充分考慮程序的執(zhí)行效率 D. 程序的注釋可有可無 A 2. 程序設(shè)計基礎(chǔ) ? 下面對對象概念描述錯誤的是（） A. 任何對象都必須有繼承性 B. 對象是屬性和方法的封裝體 C. 對象間的通訊靠消息傳遞 D. 操作是對象的動態(tài)性屬性 A 2. 程序設(shè)計基礎(chǔ) ? 對象實現(xiàn)了數(shù)據(jù)和操作的結(jié)合，是指對數(shù)據(jù)和數(shù)據(jù)的操作進行 () A)結(jié)合 B)隱藏 C)封裝 D)抽象 C 2. 程序設(shè)計基礎(chǔ) ? 下面概念中，不屬于面向?qū)ο蠓椒ǖ氖牵ǎ? A. 對象 B. 繼承 C. 類 D. 過程調(diào)用 D 2. 程序設(shè)計基礎(chǔ) ? 在面向?qū)ο蠓椒ㄖ校粋€對象請求另一對象為其服務的方式是通過發(fā)送 （） A. 調(diào)用語句 B. 命令 C. 口令 D. 消息 D 2. 程序設(shè)計基礎(chǔ) ? 面向?qū)ο蟮脑O(shè)計方法與傳統(tǒng)的的面向過程的方法有本質(zhì)不同，它的基本原理是（） A. 模擬現(xiàn)實世界中不同事物之間的聯(lián)系 B. 強調(diào)模擬現(xiàn)實世界中的算法而不強調(diào)概念 C. 使用現(xiàn)實世界的概念抽象地思考問題從而自然地解決問題 D. 鼓勵開發(fā)者在軟件開發(fā)的絕大部分中都用實際領(lǐng)域的概念去思考 C 2. 程序設(shè)計基礎(chǔ) ? 結(jié)構(gòu)化程序設(shè)計方法的主要原則可以概括為自頂向下、逐步求精、 ______和限制使用goto語句。 （模塊化） ? 面向?qū)ο蟮某绦蛟O(shè)計方法中涉及的對象是系統(tǒng)中用來描述客觀事物的一個 ____。（實體） ? 在面向?qū)ο蠓椒ㄖ?，信息隱蔽是通過對象的______性來實現(xiàn)的。 （封裝） ? 一個類可以從直接或間接的祖先中繼承所有屬性和方法。采用這個方法提高了軟件的______。 （可重用性） 2. 程序設(shè)計基礎(chǔ) ? 面向?qū)ο蟮哪Ｐ椭?，最基本的概念是對象? ______。 （類） ? Jackson結(jié)構(gòu)化程序設(shè)計方法是英國的，它是一種面向 ______的設(shè)計方法。 （數(shù)據(jù)結(jié)構(gòu)） ? 與結(jié)構(gòu)化需求分析方法相對應的是 ______方法。 （結(jié)構(gòu)化設(shè)計） 3. 軟件工程基礎(chǔ) ? 軟件工程基本概念 ? 計算機軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。 ? 軟件的特點包括： ? （ 1）軟件是一種邏輯實體； ? （ 2）軟件的生產(chǎn)與硬件不同，它沒有明顯的制作過程； ? （ 3）軟件在運行、使用期間不存在磨損、老化問題； ? （ 4）軟件的開發(fā)、運行對計算機系統(tǒng)具有依賴性，受計算機系統(tǒng)的限制，這導致了軟件移植的問題； ? （ 5）軟件復雜性高，成本昂貴； ? （ 6）軟件開發(fā)涉及諸多的社會因素。 3. 軟件工程基礎(chǔ) ? 軟件按功能分為應用軟件、系統(tǒng)軟件、支撐軟件（或工具軟件）。 ? 軟件危機主要表現(xiàn)在成本、質(zhì)量、生產(chǎn)率等問題。 ? 軟件工程是應用于計算機軟件的定義、開發(fā)和維護的一整套方法、工具、文檔、實踐標準和工序。 ? 軟件工程包括 3個要素：方法、工具和過程。 ? 軟件工程過程是把軟件轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動，包含 4種基本活動： ? （ 1） P——軟件規(guī)格說明；（ 2） D——軟件開發(fā)；（ 3） C——軟件確認；（ 4） A——軟件演進。 3. 軟件工程基礎(chǔ) ? 軟件周期：軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停止使用退役的過程。 ? 軟件生命周期三個階段 :軟件定義、軟件開發(fā)、運行維護，主要活動階段是： ? 可行性研究與計劃制定； ? 需求分析； ? 軟件設(shè)計； ? 軟件實現(xiàn)； ? 軟件測試； ? 運行和維護。 3. 軟件工程基礎(chǔ) ? 軟件工程的目標和與原則： ? 目標：在給定成本、進度的前提下，開發(fā)出具有有效性、可靠性、可理解性、可維護性、可重用性、可適應性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。 ? 基本目標：付出較低的開發(fā)成本；達到要求的軟件功能；取得較好的軟件性能；開發(fā)軟件易于移植；需要較低的費用；能按時完成開發(fā)，及時交付使用。 ? 基本原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗證性。 3. 軟件工程基礎(chǔ) ? 軟件工程的理論和技術(shù)性研究的內(nèi)容主要包括：軟件開發(fā)技術(shù)和軟件工程管理。 ? 軟件開發(fā)技術(shù)包括：軟件開發(fā)方法學、開發(fā)過程、開發(fā)工具和軟件工程環(huán)境。 ? 軟件工程管理包括：軟件管理學、軟件工程經(jīng)濟學、軟件心理學等內(nèi)容。 ? 軟件管理學包括人員組織、進度安排、質(zhì)量保證、配置管理、項目計劃等。 ? 軟件工程原則包括抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗證性。 3. 軟件工程基礎(chǔ) ? 結(jié)構(gòu)化分析方法 ? 結(jié)構(gòu)化方法的核心和基礎(chǔ)是結(jié)構(gòu)化程序設(shè)計理論。 ?