2022年全國(guó)計(jì)算機(jī)等級(jí)考試公共基礎(chǔ)知識(shí)總結(jié)及歷年真題及答案

1、全國(guó)運(yùn)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)學(xué)問(wèn)總 結(jié)第一章數(shù)據(jù)結(jié)構(gòu)與算法 算法 算法：是指解題方案的精確而完整的描述；算法不等于程序,也不等運(yùn)算機(jī)方法,程序的編制不行能優(yōu)于算法的設(shè)計(jì)；算法的基本特點(diǎn)：是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算次序的規(guī)章,每一個(gè)規(guī)章都是有效的,是明確的,此次序?qū)⒃谟邢薜拇螖?shù)下終止；特點(diǎn)包括：（1）可行性；（2）確定性,算法中每一步驟都必需有明確定義,不充許有模棱兩可的說(shuō)明,不答應(yīng) 有多義性；（3）有窮性,算法必需能在有限的時(shí)間內(nèi)做完,即能在執(zhí)行有限個(gè)步驟后終止,包括 合理的執(zhí)行時(shí)間的含義；（4）擁有足夠的情報(bào)；算法的基本要素：一是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作；二是算法的掌握結(jié)構(gòu)；指令系統(tǒng)：一個(gè)運(yùn)算機(jī)系

2、統(tǒng)能執(zhí)行的全部指令的集合；基本運(yùn)算和操作包括：算術(shù)運(yùn)算、規(guī)律運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)傳輸；算法的掌握結(jié)構(gòu)：次序結(jié)構(gòu)、挑選結(jié)構(gòu)、循環(huán)結(jié)構(gòu)；算法基本設(shè)計(jì)方法：列舉法、歸納法、遞推、遞歸、減斗遞推技術(shù)、回溯法；算法復(fù)雜度：算法時(shí)間復(fù)雜度和算法空間復(fù)雜度；算法時(shí)間復(fù)雜度是指執(zhí)行算法所需要的運(yùn)算工作量；算法空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間；數(shù)據(jù)結(jié)構(gòu)的基本基本概念 數(shù)據(jù)結(jié)構(gòu)爭(zhēng)論的三個(gè)方面：（1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的規(guī)律關(guān)系,即數(shù)據(jù)的規(guī)律結(jié)構(gòu)；（2）在對(duì)數(shù)據(jù)進(jìn)行處理時(shí),各數(shù)據(jù)元素在運(yùn)算機(jī)中的儲(chǔ)備關(guān)系,即數(shù)據(jù)的儲(chǔ)備結(jié)構(gòu)；（3）對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算；數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合；

3、數(shù)據(jù)的規(guī)律結(jié)構(gòu)包含：（1）表示數(shù)據(jù)元素的信息；（2）表示各數(shù)據(jù)元素之間的前后件關(guān)系；數(shù)據(jù)的儲(chǔ)備結(jié)構(gòu)有次序、鏈接、索引等；線性結(jié)構(gòu)條件：（1）有且只有一個(gè)根結(jié)點(diǎn)；（2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件,也最多有一個(gè)后件；非線性結(jié)構(gòu)：不滿意線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)；13 線性表及其次序儲(chǔ)備結(jié)構(gòu) 線性表由一組數(shù)據(jù)元素構(gòu)成,數(shù)據(jù)元素的位置只取決于自己的序號(hào),元素之間的相對(duì)位 置是線性的；在復(fù)雜線性表中, 由如干項(xiàng)數(shù)據(jù)元素組成的數(shù)據(jù)元素稱(chēng)為記錄,而由多個(gè)記錄構(gòu)成的線 性表又稱(chēng)為文件；非空線性表的結(jié)構(gòu)特點(diǎn)：（1）且只有一個(gè)根結(jié)點(diǎn) a1,它無(wú)前件；an,它無(wú)后件；（2）有且只有一個(gè)終端結(jié)點(diǎn)（3）除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外,

4、其他全部結(jié)點(diǎn)有且只有一個(gè)前件,也有且只有一個(gè)后件；結(jié)點(diǎn)個(gè)數(shù) n 稱(chēng)為線性表的長(zhǎng)度,當(dāng) n=0 時(shí),稱(chēng)為空表；線性表的次序儲(chǔ)備結(jié)構(gòu)具有以下兩個(gè)基本特點(diǎn)：（1）線性表中全部元素的所占的儲(chǔ)備空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在儲(chǔ)備空間中是按規(guī)律次序依次存放的；ai 的儲(chǔ)備地址為： ADRai=ADRa1+i-1k,ADRa1為第一個(gè)元素的地址,k 代表每個(gè)元素占的字節(jié)數(shù)；次序表的運(yùn)算：插入、刪除；（詳見(jiàn) 14-16 頁(yè)）14 棧和隊(duì)列答應(yīng)插入與刪除的一端稱(chēng)為棧頂,不答應(yīng)插棧是限定在一端進(jìn)行插入與刪除的線性表,入與刪除的另一端稱(chēng)為棧底；棧依據(jù)“ 先進(jìn)后出” （FILO）或“ 后進(jìn)先出” （LIFO

5、）組織數(shù)據(jù),棧具有記憶作用；用top 表示棧頂位置,用 bottom 表示棧底；棧的基本運(yùn)算： （1）插入元素稱(chēng)為入棧運(yùn)算； （2）刪除元素稱(chēng)為退棧運(yùn)算； （ 3）讀棧頂元素是將棧頂元素賦給一個(gè)指定的變量,此時(shí)指針無(wú)變化；隊(duì)列是指答應(yīng)在一端（隊(duì)尾）進(jìn)入插入,而在另一端（隊(duì)頭）進(jìn)行刪除的線性表；Rear指針指向隊(duì)尾,front 指針指向隊(duì)頭；隊(duì)列是“ 先進(jìn)行出” （FIFO）或“ 后進(jìn)后出” （LILO）的線性表；隊(duì)列運(yùn)算包括（1）入隊(duì)運(yùn)算：從隊(duì)尾插入一個(gè)元素；（2）退隊(duì)運(yùn)算：從隊(duì)頭刪除一個(gè)元素；循環(huán)隊(duì)列： s=0 表示隊(duì)列空, s=1 且 front=rear表示隊(duì)列滿簡(jiǎn)稱(chēng)結(jié)點(diǎn)；15 線性鏈表

6、這種儲(chǔ)備單元稱(chēng)為儲(chǔ)備結(jié)點(diǎn),數(shù)據(jù)結(jié)構(gòu)中的每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)儲(chǔ)備單元,結(jié)點(diǎn)由兩部分組成： （1）用于儲(chǔ)備數(shù)據(jù)元素值,稱(chēng)為數(shù)據(jù)域；指針域,用于指向前一個(gè)或后一個(gè)結(jié)點(diǎn)；（2）用于存放指針,稱(chēng)為在鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)中,儲(chǔ)備數(shù)據(jù)結(jié)構(gòu)的儲(chǔ)備空間可以不連續(xù),各數(shù)據(jù)結(jié)點(diǎn)的儲(chǔ)備次序與數(shù)據(jù)元素之間的規(guī)律關(guān)系可以不一樣,而數(shù)據(jù)元素之間的規(guī)律關(guān)系是由指針域來(lái)確定的；鏈?zhǔn)絻?chǔ)備方式即可用于表示線性結(jié)構(gòu),也可用于表示非線性結(jié)構(gòu)；線性鏈表,HEAD稱(chēng)為頭指針, HEAD=NULL（或 0）稱(chēng)為空表, 假如是兩指針： 左指針（Llink）指向前件結(jié)點(diǎn),右指針（Rlink ）指向后件結(jié)點(diǎn)；線性鏈表的基本運(yùn)算：查找、插入、刪除；16 樹(shù)

7、與二叉樹(shù) 樹(shù)是一種簡(jiǎn)潔的非線性結(jié)構(gòu),全部元素之間具有明顯的層次特性；在樹(shù)結(jié)構(gòu)中,每一個(gè)結(jié)點(diǎn)只有一個(gè)前件,稱(chēng)為父結(jié)點(diǎn),沒(méi)有前件的結(jié)點(diǎn)只有一個(gè),稱(chēng)為樹(shù)的根結(jié)點(diǎn),簡(jiǎn)稱(chēng)樹(shù)的根；每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件,稱(chēng)為該結(jié)點(diǎn)的子結(jié)點(diǎn)；沒(méi)有后件的結(jié)點(diǎn)稱(chēng)為葉子結(jié)點(diǎn)；在樹(shù)結(jié)構(gòu)中, 一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱(chēng)為該結(jié)點(diǎn)的度,樹(shù)的度；樹(shù)的最大層次稱(chēng)為樹(shù)的深度；全部結(jié)點(diǎn)中最大的度稱(chēng)為二叉樹(shù)的特點(diǎn)： （1）非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)；（2）每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù),且分別稱(chēng)為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)；二叉樹(shù)的基本性質(zhì)：（1）在二叉樹(shù)的第 k 層上,最多有 2k- 1k 1 個(gè)結(jié)點(diǎn)；（2）深度為 m的二叉樹(shù)最多有 2m-1 個(gè)結(jié)點(diǎn)；

8、（3）度為 0 的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為 2 的結(jié)點(diǎn)多一個(gè)；（4）具有 n 個(gè)結(jié)點(diǎn)的二叉樹(shù), 其深度至少為 log2n+1, 其中 log2n 表示取 log2n 的整數(shù)部分；（5）具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2n+1；（6）設(shè)完全二叉樹(shù)共有n 個(gè)結(jié)點(diǎn)；假如從根結(jié)點(diǎn)開(kāi)頭,按層序（每一層從左到右）用自然數(shù) 1,2, .n 給結(jié)點(diǎn)進(jìn)行編號(hào)（ k=1,2 .n ） ,有以下結(jié)論：如 k=1,就該結(jié)點(diǎn)為根結(jié)點(diǎn),它沒(méi)有父結(jié)點(diǎn)；如 k1,就該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為 INTk/2；如 2kn,就編號(hào)為 k 的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為 2k；否就該結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn)（也無(wú)右 子結(jié)點(diǎn)）；如 2k+1n,

9、就編號(hào)為 k 的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為 2k+1；否就該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn)；滿二叉樹(shù)是指除最終一層外,每一層上的全部結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn),就 k 層上有 2k-1 個(gè) 結(jié)點(diǎn)深度為 m的滿二叉樹(shù)有 2m-1 個(gè)結(jié)點(diǎn)；完全二叉樹(shù)是指除最終一層外,每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值,在最終一層上只缺少 右邊的如干結(jié)點(diǎn)；儲(chǔ)；二叉樹(shù)儲(chǔ)備結(jié)構(gòu)采納鏈?zhǔn)絻?chǔ)備結(jié)構(gòu),對(duì)于滿二叉樹(shù)與完全二叉樹(shù)可以按層序進(jìn)行次序存二叉樹(shù)的遍歷：（1）前序遍歷（ DLR）,第一拜訪根結(jié)點(diǎn),然后遍歷左子樹(shù),最終遍歷右子樹(shù)；（2）中序遍歷（ LDR）,第一遍歷左子樹(shù),然后拜訪根結(jié)點(diǎn),最終遍歷右子樹(shù)；（3）后序遍歷（ LRD）第一遍歷左子樹(shù),然后拜訪遍歷右

10、子樹(shù),最終拜訪根結(jié)點(diǎn)；17 查找技術(shù)次序查找的使用情形：（1）線性表為無(wú)序表；（2）表采納鏈?zhǔn)絻?chǔ)備結(jié)構(gòu)；二分法查找只適用于次序儲(chǔ)備的有序表,對(duì)于長(zhǎng)度為n 的有序線性表, 最壞情形只需比較 log2n 次；18 排序技術(shù)排序是指將一個(gè)無(wú)序序列整理成按值非遞減次序排列的有序序列；交換類(lèi)排序法： （1）冒泡排序法,需要比較的次數(shù)為 nn-1/2；（2）快速排序法；插入類(lèi)排序法： （1）簡(jiǎn)潔插入排序法,最壞情形需要 nn-1/2 次比較；（2）希爾排序法,最壞情形需要 O次比較；挑選類(lèi)排序法： （1）簡(jiǎn)潔挑選排序法 , 最壞情形需要 nn-1/2 次比較；（2）堆排序法,最壞情形需要 Onlog2n

11、次比較；其次章程序設(shè)計(jì)基礎(chǔ)21 程序設(shè)計(jì)設(shè)計(jì)方法和風(fēng)格如何形成良好的程序設(shè)計(jì)風(fēng)格1、源程序文檔化；2、數(shù)據(jù)說(shuō)明的方法；3、語(yǔ)句的結(jié)構(gòu)；4、輸入和輸出；注釋分序言性注釋和功能性注釋,語(yǔ)句結(jié)構(gòu)清晰第一、效率其次；22 結(jié)構(gòu)化程序設(shè)計(jì)1. 自頂向下； 2. 逐步求精； 3. 模塊化； 4. 限制結(jié)構(gòu)化程序設(shè)計(jì)方法的四條原就是：使用 goto 語(yǔ)句；結(jié)構(gòu)化程序的基本結(jié)構(gòu)和特點(diǎn)：（1）次序結(jié)構(gòu)：一種簡(jiǎn)潔的程序設(shè)計(jì),最基本、最常用的結(jié)構(gòu)；（2）挑選結(jié)構(gòu)：又稱(chēng)分支結(jié)構(gòu),包括簡(jiǎn)潔挑選和多分支挑選結(jié)構(gòu),可依據(jù)條件,判定 應(yīng)當(dāng)挑選哪一條分支來(lái)執(zhí)行相應(yīng)的語(yǔ)句序列；（3）重復(fù)結(jié)構(gòu)：又稱(chēng)循環(huán)結(jié)構(gòu),可依據(jù)給定條件,判定是

12、否需要重復(fù)執(zhí)行某一相同程 序段；23 面對(duì)對(duì)象的程序設(shè)計(jì)60 歲月末挪威奧斯陸高校和挪威運(yùn)算機(jī)中心研制的SIMULA面對(duì)對(duì)象的程序設(shè)計(jì)：以語(yǔ)言為標(biāo)志；面對(duì)對(duì)象方法的優(yōu)點(diǎn)：（1）與人類(lèi)習(xí)慣的思維方法一樣；（2）穩(wěn)固性好；（3）可重用性好；（4）易于開(kāi)發(fā)大型軟件產(chǎn)品；（5）可愛(ài)護(hù)性好；對(duì)象是面對(duì)對(duì)象方法中最基本的概念,可以用來(lái)表示客觀世界中的任何實(shí)體,對(duì)象是實(shí)體的抽象；面對(duì)對(duì)象的程序設(shè)計(jì)方法中的對(duì)象是系統(tǒng)中用來(lái)描述客觀事物的一個(gè)實(shí)體,是構(gòu)成系統(tǒng) 的一個(gè)基本單位,由一組表示其靜態(tài)特點(diǎn)的屬性和它可執(zhí)行的一組操作組成；屬性即對(duì)象所包含的信息,操作描述了對(duì)象執(zhí)行的功能,操作也稱(chēng)為方法或服務(wù)；對(duì)象的基本特點(diǎn)

13、：（1）標(biāo)識(shí)惟一性；（2）分類(lèi)性；（3）多態(tài)性；（4）封裝性；（5）模塊獨(dú)立性好；類(lèi)是指具有共同屬性、共同方法的對(duì)象的集合；所以類(lèi)是對(duì)象的抽象,對(duì)象是對(duì)應(yīng)類(lèi)的一個(gè)實(shí)例；消息是一個(gè)實(shí)例與另一個(gè)實(shí)例之間傳遞的信息；消息的組成包括（1）接收消息的對(duì)象的名稱(chēng)；（2）消息標(biāo)識(shí)符,也稱(chēng)消息名；（3）零個(gè)或多個(gè)參數(shù)；繼承是指能夠直接獲得已有的性質(zhì)和特點(diǎn),而不必重復(fù)定義他們；繼承分單繼承和多重繼承；單繼承指一個(gè)類(lèi)只答應(yīng)有一個(gè)父類(lèi),多重繼承指一個(gè)類(lèi)答應(yīng)有多個(gè)父類(lèi)；多態(tài)性是指同樣的消息被不同的對(duì)象接受時(shí)可導(dǎo)致完全不同的行動(dòng)的現(xiàn)象；第三章軟件工程基礎(chǔ) 31 軟件工程基本概念 運(yùn)算機(jī)軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完

14、整集合；軟件的特點(diǎn)包括：（1）軟件是一種規(guī)律實(shí)體；（2）軟件的生產(chǎn)與硬件不同,它沒(méi)有明顯的制作過(guò)程；（3）軟件在運(yùn)行、使用期間不存在磨損、老化問(wèn)題；（4）軟件的開(kāi)發(fā)、運(yùn)行對(duì)運(yùn)算機(jī)系統(tǒng)具有依靠性,受運(yùn)算機(jī)系統(tǒng)的限制,這導(dǎo)致了軟 件移植的問(wèn)題；（5）軟件復(fù)雜性高,成本昂貴；（6）軟件開(kāi)發(fā)涉及諸多的社會(huì)因素；軟件按功能分為應(yīng)用軟件、系統(tǒng)軟件、支撐軟件（或工具軟件）；軟件危機(jī)主要表現(xiàn)在成本、質(zhì)量、生產(chǎn)率等問(wèn)題；工具、文檔、實(shí)踐標(biāo) 軟件工程是應(yīng)用于運(yùn)算機(jī)軟件的定義、開(kāi)發(fā)和愛(ài)護(hù)的一整套方法、準(zhǔn)和工序；軟件工程包括 3 個(gè)要素：方法、工具和過(guò)程；軟件工程過(guò)程是把軟件轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動(dòng),包含

15、 4 種基本活動(dòng)：（1）P軟件規(guī)格說(shuō)明；（2）D軟件開(kāi)發(fā)；（3）C軟件確認(rèn)；（4）A軟件演進(jìn)；軟件周期：軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用愛(ài)護(hù)到停止使用退役的過(guò)程；軟件生命周期三個(gè)階段 : 軟件定義、軟件開(kāi)發(fā)、運(yùn)行愛(ài)護(hù),主要活動(dòng)階段是：（1）可行性爭(zhēng)論與方案制定；（2）需求分析；（3）軟件設(shè)計(jì)；（4）軟件實(shí)現(xiàn)；（5）軟件測(cè)試；（6）運(yùn)行和愛(ài)護(hù)；軟件工程的目標(biāo)和與原就：目標(biāo)： 在給定成本、 進(jìn)度的前提下, 開(kāi)發(fā)出具有有效性、牢靠性、 可懂得性、 可愛(ài)護(hù)性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿意用戶需求的產(chǎn)品；基本目標(biāo)： 付出較低的開(kāi)發(fā)成本；達(dá)到要求的軟件功能；取得較好的軟件性能；開(kāi)發(fā)軟

16、 件易于移植；需要較低的費(fèi)用；能按時(shí)完成開(kāi)發(fā),準(zhǔn)時(shí)交付使用；基本原就：抽象、信息隱藏、模塊化、局部化、確定性、一樣性、完備性和可驗(yàn)證性；軟件工程的理論和技術(shù)性爭(zhēng)論的內(nèi)容主要包括：軟件開(kāi)發(fā)技術(shù)和軟件工程治理；軟件開(kāi)發(fā)技術(shù)包括：軟件開(kāi)發(fā)方法學(xué)、開(kāi)發(fā)過(guò)程、開(kāi)發(fā)工具和軟件工程環(huán)境；軟件工程治理包括：軟件治理學(xué)、軟件工程經(jīng)濟(jì)學(xué)、軟件心理學(xué)等內(nèi)容；軟件治理學(xué)包括人員組織、進(jìn)度支配、質(zhì)量保證、配置治理、項(xiàng)目方案等；軟件工程原就包括抽象、信息隱藏、模塊化、局部化、確定性、一樣性、完備性和可驗(yàn) 證性；32 結(jié)構(gòu)化分析方法 結(jié)構(gòu)化方法的核心和基礎(chǔ)是結(jié)構(gòu)化程序設(shè)計(jì)理論；需求分析方法有（1）結(jié)構(gòu)化需求分析方法；（2）

17、面對(duì)對(duì)象的分析的方法；從需求分析建立的模型的特性來(lái)分：靜態(tài)分析和動(dòng)態(tài)分析；結(jié)構(gòu)化分析方法的實(shí)質(zhì)：著眼于數(shù)據(jù)流,自頂向下,逐層分解,建立系統(tǒng)的處理流程,以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具 , 建立系統(tǒng)的規(guī)律模型；結(jié)構(gòu)化分析的常用工具（1）數(shù)據(jù)流圖；（2）數(shù)據(jù)字典；（3）判定樹(shù)；（4）判定表；數(shù)據(jù)流圖： 描述數(shù)據(jù)處理過(guò)程的工具,是需求懂得的規(guī)律模型的圖形表示,它直接支持系統(tǒng)功能建模；數(shù)據(jù)字典： 對(duì)全部與系統(tǒng)相關(guān)的數(shù)據(jù)元素的一個(gè)有組織的列表,以及精確的、 嚴(yán)格的定義,使得用戶和系統(tǒng)分析員對(duì)于輸入、輸出、儲(chǔ)備成分和中間運(yùn)算結(jié)果有共同的懂得；判定樹(shù)： 從問(wèn)題定義的文字描述中分清哪些是判定的條件,哪些是判定的

18、結(jié)論,依據(jù)描述材料中的連接詞找出判定條件之間的從屬關(guān)系、樹(shù)；并列關(guān)系、 挑選關(guān)系, 依據(jù)它們構(gòu)造判定判定表： 與判定樹(shù)相像, 當(dāng)數(shù)據(jù)流圖中的加工要依靠于多個(gè)規(guī)律條件的取值,即完成該 加工的一組動(dòng)作是由于某一組條件取值的組合而引發(fā)的,使用判定表描述比較相宜；數(shù)據(jù)字典是結(jié)構(gòu)化分析的核心；軟件需求規(guī)格說(shuō)明書(shū)的特點(diǎn)：（1）正確性；（2）無(wú)岐義性；（3）完整性；（4）可驗(yàn)證性；（5）一樣性；（6）可懂得性；（7）可追蹤性；33 結(jié)構(gòu)化設(shè)計(jì)方法 軟件設(shè)計(jì)的基本目標(biāo)是用比較抽象概括的方式確定目標(biāo)系統(tǒng)如何完成預(yù)定的任務(wù),軟件 設(shè)計(jì)是確定系統(tǒng)的物理模型；軟件設(shè)計(jì)是開(kāi)發(fā)階段最重要的步驟,一途徑；是將需求精確地轉(zhuǎn)化

19、為完整的軟件產(chǎn)品或系統(tǒng)的唯從技術(shù)觀點(diǎn)來(lái)看,軟件設(shè)計(jì)包括軟件結(jié)構(gòu)設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、過(guò)程設(shè)計(jì)；結(jié)構(gòu)設(shè)計(jì)：定義軟件系統(tǒng)各主要部件之間的關(guān)系；數(shù)據(jù)設(shè)計(jì)：將分析時(shí)創(chuàng)建的模型轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)的定義；接口設(shè)計(jì)：描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)之間以及軟件與人之間如何通信；過(guò)程設(shè)計(jì)：把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過(guò)程描述；從工程治理角度來(lái)看：概要設(shè)計(jì)和具體設(shè)計(jì)；軟件設(shè)計(jì)的一般過(guò)程：軟件設(shè)計(jì)是一個(gè)迭代的過(guò)程；先進(jìn)行高層次的結(jié)構(gòu)設(shè)計(jì)；后進(jìn)行低層次的過(guò)程設(shè)計(jì)；穿插進(jìn)行數(shù)據(jù)設(shè)計(jì)和接口設(shè)計(jì)；衡量軟件模塊獨(dú)立性使用耦合性和內(nèi)聚性兩個(gè)定性的度量標(biāo)準(zhǔn)；在程序結(jié)構(gòu)中各模塊的內(nèi)聚性越強(qiáng),就耦合性越弱；優(yōu)秀軟件應(yīng)高內(nèi)聚,低耦合；軟件

20、概要設(shè)計(jì)的基本任務(wù)是：（1）設(shè)計(jì)軟件系統(tǒng)結(jié)構(gòu)；（3）編寫(xiě)概要設(shè)計(jì)文檔；（2）數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫(kù)設(shè)計(jì)；（4）概要設(shè)計(jì)文檔評(píng)審；模塊用一個(gè)矩形表示,箭頭表示模塊間的調(diào)用關(guān)系；在結(jié)構(gòu)圖中仍可以用帶注釋的箭頭表示模塊調(diào)用過(guò)程中來(lái)回傳遞的信息；仍可用帶實(shí)心 圓的箭頭表示傳遞的是掌握信息,空心圓箭心表示傳遞的是數(shù)據(jù)；結(jié)構(gòu)圖的基本形式：基本形式、次序形式、重復(fù)形式、挑選形式；結(jié)構(gòu)圖有四種模塊類(lèi)型：傳入模塊、傳出模塊、變換模塊和和諧模塊；典型的數(shù)據(jù)流類(lèi)型有兩種：變換型和事務(wù)型；變換型系統(tǒng)結(jié)構(gòu)圖由輸入、中心變換、輸出三部分組成；事務(wù)型數(shù)據(jù)流的特點(diǎn)是：接受一項(xiàng)事務(wù), 依據(jù)事務(wù)處理的特點(diǎn)和性質(zhì),挑選分派一個(gè)適當(dāng)?shù)奶幚?/p>

21、單元,然后給出結(jié)果；具體設(shè)計(jì)： 是為軟件結(jié)構(gòu)圖中的每一個(gè)模塊確定實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu),用某種選定 的表達(dá)工具表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)；常見(jiàn)的過(guò)程設(shè)計(jì)工具有：34 軟件測(cè)試圖形工具（程序流程圖） 、表格工具（判定表）、語(yǔ)言工具 （PDL）；軟件測(cè)試定義： 使用人工或自動(dòng)手段來(lái)運(yùn)行或測(cè)定某個(gè)系統(tǒng)的過(guò)程,其目的在于檢驗(yàn)它是否滿意規(guī)定的需求或是弄清預(yù)期結(jié)果與實(shí)際結(jié)果之間的差別；軟件測(cè)試的目的：發(fā)覺(jué)錯(cuò)誤而執(zhí)行程序的過(guò)程；軟件測(cè)試方法：靜態(tài)測(cè)試和動(dòng)態(tài)測(cè)試；靜態(tài)測(cè)試包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、 代碼質(zhì)量度量； 不實(shí)際運(yùn)行軟件,主要通過(guò)人工進(jìn)行；動(dòng)態(tài)測(cè)試：是基本運(yùn)算機(jī)的測(cè)試,主要包括白盒測(cè)試方法和黑盒測(cè)試方

22、法；白盒測(cè)試： 在程序內(nèi)部進(jìn)行, 主要用于完成軟件內(nèi)部操作的驗(yàn)證；主要方法有規(guī)律掩蓋、基本基路徑測(cè)試；黑盒測(cè)試： 主要診斷功能不對(duì)或遺漏、界面錯(cuò)誤、數(shù)據(jù)結(jié)構(gòu)或外部數(shù)據(jù)庫(kù)拜訪錯(cuò)誤、性 能錯(cuò)誤、初始化和終止條件錯(cuò),用于軟件確認(rèn)；主要方法有等價(jià)類(lèi)劃分法、邊界值分析法、錯(cuò)誤估計(jì)法、因果圖等；軟件測(cè)試過(guò)程一般按 4 個(gè)步驟進(jìn)行：?jiǎn)卧獪y(cè)試、集成測(cè)試、驗(yàn)收測(cè)試（確認(rèn)測(cè)試）和系 統(tǒng)測(cè)試；35 程序的調(diào)試 程序調(diào)試的任務(wù)是診斷和改正程序中的錯(cuò)誤,主要在開(kāi)發(fā)階段進(jìn)行；程序調(diào)試的基本步驟：（1）錯(cuò)誤定位；（2）修改設(shè)計(jì)和代碼,以排除錯(cuò)誤；（3）進(jìn)行回來(lái)測(cè)試,防止引進(jìn)新的錯(cuò)誤；軟件調(diào)試可分表靜態(tài)調(diào)試和動(dòng)態(tài)調(diào)試；靜態(tài)調(diào)

23、試主要是指通過(guò)人的思維來(lái)分析源程序代 碼和排錯(cuò),是主要的設(shè)計(jì)手段,而動(dòng)態(tài)調(diào)試是幫助靜態(tài)調(diào)試；主要調(diào)試方法有：（1）強(qiáng)行排錯(cuò)法；（2）回溯法；（3）緣由排除法；第四章數(shù)據(jù)庫(kù) 41 數(shù)據(jù)庫(kù)系統(tǒng)的基本概念 數(shù)據(jù)：實(shí)際上就是描述事物的符號(hào)記錄；數(shù)據(jù)的特點(diǎn)：有肯定的結(jié)構(gòu),有型與值之分,如整型、實(shí)型、字符型等；而數(shù)據(jù)的值給 出了符合定型的值,如整型值 15；數(shù)據(jù)庫(kù)： 是數(shù)據(jù)的集合, 具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的儲(chǔ)備介質(zhì)內(nèi),是多種應(yīng)用 數(shù)據(jù)的集成,并可被各個(gè)應(yīng)用程序共享；數(shù)據(jù)庫(kù)存放數(shù)據(jù)是按數(shù)據(jù)所供應(yīng)的數(shù)據(jù)模式存放的,具有集成與共享的特點(diǎn)；數(shù)據(jù)庫(kù)治理系統(tǒng)：一種系統(tǒng)軟件,負(fù)責(zé)數(shù)據(jù)庫(kù)中的數(shù)據(jù)組織、數(shù)據(jù)操縱、數(shù)

24、據(jù)愛(ài)護(hù)、控 制及愛(ài)護(hù)和數(shù)據(jù)服務(wù)等,是數(shù)據(jù)庫(kù)的核心；目前的數(shù)據(jù)庫(kù)治理系統(tǒng)（DBMS）均為關(guān)系數(shù)據(jù) 庫(kù)系統(tǒng)；如 Oracle 、Sybase、 DB2、SQLServer 等；仍有小型數(shù)據(jù)庫(kù)系統(tǒng) Visual Foxpro 和 Access 等；數(shù)據(jù)庫(kù)治理系統(tǒng)功能：（1）數(shù)據(jù)模式定義：即為數(shù)據(jù)庫(kù)構(gòu)建其數(shù)據(jù)框架；（2）數(shù)據(jù)存取的物理構(gòu)建：為數(shù)據(jù)模式的物理存取與構(gòu)建供應(yīng)有效的存取方法與手段；（3）數(shù)據(jù)操縱：為用戶使用數(shù)據(jù)庫(kù)的數(shù)據(jù)供應(yīng)便利,如查詢、插入、修改、刪除等以 及簡(jiǎn)潔的算術(shù)運(yùn)算及統(tǒng)計(jì)；（4）數(shù)據(jù)的完整性、安生性定義與檢查；（5）數(shù)據(jù)庫(kù)的并發(fā)掌握與故障復(fù)原；（6）數(shù)據(jù)的服務(wù)：如拷貝、轉(zhuǎn)存、重組、性

25、能監(jiān)測(cè)、分析等；為完成以上六個(gè)功能,數(shù)據(jù)庫(kù)治理系統(tǒng)供應(yīng)以下的數(shù)據(jù)語(yǔ)言：（1）數(shù)據(jù)定義語(yǔ)言：負(fù)責(zé)數(shù)據(jù)的模式定義與數(shù)據(jù)的物理存取構(gòu)建；（2）數(shù)據(jù)操縱語(yǔ)言：負(fù)責(zé)數(shù)據(jù)的操縱,如查詢與增、刪、改等；（3）數(shù)據(jù)掌握語(yǔ)言：負(fù)責(zé)數(shù)據(jù)完整性、安全性的定義與檢查以及并發(fā)掌握、故障復(fù)原 等；數(shù)據(jù)語(yǔ)言按其使用方式具有兩種結(jié)構(gòu)形式：交互式命令 又稱(chēng)自含型或自主型語(yǔ)言 宿主型語(yǔ)言（一般可嵌入某些宿主語(yǔ)言中）；數(shù)據(jù)庫(kù)治理員：對(duì)數(shù)據(jù)庫(kù)進(jìn)行規(guī)劃、設(shè)計(jì)、愛(ài)護(hù)、監(jiān)視等的專(zhuān)業(yè)治理人員；數(shù)據(jù)庫(kù)系統(tǒng)：由數(shù)據(jù)庫(kù)（數(shù)據(jù)）、數(shù)據(jù)庫(kù)治理系統(tǒng)（軟件）、數(shù)據(jù)庫(kù)治理員（人員） 、硬件平臺(tái)（硬件） 、軟件平臺(tái)（軟件）五個(gè)部分構(gòu)成的運(yùn)行實(shí)體；數(shù)據(jù)庫(kù)應(yīng)用系

26、統(tǒng)：由數(shù)據(jù)庫(kù)系統(tǒng)、應(yīng)用軟件及應(yīng)用界面三者組成；文件系統(tǒng)階段： 供應(yīng)了簡(jiǎn)潔的數(shù)據(jù)共享與數(shù)據(jù)治理才能,但是它無(wú)法供應(yīng)完整的、統(tǒng)一的、治理和數(shù)據(jù)共享的才能；層次數(shù)據(jù)庫(kù)與網(wǎng)狀數(shù)據(jù)庫(kù)系統(tǒng)階段 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)階段：為統(tǒng)一與共享數(shù)據(jù)供應(yīng)了有力支撐；數(shù)據(jù)庫(kù)系統(tǒng)的基本特點(diǎn)：數(shù)據(jù)的集成性、數(shù)據(jù)的高共享性與低冗余性、數(shù)據(jù)獨(dú)立性（物理獨(dú)立性與規(guī)律獨(dú)立性）、數(shù)據(jù)統(tǒng)一治理與掌握；數(shù)據(jù)庫(kù)系統(tǒng)的三級(jí)模式：（1）概念模式：數(shù)據(jù)庫(kù)系統(tǒng)中全局?jǐn)?shù)據(jù)規(guī)律結(jié)構(gòu)的描述,全體用戶公共數(shù)據(jù)視圖；（2）外模式：也稱(chēng)子模式與用戶模式；是用戶的數(shù)據(jù)視圖,也就是用戶所見(jiàn)到的數(shù)據(jù) 模式；（3）內(nèi)模式：又稱(chēng)物理模式,它給出了數(shù)據(jù)庫(kù)物理儲(chǔ)備結(jié)構(gòu)與物理存取方

27、法；數(shù)據(jù)庫(kù)系統(tǒng)的兩級(jí)映射：（1）概念模式到內(nèi)模式的映射；（2）外模式到概念模式的映射；數(shù)據(jù)模型 數(shù)據(jù)模型的概念：是數(shù)據(jù)特點(diǎn)的抽象,從抽象層次上描述了系統(tǒng)的靜態(tài)特點(diǎn)、動(dòng)態(tài)行為 和約束條件, 為數(shù)據(jù)庫(kù)系統(tǒng)的信息表與操作供應(yīng)一個(gè)抽象的框架；描述了數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操 作及數(shù)據(jù)約束；E-R 模型的基本概念（1）實(shí)體：現(xiàn)實(shí)世界中的事物；（2）屬性：事物的特性；（3）聯(lián)系：現(xiàn)實(shí)世界中事物間的關(guān)系；實(shí)體集的關(guān)系有一對(duì)一、一對(duì)多、多對(duì)多的聯(lián) 系；E-R 模型三個(gè)基本概念之間的聯(lián)接關(guān)系：實(shí)體是概念世界中的基本單位,屬性有屬性域,每個(gè)實(shí)體可取屬性域內(nèi)的值；一個(gè)實(shí)體的全部屬性值叫元組；E-R 模型的圖示法： （1）實(shí)體

28、集表示法；（2）屬性表法；（3）聯(lián)系表示法；層次模型的基本結(jié)構(gòu)是樹(shù)形結(jié)構(gòu),具有以下特點(diǎn)：（1）每棵樹(shù)有且僅有一個(gè)無(wú)雙親結(jié)點(diǎn),稱(chēng)為根；（2）樹(shù)中除根外全部結(jié)點(diǎn)有且僅有一個(gè)雙親；從圖論上看,網(wǎng)狀模型是一個(gè)不加任何條件限制的無(wú)向圖；關(guān)系模型采納二維表來(lái)表示,簡(jiǎn)稱(chēng)表, 由表框架及表的元組組成；一個(gè)二維表就是一個(gè)關(guān)系；在二維表中凡能唯獨(dú)標(biāo)識(shí)元組的最小屬性稱(chēng)為鍵或碼；從全部侯選健中選取一個(gè)作為用 戶使用的鍵稱(chēng)主鍵；表 A 中的某屬性是某表 B 的鍵,就稱(chēng)該屬性集為 A 的外鍵或外碼；關(guān)系中的數(shù)據(jù)約束：（1）實(shí)體完整性約束：約束關(guān)系的主鍵中屬性值不能為空值；（2）參照完全性約束：是關(guān)系之間的基本約束；（3）

29、用戶定義的完整性約束：它反映了具體應(yīng)用中數(shù)據(jù)的語(yǔ)義要求；關(guān)系代數(shù)關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的特點(diǎn)之一是它建立在數(shù)據(jù)理論的基礎(chǔ)之上,關(guān)系模型的數(shù)據(jù)操作,其中最為聞名的是關(guān)系代數(shù)與關(guān)系演算；關(guān)系模型的基本運(yùn)算：有許多數(shù)據(jù)理論可以表示（1）插入（2）刪除3 修改（ 4）查詢（包括投影、挑選、笛卡爾積運(yùn)算）數(shù)據(jù)庫(kù)設(shè)計(jì)與治理 數(shù)據(jù)庫(kù)設(shè)計(jì)是數(shù)據(jù)應(yīng)用的核心；數(shù)據(jù)庫(kù)設(shè)計(jì)的兩種方法：（1）面對(duì)數(shù)據(jù)：以信息需求為主,兼顧處理需求；（2）面對(duì)過(guò)程：以處理需求為主,兼顧信息需求；數(shù)據(jù)庫(kù)的生命周期：需求分析階段、概念設(shè)計(jì)階段、規(guī)律設(shè)計(jì)階段、物理設(shè)計(jì)階段、編 碼階段、測(cè)試階段、運(yùn)行階段、進(jìn)一步修改階段；SA）方法用自頂向下、需求分析

30、常用結(jié)構(gòu)析方法和面對(duì)對(duì)象的方法；結(jié)構(gòu)化分析（簡(jiǎn)稱(chēng) 逐層分解的方式分析系統(tǒng)；用數(shù)據(jù)流圖表達(dá)數(shù)據(jù)和處理過(guò)程的關(guān)系；對(duì)數(shù)據(jù)庫(kù)設(shè)計(jì)來(lái)講,數(shù) 據(jù)字典是進(jìn)行具體的數(shù)據(jù)收集和數(shù)據(jù)分析所獲得的主要結(jié)果；數(shù)據(jù)字典是各類(lèi)數(shù)據(jù)描述的集合,包括5 個(gè)部分：數(shù)據(jù)項(xiàng)、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)流（可以是數(shù)據(jù)項(xiàng),也可以是數(shù)據(jù)結(jié)構(gòu)）、數(shù)據(jù)儲(chǔ)備、處理過(guò)程；數(shù)據(jù)庫(kù)概念設(shè)計(jì)的目的是分析數(shù)據(jù)內(nèi)在語(yǔ)義關(guān)系；設(shè)計(jì)的方法有兩種（1）集中式模式設(shè)計(jì)法（適用于小型或并不復(fù)雜的單位或部門(mén)）；（2）視圖集成設(shè)計(jì)法；設(shè)計(jì)方法： E-R 模型與視圖集成；視圖設(shè)計(jì)一般有三種設(shè)計(jì)次序：自頂向下、由底向上、由內(nèi)向外；視圖集成的幾種沖突：命名沖突、概念沖突、域沖突、約束

31、沖突；關(guān)系視圖設(shè)計(jì)：關(guān)系視圖的設(shè)計(jì)又稱(chēng)外模式設(shè)計(jì)；關(guān)系視圖的主要作用：（1）供應(yīng)數(shù)據(jù)規(guī)律獨(dú)立性；（2）能適應(yīng)用戶對(duì)數(shù)據(jù)的不同需求；（3）有肯定數(shù)據(jù)保密功能；數(shù)據(jù)庫(kù)的物理設(shè)計(jì)主要目標(biāo)是對(duì)數(shù)據(jù)內(nèi)部物理結(jié)構(gòu)作調(diào)整并挑選合理的存取路徑,以提高數(shù)據(jù)庫(kù)拜訪速度有效利用儲(chǔ)備空間；引設(shè)計(jì)、集成簇設(shè)計(jì)和分區(qū)設(shè)計(jì)；數(shù)據(jù)庫(kù)治理的內(nèi)容：（1）數(shù)據(jù)庫(kù)的建立；（2）數(shù)據(jù)庫(kù)的調(diào)整；（3）數(shù)據(jù)庫(kù)的重組；一般 RDBMS中留給用戶參加物理設(shè)計(jì)的內(nèi)容大致有索（4）數(shù)據(jù)庫(kù)安全性與完整性掌握；（5）數(shù)據(jù)庫(kù)的故障復(fù)原；（6）數(shù)據(jù)庫(kù)監(jiān)控；算法的基本概念（11）算法具有五個(gè)特性,以下選項(xiàng)中不屬于算法特性的是 _；2022-4A）有窮性 B

32、）簡(jiǎn)潔性 C）可行性 D）確定性答案： B（5）問(wèn)題處理方案的正確而完整的描述稱(chēng)為【5】 2022-4；答案：算法（2）算法復(fù)雜度主要包括時(shí)間復(fù)雜度和【2】復(fù)雜度； 2022 年 9 月答案：空間45 以下表達(dá)中錯(cuò)誤選項(xiàng) 2022 年 4 月 A算法正確的程序最終肯定會(huì)終止 B算法正確的程序可以有零個(gè)輸出 C算法正確的程序可以有零個(gè)輸入 D算法正確的程序?qū)τ谙嗤妮斎肟隙ㄓ邢嗤慕Y(jié)果答案： B7. 以下表達(dá)中正確選項(xiàng) _；2022 年 9 月 A）一個(gè)算法的空間復(fù)雜度大,就其時(shí)間復(fù)雜度也必定大 B）一個(gè)算法的空間復(fù)雜度大,就其時(shí)間復(fù)雜度必定小 C）一個(gè)算法的時(shí)間復(fù)雜度大,就其空間復(fù)雜度必定小

33、D）上述三種說(shuō)法都不對(duì)答案： D1 以下表達(dá)中正確選項(xiàng) _；2022 年 4 月 A算法的效率只與問(wèn)題的規(guī)模有關(guān),而與數(shù)據(jù)的儲(chǔ)備結(jié)構(gòu)無(wú)關(guān) B算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的運(yùn)算工作量 C數(shù)據(jù)的規(guī)律結(jié)構(gòu)與儲(chǔ)備結(jié)構(gòu)是一一對(duì)應(yīng)的 D算法的時(shí)間復(fù)雜度與空間復(fù)雜度肯定相關(guān)答案： B（11）算法中,對(duì)需要執(zhí)行的每一步操作,必需給出清晰、嚴(yán)格的規(guī)定,這屬于 算法的 A ）正值性 B ）可行性 C）確定性 D）有窮性答案： C（12）算法的有窮性是指： 2022 年 4 月A）算法程序的運(yùn)行時(shí)間是有限的 B）算法程序所處理的數(shù)據(jù)量是有限的C）算法程序的長(zhǎng)度是有限的 D）算法只能被有限的用戶使用答案： A數(shù)

34、據(jù)結(jié)構(gòu)考試內(nèi)容：1. 數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的規(guī)律結(jié)構(gòu)與儲(chǔ)備結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性結(jié)構(gòu)與 非線性結(jié)構(gòu)的概念；2. 線性表的定義；線性表的次序儲(chǔ)備結(jié)構(gòu)及其插入與刪除運(yùn)算；3. 棧和隊(duì)列的定義；棧和隊(duì)列的次序儲(chǔ)備結(jié)構(gòu)及其基本運(yùn)算；4. 線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算；5. 樹(shù)的基本概念；二叉樹(shù)的定義及其儲(chǔ)備結(jié)構(gòu)；二叉樹(shù)的前序、中序和后序遍歷；6. 次序查找與二分法查找算法；基本排序算法（交換類(lèi)排序,挑選類(lèi)排序,插入類(lèi)排 序）；2022-4（1）數(shù)據(jù)的儲(chǔ)備結(jié)構(gòu)是指 _；A）儲(chǔ)備在外存中的數(shù)據(jù) B）數(shù)據(jù)所占的儲(chǔ)備空間量C）數(shù)據(jù)在運(yùn)算機(jī)中的次序儲(chǔ)備方式 D）數(shù)據(jù)的規(guī)律結(jié)構(gòu)在運(yùn)算機(jī)

35、中的表示 答案： D（2）以下關(guān)于棧的描述中錯(cuò)誤選項(xiàng) _；A） 棧是先進(jìn)后出的線性表 B） 棧只能次序儲(chǔ)備 C） 棧具有記憶作用 D） 對(duì)棧的插入與刪除操作中,不需要轉(zhuǎn)變棧底指針答案：B（3）對(duì)于長(zhǎng)度為 n 的線性表,在最壞情形下,以下各排序法所對(duì)應(yīng)的比較次數(shù)中正確選項(xiàng) _；A）冒泡排序?yàn)?n/2 B）冒泡排序?yàn)?n n D）快速排序?yàn)?nn-1/2 C）快速排序?yàn)?答案：D冒泡排序?yàn)?nn-1/2（4）對(duì)長(zhǎng)度為 n 的線性表進(jìn)行次序查找,在最壞情形下所需要的比較次數(shù)為 _；） n+1 A） log2n B）n/2 C）n D 答案：C（5）以下對(duì)于線性鏈表的描述中正確選項(xiàng) _；A） 儲(chǔ)備空間

36、不肯定是連續(xù),且各元素的儲(chǔ)備次序是任意的 B） 儲(chǔ)備空間不肯定是連續(xù),且前件元素肯定儲(chǔ)備在后件元素的前面 C） 儲(chǔ)備空間必需連續(xù),且前件元素肯定儲(chǔ)備在后件元素的前面 D） 儲(chǔ)備空間必需連續(xù),且各元素的儲(chǔ)備次序是任意的 答案： A（47）有以下結(jié)構(gòu)體說(shuō)明和變量定義,如下列圖： struct node int data; struct node *next; *p,*q,*r; data next data next data next p q r現(xiàn)要將 q 所指結(jié)點(diǎn)從鏈表中刪除,同時(shí)要保持鏈表的連續(xù),以下不能完成指定操作的語(yǔ)句是 _；A） P-next=q-next; B）p-next=p-ne

37、xt-next; C） p-next=r; D） p=q-next;答案： D二、填空題（每空2 分,共 40 分 請(qǐng)將每空的正確答案寫(xiě)在【1】至【 20】序號(hào)的橫線上,答在試卷上不得分；（1）某二叉樹(shù)中度為2 的結(jié)點(diǎn)有 18 個(gè),就該二叉樹(shù)中有【1】 個(gè)葉子結(jié)點(diǎn)；答案： 19對(duì)任何一棵二叉樹(shù)T,假如其終端結(jié)點(diǎn)數(shù)為n0,度為 2 的結(jié)點(diǎn)數(shù)為n2,就 n0=n2+12022-9（2）以下數(shù)據(jù)結(jié)構(gòu)中,能用二分法進(jìn)行查找的是 A）次序儲(chǔ)備的有序線性表 B ）線性鏈表 C）二叉鏈表 D）有序線性鏈表 答案： A（3）以下關(guān)于棧的描述正確選項(xiàng) A）在棧中只能插入元素而不能刪除元素 B）在棧中只能刪除元素

38、而不能插入元素 C）棧是特別的線性表,只能在一端插入或刪除元素 D）棧是特別的線性表,只能在一端插入元素,而在另一端刪除元素答案： C（4）以下表達(dá)中正確選項(xiàng) A）一個(gè)規(guī)律數(shù)據(jù)結(jié)構(gòu)只能有一種儲(chǔ)備結(jié)構(gòu) B）數(shù)據(jù)的規(guī)律結(jié)構(gòu)屬于線性結(jié)構(gòu),儲(chǔ)備結(jié)構(gòu)屬于非線性結(jié)構(gòu) C）一個(gè)規(guī)律數(shù)據(jù)結(jié)構(gòu)可以有多種儲(chǔ)備結(jié)構(gòu),且各種儲(chǔ)備結(jié)構(gòu)不影響數(shù)據(jù)處理的效率 D）一個(gè)規(guī)律數(shù)據(jù)結(jié)構(gòu)可以有多種儲(chǔ)備結(jié)構(gòu),且各種儲(chǔ)備結(jié)構(gòu)影響數(shù)據(jù)處理的效率 答案： D填空題：（5）數(shù)據(jù)結(jié)構(gòu)分為規(guī)律結(jié)構(gòu)和儲(chǔ)備結(jié)構(gòu),循環(huán)隊(duì)列屬于【5】 結(jié)構(gòu)；答案：儲(chǔ)備結(jié)構(gòu)（4）一棵二叉樹(shù)第六層（根結(jié)點(diǎn)為第一層）的結(jié)點(diǎn)數(shù)最多為【4】 個(gè)；答案： 32第 K 層上最多有2

39、K-12022-4 4 依據(jù)“ 后進(jìn)先出” 原就組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是A隊(duì)列 B棧 C雙向鏈表 D二叉樹(shù)答案： B5 以下表達(dá)中正確選項(xiàng) A線性鏈表是線性表的鏈?zhǔn)絻?chǔ)備結(jié)構(gòu) B棧與隊(duì)列是非線性結(jié)構(gòu) C雙向鏈表是非線性結(jié)構(gòu) D只有根結(jié)點(diǎn)的二叉樹(shù)是線性結(jié)構(gòu) 答案： AAB CDEF6 對(duì)如下二叉樹(shù) 進(jìn)行后序遍歷的結(jié)果為 AABCDEF BDBEAFC CABDECF DDEBFCA 答案： D7 在深度為 7 的滿二叉樹(shù)中,葉子結(jié)點(diǎn)的個(gè)數(shù)為A32 B31 C64 D63答案： C2 K-1=127k=7n0=n2+1 n0+n2=127二、填空題1 對(duì)長(zhǎng)度為 10 的線性表進(jìn)行冒泡排序,最壞情形下需要

40、比較的次數(shù)為【1】；答案： 45nn-1/22022-98. 在長(zhǎng)度為 64 的有序線性表中進(jìn)行次序查找,最環(huán)境情形下需要比較的次數(shù)為 _；A）63 B）64 C）6 D）7答案： B10. 對(duì)以下二叉樹(shù)進(jìn)行中序遍歷的結(jié)果是 _；FC EADGB A） ACBDFEG B） ACBDFGE C）ABDCGEF D）FCADBEG答案： A填空題：（4）按“ 先進(jìn)后出” 原就組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是【4】；答案：棧（5）數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu),帶鏈的隊(duì)列屬于【5】；答案：線性結(jié)構(gòu)2022-4 5 以下對(duì)隊(duì)列的表達(dá)正確選項(xiàng) A隊(duì)列屬于非線性表 B隊(duì)列按“ 先進(jìn)后出” 原就組織數(shù)據(jù) C隊(duì)列在隊(duì)

41、尾刪除數(shù)據(jù) D隊(duì)列按“ 先進(jìn)先出” 原就組織數(shù)據(jù) 答案： D6 對(duì)以下二叉樹(shù) A B C D E F X Y Z 進(jìn)行前序遍歷的結(jié)果為 A DYBEAFCZX B YDEBFZXCA C ABDYECFXZ D ABCDEFXYZ 答案： C 7 某二叉樹(shù)中有n 個(gè)度為 2 的結(jié)點(diǎn),就該二叉樹(shù)中的葉子結(jié)點(diǎn)數(shù)為 A n+1 B n-1 C 2n D n/2 答案： A n0=n2+1 二填空題（每空 2 分,共 40 分）（1）在深度為 7 的滿二叉樹(shù)中,度為 2 的結(jié)點(diǎn)個(gè)數(shù)為 _；答案： 63 2 K-1=127k=7 n0=n2+1 n0+n2=1272022-9一、挑選題 1-10每題 2

42、 分, 11-50每題 1 分. 共 60 分（5）以下表達(dá)中正確選項(xiàng) A）程序執(zhí)行的效率與數(shù)據(jù)的儲(chǔ)備結(jié)構(gòu)親密相關(guān) B）程序執(zhí)行的效率只取決于程序的掌握結(jié)構(gòu) C）程序執(zhí)行的效率只取決于所處理的數(shù)據(jù)量 D）以上三種說(shuō)法都不對(duì) 答案： A （6）以下表達(dá)中正確選項(xiàng) A）數(shù)據(jù)的規(guī)律結(jié)構(gòu)與儲(chǔ)備結(jié)構(gòu)必定是一一對(duì)應(yīng)的 B）由于運(yùn)算機(jī)儲(chǔ)備空間是向量式的儲(chǔ)備結(jié)構(gòu),因此,數(shù)據(jù)的儲(chǔ)備結(jié)構(gòu)肯定是線性結(jié)構(gòu) C）程序設(shè)計(jì)語(yǔ)言中的數(shù)組一般是次序儲(chǔ)備結(jié)構(gòu),因此,利用數(shù)組只能處理線性結(jié)構(gòu) D）以上三種說(shuō)法都不對(duì) 答案： D（7）冒泡排序在最壞情形下的比較次數(shù)是A）n（n+1） /2 B ）nlog2n C）n（n-1 ）/2

43、 D）n/2答案： C（8）一棵二叉樹(shù)中共有70 個(gè)葉子結(jié)點(diǎn)與80 個(gè)度為 1 的結(jié)點(diǎn),就該二叉樹(shù)中的總結(jié)點(diǎn)數(shù)為）A）219 D）231B）221 C229 答案： A n0=n2+1 n=n0+n1+n2 二、填空題 每空 2 分, 共 40 分3 線性表的儲(chǔ)備結(jié)構(gòu)主要分為次序儲(chǔ)備結(jié)構(gòu)和鏈?zhǔn)絻?chǔ)備結(jié)構(gòu). 隊(duì)列是一種特別的線性表,循環(huán)隊(duì)列是隊(duì)列的_3_ 儲(chǔ)備結(jié)構(gòu) . 鏈?zhǔn)?4 對(duì)以下二叉樹(shù)進(jìn)行中序遍歷的結(jié)果為 F / C E_4_ ACBDFEHGP / B G / P A D / H 三、軟件工程基礎(chǔ) 1. 軟件工程基本概念,軟件生命周期概念,軟件工具與軟件開(kāi)發(fā)環(huán)境；2. 結(jié)構(gòu)化分析方法,數(shù)據(jù)

44、流圖,數(shù)據(jù)字典,軟件需求規(guī)格說(shuō)明書(shū)；3. 結(jié)構(gòu)化設(shè)計(jì)方法,總體設(shè)計(jì)與具體設(shè)計(jì)；4. 軟件測(cè)試的方法,白盒測(cè)試與黑盒測(cè)試,測(cè)試用例設(shè)計(jì),軟件測(cè)試的實(shí)施,單元測(cè) 試、集成測(cè)試和系統(tǒng)測(cè)試；5. 程序的調(diào)試,靜態(tài)調(diào)試與動(dòng)態(tài)調(diào)試；6. 面對(duì)對(duì)象的程序設(shè)計(jì)方法,對(duì)象,方法,屬性及繼承與多態(tài)性；2022 年 4 月一、挑選題（ （1）（ 10）每道題 2 分,（11）（ 50）每道題 1 分,共 60 分）以下各題 A）、B）、C）、D）四個(gè)選項(xiàng)中,只有一個(gè)選項(xiàng)是正確的,請(qǐng)將正確的選項(xiàng)涂寫(xiě) 在答題卡相應(yīng)位置上,答在試卷上不得分；（6）以下對(duì)于軟件測(cè)試的描述中正確選項(xiàng) _；A） 軟件測(cè)試的目的是證明程序是否正

45、確 B） 軟件測(cè)試的目的是使程序運(yùn)行結(jié)果正確 C） 軟件測(cè)試的目的是盡可能多地發(fā)覺(jué)程序中的錯(cuò)誤 D） 軟件測(cè)試的目的是使程序符合結(jié)構(gòu)化原就 答案： C（7）為了使模塊盡可能獨(dú)立,要求 _；A） 模塊的內(nèi)聚程度要盡量高,且各模塊間的耦合程度要盡量強(qiáng) B） 模塊的內(nèi)聚程度要盡量高,且各模塊間的耦合程度要盡量弱 C） 模塊的內(nèi)聚程度要盡量低,且各模塊間的耦合程度要盡量弱 D） 模塊的內(nèi)聚程度要盡量低,且各模塊間的耦合程度要盡量強(qiáng) 答案： B（8）以下描述中正確選項(xiàng) _；A）程序就是軟件 B）軟件開(kāi)發(fā)不受運(yùn)算機(jī)系統(tǒng)的限制 C）軟件既是規(guī)律實(shí)體,又是物理實(shí)體 D）軟件是程序、數(shù)據(jù)與相關(guān)文檔的集合 答案：

46、 D二、填空題（每空 2 分,共 40 分（2）在面對(duì)對(duì)象方法中,類(lèi)的實(shí)例稱(chēng)為【2】 ；答案：對(duì)象（3）診斷和改正程序中錯(cuò)誤的工作通常稱(chēng)為【3】 ；答案：程序調(diào)試2022 年 9 一、挑選題（ （1）（ 10）每題 2 分,（ 11）（ 50）每題 1 分,共 60 分）（1）以下表達(dá)中正確選項(xiàng)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（5）以下描述中正確選項(xiàng) A）軟件工程只是解決軟件項(xiàng)目的治理問(wèn)題 B）軟件工程主要解決軟件產(chǎn)品的生產(chǎn)率問(wèn)題 C）軟件工程的主要思想是強(qiáng)調(diào)在軟件開(kāi)發(fā)過(guò)程中需要應(yīng)用

47、工程化原就 D）軟件工程只是解決軟件開(kāi)發(fā)中的技術(shù)問(wèn)題 答案： C（6）在軟件設(shè)計(jì)中,不屬于過(guò)程設(shè)計(jì)工具的是 A） PDL過(guò)程設(shè)計(jì)語(yǔ)言 B ） PAD圖 C）N-S 圖 D） DFD圖 答案： D DFD圖：數(shù)據(jù)流圖（需求分析）（7）以下表達(dá)中正確選項(xiàng) A）軟件交付使用后仍需要進(jìn)行愛(ài)護(hù) B）軟件一旦交付使用就不需要再進(jìn)行愛(ài)護(hù) C）軟件交付使用后其生命周期就終止 D）軟件愛(ài)護(hù)是指修復(fù)程序中被破壞的指令 答案： A 二、填空題（每空 2 分,共 40 分）（3）在進(jìn)行模塊測(cè)試時(shí),要為每個(gè)被測(cè)試的模塊另外設(shè)計(jì)兩類(lèi)模塊：驅(qū)動(dòng)模塊和承接 模塊（樁模塊） ；其中 【 3】 的作用是將測(cè)試數(shù)據(jù)傳送給被測(cè)試的模

48、塊,并顯示被測(cè)試模塊 所產(chǎn)生的結(jié)果；答案： 驅(qū)動(dòng)模塊 2022-4 一、挑選題 1 一 10 每題 2 分, 11 一50 每題 1 分,共 60 分 1 以下選項(xiàng)中不屬于結(jié)構(gòu)化程序設(shè)計(jì)方法的是A自頂向下 B逐步求精 C模塊化 D 可復(fù)用 答案： D2 兩個(gè)或兩個(gè)以上模塊之間關(guān)聯(lián)的緊密程度稱(chēng)為 A耦合度 B內(nèi)聚度 C復(fù)雜度 D 數(shù)據(jù)傳輸特性答案： A3 以下表達(dá)中正確選項(xiàng) A軟件測(cè)試應(yīng)當(dāng)由程序開(kāi)發(fā)者來(lái)完成 B程序經(jīng)調(diào)試后一般不需要再測(cè)試 C軟件愛(ài)護(hù)只包括對(duì)程序代碼的愛(ài)護(hù) D以上三種說(shuō)法都不對(duì) 答案： D二、填空題 每空 2 分,共 40 分 2 在面對(duì)對(duì)象方法中, 【 2】描述的是具有相像屬性

49、與操作的一組對(duì)象；答案：類(lèi) 4 程序測(cè)試分為靜態(tài)分析和動(dòng)態(tài)測(cè)試；其中【4】是指不執(zhí)行程序,而只是對(duì)程序文本進(jìn)行檢查,通過(guò)閱讀和爭(zhēng)論,分析和發(fā)覺(jué)程序中的錯(cuò)誤；答案：靜態(tài)分析2022-9 月一、挑選題（每題 2 分,共計(jì) 70 分）1. 以下選項(xiàng)中不符合良好程序設(shè)計(jì)風(fēng)格的是 _；A）源程序要文檔化 B）數(shù)據(jù)說(shuō)明的次序要規(guī)范化C）防止濫用goto 語(yǔ)句D）模塊設(shè)計(jì)要保證高耦合、高內(nèi)聚答案： D2. 從工程治理角度,軟件設(shè)計(jì)一般分為兩步完成,它們是 _；A）概要設(shè)計(jì)與具體設(shè)計(jì) B）數(shù)據(jù)設(shè)計(jì)與接口設(shè)計(jì)C）軟件結(jié)構(gòu)設(shè)計(jì)與數(shù)據(jù)設(shè)計(jì) D）過(guò)程設(shè)計(jì)與數(shù)據(jù)設(shè)計(jì)答案： A3. 以下選項(xiàng)中不屬于軟件生命周期開(kāi)發(fā)階段任

50、務(wù)的是 _；A）軟件測(cè)試 B）概要設(shè)計(jì) C）軟件愛(ài)護(hù) D）具體設(shè)計(jì)答案： C二、填空題（每空 2 分,共計(jì) 30 分）（1）以下軟件系統(tǒng)結(jié)構(gòu)圖TBCDE F的寬度為【1】答案： 3（2）【2】的任務(wù)是診斷和改正程序中的錯(cuò)誤；答案：程序調(diào)試2022-4一、挑選題 （1）（ 10）每道題 2 分,（ 11）（ 50）每題 1 分,共 60 分 2 在結(jié)構(gòu)化程序設(shè)計(jì)中,模塊劃分的原就是 D A各模塊應(yīng)包括盡量多的功能 B各模塊的規(guī)模應(yīng)盡量大 C各模塊之間的聯(lián)系應(yīng)盡量緊密 D模塊內(nèi)具有高內(nèi)聚度、模塊間具有低耦合度 答案： D3 以下表達(dá)中正確選項(xiàng) A A軟件測(cè)試的主要目的是發(fā)覺(jué)程序中的錯(cuò)誤 B軟件測(cè)試

51、的主要目的是確定程序中錯(cuò)誤的位置 C為了提高軟件測(cè)試的效率,最好由程序編制者自己來(lái)完成軟件測(cè)試的工作 D軟件測(cè)試是證明軟件沒(méi)有錯(cuò)誤 答案： A4 下面選項(xiàng)中不屬于面對(duì)對(duì)象程序設(shè)計(jì)特點(diǎn)的是 C A繼承性 B 多態(tài)性 C 類(lèi)比性 D 封裝性答案： C二填空題（每空 2 分,共 40 分）（2）軟件測(cè)試分為白箱（盒）測(cè)試和黑箱（盒）測(cè)試,等價(jià)類(lèi)劃分法屬于 測(cè) 試；答案：黑箱或黑盒（4）軟件生命周期可分為多個(gè)階段,一般分為定義階段、開(kāi)發(fā)階段和愛(ài)護(hù)階段；編碼和測(cè)試屬于 _ 階段；答案：開(kāi)發(fā)2022-9一、挑選題 1-10每題 2 分, 11-50每題 1 分. 共 60 分以下各題 A、B 、C、D四個(gè)

52、選項(xiàng)中,只有一個(gè)是正確的,請(qǐng)將正確選項(xiàng)涂寫(xiě)在答題卡上,答在試卷上不得分；（1）軟件是指 A）程序 B ）程序和文檔C）算法加數(shù)據(jù)結(jié)構(gòu) 答案： D D）程序、數(shù)據(jù)和相關(guān)文檔的集合（2）軟件調(diào)試的目的是A）發(fā)覺(jué)錯(cuò)誤 B ）改正錯(cuò)誤C）改善軟件的性能 D）驗(yàn)證軟件的正確性答案： B（3）在面對(duì)對(duì)象方法中,實(shí)現(xiàn)信息隱藏是依靠A）對(duì)象的繼承 B ）對(duì)象的多態(tài)C）對(duì)象的封裝 D）對(duì)象的分類(lèi)答案： C（4）以下表達(dá)中,不符合良好程序設(shè)計(jì)風(fēng)格的是A）程序的效率第一,清晰其次 B ）程序的可讀性好C）程序中有必要的注釋 答案： A D）輸入數(shù)據(jù)前要有提示信息二、填空題 每空 2 分, 共 40 分請(qǐng)將每一個(gè)空的

53、正確答案寫(xiě)在答題卡1 至 20 序號(hào)的橫線上 , 答在試卷上不得分.1 軟件需求規(guī)格說(shuō)明書(shū)應(yīng)具有完整性、無(wú)歧義性、正確性、可驗(yàn)證性、可修改性等特性,其中最重要的 _1_. 無(wú)歧義性 測(cè)試的原就之一是保證所測(cè)模塊中每一個(gè)獨(dú)立路2 在兩種基本測(cè)試方法中, _2_徑至少要執(zhí)行一次. 白盒 四、數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ) 1. 數(shù)據(jù)庫(kù)的基本概念：數(shù)據(jù)庫(kù),數(shù)據(jù)庫(kù)治理系統(tǒng),數(shù)據(jù)庫(kù)系統(tǒng)；2. 數(shù)據(jù)模型,實(shí)體聯(lián)系模型及ER 圖,從ER 圖導(dǎo)出關(guān)系數(shù)據(jù)模型；3. 關(guān)系代數(shù)運(yùn)算,包括集合運(yùn)算及挑選、投影、連接運(yùn)算,數(shù)據(jù)庫(kù)規(guī)范化理論；4. 數(shù)據(jù)庫(kù)設(shè)計(jì)方法和步驟：需求分析、概念設(shè)計(jì)、規(guī)律設(shè)計(jì)和物理設(shè)計(jì)的相關(guān)策略；2022 年 4

54、 一、挑選題（ （1）（ 10）每道題 2 分,（11）（ 50）每道題 1 分,共 60 分）（ 9）數(shù)據(jù)獨(dú)立性是數(shù)據(jù)庫(kù)技術(shù)的重要特點(diǎn)之一,所謂數(shù)據(jù)獨(dú)立性是指 _；A）數(shù)據(jù)與程序獨(dú)立存放 B）不同的數(shù)據(jù)被存放在不同的文件中 C）不同的數(shù)據(jù)只能被對(duì)應(yīng)的應(yīng)用程序所使用 D）以上三種說(shuō)法都不對(duì) 答案： D 數(shù)據(jù)的獨(dú)立性是指應(yīng)用程序和數(shù)據(jù)庫(kù)的數(shù)據(jù)結(jié)構(gòu)之間相互獨(dú)立,不受影響；（10）用樹(shù)形結(jié)構(gòu)表示實(shí)體之間聯(lián)系的模型是 _；A）關(guān)系模型 B）網(wǎng)狀模型 C）層次模型 D）以上三個(gè)都是 答案： C二、填空題（每空 2 分,共 40 分（4）在關(guān)系數(shù)據(jù)庫(kù)中,把數(shù)據(jù)表示成二維表,每一個(gè)二維表稱(chēng)為【4】 ；答案：

55、關(guān)系 2022 年 9 月 一、挑選題（ （1）（ 10）每題 2 分,（ 11）（ 50）每題 1 分,共 60 分）（8）數(shù)據(jù)庫(kù)設(shè)計(jì)的根本目標(biāo)是要解決 A ）數(shù)據(jù)共享問(wèn)題 B ）數(shù)據(jù)安全問(wèn)題 C）大量數(shù)據(jù)儲(chǔ)備問(wèn)題 D）簡(jiǎn)化數(shù)據(jù)愛(ài)護(hù) 答案： A 一般數(shù)據(jù)庫(kù)是長(zhǎng)期儲(chǔ)備在運(yùn)算機(jī)內(nèi)有組織的可共享的數(shù)據(jù)集合（9）設(shè)有如下關(guān)系表 : R S T A B C A B C A B C 1 1 2 3 1 3 1 1 2 2 2 3 2 2 3 3 1 3 就以下操作中正確選項(xiàng)A） TRS B） TRS C ）TR S D）TR/S答案： B（10）數(shù)據(jù)庫(kù)系統(tǒng)的核心是 A ）數(shù)據(jù)模型 B）數(shù)據(jù)庫(kù)治理系統(tǒng) 答案： B C）數(shù)據(jù)庫(kù) D）數(shù)據(jù)庫(kù)治理員二、填空題（每空 2 分,共 40 分）（1）數(shù)據(jù)治理技術(shù)進(jìn)展過(guò)程經(jīng)過(guò)人工治理、文件系統(tǒng)和數(shù)據(jù)庫(kù)系統(tǒng)三個(gè)階段,其中數(shù)據(jù)獨(dú)立性最高的階段是【 1】 ；答