全國(guó)計(jì)算機(jī)二級(jí)考試公共基礎(chǔ)知識(shí)整合

計(jì)算機(jī)二級(jí)考試公共根底學(xué)問(wèn)計(jì)算機(jī)二級(jí)考試公共根底學(xué)問(wèn)第一章數(shù)據(jù)構(gòu)造與算法重點(diǎn)學(xué)習(xí)。具體重點(diǎn)學(xué)習(xí)學(xué)問(wèn)點(diǎn)：算法的概念、算法時(shí)間簡(jiǎn)單度及空間簡(jiǎn)單度的概念數(shù)據(jù)構(gòu)造的定義、數(shù)據(jù)規(guī)律構(gòu)造及物理構(gòu)造的定義棧的定義及其運(yùn)算、線(xiàn)性鏈表的存儲(chǔ)方式樹(shù)與二叉樹(shù)的概念、二叉樹(shù)的根本性質(zhì)、完全二叉樹(shù)的概念、二叉樹(shù)的遍歷二分查找法冒泡排序法算法考點(diǎn)1算法的根本概念考試鏈接：考點(diǎn)130%，主要是以填空題的形式消滅，分值2分，此考點(diǎn)為識(shí)記內(nèi)容，讀者還應(yīng)當(dāng)了解算法中對(duì)數(shù)據(jù)的根本運(yùn)算。計(jì)算機(jī)解題的過(guò)程實(shí)際上是在實(shí)施某種算法，這種算法稱(chēng)為計(jì)算機(jī)算法。算法的根本特征：可行性、確定性、有窮性、擁有足夠的情報(bào)。算法的根本要素：算法中對(duì)數(shù)據(jù)的運(yùn)算和操作。在一般的計(jì)算機(jī)系統(tǒng)中，根本的運(yùn)算和操作有以下4類(lèi)：算術(shù)運(yùn)算、規(guī)律運(yùn)算、關(guān)系運(yùn)算和數(shù)據(jù)傳輸。算法的掌握構(gòu)造：算法中各操作之間的執(zhí)行挨次稱(chēng)為算法的掌握構(gòu)造。算法一般都可以用挨次、選擇、循環(huán)3種根本掌握構(gòu)造組合而成?？键c(diǎn)2算法簡(jiǎn)單度考試鏈接：考點(diǎn)270%，主要是以選擇2分，此考點(diǎn)為重點(diǎn)識(shí)記內(nèi)容，讀者還應(yīng)當(dāng)識(shí)記算法時(shí)間簡(jiǎn)單度及空間簡(jiǎn)單度的概念。算法的時(shí)間簡(jiǎn)單度算法的時(shí)間簡(jiǎn)單度是指執(zhí)行算法所需要的計(jì)算工作量。同一個(gè)算法用不同的語(yǔ)言實(shí)現(xiàn)，或者用不同的編譯程序進(jìn)展編譯，或者在不同〔通常用整數(shù)表示，它是問(wèn)題規(guī)模的函數(shù)。即算法的工作量=f〔n〕算法的空間簡(jiǎn)單度算法的空間簡(jiǎn)單度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。一個(gè)算法所占用的存儲(chǔ)空間包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的疑難解答：算法的工作量用什么來(lái)計(jì)算？算法的工作量用算法所執(zhí)行的根本運(yùn)算次數(shù)來(lái)計(jì)算，而算法所執(zhí)行的根本運(yùn)算次數(shù)是問(wèn)題=f〔是問(wèn)題的規(guī)模。數(shù)據(jù)構(gòu)造的根本概念考點(diǎn)3數(shù)據(jù)構(gòu)造的定義考試鏈接：考點(diǎn)370%，主要是以選擇2分，此考點(diǎn)為識(shí)記內(nèi)容，讀者還應(yīng)當(dāng)識(shí)記數(shù)據(jù)的規(guī)律構(gòu)造和存儲(chǔ)構(gòu)造的概念。數(shù)據(jù)構(gòu)造作為計(jì)算機(jī)的一門(mén)學(xué)科，主要爭(zhēng)論和爭(zhēng)論以下三個(gè)方面：數(shù)據(jù)集合中個(gè)數(shù)據(jù)元素之間所固有的規(guī)律關(guān)系，即數(shù)據(jù)的規(guī)律構(gòu)造；存儲(chǔ)構(gòu)造；對(duì)各種數(shù)據(jù)構(gòu)造進(jìn)展的運(yùn)算。并被計(jì)算機(jī)程序處理的符號(hào)的總稱(chēng)。處理。數(shù)據(jù)對(duì)象：是性質(zhì)一樣的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)的規(guī)律構(gòu)造是對(duì)數(shù)據(jù)元素之間的規(guī)律關(guān)系的描述，它可以用一個(gè)數(shù)據(jù)元素的集合和定義在此集合中的假設(shè)干關(guān)系來(lái)表示。數(shù)據(jù)的規(guī)律構(gòu)造有兩個(gè)要素：一是數(shù)D通常記為R。一個(gè)數(shù)據(jù)構(gòu)造可以表示成B=〔D，R〕其中B表示數(shù)據(jù)構(gòu)造。為了反映D中各數(shù)據(jù)元素之間的前后件關(guān)系，一般用二元組來(lái)表示。〔也稱(chēng)數(shù)據(jù)的物理構(gòu)造。由于數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間中的位置關(guān)系可能與規(guī)律關(guān)系不同，因此，為〔即前后件關(guān)系前后件關(guān)系的信息。一種數(shù)據(jù)的規(guī)律構(gòu)造依據(jù)需要可以表示成多種存儲(chǔ)構(gòu)造，常用的存儲(chǔ)構(gòu)造有挨次因此，在進(jìn)展數(shù)據(jù)處理時(shí)，選擇適宜的存儲(chǔ)構(gòu)造是很重要的?？键c(diǎn)4線(xiàn)性構(gòu)造與非線(xiàn)性構(gòu)造考試鏈接：考點(diǎn)430%，主要是以填空題消滅的形式消滅，分值2分，此考點(diǎn)為識(shí)記內(nèi)容。依據(jù)數(shù)據(jù)構(gòu)造中各數(shù)據(jù)元素之間前后件關(guān)系的簡(jiǎn)單程度，一般將數(shù)據(jù)構(gòu)造分為兩大類(lèi)型：線(xiàn)性構(gòu)造與非線(xiàn)性構(gòu)造。假設(shè)一個(gè)非空的數(shù)據(jù)構(gòu)造滿(mǎn)足以下兩個(gè)條件：有且只有一個(gè)根結(jié)點(diǎn)；每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。則稱(chēng)該數(shù)據(jù)構(gòu)造為線(xiàn)性構(gòu)造。線(xiàn)性構(gòu)造又稱(chēng)線(xiàn)性表。在一個(gè)線(xiàn)性構(gòu)造中插入或非線(xiàn)性構(gòu)造。疑難解答：空的數(shù)據(jù)構(gòu)造是線(xiàn)性構(gòu)造還是非線(xiàn)性構(gòu)造？一個(gè)空的數(shù)據(jù)構(gòu)造到底是屬于線(xiàn)性構(gòu)造還是屬于非線(xiàn)性構(gòu)造，這要依據(jù)具體狀況來(lái)確定。假設(shè)對(duì)該數(shù)據(jù)構(gòu)造的算法是按線(xiàn)性構(gòu)造的規(guī)章來(lái)處理的，則屬于線(xiàn)性構(gòu)造；否則屬于非線(xiàn)性構(gòu)造。棧及線(xiàn)性鏈表考點(diǎn)5棧及其根本運(yùn)算考試鏈接：考點(diǎn)5在筆試考試中，是一個(gè)必考的內(nèi)，100%，主要是以選擇的2分，此考點(diǎn)為重點(diǎn)把握內(nèi)容，讀者應(yīng)當(dāng)把握棧的運(yùn)棧的根本概念棧是限定只在一端進(jìn)展插入與刪除的線(xiàn)性表，通常稱(chēng)插入、刪除的這一端為棧被刪除的元素。棧是依據(jù)“先進(jìn)后出“或“后進(jìn)先出“的原則組織數(shù)據(jù)的。棧的挨次存儲(chǔ)及其運(yùn)算S〔1∶m〕作為棧的挨次存儲(chǔ)空間，其中m為最大容量。在棧的挨次存儲(chǔ)空間S〔1∶m〕中，S〔bottom〕為棧底元素，S〔top〕為棧頂元素。top=0表示?？?；top=m表示棧滿(mǎn)。棧的根本運(yùn)算有三種：入棧、退棧與讀棧頂元素。入棧運(yùn)算：入棧運(yùn)算是指在棧頂位置插入一個(gè)元素。首先將棧頂指針加一〔top加1儲(chǔ)空間的最終一個(gè)位置時(shí)，說(shuō)明?？臻g已滿(mǎn)，不行能再進(jìn)展入棧操作。這種狀況稱(chēng)為?！吧弦纭板e(cuò)誤。退棧運(yùn)算：退棧是指取出棧頂元素并賦給一個(gè)指定的變量。首先將棧頂元〔棧頂指針指向的元素〔即top減1當(dāng)棧頂指針為0時(shí)，說(shuō)明?？?，不行進(jìn)展退棧操作。這種狀況稱(chēng)為棧的“下溢“錯(cuò)誤。0時(shí)，說(shuō)明?？眨x不到棧頂元素。小技巧：棧是依據(jù)“先進(jìn)后出“或“后進(jìn)先出“的原則組織數(shù)據(jù)，但是出棧方式有多種選擇，在考題中常常考察各種不同的出棧方式?？键c(diǎn)6線(xiàn)性鏈表的根本概念考試鏈接：考點(diǎn)630%，主要是以選擇的形式消滅，分值2分，此考點(diǎn)為識(shí)記內(nèi)容。重點(diǎn)識(shí)記結(jié)點(diǎn)的組成。一個(gè)或后一個(gè)結(jié)點(diǎn)〔即前件或后件。鏈?zhǔn)酱鎯?chǔ)方式既可用于表示線(xiàn)性構(gòu)造，也可用于表示非線(xiàn)性構(gòu)造。線(xiàn)性鏈表線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造稱(chēng)為線(xiàn)性鏈表。在某些應(yīng)用中，對(duì)線(xiàn)性鏈表中的每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針，一個(gè)稱(chēng)為左指針，用鏈表。帶鏈的?？臻g中全部空閑的存儲(chǔ)結(jié)點(diǎn)，這種帶鏈的棧稱(chēng)為可利用棧。疑難解答：在鏈?zhǔn)綐?gòu)造中，存儲(chǔ)空間位置關(guān)系與規(guī)律關(guān)系是什么？在鏈?zhǔn)酱鎯?chǔ)構(gòu)造中，存儲(chǔ)數(shù)據(jù)構(gòu)造的存儲(chǔ)空間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)挨次與數(shù)據(jù)元素之間的規(guī)律關(guān)系可以不全都，而數(shù)據(jù)元素之間的規(guī)律關(guān)系是由指針域來(lái)確定的。樹(shù)與二叉樹(shù)考點(diǎn)7樹(shù)與二叉樹(shù)及其根本性質(zhì)考試鏈接：考點(diǎn)7在筆試考試中，是一個(gè)必考的內(nèi)容，在筆試考試中消滅的幾率00%，主要是以選擇的形式消滅，有時(shí)也有消滅在填空題中，分值2分，此考點(diǎn)為重點(diǎn)把握內(nèi)容。重點(diǎn)識(shí)記樹(shù)及二叉樹(shù)的性質(zhì)。誤區(qū)警示：滿(mǎn)二叉樹(shù)也是完全二叉樹(shù)，而完全二叉樹(shù)一般不是滿(mǎn)二叉樹(shù)。應(yīng)當(dāng)留意二者的區(qū)分。1、樹(shù)的根本概念樹(shù)(tree〕是一種簡(jiǎn)潔的非線(xiàn)性構(gòu)造。在樹(shù)構(gòu)造中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，后件，它們稱(chēng)為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒(méi)有后件的結(jié)點(diǎn)稱(chēng)為葉子結(jié)點(diǎn)。0。在樹(shù)中，全部結(jié)點(diǎn)中的最大的度稱(chēng)為樹(shù)的度。2、二叉樹(shù)及其根本性質(zhì)二叉樹(shù)的定義二叉樹(shù)是一種很有用的非線(xiàn)性構(gòu)造，具有以下兩個(gè)特點(diǎn)：①非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)；②每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)，且分別稱(chēng)為該結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)。由以上特點(diǎn)可以看出，在二叉樹(shù)中，每一個(gè)結(jié)點(diǎn)的度最大為2，即全部子樹(shù)〔左二叉樹(shù)中的每個(gè)結(jié)點(diǎn)的子樹(shù)被明顯地分為左子樹(shù)和右子樹(shù)。在二叉樹(shù)中，一個(gè)結(jié)點(diǎn)可以只有左子樹(shù)而沒(méi)有右子樹(shù)，也可以只有右子樹(shù)而沒(méi)有左子樹(shù)。當(dāng)一個(gè)結(jié)點(diǎn)既沒(méi)有左子樹(shù)也沒(méi)有右子樹(shù)時(shí)，該結(jié)點(diǎn)即為葉子結(jié)點(diǎn)。二叉樹(shù)的根本性質(zhì)二叉樹(shù)具有以下幾共性質(zhì)：k層上，最多有2k-1〔k≥1〕個(gè)結(jié)點(diǎn)；性質(zhì)2：深度為m的二叉樹(shù)最多有2m-1個(gè)結(jié)點(diǎn)；多一個(gè)。［log2n］+1，其中［log2n］表示取log2n的整數(shù)局部。小技巧：在二叉樹(shù)的遍歷中，無(wú)論是前序遍歷，中序遍歷還是后序遍歷，二叉樹(shù)的葉子結(jié)點(diǎn)的先后挨次都是不變的。3、滿(mǎn)二叉樹(shù)與完全二叉樹(shù)滿(mǎn)二叉樹(shù)是指這樣的一種二叉樹(shù)：除最終一層外，每一層上的全部結(jié)點(diǎn)都有兩k層上有2k-1個(gè)結(jié)點(diǎn)，且深度為m的滿(mǎn)二叉樹(shù)有2m－1個(gè)結(jié)點(diǎn)。值；在最終一層上只缺少右邊的假設(shè)干結(jié)點(diǎn)。對(duì)于完全二叉樹(shù)來(lái)說(shuō)，葉子結(jié)點(diǎn)只可能在層次最大的兩層上消滅：對(duì)于任何一層次或?yàn)閜，或?yàn)閜+1。完全二叉樹(shù)具有以下兩共性質(zhì)：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為［log2n］+1。性質(zhì)6:設(shè)完全二叉樹(shù)共有n個(gè)結(jié)點(diǎn)。假設(shè)從根結(jié)點(diǎn)開(kāi)頭，按層次〔每一層從左到k〔k=1，2，……，n〕的結(jié)點(diǎn)有以下結(jié)論：①假設(shè)k=1，則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒(méi)有父結(jié)點(diǎn)；假設(shè)k>1，則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為IN〔k/2。②假設(shè)2k≤n，則編號(hào)為k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為2k〔顯然也沒(méi)有右子結(jié)點(diǎn)。③假設(shè)2k+1≤n，則編號(hào)為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為2k+1；否則該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn)?？键c(diǎn)8二叉樹(shù)的遍歷考試鏈接：考點(diǎn)830%，分值為2由兩種遍歷的結(jié)果推導(dǎo)另一種遍歷的結(jié)果。在遍歷二叉樹(shù)的過(guò)程中，一般先遍歷左子樹(shù)，再遍歷右子樹(shù)。在先左后右的原序遍歷。遍歷左、右子樹(shù)時(shí)，仍舊先訪(fǎng)問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最終遍歷右子樹(shù)。遍歷左、右子樹(shù)時(shí)，仍舊先遍歷左子樹(shù)，然后訪(fǎng)問(wèn)根結(jié)點(diǎn)，最終遍歷右子樹(shù)。遍歷左、右子樹(shù)時(shí)，仍舊先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最終訪(fǎng)問(wèn)根結(jié)點(diǎn)。疑難解答：樹(shù)與二叉樹(shù)的不同之處是什么？在二叉樹(shù)中，每一個(gè)結(jié)點(diǎn)的度最大為2，即全部子樹(shù)〔左子樹(shù)或右子樹(shù)〕也均為二叉樹(shù)，而樹(shù)構(gòu)造中的每一個(gè)結(jié)點(diǎn)的度可以是任意的。查找技術(shù)考點(diǎn)9挨次查找考試鏈接：考點(diǎn)930%2分，讀者應(yīng)當(dāng)具體把握挨次查找的算法。查找是指在一個(gè)給定的數(shù)據(jù)構(gòu)造中查找某個(gè)指定的元素。從線(xiàn)性表的第一個(gè)元在以下兩種狀況下也只能承受挨次查找：挨次查找。即使是有序線(xiàn)性表，假設(shè)承受鏈?zhǔn)酱鎯?chǔ)構(gòu)造，也只能用挨次查找。考點(diǎn)10二分法查找考試鏈接：考點(diǎn)1030%2次數(shù)，讀者應(yīng)當(dāng)具體把握二分查找法的算法。二分法只適用于挨次存儲(chǔ)的，按非遞減排列的有序表，其方法如下：設(shè)有序線(xiàn)性表的長(zhǎng)度為n，被查找的元素為i，將i與線(xiàn)性表的中間項(xiàng)進(jìn)展比較；假設(shè)i與中間項(xiàng)的值相等，則查找成功；假設(shè)i小于中間項(xiàng)，則在線(xiàn)性表的前半局部以一樣的方法查找；假設(shè)i大于中間項(xiàng)，則在線(xiàn)性表的后半局部以一樣的方法查找。疑難解答：二分查找法適用于哪種狀況？二分查找法只適用于挨次存儲(chǔ)的有序表。在此所說(shuō)的有序表是指線(xiàn)性表中的元素按值非遞減排列〔即從小到大，但允許相鄰元素值相等。這個(gè)過(guò)程始終進(jìn)展到查找成功或子表長(zhǎng)度為0為止。log2n次。排序技術(shù)考點(diǎn)11交換類(lèi)排序法:考點(diǎn)110%，2嫻熟把握幾種排序算法的根本過(guò)程。冒泡排序法和快速排序法都屬于交換類(lèi)排序法。冒泡排序法首先，從表頭開(kāi)頭往后掃描線(xiàn)性表，逐次比較相鄰兩個(gè)元素的大小，假設(shè)前面的最終最大者到了線(xiàn)性表的最終。然后，從后到前掃描剩下的線(xiàn)性表，逐次比較相鄰兩個(gè)元素的大小，假設(shè)后面的最終最小者到了線(xiàn)性表的最前面。在最壞的狀況下，冒泡排序需要比較次數(shù)為n〔n－1〕/2?？焖倥判蚍ā惨话闳〉谝粋€(gè)元素通過(guò)一趟排序，將待排元素分為左右兩個(gè)子序列，左子序列元素的排序碼均小于或等于基準(zhǔn)元素的排序碼，右子序列的排序碼則大于基準(zhǔn)元素的排序碼，然后分別對(duì)兩個(gè)子序列連續(xù)進(jìn)展排序，直至整個(gè)序列有序。疑難解答：冒泡排序和快速排序的平均執(zhí)行時(shí)間分別是多少？On〔nlo2n。例題詳解一、選擇題【例1】算法的時(shí)間簡(jiǎn)單度取決于 考點(diǎn)2〕A〕問(wèn)題的規(guī)模 B〕待處理的數(shù)據(jù)的初態(tài)C〕問(wèn)題的難度 D〕A〕和B〕解析：算法的時(shí)間簡(jiǎn)單度不僅與問(wèn)題的規(guī)模有關(guān)，在同一個(gè)問(wèn)題規(guī)模下，而且率有關(guān)。D〕【例2】在數(shù)據(jù)構(gòu)造中，從規(guī)律上可以把數(shù)據(jù)構(gòu)造分成 A〕內(nèi)部構(gòu)造和外部構(gòu)造 B〕線(xiàn)性構(gòu)造和非線(xiàn)性構(gòu)造C〕緊湊構(gòu)造和非緊湊構(gòu)造 D〕動(dòng)態(tài)構(gòu)造和靜態(tài)構(gòu)造解析：規(guī)律構(gòu)造反映數(shù)據(jù)元素之間的規(guī)律關(guān)系，線(xiàn)性構(gòu)造表示數(shù)據(jù)元素之間為?！纠?】以下 不是棧的根本運(yùn)算〔考點(diǎn)5〕A〕推斷棧是否為素空 棧置為空棧C〕刪除棧頂元素 刪除棧底元素解析：棧的根本運(yùn)算有：入棧，出?！矂h除棧頂元素是否為空或滿(mǎn)、提取棧頂元素等，對(duì)棧的操作都是在棧頂進(jìn)展的。D〕【例4】鏈表不具備的特點(diǎn)是 〔考點(diǎn)6〕〕可隨機(jī)訪(fǎng)問(wèn)任意一個(gè)結(jié)點(diǎn) 插入和刪除不需要移動(dòng)任元素C〕不必事先估量存儲(chǔ)空間 D〕所需空間與其長(zhǎng)度成正比逐一查找每個(gè)結(jié)點(diǎn)。所以答案為答案：A〕序遍歷序列是DACBE，中序遍歷序列是DEBAC，則它的前序遍歷序列是 〔考點(diǎn)8〕A〕ACBED B〕DEABCC〕DECAB D〕EDBAC法，不難得出前序遍歷序列是EDBA。所以答案為。D〕【例6】設(shè)有一個(gè)已按各元素的值排好序的線(xiàn)性表〔長(zhǎng)度大2，對(duì)給定的分別用挨次查找法和二分查找法查找一個(gè)與k相等的元素，比較的次數(shù)分別是s和b，在查找不成功的狀況下，s和b的關(guān)系是 〔考點(diǎn)9〕A〕s=b B〕s>b C〕s<b D〕s≥bn+1。二分查找［log2n］+1。當(dāng)n≥2時(shí)，明顯n+1>［log2n］+1。答案：B〕】在快速排序過(guò)程中，每次劃分，將被劃分的表〔或子表〕分成左、右兩個(gè)子表，考慮這兩個(gè)子表，以下結(jié)論肯定正確的選項(xiàng)是 〔考點(diǎn)11〕A〕左、右兩個(gè)子表都已各自排好序C〕左邊子表的長(zhǎng)度小于右邊子表的長(zhǎng)度D〕左、右兩個(gè)子表中元素的平均值相等解析：快速排序根本思想是：任取待排序表中的某個(gè)元素作為基準(zhǔn)〔一般取第一個(gè)元素別對(duì)兩個(gè)子表連續(xù)進(jìn)展排序，直至整個(gè)表有序。答案：B〕【例1】問(wèn)題處理方案的正確而完整的描述稱(chēng)為 〔考點(diǎn)1〕答案：算法【例2】一個(gè)空的數(shù)據(jù)構(gòu)造是按線(xiàn)性構(gòu)造處理的，則屬于 〔考點(diǎn)4〕個(gè)空的數(shù)據(jù)構(gòu)造是線(xiàn)性構(gòu)造或是非線(xiàn)性構(gòu)造，要依據(jù)具體狀況而定。構(gòu)造。答案：線(xiàn)性構(gòu)造１、１，則Ｔ中葉子結(jié)點(diǎn)的個(gè)數(shù)為 〔考點(diǎn)7〕加１。16。葉子結(jié)點(diǎn)數(shù)目等于樹(shù)結(jié)點(diǎn)總數(shù)減去度不為０的結(jié)點(diǎn)數(shù)之和，即16－〔４＋２＋１＋１〕＝８。答案：8【例4】二分法查找的存儲(chǔ)構(gòu)造僅限于 且是有序的〔考點(diǎn)10〕解析：二分查找，也稱(chēng)折半查找，它是一種高效率的查找方法。但二分查找有(升序或降序均可。答案：挨次存儲(chǔ)構(gòu)造其次章程序設(shè)計(jì)根底具體重點(diǎn)學(xué)習(xí)學(xué)問(wèn)點(diǎn)：構(gòu)造化程序設(shè)計(jì)方法的四個(gè)原則對(duì)象、類(lèi)、消息、繼承的概念、類(lèi)與實(shí)例的區(qū)分構(gòu)造化程序設(shè)計(jì)考點(diǎn)1構(gòu)造化程序設(shè)計(jì)的原則考試鏈接：考點(diǎn)130%，主要是以選擇題的形式消滅2記內(nèi)容，讀者應(yīng)當(dāng)識(shí)記構(gòu)造化程序設(shè)計(jì)方法的四個(gè)主要原則。20世紀(jì)70年月提出了“構(gòu)造化程序設(shè)計(jì)“的思想和方法。構(gòu)造化程序設(shè)計(jì)方法引入了工程化思想和構(gòu)造化思想，使大型軟件的開(kāi)發(fā)和編程得到了極大的改善。構(gòu)造goto語(yǔ)句。疑難解答：如何進(jìn)展自頂向下設(shè)計(jì)方法？程序設(shè)計(jì)時(shí)，應(yīng)先考慮總體，后考慮細(xì)節(jié)；先考慮全局目標(biāo)，后考慮局部目標(biāo)；不要一開(kāi)始就過(guò)多追求眾多的細(xì)節(jié)，先從最上層總目標(biāo)開(kāi)頭設(shè)計(jì)，逐步使問(wèn)題具體化。面對(duì)對(duì)象的程序設(shè)計(jì)考點(diǎn)2面對(duì)對(duì)象方法的根本概念考試鏈接：考點(diǎn)270%，主要是以填空2分，此考點(diǎn)為重點(diǎn)識(shí)記內(nèi)容，讀者應(yīng)當(dāng)識(shí)記幾個(gè)根本要素的定義、對(duì)象的特征以及消息、繼承、類(lèi)的定義。誤區(qū)警示：實(shí)例“這個(gè)術(shù)語(yǔ)時(shí)，必需是指一個(gè)具體的對(duì)象。面對(duì)對(duì)象方法涵蓋對(duì)象及對(duì)象屬性與方法、類(lèi)、繼承、多態(tài)性幾個(gè)根本要素。對(duì)象通常把對(duì)對(duì)象的操作也稱(chēng)為方法或效勞。作來(lái)轉(zhuǎn)變。屬性值應(yīng)當(dāng)指的是純粹的數(shù)據(jù)值，而不能指對(duì)象。類(lèi)和實(shí)例對(duì)象的性質(zhì)，而一個(gè)對(duì)象則是其對(duì)應(yīng)類(lèi)的一個(gè)實(shí)例。組合法操作。消息它統(tǒng)一了數(shù)據(jù)流和掌握流?！蚕⒚澈土銈€(gè)或多個(gè)參數(shù)。繼承級(jí)為樹(shù)形構(gòu)造。多重繼承是指，一個(gè)類(lèi)允許有多個(gè)父類(lèi)。多態(tài)性全不同的行動(dòng)，該現(xiàn)象稱(chēng)為多態(tài)性。疑難解答：能舉一下現(xiàn)實(shí)中的對(duì)象及其屬性和操作嗎？一輛汽車(chē)是一個(gè)對(duì)象，它包含了汽車(chē)的屬性〔如顏色、型號(hào)等〕及其操作〔如啟動(dòng)、剎車(chē)等。一個(gè)窗口是對(duì)象，它包含了窗口的屬性〔如大小、顏色等〕及其操作〔如翻開(kāi)、關(guān)閉等。例題詳解一、選擇題【例1】構(gòu)造化程序設(shè)計(jì)方法提出于 〔考點(diǎn)1〕A〕20世紀(jì)50年月 世紀(jì)60年月C〕20世紀(jì)70年月 世紀(jì)80年月和編程得到了極大的改善。答案：C〕【例2】構(gòu)造化程序設(shè)計(jì)方法的主要原則有以下4項(xiàng)，不正確的選項(xiàng)是 點(diǎn)1〕A〕自下向上 B〕逐步求精C〕模塊化 語(yǔ)句解析：構(gòu)造化程序設(shè)計(jì)方法的主要原則為：標(biāo)。逐步求精：對(duì)簡(jiǎn)單問(wèn)題，應(yīng)設(shè)計(jì)一些子目標(biāo)作過(guò)渡，逐步細(xì)化。目標(biāo)，把每個(gè)小目標(biāo)稱(chēng)為一個(gè)模塊。語(yǔ)句。答案：A〕【例3】面對(duì)對(duì)象的開(kāi)發(fā)方法中，類(lèi)與對(duì)象的關(guān)系是 〔考點(diǎn)2〕A〕抽象與具體 與抽象C〕局部與整體 整體與局部解析：現(xiàn)實(shí)世界中的很多事物都具有相像的性質(zhì)，把具有相像的屬性和操作的例。所以此題正確答案為A〕項(xiàng)。A〕二、填空題】在面對(duì)對(duì)象方法中，使用已經(jīng)存在的類(lèi)定義作為根底建立的類(lèi)定義，這樣的技術(shù)叫做 〔考點(diǎn)2〕解析：繼承是面對(duì)對(duì)象方法的一個(gè)主要特征。繼承是使用已有的類(lèi)定義作為根底引用。答案：繼承【例2】對(duì)象的根本特點(diǎn)包括 多態(tài)性、封裝性和模塊獨(dú)立性好等5個(gè)特點(diǎn)〔考點(diǎn)2〕解析：對(duì)象具有如下的根本特點(diǎn)：標(biāo)識(shí)惟一性。對(duì)象是可區(qū)分的，并且由對(duì)象的內(nèi)在本質(zhì)來(lái)區(qū)分；分類(lèi)性。可以將具有一樣屬性和操作的對(duì)象抽象成類(lèi)；多態(tài)性。同一個(gè)操作可以是不同對(duì)象的行為；的算法；一體。答案：標(biāo)識(shí)惟一性可能導(dǎo)致完全不同的行為，這種現(xiàn)象稱(chēng)為 〔考點(diǎn)2〕導(dǎo)致完全不同的行為，該現(xiàn)象稱(chēng)為多態(tài)性。答案：多態(tài)性第三章軟件工程根底應(yīng)對(duì)此局部進(jìn)展重點(diǎn)學(xué)習(xí)。具體重點(diǎn)學(xué)習(xí)學(xué)問(wèn)點(diǎn)：軟件的概念、軟件生命周期的概念及各階段所包含的活動(dòng)的工具軟件測(cè)試的目的、軟件測(cè)試的4個(gè)步驟、軟件調(diào)試的任務(wù)軟件工程根本概念考點(diǎn)1軟件定義與軟件特點(diǎn)考試鏈接：考點(diǎn)170%，主要是以選擇題的形式消滅，分值為2分，此考點(diǎn)為識(shí)記內(nèi)容，讀者應(yīng)當(dāng)識(shí)記軟件的定義，特點(diǎn)及其分類(lèi)。軟件指的是計(jì)算機(jī)系統(tǒng)中與硬件相互依存的另一局部，包括程序、數(shù)據(jù)和相關(guān)是與程序的開(kāi)發(fā)、維護(hù)和使用有關(guān)的圖文資料?？梢?jiàn)，軟件由兩局部組成：機(jī)器可執(zhí)行的程序和數(shù)據(jù)；軟件的特點(diǎn)：軟件是規(guī)律實(shí)體，而不是物理實(shí)體，具有抽象性；沒(méi)有明顯的制作過(guò)程，可進(jìn)展大量的復(fù)制；使用期間不存在磨損、老化問(wèn)題；軟件的開(kāi)發(fā)、運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依靠性；軟件簡(jiǎn)單性高，本錢(qián)昂貴；軟件開(kāi)發(fā)涉及諸多社會(huì)因素?！不蚬ぞ哕浖?。小提示：應(yīng)用軟件是為解決特定領(lǐng)域的應(yīng)用而開(kāi)發(fā)的軟件；系統(tǒng)軟件是計(jì)算機(jī)治理自幫助用戶(hù)開(kāi)發(fā)軟件的工具性軟件?？键c(diǎn)2軟件工程過(guò)程與軟件生命周期考試鏈接：考點(diǎn)2在筆試考試中，在筆試考試中消滅的幾率30%，主要是以選擇題的形式消滅，分值2分，此考點(diǎn)為識(shí)記內(nèi)容，讀者應(yīng)當(dāng)識(shí)記軟件生命周軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停頓使用退役的過(guò)程稱(chēng)為軟件生命周期。動(dòng)，如圖3－1所示。計(jì)算機(jī)二級(jí)考試公共根底學(xué)問(wèn)計(jì)算機(jī)二級(jí)考試公共根底學(xué)問(wèn)圖3－1軟件生命周期3個(gè)階段。軟件實(shí)施、軟件測(cè)試及運(yùn)行與維護(hù)。構(gòu)造化設(shè)計(jì)方法考點(diǎn)3軟件設(shè)計(jì)的根本概念考試鏈接：考點(diǎn)370%，主要是以選擇題的形式消滅，分值為2分，此考點(diǎn)為重點(diǎn)把握內(nèi)容，讀者應(yīng)當(dāng)識(shí)記模塊獨(dú)立性中的耦合性和內(nèi)聚性。誤區(qū)警示：在程序構(gòu)造中，各模塊的內(nèi)聚性越強(qiáng)，則耦合性越弱。軟件設(shè)計(jì)應(yīng)盡量做到高內(nèi)聚，低耦合，即減弱模塊之間的耦合性和提高模塊內(nèi)的內(nèi)聚性，有利于提高模塊的獨(dú)立性。軟件設(shè)計(jì)的根底計(jì)。構(gòu)造設(shè)計(jì)定義軟件系統(tǒng)各主要部件之間的關(guān)系；數(shù)據(jù)設(shè)計(jì)將分析時(shí)創(chuàng)立的模型轉(zhuǎn)化為數(shù)據(jù)構(gòu)造的定義；接口設(shè)計(jì)是描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)之間以及軟件與人之間如何通信；過(guò)程設(shè)計(jì)則是把系統(tǒng)構(gòu)造部件轉(zhuǎn)換為軟件的過(guò)程性描述。從工程治理角度來(lái)看，軟件設(shè)計(jì)分兩步完成：概要設(shè)計(jì)和具體設(shè)計(jì)?；驍?shù)據(jù)庫(kù)模式；計(jì)算機(jī)二級(jí)考試公共根底學(xué)問(wèn)計(jì)算機(jī)二級(jí)考試公共根底學(xué)問(wèn)和數(shù)據(jù)構(gòu)造的細(xì)節(jié)。軟件設(shè)計(jì)的根本原理的層次從概要設(shè)計(jì)到具體設(shè)計(jì)逐步降低。化是指解決一個(gè)簡(jiǎn)單問(wèn)題時(shí)自頂向下逐層把軟件系統(tǒng)劃分成假設(shè)干模塊的過(guò)程。〔過(guò)程或數(shù)據(jù)不需要這些信息的其他模塊來(lái)說(shuō)是不能訪(fǎng)問(wèn)的。并且與其他模塊的聯(lián)系最少且接口簡(jiǎn)潔。模塊的獨(dú)立程度是評(píng)價(jià)設(shè)計(jì)好壞的重要度量標(biāo)準(zhǔn)。衡量軟件的模塊獨(dú)立性使用耦合性和內(nèi)聚性?xún)蓚€(gè)定性的度量標(biāo)準(zhǔn)。內(nèi)聚性是信息隱蔽和局部化概念的自然擴(kuò)展。一個(gè)模塊的內(nèi)聚性越強(qiáng)則該模塊的模塊獨(dú)立性越強(qiáng)。一個(gè)模塊與其他模塊的耦合性越強(qiáng)則該模塊的模塊獨(dú)立性越弱。內(nèi)聚性是度量一個(gè)模塊功能強(qiáng)度的一個(gè)相對(duì)指標(biāo)。內(nèi)聚是從功能角度來(lái)衡量模功能內(nèi)聚。耦合性是模塊之間相互連接的嚴(yán)密程度的度量。耦合性取決于各個(gè)模塊之間接數(shù)據(jù)耦合、非直接耦合。應(yīng)盡量做到高內(nèi)聚，低耦合，即減弱模塊之間的耦合性和提高模塊內(nèi)的內(nèi)聚性，有利于提高模塊的獨(dú)立性。小提示：上面僅是對(duì)耦合機(jī)制進(jìn)展的一個(gè)分類(lèi)?？梢?jiàn)一個(gè)模塊與其他模塊的耦合性越強(qiáng)則該模塊獨(dú)立性越弱。原則上講，模塊化設(shè)計(jì)總是期望模塊之間的耦合表現(xiàn)為非直接耦合方式。但是，由于問(wèn)題所固有的簡(jiǎn)單性和構(gòu)造化設(shè)計(jì)的原則，非直接耦合是不存在的?？键c(diǎn)4具體設(shè)計(jì)考試鏈接：考點(diǎn)4在筆試考試中，在筆試考試中消滅的幾率30%，主要是以選擇題的形式消滅，分值2分，此考點(diǎn)為識(shí)記內(nèi)容，讀者應(yīng)當(dāng)識(shí)記過(guò)程設(shè)計(jì)包括哪些常用工具。具體設(shè)計(jì)的任務(wù)是為軟件構(gòu)造圖中的每個(gè)模塊確定實(shí)現(xiàn)算法和局部數(shù)據(jù)構(gòu)造，具體過(guò)程設(shè)計(jì)的常用工具有：表格工具：判定表。語(yǔ)言工具：PDL〔偽碼。5種掌握構(gòu)造：挨次型、選擇型、先推斷重復(fù)型、后推斷重復(fù)型和多分支選擇型。重復(fù)型。型和UNTIL重復(fù)型。過(guò)程設(shè)計(jì)語(yǔ)言〔PDL〕也稱(chēng)為構(gòu)造化的語(yǔ)言和偽碼，它是一種混合語(yǔ)言，承受英語(yǔ)的詞匯和構(gòu)造化程序設(shè)計(jì)語(yǔ)言，類(lèi)似編程語(yǔ)言。PDL可以由編程語(yǔ)言轉(zhuǎn)換得到，也可以是特地為過(guò)程描述而設(shè)計(jì)的。疑難解答：程序流程圖，N-S圖，PAD圖的掌握構(gòu)造的異同點(diǎn)是什么？一樣點(diǎn)是三種圖都有挨次構(gòu)造，選擇構(gòu)造和多分支選擇，并且N-S圖和PAD圖還有一樣的WHILE重復(fù)型、UNTILWHILE重復(fù)型、UNTIL重復(fù)型而有后推斷重復(fù)型和先推斷重復(fù)型。軟件測(cè)試考點(diǎn)5軟件測(cè)試的目的考試鏈接：考點(diǎn)50%，主要是以選擇2分，此考點(diǎn)為理解內(nèi)容，讀者應(yīng)當(dāng)理解測(cè)試是為了覺(jué)察錯(cuò)誤。軟件測(cè)試是在軟件投入運(yùn)行前對(duì)軟件需求、設(shè)計(jì)、編碼的最終審核。其工作量、40%以上，而且具有較高的組織治理和技術(shù)難度。軟件測(cè)試是為了覺(jué)察錯(cuò)誤而執(zhí)行程序的過(guò)程；一個(gè)好的測(cè)試用例是能夠覺(jué)察至今尚未覺(jué)察的錯(cuò)誤的用例；一個(gè)成功的測(cè)試是覺(jué)察了至今尚未覺(jué)察的錯(cuò)誤的測(cè)試?？键c(diǎn)6軟件測(cè)試的實(shí)施考試鏈接：考點(diǎn)630%，主要是以選擇題的形式消滅，分值2分，此考點(diǎn)為識(shí)記內(nèi)容，讀者應(yīng)當(dāng)識(shí)記軟件測(cè)試過(guò)程4個(gè)步驟，單元測(cè)試的兩種測(cè)試方式。軟件測(cè)試過(guò)程分4個(gè)步驟，即單元測(cè)試、集成測(cè)試、驗(yàn)收測(cè)試和系統(tǒng)測(cè)試。單元測(cè)試是對(duì)軟件設(shè)計(jì)的最小單位--模塊〔程序單元〕進(jìn)展正確性檢驗(yàn)測(cè)試。單元測(cè)試的技術(shù)可以承受靜態(tài)分析和動(dòng)態(tài)測(cè)試。集成測(cè)試是測(cè)試和組裝軟件的過(guò)程，主要目的是覺(jué)察與接口有關(guān)的錯(cuò)誤，主要常承受兩種方式：非增量方式組裝和增量方式組裝。確認(rèn)測(cè)試的任務(wù)是驗(yàn)證軟件的功能和性能，以及其他特性是否滿(mǎn)足了需求規(guī)格認(rèn)的標(biāo)準(zhǔn)。系統(tǒng)測(cè)試是通過(guò)測(cè)試確認(rèn)軟件，作為整個(gè)基于計(jì)算機(jī)系統(tǒng)的一個(gè)元素，與計(jì)算〔使用〕環(huán)境下對(duì)計(jì)算機(jī)系統(tǒng)進(jìn)展一系列的集成測(cè)試和確認(rèn)測(cè)試。外部接口測(cè)試、安全性測(cè)試等。軟件的調(diào)試考點(diǎn)7軟件調(diào)試的根本概念考試鏈接：考點(diǎn)70%，主要是以選擇2分，此考點(diǎn)為重點(diǎn)識(shí)記內(nèi)容，讀者應(yīng)當(dāng)識(shí)記軟件調(diào)試的概念。誤區(qū)警示：程序經(jīng)調(diào)試改錯(cuò)后還應(yīng)進(jìn)展再測(cè)試，由于經(jīng)調(diào)試后有可能產(chǎn)生的錯(cuò)誤，而且測(cè)試是貫穿生命周期的整個(gè)過(guò)程。在對(duì)程序進(jìn)展了成功的測(cè)試之后將進(jìn)入程序調(diào)試〔通常稱(chēng)Debug，即排錯(cuò)。程序的調(diào)試任務(wù)是診斷和改正程序中的錯(cuò)誤。調(diào)試主要在開(kāi)發(fā)階段進(jìn)展。緣由和位置；二是對(duì)程序進(jìn)展修改，排解這個(gè)錯(cuò)誤。程序調(diào)試的根本步驟：中出錯(cuò)位置，找出錯(cuò)誤的內(nèi)在緣由；修改設(shè)計(jì)和代碼，以排解錯(cuò)誤；調(diào)試原則可以從以下兩個(gè)方面考慮：確定錯(cuò)誤的性質(zhì)和位置時(shí)的留意事項(xiàng)使用；避開(kāi)用摸索法，最多只能把它當(dāng)作最終手段。修改錯(cuò)誤原則代碼程序，不要轉(zhuǎn)變目標(biāo)代碼。疑難解答：軟件測(cè)試與軟件調(diào)試有何不同？軟件測(cè)試是盡可能多地覺(jué)察軟件中的錯(cuò)誤，而軟件調(diào)試的任務(wù)是診斷和改正程序中的錯(cuò)誤。軟件測(cè)試貫穿整個(gè)軟件生命周期，調(diào)試主要在開(kāi)發(fā)階段。例題詳解一、選擇題【例1】對(duì)軟件的特點(diǎn)，下面描述正確的選項(xiàng)是 〔考點(diǎn)1〕A〕軟件是一種物理實(shí)體B〕軟件在運(yùn)行使用期間不存在老化問(wèn)題件開(kāi)發(fā)、運(yùn)行對(duì)計(jì)算機(jī)沒(méi)有依靠性，不受計(jì)算機(jī)系統(tǒng)的限制D〕軟件的生產(chǎn)有一個(gè)明顯的制作過(guò)程解析：軟件在運(yùn)行期間不會(huì)由于介質(zhì)的磨損而老化，只可能由于適應(yīng)硬件環(huán)境。【例2】以下哪項(xiàng)是軟件生命周期的主要活動(dòng)階段？ 〔考點(diǎn)2〕A〕需求分析 件開(kāi)發(fā)C〕軟件確認(rèn) 軟件演進(jìn)解析：B、C、D〕明。A〕【例3】從技術(shù)觀點(diǎn)看，軟件設(shè)計(jì)包括 A〕構(gòu)造設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、程序設(shè)計(jì)B〕構(gòu)造設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、過(guò)程設(shè)計(jì)C〕構(gòu)造設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、文檔設(shè)計(jì)、過(guò)程設(shè)計(jì)D〕構(gòu)造設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、文檔設(shè)計(jì)、程序設(shè)計(jì)解析：技術(shù)角度，要進(jìn)展構(gòu)造、接口、數(shù)據(jù)、過(guò)程的設(shè)計(jì)。構(gòu)造設(shè)計(jì)是定義系過(guò)程設(shè)計(jì)是把系統(tǒng)構(gòu)造部件轉(zhuǎn)化為軟件的過(guò)程性描述。【例4】以下哪個(gè)是軟件測(cè)試的目的？ 〔考點(diǎn)5〕A〕證明程序沒(méi)有錯(cuò)誤 示程序的正確性C〕覺(jué)察程序中的錯(cuò)誤 改正程序中的錯(cuò)誤解析：關(guān)于測(cè)試目的的根本學(xué)問(wèn)，IEEE的定義是：使用人工或自動(dòng)手段來(lái)運(yùn)行果與實(shí)際結(jié)果之間的差異，所以正確答案是C。答案：C〕【例5】以下哪個(gè)測(cè)試要對(duì)接口測(cè)試？ 〔考點(diǎn)6〕A〕單元測(cè)試 成測(cè)試C〕驗(yàn)收測(cè)試 系統(tǒng)測(cè)試構(gòu)造測(cè)試、邊界條件測(cè)試和非法輸入的測(cè)試等，所以正確答案是?！纠?】程序調(diào)試的主要任務(wù)是 〔考點(diǎn)7〕A〕檢查錯(cuò)誤 B〕改正錯(cuò)誤C〕覺(jué)察錯(cuò)誤 D〕以上都不是答案：B〕【例7】以下哪些不是程序調(diào)試的根本步驟？ 〔考點(diǎn)7〕A〕分析錯(cuò)誤緣由 B〕錯(cuò)誤定位C〕修改設(shè)計(jì)代碼以排解錯(cuò)誤 測(cè)試，防止引入錯(cuò)誤解析：程序調(diào)試的根本步驟：中出錯(cuò)位置，找出錯(cuò)誤的內(nèi)在緣由。修改設(shè)計(jì)和代碼，以排解錯(cuò)誤。答案：A〕【例8】在修改錯(cuò)誤時(shí)應(yīng)遵循的原則有 〔考點(diǎn)7〕改錯(cuò)誤本身而不僅僅是錯(cuò)誤的征兆和表現(xiàn)B〕修改錯(cuò)誤的選項(xiàng)是源代碼而不是目標(biāo)代碼C〕遵循在程序設(shè)計(jì)過(guò)程中的各種方法和原則D〕以上3個(gè)都是解析：修改錯(cuò)誤原則：(1〕在消滅錯(cuò)誤的地方，很可能有別的錯(cuò)誤；修改錯(cuò)誤的一個(gè)常見(jiàn)失誤是只修改了這個(gè)錯(cuò)誤的征兆或這個(gè)錯(cuò)誤的表現(xiàn)，而沒(méi)有修改錯(cuò)誤本身；(3〕留意修正一個(gè)錯(cuò)誤的同時(shí)有可能會(huì)引入的錯(cuò)誤；(5〕修改源代碼程序，不要轉(zhuǎn)變目標(biāo)代碼。D〕二、填空題【例1】軟件設(shè)計(jì)是軟件工程的重要階段，是一個(gè)把軟件需求轉(zhuǎn)換為 過(guò)程〔考點(diǎn)3〕解析：軟件設(shè)計(jì)是軟件工程的重要階段，是一個(gè)把軟件需求轉(zhuǎn)換為軟件表示的軟件設(shè)計(jì)是確定系統(tǒng)的物理模型。答案：軟件表示【例2】 把一個(gè)待開(kāi)發(fā)的軟件分解成假設(shè)干小的簡(jiǎn)潔的局部〔考點(diǎn)3〕解析：模塊化是指把一個(gè)待開(kāi)發(fā)的軟件分解成假設(shè)干小的簡(jiǎn)潔的局部。如高級(jí)語(yǔ)以按肯定的方法組裝起來(lái)成為一個(gè)整體，從而實(shí)現(xiàn)整個(gè)系統(tǒng)的功能。答案：模塊化【例3】數(shù)據(jù)流圖承受4種符號(hào)表示 點(diǎn)和終點(diǎn)、數(shù)據(jù)流向和數(shù)據(jù)加工〔考點(diǎn)4〕解析：數(shù)據(jù)流圖可以表達(dá)軟件系統(tǒng)的數(shù)據(jù)存儲(chǔ)、數(shù)據(jù)源點(diǎn)和終點(diǎn)、數(shù)據(jù)流向和數(shù)據(jù)存儲(chǔ)，用方框來(lái)表示數(shù)據(jù)源點(diǎn)和終點(diǎn)。答案：數(shù)據(jù)存儲(chǔ)第四章數(shù)據(jù)庫(kù)設(shè)計(jì)根底E-R模型，關(guān)系模型和關(guān)系代數(shù)，讀者應(yīng)對(duì)此局部進(jìn)展重點(diǎn)學(xué)習(xí)。具體重點(diǎn)學(xué)習(xí)學(xué)問(wèn)點(diǎn)：數(shù)據(jù)的概念、數(shù)據(jù)庫(kù)治理系統(tǒng)供給的數(shù)據(jù)語(yǔ)言、數(shù)據(jù)治理員的主要工作、三級(jí)模式及兩級(jí)映射的概念數(shù)據(jù)模型3個(gè)描述內(nèi)容、E-R模型的概念及其E-R圖表示法、關(guān)系操縱、關(guān)系模型三類(lèi)數(shù)據(jù)約束關(guān)系模型的根本操作、關(guān)系代數(shù)中的擴(kuò)大運(yùn)算數(shù)據(jù)庫(kù)設(shè)計(jì)生命周期法的4個(gè)階段數(shù)據(jù)庫(kù)系統(tǒng)的根本概念考點(diǎn)1數(shù)據(jù)、數(shù)據(jù)庫(kù)、數(shù)據(jù)庫(kù)治理系統(tǒng)考試鏈接：考點(diǎn)10%，主要是以選擇2分，此考點(diǎn)為重點(diǎn)識(shí)記內(nèi)容，讀者還應(yīng)當(dāng)識(shí)記數(shù)據(jù)語(yǔ)言所包括的數(shù)據(jù)定義語(yǔ)言、數(shù)據(jù)操縱語(yǔ)言和數(shù)據(jù)掌握語(yǔ)言。數(shù)據(jù)是數(shù)據(jù)庫(kù)中存儲(chǔ)的根本對(duì)象，描述事物的符號(hào)記錄。數(shù)據(jù)庫(kù)是長(zhǎng)期儲(chǔ)存在計(jì)算機(jī)內(nèi)、有組織的、可共享的大量數(shù)據(jù)的集合，它具有應(yīng)用程序所共享。數(shù)據(jù)庫(kù)治理系統(tǒng)〔DBMS，DatabaseManagementSystem〕是數(shù)據(jù)庫(kù)的機(jī)構(gòu)，它是一種系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)庫(kù)中的數(shù)據(jù)組織、數(shù)據(jù)操作、數(shù)據(jù)維護(hù)、掌握及保護(hù)和數(shù)據(jù)存取的物理構(gòu)建、數(shù)據(jù)操縱、數(shù)據(jù)的完整性、安全性定義和檢查、數(shù)據(jù)庫(kù)的并發(fā)掌握與故障恢復(fù)、數(shù)據(jù)的效勞。義語(yǔ)言、數(shù)據(jù)操縱語(yǔ)言、數(shù)據(jù)掌握語(yǔ)言。高系統(tǒng)效率?？键c(diǎn)2數(shù)據(jù)庫(kù)系統(tǒng)的進(jìn)展考試鏈接：考點(diǎn)230%，主要是以選擇題的形式消滅，分值2分，此考點(diǎn)為識(shí)記內(nèi)容，讀者還應(yīng)當(dāng)留意各個(gè)階段的特點(diǎn)。3個(gè)階段，見(jiàn)表4-1：表4-1 各階段特點(diǎn)的具體說(shuō)明計(jì)算機(jī)二級(jí)考試公共根底學(xué)問(wèn)計(jì)算機(jī)二級(jí)考試公共根底學(xué)問(wèn)考點(diǎn)3數(shù)據(jù)庫(kù)系統(tǒng)的根本特點(diǎn)考試鏈接：考點(diǎn)330%，主要是以填空題的形式消滅，分值2分，此考點(diǎn)為識(shí)記內(nèi)容，讀者還應(yīng)當(dāng)理解物理獨(dú)立性和規(guī)律獨(dú)立性的定義。數(shù)據(jù)獨(dú)立性是數(shù)據(jù)與程序間的互不依靠性，即數(shù)據(jù)庫(kù)中的數(shù)據(jù)獨(dú)立于應(yīng)用程序而不依靠于應(yīng)用程序。數(shù)據(jù)的獨(dú)立性一般分為物理獨(dú)立性與規(guī)律獨(dú)立性?xún)煞N。物理獨(dú)立性：指用戶(hù)的應(yīng)用程序與存儲(chǔ)在磁盤(pán)上的數(shù)據(jù)庫(kù)中數(shù)據(jù)是相互〔包括存儲(chǔ)構(gòu)造、存取方式等〕轉(zhuǎn)變時(shí)，如存儲(chǔ)設(shè)備的更換、物理存儲(chǔ)的更換、存取方式轉(zhuǎn)變等，應(yīng)用程序都不用轉(zhuǎn)變。的規(guī)律構(gòu)造轉(zhuǎn)變了，如修改數(shù)據(jù)模式、增加的數(shù)據(jù)類(lèi)型、轉(zhuǎn)變數(shù)據(jù)間聯(lián)系等，用戶(hù)程序都可以不變。保護(hù)和并發(fā)掌握?？键c(diǎn)4數(shù)據(jù)庫(kù)系統(tǒng)的內(nèi)部構(gòu)造體系考試鏈接：考點(diǎn)430%，主要是以選擇題的形式消滅，分值2分，此考點(diǎn)為識(shí)記內(nèi)容，讀者還應(yīng)當(dāng)理解三級(jí)模式及兩級(jí)映射的定義。誤區(qū)警示：一個(gè)數(shù)據(jù)庫(kù)只有一個(gè)概念模式。一個(gè)概念模式可以有假設(shè)干個(gè)外模式。三級(jí)模式都有幾種名稱(chēng)，讀者應(yīng)當(dāng)熟記每個(gè)模式的另一些名稱(chēng)。數(shù)據(jù)統(tǒng)系統(tǒng)的3級(jí)模式是全體用戶(hù)〔應(yīng)用〕公共數(shù)據(jù)視圖。一個(gè)數(shù)據(jù)庫(kù)只有一個(gè)概念模式。的規(guī)律構(gòu)造和特征的描述，它是由概念模式推導(dǎo)而出來(lái)的，是數(shù)據(jù)庫(kù)用戶(hù)的數(shù)據(jù)視計(jì)算機(jī)二級(jí)考試公共根底學(xué)問(wèn)計(jì)算機(jī)二級(jí)考試公共根底學(xué)問(wèn)圖，是與某一應(yīng)用有關(guān)的數(shù)據(jù)的規(guī)律表示。一個(gè)概念模式可以有假設(shè)干個(gè)外模式。方法。內(nèi)模式處于最底層，它反映了數(shù)據(jù)在計(jì)算機(jī)物理構(gòu)造中的實(shí)際存儲(chǔ)形式，概念反映了用戶(hù)對(duì)數(shù)據(jù)的要求。小提示：內(nèi)模式處于最底層，它反映了數(shù)據(jù)在計(jì)算機(jī)物理構(gòu)造中的實(shí)際存儲(chǔ)形式，概念模式處于中間層，它反映了設(shè)計(jì)者的數(shù)據(jù)全局規(guī)律要求，而外模式處于最外層，它反映了用戶(hù)對(duì)數(shù)據(jù)的要求。數(shù)據(jù)庫(kù)系統(tǒng)的兩級(jí)映射兩級(jí)映射保證了數(shù)據(jù)庫(kù)系統(tǒng)中數(shù)據(jù)的獨(dú)立性。概念模式到內(nèi)模式的映射。該映射給出了概念模式中數(shù)據(jù)的全局規(guī)律構(gòu)造到數(shù)據(jù)的物理存儲(chǔ)構(gòu)造間的對(duì)應(yīng)關(guān)系；外模式到概念模式的映射。概念模式是一個(gè)全局模式而外模式是用戶(hù)的根本視圖。疑難解答：數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)的構(gòu)造是什么樣的？數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)的7個(gè)局部以肯定的規(guī)律層次構(gòu)造方式組成一個(gè)有機(jī)的整體，它們的構(gòu)造關(guān)系是：應(yīng)用系統(tǒng)工、應(yīng)用開(kāi)發(fā)工具軟件、數(shù)據(jù)庫(kù)治理系統(tǒng)、操作系統(tǒng)、硬件。數(shù)據(jù)模型考點(diǎn)5數(shù)據(jù)模型的根本概念考試鏈接：考點(diǎn)5在筆試考試中是一個(gè)常?？疾斓膬?nèi)容，消滅的機(jī)率70%，主要是以填空形式消滅，分值為2分，此考點(diǎn)為重點(diǎn)識(shí)記內(nèi)容，讀者應(yīng)當(dāng)識(shí)記數(shù)據(jù)模型數(shù)據(jù)模型用來(lái)抽象、表示和處理現(xiàn)實(shí)世界中的數(shù)據(jù)和信息。分為兩個(gè)階段：把現(xiàn)實(shí)世界中的客觀對(duì)象抽象為概念模型；把概念模型轉(zhuǎn)換為某一DBMS支持的數(shù)據(jù)模型。數(shù)據(jù)模型所描述的內(nèi)容有3個(gè)局部，它們是數(shù)據(jù)構(gòu)造、數(shù)據(jù)操作與數(shù)據(jù)約束。考點(diǎn)6E-R模型考試鏈接：考點(diǎn)630%，主要是以選擇題的形式消滅，分值4分，此考點(diǎn)為理解內(nèi)容，讀者應(yīng)當(dāng)理解實(shí)體間三種函數(shù)關(guān)系，識(shí)記實(shí)體、屬性、聯(lián)系各用什么圖形來(lái)表示。1．E-R模型的根本概念位，它們是客觀存在的且又能相互區(qū)分的事物。屬性：現(xiàn)實(shí)世界中事物均有一些特性，這些特性可以用屬性來(lái)表示。碼：唯一標(biāo)識(shí)實(shí)體的屬性集稱(chēng)為碼。域：屬性的取值范圍稱(chēng)為該屬性的域。聯(lián)系：在現(xiàn)實(shí)世界中事物間的關(guān)聯(lián)稱(chēng)為聯(lián)系。幾種：一對(duì)一的聯(lián)系、一對(duì)多或多對(duì)一聯(lián)系、多對(duì)多。2．E-R模型的圖示法E-R模型用E-R圖來(lái)表示。實(shí)體表示法：在E-R圖中用矩形表示實(shí)體集，在矩形內(nèi)寫(xiě)上該實(shí)體集的名字。屬性表示法：在E-R圖中用橢圓形表示屬性，在橢圓形內(nèi)寫(xiě)上該屬性的名稱(chēng)。聯(lián)系表示法：在E-R圖中用菱形表示聯(lián)系，菱形內(nèi)寫(xiě)上聯(lián)系名。考點(diǎn)7層次模型考試鏈接：考點(diǎn)730%，主要是以選擇題的形式消滅，分值2分，此考點(diǎn)為識(shí)記內(nèi)容，讀者應(yīng)當(dāng)理解層次模型的定義。它的根本構(gòu)造是樹(shù)形構(gòu)造。滿(mǎn)足下面兩個(gè)條件的根本層次聯(lián)系的集合為層次模型。有且只有一個(gè)結(jié)點(diǎn)沒(méi)有雙親結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)稱(chēng)為根結(jié)點(diǎn)；除根結(jié)點(diǎn)以外的其他結(jié)點(diǎn)有且僅有一個(gè)雙親結(jié)點(diǎn)?？键c(diǎn)8關(guān)系模型考試鏈接：考點(diǎn)80%，主要是以選擇題2數(shù)據(jù)約束。誤區(qū)警示：當(dāng)對(duì)關(guān)系模型進(jìn)展查詢(xún)運(yùn)算，涉及到多種運(yùn)算時(shí)，應(yīng)當(dāng)留意它們之間的先后挨次，由于有可能進(jìn)展投影運(yùn)算時(shí)，把符合條件的記錄過(guò)濾，產(chǎn)生錯(cuò)誤的結(jié)果。關(guān)系模型承受二維表來(lái)表示，二維表一般滿(mǎn)足下面7共性質(zhì)：二維表中元組個(gè)數(shù)是有限的--元組個(gè)數(shù)有限性；二維表中元組均不一樣--元組的唯一性；二維表中元組的次序可以任意交換--元組的次序無(wú)關(guān)性；二維表中元組的重量是不行分割的根本數(shù)據(jù)項(xiàng)--元組重量的原子性；二維表中屬性名各不一樣--屬性名唯一性；二維表中屬性與次序無(wú)關(guān)，可任意交換--屬性的次序無(wú)關(guān)性；二維表屬性的重量具有與該屬性一樣的值域--重量值域的統(tǒng)一性。在二維表中惟一標(biāo)識(shí)元組的最小屬性值稱(chēng)為該表的鍵或碼。二維表中可能有假設(shè)鍵或外碼。關(guān)系操縱：數(shù)據(jù)查詢(xún)、數(shù)據(jù)刪除、數(shù)據(jù)插入、數(shù)據(jù)修改。及用戶(hù)定義的完整性約束。小提示：關(guān)系模式承受二維表來(lái)表示，一個(gè)關(guān)系對(duì)應(yīng)一張二維表?？梢赃@么說(shuō)，一個(gè)關(guān)系就是一個(gè)二維表，但是一個(gè)二維表不肯定是一個(gè)關(guān)系。疑難解答：E-R圖是如何向關(guān)系模式轉(zhuǎn)換的？從E-RE-R圖中屬性也可以轉(zhuǎn)換成關(guān)系的屬性。實(shí)體集也可以轉(zhuǎn)換成關(guān)系。關(guān)系代數(shù)考點(diǎn)9關(guān)系代數(shù)考試鏈接：考點(diǎn)930%，主要是以選擇題的形式消滅，分值2分，此考點(diǎn)重點(diǎn)把握理解內(nèi)容，讀者應(yīng)當(dāng)理解關(guān)系模型的根本操作以及關(guān)系代數(shù)的幾種運(yùn)算。誤區(qū)警示：當(dāng)對(duì)關(guān)系模型進(jìn)展查詢(xún)運(yùn)算，涉及到多種運(yùn)算時(shí)，應(yīng)當(dāng)留意它們之間的先后挨次，由于有可能進(jìn)展投影運(yùn)算時(shí)，把符合條件的記錄過(guò)濾，產(chǎn)生錯(cuò)誤的結(jié)果。關(guān)系模型的根本操作其中查詢(xún)包含如下運(yùn)算：①投影運(yùn)算。從R中選擇出假設(shè)干屬性列組成的關(guān)系。R〔并由該運(yùn)算給出所選擇的規(guī)律條件〕后仍為一個(gè)關(guān)系。設(shè)關(guān)系的規(guī)律條件為F，則R滿(mǎn)足F的選擇運(yùn)算可寫(xiě)成：σF(R)R與S經(jīng)笛卡爾積記為R×S，該關(guān)系是一個(gè)n+m元關(guān)系，元組個(gè)數(shù)是p×q，由R與S的有序組組合而成。小提示：當(dāng)關(guān)系模式進(jìn)展笛卡爾積運(yùn)算時(shí)，讀者應(yīng)當(dāng)留意運(yùn)算后的結(jié)果是n+m元關(guān)系，元組個(gè)數(shù)是p×q，這是常?；煜?。關(guān)系代數(shù)中的擴(kuò)大運(yùn)算交運(yùn)算：關(guān)系R與S經(jīng)交運(yùn)算后所得到的關(guān)系是由那些既在R內(nèi)又在S內(nèi)的有序組所組成，記為R∩S。除運(yùn)算時(shí)，則可將除運(yùn)算寫(xiě)成：T÷R=S或T/R=SS稱(chēng)為T(mén)除以R的商。除法運(yùn)算不是根本運(yùn)算，它可以由根本運(yùn)算推導(dǎo)而出。連接與自然連接運(yùn)算連接運(yùn)算又可稱(chēng)為θ運(yùn)算，這是一種二元運(yùn)算，通過(guò)它可以將兩個(gè)關(guān)系合并成一個(gè)大關(guān)系。設(shè)有關(guān)系R、S以及比較式iθj，其中i為R中的域，j為S中的域，θ含義同前。則可以將R、S在域i，j上的θ連接記為：R|×|Siθjθ為“=“，就稱(chēng)此連接為等值連接，否則稱(chēng)為不等值連接；如θ為“<“時(shí)稱(chēng)為小于連接；如θ為“>“時(shí)稱(chēng)為大于連接。自然連接〔naturaljoin〕是一種特別的等值連接，它滿(mǎn)足下面的條件：①兩關(guān)系間有公共域；②通過(guò)公共域的等值進(jìn)展連接。R、S，R有域A1，A2，…，An，S有域B1，B2，…，Bm，并且，Ai1，B1，B2，…，Bj分別為一樣域，此時(shí)它們自然連接可記為：R|×|S自然連接的含義可用下式表示：R|×|S=πA1A2

An,Bj+1,

Bm〔σAi1=B1^Ai2=B2^

^Aij=,Bj(R×S)〕， ，…… …… …疑難解答：連接與自然連接的不同之處在什么？一般的連接操作是從行的角度進(jìn)展運(yùn)算，但自然連接還需要取消重復(fù)列，所以是同時(shí)從行和列的角度進(jìn)展運(yùn)算。數(shù)據(jù)庫(kù)設(shè)計(jì)與治理考點(diǎn)10數(shù)據(jù)庫(kù)設(shè)計(jì)概述考試鏈接：考點(diǎn)1030%，主要是以選擇題的形式消滅，分值2分，此考點(diǎn)為識(shí)記內(nèi)容，讀者還應(yīng)識(shí)記數(shù)據(jù)庫(kù)設(shè)計(jì)的4個(gè)階段以及它們相應(yīng)的任務(wù)。數(shù)據(jù)庫(kù)設(shè)計(jì)中有兩種方法，面對(duì)數(shù)據(jù)的方法和面對(duì)過(guò)程的方法：面對(duì)數(shù)據(jù)的方法是以信息需求為主，兼顧處理需求；面對(duì)過(guò)程的方法是以處理因此面對(duì)數(shù)據(jù)的設(shè)計(jì)方法已成為主流。數(shù)據(jù)庫(kù)設(shè)計(jì)目前一般承受生命周期法，馬上整個(gè)數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)的開(kāi)發(fā)分解成承受前4個(gè)階段。疑難解答：數(shù)據(jù)庫(kù)設(shè)計(jì)的前4個(gè)階段的成果分別是什么？數(shù)據(jù)庫(kù)設(shè)計(jì)中一般承受前4個(gè)階段，它們的成果分別是需求說(shuō)明書(shū)、概念數(shù)據(jù)模型、規(guī)律數(shù)據(jù)模型和數(shù)據(jù)庫(kù)內(nèi)模式。4.4一、選擇題】對(duì)于數(shù)據(jù)庫(kù)系統(tǒng)，負(fù)責(zé)定義數(shù)據(jù)庫(kù)內(nèi)容，打