二級公共基礎知識ppt課件

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

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

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

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

5、工具； 6、了解軟件測試的目的和方法，以及軟件測試的準則，了解常用的軟件 測試方法的區(qū)別和各自的功能與特點； 7、了解程序調試的方法和原則 。81、了解程序設計的方法，以及程序設計風格確立的一些因素，掌握程序 設計的基本規(guī)則； 2、了解結構化程序設計的基本原則，掌握結構化程序設計的基本結構與特點;學習目標與要求 程序設計基礎：3、了解面向對象的程序設計方法，并理解面向對象方法的一些基本概念。 數(shù)據(jù)庫系統(tǒng)：1、了解數(shù)據(jù)庫系統(tǒng)的基本概念，以及數(shù)據(jù)庫系統(tǒng)的發(fā)展； 2、了解數(shù)據(jù)模型的基本概念，并對E-R模型、層次模型、網(wǎng)狀模型和關系模型 進行了解，并掌握關系模型的數(shù)據(jù)結構、關系的操作和數(shù)據(jù)約束等知識；

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

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

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

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

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

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

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

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

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

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

16、。例：整數(shù)(1,2)、實數(shù)(1.1,1.2)字符串(Beijing)、圖形、聲音。計算機管理圖書問題 ： 在圖書館里有各種卡片：有按書名編排的、有按作者編排的、有按分類編排。如何將查詢圖書的這些信息存入計算機中既要考慮查詢時間短，又要考慮節(jié)省空間。最簡單的辦法之一是建立一張表，每一本書的信息在表中占一行，如：3030數(shù)據(jù)元素在計算機中的表示 數(shù)據(jù)結構是一門研究數(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é)點進行操作處理（插入、刪除、修改、查找、排序）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ù)結構可描述為 Group=（D，R）有限個數(shù)據(jù)元素的集合有限個節(jié)點間關系的集合3232數(shù)據(jù)結構可描述為 Group=（D，R） 例1：一年四季的數(shù)據(jù)結構可表示成B=（D，R） D=春，夏，秋，冬 R=（春，夏），（夏，秋），（秋，冬） 例2：家庭成員數(shù)據(jù)結構可表示成B=（D，R）D=父親，兒子，女

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

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

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

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

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

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

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

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

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

27、an隊 列 示 意 圖隊頭隊尾 隊列的主要運算（1）設置一個空隊列；（2）插入一個新的隊尾元素，稱為進隊；（3）刪除隊頭元素，稱為出隊；（4）讀取隊頭元素。52出隊入隊rearfront52 循環(huán)隊列及其運算循環(huán)隊列：將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間，供隊列循環(huán)使用。循環(huán)隊列的元素：從排頭指針指向的后一個位置直到隊尾指針指向的位置之間所有的元素。說明：為了能夠區(qū)分隊列滿與空，設置一個標志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語言) 允許過程的遞歸調用。而實現(xiàn)遞歸調用中的存儲分配通常用（ A ） A) 棧 B) 堆 C) 數(shù)組 D) 鏈表 5555 棧底至棧頂依次存放元素A、B、C、D，在第五個元素E 入棧前，棧中元素可以出棧，則出棧序列可能是（ B ） A) ABCED B) DCBEA C) DBCEA D

30、) CDABE 棧通常采用的兩種存儲結構是（ A ） A) 順序存儲結構和鏈表存儲結構 B) 散列方式和索引方式 C) 鏈表存儲結構和數(shù)組 D) 線性存儲結構和非線性存儲結構 棧和隊列通常采用的存儲結構是 【1】。 【答案】鏈式存儲和順序存儲 下列數(shù)據(jù)結構中，按先進后出原則組織數(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ā)生的機率下列關于棧的敘述中正確的是（ D ）)在棧中只能插入數(shù)據(jù) B）在棧中只能刪除數(shù)據(jù)C）棧是先進先出的線性表 D）棧是后進先出的線性表下列關于隊列的敘述中正確的是（ C ）在隊列中只能插入數(shù)據(jù) B）在隊列中只能刪除數(shù)據(jù)C）隊列是先進先出的線性表 D）隊列是后進先出的線性表 5757 順序存儲結構常用于線性數(shù)據(jù)結構，將邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元里。 順序存儲結構的三個缺點： 1.作插入或刪除操作時，需移動大量元數(shù)。 2.長度變化較大時，需按最大空間分配。 3.表的容量難以擴充。存儲內容元素n.元素i.元素2元

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

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

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

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

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

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

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

39、雜。所以引出二叉樹的討論。76767777性質1：在任意一棵二叉樹中，度為0的結點（即葉子結點）總是比度為2的結點多一個。例子1：某二叉樹中度為2的結點有18個，則該二叉樹中有 19 個葉子結點。二叉樹的性質： 特別要注意：二叉樹不是樹的特殊情況。aabb兩棵不同的二叉樹7878性質2：二叉樹的第i層上至多有2 i-1（i 1）個結點二叉樹的性質：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二叉樹的性質：性質3：深度為h的二叉樹中至多

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

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

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

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

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

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

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

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

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

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

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

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

52、入手來研究問題。108消息(Message) 對象之間進行通信的一種構造類（Class）：類是一組具有相同屬性和相同操作的對象的集合。 一個類定義了一組大體上相似的對象。 一個類所包含的方法和數(shù)據(jù)描述一組對象的共同行為和屬性。 類是在對象之上的抽象，對象是類的具體化，是類的實例?；悾河脕砩尚骂惖念悺Ｅ缮悾河梢汛嬖诘念惻缮鰜淼男骂?，也叫子類。繼承：是指能夠直接獲得已有的性質和特征，而不必重復定義他們。繼承分單繼承和多重繼承。109 水上交通工具陸上交通工具水陸兩用交通工具 多 重 繼 承 圖 程序設計基礎單繼承指一個類只允許有一個父類，多重繼承指一個類允許有多個父類。110 程序設計基礎

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

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

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

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

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

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

59、結構化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說明書。3、結構化設計方法，總體設計與詳細設計。4、軟件測試的方法，白盒測試與黑盒測試，測試用例設計，軟件測試的實施，單元測試、集成測試和系統(tǒng)測試。5、程序的調試，靜態(tài)調試與動態(tài)調試。121軟件工程基礎（一）基本概念 軟件工程：軟件工程是指應用計算機科學、數(shù)學及管理 科學等原理，以工程化的原則和方法來解決軟件問題的 工程。其目的是提高軟件生產(chǎn)率、提高軟件質量、降低 軟件成本。 軟件危機：是指在計算機軟件開發(fā)和維護過程中所遇到的一系列嚴重的問題。主要表現(xiàn)在：成本、質量、生產(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）反映用戶問題的結構，可以作為軟件開發(fā)工作的基礎和依據(jù)；（3）作為確認測試和驗收的依據(jù)。123軟件設計：包括軟件結構設計、數(shù)據(jù)設計、接口設計和過程設