公共基礎(chǔ)知識

全國計(jì)算機(jī)二級考試公共基礎(chǔ)知識第1頁公共基礎(chǔ)知識考試范圍單選2*10=20分，填空2*5=10分，共30分?jǐn)?shù)據(jù)構(gòu)造與算法程序設(shè)計(jì)基礎(chǔ)軟件工程基礎(chǔ)數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)第2頁算法算法：解題方案精確而完整描述。5個(gè)特性：有窮性：算法執(zhí)行有時(shí)間限制，不能無限制執(zhí)行確定性：不能有二義性可行性:有輸入：一種算法應(yīng)有零個(gè)或多種輸入。有輸出：一定要有一種或多種輸出。a=4/0第3頁算法特性算法有窮性是指（）。（2023年4月）A）算法程序運(yùn)行時(shí)間是有限B）算法程序所處理數(shù)據(jù)量是有限C）算法程序長度是有限D(zhuǎn)）算法只能被有限顧客使用A第4頁算法復(fù)雜度p5算法時(shí)間復(fù)雜度：執(zhí)行算法所需要計(jì)算工作量。算法時(shí)間復(fù)雜度是指（）。A）執(zhí)行算法程序所需要時(shí)間B）算法程序長度C）算法執(zhí)行過程中所需要基本運(yùn)算次數(shù)D）算法程序中指令數(shù)C第5頁算法空間復(fù)雜度算法空間復(fù)雜度：執(zhí)行算法所需要內(nèi)存空間。算法空間復(fù)雜度是指（）（2023年9月）A）算法在執(zhí)行過程中所需要計(jì)算機(jī)存放空間B）算法所處理數(shù)據(jù)量C）算法程序中語句或指令條數(shù)D）算法在執(zhí)行過程中所需要臨時(shí)工作單元數(shù)A第6頁1.2數(shù)據(jù)構(gòu)造p7數(shù)據(jù)構(gòu)造+算法=程序數(shù)據(jù)構(gòu)造是指數(shù)據(jù)元素集合及數(shù)據(jù)元素之間關(guān)系集合。其邏輯構(gòu)造有4種：（a）集合構(gòu)造（b）線性構(gòu)造（c）樹型構(gòu)造

（d）圖狀構(gòu)造一對一一對多多對多非線性第7頁數(shù)據(jù)構(gòu)造存放概念：數(shù)據(jù)邏輯構(gòu)造在計(jì)算機(jī)中存放表達(dá)分類：次序存放鏈?zhǔn)酱娣诺?頁線性表兩種存放方式線性表次序存放：線性表中所有元素所占存放空間是連續(xù)線性表中各數(shù)據(jù)元素在存放空間中是按邏輯次序次序放12354地址：100101102第9頁線性表兩種存放方式15∧H…2線性表鏈?zhǔn)酱娣牛哼壿嬌舷噜弮蓚€(gè)數(shù)據(jù)元素存放位置上不一定相鄰。注意：鏈?zhǔn)綐?gòu)造通過一種鏈連接到下一種元素次序存放和鏈?zhǔn)酱娣拍軌虮磉_(dá)線性、非線性構(gòu)造地址：100300300第10頁次序存放和鏈?zhǔn)酱娣畔铝姓撌鲋姓_是（）（2023年9月）A）次序存放構(gòu)造存放一定是連續(xù)，鏈?zhǔn)酱娣艠?gòu)造存放空間不一定是連續(xù)B）次序存放構(gòu)造只針對線性構(gòu)造，鏈?zhǔn)酱娣艠?gòu)造只針對非線性構(gòu)造C）次序存放構(gòu)造能存放有序表，鏈?zhǔn)酱娣艠?gòu)造不能存放有序表D）鏈?zhǔn)酱娣艠?gòu)造比次序存放構(gòu)造節(jié)省存放空間A第11頁1.4線性表——棧和隊(duì)列P19-20棧——先進(jìn)后出表。棧頂top入棧出棧棧底bottom

進(jìn)：a1,a2,a3a1a2a3出：a3,a2,a1操作受限制：只能從棧頂插入，只能從棧頂刪除第12頁棧1、一種棧初始狀態(tài)為空。現(xiàn)將元素1、2、3、4、5、A、B、C、D、E依次入棧，然后再依次出棧，則元素出棧次序是（）。（2023年9月）A）12345ABCDEB）EDCBA54321C）ABCDE12345D）54321EDCBA2、棧底至棧頂依次寄存元素A、B、C、D，在第五個(gè)元素E入棧前，棧中元素能夠出棧，則出棧序列也許是()ABCEDB.DBCEAC.CDABED.DCBEA

BD第13頁棧假設(shè)用一種長度為50數(shù)組(數(shù)組元素下標(biāo)從0到49)作為棧存放空間，棧底指針bottom指向棧底元素，棧頂指針top指向棧頂元素，假如bottom=49，top=30(數(shù)組下標(biāo))，則棧中具有

個(gè)元素。（2023年3月）20…p…a03049bottomtop第14頁隊(duì)列21隊(duì)列——先進(jìn)先出入隊(duì)出隊(duì)隊(duì)頭標(biāo)志front指向隊(duì)頭元素前一種；隊(duì)尾標(biāo)志rear指向最后一種元素。隊(duì)頭出，隊(duì)尾進(jìn)ABCfrontrearD012345隊(duì)列長度=rear-front第15頁54331092循環(huán)隊(duì)列p22CBA…rear循環(huán)隊(duì)列front隊(duì)頭標(biāo)志front指向隊(duì)頭元素前一種；隊(duì)尾標(biāo)志rear指向最后一種元素。隊(duì)頭出，隊(duì)尾進(jìn)設(shè)某循環(huán)隊(duì)列容量為50，頭指針front=5（指向隊(duì)頭元素前一位置），尾指針rear=29（指向隊(duì)尾元素），則該循環(huán)隊(duì)列中共有個(gè)元素。（2023年4月）24第16頁循環(huán)隊(duì)列對于循環(huán)隊(duì)列，下列論述中正確是()。（2023年9月）A）隊(duì)頭指針是固定不變B）隊(duì)頭指針一定大于隊(duì)尾指針C）隊(duì)頭指針一定不大于隊(duì)尾指針D）隊(duì)頭指針能夠大于隊(duì)尾指針，也能夠不大于隊(duì)尾指針D第17頁二叉樹P34結(jié)點(diǎn)度：結(jié)點(diǎn)所擁有孩子個(gè)數(shù)稱為該結(jié)點(diǎn)度。葉結(jié)點(diǎn)：度為0結(jié)點(diǎn)稱為葉結(jié)點(diǎn)，或者稱為終端結(jié)點(diǎn)。分枝結(jié)點(diǎn)：度不為0結(jié)點(diǎn)稱為分支結(jié)點(diǎn)，或者稱為非終端結(jié)點(diǎn)。一棵樹結(jié)點(diǎn)除葉結(jié)點(diǎn)外，其他都是分支結(jié)點(diǎn)。左孩子、右孩子、雙親、弟兄。祖先、子孫。結(jié)點(diǎn)層數(shù)（深度）ABCEDFIGH第1層第2層第3層第4層第18頁二叉樹性質(zhì)34性質(zhì)1一棵非空二叉樹第k層上最多有個(gè)結(jié)點(diǎn)（i≥1）。性質(zhì)2一棵深度為k二叉樹中，最多具有個(gè)結(jié)點(diǎn)。2k﹣12k﹣1ABCEDFIHKGJLMNO第19頁二叉樹性質(zhì)34性質(zhì)3對于一棵非空二叉樹，假如葉子結(jié)點(diǎn)數(shù)為n0，度數(shù)為2結(jié)點(diǎn)數(shù)為n2，則有：n0＝n2＋1。ABCEDFIGH證明：1、入枝：除了根結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)有一種入枝，假設(shè)有分支個(gè)數(shù)為m，總結(jié)點(diǎn)個(gè)數(shù)為n，n和m關(guān)系是：2、出支：度為2有2個(gè)出枝，度為1有1個(gè)出枝，度為0沒有出枝，因此m=2*n2+n1m=n-1即m=n2+n1+n0-13、n2+n1+n0-1=2*n2+n1得n0=n2+1第20頁二叉樹特性例1：某二叉樹有5個(gè)度為2結(jié)點(diǎn)以及3個(gè)度為1結(jié)點(diǎn)，則該二叉樹中共有個(gè)結(jié)點(diǎn)。（2023年9月）【解析】：度為2：5個(gè)，度為1：3，度為0：6；一共5+3+6=14例2：深度為5滿二叉樹有個(gè)葉子結(jié)點(diǎn)（2023年4月）

【解析】：滿二叉樹第5層上有25-1個(gè)結(jié)點(diǎn)。1416第21頁二叉樹35滿二叉樹完全二叉樹ABCEDFIHKGJLMNOABCEDFIHGJ××第22頁二叉樹性質(zhì)設(shè)完全二叉樹共有n個(gè)結(jié)點(diǎn)，假如從根結(jié)點(diǎn)開始（根k=1），按層排序12354698710編號為k結(jié)點(diǎn)左孩子結(jié)點(diǎn)編號為2k，右孩子結(jié)點(diǎn)編號為2k+1;K父結(jié)點(diǎn)編號為INT(K/2);第23頁二叉樹遍歷P186前序：根左右；中序：左根右；后序：左右根ABDEFZYCX前：ABDEXCFYZ中：DBXEAYFZC后：DXEBYZFCA第24頁已知一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF，則該二叉樹后序遍歷為（）A）GEDHFBCAB）DGEBHFCAC）ABCDEFGHD）ACBFEDHGB根左右第25頁已知一棵二叉樹后序遍歷序列是dabec，中序遍歷序列是debac，則它前序遍歷序列是（）A．a(chǎn)cbedB.decabC.deabcD.cedbaD第26頁已知一棵二叉樹中序遍歷序列是DBEAFC，前序遍歷序列是ABDECF，則它后序遍歷序列是（）第27頁1.7查找技術(shù)p39比較次數(shù)時(shí)間復(fù)雜度次序查找最壞nO(n)次序查找：從頭到尾一種一種找，能夠用于次序表或鏈表。

01234567109820332260533次序查找可用于有序、無序表，可用于次序存放和鏈?zhǔn)酱娣沛湵碇荒苡么涡虿檎业?8頁折半查找：有有序表(3,14,19,20,27,55,72,80,88,92)，查找723141920275572808892↑low=1↑High=10↑mid3141920275572808892↑low↑high↑mid3141920275572808892↑low↑high↑mid3141920275572808892↑low↑high↑mid12345678第29頁1.8排序技術(shù)40交換類排序比較次數(shù)冒泡排序n(n-1)/2迅速排序log2n

插入類排序直接插入排序n(n-1)/2希爾排序n1.5選擇類排序簡單選擇排序n(n-1)/2堆排序nlog2n下列排序辦法中，最壞情況下比較次數(shù)最少是__________。（2023年9月二級C真題）冒泡排序

簡單選擇排序

直接插入排序

堆排序D第30頁程序設(shè)計(jì)基礎(chǔ)（記住基礎(chǔ)概念）481、構(gòu)造化程序設(shè)計(jì)標(biāo)準(zhǔn)：自頂向下，逐漸求精，模塊化，限制使用goto語句。標(biāo)準(zhǔn)：清楚第一、效率第二3大基本構(gòu)造：次序、選擇、循環(huán)2、面向?qū)ο蟪绦蛟O(shè)計(jì)（略）第31頁軟件工程62軟件、軟件危機(jī)、軟件工程定義軟件生命周期：可行性研究、需求分析、軟件設(shè)計(jì)、軟件實(shí)現(xiàn)、軟件測試、運(yùn)行和維護(hù)軟件工程標(biāo)準(zhǔn)：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完整性、可驗(yàn)證性構(gòu)造化分析常用工具：數(shù)據(jù)流圖（DFD）、數(shù)據(jù)字典(DD)等模塊獨(dú)立化：內(nèi)聚性——模塊內(nèi)緊密程度耦合性——模塊間緊密程度

高內(nèi)聚，低耦合第32頁軟件測試86軟件測試辦法：靜態(tài)測試和動(dòng)態(tài)測試白盒測試——構(gòu)造測試、邏輯驅(qū)動(dòng)測試

辦法——邏輯覆蓋、基本途徑測試等黑盒測試——功能測試、數(shù)據(jù)驅(qū)動(dòng)測試

辦法——等價(jià)劃分法、邊界值分析法、因果法等軟件測試實(shí)行：單元測試、集成測試、確認(rèn)測試、系統(tǒng)測試程序調(diào)試第33頁數(shù)據(jù)庫101數(shù)據(jù)——計(jì)算機(jī)中文字、圖形、圖像、聲音等。e.g.一種學(xué)生數(shù)據(jù)學(xué)號姓名性別出生日期1001喜洋洋男1991.1.2數(shù)據(jù)庫——數(shù)據(jù)集合。e.g.多種學(xué)生數(shù)據(jù)學(xué)號姓名性別出生日期1001喜洋洋男1991.1.11002美羊羊女1992.3.31003懶洋洋男1992.5.51004沸羊羊男1990.7.7放在計(jì)算機(jī)內(nèi)存里第34頁數(shù)據(jù)庫應(yīng)用系統(tǒng)（如：教學(xué)管理系統(tǒng)）2、數(shù)據(jù)庫數(shù)據(jù)庫管理系統(tǒng)（如：ACCESS）操作系統(tǒng)（如：WindowsXP）電腦硬件數(shù)據(jù)庫系統(tǒng)存入數(shù)據(jù)（庫）數(shù)據(jù)庫系統(tǒng)關(guān)鍵第35頁數(shù)據(jù)模型數(shù)據(jù)模型——E-R模型（實(shí)體——屬性）課程教師參照書講授編號姓名職稱實(shí)體屬性聯(lián)系第36頁數(shù)據(jù)模型實(shí)體間聯(lián)系分類一對一聯(lián)系(1:1)一對多聯(lián)系(1:M)多對多聯(lián)系(M:N)學(xué)生校長學(xué)校教師課程學(xué)生校長課程學(xué)生校長教師課程學(xué)生正校長一對一一對多多對多多對多第37頁關(guān)系模型：二維表學(xué)號姓名學(xué)院年紀(jì)2023001202300220230032023004張浩然李一明王偉趙堅(jiān)強(qiáng)CPCPEEEE18191820元組/統(tǒng)計(jì)屬性第38頁傳統(tǒng)關(guān)系運(yùn)算ABCa1b1c1a1b2c2a2b2c1RABCa1b2c2a1b3c2a2b2c1S(1)并運(yùn)算：RUSABCa1b1c1a1b2c2a2b2c1a1b3c2(2)差運(yùn)算：R-SR中有，S中沒有ABCa1b1c1(3)差運(yùn)算：R∩SABCa1b2c2a2b2c1第39頁專門關(guān)系運(yùn)算1、選擇：從關(guān)系中找出滿足給定條件元組。(選擇運(yùn)算是在二維表中選擇滿足指定條件行)2、投影：從關(guān)系模式中指定若干屬性組成新關(guān)系。(在