計(jì)算機(jī)復(fù)試-二級(jí)公共基礎(chǔ)知識(shí)

第1考點(diǎn) 算法的基本概考點(diǎn) 算法復(fù)雜運(yùn)行，效率均不同。這表明使用時(shí)間單位衡量算法的效率是不合適的。撇開這些與計(jì)算機(jī)硬件、有關(guān)的因素，可以認(rèn)為一個(gè)特定算法"運(yùn)行工作量"的大小，只依賴于問題的規(guī)模算法的工作量某種數(shù)據(jù)結(jié)構(gòu)所需要的附加空間。如果額外空間量相對(duì)于問題規(guī)模來說是常數(shù)，則稱該算考點(diǎn) 數(shù)據(jù)結(jié)構(gòu)的定數(shù)據(jù)的邏輯結(jié)構(gòu)是對(duì)數(shù)據(jù)元間的邏輯關(guān)系的描述，它可以用一個(gè)數(shù)據(jù)元素的集合和定為D；二是D上的關(guān)系，它反映了數(shù)據(jù)元間的前后件關(guān)系，通常記為R。一個(gè)數(shù)據(jù)結(jié)構(gòu)可以數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)空間中的存放形式稱為數(shù)據(jù)的結(jié)構(gòu)（也稱數(shù)據(jù)的物理構(gòu)由于數(shù)據(jù)元素在計(jì)算機(jī)空間中的位置關(guān)系可能與邏輯關(guān)系不同，因此，為了表示存放僅要存放各數(shù)據(jù)元素的信息，還需要存放各數(shù)據(jù)元間的前后件關(guān)系的信息。一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種結(jié)構(gòu)，常用的結(jié)構(gòu)有順序、、索引等結(jié)構(gòu)。而采用不同的結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。因此，在進(jìn)行數(shù)據(jù)處考點(diǎn) 線性結(jié)構(gòu)與非線性結(jié)考點(diǎn) 棧及其基本運(yùn)為2分，此考點(diǎn)為重點(diǎn)掌握內(nèi)容，讀者應(yīng)該掌握棧的運(yùn)算。棧是限定只在一端進(jìn)行與刪除的線性表，通常稱、刪除的這一端為棧頂，另一端為棧底。當(dāng)表中沒有元素時(shí)稱為空棧。棧頂元素總是后入的元素，從而也是最先被刪除的用一維數(shù)組S（1∶m）作為棧的順序空間，其中m為最大容量入棧運(yùn)算：入棧運(yùn)算是指在棧頂位置一個(gè)新元素。首先將棧頂指針加一（即top1考點(diǎn) 線性鏈表的基本概在鏈?zhǔn)椒绞街?，要求每個(gè)結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù) 考點(diǎn) 樹與二叉樹及其基本性IN（k/2考點(diǎn) 二叉樹的遍子樹時(shí)，仍然先遍歷左子樹，然后根結(jié)點(diǎn)，最后遍歷右子樹。考點(diǎn) 順序查考點(diǎn)10二分法查找考點(diǎn)11交換類排序法在的情況下，冒泡排序需要比較次數(shù)為n（n－1）/2。冒泡排序法的平均執(zhí)行時(shí)間是O（n2），而快速排序法的平均執(zhí)行時(shí)間是O（nlog2n） A）問題的規(guī) B）待處理的數(shù)據(jù)的初C）問題的難 D）A）和 A）結(jié)構(gòu)和外部結(jié)）線性結(jié)構(gòu)和非線性結(jié)構(gòu) 系，非線性結(jié)構(gòu)表示數(shù)據(jù)元間為一對(duì)多或者多對(duì)一的關(guān)系，所以答案為B【例3】以 A）判斷棧是否為B）將棧置為空C）刪除棧頂元 D）刪除棧底元 A）可隨機(jī)任意一個(gè)結(jié) D）所需空間與其長度成正【例5】已知某二叉樹的后序遍歷序列是DACBE，中序遍歷序列是DEBAC，則它的前【例6】設(shè)有一個(gè)已按各元素的值排好序的線性表（長度大于2）k，分別用順下，s和b的關(guān)系是（考點(diǎn)9）A）s= A）左、右兩個(gè)子表都已各自排好序B）左邊子表中的元素都不大于右邊子表中的元素C）左邊子表的長度小于右邊子表的長度D）左、， 第2設(shè)計(jì)的原則、面象方法的基本概念，讀者應(yīng)對(duì)此部分進(jìn)行重點(diǎn)學(xué)習(xí)?？键c(diǎn) 結(jié)構(gòu)化程序設(shè)計(jì)的原思想和結(jié)構(gòu)化思想，使大型的開發(fā)和編程得到了極大的改善。結(jié)構(gòu)化程序設(shè)計(jì)方法的主要面象的程序設(shè)考點(diǎn) 面象方法的基本概考試一個(gè)消息由三部分組成：接收消息的對(duì)象的名稱、消息標(biāo)識(shí)符（消）和零個(gè)或多個(gè) A）20世紀(jì)50年 D）20世紀(jì)80年解析：20世紀(jì)70年代提出了"結(jié)構(gòu)化程序設(shè)計(jì)（structuredprogramming）"的思想和方法。結(jié)構(gòu)化程序設(shè)計(jì)方法引入了工程化思想和結(jié)構(gòu)化思想，使大型的開發(fā)和編程得到了極大的 A）自下向 B）逐步求 A）抽象與具 B）具體與抽C）部分與整 D）整體與部 定義技術(shù)。已有的類可當(dāng)作基類來，則新類相應(yīng)地可當(dāng)作派生類來。 （考點(diǎn) 第3章工程基經(jīng)過對(duì)部分考生的以及對(duì)近年的總結(jié)分析，筆試部分經(jīng)?？疾榈氖巧芷?、設(shè)計(jì)的基本原理，測(cè)試的目的、調(diào)試的基本概念，讀者應(yīng)對(duì)此部分進(jìn)行重點(diǎn)考點(diǎn)1定義與特集合。程序是開發(fā)根據(jù)用戶需求開發(fā)的、用程序設(shè)計(jì)語言描述的、適合計(jì)算機(jī)執(zhí)行的指令序列。數(shù)據(jù)是使程序能正常信息的數(shù)據(jù)結(jié)構(gòu)。文檔是與程序的開發(fā)、和使用有關(guān)的圖文資料?？梢?，由兩部分組成：（1）是邏輯實(shí)體，而不是物理實(shí)體，具有抽象性根據(jù)應(yīng)用目標(biāo)的不同，可分應(yīng)用、系統(tǒng)支撐（或工具小提示：應(yīng)用是為解決特定領(lǐng)域的應(yīng)用而開發(fā)的；系統(tǒng)是計(jì)算機(jī)管理自身資源，提高計(jì)算機(jī)使用效率并為計(jì)算機(jī)用戶提供各種服務(wù)的；支撐是介于兩者之間，協(xié)助用戶開發(fā)的工具性軟考點(diǎn)2工程過程與生命周內(nèi)容，讀者應(yīng)該識(shí)記生命周期的定義，主要活動(dòng)階段及其任務(wù)。 圖 還可以將生命周期分為如上圖所示的 開發(fā)和運(yùn)行 考點(diǎn)3設(shè)計(jì)的基本概考試1.設(shè)計(jì)的基 2.設(shè)計(jì)的基本原模塊的聯(lián)系最少且接口簡單。模塊的獨(dú)立程度是評(píng)價(jià)設(shè)計(jì)好壞的重要度量標(biāo)準(zhǔn)。衡量的模在程序結(jié)構(gòu)中，各模塊的內(nèi)聚性越強(qiáng)，則耦合性越弱。一般較優(yōu)秀的設(shè)計(jì)，應(yīng)盡量做小提示：上面僅是對(duì)耦合機(jī)制進(jìn)行的一個(gè)分類?？梢娨粋€(gè)模塊與其他模塊的耦合性越強(qiáng)則該模塊獨(dú)立考點(diǎn) 詳細(xì)設(shè)考試圖形工具：程序流程圖，N-S，PAD，HIPO語言工具：PDL（偽碼方框圖中僅含5種基本的控制結(jié)構(gòu)，即順序型、選擇型、多分支選擇型、WHILE重復(fù)型UNTILPAD圖表示5種基本控制結(jié)構(gòu)，即順序型、選擇型、多分支選擇型、WHILE重復(fù)型和PDL可以由編程語言轉(zhuǎn)換得到，也可以是專門為過程描述而設(shè)計(jì)疑難解答：程序流程圖，N-S圖，PAD圖的控制結(jié)構(gòu)的異同點(diǎn)是什么？相同點(diǎn)是三種圖都有順序結(jié)構(gòu)，選擇結(jié)構(gòu)和多分支選擇，并且N-S圖和PAD圖還有相同的WHILE重復(fù)型UNTIL重復(fù)型；不同點(diǎn)是程序流程圖沒有WHILE重復(fù)型、UNTIL重復(fù)型而有后判斷重復(fù)型和先判斷重考點(diǎn)5測(cè)試的目考試（1）測(cè)試是為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過程考點(diǎn)6測(cè)試的實(shí)考試 集成測(cè)試是測(cè)試和組裝的過程，主要目的是發(fā)現(xiàn)與接口有關(guān)的錯(cuò)誤，主要依據(jù)是概要設(shè)計(jì)說明書。集成測(cè)試所設(shè)計(jì)的內(nèi)容包括：單元的接口測(cè)試、全局?jǐn)?shù)據(jù)結(jié)構(gòu)測(cè)試、邊界條件和輸入的測(cè)試等。集成測(cè)試時(shí)將模塊組裝成程序，通常采用兩種方式：非增量方式組裝確認(rèn)測(cè)試的任務(wù)是驗(yàn)證的功能和性能，以及其他特性是否滿足了需求規(guī)格說明中確定的各種需求，包括配置是否完全、正確。確認(rèn)測(cè)試的實(shí)施首先運(yùn)用黑盒測(cè)試方法，對(duì)進(jìn)行有效性測(cè)試，即驗(yàn)證被測(cè)是否滿足需求規(guī)格說明確認(rèn)的標(biāo)準(zhǔn)。系統(tǒng)測(cè)試是通過測(cè)試確認(rèn)，作為整個(gè)基于計(jì)算機(jī)系統(tǒng)的一個(gè)元素，與計(jì)算機(jī)硬件、外設(shè)、支撐、數(shù)據(jù)和等其他系統(tǒng)元素組合在一起，在實(shí)際運(yùn)行（使用）環(huán)境下對(duì)計(jì)算機(jī)考點(diǎn) 調(diào)試的基本概

考試在對(duì)程序進(jìn)行了成功的測(cè)試之后將進(jìn)入程序調(diào)試（通常稱Debug，即排錯(cuò)。程序的調(diào)試疑難解答：

3.5 開發(fā)、運(yùn)行對(duì)計(jì)算機(jī)沒有依賴性，不受計(jì)算機(jī)系統(tǒng)的限制D）軟B （考點(diǎn)A）需求分 開C）確 【例3】從技術(shù)觀點(diǎn)看，設(shè)計(jì)包括 【例4】以下哪個(gè)是測(cè)試的目的？（考點(diǎn)A）證明程序沒有錯(cuò) B）演示程序的正確C）發(fā)現(xiàn)程序中的錯(cuò) D）改正程序中的錯(cuò)C （考點(diǎn)A）單元測(cè) B）集成測(cè)C）驗(yàn)收測(cè) D）系統(tǒng)測(cè)邊界條件測(cè)試和輸入的測(cè)試等，所以正確答案是B （考點(diǎn)A）檢查錯(cuò) B）改正錯(cuò)C）發(fā)現(xiàn)錯(cuò) D）以上都不 D）回歸測(cè)試，防止引入新錯(cuò) （考點(diǎn)7）A）注意修改錯(cuò)誤本身而不僅僅是錯(cuò)誤的征兆和表現(xiàn)B） (1）在出現(xiàn)錯(cuò)誤的地方，很可能有別的錯(cuò) 答案：表【例2 【例3】數(shù)據(jù)流圖采用4種符號(hào)表示、數(shù)據(jù)源點(diǎn)和終點(diǎn)、數(shù)據(jù)流向和數(shù)據(jù)加工（考解析：數(shù)據(jù)流圖可以表達(dá)系統(tǒng)的數(shù)據(jù)、數(shù)據(jù)源點(diǎn)和終點(diǎn)、數(shù)據(jù)流向和數(shù)據(jù)加工。其中，用箭頭表示數(shù)據(jù)流向，用圓或者橢圓表示數(shù)據(jù)加工，杠表示數(shù)據(jù)，用方框來表第4經(jīng)過對(duì)部分考生的以及對(duì)近年的總結(jié)分析，筆試部分經(jīng)?？疾榈氖菙?shù)據(jù)庫管理階段的特點(diǎn)、數(shù)據(jù)的物理獨(dú)立性及邏輯獨(dú)立性、數(shù)據(jù)管理與控制、三級(jí)模式及兩級(jí)的考點(diǎn)1 數(shù)據(jù)庫是長期在計(jì)算機(jī)內(nèi)、有組織的、可共享的大量數(shù)據(jù)的集合，它具有的結(jié)構(gòu)形式并存放于的介質(zhì)內(nèi)，是多種應(yīng)用數(shù)據(jù)的集成，并可被各個(gè)應(yīng)用程序所共享。，負(fù)責(zé)數(shù)據(jù)庫中的數(shù)據(jù)組織、數(shù)據(jù)操作、數(shù)據(jù)、控制及保護(hù)和數(shù)據(jù)服務(wù)等。數(shù)據(jù)庫管考點(diǎn) 數(shù)據(jù)庫系統(tǒng)的發(fā)表4-1考點(diǎn) 數(shù)據(jù)庫系統(tǒng)的基本特?fù)?jù)的物理結(jié)構(gòu)（包括結(jié)構(gòu)、存取方式等）改變時(shí)，如設(shè)備的更換、物理的更換、考點(diǎn) 數(shù)據(jù)庫系統(tǒng)的結(jié)構(gòu)體該理解三級(jí)模式及兩級(jí)的定義。內(nèi)模式處于最底層，它反映了數(shù)據(jù)在計(jì)算機(jī)物理結(jié)構(gòu)中的實(shí)際形式，概念模式處于中小提示：內(nèi)模式處于最底層，它反映了數(shù)據(jù)在計(jì)算機(jī)物理結(jié)構(gòu)中的實(shí)際 考點(diǎn) 數(shù)據(jù)模型的基本概考點(diǎn) E-R模考點(diǎn) 層次?？键c(diǎn) 關(guān)系模們稱為表的侯選碼或。從二維表的所有侯選鍵選取一個(gè)作為用戶使用的鍵稱為主鍵或主考點(diǎn) 關(guān)系代S稱為T除以R的商。除法運(yùn)算不是基本運(yùn)算，它可以由基本運(yùn)算設(shè)有關(guān)系R、S，R有域A1，A2，…，An，S有域B1，B2，…，Bm，并且 Bm（σAi1=B1^Ai2=B2^^Aij=,Bj考點(diǎn)10數(shù)據(jù)庫設(shè)計(jì)概述兼顧信息需求。由于數(shù)據(jù)在系統(tǒng)中穩(wěn)定性高，數(shù)據(jù)已成為系統(tǒng)的，因此面向數(shù)據(jù)的設(shè)計(jì)方4.4 A）應(yīng)用程序 B）用C）數(shù)據(jù)庫管理 D）數(shù)據(jù)庫管理系統(tǒng)的設(shè)計(jì)解析：數(shù)據(jù)庫管理員（簡稱DBA），具有如下的職能：設(shè)計(jì)、定義數(shù)據(jù)庫系統(tǒng)；幫助用戶使據(jù)庫；重構(gòu)數(shù)據(jù)庫。所以，定義數(shù)據(jù)庫內(nèi)容，決定結(jié)構(gòu)和存取策略及安全等是數(shù)據(jù)庫 A）數(shù)據(jù)庫系 B）文件系C）人工管 D）數(shù)據(jù)項(xiàng)管 （考點(diǎn)A）應(yīng)用程 B）邏輯結(jié)構(gòu)和物理結(jié)構(gòu)之間C）結(jié) D）局部邏輯結(jié)構(gòu)到總體邏輯結(jié)構(gòu) A）具有封裝機(jī)制 式分級(jí)，各級(jí)模式之間的D）系統(tǒng)在這3級(jí)模式之間提供了兩層：外模式/模式，模式/內(nèi)模式。這兩層保證 （考