1、A效率B. 復(fù)雜性 C. 現(xiàn)實(shí)性D. 難度A程序 B 問(wèn)題求解步驟的描述C要滿足五個(gè)基本特性DA 和 C.第一章 算法【內(nèi)容】 算法：是指解題方案的準(zhǔn)確而完整的描述。 算法不等于程序，也不等計(jì)算機(jī)方法，程序的編 制不可能優(yōu)于算法的設(shè)計(jì)。 K M 算法的基本特征：是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，每一個(gè)規(guī)則都是有效的，是明確的， 此順序?qū)⒃谟邢薜拇螖?shù)下終止。特征包括：(1) 可行性；(2) 確定性，算法中每一步驟都必須有明確定義，不充許有模棱兩可的解釋?zhuān)辉试S有多義 性；(3) 有窮性，算法必須能在有限的時(shí)間內(nèi)做完，即能在執(zhí)行有限個(gè)步驟后終止，包括合理的 執(zhí)行時(shí)間的含義；(4) 擁有足夠的情報(bào)。

2、算法的基本要素：一是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作；二是算法的控制結(jié)構(gòu)。 指令系統(tǒng)：一個(gè)計(jì)算機(jī)系統(tǒng)能執(zhí)行的所有指令的集合。 基本運(yùn)算和操作包括：算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)傳輸。 _ 算法的控制結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。 算法基本設(shè)計(jì)方法：列舉法、歸納法、遞推、遞歸、減斗遞推技術(shù)、回溯法。 算法復(fù)雜度：算法時(shí)間復(fù)雜度和算法空間復(fù)雜度。 算法時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。 用平均性態(tài)，最壞情況復(fù)雜性?xún)煞N方法來(lái)分析算法的工作量。 算法空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。【習(xí)題】一、填空題(1) 算法的復(fù)雜度主要包括 復(fù)雜度和空間復(fù)雜度。答：時(shí)間(2) 算法的基本特征是可

3、行性、確定性、 和擁有足夠的情報(bào)。答：有窮性(3) 實(shí)現(xiàn)算法所需的存儲(chǔ)單元多少和算法的工作量大小分別稱(chēng)為算法的 。答：空間復(fù)雜度和時(shí)間復(fù)雜度(4) 在算法正確的前提下， 評(píng)價(jià)一個(gè)算法的兩個(gè)標(biāo)準(zhǔn)是 。答：時(shí)間復(fù)雜度和空間復(fù)雜度二、選擇題(1) 下面敘述正確的是 。(C)A. 算法的執(zhí)行效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)B. 算法的空間復(fù)雜度是指算法程序中指令(或語(yǔ)句)的條數(shù)C. 算法的有窮性是指算法必須能在執(zhí)行有限個(gè)步驟之后終止D. 以上三種描述都不對(duì)(2) 算法的時(shí)間復(fù)雜度是指 。(C)A. 執(zhí)行算法程序所需要的時(shí)間 B. 算法程序的長(zhǎng)度C. 算法執(zhí)行過(guò)程中所需要的基本運(yùn)算次數(shù)D. 算法程序中的指令條數(shù)

4、(3) 算法的空間復(fù)雜度是指 。(D)A. 算法程序的長(zhǎng)度 B. 算法程序中的指令條數(shù)C. 算法程序所占的存儲(chǔ)空間 D. 算法執(zhí)行過(guò)程中所需要的存儲(chǔ)空間(4) 算法一般都可以用哪幾種控制結(jié)構(gòu)組合而成 。(D)A. 循環(huán)、分支、遞歸 B. 順序、循環(huán)、嵌套 C. 循環(huán)、遞歸、選擇 D. 順序、選擇、循 環(huán)(5) 在下列選項(xiàng)中，哪個(gè)不是一個(gè)算法一般應(yīng)該具有的基本特征 。 (C)A. 確定性 B. 可行性 C. 無(wú)窮性 D. 擁有足夠的情報(bào)(6) 在計(jì)算機(jī)中，算法是指 。 (C)A. 查詢(xún)方法 B. 加工方法 C. 解題方案的準(zhǔn)確而完整的描述 D. 排序方法(7) 算法分析的目的是 。 (D)A.

5、找出數(shù)據(jù)結(jié)構(gòu)的合理性 B. 找出算法中輸入和輸出之間的關(guān)系C. 分析算法的易懂性和可靠性 D. 分析算法的效率以求改進(jìn)(8) 算法的時(shí)間復(fù)雜度取決于 。(D)A問(wèn)題的規(guī)模B. 待處理數(shù)據(jù)的初態(tài)C. A 和 B(9) 算法的計(jì)算量的大小稱(chēng)為計(jì)算的 。 (B)(10) 計(jì)算機(jī)算法指的是( 1)，它必須具備( 2) 這三個(gè)特性。 (C) (B)(1) A 計(jì)算方法 B. 排序方法 C. 解決問(wèn)題的步驟序列 D. 調(diào)度方法(2) A 可執(zhí)行性、可移植性、可擴(kuò)充性B. 可執(zhí)行性、確定性、有窮性C. 確定性、有窮性、穩(wěn)定性 D. 易讀性、穩(wěn)定性、安全性(11) 一個(gè)算法應(yīng)該是 。(D)(12) 下面關(guān)于算

6、法說(shuō)法錯(cuò)誤的是 。A算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)B. 為解決某問(wèn)題的算法同為該問(wèn)題編寫(xiě)的程序含義是相同的C. 算法的可行性是指指令不能有二義性 D. 以上幾個(gè)都是錯(cuò)誤的（13）下面說(shuō)法錯(cuò)誤的是 。（1）算法原地工作的含義是指不需要任何額外的輔助空間（2）在相同的規(guī)模 n 下，復(fù)雜度 O（n）的算法在時(shí)間上總是優(yōu)于復(fù)雜度O（2n） 的算法（3）所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界（4）同一個(gè)算法，實(shí)現(xiàn)語(yǔ)言的級(jí)別越高，執(zhí)行效率就越低A（1） B （1）,（2） C（1）,（4） D（3）三、簡(jiǎn)答、計(jì)算題1. 設(shè)給定三個(gè)整數(shù) a， b，c，試寫(xiě)出尋找其中數(shù)的一個(gè)算法。并放分析在平

7、均情況與最壞情 況下，你的算法分別要作多少次比較？四、程序設(shè)計(jì)題2. 利用減半遞推技術(shù)，寫(xiě)出求長(zhǎng)度為 n 的數(shù)組中最大元素的遞歸算法。設(shè) n=2k，其中 K 1第二章 基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算【內(nèi)容】2.1 數(shù)據(jù)結(jié)構(gòu)的基本基本概念 數(shù)據(jù)結(jié)構(gòu)研究的三個(gè)方面： I&F6W K 8V（1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；（2）在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)；（3）對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。 B e Y&L 數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。 &R I/c V數(shù)據(jù)的邏輯結(jié)構(gòu)包含：（1）表示數(shù)據(jù)元素的信息；（2）

8、表示各數(shù)據(jù)元素之間的前后件關(guān)系。 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等。線性結(jié)構(gòu)條件：（1）有且只有一個(gè)根結(jié)點(diǎn)；（2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。 非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。 ;N ?O$O J x ?2.2 線性表及其順序存儲(chǔ)結(jié)構(gòu) A-A 2.2.1 線性表及其運(yùn)算 線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號(hào)，元素之間的相對(duì)位置是 線性的。 g G3V（"|.r 在復(fù)雜線性表中，由若干項(xiàng)數(shù)據(jù)元素組成的數(shù)據(jù)元素稱(chēng)為記錄，而由多個(gè)記錄構(gòu)成的線性表 又稱(chēng)為文件。非空線性表的結(jié)構(gòu)特征：（ 1）且只有一個(gè)根結(jié)點(diǎn) a1，它無(wú)前件； （2）有且只有一

9、個(gè)終端結(jié)點(diǎn) an，它無(wú)后件； （ 3）除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有 且只有一個(gè)前件，也有且只有一個(gè)后件。結(jié)點(diǎn)個(gè)數(shù) n 稱(chēng)為線性表的長(zhǎng)度，當(dāng) n=0 時(shí)，稱(chēng)為空 表。線性表的順序存儲(chǔ)結(jié)構(gòu)具有以下兩個(gè)基本特點(diǎn)：（1）線性表中所有元素的所占的存儲(chǔ)空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。 ai 的存儲(chǔ)地址為： ADR（ai）=ADR（a1） （i-1）k, ，ADR（a1） 為第一個(gè)元素的地址， k 代表每個(gè)元素 占的字節(jié)數(shù)。 0e M B p（ l順序表的運(yùn)算：插入、刪除。 （詳見(jiàn) 14-16 頁(yè)）2.2.2 棧及其運(yùn)算 "s*Sz x E1_ s

10、 棧是限定在一端進(jìn)行插入與刪除的線性表，允許插入與刪除的一端稱(chēng)為棧頂，不允許插入與 刪除的另一端稱(chēng)為棧底。棧按照 “先進(jìn)后出 ”（FILO ）或“后進(jìn)先出 ”（LIFO ）組織數(shù)據(jù)，棧具有記憶作用。用 top 表示棧頂位置，用 bottom 表示棧底。棧的基本運(yùn)算： （1）插入元素稱(chēng)為入棧運(yùn)算； （ 2）刪除元素稱(chēng)為退棧運(yùn)算； （ 3）讀棧頂元素 是將棧頂元素賦給一個(gè)指定的變量，此時(shí)指針無(wú)變化。2.2.3 隊(duì)列及其運(yùn)算 隊(duì)列是指允許在一端（隊(duì)尾）進(jìn)入插入，而在另一端（隊(duì)頭）進(jìn)行刪除的線性表。Rear 指針指向隊(duì)尾， front 指針指向隊(duì)頭。隊(duì)列是 “先進(jìn)行出 ”（ FIFO）或“后進(jìn)后出 ”

11、（LILO ）的線性表。隊(duì)列運(yùn)算包括（1）入隊(duì)運(yùn)算：從隊(duì)尾插入一個(gè)元素；（2）退隊(duì)運(yùn)算： 從隊(duì)頭刪除一個(gè)元素。5循環(huán)隊(duì)列： s=0 表示隊(duì)列空， s=1 且 front=rear 表示隊(duì)列滿 線性鏈表及其運(yùn)算 數(shù)據(jù)結(jié)構(gòu)中的每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)存儲(chǔ)單元，這種存儲(chǔ)單元稱(chēng)為存儲(chǔ)結(jié)點(diǎn)，簡(jiǎn)稱(chēng)結(jié)點(diǎn)。 結(jié)點(diǎn)由兩部分組成： （ 1）用于存儲(chǔ)數(shù)據(jù)元素值，稱(chēng)為數(shù)據(jù)域； （2）用于存放指針，稱(chēng)為指針 域，用于指向前一個(gè)或后一個(gè)結(jié)點(diǎn)。在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來(lái)確定的。鏈?zhǔn)酱鎯?chǔ)方式即可用于表示線性結(jié)構(gòu)，

12、也可用于表示非線性結(jié)構(gòu)。線性鏈表，HEAD 稱(chēng)為頭指針， HEAD=NULL (或 0)稱(chēng)為空表，如果是兩指針： 左指針(Llink ) 指向前件結(jié)點(diǎn)，右指針( Rlink )指向后件結(jié)點(diǎn)。線性鏈表的基本運(yùn)算：查找、插入、刪除。2.4 樹(shù)與二叉樹(shù)樹(shù)是一種簡(jiǎn)單的非線性結(jié)構(gòu)，所有元素之間具有明顯的層次特性。在樹(shù)結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱(chēng)為父結(jié)點(diǎn)，沒(méi)有前件的結(jié)點(diǎn)只有一個(gè)，稱(chēng)為樹(shù)的 根結(jié)點(diǎn)，簡(jiǎn)稱(chēng)樹(shù)的根。每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，稱(chēng)為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒(méi)有后件的結(jié)點(diǎn) 稱(chēng)為葉子結(jié)點(diǎn)。在樹(shù)結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱(chēng)為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱(chēng)為樹(shù)的 度。樹(shù)的最大層次稱(chēng)為樹(shù)的深度。二叉樹(shù)

13、的特點(diǎn)： (1)非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)； (2)每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)，且分別 稱(chēng)為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)。 h Lj-N 二叉樹(shù)的基本性質(zhì)： WK J.M(1) 在二叉樹(shù)的第 k 層上，最多有 2k-1(k1個(gè)) 結(jié)點(diǎn)； 2K6 v 8 (2) 深度為 m的二叉樹(shù)最多有 2m-1 個(gè)結(jié)點(diǎn)；(3) 度為 0 的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為 2 的結(jié)點(diǎn)多一個(gè)；( 4)具有 n 個(gè)結(jié)點(diǎn)的二叉樹(shù)，其深度至少為 log2n 1, 其中 log2n 表示取 log2n 的整數(shù)部分；(5) 具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 log2n 1 ；(6) 設(shè)完全二叉樹(shù)共有 n 個(gè)結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開(kāi)始，

14、按層序(每一層從左到右)用自然數(shù) 1，2，.n給結(jié)點(diǎn)進(jìn)行編號(hào)( k=1,2 .n)，有以下結(jié)論： 若 k=1 ，則該結(jié)點(diǎn)為根結(jié)點(diǎn)， 它沒(méi)有父結(jié)點(diǎn)； 若 k>1 ，則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為 INT(k/2) ； 若 2kn，則編號(hào)為 k 的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為 2k ；否則該結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn)(也無(wú)右子 結(jié)點(diǎn))； 若 2k 1 n，則編號(hào)為 k 的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為 2k 1；否則該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn)。 滿二叉樹(shù)是指除最后一層外，每一層上的所有結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，則k 層上有 2k-1 個(gè)結(jié)點(diǎn)深度為 m 的滿二叉樹(shù)有 2m-1 個(gè)結(jié)點(diǎn)。 完全二叉樹(shù)是指除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，在最

15、后一層上只缺少 右邊的若干結(jié)點(diǎn)。 二叉樹(shù)存儲(chǔ)結(jié)構(gòu)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)， 對(duì)于滿二叉樹(shù)與完全二叉樹(shù)可以按層序進(jìn)行順序存儲(chǔ)。 +_二叉樹(shù)的遍歷： .a*(1) 前序遍歷( DLR )，首先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)；(2) 中序遍歷(LDR)，首先遍歷左子樹(shù)， 然后訪問(wèn)根結(jié)點(diǎn)， 最后遍歷右子樹(shù)； R9;k g#(3) 后序遍歷( LRD )首先遍歷左子樹(shù)，然后訪問(wèn)遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。 【習(xí)題】 6一、填空題(1) 棧的基本運(yùn)算有三種：入棧、退棧和 。答：讀棧頂元素(2) 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的 結(jié)構(gòu)和數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。答：邏輯(3) 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱(chēng)為數(shù)據(jù)

16、的 。答：存儲(chǔ)結(jié)構(gòu)(4) 在先左后右的原則下， 根據(jù)訪問(wèn)根結(jié)點(diǎn)的次序， 二叉樹(shù)的遍歷可以分為三種： 前序遍歷、 遍歷和后序遍歷。答：中序(5) 設(shè)一棵完全二叉樹(shù)共有 500 個(gè)結(jié)點(diǎn)，則在該二叉樹(shù)中有 個(gè)葉子結(jié)點(diǎn)。答： 250(6) 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的 以及對(duì)數(shù)據(jù)的操作運(yùn)算。答：存儲(chǔ)結(jié)構(gòu)(7) 順序存儲(chǔ)方法是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置 的存儲(chǔ)單元中。答：相鄰(8) Jackson 結(jié)構(gòu)化程序設(shè)計(jì)方法是英國(guó)的 M.Jackson 提出的，它是一種面向 的設(shè)計(jì)方法。答：數(shù)據(jù)結(jié)構(gòu)(9) 某二叉樹(shù)中度為 2 的結(jié)點(diǎn)有 18 個(gè)，則該二叉樹(shù)中有個(gè)葉子結(jié)點(diǎn)。答：19二、選擇題(1) 以

17、下數(shù)據(jù)結(jié)構(gòu)中不屬于線性數(shù)據(jù)結(jié)構(gòu)的是 。 (C)A. 隊(duì)列 B. 線性表 C. 二叉樹(shù) D. 棧(2) 在一棵二叉樹(shù)上第 5 層的結(jié)點(diǎn)數(shù)最多是 。 (B)A. 8 B. 16C. 32 D. 15(3) 下列敘述中正確的是 。(A)A. 線性表是線性結(jié)構(gòu)B. 棧與隊(duì)列是非線性結(jié)構(gòu)C. 線性鏈表是非線性結(jié)構(gòu)D. 二叉樹(shù)是線性結(jié)構(gòu)(4) 設(shè)一棵完全二叉樹(shù)共有 699 個(gè)結(jié)點(diǎn)，則在該二叉樹(shù)中的葉子結(jié)點(diǎn)數(shù)為 。(B)A. 349 B. 350 C. 255(5) 下列關(guān)于棧的敘述中正確的是A. 在棧中只能插入數(shù)據(jù)D. 351。(D)B. 在棧中只能刪除數(shù)據(jù)D. 棧是先進(jìn)后出的線性表C. 棧是先進(jìn)先出的線

18、性表(6) 在深度為 5 的滿二叉樹(shù)中，葉子結(jié)點(diǎn)的個(gè)數(shù)為 。(C)A. 32 B. 31 C. 16 D. 15(7) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指 。(B)A. 數(shù)據(jù)所占的存儲(chǔ)空間量B.數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示C. 數(shù)據(jù)在計(jì)算機(jī)中的順序存儲(chǔ)方式 D. 存儲(chǔ)在外存中的數(shù)據(jù)(8) 設(shè)有下列二叉樹(shù)：對(duì)此二叉樹(shù)中序遍歷的結(jié)果為 。 (B)A. ABCDEF B. DBEAFC C. ABDECF D. DEBFCA(9) n 個(gè)頂點(diǎn)的強(qiáng)連通圖的邊數(shù)至少有 。 (C)A. n-1 B. n(n-1) C. n D. n+1(10) 用鏈表表示線性表的優(yōu)點(diǎn)是 。 (A)A. 便于插入和刪除操作 B. 數(shù)據(jù)元

19、素的物理順序與邏輯順序相同C. 花費(fèi)的存儲(chǔ)空間較順序存儲(chǔ)少 D. 便于隨機(jī)存取(11) 線性表的順序存儲(chǔ)結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)分別是 。 (B)A. 順序存取的存儲(chǔ)結(jié)構(gòu)、順序存取的存儲(chǔ)結(jié)構(gòu)B. 隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)、順序存取的存儲(chǔ)結(jié)構(gòu)C. 隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)、隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)D. 任意存取的存儲(chǔ)結(jié)構(gòu)、任意存取的存儲(chǔ)結(jié)構(gòu)(12) 在單鏈表中，增加頭結(jié)點(diǎn)的目的是 。(A)A. 方便運(yùn)算的實(shí)現(xiàn) B. 使單鏈表至少有一個(gè)結(jié)點(diǎn)C. 標(biāo)識(shí)表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置 D. 說(shuō)明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)(13) 棧底至棧頂依次存放元素 A、B、C、D，在第五個(gè)元素 E 入棧前，棧中元素可以出棧， 則出棧序列

20、可能是 。(D)A. ABCED B. DBCEA C. CDABE D. DCBEA(14) 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的 。(C)A. 存儲(chǔ)結(jié)構(gòu) B. 物理結(jié)構(gòu) C. 邏輯結(jié)構(gòu) D. 物理和存儲(chǔ)結(jié)構(gòu)(15) 棧和隊(duì)列的共同點(diǎn)是 。 (C)A. 都是先進(jìn)后出 B. 都是先進(jìn)先出C. 只允許在端點(diǎn)處插入和刪除元素 D. 沒(méi)有共同點(diǎn)(16) 已知二叉樹(shù)后序遍歷序列是 dabec，中序遍歷序列是 debac，它的前序遍歷序列 是 。 (A)A. cedba B. acbed C. decab D. deabc(17) 下列關(guān)于隊(duì)列的敘述中正確的是 。(C)A. 在隊(duì)列中只能插入數(shù)據(jù)

21、B. 在隊(duì)列中只能刪除數(shù)據(jù)C. 隊(duì)列是先進(jìn)先出的線性表 D. 隊(duì)列是先進(jìn)后出的線性表(18) 以下數(shù)據(jù)結(jié)構(gòu)中不屬于線性數(shù)據(jù)結(jié)構(gòu)的是 。(C)A. 隊(duì)列 B. 線性表 C. 二叉樹(shù) D. 棧(19) 在一棵二叉樹(shù)上第 8 層的結(jié)點(diǎn)數(shù)最多是 。(B)A. 256 B. 128C. 127D. 255(20) 下列敘述中正確的是 。(D)A. 棧是非線性結(jié)構(gòu)B. 隊(duì)列是非線性結(jié)構(gòu)C. 線性鏈表是非線性結(jié)構(gòu)D. 二叉樹(shù)是非線性結(jié)構(gòu)(21) 設(shè)一棵完全二叉樹(shù)共有 127 個(gè)結(jié)點(diǎn)，則在該二叉樹(shù)中的葉子結(jié)點(diǎn)數(shù)為 。(B)A.63 B. 64 C. 31 D. 32(22) 用鏈表表示線性表的優(yōu)點(diǎn)是 。(A)

22、A. 便于插入和刪除操作 B. 數(shù)據(jù)元素的物理順序與邏輯順序相同C. 花費(fèi)的存儲(chǔ)空間較順序存儲(chǔ)少 D. 便于隨機(jī)存取(23) 對(duì)長(zhǎng)度為 n 的線性表進(jìn)行順序查找， 在最壞情況下所需要的比較次數(shù)為 _。(C)A 、 log2n B、 n/2 C、 nD、n+1三、簡(jiǎn)答、計(jì)算題1. 設(shè)樹(shù) T的度為 4，其中度為 1，2，3，4的結(jié)點(diǎn)個(gè)數(shù)分別為 4，2，1，1。問(wèn) T 中 有多少個(gè)葉子結(jié)點(diǎn)？2. 設(shè)一棵完全二叉樹(shù)具有 1000 個(gè)結(jié)點(diǎn)。 問(wèn)該樹(shù)有多少個(gè)葉子結(jié)點(diǎn)？有多少個(gè)度為2的結(jié)點(diǎn)？有多少個(gè)度為 1 的結(jié)點(diǎn)？若完全二叉樹(shù)有 1001 個(gè)結(jié)點(diǎn)，再回答上述問(wèn)題， 并說(shuō)明理由。四、程序設(shè)計(jì)題1. 試編寫(xiě)一

23、個(gè)算法，將兩個(gè)有序線性表合并成一個(gè)有序線性表。2. 設(shè)有一個(gè)線性單鏈表，其結(jié)點(diǎn)值均為正整數(shù)，且按值從大到小鏈接。試寫(xiě)出一個(gè) 算法， 將該線性單鏈表分解為兩個(gè)線性單鏈表，其中一個(gè)鏈表中的結(jié)點(diǎn)值均為奇數(shù)，而另一個(gè)鏈表中的結(jié)點(diǎn)值均為偶數(shù)，且這兩個(gè)鏈表均按值從小到大鏈接。第三章 查找與排序技術(shù)【內(nèi)容】3.1 基本查找技術(shù) 順序查找的使用情況：(1) 線性表為無(wú)序表；(2) 表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。二分法查找只適用于順序存儲(chǔ)的有序表， 對(duì)于長(zhǎng)度為 n的有序線性表， 最壞情況只需比較 log2n 次。3.2 基本排序技術(shù) 排序是指將一個(gè)無(wú)序序列整理成按值非遞減順序排列的有序序列。交換類(lèi)排序法： (1)冒泡排序

24、法，需要比較的次數(shù)為 n(n-1)/2； (2)快速排序法。插入類(lèi)排序法： ( 1)簡(jiǎn)單插入排序法，最壞情況需要n(n-1)/2 次比較；( 2)希爾排序法，最壞情況需要 O(n1.5)次比較。選擇類(lèi)排序法： (1)簡(jiǎn)單選擇排序法 , 最壞情況需要 n(n-1)/2 次比較；(2)堆排序法，最壞 情況需要 O(nlog2n) 次比較。【習(xí)題】一、填空題(1) 在最壞情況下，冒泡排序的時(shí)間復(fù)雜度為 。答： n(n-1)/2#n*(n-1)/2#O(n(n-1)/2)#O(n*(n-1)/2)(2) 在最壞情況下，堆排序需要比較的次數(shù)為 。答： O(nlog2n)(3) 在長(zhǎng)度為 n 的有序線性表

25、中進(jìn)行二分查找。最壞的情況下，需要的比較次數(shù)為 。O(log2n)二、選擇題(1) 希爾排序法屬于哪一種類(lèi)型的排序法 。 (B)A. 交換類(lèi)排序法 B. 插入類(lèi)排序法 C. 選擇類(lèi)排序法 D. 建堆排序法(2) 對(duì)長(zhǎng)度為 N 的線性表進(jìn)行順序查找，在最壞情況下所需要的比較次數(shù)為 。(B)A. N+1 B. N C. (N+1)/2 D. N/2(3) 已知數(shù)據(jù)表 A中每個(gè)元素距其最終位置不遠(yuǎn)， 為節(jié)省時(shí)間， 應(yīng)采用的算法是 。(B)A. 堆排序 B. 直接插入排序 C. 快速排序 D. 直接選擇排序(4) 在下列幾種排序方法中，要求內(nèi)存量最大的是 。 (D)A. 插入排序 B. 選擇排序 C.

26、 快速排序 D. 歸并排序(5) 下列數(shù)據(jù)結(jié)構(gòu)中，能用二分法進(jìn)行查找的是 (A) A.順序存儲(chǔ)的有序線性表B. 線性鏈表 C. 二叉鏈表 D.有序線性鏈表(6) 對(duì)于長(zhǎng)度為 n 的線性表，在最壞情況下，下列各排序法所對(duì)應(yīng)的比較次數(shù)中正確的 是 (D)A. 冒泡排序?yàn)?n/2 B. 冒泡排序?yàn)?n C.快速排序?yàn)?n D.快速排序?yàn)?n(n-1)/2三、簡(jiǎn)答題 1順序查找法和二分查找法各有什么特點(diǎn)。2試述快速排序的排序過(guò)程四、程序設(shè)計(jì)題 編寫(xiě)程序，分別用冒泡排序法、選擇排序法和希爾排序法對(duì) 20 個(gè)偽隨機(jī)數(shù)進(jìn)行排序。第四章 操作系統(tǒng)【內(nèi)容】【習(xí)題】一、選擇題1. 操作系統(tǒng)負(fù)責(zé)管理計(jì)算機(jī)中的 (

27、C ) .A) 程序 B) 作業(yè) C) 資源 D) 進(jìn)程2. 同一程序運(yùn)行在不同的數(shù)據(jù)集上 ,創(chuàng)建了 ( A )的進(jìn)程 .A) 不同 B) 相同 C)同步 D) 互斥3. 進(jìn)程在三個(gè)基本狀態(tài)中轉(zhuǎn)換 ,肯定不會(huì)有的轉(zhuǎn)換是 ( B ).A) 運(yùn)行態(tài)就緒態(tài) B) 等待態(tài)運(yùn)行態(tài)C) 運(yùn)行態(tài)等待態(tài) D) 等待態(tài)就緒態(tài)4. 在任何時(shí)刻 ,一個(gè)進(jìn)程的狀態(tài)變化 ( C ) 引起另一個(gè)進(jìn)程的狀態(tài)變化 .A) 必定 B) 一定不 C) 不一定 D)不可能5. 中斷裝置按預(yù)定的順序來(lái)響應(yīng)同時(shí)出現(xiàn)的中斷事件,這個(gè)預(yù)定的順序是 ( D ).A) 調(diào)度優(yōu)先數(shù) B) 中斷優(yōu)先數(shù) C) 中斷屏蔽 D) 先來(lái)先服務(wù)6. 頁(yè)式存

28、儲(chǔ)管理的主要特點(diǎn)是 (C ) .A) 不要求作業(yè)同時(shí)全部裝入主存 B) 擴(kuò)充主存容量C) 不要求作業(yè)裝入到主存的連續(xù)區(qū)域 D) 要求處理缺頁(yè)中斷7. ( D) 是文件系統(tǒng)實(shí)現(xiàn)按名存取的重要手段.A) 堆棧結(jié)構(gòu) B) 指針 C) 頁(yè)表 D) 文件目錄8. 幾個(gè)進(jìn)程爭(zhēng)奪同一個(gè)資源 ,( C) .A) 不會(huì)死鎖 B) 一定會(huì)死鎖 C) 不一定會(huì)死鎖 D) 上述都不對(duì)9. 在時(shí)間片輪轉(zhuǎn)調(diào)度算法中 ,如果某個(gè)被選中的進(jìn)程運(yùn)行時(shí)間片到 讓出 CPU,進(jìn)入( B)狀態(tài).A) 等待 B) 就緒 C) 執(zhí)行 D) 運(yùn)行10. 下列說(shuō)法哪個(gè)不正確 (B ).A) 進(jìn)程是有生命期的 B) 進(jìn)程與程序一一對(duì)應(yīng)C) 進(jìn)

29、程是動(dòng)態(tài)的 D) 進(jìn)程執(zhí)行中有三種基本狀態(tài)11. 在進(jìn)程管理中 ,下面(B )是進(jìn)程存在的惟一標(biāo)志 .A) JCB B) PCB C) PSW D) 進(jìn)程名12. 操作系統(tǒng)的英語(yǔ)縮寫(xiě)是 ( ).A) WINDOWS B) UNIX C) DOS D) OS13. 文件系統(tǒng)實(shí)現(xiàn)按名存取主要是通過(guò) ( B) 來(lái)實(shí)現(xiàn)的 .A) 查找位示圖 B) 查找文件目錄C) 查找作業(yè)表 D) 內(nèi)存地址轉(zhuǎn)換14. UNIX 屬于(C )操作系統(tǒng) .A) 批處理系統(tǒng) B) 實(shí)時(shí)系統(tǒng) C) 分時(shí)系統(tǒng) D) 分布式系統(tǒng)15. 操作系統(tǒng)是一組 ( C)程序 .A) 文件管理 B) 中斷處理 C) 資源管理 D) 設(shè)備管理

30、16. 在分時(shí)系統(tǒng)中 ,時(shí)間片一定時(shí) ,(B ),響應(yīng)時(shí)間越長(zhǎng) .A) 內(nèi)存越大 B) 用戶數(shù)越多 C) 內(nèi)存越小 D) 用戶數(shù)越少17. 進(jìn)程與程序的本質(zhì)區(qū)別是 (C ).A) 存儲(chǔ)在內(nèi)存和外存 B) 順序和非順序執(zhí)行機(jī)器指令C) 動(dòng)態(tài)和靜態(tài)特征 D) 分時(shí)使用和獨(dú)占使用計(jì)算機(jī)資源18. 進(jìn)程被創(chuàng)建后立即進(jìn)入 ( B)排隊(duì).A) 等待隊(duì)列 B) 就緒隊(duì)列 C) 緩沖隊(duì)列 D) 運(yùn)行隊(duì)列19. 保護(hù)現(xiàn)場(chǎng)是指將現(xiàn)場(chǎng)信息保存至 (C ).A) 磁盤(pán) B) 各相應(yīng)的寄存器,而運(yùn)行并沒(méi)結(jié)束 ,它也必須C) 進(jìn)程的 PCB 中 D) 內(nèi)存系統(tǒng)區(qū)20. 文件系統(tǒng)采用二級(jí)文件目錄 ,主要是 ( C).A)

31、縮短訪問(wèn)存儲(chǔ)器的時(shí)間 B) 實(shí)現(xiàn)文件共享C) 解決不同用戶間文件命名沖突 D) 節(jié)省內(nèi)存空間21. 進(jìn)程從運(yùn)行態(tài)變?yōu)榈却龖B(tài)的原因可能是 (A ).A) I/O 事件發(fā)生 B) 時(shí)間片到C) I/O 事件完成 D) 某個(gè)進(jìn)程被喚醒22. 進(jìn)程調(diào)度主要負(fù)責(zé) ( A).A) 選一進(jìn)程占有 CPU B) 建立一進(jìn)程C) 撤消一進(jìn)程 D) 選作業(yè)進(jìn)入內(nèi)存23. 通常,文件的各種屬性放在 (D )中A) 數(shù)據(jù)字典 B)索引文件 C)文件屬性表 D)文件目錄24. 文件系統(tǒng)是指 (B )A) 文件的集合 B) 實(shí)現(xiàn)文件管理的一組軟件 C)文件的目錄 D) 管理文件的軟件及數(shù)據(jù)結(jié)構(gòu)的總體25. (D ) 是文

32、件系統(tǒng)實(shí)現(xiàn) "按名存取 "的重要手段 .A)堆棧結(jié)構(gòu) B)指針 C) 頁(yè)表 D) 文件目錄26. 文件系統(tǒng)采用多級(jí)目錄結(jié)構(gòu)后 ,對(duì)于不同用戶的文件 ,其文件名 (C ).A) 應(yīng)該相同 B)應(yīng)該不同C)可以不同 , 也可以相同 D) 受系統(tǒng)約束27. 文件系統(tǒng)中 ,索引文件中的索引表是用來(lái) (D ).A) 指示邏輯記錄的邏輯地址的B)存放部分?jǐn)?shù)據(jù)信息的C)存放查找關(guān)鍵字項(xiàng)內(nèi)容的 D) 指示邏輯記錄和物理之間對(duì)應(yīng)關(guān)系的28. 進(jìn)程之間的同步是指進(jìn)程間在邏輯上的相互(A )關(guān)系.A) 制約 B) 排斥 C) 調(diào)用 D) 轉(zhuǎn)移29. 資源的靜態(tài)分配算法在解決死鎖問(wèn)題中用于(A )

33、.A) 預(yù)防死鎖 B) 避免死鎖 C) 檢測(cè)死鎖 D) 解除死鎖30. 由于并發(fā)進(jìn)程之間 ( B)不能由進(jìn)程本身控制 ,當(dāng)它們?cè)诠蚕砟承┵Y源的時(shí)候可能會(huì)產(chǎn)生與時(shí) 間有關(guān)的錯(cuò)誤 .A) 占用存儲(chǔ)器的位置 B)執(zhí)行的相對(duì)速度C) 分配外部設(shè)備 D) 外部設(shè)備的啟動(dòng)31. 在(C )的情況下,系統(tǒng)出現(xiàn)死鎖 .A） 計(jì)算機(jī)系統(tǒng)發(fā)生重大故障B）有多個(gè)封鎖的進(jìn)程同時(shí)存在C）多進(jìn)程因競(jìng)爭(zhēng)資源而無(wú)休止地相互等待它方釋放已占有的資源D）資源數(shù)大大小于進(jìn)程數(shù)或進(jìn)程同時(shí)申請(qǐng)的資源數(shù)大大超過(guò)資源總數(shù)32. 下列選擇中 ,（D ） 不是操作系統(tǒng)關(guān)心的主要問(wèn)題 .A） 管理計(jì)算機(jī)裸機(jī) B） 設(shè)計(jì)提供用戶與計(jì)算機(jī)硬件系統(tǒng)的

34、界面 C）管理計(jì)算機(jī)系統(tǒng)資源 D） 高級(jí)程序設(shè)計(jì)語(yǔ)言的編譯器33. 實(shí)時(shí)操作系統(tǒng)必須在 （ A） 內(nèi)完成來(lái)自外部的事件 .A） 響應(yīng)時(shí)間 B）周轉(zhuǎn)時(shí)間C）規(guī)定時(shí)間 D） 調(diào)度時(shí)間34. 批處理系統(tǒng)的主要缺點(diǎn)是 （C ）. A）CPU 利用率低 B）不能并發(fā)執(zhí)行 C）缺少交互性 D） 以上都不是35. 下面對(duì)進(jìn)程的描述中 ,錯(cuò)誤的是 （C ）. A） 進(jìn)程是動(dòng)態(tài)的概念 B）進(jìn)程有生命期 C）進(jìn)程是指令的集合 D）進(jìn)程可以并發(fā)執(zhí)行36. 并發(fā)進(jìn)程之間 （D ）.A） 彼此無(wú)關(guān) B）必須同步C）必須互斥 D） 可能需要同步或互斥37. 一個(gè)作業(yè) 8:00 到達(dá)系統(tǒng) ,估計(jì)運(yùn)行時(shí)間為 1 小時(shí),若 1

35、0:00開(kāi)始執(zhí)行該作業(yè) ,其響應(yīng)比為 （ C）. A） 2 B） 2 C） 3 D） 0.538. 在作業(yè)調(diào)度中 ,（ D） 兼顧了短作業(yè)與長(zhǎng)作業(yè) .A） 先來(lái)先服務(wù) B） 短作業(yè)優(yōu)先C）均衡調(diào)度 D） 響應(yīng)比高者優(yōu)先39. 作業(yè)調(diào)度是 （A ）.A）從輸入井挑選作業(yè)進(jìn)主存B）從讀卡機(jī)挑選作業(yè)進(jìn)輸入井C）從主存中挑選作業(yè)進(jìn)程進(jìn)處理器D）從等待設(shè)備的隊(duì)列中選取一個(gè)作業(yè)進(jìn)程40. 現(xiàn)有三個(gè)作業(yè)同時(shí)到達(dá) ,每個(gè)作業(yè)的運(yùn)行時(shí)間都為 1 小時(shí) ,它們?cè)谝慌_(tái)處理器上按單道方式 運(yùn)行,則平均等待時(shí)間為 （ B）.A） 1 小時(shí) B） 2 小時(shí) C） 3 小時(shí) D） 6 小時(shí)二、填空題1、操作系統(tǒng)的形成經(jīng)歷了

36、（手工操作） 、（成批處理系統(tǒng)） 、（執(zhí)行系統(tǒng)）和（多道程序系統(tǒng)） 階段。2、通常所說(shuō)操作系統(tǒng)的五大功能是文件管理、設(shè)備管理、（處理機(jī)管理） 、（存儲(chǔ)器管理）和（作業(yè)管理）。3、多道批處理系統(tǒng)的主要優(yōu)點(diǎn)是資源利用率高、系統(tǒng)吞吐量大。4、作業(yè)調(diào)度是從（后備作業(yè)）中選一道作業(yè)，為它分配資源，并為它創(chuàng)建（相應(yīng)的進(jìn)程）。5、進(jìn)程調(diào)度的職責(zé)是按給定的調(diào)度算法從 （就緒） 隊(duì)列中選擇一個(gè)進(jìn)程， 讓它占用（處理器）6、程序順序執(zhí)行具有（順序性） 、（封閉性）和（可再現(xiàn)性） 。7、程序并發(fā)執(zhí)行時(shí)具有（間斷性） 、（失去封閉性）和（不可再現(xiàn)性） 。8、常用的解除死鎖的方法有 （撤消 ）和（掛起 ）進(jìn)程。9、按文

37、件的邏輯結(jié)構(gòu)分類(lèi)，將文件分為（無(wú)結(jié)構(gòu)文件）和（記錄式文件）。10、文件存儲(chǔ)空間管理常用的技術(shù)有（空閑文件目錄）、（位示圖）、（空閑塊鏈） 。三、簡(jiǎn)答題1. 什么是操作系統(tǒng)？它的主要功能是什么？2. 并發(fā)執(zhí)行的程序有什么特點(diǎn)？它與順序執(zhí)行的程序有什么本質(zhì)的區(qū)別？3. 什么是進(jìn)程？它與程序有什么關(guān)系？第五章 數(shù)據(jù)庫(kù)技術(shù)【內(nèi)容】51 數(shù)據(jù)庫(kù)系統(tǒng)的基本概念 數(shù)據(jù)：實(shí)際上就是描述事物的符號(hào)記錄。 數(shù)據(jù)的特點(diǎn)：有一定的結(jié)構(gòu)，有型與值之分，如整型、實(shí)型、字符型等。而數(shù)據(jù)的值給 出了符合定型的值，如整型值 15。數(shù)據(jù)庫(kù)：是數(shù)據(jù)的集合，具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲(chǔ)介質(zhì)內(nèi)，是多種應(yīng)用 數(shù)據(jù)的集成，并可被各

38、個(gè)應(yīng)用程序共享。數(shù)據(jù)庫(kù)存放數(shù)據(jù)是按數(shù)據(jù)所提供的數(shù)據(jù)模式存放的，具有集成與共享的特點(diǎn)。 數(shù)據(jù)庫(kù)管理系統(tǒng)：一種系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)庫(kù)中的數(shù)據(jù)組織、數(shù)據(jù)操縱、數(shù)據(jù)維護(hù)、控 制及保護(hù)和數(shù)據(jù)服務(wù)等，是數(shù)據(jù)庫(kù)的核心。數(shù)據(jù)庫(kù)管理系統(tǒng)功能：（1）數(shù)據(jù)模式定義：即為數(shù)據(jù)庫(kù)構(gòu)建其數(shù)據(jù)框架；（2）數(shù)據(jù)存取的物理構(gòu)建：為數(shù)據(jù)模式的物理存取與構(gòu)建提供有效的存取方法與手段；（3）數(shù)據(jù)操縱：為用戶使用數(shù)據(jù)庫(kù)的數(shù)據(jù)提供方便，如查詢(xún)、插入、修改、刪除等以及 簡(jiǎn)單的算術(shù)運(yùn)算及統(tǒng)計(jì)；（4）數(shù)據(jù)的完整性、安生性定義與檢查；（5）數(shù)據(jù)庫(kù)的并發(fā)控制與故障恢復(fù)；（6）數(shù)據(jù)的服務(wù)：如拷貝、轉(zhuǎn)存、重組、性能監(jiān)測(cè)、分析等。 為完成以上六個(gè)功能，數(shù)

39、據(jù)庫(kù)管理系統(tǒng)提供以下的數(shù)據(jù)語(yǔ)言：（1）數(shù)據(jù)定義語(yǔ)言：負(fù)責(zé)數(shù)據(jù)的模式定義與數(shù)據(jù)的物理存取構(gòu)建；（2）數(shù)據(jù)操縱語(yǔ)言：負(fù)責(zé)數(shù)據(jù)的操縱，如查詢(xún)與增、刪、改等；（ 3）數(shù)據(jù)控制語(yǔ)言： 負(fù)責(zé)數(shù)據(jù)完整性、 安全性的定義與檢查以及并發(fā)控制、 故障恢復(fù)等。 數(shù)據(jù)語(yǔ)言按其使用方式具有兩種結(jié)構(gòu)形式： 交互式命令 （又稱(chēng)自含型或自主型語(yǔ)言 ）宿主型 語(yǔ)言（一般可嵌入某些宿主語(yǔ)言中） 。數(shù)據(jù)庫(kù)管理員：對(duì)數(shù)據(jù)庫(kù)進(jìn)行規(guī)劃、設(shè)計(jì)、維護(hù)、監(jiān)視等的專(zhuān)業(yè)管理人員。 數(shù)據(jù)庫(kù)系統(tǒng)：由數(shù)據(jù)庫(kù)（數(shù)據(jù)） 、數(shù)據(jù)庫(kù)管理系統(tǒng)（軟件） 、數(shù)據(jù)庫(kù)管理員（人員） 、硬件 平臺(tái)（硬件）、軟件平臺(tái)（軟件）五個(gè)部分構(gòu)成的運(yùn)行實(shí)體。數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)：由數(shù)據(jù)庫(kù)系

40、統(tǒng)、應(yīng)用軟件及應(yīng)用界面三者組成。 文件系統(tǒng)階段：提供了簡(jiǎn)單的數(shù)據(jù)共享與數(shù)據(jù)管理能力，但是它無(wú)法提供完整的、統(tǒng)一 的、管理和數(shù)據(jù)共享的能力。層次數(shù)據(jù)庫(kù)與網(wǎng)狀數(shù)據(jù)庫(kù)系統(tǒng)階段 ：為統(tǒng)一與共享數(shù)據(jù)提供了有力支撐。 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)階段數(shù)據(jù)庫(kù)系統(tǒng)的基本特點(diǎn)： 數(shù)據(jù)的集成性 、數(shù)據(jù)的高共享性與低冗余性 、數(shù)據(jù)獨(dú)立性 （物 理獨(dú)立性與邏輯獨(dú)立性） 、數(shù)據(jù)統(tǒng)一管理與控制。數(shù)據(jù)庫(kù)系統(tǒng)的三級(jí)模式：（1）概念模式：數(shù)據(jù)庫(kù)系統(tǒng)中全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述，全體用戶公共數(shù)據(jù)視圖；（2）外模式：也稱(chēng)子模式與用戶模式。是用戶的數(shù)據(jù)視圖，也就是用戶所見(jiàn)到的數(shù)據(jù)模 式；（3）內(nèi)模式：又稱(chēng)物理模式，它給出了數(shù)據(jù)庫(kù)物理存儲(chǔ)結(jié)構(gòu)與物理存取

41、方法。 數(shù)據(jù)庫(kù)系統(tǒng)的兩級(jí)映射：（1）概念模式到內(nèi)模式的映射；（2）外模式到概念模式的映射。5.2 數(shù)據(jù)模型數(shù)據(jù)模型的概念：是數(shù)據(jù)特征的抽象，從抽象層次上描述了系統(tǒng)的靜態(tài)特征、動(dòng)態(tài)行為 和約束條件，為數(shù)據(jù)庫(kù)系統(tǒng)的信息表與操作提供一個(gè)抽象的框架。描述了數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操 作及數(shù)據(jù)約束。E-R 模型的基本概念（1）實(shí)體：現(xiàn)實(shí)世界中的事物；（2）屬性：事物的特性；（ 3）聯(lián)系：現(xiàn)實(shí)世界中事物間的關(guān)系。 實(shí)體集的關(guān)系有一對(duì)一、 一對(duì)多、 多對(duì)多的聯(lián)系 E-R 模型三個(gè)基本概念之間的聯(lián)接關(guān)系：實(shí)體是概念世界中的基本單位，屬性有屬性域， 每個(gè)實(shí)體可取屬性域內(nèi)的值。一個(gè)實(shí)體的所有屬性值叫元組。E-R 模型的圖示

42、法： （ 1）實(shí)體集表示法； （ 2）屬性表法； （3）聯(lián)系表示法。 層次模型的基本結(jié)構(gòu)是樹(shù)形結(jié)構(gòu)，具有以下特點(diǎn)：（1）每棵樹(shù)有且僅有一個(gè)無(wú)雙親結(jié)點(diǎn)，稱(chēng)為根；（2）樹(shù)中除根外所有結(jié)點(diǎn)有且僅有一個(gè)雙親。 從圖論上看，網(wǎng)狀模型是一個(gè)不加任何條件限制的無(wú)向圖。 關(guān)系模型采用二維表來(lái)表示，簡(jiǎn)稱(chēng)表，由表框架及表的元組組成。一個(gè)二維表就是一個(gè) 關(guān)系。在二維表中凡能唯一標(biāo)識(shí)元組的最小屬性稱(chēng)為鍵或碼。從所有侯選健中選取一個(gè)作為用戶使用的鍵稱(chēng)主鍵。表 A 中的某屬性是某表 B 的鍵，則稱(chēng)該屬性集為 A 的外鍵或外碼。關(guān)系中的數(shù)據(jù)約束：（1）實(shí)體完整性約束：約束關(guān)系的主鍵中屬性值不能為空值；（2）參照完全性約束：

43、是關(guān)系之間的基本約束；（3）用戶定義的完整性約束：它反映了具體應(yīng)用中數(shù)據(jù)的語(yǔ)義要求。4.3 關(guān)系代數(shù)關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的特點(diǎn)之一是它建立在數(shù)據(jù)理論的基礎(chǔ)之上，有很多數(shù)據(jù)理論可以表示 關(guān)系模型的數(shù)據(jù)操作，其中最為著名的是關(guān)系代數(shù)與關(guān)系演算。關(guān)系模型的基本運(yùn)算：（1）插入 （2）刪除 （3） 修改 （4）查詢(xún)（包括投影、選擇、笛卡爾積運(yùn)算）5.4 數(shù)據(jù)庫(kù)設(shè)計(jì) 數(shù)據(jù)庫(kù)設(shè)計(jì)是數(shù)據(jù)應(yīng)用的核心。 數(shù)據(jù)庫(kù)設(shè)計(jì)的兩種方法：(1) 面向數(shù)據(jù)：以信息需求為主，兼顧處理需求；(2) 面向過(guò)程：以處理需求為主，兼顧信息需求。 數(shù)據(jù)庫(kù)的生命周期：需求分析階段、概念設(shè)計(jì)階段、邏輯設(shè)計(jì)階段、物理設(shè)計(jì)階段、編 碼階段、測(cè)試階段、

44、運(yùn)行階段、進(jìn)一步修改階段。需求分析常用結(jié)構(gòu)析方法和面向?qū)ο蟮姆椒ā＝Y(jié)構(gòu)化分析(簡(jiǎn)稱(chēng)SA )方法用自頂向下、逐層分解的方式分析系統(tǒng)。用數(shù)據(jù)流圖表達(dá)數(shù)據(jù)和處理過(guò)程的關(guān)系。對(duì)數(shù)據(jù)庫(kù)設(shè)計(jì)來(lái)講，數(shù) 據(jù)字典是進(jìn)行詳細(xì)的數(shù)據(jù)收集和數(shù)據(jù)分析所獲得的主要結(jié)果。 數(shù)據(jù)字典是各類(lèi)數(shù)據(jù)描述的集合，包括 5 個(gè)部分：數(shù)據(jù)項(xiàng)、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)流(可以是數(shù)據(jù) 項(xiàng)，也可以是數(shù)據(jù)結(jié)構(gòu)) 、數(shù)據(jù)存儲(chǔ)、處理過(guò)程。數(shù)據(jù)庫(kù)概念設(shè)計(jì)的目的是分析數(shù)據(jù)內(nèi)在語(yǔ)義關(guān)系。設(shè)計(jì)的方法有兩種(1) 集中式模式設(shè)計(jì)法(適用于小型或并不復(fù)雜的單位或部門(mén))；(2) 視圖集成設(shè)計(jì)法。設(shè)計(jì)方法： E-R 模型與視圖集成。 視圖設(shè)計(jì)一般有三種設(shè)計(jì)次序：自頂向下、由

45、底向上、由內(nèi)向外。 視圖集成的幾種沖突：命名沖突、概念沖突、域沖突、約束沖突。 關(guān)系視圖設(shè)計(jì)：關(guān)系視圖的設(shè)計(jì)又稱(chēng)外模式設(shè)計(jì)。關(guān)系視圖的主要作用：(1) 提供數(shù)據(jù)邏輯獨(dú)立性；(2) 能適應(yīng)用戶對(duì)數(shù)據(jù)的不同需求；(3) 有一定數(shù)據(jù)保密功能。 數(shù)據(jù)庫(kù)的物理設(shè)計(jì)主要目標(biāo)是對(duì)數(shù)據(jù)內(nèi)部物理結(jié)構(gòu)作調(diào)整并選擇合理的存取路徑，以提 高數(shù)據(jù)庫(kù)訪問(wèn)速度有效利用存儲(chǔ)空間。一般 RDBMS 中留給用戶參與物理設(shè)計(jì)的內(nèi)容大致有 索引設(shè)計(jì)、集成簇設(shè)計(jì)和分區(qū)設(shè)計(jì)。數(shù)據(jù)庫(kù)管理的內(nèi)容：(1) 數(shù)據(jù)庫(kù)的建立；(2) 數(shù)據(jù)庫(kù)的調(diào)整；(3) 數(shù)據(jù)庫(kù)的重組；(4) 數(shù)據(jù)庫(kù)安全性與完整性控制；(5) 數(shù)據(jù)庫(kù)的故障恢復(fù)；(6) 數(shù)據(jù)庫(kù)監(jiān)控。

46、【習(xí)題】一、填空題(1) 數(shù)據(jù)庫(kù)管理系統(tǒng)常見(jiàn)的數(shù)據(jù)模型有層次模型、網(wǎng)狀模型和 三種。答：關(guān)系模型(2) 一個(gè)項(xiàng)目具有一個(gè)項(xiàng)目主管，一個(gè)項(xiàng)目主管可管理多個(gè)項(xiàng)目，則實(shí)體 "項(xiàng)目主管 " 與實(shí)體 "項(xiàng)目"的聯(lián)系屬于 的聯(lián)系。答： 1 對(duì)多#1： N(3) 數(shù)據(jù)庫(kù)保護(hù)分為：安全性控制 、并發(fā)性控制和數(shù)據(jù)的恢復(fù)。答：完整性控制(4) 數(shù)據(jù)庫(kù)設(shè)計(jì)分為以下 6 個(gè)設(shè)計(jì)階段：需求分析階段、 、邏輯設(shè)計(jì)階段、物理設(shè)計(jì)階段、實(shí)施階段、運(yùn)行和維護(hù)階段。答：概念設(shè)計(jì)階段#數(shù)據(jù)庫(kù)概念設(shè)計(jì)階段(5) 關(guān)系模型的數(shù)據(jù)操縱即是建立在關(guān)系上的數(shù)據(jù)操縱， 一般有 、增加、刪除和修改四種操作

47、。答：查詢(xún)(6) 數(shù)據(jù)庫(kù)系統(tǒng)中實(shí)現(xiàn)各種數(shù)據(jù)管理功能的核心軟件稱(chēng)為 。答：數(shù)據(jù)庫(kù)管理系統(tǒng) #DBMS(7) 數(shù)據(jù)模型按不同的應(yīng)用層次分為三種類(lèi)型， 它們是 數(shù)據(jù)模型、 邏輯數(shù)據(jù)模型和物理數(shù)據(jù)模型。答：概念(8) 關(guān)系模型的完整性規(guī)則是對(duì)關(guān)系的某種約束條件， 包括實(shí)體完整性、 和自定義完整性。答：參照完整性(7) 是數(shù)據(jù)庫(kù)應(yīng)用的核心。答：數(shù)據(jù)庫(kù)設(shè)計(jì)(8) 數(shù)據(jù)字典是各類(lèi)數(shù)據(jù)描述的集合，它通常包括 5 個(gè)部分，即數(shù)據(jù)項(xiàng)、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)流、 和處理過(guò)程。答：數(shù)據(jù)存儲(chǔ)(9) 數(shù)據(jù)庫(kù)系統(tǒng)的三級(jí)模式分別為 模式、內(nèi)部級(jí)模式與外部級(jí)模式。答：概念#概念級(jí)(10) 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱(chēng)為

48、數(shù)據(jù)的 。答：模式 #邏輯模式#概念模式(11) 如果一個(gè)工人可管理多個(gè)設(shè)施，而一個(gè)設(shè)施只被一個(gè)工人管理，則實(shí)體"工人"與實(shí)體 "設(shè)備"之間存在 聯(lián)系。答：一對(duì)多 #1： N#1:n(12) 關(guān)系數(shù)據(jù)庫(kù)管理系統(tǒng)能實(shí)現(xiàn)的專(zhuān)門(mén)關(guān)系運(yùn)算包括選擇、連接和 。答：投影二、選擇題(1) 數(shù)據(jù)庫(kù)系統(tǒng)的核心是 。(B)A. 數(shù)據(jù)模型B. 數(shù)據(jù)庫(kù)管理系統(tǒng)C. 軟件工具D. 數(shù)據(jù)庫(kù)(2) 下列敘述中正確的是 。(C)A. 數(shù)據(jù)庫(kù)是一個(gè)獨(dú)立的系統(tǒng)，不需要操作系統(tǒng)的支持B. 數(shù)據(jù)庫(kù)設(shè)計(jì)是指設(shè)計(jì)數(shù)據(jù)庫(kù)管理系統(tǒng)C. 數(shù)據(jù)庫(kù)技術(shù)的根本目標(biāo)是要解決數(shù)據(jù)共享的問(wèn)題D. 數(shù)據(jù)庫(kù)系統(tǒng)中，數(shù)據(jù)

49、的物理結(jié)構(gòu)必須與邏輯結(jié)構(gòu)一致(3) 下列模式中，能夠給出數(shù)據(jù)庫(kù)物理存儲(chǔ)結(jié)構(gòu)與物理存取方法的是 。 (A)A. 內(nèi)模式 B. 外模式 C. 概念模式 D. 邏輯模式(4) 下述關(guān)于數(shù)據(jù)庫(kù)系統(tǒng)的敘述中正確的是 。 (A)A. 數(shù)據(jù)庫(kù)系統(tǒng)減少了數(shù)據(jù)冗余 B. 數(shù)據(jù)庫(kù)系統(tǒng)避免了一切冗余C. 數(shù)據(jù)庫(kù)系統(tǒng)中數(shù)據(jù)的一致性是指數(shù)據(jù)類(lèi)型的一致D. 數(shù)據(jù)庫(kù)系統(tǒng)比文件系統(tǒng)能管理更多的數(shù)據(jù)(4) 關(guān)系表中的每一橫行稱(chēng)為一個(gè) 。 (A)A. 元組 B. 字段C. 屬性D. 碼(5) 數(shù)據(jù)庫(kù)設(shè)計(jì)包括兩個(gè)方面的設(shè)計(jì)內(nèi)容，它們是 。(A)A. 概念設(shè)計(jì)和邏輯設(shè)計(jì)B. 模式設(shè)計(jì)和內(nèi)模式設(shè)計(jì)C. 內(nèi)模式設(shè)計(jì)和物理設(shè)計(jì)D. 結(jié)構(gòu)特

50、性設(shè)計(jì)和行為特性設(shè)計(jì)(6) 在數(shù)據(jù)管理技術(shù)的發(fā)展過(guò)程中，經(jīng)歷了人工管理階段、文件系統(tǒng)階段和數(shù)據(jù)庫(kù)系統(tǒng)階段。 其中數(shù)據(jù)獨(dú)立性最高的階段是 。 (A)A. 數(shù)據(jù)庫(kù)系統(tǒng)B. 文件系統(tǒng)C. 人工管理 D. 數(shù)據(jù)項(xiàng)管理(7) 用樹(shù)形結(jié)構(gòu)來(lái)表示實(shí)體之間聯(lián)系的模型稱(chēng)為 。(B)A. 關(guān)系模型B. 層次模型C. 網(wǎng)狀模型 D. 數(shù)據(jù)模型(8) 關(guān)系數(shù)據(jù)庫(kù)管理系統(tǒng)能實(shí)現(xiàn)的專(zhuān)門(mén)關(guān)系運(yùn)算包括 。(B)A. 排序、索引、統(tǒng)計(jì)B. 選擇、投影、連接C. 關(guān)聯(lián)、更新、排序D. 顯示、打印、制表(9) 索引屬于 。 (B)A. 模式 B. 內(nèi)模式 C. 外模式 D. 概念模式(10) 在關(guān)系數(shù)據(jù)庫(kù)中，用來(lái)表示實(shí)體之間聯(lián)系的

51、是 。(D)A. 樹(shù)結(jié)構(gòu) B. 網(wǎng)結(jié)構(gòu) C. 線性表 D. 二維表(11) 將 E-R 圖轉(zhuǎn)換到關(guān)系模式時(shí)，實(shí)體與聯(lián)系都可以表示成 。 (B)A. 屬性 B. 關(guān)系 C. 鍵 D. 域(12) 在數(shù)據(jù)管理技術(shù)發(fā)展過(guò)程中，文件系統(tǒng)與數(shù)據(jù)庫(kù)系統(tǒng)的主要區(qū)別是數(shù)據(jù)庫(kù)系統(tǒng)具有 。(D)A. 數(shù)據(jù)無(wú)冗余 B. 數(shù)據(jù)可共享 C. 專(zhuān)門(mén)的數(shù)據(jù)管理軟件 D. 特定的數(shù)據(jù)模型(13) 分布式數(shù)據(jù)庫(kù)系統(tǒng)不具有的特點(diǎn)是 。(B)A. 分布式 B. 數(shù)據(jù)冗余 C. 數(shù)據(jù)分布性和邏輯整體性 D. 位置透明性和復(fù)制透明性(14) 下列說(shuō)法中，不屬于數(shù)據(jù)模型所描述的內(nèi)容的是 。(C)A. 數(shù)據(jù)結(jié)構(gòu) B. 數(shù)據(jù)操作 C. 數(shù)據(jù)

52、查詢(xún) D. 數(shù)據(jù)約束(15) 按條件 f 對(duì)關(guān)系 R進(jìn)行選擇，其關(guān)系代數(shù)表達(dá)式為 。 (C)A. R|X|R B. R|X|R f C. f(R) D.f(R)(16) 數(shù)據(jù)庫(kù)概念設(shè)計(jì)的過(guò)程中，視圖設(shè)計(jì)一般有三種設(shè)計(jì)次序，以下各項(xiàng)中不對(duì)的是 。(D)A. 自頂向下 B. 由底向上 C. 由內(nèi)向外 D. 由整體到局部(17) SQL語(yǔ)言又稱(chēng)為 。(C)A. 結(jié)構(gòu)化定義語(yǔ)言 B. 結(jié)構(gòu)化控制語(yǔ)言 C. 結(jié)構(gòu)化查詢(xún)語(yǔ)言 D. 結(jié)構(gòu)化操縱語(yǔ)言(18) 視圖設(shè)計(jì)一般有 3 種設(shè)計(jì)次序，下列不屬于視圖設(shè)計(jì)的是 。(B)A. 自頂向下 B. 由外向內(nèi) C. 由內(nèi)向外 D. 自底向上(19) 數(shù)據(jù)處理的最小單

53、位是 。 (C)A. 數(shù)據(jù) B. 數(shù)據(jù)元素 C. 數(shù)據(jù)項(xiàng) D. 數(shù)據(jù)結(jié)構(gòu)(20) 下列有關(guān)數(shù)據(jù)庫(kù)的描述，正確的是 。(C)A. 數(shù)據(jù)庫(kù)是一個(gè) DBF文件 B. 數(shù)據(jù)庫(kù)是一個(gè)關(guān)系C. 數(shù)據(jù)庫(kù)是一個(gè)結(jié)構(gòu)化的數(shù)據(jù)集合 D. 數(shù)據(jù)庫(kù)是一組文件(21) 單個(gè)用戶使用的數(shù)據(jù)視圖的描述稱(chēng)為 。 (A)A. 外模式 B. 概念模式 C. 內(nèi)模式 D. 存儲(chǔ)模式三、簡(jiǎn)答題1. 數(shù)據(jù)庫(kù)管理技術(shù)的發(fā)展經(jīng)歷了哪幾個(gè)階段？2. 數(shù)據(jù)的邏輯獨(dú)立性的含義是什么？數(shù)據(jù)的物理獨(dú)立性的含義是什么？3. 什么是 ER 圖？利用 ER圖進(jìn)行數(shù)據(jù)庫(kù)概念結(jié)構(gòu)設(shè)計(jì)分為哪幾步？第六章 軟件工程基礎(chǔ)【內(nèi)容】 |61 軟件工程基本概念 計(jì)算機(jī)軟

54、件是包括程序、數(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)具有依賴(lài)性，受計(jì)算機(jī)系統(tǒng)的限制，這導(dǎo)致了軟件 移植的問(wèn)題；（5）軟件復(fù)雜性高，成本昂貴；（6）軟件開(kāi)發(fā)涉及諸多的社會(huì)因素。 軟件按功能分為應(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ò)程是把軟

55、件轉(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)。 軟件周期：軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過(guò)程。軟件生命周期三個(gè)階段 : 軟件定義、軟件開(kāi)發(fā)、運(yùn)行維護(hù)，主要活動(dòng)階段是： （1）可行性研究與計(jì)劃制定；（2）需求分析；（3）軟件設(shè)計(jì)；（4）軟件實(shí)現(xiàn)；（5）軟件測(cè)試；（6）運(yùn)行和維護(hù)。軟件工程的目標(biāo)和與原則： 目標(biāo)：在給定成本、進(jìn)度的前提下，開(kāi)發(fā)出具有有效性、可靠性、可理解性、可維護(hù)性、 可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。基本目標(biāo)：付出較低的開(kāi)發(fā)成本；達(dá)

56、到要求的軟件功能；取得較好的軟件性能；開(kāi)發(fā)軟 件易于移植；需要較低的費(fèi)用；能按時(shí)完成開(kāi)發(fā)，及時(shí)交付使用。 基本原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗(yàn)證性。軟件工程的理論和技術(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) 證性。62 結(jié)構(gòu)化治齜椒 ?BR> 結(jié)構(gòu)化方法的核心和基礎(chǔ)是結(jié)構(gòu)化程序設(shè)計(jì)理論。 需求分析方法有（ 1）結(jié)構(gòu)化需求分析方法； （