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