第一章 數(shù)據(jù)結(jié)構(gòu)與算法

一.算法的基本概念
計(jì)算機(jī)解題的過程實(shí)際上是在實(shí)施某種算法，這種算法稱為計(jì)算機(jī)算法。
1.算法的基本特征：可行性，確定性，有窮性，擁有足夠的情報(bào)。
2.算法的基本要素：算法中對數(shù)據(jù)的運(yùn)算和操作、算法的控制結(jié)構(gòu)。
3.算法設(shè)計(jì)的基本方法：列舉法、歸納法、遞推、遞歸、減半遞推技術(shù)、回溯法。
4.算法設(shè)計(jì)的要求：正確性、可讀性、健壯性、效率與低存儲量需求

二.算法的復(fù)雜度
1.算法的時(shí)間復(fù)雜度：指執(zhí)行算法所需要的計(jì)算工作量
2.算法的空間復(fù)雜度：執(zhí)行這個(gè)算法所需要的內(nèi)存空間

三.數(shù)據(jù)結(jié)構(gòu)的定義
1.數(shù)據(jù)的邏輯結(jié)構(gòu)：反映數(shù)據(jù)元素之間的關(guān)系的數(shù)據(jù)元素集合的表示。數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合、線形結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)四種。
2.數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲空間種的存放形式稱為數(shù)據(jù)的存儲結(jié)構(gòu)。常用的存儲結(jié)構(gòu)有順序、鏈接、索引等存儲結(jié)構(gòu)。

四.數(shù)據(jù)結(jié)構(gòu)的圖形表示：
在數(shù)據(jù)結(jié)構(gòu)中，沒有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn)；沒有后件的結(jié)點(diǎn)成為終端結(jié)點(diǎn)。插入和刪除是對數(shù)據(jù)結(jié)構(gòu)的兩種基本運(yùn)算。還有查找、分類、合并、分解、復(fù)制和修改等。

五.線性結(jié)構(gòu)和非線性結(jié)構(gòu)
根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。
線性結(jié)構(gòu)：非空數(shù)據(jù)結(jié)構(gòu)滿足：有且只有一個(gè)根結(jié)點(diǎn)；每個(gè)結(jié)點(diǎn)最多有一個(gè)前件，最多只有一個(gè)后件。非線性結(jié)構(gòu)：如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，稱之為非線性結(jié)構(gòu)。
常見的線性結(jié)構(gòu)：線性表、棧、隊(duì)列

六.線性表的定義
線性表是n 個(gè)元素構(gòu)成的有限序列（A1，A2，A3……）。表中的每一個(gè)數(shù)據(jù)元素，除了第一個(gè)以外，有且只有一個(gè)前件。除了最后一個(gè)以外有且只有一個(gè)后件。即線性表是一個(gè)空表，或可以表示為（a1,a2,……an）, 其中ai(I=1,2,……n)是屬于數(shù)據(jù)對象的元素，通常也稱其為線性表中的一個(gè)結(jié)點(diǎn)。
非空線性表有如下一些特征：
（1）有且只有一個(gè)根結(jié)點(diǎn)a1,它無前件；
（2）有且只有一個(gè)終端結(jié)點(diǎn)an，它無后件；
（3）除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且只有一個(gè)后件。線性表中結(jié)點(diǎn)的個(gè)數(shù)n稱為線性表的長度。當(dāng)n=0時(shí)稱為空表。

七.線性表的順序存儲結(jié)構(gòu)
線性表的順序表指的是用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。
線性表的順序存儲結(jié)構(gòu)具備如下兩個(gè)基本特征：
1.線性表中的所有元素所占的存儲空間是連續(xù)的；
2.線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。
即線性表邏輯上相鄰、物理也相鄰，則已知第一個(gè)元素首地址和每個(gè)元素所占字節(jié)數(shù)，則可求出任一個(gè)元素首地址。
假設(shè)線性表的每個(gè)元素需占用K個(gè)存儲單元，并以所占的第一個(gè)單元的存儲地址作為數(shù)據(jù)元素的存儲位置。則線性表中第i+1個(gè)數(shù)據(jù)元素的存儲位置LOC(ai+1)和第i個(gè)數(shù)據(jù)元素的存儲位置LOC(ai)之間滿足下列關(guān)系:
LOC(ai+1)=LOC(ai)+K
LOC(ai)=LOC(a1)+(i-1)*K???? ①
其中，LOC(a1)是線性表的第一個(gè)數(shù)據(jù)元素a1的存儲位置，通常稱做線性表的起始位置或基地址。
因?yàn)樵陧樞虼鎯Y(jié)構(gòu)中，每個(gè)數(shù)據(jù)元素地址可以通過公式①計(jì)算得到，所以線性表的順序存儲結(jié)構(gòu)是隨機(jī)存取的存儲結(jié)構(gòu)。
在線性表的順序存儲結(jié)構(gòu)下，可以對線性表做以下運(yùn)算：
插入、刪除、查找、排序、分解、合并、復(fù)制、逆轉(zhuǎn)

八.順序表的插入運(yùn)算
線性表的插入運(yùn)算是指在表的第I個(gè)位置上，插入一個(gè)新結(jié)點(diǎn)x，使長度為n的線性表（a1,a2 …ai…an）變成長度為n+1的線性表(a1,a2…x,ai…an).
該算法的時(shí)間主要花費(fèi)在循環(huán)的結(jié)點(diǎn)后移語句上，執(zhí)行次數(shù)是n-I+1。
當(dāng)I=n+1,最好情況，時(shí)間復(fù)雜度o(1) 當(dāng)I=1, 最壞情況，時(shí)間復(fù)雜度o(n)
算法的平均時(shí)間復(fù)雜度為o(n)

九.順序表的刪除運(yùn)算
線性表的刪除運(yùn)算是指在表的第I個(gè)位置上，刪除一個(gè)新結(jié)點(diǎn)x，使長度為n的線性表（a1,a2 …ai…an）變成長度為n-1的線性表(a1,a2…ai-1,ai+1…an).
當(dāng)I=n,時(shí)間復(fù)雜度o(1),當(dāng)I=1,時(shí)間復(fù)雜度o(n) ,平均時(shí)間復(fù)雜度為o(n)

十.棧及其基本運(yùn)算
1.什么是棧？ 棧實(shí)際上也是一個(gè)線性表，只不過是一種特殊的線性表。棧是只能在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，通常稱插入、刪除這一端為棧頂（TOP），另一端為棧底（BOTTOM）。當(dāng)表中沒有元素時(shí)稱為空棧。棧頂元素總是后被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入的元素，從而也是最后才能被刪除的元素。
假設(shè)棧S=（a1,a2,a3,……an），則a1 稱為棧底元素，an稱為棧頂元素。棧中元素按a1,a2,a3……an的次序進(jìn)棧，退棧的第一個(gè)元素應(yīng)該是棧頂元素。即后進(jìn)先出。
2.棧的順序存儲及其運(yùn)算
用S（1：M）作為棧的順序存儲空間。M為棧的最大容量。
棧的基本運(yùn)算有三種：入棧、退棧與讀棧頂元素。
入棧運(yùn)算：在棧頂位置插入一個(gè)新元素。
首先將棧頂指針進(jìn)一（TOP+1），然后將新元素插入到棧頂指針指向的位置。
退棧運(yùn)算：指取出棧頂元素并賦給一個(gè)指定的變量。
首先將棧頂元素賦給一個(gè)指定的變量，然后將棧頂指針退一（TOP-1）
讀棧頂元素：將棧頂元素賦給一個(gè)指定的變量。棧頂指針不會(huì)改變。

十一.隊(duì)列及其基本運(yùn)算
1.什么是隊(duì)列
隊(duì)列是只允許在一端刪除，在另一端插入的順序表，允許刪除的一端叫做對頭，允許插入的一端叫做對尾。
隊(duì)列的修改是先進(jìn)先出。往隊(duì)尾插入一個(gè)元素成為入隊(duì)運(yùn)算。從對頭刪除一個(gè)元素稱為退隊(duì)運(yùn)算。
2.循環(huán)隊(duì)列及其運(yùn)算
在實(shí)際應(yīng)用中，隊(duì)列的順序存儲結(jié)構(gòu)一般采用循環(huán)隊(duì)列的形式。所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間。在循環(huán)隊(duì)列中，，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用排頭指針front指向排頭元素的前一個(gè)位置，因此，從排頭指針front指向的后一個(gè)位置直到隊(duì)尾指針 rear指向的位置之間所有的元素均為隊(duì)列中的元素。
在實(shí)際使用循環(huán)隊(duì)列時(shí)，為了能區(qū)分隊(duì)滿還是隊(duì)列空，通常需要增加一個(gè)標(biāo)志S：
隊(duì)列空，則S=0，rear=front=m???? 隊(duì)列滿，則S=1，rear=front=m
循環(huán)隊(duì)列主要有兩種基本運(yùn)算：入隊(duì)運(yùn)算和退隊(duì)運(yùn)算
n????? 入隊(duì)運(yùn)算
指在循環(huán)隊(duì)列的隊(duì)尾加入一個(gè)新元素，首先rear=rear+1,當(dāng)rear=m+1時(shí)，置rear=1,然后將新元素插入到隊(duì)尾指針指向的位置。當(dāng)S=1，rear=front,說明隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算，稱為“上溢”。
n????? 退隊(duì)運(yùn)算
指在循環(huán)隊(duì)列的排頭位置退出一個(gè)元素并賦給指定的變量。首先front=front+1,并當(dāng)front=m+1時(shí)，置front=1,然后將排頭指針指向的元素賦給指定的變量。當(dāng)循環(huán)隊(duì)列為空S=0，不能進(jìn)行退隊(duì)運(yùn)算，這種情況成為“下溢”。

十二.線性單鏈表的結(jié)構(gòu)及其基本運(yùn)算
1.線性單鏈表的基本概念
一組任意的存儲單元存儲線性表的數(shù)據(jù)元素，因此，為了表示每個(gè)數(shù)據(jù)元素ai與其直接后繼數(shù)據(jù)元素ai+1之間的邏輯關(guān)系，對數(shù)據(jù)元素ai來說，除了存儲其本身的信息之外，還需存儲一個(gè)指示其直接后繼的信息（即直接后繼的存儲位置）。這兩部分信息組成數(shù)據(jù)元素ai的存儲映象，成為結(jié)點(diǎn)。它包括兩個(gè)域：其中存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域，存儲直接后繼存儲位置的域稱為指針域。指針域中存儲的信息稱做指針或鏈。N個(gè)結(jié)點(diǎn)鏈結(jié)成一個(gè)鏈表，即為線性表(a1, a2,……,an)的鏈?zhǔn)酱鎯Y(jié)構(gòu)。又由于此鏈表的每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，故又稱線性鏈表或單鏈表。
有時(shí)，我們在單鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，稱之為頭結(jié)點(diǎn)，它指向表中第一個(gè)結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲任何信息，也可存儲如線性表的長度等類的附加信息，頭結(jié)點(diǎn)的指針域存儲指向第一個(gè)結(jié)點(diǎn)的指針（即第一個(gè)元素結(jié)點(diǎn)的存儲位置）。
在單鏈表中，取得第I個(gè)數(shù)據(jù)元素必須從頭指針出發(fā)尋找，因此，單鏈表是非隨機(jī)存取的存儲結(jié)構(gòu)?? 鏈表的形式：單向，雙向
2.線性單鏈表的存儲結(jié)構(gòu)
3帶鏈
3.帶列的棧與隊(duì)列
棧也是線性表，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。
隊(duì)列也是線性表，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。

十三.線性鏈表的基本運(yùn)算 1.線性鏈表的插入 2.線性鏈表的刪除

十四.雙向鏈表的結(jié)構(gòu)及其基本運(yùn)算

在雙向鏈表的結(jié)點(diǎn)中有兩個(gè)指針域，其一指向直接后繼，另一指向直接前驅(qū)。

十五.循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算
是另一種形式的鏈?zhǔn)酱鎯Y(jié)構(gòu)，它的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)。因此，從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)。

十六.樹的定義
樹是一種簡單的非線性結(jié)構(gòu)。樹型結(jié)構(gòu)的特點(diǎn)：
1.每個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)，沒有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹的根結(jié)點(diǎn)。
2.每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件結(jié)點(diǎn)，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)
3.一個(gè)結(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱為樹的結(jié)點(diǎn)度
4.樹的最大層次稱為樹的深度。

十七.二叉樹的定義及其基本性質(zhì)
1.二叉樹是另一種樹型結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有二棵子樹（即二叉樹中不存在度大于2的結(jié)點(diǎn)），并且，二叉樹的子樹有左右之分，其次序不能任意顛倒。
2.二叉樹的基本性質(zhì)
①在二叉樹的第I層上至多有2i-1個(gè)結(jié)點(diǎn)。
②深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)(k>=1)
③在任意一個(gè)二叉樹中，度為0的結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個(gè)；
④具有n 個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為[log2n]+1。
一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。這種樹的特點(diǎn)是每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)。
3.滿二叉樹與完全二叉樹
滿二叉樹：除最后一層以外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。在滿二叉樹的第K層上有2K-1個(gè)結(jié)點(diǎn)，且深度為M的滿二叉樹右2M-1個(gè)結(jié)點(diǎn)
完全二叉樹：除最后一層以外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。具有N個(gè)結(jié)點(diǎn)的完全二叉樹的深度為[log2n]+1
完全二叉樹總結(jié)點(diǎn)數(shù)為N，
若N為奇數(shù)，則葉子結(jié)點(diǎn)數(shù)為（N+1）/2 若N為偶數(shù)，則葉子結(jié)點(diǎn)數(shù)為N/2
4.二叉樹的存儲結(jié)構(gòu)
二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)

十八.二叉樹的遍歷
就是遵從某種次序，訪問二叉樹中的所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)僅被訪問一次。一般先左后右。
1.前序遍歷DLR 首先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。
2.中序遍歷LDR 首先遍歷左子樹，然后根結(jié)點(diǎn)，最后右子樹
3.后序遍歷LRD 首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)。

十九.順序查找與二分查找
1.順序查找 在兩種情況下只能用順序查找：線性表為無序表、鏈?zhǔn)酱鎯Y(jié)構(gòu)的有序表
2.二分查找 只適用于順序存儲的有序表（從小到大）。
對于長度為N的有序線性表，在最壞情況下，二分查找只需要比較log2N次，而順序查找要比較N次。 排序：指將一個(gè)無序序列整理成按值非遞減順序排列的有序序列。

二十.交換類排序法
冒泡排序與快速排序法屬于交換類的排序方法
1.冒泡排序法 假設(shè)線性表的長度為N，則在最壞的情況下，冒跑排序需要經(jīng)過N/2遍的從前往后的掃描和N/2遍的從后往前的掃描，需要的比較次數(shù)為N（N-1）/2
2.快速排序法

二十一.選擇類排序法 1.簡單選擇排序法 2.堆排序法

二十三.插入類排序法 1.簡單插入排序法2.希爾排序法
?????????? 最壞情況下????? 最好情況下????? 說明
交換排序????? 冒泡排序????? n(n-1)/2??????????? 最簡單的交換排序。在待排序的元素序列基本有序的前提下，效率最高
???? 快速排序????? n(n-1)/2????? O(Nlog2 N)?????
插入排序????? 簡單插入排序????? n(n-1)/2??????????? 每個(gè)元素距其最終位置不遠(yuǎn)時(shí)適用
???? 希爾排序????? O(n1.5)???????????
選擇排序????? 簡單選擇排序????? n(n-1)/2???????????
???? 堆排序????? O(nlog2n)??????????? 適用于較大規(guī)模的線性表

練習(xí)：
1.棧和隊(duì)列的共同特點(diǎn)是（只允許在端點(diǎn)處插入和刪除元素）

2.如果進(jìn)棧序列為e1,e2,e3,e4，則可能的出棧序列是（e2,e4,e3,e1）

3.棧底至棧頂依次存放元素A、B、C、D，在第五個(gè)元素E入棧前，棧中元素可以出棧，則出棧序列可能是（DCBEA）

4.棧通常采用的兩種存儲結(jié)構(gòu)是（線性存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)）

5.下列關(guān)于棧的敘述正確的是（D）
???? A.棧是非線性結(jié)構(gòu)B.棧是一種樹狀結(jié)構(gòu)C.棧具有先進(jìn)先出的特征D.棧有后進(jìn)先出的特征

6.鏈表不具有的特點(diǎn)是（B）A.不必事先估計(jì)存儲空間?????? B.可隨機(jī)訪問任一元素
C.插入刪除不需要移動(dòng)元素????? D.所需空間與線性表長度成正比

7.用鏈表表示線性表的優(yōu)點(diǎn)是（便于插入和刪除操作）

8.在單鏈表中，增加頭結(jié)點(diǎn)的目的是（方便運(yùn)算的實(shí)現(xiàn)）

9.循環(huán)鏈表的主要優(yōu)點(diǎn)是（從表中任一結(jié)點(diǎn)出發(fā)都能訪問到整個(gè)鏈表）

10.線性表L＝（a1,a2,a3,……ai,……an），下列說法正確的是（D）
???? A.每個(gè)元素都有一個(gè)直接前件和直接后件?? B.線性表中至少要有一個(gè)元素
???? C.表中諸元素的排列順序必須是由小到大或由大到小
???? D.除第一個(gè)和最后一個(gè)元素外，其余每個(gè)元素都有一個(gè)且只有一個(gè)直接前件和直接后件

11.線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲單元的地址（D）
A.必須是連續(xù)的 B.部分地址必須是連續(xù)的C.一定是不連續(xù)的 D.連續(xù)不連續(xù)都可以

12.線性表的順序存儲結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)分別是（隨機(jī)存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu)）

13.樹是結(jié)點(diǎn)的集合，它的根結(jié)點(diǎn)數(shù)目是（有且只有1）

14.在深度為5的滿二叉樹中，葉子結(jié)點(diǎn)的個(gè)數(shù)為（31）

15.具有3個(gè)結(jié)點(diǎn)的二叉樹有（5種形態(tài)）

16.設(shè)一棵二叉樹中有3個(gè)葉子結(jié)點(diǎn)，有8個(gè)度為1的結(jié)點(diǎn)，則該二叉樹中總的結(jié)點(diǎn)數(shù)為（13）

17.已知二叉樹后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是（cedba）

18.已知一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF，則該二叉樹的后序遍歷為（DGEBHFCA）

19.若某二叉樹的前序遍歷訪問順序是abdgcefh，中序遍歷訪問順序是dgbaechf，則其后序遍歷的結(jié)點(diǎn)訪問順序是（gdbehfca）

20.數(shù)據(jù)庫保護(hù)分為：安全性控制、 完整性控制 、并發(fā)性控制和數(shù)據(jù)的恢復(fù)。

1. 在計(jì)算機(jī)中，算法是指（解題方案的準(zhǔn)確而完整的描述）

2.在下列選項(xiàng)中，哪個(gè)不是一個(gè)算法一般應(yīng)該具有的基本特征（無窮性）
說明：算法的四個(gè)基本特征是：可行性、確定性、有窮性和擁有足夠的情報(bào)。

3. 算法一般都可以用哪幾種控制結(jié)構(gòu)組合而成（順序、選擇、循環(huán)）

4.算法的時(shí)間復(fù)雜度是指（算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù)）

5. 算法的空間復(fù)雜度是指（執(zhí)行過程中所需要的存儲空間）

6. 算法分析的目的是（分析算法的效率以求改進(jìn)）

7. 下列敘述正確的是（C）
A．算法的執(zhí)行效率與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)
B．算法的空間復(fù)雜度是指算法程序中指令（或語句）的條數(shù)
C．算法的有窮性是指算法必須能在執(zhí)行有限個(gè)步驟之后終止
D．算法的時(shí)間復(fù)雜度是指執(zhí)行算法程序所需要的時(shí)間

8.數(shù)據(jù)結(jié)構(gòu)作為計(jì)算機(jī)的一門學(xué)科，主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算，以及（數(shù)據(jù)的存儲結(jié)構(gòu)）

9. 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的（C）
A．存儲結(jié)構(gòu)?? B．物理結(jié)構(gòu)???? C．邏輯結(jié)構(gòu)???? D．物理和存儲結(jié)構(gòu)

10. 下列敘述中，錯(cuò)誤的是（B）
A．數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率密切相關(guān)
B．數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率無關(guān)
C．數(shù)據(jù)的存儲結(jié)構(gòu)在計(jì)算機(jī)中所占的空間不一定是連續(xù)的
D．一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)

11. 數(shù)據(jù)的存儲結(jié)構(gòu)是指（數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示）

12. 數(shù)據(jù)的邏輯結(jié)構(gòu)是指（反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)）

13. 根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為（線性結(jié)構(gòu)和非線性結(jié)構(gòu)）

14. 下列數(shù)據(jù)結(jié)構(gòu)具有記憶功能的是（C）A．隊(duì)列B．循環(huán)隊(duì)列C．棧D．順序表

15. 下列數(shù)據(jù)結(jié)構(gòu)中，按先進(jìn)后出原則組織數(shù)據(jù)的是（B）
A．線性鏈表?? B．棧??????????? C．循環(huán)鏈表??????? D．順序表

16. 遞歸算法一般需要利用（隊(duì)列）實(shí)現(xiàn)。

17. 下列關(guān)于棧的敘述中正確的是（D）A．在棧中只能插入數(shù)據(jù)B．在棧中只能刪除數(shù)據(jù)
C．棧是先進(jìn)先出的線性表??????????? D．棧是先進(jìn)后出的線性表

18. 棧底至棧頂依次存放元素A、B、C、D，在第五個(gè)元素E入棧前，棧中元素可以出棧，則出棧序列可能是（DCBEA）

19.如果進(jìn)棧序列為e1,e2,e3,e4，則可能的出棧序列是（e2,e4,e3,e1）

20.? 由兩個(gè)棧共享一個(gè)存儲空間的好處是（節(jié)省存儲空間，降低上溢發(fā)生的機(jī)率）

21.? 應(yīng)用程序在執(zhí)行過程中，需要通過打印機(jī)輸出數(shù)據(jù)時(shí)，一般先形成一個(gè)打印作業(yè)，將其存放在硬盤中的一個(gè)指定（隊(duì)列）中，當(dāng)打印機(jī)空閑時(shí)，就會(huì)按先來先服務(wù)的方式從中取出待打印的作業(yè)進(jìn)行打印。

22.下列關(guān)于隊(duì)列的敘述中正確的是（C）A．在隊(duì)列中只能插入數(shù)據(jù) B．在隊(duì)列中只能刪除數(shù)據(jù)?? C．隊(duì)列是先進(jìn)先出的線性表??????????? D．隊(duì)列是先進(jìn)后出的線性表

23.下列敘述中，正確的是（D）A．線性鏈表中的各元素在存儲空間中的位置必須是連續(xù)的
B．線性鏈表中的表頭元素一定存儲在其他元素的前面 C．線性鏈表中的各元素在存儲空間中的位置不一定是連續(xù)的，但表頭元素一定存儲在其他元素的前面 D．線性鏈表中的各元素在存儲空間中的位置不一定是連續(xù)的，且各元素的存儲順序也是任意的

24.下列敘述中正確的是（A）A．線性表是線性結(jié)構(gòu)????? B．棧與隊(duì)列是非線性結(jié)構(gòu)
C．線性鏈表是非線性結(jié)構(gòu)???????????????????????????????? D．二叉樹是線性結(jié)構(gòu)

25. 線性表L＝（a1,a2,a3,……ai,……an），下列說法正確的是（D）
A．每個(gè)元素都有一個(gè)直接前件和直接后件????? B．線性表中至少要有一個(gè)元素
C．表中諸元素的排列順序必須是由小到大或由大到小D．除第一個(gè)元素和最后一個(gè)元素外，其余每個(gè)元素都有一個(gè)且只有一個(gè)直接前件和直接后件

26.線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲單元的地址（連續(xù)不連續(xù)都可以）

27. 鏈表不具有的特點(diǎn)是（B）A．不必事先估計(jì)存儲空間??????????? B．可隨機(jī)訪問任一元素
C．插入刪除不需要移動(dòng)元素??????????? D．所需空間與線性表長度成正比

28. 非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向），滿足（p->next=head）

29.與單向鏈表相比，雙向鏈表的優(yōu)點(diǎn)之一是（更容易訪問相鄰結(jié)點(diǎn)）

30. 在（D）中，只要指出表中任何一個(gè)結(jié)點(diǎn)的位置，就可以從它出發(fā)依次訪問到表中其他所有結(jié)點(diǎn)。A．線性單鏈表??????????? B．雙向鏈表??????????? C．線性鏈表??????????? D．循環(huán)鏈表

31. 以下數(shù)據(jù)結(jié)構(gòu)屬于非線性數(shù)據(jù)結(jié)構(gòu)的是（C）A．隊(duì)列????? B．線性表C．二叉樹????? D．棧

32.樹是結(jié)點(diǎn)的集合，它的根結(jié)點(diǎn)數(shù)目是（有且只有1）

33.具有3個(gè)結(jié)點(diǎn)的二叉樹有（5種形態(tài)）

34. 在一棵二叉樹上第8層的結(jié)點(diǎn)數(shù)最多是（128） 注：2K-1

35. 在深度為5的滿二叉樹中，葉子結(jié)點(diǎn)的個(gè)數(shù)為（16） 注：2n-1

36. 在深度為5的滿二叉樹中，共有（31）個(gè)結(jié)點(diǎn)。 注：2n－1

37.設(shè)一棵完全二叉樹共有699個(gè)結(jié)點(diǎn)，則在該二叉樹中的葉子結(jié)點(diǎn)數(shù)為（350）
說明：完全二叉樹總結(jié)點(diǎn)數(shù)為N，若N為奇數(shù)，則葉子結(jié)點(diǎn)數(shù)為（N+1）/2；若N為偶數(shù)，則葉子結(jié)點(diǎn)數(shù)為N/2。

38. 設(shè)有下列二叉樹，對此二叉樹中序遍歷的結(jié)果是（B）
A．ABCDEF?????
B．DBEAFC
C．ABDECF?????
D．DEBFCA

39.已知二叉樹后序遍歷序列是dabec，中序遍歷序列debac，它的前序遍歷序列是（cedba）

40. 已知一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF，則該二叉樹的后序遍歷為（DGEBHFCA）

41.若某二叉樹的前序遍歷訪問順序是abdgcefh，中序遍歷訪問順序是dgbaechf，則其后序遍歷的結(jié)點(diǎn)訪問順序是（gdbehfca）

42. 串的長度是（串中所含字符的個(gè)數(shù)）

43.設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)位置的運(yùn)算稱做（模式匹配）

44. N個(gè)頂點(diǎn)的連通圖中邊的條數(shù)至少為（N-1）

45.N個(gè)頂點(diǎn)的強(qiáng)連通圖的邊數(shù)至少有（N）

46.對長度為n的線性表進(jìn)行順序查找，在最壞情況下所需要的比較次數(shù)為（N）

47. 最簡單的交換排序方法是（冒泡排序）

48.假設(shè)線性表的長度為n，則在最壞情況下，冒泡排序需要的比較次數(shù)為（n(n-1)/2）

49. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是（冒泡排序）

50. 在最壞情況下，下列順序方法中時(shí)間復(fù)雜度最小的是（堆排序）

51. 希爾排序法屬于（插入類排序）

52. 堆排序法屬于（選擇類排序）

53. 在下列幾種排序方法中，要求內(nèi)存量最大的是（歸并排序）

54.? 已知數(shù)據(jù)表A中每個(gè)元素距其最終位置不遠(yuǎn)，為節(jié)省時(shí)間，應(yīng)采用（直接插入排序）

55. 算法的基本特征是可行性、確定性、 有窮性?? 和擁有足夠的情報(bào)。

1.一個(gè)算法通常由兩種基本要素組成：一是對數(shù)據(jù)對象的運(yùn)算和操作，二是算法的控制結(jié)構(gòu)。

1. 算法的復(fù)雜度主要包括時(shí)間復(fù)雜度和 空間 復(fù)雜度。

2.? 實(shí)現(xiàn)算法所需的存儲單元多少和算法的工作量大小分別稱為算法的空間復(fù)雜度和時(shí)間復(fù)雜度 。

3.所謂數(shù)據(jù)處理是指對數(shù)據(jù)集合中的各元素以各種方式進(jìn)行運(yùn)算，包括插入、刪除、查找、更改等運(yùn)算，也包括對數(shù)據(jù)元素進(jìn)行分析。

4.數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的 數(shù)據(jù)元素 的集合。

5.數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)，線性鏈表屬于 存儲結(jié)構(gòu) 。

6.數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的 邏輯 結(jié)構(gòu)和數(shù)據(jù)的存儲結(jié)構(gòu)。

7. 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的 存儲結(jié)構(gòu) 以及對數(shù)據(jù)的操作運(yùn)算。

8.數(shù)據(jù)元素之間的任何關(guān)系都可以用 前趨和后繼 關(guān)系來描述。

9.數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。

10.常用的存儲結(jié)構(gòu)有順序、鏈接、 索引 等存儲結(jié)構(gòu)。

11. 順序存儲方法是把邏輯上相鄰的結(jié)點(diǎn)存儲在物理位置?? 相鄰 的存儲單元中。

12. 棧的基本運(yùn)算有三種：入棧、退棧與讀棧頂元素 。

13. 隊(duì)列主要有兩種基本運(yùn)算：入隊(duì)運(yùn)算與 退隊(duì)運(yùn)算 。

14. 在實(shí)際應(yīng)用中，帶鏈的棧可以用來收集計(jì)算機(jī)存儲空間中所有空閑的存儲結(jié)點(diǎn)，這種帶鏈的棧稱為 可利用棧 。

15.棧和隊(duì)列通常采用的存儲結(jié)構(gòu)是 鏈?zhǔn)酱鎯晚樞虼鎯?? 。

16.當(dāng)線性表采用順序存儲結(jié)構(gòu)實(shí)現(xiàn)存儲時(shí)，其主要特點(diǎn)是 邏輯結(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲結(jié)構(gòu)中仍相鄰 。

17. 循環(huán)隊(duì)列主要有兩種基本運(yùn)算：入隊(duì)運(yùn)算與退隊(duì)運(yùn)算。每進(jìn)行一次入隊(duì)運(yùn)算，隊(duì)尾指針就 進(jìn)1 。

18.當(dāng)循環(huán)隊(duì)列非空且隊(duì)尾指針等于對頭指針時(shí)，說明循環(huán)隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算。這種情況稱為 上溢?? 。

19.當(dāng)循環(huán)隊(duì)列為空時(shí)，不能進(jìn)行退隊(duì)運(yùn)算，這種情況稱為 下溢 。

20. 在一個(gè)容量為25的循環(huán)隊(duì)列中，若頭指針front=16，尾指針rear=9，則該循環(huán)隊(duì)列中共有 18 個(gè)元素。注：當(dāng)rear<front時(shí)，元素個(gè)數(shù)＝總?cè)萘?#xff0d;（front－rear）；
當(dāng)rear>front時(shí)，元素個(gè)數(shù)＝rear－front。

21. 在一個(gè)容量為15的循環(huán)隊(duì)列中，若頭指針front=6，尾指針rear=9，則該循環(huán)隊(duì)列中共有3 個(gè)元素。

22.順序查找一般是指在 線性表 中查找指定的元素。

23.在計(jì)算機(jī)中存放線性表，一種最簡單的方法是 順序存儲 。

24.在程序設(shè)計(jì)語言中，通常定義一個(gè) 一維數(shù)組 來表示線性表的順序存儲空間。

25.在鏈?zhǔn)酱鎯Ψ绞街?#xff0c;要求每個(gè)結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域，另一部分用于存放指針，稱為 指針域 。其中指針用于指向該結(jié)點(diǎn)的前一個(gè)或

后一個(gè)結(jié)點(diǎn)（即前件或后件）。

26.在 線性單鏈表中 ，每一個(gè)結(jié)點(diǎn)只有一個(gè)指針域，由這個(gè)指針只能找到后繼結(jié)點(diǎn)，但不能找到前驅(qū)結(jié)點(diǎn)。

27. 為了要在線性鏈表中插入一個(gè)新元素，首先要給該元素分配一個(gè) 新結(jié)點(diǎn) ，以便用于存儲該元素的值。

28. 在線性鏈表中刪除一個(gè)元素后，只需要改變被刪除元素所在結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)的 指針域 即可。

29. 用鏈表表示線性表的突出優(yōu)點(diǎn)是 便于插入和刪除操作 。

30. 在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有?? 前件 。

31. 在樹結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱為該結(jié)點(diǎn)的度。葉子結(jié)點(diǎn)的度為 0 。

32. 設(shè)一棵二叉樹中有3個(gè)葉子結(jié)點(diǎn)，8個(gè)度為1的結(jié)點(diǎn)，則該二叉樹中總的結(jié)點(diǎn)數(shù)為 13。

33. 設(shè)一棵完全二叉樹共有739個(gè)結(jié)點(diǎn)，則在該二叉樹中有 370 個(gè)葉子結(jié)點(diǎn)。

34. 設(shè)一棵完全二叉樹共有700個(gè)結(jié)點(diǎn)，則在該二叉樹中有 350 個(gè)葉子結(jié)點(diǎn)。

35. 在先左后右的原則下，根據(jù)訪問根結(jié)點(diǎn)的次序，二叉樹的遍歷可以分為三種：前序遍歷、 中序 遍歷和后序遍歷。

36.? 若串S="Program"，則其子串的數(shù)目是 29 。 注：n(n+1)/2+1

37.? 若串S=”MathTypes”，則其子串的數(shù)目是 46 。

38. 對長度為n的線性表進(jìn)行插入一個(gè)新元素或刪除一個(gè)元素時(shí)，在最壞情況下所需要的比較次數(shù)為 n 。

39.? 在長度為n的有序線性表中進(jìn)行順序查找。最壞的情況下，需要的比較次數(shù)為?? n?? 。

40.? 在長度為n的有序線性表中進(jìn)行二分查找。最壞的情況下，需要的比較次數(shù)為 log2n 。

41. 長度為n的順序存儲線性表中，當(dāng)在任何位置上插入一個(gè)元素概率都相等時(shí)，插入一個(gè)元素所需移動(dòng)元素的平均個(gè)數(shù)為 n/2 。

42.? 排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，常見的排序方法有插入排序、 交換排序 和選擇排序等。

43. 快速排序法可以實(shí)現(xiàn)通過一次交換而消除多個(gè) 逆序 。

44. 快速排序法的關(guān)鍵是對線性表進(jìn)行 分割 。

45. 冒泡排序算法在最好的情況下的元素交換次數(shù)為 0 。

46. 在最壞情況下，冒泡排序的時(shí)間復(fù)雜度為 n(n-1) /2 。

47.? 對于長度為n的線性表，在最壞情況下，快速排序所需要的比較次數(shù)為 n(n-1) /2 。

48.在最壞情況下，簡單插入排序需要比較的次數(shù)為 n(n-1) /2 。

49.在最壞情況下，希爾排序需要比較的次數(shù)為 O(n1.5) 。注：括號里是n的1.5次方。

50. 在最壞情況下，簡單選擇排序需要比較的次數(shù)為 n(n-1) /2 。

51. 在最壞情況下，堆排序需要比較的次數(shù)為 o(nlog2n) 。

52.對于輸入為N個(gè)數(shù)進(jìn)行快速排序算法的平均時(shí)間復(fù)雜度是 O(Nlog2 N)。

?

第二章 程序設(shè)計(jì)基礎(chǔ)

一.程序設(shè)計(jì)方法與風(fēng)格
當(dāng)今主導(dǎo)的程序設(shè)計(jì)風(fēng)格是“清晰第一，效率第二”的觀點(diǎn)。
1.在結(jié)構(gòu)化程序設(shè)計(jì)思想提出之前，在程序設(shè)計(jì)中曾強(qiáng)調(diào)程序的效率。與程序的效率相比，人們更重視程序的( C )。 A.安全性?? B.一致性 C.可理解性D.合理性
2.對建立良好的程序設(shè)計(jì)風(fēng)格,下面的描述正確的是(A )
A.程序應(yīng)簡單、清晰、可讀性好 B.符號名的命名只要符合語法??
C.充分考慮程序的執(zhí)行效率???? D.程序的注釋可有可無
3. 在設(shè)計(jì)程序時(shí)．應(yīng)采納的原則之一是( D)。A.不限制GOTO語句的使用
B.減少或取消注解行???? C.程序越短越好???? D.程序結(jié)構(gòu)應(yīng)有助于讀者理解
4.程序應(yīng)該簡單易懂，語句構(gòu)造應(yīng)該簡單直接，不應(yīng)該為提高效率而把語句復(fù)雜化。
5.源程序文檔化要求程序應(yīng)加注釋，注釋一般分為序言性注釋和 功能性注釋 。
6.在編寫程序時(shí)，需要注意 數(shù)據(jù)說明 的風(fēng)格，以便使程序中的數(shù)據(jù)說明更易理解和維護(hù)。
7.當(dāng)程序設(shè)計(jì)語言對輸入格式有嚴(yán)格要求時(shí)，應(yīng)保持輸入格式與輸入語句的一致性??
程序設(shè)計(jì)語言的基本成分是數(shù)據(jù)成分、運(yùn)算成分、控制成分和(傳輸成分)。

二.結(jié)構(gòu)化程序設(shè)計(jì)
1結(jié)構(gòu)化程序設(shè)計(jì)的原則
8.結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則是：自頂向下、逐步求精、模塊化、限制使用goto語句?? 2結(jié)構(gòu)化程序的基本結(jié)構(gòu)與特點(diǎn)
9.結(jié)構(gòu)化程序設(shè)計(jì)主要強(qiáng)調(diào)的是(B)???? A.程序的規(guī)模???? B.程序的易讀性?????? C.程序的執(zhí)行效率 D.程序的可移植性
10.結(jié)構(gòu)化程序設(shè)計(jì)的3種結(jié)構(gòu)是(順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu))。
結(jié)構(gòu)化程序設(shè)計(jì)方法是程序設(shè)計(jì)的先進(jìn)方法和工具。下面為三種基本的控制結(jié)構(gòu)：
順序結(jié)構(gòu)：是一種簡單的程序設(shè)計(jì)，它是最基本，最常用的結(jié)構(gòu)
選擇結(jié)構(gòu)：又稱為分支結(jié)構(gòu)，包括簡單選擇和多分支選擇結(jié)構(gòu)
重復(fù)結(jié)構(gòu)：又稱循環(huán)結(jié)構(gòu)，有兩類循環(huán)語句：當(dāng)型循環(huán)結(jié)構(gòu)（先判斷后執(zhí)行循環(huán)體）和直到型循環(huán)結(jié)構(gòu)（先執(zhí)行循環(huán)體后判斷）
按結(jié)構(gòu)化程序設(shè)計(jì)方法設(shè)計(jì)出的程序具有兩大明顯的優(yōu)點(diǎn)：1、程序易于理解、使用和維護(hù)。2、提高了編程工作效率，降低了軟件開發(fā)成本。
3.結(jié)構(gòu)化程序設(shè)計(jì)原則和方法的應(yīng)用
11.結(jié)構(gòu)化程序設(shè)計(jì)的主要特點(diǎn)是（每個(gè)控制結(jié)構(gòu)只有一個(gè)入口和一個(gè)出口）
12.下列敘述中，不屬于結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則的是(B)。
A.自頂向下?? B.由底向上?? C.模塊化?? D.限制使用GOTO語句
在結(jié)構(gòu)化程序設(shè)計(jì)的具體實(shí)施中,要注意如下要素:
使用程序設(shè)計(jì)語言中的順序、選擇、循環(huán)等有限的控制結(jié)構(gòu)表示程序的控制邏輯；選用的控制結(jié)構(gòu)只準(zhǔn)許的一個(gè)入口和一個(gè)出口；程序語句組成容易識別的塊，每塊只有一個(gè)入口和一人出口；復(fù)雜結(jié)構(gòu)應(yīng)該用嵌套的基本控制結(jié)構(gòu)進(jìn)行組合嵌套來實(shí)現(xiàn)；語言中所沒有的控制結(jié)構(gòu)，應(yīng)該采用前后一致的方法來模擬；嚴(yán)格控制GOTO語句的使用。其意思有三：1.用一個(gè)非結(jié)構(gòu)化的程序設(shè)計(jì)語言去實(shí)現(xiàn)一個(gè)結(jié)構(gòu)化的構(gòu)造；2.如不使用GOTO語句會(huì)使功能模糊；3.在某種可以改善而不是損害程序可讀性的情況下。

三.面向?qū)ο蟮某绦蛟O(shè)計(jì)
1. 關(guān)于面向?qū)ο蠓椒?br /> 25.面向?qū)ο蟮某绦蛟O(shè)計(jì)方法中涉及的對象是系統(tǒng)中用來描述客觀事物的一個(gè) 實(shí)體
傳統(tǒng)的程序設(shè)計(jì)方法是面向過程的，其核心方法是以 算法 為核心。面向?qū)ο蠓椒ê图夹g(shù)以 對象 為核心。對象是由 數(shù)據(jù) 和 容許的操作 組成的封裝體，與客觀實(shí)體有直接的對應(yīng)關(guān)系。對象之間通過傳遞 消息 互相聯(lián)系，以模擬現(xiàn)實(shí)世界中不同事物彼此之間的聯(lián)系。
? 面向?qū)ο蠓椒ɑ跇?gòu)造問題領(lǐng)域的對象模型，以對象為中心構(gòu)造軟件系統(tǒng)。它的基本作法是用 對象 模擬問題領(lǐng)域中的實(shí)體，以 對象間的聯(lián)系 刻畫實(shí)體間的聯(lián)系。
? 軟件重用 是指在不同的軟件開發(fā)過程中重復(fù)使用相同的或者相似軟件元素的過程。?? 重用是提高軟件生產(chǎn)率的最主要的方法。
2. 面向?qū)ο蠓椒ǖ幕靖拍?#xff08;對象、類、消息、繼承、多態(tài)性）
13.面向?qū)ο蟮哪Ｐ椭?#xff0c;最基本的概念是對象和 類
14.類是一個(gè)支持集成的抽象數(shù)據(jù)類型，而對象是類的 實(shí)例
對象：面向?qū)ο蟮某绦蛟O(shè)計(jì)方法中涉及的對象是系統(tǒng)中用來描述客觀事物的一個(gè)實(shí)體，是構(gòu)成系統(tǒng)一個(gè)基本單位，它由一組表示靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。（是由描述該對象屬性的數(shù)據(jù)以及可以對這些數(shù)據(jù)施加的所有操作封裝在一起構(gòu)成的統(tǒng)一體。）
? 屬性：是對象所包含的信息，它在設(shè)計(jì)對象時(shí)確定，一般只能通過執(zhí)行對象的操作來改變。
? 操作：描述了對象執(zhí)行的功能，若通過信息傳遞，還可為其它對象使用。操作過程對外是封閉的，用戶只能看到這一操作實(shí)施后的結(jié)果，對象的這一特性，即是對象的封裝體。
15.對象實(shí)現(xiàn)了數(shù)據(jù)和操作的結(jié)合，是指對數(shù)據(jù)和數(shù)據(jù)的操作進(jìn)行(封裝)。
16.封裝是一種（信息屏蔽）技術(shù)，封裝的目的是使對象的定義和實(shí)現(xiàn)分離。
17.以下不屬于對象的基本特點(diǎn)的是(C)。 A.分類性?? B.多態(tài)性?? C.繼承性?? D.封裝性
對象有如下一些基本特點(diǎn)．即標(biāo)識惟一性、分類性、多態(tài)性、封裝性和模塊獨(dú)立性。
18.下面關(guān)于對象的描述錯(cuò)誤的是（A）A.任何對象都必須有繼承性B.對象是屬性和方法的封裝體???????? C.對象間的通迅靠消息傳遞?? D.操作是對象的動(dòng)態(tài)屬性
19.信息隱蔽的概念與下述哪能一種概念直接相關(guān)（模塊獨(dú)立性）
20.可以把具有相同屬性的一些不同對象歸類，稱為?? 對象類?? 。
類：是具有其同屬性、共同方法的對象的集合。所以，類是對象的抽象，這描述了屬于該對象類型的所有對象的性質(zhì)，而一個(gè)對象則是其對應(yīng)類的一個(gè)實(shí)例。類同對象一樣，包括一組數(shù)據(jù)屬性和在數(shù)據(jù)上的一組合法操作。 對象可以是一個(gè)具體的對象也可以是泛指一般的對象，而實(shí)例必然是指一個(gè)具體的對象。
21.在面向?qū)ο蠓椒ㄖ?#xff0c;一個(gè)對象請求另一對象為其服務(wù)的方式是通過發(fā)送(消息)
消息：面向?qū)ο蟮氖澜缡峭ㄟ^對象與對象間彼此的相合合作來推動(dòng)的，對象間這種合作需要一個(gè)機(jī)制協(xié)助進(jìn)行，這樣的機(jī)制稱為“消息”。消息就是一個(gè)實(shí)例與另一個(gè)實(shí)例之間傳遞的信息，它統(tǒng)一了數(shù)據(jù)流和控制流。一個(gè)消息由下述三部分組成：1、接收消息的對象的名稱。 2、消息標(biāo)識符（即消息名）3、零個(gè)或多個(gè)參數(shù)。
22.在面向?qū)ο蠓椒ㄖ?#xff0c;類之間共享屬性和操作的機(jī)制稱為?? 繼承?? 。
23.一個(gè)類可以從直接或間接的祖先中繼承所有屬性和方法。采用此方法提高了軟件的可重用性
繼承：是面向?qū)ο蠓椒ǖ囊粋€(gè)主要特征。繼承是使用已有的定義作為基礎(chǔ)建立新類的定義技術(shù)。也就是說繼承是指能夠直接獲得已有的功能和突出的優(yōu)點(diǎn)，而不必重復(fù)定義它們。
? 繼承具有傳遞性，可分為單繼承與多重繼承。單繼承是指一個(gè)類只允許有一人父類，即類等級為樹形結(jié)構(gòu)。多重繼承是指一個(gè)類允許有多個(gè)父類。多態(tài)性：對象根據(jù)所接受的消息而做出動(dòng)作，同樣的消息被不同的對象接受時(shí)可導(dǎo)致完全不同的行動(dòng)，這種現(xiàn)象即為多態(tài)性。多態(tài)性機(jī)制可提高軟件系統(tǒng)的靈活性，可重用性和可擴(kuò)充性。
24.子程序通常分為兩類： 過程?? 和函數(shù)，前者是命令的抽象，后者是為了求值。

?

第三章 軟件工程
重點(diǎn)：需求分析、概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)、軟件測試和軟件調(diào)試的作用、方法等

?

一、 軟件工程基本概念
1. 軟件是計(jì)算機(jī)系統(tǒng)中與硬件相互依存的重要部分，包括程序、數(shù)據(jù)及相關(guān)的 文檔 。其中，程序 是軟件開發(fā)人員根據(jù)用戶需求開發(fā)的、用程序設(shè)計(jì)語言描述的、適合計(jì)算機(jī)執(zhí)行的指令（語句）序列。
2. 下列敘述中，正確的是(D)。 A.軟件就是程序清單?? B.軟件就是存放在計(jì)算機(jī)中的文件 C.軟件應(yīng)包括程序清單及運(yùn)行結(jié)果???? D.軟件包括程序和文檔?
3. 軟件按功能可以分為：應(yīng)用軟件、系統(tǒng)軟件、支撐軟件（或工具軟件）
4. 軟件工程的出現(xiàn)是由于（軟件危機(jī)的出現(xiàn)）
5. 開發(fā)軟件所需高成本和產(chǎn)品的低質(zhì)量之間有著尖銳的矛盾，這種現(xiàn)象稱做（軟件危機(jī)）
軟件工程概念的出現(xiàn)源自軟件危機(jī)。所謂軟件危機(jī)是泛指在計(jì)算機(jī)軟件的開發(fā)和維護(hù)過程中所遇到的一系列嚴(yán)重問題。總之，可以將軟件危機(jī)歸結(jié)為成本、質(zhì)量、生產(chǎn)率等問題。
6. 開發(fā)大型軟件時(shí)，產(chǎn)生困難的根本原因是(大型系統(tǒng)的復(fù)雜性)。
7. 軟件危機(jī)出現(xiàn)于20世紀(jì)60年代末，為了解決軟件危機(jī)，人們提出了 軟件工程學(xué) 的原理來設(shè)計(jì)軟件這就是軟件工程誕生的基礎(chǔ)。
8. 下列不屬于軟件工程的3個(gè)要素的是（D）
A.工具?? B.過程?? C.方法?? D.環(huán)境
軟件工程過程與軟件生命周期
9. 軟件工程過程是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的 資源 和活動(dòng)。通常，將軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過程稱為 軟件生命周期
10.軟件生命周期中所花費(fèi)用最多的階段是（軟件維護(hù)）
11.軟件開發(fā)的結(jié)構(gòu)化生命周期方法將軟件生命周期劃分成(定義、開發(fā)、運(yùn)行維護(hù))。???????
12. 軟件生命周期一般包括可行性研究與需求分析、設(shè)計(jì)、實(shí)現(xiàn)、測試、交付使用以及維護(hù)等活動(dòng)。
軟件工程的目標(biāo)與原則
13. 軟件工程的理論和技術(shù)性研究的內(nèi)容主要包括：軟件開發(fā)技術(shù)和軟件工程管理。軟件開發(fā)技術(shù)包括：軟件開發(fā)方法學(xué)、開發(fā)過程、開發(fā)工具和軟件工程環(huán)境，主體內(nèi)容是軟件開發(fā)方法學(xué)。軟件工程管理包括：軟件管理學(xué)、軟件工程經(jīng)濟(jì)學(xué)、軟件心理學(xué)等內(nèi)容。
14. 軟件工程的理論和技術(shù)性研究的內(nèi)容主要包括軟件開發(fā)技術(shù)和（軟件工程管理）????????
15. 軟件工程的原則包括抽象、信息隱藏、模塊化、局部化、確定性、一致性、完備性和可驗(yàn)證性。
軟件開發(fā)工具與軟件開發(fā)環(huán)境
16. 開發(fā)軟件時(shí)對提高開發(fā)人員工作效率至關(guān)重要的是（先進(jìn)的軟件開發(fā)工具和環(huán)境）?????? 17. 軟件開發(fā)環(huán)境是全面支持軟件開發(fā)全過程的 軟件工具 集合。
常用的軟件開發(fā)方法和技術(shù)可以分為三大類：瀑布型、增量型和變換型。瀑布型開發(fā)方法將軟件生命周期的各項(xiàng)活動(dòng)規(guī)定為按固定順序連接的若干階段，強(qiáng)調(diào)早期的需求分析和開發(fā)的階段性，強(qiáng)調(diào)產(chǎn)品測試；但是不能適應(yīng)需求的變化。增量型則先建立一個(gè)不完全的系統(tǒng)，通過對需求的理解再進(jìn)一步擴(kuò)充和完善。
例：瀑布模型突出的缺點(diǎn)是不適應(yīng)（D）的變動(dòng)
A.算法B.平臺C)程序語言D.用戶需求

二、結(jié)構(gòu)化分析方法??
需求分析與需求分析方法
18. 在軟件生產(chǎn)過程中，需求信息的給出是(軟件用戶)。
19. 需求分析中，開發(fā)人員要從用戶那里了解(軟件做什么)。
20. 需求分析階段的任務(wù)是確定 (軟件系統(tǒng)功能)
21. 需求分析的任務(wù)是發(fā)現(xiàn)需求、求精、建模和定義需求的過程。需求分析將創(chuàng)建所需的數(shù)據(jù)模型、功能模型和 控制模型
22. 需求分析階段的工作：需求獲取、需求分析、編寫需求規(guī)格說明書、需求評審
下列工具中屬于需求分析常用工具的是(D)。
A)PAD???? B)PFD???? C)N—S???? D)DFD
結(jié)構(gòu)化分析方法
常用的需求分析方法：
（1）結(jié)構(gòu)化分析方法。主要包括：面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法(SA)，面向數(shù)據(jù)結(jié)構(gòu)的Jackson方法(JSD)和面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開發(fā)方法(DSSD)
（2）面向?qū)ο蟮姆治龇椒?OOA)
23. 結(jié)構(gòu)化方法的核心和基礎(chǔ)是 結(jié)構(gòu)化程序設(shè)計(jì)理論
24. 下列不屬于結(jié)構(gòu)化分析的常用工具的是(D)。
A)數(shù)據(jù)流圖?? B)數(shù)據(jù)字典?? C)判定樹?? D)PAD圖
25. 在結(jié)構(gòu)化方法中，用數(shù)據(jù)流程圖（DFD）作為描述工具的軟件開發(fā)階段是 (B)
A)可行性分析 B)需求分析?? C)詳細(xì)設(shè)計(jì)?? D)程序編碼
26. 數(shù)據(jù)流圖用于抽象描述一個(gè)軟件的邏輯模型．數(shù)據(jù)流圖由一些特定的圖符構(gòu)成。下列圖符名標(biāo)識的圖符不屬于數(shù)據(jù)流圖合法圖符的是(A)。
A)控制流?? B)加工?? C)數(shù)據(jù)存儲?? D)源和潭
說明：數(shù)據(jù)流圖中的主要圖形元素與說明：
27. 在數(shù)據(jù)流圖(DFD)中的箭頭代表的是(數(shù)據(jù)流)
28. 在數(shù)據(jù)流圖(DFD)中，帶有名字的箭頭表示(數(shù)據(jù)的流向)。
29. 在結(jié)構(gòu)化分析方法中，用于描述系統(tǒng)中所用到的全部數(shù)據(jù)和文件的文檔稱為 數(shù)據(jù)字典
軟件需求規(guī)格說明書
30. 軟件需求規(guī)格說明書 是需求分析階段的最后結(jié)果
31. 下列敘述中，不屬于軟件需求規(guī)格說明書的作用的是（D）
A.便于用戶、開發(fā)人員進(jìn)行理解和交流??????????? B.反映出用戶問題的結(jié)構(gòu)，可以作為軟件開發(fā)工作的基礎(chǔ)和依據(jù)?????????????????? C.作為確認(rèn)測試和驗(yàn)收的依據(jù)???? D.便于開發(fā)人員進(jìn)行需求分析
32. (數(shù)據(jù)描述)是對軟件系統(tǒng)所必須解決的問題做出的詳細(xì)說明
說明：需求規(guī)格說明書一般包括以下內(nèi)容：概述、數(shù)據(jù)描述、性能描述、功能描述、參考文獻(xiàn)目錄等。其中概述從系統(tǒng)角度描述軟件的目標(biāo)和任務(wù)；功能描述中描述了為解決用戶問題所需要的每一項(xiàng)功能的過程細(xì)節(jié)；性能描述說明系統(tǒng)應(yīng)達(dá)到的性能和應(yīng)該滿足的限制條件、檢測的方法和標(biāo)準(zhǔn)。

三、???? 結(jié)構(gòu)化設(shè)計(jì)方法
軟件設(shè)計(jì)的基本概念
33. 在軟件開發(fā)中，下面任務(wù)不屬于設(shè)計(jì)階段的是(D)
A)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) B) 給出系統(tǒng)模塊結(jié)構(gòu) C)定義模塊算法 D)定義需求并建立系統(tǒng)模型
34. 軟件設(shè)計(jì)包括軟件的結(jié)構(gòu)、數(shù)據(jù)、接口和過程設(shè)計(jì)，其中軟件的過程設(shè)計(jì)是指(系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過程描述)。
說明：結(jié)構(gòu)設(shè)計(jì)：定義軟件系統(tǒng)各主要部件之間的關(guān)系；數(shù)據(jù)設(shè)計(jì)：將分析時(shí)創(chuàng)建的模型轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)的定義；接口定義：描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)之間以及軟件與人之間如何通信；過程設(shè)計(jì)：把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過程性描述。
35. 下面不屬于軟件設(shè)計(jì)原則的是（C）A.抽象 B.模塊化?? C.自底向上?? D.信息隱藏???? 36. 耦合和內(nèi)聚是評價(jià)模塊獨(dú)立性的兩個(gè)主要標(biāo)準(zhǔn)，其中?? 內(nèi)聚 反映了模塊內(nèi)各成分之間的聯(lián)系，耦合反映了模塊間互相連接的緊密程度。
?37. 內(nèi)聚性是信息隱蔽和局部化概念的自然擴(kuò)展，一個(gè)模塊的內(nèi)聚性越強(qiáng)，則該模塊的模塊獨(dú)立性越 強(qiáng) 。一個(gè)模塊與其它模塊的耦合性越強(qiáng)，則它的模塊獨(dú)立性越 弱 。????????????????
?38. 下列敘述中，正確的是（C）
A.接口復(fù)雜的模塊，其耦合程度一定低?????? B.耦合程度弱的模塊，其內(nèi)聚程度一定低?? C.耦合程度弱的模塊，其內(nèi)聚程度一定高???? D.以上都不對
39.下列選項(xiàng)中，不屬于模塊間耦合的是(B)。A.數(shù)據(jù)耦合B.同構(gòu)耦合C.異構(gòu)耦D.公用耦合40.軟件設(shè)計(jì)中，有利于提高模塊獨(dú)立性的一個(gè)準(zhǔn)則是( C)。
A.低內(nèi)聚低耦合?? B.低內(nèi)聚高耦合?? C.高內(nèi)聚低耦合?? D.高內(nèi)聚高耦合
概要設(shè)計(jì)
41. 軟件的概要 設(shè)計(jì)又稱為總體結(jié)構(gòu)設(shè)計(jì)，其主要任務(wù)是建立軟件系統(tǒng)的總體結(jié)構(gòu)，設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫，編寫概要設(shè)計(jì)文檔，概要設(shè)計(jì)文檔評審。
42. 在結(jié)構(gòu)化方法中，軟件功能分解屬于下列軟件開發(fā)中的階段是 (C)
A.詳細(xì)設(shè)計(jì) B.需求分析 C.總體設(shè)計(jì) D.編程調(diào)試
43. 在概要設(shè)計(jì)階段，常用的軟件結(jié)構(gòu)設(shè)計(jì)工具是 結(jié)構(gòu)圖 (sc)，也稱程序結(jié)構(gòu)圖。生成的結(jié)構(gòu)圖中，帶有箭頭的連線表示(模塊之間的調(diào)用關(guān)系)，矩形表示模塊。???????????????????????? 44. 在概要設(shè)計(jì)階段，一般采用面向數(shù)據(jù)流的設(shè)計(jì)方法。數(shù)據(jù)流的類型有 變換型?? 和事務(wù)型。將變換型映射成結(jié)構(gòu)圖稱為 變換分析 。將事務(wù)型映射成結(jié)構(gòu)圖稱為 事務(wù)分析 。???? 45. 好的軟件設(shè)計(jì)結(jié)構(gòu)通常 頂層 高 扇出，中間扇出較少，底層 高 扇入。???????????????? 46. 模塊的控制范圍包括它本身以及它所有的從屬模塊，模塊的作用范圍是指模塊內(nèi)一個(gè)判定的作用范圍，凡是受到這個(gè)判定影響的所有模塊都屬于這個(gè)判定的作用范圍。理想的情況是(模塊的作用范圍應(yīng)在控制范圍內(nèi))
詳細(xì)設(shè)計(jì)
47. 詳細(xì)設(shè)計(jì) 的任務(wù)是為軟件結(jié)構(gòu)圖中的每一個(gè)模塊確定實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用選定的表達(dá)工具表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。確定怎樣來具體實(shí)現(xiàn)所要求的系統(tǒng)。?????????????? 48. 為了避免流程圖在描述程序邏輯時(shí)的靈活性，提出了用方框圖來代替?zhèn)鹘y(tǒng)的程序流程圖，通常也把這種圖稱為(N—S圖)。
49. 詳細(xì)設(shè)計(jì)的結(jié)果基本決定了最終程序的(質(zhì)量)。
50. 軟件設(shè)計(jì)模塊化的目的是 降低復(fù)雜性。
51. 詳細(xì)設(shè)計(jì)的典型語言描述工具是(PDL)
結(jié)構(gòu)化分析(需求階段)的常用工具有：數(shù)據(jù)流圖(DFD)、數(shù)據(jù)字典(DD)、判定樹和判定表
結(jié)構(gòu)設(shè)計(jì)（概要設(shè)計(jì)階段）工具是：結(jié)構(gòu)圖(SC, structure chart)
過程設(shè)計(jì)(詳細(xì)設(shè)計(jì)階段)常見的工具有：程序流程圖、N—S圖、PAD圖（問題分析圖,）和PDL( 過程設(shè)計(jì)語言)

四、軟件測試 軟件測試的目的
52. 在軟件測試設(shè)計(jì)中，軟件測試的主要目的是(D)。A.實(shí)驗(yàn)性運(yùn)行軟件?? B.證明軟件正確 C.找出軟件中全部錯(cuò)誤?? D.發(fā)現(xiàn)軟件錯(cuò)誤而執(zhí)行程序
（注意：不是為了證明軟件的正確性，也不是為了找出全部錯(cuò)誤）
?軟件測試的準(zhǔn)則
53. 下列敘述中．不屬于測試的特征的是(C)。
A.測試的挑剔性?? B.完全測試的不可能性?? C.測試的可靠性?? D.測試的經(jīng)濟(jì)性
軟件測試技術(shù)與方法
軟件測試方法從是否需要執(zhí)行被測試軟件的角度，可以分為 靜態(tài)測試 和 動(dòng)態(tài)測試 ；按功能劃分為 白盒測試 和 黑盒測試 。
靜態(tài)測試包括 代碼檢查 、 靜態(tài)結(jié)構(gòu)分析 、 代碼質(zhì)量量度 等
白盒測試和黑盒測試都屬于 動(dòng)態(tài)測試
白盒測試的主要方法： 邏輯覆蓋 、 基本路徑測試 等
黑盒測試的主要方法： 等價(jià)類劃分法 、 邊界值分析法 、 錯(cuò)誤推測法 、 因果圖 等
54. 下列不屬于靜態(tài)測試方法的是(B)。
A.代碼檢查???? B.白盒法?????? C.靜態(tài)結(jié)構(gòu)分析?? D.代碼質(zhì)量度量
55. 在軟件工程中，白箱測試法可用于測試程序的內(nèi)部結(jié)構(gòu)。此方法將程序看做是(A)。
A.路徑的集合?? B.循環(huán)的集合???? C.目標(biāo)的集臺???? D.地址的集合
56. 完全不考慮程序的內(nèi)部結(jié)構(gòu)和內(nèi)部特征，而只是根據(jù)程序功能導(dǎo)出測試用例的測試方法是(A)
A.黑箱測試法?? B.白箱測試法???? C.錯(cuò)誤推測法???? D.安裝測試法
57. 黑盒測試是對軟件已經(jīng)實(shí)現(xiàn)的功能是否滿足需求進(jìn)行測試和驗(yàn)證，不考慮程序內(nèi)部的邏輯結(jié)構(gòu)，在軟件接口處進(jìn)行。常用的黑箱測試有等價(jià)分類法、 邊界值分析法 、因果圖法和錯(cuò)誤推測法4種。
軟件測試的實(shí)施
58. 軟件測試過程一般按4個(gè)步驟進(jìn)行，即單元測試、集成測試、驗(yàn)收測試（確認(rèn)測試）和系統(tǒng)測試
58.檢查軟件產(chǎn)品是否符合需求定義的過程稱為（A）
?? A.確認(rèn)測試B.集成測試C.驗(yàn)證測試D.驗(yàn)收測試
說明：軟件的測試過程一般按4個(gè)步驟進(jìn)行：
單元測試：對軟件設(shè)計(jì)的最小單位—模塊進(jìn)行正確性檢驗(yàn)的測試，發(fā)現(xiàn)模塊內(nèi)部可能存在的錯(cuò)誤。由于模塊通常不是一個(gè)獨(dú)立的程序，不能單獨(dú)運(yùn)行，所以常常需要用到模擬環(huán)境。可以采用靜態(tài)測試和動(dòng)態(tài)測試（以白盒測試為主）。
集成測試：測試和組裝模塊的過程，主要是發(fā)現(xiàn)與接口有關(guān)的錯(cuò)誤，依據(jù)是概要設(shè)計(jì)說明書。涉及的內(nèi)容有：軟件單元的接口測試、全局?jǐn)?shù)據(jù)結(jié)構(gòu)測試、邊界條件和非法輸入的測試等。通常采用兩種方式：非增量方式組裝域增量方式組裝
驗(yàn)收測試（確認(rèn)測試）：驗(yàn)證軟件的功能和性能以及其他特性是否滿足了需求規(guī)格說明書中確定的各種需求，以及軟件配置是否完全、正確。采用黑盒測試。
系統(tǒng)測試：將軟件與硬件、用戶、數(shù)據(jù)等組合，在實(shí)際運(yùn)行環(huán)境下對整個(gè)系統(tǒng)進(jìn)行集成測試和確認(rèn)測試。
59. 軟件開發(fā)離不開系統(tǒng)環(huán)境資源的支持．其中必要的測試數(shù)據(jù)屬于(D)。
A.硬件資源???? B.通信資源???? C.支持軟件???? D.輔助資源
軟件測試過程中，輔助資源包括測試用例(測試數(shù)據(jù))、測試計(jì)劃、出錯(cuò)統(tǒng)計(jì)和最終分析報(bào)告等。
60. 為了提高測試的效率，應(yīng)該(D)A.隨機(jī)選取測試數(shù)據(jù)???? B.取一切可能的輸入數(shù)據(jù)作為測試數(shù)據(jù) C.在完成編碼以后制定軟件的測試計(jì)劃???? D.集中對付那些錯(cuò)誤群集的程序
61. 為了便于對照檢查，測試用例應(yīng)由輸入數(shù)據(jù)和預(yù)期的 輸出結(jié)果 兩部分組成。

五、程序的調(diào)試
軟件調(diào)試(Debug，即排錯(cuò))的任務(wù)是診斷和改正程序中的錯(cuò)誤，與軟件測試不同，軟件測試是盡可能多地發(fā)現(xiàn)軟件中的錯(cuò)誤。軟件測試貫穿整個(gè)軟件生命期，調(diào)試主要在開發(fā)階段。
62. 程序調(diào)試的基本步驟：錯(cuò)誤定位、修改和設(shè)計(jì)代碼以排除錯(cuò)誤、進(jìn)行回歸測試防治引進(jìn)新的錯(cuò)誤。
63.下列敘述正確的是（D）
A.測試和調(diào)試工作必須由程序編制者自己完成???? B.測試用例和調(diào)試用例必須完全一致
C.一個(gè)程序經(jīng)調(diào)試改正錯(cuò)誤后，一般不必再進(jìn)行測試 D.上述三種說法都不對
軟件調(diào)試方法
64. 下列不屬于軟件調(diào)試技術(shù)的是(B)。
A.強(qiáng)行排錯(cuò)法B.集成測試法C.回溯法D.原因排除法

六、軟件維護(hù)
65. 軟件維護(hù)活動(dòng)包括以下幾類：校正性維護(hù)、適應(yīng)性維護(hù)、 完善性維護(hù)和預(yù)防性維護(hù)。

?

第四章????? 數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)

一、數(shù)據(jù)庫系統(tǒng)的基本概念
數(shù)據(jù)、數(shù)據(jù)庫、數(shù)據(jù)庫管理系統(tǒng)
1.數(shù)據(jù)處理的最小單位是(C)。
A.數(shù)據(jù)?? B.數(shù)據(jù)元素?? C.數(shù)據(jù)項(xiàng)???? D.數(shù)據(jù)結(jié)構(gòu)
2.下列有關(guān)數(shù)據(jù)庫的描述，正確的是(C)。A.數(shù)據(jù)庫是一個(gè)DBF文件?? B.數(shù)據(jù)庫是一個(gè)關(guān)系
C.數(shù)據(jù)庫是一個(gè)結(jié)構(gòu)化的數(shù)據(jù)的集合?? D.數(shù)據(jù)庫是一組文件
3.下述關(guān)于數(shù)據(jù)庫系統(tǒng)的敘述中正確的是(A)
A.數(shù)據(jù)庫系統(tǒng)減少了數(shù)據(jù)冗余?????? B.數(shù)據(jù)庫系統(tǒng)避免了一切冗余
C.數(shù)據(jù)庫系統(tǒng)避免了一切數(shù)據(jù)的重復(fù)?? D.數(shù)據(jù)庫系統(tǒng)比文件系統(tǒng)能管理更多的數(shù)據(jù)
4.下列有關(guān)數(shù)據(jù)庫的描述．正確的是(D)。A.數(shù)據(jù)處理是將信息轉(zhuǎn)化為數(shù)據(jù)的過程
B.數(shù)據(jù)的物理獨(dú)立性是指當(dāng)數(shù)據(jù)的邏輯結(jié)構(gòu)改變時(shí)，數(shù)據(jù)的存儲結(jié)構(gòu)不變
C.關(guān)系中的每一列稱為元組，一個(gè)元組就是一個(gè)字段
D.如果一個(gè)關(guān)系中的屬性或?qū)傩越M并非該關(guān)系的關(guān)鍵字，但它是另一個(gè)關(guān)系的關(guān)鍵字，則稱其為本關(guān)系的外關(guān)鍵字
5.下列4項(xiàng)說法中不正確的是(C)。
A.數(shù)據(jù)庫減少了數(shù)據(jù)冗余?????? B.數(shù)據(jù)庫中的數(shù)據(jù)可以共享
C.數(shù)據(jù)庫避免了一切數(shù)據(jù)的重復(fù)?? D.數(shù)據(jù)庫具有較高的數(shù)據(jù)獨(dú)立性
6.下列敘述中。不屬于數(shù)據(jù)庫系統(tǒng)的是(D)。
A.數(shù)據(jù)庫?? B.數(shù)據(jù)庫管理系統(tǒng)?? C.數(shù)據(jù)庫管理員?? D.數(shù)據(jù)庫應(yīng)用系統(tǒng)
7.數(shù)據(jù)庫系統(tǒng)的核心是(數(shù)據(jù)庫管理系統(tǒng))。
8.數(shù)據(jù)庫、數(shù)據(jù)庫系統(tǒng)和數(shù)據(jù)庫管理系統(tǒng)之間的關(guān)系是(數(shù)據(jù)庫系統(tǒng)包括數(shù)據(jù)庫和數(shù)據(jù)庫管理系統(tǒng))。
9.為用戶與數(shù)據(jù)庫系統(tǒng)提供接口的語言是(數(shù)據(jù)操縱語言(DML))。
數(shù)據(jù)庫管理系統(tǒng)一般提供的數(shù)據(jù)語言有：
數(shù)據(jù)庫定義語言(DDL)：負(fù)責(zé)數(shù)據(jù)的模式定義與數(shù)據(jù)的物理存取構(gòu)建
數(shù)據(jù)操縱語言(DML)：負(fù)責(zé)數(shù)據(jù)的操縱，包括查詢及增、刪、改變等操作
數(shù)據(jù)庫控制語言(DCL)：負(fù)責(zé)數(shù)據(jù)完整性、安全性的定義與檢查以及并發(fā)控制、故障恢復(fù)等
2. 數(shù)據(jù)庫系統(tǒng)的發(fā)展
10.在數(shù)據(jù)管理技術(shù)的發(fā)展過程中．經(jīng)歷了人工管理階段、文件系統(tǒng)階段和數(shù)據(jù)庫系統(tǒng)階段。其中數(shù)據(jù)獨(dú)立性最高的階段是(數(shù)據(jù)庫系統(tǒng))。
11.在數(shù)據(jù)管理技術(shù)發(fā)展過程中，文件系統(tǒng)與數(shù)據(jù)庫系統(tǒng)的主要區(qū)別是數(shù)據(jù)庫系統(tǒng)具有(A)。
A.特定的數(shù)據(jù)模型?? B.數(shù)據(jù)無冗余?? C.數(shù)據(jù)可共享?? D.專門的數(shù)據(jù)管理軟件
12.相對于數(shù)據(jù)庫系統(tǒng)，文件系統(tǒng)的主要缺陷有數(shù)據(jù)關(guān)聯(lián)差、數(shù)據(jù)不一致性和(冗余性)。
13.分布式數(shù)據(jù)庫系統(tǒng)不具有的特點(diǎn)是( D)。 A.數(shù)據(jù)分布性和邏輯整體性
B.位置透明性和復(fù)制透明性?????????? C.分布性???????????? D.數(shù)據(jù)冗余
3．數(shù)據(jù)庫系統(tǒng)的基本特點(diǎn)
數(shù)據(jù)獨(dú)立性 是數(shù)據(jù)與程序間的互不依賴性，即數(shù)據(jù)庫中數(shù)據(jù)獨(dú)立于應(yīng)用程序而不依賴于應(yīng)用程序。也就是說，數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和存取方式的改變都不會(huì)影響應(yīng)用程序。數(shù)據(jù)獨(dú)立性包括物理獨(dú)立性和?? 邏輯獨(dú)立性 兩個(gè)含義。
當(dāng)數(shù)據(jù)的物理結(jié)構(gòu)(存儲結(jié)構(gòu)、存取方式等)改變時(shí)，不影響數(shù)據(jù)庫的邏輯結(jié)構(gòu)．從而不致引起應(yīng)用程序的變化，這是指數(shù)據(jù)的?? 物理獨(dú)立性?? 。
4．數(shù)據(jù)庫系統(tǒng)的內(nèi)部結(jié)構(gòu)
數(shù)據(jù)庫系統(tǒng)在其內(nèi)部具有三級模式及二級映射，三級模式分別是概念級模式、內(nèi)部級模式與外部級模式，二級映射分別是概念級到內(nèi)部級的映射以及外部級到概念級的映射。這種三級模式與二級映射構(gòu)成了數(shù)據(jù)庫系統(tǒng)內(nèi)部抽象結(jié)構(gòu)體系。
14.單個(gè)用戶使用的數(shù)據(jù)視圖的描述稱為(外模式)。索引屬于(內(nèi)模式)。

二、數(shù)據(jù)模型
1．數(shù)據(jù)模型的基本概念
數(shù)據(jù)模型是數(shù)據(jù)庫設(shè)計(jì)的核心。其內(nèi)容有三個(gè)部分：數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作和數(shù)據(jù)約束
數(shù)據(jù)模型按不同應(yīng)用層次分3種類型，它們是概念數(shù)據(jù)模型、邏輯數(shù)據(jù)模型和物理數(shù)據(jù)模型。
概念數(shù)據(jù)模型簡稱概念模型，是面向客觀世界、面向用戶的模型；是整個(gè)數(shù)據(jù)模型的基礎(chǔ)。與具體的數(shù)據(jù)庫管理系統(tǒng)無關(guān)，著重于對客觀事件的結(jié)構(gòu)描述以及它們之間的內(nèi)在聯(lián)系的刻畫。常用的有E-R模型、擴(kuò)充的E-R模型等。
邏輯數(shù)據(jù)模型又稱數(shù)據(jù)模型，是面向數(shù)據(jù)庫系統(tǒng)的模型，著重于數(shù)據(jù)庫系統(tǒng)一級的實(shí)現(xiàn)。概念模型只有在轉(zhuǎn)換成數(shù)據(jù)模型后才有可能在數(shù)據(jù)庫中得以表示。常見的有層次模型、網(wǎng)狀模型和關(guān)系模型。
數(shù)據(jù)庫管理系統(tǒng)常見的數(shù)據(jù)模型有層次模型、網(wǎng)狀模型和 關(guān)系模型 3種。
15.下列數(shù)據(jù)模型中，具有堅(jiān)實(shí)理論基礎(chǔ)的是(C)。
A.層次模型?? B.網(wǎng)狀模型?? C.關(guān)系模型?? D.以上3個(gè)都是
16.下列說法中，不屬于數(shù)據(jù)模型所描述的內(nèi)容的是(C)。
A.數(shù)據(jù)結(jié)構(gòu)?? B.數(shù)據(jù)操作?? C.數(shù)據(jù)查詢?? D.數(shù)據(jù)約束
2．E-R模型
17.實(shí)體是信息世界中廣泛使用的一個(gè)術(shù)語，它用于表示(C)。
A.有生命的事物?? B.無生命的事物?? C.實(shí)際存在的事物?? D.一切事物
18.E-R模型由 實(shí)體 、聯(lián)系 和 屬性 三個(gè)基本概念組成。
19.將E—R圖轉(zhuǎn)換到關(guān)系模式時(shí)，實(shí)體與聯(lián)系都可以表示成(關(guān)系)。
20.下列敘述中，正確的是(A)。
A.用E—R圖能夠表示實(shí)體集間一對一的聯(lián)系、一對多的聯(lián)系和多對多的聯(lián)系
B.用E—R圖只能表示實(shí)體集之問一對一的聯(lián)系
C.用E—R圖只能表示實(shí)體集之間一對多的聯(lián)系
D.用E—R圖表示的概念數(shù)據(jù)模型只能轉(zhuǎn)換為關(guān)系數(shù)據(jù)模型
21.公司中有多個(gè)部門和多名職員，每個(gè)職員只能屬于一個(gè)部門，一個(gè)部門可以有多名職員，從職員到部門的聯(lián)系類型是(多對一)。
3．層次模型和網(wǎng)狀模型
4．關(guān)系模型
22.在關(guān)系模型中，把數(shù)據(jù)看成一個(gè)二維表，每一個(gè)二維表稱為一個(gè)?? 關(guān)系
23.最常用的一種基本數(shù)據(jù)模型是關(guān)系數(shù)據(jù)模型，它的表示應(yīng)采用(二維表)。
24.由關(guān)系數(shù)據(jù)庫系統(tǒng)支持的完整性約束是指?? 實(shí)體完整性?? 和參照完整性。
25.關(guān)系模型允許定義3類數(shù)據(jù)約束，下列不屬于數(shù)據(jù)約束的是(C)。
A.實(shí)體完整性約束?? B.參照完整性約束 C.域完整性約束?? D.用戶自定義的完整性約束
26.“年齡在18歲一25歲之間”這種約束是屬于數(shù)據(jù)庫中的( C )。
A.原子性措施 B.一致性措施?? C.完整性措施?? D.安全性措施
27.關(guān)系模型的數(shù)據(jù)操縱是建立在關(guān)系上的數(shù)據(jù)操縱，一般有查詢、增加、刪除和修改四種操作。
28.下列4項(xiàng)中．必須進(jìn)行查詢優(yōu)化的是( A)。
A.關(guān)系數(shù)據(jù)庫?? B.網(wǎng)狀數(shù)據(jù)庫?? C.層次數(shù)據(jù)庫?? D.非關(guān)系模型

三、關(guān)系代數(shù)
29.關(guān)系操作的特點(diǎn)是?? 集合?? 操作。
30.關(guān)系數(shù)據(jù)庫的關(guān)系演算語言是以?? 謂詞演算?? 為基礎(chǔ)的DML語言。
31.一個(gè)關(guān)系中屬性個(gè)數(shù)為l時(shí)，稱此關(guān)系為(一元關(guān)系)。
32.關(guān)系表中的每一橫行稱為一個(gè)(元組)。
33.下列關(guān)系模型中，能使經(jīng)運(yùn)算后得到的新關(guān)系中屬性個(gè)數(shù)多于原來關(guān)系中屬性個(gè)數(shù)的是(B)。A.選擇?? B.連接?? C.投影?? D.并
34.關(guān)系運(yùn)算?? 是從二維表列的方向進(jìn)行的運(yùn)算。
35.關(guān)系數(shù)據(jù)庫管理系統(tǒng)應(yīng)能實(shí)現(xiàn)的專門的關(guān)系運(yùn)算包括(選擇、投影、連接)。

四、數(shù)據(jù)庫設(shè)計(jì)與管理
數(shù)據(jù)庫設(shè)計(jì)概述
36.數(shù)據(jù)庫設(shè)計(jì)包括兩個(gè)方面的設(shè)計(jì)內(nèi)容，它們是(D)。A.概念設(shè)計(jì)和邏輯設(shè)計(jì)
B.模式設(shè)計(jì)和內(nèi)模式設(shè)計(jì)?? C.內(nèi)模式設(shè)計(jì)和物理設(shè)計(jì)?? D.結(jié)構(gòu)特性設(shè)計(jì)和行為特性設(shè)計(jì)
37.數(shù)據(jù)庫設(shè)計(jì)分為以下6個(gè)設(shè)計(jì)階段：需求分析階段、 概念設(shè)計(jì)階段 、邏輯設(shè)計(jì)階段、物理設(shè)計(jì)階段、實(shí)施階段、運(yùn)行和維護(hù)階段。
數(shù)據(jù)庫設(shè)計(jì)的需求分析
38.對數(shù)據(jù)庫設(shè)計(jì)來講，數(shù)據(jù)字典 是進(jìn)行詳細(xì)的數(shù)據(jù)收集和數(shù)據(jù)分析所獲得的主要結(jié)果。
數(shù)據(jù)庫概念設(shè)計(jì)
39.數(shù)據(jù)庫概念設(shè)計(jì)的目的是分析數(shù)據(jù)間內(nèi)在語義聯(lián)系，在此基礎(chǔ)上建立一個(gè)數(shù)據(jù)的抽象模型。方法有以下兩種：集中式模式設(shè)計(jì)法、視圖集成設(shè)計(jì)法。
40.視圖設(shè)計(jì)一般有3種設(shè)計(jì)次序，下列不屬于視圖設(shè)計(jì)次序的是(B)。
A.自頂向下?? B.由外向內(nèi)?? C.由內(nèi)向外?? D.自底向上
數(shù)據(jù)庫的邏輯設(shè)計(jì)
41.數(shù)據(jù)庫的邏輯設(shè)計(jì)的主要工作是將E-R圖轉(zhuǎn)換成指定RDBMS（關(guān)系數(shù)據(jù)庫管理系統(tǒng)）中的關(guān)系模式，另一個(gè)重要內(nèi)容是關(guān)系視圖的設(shè)計(jì)，又稱外模式設(shè)計(jì)。
42.在數(shù)據(jù)庫設(shè)計(jì)中，將E—R圖轉(zhuǎn)換成關(guān)系數(shù)據(jù)模型的過程屬于(邏輯設(shè)計(jì)階段)。
數(shù)據(jù)庫的物理設(shè)計(jì)
43.數(shù)據(jù)庫的物理設(shè)計(jì)主要目標(biāo)是對數(shù)據(jù)庫內(nèi)部物理結(jié)構(gòu)做出調(diào)整并選擇合理的存取路徑，以提高數(shù)據(jù)庫訪問速度及有效利用存儲空間。大致包括：索引設(shè)計(jì)、集簇設(shè)計(jì)和分區(qū)設(shè)計(jì)。
數(shù)據(jù)庫管理
44.數(shù)據(jù)庫是一種共享資源，需要維護(hù)與管理，這種工作稱為 數(shù)據(jù)庫管理 。實(shí)施此項(xiàng)管理的人稱為數(shù)據(jù)庫管理員。數(shù)據(jù)庫的建立包括兩部分的內(nèi)容：數(shù)據(jù)模式的建立和數(shù)據(jù)加載。
45.數(shù)據(jù)庫在運(yùn)行一段時(shí)間以后，性能會(huì)逐步下降，需要對數(shù)據(jù)庫進(jìn)行重新整理，重新調(diào)整存貯空間，這種工作叫數(shù)據(jù)庫重組。
46.數(shù)據(jù)庫的故障恢復(fù)一般是由DBA完成的
47.數(shù)據(jù)庫保護(hù)分為：安全性控制、完整性控制、并發(fā)性控制和數(shù)據(jù)的恢復(fù)。
48.數(shù)據(jù)庫恢復(fù)是將數(shù)據(jù)庫從錯(cuò)誤狀態(tài)恢復(fù)到某一已知的正確狀態(tài)。
SQL語句的循序漸進(jìn)寫法
二級VF考試中，SQL語言部分占了很大比例，可以說該部分掌握好壞直接關(guān)系到整個(gè)考試的成敗。
???? 在上機(jī)考試中，初學(xué)者在進(jìn)行SQL語言查詢時(shí)常常丟三拉四，或是標(biāo)點(diǎn)符號的全角半角搞錯(cuò)了，或丟掉了某些必要步驟，導(dǎo)致很長時(shí)間也無法得到正確輸入。
那么，如何能書寫好的復(fù)雜SQL查詢語句呢？
????? 本人歸納了一套循序漸進(jìn)的書寫方法，對于初學(xué)者非常有效。
1) SQL語句的格式可以歸納為：
select 字段 from 表;
? where 篩選條件;
? group by 分組字段;
??? having 分組條件;
? order by 排序字段 asc,desc
2) 學(xué)習(xí)語言可以認(rèn)為是一個(gè)學(xué)習(xí)填空的過程。語言的框架已經(jīng)在設(shè)計(jì)語言編譯器時(shí)就給定了，用戶不可違背，必須遵守語言提供好的規(guī)范，用戶做的就是把自己需要表達(dá)的東西以填空的方式填入其中。
2.1) 分析數(shù)據(jù)源，嘗試在命令窗口運(yùn)行基本框架直到正確。
單表可以在命令窗口中輸入：select * from 表
雙表可以在命令窗口中輸入：select * from 表1,表2 where 表1.聯(lián)接字段=表2.聯(lián)接字段
三表需要分析表如何鏈接然后在命令窗口中輸入：select * from 表1,表2,表3 where 表1.聯(lián)接字段=表2.聯(lián)接字段 and 表2.聯(lián)接字段=表3.聯(lián)接字段
如果采用超聯(lián)接模式書寫，
雙表模式可以書寫為：select * from 表1 join 表2 on 表1.聯(lián)接字段=表2.聯(lián)接字段
三表模式可以書寫為：select * from 表1 join 表2 join 表3 on 表2.聯(lián)接字段=表3.聯(lián)接字段 and 表1.聯(lián)接字段=表2.聯(lián)接字段
2.2) 分析篩選條件，將其轉(zhuǎn)換為邏輯表達(dá)式。
光標(biāo)移動(dòng)到上一步驟命令末尾，補(bǔ)充篩選條件，然后回車檢查。
如果出現(xiàn)錯(cuò)誤或同預(yù)期結(jié)果不同，說明剛才輸入語句有問題，修改后繼續(xù)回車檢查。
2.3) 補(bǔ)充篩選字段，具體操作類似上一步，光標(biāo)移動(dòng)到上一步驟命令末尾，補(bǔ)充篩選條件，然后回車檢查。
如果出現(xiàn)錯(cuò)誤或同預(yù)期結(jié)果不同，說明剛才輸入語句有問題，修改后繼續(xù)回車檢查。
2.4) 補(bǔ)充排序條件
??? 以上操作看似煩瑣，實(shí)則不然：每次增加的部分不是全部SQL語句重新輸入，而是在已經(jīng)成功的命令行基礎(chǔ)上予以修訂和補(bǔ)充。上一步驟已經(jīng)正確完成了，出現(xiàn)錯(cuò)誤的話只能是本步驟操作失誤造成的，修改增加部分即可。
相反，由于初學(xué)者對SQL語法格式不熟悉，書寫SQL語句巴不得一氣呵成，一旦發(fā)生錯(cuò)誤，往往會(huì)用大量時(shí)間去調(diào)試，反而欲速而不達(dá)。
根據(jù)題目要求還可以繼續(xù)補(bǔ)充：
2.5) 補(bǔ)充分組字段，增加group by語句，查看能否正確分組，但這時(shí)一定注意，select * from 表 group by 分組字段彈出每一行記錄除少數(shù)字段有意義外，因此最好隨后修改顯示字段
2.6) 在增加分組字段正確后，補(bǔ)充having條件
2.7) 最后補(bǔ)充其它信息，如top短語、into table等短語等
以下題為例采用循序漸進(jìn)法予以說明：
例：以表employee.dbf和orders.dbf中數(shù)據(jù)為基礎(chǔ)，使用SQL命令檢索訂單數(shù)最多的前三名男職工的職工號、姓名、訂單數(shù)，檢索結(jié)果按訂單數(shù)降序存入表newcoun.dbf中。
employee(職工號,姓名,性別,年齡)
orders(訂單號,訂購物品,訂購單位,訂購日期,職工號)
分析：首先打開兩表，發(fā)現(xiàn)兩表屬于1對多關(guān)系，一個(gè)職工對應(yīng)多個(gè)訂單。沒有訂單數(shù)字段，只能按照職工號分組然后通過COUNT計(jì)數(shù)后求出訂單數(shù)量。
操作：
1) 搭建框架，在命令窗口中輸入基本框架：select * from employee e join orders o on e.職工號=o.職工號
2) 補(bǔ)充篩選字段，光標(biāo)移動(dòng)到上一行末尾，補(bǔ)充為：select * from employee e join orders o on e.職工號=o.職工號 where 性別="男"
3) 補(bǔ)充分組字段，光標(biāo)移動(dòng)到上一行末尾，補(bǔ)充為：select * from employee e join orders o on e.職工號=o.職工號 where 性別="男" group by e.職工號
4) 修改顯示字段：select e.職工號,姓名,count(*) as 訂單數(shù) from employee e join orders o on e.職工號=o.職工號 where 性別="男" group by e.職工號
5) 沒有having分組條件，補(bǔ)充top短語：select top 3 e.職工號,姓名,count(*) as 訂單數(shù) from employee e join orders o on e.職工號=o.職工號 where 性別="男" group by e.職工號
6) 補(bǔ)充查詢?nèi)ハ?#xff1a;select top 3 e.職工號,姓名,count(*) as 訂單數(shù) from employee e join orders o on e.職工號=o.職工號 where 性別="男" group by e.職工號 into table newcoun
大家可以把這種方法推廣到其它方面，也可在查詢設(shè)計(jì)器中套用該方法。總之，操作不可急于求成，要按部就班，循序漸進(jìn)。

轉(zhuǎn)載于:https://www.cnblogs.com/pekkle/archive/2008/04/09/6568863.html

總結(jié)

以上是生活随笔為你收集整理的[转载]数据结构笔试题基础的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。