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

第1 章數(shù)據(jù)構(gòu)造與算法具體重點(diǎn)學(xué)習(xí)學(xué)問(wèn)點(diǎn)：1. 算法的概念、算法時(shí)間簡(jiǎn)單度及空間簡(jiǎn)單度的概念2?數(shù)據(jù)構(gòu)造的定義、數(shù)據(jù)邏笹構(gòu)造及物理構(gòu)造的定義棧的定義及其運(yùn)算、線性鏈表的存儲(chǔ)方式樹(shù)與二叉樹(shù)的概念、二叉樹(shù)的根本性質(zhì)、完全二叉樹(shù)的概念、二叉樹(shù)的遍歷二分杳找法冒泡排序法1?1算法1算法的根本概念考試鏈接：130%,2分，此考點(diǎn)為識(shí)記內(nèi)容，讀者還應(yīng)當(dāng)了解算法中對(duì)數(shù)據(jù)的根本運(yùn)算。計(jì)算機(jī)解題的過(guò)程實(shí)際上是在實(shí)施某種算法，這種算法稱為計(jì)算機(jī)算法。算法的基木特征：可行性、確定性、有窮性、擁有足夠的情報(bào)。2?算法的基木要素：算法屮對(duì)數(shù)據(jù)的運(yùn)算和操作4類：算術(shù)運(yùn)算、規(guī)律運(yùn)算、關(guān)系運(yùn)算和數(shù)據(jù)傳輸。算法的掌握構(gòu)造：算法屮各操作Z間的執(zhí)行挨次稱為算法的掌握構(gòu)造。描述算法的工具通常有傳統(tǒng)流稈圖、N?S構(gòu)造化流稈圖、算法描述語(yǔ)言等。一個(gè)算法一般都可以用挨次、選擇、循環(huán)3種根本掌握構(gòu)造組合而成。2算法簡(jiǎ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)展編譯，或者在不同的計(jì)算機(jī)上運(yùn)行，效率均不同。這說(shuō)明使用確定的時(shí)間單位衡量算法的效率是不適宜的。撇開(kāi)這些與計(jì)算機(jī)駛〔通常n表示〕，它是問(wèn)題規(guī)模的函數(shù)。即算法的工作量=f〔n〕算法的空間簡(jiǎn)單度算法的空間簡(jiǎn)單度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。一個(gè)算法所l1用的存儲(chǔ)空間包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間以及算法執(zhí)行過(guò)稈中所需要的額外空間。其屮額外空間包括算法稈序執(zhí)行過(guò)稈屮的工作單元以及某種數(shù)據(jù)構(gòu)造所需要的附加存儲(chǔ)空間。假設(shè)額外空間景相對(duì)于問(wèn)題規(guī)模來(lái)說(shuō)是常數(shù)，則稱該算法是原地工作的。在很多實(shí)際問(wèn)題屮，為了削減算法所占的存儲(chǔ)空間，通常承受壓縮存儲(chǔ)技術(shù)，以便盡量削減不必要的額外空間。疑難解答：算法的工作量用什么來(lái)計(jì)算？法的工作最=4〔n〕,n是問(wèn)題的規(guī)模。1.2 數(shù)據(jù)構(gòu)造的根本概念3數(shù)據(jù)構(gòu)造的定義考試鏈接：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ù)元素Z間所尚有的規(guī)律關(guān)系，即數(shù)據(jù)的規(guī)律構(gòu)造；在對(duì)數(shù)據(jù)元素進(jìn)展處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)屮的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)；對(duì)各種數(shù)據(jù)構(gòu)造進(jìn)展的運(yùn)算。數(shù)據(jù)：是對(duì)客觀事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)屮是指全部能輸入到計(jì)算機(jī)小并被計(jì)算機(jī)程序處理的符號(hào)的總稱。數(shù)據(jù)元素：是數(shù)據(jù)的基木單位，在計(jì)算機(jī)程序屮通常作為一個(gè)整體進(jìn)展考慮和處理。數(shù)據(jù)對(duì)象：是性質(zhì)一樣的數(shù)據(jù)元索的集合，是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)的規(guī)律構(gòu)造是對(duì)數(shù)據(jù)元素Z間的規(guī)律關(guān)系的描述，它可以用一個(gè)數(shù)據(jù)元素的集合和定義在此集合屮的假設(shè)干關(guān)系來(lái)表示。數(shù)據(jù)的規(guī)律構(gòu)造有兩個(gè)要素：一是數(shù)據(jù)元素的集合，通常記為D；二DZR。一個(gè)數(shù)據(jù)構(gòu)造可以表示成B=〔D,R〕其中B表示數(shù)據(jù)構(gòu)造。為了反映D屮各數(shù)據(jù)元素之間的前后件關(guān)系，一般用二元組來(lái)表示。數(shù)〔也稱數(shù)據(jù)的物理構(gòu)造。由于數(shù)據(jù)元索在計(jì)算機(jī)存儲(chǔ)空間屮的位置關(guān)系可能與規(guī)律關(guān)系不同，因此，為了表示存放在計(jì)算機(jī)存儲(chǔ)空間中的各數(shù)據(jù)元素2間的規(guī)律關(guān)系〔即前后件關(guān)系〕，在數(shù)據(jù)的存儲(chǔ)構(gòu)造中，不僅要存放Z間的前后件關(guān)系的信息。一種數(shù)據(jù)的規(guī)律構(gòu)造依據(jù)需要可以表示成多種存儲(chǔ)構(gòu)造，常用的存儲(chǔ)構(gòu)造有挨次、鏈接、索引等存儲(chǔ)構(gòu)造。而承受不同的存儲(chǔ)構(gòu)造，其數(shù)據(jù)處理的效率是不同的。因此，在進(jìn)展數(shù)據(jù)處理時(shí)，選擇適宜的存儲(chǔ)構(gòu)造是很重要的。4線性構(gòu)造與非線性構(gòu)造考試鏈接：4在筆試考試中，雖然說(shuō)不是考試常常考察的內(nèi)容，但讀者還是對(duì)此考點(diǎn)有所了解，在筆試考試中消滅30%,2分，此考點(diǎn)為識(shí)記內(nèi)容°依據(jù)數(shù)據(jù)構(gòu)造屮各數(shù)據(jù)元索Z間前后件關(guān)系的簡(jiǎn)單程度，一般將數(shù)據(jù)構(gòu)造分為兩大類型：線性構(gòu)造與非線性構(gòu)造。假設(shè)一個(gè)非空的數(shù)據(jù)構(gòu)造滿足以下兩個(gè)條件：有且只有一個(gè)根結(jié)點(diǎn)；每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。Z為非線性構(gòu)造。?疑難解答：空的數(shù)據(jù)構(gòu)造是線性構(gòu)造還是菲線性構(gòu)造？的算法是按線性構(gòu)造的規(guī)章來(lái)處理的，則屬于線性構(gòu)造；否則屬于非線性構(gòu)造。1 3棧及線性鏈表5棧及其根本運(yùn)算考試鏈接：5100%,主要是以選擇的形式消滅，2分，此考點(diǎn)為重點(diǎn)把握內(nèi)容，讀者應(yīng)當(dāng)把握棧的運(yùn)算。棧的基木概念棧是限定只在一端進(jìn)展插入與刪除的線性表，通常稱插入、刪除的這一端為棧頂，另一端為棧底。當(dāng)表屮沒(méi)有元索時(shí)稱為空棧。棧頂元索總是后被插入的元索，從而也是最先被刪除的元素；棧底先進(jìn)后出〃或“后進(jìn)先出〃的原則組織數(shù)據(jù)的。棧的挨次存儲(chǔ)及其運(yùn)算用一維數(shù)纟RS〔1：m〕作為棧的挨次存儲(chǔ)空間，其中m為最大容量。在棧的挨次存儲(chǔ)空間S〔1：m〕屮，S〔bottom〕為棧底元索，S〔top〕為棧頂元索。top=0表示?？?top=m表示棧滿。棧的基木運(yùn)算有三種：入棧、退棧與讀棧頂元素。入棧運(yùn)算：入棧運(yùn)算是指在棧頂位置插入一個(gè)元素。首先將棧頂指針加一〔top加1〕,然后將元素插入到棧頂指針指向的位置。當(dāng)棧頂指件已經(jīng)指向存儲(chǔ)空間的最終一個(gè)位置時(shí)，說(shuō)明?？臻g已滿，不行能再進(jìn)展入棧操作。這種狀況稱為?！ㄉ弦纭ㄥe(cuò)誤。退棧運(yùn)算：退棧是指取出棧頂元素并賦給一個(gè)指定的變量。首先將棧頂元素〔指針指向的元素〕賦給一個(gè)指定的變量，然后將棧頂指針減一〔即top減1〕。當(dāng)棧頂指針為0時(shí)，說(shuō)明?？眨恍羞M(jìn)展退棧操作。這種狀況稱為棧的〃下溢〃錯(cuò)誤。頂元索，只是將它賦給一個(gè)變量，因此棧頂指針不會(huì)轉(zhuǎn)變。當(dāng)棧頂指針為0時(shí)，說(shuō)明?？?讀不到棧頂元素?？疾旄鞣N不同的出棧方式。6線性鏈表的根本概念考試鏈接：630%,2分，此考點(diǎn)為識(shí)記內(nèi)容。重點(diǎn)識(shí)記結(jié)點(diǎn)的紐成?！布辞凹蚝蠹?。鏈?zhǔn)酱鎯?chǔ)方式既可用于表示線性構(gòu)造，也可用于表示非線性構(gòu)造。線性鏈表線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造稱為線性鏈表。在某些應(yīng)用屮，對(duì)線性鏈表屮的每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針，一個(gè)稱為左指針，用以指向其前件結(jié)點(diǎn)；另一個(gè)稱為右指針，用以指向其后件結(jié)點(diǎn)。這樣的表稱為雙向鏈表。帶鏈的棧棧也是線性表，也可以承受鏈?zhǔn)酱鎯?chǔ)構(gòu)造。帶鏈的棧可以用來(lái)收集計(jì)算機(jī)存儲(chǔ)空間中所有空閑的存儲(chǔ)結(jié)點(diǎn)，這種帶鏈的棧稱為可利用棧。?疑難解答：在鏈?zhǔn)綐?gòu)造中，存儲(chǔ)空間位置關(guān)系與規(guī)律關(guān)系是什么？系可以不全都，而數(shù)據(jù)元索之間的規(guī)律關(guān)系是山指針域來(lái)確定的。1.4 樹(shù)與二叉樹(shù)7樹(shù)與二叉樹(shù)及其根本性質(zhì)考試鏈接：7100%,主要是以選擇的形式消滅，2分，此考點(diǎn)為重點(diǎn)把握內(nèi)容。重點(diǎn)識(shí)記樹(shù)及二叉樹(shù)的性質(zhì)。誤區(qū)警示：滿二叉樹(shù)也是完全二叉樹(shù)，而完全二叉樹(shù)一般不是滿二叉樹(shù)。應(yīng)當(dāng)留意二者的區(qū)分。1、樹(shù)的根本概念樹(shù)〔tree〕點(diǎn)。沒(méi)有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。在樹(shù)構(gòu)造中，一個(gè)結(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱為該結(jié)點(diǎn)的度。葉子結(jié)點(diǎn)的度為0。在樹(shù)中,全部結(jié)點(diǎn)中的最大的度稱為樹(shù)的度。2、二叉樹(shù)及其基木性質(zhì)二叉樹(shù)的定義二叉樹(shù)是一種很有用的非線性構(gòu)造，具有以下兩個(gè)特點(diǎn)：①非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)；②每一個(gè)結(jié)點(diǎn)報(bào)多有兩棵子樹(shù)，且分別稱為該結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)。由以上特點(diǎn)可以看出，在二叉樹(shù)中，每一個(gè)結(jié)點(diǎn)的度最大為2,即全部了樹(shù)〔左了樹(shù)或右了樹(shù)〕也均為二叉樹(shù)，而樹(shù)構(gòu)造屮的每一個(gè)結(jié)點(diǎn)的度可以是任意的。另外，二叉樹(shù)屮的每個(gè)結(jié)點(diǎn)的了樹(shù)被明右子樹(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ì)：性質(zhì)1：在二叉樹(shù)的第k層上，最多有2k?l〔k$l〕個(gè)結(jié)點(diǎn)；2：m2m?l個(gè)結(jié)點(diǎn)；性質(zhì)3：在任意一棵二叉樹(shù)中，度為0的結(jié)點(diǎn)〔即葉子結(jié)點(diǎn)〕總是比度為2的結(jié)點(diǎn)多一個(gè)。性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的二叉樹(shù),其深度至少為［log2n］+1,其中Elog2n］表示取log?“的整數(shù)局部。不變的。3、滿二叉樹(shù)與完全二叉樹(shù)二叉樹(shù)屮，每一層上的結(jié)點(diǎn)數(shù)祁到達(dá)最大值，即在滿二叉樹(shù)的第k層上有2k?l個(gè)結(jié)點(diǎn)，且深度為m2m—1個(gè)結(jié)點(diǎn)。上只缺少右邊的假設(shè)干結(jié)點(diǎn)。P，p,或?yàn)閜+1。完全二叉樹(shù)具有以下兩共性質(zhì)：性質(zhì)5:具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為［log2n］+1。性質(zhì)6:設(shè)完全二叉樹(shù)共有n個(gè)結(jié)點(diǎn)。假設(shè)從根結(jié)點(diǎn)開(kāi)頭，按層次〔每一層從左到右〕用自然數(shù)1，2,……，nk〔k=l,2,……,n〕的結(jié)點(diǎn)有以下結(jié)論：0①k=l,則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒(méi)有父結(jié)點(diǎn)；假設(shè)k>l,INT〔k/2〕0②假設(shè)2kWn,k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為2k；否則該結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn)〔明顯也沒(méi)有右子結(jié)點(diǎn)〕。2k+lWmk2k+l；否則該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn)?？键c(diǎn)8二叉樹(shù)的遍歷考試鏈接：830%,2分，讀者應(yīng)當(dāng)嫻熟把握各種遍歷的具體算法，能由兩種遍歷的結(jié)果推導(dǎo)另一種遍歷的結(jié)果，根結(jié)點(diǎn)的次序，二叉樹(shù)的遍歷分為三類：前序遍歷、屮序遍歷和后序遍歷。子樹(shù)時(shí)，仍舊先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最終遍歷右子樹(shù)。中序遍歷：先遍歷左子樹(shù)、然后訪問(wèn)根結(jié)點(diǎn)，最終遍歷右子樹(shù)；并且，在遍歷左、右了樹(shù)時(shí)，仍舊先遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最終遍歷右了樹(shù)。后序遍歷：先遍歷左了樹(shù)、然后遍歷右了樹(shù)，最終訪問(wèn)根結(jié)點(diǎn)；并且，在遍歷左、右了樹(shù)時(shí)，仍舊先遍歷左子樹(shù)，然后遍歷右了樹(shù)，最終訪問(wèn)根結(jié)點(diǎn)。?疑難解答：樹(shù)與二叉樹(shù)的不同之處是什么？2,即全部子樹(shù)〔左子樹(shù)或右子樹(shù)〕也均為二叉樹(shù)，血樹(shù)構(gòu)造屮的毎一個(gè)結(jié)點(diǎn)的度可以是任意的。9挨次查找

1?5查找技術(shù)考試鏈接：930%,2分，讀者應(yīng)當(dāng)具體把握挨次查找的算法。找元索進(jìn)展了比校但都不相等，則表示查找失敗。在以下兩種狀況下也只能承受挨次查找：假設(shè)線性表為無(wú)序表，則不管是挨次存儲(chǔ)構(gòu)造還是鏈?zhǔn)酱鎯?chǔ)構(gòu)造，只能用挨次杳找。即使是有序線性表，假設(shè)承受鏈?zhǔn)酱鎯?chǔ)構(gòu)造，也只能用挨次杏找。10二分法查找考試鏈接：1030%,2分，考核比較多查找的比較次數(shù)，讀者應(yīng)當(dāng)具體把握二分查找法的算法。二分法只適用于挨次存儲(chǔ)的，按非遞減排列的冇序表，其方法如下：設(shè)有序線性表的長(zhǎng)度為m被查找的元索為i,i與線性表的中間項(xiàng)進(jìn)展比較;i與屮間項(xiàng)的值相等，則查找成功；假設(shè)i小于屮間項(xiàng)，則在線性表的前半局部以一樣的方法杏找；假設(shè)i大于屮間項(xiàng)，則在線性表的后半局部以一樣的方法杏找。?疑難解答：二分查找法適用于哪種狀況？二分查找法只適用于挨次存儲(chǔ)的有■序表。在此所說(shuō)的有序表是指線性表中的元素按值非遞減排列〔小到大，但允許相鄰元索值相等〕。這個(gè)過(guò)程始終進(jìn)展到杳找成功或了表長(zhǎng)度為0為止。對(duì)于長(zhǎng)度為n的有序線性表，在最壞狀況下，二分杏找只需要比較log2n次。1.6 排序技術(shù)11交換類排序法考試鏈接：1130%,2分，讀者應(yīng)當(dāng)嫻熟把握幾種排序算法的根本過(guò)程。冒泡排序法和快速排序法祁屬于交換類排序法。冒泡排序法然后，從示到前掃描剩下的線性表，逐次比較相鄰兩個(gè)元素的大小，假設(shè)示面的元素小于前血的面。對(duì)剩下的線性表重復(fù)上述過(guò)程，育到剩下的線性表變空為止，此時(shí)已經(jīng)排好序。n〔n-1〕/2?？焖倥判蚍ㄋ母舅枷胧牵喝稳〈判蛐蛄行〉哪硞€(gè)元素作為基準(zhǔn)〔一般取第一個(gè)元素〕，通過(guò)一趟排序，將待排元素分為左右兩個(gè)了序列，左了序列元素的排序碼均小于或等于基準(zhǔn)元素的排序碼，右了序?疑難解答：冒泡排序和快速排序的平均執(zhí)行時(shí)間分別是多少？冒泡排序法的平均執(zhí)行時(shí)間是O〔朋〕，而快速排序法的平均執(zhí)行時(shí)間是O〔nlog2n〕。7 例題詳解一、選擇題【例1】算法的時(shí)問(wèn)簡(jiǎn)單度取決于 。〔考點(diǎn)2〕C〕問(wèn)題的難度

D〕A〕B〕據(jù)有關(guān)。即與輸入數(shù)據(jù)全部的可能取值范圍、輸入各種數(shù)據(jù)或數(shù)據(jù)集的概率有關(guān)。答案：D〕【例2】在數(shù)據(jù)構(gòu)造屮，從規(guī)律上可以把數(shù)據(jù)構(gòu)造分成 ?！部键c(diǎn)3〕A〕內(nèi)部構(gòu)造和外部構(gòu)造 B〕線性構(gòu)造和非線性構(gòu)造C〕緊湊構(gòu)造和非緊湊構(gòu)造 D〕動(dòng)態(tài)構(gòu)造和靜態(tài)構(gòu)造解析：邏笹構(gòu)造反映數(shù)據(jù)元素Z間的邏供關(guān)系，線性構(gòu)造表示數(shù)據(jù)元素Z間為一對(duì)一的關(guān)ZB〕。答案：B〕【例3】以下 不是棧的根本運(yùn)算。〔考點(diǎn)5〕C〕刪除棧頂元素

將棧置為空棧解析：棧的根本運(yùn)算有：入棧，出?！矂h除棧頂元索〕，滿、提取棧頂元素等，對(duì)棧的操作都是在棧頂進(jìn)展的。答案：D〕【例4】鏈表不具備的特點(diǎn)是 。〔考點(diǎn)6〕C〕不必事先估量存儲(chǔ)空間

D〕所需空間與其長(zhǎng)度成正比A〕。答案：A〕【例5】己知某二叉樹(shù)的后序遍歷序列是DACBE,屮序遍歷序列是DEBAC,則它的前序遍歷序列是 o〔考點(diǎn)8〕A〕ACBED

B〕DEABC解析：后序遍歷的挨次是〃左了?樹(shù)一右了樹(shù)一根結(jié)點(diǎn)〃；中序遍歷挨次是〃左了樹(shù)一根結(jié)點(diǎn)一右了樹(shù)〃；前序遍歷挨次是〃根結(jié)點(diǎn)一左了樹(shù)一右了樹(shù)〃。依據(jù)各種遍歷算法，不難得出前序遍歷序EDBACoD〕。答案：D〕【例6】設(shè)有一個(gè)已按各元素的值扌非好序的線性表〔長(zhǎng)度大于2〕,對(duì)給定的值k,分別用挨次杳找法和二分查找法查找一個(gè)與k相等的元索，比較的次數(shù)分別是S和b,在杳找不成功的狀況下，S和b的關(guān)系是 。〔考點(diǎn)9〕A〕s=b B〕s>b C〕s<b s2b解析：對(duì)于挨次杳找，查找不成功時(shí)和給定關(guān)鍵字比較的次數(shù)為n+1。二分杏找杏找不成功的關(guān)鍵字比較次數(shù)為[log2n]+lon$2n+l>[log2n]+1。答案：B〕【例7】在快速排序過(guò)程中，每次劃分，將被劃分的表〔或子表〕分成左、右兩個(gè)子表,考慮這兩個(gè)了表，以下結(jié)論肯定正確的選項(xiàng)是 ?！部键c(diǎn)11〕左、右兩個(gè)子表都已備自排好序左邊了表屮的元素都不大于右邊了表屮的元素C〕左邊子表的長(zhǎng)度小于右邊子表的長(zhǎng)度D〕左、右兩個(gè)子表屮元素的平均值相等解析:快速排序根本思想是:任取待排序表屮的某個(gè)元素作為基準(zhǔn)〔一般取第一個(gè)元素〕答案：B〕二、填空題【例1】問(wèn)題處理方案的正確而完整的描述稱為 o〔考點(diǎn)1〕解析：計(jì)算機(jī)解題的過(guò)程實(shí)際上是在實(shí)施某種算法，這種算法稱為計(jì)算機(jī)算法。答案：算法【例2】一個(gè)空的數(shù)據(jù)構(gòu)造是按線性構(gòu)造處理的，則屬于 ?！部键c(diǎn)4〕的運(yùn)算是按線性構(gòu)造來(lái)處理的，則屬于線性構(gòu)造，否則屬于非線性構(gòu)造。答案：線性構(gòu)造【例3】設(shè)樹(shù)T的度為4,其屮度為1、2、3和4的結(jié)點(diǎn)的個(gè)數(shù)分別為4、2、1、1,則T中葉子結(jié)點(diǎn)的個(gè)數(shù)為 ?！部键c(diǎn)7〕解析：依據(jù)樹(shù)的性質(zhì)：樹(shù)的結(jié)點(diǎn)數(shù)等于全部結(jié)點(diǎn)的度與對(duì)應(yīng)的結(jié)點(diǎn)個(gè)數(shù)乘積Z和加1。1X4+2X2+3X1+4X1+1=16。葉了結(jié)點(diǎn)數(shù)目等于樹(shù)結(jié)點(diǎn)總數(shù)減去度不016〔4+2+1+1〕=8。答案:8【例4】二分法查找的存儲(chǔ)構(gòu)造僅限于 且是有序的?！部键c(diǎn)10〕表必需用挨次存儲(chǔ)構(gòu)造,且表屮元素必需按關(guān)鍵字有序〔升序或降序均可〕。答案：挨次存儲(chǔ)構(gòu)造第2 章程序設(shè)計(jì)根底的原則、面對(duì)對(duì)象方法的根本概念，讀者應(yīng)對(duì)此局部進(jìn)展重點(diǎn)學(xué)習(xí)。具體重點(diǎn)學(xué)習(xí)學(xué)問(wèn)點(diǎn)：構(gòu)造化稈序設(shè)計(jì)方法的四個(gè)原則對(duì)象、類、消息、繼承的概念、類與實(shí)例的區(qū)分2.1 構(gòu)造化程序設(shè)計(jì)1構(gòu)造化程序設(shè)計(jì)的原則考試鏈接：130%,2分，此考點(diǎn)為識(shí)記內(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)造化程序設(shè)計(jì)方法的主要原則goto語(yǔ)句。?疑難解答：如何進(jìn)展自頂向下設(shè)計(jì)方法？多的細(xì)節(jié)，先從最上層總目標(biāo)開(kāi)頭設(shè)計(jì)，逐步使問(wèn)題具體化。2.2 面對(duì)對(duì)象的程序設(shè)計(jì)2面對(duì)對(duì)象方法的根本概念考試鏈接：270%,主要是以填空題的形式消滅2分，此考點(diǎn)為重點(diǎn)識(shí)記內(nèi)容，讀者應(yīng)當(dāng)識(shí)記幾個(gè)根本要素的定義、對(duì)象的特征以及消息、繼承、類的定義。誤區(qū)警示：語(yǔ)時(shí)，必需是指一個(gè)具體的對(duì)象。面對(duì)對(duì)象方法涵蓋對(duì)象及對(duì)象屬性與方法、類、繼承、多態(tài)性幾個(gè)根本要素。對(duì)象通常把對(duì)對(duì)象的操作也稱為方法或效勞。值應(yīng)當(dāng)指的是純粹的數(shù)據(jù)值，而不能指對(duì)彖。操作描述了對(duì)象執(zhí)行的功能，假設(shè)通過(guò)信息的傳遞，還可以為其他對(duì)彖使用。對(duì)象具有如下特征：標(biāo)識(shí)惟一性、分類性、多態(tài)性、封裝性、模塊獨(dú)立性。類和實(shí)例一個(gè)對(duì)彖則是其對(duì)應(yīng)類的一個(gè)實(shí)例。消息流和掌握流。一個(gè)消息由三局部組成：接收消息的對(duì)象的名稱、消息標(biāo)識(shí)符〔消息名〕繼承廣義地說(shuō)，繼承是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義它們。多重繼承是指，一個(gè)類允許有多個(gè)父類。多態(tài)性該現(xiàn)象稱為多態(tài)性。?疑難解答：能舉一下現(xiàn)實(shí)中的對(duì)象及其屬性和操作嗎？一輛汽車是一個(gè)對(duì)象，它包含了汽車的屬性〔如顏色、型號(hào)等〕及其操作〔如啟動(dòng)、剎車等〕。一個(gè)窗口是對(duì)象，它包含了窗口的屬性〔如大小、顏色等〕及其操作〔如翻開(kāi)、關(guān)閉等〕。2.3 例題詳解一、選擇題【例1】構(gòu)造化程序設(shè)計(jì)方法提出于 ?！部键c(diǎn)1〕A〕C〕2070年月

2050年月B〕2060年月D〕2080年月解析：20卄t紀(jì)70年月提出了“構(gòu)造化程序設(shè)計(jì)〔stnicturedprogramming〕“的思想和方法。構(gòu)造化程序設(shè)計(jì)方法引入了工程化思想和構(gòu)造化思想，使大型軟件的開(kāi)發(fā)和編程得到了極大的改善。答案：C〕【例2】構(gòu)造化程序設(shè)計(jì)方法的主要原則有以下4項(xiàng)，不正確的選項(xiàng)是 ?！部键c(diǎn)1〕C〕模塊化

逐步求精D〕goto語(yǔ)句解析：構(gòu)造化程序設(shè)計(jì)方法的主要原則為：H頂向下：即先考慮總體，后考慮細(xì)節(jié)；先考慮全局目標(biāo)，后考慮局部目標(biāo)。逐步求精：對(duì)簡(jiǎn)單問(wèn)題，應(yīng)設(shè)計(jì)一些了目標(biāo)作過(guò)渡，逐步細(xì)化。模塊化：把稈序要解決的總1=1標(biāo)分解為分1=1標(biāo)，再進(jìn)一步分解為具體的小目goto語(yǔ)句。答案：A〕【例3】面對(duì)對(duì)象的開(kāi)發(fā)方法屮，類與對(duì)象的關(guān)系是 ?！部键c(diǎn)2〕A〕抽象與具體 B〕具體與抽象C〕局部與整體 D〕整體與局部A〕項(xiàng)。答案：A〕【例1】在面對(duì)對(duì)彖方法屮，使用已經(jīng)存在的類定義作為根底建立的類定義，這樣的技術(shù)叫做 0〔考點(diǎn)2〕技術(shù)。已有的類可當(dāng)作基類來(lái)引用，則類相應(yīng)地可當(dāng)作派生類來(lái)引用。答案：繼承【例2】對(duì)象的基木特點(diǎn)包括 、分類性、多態(tài)性、封裝性和模塊獨(dú)立性好等5個(gè)特點(diǎn)?！部键c(diǎn)2〕解用I:對(duì)象具有如卜的基木特點(diǎn)：標(biāo)識(shí)?惟一性。對(duì)象是可區(qū)分的，并且由對(duì)象的內(nèi)在木質(zhì)來(lái)區(qū)分；分類性?？梢詫⒕哂幸粯訉傩院筒僮鞯膶?duì)象抽象成類；多態(tài)性。同一個(gè)操作可以是不同對(duì)象的行為；封裝性。只能看到對(duì)彖的外部特征，無(wú)需知道數(shù)據(jù)的具體構(gòu)造以及實(shí)現(xiàn)操作的算法;案：標(biāo)識(shí)惟一性【例3】對(duì)象依據(jù)所接收的消息而做出動(dòng)作，同樣的消息被不同的對(duì)象所接收時(shí)可能導(dǎo)致完全不同的行為，這種現(xiàn)象稱為 o〔考點(diǎn)2〕答案:多態(tài)性第3 章軟件工程根底軟件設(shè)計(jì)的根本原理，軟件測(cè)試的H的、軟件調(diào)試的基木概念，讀者應(yīng)對(duì)此局部進(jìn)展重點(diǎn)學(xué)習(xí)。具體重點(diǎn)學(xué)習(xí)學(xué)問(wèn)點(diǎn)：軟件的概念、軟件生命周期的概念及各階段所包含的活動(dòng)概要設(shè)計(jì)與具體設(shè)計(jì)的概念、模塊獨(dú)立性及其度量的標(biāo)準(zhǔn)、具體設(shè)計(jì)常用的工具軟件測(cè)試的目的、軟件測(cè)試的4個(gè)步驟、軟件調(diào)試的任務(wù)3.1 軟件工程根本概念1軟件定義與軟件特點(diǎn)考試鏈接：I702分，此考點(diǎn)為識(shí)記內(nèi)容，讀者應(yīng)當(dāng)識(shí)記軟件的定義，特點(diǎn)及其分類。軟件指的是計(jì)算機(jī)系統(tǒng)屮與駛件相互依存的另一局部，包括稈序、數(shù)據(jù)和相關(guān)文檔的完資料?？梢?jiàn)，軟件由兩局部組成：機(jī)器可執(zhí)行的程序和數(shù)據(jù)；機(jī)器不行執(zhí)行的，與軟件開(kāi)發(fā)、運(yùn)行、維護(hù)、使用等有關(guān)的文檔。軟件的特點(diǎn)：〔1〕〔2〕

軟件是規(guī)律實(shí)體，而不是物理實(shí)體，具有抽象性；沒(méi)有明顯的制作過(guò)程，可講行大景的復(fù)制；使用期間不存在磨損、老化問(wèn)題；軟件的開(kāi)發(fā)、運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依靠性；軟件簡(jiǎn)單性高，本錢(qián)昂貴；軟件開(kāi)發(fā)涉及諸多社會(huì)因素。4?段開(kāi)黝段般階段4?段開(kāi)黝段般階段1?件。2軟件工程過(guò)程與軟件生命周期考試鏈接：230%,2分，此考點(diǎn)分析爭(zhēng)論與需求分析、設(shè)計(jì)、實(shí)現(xiàn)、測(cè)試、交付使用以及維護(hù)等活動(dòng)，如圖3—1所示。31軟件生命周期還可以將軟件生命周期分為如上圖所示的軟件定義、軟件開(kāi)發(fā)和軟件運(yùn)行維護(hù)3個(gè)階段。生命周期的主要活動(dòng)階段是：可行性爭(zhēng)論與打算制定、需求分析、軟件設(shè)計(jì)、軟件實(shí)施、軟件測(cè)試及運(yùn)行與維護(hù)。3.2 構(gòu)造化設(shè)計(jì)方法3軟件設(shè)計(jì)的根本概念考試鏈接：370%,2分，此考點(diǎn)為重點(diǎn)把握內(nèi)容，讀者應(yīng)當(dāng)識(shí)彳對(duì)奠塊獨(dú)立性中的耦合性和內(nèi)聚性。誤區(qū)警示：在程序構(gòu)造中，各模塊的內(nèi)聚性越祭，則耦合性越弱。軟件設(shè)計(jì)應(yīng)盡量做到高內(nèi)聚，低耦合，即減弱模塊之間的耦合性和提高模塊內(nèi)的內(nèi)聚性，有利于提高模塊的獨(dú)立性。軟件設(shè)計(jì)的根底從技術(shù)觀點(diǎn)上看，軟件設(shè)計(jì)包括軟件構(gòu)造設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、過(guò)程設(shè)計(jì)。構(gòu)造設(shè)計(jì)定義軟件系統(tǒng)各主要部件Z間的關(guān)系；數(shù)據(jù)設(shè)計(jì)將分析時(shí)創(chuàng)立的模型轉(zhuǎn)化為數(shù)據(jù)構(gòu)造的定義；接口設(shè)計(jì)是描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)Z間以及軟件與人Z間如何通信；過(guò)程設(shè)計(jì)則是把系統(tǒng)構(gòu)造部件轉(zhuǎn)換為軟件的過(guò)程性描述。從工稈治理角度來(lái)看，軟件設(shè)計(jì)分兩步完成：概要設(shè)計(jì)和具體設(shè)計(jì)。庫(kù)模式；的細(xì)節(jié)。軟件設(shè)計(jì)的根本原理抽象：軟件設(shè)計(jì)中考慮模塊化解決方案時(shí)，可以定出多個(gè)抽彖級(jí)別。抽象的層次從概要設(shè)計(jì)到具體設(shè)計(jì)逐步降低。模塊化：模塊是指把一個(gè)待開(kāi)發(fā)的軟件分解成假設(shè)干小的簡(jiǎn)潔的局部。模塊化是指解決一個(gè)簡(jiǎn)單問(wèn)題時(shí)H頂向下逐層把軟件系統(tǒng)劃分成假設(shè)干模塊的過(guò)稈。信息隱蔽：信息隱蔽是指在一個(gè)模塊內(nèi)包含的信息〔過(guò)稈或數(shù)據(jù)〕，對(duì)于不需要這些信息的其他模塊來(lái)說(shuō)是不能訪問(wèn)的。模塊獨(dú)立性：模塊獨(dú)立性是指每個(gè)模塊只完成系統(tǒng)要求的獨(dú)立的了功能，并且與其他件的模塊獨(dú)立內(nèi)聚性越強(qiáng)則該模塊的模塊獨(dú)立性越強(qiáng)。一個(gè)模塊與其他模塊的耦合性越強(qiáng)則該模塊的模塊獨(dú)立性越弱。述的是模塊內(nèi)的功能聯(lián)系。內(nèi)聚有如下種類，它們Z間的內(nèi)聚度由弱到強(qiáng)排列：偶然內(nèi)聚、規(guī)律內(nèi)聚、時(shí)間內(nèi)聚、過(guò)程內(nèi)聚、通信內(nèi)聚、挨次內(nèi)聚、功能內(nèi)聚。耦合性是模塊Z間相互連接的嚴(yán)密稈度的度量。耦合性取決于各個(gè)模塊Z間接口的簡(jiǎn)單度、調(diào)用方式以及哪些信息通過(guò)接口。耦合可以分為以下幾種，它們Z間的耦合度由高到低排列：內(nèi)容耦合、公共耦合、外部耦合、掌握耦合、標(biāo)記耦合、數(shù)據(jù)耦合、非宜接耦合。內(nèi)聚，低耦合，即減弱模塊之間的耦合性和提高模塊內(nèi)的內(nèi)聚性，有利于提高模塊的獨(dú)立性。?性和構(gòu)造化設(shè)計(jì)的原則，非直接耦合是不存在的。4具體設(shè)計(jì)考試鏈接：430%,2分，此考點(diǎn)為識(shí)記內(nèi)容，讀者應(yīng)當(dāng)識(shí)記過(guò)程設(shè)計(jì)包括哪些常用工具。達(dá)表示工具算法和數(shù)據(jù)構(gòu)造的細(xì)節(jié)。具體過(guò)稈設(shè)計(jì)的常用工具有：圖形工具：程序流程圖，N S,PAD,HIPOo表格工具：判定表。語(yǔ)言工具：PDL〔偽碼〕。稈序流稈圖的5種掌握構(gòu)造：挨次型、選擇型、先推斷重復(fù)型、后推斷重復(fù)型和多分支選擇型。方框圖屮僅含5種基木的掌握構(gòu)造，即挨次型、選擇型、多分支選擇型、WHILE重復(fù)型和UNTIL重復(fù)型。PAD圖表示5種根本掌握構(gòu)造，即挨次型、選擇型、多分支選擇型、WHILE重復(fù)型和UNTIL重復(fù)型。過(guò)稈設(shè)計(jì)語(yǔ)言〔PDL〕構(gòu)造化程序設(shè)計(jì)語(yǔ)言，類似編程語(yǔ)言。PDL可以由編程語(yǔ)言轉(zhuǎn)換得到，也可以是特地為過(guò)程描述而設(shè)計(jì)的。?疑難解答：程序流程圖，N-S圖，PAD圖的掌握構(gòu)造的異同點(diǎn)是什么？N-SPADWHILE匝復(fù)WHILE匝復(fù)型、UNTILE型。3 軟件測(cè)試5軟件測(cè)試的目的考試鏈接：570%,主要是以選擇題的形式消滅2分，此考點(diǎn)為理解內(nèi)容，讀者應(yīng)當(dāng)理解測(cè)試是為了覺(jué)察錯(cuò)誤。軟件測(cè)試是在軟件投入運(yùn)行前對(duì)軟件需求、設(shè)計(jì)、編碼的最終審核。其T作量、成木占總工作量、總本錢(qián)的40%以上，而且具有較高的組織治理和技術(shù)難度。軟件測(cè)試是為了覺(jué)察錯(cuò)誤而執(zhí)行程序的過(guò)程；一個(gè)好的測(cè)試用例是能夠覺(jué)察至今尚未覺(jué)察的錯(cuò)誤的用例；一個(gè)成功的測(cè)試是覺(jué)察了至今尚未覺(jué)察的錯(cuò)誤的測(cè)試。6軟件測(cè)試的實(shí)施考試鏈接：630%,主要是以選擇題的形式消滅，分值為2分，此考點(diǎn)為識(shí)記內(nèi)容，讀者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ò)程，主要li的是覺(jué)察與接口有關(guān)的錯(cuò)誤，主要依據(jù)是概要設(shè)計(jì)說(shuō)明書(shū)。集成測(cè)試所設(shè)計(jì)的內(nèi)容包括：軟件單元的接口測(cè)試、全局?jǐn)?shù)據(jù)構(gòu)造測(cè)試、邊界條件和非法輸入的測(cè)試等。集成測(cè)試時(shí)將模塊纟R裝成程序，通常承受兩種方式：非增量方式組裝和增量方式組裝。確認(rèn)測(cè)試的任務(wù)是驗(yàn)證軟件的功能和性能，以及其他特性是否滿足了需求規(guī)格說(shuō)明中確定的備種需求，包括軟件配置是否完全、正確。確認(rèn)測(cè)試的實(shí)施首先運(yùn)用黑盒測(cè)試方法，對(duì)軟件進(jìn)展有效性測(cè)試，即驗(yàn)證被測(cè)軟件是否滿足需求規(guī)格說(shuō)明確認(rèn)的標(biāo)準(zhǔn)。系統(tǒng)測(cè)試是通過(guò)測(cè)試確認(rèn)軟件，作為整個(gè)基于計(jì)算機(jī)系統(tǒng)的一個(gè)元素，與計(jì)算機(jī)硬件、外設(shè)、支撐軟件、數(shù)據(jù)和人員等其他系統(tǒng)元索組合在一起，在實(shí)際運(yùn)行〔使用〕環(huán)境下對(duì)計(jì)算機(jī)系統(tǒng)進(jìn)展一系列的集成測(cè)試和確認(rèn)測(cè)試。系統(tǒng)測(cè)試的具體實(shí)施一般包括：功能測(cè)試、性能測(cè)試、操作測(cè)試、配置測(cè)試、外部接口測(cè)試、安全性測(cè)試等。3.4 軟件的調(diào)試7軟件調(diào)試的根本概念考試鏈接：考點(diǎn)7在筆試考試中，是一個(gè)常?？疾斓膬?nèi)容，在筆試考試中消滅的幾率為70%,主要是以選擇題的形式消滅2分，此考點(diǎn)為重點(diǎn)識(shí)記內(nèi)容，讀者應(yīng)當(dāng)識(shí)記軟件調(diào)試的概念。誤區(qū)警示：程。在對(duì)程序進(jìn)展了成功的測(cè)試Z后將進(jìn)入程序調(diào)試〔通常稱Debug,即排錯(cuò)〕。程序的調(diào)試任務(wù)是診斷和改正程序屮的錯(cuò)誤。調(diào)試主要在開(kāi)發(fā)階段進(jìn)展。二是對(duì)稈序進(jìn)展修改，排解這個(gè)錯(cuò)誤。稈序調(diào)試的根本步驟：位置，找出錯(cuò)誤的內(nèi)在緣由；修改設(shè)計(jì)和代碼，以排解錯(cuò)誤；進(jìn)展冋歸測(cè)試，防上引進(jìn)的錯(cuò)誤。調(diào)試原則可以從以下兩個(gè)方血考慮：確定錯(cuò)誤的性質(zhì)和位置時(shí)的留意事項(xiàng)分析思考與錯(cuò)謀征兆有關(guān)的信息；避開(kāi)死胡同；只把調(diào)試工具當(dāng)作關(guān)心手段來(lái)使用；避免用摸索法，最多只能把它當(dāng)作最終手段。修改錯(cuò)誤原則的過(guò)稈將迫使人們臨時(shí)冋到稈序設(shè)計(jì)階段；修改源代碼稈序，不要轉(zhuǎn)變目標(biāo)代碼。疑難解答：軟件測(cè)試與軟件調(diào)試有何不同？軟件測(cè)試是盡可能多地覺(jué)察軟件屮的錯(cuò)誤，而軟件調(diào)試的任務(wù)是診斷和改正程序中的錯(cuò)誤。軟件測(cè)試貫穿整個(gè)軟件生命周期，調(diào)試主要在開(kāi)發(fā)階段。3.5 例題詳解一、選擇題【例1】對(duì)軟件的特點(diǎn)，下面描述正確的選項(xiàng)是軟件是一種物理實(shí)體軟件在運(yùn)行使用期間不存在老化問(wèn)題

?！部键c(diǎn)1〕軟件開(kāi)發(fā)、運(yùn)行對(duì)計(jì)算機(jī)沒(méi)有依靠性，不受計(jì)算機(jī)系統(tǒng)的限制D〕軟件的生產(chǎn)有一個(gè)明顯的制作過(guò)稈B〕。答案：B〕【例2】以下哪項(xiàng)是軟件生命周期的主要活動(dòng)階段？A〕需求分析 B〕軟件開(kāi)發(fā)C〕軟件確認(rèn) D〕軟件演進(jìn)

〔考點(diǎn)2〕解析：B〕、C〕、D〕A〕【例3】從技術(shù)觀點(diǎn)看，軟件設(shè)計(jì)包括構(gòu)造設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、構(gòu)造設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、構(gòu)造設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、文檔設(shè)計(jì)、構(gòu)造設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、文檔設(shè)計(jì)、

o〔3〕過(guò)程設(shè)計(jì)過(guò)程設(shè)計(jì).程序設(shè)計(jì)解析：技術(shù)角度，要進(jìn)展構(gòu)造、接口、數(shù)據(jù)、過(guò)稈的設(shè)計(jì)。構(gòu)造設(shè)計(jì)是定義系統(tǒng)齊部件關(guān)系，數(shù)據(jù)設(shè)計(jì)是依據(jù)分析模型轉(zhuǎn)化數(shù)據(jù)構(gòu)造，接口設(shè)計(jì)是描述如何通信，過(guò)稈設(shè)計(jì)是把系統(tǒng)構(gòu)造部件轉(zhuǎn)化為軟件的過(guò)程性描述。答案：B〕【例4】以下哪個(gè)是軟件測(cè)試的目的？ C〕覺(jué)察程序中的錯(cuò)誤

〔考點(diǎn)5〕演示程序的正確性解析：關(guān)于測(cè)試目的的根本學(xué)問(wèn)，IEEE的定義是：使用人T或自動(dòng)手段來(lái)運(yùn)行或測(cè)定某個(gè)系C〕。答案：C〕【例5】以下哪個(gè)測(cè)試要對(duì)接口測(cè)試？ ?！部键c(diǎn)6〕C〕驗(yàn)收測(cè)試

集成測(cè)試B〕。答案:B〕【例6】程序調(diào)試的主要任務(wù)是 ?！部键c(diǎn)7〕C〕覺(jué)察錯(cuò)誤

改正錯(cuò)誤B〕【例7】以下哪些不是程序調(diào)試的基木步驟？A〕分析錯(cuò)誤緣由C〕修改設(shè)計(jì)代碼以排解錯(cuò)誤

〔考點(diǎn)7〕B〕錯(cuò)誤定位回歸測(cè)試，防止引入錯(cuò)誤解析：程序調(diào)試的基木步驟：位置，找出錯(cuò)誤的內(nèi)在緣由。修改設(shè)計(jì)和代碼，以排解錯(cuò)誤。進(jìn)展回歸測(cè)試,防止引進(jìn)的錯(cuò)誤。答案：A〕【例對(duì)在修改錯(cuò)誤時(shí)應(yīng)遵循的原則有 ?！部键c(diǎn)7〕A〕留意修改錯(cuò)誤木身而不僅僅是錯(cuò)誤的征兆和表現(xiàn)B〕修改錯(cuò)誤的選項(xiàng)是源代碼而不是目標(biāo)代碼C〕遵循在程序設(shè)計(jì)過(guò)程中的各種方法和原則D〕3個(gè)都是解析：修改錯(cuò)誤原則：在消滅錯(cuò)誤的地方，很可能有別的錯(cuò)誤；誤本身；留意修正一個(gè)錯(cuò)誤的同時(shí)有可能會(huì)引入的錯(cuò)誤；修改錯(cuò)誤的過(guò)稈將迫使人們臨時(shí)冋到程序設(shè)計(jì)階段；修改源代碼程序，不要轉(zhuǎn)變目標(biāo)代碼。答案：D〕二、填空題【例1】軟件設(shè)計(jì)是軟件工程的重要階段，是一個(gè)把軟件需求轉(zhuǎn)換為 點(diǎn)3〕解析：軟件設(shè)計(jì)是軟件丁?稈的重要階段，是一個(gè)把軟件需求轉(zhuǎn)換為軟件表示的過(guò)程。其根本H答案：軟件表示【例2】 是指把一個(gè)待開(kāi)發(fā)的軟件分解成假設(shè)干小的簡(jiǎn)潔的局部。〔考點(diǎn)3〕解析：模塊化是指把一個(gè)待開(kāi)發(fā)的軟件分解成假設(shè)干小的簡(jiǎn)潔的局部。如高級(jí)語(yǔ)言屮的過(guò)程、函數(shù)、子程序等。每個(gè)模塊可以完成一個(gè)特定的子功能，備個(gè)模塊可以按肯定的方法組裝起來(lái)成為一個(gè)整體，從而實(shí)現(xiàn)整個(gè)系統(tǒng)的功能。答案：模塊化【例3】數(shù)據(jù)流圖承受4種符號(hào)表示 、數(shù)據(jù)源點(diǎn)和終點(diǎn)、數(shù)據(jù)流向和數(shù)據(jù)加工?！?〕其屮，用箭頭表示數(shù)據(jù)流向，用圓或者橢圓表示數(shù)據(jù)加工，用雙杠表示數(shù)據(jù)存儲(chǔ)，用方框來(lái)表示數(shù)據(jù)源點(diǎn)和終點(diǎn)。答案：數(shù)據(jù)存儲(chǔ)第4 章數(shù)據(jù)庫(kù)設(shè)計(jì)根底數(shù)據(jù)庫(kù)基木特點(diǎn)，數(shù)據(jù)庫(kù)系統(tǒng)的三級(jí)模式及二級(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ù)治理員的主要工作、數(shù)據(jù)庫(kù)系統(tǒng)階段的特點(diǎn)、數(shù)據(jù)的物理獨(dú)立性及規(guī)律獨(dú)立性、數(shù)據(jù)統(tǒng)一治理與掌握、三級(jí)模式及兩級(jí)映射的概念數(shù)據(jù)模型3個(gè)描述內(nèi)容、E-R模型的概念及ME-R圖表示法、關(guān)系操縱、關(guān)系模型三類數(shù)據(jù)約束關(guān)系模型的根本操作、關(guān)系代數(shù)屮的擴(kuò)大運(yùn)算數(shù)據(jù)庫(kù)設(shè)計(jì)生命周期法的4個(gè)階段4.1 數(shù)據(jù)庫(kù)系統(tǒng)的根本概念1數(shù)據(jù)、數(shù)據(jù)庫(kù)、數(shù)據(jù)庫(kù)治理系統(tǒng)考試鏈接：考點(diǎn)1在筆試考試中，是一個(gè)常?？疾斓膬?nèi)容，在筆試考試中消滅的機(jī)率為70%,主要是以選擇題的形式消滅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)記錄。并存放于統(tǒng)一的存儲(chǔ)介質(zhì)內(nèi)，是多種應(yīng)用數(shù)據(jù)的集成，并可被各個(gè)應(yīng)用程序所共享。數(shù)據(jù)庫(kù)治理系統(tǒng)(DBMS,DatabaseManagementSystem)是數(shù)據(jù)庫(kù)的機(jī)構(gòu)，它是一種系統(tǒng)軟整性、安全性定義和檢杳、數(shù)據(jù)庫(kù)的并發(fā)掌握與故障恢復(fù)、數(shù)據(jù)的效勞?？v語(yǔ)言、數(shù)據(jù)掌握語(yǔ)言。2數(shù)據(jù)庫(kù)系統(tǒng)的進(jìn)展考試鏈接：230%,2分，此考點(diǎn)為識(shí)記內(nèi)容，讀者還應(yīng)當(dāng)留意各個(gè)階段的特點(diǎn)。3個(gè)階段，見(jiàn)表4-1各階段特點(diǎn)的具體說(shuō)明人工它理階段門(mén)人工它理階段門(mén)文件系統(tǒng)附段-J應(yīng)用背累q科學(xué)計(jì)算“科學(xué)計(jì)算.言理?碩件背彙。無(wú)直接存取存儲(chǔ)設(shè)備?KB-大容量磁盤(pán)卩*沒(méi)襯拯作鬲統(tǒng)“育數(shù)卅陣治理系扯Q處理方或?批處理?JT批處理?聯(lián)機(jī)實(shí)旳處理、分布處理.批處理「魏握的■理育?用戶〔程序貝〕卩文件柚B!向的對(duì)食》M-S用程序?熹一應(yīng)用》現(xiàn)實(shí)世界“數(shù)覓的共無(wú)共草?冗余度大門(mén)共草性菱?咒余度大卩共草性高，冗余度小卩旦有髙廈的物理獨(dú)立性和肯定的數(shù)據(jù)的獨(dú)文性J 不獨(dú)丄完全依較干程序，邏綺獨(dú)立性心軸構(gòu)造化?記錄內(nèi)有構(gòu)造、整體無(wú)構(gòu)造?整體構(gòu)造化，用數(shù)據(jù)模型描述卩由數(shù)據(jù)庫(kù)首理系統(tǒng)供給數(shù)幄安全數(shù)據(jù)湮制力量?〉應(yīng)用程序自己桎制?”應(yīng)用程序自己疫制?性、疣整性、并發(fā)栓制和恢復(fù)龍力?3數(shù)據(jù)庫(kù)系統(tǒng)的根本特點(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ú)立性兩種。物理獨(dú)立性：指用戶的應(yīng)用稈序與存儲(chǔ)在磁盤(pán)上的數(shù)據(jù)庫(kù)屮數(shù)據(jù)是相互獨(dú)立的。當(dāng)數(shù)據(jù)的物理構(gòu)造〔包括存儲(chǔ)構(gòu)造、存取方式等〕取方式轉(zhuǎn)變等，應(yīng)用程序都不用轉(zhuǎn)變。規(guī)律獨(dú)立性：指用戶的應(yīng)用程序與數(shù)據(jù)庫(kù)的規(guī)律構(gòu)造是相互獨(dú)立的。數(shù)據(jù)的規(guī)律構(gòu)造數(shù)據(jù)統(tǒng)一治理與掌握主要包括以下3個(gè)方曲：數(shù)據(jù)的完整性檢杏、數(shù)據(jù)的安全性保護(hù)和并發(fā)控制。4數(shù)據(jù)庫(kù)系統(tǒng)的內(nèi)部構(gòu)造體系考試鏈接：430%,2分，此考點(diǎn)為識(shí)記內(nèi)容，讀者還應(yīng)當(dāng)理解三級(jí)模式及兩級(jí)映射的定義。誤區(qū)警示：一個(gè)數(shù)據(jù)庫(kù)只有一個(gè)概念模式。一個(gè)概念模式可以有假設(shè)干個(gè)外模式。三級(jí)模式都有幾種名稱，讀者應(yīng)當(dāng)熟記每個(gè)模式的另一些名稱。3級(jí)模式概念模式，也稱規(guī)律模式，是對(duì)數(shù)據(jù)庫(kù)系統(tǒng)中全局?jǐn)?shù)據(jù)規(guī)律構(gòu)造的描述，是全體用戶〔應(yīng)用〕公共數(shù)據(jù)視圖。一個(gè)數(shù)據(jù)庫(kù)只有一個(gè)概念模式。外模式，外模式也稱了模式，它是數(shù)據(jù)庫(kù)用戶能夠觀察和使用的局部數(shù)據(jù)的規(guī)律構(gòu)造用有關(guān)的數(shù)據(jù)的規(guī)律表示。一個(gè)概念模式可以有假設(shè)干個(gè)外模式。內(nèi)模式，內(nèi)模式又稱物理模式，它給出了數(shù)據(jù)庫(kù)物理存儲(chǔ)構(gòu)造與物理存取方法。?它反映了設(shè)計(jì)者的數(shù)據(jù)全局規(guī)律要求，而外模式處于最外層，它反映了用戶對(duì)數(shù)據(jù)的要求。數(shù)據(jù)庫(kù)系統(tǒng)的兩級(jí)映射兩級(jí)映射保證了數(shù)據(jù)庫(kù)系統(tǒng)中數(shù)據(jù)的獨(dú)立性。物理存儲(chǔ)構(gòu)造間的對(duì)應(yīng)關(guān)系；外模式到概念模式的映射。概念模式是一個(gè)全局模式而外模式是用戶的局部模式。一個(gè)概念模式屮可以定義多個(gè)外模式，而每個(gè)外模式是概念模式的一個(gè)基木視圖。?疑難解答：數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)的構(gòu)造是什么樣的？7統(tǒng)工、應(yīng)用開(kāi)發(fā)工具軟件、數(shù)據(jù)庫(kù)治理系統(tǒng)、操作系統(tǒng)、換件。4.2 數(shù)據(jù)模型5數(shù)據(jù)模型的根本概念考試鏈接：570%,2分，此3個(gè)局部。觀對(duì)象抽象為概念模型；把概念模型轉(zhuǎn)換為某一DBMS支持的數(shù)據(jù)模型。數(shù)據(jù)模型所描述的內(nèi)容有3個(gè)局部，它們是數(shù)據(jù)構(gòu)造、數(shù)據(jù)操作與數(shù)據(jù)約朿。6E-R模型考試鏈接：考點(diǎn)、630%,4分，此考點(diǎn)為理解內(nèi)容，讀E?R模型的根本概念是客觀存在的且又能相互區(qū)分的事物。屬性：現(xiàn)實(shí)世界屮事物均有一些特性，這些特性可以用屬性來(lái)表示。碼：唯一標(biāo)識(shí)實(shí)體的屬性集稱為碼。域：屬性的収值范圍稱為該屬性的域。聯(lián)系：在現(xiàn)實(shí)世界屮事物間的關(guān)聯(lián)稱為聯(lián)系。聯(lián)系、一對(duì)多或多對(duì)一聯(lián)系、多對(duì)多。E?R模型的圖示法E?RE?R圖來(lái)表示。實(shí)體表示法：在E?R圖屮用矩形表示實(shí)體無(wú)在矩形內(nèi)寫(xiě)上i亥實(shí)體集的名字。屬性表示法：在E?R圖屮用橢圓形表示屬性，在橢圓形內(nèi)寫(xiě)上該屬性的名稱。聯(lián)系表示法：在E?R圖屮用菱形表示聯(lián)系，菱形內(nèi)寫(xiě)上聯(lián)系名。7層次模型考試鏈接：730%,2分，此考點(diǎn)為識(shí)記內(nèi)容，讀滿足下面兩個(gè)條件的根本層次聯(lián)系的集合為層次模型。有且只有一個(gè)結(jié)點(diǎn)沒(méi)有雙親結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)稱為根結(jié)點(diǎn)；除根結(jié)點(diǎn)以外的其他結(jié)點(diǎn)有且僅有一個(gè)雙親結(jié)點(diǎn)。8關(guān)系模型考試鏈接：70%,主要是以選擇題的形式消滅,27共性質(zhì)，識(shí)記三類數(shù)據(jù)約束。誤區(qū)警示：算時(shí)，把*符合條件的記錄過(guò)濾，產(chǎn)生錯(cuò)誤的結(jié)果。關(guān)系模型承受二維表來(lái)表示，二維表一般滿足下血7共性質(zhì)：〔1〕二維表屮元組個(gè)數(shù)是有限的一元組個(gè)數(shù)有限性；〔2〕

二維表屮元組均不一樣一元組的唯一性；二維表中元組的次序可以任意交換一元組的次序無(wú)關(guān)性；二維表中元纟H?的重量是不行分割的基木數(shù)據(jù)項(xiàng)一元組重量的原了性；二維表中屬性名各不一樣一屬性名唯一性；二維表屮屬性與次序無(wú)關(guān)，可任意交換一屬性的次序無(wú)關(guān)性；二維表屬性的重量具有與該屬性一樣的值域一重量值域的統(tǒng)一性。為表的侯選碼或侯選健。從二維表的全部侯選鍵選取一個(gè)作為用戶使用的鍵稱為主鍵或主碼。表ABUA的外鍵或外碼。關(guān)系操縱：數(shù)據(jù)查詢、數(shù)據(jù)刪除、數(shù)據(jù)插入、數(shù)據(jù)修改。整性約束。?但是一個(gè)二維表不肯定是一個(gè)關(guān)系。?疑難解答：E-R圖是如何向關(guān)系模式轉(zhuǎn)換的？E-R系的屬性。實(shí)體集也可以轉(zhuǎn)換成關(guān)系。4.3 關(guān)系代數(shù)9關(guān)系代數(shù)考試鏈接：930%,2分，此考點(diǎn)重點(diǎn)把握理解內(nèi)容,讀者應(yīng)當(dāng)理解關(guān)系模型的根本操作以及關(guān)系代數(shù)的幾種運(yùn)算。誤區(qū)警示：時(shí)，把符合條件的記錄過(guò)濾，產(chǎn)生錯(cuò)誤的結(jié)果。關(guān)系模型的根本操作關(guān)系模型的根本操作：插入、刪除、修改和查詢。其屮查詢包含如下運(yùn)算：①投影運(yùn)算。從R屮選擇出假設(shè)干屬性列組成的關(guān)系。②選擇運(yùn)算。選擇運(yùn)算是一個(gè)一元運(yùn)算，關(guān)系R通過(guò)選擇運(yùn)算〔并由該運(yùn)算給出所選擇的規(guī)律條件〕F,RF的選擇運(yùn)算可寫(xiě)成：oF〔R〕③笛卡爾積運(yùn)算。設(shè)有nRmS,p、qRS經(jīng)RXS,n+mpXq,與S的有序組組合而成。n+m元關(guān)系，元組個(gè)數(shù)是pXq,這是常?；煜?。關(guān)系代數(shù)中的擴(kuò)大運(yùn)算RS經(jīng)交運(yùn)算后所得到的關(guān)系是由那些既在R內(nèi)又在S內(nèi)的有序組所RASo除運(yùn)算假設(shè)將笛卡爾積運(yùn)算看作乘運(yùn)算的話，除運(yùn)算就是它的逆運(yùn)算。當(dāng)關(guān)系T=RXS時(shí)，則可將除運(yùn)算寫(xiě)成：T4-R=ST/R=SSTR的商。除法運(yùn)算不是基木運(yùn)算，它可以由基木運(yùn)算推導(dǎo)而出。H然連接運(yùn)算連接運(yùn)算又可稱為B運(yùn)算，這是一種二元運(yùn)算，通過(guò)它可以將兩個(gè)關(guān)系合并成一個(gè)大關(guān)系。設(shè)R、Si〔〕j,iR屮的域，jS屮的域，0含義同前。則可以將R、S在i,jB連接記為：R|x|SiOj在B連接中假設(shè)。為就稱此連接為等值連接，否則稱為不等值連接；如e為〃時(shí)稱為小于連接；如〔〕為“〉〃時(shí)稱為大于連接。自然連接〔naturaljoin〕是一種特別的等值連接，它滿足下面的條件：①兩關(guān)系間有公共域；②通過(guò)公共域的等值進(jìn)展連接。R、S,RA],A2，…，An,SB[,B2，…，Bm,并且，A；i,Ai2，…,Aij,3,B,…，Bj分別為一樣域，此時(shí)它們自然連接可記為：2R|x|S自然連接的含義可用下式表示：R|X|S=兀Al，A2-……An.Bj+l,……Bm〔0AiI=B1AAi2=B2A-AAij=Bj〔RXS〕〕?疑難解答：連接與自然連接的不同之處在什么？算。4.4 數(shù)據(jù)庫(kù)設(shè)計(jì)與治理10數(shù)據(jù)庫(kù)設(shè)計(jì)概述考試鏈接：1030%,2分，此考點(diǎn)為識(shí)記內(nèi)容，讀T4個(gè)階段以及它們相應(yīng)的任務(wù)。數(shù)據(jù)庫(kù)設(shè)計(jì)屮有兩種方法，甌向數(shù)據(jù)的方法和甌向過(guò)程的方法：面對(duì)數(shù)據(jù)的方法是以信息需求為主，兼顧處理需求;面對(duì)過(guò)程的方法是以處理需求為主,兼顧信息需求。由于數(shù)據(jù)在系統(tǒng)屮穩(wěn)定性高，數(shù)據(jù)已成為系統(tǒng)的核心，因此面對(duì)數(shù)據(jù)的設(shè)計(jì)方法已成為主流。數(shù)據(jù)庫(kù)設(shè)計(jì)日前一般承受生命周期法，馬上整個(gè)數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)的開(kāi)發(fā)分解成目標(biāo)獨(dú)立的假設(shè)干4個(gè)階段。4個(gè)階段的成果分別是什么？4個(gè)階段，它們的成果分別是需求說(shuō)明書(shū)、概念數(shù)據(jù)模型、規(guī)律數(shù)據(jù)模型和數(shù)據(jù)庫(kù)內(nèi)模式。4.4 例題詳解一、選擇題【例1】對(duì)于數(shù)據(jù)庫(kù)系統(tǒng)，負(fù)責(zé)定義數(shù)據(jù)庫(kù)內(nèi)容，打算存儲(chǔ)構(gòu)造和存取策略及安全授權(quán)等工作的