二級公共基礎(chǔ)知識ppt課件

1、二 級 公 共 基 礎(chǔ) 知 識 考試需知:考試內(nèi)容及安排第一章 算法與數(shù)據(jù)結(jié)構(gòu)第二章 程序設(shè)計基礎(chǔ)第三章 軟件工程基礎(chǔ)第四章 數(shù)據(jù)庫設(shè)計基礎(chǔ)1 一、涉及面廣，但難度小你應(yīng)該知道 公共基礎(chǔ)知識考題特點及復(fù)習建議 計算機等級二級理論考試中有關(guān)公共知識部分的題目共有15道，涉及算法及數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計基礎(chǔ)、軟件工程基礎(chǔ)和數(shù)據(jù)庫設(shè)計基礎(chǔ)等四門學科，但是從整體上分析，考試中的考核內(nèi)容的難度不大，考點也相對集中些。2二、考核重點為基本概念、基本方法 和基本運算你應(yīng)該知道 計算機等級二級理論考試中涉及的題目都是基本概念、基本方法和基本運算，考核以概念和認識性內(nèi)容為主，理解性、應(yīng)用性內(nèi)容極少。 3三、考核重點

2、是數(shù)據(jù)結(jié)構(gòu)和算法你應(yīng)該知道 以下是對以往二級理論考試的大概統(tǒng)計： 算法及數(shù)據(jù)結(jié)構(gòu)： 50% 程序設(shè)計基礎(chǔ)：12.5% 軟件工程基礎(chǔ)：18.75% 數(shù)據(jù)庫設(shè)計基礎(chǔ)：18.75%4四、六點復(fù)習及應(yīng)試建議 復(fù)習的關(guān)鍵是考生必須準確判斷和掌握常見考點 公共基礎(chǔ)知識部分的知識點多、雜，考生在學習過程中應(yīng)理 清其中的脈絡(luò)關(guān)系（即框架提綱），才能有效地組織和記住 各知識點考生不要太追求靈活掌握該部分的內(nèi)容，最好經(jīng)歷一個“先死 后活、熟能生巧”的過程，這是多數(shù)考生常犯的另一種錯誤 最后給大家一個答題技巧：“會就會，不會就不會”，不要拖 時間，要考慮成本/效果的關(guān)系，為后面的題目提供時間。5你應(yīng)該知道 共講授

3、20個學時，具體安排如下： 第 周 （ 月 日）： 算法、數(shù)據(jù)結(jié)構(gòu)（上）（地點：） 第 周 （ 月 日）：數(shù)據(jù)結(jié)構(gòu)(下）、軟件工程、程序設(shè)計基礎(chǔ)（地點：） 第 周 （ 月 日）： 數(shù)據(jù)庫系統(tǒng)、真題講解（地點：） 本 課 程 授 課 安 排61、了解算法的基本概念和一些常用的算法，學會計算算法的時間復(fù)雜度；2、掌握數(shù)據(jù)結(jié)構(gòu)的基本概念，并了解數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，學會利 用圖形的方式表示數(shù)據(jù)結(jié)構(gòu) ；學習目標與要求 算法與數(shù)據(jù)結(jié)構(gòu)：3、了解線性表的基本概念，并掌握線性表的順序存儲結(jié)構(gòu)以及順序存儲的 線性表的基本運算； 4、了解棧和隊列的基本概念，并掌握它們的基本運算； 5、了解線性鏈表的基本概念

4、，并掌握線性鏈表的基本運算，同時，了解循 環(huán)鏈表的基本概念和基本操作； 6、理解樹的概念，尤其是二叉樹的基本概念和相關(guān)性質(zhì)，掌握二叉樹的存 儲結(jié)構(gòu)和遍歷技術(shù)； 7、掌握查找技術(shù)，學會利用順序查找和二分查找在數(shù)列中查找指定的數(shù)據(jù)； 8、學會利用相關(guān)的排序技術(shù)實現(xiàn)無序數(shù)列的排序操作。 71、了解軟件工程的基本概念；2、了解軟件工程過程與軟件的生命周期，以及軟件工程的目標和原則；學習目標與要求 軟件工程：3、了解利用結(jié)構(gòu)化分析法進行軟件工程中的需求分析的方法，并了解需 求分析的方法和需要完成的任務(wù)； 4、了解數(shù)據(jù)流圖的使用方法； 5、了解如何利用結(jié)構(gòu)化設(shè)計方法進行軟件設(shè)計，并了解軟件設(shè)計的一些 常用

5、工具； 6、了解軟件測試的目的和方法，以及軟件測試的準則，了解常用的軟件 測試方法的區(qū)別和各自的功能與特點； 7、了解程序調(diào)試的方法和原則 。81、了解程序設(shè)計的方法，以及程序設(shè)計風格確立的一些因素，掌握程序 設(shè)計的基本規(guī)則； 2、了解結(jié)構(gòu)化程序設(shè)計的基本原則，掌握結(jié)構(gòu)化程序設(shè)計的基本結(jié)構(gòu)與特點;學習目標與要求 程序設(shè)計基礎(chǔ)：3、了解面向?qū)ο蟮某绦蛟O(shè)計方法，并理解面向?qū)ο蠓椒ǖ囊恍┗靖拍睢?數(shù)據(jù)庫系統(tǒng)：1、了解數(shù)據(jù)庫系統(tǒng)的基本概念，以及數(shù)據(jù)庫系統(tǒng)的發(fā)展； 2、了解數(shù)據(jù)模型的基本概念，并對E-R模型、層次模型、網(wǎng)狀模型和關(guān)系模型 進行了解，并掌握關(guān)系模型的數(shù)據(jù)結(jié)構(gòu)、關(guān)系的操作和數(shù)據(jù)約束等知識；

6、 3、了解關(guān)系模型的基本操作，掌握關(guān)系模型的基本運算及擴充運算； 4、了解數(shù)據(jù)庫的設(shè)計與管理，掌握數(shù)據(jù)庫設(shè)計的幾個階段的方法和特點。 9程序設(shè)計基本概念一、 計算機工作原理 通過工作原理了解，熟悉計算機內(nèi)部執(zhí)行功能的基本意義。為理解程序打下基礎(chǔ)，特別理解計算機是機器。二、 程序的定義 指令的集合。（解釋指令） 通過硬件控制系統(tǒng)自動完成某一功能。 通過一系列代碼實現(xiàn)。10程序設(shè)計基本概念三、 程序怎樣執(zhí)行、如何編寫程序計算機本身僅能識別二進制代碼“0”、“1”。編程最直接、最低級的就是機器語言。為解決機器語言難理解、記憶等問題。出現(xiàn)符號語言。為使編程接近自然語言，出現(xiàn)高級語言。如C、PASCAL

7、、FORTRAN等。為配合高級語言編程，出現(xiàn)了開發(fā)工具，提高效率、減輕勞動量。如VB、VC、PB、Delphi、VFP等。因此VFP不是編程語言。11程序設(shè)計基本概念 不管什么形式編寫代碼，最終都應(yīng)將代碼翻譯成機器語言， 這就是編譯程序的工作。不同的語言有不同的編譯器。 程序控制是一種邏輯控制。因此，嚴謹?shù)倪壿嬎季S是一個 程序員必備的基本素質(zhì)。 用程序?qū)崿F(xiàn)某一功能。有許多方法。具體用哪種完全取決 于程序員個人的思維方式。因此，程序是腦力勞動的結(jié)晶， 從某種意義上，編程又是一門藝術(shù)。 程序的特殊性決定了程序的復(fù)雜性，且與實現(xiàn)功能的復(fù)雜 性密切相關(guān)成正比。因此為使復(fù)雜的、智力的編程工作規(guī) 范化、科

8、學化，便出現(xiàn)了各種編程設(shè)計方法。如結(jié)構(gòu)化編 程方法、面向?qū)ο蟮某绦蛟O(shè)計方法等。12程序設(shè)計基本概念 不管用什么方法編程，不管編程者智力程度如何，不管 采用什么樣的編程語言和方法，程序最終完成的功能穩(wěn) 定、可靠、實用、易維護和安全等是程序的最終目標， 也是程序員的追求。 程序設(shè)計是一個復(fù)雜艱巨的過程。編寫代碼僅是程序設(shè) 計的一部分。必須先有思想，再有方法，然后才是編寫 代碼，且要經(jīng)過許多反復(fù)，不可急功近利。13程序設(shè)計基本概念四、 程序設(shè)計語言或工具 程序設(shè)計語言指的是用來編寫程序的語言。 人與計算機交流要使用語言，以便讓計算機工作，計算 機也通過語言把結(jié)果告訴用計算機的人“人機對 話”。 人與

9、計算機交流的語言非平常人與人之間交流的語言， 是專門的語言程序設(shè)計語言。 程序設(shè)計語言是計算機系統(tǒng)軟件的重要組成部分。14程序設(shè)計基本概念 執(zhí)行程序設(shè)計的語言有很多，可分高級語言和低級語言， 區(qū)別在于接近自然語言的程度 高級語言一般與具體的計算機硬件無關(guān)，比較接近人類 自然語言的語法習慣及數(shù)學表達形式。 用高級語言編寫的源程序不能被機器直接執(zhí)行，需通過 編譯成解釋程序的翻譯才可被機器執(zhí)行（機器語言）。 四、 程序設(shè)計語言或工具（續(xù)）15第一章 算法與數(shù)據(jù)結(jié)構(gòu)二級公共基礎(chǔ)知識返回16算法與數(shù)據(jù)結(jié)構(gòu)一、算法1、算法的基本概念 算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表

10、示一個或多個操作。它是一組嚴謹?shù)囟x運算順序的規(guī)則，并且每一個規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。算法具有有窮性、確定性、可行性、輸入和輸出（擁有足夠的情報）等個重要特性。17學習目標與要求2、算法的基本要素 對數(shù)據(jù)對象的運算和操作： 算術(shù)運算、邏輯運算、關(guān)系運算、數(shù)據(jù)傳輸 算法中各操作之間的執(zhí)行順序； 描述算法的工具通常有傳統(tǒng)流程圖、N-S結(jié)構(gòu)化流程 圖、算法描述語言等； 一個算法一般可以用順序、選擇、循環(huán)三種基本結(jié)構(gòu) 組合而成。 算法的控制結(jié)構(gòu)： 18算法與數(shù)據(jù)結(jié)構(gòu)3、算法設(shè)計的基本方法 列舉法 歸納法 遞推 遞歸（以簡潔的形式設(shè)計和描述算法） 減半遞推技術(shù) 回溯法19

11、算法與數(shù)據(jù)結(jié)構(gòu)二、算法的復(fù)雜度1、時間復(fù)雜度 依據(jù)算法編制的程序在計算機上運行時所消耗的時間 來度量。通常有事后統(tǒng)計法和事前分析估算法。 一個算法是由控制結(jié)構(gòu)（順序、分支和循環(huán)）和原操 作構(gòu)成的，算法時間取決于兩者的綜合效果。 算法中基本操作重復(fù)執(zhí)行次數(shù)n和算法執(zhí)行時間同步 增長，稱作算法的時間復(fù)雜度。20算法與數(shù)據(jù)結(jié)構(gòu)2、空間復(fù)雜度 一般是指執(zhí)行這個算法所需要的內(nèi)存空間。 一個算法所占用的存儲空間包括算法程序所占的空間、 輸入的初始數(shù)據(jù)所占的存儲空間以及某種數(shù)據(jù)結(jié)構(gòu)所需 要的附加存儲空間。 一個上機執(zhí)行的程序除了需要存儲空間來寄存本身所用 指令、常數(shù)、變量和輸入數(shù)據(jù)外，也需要一些對數(shù)據(jù)進 行

12、操作的工作單元和存儲一些為實現(xiàn)計算所需信息的輔 助空間。21算法與數(shù)據(jù)結(jié)構(gòu)3、例題講解 算法的時間復(fù)雜度是指( C ) A、執(zhí)行算法程序所需要的時間 B、算法程序的長度 C、算法執(zhí)行過程中所需要的基本運算次數(shù) D、算法程序中的指令條數(shù) 算法的基本特征是可行性、確定性、 【1】和擁有足夠 的情報。 【答案】:有窮性 算法的空間復(fù)雜度是指( D ) A) 算法程序的長度 B) 算法程序中的指令條數(shù) C) 算法程序所占的存儲空間 D) 執(zhí)行過程中所需要的存儲空間 22算法與數(shù)據(jù)結(jié)構(gòu) 在計算機中，算法是指（ B ） A) 加工方法 B) 解題方案的準確而完整的描述 C) 排序方法 D) 查詢方法 算法

13、分析的目的是( D ) A) 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B) 找出算法中輸入和輸出之間的關(guān)系 C) 分析算法的易懂性和可靠性 D) 分析算法的效率以求改進 算法的工作量大小和實現(xiàn)算法所需的存儲單元多少分別稱 為算法的 【 1 】 ?！敬鸢浮?時間復(fù)雜度和空間復(fù)雜度 23算法與數(shù)據(jù)結(jié)構(gòu)三、數(shù)據(jù)結(jié)構(gòu)（ Data Structure）1、數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容當今計算機應(yīng)用的特點： 1、所處理的數(shù)據(jù)量大且具有一定的關(guān)系； 2、對其操作不再是單純的數(shù)值計算，而更多地是需 要對其進行組織、管理和檢索。 對數(shù)據(jù)的討論不單是數(shù)據(jù)本身，還要包括數(shù)據(jù)與數(shù)據(jù)之間的關(guān)系。24特點： 每個學生的信息占據(jù)一行，所有學生的信

14、息按學號順序依次排列構(gòu)成一張表格； 表中每個學生的信息依據(jù)學號的大小存在著一種前后關(guān)系，這就是我們所說的線性結(jié)構(gòu)； 對它的操作通常是插入某個學生的信息，刪除某個學生的信息，更新某個學生的信息，按條件檢索某個學生的信息等。 應(yīng)用舉例1學籍檔案管理假設(shè)一個學籍檔案管理系統(tǒng)應(yīng)包含如下表所示的學生信息。25 應(yīng)用舉例2家庭血緣關(guān)系圖 表示家庭成員的輩分關(guān)系，使用下圖1-1所示的形式描述。圖 1-1 家庭血緣關(guān)系圖特點： 在求解過程中，所處理的數(shù)據(jù)之間具有層次關(guān)系，這是我們 所說的樹形結(jié)構(gòu)； 對它的操作有：建立樹形結(jié)構(gòu)，輸出終結(jié)點內(nèi)容等。26 應(yīng)用舉例3制定教學計劃 在制定教學計劃時，需要考慮各門課程的

15、開設(shè)順序。有些課程需要先導(dǎo)課程，有些課程則不需要，而有些課程又是其他課程的先導(dǎo)課程。比如，計算機專業(yè)課程的開設(shè)情況如下表所示：27這種數(shù)據(jù)可以用下面的圖來表示：27 課程先后關(guān)系的圖形描形式：c1c9c4c2c12c10c11c5c3c6c7c8圖 1-2 計算機專業(yè)必修課程開設(shè)先后關(guān)系2828 1、數(shù)據(jù)的邏輯結(jié)構(gòu) 2、數(shù)據(jù)的存儲結(jié)構(gòu) 3、數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等。 A線性結(jié)構(gòu)B非線性結(jié)構(gòu)A順序存儲 B鏈式存儲 線性表棧隊樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個方面(亦稱物理結(jié)構(gòu))數(shù)據(jù)結(jié)構(gòu)的主要研究問題：29292、基本概念和術(shù)語 數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲和運算的一般方法的學科

16、。例：整數(shù)(1,2)、實數(shù)(1.1,1.2)字符串(Beijing)、圖形、聲音。計算機管理圖書問題 ： 在圖書館里有各種卡片：有按書名編排的、有按作者編排的、有按分類編排。如何將查詢圖書的這些信息存入計算機中既要考慮查詢時間短，又要考慮節(jié)省空間。最簡單的辦法之一是建立一張表，每一本書的信息在表中占一行，如：3030數(shù)據(jù)元素在計算機中的表示 數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲和運算的一般方法的學科。如何將0,1,2,3,4,5,6,7,8,9這10個數(shù)存放在計算機中能最快地達到你所需要的目的？ 目的不同，最佳的存儲方方法就不同。從大到小排列：9,8,7,6,5,4,3,2,1,0輸出偶數(shù)：0,2

17、,4,6,8,1,3,5,7,9 對數(shù)據(jù)結(jié)構(gòu)中的節(jié)點進行操作處理（插入、刪除、修改、查找、排序）3131 數(shù)據(jù)元素(Data Element) 數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個體。 有時一個數(shù)據(jù)元素可由若干數(shù)據(jù)項(Data Item)組成。數(shù)據(jù)項是數(shù)據(jù)的最小單位。數(shù)據(jù)元素亦稱節(jié)點或記錄。數(shù)據(jù)結(jié)構(gòu)可描述為 Group=（D，R）有限個數(shù)據(jù)元素的集合有限個節(jié)點間關(guān)系的集合3232數(shù)據(jù)結(jié)構(gòu)可描述為 Group=（D，R） 例1：一年四季的數(shù)據(jù)結(jié)構(gòu)可表示成B=（D，R） D=春，夏，秋，冬 R=（春，夏），（夏，秋），（秋，冬） 例2：家庭成員數(shù)據(jù)結(jié)構(gòu)可表示成B=（D，R）D=父親，兒子，女

18、兒 R=（父親，兒子），（父親，女兒）冬春夏秋父親兒子女兒33數(shù)據(jù)結(jié)構(gòu)也可用圖形表示一年四季的數(shù)據(jù)結(jié)構(gòu)可表示成家庭成員數(shù)據(jù)結(jié)構(gòu)可表示成冬春夏秋父親兒子女兒（ 概念：結(jié)點、前件、后件、根結(jié)點、葉子 ）34 樹形結(jié)構(gòu)全校學生檔案管理的組織方式計算機程序管理系統(tǒng)也是典型的樹形結(jié)構(gòu)。35HGFECDBA樹形結(jié)構(gòu) 結(jié)點間具有分層次的連接關(guān)系HBCDEFGA36 D=1 , 2 , 3 , 4R=(1,2),(1,3), (1,4),(2,3), (3,4),(2,4) 213 D= 1 , 2 , 3 R=(1,2),(2,3),(3,2),(1,3) 圖形結(jié)構(gòu)節(jié)點間的連結(jié)是任意的1423373、例題講

19、解數(shù)據(jù)處理的最小單位是( C ) A)數(shù)據(jù) B)數(shù)據(jù)元素 C) 數(shù)據(jù)項 D) 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)作為計算機的一門學科，主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、對各種數(shù)據(jù)結(jié)構(gòu)進行的運算，以及( A ) A) 數(shù)據(jù)的存儲結(jié)構(gòu) B) 計算方法 C) 數(shù)據(jù)映象 D) 邏輯存儲數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的 【4】 以及對數(shù)據(jù)的操作運算。 【答案】物理結(jié)構(gòu)（或存儲結(jié)構(gòu)）38 線性結(jié)構(gòu)與非線性結(jié)構(gòu)： 線性結(jié)構(gòu)：有且只有一個根結(jié)點；每一個結(jié)點最多有一個前件，也最多有一個后件。 如：一年四季，26個英文字母非線性結(jié)構(gòu)：線性以外的數(shù)據(jù)結(jié)構(gòu)。 如：反映家庭成員間輩分關(guān)系的數(shù)據(jù)結(jié)構(gòu) 算法與數(shù)據(jù)結(jié)構(gòu)394、線性表（Linear L

20、ist）學 生 成 績 表 (按成績排列)86胡孝臣986110395劉忠賞9861107100張卓9861109成 績姓 名學 號 線性表結(jié)點間是以線性關(guān)系聯(lián)結(jié)： 線性表：具有線性結(jié)構(gòu)的有限序列。 數(shù)據(jù)元素在線性表中的位置只取決于它們自己的序號，即數(shù)據(jù)元素之間的相對位置是線性的。40線性表的定義: 線性表是n個元素的有限序列，它們之間的關(guān)系可以排成一個線性序列：a1，a2， ，ai， ，an 其中n稱作表的長度，當n=0時，稱作空表。線性表的特點： 1、線性表中所有元素的性質(zhì)相同。 2、除第一個和最后一個數(shù)據(jù)元素之外，其它數(shù)據(jù)元素有且 僅有一個前驅(qū)和一個后繼。第一個數(shù)據(jù)元素無前驅(qū)，最 后一個

21、數(shù)據(jù)元素無后繼。 3、數(shù)據(jù)元素在表中的位置只取決于它自身的序號。在線性表上常用的運算有： 初始化、求長度、取元素、修改、前插、刪除、檢索、排序4141 線性表的 順序存儲結(jié)構(gòu) 及其 插入 與 刪除 操作特點： 1、線性表中數(shù)據(jù)元素類型一致，只有數(shù)據(jù)域，存儲空間 利用率高。 2、所有元素所占的存儲空間是連續(xù)的。 3、各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的 （a）做插入、刪除時需移動大量元素。 （b）空間估計不明時，按最大空間分配。算法與數(shù)據(jù)結(jié)構(gòu)42順序存儲存儲地址存儲內(nèi)容元素n.元素i.元素2元素1LoLo + mLo+(i-1)mLo+（n-1)mLoc(元素i)=Lo+（i-1)m每個

22、元素所占用的存儲單元個數(shù) 線性表的 順序存儲結(jié)構(gòu)：首地址起始地址基地址43元素a1元素a2.元素ai+1. 0 1i 線性表的順序存儲結(jié)構(gòu)可用C語言中的一維數(shù)組來描述.第i個元素的ai存儲地址：Loc(ai)=Loc(a1)+(i-1)* mVVViVm-1 int VM; 其中：V是數(shù)組的名字，M是數(shù)組大小， 假設(shè)數(shù)組中的元素是整型類型算法與數(shù)據(jù)結(jié)構(gòu)44插入運算.a2a1an.ai+1ai01i-1in-1ai-1.a2a1alength ai+1ai x ai-1. a2 a1 X aiai+1.alength插入算法的分析 假設(shè)線性表中含有n個數(shù)據(jù)元素，在進行插入操作時，若假定在n+1個

23、位置上插入元素的可能性均等，則平均移動元素的個數(shù)為：4545在進行刪除操作時，若假定刪除每個元素的可能性均等，則平均移動元素的個數(shù)為：分析結(jié)論 順序存儲結(jié)構(gòu)表示的線性表，在做插入或刪除操作時，平均需要移動大約一半的數(shù)據(jù)元素。當線性表的數(shù)據(jù)元素量較大，并且經(jīng)常要對其做插入或刪除操作時，這一點需要值得考慮。刪除算法的分析4646 線性表的例題講解 順序存儲方法是把邏輯上相鄰的結(jié)點存儲在物理位置 【1】 的存儲單元中。 【答案】相鄰 長度為n的順序存儲線性表中，當在任何位置上插入一個元 素概率都相等時，插入一個元素所需移動元素的平均個數(shù) 為【2】 。 【答案】 n/2 線性表L=(a1,a2,a3,

24、ai，an)，下列說法正確的是（D） A) 每個元素都有一個直接前件和直接后件 B) 線性表中至少要有一個元素 C) 表中諸元素的排列順序必須是由小到大或由大到小 D) 除第一個元素和最后一個元素外，其余每個元素都有一 個且只有一個直接前件和直接后件 4747數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的( C ) A) 存儲結(jié)構(gòu)B) 物理結(jié)構(gòu) C) 邏輯結(jié)構(gòu)D) 物理和存儲結(jié)構(gòu) 下列敘述中，錯誤的是（ B ） A) 數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率密切相關(guān) B) 數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率無關(guān) C) 數(shù)據(jù)的存儲結(jié)構(gòu)在計算機中所占的空間不一定是連續(xù)的 D) 一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)

25、數(shù)據(jù)的存儲結(jié)構(gòu)是指（ B ） A）數(shù)據(jù)所占的存儲空間 B）數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示 C）數(shù)據(jù)在計算機中的順序存儲方式 D）存儲在外存中的數(shù)據(jù)48 根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分成( C ) A) 動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B) 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C) 線性結(jié)構(gòu)和非線性結(jié)構(gòu) D) 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和 【2】兩大類。非線性結(jié)構(gòu) 當線性表采用順序存儲結(jié)構(gòu)實現(xiàn)存儲時，其主要特點是【1】。 【答案】邏輯結(jié)構(gòu)中相鄰的結(jié)點在存儲結(jié)構(gòu)中仍相鄰。49495、堆棧和隊列 堆棧和隊列的定義 棧和隊列是兩種特殊的線性表，它們是運算時要受到某些限制的線

26、性表，故也稱為限定性的數(shù)據(jù)結(jié)構(gòu)。 堆棧的定義堆棧：限定只能在表的一端進行插入和刪除的特殊的線性表,此種 結(jié)構(gòu)稱為后進先出。設(shè)棧s=（a1，a2，ai， ，an）,其中a1是棧底元素， an是棧頂元素。棧頂（top)：允許插入和刪除的一端；約定top始終指向新數(shù)據(jù)元素將存放的位置。棧底（bottom):不允許插入和刪除的一端。 a1 a2 . an進棧出棧棧頂棧底5050 a1 a2 . an進棧出棧棧頂棧底5151 隊列的定義隊列：一種特殊的線性結(jié)構(gòu)，限定只能在表的一端進行插入， 在表的另一端進行刪除的線性表。此種結(jié)構(gòu)稱為先進 先出（FIFO）表。 a1 , a2 , a3 , an-1 ,

27、an隊 列 示 意 圖隊頭隊尾 隊列的主要運算（1）設(shè)置一個空隊列；（2）插入一個新的隊尾元素，稱為進隊；（3）刪除隊頭元素，稱為出隊；（4）讀取隊頭元素。52出隊入隊rearfront52 循環(huán)隊列及其運算循環(huán)隊列：將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間，供隊列循環(huán)使用。循環(huán)隊列的元素：從排頭指針指向的后一個位置直到隊尾指針指向的位置之間所有的元素。說明：為了能夠區(qū)分隊列滿與空，設(shè)置一個標志s。53s=0 表示隊列空1 表示隊列非空隊列空與滿的條件：隊列空時，s=0；隊列滿時，s=1且front=rear。53循環(huán)隊列的運算：入隊運算和退隊運算入隊運算：是指在循環(huán)隊

28、列中的隊尾加入一新元素。具體操作：（1）將隊尾指針進一，即rear=rear+1。 注：當rear=m+1時，重置rear=1。（2）將新元素插入到rear指向的位置。注：當s=1且rear=front時，循環(huán)隊列滿，不能再進行入隊運算，稱為“上溢”。退隊運算：是指在循環(huán)隊列的排頭位置退出一個元素并賦給指定的變量。具體操作：（1）將排頭指針進一，即front=front+1。 注：當front=m+1時，重置front=1。（2）將排頭指針指向位置的后一個元素賦給指定的變量。注：當s=0時，循環(huán)隊列為空，再不能進行退隊運算，稱為“下溢”。5454 堆棧和隊列的例題講解棧和隊列的共同特點是（ C

29、 ） A)都是先進先出 B) 都是先進后出 C) 只允許在端點處插入和刪除元素 D) 沒有共同點如果進棧序列為e1,e2,e3,e4，則可能的出棧序列是（ B ） A) e3,e1,e4,e2 B) e4,e3,e2,e1 C) e3,e4,e1,e2 D) 任意順序一些重要的程序語言(如C語言和Pascal語言) 允許過程的遞歸調(diào)用。而實現(xiàn)遞歸調(diào)用中的存儲分配通常用（ A ） A) 棧 B) 堆 C) 數(shù)組 D) 鏈表 5555 棧底至棧頂依次存放元素A、B、C、D，在第五個元素E 入棧前，棧中元素可以出棧，則出棧序列可能是（ B ） A) ABCED B) DCBEA C) DBCEA D

30、) CDABE 棧通常采用的兩種存儲結(jié)構(gòu)是（ A ） A) 順序存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu) B) 散列方式和索引方式 C) 鏈表存儲結(jié)構(gòu)和數(shù)組 D) 線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu) 棧和隊列通常采用的存儲結(jié)構(gòu)是 【1】。 【答案】鏈式存儲和順序存儲 下列數(shù)據(jù)結(jié)構(gòu)中，按先進后出原則組織數(shù)據(jù)的是（ B ） A) 線性鏈表 B) 棧 C) 循環(huán)鏈表 D) 順序表 5656當循環(huán)隊列非空且隊尾指針等于隊頭指針時，說明循環(huán)隊列已滿，不能進行入隊運算。這種情況稱為【2】。答案：上溢 由兩個棧共享一個存儲空間的好處是（ B ） A) 減少存取時間，降低下溢發(fā)生的機率 B) 節(jié)省存儲空間，降低上溢發(fā)生的機率 C)

31、減少存取時間，降低上溢發(fā)生的機率 D) 節(jié)省存儲空間，降低下溢發(fā)生的機率下列關(guān)于棧的敘述中正確的是（ D ）)在棧中只能插入數(shù)據(jù) B）在棧中只能刪除數(shù)據(jù)C）棧是先進先出的線性表 D）棧是后進先出的線性表下列關(guān)于隊列的敘述中正確的是（ C ）在隊列中只能插入數(shù)據(jù) B）在隊列中只能刪除數(shù)據(jù)C）隊列是先進先出的線性表 D）隊列是后進先出的線性表 5757 順序存儲結(jié)構(gòu)常用于線性數(shù)據(jù)結(jié)構(gòu)，將邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元里。 順序存儲結(jié)構(gòu)的三個缺點： 1.作插入或刪除操作時，需移動大量元數(shù)。 2.長度變化較大時，需按最大空間分配。 3.表的容量難以擴充。存儲內(nèi)容元素n.元素i.元素2元

32、素158586、線性鏈表線性鏈表的基本概念： 線性表的鏈式存儲結(jié)構(gòu)稱為線性鏈表。 為了適應(yīng)線性表的鏈式存儲結(jié)構(gòu)，計算機存儲空間被劃分為一個一個小塊，每一小塊占若干字節(jié)，通常稱這些小塊為存儲結(jié)點。算法與數(shù)據(jù)結(jié)構(gòu)59將存儲空間中的每一個存儲結(jié)點分為兩部：一部分稱為數(shù)據(jù)域，用于存儲數(shù)據(jù)元素的值；另一部分稱為指針域，用于存放下一個數(shù)據(jù)元素的存儲序號（即存儲結(jié)點的地址），也就是指向后件結(jié)點。線性鏈表中存儲結(jié)點的結(jié)構(gòu)如圖2.20所示60601、比順序存儲結(jié)構(gòu)的存儲密度小 (每個節(jié)點都由數(shù)據(jù)域和指針域組成，所以相同空間內(nèi)假設(shè)全存滿的話順序比鏈式存儲更多)。2、邏輯上相鄰的節(jié)點物理上不必相鄰。3、插入、刪除靈

33、活 (不必移動節(jié)點，只要改變節(jié)點中的指針)。4、查找結(jié)點時鏈式存儲要比順序存儲慢。 鏈式存儲結(jié)構(gòu)特點：算法與數(shù)據(jù)結(jié)構(gòu)61 線性鏈表的物理結(jié)構(gòu)算法與數(shù)據(jù)結(jié)構(gòu) 線性鏈表的邏輯結(jié)構(gòu)圖HEAD：指向線性表中第一個結(jié)點的指針，稱為頭指針。當HEAD=NULL（或0）時稱為空表。 對于線性鏈表，可以從頭指針開始，沿著各個結(jié)點的指針掃描到鏈表中的所有結(jié)點。6263 為了彌補線性單鏈表的這個缺點，在某些應(yīng)用中，對線性鏈表中的每個結(jié)點設(shè)置兩個指針，一個稱為左指針（Llink），用以指向其前件結(jié)點；另一個稱為右指針（Rlink），用以指向其后件的結(jié)點。 這樣的線性鏈表稱為雙向鏈表，其邏輯狀態(tài)如圖2.23所示。63

34、 線性鏈表的基本運算：線性鏈表的運算主要有以下幾個： 在線性鏈表中包含指定元素的結(jié)點之前 插入一個新元素。 在線性鏈表中刪除包含指定元素的結(jié)點。 將兩個線性鏈表按要求合并成一個線性 鏈表。64 線性鏈表的 插入 運算： 線性鏈表的插入是指在鏈式存儲結(jié)構(gòu)下的線性表中插入一個新元素。 為了要在線性鏈表中插入一個新元素，首先要給該元素分配一個新結(jié)點，然后將存放新元素值的結(jié)點鏈接到線性鏈表中指定的位置。算法與數(shù)據(jù)結(jié)構(gòu)656666 線性鏈表的刪除指在鏈式存儲結(jié)構(gòu)下的線性表中刪除包含指定元素的結(jié)點。 為了在線性鏈表中刪除包含指定元素的結(jié)點，首先要在線性鏈表中找到這個結(jié)點，然后將要刪除結(jié)點放回到可利用棧。

35、線性鏈表的 刪除 運算：算法與數(shù)據(jù)結(jié)構(gòu)676868 循環(huán)鏈表的結(jié)構(gòu)與前面所討論的線性鏈表相比，具有以下兩個特點： 循環(huán)鏈表的頭指針指向表頭結(jié)點。 在循環(huán)鏈表中，所有結(jié)點的指針構(gòu)成了一個環(huán)狀鏈。 圖2.29是循環(huán)鏈表的示意圖。循環(huán)鏈表：6969 在實際應(yīng)用中，循環(huán)鏈表與線性單鏈表相比主要有以下兩個方面的優(yōu)點： 在循環(huán)鏈表中，只要指出表中任何一個結(jié)點 的位置，就可以從它出發(fā)訪問到表中其他所有的結(jié)點。 由于在循環(huán)鏈表中設(shè)置了一個表頭結(jié)點，因 此，在任何情況下，循環(huán)鏈表中至少有一個結(jié)點存在，從而使空表與非空表的運算統(tǒng)一。算法與數(shù)據(jù)結(jié)構(gòu)70鏈表不具有的特點是（ B ） A) 不必事先估計存儲空間 B)

36、可隨機訪問任一元素 C) 插入刪除不需要移動元素 D) 所需空間與線性表長度成正比數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)，線性鏈表屬于 【1】 。 【答案】存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)和線性表的鏈式存儲結(jié)構(gòu)分別是( B ) A) 順序存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) B) 隨機存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) C) 隨機存取的存儲結(jié)構(gòu)、隨機存取的存儲結(jié)構(gòu) D) 任意存取的存儲結(jié)構(gòu)、任意存取的存儲結(jié)構(gòu) 線性鏈表的例題講解71717、樹與二叉樹： 樹的基本概念： 前面我們討論的線性表，棧、隊列和數(shù)組等都是線性結(jié)構(gòu)。而樹是一種非線性數(shù)據(jù)結(jié)構(gòu)，它的每一個結(jié)點，都可以有不止一個直接后繼，除根外的所有結(jié)點，都

37、有且只有一個直接前趨。這些數(shù)據(jù)結(jié)點按分支關(guān)系組織起，清晰地反映了數(shù)據(jù)元素之間的層次關(guān)系。 72算法與數(shù)據(jù)結(jié)構(gòu)現(xiàn)實世界中，能用樹的結(jié)構(gòu)表示的例子：學校的行政關(guān)系（P31）、書的層次結(jié)構(gòu)（P32）、人類的家族血緣關(guān)系等。7374例：下圖是一個有13個結(jié)點的樹，其中A是根，其余結(jié)點為分三個互不相交的子集：T1B,E,F,K,LT2F,GT3D,H,I,J,MT1、T2和T3都是根A的子樹。7475樹結(jié)構(gòu)的基本術(shù)語：結(jié)點的度：結(jié)點所擁有子樹的個數(shù)，圖中A的度為3，C的度為1，F(xiàn)的度為0。葉子結(jié)點：樹中度為0的結(jié)點，圖中的K、L、F、G、M、I、J均稱為葉子結(jié)點（或終端結(jié)點）。子結(jié)點與父結(jié)點：把每一個結(jié)

38、點的一個或多個后件稱為該點的子結(jié)點；反之，這個結(jié)點稱為其子結(jié)點的父結(jié)點，同一個父結(jié)點的子結(jié)點之間互稱為兄弟。樹的度：樹中各結(jié)點的度的最大值，度不為0的結(jié)點為非終端結(jié)點同，又叫分支結(jié)點。森林：N0或N=0棵互不相交的樹的集合組成森林。圖中將根結(jié)點A去掉，其中三棵子樹就組成一個森林。樹的深度：樹中結(jié)點的最大層次稱為樹的深度或高度。圖中樹的深度為4。75二叉樹是一種很有用的非線性結(jié)構(gòu)。二叉樹具有以下兩個特點：（1）非空二叉樹只有一個根結(jié)點；（2）每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右子樹。 二叉樹（Binary Tree）： 因為樹的每個結(jié)點的度不同，存儲困難，使得對樹的處理算法很復(fù)

39、雜。所以引出二叉樹的討論。76767777性質(zhì)1：在任意一棵二叉樹中，度為0的結(jié)點（即葉子結(jié)點）總是比度為2的結(jié)點多一個。例子1：某二叉樹中度為2的結(jié)點有18個，則該二叉樹中有 19 個葉子結(jié)點。二叉樹的性質(zhì)： 特別要注意：二叉樹不是樹的特殊情況。aabb兩棵不同的二叉樹7878性質(zhì)2：二叉樹的第i層上至多有2 i-1（i 1）個結(jié)點二叉樹的性質(zhì)：423167891011121314155第一層(i=1)，有21-1=1個節(jié)點。第二層(i=2)，有22-1=2個節(jié)點。第三層(i=3)，有23-1=4個節(jié)點。第四層(i=4)，有24-1=8個節(jié)點。79二叉樹的性質(zhì)：性質(zhì)3：深度為h的二叉樹中至多

40、含有2h-1個結(jié)點423167891011121314155此樹的深度h=4，共有24-1=15個節(jié)點。1+2+4+2m-1=2m-1(等比數(shù)列前M項和)80滿二叉樹與完全二叉樹滿二叉樹是指除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點。完全二叉樹是指這樣的二叉樹：除最后一層外，每一層上的結(jié)點數(shù)均達到最大值；在最后一層上只缺少右邊的若干結(jié)點。注意：滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。算法與數(shù)據(jù)結(jié)構(gòu)81 滿二叉樹的特點：每一層上都含有最大結(jié)點數(shù)。8282完全二叉樹的特點：除最后一層外，每一層都取最大 結(jié)點數(shù)，最后一層結(jié)點都集中在該層最左邊的若干位置83838484 對于完全二叉樹而

41、言如果它的結(jié)點個數(shù)為偶數(shù)，則該二叉樹中：葉子結(jié)點的個數(shù)=非葉子結(jié)點的個數(shù)如果它的結(jié)點個數(shù)為奇數(shù)，則該二叉樹中：葉子結(jié)點的個數(shù)=非葉子結(jié)點的個數(shù)+1 （即葉子結(jié)點數(shù)比非葉子結(jié)點數(shù)多一個）規(guī)律總結(jié)：算法與數(shù)據(jù)結(jié)構(gòu)1234123452 葉子結(jié)點 32 非葉子結(jié)點 285 例題講解1、設(shè)一棵完全二叉樹共有700個結(jié)點，則在該二叉樹中有 350 個葉子結(jié)點。2、在深度為5的滿二叉樹中，葉子結(jié)點的個數(shù)為（ C ） A) 32 B) 31 C) 16 D) 15算法與數(shù)據(jù)結(jié)構(gòu)86二叉樹的遍歷二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點。二叉樹的遍歷可以分為三種：前序遍歷、中序遍歷、后序遍歷。 設(shè)訪問根結(jié)點

42、記作V；遍歷根的左子樹記作L；遍歷根的右子樹記作R； 前序： VLR（即根左右） 中序： LVR（即左根右） 后序： LRV（即左右根）8787884 10 8 9 5 2 6 7 3 1 例：結(jié)合下圖所示的二叉樹，寫出該二叉樹的前序、中序及后序遍歷結(jié)果。后序遍歷：中序遍歷：前序遍歷：1 2 4 5 8 10 9 3 6 74 2 10 8 5 9 1 6 3 7 881、設(shè)一棵二叉樹的中序遍歷結(jié)果為DBEAFC,前序遍歷結(jié)果為ABDECF，則后序遍歷結(jié)果為： DEBFCA 例題講解2、已知一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF，則該二叉樹的后序遍歷為（ B ）

43、A) GEDHFBCA B) DGEBHFCA C) ABCDEFGH D) ACBFEDHG89具有3個結(jié)點的二叉樹有（ D ） A) 2種形態(tài) B) 4種形態(tài) C) 7種形態(tài) D) 5種形態(tài) 設(shè)有下列二叉樹： 對此二叉樹前序遍歷的結(jié)果為（ B ） A) ZBTTCPXA B) ATBZXCTP C) ZBTACTXP D) ATBZXCPT90908、查找和排序：查找又稱為檢索 查找算法的評價主要考慮算法的時間復(fù)雜性，既可以采用數(shù)量級的形式表示，也可以采用平均檢索（查找）長度，即在查找成功情況下的平均比較次數(shù)來表示。 查找可分為順序查找和二分法查找兩種。算法與數(shù)據(jù)結(jié)構(gòu)91（a）順序查找：

44、順序查找又稱線性查找。它是一種最簡單、最基本的查找方法?；舅枷胧牵簭谋碇械谝粭l記錄開始，逐個進行記錄的關(guān)鍵字和給定值的比較。若某個記錄的關(guān)鍵字和給定值相等，則查找成功；否則，若直至最后一個記錄，其關(guān)鍵字和給定值都不相等，則表明表中沒有所查記錄，查找不成功。算法與數(shù)據(jù)結(jié)構(gòu)92 二分查找又稱折半查找。作為二分查找對象的表必須是順序存儲的有序表，即各記錄的次序是按其關(guān)鍵字的大小順序（以下假定按從小到大的順序）排列的表。（b）二分查找：算法與數(shù)據(jù)結(jié)構(gòu)93 二分查找的具體做法是: 先取表中間位置的記錄關(guān)鍵字與給定值比較。若相等, 則查找成功；否則, 若給定值比該記錄的關(guān)鍵字小，則給定值必在表的前半部分

45、。在這前半部分中再取中間位置記錄的關(guān)鍵字進行比較，就又可以排除這部分的一半。依次反復(fù)進行，直到找到給定值或找完全表而找不到為止。 對于n較大時，查找長度可以近似地表示為算法與數(shù)據(jù)結(jié)構(gòu)94排序是將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。通常數(shù)據(jù)對象有多個屬性域，即由多個數(shù)據(jù)成員組成, 其中有一個屬性域可用來區(qū)分對象, 作為排序依據(jù)。該域稱為關(guān)鍵字（key）。排序的時間開銷是衡量算法好壞的最重要的標志。對于長度為n的有序線性表，查找時最壞情況只需比較 n 次。 排序（sort）95（a）交換類排序：交換類排序法：冒泡排序法：需要比較的次數(shù)為n(n-1)/2快速排序法：是對冒泡排序的改進，是目

46、前內(nèi)部排序中速度最快的一種。算法與數(shù)據(jù)結(jié)構(gòu)96（b）插入類排序： 插入類排序的基本方法是：每步將一個待排序的對象，按其關(guān)鍵字大小，插入到前面已經(jīng)排好序的一組對象的適當位置上，直到對象全部插入為止。簡單插入排序法：最壞情況需要n(n-1)/2次比較；希爾排序法：最壞情況需要O（n1.5 ）次比較。算法與數(shù)據(jù)結(jié)構(gòu)97（c）選擇類排序：選擇類排序的思想是：每一趟（例如，第i趟，i=0，1，n2）在后面ni個待排序?qū)ο笾羞x出關(guān)鍵字最?。ㄉ颍魹榻敌?，選出最大關(guān)鍵字）的對象，作為有序?qū)ο笮蛄械牡趇個對象。待到第n2趟作完，待排序?qū)ο笾皇Ｏ?個，不用再選了，結(jié)束排序。簡單選擇排序法，最壞情況需要n(n-

47、1)/2次比較；堆排序法，最壞情況需要O（nlog2 n）次比較。98第二章 程序設(shè)計基礎(chǔ)二級公共基礎(chǔ)知識返回99內(nèi)容1、程序設(shè)計方法與風格2、結(jié)構(gòu)化程序設(shè)計3、面向?qū)ο蟮某绦蛟O(shè)計方法，對象、方法、屬性及繼承與多態(tài)性。程序設(shè)計基礎(chǔ)100程序設(shè)計基礎(chǔ)（一）程序設(shè)計方法與風格 如何形成良好的程序設(shè)計風格： 1、源程序內(nèi)部文檔化； 選擇標識符的名字 注釋（序言性和功能性注釋） 程序的視覺組織一般位于模塊的首部，用于說明模塊的相關(guān)信息位于源程序模塊內(nèi)部風格：清晰第一，效率第二。101 顯式地說明一切變量 數(shù)據(jù)說明的次序應(yīng)該規(guī)范化 便于查找變量（按順序排列） 對復(fù)雜數(shù)據(jù)結(jié)構(gòu)應(yīng)注釋說明 2、數(shù)據(jù)說明程序設(shè)

48、計基礎(chǔ)3、語句的結(jié)構(gòu) 每條語句簡單明了 限制GOTO語句的使用(盡量不用或少用) 盡量只采用3種基本控制結(jié)構(gòu)編程1024、輸入和輸出 對所有輸入數(shù)據(jù)進行校驗和合理性檢查 輸入輸出格式保持一致 設(shè)計良好的輸出報表 輸入方式應(yīng)力求簡單，盡量避免給用戶帶來不必要的麻煩；交互式輸入數(shù)據(jù)時應(yīng)有必要的提示信息; 程序應(yīng)對輸入數(shù)據(jù)的合法性進行檢查;若用戶輸入某些數(shù)據(jù)后可能產(chǎn)生嚴重后果,應(yīng)給用戶輸出必要的提示并要求用戶確認；應(yīng)根據(jù)系統(tǒng)的特點和用戶的習慣設(shè)計出令用戶滿意的輸入方式。 輸出數(shù)據(jù)的格式應(yīng)清晰，美觀；輸出數(shù)據(jù)時要加上必要的提示信息。103103主要思想：對大型的程序設(shè)計，使用一些基本的結(jié)構(gòu)來設(shè)計程序，

49、無論多復(fù)雜的程序，都可以使用這些基本結(jié)構(gòu)按一定的順序組合起來。這些基本結(jié)構(gòu)的特點都是只有一個入口、一個出口。由這些基本結(jié)構(gòu)組成的程序就避免了任意轉(zhuǎn)移、閱讀起來需要來回尋找的問題。程序設(shè)計基礎(chǔ)（二）結(jié)構(gòu)化程序設(shè)計 三種基本結(jié)構(gòu)的特點 只有一個入口 只有一個出口 基本結(jié)構(gòu)中的每一部分都有機會執(zhí)行到 結(jié)構(gòu)內(nèi)不存在“死循環(huán)”三種基本結(jié)構(gòu) 順序結(jié)構(gòu) 選擇結(jié)構(gòu) 循環(huán)結(jié)構(gòu)104程序設(shè)計基礎(chǔ)設(shè)計原則 自頂向下 逐步求精 模塊化 限制使用goto語句（二）結(jié)構(gòu)化程序設(shè)計 結(jié)構(gòu)化程序設(shè)計方法1、要求把程序的結(jié)構(gòu)規(guī)定為順序、選擇和循環(huán)三種基本機構(gòu)，并提出了自頂向下、逐步求精、模塊化程序設(shè)計等原則。2、結(jié)構(gòu)化程序設(shè)計

50、是把模塊分割方法作為對大型系統(tǒng)進行分析的手段，使其最終轉(zhuǎn)化為三種基本結(jié)構(gòu)，其目的是為了解決由許多人共同開發(fā)大型軟件時，如何高效率地完成可靠系統(tǒng)的問題。3、程序的可讀性好、可維護性好成為評價程序質(zhì)量的首要條件。4、缺點：程序和數(shù)據(jù)結(jié)構(gòu)松散地耦合在一起。解決此問題的方法就是采用面向?qū)ο蟮某绦蛟O(shè)計方法(OOP)。105（三）面向?qū)ο蟮某绦蛟O(shè)計方法 面向?qū)ο蟮某绦蛟O(shè)計（Object-Oriented Programming，OOP）是一種把面向?qū)ο蟮乃枷霊?yīng)用于軟件開發(fā)過程中，指導(dǎo)開發(fā)活動的系統(tǒng)方法，簡稱OOP方法，它是建立在對象概念（對象、類和繼承）基礎(chǔ)上的方法。程序設(shè)計基礎(chǔ)106面向?qū)ο蟪绦蛟O(shè)計方法

51、的優(yōu)點 1、與人類習慣的思維方法一致 2、穩(wěn)定性好 3、可重用性好 4、易于開發(fā)大型軟件產(chǎn)品 5、可維護性好程序設(shè)計基礎(chǔ)107基本概念對象(Object) 對象是基本的運行時認得實體，它既包括數(shù)據(jù)（屬性），也包括作用于數(shù)據(jù)的操作（行為）。 一個對象把屬性和行為封裝為一個整體。 一個對象通?？捎蓪ο竺?、屬性和操作3部分組成。 屬性：通常是一些數(shù)據(jù)，有時它也可以是另一個對象。 事件：是由對象識別的一個動作，用戶可以編寫相應(yīng)代碼對此動作進行響應(yīng)，如單擊、雙擊、移動等。 方法：對象中的屬性只能通過該對象所提供的操作來存取或修改。 面向?qū)ο?Object Oriented, OO) 從該問題所涉及的對象

52、入手來研究問題。108消息(Message) 對象之間進行通信的一種構(gòu)造類（Class）：類是一組具有相同屬性和相同操作的對象的集合。 一個類定義了一組大體上相似的對象。 一個類所包含的方法和數(shù)據(jù)描述一組對象的共同行為和屬性。 類是在對象之上的抽象，對象是類的具體化，是類的實例。基類：用來生成新類的類。派生類：由已存在的類派生出來的新類，也叫子類。繼承：是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義他們。繼承分單繼承和多重繼承。109 水上交通工具陸上交通工具水陸兩用交通工具 多 重 繼 承 圖 程序設(shè)計基礎(chǔ)單繼承指一個類只允許有一個父類，多重繼承指一個類允許有多個父類。110 程序設(shè)計基礎(chǔ)

53、封裝(Encapsulation) 將數(shù)據(jù)和操作數(shù)據(jù)的函數(shù)銜接在一起，構(gòu)成一個具有類類型的對象的描述。 對象的內(nèi)部實現(xiàn)受保護，外界不能訪問 封裝簡化了程序員對對象的使用多態(tài)性(Polymorphism) 不同的對象收到同一消息可以產(chǎn)生完全不同的結(jié)構(gòu)，這一現(xiàn)象叫做多態(tài)性 多態(tài)的實現(xiàn)受到繼承的支持111四、例題講解：程序設(shè)計基礎(chǔ) 結(jié)構(gòu)化程序設(shè)計的3種結(jié)構(gòu)是（ D ） A) 順序結(jié)構(gòu)、選擇結(jié)構(gòu)、轉(zhuǎn)移結(jié)構(gòu) B) 分支結(jié)構(gòu)、等價結(jié)構(gòu)、循環(huán)結(jié)構(gòu) C) 多分支結(jié)構(gòu)、賦值結(jié)構(gòu)、等價結(jié)構(gòu) D) 順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu) 在設(shè)計程序時，應(yīng)采納的原則之一是（ D ） A) 不限制goto語句的使用 B) 減少或

54、取消注解行 C) 程序越短越好 D) 程序結(jié)構(gòu)應(yīng)有助于讀者理解112 程序設(shè)計語言的基本成分是數(shù)據(jù)成分、運算成分、控制成 分和（ D ） A) 對象成分 B) 變量成分 C) 語句成分D) 傳輸成分程序設(shè)計基礎(chǔ) 結(jié)構(gòu)化程序設(shè)計主要強調(diào)的是（ D ） A) 程序的規(guī)模B) 程序的效率 C) 程序設(shè)計語言的先進性 D) 程序易讀性 以下不屬于對象的基本特點的是（ C ） A) 分類性 B) 多態(tài)性 C) 繼承性 D) 封裝性113 對建立良好的程序設(shè)計風格，下面描述正確的是（ A ） A) 程序應(yīng)簡單、清晰、可讀性好 B) 符號名的命名只要符合語法 C) 充分考慮程序的執(zhí)行效率 D) 程序的注釋可

55、有可無 在結(jié)構(gòu)化程序設(shè)計思想提出之前，在程序設(shè)計中曾強調(diào)程序 的效率，現(xiàn)在，與程序的效率相比，人們更重視程序的（C） A) 安全性 B) 一致性 C) 可理解性D) 合理性程序設(shè)計基礎(chǔ)114 下列敘述中，不屬于結(jié)構(gòu)化程序設(shè)計方法的主要原則的是（B） A) 自頂向下 B) 由底向上 C) 模塊化D) 限制使用goto語句 對象實現(xiàn)了數(shù)據(jù)和操作的結(jié)合，是指對數(shù)據(jù)和數(shù)據(jù)的操作進行（ C ） A) 結(jié)合 B) 隱藏 C) 封裝 D) 抽象 在面向?qū)ο蠓椒ㄖ?，一個對象請求另一個對象為其服務(wù)的方式是通過發(fā)送（ D ）A）調(diào)用語句 B）命令 C）口令 D）消息程序設(shè)計基礎(chǔ)115 信息屏蔽的概念與下述哪一種概

56、念直接相關(guān)（ B ）A）軟件結(jié)構(gòu)定義 B）模塊獨立性C）模塊類型劃分 D）模塊耦合度 下列對對象概念描述錯誤的是（ A ）A）任何對象都必須有繼承性B）對象是屬性和方法的封裝體C）對象間的通訊靠消息傳遞D）操作是對象的動態(tài)屬性程序設(shè)計基礎(chǔ)116面向?qū)ο蟮脑O(shè)計方法與傳統(tǒng)的面向過程的方法有本質(zhì)的不同,它的基本原理是（ C ） A) 模擬現(xiàn)實世界中不同事物之間的聯(lián)系 B) 強調(diào)模擬現(xiàn)實世界中的算法而不強調(diào)概念 C) 使用現(xiàn)實世界的概念抽象地思考問題從而自然地解決問題 D) 鼓勵開發(fā)者在軟件開發(fā)的絕大部分中都用實際領(lǐng)域的概念去思考 在面向?qū)ο蟮某绦蛟O(shè)計中，類描述的是具有相似性質(zhì)的一組 【1】?！敬鸢浮?/p>

57、對象 在面向?qū)ο蠓椒ㄖ校愔g共享屬性和操作的機制稱為 【2】?！敬鸢浮坷^承 一個類可以從直接或間接的祖先中繼承所有屬性和方法。采用這個方法提高了軟件的 【3】。【答案】可重用性 117在面向?qū)ο蟮哪Ｐ椭?，最基本的概念是對象和?】。 【答案】：類 在面向?qū)ο蟮脑O(shè)計中，用來請求對象執(zhí)行某一處理或回答某些信息的要求稱為【5】。 【答案】：消息在程序設(shè)計階段應(yīng)該采取 【6】 和逐步求精的方法，把一個模塊的功能逐步分解，細化為一系列具體的步驟，進而用某種程序設(shè)計語言寫成程序。 【答案】 ：自頂向下程序設(shè)計基礎(chǔ)118【7】是一種信息隱蔽技術(shù)，目的在于將對象的使用者和對象的設(shè)計者分開?！敬鸢浮浚悍庋b可以

58、把具有相同屬性的一些不同對象歸類，稱為 【8】 。 【答案】：對象類子程序通常分為兩類：【9】和函數(shù)，前者是命令的抽象，后者是為了求值。 【答案】：過程源程序文檔化要求程序應(yīng)加注釋。注釋一般分為序言性注釋和【10】。 【答案】：功能性注釋在面向?qū)ο蠓椒ㄖ?，信息屏蔽是通過對象的【11】 性來實現(xiàn)的。 【答案】 ：封裝類是一個支持集成的抽象數(shù)據(jù)類型，而對象是類的【12】 。 【答案】：實例 在面向?qū)ο蠓椒ㄖ校愔g共享屬性和操作的機制稱為【13】。 【答案】：繼承119第三章 軟件工程基礎(chǔ)二級公共基礎(chǔ)知識返回120軟件工程基礎(chǔ)內(nèi)容1、軟件工程基本概念，軟件生命周期概念，軟件工具與軟件開發(fā)環(huán)境。2、

59、結(jié)構(gòu)化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說明書。3、結(jié)構(gòu)化設(shè)計方法，總體設(shè)計與詳細設(shè)計。4、軟件測試的方法，白盒測試與黑盒測試，測試用例設(shè)計，軟件測試的實施，單元測試、集成測試和系統(tǒng)測試。5、程序的調(diào)試，靜態(tài)調(diào)試與動態(tài)調(diào)試。121軟件工程基礎(chǔ)（一）基本概念 軟件工程：軟件工程是指應(yīng)用計算機科學、數(shù)學及管理 科學等原理，以工程化的原則和方法來解決軟件問題的 工程。其目的是提高軟件生產(chǎn)率、提高軟件質(zhì)量、降低 軟件成本。 軟件危機：是指在計算機軟件開發(fā)和維護過程中所遇到的一系列嚴重的問題。主要表現(xiàn)在：成本、質(zhì)量、生產(chǎn)率等問題。122軟件生命周期將軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停止使用退役的

60、過程稱為軟件生命周期。分為軟件定義、軟件開發(fā)及軟件運行維護3個時期。維護是持續(xù)時間最長，花費代價最大的一個時期，軟件工程學的一個目的就是提高軟件的可維護性，降低維護代價。6個活動階段：可行性研究與計劃制定：確定系統(tǒng)的總體目標。參加人員有用戶、項目負責人和系統(tǒng)分析員，產(chǎn)生文檔有可行性分析報告、項目計劃書等。需求分析：確定系統(tǒng)的邏輯模型。參加人員有用戶、項目負責人和系統(tǒng)分析員。產(chǎn)生文檔為需求規(guī)格說明書，其作用：（1）便于用戶、開發(fā)人員進行理解交流；（2）反映用戶問題的結(jié)構(gòu)，可以作為軟件開發(fā)工作的基礎(chǔ)和依據(jù)；（3）作為確認測試和驗收的依據(jù)。123軟件設(shè)計：包括軟件結(jié)構(gòu)設(shè)計、數(shù)據(jù)設(shè)計、接口設(shè)計和過程設(shè)