計算機2級公共基礎(chǔ)知識課件

計算機等級考試

公共基礎(chǔ)知識

計算機等級考試

公共基礎(chǔ)知識第2頁計算機二級考試公共基礎(chǔ)知識大綱

數(shù)據(jù)結(jié)構(gòu)與算法程序設(shè)計基礎(chǔ)軟件工程基礎(chǔ)數(shù)據(jù)庫設(shè)計基礎(chǔ)第2頁計算機二級考試公共基礎(chǔ)知識大綱數(shù)據(jù)結(jié)構(gòu)與算法第3頁算法⒈算法的基本概念

2.算法復(fù)雜度的概念和意義

一、基本數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)⒈數(shù)據(jù)結(jié)構(gòu)的概念⒉線性表⒊棧和隊列⒋樹與二叉樹⒌查找技術(shù)⒍排序技術(shù)

對于等級考試，這個部分的考核重點主要在算法和數(shù)據(jù)結(jié)構(gòu)的基本概念、二叉樹(遍歷、結(jié)點），還有排序和查找考試中也經(jīng)常會涉及到。第3頁算法一、基本數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)對于等級考試，這個第4頁算法的定義對解題方案準(zhǔn)確而完整的描述稱為算法。算法是程序設(shè)計的核心⒈算法的基本概念

算法是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。通俗點說，就是計算機解題的過程(計算的方法)。在這個過程中，無論是形成解題思路(推理實現(xiàn)的算法)還是編寫程序(操作實現(xiàn)的算法)，都是在實施某種算法。例：n個數(shù)從大到小進行排序。

有多種排序方法，常用的有冒泡排序、選擇排序等。第4頁算法的定義算法是程序設(shè)計的核心⒈算法的基本概念第5頁

2.

算法的基本特征一個算法應(yīng)該具有以下五個重要的特征：有窮性確定性輸入輸出可行性一個算法必須保證執(zhí)行有限步之后結(jié)束；算法的每一步驟必須有確切的定義；一個算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指算法本身定除了初始條件；一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的；算法原則上能夠精確地運行，而且人們用筆和紙做有限次運算后即可完成第5頁2.算法的基本特征有窮性一個算法必須保證執(zhí)第6頁算法與計算機程序算法____是一組邏輯步驟程序——用計算機語言描述的算法3.算法的表示INPUTrS=3.14*r*rPTINTS開始輸入RS=3.14*

R*R輸出S結(jié)束問題：輸入園的半徑，計算園的面積

一個算法的表示需要使用一些語言形式。傳統(tǒng)的算法-------圖形法，如“流程圖”和N-S圖目前常用的方法-------使用偽碼描述算法。第6頁算法與計算機程序3.算法的表示INPUTr第7頁冒泡排序的方法：1.掃描整個線性表，逐次對相鄰的兩個元素進行比較，若為逆序，則交換；第一趟掃描的結(jié)果使最大的元素排到表的最后；2.除最后一個元素，對剩余的元素重復(fù)上述過程，將次大的數(shù)排到表的倒數(shù)第二個位置；3.重復(fù)上述過程；對于長度為n的線性表，冒泡排序需要對表掃描n-1遍。

算法舉例：n個數(shù)排序第7頁冒泡排序的方法：算法舉例：n個數(shù)排序第8頁4.算法的兩個基本要素：基本運算和操作算術(shù)運算關(guān)系運算邏輯運算數(shù)據(jù)傳輸控制結(jié)構(gòu)

順序選擇循環(huán)一是對數(shù)據(jù)對象的運算和操作；二是算法的控制結(jié)構(gòu)。算法基本設(shè)計方法：列舉法、歸納法、遞推、遞歸、減斗遞推技術(shù)、回溯法

第8頁4.算法的兩個基本要素：基本運算和操作控制結(jié)構(gòu)第9頁5.

算法評價評價一個算法優(yōu)劣的主要標(biāo)準(zhǔn)是算法的執(zhí)行效率和存儲需求：時間復(fù)雜度：執(zhí)行這個算法所需要的計算工作量一般可以用算法在執(zhí)行過程中所需基本運算的執(zhí)行次數(shù)來度量計算工作量空間復(fù)雜度：執(zhí)行這個算法所需要的內(nèi)存空間

算法在執(zhí)行過程中臨時占用的存儲空間

時間復(fù)雜度它大致等于計算機執(zhí)行一種簡單操作所需的平均時間與算法中進行簡單操作的次數(shù)的乘積。

一個算法在計算機存儲器上所占用的存儲空間，包括存儲算法本身所占用的存儲空間、算法中的輸入輸出數(shù)據(jù)所占用的存儲空間和算法在運行過程中臨時占用的存儲空間這三個部分第9頁5.算法評價第10頁一、算法對解題方案準(zhǔn)確而完整的描述稱為算法。算法不等于程序，也不等計算機方法，程序的編制不可能優(yōu)于算法的設(shè)計。算法評價：

時間復(fù)雜度：執(zhí)行這個算法所需要的計算工作量空間復(fù)雜度：執(zhí)行這個算法所需要的內(nèi)存空間第10頁一、算法對解題方案準(zhǔn)確而完整的描述稱為算法。第11頁(1)在計算機中，算法是指______。

A.查詢方法B.加工方法

C.解題方案的準(zhǔn)確而完整的描述D.排序方法(2)下列敘述中正確的是A)算法的效率只與問題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)B)算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量C)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是一一對應(yīng)的D)算法的時間復(fù)雜度與空間復(fù)雜度一定相關(guān)(3)算法的有窮性是指A）算法程序的運行時間是有限的B）算法程序所處理的數(shù)據(jù)量是有限的C）算法程序的長度是有限的D）算法只能被有限的用戶使用(c)(B)算法習(xí)題:(A)第11頁(1)在計算機中，算法是指______。

A.第12頁(4)算法的時問復(fù)雜度是指(2010年3月)A)算法的執(zhí)行時間B)算法所處理的數(shù)據(jù)量C)算法程序中的語句或指令條數(shù)D)算法在執(zhí)行過程中所需要的基本運算次數(shù)(5)算法的空間復(fù)雜度是指(09年9月)A）算法在執(zhí)行過程中所需要的計算機存儲空間B）算法所處理的數(shù)據(jù)量C）算法程序中的語句或指令條數(shù)D）算法在執(zhí)行過程中所需要的臨時工作單元數(shù)(6)下列敘述中正確的是(06年9月)A）一個算法的空間復(fù)雜度大，則其時間復(fù)雜度也必定大B）一個算法的空間復(fù)雜度大，則其時間復(fù)雜度必定小C）一個算法的時間復(fù)雜度大，則其空間復(fù)雜度必定小D）上述三種說法都不對(D)計算工作量(A)(D)第12頁(4)算法的時問復(fù)雜度是指(2010年3月)(第13頁

計算機在進行數(shù)據(jù)處理時，實際需要處理的數(shù)據(jù)元素一般有很多，而這些大量的數(shù)據(jù)元素都需要存放在計算機中，因此，大量的數(shù)據(jù)元素在計算機中如何組織，以便提高數(shù)據(jù)處理的效率，并且節(jié)省計算機的存儲空間，這是進行數(shù)據(jù)處理的關(guān)鍵問題。二、數(shù)據(jù)結(jié)構(gòu)程序=算法+數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。

一般來說，人們不會同時處理特征完全不同且互相之間沒有任何關(guān)系的各類數(shù)據(jù)元素，對于具有不同特征的數(shù)據(jù)元素總是分別進行處理。一般情況下，在具有相同特征的數(shù)據(jù)元素集合中，各個數(shù)據(jù)元素之間存在有某種關(guān)系（即聯(lián)系），這種關(guān)系反映了該集合中的數(shù)據(jù)元素所固有的一種結(jié)構(gòu)。第13頁計算機在進行數(shù)據(jù)處理時，實際需要處理的數(shù)據(jù)元素一般第14頁二.數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)和數(shù)據(jù)之間關(guān)系的一門學(xué)科，它包括三個方面。

（1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；（2）在對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)；（3）對各種數(shù)據(jù)結(jié)構(gòu)進行的運算。第14頁二.數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合第15頁1.邏輯結(jié)構(gòu)

數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)包含：（1）表示數(shù)據(jù)元素的信息；（2）表示各數(shù)據(jù)元素之間的前后件關(guān)系。例：1.一年四季的數(shù)據(jù)結(jié)構(gòu)B=(D,R)D={春，夏，秋，冬}R={(春，夏),(夏，秋),(秋，冬)}2.家庭成員的數(shù)據(jù)結(jié)構(gòu)B=(D,R)D={父親，兒子，女兒}R={(父親，兒子),(父親，女兒)}春夏秋冬數(shù)據(jù)結(jié)構(gòu)的圖形表示父親兒子女兒第15頁1.邏輯結(jié)構(gòu)春夏秋冬數(shù)據(jù)結(jié)構(gòu)的圖形表示父親第16頁常見的邏輯結(jié)構(gòu)有：線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)。線性結(jié)構(gòu)樹形結(jié)構(gòu)圖形結(jié)構(gòu)①線性結(jié)構(gòu)結(jié)構(gòu)中的每個元素之間存在一個對一個的關(guān)系；②樹形結(jié)構(gòu)結(jié)構(gòu)中的每個元素之間存在一個對多個的關(guān)系；③圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)結(jié)構(gòu)中的每個元素之間存在多個對多個的關(guān)系。其中，樹形結(jié)構(gòu)和圖形結(jié)構(gòu)統(tǒng)稱為非線形結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)可以用二元關(guān)系表示，也可以直觀地用圖形來表示。第16頁常見的邏輯結(jié)構(gòu)有：線性結(jié)構(gòu)樹形結(jié)構(gòu)圖形結(jié)構(gòu)①線性第17頁2.存儲結(jié)構(gòu)（物理結(jié)構(gòu)）計算機在實際進行數(shù)據(jù)處理時，被處理的各數(shù)據(jù)元素總是被存放在計算機的存儲空間中，并且，各數(shù)據(jù)元素在計算機存儲空間中的位置與它們的邏輯關(guān)系不一定是相同的，而且一般也不可能相同。如：一年四季

家庭成員計算機存儲空間怎樣存放？

存儲結(jié)構(gòu)指數(shù)據(jù)結(jié)構(gòu)在計算機存儲空間中的具體實現(xiàn)。常見的存儲結(jié)構(gòu)有：順序存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)索引存儲結(jié)構(gòu)只抽象地反映數(shù)據(jù)元素之間的關(guān)系的結(jié)構(gòu)，而不管其存儲方式的數(shù)據(jù)結(jié)構(gòu)稱為邏輯結(jié)構(gòu)。一種數(shù)據(jù)結(jié)構(gòu)可以根據(jù)需要表示成一種或多種存儲結(jié)構(gòu)。第17頁2.存儲結(jié)構(gòu)（物理結(jié)構(gòu)）只抽象地反映數(shù)據(jù)元素之間第18頁3.數(shù)據(jù)的運算檢索插入刪除更新排序

通常，一個數(shù)據(jù)結(jié)構(gòu)中的元素結(jié)點可能是動態(tài)變化的。根據(jù)需要或在處理過程中，可以在一個數(shù)據(jù)結(jié)構(gòu)中增加一個新結(jié)點（插入運算），也可以刪除某個結(jié)點（刪除運算），除此之外，對數(shù)據(jù)結(jié)構(gòu)的運算還有查找、分類、合并、分解、復(fù)制和修改。在對數(shù)據(jù)結(jié)構(gòu)的處理過程中，不僅數(shù)據(jù)結(jié)構(gòu)中結(jié)點的個數(shù)在動態(tài)變化，而且，各數(shù)據(jù)元素之間的關(guān)系也有可能在動態(tài)地變化。如：無序表變有序表數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)和數(shù)據(jù)之間關(guān)系的一門學(xué)科，研究以下三方面內(nèi)容：

數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的運算第18頁3.數(shù)據(jù)的運算通常，一個數(shù)據(jù)結(jié)構(gòu)中的元素第19頁常見的數(shù)據(jù)結(jié)構(gòu)

1.線性表2.棧和隊列3.樹第19頁常見的數(shù)據(jù)結(jié)構(gòu)第20頁１．線性表（LinearList）線性表是由n（n≥0）個數(shù)據(jù)元素a1，a2，…，ai，…，an組成的一個有限序列。簡單的線性表春夏秋冬復(fù)雜的線性表記錄102011001張三男…記錄202011003李四女…記錄3記錄4第20頁１．線性表（LinearList）線性第21頁線性表的順序存儲結(jié)構(gòu)

順序存儲結(jié)構(gòu)把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元里，順序存儲結(jié)構(gòu)只存儲結(jié)點的值，不存儲結(jié)點間的關(guān)系，結(jié)點間的關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。…a1a2…ai…an…存儲地址200020042000+4*(i-1)2000+4*(n-1)……占4個字節(jié)Loa（ai）=Loa（a1）+L*（i-1）第i個數(shù)的地址第一個數(shù)的地址L為該類型數(shù)所占的字節(jié)線性表的存儲結(jié)構(gòu)線性表的存儲結(jié)構(gòu)有兩種：

順序存儲結(jié)構(gòu)

鏈?zhǔn)酱鎯Y(jié)構(gòu)第21頁線性表的順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)把邏第22頁順序表的插入運算順序表的刪除運算順序表的插入和刪除運算在線性表順序存儲情況下，要插入或刪除一個元素，都會由于數(shù)據(jù)元素的移動而消耗大量的處理時間，所以這種存儲方式對于小線性表或其中數(shù)據(jù)元素不經(jīng)常變動的線性表是合適的。線性表的順序存儲結(jié)構(gòu)稱為順序表。第22頁順序表的插入運算順序表的插入和刪除運算第23頁線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表。鏈?zhǔn)酱鎯Y(jié)構(gòu)不要求邏輯上相鄰的數(shù)據(jù)元素物理位置也相鄰，而且各數(shù)據(jù)元素的存儲順序也是任意的。各數(shù)據(jù)元素的先后關(guān)系是由各結(jié)點的指針域指示。鏈?zhǔn)酱鎯Y(jié)構(gòu)的每一個存儲結(jié)點不僅存儲結(jié)點的值，而且存儲結(jié)點之間的關(guān)系：數(shù)據(jù)域指針域第23頁線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈第24頁應(yīng)用舉例——線性鏈表的存儲結(jié)構(gòu)設(shè)線性表為（a1，a2，a3，a4，a5）1a2923a1145a4106789a3510a50HEAD3a1a2a5a3a4HEAD319510線性鏈表的邏輯狀態(tài)線性鏈表的物理狀態(tài)1a12a23a34a45a567線性表的順序存儲結(jié)構(gòu)注意:123此類編號不代表所在的地址單元的地址編碼第24頁應(yīng)用舉例——線性鏈表的存儲結(jié)構(gòu)設(shè)線性表為（a1，a2第25頁單鏈表的插入運算單鏈表的刪除運算線性鏈表的插入和刪除運算采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，存儲空間開銷較大，但是進行插入和刪除運算不會造成大量元素的移動。循環(huán)鏈表是加一種形式的鏈?zhǔn)酱鎯Y(jié)構(gòu)。它的特點是表中最后一個結(jié)點的指針域指向頭結(jié)點。

a1a2a5a3a4HEAD319510第25頁單鏈表的插入運算線性鏈表的插入和刪除運算采用鏈?zhǔn)酱娴?6頁雙向鏈表的存儲結(jié)構(gòu)

提問：單向鏈表的缺點是什么？提示：如何尋找結(jié)點的直接前趨。

雙向鏈表可以克服單鏈表的單向性的缺點。

在雙向鏈表的結(jié)點中有兩個指針域，其一指向直接后繼，另一指向直接前趨。HEAD31510a2a3a4a1雙向循環(huán)鏈表

第26頁雙向鏈表的存儲結(jié)構(gòu)提問：單向鏈表的缺點是什么？H第27頁線性表的存儲結(jié)構(gòu)有兩種

順序存儲結(jié)構(gòu)注意：數(shù)據(jù)元素在計算機存儲空間中的位置關(guān)系與它們的邏輯關(guān)系不一定是相同的。一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且不同的存儲結(jié)構(gòu)影響數(shù)據(jù)處理的效率。1a2923a1145a4106789a3510a50HEAD31a12a23a34a45a567鏈?zhǔn)酱鎯Y(jié)構(gòu)線性表:{a1，a2，a3，a4，a5}第27頁線性表的存儲結(jié)構(gòu)有兩種順序存儲結(jié)構(gòu)注意：1a292第28頁2.棧和隊列棧和隊列都是特殊的線性表。

棧（Stack）及其基本運算

隊列（Queue）及其基本運算

循環(huán)隊列及其基本運算第28頁2.棧和隊列棧和隊列都是特殊的線性表。第29頁棧（Stack）是一種特殊的線性表。其特點是插入和刪除運算都只能在線性表的一端進行。棧是按照“先進后出”或“后進先出”的原則組織數(shù)據(jù)的線性表。棧的物理存儲結(jié)構(gòu)可以用順序結(jié)構(gòu)，也可以用鏈表結(jié)構(gòu)。下面討論順序存儲結(jié)構(gòu)中棧元素的插入和刪除運算。順序棧的進棧和出棧運算棧的基本運算有三種：入棧、退棧和讀棧頂元素在順序棧中插入和刪除運算不需要移動表中其他數(shù)據(jù)元素。第29頁棧（Stack）是一種特殊的線性表。其特點是插入和刪第30頁隊列（Queue）是一種特殊的線性表。其特點是所有的插入都在表的一端進行，所有的刪除運算都在表的另一端進行。隊列是按照“先進先出”或“后進后出”的原則組織數(shù)據(jù)的線性表。隊列的物理存儲結(jié)構(gòu)可以用順序結(jié)構(gòu)，也可以用鏈?zhǔn)浇Y(jié)構(gòu)。順序隊列的運算棧有三種操作：入棧＼出棧＼讀棧頂元素隊列有三種操作：入隊＼出隊＼讀隊首元素例：有入棧元素序列：ABCD，求可能的出棧序列．如是隊列又是什么情況呢？第30頁隊列（Queue）是一種特殊的線性表。其特點是所有的第31頁循環(huán)隊列把隊列的存儲空間在邏輯上看作一個環(huán)，當(dāng)R指向存儲空間的末端后，就把它重新置于始端。循環(huán)隊列的運算隊列中進行插入的一端稱做隊尾(rear),進行刪除的一端稱做隊首(front)。

習(xí)題：數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，循環(huán)隊列屬于【】結(jié)構(gòu)。（2005年9月）答案：存儲結(jié)構(gòu)。第31頁循環(huán)隊列隊列中進行插入的一端稱做隊尾(rear第32頁常見數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)線性表

線性結(jié)構(gòu)棧

是特殊的線性表

隊列

也是一種操作受限的特殊的線性表樹（樹型結(jié)構(gòu)）是一種重要的非線形數(shù)據(jù)結(jié)構(gòu)第32頁常見數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)線性表線性第33頁數(shù)據(jù)存儲結(jié)構(gòu)方面的考題

1：數(shù)據(jù)的存儲結(jié)構(gòu)是指（2005年4月）A)存儲在外存中的數(shù)據(jù)B)數(shù)據(jù)所占的存儲空間量C)數(shù)據(jù)在計算機中的順序存儲方式D)數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示2.下列敘述中正確的是（2009年3月）A）棧是“先進先出”的線性表

B）隊列是“先進后出”的線性表

C）循環(huán)隊列是非線性結(jié)構(gòu)D）有序線性表既可以采用順序存儲結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)3.數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，帶鏈的隊列屬于[]。4.下列數(shù)據(jù)結(jié)構(gòu)中，屬于非線性結(jié)構(gòu)的是A）循環(huán)隊列B)帶鏈隊列C)二叉樹D）帶鏈棧答案：D。答案：D。答案：線性結(jié)構(gòu)。答案：c第33頁數(shù)據(jù)存儲結(jié)構(gòu)方面的考題1：數(shù)據(jù)的存儲結(jié)構(gòu)是指第34頁5。下列敘述中正確的是（）。（2008年9月）

A）順序存儲結(jié)構(gòu)的存儲一定是連續(xù)的，鏈?zhǔn)酱鎯Y(jié)構(gòu)的存儲空間不一定是連續(xù)的B）順序存儲結(jié)構(gòu)只針對線性結(jié)構(gòu)，鏈?zhǔn)酱鎯Y(jié)構(gòu)只針對非線性結(jié)構(gòu)C）順序存儲結(jié)構(gòu)能存儲有序表，鏈?zhǔn)酱鎯Y(jié)構(gòu)不能存儲有序表D）鏈?zhǔn)酱鎯Y(jié)構(gòu)比順序存儲結(jié)構(gòu)節(jié)省存儲空間答案：A。6。下列關(guān)于棧的敘述正確的是（2008年4月）

A）棧按“先進先出”組織數(shù)據(jù)B)棧按“先進后出”組織數(shù)據(jù)

C）只能在棧底插入數(shù)據(jù)D）不能刪除數(shù)據(jù)

答案：B。7.一個隊列的初始狀態(tài)為空。現(xiàn)將元素A，B，C，D，E，F(xiàn)，5，4，3，2，1依次入隊，然后再依次退隊，則元素退隊的順序為【1】。（2010年3月）

答案：A，B，C，D，E，F(xiàn)，5，4，3，2，1第34頁5。下列敘述中正確的是（）。（2008年9月）第35頁9.設(shè)某循環(huán)隊列的容量為50，如果頭指針front=45(指向隊頭元素的前一位置)，尾指針rear=10(指向隊尾元素)，則該循環(huán)隊列中共有【2】個元素。

（2010年3月）

8。假設(shè)用一個長度為50的數(shù)組（數(shù)組元索的下標(biāo)從0到49）作為棧的存儲空間，棧底指針bottom指間棧底元素，棧頂指針top指向棧頂元素，如果bottom=49，top=30（數(shù)組下標(biāo)），則棧中具有【】個元素。（2009年3月）

答案：19答案：15第35頁9.設(shè)某循環(huán)隊列的容量為50，如果頭指針front第36頁一個非空的數(shù)據(jù)結(jié)構(gòu)若滿足下面的兩個條件，則這種數(shù)據(jù)結(jié)構(gòu)即為線性結(jié)構(gòu)。①有且僅有一個根結(jié)點；②除第一個結(jié)點外，每一個結(jié)點最多有一個直接前驅(qū)結(jié)點；③除最后一個結(jié)點外，每一個結(jié)點最多有一個直接后繼結(jié)點。

線性結(jié)構(gòu)與非線性結(jié)構(gòu)線性表、棧和隊列都是線性結(jié)構(gòu)

一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱其為非線性結(jié)構(gòu)。a1a2a5a3a4HEAD319510線性鏈表的邏輯狀態(tài)第36頁一個非空的數(shù)據(jù)結(jié)構(gòu)若滿足下面的兩個條件，則這種數(shù)據(jù)結(jié)第37頁樹型結(jié)構(gòu)是一種重要的非線性結(jié)構(gòu)。

樹的概念

二叉樹的概念

二叉樹的存儲

二叉樹的遍歷3.樹與二叉樹第37頁樹型結(jié)構(gòu)是一種重要的非線性結(jié)構(gòu)。3.樹與二叉樹第38頁樹的概念

樹的定義：n個結(jié)點的有限集。（n>=0）

ABDFECGHIJKM根：onlyone若n=0，則稱為空樹；否則，當(dāng)n>1時，其余結(jié)點被分成m（m>0）個互不相交的子集T1，T2，...，Tm，每個子集又是一棵樹。由此可以看出，樹的定義是遞歸的。Question：如何辨別根？A只有一個結(jié)點的樹第38頁樹的概念樹的定義：n個結(jié)點的有限集。（n>=0）第39頁樹型結(jié)構(gòu)的常用術(shù)語ABDFECGHIJKM

結(jié)點的度一個結(jié)點的子樹的個數(shù)；Q：結(jié)點A、G的度數(shù)？

樹的度樹中所有結(jié)點度的最大值；Q：右圖中樹的度？

終端結(jié)點度為0的結(jié)點；Q：圖中葉子結(jié)點有幾個？7

非終端結(jié)點

度不為0的結(jié)點；Q：圖中非終端結(jié)點有幾個？5孩子結(jié)點、雙親結(jié)點、兄弟結(jié)點、結(jié)點的子孫、結(jié)點的祖先第39頁樹型結(jié)構(gòu)的常用術(shù)語ABDFECGHIJKM結(jié)點的度第40頁樹型結(jié)構(gòu)的常用術(shù)語ABDFECGHIJKM

結(jié)點的層次樹中根結(jié)點的層次為1，根結(jié)點子樹的根為第2層，以此類推；Q：圖中結(jié)點F的層次？

樹的深度

樹中所有結(jié)點層次的最大值；

Q：圖中樹的深度？

有序樹、無序樹如果樹中每棵子樹從左向右的排列擁有一定的順序，不得互換，則稱為有序樹，否則稱為無序樹。①②③④第40頁樹型結(jié)構(gòu)的常用術(shù)語ABDFECGHIJKM結(jié)點的第41頁二叉樹的概念

定義：二叉樹是一種有序的樹形結(jié)構(gòu)。它與一般樹形結(jié)構(gòu)的區(qū)別是：每個結(jié)點最多有兩棵子樹；子樹有左右之分，次序不能任意顛倒。

二叉樹的5種基本形態(tài)第41頁二叉樹的概念定義：二叉樹是一種有序的樹形結(jié)構(gòu)。第42頁二叉樹的性質(zhì)【性質(zhì)1】

在二叉樹的第i層上最多有2i-1個結(jié)點（i≥1）ABCDFEHG第42頁二叉樹的性質(zhì)【性質(zhì)1】在二叉樹的第i層上最多有2i第43頁【性質(zhì)2】深度為h的二叉樹最多有2h-1個結(jié)點（h≥1）滿二叉樹：如果一個深度為h的二叉樹擁有2h-1個結(jié)點，則將它稱為滿二叉樹。完全二叉樹：有一棵深度為h，具有n個結(jié)點的二叉樹，若將它與一棵同深度的滿二叉樹中的所有結(jié)點按從上到下，從左到右的順序分別進行編號，且該二叉樹中的每個結(jié)點分別與滿二叉樹中編號為1~n的結(jié)點位置一一對應(yīng)，則稱這棵二叉樹為完全二叉樹。第43頁【性質(zhì)2】深度為h的二叉樹最多有2h-1個結(jié)點（h第44頁121314158910114567123滿二叉樹完全二叉樹12138910114567123完全二叉樹是滿二叉樹滿二叉樹也是完全二叉樹第44頁121314158910114567123滿二叉樹完第45頁1213891011456123非完全二叉樹深度為4的完全二叉樹84567123第45頁1213891011456123非完全二叉樹深度為4第46頁【性質(zhì)3】二叉樹上葉子結(jié)點數(shù)比度為2的結(jié)點數(shù)多1ABCDFEHG度為2的結(jié)點葉子結(jié)點第46頁【性質(zhì)3】二叉樹上葉子結(jié)點數(shù)比度為2的結(jié)點數(shù)多1AB第47頁【性質(zhì)4】具有n個結(jié)點的完全二叉樹的深度為

log2(n+1)其中，log2n

的結(jié)果是不大于log2n的最大整數(shù)121314158910114567123深度為4的滿二叉樹深度為4的完全二叉樹84567123深度為3的完全二叉樹具有4～7深度為4的完全二叉樹具有8～15深度為5的完全二叉樹具有15～31log2(8+1)=ln9/In2=4log2(15+1)=In16/In2=4深度為6的完全二叉樹具有32～63深度為7的完全二叉樹具有64～127深度為8的完全二叉樹具有128～255深度為9的完全二叉樹具有256～511深度為10的完全二叉樹具有512～1023深度為11的完全二叉樹具有1024～2047第47頁【性質(zhì)4】具有n個結(jié)點的完全二叉樹的深度為lo第48頁1：在深度為7的滿二叉樹中,葉子結(jié)點的個數(shù)為（2006年4月）

A)32

B)31

C)64

D)632：在深度為7的滿二叉樹中，度為2的結(jié)點個數(shù)為【】。(07年4月）3：一棵二叉樹中共有70個葉子結(jié)點與80個度為1的結(jié)點，則該二叉樹中的總結(jié)點數(shù)為（07年9月）A）219B）221C）229D）2314：某二叉樹中度為2的結(jié)點有18個，則該二叉樹中有【】個葉子結(jié)點。（2005年4月）5：一棵二叉樹第六層（根結(jié)點為第一層）的結(jié)點數(shù)最多為【】個。（2005年9月）

樹型結(jié)構(gòu)方面的考題

1答案：C。3答案：A。5答案：32。2答案：63。4答案：19。第48頁1：在深度為7的滿二叉樹中,葉子結(jié)點的個數(shù)為（200第49頁二叉樹的存儲在計算機中，二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。LlinkinfoRlink二叉樹的存儲結(jié)點的結(jié)構(gòu)ABDCFGEA∧G∧∧E∧∧F∧B∧C∧

Dt第49頁二叉樹的存儲在計算機中，二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)第50頁二叉樹的遍歷遍歷指不重復(fù)地訪問二叉樹中的所有結(jié)點。二叉樹的遍歷的次序與樹型結(jié)構(gòu)上的大多數(shù)運算有聯(lián)系。遍歷的方式有三種（1）先（前）序遍歷（DLR）（2）中序遍歷（LDR）（3）后序遍歷（LRD）ABCDFEHG第50頁二叉樹的遍歷遍歷指不重復(fù)地訪問二叉樹中的所有結(jié)點。第51頁二叉樹的遍歷遍歷指不重復(fù)地訪問二叉樹中的所有結(jié)點。（1）先（前）序遍歷（DLR）若二叉樹為空，則結(jié)束遍歷操作；否則訪問根結(jié)點；先序遍歷左子樹；先序遍歷右子樹。ABCDFEHG先序遍歷的結(jié)果：

ABECFGHD第51頁二叉樹的遍歷遍歷指不重復(fù)地訪問二叉樹中的所有結(jié)點。第52頁（2）中序遍歷（LDR）若二叉樹為空，則結(jié)束遍歷操作；否則中序遍歷左子樹；訪問根結(jié)點；中序遍歷右子樹。中序遍歷的結(jié)果：EBAFHGCD（3）后序遍歷（LRD）若二叉樹為空，則結(jié)束遍歷操作；否則后序遍歷左子樹；后序遍歷右子樹；訪問根結(jié)點。后序遍歷的結(jié)果：E

BHGFDCAABCDFEHG第52頁（2）中序遍歷（LDR）ABCDFEHG第53頁先序序列：ABDGCEFH 中序序列：DGBAECHF 后序序列：GDBEHFCAABCFHDEG下圖所示的二叉樹經(jīng)過三種遍歷得到的順序分別為？練習(xí)：根據(jù)先序遍歷序列，建立二叉樹第53頁ABCFHDEG下圖所示的二叉樹經(jīng)過三種遍歷得到的順第54頁1:設(shè)二叉樹如下：

（2010年3月）

對該二叉樹進行后序遍歷的結(jié)果為【3】樹型結(jié)構(gòu)方面的考題

22:對如下二叉樹（2006年4月）進行后序遍歷的結(jié)果為A)ABCDEF

B)DBEAFCC)ABDECF

D)DEBFCA

EDBGHFCA

DABCFHDGE第54頁1:設(shè)二叉樹如下：

（2010年3月）

第55頁⒌查找技術(shù)查找是數(shù)據(jù)處理的重要內(nèi)容。查找指在一個給定的數(shù)據(jù)結(jié)構(gòu)中查找指定的元素，該元素也稱關(guān)鍵字。若找到了滿足條件的結(jié)點，稱查找成功；否則稱查找失敗。衡量一個查找算法的主要標(biāo)準(zhǔn)是查找過程中對關(guān)鍵字進行的平均比較次數(shù)。通常根據(jù)不同的數(shù)據(jù)結(jié)構(gòu)，采用不同的查找方法：

順序查找

二分查找第55頁⒌查找技術(shù)查找是數(shù)據(jù)處理的重要內(nèi)容。第56頁順序查找線性表中最簡單的查找方法。

方法：從線性表的第一個元素開始，依次將線性表中的元素與關(guān)鍵字進行比較，若相等，則查找成功；若將所有元素都與關(guān)鍵字進行了比較但不相等，則查找失敗。順序查找法的適用場合：對線性表中元素的排列次序沒有要求；對線性表的存儲結(jié)構(gòu)沒有要求，鏈?zhǔn)浇Y(jié)構(gòu)和順序結(jié)構(gòu)均可。第56頁順序查找線性表中最簡單的查找方法。第57頁二分查找(折半查找)

是一種效率較高的查找方法，但是只適合順序存儲的有序表。二分查找的方法：首先將關(guān)鍵字與線性表中間位置的結(jié)點比較，相等則查找成功；不相等則根據(jù)比較結(jié)果確定下一步查找應(yīng)在哪個子表中進行；重復(fù)上述過程，直至查找成功或子表長度為0。二分查找法的適用場合：線性表中的元素按關(guān)鍵字值遞增或遞減的次序排列；線性表采用順序存儲結(jié)構(gòu)。第57頁二分查找(折半查找)是一種效率較高的查找方法，但是第58頁練習(xí)

假設(shè)待查有序（升序）順序表中數(shù)據(jù)元素的關(guān)鍵字序列為（8,18,27,42,47,50,56,68,95,120），用折半查找方法查找關(guān)鍵字值為27的數(shù)據(jù)元素.對于長度為n的有序線性表，最壞情況只需比較log2n次。

第58頁練習(xí)對于長度為n的有序線性表，最壞情況只需比較log第59頁⒍排序技術(shù)

排序指將一個無序序列整理成按關(guān)鍵字值遞增或遞減排列的有序序列。排序方法中其排序?qū)ο笠话闶琼樞虼鎯Φ木€性表。根據(jù)排序序列的規(guī)模以及數(shù)據(jù)處理的要求，可以采用不同的排序方法：交換類排序法

冒泡排序快速排序

插入類排序法簡單插入排序希爾排序選擇類排序法簡單選擇排序堆排序第59頁⒍排序技術(shù)排序指將一個無序序列整理成按關(guān)鍵字值遞第60頁冒泡排序冒泡排序的方法：掃描整個線性表，逐次對相鄰的兩個元素進行比較，若為逆序，則交換；第一趟掃描的結(jié)果使最大(或最小)的元素排到表的最后(或最前)；除最后(或最前)一個元素，對剩余的元素重復(fù)上述過程，將次大(或次小)的數(shù)排到表的倒數(shù)(或正數(shù))第二個位置；重復(fù)上述過程；對于長度為n的線性表，冒泡排序需要對表掃描n-1遍。第60頁冒泡排序冒泡排序的方法：第61頁冒泡排序的方法設(shè)待排數(shù)據(jù)元素的關(guān)鍵字為（18，20，15，32，4，25），第一趟冒泡排序后的序列狀態(tài)如圖所示：

182015324251820153242518152032425181520324251815204322518152042532最大數(shù)第二趟冒泡排序第61頁冒泡排序的方法設(shè)待排數(shù)據(jù)元素的關(guān)鍵字為（18，20，第62|92頁Q：第二趟冒泡排序后的結(jié)果是什么樣的？達到了最終的排序目標(biāo)嗎？一共需要多少次能夠最后成為有序序列？Q：你覺得冒泡排序的效率如何？如果是你，你會用什么方法來排序？

冒泡排序比較簡單，當(dāng)初始序列基本有序時，冒泡排序有較高的效率，反之效率較低。冒泡排序終止條件:本趟排序未發(fā)生交換，終止排序算法第62|92頁Q：第二趟冒泡排序后的結(jié)果是什么樣的？達到了最第63|92頁初始第一趟第二趟第三趟第四趟第五趟序列排序后排序后排序后排序后排序后 26 18 1818 189 18 26 2626 915 32 32 329 15 18 54 47 915 26 47 9 1532

9 15 47

15 54

設(shè)待排數(shù)據(jù)元素的關(guān)鍵字為（26,18,32,54,47,9,15)冒泡排序法，需要比較的次數(shù)為n(n-1)/2；

第63|92頁初始第一趟第64頁選擇排序選擇排序的方法：掃描整個線性表，從中找出最小的元素，與第一個元素交換；除第一個元素，對剩下的子表采用相同的方法找出次小的數(shù)，與第二個數(shù)交換；重復(fù)上述過程；對于長度為n的線性表，選擇排序需要對表掃描n-1遍。簡單選擇排序法,

最壞情況需要n(n-1)/2次比較；

第64頁選擇排序選擇排序的方法：簡單選擇排序法,

最壞情況第65|92頁初態(tài)：[15，14，22，30，37，15，11]第一趟：[11][14，22，30，37，15，15]第二趟：[11，14][22，30，37，15，15]第三趟：[11，14，15][30，37，22，15]第四趟：[11，14，15，15][37，22，30]第五趟：[11，14，15，15，22][37，30]第六趟：[11，14，15，15，22，30][37]

有序序列例：設(shè)待排數(shù)據(jù)元素的關(guān)鍵字為（15，14，22，30，37，11），每一趟排序后的序列狀態(tài)如圖所示：第65|92頁初態(tài)：[15，14，22，30，37第66頁排序法小結(jié)：簡單選擇排序法,

最壞情況需要n(n-1)/2次比較；冒泡排序法,

最壞情況需要n(n-1)/2次比較；希爾排序法,

最壞情況需要O(n1.5)次比較；堆排序法,最壞情況需要O(nlog2n)次比較；

第66頁排序法小結(jié)：簡單選擇排序法,

最壞情況需要n(n-1第67頁排序查找方面的考題：(1)對于長度為n的線性表，在最壞情況下，下列各排序法所對應(yīng)的比較次數(shù)中正確的是（2005年4月）A)冒泡排序為n/2B)冒泡排序為nC)快速排序為nD)快速排序為n(n-1)/2

(2)在長為64的有序線性表中進行順序查找，最壞情況下需要比較的次數(shù)為______。（06年9月）

A）、63B）、64C）、6D）、7(3)下列數(shù)據(jù)結(jié)構(gòu)中，能用二分法進行查找的是（2005年9月）A）順序存儲的有序線性表 B）線性鏈表C）二叉鏈表 D）有序線性鏈表(4)下列排序方法中，最壞情況下比較次數(shù)最少的是（09年3月）

A）冒泡排序

B）簡單選擇排序

C）直接插入排序

D）堆排序DBAD第67頁排序查找方面的考題：(1)對于長度為n的線性表，在第68頁第二章程序設(shè)計基礎(chǔ)內(nèi)容：

1.程序設(shè)計方法與風(fēng)格。2.結(jié)構(gòu)化程序設(shè)計。3.面向?qū)ο蟮某绦蛟O(shè)計方法，對象，方法，屬性及繼承與多態(tài)性。第68頁第二章程序設(shè)計基礎(chǔ)內(nèi)容：第69頁1．結(jié)構(gòu)化程序設(shè)計

結(jié)構(gòu)化程序設(shè)計方法的四條原則是：1.自頂向下；2.逐步求精；3.模塊化；4.限制使用goto語句。

結(jié)構(gòu)化程序的基本結(jié)構(gòu)和特點：

（1）順序結(jié)構(gòu)：簡單的程序設(shè)計，最基本、最常用的結(jié)構(gòu)；

（2）選擇結(jié)構(gòu)（分支結(jié)構(gòu)）：包括簡單選擇和多分支選擇結(jié)構(gòu)，

（3）重復(fù)結(jié)構(gòu)（循環(huán)結(jié)構(gòu)）：可根據(jù)給定條件，判斷是否需要重復(fù)執(zhí)行某一相同程序段。第69頁1．結(jié)構(gòu)化程序設(shè)計結(jié)構(gòu)化程序設(shè)計方法的四條原則是：第70頁2．面向?qū)ο蟮某绦蛟O(shè)計

對象是面向?qū)ο蠓椒ㄖ凶罨镜母拍睢?/p>

對象是系統(tǒng)中用來描述客觀事物的一個實體，是構(gòu)成系統(tǒng)的一個基本單位，由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。屬性即對象所包含的信息操作描述了對象執(zhí)行的功能，操作也稱為方法或服務(wù)。第70頁2．面向?qū)ο蟮某绦蛟O(shè)計對象是面向?qū)ο蠓椒ㄖ凶罨镜牡?1頁類是指具有共同屬性、共同方法的對象的集合。所以類是對象的抽象，對象是對應(yīng)類的一個實例。消息是一個實例與另一個實例之間傳遞的信息。

消息的組成包括（1）接收消息的對象的名稱；（2）消息標(biāo)識符，也稱消息名；（3）零個或多個參數(shù)。繼承是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義他們。單繼承指一個類只允許有一個父類多重繼承指一個類允許有多個父類。多態(tài)性是指同樣的消息被不同的對象接受時可導(dǎo)致完全不同的行動的現(xiàn)象。第71頁類是指具有共同屬性、共同方法的對象的集合。第72頁程序設(shè)計基礎(chǔ)方面的考題1.符合結(jié)構(gòu)化原則的三種基本控制結(jié)構(gòu)是：選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)和【】

.(2009年3月)2.下列選項中不屬于結(jié)構(gòu)化程序設(shè)計原則的是（2009年9月）A)可封裝D)自頂向下C)模塊化D)逐步求精3.以下敘述中正確的是。（2010年3月）A）程序設(shè)計的任務(wù)就是編寫程序代碼并上機調(diào)試B）程序設(shè)計的任務(wù)就是確定所用數(shù)據(jù)結(jié)構(gòu)C）程序設(shè)計的任務(wù)就是確定所用算法D）以上三種說法都不完整4.在面向?qū)ο蠓椒ㄖ?，類的實例稱為【____】。（2005年4月）5.在面向?qū)ο蠓椒ㄖ?【____】描述的是具有相似屬性與操作的一組對象。（2006年4月）（順序結(jié)構(gòu)）A

D對象類第72頁程序設(shè)計基礎(chǔ)方面的考題1.符合結(jié)構(gòu)化原則的三種基本控第73頁第三章軟件工程基礎(chǔ)計算機軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。軟件按功能分為應(yīng)用軟件、系統(tǒng)軟件、支撐軟件（或工具軟件）。

第73頁第三章軟件工程基礎(chǔ)計算機軟件是包括程序、數(shù)據(jù)及相關(guān)第74頁1.軟件工程概念軟件工程是應(yīng)用于計算機軟件的定義、開發(fā)和維護的一整套方法、工具、文檔、實踐標(biāo)準(zhǔn)和工序。

軟件工程包括3個要素：方法、工具和過程。軟件周期：軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停止使用退役的過程。

軟件生命周期三個階段:軟件定義、軟件開發(fā)、運行維護，主要活動階段是：

（1）可行性研究與計劃制定；

（2）需求分析；

（3）軟件設(shè)計；

（4）軟件實現(xiàn)；

（5）軟件測試；

（6）運行和維護。第74頁1.軟件工程概念軟件工程是應(yīng)用于計算機軟件的定義、開第75頁2．結(jié)構(gòu)化分析方法結(jié)構(gòu)化分析方法：著眼于數(shù)據(jù)流，自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具,建立系統(tǒng)的邏輯模型。結(jié)構(gòu)化分析的常用工具（1）數(shù)據(jù)流圖；

（2）數(shù)據(jù)字典；

（3）判定樹；

判定表。

（4）軟件需求規(guī)格說明書第75頁2．結(jié)構(gòu)化分析方法結(jié)構(gòu)化分析方法：著眼于數(shù)據(jù)流，自頂?shù)?6頁3．結(jié)構(gòu)化設(shè)計方法軟件設(shè)計包括：總體設(shè)計與詳細設(shè)計在程序結(jié)構(gòu)中各模塊的內(nèi)聚性越強，則耦合性越弱。優(yōu)秀軟件應(yīng)高內(nèi)聚，低耦合。常見的過程設(shè)計工具有：圖形工具（程序流程圖,N-S,PAD）表格工具（判定表）語言工具（PDL偽碼）第76頁3．結(jié)構(gòu)化設(shè)計方法軟件設(shè)計包括：總體設(shè)計與詳細設(shè)計第77頁程序流程圖N-S圖PAD圖第77頁程序流程圖N-S圖PAD圖第78頁4．軟件測試軟件測試的目的：發(fā)現(xiàn)錯誤而執(zhí)行程序的過程。

軟件測試方法：

靜態(tài)測試：

包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量。不實際運行軟件，主要通過人工進行。

動態(tài)測試：

是基本計算機的測試，主要包括白盒測試方法和黑盒測試方法

軟件測試過程一般按4個步驟進行：單元測試、集成測試、驗收測試（確認(rèn)測試）和系統(tǒng)測試。第78頁4．軟件測試軟件測試的目的：發(fā)現(xiàn)錯誤而執(zhí)行程序的過第79頁5．程序的調(diào)試

程序調(diào)試的任務(wù)是診斷和改正程序中的錯誤，主要在開發(fā)階段進行。軟件調(diào)試靜態(tài)調(diào)試主要是指通過人的思維來分析源程序代碼和排錯，是主要的設(shè)計手段。動態(tài)調(diào)試是輔助靜態(tài)調(diào)試。主要調(diào)試方法有：

（1）強行排錯法；

（2）回溯法；

（3）原因排除法。第79頁5．程序的調(diào)試程序調(diào)試的任務(wù)是診斷和改正程序中的第80頁(1)下面敘述中錯誤的是(2009年3月）

A）軟件測試的目的是發(fā)現(xiàn)錯誤并改正錯誤B）對被調(diào)試的程序進行“錯誤定位”是程序調(diào)試的必要步驟C）程序調(diào)試通常也稱為DebugD）軟件測試應(yīng)嚴(yán)格執(zhí)行測試計劃，排除測試的隨意性(2)軟件測試可分為白盒測試和黑盒測試?；韭窂綔y試屬于【】測試。(2009年3月）(3)

按照軟件測試的一般步驟，集成測試應(yīng)在_____測試之后進行。(4)軟件工程三要素包括方法、工具和過程，其中，_____支持軟件開發(fā)的各個環(huán)節(jié)的控制和管理。(2008年9月)(5)軟件設(shè)計中劃分模塊的一個準(zhǔn)則是(2009年9月）A)低內(nèi)聚低耦合B)高內(nèi)聚低耦合C)低內(nèi)聚高耦合D)高內(nèi)聚高耦合A

軟件工程方面的考題：白盒

單元過程B第80頁(1)下面敘述中錯誤的是(2009年3月）A第81頁(6)下列敘述中正確的是（2005年9月）AA）軟件交付使用后還需要進行維護B）軟件一旦交付使用就不需要再進行維護C）軟件交付使用后其生命周期就結(jié)束D）軟件維護是指修復(fù)程序中被破壞的指令(7)程序流程圖中的菱形框表示的是【2】(2009年9月)。(8)軟件開發(fā)過程主要分為需求分析、設(shè)計、編碼與測試四個階段，其中【3】階段產(chǎn)生“軟件需求規(guī)格說明書。（2009年9月）

(9)下列敘述中正確的是（2006年4月）

A)軟件測試應(yīng)該由程序開發(fā)者來完成

B)程序經(jīng)調(diào)試后一般不需要再測試

C)軟件維護只包括對程序代碼的維護

D)以上三種說法都不對A

邏輯條件需求分析D第81頁(6)下列敘述中正確的是（2005年9月）AA邏第82頁(3)軟件按功能可以分為：應(yīng)用軟件、系統(tǒng)軟件和支撐軟件(或工具軟件)。下面屬于系統(tǒng)軟件的是A)編輯軟件B)操作系統(tǒng)C)教務(wù)管理系統(tǒng)D)瀏覽器(4)軟件(程序)調(diào)試的任務(wù)是A)診斷和改正程序中的錯誤B)盡可能多地發(fā)現(xiàn)程序中的錯誤C)發(fā)現(xiàn)并改正程序中的所有錯誤D)確定程序中錯誤的性質(zhì)(5)數(shù)據(jù)流程圖(DFD圖)是A)軟件概要設(shè)計的工具B)軟件詳細設(shè)計的工具C)結(jié)構(gòu)化方法的需求分析工具D)面向?qū)ο蠓椒ǖ男枨蠓治龉ぞ?6)軟件生命周期可分為定義階段，開發(fā)階段和維護階段。詳細設(shè)計屬于A)定義階段B)開發(fā)階段C)維護階段D)上述三個階段2010年3月計算機等級考試

BA

C

B

第82頁(3)軟件按功能可以分為：應(yīng)用軟件、系統(tǒng)軟件和支撐軟第83頁數(shù)據(jù)庫設(shè)計基礎(chǔ)知識點得分表數(shù)據(jù)庫的基本概念數(shù)據(jù)模型關(guān)系代數(shù)數(shù)據(jù)庫設(shè)計與管理小計08年4月2分6分2分10分08年9月2分4分2分2分10分09年3月2分2分2分4分10分09年9月2分2分2分4分10分10年3月2分4分2分2分10分時間知識點第83頁數(shù)據(jù)庫設(shè)計基礎(chǔ)知識點得分表數(shù)據(jù)庫的基本概念數(shù)據(jù)關(guān)系數(shù)第84頁第四章數(shù)據(jù)庫設(shè)計基礎(chǔ)數(shù)據(jù)：實際上就是描述事物的符號記錄。數(shù)據(jù)庫：是數(shù)據(jù)的集合，具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲介質(zhì)內(nèi)，是多種應(yīng)用數(shù)據(jù)的集成，并可被各個應(yīng)用程序共享。數(shù)據(jù)庫管理系統(tǒng)：一種系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)庫中的數(shù)據(jù)組織、數(shù)據(jù)操縱、數(shù)據(jù)維護、控制及保護和數(shù)據(jù)服務(wù)等，是數(shù)據(jù)庫的核心。數(shù)據(jù)庫系統(tǒng)：由數(shù)據(jù)庫（數(shù)據(jù)）、數(shù)據(jù)庫管理系統(tǒng)（軟件）、數(shù)據(jù)庫管理員（人員）、硬件平臺（硬件）、軟件平臺（軟件）五個部分構(gòu)成的運行實體。數(shù)據(jù)庫應(yīng)用系統(tǒng)：由數(shù)據(jù)庫系統(tǒng)、應(yīng)用軟件及應(yīng)用界面三者組成。第84頁第四章數(shù)據(jù)庫設(shè)計基礎(chǔ)數(shù)據(jù)：實際上就是描述事物的符號第85頁數(shù)據(jù)庫系統(tǒng)第85頁數(shù)據(jù)庫系統(tǒng)86常見的關(guān)系數(shù)據(jù)庫管理系統(tǒng)小型數(shù)據(jù)庫：VisualFoxPro（以后簡稱為VFP）Access(office套件中的一個)Paradox大型數(shù)據(jù)庫：OracleInformixSYBASESQLserver等86常見的關(guān)系數(shù)據(jù)庫管理系統(tǒng)小型數(shù)據(jù)庫：第87頁數(shù)據(jù)庫管理系統(tǒng)提供的數(shù)據(jù)語言：

（1）數(shù)據(jù)定義語言：負(fù)責(zé)數(shù)據(jù)的模式定義與數(shù)據(jù)的物理存取構(gòu)建；（2）數(shù)據(jù)操縱語言：

負(fù)責(zé)數(shù)據(jù)的操縱，如查詢與增、刪、改等；

（3）數(shù)據(jù)控制語言：負(fù)責(zé)數(shù)據(jù)完整性、安全性的定義與檢查以及并發(fā)控制、故障恢復(fù)等。數(shù)據(jù)庫管理系統(tǒng)的發(fā)展(1)文件系統(tǒng)階段：提供了簡單的數(shù)據(jù)共享與數(shù)據(jù)管理能力，但是它無法提供完整的、統(tǒng)一的、管理和數(shù)據(jù)共享的能力。(2)層次數(shù)據(jù)庫與網(wǎng)狀數(shù)據(jù)庫系統(tǒng)階段：為統(tǒng)一與共享數(shù)據(jù)提供了有力支撐。(3)關(guān)系數(shù)據(jù)庫系統(tǒng)階段1.數(shù)據(jù)庫系統(tǒng)的基本概念第87頁數(shù)據(jù)庫管理系統(tǒng)提供的數(shù)據(jù)語言：

（1）數(shù)據(jù)定義語言：第88頁關(guān)系數(shù)據(jù)庫系統(tǒng)的基本特點：數(shù)據(jù)的集成性數(shù)據(jù)的高共享性與低冗余性數(shù)據(jù)獨立性（物理獨立性與邏輯獨立性）數(shù)據(jù)統(tǒng)一管理與控制。數(shù)據(jù)庫存放數(shù)據(jù)是按數(shù)據(jù)所提供的數(shù)據(jù)模式存放的，具有集成與共享的特點。數(shù)據(jù)庫系統(tǒng)的三級模式：

（1）概念模式（2）外模式（3）內(nèi)模式數(shù)據(jù)庫系統(tǒng)的兩級映射：

（1）概念模式到內(nèi)模式的映射；

（2）外模式到概念模式的映射。1.數(shù)據(jù)庫系統(tǒng)的基本概念第88頁關(guān)系數(shù)據(jù)庫系統(tǒng)的基本特點：1.數(shù)據(jù)庫系統(tǒng)的基本概念89應(yīng)用外模式(用戶數(shù)據(jù)庫)應(yīng)用外模式(用戶數(shù)據(jù)庫)應(yīng)用外模式(用戶數(shù)據(jù)庫)概念模式(概念數(shù)據(jù)庫)內(nèi)模式(物理數(shù)據(jù)庫)數(shù)據(jù)庫外模式→概念模式映射概念模式→內(nèi)模式映射模式89應(yīng)用外模式應(yīng)用外模式應(yīng)用外模式概念模式內(nèi)模式數(shù)據(jù)庫外模式902.數(shù)據(jù)模型數(shù)據(jù)模型（DataModel）是對客觀事物及其關(guān)系的數(shù)據(jù)描述。數(shù)據(jù)庫中的數(shù)據(jù)模型可以將復(fù)雜的現(xiàn)實世界要求反映到計算機數(shù)據(jù)庫中的物理世界?，F(xiàn)實世界信息世界計算機世界

數(shù)據(jù)模型是數(shù)據(jù)特征的抽象，從抽象層次上描述了系統(tǒng)的靜態(tài)特征、動態(tài)行為和約束條件。數(shù)據(jù)模型所描述的內(nèi)容包含：數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作和數(shù)據(jù)約束。902.數(shù)據(jù)模型數(shù)據(jù)模型（DataModel）是對客觀事第91頁2.數(shù)據(jù)模型E-R模型的基本概念

（1）實體：現(xiàn)實世界中的事物；

（2）屬性：事物的特性；

（3）聯(lián)系：現(xiàn)實世界中事物間的關(guān)系。實體集的關(guān)系有一對一、一對多、多對多的聯(lián)系。

一個班級的學(xué)生，學(xué)生與學(xué)生之間是一對一的關(guān)系。在一所學(xué)校，一門課程與學(xué)生之間是一對多的關(guān)系。在一所學(xué)校，多門課程與多個學(xué)生之間是多對多的關(guān)系。第91頁2.數(shù)據(jù)模型E-R模型的基本概念

（1）實體：現(xiàn)實92E-R模型的圖示法用簡單的幾何圖形表示實體集、屬性與聯(lián)系。(1)實體集表示法在E-R圖中用矩形表表示實體集，在矩形內(nèi)寫上實體集名稱。如實體集學(xué)生(student)、實體集課程(course)(2)屬性表示法在E-R圖中用橢圓形表示屬性，在橢圓形內(nèi)寫上該屬性名稱。如學(xué)生有屬性：學(xué)號(S#)、姓名(Sn)及年齡(Sa)可用如下表示。studentcourseS#SnSa92E-R模型的圖示法studentcourseS#SnSa93(3)聯(lián)系表示法在E-R圖中用菱形(內(nèi)寫上聯(lián)系名)表示聯(lián)系。如學(xué)生與課程的聯(lián)系SC,如下圖所示：(4)實體集與屬性間的聯(lián)系關(guān)系屬性依附于實體集，它們之間有聯(lián)系關(guān)系用無向線段表示。SCstudentS#SnSa93(3)聯(lián)系表示法SCstudentS#SnSa94屬性也依附于聯(lián)系，它們之間也有聯(lián)系關(guān)系，因此也可用無向線段，如聯(lián)系SC可與學(xué)生的課程成績屬性G建立聯(lián)系并用下圖表示。(5)實體集與聯(lián)系間的連接關(guān)系(也可用無向線段)SCGstudentcourseSC94屬性也依附于聯(lián)系，它們之間也有聯(lián)系關(guān)系，因此也可用無向線第95頁E-R模型之間的聯(lián)接關(guān)系：實體是概念世界中的基本單位，屬性有屬性域，每個實體可取屬性域內(nèi)的值。一個實體的所有屬性值叫元組。

E-R模型的圖示法：（1）實體集表示法；用長方形（2）屬性表法；用橢圓形（3）聯(lián)系表示法。用菱形，(m:n)第95頁E-R模型之間的聯(lián)接關(guān)系：第96頁層次模型（采用樹型結(jié)構(gòu)）圖1-4層次模型示例第96頁層次模型（采用樹型結(jié)構(gòu)）圖1-4層次模型示例第97頁

網(wǎng)絡(luò)模型（采用無向圖型結(jié)構(gòu)）第97頁

網(wǎng)絡(luò)模型（采用無向圖型結(jié)構(gòu)）第98頁關(guān)系模型（采用二維表結(jié)構(gòu)）第98頁關(guān)系模型（采用二維表結(jié)構(gòu)）第99頁關(guān)系數(shù)據(jù)模型關(guān)系模型采用二維表來表示，簡稱表，由表框架及表的元組組成。一個二維表就是一個關(guān)系。關(guān)系數(shù)據(jù)庫系統(tǒng)的特點之一是它建立在數(shù)據(jù)理論的基礎(chǔ)之上，有很多數(shù)據(jù)理論可以表示關(guān)系模型的數(shù)據(jù)操作，其中最為著名的是關(guān)系代數(shù)與關(guān)系演算。學(xué)號姓名性別出生日期入學(xué)成績四級通過否計算機等級考試備注04001001尚杰男86-11-20520.5T一級04001002余習(xí)芳女86-12-26513.5F二級04001057張軼一男86-01-09612.0T04002023陶紅莉女85-02-14535.0F二級第99頁關(guān)系數(shù)據(jù)模型關(guān)系模型采用二維表來表示，簡稱表，由表框1001.關(guān)系的數(shù)據(jù)結(jié)構(gòu)二維表由表框架與表元組組成。表框架由n個命名的屬性組成(n稱為屬性元素)。每個屬性有一個取值范圍稱為值域。表框架對應(yīng)了關(guān)系的模式，即類型的概念。每行數(shù)據(jù)稱為元組，一個元組由n個元組分量所組成，每個元組分量是表結(jié)構(gòu)中每個屬性的投影值。學(xué)號姓名性別出生日期入學(xué)成績四級通過否計算機等級考試備注04001001尚杰男86-11-20520.5T一級04001002余習(xí)芳女86-12-26513.5F二級04001057張軼一男86-01-09612.0T04002023陶紅莉女85-02-14535.0F二級1001.關(guān)系的數(shù)據(jù)結(jié)構(gòu)學(xué)號姓名性別出生日期入學(xué)成績四級通過101一個二維表要滿足下面7個性質(zhì)就可稱為一個關(guān)系。①二維表中元組個數(shù)是有限的②二維表中元組均不相同③二維表中元組的次序可任意交換④二維表中元組的分量是不可分割的基本數(shù)據(jù)項⑤二維表中屬性名各不相同⑥二維表中屬性與次序無關(guān)，可任意交換⑦二維表屬性中的分量具有與該屬性相同的值域二維表關(guān)系模型VFP表文件二維表框架關(guān)系模式數(shù)據(jù)表結(jié)構(gòu)行元組記錄

元組分量數(shù)據(jù)項列屬性字段

屬性值域字段值域惟一標(biāo)識元組的最小屬性集稱為該表的鍵(或碼)，在VFP表中稱為主關(guān)鍵字101一個二維表要滿足下面7個性質(zhì)就可稱為一個關(guān)系。二維表關(guān)102關(guān)系模型的基本運算：

1.數(shù)據(jù)查詢

查詢關(guān)系數(shù)據(jù)庫中的數(shù)據(jù)，一個關(guān)系內(nèi)的查詢以及多個關(guān)系間的查詢。

查詢的基本單位為元組分量，先定位后操作。

縱向定位（列指定）橫向定位（行選擇）2.數(shù)據(jù)插入插入一個元組（不定位）

3.數(shù)據(jù)刪除刪除一個元組（定位、操作）

4.數(shù)據(jù)修改刪除需修改的元組再插入修改后的元組關(guān)系操作102關(guān)系模型的基本運算：關(guān)系操作103關(guān)系模型的基本運算：

1.插入集合的并運算

2.刪除集合的差(交)

運算

3.修改集合的差|并(除)運算。

4.查詢（投影、選擇、笛卡爾積運算）3.關(guān)系代數(shù)集合的并運算103關(guān)系模型的基本運算：3.關(guān)系代數(shù)集合的并運算104

由關(guān)系R和S通過交運算得到關(guān)系T，104

由關(guān)系R和S通過交運算得到關(guān)系T，105用于查詢的集合運算：（1）投影對于關(guān)系R內(nèi)的域指定稱為投影運算。S關(guān)系就是對R關(guān)系指定A和B兩個域的結(jié)果ABCa32b01c21ABa3b0c2RS3.關(guān)系代數(shù)105用于查詢的集合運算：ABCa32b01c21ABa3b106關(guān)系代數(shù)（2）選擇選擇運算的關(guān)系是由關(guān)系R中那些滿足邏輯條件的元組所組成。S關(guān)系就是R關(guān)系中滿足A=‘a(chǎn)’的結(jié)果ABCa32b01a69c21RSABCa32a69有了投影和選擇運算，我們對一個關(guān)系內(nèi)的任意行、列的數(shù)據(jù)都可以方便的找到。106關(guān)系代數(shù)（2）選擇ABCa32b01a69c21RSA107笛卡爾積是對兩個關(guān)系的合并操作。有三個關(guān)系R、S和T

R關(guān)系n1行,m1列S關(guān)系n2行，m2列

T關(guān)系行數(shù)=n1*n2列數(shù)=m1+m2AmnBC13ABCm13n13RST（3）笛卡爾積運算107笛卡爾積是對兩個關(guān)系的合并操作。AmnBC13ABCm108笛卡爾積建立兩個關(guān)系的連接，但得到的關(guān)系龐大且數(shù)據(jù)大量冗余。在實際應(yīng)用中一般相互連接的關(guān)系往往須滿足一些條件，所得到的結(jié)果也較為簡單。自然連接滿足兩個關(guān)系中有公共域，通過公共域的相等值進行連接。有三個關(guān)系R、S和T

R關(guān)系n1行,m1列S關(guān)系n2行，m2列T關(guān)系行數(shù)≤(n1或n2中行數(shù)多的一個)列數(shù)≤m1+m2（4）自然連接運算108笛卡爾積建立兩個關(guān)系的連接，但得到的關(guān)系龐大且109有三個關(guān)系R、S和T，由關(guān)系R和S通過運算得到關(guān)系T，則使用的運算為笛卡爾積ABk1f1k2r1BCf13r13ABCk1f13k2r13RST自然連接ABk1f1k2r1BCf13r13ABBCk1f1f13k1f1r13k2r1f13k2r1r13RST109有三個關(guān)系R、S和T，由關(guān)系R和S通過運算得到關(guān)系T，110在三個關(guān)系R，S和T如下：由關(guān)系R和S通過自然連接運算得到關(guān)系T。ABm1n2BC1335ABCm13RST110在三個關(guān)系R，S和T如下：ABm1n2BC1335第111頁

數(shù)據(jù)庫設(shè)計與管理數(shù)據(jù)庫設(shè)計的兩種方法：

（1）面向數(shù)據(jù)：以信息需求為主，兼顧處理需求；

（2）面向過程：以處理需求為主，兼顧信息需求。

數(shù)據(jù)庫的生命周期：需求分析階段結(jié)構(gòu)析方法和面向?qū)ο蟮姆椒〝?shù)據(jù)字典是各類數(shù)據(jù)描述的集合，包括5個部分：數(shù)據(jù)項、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)流、數(shù)據(jù)存儲、處理過程。概念設(shè)計階段分析數(shù)據(jù)內(nèi)在語義關(guān)系。E-R模型邏輯設(shè)計階段物理設(shè)計階段編碼階段測試階段運行階段進一步修改階段第111頁數(shù)據(jù)庫設(shè)計與管理數(shù)據(jù)庫設(shè)計的兩種方法：

（1）面1124.4數(shù)據(jù)庫設(shè)計與管理數(shù)據(jù)庫應(yīng)用系統(tǒng)(DBAS)中,核心問題是數(shù)據(jù)庫設(shè)計。需求分析概念設(shè)計邏輯設(shè)計物理設(shè)計編碼測試運行進一步修改分析客戶的業(yè)務(wù)和數(shù)據(jù)處理需求;設(shè)計數(shù)據(jù)庫的E-R模型圖，確認(rèn)需求信息的正確和完整;將E-R圖轉(zhuǎn)換為多張表，進行邏輯設(shè)計,并應(yīng)用數(shù)據(jù)庫設(shè)計的三大范式進行審核;

數(shù)據(jù)庫內(nèi)模式包括存儲結(jié)構(gòu)和存取方法。

重點記8個階段選擇具體數(shù)據(jù)庫進行物理實現(xiàn)，并編寫代碼實現(xiàn)前端應(yīng)用;

1124.4數(shù)據(jù)庫設(shè)計與管理數(shù)據(jù)庫應(yīng)用系統(tǒng)(DBAS)中,第113頁數(shù)據(jù)庫管理的內(nèi)容（1）數(shù)據(jù)庫的建立；（2）數(shù)據(jù)庫的調(diào)整；（3）數(shù)據(jù)庫的重組；（4）數(shù)據(jù)庫安全性與完整性控制；（5）數(shù)據(jù)庫的故障恢復(fù)；（6）數(shù)據(jù)庫監(jiān)控。第113頁數(shù)據(jù)庫管理的內(nèi)容（1）數(shù)據(jù)庫的建立；11406年9月全國計算機等級考試二級筆試試卷一、單選題4)在數(shù)據(jù)庫系統(tǒng)中,用戶所見的數(shù)據(jù)模式為A)概念模式B)外模式C)內(nèi)模式D)物理模式5)數(shù)據(jù)庫設(shè)計的四個階段是:需求分析、概念設(shè)計、邏輯設(shè)計和A)編碼設(shè)計B)測試階段C)運行階段D)物理設(shè)計D4D5√√11406年9月全國計算機等級考試二級筆試試卷一、單選題D41156）設(shè)有如下三個表AmnBC13ABCm13n13下列操作中正確的是A)T=R∩SB)T=R∪SC)T=R×SD)=R/SRSTD6√A)并B)交C)笛卡爾積D)除1156）設(shè)有如下三個表AmnBC13ABCm13n13下列1169)數(shù)據(jù)庫技術(shù)的根本目標(biāo)是要解決數(shù)據(jù)的A)存儲問題B)共享問題C)安全問題D)保護文題二、填空題3)一個關(guān)系表的行稱為【3】

D9T3√元組1169)數(shù)據(jù)庫技術(shù)的根本目標(biāo)是要解決數(shù)據(jù)的D9T3√元組11707年4月全國計算機等級考試二級筆試試卷一、單選題8）在下列關(guān)系運算中，不改變關(guān)系表中的屬性個數(shù)但能減少元組個數(shù)為A）并

B）交

C）投影

D）笛卡兒乘積9）在E-R圖中，用來表示實體之間聯(lián)系的圖形是

A）矩形

B）橢圓形

C）菱形

D）平行四邊形√√D9D811707年4月全國計算機等級考試二級筆試試卷一、單選題√√11810）下列敘述中錯誤的是

A）在數(shù)據(jù)庫系統(tǒng)中，數(shù)據(jù)的物理結(jié)構(gòu)必須與邏輯結(jié)構(gòu)一致

B）數(shù)據(jù)庫技術(shù)的根本目標(biāo)是要解決數(shù)據(jù)的共享問題

C）數(shù)據(jù)庫設(shè)計是指在已有數(shù)據(jù)庫管理系統(tǒng)的基礎(chǔ)上建立數(shù)據(jù)庫

D）數(shù)據(jù)庫系統(tǒng)需要操作系統(tǒng)的支持√D10二、填空題3）在數(shù)據(jù)庫系統(tǒng)中實現(xiàn)各種數(shù)據(jù)管理功能的核心軟件稱為【3】

。數(shù)據(jù)庫管理系統(tǒng)或DBMST311810）下列敘述中錯誤的是√D10二、填空題數(shù)據(jù)庫管理系11907年9月全國計算機等級考試二級筆試試卷一、單選題9)下列敘述中正確的是A)數(shù)據(jù)庫系統(tǒng)是一個獨立的系統(tǒng)，不需要操作系統(tǒng)的支持B)數(shù)據(jù)庫技術(shù)的根本目標(biāo)是要解決數(shù)據(jù)的共享問題C)數(shù)據(jù)庫管理系統(tǒng)就是數(shù)據(jù)庫系統(tǒng)D)以上三種說法都不對 D9√11907年9月全國計算機等級考試二級筆試試卷一、單選題D912010)下列敘述中正確的是A)為了建立一個關(guān)系，首先要構(gòu)造數(shù)據(jù)的邏輯關(guān)系B)表示關(guān)系的二維表中各元組的每一個分量還可以分成若干數(shù)據(jù)項C)一個關(guān)系的屬性名表稱為關(guān)系模式D)一個關(guān)系可以包括多個二維表二、填空題5)在E-R圖中，矩形表示[5]。D10T5√實體集12010)下列敘述中正確的是D10T5√實體集12108年4月全國計算機等級考試二級筆試試卷一、單選題8)在數(shù)據(jù)庫設(shè)計中，將E-R圖轉(zhuǎn)換成關(guān)系數(shù)據(jù)模型的過程屬于A)需求分析階段B)概念設(shè)計階段C)邏輯設(shè)計階段D)物理設(shè)計階段D8√12108年4月全國計算機等級考試二級筆試試卷一、單選題D122(9)有三個關(guān)系R、S和T如下：

由關(guān)系R和S通過運算得到關(guān)系T，則所使用的運算為A．并B．自然連接C．笛卡爾積D.交D9√122(9)有三個關(guān)系R、S和T如下：D9√123