全國計算機等級考試《二級公共基礎(chǔ)知識》專用教材考綱分析+考點精講+真題演練+強化習(xí)題

第1章數(shù)據(jù)構(gòu)造與算法 4考綱分析 4考點精講 4算法 4考點1算法的根本概念 4考點2算法設(shè)計根本方法 4考點3算法簡潔度 6數(shù)據(jù)構(gòu)造的根本概念 7考點1概述 7考點2數(shù)據(jù)構(gòu)造的概念 7考點3數(shù)據(jù)構(gòu)造的圖形表示 8考點4線性構(gòu)造與非線性構(gòu)造 8線性表及其挨次存儲構(gòu)造 8考點1線性表的根本概念 8考點2線性表的挨次存儲構(gòu)造 9考點3挨次表的插入運算 9考點4挨次表的刪除運算 10棧和隊歹〔J. 10考點1棧及其根本運算 10考點2隊列及其根本運算 11線性鏈表 13考點1線性鏈表的根本概念 13考點2線性鏈表的根本運算 14考點3循環(huán)鏈表 15樹與二叉樹 15考點1樹的根本概念 15考點2二叉樹及其根本性質(zhì) 16考點3二叉樹的存儲構(gòu)造 18考點4二叉樹的遍歷 18查找技術(shù) 19考點1挨次查找〔挨次搜尋〕 19考點2二分法查找〔對分查找〕 192插入類排序法12插入類排序法3選擇類排序法第2章程序設(shè)計根底 25考綱分析 25考點精講 252」程序設(shè)計方法與風(fēng)格 25考點1程序設(shè)計進展階段 25考點2程序設(shè)計風(fēng)格 25考點3良好的程序設(shè)計風(fēng)格應(yīng)考慮的因素 25構(gòu)造化程序設(shè)計 26考點1構(gòu)造化程序設(shè)計的原則 26考點2構(gòu)造化程序的根本構(gòu)造與特點 26考點3構(gòu)造化程序設(shè)計原則和方法的應(yīng)用 27面對對彖的程序設(shè)計 27考點1關(guān)于面對對象方法 27考點2面對對象方法的根本概念 28強化習(xí)題 31第3章 軟件工程根底 33考綱分析 33考點精講 33軟件工程根本概念 33考點1 軟件定義與軟件特點 33考點2軟件危機與軟件工程 34考點3軟件過程與軟件生命周期 35考點4軟件工程的目標(biāo)與原則 36考點5軟件開發(fā)工具與軟件開發(fā)環(huán)境 37構(gòu)造化分析方法 37考點1需求分析與需求分析方法 37考點2 構(gòu)造化分析方法 38考點3軟件需求規(guī)格說明書 40構(gòu)造化設(shè)計方法 40考點1軟件設(shè)計的根本概念 40考點2概要設(shè)計 42考點3 具體設(shè)計 45軟件測試 47考點1 軟件測試的目的和定義 47考點2 軟件測試的準(zhǔn)則 48考點3軟件測試方法與技術(shù)綜述 48考點4軟件測試的策略 50程序的調(diào)試 52考點1根本概念 52考點2軟件調(diào)試方法 53強化習(xí)題 55第4章 數(shù)據(jù)庫設(shè)計根底 58考綱分析 58考點精講 58數(shù)據(jù)庫系統(tǒng)的根本概念 58考點1數(shù)據(jù)、數(shù)據(jù)庫、數(shù)據(jù)庫治理系統(tǒng) 58考點2數(shù)據(jù)庫系統(tǒng)的進展 60考點3數(shù)據(jù)庫系統(tǒng)的根本特點 62考點4數(shù)據(jù)庫系統(tǒng)的內(nèi)部構(gòu)造體系 62數(shù)據(jù)模型 63考點1數(shù)據(jù)模型的根本概念 63考點2E R模型 64考點3層次模型 66考點4網(wǎng)狀模型 67考點5關(guān)系模型 67關(guān)系代數(shù) 69考點1關(guān)系模型的根本操作 69考點2關(guān)系模型的根本運算 69考點3關(guān)系代數(shù)中的擴大運算 72數(shù)據(jù)庫設(shè)計與治理 73考點1數(shù)據(jù)庫設(shè)計概述 73考點2數(shù)據(jù)庫設(shè)計的需求分析 74考點3數(shù)據(jù)庫概念設(shè)計 74考點4數(shù)據(jù)庫的規(guī)律設(shè)計 75考點5數(shù)據(jù)庫的物理設(shè)計 76考點6數(shù)據(jù)庫治理 76強化習(xí)題 77附錄全國計算機等級考試二級公共根底學(xué)問考試大綱〔2023年版〕 80考綱分析算法的根本概念，算法簡潔度的概念和意義〔時間簡潔度與空間簡潔度〕。數(shù)據(jù)構(gòu)造的定義，數(shù)據(jù)的規(guī)律構(gòu)造與存儲構(gòu)造；數(shù)據(jù)構(gòu)造的圖形表示；線性構(gòu)造與非線性構(gòu)造的概念。線性表的定義，線性表的挨次存儲構(gòu)造及其插入與刪除運算。棧和隊列的定義，棧和隊列的挨次存儲構(gòu)造及英根本運算。線性單鏈表、雙向鏈表與循環(huán)鏈表的構(gòu)造及其根本運算。樹的根本概念，二叉樹的定義及其存儲構(gòu)造；二叉樹的前序、中序和后序遍歷。挨次查找與二分法查找算法，根本排序算法〔交換類排序，選擇類排序，插入類排序〕。考點精講算法1算法的根本概念嚴謹定義運算挨次的規(guī)章，且每個規(guī)章都是明確有效的，此挨次將在有限的次數(shù)下終止。需要留意的是：算法不等于程序，也不等于計算方法。算法的基木特征現(xiàn)；b.算法執(zhí)行的結(jié)果要能夠到達預(yù)期的目的。③有窮性有窮性是指算法必需能在有限的時間內(nèi)做完，即必需能在執(zhí)行有限個步驟Z行時間。法有效，而當(dāng)供給的情報不夠時，算法可能無效。【真題演練】算法的有窮性是指〔〕。［20239月真題］A. 算法程序的運行時I”B.算法程序所處理的數(shù)據(jù)量是有限的C.算法程序的長度是有限的D.算法只能被有限的用八使用【答案】A的。2算法設(shè)計根本方法〔1〕列舉法常用于解決“是否存在”或“有多少種可能”等類型的問題。算法比較簡潔，但列舉狀況較多時，算法工作量很大。找出規(guī)律，或?qū)θ靠赡艿臓顩r進展分類，從而引出一些有用的信息，削減列舉量。歸納法①根本思想通過列舉少量的特別狀況，經(jīng)過分析，最終找汕一般的關(guān)系。②主要特點a.b.可操作性低，不易歸納出一個具體數(shù)學(xué)模型；c.遞推結(jié)果。a.b.遞推本質(zhì)上屬于歸納法，遞推關(guān)系式往往是歸納的結(jié)果；c.數(shù)值型遞推算法計算過程屮必需留意數(shù)值計算的穩(wěn)定性問題。遞歸綜合。a.b.在可計算性理論和算法設(shè)計中占有重要地位；c.d.設(shè)計遞歸算法比遞推算法簡潔，但是其執(zhí)行效率較低。直接遞歸。一個算法P顯式地調(diào)用自己。間接遞歸。算法P調(diào)用另一個算法Q,QP。a.遞歸是從算法本身到達遞歸的邊界的；b.不變；“遞推”指重復(fù)“減半”的過程。則問題得到解決，假設(shè)摸索失敗，則逐步回退換別的路線再進展摸索?！菊骖}演練】以下表達中正確的選項是()。［20239月真題］A.所謂算法就是計算方法B.程序可以作為算法的-種描述方法C.算法設(shè)計只需考慮得到計算結(jié)果D.算法設(shè)計可以無視算法的運算時間【答案】BA不等同于計算方法，是指對解題方案的進確而完整的描述；C項錯誤，算法設(shè)計需要考慮可行性、確定性、有窮性與足夠的情報；D項錯誤，算法設(shè)計有窮性要求操作步驟有限且必需在有限時間內(nèi)完成，消耗太長時間得到的正確結(jié)果是沒有意義的。以下關(guān)于算法的描述中錯誤的選項是。［20233月真題］A.算法強調(diào)動態(tài)的執(zhí)行過程，不同于靜態(tài)的計算公式B.算法必需能在有限個步驟Z后終止C算法設(shè)計必需考慮算法的簡潔D.算法的優(yōu)劣取決于運行算法程序的環(huán)境【答案】D【解析】算法是指對解題方案的準(zhǔn)確而完整的描述。A項正確，算法強調(diào)實現(xiàn)，不同于數(shù)學(xué)上的計算方法；BCD法被編程實現(xiàn)運行時才會受到運行環(huán)境影響。3算法簡潔度時間簡潔度量。算法的工作量用算法所執(zhí)行的根本運算次數(shù)來度量，而算法所執(zhí)行的根本運算次數(shù)是問題規(guī)模的函數(shù)，即算法的工作量=彳(n)其中，n是問題的規(guī)模。均性態(tài)定義為：A(n)=Xp(x)t(x)nXDn其屮，X是全部可能輸入屮的某個特定輸入，p(X)X消滅的概率，即輸入為X的概率，t(X)X時所執(zhí)行的根本運算次數(shù)，Dn表示當(dāng)規(guī)模為n時，算法執(zhí)行時全部可能輸入的集合。最壞狀況簡潔性最壞狀況分析是指規(guī)模為n時，算法所執(zhí)行的根本運算的最大次數(shù)。其定義為：W(n)=max{t(x)}空間簡潔度

XGDn空間。括以下兒種：a.算法程序占用的空間；b.輸入的初始數(shù)據(jù)占用的存儲空間；c. 算法執(zhí)行過程屮所需要的額外空間。規(guī)模來說是常數(shù)，則稱該算法是原地工作的?！菊骖}演練】以下表達中正確的選項是()。［20233月真題］算法的效率只與問題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲構(gòu)造無關(guān)算法的時間簡潔度是指執(zhí)行算法所需要的計算工作量數(shù)據(jù)的規(guī)律構(gòu)造與存儲構(gòu)造是一一對應(yīng)的D.算法的時間簡潔度與空間簡潔度確定相關(guān)【答案】B【解析】算法的時間復(fù)朵度是指算法在計算機內(nèi)執(zhí)行時所需時間的度量；與時間簡潔度類似，空間簡潔度是指算法在計算機內(nèi)執(zhí)行時所需存儲空間的度量。算法的空間簡潔度是指〔 〕。［2023年9月真題］A. 算法在執(zhí)行過程屮所需要的計算機存儲空I”B.算法所處理的數(shù)據(jù)量C.算法程序中的語句或指令條數(shù)D.算法在執(zhí)行過程中所需要的臨時工作單元數(shù)【答案】A【解析】空間簡潔度是是對一個算法在運行過程中臨時占用存儲空間大小的量度。算法空間簡潔度的度量方法是〔 〕。［2023年9月真題］算法程序的長度算法所處理的數(shù)據(jù)量C.執(zhí)行算法所需要的工作D.執(zhí)行算法所需要的存儲空間【答案】D【解析】算法的空間簡潔度包括：①輸入數(shù)據(jù)所占的存儲空間；②程序本身所占的存儲空間；③算法執(zhí)行過程中所需要的額外空I”可，是指執(zhí)行這個算法所需要的內(nèi)存空I”可，數(shù)據(jù)構(gòu)造的根本概念1概述數(shù)據(jù)處理概述元素進展分析。②關(guān)鍵問題大量數(shù)據(jù)元素在計算機中如何組織，以便提高數(shù)據(jù)處理的效率，從而節(jié)約計算機的存儲空間，這是進展數(shù)據(jù)構(gòu)造處理的關(guān)鍵問題。數(shù)據(jù)構(gòu)造爭論概述算機中的存儲關(guān)系，即數(shù)據(jù)的存儲構(gòu)造；c.對各種數(shù)據(jù)構(gòu)造進展的運算。在數(shù)據(jù)處理過程中所占用的計算機存儲空間。2數(shù)據(jù)構(gòu)造的概念數(shù)據(jù)構(gòu)造的定義數(shù)據(jù)構(gòu)造是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合，即它是反映數(shù)據(jù)元素Z集合的表示。簡言之，兩方面內(nèi)容：①表述數(shù)據(jù)元素的信息；②表示各數(shù)據(jù)元素Z間的前后件關(guān)系。數(shù)據(jù)的規(guī)律構(gòu)造①定義數(shù)據(jù)的規(guī)律構(gòu)造是指反映數(shù)據(jù)元素之問規(guī)律關(guān)系的數(shù)據(jù)構(gòu)造。數(shù)據(jù)元素的集合，通常記為D；D上的關(guān)系，通常記為R,它反映了D中各數(shù)據(jù)元素之間的前后件關(guān)系。一個數(shù)據(jù)構(gòu)造B可表示為：B=〔D,R〕為反D中個數(shù)據(jù)元素之間的前后件關(guān)系，一般用二元組來表示。數(shù)據(jù)的存儲構(gòu)造①定義數(shù)據(jù)的存儲構(gòu)造，也稱數(shù)據(jù)的物理構(gòu)造，是指數(shù)據(jù)規(guī)律構(gòu)造在計算機存儲空間中的存放形式。在數(shù)據(jù)的存儲構(gòu)造中，不僅要存放各數(shù)據(jù)元素的信息，而且要存放各數(shù)據(jù)元素之I”可的前后件信息。②常用的存儲構(gòu)造：a.挨次；b.鏈接；c.索引。承受不同的存儲構(gòu)造，數(shù)據(jù)處理的效率是不同的?！菊骖}演練】以下表達中正確的選項是〔 〕。［2023年3月真題］A.有且只有一個根結(jié)點的數(shù)據(jù)構(gòu)造確定是線性構(gòu)造B.每一個結(jié)點最多有一個前件也最多有一個后件的數(shù)據(jù)構(gòu)造確定是線性構(gòu)造C.有且只有一個根結(jié)點的數(shù)據(jù)構(gòu)造確定是非線性構(gòu)造D.【答案】D之外，其它數(shù)據(jù)元素均有唯一的“后繼”。D項正確，如樹形構(gòu)造只有一個根結(jié)點，為非線性構(gòu)造。3數(shù)據(jù)構(gòu)造的圖形表示在數(shù)據(jù)構(gòu)造的圖形表示屮，數(shù)據(jù)集合D屮每個元素用屮間標(biāo)有元素值的方框表示，稱為數(shù)據(jù)結(jié)點〔簡稱結(jié)點〕；對關(guān)系R中的每一個二元組，用一條有向線段從前件結(jié)點指向后件結(jié)點?！惨卜Q葉子結(jié)點都稱為內(nèi)部結(jié)點。數(shù)據(jù)構(gòu)造屮的元素結(jié)點可能是在動態(tài)變化的，這種變化表達在結(jié)點數(shù)量的增減以及各結(jié)點Z關(guān)系的動態(tài)變化上。4線性構(gòu)造與非線性構(gòu)造依據(jù)數(shù)據(jù)構(gòu)造中各數(shù)據(jù)元素之間的前后件關(guān)系的簡潔程度，可將數(shù)據(jù)構(gòu)造分為：線性構(gòu)造〔線性表〕一個非空的數(shù)據(jù)構(gòu)造滿足以下兩個條件時，稱其為線性構(gòu)造：①有且只有一個根結(jié)點；②每個結(jié)點最多只有一個前件，也最多只有一個后件。線性構(gòu)造中插入或刪除任何一個結(jié)點還應(yīng)是線性構(gòu)造，假設(shè)不滿足這個條件就不能稱之為線性構(gòu)造。非線性構(gòu)造假設(shè)一個數(shù)據(jù)構(gòu)造不是線性構(gòu)造，則稱之為非線性構(gòu)造。對該數(shù)據(jù)構(gòu)造的運算是否依據(jù)線性構(gòu)造的規(guī)章來處理進展推斷。線性表及其挨次存儲構(gòu)造1線性表的根本概念們白己的序號，即數(shù)據(jù)元素之間的相對位置是線性的。非空線性表的構(gòu)造特征：①有且只有一個根結(jié)點ai.它無前件；②有且只有一個終端結(jié)點務(wù)，它無后件；③除根結(jié)點與終端結(jié)點外，英他全部結(jié)點有且只有一個前件，也有且只有一個后件。線性表屮結(jié)點的個數(shù)n稱為線性表的長度。當(dāng)n=0時，稱為空表?！菊骖}演練】以下表達中正確的選項是〔 題］A.結(jié)點中具有兩個指針域的鏈表確定是二叉鏈表B.結(jié)點中具有兩個指針域的鏈表可以是線性構(gòu)造，也可以是非線性構(gòu)造C 二叉樹只能釆用鏈?zhǔn)酱鎯?gòu)造D.循環(huán)鏈表是非線性構(gòu)造【答案】B【解析】A項錯誤，具有兩個指針域的鏈表可能是雙向鏈表；B項正確，如雙向鏈表是線性構(gòu)造，二叉樹為非線性構(gòu)造，兩者結(jié)點中均有兩個指針域；C項錯誤，二叉樹通常承受鏈?zhǔn)酱鎯?gòu)造，也可承受其他構(gòu)造；D壞鏈表是線性構(gòu)造，規(guī)律概念線性非線性與實際存儲構(gòu)造無關(guān)?？键c2線性表的挨次存儲構(gòu)造概述挨次存儲是一種最簡潔的在計算機屮存放線性表的方法，也稱挨次安排。特點：①線性表中全部元素所占的存儲空間是連續(xù)的；②線性表中各數(shù)據(jù)元素在存儲空間中是按規(guī)律挨次依次存放的。在線性表的挨次存儲構(gòu)造中，其前后件兩個元素在存儲空間中是緊鄰的，且前件元素確定存儲在后件元素的前面。運算在線性表的挨次存儲構(gòu)造下，可對線性表進展以下運算：①插入：在線性表的指定位置處參與一個的元素；②刪除：在線性表屮刪除指定的元素；③查找：在線性表中查找某個〔或某些〕特定的元素；④排序：對線性表中的元素進展整序；⑤分解：按要求將一個線性表分解成多個線性表；⑥合并：按要求將多個線性表合并成一個線性表；⑦復(fù)制：復(fù)制一個線性表；⑧逆轉(zhuǎn)：逆轉(zhuǎn)一個線性表等。【真題演練】在線性表的挨次存儲構(gòu)造中，其存儲空間連續(xù)，各個元素所占的字節(jié)數(shù)〔 〕。［2023年3月真題］一樣，元素的存儲挨次與規(guī)律挨次全都一樣，但其元素的存儲挨次可以與規(guī)律挨次不全都C.不同，但元素的存儲挨次與規(guī)律挨次全都D.不同，且其元素的存儲挨次可以與規(guī)律挨次不全都【答案】A【解析】在挨次表中，每個元素占有一樣的存儲單元。挨次表具有特征：①線性表中全部元素所占的存儲空間是連續(xù)的；②線性表屮各數(shù)據(jù)元素在存儲空問屮是按規(guī)律挨次依次存放的?？键c3挨次表的插入運算假設(shè)線性表的存儲空間為V〔1：m〕,線性表的長度為n〔㈣ 插入的位置為i〔表示在第i個位置插入元素〕，則挨次表插入元素過程如下：首先處理以下三種特別狀況：①當(dāng)存儲空間已滿〔即n=m〕時為“上溢”錯誤，不能進展插入，算法完畢；i>n時，認為在最終一個元素之后〔即第n+1個元素之前〕插入；ivl1個元素之前插入。從最終一個元素開頭，直到第i個元素，其中每一個元素均往后移動一個位置。最終將元素插入到第i1。4挨次表的刪除運算假設(shè)線性表的存儲空間為V〔1m〕,線性表的長度為n〔n<m〕,i〔i個元素〕，挨次表刪除元素的過程如下：首先處理以下兩種特別狀況：①當(dāng)線性表為空〔即n=0〕時為上溢”錯誤，不能進展插入，算法完畢；i<li>n時，認為在最終一個元素之后〔即第n+1個元素之前〕插入。然后從第i+1個元素開頭，直到最終一個元素，其屮每一個元素均依次往前移動一個位置。1。棧和隊列1棧及其根本運算刪除的線性表。棧的特點：最先被刪除的元素；棧底元素總是最先被插入也是最終被刪除的。③通常用指針top來指示棧頂位置，用指針bottom指向棧底，棧頂指針top動態(tài)反映了棧中元素的變化狀況。棧的挨次存儲及其運算在棧的挨次存儲空間S〔l:m〕中，top0表示棧空；top=m表示棧滿。棧的三種運算：程如下：作〔這種狀況稱為?！吧弦纭卞e誤〕，算法完畢。然后將棧頂指針進一〔即top1〕。c.最終將x插入棧頂指針指向的位置。②退棧運算退棧運算是指取岀棧頂元素并賦給一個指定的變量。操作過程如下：〕，法完畢。然后將棧頂元素〔棧頂指針指向的元素〕賦給一個指定的變量。最終將棧頂指針退一〔即top1〕o程如下：0。假設(shè)是，則說明?？眨x不到棧頂元素，算法完畢。b.y。這個運算不刪除棧頂元素，只是將它的值賦給一個變量，棧頂指針不會變?！菊骖}演練】1.棧

支持子程序調(diào)用的數(shù)據(jù)構(gòu)造是〔〕。［20239月真題］樹隊列二叉樹【答案】A調(diào)用后返回到主程序中調(diào)用子程序的位置，連續(xù)執(zhí)行，這種調(diào)用符合棧的特點。以下與棧構(gòu)造有關(guān)聯(lián)的是〔 〕。［2023年3月真題］數(shù)組的定義域使用操作系統(tǒng)的進程調(diào)度C.函數(shù)的D.選擇構(gòu)造的執(zhí)行【答案】C遞歸函數(shù)是通過棧來實現(xiàn)的，所以調(diào)用原則和棧的實現(xiàn)相全都。設(shè)棧的挨次存儲空間為S〔1：50〕,初始狀態(tài)為top=0o現(xiàn)經(jīng)過一系列入棧與退棧運算后，top=20,則當(dāng)前棧中的元素個數(shù)為〔 〕。［2023年3月真題］30292019【答案】C1,退1。top=0表示棧為空，在運算過程中，指針始終指向棧頂元素。top=20,20一個棧的初始狀態(tài)為空?，F(xiàn)將元素1、2、3、4、5、A、B、C、D、E依次入棧，然后再依次出棧，則元素出棧的挨次是〔 〕。［2023年9月真題］12345ABCDED.54321FDCBA【答案】B【解析】棧中數(shù)據(jù)的插入和刪除都在棧頂依據(jù)“先進后出”的原則進展操作。2什么是隊列隊列〔Queue〕是指允許在一端進展插入、而在另一端進展刪除的線性表。隊列的特點前一個位置。②最先插入的元素最先被刪除，最終插入的元素最終被刪除，遵循“先進先出”或“后進后出”原則。rear和排頭指針front共同反映隊列中元素變動狀況。④入隊運算指只涉及隊尾指針rear變化，退隊運算只涉及排頭指針front變化。供隊列循環(huán)使用。在循環(huán)隊列屮，用隊尾指針real指向隊尾元素，用排頭指針front指向排頭元素的前一個位置，從排頭指針front指向的后一個位置到隊尾指針real指向的位置均是隊列中元素。隊列空的條件是s=0；隊列滿的條件是s=l且front=rearo隊列的兩種運算假設(shè)循環(huán)隊列的初始狀態(tài)為空，即：s=0,Mfront=rcar=mo①入隊運算入隊運算是指在循環(huán)隊列的隊尾參與一個元素。操作過程如下：〔S=l〕行入隊運算。這種狀況稱為“上溢二此時算法完畢。然后將隊尾指針進一〔即rear=rear+1〕rear=m+1rear=1o最終將元素x插入隊尾指針指向的位置，并且置循壞隊列非空標(biāo)志。②退隊運算退隊運算是指在循環(huán)隊列的排頭位置退出一個元素并賦給指定的變量。操作過程如下：首先推斷循環(huán)隊列是否為空。當(dāng)循環(huán)隊列為空〔s=0〕算法完畢。然后將排頭指針進一〔即front=front+1〕,front=m+1front=loc.的變量。d.front=rear時置循環(huán)隊列空標(biāo)志〔即s=0〕?！菊骖}演練】以下表達中正確的選項是〔 〕。［2023年9月真題］棧是“先進先出”的線性表B.隊列是“先進后出“的線性表C.循壞隊列是非線性構(gòu)造D.有序線性表既可以釆用挨次存儲構(gòu)造，也可以承受鏈?zhǔn)酱鎯?gòu)造【答案】D【解析】棧和隊列都是受限的線性表，其中棧依據(jù)“先進后Hr的原則組織數(shù)據(jù)，插入與刪除操作被限制在棧頂一端進展；隊列承受“先進先出‘‘的原則組織數(shù)據(jù)。循環(huán)隊列是隊列的一種特別形式，是線性構(gòu)造。以下表達中正確的選項是〔 〕。［2023年3月真題］A.循環(huán)隊列是挨次存儲構(gòu)造B.C.循壞隊列是非線性構(gòu)造D.發(fā)生溢消滅象【答案】A【解析】B項錯誤，循環(huán)隊列是一種挨次存儲構(gòu)造的隊列；CD11!現(xiàn)象，掩蓋前面的數(shù)據(jù)。對于循環(huán)隊列，以下表達中正確的選項是〔 〕。［2023年9月真題］隊頭指針是固定不變的隊頭指針確定大于隊尾指針C.隊頭指針確定小于隊尾D.隊頭指針可以大于隊尾指針，也可以小于隊尾指針【答案】D1111,頭指針要％011。由于存在％皿運算，所以隊頭指針與隊尾指針大小關(guān)系不確定。以下表達中正確的選項是〔 循環(huán)隊列有隊頭和隊尾兩個指針，因此，循環(huán)隊列是非線性構(gòu)造B 在循環(huán)隊列中，只需要隊頭指針就能反映隊列中元索的動態(tài)變化狀況C. 在循環(huán)隊列屮，只需要隊尾指針就能反映隊列屮元素的動態(tài)變化狀況D.循壞隊列中元素的個數(shù)是由隊頭指針和隊尾指針共同打算【答案】D【解析】在循環(huán)隊列中元素的個數(shù)是由隊頭指針和隊尾指針共同打算的，入隊使得隊尾指針變化，出隊使得隊頭指針變化。線性鏈表1線性鏈表的根本概念線性表的挨次存儲構(gòu)造存在的缺陷：①在插入或刪除元素時，為保證操作后的線性表照舊是挨次存儲，需要大量移動數(shù)據(jù)元素，效率很低。②在挨次存儲構(gòu)造下，線性表的存儲空間不便于擴大，易產(chǎn)生上溢現(xiàn)彖。③線性表的挨次存儲構(gòu)造不便于對存儲空間的動態(tài)安排。鏈?zhǔn)酱鎯Y(jié)點組成：①數(shù)據(jù)域：用于存放數(shù)據(jù)元素值；各數(shù)據(jù)結(jié)點的存儲挨次示線性構(gòu)造，也可用于表示非線性構(gòu)造。在用鏈?zhǔn)綐?gòu)造表示較簡潔的非線性構(gòu)造時，其指針域的個數(shù)要多一些。線性璉表①定義：線性鏈表是線性表的鏈?zhǔn)酱鎯?gòu)造。各數(shù)據(jù)元素之間的前后件關(guān)系是由各結(jié)點的指針域來指示的；指針指向其后件結(jié)點。帶鏈的棧帶鏈的?？梢杂脕硎占囁銠C存儲空間中全部空閑的存儲結(jié)點。與挨次棧一樣，帶鏈棧的根本操作有以下兒個：①棧的初始化：建立一個空棧的挨次存儲空間；②入棧運算：在棧頂位置插入一個元素；③退棧運算：取出棧頂元素并賦給一個指定的變量；④讀棧頂元素：將棧頂元素賦給一個指定的變量。帶鏈的隊列與挨次隊列一樣，帶鏈隊列的根本操作有以下兒個：①隊列的初始化：建立一個空隊列的挨次存儲空間；②入隊運算：在循環(huán)隊列的隊尾參與一個元素；③退隊運算：在循壞隊列的排頭位置退出一個元素并賦給指定的變量。【真題演練】1. 以下表達屮正確的選項是〔〕。［20239月真題］所謂有序表是指在挨次存儲空間內(nèi)連續(xù)存放的元素序列有序表只能挨次存儲在連續(xù)的存儲空間內(nèi)C.有序表可以用鏈?zhǔn)酱鎯Ψ绞酱鎯υ诓贿B續(xù)的存儲空間內(nèi)D.任何存儲方式的有序表均能承受二分法進展查找【答案】C〔允許相鄰元素一樣與物理存儲無關(guān)。二分法查找時涉及下標(biāo)運算，要求有序表必需挨次存儲。2.存儲構(gòu)造相比，鏈?zhǔn)酱鎯?gòu)造的優(yōu)點有〔節(jié)約存儲空間插入與刪除運算效率高C.便于【答案】B【解析】線性表的鏈?zhǔn)酱鎯?gòu)造與挨次存儲構(gòu)造的優(yōu)缺點比較如下：

線性表的璉式存儲構(gòu)造與挨次〕。［20239月真題］類型優(yōu)點缺點挨次表①便利隨機存?、跓o需額外的存儲空間來表示結(jié)點間的規(guī)律關(guān)系①插入和刪除運算效率很低②存儲空間不便于擴大③不便于對存儲空間的動態(tài)安排鏈表指針類型優(yōu)點缺點挨次表①便利隨機存?、跓o需額外的存儲空間來表示結(jié)點間的規(guī)律關(guān)系①插入和刪除運算效率很低②存儲空間不便于擴大③不便于對存儲空間的動態(tài)安排鏈表指針間的動態(tài)安排需要額外的空間來表示數(shù)據(jù)元素之間的規(guī)律關(guān)系，存儲密度低A.挨次存儲構(gòu)造的存儲一是是連續(xù)的，鏈?zhǔn)酱鎯?gòu)造的存儲空I”可不愿定是連續(xù)的B.，鏈?zhǔn)酱鎯?gòu)造只針對非線性構(gòu)造C挨次存儲構(gòu)造能存儲有序表，鏈?zhǔn)酱鎯?gòu)造不能存儲有序表D.鏈?zhǔn)酱鎯?gòu)造比挨次存儲構(gòu)造節(jié)約存儲空I”可【答案】A【解析】BC兩項錯誤，規(guī)律概念上的線性非線性是否有序與存儲構(gòu)造為挨次還是鏈?zhǔn)經(jīng)]有直接關(guān)系；D項錯誤，2常見的線性表的運算線性鏈表的運算主要有以下兒個：①在線性鏈表中包含指定元素的結(jié)點之前插入一個元素；②在線性鏈表屮刪除包含指定元素的結(jié)點；③將兩個線性鏈表按要求合并成一個線性鏈表；④將一個線性鏈表按要求進展分解；⑤逆轉(zhuǎn)線性鏈表；⑥復(fù)制線性鏈表；⑦線性鏈表的排序；⑧線性鏈表的查找。在線性鏈表中查找指定元素非空線性鏈表中查找包含指定元素x的前一個結(jié)點p的根本方法：從頭指針指向的結(jié)點開頭往后沿指針進展掃描，直到后面已沒有結(jié)點或下一個結(jié)點的數(shù)據(jù)域為x為止。因此，由這種方法找到的結(jié)點p有兩種可能：當(dāng)線性鏈表屮存在包含元素x的結(jié)點時，則找到的px的前一個結(jié)點序號；當(dāng)線性鏈表屮不存在包含元素x的結(jié)點時，則找到的p線性鏈表的插入①定義：線性鏈表的插入是指在鏈?zhǔn)絻Υ鏄?gòu)造下的線性表小插入一個元素。在線性鏈表中包含元素X的結(jié)點之前插入一個元素boa.從可利用棧取得一個結(jié)點，設(shè)該結(jié)點號為p,并置結(jié)點p的數(shù)據(jù)域為插入的元素值b。 b.在線性鏈表中查找包含元素x的前一個結(jié)點，設(shè)該結(jié)點的存儲序號為q。c. 最終將結(jié)點p插入到結(jié)點qP指向包含元素x的結(jié)點；其次，使結(jié)點q的指針域內(nèi)容改為指向結(jié)點P。a.不會發(fā)生上溢現(xiàn)象；b.可便利實現(xiàn)存儲空間動態(tài)安排；c.不發(fā)生數(shù)據(jù)元素移動現(xiàn)象，只轉(zhuǎn)變結(jié)點指針，提高插入效率。線性鏈表的刪除①定義：線性鏈表的刪除是指在鏈?zhǔn)絻Υ鏄?gòu)造下的線性表中刪除包含指定元素的結(jié)點。x的結(jié)點。在線性鏈表中查找包含元素x的前一個結(jié)點，設(shè)該結(jié)點序號為q；q后的結(jié)點p從線性鏈表中刪除，即讓結(jié)點q的指針指向包含元素x的結(jié)點p的指針指向的結(jié)點；將包含元素xp送回可利用棧。在線性鏈表中刪除一個元素后，不需要移動表的數(shù)據(jù)元素，只需轉(zhuǎn)變被刪除元素所在結(jié)點的前一個結(jié)點的指針域即可。3循環(huán)鏈表與線性鏈表相比，循環(huán)鏈表具有的特點：的結(jié)點。循壞鏈表的頭指針指向表頭結(jié)點。個環(huán)狀鏈。與線性單鏈表相比，循環(huán)鏈表具有兩方面優(yōu)點：鏈表做不到這一點。與非空表的運算統(tǒng)一。特別狀況，從而實現(xiàn)了空表與非空表運算的統(tǒng)一?！菊骖}演練】3月真題］A.在雙向鏈表中，可以從任何一個結(jié)點開頭直接遍歷到全部結(jié)點B.在循環(huán)鏈表中，可以從任何一個結(jié)點開頭直接遍歷到全部結(jié)點C 在線性單鏈表中，可以從任何一個結(jié)點開頭直接遍歷到全部結(jié)點D.在二叉鏈表中，可以從根結(jié)點開頭遍歷到全部結(jié)點【答案】C【解析】C結(jié)點。A項正確，雙向鏈表的結(jié)點包含前驅(qū)和后繼的兩個指針；B點；D項正確，二叉鏈表屮全部的結(jié)點都是根結(jié)點的分支。樹與二叉樹1樹的根本概念樹是一種簡潔的非線性構(gòu)造，在這種構(gòu)造中，全部數(shù)據(jù)元素Z間的關(guān)系具有明顯的層次特性。在樹的圖形表示中，上端結(jié)點是前件，下端結(jié)點是后件。〔父結(jié)點都可以有多個后件〔子結(jié)點〕，沒有后件的結(jié)點稱為葉子結(jié)點?！獋€結(jié)點擁有的后件個數(shù)稱為該結(jié)點的度。某結(jié)點的度為n,表示該結(jié)點有n后件，除根結(jié)點外，每個結(jié)點都有一個唯一的分支指向它。樹中的結(jié)點數(shù)為樹中全部結(jié)點的度之和再加1。1層，同一層上全部結(jié)點的全部子結(jié)點都在下一層，樹的最大層次稱為樹的深度在樹中，葉子結(jié)點沒有子樹。用樹來表示算術(shù)表達式的原則：①表達式中的每一個運算符在樹中對應(yīng)一個結(jié)點，稱為運算符結(jié)點；②運算符的每一個運算對象在樹中為該運算符結(jié)點的子樹〔在樹中的挨次為從左到右〕；有子樹。【真題演練】以下數(shù)據(jù)構(gòu)造中，屬于非線性構(gòu)造的是〔 〕。［2023年3月真題］A循環(huán)隊列帶鏈隊列D.帶鏈?！敬鸢浮緾點任何一個元素只有唯一的后件。二叉樹的后繼結(jié)點可能不唯一，屬于非線性構(gòu)造。某二叉樹的中序序列為DCBAEFG,DCBGFEA,則該二叉樹的深度〔1層〕為〔 〕o［20233月真題］5432【答案】BDCBGFEA,ADCBAEFG,DCB為左子樹節(jié)點，EFG為右子樹節(jié)點。同理BC父節(jié)點，CD11!左子樹，同理EF根節(jié)點，F(xiàn)G根4,4層。2二叉樹及其根本性質(zhì)二叉樹定義二叉樹是一種很有用的非線性構(gòu)造，與樹構(gòu)造很相像，樹構(gòu)造的全部術(shù)語都可以用到叉樹這種數(shù)據(jù)構(gòu)造上。二叉樹的兩個特點①非空二叉樹只有一個根結(jié)點；②每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右子樹。二叉樹的根本性質(zhì)①在二叉樹的第k2小〔k>l〕個結(jié)點。m2ni-l個結(jié)點。0的結(jié)點〔即葉子結(jié)點〕2的結(jié)點多一個。n個結(jié)點的二叉樹，其深度至少為［log2n］+l,其中［［10妙］10滿二叉樹與完全二叉樹滿二叉樹與完全二叉樹是兩種特殊形態(tài)的二叉樹。①滿二叉樹除最終一層外，每一層上的全部結(jié)點都有兩個子結(jié)點。②完全二叉樹a.b.更精準(zhǔn)地說，假設(shè)從根結(jié)點起，對二叉樹的結(jié)點自上而下、自左至右用自然數(shù)進展連續(xù)編號，則深度為mn個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為m1n之為完全二叉樹。的最大層次為P，則其左分支下的子孫結(jié)點的最大層次或為P,或為p+1。c. 滿二叉樹也是完全二叉樹，而完全二叉樹一般不是滿二叉樹。完全二叉樹具有以下兩共性質(zhì)：n個結(jié)點的完全二叉樹的深度為［logn］+lo2設(shè)完全二叉樹共有n個結(jié)點。假設(shè)從根結(jié)點開頭，按層序〔每一層從左到右〕1,2,n給結(jié)點進展編號，則對于編號為k〔k=l,2,n〕的結(jié)點有以下結(jié)論：第一，假設(shè)k=l,則該結(jié)點為根結(jié)點，它沒有父結(jié)點；假設(shè)k>l,則該結(jié)點的父結(jié)點編號為INT〔k/2〕2kWn,則編號為k2k；否則該結(jié)點無左子結(jié)點〔明顯也沒有右子結(jié)點〕2k+l<n,則k2k+l；從左到右挨次存儲完全二叉樹的各結(jié)點，則很簡潔確定每一個結(jié)點的父結(jié)點、左子結(jié)點和右子結(jié)點的位置。【真題演練】某二叉樹共有13個結(jié)點，其屮有4個度為1的結(jié)點，則葉子結(jié)點數(shù)為〔 〕。［2023年3月真題］5432【答案】A【解析】對任何一棵二叉樹來說，度為0的節(jié)點，即葉子節(jié)點，總是比度為2的節(jié)點多一個。所以可設(shè)葉子節(jié)點n,2的節(jié)點個數(shù)為n-lo13=n+4+n-l,n=5。151的結(jié)點，162的結(jié)點，則該二叉樹中總的結(jié)點數(shù)為〔9

〕。［2023年月真題］32464849【答案】C221617,因此結(jié)點總數(shù)為16+17+15=48。9354352的結(jié)點個數(shù)為〔3月真題］6466C. 436D. 434【答案】D

［2023024352434。4.125個結(jié)點，則該完全二叉樹中的葉子結(jié)點數(shù)為〔題］

7的完全二叉62636465【答案】B1，1,次稱為樹的深度。完全二叉樹指除最終一層外，每一層上的結(jié)點數(shù)均到達最大值，在最終一層上只缺少右邊的假設(shè)干結(jié)點。此題中，前6層是滿二叉樹，結(jié)點個數(shù)為6-1=63所以第7層有125-63=62個葉子結(jié)點，分別掛在第6層的左邊626162+1=63個葉子結(jié)3在計算機中，二叉樹承受鏈?zhǔn)酱鎯?gòu)造。用于存儲二叉樹中各元素的存儲結(jié)點由兩局部組成：址；b.右指針：指向該結(jié)點的右指結(jié)點的存儲地址?！菊骖}演練】以下表達屮正確的選項是〔 題］A.結(jié)點中具有兩個指針域的鏈表確定是二叉鏈表B.結(jié)點中具有兩個指針域的鏈表可以是線性構(gòu)造，也可以是非線性構(gòu)造C 二叉樹只能釆用鏈?zhǔn)酱鎯?gòu)造D.循環(huán)鏈表是非線性構(gòu)造【答案】B【解析】A項錯誤，具有兩個指針域的鏈表可能是雙向鏈表；B項正確，如雙向鏈表是線性構(gòu)造，二叉樹為非線性構(gòu)造，兩者結(jié)點屮均有兩個指針域；C項錯誤，二叉樹通常承受鏈?zhǔn)酱鎯?gòu)造，也可承受其他構(gòu)造；D環(huán)鏈表是線性構(gòu)造，規(guī)律概念線性非線性與實際存儲構(gòu)造無關(guān)。4原則。二叉樹的遍歷可分為三種：前序遍歷〔DLR〕樹，最終遍歷右子樹；并且，在遍歷左、右子樹時，照舊先訪問根結(jié)點，然后遍歷左子樹，最終遍歷右子樹。該過程是一個遞歸的過程。中序遍歷〔LDR〕點，最終遍歷右子樹；并且，在遍歷左、右子樹時，照舊先遍歷左子樹，然后訪問根結(jié)點，最終遍歷右子樹。因此，屮序遍歷二叉樹的過程也是一個遞歸的過程。后序遍歷〔LRD〕樹，最終訪問根結(jié)點，并且，在遍歷左、右子樹時，照舊先遍歷左子樹，然后遍歷右子樹，最終訪問根結(jié)點。因此，后序遍歷二叉樹的過程也是一個遞歸的過程。假設(shè)知道了某二叉樹的前序序列和屮序序列，則可以唯一地恢復(fù)該二叉樹，假設(shè)知道了某二叉樹的后序序列和小序序列，則也可以唯一地恢復(fù)該二叉樹。但假設(shè)只知道某二叉樹的前序序列和后序序列，是不能唯一恢復(fù)該二叉樹的。【真題演練】則后序遍歷為〔ABDEGCFH則后序遍歷為〔D.ABCDEFGH【答案】C【解析】二叉樹遍歷方式有：①前序遍歷，即訪問根結(jié)點在訪問左子樹和訪問右子樹Z前；②中序遍歷，即訪問Z前序遍歷ABDEGCFHDBGEAFHC,不斷地推斷根結(jié)點以及左右子樹，可求后序遍歷為DGEBHFCAo2.DCBA,則后序序列為〔BADCDCBACDABABCD【答案】B

某二叉樹的前序序列為ABCD,中〕。［20239月真題］問根結(jié)點在訪問左子樹和訪問右子樹兩者Z間；③后序遍歷，即訪問根結(jié)點在訪問左子樹和訪問右子樹Z后。題中前ABCD,DCBA,A為根結(jié)點，DC的左子結(jié)點，CB的左子結(jié)點，B為A的左子結(jié)點，所以后序序列為DCBAo查找技術(shù)1挨次查找〔挨次搜尋〕根本方法從線性表的第一個元素開頭，依次將線性表中的元素與被查元素進展比較，假設(shè)相等則表示找到〔即查找成功〕線性表中全部的元素都與被查元素進展了比較但都不相等，則表示線性表中沒有要找的元素〔即查找失敗〕。以下兩種狀況只能承受挨次查找：〔即表中元素的排列是無序的〕，則不管是挨次存儲構(gòu)造還是鏈?zhǔn)酱鎯?gòu)造，都只能用挨次查找。②即使是有序線性表，假設(shè)承受鏈?zhǔn)酱鎯?gòu)造，也只能用挨次查找。挨次查找的缺陷：效率太低2二分法查找〔對分查找〕適用范圍只適用于挨次存儲的有序表，在此所說的有序表是指線性表中元素按值非遞減排列。具體方法設(shè)有序線性表的長度為n,被查元素為x,lhX與線性表的中間項進展比較：假設(shè)中間項的值等于X,則說明查到，查找完畢；X小于中間項的值，則在線性表的前半局部〔即中間項以前的局部〕以一樣的方法進展查找X大于屮間項的值，則在線性表的后半局部〔即屮間項以后的局部〕以一樣的方法進展查找0〔說明線性表屮沒有這個元素〕為止?！菊骖}演練】在長度為n的有序線性表屮進展二分查找，最壞狀況下需要比較的次數(shù)是〔 〕。［2023年9月真題］O〔n〕O〔2〕C.O〔log2n〕D.O〔nlog2n〕【答案】C【解析】在最壞狀況下，對于長度為n的有序線性表，二分法查找只需要比較k〕g2n次。排序技術(shù)1交換類排序法〔1〕冒泡排序法①定義：冒泡排序法是一種最簡潔的交換類排序方法，通過相鄰數(shù)據(jù)元素的交換逐步將線性表變成有序。②a.根本過程：從表頭開頭往后掃描線性表，在掃描過程屮逐次比較相鄰兩個元素的大小。假設(shè)相鄰兩個元素屮，前面的元素大于后面的元素，則將它們互換，稱之為消去了一個逆序。的元素小于前面的元素，則將它們互換，這樣就又消去了一個逆序。對剩下的線性表重復(fù)上述過程，直到剩下的線性表變空為止，此時的線性表已經(jīng)變?yōu)橛行颉５奖淼那邦^。冒泡排序由此而得名，且冒泡排序又稱下沉排序。假設(shè)線性表的長度為m則在最壞狀況下，冒泡排序需要經(jīng)過n/2遍的從前往后的掃描和n/2需要的比較次數(shù)為n〔n-1〕/2o〔2〕快速排序法從線性表中選取一個元素T,將線性表后面小于T的元素移到前面，前面大于TT為分割線將線性表分割成前后兩個子表。再將得到的子表依據(jù)這個過程連續(xù)下去，直到全部子表為空為止。②快速排序在最壞狀況下需要進展n〔n-1〕/2次比較，但實際的排序效率要比冒泡排序高得多。2插入類排序法簡潔插入排序法①定義:所謂插入排序，是指將無序序列中的各元素依次插入到已經(jīng)有序的線性表中。②插入過程：j個元素放到一個變量T中，然后從有序子表的最終一個元素〔即線性表中第jl個元素〕T進展比較，將大于T的元素均依次向后移動一個位置，直到覺察一個元素不大于T為止，此時就將T〔即原線性表中的第j個元素〕插入到剛移出的空位置上，有序子表的長度就變?yōu)閖了。③這種排序方法的效率與冒泡排序法一樣。在最壞狀況下，簡潔插入排序需要n〔n-1〕/2次比較。希爾排序法①根本思想：將整個無序序列分割成假設(shè)干小的子序列分別進展插入排序。②子序列的分割方法：將相隔某個增量h的元素構(gòu)成一個子序列。在排序過程中，逐次減小這個增量，最終當(dāng)h1時，進展一次插入排序，排序就完成。增量序列一般取ht=n/2k〔k=l,2,［log2n］〕,n為待排序序列的長度。0(』5)?！菊骖}演練】在最壞悄況下( ］A.快速排序的時間簡潔度比冒泡排序的時間簡潔度要小B.快速排序的時間簡潔度比希爾排序的時間簡潔度要小C.希爾排序的時間簡潔度比直接插入排序的時間簡潔度要小D.快速排序的時間簡潔度與希爾排序的時間簡潔度是一樣的【答案】CB(OnL5<0n2C項正確；快速排序比希爾排序的時間簡潔度大(O(『)>0(nL5D項錯誤。3選擇類排序法簡潔選擇排序法的子表承受同樣的方法，直到子表空為止。對于長度為n的序列，選擇排序需要掃描ml遍，每一遍掃描均從剩下的子表中選出最小的元素，然后將該最小的元素與子表中的第一個元素進展交換。②簡潔選擇排序法在最壞狀況下需要比較n(n-1)/2次。堆排序法堆的定義n個元素的序列(hl，h2,…，hj當(dāng)且僅當(dāng)滿足h.^h2. rh.^h2.或(il,2, n/2)時稱之為堆。堆排序的方法：a.將一個無序序列建成堆；b.c.反復(fù)做上一步，直到剩下的子序列為空為止。0(nlog2n)o【真題演練】1.以下各序列中不是堆的是( )。［2023年9月真題］A. (91,85,53,36,47,30,24,12)B.(91,85,53,47,36,30,24,12)C.(47,91,53,85,30,12,24,36)D.(91,85,53,47,30,12,24,36)【答案】C【解析】假設(shè)有n個元素的序列，將元素按挨次組成一棵完全二叉樹，假設(shè)全部結(jié)點的值大于或等于左右子結(jié)點的2 對長度為n的線性表排序，在最壞狀況下，比較次數(shù)不是n(n-1)/2的排序方法是(月真題］B.冒泡排C.直接插入排序

)。［20239值，則為大根堆；假設(shè)全部結(jié)點的值小于或等于左右子結(jié)點的值，貝I」為小根堆。C項錯誤，47<91,但91>85,不滿足堆的條件，所以不是堆。D.堆排序【答案】D【解析】在最壞狀況下，快速排序、冒泡排序、直接插入排序與簡潔選擇排序法均需要比較n〔n-1〕/2排序需要比較的次數(shù)最少，為nlog2n03.O〔n15〕O〔nlog2n〕o”n〔n“〕〕

堆排序最壞狀況下的時間簡潔度為〔〕。［20239月真題］2\/O〔log2n〕【答案】B【解析】堆排序是指利用積存樹這種數(shù)據(jù)構(gòu)造所設(shè)計的一種排序算法，屈于選擇排序。在對長度為n的線性表『O〔nlogzn〕,簡潔度最小。強化習(xí)題以下表達屮正確的選項是〔 〕。一個規(guī)律數(shù)據(jù)構(gòu)造只能有一種存儲構(gòu)造規(guī)律構(gòu)造屬于線性構(gòu)造，存儲構(gòu)造屬于非線性構(gòu)造C.一個規(guī)律數(shù)據(jù)構(gòu)造可以有多種存儲構(gòu)造，且各種存儲構(gòu)造不影響數(shù)據(jù)處理的效率D.【答案】D【解析】規(guī)律數(shù)據(jù)構(gòu)造，是指反映數(shù)據(jù)元索Z據(jù)處理的效率是不同的。以下表達中正確的選項是〔〕。A.線性表的鏈?zhǔn)酱鎯?gòu)造與挨次存儲構(gòu)造所需要的存儲空間是一樣的B.線性表的鏈?zhǔn)酱鎯?gòu)造所需要的存儲空間一般要多于挨次存儲構(gòu)造C.線性表的鏈?zhǔn)酱鎯?gòu)造所需要的存儲空間一般要少于挨次存儲構(gòu)造D.間的需求上沒有可比性【答案】B結(jié)點和一個后繼結(jié)點。它的常用存儲構(gòu)造為：①挨次存儲構(gòu)造，物理上連續(xù)存儲，空間位置隱含規(guī)律位置；②鏈?zhǔn)酱嫠枣準(zhǔn)酱鎯?gòu)造所需的存儲空間一般要多于挨次存儲構(gòu)造。以下數(shù)據(jù)構(gòu)造屮，能夠依據(jù)“先進后出”原則存取數(shù)據(jù)的是〔 〕。循環(huán)隊列隊【答案】B列只能在隊頭刪除元素，在隊尾插入元素，依據(jù)先進先出的原則組織數(shù)據(jù)。以下表達中正確的選項是〔 〕。循環(huán)隊列是隊列的一種鏈?zhǔn)酱鎯?gòu)造B.循環(huán)隊列是隊列的一種挨次存儲構(gòu)造C.循環(huán)隊列是非線D.循環(huán)隊列是一種規(guī)律構(gòu)造【答案】Bo單元存儲數(shù)據(jù)元素，定義兩個游標(biāo)：指向隊頭的游標(biāo)〔hont〕、指向隊尾的游標(biāo)〔rear〕o以下關(guān)于線性鏈表的表達中，正確的選項是〔 〕。A.各數(shù)據(jù)結(jié)點的存儲空間可以不連續(xù)，但它們的存儲挨次與規(guī)律挨次必需全都B.各數(shù)據(jù)結(jié)點的存儲挨次與規(guī)律挨次可以不全都，但它們的存儲空問必需連續(xù)C.進展插入與刪除時，不需要移動表中的元素D.以上說法均不正確【答案】C【解析】線性構(gòu)造常用存儲構(gòu)造為：①挨次存儲構(gòu)造，物理上連續(xù)存儲，空間位置隱含規(guī)律位置；②鏈?zhǔn)酱鎯Ρ碇械脑?，只需轉(zhuǎn)變結(jié)點的指針域即可。-棵二叉樹共有25個結(jié)點，其中5個是葉子結(jié)點，則度為1的結(jié)點數(shù)為〔 〕。161064【答案】A3：0225-1=4125-5-4=16個。己知二叉樹后丿了；遍歷序列是CDABE,中序遍歷序列是CADEB?它的前療；遍歷用列是〔 〕。ABCDEECABDEACDBCDEAB【答案】C【解析】二叉樹的遍歷方式包括：①前序遍歷，先訪問根結(jié)點，再訪問左右子樹；②中序遍歷，訪問根結(jié)點在訪問左右子樹之間；③后序遍歷，在訪問左右子樹之后再訪問根結(jié)點。后序遍歷最終遍歷到根結(jié)點，所以E為根結(jié)點。中序遍歷根結(jié)點在左右子樹之間，所以B為二叉樹的右子樹，CAD為左子樹。同理，在CAD分支中，DCA的父結(jié)點，CD的左孩子，AD的右孩子。依據(jù)所得樹的外形，可得前序遍歷為EACDBo8. 對有序線性表〔23,29,34,55,60,70,78〕用二分法查找值為60的元素時，需要比較次數(shù)為〔 〕。12C 3D.4【答案】C【解析】二分法查找法不斷的將序列分為可能包含和必定不包含的兩局部，此題流程為：①將60與中間的元素55進展比較，60>55,6046070進展比較，60<70,60不行26060比較，這時查找成功。以下排序方法中，最壞狀況下比較次數(shù)最少的是( A.B.簡單項選擇擇排序C.直接插入排序D.堆排序【答案】D【解析】在最壞狀況下，冒泡排序、直接插入排序與簡潔選擇排序法均需要比較n(n-1)/2nl.5次，堆排序需要比佼的次數(shù)最少，為nlog2n0B在序列中的序號是。1379【答案】B【解析】堆排序是一種選擇排序的算法，它從建堆開頭：首先將要排序的全部關(guān)鍵碼放到一棵完全二叉樹的各個結(jié)點中，然后，從i=[n/2]的結(jié)點Ki開頭，逐步把以K[n/2], K[n/2]-l,K[n/2]-2,……為根的子樹排成堆，直到以K1為根的樹排成堆，就完成了建堆過程。此題中，n=16,i=[16/2]=8,8個結(jié)點開頭，建堆完成后如以以下圖所示：關(guān)鍵碼值B302章程序設(shè)計根底考綱分析程序設(shè)計方法與風(fēng)格。構(gòu)造化程序設(shè)計。面對對象的程序設(shè)計方法，對彖，方法，屬性及繼承與多態(tài)性?？键c精講程序設(shè)計方法與風(fēng)格1段。2代碼便于維護，程序設(shè)計風(fēng)格總體強調(diào)簡明清楚，易讀易懂，程序必需是可理解的，總體遵循“清楚第一，效率其次”的原則。3良好的程序設(shè)計風(fēng)格應(yīng)考慮的因素〔1〕源程序文檔化能的理解。②程序注釋明、主要算法、接口說明、程序位置、開發(fā)簡歷、程序設(shè)計者、復(fù)審者、復(fù)審日期、修改日期等。功能性注釋嵌在源程序體之屮，主要描述其后的語句或程序做什么。③視覺組織在程序中利用空格、空行、縮進等技巧可以使層次清楚，便于閱讀。數(shù)據(jù)說明的方法為使程序中的數(shù)據(jù)說明更易于理解和維護，應(yīng)留意以下幾點：①數(shù)據(jù)說明的次序標(biāo)準(zhǔn)化數(shù)據(jù)說明次序固定，可以使數(shù)據(jù)的屬性簡潔查找，也有利于測試、排錯和維護。字母挨次排序為好。③使用注釋來說明簡潔數(shù)據(jù)的構(gòu)造。語句的構(gòu)造程序應(yīng)當(dāng)簡潔易懂，語句構(gòu)造應(yīng)當(dāng)簡潔直接，不為提高效率而把語句簡潔化。①在一行內(nèi)只寫一條語句；②程序編寫應(yīng)優(yōu)先考慮清楚性；③除非對效率有特別要求，程序編寫要做到清楚第一，效率其次；④首先要保證程序正確，然后才要求提高速度；⑤避開使用臨時變量而使程序的可讀性下降；⑥避開不必要的轉(zhuǎn)移；⑦盡可能使用庫函數(shù)；⑧避開承受簡潔的條件語句；⑨盡量削減使用“否認”條件的條件語句；⑩數(shù)據(jù)構(gòu)造要有利于程序的簡化；團要模塊化，使模塊功能盡可能單一化；團利用信息隱蔽，確保每一個模塊的獨立性；團從數(shù)據(jù)動身去構(gòu)造程序；團不要修補不好的程序，要重編寫；輸入和輸出輸入輸出的方式和格式應(yīng)當(dāng)盡量便利用戶使用，在設(shè)計和編稈時應(yīng)遵循以下原則：①對全部的輸入數(shù)據(jù)都要檢驗數(shù)據(jù)的合法性；②檢查輸入項的各種重要組合的合理性；③輸入格式要簡潔，以使得輸入的步驟和操作盡可能簡潔；④輸入數(shù)據(jù)吋，應(yīng)允許使用自由格式；⑤應(yīng)允許缺省值；⑥輸入一批數(shù)據(jù)時，最好使用輸入完畢標(biāo)志；/輸入完畢吋，應(yīng)在屏幕上給出狀態(tài)信息；計輸出報表格式。構(gòu)造化程序設(shè)計1構(gòu)造化程序設(shè)計的原則構(gòu)造化程序設(shè)計方法的主要原則可以概括為自頂向下，逐步求精，模塊化，限制使用goto語句。使問題具體化。細化。限制使用goto語句GOTO語句確實有害，應(yīng)盡量避開；②完全避開使用GOTOGOTO③爭論的焦點不應(yīng)當(dāng)放在是否取消GOTO高程序清楚性為目標(biāo)的構(gòu)造化方法。【真題演練】以下選項中不屬于構(gòu)造化程序設(shè)計原則的是〔 〕。［2023年9月真題］可封裝自頂向下D.逐步求精【答案】Agoto語句?？煞庋b是面對對象的設(shè)計思想。2構(gòu)造化程序的根本構(gòu)造與特點根本構(gòu)造句一條語句地執(zhí)行程序。〔分支構(gòu)造〕選擇構(gòu)造包括簡潔懸著多分枝選擇，可依據(jù)設(shè)定條件，推斷應(yīng)中選擇哪一個分支來執(zhí)行相應(yīng)的語句序列。序行。a.當(dāng)型循環(huán)構(gòu)造：先推斷后執(zhí)行循環(huán)體；b.直到型循環(huán)構(gòu)造：先執(zhí)行循環(huán)體后推斷。構(gòu)造化程序設(shè)計方法的優(yōu)點①程序易于理解、使用和維護，便于把握、降低程序的簡潔性，可理解性好；②提高了編程工作的效率，降低了軟件開發(fā)本錢?！菊骖}演練】構(gòu)造化程序包括的根本把握構(gòu)造是〔 〕。［2023年3月真題］主程序與子程序選擇構(gòu)造、循環(huán)構(gòu)造與層次構(gòu)造挨次構(gòu)造、選擇構(gòu)造與循環(huán)構(gòu)造輸入、處理、輸出【答案】C把握構(gòu)造；。輸入、處理、輸出是計算機的組成規(guī)律構(gòu)造。3構(gòu)造化程序設(shè)計原則和方法的應(yīng)用在構(gòu)造化程序設(shè)計中應(yīng)把握以下要素：使用程序設(shè)計-語言中的挨次、選擇、循環(huán)等有限的把握構(gòu)造表示程序的把握規(guī)律；選用的把握構(gòu)造只準(zhǔn)許有一個入口和一個出口；程序語句組成簡潔識別的塊，每塊只有一個入口和一個出口；簡潔構(gòu)造應(yīng)當(dāng)用嵌套的根本把握構(gòu)造進展組合嵌套來實現(xiàn)；GOTO語句的使用。其意思是指：①用一個非構(gòu)造化的程序設(shè)計語言去實現(xiàn)一個構(gòu)造化的構(gòu)造；GOTO語句會使功能模糊；③在某種可以改善而不是損害程序可讀性的狀況下。23面對對象的程序設(shè)計1關(guān)于面對對象方法面對對象的本質(zhì)Z間的關(guān)系能夠照實地反映問題域屮固有事物及其關(guān)系。面對對象的主要優(yōu)點遞信息相互聯(lián)系，以模擬過程中都應(yīng)用領(lǐng)域的概念去思考。系統(tǒng)的功能需求變化時不會引起軟件構(gòu)造的整體變化，僅需要做一些局部性的修改。③可重用性好的內(nèi)部實現(xiàn)與外界隔離，具有較強的獨立性。重復(fù)使用一個對象的兩種方法：第一，創(chuàng)立該類的實例，直接使用它；其次，從它派生出一個滿足當(dāng)前需要的類。品來處理，這就不僅降低了開發(fā)的技術(shù)難度，而且也使得對開發(fā)工作的治理變得簡潔。面對對象設(shè)計軟件可維護性好的主要表現(xiàn)局部做修改，簡潔實現(xiàn)。它類，特有的繼承機制使得對開發(fā)的軟件的修改和擴大比較簡潔實現(xiàn)。件系統(tǒng)的構(gòu)造與問題空間的構(gòu)造根本一生出一些類來實現(xiàn)。很強的模塊，因此軟件的測試和調(diào)試就很簡潔實現(xiàn)。【真題演練】面對對象方法屮，實現(xiàn)對象的數(shù)據(jù)和操作結(jié)合予統(tǒng)一體中的是〔 〕。［2023年9月真題］結(jié)合封裝隱蔽抽象【答案】B【解析】對象的根本特點包括：①標(biāo)識唯一性；②分類性；③多態(tài)性；④封裝性；⑤模塊獨立性好。其中封 是指隱蔽對象的屬性和實現(xiàn)細節(jié)，將數(shù)據(jù)和操作統(tǒng)一，僅對外供給訪問方式。2對象可以作為對象。由一組表示英靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。③對象的屬性和操作a.屬性屬性即對象包含的信息，在設(shè)計對象時確定，一般只能通過執(zhí)行對象的操作來轉(zhuǎn)變。b.操作的結(jié)果，全部的操作過程都封裝在對象中。④對象具有的特點：標(biāo)識唯一性對象是可區(qū)分的，且這種區(qū)分是通過對象的內(nèi)在本質(zhì)，而不是通過描述來區(qū)分。分類性可以將具有一樣屬性和操作的對象抽象成類。C. 多態(tài)性同一個操作可以是不同對彖的行為。d.封裝性從外面只能看到對象的外部特征，只知道數(shù)值的収值范圍和可以對數(shù)據(jù)施加的操作，無法知道數(shù)據(jù)的具體構(gòu)造及實現(xiàn)操作的算法。對象的處理力氣對外不行見，從外面不能直接使用對象的處理力氣，無法修改其內(nèi)部狀態(tài),其內(nèi)部狀態(tài)只能由其自身轉(zhuǎn)變。C. 而且對彖是以數(shù)據(jù)為中心的，操作圍繞對其數(shù)據(jù)所需做的處理來設(shè)置，沒有無關(guān)的操作。從模塊的獨立性考慮，對象內(nèi)部各種元素彼此結(jié)合得很嚴密，內(nèi)聚性強。類和實例應(yīng)類的一個實例。然是指一個具體的對象。③類是關(guān)于對象性質(zhì)的描述，它同對象一樣，包括一組數(shù)據(jù)屬性和在數(shù)據(jù)上的一組合法操作。消息Z數(shù)據(jù)流和把握流。獨立打算承受什么樣的方式完成所需的處理。式一樣的消息可以有不同的解釋，作出不同反響。a.接收消息的對象的名稱；b.消息標(biāo)識符〔也稱為消息名〕；c.零個或多個參數(shù)。繼承類來引用。③繼承的分類a.單繼承一個類只允許有一個父類，類等級為樹狀構(gòu)造。b.多繼承④繼承性的優(yōu)點軟件修改維護。再派生出的類以實現(xiàn)所需要的功能。多態(tài)性種現(xiàn)象。象也可以發(fā)送給子類對彖。擴大性?！菊骖}演練】〔全都性C.多態(tài)D.標(biāo)識唯一性【答案】A

〕。［20239月真題］【解析】對彖的特點包括：①標(biāo)識唯一性；②分類性；③多態(tài)性；④封裝性；⑤模塊獨立性好。2.月真題］對象唯一性對象無關(guān)性類的單一性類的依靠性【答案】A

下面對類一對象主要特征描述正確的選項是〔〕。［20233【解析】面對對彖設(shè)計是建立在“對彖”概念上的方法學(xué)，類是具有共同屬性、共同方法的對象的集合，是關(guān)于對象的抽象描述，反映屬于該對象類型的全部對彖的性質(zhì)。對象具有的性質(zhì)，類也具有，即類也具備對彖所具有的特征，如標(biāo)識唯一性、分類性、多態(tài)性、封裝性和模塊獨立性好。3. 面對對象方法中，繼承是指〔 〕。［2023年3月真題］A.一組對象所具有的相像性質(zhì)B.一個對象具有另一個對象的性質(zhì)C.各對象之間的共同性質(zhì)D.類之間共享屬性和操作的機制【答案】D強化習(xí)題以下各選項中，不屬于序言性注釋的是〔〕。程序標(biāo)題B.程序設(shè)計者C.主要算D.數(shù)據(jù)狀態(tài)【答案】D法、接口說明、程序位置、開發(fā)簡歷、程序設(shè)計者、復(fù)審者、復(fù)審日期及修改日期等；②功能性注釋，一般嵌在源程序體之中，用于描述其后的語句或程序的主要功能。以下表達屮，不符合良好程序設(shè)計風(fēng)格要求的是〔 〕。程序的效率第一，清楚其次程序的可讀性好C.程序中要有必要的注釋D.輸入數(shù)據(jù)前要有提示信息【答案】A和維護，所以程序要具有良好的可讀性，語句構(gòu)造應(yīng)當(dāng)簡潔直接，這有利于程序的開發(fā)與維護。信息隱蔽的概念與下述哪一種概念直接相關(guān)〔 〕。軟件構(gòu)造定義模塊獨立性模塊類型劃分模塊耦合度【答案】B【解析】信息隱蔽是指，所設(shè)計的模塊使得其所包含的信息〔過程和數(shù)據(jù)〕訪問的。模塊獨立性的概念是抽象、模塊化、信息隱蔽和局部化的直接結(jié)杲。利用信息隱蔽，可以確保每一個模塊的獨立性。構(gòu)造化程序所要求的根本構(gòu)造不包括〔 〕。挨次構(gòu)造GOTOC.選擇〔分支〕構(gòu)造D. 重復(fù)〔循環(huán)〕構(gòu)造【答案】B算法都可以通過：①挨次構(gòu)造；②選擇構(gòu)造；③循環(huán)構(gòu)造來實現(xiàn)。構(gòu)造化程序設(shè)計主要強調(diào)的是〔 〕。A.程序的規(guī)模B.程序的效C.程序設(shè)計語言的先進性D. 程序易讀性【答案】D【解析】遵循構(gòu)造化程序的設(shè)計原則，按構(gòu)造化程序設(shè)計方法設(shè)計出的程序具有明顯的優(yōu)點：①程序易于理解、使用和維護；②提高了編程工作的效率，降低了軟件開發(fā)本錢。在構(gòu)造化程序設(shè)計中，模塊劃分的原則是〔 〕。A.各模塊應(yīng)包括盡量多的功能B.各模塊的規(guī)模應(yīng)盡量大c.Z間的聯(lián)系應(yīng)盡量嚴密D.模塊內(nèi)具有高內(nèi)聚度、模塊間具有低耦合度【答案】D【解析】模塊獨立性最大原則是模塊劃分的原則之一，高內(nèi)聚低耦合是優(yōu)秀軟件設(shè)計應(yīng)當(dāng)遵循的規(guī)章，內(nèi)聚度是一個模塊內(nèi)部各個元素間彼此結(jié)合的嚴密程序的度量，耦合度是模塊間相互連接的嚴密程度的度量。以下特征中不是面對對彖方法的主要特征的是〔 〕。B.標(biāo)識唯一性C.封裝【答案】D【解析】面對對彖設(shè)計是建立在“對彖”概念上的方法學(xué)，對彖是面對對彖語言中類的實體，其特點包括：①標(biāo)識唯一性，對象可區(qū)分；②分類性，可以將具有一樣屬性和操作的對象抽象成類；③多態(tài)性，同一個操作對于不同対象表現(xiàn)不同的行為；④封裝性，屏蔽數(shù)據(jù)的具體構(gòu)造以及操作的算法；⑤模塊獨立性好，對象內(nèi)部各種元素結(jié)合嚴密，內(nèi)聚性強。以下不屬于對彖的根本特征的是〔 〕。繼承性封裝性分類性多態(tài)性【答案】A【解析】對象是面對對象語言中類的實體，其特點包括：①標(biāo)識唯一性，對象可區(qū)分；②分類性，可以將具有一樣屬性和操作的對象抽象成類；③多態(tài)性，同一個操作對于不同對象表現(xiàn)不同的行為；④封裝性，屏蔽數(shù)據(jù)的具體構(gòu)造以及操作的算法；⑤模塊獨立性好，對象內(nèi)部各種元素結(jié)合嚴密，內(nèi)聚性強。以下關(guān)于類、對象、屬性和方法的表達中，錯誤的選項是〔 〕。A.類是對一類具有一樣的屬性和方法對象的描述B.屬性用于描述對象的狀態(tài)C. 方法用于表示對象的行為D.基于同一個類產(chǎn)生的兩個對象不行以分別設(shè)置自己的屬性值【答案】DD誤，基于同一個類產(chǎn)生的兩個對象屬性一樣，但是屬性值可以由對象自己設(shè)定。定義無符號整數(shù)類為UInt,下面可以作為類UInt實例化值的是〔 〕。A. 369B. 369C. 0.369D. 整數(shù)集合{1,2,3,4,5}【答案】B【解析】無符號整數(shù)類只能是正整數(shù)。D項的整數(shù)集合需要用數(shù)組存儲。3章軟件工程根底考綱分析軟件工程根本概念，軟件生命周期概念，軟件工具與軟件開發(fā)環(huán)境。構(gòu)造化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說明書。構(gòu)造化設(shè)計方法，總體設(shè)計與具體設(shè)計。程序的調(diào)試，靜態(tài)調(diào)試與動態(tài)調(diào)試?？键c精講軟件工程根本概念1軟件定義與軟件特點軟件的定義計算機軟件〔Software〕是計算機系統(tǒng)屮與硬件相互依存的另一局部，是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。軟件的組成①機器可以執(zhí)行的程序和數(shù)據(jù)；②機器不行執(zhí)行的，與軟件開發(fā)、運行、維護、使用等有關(guān)的文檔。軟件的特點通過觀看、分析、思考、推斷才能了解其功能和特性。開發(fā)方而。等變化，必要時要做出修改。修改可能會引入錯誤，導(dǎo)致軟件失效率上升，軟件退化。④軟件的開發(fā)、運行對計算機系統(tǒng)有很大依靠性，導(dǎo)致軟件消滅移植問題。險大。甚至涉及人們的觀念和心理，軟件學(xué)問產(chǎn)權(quán)及法律等問題。軟件的分類軟件依據(jù)應(yīng)用功能劃分，XI分為：軟件，實時處理軟件等。操作系統(tǒng)，編譯程序，匯編程序，網(wǎng)絡(luò)軟件，數(shù)據(jù)庫治理系統(tǒng)等③支撐軟件支撐軟件是介于系統(tǒng)軟件和應(yīng)用軟件Z間，幫助用戶開發(fā)軟件的工具性軟件，包括關(guān)心和支持開發(fā)和維護應(yīng)用軟件的工具軟件。常用的支撐軟件：需求分析工具軟件，設(shè)計工具軟件，編碼工具軟件，測試工具軟件等?！菊骖}演練】1.計算機軟件包括〔算法和數(shù)據(jù)程序和數(shù)據(jù)C 程序和文檔

〕。［20239月真題］D. 程序、數(shù)據(jù)及相關(guān)文檔【答案】D【解析】計算機軟件包括：①機器可執(zhí)行的程序和數(shù)據(jù)；②機器不行執(zhí)行的，與軟件開發(fā)、運行、維護、使用等有關(guān)的文檔。下而對軟件特點描述錯課的是〔〕。［20233月真題］A.軟件沒有明顯的制作過程B.軟件是一種規(guī)律實體，不是物理實體，具有抽象性C.軟件的開發(fā)、運行對計算機系統(tǒng)具有依靠性D.軟件在使用中存在磨損、老化問題【答案】D【解析】軟件的特點有：①具有抽象性，是規(guī)律實體；②沒有明顯的制作過程；③在使用期間不存在磨損、老化問題；④對硬件和環(huán)境具有依靠性；⑤簡潔性高，本錢昂貴；⑥開發(fā)涉及諸多的社會因素。下而屬于系統(tǒng)軟件的是〔 〕。［2023年3月真題］財務(wù)治理系統(tǒng)數(shù)據(jù)庫治理系統(tǒng)WordD.殺毒軟件【答案】B【解析】按不同的功能，計算機軟件可分為：①應(yīng)用軟件；②系統(tǒng)軟件；③支撐軟件，即工具軟件。其中，系統(tǒng)某種特定的用途而被開發(fā)。2〔1〕軟件危機問題。b.超出預(yù)算，開發(fā)周期大大超過規(guī)定日期的狀況常常發(fā)生；c.軟件質(zhì)量難以保證；d.軟件不行維護或維護程度格外低；e.軟件的成本不斷提高；f.軟件開發(fā)生產(chǎn)率的提高趕不上硬件的進展和應(yīng)用需求的增長。a. 異以及軟件和其他工業(yè)產(chǎn)品的不同?！?〕軟件工稈IEEE給出一個綜合的定義是：將系統(tǒng)化的、標(biāo)準(zhǔn)的、可度量的方法應(yīng)用于軟件的開發(fā)、運行和維護的過程，馬上工程化應(yīng)用于軟件中。a.方法：完成軟件工程工程的技術(shù)手段。b.工具：支持軟件的開發(fā)、治理、文檔生成。過程：支持軟件開發(fā)的各個壞節(jié)的把握、治理。③核心把軟件產(chǎn)品當(dāng)作工程產(chǎn)品來處理，把需求打算、可行性爭論、工程審核、質(zhì)量監(jiān)視等工程化的概念引入到軟件生產(chǎn)當(dāng)中，以期到達工程工程的三個根本要素：進度、經(jīng)費和質(zhì)量的目標(biāo)。同吋，也留意爭論不同于其他工業(yè)產(chǎn)品生產(chǎn)的一些獨特特性，并針對軟件的特點提出了很多有別于一般工業(yè)工程技術(shù)的一些技術(shù)方法。代表性的有構(gòu)造化的方法、面對對彖方法和軟件開發(fā)模型及軟件開發(fā)過程等?！菊骖}演練】方法、工具和過程建模、方法和工具建模、方法和過程定義、方法和過程【答案】A

〕。［20233月真題］【解析】應(yīng)用于計算機軟件的定義、開發(fā)和維護的一整套方法、工具、文檔、實踐標(biāo)準(zhǔn)和工序被稱為軟件工程，它包含的三要素是：①方法；②工具；③過程。3軟件過程ISO9000定義：軟件過程是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動。a.D〔Do〕設(shè)計與實現(xiàn)。生產(chǎn)滿足規(guī)格說明的軟件；第三，C〔Cheek〕——軟件確認。確認軟件能夠滿足客戶提出的要求；第四，A〔Action〕b.使用適當(dāng)?shù)馁Y源，為開發(fā)軟件進展的一組開發(fā)活動，在過程完畢時將輸入〔用戶要求〕〔軟件產(chǎn)品〕。軟件生命周期①定義軟件生命周期是指軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停頓使用退役的過程。②階段的目標(biāo)，確定工程可行性所定義的軟件，總體設(shè)計和具體設(shè)計又稱為系統(tǒng)設(shè)計，編碼和測試又稱為系統(tǒng)實現(xiàn)。要，準(zhǔn)時改正軟件在使用中發(fā)生的錯誤，修改軟件以適應(yīng)不同的使用環(huán)境。③各階段的根本任務(wù)方面的可能方案，制定完成開發(fā)任務(wù)的實施打算。審。c.功能的分具體設(shè)計說明書和測試打算初稿，提交評審。編碼編碼是把軟件設(shè)計轉(zhuǎn)換成計算機可以承受的程序代碼。即完成源程序的編碼，編寫用戶手冊、操作手冊等面對用戶的文檔，編寫單元測試打算。軟件測試在設(shè)計測試用例的根底上，檢驗軟件的各個組成局部。編寫測試分析報告。f.運行和維護將已交付的軟件投入運行，并在運行使用屮不斷地維護，依據(jù)提出的需求進展必要而且可能的擴大和刪改。4軟件工程的目標(biāo)重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。a.付出較低的開發(fā)本錢；b.到達要求的軟件功能；c.取得較好的軟件性能；d.開發(fā)的軟件易于移植；e.需要較低的維護費用；f.能按時完成開發(fā)，準(zhǔn)時交付使用。③軟件工程的理論和技術(shù)性爭論的內(nèi)容：是軟件開發(fā)方法學(xué)。其次，軟件開發(fā)方法學(xué)是依據(jù)不同的軟件類型，按不同的觀點和原則，對軟件開發(fā)屮應(yīng)遵循的策略、原則、步驟和必需產(chǎn)牛的文檔資料都作出規(guī)定，從而使軟件的開發(fā)能夠進入標(biāo)準(zhǔn)化和工程化的階段，以抑制早期的手工方法生產(chǎn)屮的任憑性和非標(biāo)準(zhǔn)性做法。軟件工程治理第一，軟件工程治理包括：軟件治理學(xué)、軟件工程經(jīng)濟學(xué)、軟件心理學(xué)等內(nèi)容。軟件工程治理是軟件按工程化生產(chǎn)吋的重要環(huán)節(jié)，它要求依據(jù)預(yù)先制定的打算、進度和預(yù)算執(zhí)行，以實現(xiàn)預(yù)期的經(jīng)濟效益和社會效益。其次，軟件治理學(xué)包括人員組織、進度安排、質(zhì)量保證、配置治理、工程打算等。第三，軟件工程經(jīng)濟學(xué)是爭論軟件開發(fā)中本錢的估算、本錢效益分析的方法和技術(shù)，用經(jīng)濟學(xué)的根本原理來爭論軟件工程開發(fā)中的經(jīng)濟效益問題。第四，軟件心理學(xué)是軟件工程領(lǐng)域具有挑戰(zhàn)性的一個全的爭論視角，它是從個體心理、人類行為、組織行為和企業(yè)文化等角度來爭論軟件治理和軟件工程的。軟件工程的根本原則。開發(fā)過程的簡潔性。盡量簡潔。試和重用，過小會導(dǎo)致系統(tǒng)表示過于簡潔，不利于把握簡潔性。的內(nèi)聚性，有利于把握解的簡潔性。軟件開發(fā)過程中全部概念的表達應(yīng)是確定的、無歧義且標(biāo)準(zhǔn)的。這有助于人與人的交互不會產(chǎn)生誤會和遺漏，以保證整個開發(fā)工作的協(xié)調(diào)全都。持一致，系統(tǒng)規(guī)格說明與系統(tǒng)行為應(yīng)保持全都。功能。以確保系統(tǒng)的正確性?？键c5軟件開發(fā)工具與軟件開發(fā)環(huán)境程方法供給了自動依據(jù)確定的方法或模式組合起來，支持軟件生命周期內(nèi)的各個階段和各項任務(wù)的完成。構(gòu)造化分析方法考點1需求分析與需求分析方法需求分析①需求的定義1997年IEEE在《軟件工程標(biāo)準(zhǔn)詞匯表》中對需求定義如下：a.用戶解決問題或到達目標(biāo)所需的條件或權(quán)能；b.系統(tǒng)或系統(tǒng)部件要滿足合同、標(biāo)準(zhǔn)、標(biāo)準(zhǔn)或其他正式規(guī)定文檔所需具有的條件或權(quán)能；c.一種反映ab所描述的條件或權(quán)能的文檔說明。該定義從兩方面闡述了需求的含義：一是從用戶角度所要求的系統(tǒng)應(yīng)具有的功能，是系統(tǒng)的外部行為；二是從系統(tǒng)開發(fā)者角度所要求的系統(tǒng)應(yīng)具有的功能，是系統(tǒng)的內(nèi)部特性。概括為四個方面：a.需求獵取第一，目的是確定對目標(biāo)系統(tǒng)的各方面需求。涉及的主要任務(wù)是建立獵取用戶需求的方法框架，并支持和監(jiān)控需求獵取的過程。其次，涉及的關(guān)鍵問題有：對問題空間的理解；人與人之間的通信；不斷變化的需求。第三，一般功能性與非功能性需求包括系統(tǒng)功能、物理環(huán)境、用戶界面、用戶因素、資源、安全性、質(zhì)量保證及其他約束。b.需求分析對獵取的需求進展分析和綜合，最終給出系統(tǒng)的解決方案和目標(biāo)系統(tǒng)的規(guī)律模型。c.編寫需求規(guī)格說明書需求規(guī)格說明書作為需求分析的階段成果，可以為用戶、分析人員和設(shè)計人員之間的溝通供給便利，可以直接支持目標(biāo)軟件系統(tǒng)確實認，又可以作為把握軟件開發(fā)進程的依據(jù)。d. 和有效性。需求分析方法①構(gòu)造化分析方法面對數(shù)據(jù)流的構(gòu)造化分析方法；面對數(shù)據(jù)構(gòu)造的Jackson方法；面對數(shù)據(jù)構(gòu)造的構(gòu)造化數(shù)據(jù)系統(tǒng)開發(fā)方法?！菊骖}演練】下面描述屮不屬于軟件需求分析階段任務(wù)的是〔 〕。［2023年9月真題］撰寫軟件需求規(guī)格說明書軟件的總體構(gòu)造設(shè)計C.軟件的D.軟件的需求評審【答案】B4個方面：需求獲収、需求分析、編寫需求規(guī)格說明書和需求評審。軟件的依據(jù)。在軟件開發(fā)中，需求分析階段產(chǎn)生的主要文檔是〔 〕。［2023年3月真題］可行性分析報告軟件需求規(guī)格說明書概要設(shè)計說明書集成測試打算【答案】B確認測試和驗收的依據(jù)。A項，可行性分析報告產(chǎn)生于可行性分析階段；CD項，集成測試打算產(chǎn)生于概要設(shè)計階段。2關(guān)于構(gòu)造化分析方法①定義構(gòu)造化分析就是使用數(shù)據(jù)流圖〔DFD〕、數(shù)據(jù)字典〔DD〕立_種的、稱為構(gòu)造化規(guī)格說明的目標(biāo)文檔。統(tǒng)的規(guī)律模型。a.通過對用戶的調(diào)查，以軟件的需求為線索，獲得當(dāng)前系統(tǒng)的具體模型；b.去掉具體模型c.根據(jù)計算機的特點分析當(dāng)前系統(tǒng)與目標(biāo)系統(tǒng)的差異，建立目標(biāo)系統(tǒng)的規(guī)律模型；d.完善目標(biāo)系統(tǒng)并補充細節(jié)，寫出目標(biāo)系統(tǒng)的軟件需求規(guī)格說明；e.評審直到確認完全符合用戶對軟件的需求。構(gòu)造化分析的常用工具①數(shù)據(jù)流圖定義：數(shù)據(jù)流圖是描述數(shù)據(jù)處理過程的工具，是需求理解的規(guī)律模型的圖形表示，它直接支持系統(tǒng)的功能建模。數(shù)據(jù)流圖中的主要圖形元素與說明第一，o加工〔轉(zhuǎn)換〕輸入數(shù)據(jù)經(jīng)加工變換產(chǎn)生輸出。第二，一數(shù)據(jù)流沿箭頭方向傳送數(shù)據(jù)的通道，i〔數(shù)據(jù)源〕表示處理過程中存放各種數(shù)第四， I數(shù)據(jù)的源點和終點表示系統(tǒng)和環(huán)境的接口，屬系統(tǒng)之外的實體。C. 建立數(shù)據(jù)流圖的步驟：第一，由外向里：先畫系統(tǒng)的輸入輸出，然后畫系統(tǒng)的內(nèi)部；其次，自頂向下：挨次完成頂層、中問層、底層數(shù)據(jù)流圖；第三，逐層分解。d. 入又有輸出；其次，數(shù)據(jù)存儲之間不應(yīng)當(dāng)有數(shù)據(jù)流；沒有在處理中使用以產(chǎn)生輸出；數(shù)據(jù)存儲〔文件〕應(yīng)被數(shù)據(jù)流圖中的處理讀和寫。第四，父圖、子圖關(guān)系與平衡規(guī)章DFD之間具有父、子關(guān)系，子圖代表了父圖中某個加工的具體描述，父圖表示了子圖間的接口。子圖個的、嚴格模型嚴密地結(jié)合在一起，與各模型的圖形表示協(xié)作，能清楚地表達數(shù)據(jù)處理的要求/如何使用、內(nèi)容描述、補充信息等。Z間的附屬關(guān)系、并列關(guān)系、選擇關(guān)系，依據(jù)它們構(gòu)造判定樹。組成：b.條件項：列出了各種可能的條件組合；c.根本動作項：列出了全部的操作；動作項：列出在對應(yīng)的條件組合下所選的操作。【真題演練】1.

數(shù)據(jù)流圖中帶有箭頭的線段表示的是〔〕。［20233月真題］把握流大事驅(qū)動模塊調(diào)用數(shù)據(jù)流【答案】D【解析】數(shù)據(jù)流圖中帶箭頭的線段表示的是數(shù)據(jù)流，即沿箭頭方向傳送數(shù)據(jù)的逋道，一般在旁邊標(biāo)注數(shù)據(jù)流名。2.［20233月真題］N-S圖B?DFD圖C?PADD.程序流程圖【答案】B

在軟件開發(fā)中，需求分析階段可以使用的工具是〔?！窘馕觥啃枨蠓治鲭A段使用的工具主要有：①數(shù)據(jù)流圖DFD；②數(shù)據(jù)字典DD；③判定樹；④判定表。考點3軟件需求規(guī)格說明書軟件需求規(guī)格說明書的作用①便于用戶、開發(fā)人員進展理解和溝通；②反映出用戶問題的構(gòu)造，可以作為軟件開發(fā)工作的根底和依據(jù)；③作為確認測試和驗收的依據(jù)；④為本錢估算和編制打算進度供給根底；⑤軟件不斷改進的根底。軟件需求規(guī)格說明書的內(nèi)容軟件需求規(guī)格說明重點描述軟件的冃標(biāo)，軟件的功能需求、性能需求、外部接口、屬性及約束條件等。①功能需求軟件需求規(guī)格說明，給出軟件要執(zhí)行什么功能的詳盡描述。②性能需求定量地描述軟件系統(tǒng)應(yīng)滿足的具體性能需求，即各種軟件功能的速度、響應(yīng)時間、恢復(fù)時間。件進展交互。④屬性與軟件有關(guān)的質(zhì)量屬性，如正確性、可用性、牢靠性、安全性、可維護性等。壞境等方面的要求。軟件需求規(guī)格說明的特點軟件需求規(guī)格說明是確保軟件質(zhì)量的有力措施，衡量軟件需求規(guī)格說明書質(zhì)量好壞的標(biāo)準(zhǔn)、標(biāo)準(zhǔn)的優(yōu)先級及標(biāo)準(zhǔn)的內(nèi)涵是：①正確性：表達待開發(fā)系統(tǒng)的真實要求。②無歧義性：對每一個需求只有一種解釋，其陳述具有唯一性。③完整性：包括全部有意義的需求，功能的、性能的、設(shè)計的、約束的，屬性或外部接口等方面的需求。④可驗證性：描述的每一個需求都是可以驗證的，即存在有限代價的有效過程驗證確認。⑤全都性：各個需求的描述不沖突。⑥可理解性：需求說明必需簡明易懂，盡量少包含計算機的概念和術(shù)語，以便用戶和軟件人員都能承受它。⑦可修改性：SRS的構(gòu)造風(fēng)格在需求有必要轉(zhuǎn)變時是易于實現(xiàn)的。⑧可追蹤性：每一個需求的來源、流向是清楚的，當(dāng)產(chǎn)生和轉(zhuǎn)變文件編制時，可以便利地引證每一個需求。構(gòu)造化設(shè)計方法考點1軟件設(shè)計的根本概念軟件設(shè)計的根底型。②軟件設(shè)計的重要性和地位軟件開發(fā)階段占據(jù)軟件工程開發(fā)總本錢絕大局部，是在軟件開發(fā)中形成質(zhì)量的關(guān)鍵環(huán)節(jié)；c.軟件設(shè)計作出的決策，最終影響軟件實現(xiàn)的成?。籨.設(shè)計是軟件工程和軟件維護的根底。a.b.數(shù)據(jù)設(shè)計：將分析時創(chuàng)立的模型轉(zhuǎn)化為數(shù)據(jù)構(gòu)造的定義；c.接口設(shè)計：描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)之間以及軟件與人之間如何通信；d.a.概要設(shè)計〔構(gòu)造設(shè)計〕將軟件需求轉(zhuǎn)化為軟件體系構(gòu)造、確定系統(tǒng)級接口、全局數(shù)據(jù)構(gòu)造或數(shù)據(jù)庫模式。b.具體軟件設(shè)計的根本原理軟件設(shè)計的根本原理和有關(guān)概念可概括為：解都是對軟件求解的上一層抽象的一次精化。問題，在軟件設(shè)計中一般是對模塊的劃分，將軟件系統(tǒng)模塊劃分后形成的構(gòu)造是模塊的分層構(gòu)造?；侵赴岩恍╆P(guān)系親熱的軟件元素物理地放得彼此靠近，局部化有助于實現(xiàn)信息隱蔽。④模塊獨立性模塊獨立性是指軟件模塊的編寫和修改應(yīng)使其具有獨立功能，且與其他模塊的關(guān)聯(lián)盡可能少，模塊的獨立程度是評價設(shè)計好壞的重要度量標(biāo)準(zhǔn)；模塊獨立程度的兩個定性標(biāo)準(zhǔn)度量：第一，模塊間的耦合性對一個模塊內(nèi)部各個元素間彼此結(jié)合的嚴密程度的度量，內(nèi)聚性越高，模塊獨立性越強。構(gòu)