計(jì)算機(jī)二級(jí)基礎(chǔ)知識(shí)

計(jì)算機(jī)二級(jí)基礎(chǔ)知識(shí)第一頁(yè)，共五十二頁(yè)，編輯于2023年，星期五目錄數(shù)據(jù)結(jié)構(gòu)1軟件工程2數(shù)據(jù)庫(kù)基礎(chǔ)3第二頁(yè)，共五十二頁(yè)，編輯于2023年，星期五線性表線性表

線性表簡(jiǎn)稱為表，是零個(gè)或多個(gè)元素的有窮序列，通?？梢员硎境蒶0，k1，…，kn-1（n>=1）.

順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)第三頁(yè)，共五十二頁(yè)，編輯于2023年，星期五線性表單鏈表與順序表的比較：?jiǎn)捂湵淼拇鎯?chǔ)密度比順序表低，它多占用了存儲(chǔ)空間：存儲(chǔ)密度=數(shù)據(jù)本身所占的存儲(chǔ)量/整個(gè)數(shù)據(jù)結(jié)構(gòu)所占的存儲(chǔ)量。在單鏈表里進(jìn)行插入、刪除運(yùn)算比在順序表中容易得多。對(duì)于順序表，可隨機(jī)訪問(wèn)任一元素，而在單鏈表中，需要順著鏈逐個(gè)進(jìn)行查找，因此單鏈表適合成批地、順序地處理線性表中的元素時(shí)使用。

第四頁(yè)，共五十二頁(yè)，編輯于2023年，星期五1.下列敘述中正確的是：A.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)所需的存儲(chǔ)空間是相同的B.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間一般要多于順序存儲(chǔ)結(jié)構(gòu)C.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需要的存儲(chǔ)空間一般要少于順序存儲(chǔ)結(jié)構(gòu)D.以上三種說(shuō)法都不正確第五頁(yè)，共五十二頁(yè)，編輯于2023年，星期五棧定義：棧是一種特殊的線性表，對(duì)于它所有的插入和刪除都限制在表的同一端進(jìn)行。表中允許進(jìn)行操作的一端交棧頂，另一端叫棧底。沒(méi)有元素的棧叫空棧。特征：先進(jìn)后出。第六頁(yè)，共五十二頁(yè)，編輯于2023年，星期五隊(duì)列定義：隊(duì)列是一種特殊的線性表，是一種只允許在表的一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表。允許刪除的一端叫隊(duì)列的頭，允許插入的一端叫做隊(duì)列的尾。沒(méi)有元素的叫空隊(duì)列。特征：先進(jìn)先出。第七頁(yè)，共五十二頁(yè)，編輯于2023年，星期五2.下列敘述中正確的是A.棧是“先進(jìn)先出”的線性表B.隊(duì)列是“先進(jìn)后出”的線性表C.循環(huán)隊(duì)列是非線性結(jié)構(gòu)D.有序線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)第八頁(yè)，共五十二頁(yè)，編輯于2023年，星期五3.下列敘述中正確的是A.在棧中，棧中元素隨棧底指針與棧頂指針的變化而動(dòng)態(tài)變化B.在棧中，棧頂指針不變，棧中元素隨棧底指針的變化而動(dòng)態(tài)變化C.在棧中，棧底指針不變，棧中元素隨棧頂指針的變化而變化D.上述三種說(shuō)法都不對(duì)第九頁(yè)，共五十二頁(yè)，編輯于2023年，星期五樹(shù)與樹(shù)林樹(shù)是包括n（n≥0）個(gè)結(jié)點(diǎn)的有窮集合T，當(dāng)T非空時(shí)滿足：有且僅有一個(gè)特別標(biāo)出的稱作根的結(jié)點(diǎn)。除根結(jié)點(diǎn)之外，其余結(jié)點(diǎn)分為m≥0個(gè)不相交的非空集合T1，T2，…，Tm，而這些集合中的每一個(gè)又都是樹(shù)。樹(shù)都稱作這個(gè)根結(jié)點(diǎn)的子樹(shù)。第十頁(yè)，共五十二頁(yè)，編輯于2023年，星期五樹(shù)與樹(shù)林基本術(shù)語(yǔ)父結(jié)點(diǎn)、子結(jié)點(diǎn)、邊兄弟祖先、子孫路徑、路徑長(zhǎng)度結(jié)點(diǎn)的層數(shù)樹(shù)的深度或高度第十一頁(yè)，共五十二頁(yè)，編輯于2023年，星期五樹(shù)的周游按深度方向周游先根次序中根次序后根次序按寬度方向周游第十二頁(yè)，共五十二頁(yè)，編輯于2023年，星期五二叉樹(shù)二叉樹(shù)可以定義為結(jié)點(diǎn)的有限集合，這個(gè)集合或者為空集，或者由一個(gè)根及兩棵不相交的分別稱作這個(gè)根的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。第十三頁(yè)，共五十二頁(yè)，編輯于2023年，星期五二叉樹(shù)二叉樹(shù)不是樹(shù)的特例樹(shù)和二叉樹(shù)的主要差別：二叉樹(shù)中結(jié)點(diǎn)的子樹(shù)要區(qū)分左子樹(shù)和右子樹(shù)即使在結(jié)點(diǎn)只有一棵子樹(shù)的情況下也要明確指出該子樹(shù)是左子樹(shù)還是右子樹(shù)第十四頁(yè)，共五十二頁(yè)，編輯于2023年，星期五滿二叉樹(shù)如果一棵深度為k的二叉樹(shù)，當(dāng)其結(jié)點(diǎn)數(shù)目為2k+1-1則稱之為滿二叉樹(shù)。第十五頁(yè)，共五十二頁(yè)，編輯于2023年，星期五完全二叉樹(shù)如果一個(gè)深度為k的二叉樹(shù)，其所有結(jié)點(diǎn)按層次編號(hào)，其所有結(jié)點(diǎn)的編號(hào)都與相同深度的滿二叉樹(shù)的編號(hào)位置相同，則稱之為完全二叉樹(shù)滿二叉樹(shù)一定是完全二叉樹(shù)完全二叉樹(shù)不一定是滿二叉樹(shù)第十六頁(yè)，共五十二頁(yè)，編輯于2023年，星期五二叉樹(shù)的性質(zhì)性質(zhì)1在非空二叉樹(shù)的i層上至多有2i個(gè)結(jié)點(diǎn)（i≥0）性質(zhì)2深度為k的二叉樹(shù)中最多有2k+1-1個(gè)結(jié)點(diǎn)（k≥0）性質(zhì)3對(duì)于任何一棵非空的二叉樹(shù)，如果葉節(jié)點(diǎn)個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，則有n0=n2+1性質(zhì)4具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度k為第十七頁(yè)，共五十二頁(yè)，編輯于2023年，星期五4.某二叉樹(shù)有5個(gè)度為2的結(jié)點(diǎn)，則該二叉樹(shù)中的葉子結(jié)點(diǎn)數(shù)是A.10B.8C.6D.4第十八頁(yè)，共五十二頁(yè)，編輯于2023年，星期五5.支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是A.棧B.樹(shù)C.隊(duì)列D.二叉樹(shù)第十九頁(yè)，共五十二頁(yè)，編輯于2023年，星期五排序插入排序直接插入排序（簡(jiǎn)單插入排序）簡(jiǎn)單插入排序是最簡(jiǎn)單直觀的排序方法。其基本方法是：把n個(gè)待排序的元素看成為一個(gè)有序表和一個(gè)無(wú)序表，開(kāi)始時(shí)有序表中只包含一個(gè)元素，無(wú)序表中包含n-1個(gè)元素，排序過(guò)程中每次從無(wú)序表中取出第一個(gè)元素，把它的依次與有序表中的元素進(jìn)行比較，將其插入到有序表的適當(dāng)位置，使之成為新的有序表。在最壞的情況下，簡(jiǎn)單插入排序需要為次比較n(n-1)/2。Shell排序

在最壞情況下，希爾排序所需要的比較次數(shù)為。第二十頁(yè)，共五十二頁(yè)，編輯于2023年，星期五排序選擇排序法簡(jiǎn)單選擇排序法簡(jiǎn)單選擇排序的方法：從整個(gè)數(shù)據(jù)元素中選出最小的元素，將其交換到前面（應(yīng)放的位置），對(duì)剩下的數(shù)據(jù)元素采用同樣的方法，直到?jīng)]有可交換元素。在最壞情況下，選擇排序所需要的比較次數(shù)為n(n-1)/2。堆排序堆排序法屬于選擇類的排序方法。在最壞情況下，堆排序所需要的比較次數(shù)為。第二十一頁(yè)，共五十二頁(yè)，編輯于2023年，星期五排序交換排序法冒泡排序冒泡排序法是一種最簡(jiǎn)單的交換類排序方法，通過(guò)相鄰數(shù)據(jù)元素的交換逐步將序列變成有序的。在最壞情況下，冒泡排序所需要的比較次數(shù)為n(n-1)/2?？焖倥判蚩焖倥判蚍▽儆诮粨Q類排序法。在最壞情況下，快速排序所需要的比較次數(shù)為n(n-1)/2。第二十二頁(yè)，共五十二頁(yè)，編輯于2023年，星期五排序排序的最壞比較次數(shù)排序方式時(shí)間復(fù)雜度排序方式時(shí)間復(fù)雜度直接插入法O(n2)堆排序Shell法O（n1.5）冒泡排序O(n2)簡(jiǎn)單選擇法O(n2)快速排序O(n2)第二十三頁(yè)，共五十二頁(yè)，編輯于2023年，星期五6.下列排序方法中，最壞情況下比較次數(shù)較少的是：A.冒泡排序B.簡(jiǎn)單選擇排序C.直接插入排序D.堆排序第二十四頁(yè)，共五十二頁(yè)，編輯于2023年，星期五支撐軟件支撐軟件是支撐各種軟件的開(kāi)發(fā)與維護(hù)的軟件，又稱為軟件開(kāi)發(fā)環(huán)境。它主要包括環(huán)境數(shù)據(jù)庫(kù)、各種接口軟件和工具組。

第二十五頁(yè)，共五十二頁(yè)，編輯于2023年，星期五7.軟件按功能可以分為：應(yīng)用軟件、系統(tǒng)軟件和支撐軟件（或工具軟件）。下面屬于應(yīng)用軟件的是：A.編譯程序B.操作系統(tǒng)C.教務(wù)管理系統(tǒng)D.匯編程序第二十六頁(yè)，共五十二頁(yè)，編輯于2023年，星期五軟件危機(jī)軟件危機(jī)是指在計(jì)算機(jī)軟件的開(kāi)發(fā)和維護(hù)過(guò)程中所遇到的一系列嚴(yán)重問(wèn)題。它包含兩個(gè)方面的問(wèn)題：1.如何開(kāi)發(fā)軟件，以滿足對(duì)軟件日益增長(zhǎng)的需求。2.如何維護(hù)數(shù)量不斷膨脹的已有軟件。第二十七頁(yè)，共五十二頁(yè)，編輯于2023年，星期五軟件危機(jī)典型表現(xiàn)：1.對(duì)軟件開(kāi)發(fā)成本和進(jìn)度估計(jì)常常很不準(zhǔn)確。2.用戶對(duì)“已完成的”軟件系統(tǒng)部不滿意的現(xiàn)象經(jīng)常發(fā)生。3.軟件產(chǎn)品的質(zhì)量往往靠不住。4.軟件常常是不可維護(hù)的。5.軟件通常沒(méi)有適當(dāng)?shù)奈臋n資料。6.軟件成本在計(jì)算機(jī)系統(tǒng)總成本中所占的比例逐年上升。7.軟件開(kāi)發(fā)生產(chǎn)率提高的速度，遠(yuǎn)遠(yuǎn)跟不上計(jì)算機(jī)應(yīng)用迅速普及深入的趨勢(shì)。第二十八頁(yè)，共五十二頁(yè)，編輯于2023年，星期五8.下面描述中，不屬于軟件危機(jī)表現(xiàn)的是：A.軟件過(guò)程不規(guī)范B.軟件開(kāi)發(fā)生產(chǎn)率低C.軟件質(zhì)量難以控制D.軟件成本不斷提高第二十九頁(yè)，共五十二頁(yè)，編輯于2023年，星期五軟件生命周期軟件生命周期有軟件定義、軟件開(kāi)發(fā)和運(yùn)行維護(hù)（也稱軟件維護(hù)）3個(gè)時(shí)期組成。其中，每個(gè)時(shí)期又進(jìn)一步劃分成若干個(gè)階段。

第三十頁(yè)，共五十二頁(yè)，編輯于2023年，星期五9.軟件的生命周期是指：A.軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過(guò)程B.軟件從需求分析、設(shè)計(jì)、實(shí)現(xiàn)到測(cè)試完成的過(guò)程C.軟件開(kāi)發(fā)過(guò)程D.軟件的運(yùn)行維護(hù)過(guò)程第三十一頁(yè)，共五十二頁(yè)，編輯于2023年，星期五耦合性與內(nèi)聚性耦合性耦合性是程序結(jié)構(gòu)中各個(gè)模塊之間相互關(guān)聯(lián)的度量。它取決于各個(gè)模塊之間接口的復(fù)雜程度、調(diào)用模塊的方式以及哪些信息通過(guò)接口。

內(nèi)聚性又稱為塊內(nèi)聯(lián)系，指模塊的功能強(qiáng)度的度量，即一個(gè)模塊內(nèi)部各個(gè)元素彼此結(jié)合的緊密程度的度量。第三十二頁(yè)，共五十二頁(yè)，編輯于2023年，星期五10.耦合性和內(nèi)聚性是對(duì)模塊獨(dú)立性度量的兩個(gè)標(biāo)準(zhǔn)。下列敘述正確的是：A.提高耦合性降低內(nèi)聚性有利于提高模塊的獨(dú)立性B.降低耦合性提高內(nèi)聚性有利于提高模塊的獨(dú)立性C.耦合性是指一個(gè)模塊內(nèi)部各個(gè)元素間彼此結(jié)合的緊密程度D.內(nèi)聚性是指模塊間互相連接的緊密程度第三十三頁(yè)，共五十二頁(yè)，編輯于2023年，星期五軟件測(cè)試軟件測(cè)試的目的測(cè)試是為了發(fā)現(xiàn)程序中的錯(cuò)誤而執(zhí)行程序的過(guò)程。好的測(cè)試方案是極可能發(fā)現(xiàn)迄今為止尚未發(fā)現(xiàn)的錯(cuò)誤的測(cè)試方案。成功的測(cè)試是發(fā)現(xiàn)了迄今為止尚未發(fā)現(xiàn)的錯(cuò)誤的測(cè)試。第三十四頁(yè)，共五十二頁(yè)，編輯于2023年，星期五11.軟件測(cè)試的目的是：A.評(píng)估軟件的可靠性B.發(fā)現(xiàn)并改正程序中的錯(cuò)誤C.改正程序中的錯(cuò)誤D.發(fā)現(xiàn)程序中的錯(cuò)誤第三十五頁(yè)，共五十二頁(yè)，編輯于2023年，星期五12.下面敘述中錯(cuò)誤的是：A.軟件測(cè)試的目的是發(fā)現(xiàn)錯(cuò)誤并改正錯(cuò)誤B.對(duì)被調(diào)試的程序進(jìn)行“錯(cuò)誤定位”是程序調(diào)試的必要步驟C.程序調(diào)試通常也成為DebugD.軟件測(cè)試應(yīng)嚴(yán)格執(zhí)行測(cè)試計(jì)劃，排除測(cè)試的隨意性第三十六頁(yè)，共五十二頁(yè)，編輯于2023年，星期五白盒測(cè)試與黑盒測(cè)試黑盒測(cè)試又稱功能測(cè)試，它把程序看做一個(gè)黑盒子，完全不考慮程序的內(nèi)部結(jié)構(gòu)和處理過(guò)程。即，只檢查程序的功能是否按照功能說(shuō)明書(shū)的規(guī)定正常運(yùn)行。

白盒測(cè)試又稱結(jié)構(gòu)測(cè)試，它將程序看成一個(gè)透明的白盒子，按照程序內(nèi)部的邏輯測(cè)試程序，檢測(cè)程序中的主要執(zhí)行通路是否都能按預(yù)定的要求工作。第三十七頁(yè)，共五十二頁(yè)，編輯于2023年，星期五實(shí)體-聯(lián)系圖（E-R圖）方框表示數(shù)據(jù)對(duì)象，圓角矩形表示數(shù)據(jù)對(duì)象的屬性，菱形表示“聯(lián)系”。聯(lián)系：一對(duì)一、一對(duì)多、多對(duì)多第三十八頁(yè)，共五十二頁(yè)，編輯于2023年，星期五13.一個(gè)工作人員可以使用多臺(tái)計(jì)算機(jī)，而一臺(tái)計(jì)算機(jī)可被多個(gè)人使用，則實(shí)體工作人員與實(shí)體計(jì)算機(jī)之間的聯(lián)系是：A.一對(duì)一B.一對(duì)多C.多對(duì)多D.多對(duì)一第三十九頁(yè)，共五十二頁(yè)，編輯于2023年，星期五數(shù)據(jù)模型層次型網(wǎng)狀型關(guān)系型二維表它們之間的劃分原則是數(shù)據(jù)之間的聯(lián)系方式。第四十頁(yè)，共五十二頁(yè)，編輯于2023年，星期五14.將E-R圖轉(zhuǎn)換為關(guān)系模式時(shí)，實(shí)體和聯(lián)系都可以表示為：A.屬性B.鍵C.關(guān)系D.域第四十一頁(yè)，共五十二頁(yè)，編輯于2023年，星期五15.層次型、網(wǎng)狀型和關(guān)系型數(shù)據(jù)庫(kù)劃分原則是：A.記錄長(zhǎng)度B.文件的大小C.聯(lián)系的復(fù)雜程度D.數(shù)據(jù)之間的聯(lián)系方式第四十二頁(yè)，共五十二頁(yè)，編輯于2023年，星期五數(shù)據(jù)庫(kù)三級(jí)模式模式模式又稱為概念模式或邏輯模式，對(duì)應(yīng)于概念級(jí)。它是由數(shù)據(jù)庫(kù)設(shè)計(jì)者綜合所有用戶的數(shù)據(jù)，按照統(tǒng)一的觀點(diǎn)構(gòu)造的全局邏輯結(jié)構(gòu)，是對(duì)數(shù)據(jù)庫(kù)中全部數(shù)據(jù)的邏輯結(jié)構(gòu)和特征的總體描述，是所有用戶的公共視圖（全局視圖）。體現(xiàn)、反映數(shù)據(jù)庫(kù)的整體觀。第四十三頁(yè)，共五十二頁(yè)，編輯于2023年，星期五數(shù)據(jù)庫(kù)三級(jí)模式外模式外模式又稱子模式，對(duì)應(yīng)于用戶級(jí)。它是某個(gè)或某幾個(gè)用戶所看到的數(shù)據(jù)庫(kù)的數(shù)據(jù)試圖，是與某一應(yīng)用有關(guān)的數(shù)據(jù)的邏輯表示。它反映數(shù)據(jù)庫(kù)的用戶觀。內(nèi)模式內(nèi)模式又稱存儲(chǔ)模式，對(duì)應(yīng)于物理級(jí)，它是數(shù)據(jù)庫(kù)的存儲(chǔ)觀。第四十四頁(yè)，共五十二頁(yè)，編輯于2023年，星期五16.數(shù)據(jù)庫(kù)設(shè)計(jì)中反映用戶對(duì)數(shù)據(jù)要求的模式是：A.內(nèi)模式B.概念模式C.外模式D.設(shè)計(jì)模式第四十五頁(yè)，共五十二頁(yè)，編輯于2023年，星期五關(guān)系運(yùn)算專門的關(guān)系運(yùn)算選擇投影第四十六頁(yè)，共五十二頁(yè)，編輯于2023年，星期五關(guān)系運(yùn)算連接R：

S：等值連接自然連接R:

S:除連接運(yùn)算第四十七頁(yè)，共五十二頁(yè)，編輯于2023年，星期五17.有兩個(gè)關(guān)系R，S如下：

RS

由關(guān)系R通過(guò)運(yùn)算