計(jì)算機(jī)C語(yǔ)言基礎(chǔ)知識(shí)

1、順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)（或重復(fù)結(jié)構(gòu)）是結(jié)構(gòu)化程序設(shè)計(jì)的3種基本結(jié)構(gòu)。數(shù)據(jù)定義語(yǔ)言（Data Definition Language，簡(jiǎn)稱DDL）負(fù)責(zé)數(shù)據(jù)的模式定義與數(shù)據(jù)的物理存取構(gòu)建；數(shù)據(jù)操縱語(yǔ)言（Data Manipulation Language，簡(jiǎn)稱DML）負(fù)責(zé)數(shù)據(jù)的操縱，包括查詢及增、刪、改等操作。數(shù)據(jù)定義語(yǔ)言（Data Definition Language，簡(jiǎn)稱DDL）負(fù)責(zé)數(shù)據(jù)的模式定義與數(shù)據(jù)的物理存取構(gòu)建；數(shù)據(jù)操縱語(yǔ)言（Data Manipulation Language，簡(jiǎn)稱DML）負(fù)責(zé)數(shù)據(jù)的操縱，包括查詢及增、刪、改等操作。數(shù)據(jù)庫(kù)（Database，簡(jiǎn)稱DB）是數(shù)據(jù)的集

2、合，它具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲(chǔ)介質(zhì)內(nèi)，是多種應(yīng)用數(shù)據(jù)的集成，并可被各個(gè)應(yīng)用程序所共享。數(shù)據(jù)庫(kù)中的數(shù)據(jù)具有“集成”、“共享”之特點(diǎn)。數(shù)據(jù)處理是指將數(shù)據(jù)轉(zhuǎn)換成信息的過(guò)程，故選項(xiàng)A）敘述錯(cuò)誤；數(shù)據(jù)的物理獨(dú)立性是指數(shù)據(jù)的物理結(jié)構(gòu)的改變，不會(huì)影響數(shù)據(jù)庫(kù)的邏輯結(jié)構(gòu)，故選項(xiàng)B）敘述錯(cuò)誤；關(guān)系中的行稱為元組，對(duì)應(yīng)存儲(chǔ)文件中的記錄，關(guān)系中的列稱為屬性，對(duì)應(yīng)存儲(chǔ)文件中的字段，故選項(xiàng)C）敘述錯(cuò)誤。數(shù)據(jù)庫(kù)系統(tǒng)是由5部分組成：硬件系統(tǒng)、數(shù)據(jù)庫(kù)集合、數(shù)據(jù)庫(kù)管理系統(tǒng)及相關(guān)軟件、數(shù)據(jù)庫(kù)管理員（DataBase Administrator ，DBA）、用戶。數(shù)據(jù)處理的最小單位是數(shù)據(jù)項(xiàng)；由若干數(shù)據(jù)項(xiàng)組成數(shù)據(jù)元素；而數(shù)

3、據(jù)是指能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的信息載體；數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)之間的相互關(guān)系和數(shù)據(jù)運(yùn)算。用樹(shù)型結(jié)構(gòu)表示實(shí)體類(lèi)型及實(shí)體間聯(lián)系的數(shù)據(jù)模型稱為層次模型，用有向圖結(jié)構(gòu)表示實(shí)體類(lèi)型及實(shí)體間聯(lián)系的數(shù)據(jù)模型稱為網(wǎng)狀模型，用二維表格結(jié)構(gòu)表示實(shí)體及其聯(lián)系的數(shù)據(jù)模型稱為關(guān)系模型。分布式數(shù)據(jù)庫(kù)系統(tǒng)具有數(shù)據(jù)分布性、邏輯整體性、位置透明性和復(fù)制透明性的特點(diǎn)，其數(shù)據(jù)也是分布的；但分布式數(shù)據(jù)庫(kù)系統(tǒng)中數(shù)據(jù)經(jīng)常重復(fù)存儲(chǔ)，數(shù)據(jù)也并非必須重復(fù)存儲(chǔ)，主要視數(shù)據(jù)的分配模式而定。若分配模式是一對(duì)多，即一個(gè)片段分配到多個(gè)場(chǎng)地存放，則是冗余的數(shù)據(jù)庫(kù)，否則是非冗余的數(shù)據(jù)庫(kù)。數(shù)據(jù)模型是對(duì)客觀事物及聯(lián)系的數(shù)據(jù)描述，它反映了實(shí)體內(nèi)部及實(shí)體與實(shí)體

4、之間的聯(lián)系。因此，數(shù)據(jù)模型是數(shù)據(jù)庫(kù)設(shè)計(jì)的核心。數(shù)據(jù)模型所描述的內(nèi)容有3個(gè)部分，它們是數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作和數(shù)據(jù)約束。其中，數(shù)據(jù)模型中的數(shù)據(jù)結(jié)構(gòu)主要描述數(shù)據(jù)的類(lèi)型、內(nèi)容、性質(zhì)，以及數(shù)據(jù)庫(kù)的聯(lián)系等；數(shù)據(jù)操作主要是描述在相應(yīng)數(shù)據(jù)結(jié)構(gòu)上的操作類(lèi)型與操作方式。一旦數(shù)據(jù)庫(kù)中的數(shù)據(jù)遭受破壞，需要及時(shí)進(jìn)行恢復(fù)，RDBMS一般都提供此種功能，并由DBA負(fù)責(zé)執(zhí)行故障恢復(fù)功能。層次數(shù)據(jù)模型的特點(diǎn)：有且只有一個(gè)節(jié)點(diǎn)無(wú)雙親，這個(gè)節(jié)點(diǎn)稱為“根節(jié)點(diǎn)”；其他節(jié)點(diǎn)有且只有一個(gè)雙親。網(wǎng)狀數(shù)據(jù)模型的特點(diǎn)：允許一個(gè)以上節(jié)點(diǎn)無(wú)雙親；一個(gè)節(jié)點(diǎn)可以有多余一個(gè)的雙親。關(guān)系數(shù)據(jù)模型是以二維表的形式來(lái)表示的。關(guān)系數(shù)據(jù)庫(kù)中的關(guān)系演算包括元組關(guān)系演算

5、和域關(guān)系演算。二者都是由原子公式組成的公式。而這些關(guān)系演算都是以數(shù)理邏輯中的謂詞演算為基礎(chǔ)的。Access中，一個(gè)表就是一個(gè)關(guān)系，每一個(gè)關(guān)系都是一個(gè)二維表。在Access數(shù)據(jù)庫(kù)中表之間的關(guān)系也一般為一對(duì)多型。關(guān)系模型中的“關(guān)系”是指那種具有相關(guān)性，但非從屬性的平行的數(shù)據(jù)之間按照某種序列排序的集合關(guān)系。關(guān)系表中，每一行稱為一個(gè)元組，對(duì)應(yīng)表中的一條記錄；每一列稱為表中的一個(gè)屬性，對(duì)應(yīng)表中的一個(gè)字段；在二維表中凡能惟一標(biāo)識(shí)元組的最小屬性集稱為該表的鍵或碼。關(guān)系模型較之格式化模型（網(wǎng)狀模型和層次模型）有以下方面的優(yōu)點(diǎn)，即數(shù)據(jù)結(jié)構(gòu)比較簡(jiǎn)單、具有很高的數(shù)據(jù)獨(dú)立性、可以直接處理多對(duì)多的聯(lián)系，以及有堅(jiān)實(shí)的理論

6、基礎(chǔ)。數(shù)據(jù)庫(kù)管理系統(tǒng)是位于用戶與操作系統(tǒng)之間的一層系統(tǒng)管理軟件，是一種系統(tǒng)軟件，是用戶與數(shù)據(jù)庫(kù)之間的一個(gè)標(biāo)準(zhǔn)接口。其總是基于某種數(shù)據(jù)模型，可以分為層次模型、網(wǎng)狀模型和關(guān)系模型。為了合理組織數(shù)據(jù)，應(yīng)遵從的設(shè)計(jì)原則是A）關(guān)系數(shù)據(jù)庫(kù)的設(shè)計(jì)應(yīng)遵從概念單一化“一事一地”的原則B）避免在表中出現(xiàn)重復(fù)字段C）用外部關(guān)鍵字保證有關(guān)聯(lián)的表之間的聯(lián)系數(shù)據(jù)管理技術(shù)經(jīng)歷了人工處理階段、文件系統(tǒng)和數(shù)據(jù)庫(kù)系統(tǒng)、分布式數(shù)據(jù)庫(kù)系統(tǒng)、面向?qū)ο髷?shù)據(jù)庫(kù)系統(tǒng)5個(gè)發(fā)展階段。在數(shù)據(jù)管理技術(shù)的發(fā)展過(guò)程中，經(jīng)歷了人工管理階段、文件系統(tǒng)階段和數(shù)據(jù)庫(kù)系統(tǒng)階段。其中數(shù)據(jù)獨(dú)立性最高的階段是數(shù)據(jù)庫(kù)系統(tǒng)在文件系統(tǒng)中，相互獨(dú)立的記錄其內(nèi)部結(jié)構(gòu)的最簡(jiǎn)單形式

7、是等長(zhǎng)同格式記錄的集合，易造成存儲(chǔ)空間大量浪費(fèi)，不方便使用。而在數(shù)據(jù)庫(kù)系統(tǒng)中，數(shù)據(jù)是結(jié)構(gòu)化的，這種結(jié)構(gòu)化要求在描述數(shù)據(jù)時(shí)不僅描述數(shù)據(jù)本身，還要描述數(shù)據(jù)間的關(guān)系，這正是通過(guò)采用特定的數(shù)據(jù)模型來(lái)實(shí)現(xiàn)的。數(shù)據(jù)庫(kù)設(shè)計(jì)包括兩個(gè)方面的設(shè)計(jì)內(nèi)容，它們是概念設(shè)計(jì)和邏輯設(shè)計(jì)實(shí)體是客觀存在且可以相互區(qū)別的事物。實(shí)體可以是具體的對(duì)象，如一個(gè)學(xué)生，也可以是一個(gè)抽象的事件，如一次出門(mén)旅游等。因此，實(shí)體既可以是有生命的事物，也可以是無(wú)生命的事物，但它必須是客觀存在的，而且可以相互區(qū)別。數(shù)據(jù)庫(kù)系統(tǒng)的數(shù)據(jù)具有高共享性和低冗余性，但不能完全避免數(shù)據(jù)冗余；數(shù)據(jù)的一致性是指在系統(tǒng)中同一數(shù)據(jù)的不同出現(xiàn)應(yīng)保持相同的值。(第四套第九題答

8、案錯(cuò)誤，應(yīng)該為A)數(shù)據(jù)獨(dú)立性是數(shù)據(jù)與程序間的互不依賴性，即數(shù)據(jù)庫(kù)中數(shù)據(jù)獨(dú)立于應(yīng)用程序而不依賴于應(yīng)用程序。也就是說(shuō)，數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)與存取方式的改變不會(huì)影響應(yīng)用程序。數(shù)據(jù)獨(dú)立性一般分為物理獨(dú)立性與邏輯獨(dú)立性兩級(jí)。當(dāng)數(shù)據(jù)的物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)、存取方式等）改變時(shí)，不影響數(shù)據(jù)庫(kù)的邏輯結(jié)構(gòu)，從而不致引起應(yīng)用程序的變化，這是指數(shù)據(jù)的物理獨(dú)立性。外模式是用戶的數(shù)據(jù)視圖，也就是用戶所見(jiàn)到的數(shù)據(jù)模式；全局?jǐn)?shù)據(jù)視圖的描述稱為概念模式，即數(shù)據(jù)庫(kù)中全部數(shù)據(jù)的整體邏輯結(jié)構(gòu)的描述；物理存儲(chǔ)數(shù)據(jù)視圖的描述稱為內(nèi)模式，即數(shù)據(jù)庫(kù)在物理存儲(chǔ)方面的描述；存儲(chǔ)模式即為內(nèi)模式。內(nèi)模式（Internal Schema）又稱物理模

9、式（Physical Schema），它給出了數(shù)據(jù)庫(kù)物理存儲(chǔ)結(jié)構(gòu)與物理存取方法，如數(shù)據(jù)存儲(chǔ)的文件結(jié)構(gòu)、索引、集簇及hash等存取方式與存取路徑。數(shù)據(jù)庫(kù)邏輯設(shè)計(jì)的主要工作是將E-R圖轉(zhuǎn)換成指定RDBMS中的關(guān)系模式。首先，從E-R圖到關(guān)系模式的轉(zhuǎn)換是比較直接的，實(shí)體與聯(lián)系都可以表示成關(guān)系，E-R圖中屬性也可以轉(zhuǎn)換成關(guān)系的屬性。實(shí)體集也可以轉(zhuǎn)換成關(guān)系。E-R模型即實(shí)體-聯(lián)系模型，是將現(xiàn)實(shí)世界的要求轉(zhuǎn)化成實(shí)體、聯(lián)系、屬性等幾個(gè)基本概念，以及它們之間的兩種聯(lián)接關(guān)系。數(shù)據(jù)庫(kù)邏輯設(shè)計(jì)階段包括以下幾個(gè)過(guò)程：從E-R圖向關(guān)系模式轉(zhuǎn)換，邏輯模式規(guī)范化及調(diào)整、實(shí)現(xiàn)規(guī)范化和RDBMS，以及關(guān)系視圖設(shè)計(jì)。關(guān)系模型允許

10、定義3類(lèi)數(shù)據(jù)約束，它們是實(shí)體完整性約束、參照完整性約束及用戶自定義的完整性約束。其中前兩種完整性約束由關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)支持，對(duì)于用戶自定義的完整性約束，則由關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)提供完整性約束語(yǔ)言，用戶利用該語(yǔ)言給出約束條件，運(yùn)行時(shí)由系統(tǒng)自動(dòng)檢查。數(shù)據(jù)庫(kù)設(shè)計(jì)分為以下6個(gè)設(shè)計(jì)階段：需求分析階段、概念設(shè)計(jì)階段、邏輯設(shè)計(jì)階段、物理設(shè)計(jì)階段、實(shí)施階段及數(shù)據(jù)庫(kù)運(yùn)行和維護(hù)階段。數(shù)據(jù)庫(kù)中的數(shù)據(jù)具有“集成”與“共享”的特點(diǎn)，亦即是數(shù)據(jù)庫(kù)集中了各種應(yīng)用的數(shù)據(jù)，進(jìn)行統(tǒng)一構(gòu)造與存儲(chǔ)，而使它們可以被不同應(yīng)用程序所使用，數(shù)據(jù)是現(xiàn)實(shí)世界符號(hào)的抽象，而數(shù)據(jù)模型（data model）則是數(shù)據(jù)特征的抽象，它從抽象層次上描述了系統(tǒng)的靜態(tài)

11、特征、動(dòng)態(tài)行為和約束行為，為數(shù)據(jù)庫(kù)系統(tǒng)的信息表示與操作提供一個(gè)抽象的框架。數(shù)據(jù)模型按不同的應(yīng)用層次分成3種類(lèi)型，它們是概念數(shù)據(jù)模型（conceptual data model）、邏輯數(shù)據(jù)模型（logic data model）、物理數(shù)據(jù)模型（physical data model）。數(shù)據(jù)庫(kù)系統(tǒng)（Database System，簡(jiǎn)稱DBS）包括數(shù)據(jù)庫(kù)（Database，簡(jiǎn)稱DB）和數(shù)據(jù)庫(kù)管理系統(tǒng)（Database Management System，簡(jiǎn)稱DBMS）。SQL語(yǔ)句中凡創(chuàng)建都用CREATE，刪除都用DROP，改變用ALTER，再跟類(lèi)型和名字，附加子句。SQL語(yǔ)句中，用于修改表結(jié)構(gòu)的是A

12、LTER關(guān)鍵字ASC和DESC分別表示升序排列和降序排列的含義。對(duì)象有如下一些基本特點(diǎn)，即標(biāo)識(shí)惟一性、分類(lèi)性、多態(tài)性、封裝性和模塊獨(dú)立性。類(lèi)是面向?qū)ο笳Z(yǔ)言中必備的程序語(yǔ)言結(jié)構(gòu)，用來(lái)實(shí)現(xiàn)抽象數(shù)據(jù)類(lèi)型。類(lèi)與類(lèi)之間的繼承關(guān)系實(shí)現(xiàn)了類(lèi)之間的共享屬性和操作，一個(gè)類(lèi)可以在另一個(gè)已定義的類(lèi)的基礎(chǔ)上定義，這樣使該類(lèi)型繼承了其超類(lèi)的屬性和方法，當(dāng)然，也可以定義自己的屬性和方法。在面向?qū)ο蠓椒ㄖ?，?lèi)之間共享屬性和操作的機(jī)制稱為繼承。將屬性、操作相似的對(duì)象歸為類(lèi)，也就是說(shuō)，類(lèi)是具有共同屬性、共同方法的對(duì)象的集合。在面向?qū)ο蟮脑O(shè)計(jì)中，用來(lái)請(qǐng)求對(duì)象執(zhí)行某一處理或回答某些信息的要求稱為消息。相似的對(duì)象可以共享程序代碼和數(shù)

13、據(jù)結(jié)構(gòu)，從而大大減少了程序中的冗余，提高軟件的可重用性。面向?qū)ο竽Ｐ椭?，最基本的概念是?duì)象和類(lèi)。對(duì)象是現(xiàn)實(shí)世界中實(shí)體的模型化；將屬性集和方法集相同的所有對(duì)象組合在一起，可以構(gòu)成一個(gè)類(lèi)。將屬性、操作相似的對(duì)象歸為類(lèi)，也就是說(shuō)，類(lèi)是具有共同屬性、共同方法的對(duì)象的集合。所以，類(lèi)是對(duì)象的抽象，對(duì)象則是其對(duì)應(yīng)類(lèi)的一個(gè)實(shí)例。模塊化是指解決一個(gè)復(fù)雜問(wèn)題時(shí)自頂向下逐層把軟件系統(tǒng)劃分成若干模塊的過(guò)程，由此分解來(lái)降低復(fù)雜性。軟件設(shè)計(jì)模塊化的目的是降低復(fù)雜性。算法是指解題方案的準(zhǔn)確而完整的描述。它有4個(gè)基本特征，分別是可行性、確定性、有窮性和擁有足夠的情報(bào)。算法分析是指對(duì)一個(gè)算法的運(yùn)行時(shí)間和占用空間做定量的分析，一

14、般計(jì)算出相應(yīng)的數(shù)量級(jí)，常用時(shí)間復(fù)雜度和空間復(fù)雜度表示。分析算法的目的就是要降低算法的時(shí)間復(fù)雜度和空間復(fù)雜度，提高算法的執(zhí)行效率。在算法正確的前提下，評(píng)價(jià)一個(gè)算法的兩個(gè)標(biāo)準(zhǔn)是時(shí)間復(fù)雜度和空間復(fù)雜度。算法的復(fù)雜度主要包括算法的時(shí)間復(fù)雜度和算法的空間復(fù)雜度。所謂算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量；算法的空間復(fù)雜度一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)；數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式。在數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)元素的信息，還需要存放各數(shù)據(jù)元素之間的前后件關(guān)系的信息。數(shù)據(jù)結(jié)構(gòu)概念一般包括3個(gè)方面的內(nèi)容

15、，數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及數(shù)據(jù)上的運(yùn)算集合。數(shù)據(jù)的邏輯結(jié)構(gòu)只抽象的反映數(shù)據(jù)元素之間的邏輯關(guān)系，而不管它在計(jì)算機(jī)中的存儲(chǔ)表示形式。數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)元素及其之間的相互關(guān)系和數(shù)據(jù)運(yùn)算的一門(mén)學(xué)科，它包含3個(gè)方面的內(nèi)容，即數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算。數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類(lèi)。數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)，線性鏈表屬于存儲(chǔ)結(jié)構(gòu)常用的存儲(chǔ)表示方法有4種，順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)、散列存儲(chǔ)。其中，順序存儲(chǔ)方法是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置也相鄰的存儲(chǔ)單元中。串的長(zhǎng)度指的是串中的字符的個(gè)數(shù)，且其字符個(gè)數(shù)可以為零。若串s="MathTypes"，則其子

16、串的數(shù)目是46。串s中共有9個(gè)字符，由于串中字符各不相同，則其子串中有0個(gè)字符的1個(gè)（空串），1個(gè)字符的9個(gè)，2個(gè)字符的8個(gè)，3個(gè)字符的7個(gè)，4個(gè)字符的6個(gè)，5個(gè)字符的5個(gè)，6個(gè)字符的4個(gè)，7個(gè)字符的3個(gè)，8個(gè)字符的2個(gè)，9個(gè)字符的1個(gè)，共有1+2+3+4+5+6+7+8+9+1=46。線性表是一種線性結(jié)構(gòu)，數(shù)據(jù)元素在線性表中的位置只取決于它們自己的序號(hào)，即數(shù)據(jù)元素之間的相對(duì)位置是線性的；棧、隊(duì)列、線性鏈表實(shí)際上也是線性表，故也是線性結(jié)構(gòu)；樹(shù)是一種簡(jiǎn)單的非線性結(jié)構(gòu)。線性表：線性表可以為空表；第一個(gè)元素沒(méi)有直接前件，最后一個(gè)元素沒(méi)有直接后件；線性表的定義中，元素的排列并沒(méi)有規(guī)定大小順序。在單鏈表

17、中，增加頭結(jié)點(diǎn)的目的是方便運(yùn)算的實(shí)現(xiàn)。頭結(jié)點(diǎn)不僅標(biāo)識(shí)了表中首結(jié)點(diǎn)的位置，而且根據(jù)單鏈表（包含頭結(jié)點(diǎn)）的結(jié)構(gòu)，只要掌握了表頭，就能夠訪問(wèn)整個(gè)鏈表，因此增加頭結(jié)點(diǎn)目的是為了便于運(yùn)算的實(shí)現(xiàn)。循環(huán)鏈表就是將鏈表的最后一個(gè)結(jié)點(diǎn)指向鏈表頭結(jié)點(diǎn)（或第一個(gè)結(jié)點(diǎn)），即p->next=head。循環(huán)鏈表就是將單向鏈表中最后一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，使整個(gè)鏈表構(gòu)成一個(gè)環(huán)形，這樣的結(jié)構(gòu)使得從表中的任一結(jié)點(diǎn)出發(fā)都能訪問(wèn)到整個(gè)鏈表。棧和隊(duì)列都是一種特殊的操作受限的線性表，只允許在端點(diǎn)處進(jìn)行插入和刪除。二者的區(qū)別是：棧只允許在表的一端進(jìn)行插入或刪除操作，是一種“后進(jìn)先出”的線性表；而隊(duì)列只允許在表的一端進(jìn)行插入操作，

18、在另一端進(jìn)行刪除操作，是一種“先進(jìn)先出”的線性表。在線性表的任何位置插入一個(gè)元素的概率相等，即概率為p=1/（n+1），則插入一個(gè)元素時(shí)所需移動(dòng)元素的平均次數(shù)為E=n/2。如果進(jìn)棧序列為e1,e2,e3,e4，則可能的出棧序列是e2,e4,e3,e1棧底至棧頂依次存放元素A、B、C、D，在第五個(gè)元素E入棧前，棧中元素可以出棧，則出棧序列可能是由?！昂筮M(jìn)先出”的特點(diǎn)可知：A）中e1不可能比e2先出，C）中e3不可能比e4先出，且e1不可能比e2先出，D）中棧是先進(jìn)后出的，所以不可能是任意順序。B）中出棧過(guò)程如圖所示：鏈表采用的是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，它克服了順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)：它的結(jié)點(diǎn)空間可以動(dòng)態(tài)申請(qǐng)和

19、釋放；它的數(shù)據(jù)元素的邏輯次序靠結(jié)點(diǎn)的指針來(lái)指示，不需要移動(dòng)數(shù)據(jù)元素。但是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也有不足之處：每個(gè)結(jié)點(diǎn)中的指針域需額外占用存儲(chǔ)空間；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種非隨機(jī)存儲(chǔ)結(jié)構(gòu)。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)克服了順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)：它的結(jié)點(diǎn)空間可以動(dòng)態(tài)申請(qǐng)和釋放；它的數(shù)據(jù)元素的邏輯次序靠結(jié)點(diǎn)的指針來(lái)指示，不需要移動(dòng)數(shù)據(jù)元素。故鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性表便于插入和刪除操作。對(duì)于長(zhǎng)度為n的有序線性表，在最壞情況下，二分查找只需要比較log2n次，而順序查找需要比較n次。一些重要的程序語(yǔ)言（如C語(yǔ)言和Pascal語(yǔ)言）允許過(guò)程的遞歸調(diào)用。而實(shí)現(xiàn)遞歸調(diào)用中的存儲(chǔ)分配通常用棧一些較流行的程序語(yǔ)言允許過(guò)程的遞歸調(diào)用。遞歸調(diào)用就是過(guò)程

20、調(diào)用本身。遞歸實(shí)現(xiàn)的是：當(dāng)過(guò)程每一次執(zhí)行后，都能返回到最近一次調(diào)用它的過(guò)程中。這樣各調(diào)用點(diǎn)之間形成一種后進(jìn)先出關(guān)系，而棧結(jié)構(gòu)正適合來(lái)存儲(chǔ)這些調(diào)用點(diǎn)。假設(shè)線性表的長(zhǎng)度為n，則在最壞情況下，冒泡排序要經(jīng)過(guò)n/2遍的從前往后的掃描和n/2遍的從后往前的掃描，需要的比較次數(shù)為n（n-1）/2。當(dāng)數(shù)據(jù)表A中每個(gè)元素距其最終位置不遠(yuǎn)，說(shuō)明數(shù)據(jù)表A按關(guān)鍵字值基本有序，在待排序序列基本有序的情況下，采用插入排序所用時(shí)間最少，故應(yīng)采用的算法是直接插入排序根據(jù)冒泡排序算法思想可知，若待排序的初始序列為“正序”序列，則只需進(jìn)行一趟排序，在排序過(guò)程中進(jìn)行n-1次關(guān)鍵字間的比較，且不移動(dòng)和交換記錄，這種情況是冒泡排序的

21、最好情況，故冒泡排序算法在最好的情況下的元素交換次數(shù)為0。在最壞情況下，堆排序需要比較的次數(shù)為O(log2n)。在有向圖中，若任意兩個(gè)頂點(diǎn)都連通，則稱該圖是強(qiáng)連通圖，這樣的有向圖的形狀是環(huán)狀，因而至少應(yīng)有n條邊。二叉樹(shù)依據(jù)后序遍歷序列可確定根結(jié)點(diǎn)為c；再依據(jù)中序遍歷序列可知其左子樹(shù)由deba構(gòu)成，右子樹(shù)為空；又由左子樹(shù)的后序遍歷序列可知其根結(jié)點(diǎn)為e，由中序遍歷序列可知其左子樹(shù)為d，右子樹(shù)由ba構(gòu)成，如下圖所示。求得該二叉樹(shù)的前序遍歷序列為選項(xiàng)D）。利用前序和中序遍歷的方法可以確定二叉樹(shù)的結(jié)構(gòu)，具體步驟如下：前序遍歷的第一個(gè)結(jié)點(diǎn)A為樹(shù)的根結(jié)點(diǎn)；中序遍歷中A的左邊的結(jié)點(diǎn)為A的左子樹(shù)，A右邊的結(jié)點(diǎn)為

22、A的右子樹(shù)；再分別對(duì)A的左右子樹(shù)進(jìn)行上述兩步處理，直到每個(gè)結(jié)點(diǎn)都找到正確的位置。已知一棵二叉樹(shù)前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF，則該二叉樹(shù)的后序遍歷為DGEBHFCA若某二叉樹(shù)的前序遍歷訪問(wèn)順序是abdgcefh，中序遍歷訪問(wèn)順序是dgbaechf，則其后序遍歷的結(jié)點(diǎn)訪問(wèn)順序是gdbehfca所謂滿二叉樹(shù)是指這樣的一種二叉樹(shù)：除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)葉子結(jié)點(diǎn)。這就是說(shuō)，在滿二叉樹(shù)中，層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值，即在滿二叉樹(shù)的第k層上有2k-1個(gè)結(jié)點(diǎn)，且深度為m的滿二叉樹(shù)有2m-1個(gè)結(jié)點(diǎn)。在深度為5的滿二叉樹(shù)中，葉子結(jié)點(diǎn)的個(gè)數(shù)為31樹(shù)是一個(gè)或多個(gè)結(jié)點(diǎn)組成的

23、有限集合，其中一個(gè)特定的結(jié)點(diǎn)稱為根，其余結(jié)點(diǎn)分為若干個(gè)不相交的集合。每個(gè)集合同時(shí)又是一棵樹(shù)。樹(shù)有且只有1個(gè)根結(jié)點(diǎn)。在樹(shù)形結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)，沒(méi)有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹(shù)的根結(jié)點(diǎn)；每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，它們都稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒(méi)有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。軟件工程程序設(shè)計(jì)應(yīng)該簡(jiǎn)單易懂，語(yǔ)句構(gòu)造應(yīng)該簡(jiǎn)單直接，不應(yīng)該為提高效率而把語(yǔ)句復(fù)雜化。軟件工程概念的出現(xiàn)源自軟件危機(jī)。所謂軟件危機(jī)是泛指在計(jì)算機(jī)軟件的開(kāi)發(fā)和維護(hù)過(guò)程中所遇到的一系列嚴(yán)重問(wèn)題?？傊梢詫④浖C(jī)歸結(jié)為成本、質(zhì)量、生產(chǎn)率等問(wèn)題。軟件工程概念的出現(xiàn)源自于軟件危機(jī)。為了消除軟件危機(jī)，通過(guò)認(rèn)真研究解決軟件危機(jī)

24、的方法，認(rèn)識(shí)到軟件工程是使計(jì)算機(jī)軟件走向工程科學(xué)的途徑，逐步形成了軟件工程的概念?；谲浖こ痰哪繕?biāo)，軟件工程的理論和技術(shù)性研究的內(nèi)容主要包括：軟件開(kāi)發(fā)技術(shù)和軟件工程管理。軟件開(kāi)發(fā)技術(shù)包括：軟件開(kāi)發(fā)方法學(xué)、開(kāi)發(fā)過(guò)程、開(kāi)發(fā)工具和軟件工程環(huán)境，其主體內(nèi)容是軟件開(kāi)發(fā)方法學(xué)。軟件工程管理包括：軟件管理學(xué)、軟件工程經(jīng)濟(jì)學(xué)，以及軟件心理學(xué)等內(nèi)容。軟件工程的目標(biāo)是，在給定的成本、進(jìn)度的前提下，開(kāi)發(fā)出具有有效性、可靠性、可理解性、可維護(hù)性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品?；谶@一目標(biāo)，軟件工程的理論和技術(shù)性研究的內(nèi)容主要包括：軟件開(kāi)發(fā)技術(shù)和軟件工程管理。開(kāi)發(fā)軟件時(shí)對(duì)提高

25、開(kāi)發(fā)人員工作效率至關(guān)重要的是先進(jìn)的軟件開(kāi)發(fā)工具和環(huán)境軟件工程鼓勵(lì)研制和采用各種先進(jìn)的軟件開(kāi)發(fā)方法、工具和環(huán)境。工具和環(huán)境的使用又進(jìn)一步提高了軟件的開(kāi)發(fā)效率、維護(hù)效率和軟件質(zhì)量。使用人工或自動(dòng)手段來(lái)運(yùn)行或測(cè)定某個(gè)系統(tǒng)的過(guò)程，其目的在于檢驗(yàn)它是否滿足規(guī)定的需求或是弄清預(yù)期結(jié)果與實(shí)際結(jié)果之間的差別。軟件測(cè)試是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過(guò)程。測(cè)試要以查找錯(cuò)誤為中心，而不是為了演示軟件的正確功能。結(jié)構(gòu)化分析的常用工具有數(shù)據(jù)流圖、數(shù)據(jù)字典、判定樹(shù)和判定表。而PAD圖是常見(jiàn)的過(guò)程設(shè)計(jì)工具中的圖形設(shè)計(jì)。在結(jié)構(gòu)化程序設(shè)計(jì)思想提出之前，在程序設(shè)計(jì)中曾強(qiáng)調(diào)程序的效率，現(xiàn)在，與程序的效率相比，人們更重視程序的可理解性。

26、測(cè)試的目的是發(fā)現(xiàn)軟件中的錯(cuò)誤。經(jīng)驗(yàn)表明，程序中存在錯(cuò)誤的概率與該程序中已發(fā)現(xiàn)的錯(cuò)誤數(shù)成正比。這一現(xiàn)象說(shuō)明，為了提高測(cè)試效率，測(cè)試人員應(yīng)該集中對(duì)付那些錯(cuò)誤群集的程序。軟件的白盒測(cè)試方法是把測(cè)試對(duì)象看做一個(gè)打開(kāi)的盒子，它允許測(cè)試人員利用程序內(nèi)部的邏輯結(jié)構(gòu)及有關(guān)信息，設(shè)計(jì)或選擇測(cè)試用例，對(duì)程序所有邏輯路徑進(jìn)行測(cè)試。確認(rèn)測(cè)試的任務(wù)是驗(yàn)證軟件的功能和性能，以及其他特性是否滿足需求規(guī)格說(shuō)明定的各種需求；集成測(cè)試的主要目的是發(fā)現(xiàn)與接口有關(guān)的錯(cuò)誤。典型的數(shù)據(jù)流類(lèi)型有兩種：變換型和事務(wù)型。變換型是指信息沿輸入通路進(jìn)入系統(tǒng)，同時(shí)由外部形式變換成內(nèi)部形式，進(jìn)入系統(tǒng)的信息通過(guò)變換中心，經(jīng)加工處理以后再沿輸出通路變換成

27、外部形式離開(kāi)軟件系統(tǒng)；在很多軟件應(yīng)用中，存在某種作業(yè)數(shù)據(jù)流，它可以引發(fā)一個(gè)或多個(gè)處理，這些處理能夠完成該作業(yè)要求的功能，這種數(shù)據(jù)流就叫做事務(wù)。數(shù)據(jù)流圖包括4個(gè)方面，即加工（轉(zhuǎn)換）（輸入數(shù)據(jù)經(jīng)加工變換產(chǎn)生輸出）、數(shù)據(jù)流（沿箭頭方向傳送數(shù)據(jù)的通道，一般在旁邊標(biāo)注數(shù)據(jù)流名）、存儲(chǔ)文件（數(shù)據(jù)源）（表示處理過(guò)程中存放各種數(shù)據(jù)的文件）、源和潭（表示系統(tǒng)和環(huán)境的接口，屬系統(tǒng)之外的實(shí)體）。不包括選項(xiàng)中的控制流。數(shù)據(jù)流相當(dāng)于一條管道,并有一級(jí)數(shù)據(jù)（信息）流經(jīng)它。在數(shù)據(jù)流圖中，用標(biāo)有名字的箭頭表示數(shù)據(jù)流。數(shù)據(jù)流可以從加工流向加工，也可以從加工流向文件或從文件流向加工，并且可以從外部實(shí)體流向系統(tǒng)或從系統(tǒng)流向外部實(shí)體

28、。軟件的顯著特點(diǎn)是規(guī)模龐大，復(fù)雜度超線性增長(zhǎng)，在開(kāi)發(fā)大型軟件時(shí)，要保證高質(zhì)量，極端復(fù)雜困難，不僅涉及技術(shù)問(wèn)題，更重要的是必須要有嚴(yán)格而科學(xué)的管理。開(kāi)發(fā)大型軟件時(shí)，產(chǎn)生困難的根本原因是大系統(tǒng)的復(fù)雜性軟件生命周期分為軟件定義、軟件開(kāi)發(fā)及軟件運(yùn)行維護(hù)3個(gè)階段。本題中，詳細(xì)設(shè)計(jì)、軟件編碼和軟件測(cè)試都屬于軟件開(kāi)發(fā)階段；維護(hù)是軟件生命周期的最后一個(gè)階段，也是持續(xù)時(shí)間最長(zhǎng)，花費(fèi)代價(jià)最大的一個(gè)階段，軟件工程學(xué)的一個(gè)目的就是提高軟件的可維護(hù)性，降低維護(hù)的代價(jià)。軟件產(chǎn)品從考慮其概念開(kāi)始，到該軟件產(chǎn)品不能使用為止的整個(gè)時(shí)期都屬于軟件生命周期。一般包括可行性研究與需求分析、設(shè)計(jì)、實(shí)現(xiàn)、測(cè)試、交付使用以及維護(hù)等活動(dòng)。濫用goto 語(yǔ)句將使程序流程無(wú)規(guī)律，可讀性差，；注解行有利于對(duì)程序的理解，不應(yīng)減少或取消；程序的長(zhǎng)短要依照實(shí)際情況而論，而不是越短越好；程序結(jié)構(gòu)應(yīng)有助于讀者理解。程序設(shè)計(jì)語(yǔ)言是用于書(shū)寫(xiě)計(jì)算機(jī)程序的語(yǔ)言，其基本成分有以下4種，數(shù)據(jù)成分：用來(lái)描述程序中的數(shù)據(jù)。運(yùn)算成分：描述程序中所需的運(yùn)算?？刂瞥煞郑河脕?lái)構(gòu)造程序的邏輯控制結(jié)構(gòu)。傳輸成分：定義數(shù)據(jù)傳輸成分，如輸入輸出語(yǔ)言。軟件需求是指用戶對(duì)目標(biāo)軟件系統(tǒng)在功能、行