公共基礎(chǔ)知識(shí)點(diǎn)合集

1、第一章 數(shù)據(jù)結(jié)構(gòu)與算法考點(diǎn)1：算法（概念、特征、組成、方法、算法的復(fù)雜度）1、 算法的概念(1) 概念：是指解題方案的準(zhǔn)確而完整的描述?！究碱}1】在計(jì)算機(jī)中，算法是指( ) A 查詢方法 B 加工方法 C對(duì)解題方案的準(zhǔn)確而完整的描述 D 排序方法【答案】：C【考題2】問題處理方案的正確而完整的描述稱為 ?！敬鸢浮浚核惴?、 算法的特征(1) 算法的特征具有4種：可行性、確定性、有窮性、擁有足夠的情報(bào)。 可行性：在算法的執(zhí)行過(guò)程中，每一個(gè)步驟都要可行，可通。經(jīng)過(guò)執(zhí)行能夠得到一個(gè)結(jié)果。 確定性：算法中的每一個(gè)步驟都要有確切的含義，不能有二義性，對(duì)于相同的輸入必須能得出相同的執(zhí)行結(jié)果。 有窮性：一個(gè)

2、算法包含的操作步驟是有限的。也就是說(shuō)，在執(zhí)行若干個(gè)操作步驟之后算法結(jié)束，而且每一個(gè)步驟都要在合理的時(shí)間內(nèi)完成。 擁有足夠的情報(bào)：即擁有足夠的輸入數(shù)據(jù)。通過(guò)大量的給算法輸入數(shù)據(jù)來(lái)驗(yàn)證算法輸出的結(jié)果是否有誤?！究碱}1】下列選項(xiàng)中不屬于算法特征的是( )A 無(wú)窮性 B 確定性 C 可行性 D 擁有足夠的情報(bào)【答案】：A【考題2】對(duì)于一個(gè)算法，它必須要在有限步驟合理時(shí)間內(nèi)完成，這屬于算法的( )A 可行性 B 確定性 C 有窮性 D擁有足夠的情報(bào)【答案】：C【考題3】在算法中，算法的特征具有可行性、確定性、 、擁有足夠的情報(bào)?！敬鸢浮浚河懈F性3、 算法的組成(1) 算法的組成有兩種：對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和

3、操作、算法的控制結(jié)構(gòu)。(2) 算法的控制結(jié)構(gòu)有3種：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。4、 算法的方法(1) 在算法中，對(duì)問題描述的方法有6種：列舉法、歸納法、遞推、遞歸、減半遞推技術(shù)、回溯法。5、 算法的復(fù)雜度(1) 算法的復(fù)雜度是對(duì)算法中的各種方法進(jìn)行衡量的標(biāo)準(zhǔn)。(2) 算法的復(fù)雜度有兩種：算法的時(shí)間復(fù)雜度和算法的空間復(fù)雜度。 算法的時(shí)間復(fù)雜度：是指執(zhí)行算法所需要的（計(jì)算工作量）基本運(yùn)算次數(shù)。 算法的空間復(fù)雜度：是指執(zhí)行算法所需要的內(nèi)存空間。 【知道】算法時(shí)間復(fù)雜度的好與壞不會(huì)影響空間復(fù)雜度的好與壞?！究碱}1】算法的時(shí)間復(fù)雜度是指( )A 執(zhí)行算法程序所需要的時(shí)間 B 算法程序的長(zhǎng)度 C 算法

4、執(zhí)行過(guò)程中所需要的基本運(yùn)算次數(shù) D 算法程序中的指令條數(shù)【答案】：C【考題2】算法的空間復(fù)雜度是指( )A 算法程序的長(zhǎng)度 B 算法程序中的指令條數(shù) C 算法程序所占的存儲(chǔ)空間 D 算法執(zhí)行過(guò)程中所需要的存儲(chǔ)空間【答案】：D【考題3】下列敘述中正確的是( )A 一個(gè)算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度也必定大 B 一個(gè)算法的空間復(fù)雜度大，則其時(shí)間復(fù)雜度必定小 C 一個(gè)算法的時(shí)間復(fù)雜度大，則其空間可復(fù)雜度必定小 D 上述三種說(shuō)法都不對(duì) 【答案】：D【解析】：算法時(shí)間復(fù)雜度的好與壞不會(huì)影響空間復(fù)雜度的好與壞?？键c(diǎn)2：數(shù)據(jù)結(jié)構(gòu)（邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、線性表、棧、隊(duì)列、樹和二叉樹、查找和排序）1、 數(shù)據(jù)結(jié)

5、構(gòu)(1) 數(shù)據(jù)結(jié)構(gòu)主要研究和討論三個(gè)方面的內(nèi)容：邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、運(yùn)算。【考題1】數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的 和數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。【答案】：邏輯結(jié)構(gòu)2、 邏輯結(jié)構(gòu)(1) 滿足邏輯結(jié)構(gòu)的的條件： 表示數(shù)據(jù)元素的信息； 表示各數(shù)據(jù)元素之間的前后件關(guān)系。(2) 邏輯結(jié)構(gòu)的分類：線性結(jié)構(gòu)、非線性結(jié)構(gòu)。 線性結(jié)構(gòu)：有且只有一個(gè)根結(jié)點(diǎn)；每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。 在本書中，線性結(jié)構(gòu)主要講到的有：線性表、棧、隊(duì)列。 非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的就屬于非線性結(jié)構(gòu)。 在本書中，非線性結(jié)構(gòu)主要講到的有：樹、二叉樹。【考題1】數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的( )A 存儲(chǔ)結(jié)構(gòu) B 物理結(jié)構(gòu)

6、C 邏輯結(jié)構(gòu) D 物理和存儲(chǔ)結(jié)構(gòu)【答案】：C【解析】：邏輯結(jié)構(gòu)討論的是現(xiàn)實(shí)世界中數(shù)據(jù)與數(shù)據(jù)之間的關(guān)系；存儲(chǔ)結(jié)構(gòu)也叫物理結(jié)構(gòu)，指的是邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間的存放形式。所以存儲(chǔ)結(jié)構(gòu)和計(jì)算機(jī)有關(guān)。A、B和D都不選?！究碱}2】以下數(shù)據(jù)結(jié)構(gòu)中不屬于線性結(jié)構(gòu)的是( ) A 隊(duì)列 B 線性表 C 二叉樹 D ?！敬鸢浮浚篊【考題3】數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和 兩大類?！敬鸢浮浚悍蔷€性結(jié)構(gòu)3、 存儲(chǔ)結(jié)構(gòu)(1) 概念：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(也稱數(shù)據(jù)的物理結(jié)構(gòu))(2) 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存儲(chǔ)形式通常有兩種：順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 順序存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)在

7、存儲(chǔ)空間中必須連續(xù)，且元素之間一定要有前后件的關(guān)系。 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：數(shù)據(jù)在存儲(chǔ)空間中不一定連續(xù)，且各元素的存儲(chǔ)順序是任意的。(3) 兩種存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)： 順序存儲(chǔ)結(jié)構(gòu)：優(yōu)點(diǎn)是查找方便。缺點(diǎn)是插入、刪除不方便。 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：優(yōu)點(diǎn)是插入、刪除方便。缺點(diǎn)是查找不方便?！究碱}1】數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指( ) A 存儲(chǔ)在外存中的數(shù)據(jù) B 數(shù)據(jù)所占的存儲(chǔ)空間C 數(shù)據(jù)在計(jì)算機(jī)中的順序存儲(chǔ) D 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示【答案】：D【考題2】下列敘述正確的是( )A 一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲(chǔ)結(jié)構(gòu) B 數(shù)據(jù)的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)屬于非線性結(jié)構(gòu) C 一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多

8、種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)不影響數(shù)據(jù)處理的效率 D 一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)影響數(shù)據(jù)處理的效率 【答案】：D【解析】：一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，例如順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。所以A答案不正確；數(shù)據(jù)的邏輯結(jié)構(gòu)分為兩類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)形式可以有多種，例如順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)都是我們數(shù)據(jù)結(jié)構(gòu)的討論內(nèi)容。所以B答案不正確；只有D答案正確，因?yàn)橐粋€(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，例如順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)影響數(shù)據(jù)處理的效率?！究碱}3】下列敘述中正確的是( ) A 算法的

9、效率只與問題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(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【解析】：算法的執(zhí)行效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)密切相關(guān)。所以A不正確；B是正確的；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)中的順序存儲(chǔ)結(jié)構(gòu)是一一對(duì)應(yīng)的（一致的），而與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)就不一定一一對(duì)應(yīng)了。所以C不正確；算法時(shí)間復(fù)雜度的好與壞不會(huì)影響空間復(fù)雜度的好與壞，所以不相關(guān)，故D不正確。【考題4】下列敘述中正確的是( )A 程序執(zhí)行的效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)密切相關(guān) B 程序執(zhí)行的效率只取決于程序的控制結(jié)構(gòu)C 程序執(zhí)行的效率只取決于所處

10、理的數(shù)據(jù)量 D 以上三種說(shuō)法都不對(duì)【答案】：A4、 線性表(1) 線性表往計(jì)算機(jī)中進(jìn)行存放，不僅可以采用順序存儲(chǔ)結(jié)構(gòu)存放，還可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存放。 順序表：即線性表采用順序存儲(chǔ)結(jié)構(gòu)存放。 線性鏈表：即線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存放。(2) 順序表和線性鏈表的特點(diǎn)： 順序表：隨機(jī)（訪問）存取、查找方便，插入刪除不方便、事先估計(jì)存儲(chǔ)空間。 線性鏈表：順序（訪問）存取、插入刪除方便，查找不方便、不必事先估計(jì)存儲(chǔ)空間?！究碱}1】在下面關(guān)于線性表的敘述中，選出正確的一項(xiàng)( ) A 線性表的每一個(gè)元素都有一個(gè)直接前驅(qū)和直接后繼 B 線性表中至少要有一個(gè)元素C 線性表中的元素必須按遞增或遞減的順序排列D 除

11、第一個(gè)元素和最后一個(gè)元素外，每個(gè)元素都有一個(gè)直接前驅(qū)和直接后繼【答案】：D【解析】：A答案不正確，因?yàn)槌谝粋€(gè)元素和最后一個(gè)元素外，每個(gè)元素都有一個(gè)直接前驅(qū)和直接后繼；B答案不正確，線性表中也可以沒有元素，此時(shí)為空表；C答案不正確，線性表中元素的排列順序沒有要求；D答案正確?！究碱}2】下列對(duì)線性鏈表描述正確的是( ) A 存儲(chǔ)空間不一定連續(xù)，且各元素的存儲(chǔ)順序是任意的 B 存儲(chǔ)空間不一定連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面 C 存儲(chǔ)空間必須連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面 D 存儲(chǔ)空間必須連續(xù)，且各元素的存儲(chǔ)順序是任意的【答案】：A【解析】：線性表采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)時(shí)，數(shù)據(jù)在計(jì)算

12、機(jī)存儲(chǔ)空間中必須連續(xù)，且元素之間一定要有前后件的關(guān)系；線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)時(shí)，數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)空間中不一定連續(xù)，且各元素的存儲(chǔ)順序是任意的?！究碱}3】下列對(duì)線性表敘述中，正確的一項(xiàng)是( ) A 采用鏈?zhǔn)酱鎯?chǔ)的線性表，必須占用一片連續(xù)的存儲(chǔ)單元 B 采用順序存儲(chǔ)的線性表，便于進(jìn)行插入和刪除操作 C 采用鏈?zhǔn)酱鎯?chǔ)的線性表，不必占用一片連續(xù)的存儲(chǔ)單元D 鏈?zhǔn)胶晚樞虼鎯?chǔ)的線性表，都便于進(jìn)行插入和刪除操作【答案】：C【解析】：線性表采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)時(shí)，數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)空間中必須連續(xù)，且元素之間一定要有前后件的關(guān)系；線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)時(shí)，數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)空間中不一定連續(xù)，且各元素的存儲(chǔ)順

13、序是任意的。順序表便于查找，線性鏈表便于插入和刪除操作。【考題4】線性表的順序存儲(chǔ)結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)分別是( )A 順序存取的存儲(chǔ)結(jié)構(gòu)、順序存取的存儲(chǔ)結(jié)構(gòu)B 隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)、順序存取的存儲(chǔ)結(jié)構(gòu) C 隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)、隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)D 任意存取的存儲(chǔ)結(jié)構(gòu)、任意存取的存儲(chǔ)結(jié)構(gòu)【答案】：B【解析】：順序表的特點(diǎn)是隨機(jī)（訪問）存??；線性鏈表的特點(diǎn)是順序（訪問）存取。【考題5】鏈表不具有的特點(diǎn)是( )A 不必事先估計(jì)存儲(chǔ)空間 B 可隨機(jī)訪問任一元素C 插入刪除不需要移動(dòng)元素 D 所需空間與線性表長(zhǎng)度成正比【答案】：B【解析】：線性鏈表具有的特點(diǎn)：順序（訪問）存取、插入刪除方便，查找不方

14、便、不必事先估計(jì)存儲(chǔ)空間。A、C、D都屬于，其D也要知道，線性表多長(zhǎng)，在內(nèi)存空間中也就多長(zhǎng)。故B不正確?！究碱}6】數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)，線性鏈表屬于 。 【答案】：存儲(chǔ)結(jié)構(gòu)【解析】：線性鏈表是線性表在計(jì)算機(jī)的存儲(chǔ)空間中的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。所以在計(jì)算機(jī)的存儲(chǔ)空間中，因此屬于存儲(chǔ)結(jié)構(gòu)。5、 棧(1) 棧是一種特殊的線性表，其特殊性是插入與刪除運(yùn)算都只在線性表的一端進(jìn)行。即棧的一個(gè)考點(diǎn)是：入棧和退棧都是在一端（棧頂）進(jìn)行的。(2) 棧在計(jì)算機(jī)中進(jìn)行存儲(chǔ)時(shí)通常采用的存儲(chǔ)方式有：順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。(3) 棧的原則是：先進(jìn)后出、后進(jìn)先出?！究碱}1】下列關(guān)于棧的描述正確的是( ) A 在棧中

15、只能插入元素而不能刪除元素 B 在棧中只能刪除元素而不能插入元素 C 棧是特殊的線性表，只能在一端插入或刪除元素D 棧是特殊的線性表，只能在一端插入元素，而不能在一端刪除元素【答案】：C【解析】：棧的入棧運(yùn)算和退棧運(yùn)算都是在一端進(jìn)行的，即棧頂。【考題2】下列關(guān)于棧的描述中錯(cuò)誤的是( ) A 棧是先進(jìn)后出的線性表 B 棧只能順序存儲(chǔ) C 棧具有記憶作用 D 對(duì)棧的插入與刪除操作中，不需要改變棧底指針【答案】：B【解析】：棧通常采用的存儲(chǔ)方式有：順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。所以B不正確；關(guān)于C答案同學(xué)們也要知道，棧具有記憶作用。6、 隊(duì)列(1) 隊(duì)列是一個(gè)允許在一端進(jìn)行插入、而在另一端進(jìn)行刪除的線

16、性表。即隊(duì)列的一個(gè)考點(diǎn)是：隊(duì)列的入隊(duì)運(yùn)算是在隊(duì)尾進(jìn)行、退隊(duì)運(yùn)算是在隊(duì)頭進(jìn)行的。(2) 隊(duì)列在計(jì)算機(jī)中進(jìn)行存儲(chǔ)時(shí)通常采用的存儲(chǔ)方式有：順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。(3) 隊(duì)列的原則是：先進(jìn)先出、后進(jìn)后出。(4) 循環(huán)隊(duì)列是隊(duì)列在計(jì)算機(jī)存儲(chǔ)空間中采用順序存儲(chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)的一種形式。【考題1】下列關(guān)于隊(duì)列的敘述中正確的是( ) A 在隊(duì)列中只能插入元素 B 在隊(duì)列中只能刪除數(shù) C 隊(duì)列是先進(jìn)先出的線性表 D 隊(duì)列是先進(jìn)后出的線性表【答案】：C【解析】：隊(duì)列是一個(gè)先進(jìn)先出的特殊線性表，其特殊性在于隊(duì)列的插入是從隊(duì)尾進(jìn)行的，刪除是從隊(duì)頭進(jìn)行的?！究碱}2】一個(gè)隊(duì)列的入隊(duì)序列是1，2，3，4，則隊(duì)列的輸出序

17、列是( ) A 4，3，2，1 B 1，2，3，4 C 1，4，3，2 D 3，2，4，1【答案】：B【考題3】棧和隊(duì)列的共同點(diǎn)是( )A 都是先進(jìn)后出 B 都是先進(jìn)先出 C 只允許在端點(diǎn)處插入和刪除元素 D 沒有共同點(diǎn)【答案】：C【解析】：棧和隊(duì)列的共同點(diǎn)都是在端點(diǎn)處進(jìn)行運(yùn)算的。棧的插入與刪除運(yùn)算都只在線性表的一端進(jìn)行；隊(duì)列是一個(gè)允許在一端進(jìn)行插入、而在另一端進(jìn)行刪除的特殊線性表。而與前面所講的線性表不同，它可以在任意位置進(jìn)行插入、刪除運(yùn)算。【考題4】線性表在計(jì)算機(jī)中的存儲(chǔ)結(jié)構(gòu)主要分為順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。隊(duì)列是一種特殊的線性表，循環(huán)隊(duì)列是隊(duì)列的 存儲(chǔ)結(jié)構(gòu)?！敬鸢浮浚喉樞颉究碱}5】設(shè)某

18、循環(huán)隊(duì)列的容量為50，頭指針front=5(指向隊(duì)頭元素的前一位置)，尾指針rear=29(指向?qū)ξ苍?，則該循環(huán)隊(duì)列中共有 個(gè)元素。【答案】：24【解析】：隊(duì)頭指針中不存放元素，從6號(hào)空間到29號(hào)空間中，總共有24個(gè)元素。7、 樹和二叉樹(1) 樹是一種簡(jiǎn)單的非線性結(jié)構(gòu)。在樹中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特性。樹的根節(jié)點(diǎn)可以沒有或有一個(gè)。(2) 二叉樹的性質(zhì)： 2k-1 ：在二叉樹的第k層上，最多有多少的結(jié)點(diǎn)。 2k-1 ：深度為k的二叉樹中，最多有多少個(gè)總結(jié)點(diǎn)。 n=n0+n1+n2 ：二叉樹的總結(jié)點(diǎn)個(gè)數(shù)n等于葉子結(jié)點(diǎn)個(gè)數(shù)n0、度為1的結(jié)點(diǎn)個(gè)數(shù)n1、度為2的結(jié)點(diǎn)個(gè)數(shù)n2之和。

19、n0=n2+1 ：葉子結(jié)點(diǎn)個(gè)數(shù)n0等于度為2的結(jié)點(diǎn)個(gè)數(shù)n2加1。(3) 二叉樹的特殊情況：滿二叉樹、完全二叉樹。 滿二叉樹：每一層的結(jié)點(diǎn)都達(dá)到了最多。 完全二叉樹：結(jié)點(diǎn)按從上到下、從左到右的順序依次進(jìn)行排放的二叉樹。(4) 二叉樹的遍歷方法：前序(根、左邊、右邊)、中序(左、根、右邊)、后序(左、右邊、根)?！究碱}1】一棵二叉樹第5層的結(jié)點(diǎn)數(shù)最多為( ) A 8 B 16 C 32 D 15【答案】：B【解析】：利用二叉樹的性質(zhì)2k-1。【考題2】設(shè)一棵二叉樹中有3個(gè)葉子結(jié)點(diǎn)，有8個(gè)度為1的結(jié)點(diǎn)，則該二叉樹中總的結(jié)點(diǎn)數(shù)為( )A 12 B 13 C 14 D 15【答案】：B【考題3】設(shè)一棵完

20、全二叉樹共有699個(gè)結(jié)點(diǎn)，則在該二叉樹中的葉子結(jié)點(diǎn)數(shù)為( ) A 349 B 350 C 255 D 351【答案】：B【考題4】某二叉樹中度為2的結(jié)點(diǎn)有18個(gè)，則該二叉樹中有 個(gè)葉子結(jié)點(diǎn)?！敬鸢浮浚?9【考題5】在深度為7的滿二叉樹中,葉子結(jié)點(diǎn)的個(gè)數(shù)為( )A 32 B 31 C 64 D 63【答案】：C【解析】：利用二叉樹的性質(zhì)2k-1。27-1【考題6】在深度為7的滿二叉樹中,度為2的結(jié)點(diǎn)個(gè)數(shù)為( )A 32 B 31 C 64 D 63【答案】：D【解析】：利用二叉樹的性質(zhì)2k-1。27-1，接著使用n2= n0-1?！究碱}7】有如右圖二叉樹，請(qǐng)分別寫出： 前序： 中序： 后序： 【

21、答案】：ABDYECFXZ、DYBEAFCZX、YDEBFZXCA8、 查找(1) 查找的方法有兩種：順序查找、二分法查找(對(duì)分查找)。 順序查找：順序查找在最壞的情況下需要比較n次，即時(shí)間復(fù)雜度為n。 二分法查找(對(duì)分查找)：二分法查找在最壞的情況下需要比較log2n次，即時(shí)間復(fù)雜度為log2n。 只有在順序存儲(chǔ)、并且是有序表的情況下才可以進(jìn)行二分法查找?！究碱}1】對(duì)長(zhǎng)度為n的線性表進(jìn)行順序查找，在最壞的情況下所需要的比較次數(shù)為( ) A Log2n B n/2 C n D n+1【答案】：C【考題2】下列數(shù)據(jù)結(jié)構(gòu)中，能用二分法進(jìn)行查找的是( ) A 順序存儲(chǔ)的有序線性表 B 線性鏈表 C

22、二叉鏈表 D 有序線性鏈表【答案】：A9、 排序 交換類：冒泡排序法：n(n-1)/2 快速排序法：最壞情況下也比較n(n-1)/2次 插入類：簡(jiǎn)單插入排序法：n(n-1)/2 希爾排序法：O(n1.5) 選擇類：簡(jiǎn)單選擇排序法：n(n-1)/2 堆排序法：O(nlog2n)【考題1】對(duì)于長(zhǎng)度為n的線性表，在最壞的情況下，下列各排序法所對(duì)應(yīng)的比較次數(shù)中正確的是( ) A 冒泡排序?yàn)閚/2 B 冒泡排序?yàn)閚 C 快速排序?yàn)閚 D 快速排序?yàn)閚(n-1)/2【答案】：D【考題2】希爾排序法屬于哪一種類型的排序法( ) A 交換類排序法 B 插入類排序法 C 選擇類排序法 D 建堆排序法【答案】：B

23、備考鞏固練習(xí)一、 選擇題(1) 算法一般都可以用哪幾種控制結(jié)構(gòu)組合而成( )A 循環(huán)、分支、遞歸 B 順序、循環(huán)、嵌套 C 循環(huán)、遞歸、選擇 D 順序、選擇、循環(huán)(2) 下列敘述正確的是( ) A 算法的執(zhí)行效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān) B 算法的空間復(fù)雜度是指算法程序中指令（或語(yǔ)句）的條數(shù)C 算法的有窮性是指算法必須能在執(zhí)行有限個(gè)步驟之后終止 D 以上三種描述都不對(duì)(3) 用鏈表表示線性表的優(yōu)點(diǎn)是( ) A 便于插入和刪除操作 B 數(shù)據(jù)元素的物理順序與邏輯順序相同C 花費(fèi)的存儲(chǔ)空間較順序存儲(chǔ)少 D 便于隨機(jī)存取(4) 線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址( )A 必須是連續(xù)的

24、 B 部分地址必須是連續(xù)的 C 一定是不連續(xù)的 D 連續(xù)不連續(xù)都可以(5) 棧通常采用的兩種存儲(chǔ)結(jié)構(gòu)是( )A 順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) B 散列方式和索引方式C 鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組 D 線性存儲(chǔ)結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu)(6) 樹最適合用來(lái)表示( ) A 有序數(shù)組元素 B 無(wú)序數(shù)組元素C 元素之間具有分支層次關(guān)系的數(shù)據(jù) D 元素之間無(wú)聯(lián)系的數(shù)據(jù) (7) 在一個(gè)二叉樹中，第6層的結(jié)點(diǎn)數(shù)最多有( )A 32 B 31 C 64 D 63 (8) 在一棵深度為6的滿二叉樹中，葉子結(jié)點(diǎn)有( )A 32 B 31 C 64 D 63 (9) 在一棵深度為6的滿二叉樹中，度為2的結(jié)點(diǎn)數(shù)有( )A 32 B

25、31 C 64 D 63 (10) 某二叉樹結(jié)點(diǎn)的前序序列為EACBDGF，中序序列為ABCDEFG。該二叉樹結(jié)點(diǎn)的后序序列為( ) A BDCAFGE B DBCFAGE C DCEGFAB D DEGACFB (11) 已知二叉樹后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是( )A cedba B acbed C decab D deabc (12) 二分法查找適合用于存儲(chǔ)結(jié)構(gòu)為( )且按關(guān)鍵字排好序的線性表 A 順序存儲(chǔ) B 鏈?zhǔn)酱鎯?chǔ) C 順序和鏈?zhǔn)酱鎯?chǔ) D 索引存儲(chǔ) (13) 冒泡排序法的時(shí)間復(fù)雜度為( )A n B n-1 C n(n-1)/2 D (n-1

26、)/2二、 填空題(1) 算法復(fù)雜度主要包括時(shí)間復(fù)雜度和 復(fù)雜度。(2) 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱為數(shù)據(jù)的 。(3) 數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，循環(huán)隊(duì)列屬于 結(jié)構(gòu)。(4) 順序存儲(chǔ)方法是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置 的存儲(chǔ)單元中。(5) 二叉樹的遍歷可以分為三種：前序遍歷、 遍歷和后序遍歷。(6) 設(shè)一棵完全二叉樹共有500個(gè)結(jié)點(diǎn)，則在該二叉樹中有 個(gè)葉子結(jié)點(diǎn)。(7) 在最壞情況下，堆排序需要比較的次數(shù)為 。參考答案一、 選擇題(1)-(5)：DCADA (6)-(10)：CAABA (11)-(13)：AAC二、 填空題(1)、空間 (2)、存儲(chǔ)結(jié)構(gòu) (3)、存

27、儲(chǔ) (4)、相鄰 (5)、中序 (6)、250 (7)、0(nlog2n)第二章 程序設(shè)計(jì)基礎(chǔ)1、 程序設(shè)計(jì)的風(fēng)格 (1) 程序設(shè)計(jì)的風(fēng)格注重的是：清晰第一、效率第二。 (2) 要使程序的清晰達(dá)到最好，我們?cè)诔绦蛟O(shè)計(jì)的過(guò)程中將源程序文檔化： 符號(hào)名的命名應(yīng)具有一定的實(shí)際含義，以便于讀者理解。 程序中的注釋要盡量多，程序中的注釋又分為：序言性注釋、功能性注釋。 視覺組織要合理。【考題1】結(jié)構(gòu)化程序設(shè)計(jì)主要強(qiáng)調(diào)的是( )A 程序的規(guī)模 B 程序的易讀性 C 程序的執(zhí)行效率 D 程序的可移植性【答案】：B【解析】：程序設(shè)計(jì)主要強(qiáng)調(diào)的是：清晰第一、效率第二。程序的易讀性、可理解性都表示程序清晰?！究碱}

28、2】對(duì)建立良好的程序設(shè)計(jì)風(fēng)格，下面描述正確的是( )A 程序應(yīng)簡(jiǎn)單、清晰、可讀性好 B 符號(hào)名的命名要符合語(yǔ)法C 充分考慮程序的執(zhí)行效率 D 程序的注釋可有可無(wú)【答案】：A【解析】：程序設(shè)計(jì)主要強(qiáng)調(diào)的是：清晰第一、效率第二。程序的易讀性、可理解性都表示程序清晰。所以A正確；符號(hào)名的命名要有一定的實(shí)際含義，應(yīng)做到見名之意；所以B不正確。2、 結(jié)構(gòu)化程序設(shè)計(jì)(1) 結(jié)構(gòu)化程序設(shè)計(jì)的基本結(jié)構(gòu)有三種：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。(2) 結(jié)構(gòu)化程序設(shè)計(jì)的基本原則有四種：自頂向下、逐步求精、模塊化、限制使用goto語(yǔ)句?！究碱}1】下列選項(xiàng)中不屬于結(jié)構(gòu)化程序設(shè)計(jì)方法的是( )A 自頂向下 B 逐步求精 C

29、 模塊化 D 可復(fù)用【答案】：D3、 面向?qū)ο蟮某绦蛟O(shè)計(jì)(1) 對(duì)象：客觀世界中任何的實(shí)體稱為對(duì)象。 對(duì)象的特點(diǎn)有：標(biāo)識(shí)唯一性、分類性、多態(tài)性、封裝性、模塊獨(dú)立性好。 (2) 類：是具有共同屬性，共同方法的對(duì)象的集合。即類是從對(duì)象抽象出來(lái)的。 (3) 實(shí)例：類中的實(shí)例稱為對(duì)象；對(duì)象是類的實(shí)例。 (4) 消息：是指對(duì)象間傳遞信息的手段。(5) 繼承：類之間共享屬性和操作的機(jī)制稱為繼承。 繼承的優(yōu)點(diǎn)可以提高軟件的可重用性。(6) 總結(jié)：類具有封裝性、模塊具有獨(dú)立性、信息具有隱蔽性、繼承具有傳遞性?！究碱}1】在面向?qū)ο蠓椒ㄖ校?描述的是具有相似屬性與操作的一組對(duì)象?！敬鸢浮浚侯悺究碱}2】在面向?qū)ο蠓?/p>

30、法中，類的實(shí)例稱為 ?！敬鸢浮浚簩?duì)象【考題3】下面概念中，不屬于面向?qū)ο蠓椒ǖ氖? )A 對(duì)象 B 繼承 C 類 D 過(guò)程調(diào)用【答案】：D【解析】：在面向?qū)ο蟮姆椒ㄖ校饕v到了：類、對(duì)象、實(shí)例、消息、繼承、多態(tài)性、封裝性、模塊獨(dú)立性等。備考鞏固練習(xí)一、選擇題(1) 在設(shè)計(jì)程序時(shí)，應(yīng)采納的原則之一是( )A 程序結(jié)構(gòu)應(yīng)有助于讀者理解 B 不限制goto語(yǔ)句的使用C 減少或取消注解行 D 程序越短越好(2) 在結(jié)構(gòu)化程序設(shè)計(jì)思想提出之前，在程序設(shè)計(jì)中曾強(qiáng)調(diào)程序的效率，現(xiàn)在與程序的效率相比，人們更重視程序的( )A 安全性 B 一致性 C 可理解性 D 合理性(3) 下面描述中，符合結(jié)構(gòu)化程序設(shè)計(jì)

31、風(fēng)格的是( )A 使用順序、選擇和重復(fù)(循環(huán))三種基本控制結(jié)構(gòu)表示程序的控制邏輯 B 模塊只有一個(gè)入口，可以有多個(gè)出口 C 注重提高程序的執(zhí)行效率 D 不使用goto語(yǔ)句(4) 下面對(duì)對(duì)象概念描述錯(cuò)誤的是( )A 任何對(duì)象都必須有繼承性 B 對(duì)象是屬性和方法的封裝體C 對(duì)象間的通訊靠消息傳遞 D 操作是對(duì)象的動(dòng)態(tài)性屬性(5) 面向?qū)ο蟮脑O(shè)計(jì)方法與傳統(tǒng)的的面向過(guò)程的方法有本質(zhì)不同，它的基本原理是( )A 模擬現(xiàn)實(shí)世界中不同事物之間的聯(lián)系 B 強(qiáng)調(diào)模擬現(xiàn)實(shí)世界中的算法而不強(qiáng)調(diào)概念 C 使用現(xiàn)實(shí)世界的概念抽象地思考問題從而自然地解決問題 D 鼓勵(lì)開發(fā)者在軟件開發(fā)的絕大部分中都用實(shí)際領(lǐng)域的概念去思考二

32、、填空題(1) 結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則可以概括為自頂向下、逐步求精、 和限制使用goto語(yǔ)句。(2) 面向?qū)ο蟮某绦蛟O(shè)計(jì)方法中涉及的對(duì)象是系統(tǒng)中用來(lái)描述客觀事物的一個(gè) 。(3) 在面向?qū)ο蠓椒ㄖ?，信息隱蔽是通過(guò)對(duì)象的 性來(lái)實(shí)現(xiàn)的。(4) 面向?qū)ο蟮哪Ｐ椭校罨镜母拍钍菍?duì)象和 。(5) 在面向?qū)ο蠓椒ㄖ?，類之間共享屬性和操作的機(jī)制稱為 。(6) 在面向?qū)ο蠓椒ㄖ?類的實(shí)例稱為 。 (7) 源程序文檔化要求程序應(yīng)加注釋。注釋一般分為序言性注釋和 注釋。 (8) 結(jié)構(gòu)化程序設(shè)計(jì)方法中所指的三種基本數(shù)據(jù)控制結(jié)構(gòu)包括順序結(jié)構(gòu)、選擇結(jié)構(gòu)、 。參考答案一、選擇題(1)-(5)：ACAAC二、填空題(

33、1)、模塊化 (2)、實(shí)體 (3)、封裝 (4)、類 (5)、繼承 (6)、對(duì)象 (7)、功能性 (8)、循環(huán)結(jié)構(gòu)第三章 軟件工程基礎(chǔ)考點(diǎn)1：軟件工程的基本概念（軟件、軟件危機(jī)、軟件工程、軟件生命周期）1、 軟件(1) 軟件是包括程序、數(shù)據(jù)及其相關(guān)文檔的完整集合。(2) 軟件按功能分為：應(yīng)用軟件、系統(tǒng)軟件、支撐軟件(工具軟件)?！究碱}1】下列描述中正確的是( ) A 程序就是軟件 B 軟件開發(fā)不受計(jì)算機(jī)系統(tǒng)的限制 C 軟件即是邏輯實(shí)體，又是物理實(shí)體 D 軟件是程序、數(shù)據(jù)與相關(guān)文檔的集合【答案】：D【解析】：本題選擇D，因?yàn)檐浖前ǔ绦?、?shù)據(jù)及其相關(guān)文檔的完整集合；A答案中，程序和軟件不能恒等

34、；B答案不正確的原因是：軟件的開發(fā)、運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依賴性，受計(jì)算機(jī)系統(tǒng)的限制；C答案不正確的原因是：軟件是一種邏輯實(shí)體，而不是物理實(shí)體，具有抽象性。2、 軟件危機(jī) (1) 軟件危機(jī)是指在計(jì)算機(jī)軟件的開發(fā)和維護(hù)過(guò)程中所遇到的一系列嚴(yán)重問題。3、 軟件工程(1) 定義：為了解決軟件危機(jī)在軟件的開發(fā)和維護(hù)過(guò)程中盡可能多的使用過(guò)程科學(xué)的原理來(lái)指導(dǎo)工作。(2) 3個(gè)要素：方法、工具和過(guò)程。(3) 核心思想：盡可能多的使用工程科學(xué)的原理來(lái)指導(dǎo)工作。(4) 達(dá)到目標(biāo)，要研究的內(nèi)容有：軟件開發(fā)技術(shù)、軟件工程管理。(5) 原則：抽象、信息隱蔽、模塊化、局部化等。(6) 軟件開發(fā)環(huán)境：是軟件工具的集合。如：

35、CASE(計(jì)算機(jī)輔助軟件工程)【考題1】下列描述中正確的是( ) A 軟件工程只解決軟件項(xiàng)目的管理問題 B 軟件工程主要解決軟件產(chǎn)品的生產(chǎn)率問題 C 軟件開發(fā)的主要思想是強(qiáng)調(diào)在軟件開發(fā)的過(guò)程中需要應(yīng)用工程化原則 D 軟件工程只解決軟件開發(fā)中的技術(shù)問題【答案】：C【解析】：軟件工程應(yīng)用計(jì)算機(jī)科學(xué)、數(shù)學(xué)及管理科學(xué)等原理采用工程化原則和方法開發(fā)軟件系統(tǒng)。它不僅解決軟件開發(fā)中的技術(shù)問題，還解決軟件項(xiàng)目的管理問題和軟件產(chǎn)品的生產(chǎn)率問題。【考題2】下面不屬于軟件工程的3個(gè)要素的是( )A 工具 B 過(guò)程 C 方法 D 環(huán)境【答案】：D【考題3】在軟件研制過(guò)程中，CASE是( ) A 計(jì)算機(jī)輔助系統(tǒng)過(guò)程 B

36、 CAD和CAM技術(shù)發(fā)展動(dòng)力 C 正在實(shí)驗(yàn)室用的工具 D 計(jì)算機(jī)輔助軟件工程【答案】：D【考題4】軟件工程概念的出現(xiàn)源自 ?！敬鸢浮浚很浖C(jī) 【解析】：軟件工程是在軟件危機(jī)的情況下提出的。4、 軟件生命周期(1) 軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過(guò)程稱為軟件生命周期。軟件生命周期分為以下三個(gè)階段： 定義階段：提出、分析和定義。 開發(fā)階段：編碼、測(cè)試。 維護(hù)階段：維護(hù)軟件的功能，對(duì)軟件的功能進(jìn)行增加和刪改。此階段最重要，而且所花費(fèi)用也最高?！究碱}1】軟件開發(fā)的結(jié)構(gòu)化生命周期方法將軟件生命周期劃分成( )A 定義、開發(fā)、運(yùn)行維護(hù) B 設(shè)計(jì)階段、編程階段、測(cè)試階段 C 總體設(shè)計(jì)、詳細(xì)

37、設(shè)計(jì)、編程調(diào)試 D 需求分析、功能定義、系統(tǒng)設(shè)計(jì)【答案】：A【考題2】軟件生命周期中所花費(fèi)用最多的階段是( )A 詳細(xì)設(shè)計(jì) B 軟件編碼 C 軟件測(cè)試 D 軟件維護(hù)【答案】：D【考題3】下列敘述中正確的是( ) A 軟件交付使用后還需要進(jìn)行維護(hù)  B 軟件一旦交付使用就不需要再進(jìn)行維護(hù) C 軟件交付使用后其生命周期就結(jié)束  D 軟件維護(hù)是指修復(fù)程序中被破壞的指令 【答案】：A【解析】：通常，將軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過(guò)程稱為軟件生命周期。軟件交付使用后還需要在運(yùn)行、使用過(guò)程中不斷維護(hù)，根據(jù)新提出的需求進(jìn)行必要而且可能的擴(kuò)充和刪改?？?/p>

38、點(diǎn)2：軟件定義（需求分析、結(jié)構(gòu)化分析方法、軟件需求規(guī)格說(shuō)明書）1、 需求分析(1) 任務(wù)：準(zhǔn)確地確定軟件系統(tǒng)必須做什么，確定軟件系統(tǒng)必須具備那些功能。(2) 階段： 需求獲取、 需求分析、 編寫需求規(guī)格說(shuō)明書、 需求評(píng)審?！究碱}1】在軟件生命周期中，能準(zhǔn)確地確定軟件系統(tǒng)必須做什么和必須具備哪些功能的階段是( )A 概要設(shè)計(jì) B 詳細(xì)設(shè)計(jì) C 可行性分析 D 需求分析【答案】：D【考題2】軟件需求分析四個(gè)階段分為：需求獲取、需求分析、編寫需求規(guī)格說(shuō)明書以及( ) A 階段性報(bào)告 B 需求評(píng)審 C 總結(jié) D 都不正確【答案】：B2、 結(jié)構(gòu)化分析方法(1) 在需求分析中，結(jié)構(gòu)化分析方法是常用的一種，

39、其目的是幫助弄清用戶對(duì)軟件的需求。(2) 結(jié)構(gòu)化分析方法中常使用的工具有四種：數(shù)據(jù)流圖、數(shù)據(jù)字典、判定表、判定樹。 數(shù)據(jù)流圖(DFD)：圖形中的箭頭表示“數(shù)據(jù)流”。 數(shù)據(jù)字典(DD)：字典的作用是解釋；也是結(jié)構(gòu)化分析方法的核心。【考題1】在結(jié)構(gòu)化方法中，用數(shù)據(jù)流程圖（DFD）作為描述工具的軟件開發(fā)階段是( )A 可行性分析 B 需求分析 C 詳細(xì)設(shè)計(jì) D 程序編碼【答案】：B【解析】：在需求分析階段，常使用的工具是結(jié)構(gòu)化分析方法中的數(shù)據(jù)流圖，所以選擇B。【考題2】數(shù)據(jù)流圖用于抽象描述一個(gè)軟件的邏輯模型，數(shù)據(jù)流圖由一些特定的圖符構(gòu)成。下列圖符名標(biāo)識(shí)的圖符不屬于數(shù)據(jù)流圖合法圖符的是( )A 控制流

40、 B 加工 C 數(shù)據(jù)存儲(chǔ) D 源和潭【答案】：A【解析】：數(shù)據(jù)流圖中的圖形有加工、數(shù)據(jù)流、存儲(chǔ)文件、源和潭?？刂屏魇菍儆诔绦蛄鞒虉D中的?！究碱}3】下列工具中屬于需求分析常用工具的是( )A PAD B PFD C N-S D DFD【答案】：D【考題4】下列不屬于結(jié)構(gòu)化分析的常用工具的是( )A 數(shù)據(jù)流圖 B 數(shù)據(jù)字典 C 判定樹 D PAD圖【答案】：D3、 軟件需求規(guī)格說(shuō)明書(1) 軟件需求規(guī)格說(shuō)明書的作用： 便于用戶、開發(fā)人員進(jìn)行理解和交流。 反映出用戶問題的結(jié)構(gòu)，可以作為軟件開發(fā)工作的基礎(chǔ)和依據(jù)。 作為確認(rèn)測(cè)試和驗(yàn)收的依據(jù)。(2) 軟件需求規(guī)格說(shuō)明書的特點(diǎn)：無(wú)歧義性這一特點(diǎn)是整個(gè)當(dāng)中最

41、為重要的?！究碱}1】下列敘述中，不屬于軟件需求規(guī)格說(shuō)明書的作用的是( )A 便于用戶、開發(fā)人員進(jìn)行理解和交流 B 反映出用戶問題的結(jié)構(gòu)，可以作為軟件開發(fā)工作的基礎(chǔ)和依據(jù)C 作為確認(rèn)測(cè)試和驗(yàn)收的依據(jù) D 便于開發(fā)人員進(jìn)行需求分析【答案】：D考點(diǎn)3：軟件開發(fā)（結(jié)構(gòu)化設(shè)計(jì)方法、軟件測(cè)試、程序調(diào)試）1、 結(jié)構(gòu)化設(shè)計(jì)方法(1) 按技術(shù)觀點(diǎn)來(lái)分類：結(jié)構(gòu)設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、過(guò)程設(shè)計(jì)。(2) 按工程管理角度分類：概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)。 概要設(shè)計(jì)：將軟件的功能進(jìn)行分解。 概要設(shè)計(jì)的工具有：結(jié)構(gòu)圖(SC)。 結(jié)構(gòu)圖中的箭頭表示調(diào)用關(guān)系；深度表示控制的層數(shù)；寬度表示跨度最大的模塊數(shù)目。 詳細(xì)設(shè)計(jì)：確定每個(gè)模塊的

42、實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)。 詳細(xì)設(shè)計(jì)的工具有：程序流程圖(PFD)、N-S、PAD、HIPO、判定表、PDL。 程序流程圖中的箭頭表示控制流。 N-S是用方框圖來(lái)代替?zhèn)鹘y(tǒng)的程序流程圖的。(3) 軟件設(shè)計(jì)的(原則)原理：抽象、模塊化、信心隱蔽、模塊獨(dú)立性。 其中模塊獨(dú)立性這一原則非常重要，其考點(diǎn)是：模塊要想盡可能獨(dú)立必須要遵循“高內(nèi)聚、低耦合”的設(shè)計(jì)原則。(4) 數(shù)據(jù)流的類型有兩類：變換型、事務(wù)型?！究碱}1】在結(jié)構(gòu)化方法中，軟件功能分解屬于下列軟件開發(fā)中的階段是( )A 詳細(xì)設(shè)計(jì) B 需求分析 C 總體設(shè)計(jì) D 編程調(diào)試【答案】：C【解析】：總體設(shè)計(jì)也稱為概要設(shè)計(jì)。即對(duì)軟件的總體進(jìn)行分解?！究碱}2

43、】下面不屬于軟件設(shè)計(jì)原則的是( )A 抽象 B 模塊化 C 自底向上 D 信息隱蔽【答案】：C【考題3】程序流程圖（PFD）中的箭頭代表的是( )A 數(shù)據(jù)流 B 控制流 C 調(diào)用關(guān)系 D 組成關(guān)系【答案】：B【考題4】為了使模塊盡可能獨(dú)立，要求( ) A 模塊的內(nèi)聚程度要盡量高，且各模塊間的耦合程度要盡量強(qiáng) B 模塊的內(nèi)聚程度要盡量高，且各模塊間的耦合程度要盡量弱 C 模塊的內(nèi)聚程度要盡量低，且各模塊間的耦合程度要盡量弱 D 模塊的內(nèi)聚程度要盡量低，且各模塊間的耦合程度要盡量強(qiáng)【答案】：B【考題5】面向數(shù)據(jù)流的設(shè)計(jì)方法,一般把信息流分為 ，另一種稱為事務(wù)流?！敬鸢浮浚鹤儞Q流2、 軟件測(cè)試(1)

44、 軟件測(cè)試的目的：發(fā)現(xiàn)錯(cuò)誤。(2) 軟件測(cè)試的實(shí)施(過(guò)程)：?jiǎn)卧獪y(cè)試、集成測(cè)試、確認(rèn)測(cè)試(驗(yàn)收測(cè)試)、系統(tǒng)測(cè)試。 單元測(cè)試：目的是發(fā)現(xiàn)各模塊內(nèi)部可能存在的各種錯(cuò)誤。 集成測(cè)試：目的是發(fā)現(xiàn)與接口有關(guān)的錯(cuò)誤。 確認(rèn)測(cè)試(驗(yàn)收測(cè)試)：測(cè)試是否滿足需求分析。(3) 軟件測(cè)試的方法：靜態(tài)測(cè)試、動(dòng)態(tài)測(cè)試。 靜態(tài)測(cè)試：不由計(jì)算機(jī)執(zhí)行程序代碼，主要是通過(guò)人看出程序錯(cuò)誤。 動(dòng)態(tài)測(cè)試：有計(jì)算機(jī)執(zhí)行程序進(jìn)行測(cè)試，是基于計(jì)算機(jī)的測(cè)試。 白盒測(cè)試：內(nèi)部結(jié)構(gòu)的測(cè)試。又稱為“路徑測(cè)試”。白盒測(cè)試的方法又包括：邏輯覆蓋測(cè)試、基本路徑測(cè)試等。 黑盒測(cè)試：外部接口的功能測(cè)試。黑盒測(cè)試的方法又包括：等價(jià)類劃分法、邊界值分析法、錯(cuò)誤

45、推測(cè)法、因果圖法等。【考題1】在軟件工程中，白箱測(cè)試法可用于測(cè)試程序的內(nèi)部結(jié)構(gòu)。此方法將程序看做是( ) A 循環(huán)的集合 B 地址的集合 C 路徑的集合 D 目標(biāo)的集合【答案】：C【解析】：白盒(白箱)測(cè)試的基本原則是：保證所測(cè)模塊中每一獨(dú)立路徑至少執(zhí)行一次。白盒法又叫“路徑測(cè)試”?！究碱}2】軟件測(cè)試的目的是( ) A 發(fā)現(xiàn)錯(cuò)誤 B 改正錯(cuò)誤 C 改善軟件的性能 D 挖掘軟件的潛能【答案】：A【考題3】軟件測(cè)試的內(nèi)容包括:集成測(cè)試、驗(yàn)收測(cè)試、系統(tǒng)測(cè)試、單元測(cè)試。下列正確的測(cè)試順序是( ) A B C D 【答案】：C【考題4】若按功能劃分，軟件測(cè)試的方法通常分為白盒測(cè)試方法和 測(cè)試方法?！敬鸢?/p>

46、】：黑盒【考題5】為了提高測(cè)試的效率，應(yīng)該( )A 隨機(jī)選取測(cè)試數(shù)據(jù) B 取一切可能的輸入數(shù)據(jù)作為測(cè)試數(shù)據(jù)C 在完成編碼以后制定軟件的測(cè)試計(jì)劃 D 集中對(duì)付那些錯(cuò)誤群集的程序【答案】：D【解析】：經(jīng)驗(yàn)表明，程序中存在錯(cuò)誤的概率與程序中已發(fā)現(xiàn)的錯(cuò)誤數(shù)成正比。這一現(xiàn)象說(shuō)明，為了提高測(cè)試的效率，測(cè)試人員應(yīng)該集中對(duì)付那些錯(cuò)誤群集的程序?！究碱}6】下列敘述中正確的是( ) A 程序設(shè)計(jì)就是編制程序  B 程序的測(cè)試必須由程序員自己去完成 C 程序經(jīng)調(diào)試改錯(cuò)后還應(yīng)進(jìn)行再測(cè)試  D 程序經(jīng)調(diào)試改錯(cuò)后不必進(jìn)行再測(cè)試 【答案】：C【解析】：程序設(shè)計(jì)包括程序的結(jié)構(gòu)

47、設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、過(guò)程設(shè)計(jì)，并不是只有編制程序這么簡(jiǎn)單，所以選項(xiàng)A敘述錯(cuò)誤；在軟件測(cè)試準(zhǔn)則中明確說(shuō)明程序員應(yīng)盡量避免檢查自己的程序，所以選項(xiàng)B敘述錯(cuò)誤；程序經(jīng)過(guò)調(diào)試改錯(cuò)后可能會(huì)引起其他錯(cuò)誤的現(xiàn)象發(fā)生，所以程序經(jīng)過(guò)調(diào)試改錯(cuò)后必須再進(jìn)行測(cè)試。所以選項(xiàng)D敘述錯(cuò)誤。3、 程序調(diào)試(1) 程序調(diào)試的目的：改正錯(cuò)誤。(2) 程序調(diào)試的方法：強(qiáng)行排錯(cuò)法、回溯法、原因排除法?！究碱}1】軟件調(diào)試的目的是( )A 發(fā)現(xiàn)錯(cuò)誤 B 改正錯(cuò)誤 C 改善軟件的性能 D 挖掘軟件的潛能【答案】：B【考題2】下列不屬于軟件調(diào)試技術(shù)的是( )A 強(qiáng)行排錯(cuò)法 B 集成測(cè)試法 C 回溯法 D 原因排除法【答案】：B備考鞏固練習(xí)一、 選擇題(1) 下列關(guān)于計(jì)算機(jī)軟件特點(diǎn)的描述,錯(cuò)誤的是(A ) A 軟件是物理實(shí)體,不過(guò)其具有抽象性 B 軟件沒有明顯的制作過(guò)程 C 軟件開發(fā)復(fù)雜性高,成本昂貴 D 軟件在運(yùn)行、使用期間不存在磨損和老化的問題(2) 需求分析階段的任務(wù)是確定( D)A 軟件開發(fā)方法 B 軟件開發(fā)工具 C 軟件開發(fā)費(fèi)用 D 軟件系統(tǒng)功能(3) 在數(shù)據(jù)流圖（DFD）中，帶有名字的箭頭表示( C )A 控制程序的執(zhí)行順序 B 模塊之間的調(diào)用關(guān)系 C 數(shù)據(jù)的流向 D 程序的組成成分(4) 軟件設(shè)計(jì)包括軟件的結(jié)構(gòu)、數(shù)據(jù)接口和過(guò)程設(shè)計(jì)，其中軟件的過(guò)程設(shè)計(jì)是指( B )A 模塊間的關(guān)系 B 系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成