全國計算機等級考試二級vf(存儲版)

　　

【正文】 圖14 一般的樹 （1）什么是二叉樹 二叉樹是一種很有用的非線性結構，它具有以下兩個特點：非空二叉樹只有一個根結點；每一個結點最多有兩棵子樹，且分別稱為該節點的左子樹和右子樹。完全二叉樹還具有如下兩個特性：性質5 具有n個結點的完全二叉樹的深度為［log2n］+1。【例110】 深度為5的滿二叉樹中，結點的個數為 。 二叉樹的遍歷是指不重復地訪問二叉樹中的所有結點。 圖15 二叉樹 2)接著按后序遍歷右子樹（以C為根節點，包括C、E、F三個結點），右子樹中也按后序遍歷訪問左子樹E，再訪問右子樹F，最后訪問根節點C，右子樹訪問完畢。 解析：在進行順序查找過程中，如果現行表中的第一個元素就是被查找元素，則只需做一次比較就查找成功，查找效率最高；但如果被查的元素是線性表中的最后一個元素，或者被查找元素根本不在線性表中，則為了查找這個元素需要與線性表中所有的元素進行比較，這是順行查找的最壞情況。對于長度為n的有序線性表，在最壞的情況下，二分查找只需要比較log2n次，而順序查找需要比較n次。一次排序結束后，表中最大元素為與線性表末尾。但這個工作量不是必需的，一般情況下要小于這個工作量。A）算法的執行效率與數據的存儲結構無關B)算法的空間復雜度是指算法程序中指令（或語句）的條數C）算法的有窮性是指算法必須能在執行有限個步驟之后終止。 A)算法程序的長度 B）算法程序中的指令條數C）執行算法過程中所需要的存儲空間 D）算法程序所占的存儲空間 ，若查找不成功，至少需要比較的次數為（ ） A）3 B）4 C）5 D）6 ，含有15個結點的二叉樹的最小樹深是（ ）。程序設計風格是指編寫程序是所表現出的特點、習慣和邏輯思路。3）模塊化：一個復雜問題肯定是由若干簡單的問題構成。 面向對象方法之所以日益受考查結構化程序設計的結構。這些概念包括：（1） 對象（Object）對象是面向對象方法中最基本的概念。（2） 類（Class）和實例（Instance）類是具有共同屬性、共同方法的對象的集合。零個或多個參數。在面向對象的軟件技術中，多態性是指子類對象可以像父親對象那樣使用，同樣的消息既可以發送給父類對象也可以發送給子類對象。因此他是類之間共享屬性和操作的機制。具體地說，在軟件開發和維護過程中，軟件危機主要表現在：1） 軟件需求的增長得不到滿足。1993年，IEEE(Institute of Electrical amp。該定義支持了軟件工程過程的以下兩方面內涵：其一，軟件工程過程是指為獲得軟件產品，在軟件工具支持下由軟件工程師完成的一系列軟件工程活動。隊準備開發的軟件提出的需求進行分析并給出詳細定義，編寫軟件規格說明書及初步的用戶手冊，提交評審。5），檢驗軟件的各個組成部分，編寫測試分析報告。這些原則適用于所有軟件項目。　　　　Ａ）軟件工程概念的出現源自軟件危機。　　　　選項Ｄ，軟件生命周期不僅僅分為軟件定義和軟件實現兩個階段，還有運行維護階段。　　答案：Ｄ。　Ｃ）軟件交付使用后其生命周期就結束。重要知識點 數據流圖 數據字典１. 結構化分析方法軟件需求是指用戶對目標軟件系統在功能、行為、性能、設計約束等方面的期望。３）編寫需求規格說明書　　作為需求分析的階段成果的需求規格說明書，可以為用戶、分析人員和設計人員之間的交流提供方便，可以直接支持目標軟件系統的確認，又可以作為控制軟件開發進程的依據。數據流圖中的主要符號元素與說明如表31所示。【例35】 在軟件生命周期中，能準確地確定軟件系統必須做什么和必須具備哪些功能的階段是 。抽象是一種思維工具，就是把事物本質的共同特性提取出來而不考慮其他細節。 結構化設計方法的基本思想是將軟件設計成由相對獨立、單一功能的模塊組成的結構。３） 把數據流圖映射為程序結構。但是當對大的模塊分解時，不應降低模塊的獨立性。模塊的接口復雜是軟件容易發生錯誤的一個主要原因。 表格工具：判定表。 選項C，過程內聚是指一個模塊內的處理元素是相關的，而且必須以特定次序執行。A模塊間的關聯設計B系統結構部件轉換成軟件的過程描述C描述軟件內部、軟件和協作系統之間以及軟件與人之間如何通信D軟件與操作人員之間的通信方式設計答案：C。提示：2006年4月真題選擇題第1題、2008年4月真題選擇題第2題屬該題的類似題目。 軟件測試的概念及方法216。他是根據軟件產品的內部工作過程，檢查內部成分，以確認每種內部操作符合設計規格要求。通常程序中的邏輯表示有判斷、分支、條件等幾種表示方式。其思想和步驟是，根據軟件過程描述中的控制流程確定程序的環路復雜性度量，用此度量定義基本路徑集合，并由此導出一組測試用例對一條獨立執行路徑進行測試（2）黑盒測試用例設計黑盒測試方法主要有等價類劃分法、邊界值分析法、錯誤推測法、因果圖等，主要用于軟件確認測試。 軟件測試是保證軟件質量的重要手段，軟件測試是一個過程，其測試流程是該過程規定的程序，目的是使軟件測試工作系統化。 （2）集成測試集成測試是測試和組裝軟件的過程。【例311】 成功的軟件測試是指發現程序中的 。其中代碼檢查主要檢查代碼和設計的一致性，包括代碼的邏輯表達的正確性、代碼結構的合理性等；靜態結構分析是對代碼機械、程式化的特性分析，包括控制流分析、數據流分析、接口分析和表達式分析。然后，從發現“癥狀”的地方開始，沿程序的控制歷程你想跟蹤源程序代碼，直到找到錯誤根源或確定錯誤產生的范圍。歸納法是一種從特殊推斷出一般的系統化思考方法。軟件測試中討論的靜態分析方法同樣適用于靜態調試。從出題的深度來看，本章主要考查對基本概念的識記，有少量對基本原理的理解，沒有實際運用，因此考生在復習本章時，重點應放在基本概念的記憶和基本原理的理解上。 A）強行排錯法 B)系統測試法 C）回溯法 D）原因排除法，他由一些特定的圖符構成。，模塊獨立的概念是模塊化、抽象、 和局部化概念的直接結果。20世紀60年代以后，數據管理進入數據庫系統階段。2)數據存取的物理構建。數據庫中的數據具有內在語義上的關聯性與一致性，它們構成了數據的完整性，數據的完整性是保證數據庫中數據正確的必要條件，因此必須經常檢查以維護數據的正確，數據庫中的數據具有共享性，而數據。數據庫管理系統是數據庫系統的核心，它主要有如下幾方面的具體功能：1）數據模式定義。人工管理階段是20世紀50年代中期以前，主要用于科學計算，無直接存取設備，軟件沒有操作系統。 。 A）隨機選取測試數據 B）取一切可能的輸入數據作為測試數據 C）在完成編碼以后制定軟件的測試計劃 D）集中對付那些錯誤群集的程序（ ）。重要知識點包括：軟件工程與軟件生命周期的概念以及對對它們的理解、結構化設計方法中的軟件設計原理（尤其是模塊獨立性）/軟件測試與軟件調試的概念與方法。調試的關鍵在于推斷程序內部的錯誤位置及原因。最后，再用測試數據驗證余下的假設確定出錯的原因。2）回溯法 該方法適用于小規模程序的排錯。【例313】 程序測試分為靜態測試和動態測試，其中 不實際運行軟件，主要通過人工進行 答案：靜態測試。 （4）系統測試系統測試是將通過測試確認的軟件，作為整個基于計算機系統的一個元素，與計算機硬件、外設、支持軟件、數據和人員等其他系統元素合在一起，在實際運行（使用）環境下對計算機系統進行一系列的集成測試和確認測試。單元測試的技術可以采用靜態分心和動態測試。3）錯誤推測法。判斷——條件覆蓋，設計足夠的測試用例，是判斷中每個條件的所有可能取值至少執行一次，同時每個判斷的所有可能取值分支至少執行一次。1）邏輯覆蓋。為了達到好的測試效果，應該由獨立的第三方來構造測試；５） 窮舉測試不可能；６） 妥善保存測試計劃、測試用例、出錯統計和最終分析報告，為維護提供方便。 通過以上分析，得出【1】的答案為4，【2】的答案為3。 答案：自頂向下、逐步求精法。 1973年，Nossi和Shneiderman提出了用方框圖來代替傳統的程序流程圖，通常也把這種圖稱為NS圖。 解析：分析本題的四個選項如下： 選項A,偶然內聚是指一個模塊內的各處理元素之間沒有任何聯系。圖形工具：程序流程圖、NS、PAD及HIPO。對于那些不滿足這一條件的軟件結構，修改的辦法是將判定點上移，或者將那些在作用范圍內但是不再控制范圍內的模塊移到控制范圍以內。２） 模塊規模適中。面向數據流設計方法的實施要點和設計過程有以下幾步：１） 分析、確認數據流圖的類型，區分是事務型還是變換型。經常使用的結構圖有四種模塊類型：傳入模塊、傳出模塊、變換模塊和協調模塊。遵循的原則——高內聚低耦合。模塊獨立性是指在每個模塊之完成系統要求的獨立的子功能，并且與其他模塊的聯系最少且接口簡單。軟件設計是一個迭代的過程，其一般過程是：先進行高層次的結構設計；后進行低層次的過程設計；穿插進行數據設計和接口設計。通常數據字典包含的信息有：名稱、別名、何處使用/如何使用、內容描述及補充信息等。數據流圖（Data Flow Diagram ,DFD）是描述數據處理過程的工具，是需求理解的邏輯模型的圖形表示，她直接支持系統的功能建模。涉及的主要任務是立獲取用戶需求的方法構架，并支持和監控需求獲取的過程。軟件維護已知持續到軟件生命周期的結束。Ａ）軟件交付使用后還需要進行維護。　　Ｃ）軟件工程主要是解決軟件開發過程中的技術問題。選項Ｂ，根據“軟件危機的主要表現”可知此選項正確。計算機輔助軟件工程（Computer Aided Software Engineering,CASE）是當前軟件開發環境中富有特色的研究工作和發展方向。1） 軟件工程的原則。把軟件設計轉換成計算機可以接受的程序代碼。確定待開發軟件形同的開發目標和總的要求，給出它的功能、性能、可靠性以及接口等方面的可能方案，制定完成開發任務的實施計劃。把需求分析、可行性研究、工程審核、質量監督等工程化的概念引入到軟件生產中，以期達到工程項目的三個基本要素（進度、經費和質量）的目標。軟件工程就是試圖用工程、科學和數學的原理與方法研制、維護計算機軟件的有關技術及管理方法。 （2）軟件危機與軟件工程軟件工程概念的出現源自軟件危機。 A）可靠性 B）可重用性 C）可移植性 D）可修改性（ ）實現的。 答案：繼承。這種層次結構系統的一個重要性質就是繼承，一個類直接繼承其父類的描述（數據和操作）或特性，子類自動地共享基類中定義的數據和方法。一個消息有以下三部分組成：接收消息的對象的名稱。操作的過程對外是封閉的，即用戶只能看到這一操作實施后的結果。面向對象方法的基本概念面向對象的程序設計方法中涉及的對象是系統中用來描述客觀事物的一個實體，是構成系統的一個基本單位，它由一組表示其靜態特征的屬性和它可執行的一組操作組成。【例22】 下面對于結構化程序設計方法的主要原則描述錯誤的是（ ）。 面向對象方法的基本概念結構化程序設計方法的主要原則為：1）自頂向下：程序設計時，應先考慮總體，后考慮細節；先考慮全局目標，后考慮局部目標。,前序遍歷結果為ABDECF,則后序遍歷結果為 稱為線性表的長度。A）在隊列中只能插入數據 B）在隊列中只能刪除數據C）隊列是“先進先出”的線性表 D）隊列是“先進后出”的線性表 ，葉結點的個數為（ ）。反復做第二部，知道剩下的子序列為空為止。【113】 在最壞情況下，冒泡排序法需要的比較次數為 。然后從后往前掃描剩下的線性表，同樣，在掃描過程中主次比較兩個相鄰元素的大小。 這個過程一直進行到查找成功或子表長度為0（說明現行表中沒有這個元素）為止。【例112】 對長度為n的線性表進行順序查找，在最壞的情況下所需要的比較次數是（ ）。FECBA A）ABCDEF B) DBAECF C) BCDEFA D) DBEFCA D答案：D。 與線性鏈表類似，用于存儲二叉樹中各元素的存儲結點也由兩部分組成；數據域和指針域。 答案：350個。完全二叉樹：除最后一層外，每一層上的節點數都達到最大值；在最后一層上只缺少右邊的若干結點。 樹和二叉樹 樹的基本概念 樹是一種簡單的非線性結構。即循環鏈表中，所有結點的指針構成了一個環狀鏈。4） 將一個線性鏈表按要求進行分解。 提示：2007年9月真題填空題第3題考察循環隊列的存儲結構。在循環隊列中，用隊尾指針rear指向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置，因此，從排頭指針front指向最后一個位置直到隊尾指針rear指向的位置之間，所有的元素均為隊列中的元素。 （1） 隊列的基本概念隊列是指允許在一端進行插入，而在另一端進行刪除的線性表。 隊列及其基本運算1. 及其基本運算 棧（stack）是限定在一端進