計(jì)算機(jī)二級(jí)選擇題

不要害怕,不要直接放棄!

目標(biāo)：至少15?20分

1、公共基礎(chǔ)10分（不在于理解，在于掌握做題方法+適當(dāng)?shù)挠洃洠?/p>

數(shù)據(jù)結(jié)構(gòu)與算法（5分）

程序設(shè)計(jì)基礎(chǔ)（2分）

軟件工程基礎(chǔ)（2分）

數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)（1分）

2、計(jì)算機(jī)基礎(chǔ)知識(shí)4分

3、Office6分

6設(shè)數(shù)據(jù)元素的集合D={1,2,3,4,5）,則滿足下列關(guān)系R的數(shù)據(jù)結(jié)構(gòu)中為線性結(jié)構(gòu)的是

R=((1,2),⑶2),(5,1),(4,5)}

R={(1,3),(4,1),(3,2),(5,4))

R={(1,2),(2,4),(4,5),(2,3)}

R={(1,3),(2,4),(3,5),(1,2))

計(jì)算機(jī)二級(jí)公共基礎(chǔ)

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

一、算法

算法是指解題方案的準(zhǔn)確而完整的迤述。算法不等于程序,也不等于計(jì)算方法。程序的編

制不可能優(yōu)于算法的設(shè)計(jì)。

比如：旅游（先規(guī)劃一再實(shí)施）

比如：在3,6,8,4,5里面找出最大數(shù)

編程完成問題：在一無序數(shù)據(jù)系列中找出最大數(shù)（n個(gè)數(shù)）:

算法：用第一個(gè)數(shù)和第二數(shù)比較，取較大數(shù)；

用這個(gè)較大數(shù)和下一個(gè)數(shù)比，取較大數(shù);

經(jīng)過以上步驟n步，獲得最大數(shù)。

程序：

#include<stdio.h>

voidmain()

(

inta[4],i,m;

scanf("%d",&a[0]);

m=a[0];

for(i=l;i<4;i++)

(

scanf("%d",&a[i]);

if(a[i]>m)

m=a[i];

printf("Themaxnumberis%d",m);

)

2、算法的基本特征

(1)可行性。

(2)確定性。每一條指令的含義明確，無二義性。并且在任何條件下，算法只有唯一的

一條執(zhí)行路徑，即相同的輸入只能得出相同的輸出。

(3)有窮性。算法必須在有限的時(shí)間內(nèi)完成。有兩重含義，一是算法中的操作步驟為有

限個(gè)，二是每個(gè)步驟都能在有限時(shí)間內(nèi)完成。

(4)擁有足夠的情報(bào)。

3、算法復(fù)雜度主要包括時(shí)間復(fù)雜度和空間復(fù)雜度。兩個(gè)之間沒有直接聯(lián)系。

(1)算法時(shí)間復(fù)雜度是指執(zhí)行算法所需要的吐復(fù)建量，可以用執(zhí)行算法的過程中所需

基本運(yùn)算的執(zhí)行次數(shù)來度量。

(2)算法空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)底空回。

4、設(shè)計(jì)算法時(shí)不僅要考慮對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作，還要考慮算法的控制結(jié)構(gòu)。

基本運(yùn)算包括：算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)傳輸。

算法的控制結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。

練習(xí)

【1】、算法的有窮性是指（）。

A）算法程序的運(yùn)行時(shí)間是有限的B）算法程序所處理的數(shù)據(jù)量是有限的

C）算法程序的長度是有限的D）算法只能被有限的用戶使用

正確答案：A

【解析】：有窮性是指算法程序的運(yùn)行時(shí)間是有限的。

【2】、算法的空間復(fù)雜度是指（）。

A）算法在執(zhí)行過程中所需要的計(jì)算機(jī)存儲(chǔ)空間

B）算法所處理的數(shù)據(jù)量

C）算法程序中的語句或指令條數(shù)

D）算法在執(zhí)行過程中所需要的臨時(shí)工作單元數(shù)

正確答案：A

【解析】：算法的空間復(fù)雜度是指算法在執(zhí)行過程中所需要的內(nèi)存空間。

[3]、下列關(guān)于算法敘述正確的是（）。

A）算法就是程序

B）設(shè)計(jì)算法時(shí)只需要考慮數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)

C）設(shè)計(jì)算法時(shí)只需要考慮結(jié)果的可靠性

D）以上三種說法都不對(duì)

正確答案：D

【解析】：算法是指解題方案的準(zhǔn)確而完整的描述，算法不等于程序，也不等于計(jì)算方法，所以A錯(cuò)

誤。設(shè)計(jì)算法時(shí)不僅要考慮對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作，還要考慮算法的控制結(jié)構(gòu)。

【4】、下列敘述中正確的是（）

A）一個(gè)算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度也必定大

B）一個(gè)算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度必定小

C）一個(gè)算法的時(shí)間復(fù)雜度大，則其空間復(fù)雜度必定小

D）算法的時(shí)間復(fù)雜度與空間復(fù)雜度沒有直接關(guān)系

正確答案：D

【解析】：算法的空間復(fù)雜度是指算法在執(zhí)行過程中所需要的內(nèi)存空間，算法的時(shí)間復(fù)雜度，是指執(zhí)

行算法所需要的計(jì)算工作量，兩者之間并沒有直接關(guān)系，答案為D。

[5]、下列敘述中正確的是（）

A）算法的效率只與問題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)

B卜算法時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量

C）數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)是一一對(duì)應(yīng)的

D）算法的時(shí)間復(fù)雜度與空間復(fù)雜度一定相關(guān)

正確答案：B

【解析】：算法的效率與問題的規(guī)模和數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)都有關(guān)，A錯(cuò)誤。算法的時(shí)間復(fù)雜度，是指執(zhí)

行算法所需要的計(jì)算工作量，B正確。由于數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間中的位置關(guān)系可能與邏輯關(guān)系

不同，因此數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)不是一一對(duì)應(yīng)的，C錯(cuò)誤。算法的時(shí)間復(fù)雜度和空間復(fù)雜度沒

有直接的聯(lián)系，D錯(cuò)誤。

難度提升:

■?下列敘述中正確的是

?

算法的時(shí)間復(fù)雜度與算法程序中的語句條數(shù)成正比10下列敘述中錯(cuò)誤的是

?算法的時(shí)間復(fù)雜度與運(yùn)行算法時(shí)特定的輸入有關(guān)?對(duì)于各種特定的輸入，算法的時(shí)間復(fù)雜度是固定不變的

算法的時(shí)間復(fù)雜度與算法程序編制者的水平有關(guān)算法的時(shí)間復(fù)雜度與使用的計(jì)算機(jī)系統(tǒng)無關(guān)

算法的時(shí)間復(fù)雜度與計(jì)算機(jī)的運(yùn)行速度有關(guān)算法的時(shí)間復(fù)雜度與使用的程序設(shè)計(jì)語言無關(guān)

ID:56488算法的時(shí)間復(fù)雜度與實(shí)現(xiàn)算法過程中的具體細(xì)節(jié)無關(guān)

，如要查找的數(shù)據(jù)恰好是人

第1個(gè)元素，只需比較1次

；如要查找的數(shù)據(jù)是最后

一個(gè)元素，貝M個(gè)額據(jù)需要

比較n次。2

□標(biāo)記

二、數(shù)據(jù)結(jié)構(gòu)

1、數(shù)據(jù)結(jié)構(gòu)的基本概念

a、數(shù)據(jù)：如聲音、視頻、文字、圖像；學(xué)校的學(xué)生信息、公安部門的公民信息、銀行的存款信息

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

c、數(shù)據(jù)結(jié)構(gòu)研究三個(gè)方面的問題：

邏輯結(jié)構(gòu)：就是各數(shù)據(jù)元素之間的前后件關(guān)系?？梢岳斫鉃閳D紙上畫出來的關(guān)系圖（線性結(jié)構(gòu)、非線性結(jié)構(gòu)）

存儲(chǔ)結(jié)構(gòu)：各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有順序、鏈?zhǔn)健⑺饕取?/p>

對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算：直找、排序、刪除、插入等

同一種邏輯結(jié)構(gòu)的數(shù)據(jù)可以采用不同的存儲(chǔ)結(jié)構(gòu)，但影響數(shù)據(jù)處理效率。

春夏秋冬

按順序在9個(gè)房間里面找到9顆龍珠，即可打開大寶藏。

一、順序存儲(chǔ)

?????????寶藏

12345678910

二、鏈?zhǔn)酱鎯?chǔ)

123456789101112131415

數(shù)據(jù)域指針域

datanexta——aaA

Q）結(jié)點(diǎn)結(jié)構(gòu)仆）一個(gè)非空的線性鏈表示意圖

AT族TCI》I篇

三、索引學(xué)生信息登記表

班級(jí)名稱學(xué)號(hào)姓名身份證號(hào)出生日期家庭住址

有一個(gè)索引表13級(jí)旅管1201301020001陶欣'5001234567890919281994/1/18重慶大足

13級(jí)旅管1201301020002劉靈'5109808765243512341995/7/12重慶梁平

13級(jí)旅管1201301020003常志明,4009875628191018281991/9/17湖北利川

13級(jí)旅管1201301020004蔣順"5120192837464525491994/6/7湖北咸豐

13級(jí)旅管1201301020005張宇澄'5139817591747293081994/7;8重慶永川

13級(jí)旅管1201301020006趙小矛'4092716486234508121994/8/1重慶南川

13級(jí)旅管1201301020007惇二說下色限5151234567898765431993/6/1重慶墊江

13級(jí)旅管1201301020008白敏'5030548971239876511994/11/14重慶酉陽

13級(jí)旅管1201301020009楊婷婷'5059827465892097611994/10/13重慶黔江

13級(jí)旅管1201301020010稅正芳'4149873645789012871995/4/1四川瀘州

13級(jí)旅管1201301020011傅茂竹,4567891234987659321994/3/10重慶萬盛

13級(jí)旅管1201301020012陳建英'5061239876543212111993/3/24重慶石柱

棧

三、數(shù)據(jù)結(jié)構(gòu)（邏輯結(jié)構(gòu)）分為兩大類型：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。

（1）線性結(jié)構(gòu)（非空的數(shù)據(jù)結(jié)構(gòu)）條件：

1）有且只有一個(gè)根鯉;（在數(shù)據(jù)結(jié)構(gòu)中，沒有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn)。）

2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。

常見的線性結(jié)構(gòu)有線返和線性鏈表等。

（2）非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。

*：常見的非線性結(jié)構(gòu)有樹、二叉樹和網(wǎng)等。

【1】、下列敘述中正確的是（）。

A）有一祁上根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不一定是非線性結(jié)構(gòu)

B）只有一個(gè)根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不一定是線性結(jié)構(gòu)

28下列敘述中正確的是

有且只有一個(gè)根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)可能是線性結(jié)構(gòu)，也可能是非線性結(jié)構(gòu)

有且只有一個(gè)根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)一定是線性結(jié)構(gòu)

有且只有一個(gè)根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)一定是非線性結(jié)構(gòu)

每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件也最多有一個(gè)后件的數(shù)據(jù)結(jié)構(gòu)一定是線性結(jié)構(gòu)

四、線性表（邏輯結(jié)構(gòu)）

1.1）有且只有一個(gè)根結(jié)點(diǎn)；2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。

學(xué)生1學(xué)生2學(xué)生3學(xué)生4學(xué)生5

線性表可能是空表

2、存儲(chǔ)方式：順序存儲(chǔ)方式和鏈?zhǔn)酱鎯?chǔ)方式。

245,9,8

24598

線性表的順序存儲(chǔ)結(jié)構(gòu)具有以下兩個(gè)基本特點(diǎn)：

(1)線性表中所有元素的所占的存儲(chǔ)空間是連續(xù)的；

(2)線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。

245,9,8

245

3、線性表的插入、刪除，直找(直找某個(gè)數(shù)和查找最大數(shù)、最小數(shù))運(yùn)算

順序存儲(chǔ)、和鏈?zhǔn)酱鎯?chǔ)

24598

結(jié)論：1、在插入刪除操作里面，順序存儲(chǔ)要移動(dòng)數(shù)據(jù)，鏈?zhǔn)酱鎯?chǔ)不移動(dòng)數(shù)據(jù)，鏈?zhǔn)酱鎯?chǔ)

優(yōu)于順序存儲(chǔ)，順序存儲(chǔ)插入、刪除運(yùn)算不方便。

2、在長度為n的線性表中，查找某個(gè)數(shù)最壞情況下需要查找n次；

3、在長度為n的線性表中，找到最大數(shù)（或者最小數(shù)）需要比較n-1次

■@下列關(guān)于線性鏈表的敘述中，正確的是

■o進(jìn)行插入與刪除時(shí)，不需要移動(dòng)表中的元素

Io各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與邏輯順序可以不一致，但它們的存儲(chǔ)空間必須連續(xù)

Ic各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)空間可以不連續(xù)，但它們的存儲(chǔ)順序與邏輯順序必須一致

下列敘述巾正確的是

線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間一般要少于順序存儲(chǔ)結(jié)構(gòu)

線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)空間都是連續(xù)的

線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間可以是連續(xù)的，也可以是不連續(xù)的

28下列敘述中正確的是

有且只有一個(gè)根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)可能是線性結(jié)構(gòu)，也可能是非線性結(jié)構(gòu)

o有且只有一個(gè)根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)一定是非線性結(jié)構(gòu)

o有且只有一個(gè)根結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)一定是線性結(jié)構(gòu)

o每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件也最多有一個(gè)后件的數(shù)據(jù)結(jié)構(gòu)一定是線性結(jié)構(gòu)

41下列敘述中正確的是

順序存儲(chǔ)結(jié)構(gòu)能存儲(chǔ)有序表，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不能存儲(chǔ)有序表

O鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)比順序存儲(chǔ)結(jié)構(gòu)節(jié)省存儲(chǔ)空間

順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)一定是連續(xù)的，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間不一定是連續(xù)的

O順序存儲(chǔ)結(jié)構(gòu)只針時(shí)線性結(jié)構(gòu)，鋅式存儲(chǔ)結(jié)構(gòu)只針時(shí)非線性結(jié)構(gòu)

2線性表的長度為n。在最壞情況下，比較次數(shù)為n-l的算法是

?尋找最大項(xiàng)

O有序表的插入

O同時(shí)尋找最大項(xiàng)與最小項(xiàng)

O順序查找

5在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，其存儲(chǔ)空間一般是不連續(xù)的，并且

前件結(jié)點(diǎn)的存儲(chǔ)序號(hào)小于后件結(jié)點(diǎn)的存儲(chǔ)序號(hào)

@前件結(jié)點(diǎn)的存儲(chǔ)序號(hào)可以小于也可以大于后件結(jié)點(diǎn)的存儲(chǔ)序號(hào)

前件結(jié)點(diǎn)的存儲(chǔ)序號(hào)大于后件結(jié)點(diǎn)的存儲(chǔ)序號(hào)

答案:BID:56405

t解析】鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)使人

得節(jié)點(diǎn)在內(nèi)存中不受位置

的限制，結(jié)點(diǎn)存儲(chǔ)號(hào)可以

是任意的，并且能夠保證

邏輯上的線性關(guān)系。故前

□標(biāo)記

五、棧

定義：棧是限定在一端進(jìn)行插入與刪除運(yùn)算的線性表。（棧是線性結(jié)構(gòu)）

在棧中，允許插入與刪除的一端稱為棧頂（top）---移動(dòng)的，變化的，不允許插入與刪除

的另一端稱為棧底（bottom）（棧底固定不變）。棧是按照〃先進(jìn)后出〃或“后進(jìn)先出〃

的原則組織數(shù)據(jù)的。

正棧

1、把2,3,1,5,6,8入棧再出橇p6

2、空棧:top<bottom5

初始狀態(tài)或者

top=-l04

3、滿棧:top達(dá)到最大值

3

4、計(jì)算棧中元素個(gè)數(shù)：

2

Top-Bottom+1

<—Bottom1

大-小+1

0

【1】、下列關(guān)于棧的敘述正確的是（）。

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

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

正確答案：B

[2]、一個(gè)棧的初始狀態(tài)為空?，F(xiàn)將元素，2、3、4、5、A、B、C、D、E依次入棧，然后再依

次出棧，則元素出棧的順序是（）。

A）12345ABCDEB）EDCBA54321C）ABCDE12345D）54321EDCBA

正確答案：B

【6】、下列關(guān)于棧敘述正確的是（）。

A）棧頂元素最先能被刪除B）棧頂元素最后才能被刪除

C）棧底元素永遠(yuǎn)不能被刪除D）棧底元素最先被刪除

正確答案：A

【7】、下列敘述中正確的是（）。

A）在棧中，棧中元素隨棧底指針與棧頂指針的變化而動(dòng)態(tài)變化

B）在棧中，棧頂指針不變，棧中元素隨棧底指針的變化而動(dòng)態(tài)變化

C)在棧中，棧底指針不變，棧中元素隨棧頂指針的變化而動(dòng)態(tài)變化

D)以上說法均不正確

正確答案：C

[8]、設(shè)棧的存儲(chǔ)空間為s(l:50),初始狀態(tài)為top=-l.經(jīng)過一系列正常的入棧與退棧操作后,

top=30,則棧中元素個(gè)數(shù)為：

a:30b:19c:31d:20

技巧：本例中用top初始值來判斷為一個(gè)正棧。

1、把2,3,1,5,6,8入棧再出棧

2、空棧：初始狀態(tài)

<—Bottom

Top=m+1

3、滿棧Top

4、計(jì)算棧中元素個(gè)數(shù)：

botton-Top+1

大-小+1

假設(shè)用一個(gè)長度為50的數(shù)組（數(shù)組元素的下標(biāo)為。到49）作為棧的存儲(chǔ)空間，棧底指

針bottom指向棧底元素，棧頂指針指向棧頂元素，如果bottom=49,top=30,則棧

中有（）個(gè)元素

綜合舉例：三、29、31

四、28、41、46、49

五、45、46、48

帶鏈棧:

1、帶鏈?？盏臈l件是：top=bottom=NULL,如果top=bottom且不為NULL,說

明有一個(gè)元素。

2、帶鏈棧不會(huì)溢出（不會(huì)滿棧）

五、40、49、53、54、55

小結(jié)：

1、先進(jìn)后出FILO;

工、支持子程序調(diào)用；

[9]、支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是（）。

A）棧B）樹C）隊(duì)列D）二叉樹

正確答案：A

2、具有記憶功能；

3、可以不用順序存放數(shù)據(jù)；

4、只能夠在top首部進(jìn)行操作，bottom是絕對(duì)不動(dòng)的;

5、棧的存放數(shù)據(jù)的個(gè)數(shù)為：大-小+1；

六.隊(duì)列（線性結(jié)構(gòu)）

Front

普通隊(duì)列

012345678

t

2,5,7,1,8

Rear

隊(duì)列是指允許在一端（隊(duì)尾）進(jìn)行插入，而在另一端（隊(duì)頭）出仃惻除的線性表。

1、Rear指針指向隊(duì)尾,front指針指向隊(duì)頭。

2、先進(jìn)先出FIFO,或者是后進(jìn)后出LILO

2,57,1,8入隊(duì)出隊(duì)

3、隊(duì)列可以是順序存儲(chǔ)結(jié)構(gòu)，也可以是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

4、右圖18（隊(duì)列-作業(yè)調(diào)度）

5、帶鏈隊(duì)列空的條件是：top=bottom=NULL,如果top=bottom且不為NULL,說

明有1個(gè)元素。

18下列與隊(duì)列結(jié)構(gòu)有關(guān)聯(lián)的是

21下列敘述中正確的是

先到先服務(wù)的作業(yè)調(diào)度

@帶鏈隊(duì)列的存儲(chǔ)空間可以不連續(xù)，且隊(duì)頭指針可以大于也可以小于隊(duì)尾指針多重循環(huán)的執(zhí)行

帶鏈隊(duì)列的存儲(chǔ)空間可以不連續(xù)，但隊(duì)頭指針必須小于隊(duì)尾指針

數(shù)組元素的弓I用

帶鏈隊(duì)列的存儲(chǔ)空間可以不連續(xù)，但隊(duì)頭指針必須大于隊(duì)尾指針

函數(shù)的遞歸調(diào)用

-X循環(huán)隊(duì)列

B、rear<front的時(shí)候,num=rear-front+n;（n為容量）

C、rear二front的時(shí)候，循環(huán)隊(duì)列可能為滿，可能為空

2、循環(huán)隊(duì)列中的元素個(gè)數(shù)隨隊(duì)頭指針與隊(duì)尾指針的變化而動(dòng)態(tài)變化

3、循環(huán)隊(duì)列是隊(duì)列的一種順序存儲(chǔ)結(jié)構(gòu)。（循環(huán)隊(duì)列不能使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，而一般的隊(duì)

列是可以使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的）

9下列敘述中正確的是

循環(huán)隊(duì)列是隊(duì)列的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

循環(huán)隊(duì)列是隊(duì)列的一種順序存儲(chǔ)結(jié)構(gòu)

O循環(huán)隊(duì)列是非線性結(jié)構(gòu)

循環(huán)隊(duì)列是一種邏輯結(jié)構(gòu)

練習(xí)：第一部分：4,9,12,18,21,42,44,48

第二部分:2,7,14,21,22,25,28,33,41,44

第三部分:10,14,16,22,24,35,39

第四部分：31,35

第五部分：8,13,16,44,50,51,70（由于軟件升級(jí)，紅色部分到第6部分去了。第

5部分的題庫順序發(fā)送了變化，請(qǐng)大家做第5部分和第6部分里面隊(duì)列的題）

七樹與二叉樹（非線性結(jié)構(gòu)）

一）樹

1、樹是一種簡單的非線性結(jié)構(gòu)，所有元素之間具有明顯的層次特性。［1題】

2、在樹結(jié)構(gòu)中，沒有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹的根結(jié)點(diǎn)，簡稱樹的根。

3、每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。

4、沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。葉子節(jié)點(diǎn)的度為0

5、在樹結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的

度稱為樹的度。樹的最大層次稱為樹的深度。

重點(diǎn)掌握的：根、葉子結(jié)點(diǎn)、度、

樹的度、樹的深度

*6、一棵樹的結(jié)點(diǎn)數(shù)=結(jié)點(diǎn)個(gè)數(shù)*結(jié)點(diǎn)度數(shù)+1

?21設(shè)一棵度為3的樹，其中度為2,1,0的結(jié)點(diǎn)數(shù)分別為3,1,6。該樹中度為3的結(jié)點(diǎn)數(shù)為

.o1

O3

O不可能有這樣的樹

2

二）二叉樹的特點(diǎn)：

1、非空二叉樹只有一個(gè)根結(jié)點(diǎn)；

2、每一個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹。

e

EF

3、二叉樹的基本性質(zhì)：必考的題目

(1)在二叉樹的第k層上，最多有21(kN1)個(gè)結(jié)點(diǎn)；

(2)深度為k的二叉樹最多有2?<-1個(gè)結(jié)點(diǎn)；

(3)度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)；【2題】

二叉樹中二叉樹節(jié)點(diǎn)的度只能為【、、題】

(4)n=n0+ni+n2(0,1,2)345

4、滿二叉樹

是指除最后一層外，每一層上的所有結(jié)點(diǎn)1有兩個(gè)子結(jié)點(diǎn)，則k層上有個(gè)結(jié)

點(diǎn)深度為k的滿二叉樹有2k-1個(gè)結(jié)點(diǎn)。

5、完全二叉樹是指除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上只

缺少右邊的若干結(jié)點(diǎn)。完全二叉樹中度為1的結(jié)點(diǎn)數(shù)為?；蛘?個(gè)?！?、8題】

滿二叉樹I完全二叉樹完全二叉樹

非完全二叉樹非完全二叉樹

[1]、下列數(shù)據(jù)結(jié)構(gòu)中，屬于非線性結(jié)構(gòu)的是（）O

A）循環(huán)隊(duì)列B）帶鏈隊(duì)列C）二叉樹D）帶鏈棧

正確答案：C

【2】、某二叉樹有5個(gè)度為2的結(jié)點(diǎn)，則該二叉樹中的葉子結(jié)點(diǎn)數(shù)是（）。

A）10B）8C）6D）4

正確答案：c

【3】、一棵二叉樹共有25個(gè)結(jié)點(diǎn)，其中5個(gè)是葉子結(jié)點(diǎn)，則度為工的結(jié)點(diǎn)數(shù)為（）

A）16B）10C）6D）4

正確答案：A

[4]、某二叉樹共有7個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)只有1個(gè)，則該二叉樹的深度為（假設(shè)根結(jié)點(diǎn)在

第1層）（）o

A）3B）4C）6D）7

正確答案：D

【5】、一棵二叉樹中共有80個(gè)葉子結(jié)點(diǎn)與70個(gè)度為1的結(jié)點(diǎn),則該二叉樹中的總

結(jié)點(diǎn)數(shù)為()

A)219B)229C)230D)231

正確答案：B

【6】、深度為7的完全二叉樹中共有125個(gè)結(jié)點(diǎn)則該完全二叉樹中的葉子結(jié)點(diǎn)數(shù)為

()。

A)62B)63C)64D)65

正確答案：B

【解析】：深度為k的完全二叉樹最多有2匕1個(gè)結(jié)點(diǎn)，第k層最多有2皿個(gè)結(jié)點(diǎn)。前6

層總共結(jié)點(diǎn)數(shù)=2A6-1=63,這里總共有125個(gè)，所以第7層有125-63=62個(gè)。

另外，第6層32個(gè)。所以葉子結(jié)點(diǎn)數(shù)二第6層葉子結(jié)點(diǎn)(第7層62個(gè)結(jié)點(diǎn)需要31

個(gè)結(jié)點(diǎn)發(fā)出左右子樹，只有一個(gè)結(jié)點(diǎn)沒有左右孩子)+第7層葉子結(jié)點(diǎn)(該層所有結(jié)點(diǎn)

為葉子結(jié)點(diǎn))=1+62=63

【7】、下列敘述中正確的是（）。

A）結(jié)點(diǎn)中具有兩個(gè)指針域的鏈表一短三叉藤

B）結(jié)點(diǎn)中具有兩個(gè)指針域的鏈表可以是線性結(jié)構(gòu)，也可以是非線性結(jié)構(gòu)

C）二叉樹只能采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

D）循環(huán)鏈表是非線性結(jié)構(gòu)

正確答案：B

【8】、一棵完全二叉樹共有360個(gè)節(jié)點(diǎn)，則在該二叉樹中度為1的結(jié)點(diǎn)個(gè)數(shù)為：

a）181b）0c）180d）l

正確答案：d

習(xí)題

一部分:16、22、26、35、49

二部分:1、11、16、32、40、46、48

三部分：4、7、13、17、20

四部分:21、40五部分:1、2、7、49六部分:23

=）二叉樹的遍歷

1、二叉樹存儲(chǔ)結(jié)構(gòu)一般采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，對(duì)于滿二叉樹與完全二叉樹可以按層序進(jìn)行

順序存儲(chǔ)。

2、二叉樹的遍歷：（一般畫個(gè)圖要你把順序?qū)懗鰜恚?/p>

（1）前序遍歷（根左右），首先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹；

（2）中序遍歷（左根右），首先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹；

（3）后序遍歷（左右根）首先遍歷左子樹，然后訪問遍歷右子樹，最后訪問根結(jié)點(diǎn)。

前序：123

中序:213

后續(xù)：231

[1].對(duì)下列二叉樹進(jìn)行前序遍歷的結(jié)果為（）

A)DYBEAFCZXB)YDEBFZXCAC)ABDYECFXZD)ABCDEFXYZ

練習(xí)：第三部分：44、45、46

前序：ABDYECFXZ

中序：DYBEAFCZX

后續(xù)：YDEBFZXCA

3、通過其中兩個(gè)遍歷，推導(dǎo)出另外一個(gè)遍歷

方法：找根然后分左右

步驟：a、前序后序確認(rèn)根;（前序中第一個(gè)節(jié)點(diǎn)是根，后續(xù)中最后一個(gè)節(jié)

點(diǎn)是根）

B.中序確認(rèn)左右；（確定根后，用中序確定左右樹）

3設(shè)某二叉樹的前序序列為ABC,中序序列為CBA,則該二叉樹的后序序列為

BCA

CAB

CBA

ABC

6設(shè)某二叉樹的后序序列為CBA,中序序列為ABC,則該二叉樹的前序序列為

ABC

CBA

BCA

CAB

19某二叉樹的前序序列為ABCDEFG,中序序列為DCBAEFG,則該二叉樹的深度（根結(jié)點(diǎn)在第1層）為

O3

O5

O4

O2

?

某二叉樹的前序序列為ABCDEFG,中序序列為DCBAEFG,則該二叉樹的后序序列為

DCBGFEA

DCBEFGA

BCDGFEA

EFGDCBA

30）設(shè)二叉樹的后序序列與中序序列均為ABCDEFGH,則該二叉樹的前序序列為

DCBAHGFE

HGFEDCBA

ABCDEFGH

EFGHABCD

ABCDHGFE

某完全二叉樹按層次輸出（同一層從左到右）的序列為ABCDEFGH。該完全二叉樹的前序序列為

ABCDEFGH

ABDHECFG

HDEBFGCA

HDBEAFCG

練習(xí):二部分:3、6、19、23、29、42、50

三部分：1、30、34、43、44、45、46

四部分：1、11、12、13-18.32、36、47

六部分:9、12、17、19

八、數(shù)據(jù)結(jié)構(gòu)補(bǔ)遺

1、線性表

數(shù)

士

構(gòu)

據(jù)

設(shè)\

B-RRJ其

口-Z

{bcef}

，JJ

DM={d,bVX

a,MgI

Z(a,/

該,d,d)

士

數(shù)(e,e)

(f據(jù)

a)構(gòu)￥

口/

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

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

循環(huán)鏈表

循環(huán)隊(duì)列

3、堆

Z131下列各序列中不是堆的是

答案:BID:56380O(91,85,53,36,47,30,24,12)

大根雄，所有節(jié)點(diǎn)的值大A(47,91,53,85,30,12,24,36)

于或等于左右子結(jié)點(diǎn)的值O

；小根堆，所有節(jié)點(diǎn)的值

小于或等于左右子結(jié)點(diǎn)的O(91,85,53,47,36,30,24,12)

值。v

(91,85,53,47,30,12,24,36)

□標(biāo)記

下列敘述中錯(cuò)誤的是（）。

。向量是線性結(jié)構(gòu)

O非空線性結(jié)構(gòu)中只有一個(gè)結(jié)點(diǎn)沒有前件

O非空線性結(jié)構(gòu)巾只有一個(gè)結(jié)點(diǎn)沒有后件

⑥只有一個(gè)根結(jié)點(diǎn)和一個(gè)葉子結(jié)點(diǎn)的結(jié)構(gòu)必定是線性結(jié)構(gòu)

1）下列數(shù)據(jù)結(jié)構(gòu)中，不能采用順序存儲(chǔ)結(jié)構(gòu)的是（）。

⑥非完全二叉樹

。堆棧

。隊(duì)列

練習(xí)：三部分：18

九1、查找技術(shù)

1、順序查找的使用情況：

長度為n的線性表，找出一個(gè)數(shù)據(jù)，最壞的情況為比較n次。

長度為n的線性表，找出一個(gè)最大（最?。?shù)據(jù)，最差的情況為比較n-1次。

2、二分法查找只適用于順隹僮的有序表：5,8,10,26,34,76

二分查找：對(duì)于長度為n的有序線性表，最壞情況只需比較log2n次。

4在長度為97的順序有序表中作二分查找，最多需要的比較次數(shù)為（）。

06

096

048

07

十、排序技術(shù)

1、排序是指將一個(gè)無序序列整理成按值非遞減順序排列的有序序列。

2、冒泡排序、快速排序、簡單插入排序、選擇排序，最壞情況下需要比較

n（n」）/2次

希爾排序法，最壞情況需要0（n15）次比較。

堆排序法，最壞情況需要O(nlog2n)次比較。

3、排序最壞情況下時(shí)間復(fù)雜度最小(排序的次數(shù))的是堆排序。

n(n-1)/2>n15>nlog2n

4、已經(jīng)學(xué)習(xí)的算法時(shí)間復(fù)雜度關(guān)系

n(n-1)/2>n15>nlog2n>n>n-l>log2n

【工】、對(duì)長度為10的線性表進(jìn)行冒泡排序，最壞情況下需要比較的次數(shù)為()

A)9B)10C)45D)90

【2】、對(duì)長度為n的線性表排序，在最壞情況下，比較次數(shù)不是n(n-l)/2的排序方法

是()

A)快速排序B)冒泡排序C)簡單插入排序"""D)堆排序

正確答案：D

【3】、堆排序最壞情況下的時(shí)間復(fù)雜度為()。

15

A)0(n)B)O(nlog2n)C)O(n(n-l)/2)D)O(log2n)

正確答案：B

【4】、對(duì)長度為n的線性表排序,在最壞情況下,比較次數(shù)不是n(n-l)/2的排序方

法是()。

A)快速排序B)冒泡排序C)直接插入排序"""D)堆排序

正確答案：D

【5】、下列排序方法中，最壞情況下比較次數(shù)最少的是()。

A)冒泡排序B)簡單選擇排序"""C)直接插入排序"""D)堆排序

Q）在希爾排序法中，每經(jīng)過一次數(shù)據(jù)交換后（）。

15設(shè)表的長度為n。在下列結(jié)構(gòu)所時(shí)應(yīng)的算法中，最壞情況下時(shí)間復(fù)雜度最低的是

o只能消除一個(gè)逆序

循環(huán)鏈表中尋找最大項(xiàng)

。能消除多個(gè)逆序

O堆排序

。不會(huì)產(chǎn)生新的逆序

有序鏈表查找

。消除的逆序個(gè)數(shù)一定比新產(chǎn)生的逆序個(gè)數(shù)多

希爾排序

正確答案：B

答疑；在希爾排序過程中，雖然對(duì)于每一個(gè)子表采用的仍是插入排序

排序過程的性能。故答案為B。

38下列算法中，最壞情況下時(shí)間復(fù)雜度最低的是

■?有序表的對(duì)分查找

Io堆排序

Io尋找最大項(xiàng)

Io順序查找

練習(xí)：

一部分:8、23、27、32、43

二部分：10

三部分:15、33、42、48、49、50

四部分：3、4、5、22、25

五部分:9、10、11、12、13、14、17（不要求X18（不要求X19

六部分:1、2、5、7、15,18、29、33、38

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

一、程序設(shè)計(jì)設(shè)計(jì)方法和風(fēng)格

1、注釋分序言性注釋和功能性注釋；

2、語句結(jié)構(gòu)清晰第一、效率第二；程序一定要求具有易讀性，可讀性較好。

3、程序設(shè)計(jì)方法有兩種：結(jié)構(gòu)化程序設(shè)計(jì)和面向?qū)ο蟪绦蛟O(shè)計(jì)。

二、結(jié)構(gòu)化程序設(shè)計(jì)

結(jié)構(gòu)化程序設(shè)計(jì)方法的四條原則是：考試重點(diǎn)都要背下來

1.自頂向下；

2.逐步求精；

3.模塊化；

4.限制使用goto語句。

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

(1)順序結(jié)構(gòu)

(2)選擇結(jié)構(gòu)：又稱分支結(jié)構(gòu)

(3)循環(huán)結(jié)構(gòu)(重復(fù)結(jié)構(gòu))

三、面向?qū)ο蟮某绦蛟O(shè)計(jì)

1、對(duì)象由對(duì)象名、屬性和操作(方法)三部分組成。

屬性即對(duì)象所包含的信息，操作描述了對(duì)象執(zhí)行的功能，操作也稱為方法或服務(wù)。

2、面向?qū)ο蠡靖拍睿?/p>

?對(duì)象

?類和實(shí)例：類是指具有共同屬性、共同方法的對(duì)象的集合。類是對(duì)象的抽象，

對(duì)象是對(duì)應(yīng)類的一個(gè)實(shí)例。

?消息：消息是一個(gè)實(shí)例與另一個(gè)實(shí)例之間傳遞的信息。

?繼承：繼承是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義他們。類之

間共享屬性和操作的機(jī)制。

?多態(tài)性：多態(tài)性是指同樣的消息被不同的對(duì)象接受時(shí)可導(dǎo)致完全不同的行動(dòng)的

現(xiàn)象

3、對(duì)象的基本特點(diǎn)：

(1)標(biāo)識(shí)惟一性；

(2)分類性；

(3)多態(tài)性；

(4)封裝性；

(5)模塊獨(dú)立性好。

4、面向?qū)ο蠓椒ǖ膬?yōu)點(diǎn)：

(1)與人類習(xí)慣的思維方法一致；

(2)穩(wěn)定性好；

(3)可重用性好；

(4)易于開發(fā)大型軟件產(chǎn)品；

(5)可維護(hù)性好。

【1】、在面向?qū)ο蠓椒ㄖ?，不屬于〃?duì)象〃基本特點(diǎn)的是（）。

A）一致性B）分類性C）多態(tài)性D）標(biāo)識(shí)唯一性

正確答案：A

【2】、面向?qū)ο蠓椒ㄖ?，繼承是指（）。

A）一組對(duì)象所具有的相似性質(zhì)B）一個(gè)對(duì)象具有另一個(gè)對(duì)象的性質(zhì)

C）各對(duì)象之間的共同性質(zhì)D）類之間共享屬性和操作的機(jī)制

正確答案：D

【3】、下列選項(xiàng)中屬于面向?qū)ο笤O(shè)計(jì)方法主要特征的是（）。

A）繼承B）自頂向下C）模塊化D）逐步求精

正確答案：A

【4】、下面對(duì)對(duì)象概念描述正確的是（）

A）對(duì)象間的通信靠消息傳遞B）對(duì)象是名字和方法的封裝體

C）任何對(duì)象必須有繼承性D）對(duì)象的多態(tài)性是指一個(gè)對(duì)象有多個(gè)操作

正確答案：A

【5】、面向?qū)ο蠓椒ㄖ?，?shí)現(xiàn)對(duì)象的數(shù)據(jù)和操作結(jié)合于統(tǒng)一體中的是（）。

A）結(jié)合B）封裝C）隱藏D）抽象

正確答案：B

【6】、定義無符號(hào)整數(shù)類為Ulnt,下面可以作為類UInt的實(shí)例化值的是（）。

A）-369B）369C）0.369D）整數(shù)集合{1,234,5}

正確答案：B

練習(xí)：

一部分:12,18,30

二部分:1,21,47,48,49,50,

三部分:1,2,4—13,16,22,23,36,37

四部分：3,6,7,12,18,22,32,36,37,40,43,46,51,52,53,54,55,56,57,58

第三章軟件工程基礎(chǔ)

一、軟件工程基本概念

1、軟件工程是用工程、科學(xué)和數(shù)學(xué)的原則和方法研制，維護(hù)計(jì)算機(jī)軟件的有關(guān)技術(shù)及管理方法。

軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。

2、軟件的特點(diǎn)包括：

(1)軟件是一種邏輯實(shí)體；

(2)軟件的生產(chǎn)與硬件不同，它沒有明顯的制作過程；

(3)軟件在運(yùn)行、使用期間不存在磨損、老化問題；

(4)軟件的開發(fā)、運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依賴性，

(5)軟件復(fù)雜性高，成本昂貴；

(6)軟件開發(fā)涉及諸多的社會(huì)因素。

3、軟件按功能分為應(yīng)用軟件、系統(tǒng)軟件、支撐軟件(或工具軟件)?！?】

11數(shù)據(jù)庫管理系統(tǒng)是系統(tǒng)軟件。

21教務(wù)處管理系統(tǒng)是應(yīng)用軟件。(學(xué)生、財(cái)務(wù))

4、軟件危機(jī)主要表現(xiàn)在成本、質(zhì)量、生產(chǎn)率等問題。

軟件危機(jī)主要表現(xiàn)在：

1）軟件需求的增長得不到滿足。用戶對(duì)系統(tǒng)不滿意的情況經(jīng)常發(fā)生。

2）軟件開發(fā)成本和進(jìn)度無法控制。開發(fā)成本超出預(yù)算，開發(fā)周期大大超過規(guī)定日期的情況經(jīng)常發(fā)生。

3）軟件質(zhì)量難以保證。

4）軟件不可維護(hù)或維護(hù)程度非常低。

5）軟件的成本不斷提高。

6）軟件開發(fā)生產(chǎn)率的提高跟不上硬件的發(fā)展和應(yīng)用需求的增長。

5、軟件工程包括3個(gè)要素：方法、工具、過程。

方法：完成軟件工程項(xiàng)目的技術(shù)手段。

工具：支持軟件的開發(fā)、管理、文檔生成。

過程：支持軟件開發(fā)的各個(gè)環(huán)節(jié)的控制、管理。

6、軟件生命周期：軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過程。[9、10]

軟件生命周期三個(gè)階段:軟件定義.軟件開發(fā)、運(yùn)行維護(hù)，軟件生命周期中所花費(fèi)最多的階段是軟

件運(yùn)行維護(hù)階。

1）軟件定義階段：包括可行性分析和需求分析。

a.需求分析

*：需求分析的主要任務(wù)就是解決"做什么”的問題。

*：需求分析方法有：結(jié)構(gòu)化需求分析方法.面向?qū)ο蟮姆治龇椒ā?/p>

*：需求分析一般分為需求獲取、需求分析、編寫需求規(guī)格說明書【3、13、17,20]和需

求評(píng)審四個(gè)步驟進(jìn)行。

b、結(jié)構(gòu)化需求分析方法

常用工具：1）數(shù)據(jù)流圖（DFD）;2）數(shù)據(jù)字典（DD）;3）判定樹；4）判定表。DD

為了解釋DFD[4]

*：數(shù)據(jù)字典的作用是對(duì)數(shù)據(jù)流圖中出現(xiàn)的被命名的圖形元素的確切解釋。

登錄系統(tǒng)

客戶

加工數(shù)據(jù)流存儲(chǔ)文件源、潭

2）軟件開發(fā)階段:

軟件設(shè)計(jì)：分為概要設(shè)計(jì)（總體設(shè)計(jì)）和詳細(xì)設(shè)計(jì)兩個(gè)部分。

軟件實(shí)現(xiàn)：編寫程序。軟件設(shè)計(jì)中模塊劃分應(yīng)遵循的準(zhǔn)則高內(nèi)聚，低耦合。［2、7］（大內(nèi)高手）

軟件測試：測試各部分發(fā)現(xiàn)錯(cuò)誤。

a、軟件概要設(shè)計(jì)（總體設(shè)計(jì)）

a）基本任務(wù)是：寬度:"整體控制密度7最大模炭數(shù)面前為袤東7

（1）設(shè)計(jì)軟件系統(tǒng)結(jié)構(gòu)（總結(jié)構(gòu)）；扇入：調(diào)用一個(gè)給定模塊的模塊個(gè)數(shù)。

（2）數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫設(shè)計(jì)；扇出：一個(gè)模塊直接調(diào)用的其他模塊數(shù)。

原子模塊：樹中位于葉子結(jié)點(diǎn)的模塊。

（3）編寫概要設(shè)計(jì)文檔；

（4）概要設(shè)計(jì)文檔評(píng)審。深度為4

b）相關(guān)概念：寬度為6

F的扇入為2

深度［HL寬度、扇入、扇出D的扇出為3

原子模塊：樹中位于葉子結(jié)點(diǎn)的模塊。原子模塊為5

最大扇入、最大扇出

b、詳細(xì)設(shè)計(jì)：是為軟件結(jié)構(gòu)圖中的每一個(gè)模塊確定實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用某種選定的表達(dá)工

具表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。

常見的過程設(shè)計(jì)工具有：考試重點(diǎn)

1、程序流程圖、N-S（方盒圖）、PAD（問題分析圖）和HIPO（層次圖+輸入/處理/輸出圖工

表格工具（判定表1語言工具PDL（偽碼）[8、15]

程序流程圖是考試重點(diǎn)，其中——-箭頭表示控制流【1】，菱形表示邏輯條件。

c、軟件測試

軟件測試的目的：發(fā)現(xiàn)錯(cuò)誤?！?】

軟件測試方法：靜態(tài)測試和動(dòng)態(tài)測試。

靜態(tài)測試：不實(shí)際運(yùn)行軟件，主要通過人工進(jìn)行。

動(dòng)態(tài)測試：是基本計(jì)算機(jī)的測試，主要包括白盒測試方法和黑盒測試方法。

白盒主要方法：1、邏輯覆蓋測試2、基本路徑測試3、語句覆蓋，在程序內(nèi)部進(jìn)行，白盒是可以看

見的。

黑盒主要方法[14]:1等價(jià)類劃分法、2邊界值分析法、3錯(cuò)誤推測法、4因果圖。

軟件測試過程一般按4個(gè)步驟進(jìn)行（要背先后順序）：【19】

單元測試、集成測試、驗(yàn)收測試（確認(rèn)測試）和系統(tǒng)測試。

3.5程序的調(diào)試[12]

程序調(diào)試的任務(wù)是診斷（發(fā)現(xiàn)）和改正程序中的錯(cuò)誤，debug

程序調(diào)試的任務(wù)是診斷和改正程序中的錯(cuò)誤，主要在開發(fā)階段進(jìn)行。

動(dòng)態(tài)調(diào)試是輔助靜態(tài)調(diào)試。

調(diào)試方法有：（1）強(qiáng)行排錯(cuò)法；（2）回溯法；（3）原因排除法。

最后13、16、18

[1]、程序流程圖中帶有箭頭的線段表示的是（）O

A）圖元關(guān)系B）數(shù)據(jù)流C）控制流D）調(diào)用關(guān)系

正確答案：c

【解析工在數(shù)據(jù)流圖中，用標(biāo)有名字的箭頭表示數(shù)據(jù)流。在程序流程圖中，用標(biāo)有名字的箭頭表示控制流。所以選擇C。

【2】、軟件設(shè)計(jì)中模塊劃分應(yīng)遵循的準(zhǔn)則是（）。

A）低內(nèi)聚低耦合B）高內(nèi)聚低耦合C）低內(nèi)聚高耦合D）高內(nèi)聚高耦合

正確答案：B

[3]、在軟件開發(fā)中，需求分析階段產(chǎn)生的主要文檔是（）。

A）可行性分析報(bào)告B）軟件需求規(guī)格說明書

C）概要設(shè)計(jì)說明書D）集成測試計(jì)劃

正確答案：B

[4]、在軟件開發(fā)中，需求分析階段可以使用的工具是（）o

A）N-S圖B）DFD圖C）PAD圖D）程序流程圖

正確答案：B

【5】、軟件按功能可以分為：應(yīng)用軟件、系統(tǒng)軟件和支撐軟件（或工具軟件）。下面屬于應(yīng)用軟件的是（）。

A）編譯程序B）操作系統(tǒng)C）教務(wù)管理系統(tǒng)~D）匯編程序

正確答案：C

[6]、下面敘述中錯(cuò)誤的是（）

A）軟件測試的目的是發(fā)現(xiàn)錯(cuò)誤并改正錯(cuò)誤

B）對(duì)被調(diào)試的程序進(jìn)行“錯(cuò)誤定位"是程序調(diào)試的必要步驟

C）程序調(diào)試通常也稱為Debug

D）軟件測試應(yīng)嚴(yán)格執(zhí)行測試計(jì)劃，排除測試的隨意性

正確答案：A

[7]、耦合性和內(nèi)聚性是對(duì)模塊獨(dú)立性度量的兩個(gè)標(biāo)準(zhǔn)。下列敘述中正確的是（）o

A）提高耦合性降低內(nèi)聚性有利于提高模塊的獨(dú)立性

B）降低耦合性提高內(nèi)聚性有利于提高模塊的獨(dú)立性

C）耦合性是指一個(gè)模塊內(nèi)部各個(gè)元素間彼此結(jié)合的緊密程度

D）內(nèi)聚性是指模塊間互相連接的緊密程度

正確答案：B

【8】、軟件詳細(xì)設(shè)計(jì)生產(chǎn)的圖如下：

該圖是（）

A）N-S圖B）PAD圖C）程序流程圖D）E-R圖

正確答案：C

【9】、軟件生命周期是指（）。

A）軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過程

B）軟件從需求分析、設(shè)計(jì)、實(shí)現(xiàn)到測試完成的過程

C）軟件的開發(fā)過程

D）軟件的運(yùn)行維護(hù)過程

正確答案：A

[10]、軟件生命周期中的活動(dòng)不包括（）。

A）市場調(diào)研B）需求分析C）軟件測試D）軟件維護(hù)

正確答案：A

[11]、某系統(tǒng)總體結(jié)構(gòu)圖如下圖所示：

該系統(tǒng)總體結(jié)構(gòu)圖的深度是（）。

A）7B）6C）3D）2

正確答案：c

[12]、程序調(diào)試的任務(wù)是（）。

A）設(shè)計(jì)測試用例"B）驗(yàn)證程序的正確性

C）發(fā)現(xiàn)程序中的錯(cuò)誤D）診斷和改正程序中的錯(cuò)誤

正確答案：D

、下面不屬于需求分析階段任務(wù)的是（

[13]）o

A）確定軟件系統(tǒng)的功能需求B）確定軟件系統(tǒng)的性能需求

C）需求規(guī)格說明書評(píng)審D）制定軟件集成測試計(jì)劃

正確答案：D

【14】、在黑盒測試方法中，設(shè)計(jì)測試用例的主要根據(jù)是（）o

A）程序內(nèi)部邏輯B）程序外部功能C）程序數(shù)據(jù)結(jié)構(gòu)D）程序流程圖

正確答案：B

[15]、在軟件設(shè)計(jì)中不使用的工具是（）。

A）系統(tǒng)結(jié)構(gòu)圖