計算機二級公共基礎

二級公共基礎考點總結第一章 數據結構與算法（八大考點）考點一:算法L盲法是指解題方案的準確而完整的描述。它有4個基本特征，分別是可行性、確定性、有窮性和擁有足夠的情報。2.算法的復雜度主要包括時間復雜度和空間復雜度算金的時間復雜度是指執(zhí)行算法所需要的計算所需要的計算工作量（或算法執(zhí)行過程中所需要的基本運算次數）算法的空間復雜度是指執(zhí)行這個算法所需要的內存空間.考點二:數據結構的基本概念.數據結構是研究數據元素及其之間的相互關系和數據運算的一門學科.數據結構概念一般包括3個方面的內容:數據之間的邏輯關系（邏輯結構）、數據在計算機中的存儲方式（存儲結構）以及在這些數據上定義的運算的集合（數據的運算）.數據的邏輯結構是指反映數據元素之間邏輯關系的數據結構；數據的存儲結構是指數據的邏輯結構在計

算機存儲空間中的存放形式。在數據的存儲結構中，不僅要存放各數據元素的信息，還需要存放各數據元素之間的前后件關系的信息。.在鏈式存儲結構中，存儲數據結構的存儲空間可以是連續(xù)的，也可以是不連續(xù)的，各數據結點的存儲順序與數據元素之間的邏輯關系可以不一致。.一般來說，一種數據結構根據需要可以表示成多種存儲結構。常用的存儲結構有順序、鏈接、索引等，而采用不同的存儲結構，其數據處理的效率是不同的；一個數據結構中的各數據元素在計算機存儲空間中的位置關系與邏輯關系是有可能不同的。.線性結構是指各數據元素之間的邏輯關系可以用一個線性序列簡單地表示出來。否則稱之為非線性結構?？键c三:線性表及其順序存儲結構1.當線性表采用順序存儲結構實現存儲時，其主要特點是數據元素按線性表的邏輯次序，依次存放在一組地址連續(xù)的存儲單元中。在存儲單元中各元素的物理位置和邏輯結構中各結點

間的相鄰關系是一致的。考點四:棧和隊列棧和隊列都是一種特殊的操作受限的線性表，只允許在端點處進行插入和刪除。二者的區(qū)別是：棧只允許在表的一端進行插入或刪除操作，是一種〃后進先出〃的線性表；而隊列只允許在表的一端進行插入操作，在另一端進行刪除操作，是一種〃先進先出〃的線性表。棧和隊列的共同特點是只允許在端點處插入和刪除元素常常一個程序中要用到多個棧，為了不發(fā)生上溢錯誤，就必須給每個棧分配一個足夠大的存儲空間。但實際中，很難準確地估計,若每個棧都分配過大的存儲空間，勢必造成系統(tǒng)空間緊張；若讓多個棧共用一個足夠大的連續(xù)存儲空間，則可利用棧的動態(tài)特性使他們的存儲空間互補。所以，由兩個棧共享一個存儲空間的好處是節(jié)省存儲空間，降低上溢發(fā)生的機率（設有兩個串P和q,求q在P中首次出現位置的運算稱作模式匹配）（n個頂點的連通圖中邊的條數至少為n-1）考點五:線性鏈表1.星表采用的是鏈式存儲結構（鏈式存儲中每個結點由兩部分組成:數據域和指針域）,它克服了順序存儲結構的缺點：它的結點空間可以動態(tài)申請和釋放;它的數據元素的邏輯次序靠結點的指針來指示,不需要移動數據元素。但是鏈式存儲結構也有不足之處:①每個結點中的指針域需額外占用存儲空間;②鏈式存儲結構是一種非隨機存儲結構。用鏈表表示線性表的突出優(yōu)點是便于插入和刪除操作.考點六:樹與二叉樹.樹是一個或多個結點組成的有限集合，其中一個特定的結點稱為根，其余結點分為若干個不相交的集合。每個集合同時又是一棵樹。樹有且只有1個根結點。.二叉樹的遍歷是指不重復地訪問二叉樹中的所有結點二叉樹的遍歷可以分為三種：前序遍歷(DLR)是指先訪問根結點，然后遍歷左子樹，最后遍歷右子樹.(先根后左再右)中序遍歷(LDR)是指先遍歷左子樹,然后訪問根結點，最后遍歷右子樹.(先左后根再右)后序遍歷(LRD)是指先遍歷左子樹,然后遍歷右子樹，最后訪問根結點.(先左后右再根)如：已知二叉樹后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列是cedba解題思路：由后序或前序遍歷可判斷根結點,再由中序遍歷可判斷左右子樹.考點七:查找技術一.順序查找順序查找的方法是：用待查關鍵碼值與線性表中各結點的關鍵碼值逐個比較，直到找出相等的關鍵碼值，則查找成功；或者找遍所有結點都不相等，則查找失敗。順序查找的優(yōu)點：對線性表的結點的邏輯次序無要求（不必按關鍵碼值排序），對線性表的存儲結構無要求（順序存儲、鏈接存儲皆可。）二二分法查找二分法查展是一種效率較高的線性表查找方法。要進行二分法查找，則線性表結點必須進按關鍵碼值排好序的，且線性表以順序方式存儲。二分法查找的方法：首先用要查找的關鍵碼值與線性表中間位置結點的關鍵碼值相比較，這個中間結點把線性表分成了兩個子表，比較相等則查找完成，不等則根據比較結果確定下一步的查找應在哪一個子表中進行，如此進行下去，直到找到滿足條件的結點，或者確定表中沒有這樣的結點。對于二分法查找的缺點是線性表排序需花費時間，順序方式存儲的插入、刪除不便。長度為n的有序線性表，在最壞情況下，二分查找只需要比較log2n次，而順序查找需要比較n次?？键c八:排序技術一.交換類排序法交換類排序的基本思想:兩兩比較待排序記錄的關鍵碼，并交換不滿足順序要求的那些偶對,直到全部滿足為止.冒泡排序法(或稱下沉排序)將待排序的記錄順次兩兩比較,若為逆序則進行交換.將序列照此方法從頭到尾處理一遍稱作一趟起泡，一趟起泡的效果是將關鍵碼值最大的記錄交換到了最后的位置,即該記錄的排序最終位置.若某一趟起泡過程中沒有發(fā)生任何交換，則排序過程結束.對n個記錄的文件進行排序最多需要n-1趟起泡.對n個記錄的文件進行冒泡排序，在最壞情況下，需要的比較次數為：N(N-1)/2快速排序法快速排序又稱分區(qū)交換排序，是對冒泡排序的一種改進.其基本方法是:在待排序序列中任取一個記錄,以它為基準用交換的方法將所有的記錄分成兩部分,關鍵碼值比它小的在一個部分，關鍵碼值比它大的在另一個部分.再分別對兩個部分實施上述過程，一直重復到排序完成.在最壞的情況下與起泡排序相當，然而快速排序的平均執(zhí)行時間為O(nlog2n),顯然優(yōu)于起泡排序和直接插入排序、直接選擇排序方法。需要指出的是，快速排序需要O(logzn)的附加存儲開銷，這是因為快速排序算法的實現過程中需用到大小為O(log2n)的?？臻g?？焖倥判蚴且砸粋€記錄為基準，用交換的方法把文件分成兩部分的思想。.插入類排序法插入排序的基本思想是：每步將一個待排序記錄按其關鍵碼值的大小插入到前面已排序的文件中的適當位置上,直到全部記錄插入完為止。1)簡單插入排序它是指將無序序列中的各元素依次插入到已經有序的線性表中。這種排序的效率與冒泡排序法相同。在最壞情況下，簡單插入排序需要N(N-l)/2次比較.將已排好序的序列中找插入位置時用順序法查找，找到插入位置后將該位置原來的記錄及其后面所有的記錄順序后移一個位置，空出該位置來插入記錄。

2)希爾(Shell)排序法(縮小增量法)希爾排序的基本思想是把記錄按下標的一定增量分組，對每組記錄使用插入排序，隨增量的逐漸減小，所分成的組包含的記錄越來越多，到增量的值減小到1時，整個數據合成一組，構成一組有序記錄，故其屬于插入排序方法。在最壞情況下，希爾排序所需要的比較次數為O(NL5).希爾排序的效率與所選取的增量序列有關..選擇類排序法選擇排序的基本思想是：每次從待排序的記錄中選出關鍵碼值最小(或最大)的記錄，順序放在已排序的記錄序列的最后,直到全部排完。1)簡單選擇排序簡單選擇排序法在最壞情況下需要比較N(N-l)/2次對文件進行n-1趟掃描，第I趟掃描從剩下的n-i+1個記錄中選出關鍵碼值最小的記錄，與第I個記錄交換。直接選擇排序的每一趟掃描找出當前最小關鍵碼，但沒有為以后的選擇留下任何信息。

堆排序是對直接選擇排序的改進，在第一次選擇出最小關鍵碼的同時為以后的選擇準備了條件。2）堆排序堆排序是完全二叉樹結構的一個重要應用。堆排序的基本思想是:對一組待排序的關鍵碼，首先把它們按堆的定義排成一個序列（稱為建堆），這就找到了最小的關鍵碼，然后將最小的關鍵碼取出，用剩下的關鍵碼再建堆，便得到次最小的的關鍵碼，如此反復進行，直到將全部關鍵碼排好序為止。堆排序的方法對于規(guī)模較小的線性表并不適合,但對于較大規(guī)模的線性表來說是很有效的.在最壞懷況下，堆排序需要比較的次數為nlog2n次,堆排序的執(zhí)行時間為O（nlog2n），且僅需要一個用于交換的附加存儲結點。因此堆排序是一種適合于較大文件的排序方法。相關知識點：從平均時間性能而言，快速排序最佳，其所需時間最少，但快速排序在最壞情況下的時間性能不如堆排序和歸并排序。當序列中的記錄基本有序或元素個數較少時，冒泡排序和簡單選擇排序為最佳排序方法.所以,在待排序的元素序列基本有序的前提下，效率最高的排序方法是冒泡排序和簡單選擇排序第二章 程序設計基礎（三大考點）考點一:程序設計方法與風格程序的主要風格：“清晰第一，效率第二”要形成良好的程序設計風格，主要應注意下述1II一,要素：.源程序文檔化文檔是有關計算機程序功能、設計、編制、使用的文字或圖形資料。編制一個好的程序首先要確保它的正確性和可靠性還應強調良好的編程風格。在書寫時應考慮為程序作注釋。.數據說明的方法.語句的結構程序編寫要做到清晰第一、效率第二。.輸入和輸出考點二:結構化程序設計結構化程序設計的原則：概括為：自頂向下、逐步求精、模塊化、限制使用GOTO語句。結構化程序的基本結構：順序結構、選擇結構、重復結構（或稱為循環(huán)結構）嚴格控制GOTO語句的使用。其意思是指：A.用一個非結構化的程序設計語言去實現一個結構化的構造。B.若不使用GOTO語句會使功能模糊C.在某種可以改造而不是損害程序可讀性的情況下。相關知1。程序設計語言是用于書寫計算機程序的語言，其基本成分有以下4種，數據成分：用來描述程序中的數據。運算成分：描述程序中所需的運算。控制成分：用來構造程序的邏輯控制結構。傳輸成分：定義數據傳輸成分，如輸入輸出語言。2.當程序之間發(fā)生調用關系時，調用命令所在的代碼段被稱為主程序，被調用的代碼段被稱為子程序。子程序是對功能的抽象，可分為過程和函數兩類，兩者的區(qū)別是函數是通過函數名來返回值的，而過程只能通過形式參數或對全局變量進行修改以返回值?？键c三:面向對象的程序設計一.面向對象的優(yōu)點：A.與人類習慣的思維方法一致B.穩(wěn)定性好C.可重用性好（軟件重用是指在不同的軟件開發(fā)過程中重復使用相同或相似軟件元素的過程O重用是提高軟件生產率的最主要的方法。）D.易于開發(fā)大型軟件產品E.可維護性好4.面向對象方法的基本概念1）對象面向對象方法學中的對象是由描述該對象屬性的數據以及可以對這些數據施加的所有操作封裝在一起構成的統(tǒng)一體。面向對象方法基本目的和主要優(yōu)點:通過重用性提高軟件的生產率。對象是面向對象方法中最基本的概念，可以用來表示客觀世界中的任何實體，對象是實體的抽象O對象是屬性和方法的封裝體。屬性即對象包含的信息，操作描述了對象執(zhí)行的功能，操作也稱為方法或服務。面向對象方法和技術以對象為核心，對象之間通過傳遞消息互相聯系。面向對象方法的基本概念包括：對象、屬性、方法、類、繼承、多態(tài)性沒有過程調用。對象有五個基本特點：A.標識惟一性B.分類性C.多態(tài)性D.封裝性E.模塊獨立性好2）類和實例將屬性、操作相似的對象歸為類。類是具有共同屬性、共同方法的對象的集合。所以，類是對象的抽象，它 描述了屬于該對象類型的所有對象的性質。而一個對象則是其對應類的一個實例。3）消息面向對象的世界是通過對象與對象間彼此的相互合作來推動的，對象間的這種相互合作需要一個機制協助進行，這樣的機制稱為“消息”。消息是一個實例與另一個實例之間傳遞的信息，它請求對象進行某一處理或回答某一要求的信息，它統(tǒng)一了數據流和控制流。消息的使用類似于函數調用4）繼承繼承是使用已有的類定義作為基礎建立新類的定義技術。已有的類可當作基類來引用，則新類相應地可當作派生類來引用。一個類直接繼承其父類的描述或特性，子類自動地共享基類中定義的數據和方法。繼承是指能夠直接獲得已有的性質和特征，而不必重復定義他們。繼承分單繼承和多重繼承o單繼承指一個類只允許有一個父類，多重繼承指一個類允許有多個父類。

在面向對象方法中，類之間共享屬性和操作的機制稱為繼承。繼承性是面向對象程序設計語言不同于其他語言的主要標志。5）多態(tài)性對象根據所接受的消息而做出的動作，同樣的消息被不同的對象接受時可導致完全不同的行動，該現象稱為多態(tài)性。（利用多態(tài)性，用戶能夠發(fā)送一般形式的消息，而將所有的實現細節(jié)都留給接受消息的對象）多態(tài)性是指同樣的消息被不同的對象接受時可導致完全不同的行動的現象。是否建立了豐富的類庫是衡量一個面向對象程序設計語言成熟與否的一個重要標志。第三章軟件工程基礎（五大考點）第三章軟件工程基礎（五大考點）考點一:軟件工程基本概念—軟件定▽與軟件蚌占,計算機軟件是計算機朱統(tǒng)中與硬件相互依存的另一部分，是包括程序、數據及相關文檔的完整集合。其中，程序是軟件開發(fā)人員根據用戶需求開發(fā)的、用程序設計語言描述的、適合計算機執(zhí)行的指令（語句）序列。數據是使程序能正常操縱信息的數據結構。文檔是與程序開發(fā)、維護和使用有關的圖文資料。計算機軟件是指與計算機系統(tǒng)的操作有關的計算機程序、規(guī)程、規(guī)則，以及可能有的文件、文檔及數據。軟件的特點：它是一種邏輯實體，沒有明顯的制作過程，軟件在運行、使用期間不存在磨損、老化問題，軟件的開發(fā)具有依賴性，其復雜性高，成本高，軟件開發(fā)涉及諸多的社會因素。軟件按功能來分為：應用軟件、系統(tǒng)軟件、支撐軟件（或工具軟件）。二.軟件危機與軟件工程.軟件危機是泛指在計算機軟件的開發(fā)和維護過程中所遇到的一系列嚴重問題。軟件危機歸結為成本、質量、生產率等問題。軟件工程就是試圖用工程、科學和數學的原理與方法研制、維護計算機軟件的有關技術及管理方法。軟件工程包括3個要素，即方法、工具和過程。方法是完成軟件工程項目的技術手段；工具支持軟件的開發(fā)、管理、文檔生成；過程支持軟件開發(fā)的各個環(huán)節(jié)的控制、管理。軟件工程過程是把輸入轉化為輸出的一組彼此相關的資源和活動。軟件工程過程通常包含4種基本活動：P-軟件規(guī)格說明。D-軟件開發(fā)。軟件確認A-軟件演進.軟件生命周期分為軟件定義、軟件開發(fā)及軟件運行維護3個階段。軟件定義包括可行性研究與計劃制定、需求分析兩個階段；軟件開發(fā)包括軟件設計（概要設計和詳細設計）、軟件編碼和軟件測試三大階段；軟件運行維護階段包括使用、維護、退役。軟件維護活動包括以下幾類：改正性維護、適應性維護、完善性維護、預防性維護。維護是軟件生命周期的最后一個階段，也是持續(xù)時間最長，花費代價最大的一個階段，軟件工程學的一個目的就是提高軟件的可維護性，降低維護的代價。只有軟件定義有用戶的參與。軟件產品從考慮其概念開始，到該軟件產品不能使用為止的整個時期都屬于軟件生命周期。一般包括可行性研究與需求分析、設計、實現、測試、交付使用以及維護等活動。三.軟件工程的目標和原則1.基于軟件工程的目標軟件工程的理論和技術性研究的內容主要包括：軟件開發(fā)技術（軟件開發(fā)方法學、開發(fā)過程、開發(fā)工具和軟件工程環(huán)境，其主體內容是軟件開發(fā)方法學）,另一個內容是軟件工程管理（軟件管理學、軟件工程經濟學、軟件心理學等）把用戶的要求轉變成軟件產品的過程稱為軟件開發(fā)過程。1.軟件工程的原則：其基本原則包括抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗證性。四.軟件開發(fā)工具與軟件開發(fā)環(huán)境軟件開發(fā)工具為軟件工程學提供了自動的或半自動的軟件支撐環(huán)境。軟件開發(fā)工具的發(fā)展是從單項工具的開發(fā)逐步向集成工具發(fā)展的。軟件開發(fā)環(huán)境或稱軟件工程環(huán)境是全面支持軟件開發(fā)全過程的軟件工具集合。計算機輔助軟件工程（CASE）是當前軟件開發(fā)環(huán)境中富有特色的研究工作和發(fā)展方向?？键c二:結構化分析方法一.需求分析與需求分析方法.需求分析階段工作概括為四個方面：需求獲取、需求分析、編寫需求規(guī)格說明書、需求評審。需求分析是指用戶對目標軟件系統(tǒng)在功能、行為、性能、設計約束等方面的期待。準確地解決了“軟件系統(tǒng)必須做什么”。需求規(guī)格說明書是需求分析的最終結果。.常見的需求分析方法有結構化分析方法和面向對象的分析方法兩類。其中結構化分析方法又包括面向數據流的結構化分析方法(SA一Structuredanalysis),面向數據結構的Jackson方法(JSD-Jacksonsystemdevelopmentmethod)和面向數據結構的結構化數據系統(tǒng)開發(fā)方法(DSSD-Datastructuredsystemdevelopmentmethod)o從需求分析建立的模型的特性來分，需求分析方法又分為靜態(tài)分析方法和動態(tài)分析方法。二.結構化分析方法結構化分析方法是結構化程序設計理論在軟件需求分析階段的運用。.結構化分析方法的實質是著眼于數據流，自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數據流圖和數據字典為主要工具，建立系統(tǒng)的邏輯模型。.結構化分析的常用工具：1)數據流圖(DFD-DataFlowDiagram)數據流圖是描述數據處理過程的工具，是需求理解的邏輯模型的圖形表示，它直接支持系統(tǒng)的功能建模。o 數據流圖中的主要圖形元素：加工（轉換）。輸入數據經加工變換產生輸出。f 數據流。沿箭頭方向傳送數據的通道,二般在旁邊標注數據流名。= 存儲文件（數據源）。表示處理過程中存放各種數據的文件。匚源，潭。表示系統(tǒng)和環(huán)境的接口，屬系統(tǒng)之外的實體。建立數據流圖的步驟：由外向里，自頂向下，逐層分解。2）數據字典（DD-DataDictionary）數據字典是結構化分析方法的核心。數據字典是對所有與系統(tǒng)相關的數據元素的一個有組織的列表，以及精確的，嚴格的定義，使得用戶和系統(tǒng)分析員對于輸入、輸出、存儲成分和中間計算結果有共同的理解。結構化分析方法使用的描述工具數據字典定義了數據流圖中的每個圖形元素。3）判定樹4）判定表（它與判定樹相似，當數據流圖中的加工要依賴于多個邏輯條件的取值，即完成該加工的一組動作是由于某一組條件取值的組合而引發(fā)的，使用判定表描述比較適宜）判定表采用表格表達工具。三.軟件需求規(guī)格說明書軟件需求規(guī)格說明書（SRS,SoftwareRequirementSpecification）是需求分析階段的最后成果，是軟件開發(fā)中的重要文檔之一。內容對軟件主要功能、用戶界面、運行環(huán)境、算法詳細過程、軟件的性能說明。它有以下幾個方面的作用：①便于用戶、開發(fā)人員進行理解和交流;②反映出用戶問題的結構，可以作為軟件開發(fā)工作的基礎和依據；③作為確認測試和驗收的依據。考點三:結構化設計方法一.軟件設計的基本概念.軟件設計的基礎軟件件設計是確定系統(tǒng)的物理模型。從技術觀點來看，軟件設計包括軟件結構設計、數據設計、接口設計、過程設計。其中，結構設計是定義軟件系統(tǒng)各主要部件之間的關系；數據設計是將分析時創(chuàng)建的模型轉化為數據結構的定義；接口設計是描述邏輯內部、軟件和協作系統(tǒng)之間以及軟件與人之間如何通信；過程設計則是把系統(tǒng)結構部件轉換成軟件的過程性描述。從工程管理角度來看，軟件設計分兩步完成：概要設計和詳細設計。概要設計(又稱結構設計)將軟件需求轉化為軟件體系結構、確定系統(tǒng)級接口、全局數據結構或數據庫模式;詳細設計確立每個模塊的實現算法和局部數據結構,用適當方法表示算法和數據結構的細節(jié)。軟件設計的一般過程是：軟件設計是一個迭代的過程；先進行高層次的結構設計；后進行低層次的過程設計；穿插進行數據設計和接口設計。.軟件設計的基本原理：抽象模塊化

3）信息隱蔽（信息隱蔽指在一個模塊化內包含的信息（過程或數據），對于不需要這些信息的其他模塊來說是不能訪問的。）4）模塊獨立性（耦合性和內聚性是模塊獨立性的兩個定性標準,耦合和內聚是相互關聯的。內聚性是一個模塊內部各個元素間彼此結合的緊密程度的度量。耦合性是模塊間互相連接的緊密程度的度量。）內容耦合（耦合性最強）、公共耦合、外部耦合、控制耦合、標記耦合、數據耦合、非直接耦合（獨立性最強）軟件設計中，有利于提高模塊獨立性的一個準則是高內聚低耦合。二.概要設計軟件的概要設計又稱為總體結構設計，其主要任務是建立軟件系統(tǒng)的總體結構。結果得到一個優(yōu)化的軟件結構圖。常見的軟件結構設計工具是結構圖（SC）,也稱為程序結構圖。經常使用的結構圖有四種模塊類型：傳入模塊、傳出模塊、變換模塊和協調模塊。

有關術語：深度：表示控制的層數。寬度：整體控制跨度（最大模塊數的層）的表示。扇入：調用一個給定模塊的模塊個數。扇出：一個模塊直接調用的其他模塊數。原子模塊：樹中位于葉子結點的模塊。面向數據流的設計方法中，典型的數據流類型有兩種：變換型和事務型。二詳細設計r詳質設計階段的任務是為軟件結構圖中的每一個模塊確定實現算法和局部數據結構，用某種選定的表達工具表示算法和數據結構的細節(jié)O詳細設算階段的根本目標是確定應該怎樣具體的實現所要求的系統(tǒng)，但詳細設計階段的任務還不是具體的編寫程序，而是要設計出程序的“藍圖”，以后程序員將根據這個藍圖寫出實際的程序代碼。因此，詳細設計階段的結果基本上就決定了最終的程序代碼的質里,o2.常見的過程設計工具有：A圖形工具：程序流程圖(PFD),N-S,PAD,HIPOB表格工具：判定表C語言工具：PDL(偽碼)1)程序流程圖(PFD)：它是一種傳統(tǒng)的、應用廣泛的軟件過程設計表示工具，通常也稱為流程框圖。程序流程圖表達直觀、清晰、易于學習掌握，且獨立于任何一種程序設計語言。注：一控制流口加工步驟O邏輯條件N-S圖：提出了用方框圖來代替?zhèn)鹘y(tǒng)的程序流程圖。PAD圖：它是問題分析圖(ProblemAnalysisDiagram)的英文縮寫。它是繼程序流程圖和方框圖之后，提出的又一種主要用于描述軟件詳細設計的圖形表示工具。(樹型結構)PAD圖的特征：A結構清晰，結構化程度高;B易于閱讀C最左端的縱線是程序主干線，對應程序的第一層結構；每增加一層PAD圖向右擴展一條縱線，故程序的縱線數等于程序層次數。D程序執(zhí)行：從PAD圖最左主干線上端結點開始，自上而下，自向而右依次執(zhí)行，程序終止于最左主干線。PDL過程設計語言(PDL)也稱為結構化的英語和偽碼，它是一種混合語言，采用英語的詞匯和結構化程序設計語言的語法，類似編碼語言?？键c四:軟件測試一.軟件測試的目的測試的目的是發(fā)現軟件中的錯誤。經驗表明，程序中存在錯誤的概率與該程序中已發(fā)現的錯誤數成正比。這一現象說明，為了提高測試效率，測試人員應該集中對付那些錯誤群集的程序。一個成功的測試是發(fā)現了至今尚未發(fā)現的

錯誤的測試.三.軟件測試技術從是否需要執(zhí)行被測軟件的角度，可以分為靜態(tài)測試和動態(tài)測試方法。按功能劃分為白盒測試和黑盒測試方法。.靜態(tài)測試與動態(tài)測試靜態(tài)測試不實際運行軟件,主要通過人工進行。動態(tài)測試是基于計算機的測試，是為了發(fā)現錯誤執(zhí)行程序的過程.白盒測試與黑盒測試.白盒測試方法也稱結構測試或邏輯驅動測試。它是根據軟件的內部工作過程，檢查內部成分。主要方法有邏輯覆蓋（語句覆蓋、路徑覆蓋、判定覆蓋、條件覆蓋、判斷■條件覆蓋（查錯能力最強））、基本路徑測試（最強的覆蓋準則）。白盒測試屬于動態(tài)測試。（白盒測試的基本原則是：保證所測模塊中每一獨立路徑至少執(zhí)行一次；保證所測模塊每一循環(huán)都在邊界條件和一般條件下個執(zhí)行一次；驗證所有內部結構的數據有效性?！鞍缀小狈ㄊ歉F舉路徑測試。）

.黑盒測試方法也稱功能測試或數據驅動測試。它是對軟件已經實現的功能是否滿足需求進行測試和驗證。它不考慮程序內部的邏輯結構和內部特性，只依據程序的需求和功能規(guī)格說明,檢查程序的功能是否符合它的功能說明。主要方法有：等價類劃分法、邊界值分析法、錯誤推測法、因果圖等，主要用于軟件確認測試。白盒法是根據程序的內部邏輯來設計測試用例的。黑盒法是根據程序的功能來設計測試用例的。注：白盒、黑盒法都不可能使測試達到徹底。四.軟件測試的實施軟件測試過程一般按4個步驟進行，即單元測試、集成測試、驗收測試（確認測試）和系統(tǒng)測試1）單元測試單元測試的技術可以采用靜態(tài)分析和動態(tài)測試。對動態(tài)測試多采用白盒動態(tài)測試為主，輔之以黑盒測試。單元測試的依據是詳細設計說明書和源程序。

單元測試的目的是發(fā)現各模塊內部可能存在的各種錯誤。2）集成測試（概要設計階段進行）集成測試是測試和組裝軟件的過程。集成測試的目的是發(fā)現與接口有關的錯誤。集成測試的依據是概要設計說明書。人們提出了自頂向下和自底向上相結合、從兩頭向中間副近的混合式組裝方法，被形象稱之為“三明治”方法。3）確認測試（需求分析階段進行）確認測試的任務是驗證軟件的功能和性能及其它特性是否滿足了需求規(guī)格說明中確定的各種需求，以及軟件配置是否完全、正確。確認測試首先運用黑盒方法,對軟件進行有效性測試。對軟件是否能達到用戶所期望的要求的測試稱為有效性測試.以需求規(guī)格說明文檔作為測試基礎。以4）系統(tǒng)測試系統(tǒng)測試是在真實的系統(tǒng)工作環(huán)境下檢驗軟件是否能與系統(tǒng)正確連接，發(fā)現軟件與系統(tǒng)需求

不一致的地方。系統(tǒng)測試的目的是盡可能多的發(fā)現軟件系統(tǒng)中的錯誤和缺陷。考點五:程序的調試程序調試的任務是診斷和改正程序中的錯誤。一.程序序調試的基本步驟：1）錯誤定位2）修改設計和代碼，以排除錯誤3）進行回歸測試，防止引進新的錯誤。二.軟件調試方法：調試的關鍵在于推斷程序內部的錯誤位置及原因。主要的調試方法有強行排錯法（設置斷點和監(jiān)視表達式）、回溯法（適合小規(guī)模程序）和原因排除法（通過演繹和歸納，以及二分法來實現）。第四章 數據庫設計基礎（四大考點）考點一:數據庫系統(tǒng)的基本概念一.數據、數據庫、數據庫管理系統(tǒng)?數據數據實際上就是描述事物的符號記錄。計算機中的數據一般分為兩部分，即臨時性數據和持久性數據。數據庫系統(tǒng)中處理的就是持久性數據。軟件中的數據是有一定結構的，數據有型（類型）和值之分。.數據庫數據庫（簡稱DB）是數據的集合，它具有統(tǒng)一的結構形式并存放于統(tǒng)一的存儲介質內，是多種應用數據的集成，并可被各個應用程序所共享。數據庫存放數據是按數據所提供的數據模式存放的，數據庫中的數據具有“集成”、“共享”的特點，即數據庫集中了各種應用的數據，進行統(tǒng)一的構造和存儲，而使它們可被不同應用程序所使用。.數據庫管理系統(tǒng)數據庫管理系統(tǒng)（簡稱DBMS）是數據庫的機構，它是一種系統(tǒng)軟件，負責數據庫中的數據組織、數據操縱、數據維護、控制及保護和數據服務等。數據庫管理系統(tǒng)是數據庫系統(tǒng)的核心。其主要六個功能有：1）數據模式定義2）數據存取的物理構建3）數據操縱4）數據的完整性、安全性定義與檢查5）數據庫的并發(fā)控制與故障恢復6）數據的服務數據庫管理系統(tǒng)一般提供相應的數據語言，它們是：數據定義語言（簡稱DDL）：該語言負責數據的模式定義與數據的物理存取構建。數據操縱語言（簡稱DML）：該語言負責數據的操縱，包括查詢及增、刪、改等操作。數據控制語言（簡稱DCL）：該語言負責數據完整性、安全性的定義與檢查以及并發(fā)控制、故障恢復等功能。上述數據語言按其使用方法具有兩種結構形式：交互式命令語言（又稱為自含型或自主型語言）2）宿主型語言。.數據庫管理員數據庫管理員（簡稱DBA）.其主要工作有：1）數據庫設計2）數據庫維護3）改善系統(tǒng)性能，提高系統(tǒng)效率..數據庫系統(tǒng)數據庫系統(tǒng)（簡稱DBS）.由五個部分構成:1）數據庫（數據）2）數據庫管理系統(tǒng)（軟件）3）數據庫管理員（人員） 4）硬件平臺（硬件）5）系統(tǒng)平臺（軟件）6.數據庫應用系統(tǒng)（簡稱DBAS）.數據庫系統(tǒng)的發(fā)展數據庫系統(tǒng)經歷了三個階段:人工管理階段、文件系統(tǒng)階段和數據庫系統(tǒng)階段.數據庫系統(tǒng)的基本特點數據庫系統(tǒng)基本特點有：1）數據的集成性（全局與局部的結構模式構成了數據庫系統(tǒng)數據集成性的主要特征）2）數據的高共享性與低冗余性（數據的一致性是指在系統(tǒng)中同一數據的不同出現應保持相同的值）3）數據獨立性（數據獨立性是數據與程序間的互不依賴性。數據的獨立性一般分為物理獨立性和邏輯獨立性兩級。物理獨立性是指數據的物理結構的改變，不會影響數據庫的邏輯結構。邏輯獨立性是指數據庫總體邏輯結構的改變，不需要相應修改應用程序。）4）數據統(tǒng)一管理與控制（主要包含三個方面：數據的完整性檢查、數據的安全性保護、并發(fā)控制）四.數據庫系統(tǒng)的內部結構體系數據庫系統(tǒng)的內部結構體系:數據庫系統(tǒng)在其內部具有三級模式及二級映射，三級模式分別為概念級模式、內部級模式與外部級模式，二級映射則是分別是概念級到內部級的映射以及外部級到概念級的映射。概念模式是數據庫系統(tǒng)中全局數據邏輯結構的描述，是全體用戶公共數據視圖。（可用DBMS中的DDL語言定義o）外部模式，也稱子模式或用戶模式，它是用戶的數據視圖，也是用戶所見到的數據模式。（用外模式DDL描述。）內部模式，又稱物理模式，它給出了數據庫物理存儲結構與物理存取方法。（用內模式DDL描述。）考點二:數據模型一.數據模型的基本概念數據是現實世界符號的抽象，而數據模型是數據特征的抽象.其描述的內容有三個部分，它們是數據結構、數據操作與數據約束。數據模型按不同的應用層次分成三種類型：1）概念數據模型簡稱概念模型。（它是一種面向客觀世界、面向用戶的模型；它與具體的數據庫管理系統(tǒng)無關,與具體的計算機平臺無關。較為有名的概念模型有E-R模型）以模式（或概念模式）為框架的數據庫稱為概念數據庫。關系數據庫的概念模型是關系模式的集合。2）邏輯數據模型又稱為數據模型。（它是一種面向數據庫系統(tǒng)的模型，常見的有：層次模型、網狀模型、關系模型、面向對象模型等）以子模式為框架的數據庫稱為用戶數據庫。3）物理數據模型又稱為物理模型。（它是一種面向計算機物理表示的模型，此模型給出了數據模型在計算機上物理結構的表示。）以物理模式為框架的數據庫稱為物理數據庫。二.E-R模型廣泛使用的概念模型是E-R模型（或實體聯系模型），它于1976年由PeterChen首先提出。E-R模型的基本概念1）實體（它是概念世界中的基本單位，它們是客觀存在的且又能相互區(qū)別的事物。凡是有共性的實體可組成一個集合稱為實體集。）2）屬性（它是現實世界中事物的特性。一個屬性的取值范圍稱為該屬性的值域或值集）3）聯系（它是指現實世界中事物間的關聯）兩個實體集間的聯系實際上是實體集間的函數關系，這種函數關系可以有下面幾種：一對一的聯系（簡記為1：1）一對多或多對一聯系（簡記為1：M或M：1）多對多聯系（簡記M：N）oE-R模型由上面三個基本概念組成。由實體、聯系、屬性三者結合起來才能表示現實世界。E-R模型（設計關系模式）是概念設計與邏輯設計起橋梁作用。1）實體集表示法（用矩形表示實體集，在矩形內寫上該實體集的名字）2）屬性集表示法（用橢圓形表示屬性，在橢圓內寫上該屬性的名稱）4）聯系表示法（有菱形（內寫上聯系名）表示聯系）.層次模型層次模型是最早發(fā)展起來的數據庫模型。它的基本結構是樹形結構。它們自頂向下、層次分明。但樹結構是受到限制的，每棵樹有且僅有一個無雙親結點，即根；樹中除根外所有結點有且僅有一個雙親。.網狀模型它的出現略晚于層次模型。在結構上較層次模型好，不像層次模型那樣滿足嚴格的條件。網狀模型將通用的網絡拓樸結構分成一些基本結構，一般規(guī)定根結點與任一葉子結點間的聯系均是一對多的聯系。.關系模型1）關系的數據結構關系模型采用二維表來表示，簡稱表。二

維表由表框架及表的元組組成。表框架由N個命名的屬性組成，N稱為屬性元數。每個屬性有一個取值范圍稱為值域。在表框架中按行可以存放數據，每行數據稱為元組。一個表框架可以存放M個元組，M稱為表的基數。二維表一般滿足7個性質：元組個數有限性、元組的唯一性、元組的次序無關性、元組分量的原子性、屬性名惟一性、屬性的次序無關性、分量值域的同一性。以二維表為基本結構所建立的模型稱為關系模型。鍵具有標識元組、建立元組間聯系等重要作用。在二維表中凡能惟一標識元組的最小屬性集稱為該表的鍵或碼。二維表中可能有若干個鍵，它們稱為該表的候選碼或候選鍵。從二維表的所有候選鍵中選取一個作為用戶使用的鍵稱為主鍵或主碼，一般主鍵也簡稱為鍵或碼。表A中的某些屬性集是某B的鍵，則稱該屬性集為A的外鍵或外碼。表中一定要有鍵。

空值表示未知的值或不可能出現的值，一般用NULL表示。關系框架稱為關系的模式，關系模式支持子模式，關系子模式是關系數據庫模式中用戶所見到的那部分數據模式描述。它也是二維表結構，關系子模式對應用戶數據庫稱為視圖2）關系操縱數據查詢、數據刪除、數據插入、數據修改。3）關系中的數據約束關系模型允許定義三類數據約束，它們是實體完整性、參照完整性、用戶自定義的完整性約束。其中前種由關系數據庫系統(tǒng)自動支持。相關知識點：1）數據庫管理系統(tǒng)是位于用戶與操作系統(tǒng)之間的一層系統(tǒng)管理軟件，是一種系統(tǒng)軟件，是用戶與數據庫之間的一個標準接口。其總是基于某種數據模型，可以分為層次模型、網狀模型和關系模型。2）在關系模型的數據語言中，一般除了運用常規(guī)的集合運算（并、交、差、笛卡爾積等），還定義了一些專門的關系運算,如投影、選擇、連接等。前者是將關系（即二維表）看成是元組的集合，這些運算主要是從二維表的行的方向來進行的。后者是從二維表的列的方向來進行運算的。3）關系數據模型誕生之后迅速發(fā)展，深受用戶喜愛，但關系數據模型也有缺點，其最主要的缺點是由于存取路徑對用戶透明，查詢效率往往不如非關系數據模型，因此為了提高性能，必須對用戶的查詢請求進行優(yōu)化。考點三:關系代數一.關系模型的基本運算1）插入設有關系R需插入若干元組，要插入的元組組成關系R，,則插入可用集合并運算表示為:RUR，刪除設有關系R需刪除一些元組，要刪除的元組組成關系R，則刪除可用集合差運算表示為:R-R，3）修改設需修改的元組構成關系R，則先做刪除得:R-R，設修改后的元組構成關系R”,此時將其插入即得到結果（RR）UR”4）查詢投影運算（表示為兀12,???Aim（R））選擇運算（表示為。f（R）邏輯條件F是一個邏輯表達式.基本邏輯條件:V、＞、W、2、手復合邏輯條件有：八（并且）、V（或者）、?（否））c）笛卡爾積運算（對于兩個關系R（n元關系P個元組）與S（m元關系q個元組）的合并操作可以用笛卡爾積T表示，記為T=RXS 該關系是一個n+m元系,元組個數是pXq）二.關系代數中的擴充運算：1）交運算（記為：RAS）2）除運算（如果將笛卡爾積看作乘，那么除運算就是它的逆運算。表示為：T+R=S或自然連接可記為：R|X|S通過公共域的相等值進行連接.）考點四:數據庫設計與管理一.數據庫設計概述數據庫設計的基本任務:根據用戶對象的信息需求、處理需求和數據庫的支持環(huán)境（包括硬件、操作系統(tǒng)與DBMS）設計出數據模式。數據庫設計中有兩種方法，一是面向數據；二是面向過程。面向數據的設計方法已成為主流方流。數據庫設計目前一般采用生命周期法,它們是:需求分析階段、概念設計階段、邏輯設計階段、物理設計階段、編碼階段、測試階段、運行階段等。數據庫設計中采用前四個階段，并且重點以數據結構與模型的設計為主線。

二.數據庫設計的需求分析需求分析是整個設計活動的基礎，也是最困難、最花時間的一步。分析和表達用戶的需求，經常采用的方法有結構化分析方法和面向對象的方法。結構化分析（簡稱SA方法）方法用自頂向下、逐層分解的方法分析系統(tǒng)。用數據流圖（簡記為DFD）表達了數據和處理過程的關系。數據字典對系統(tǒng)中數據的詳盡描述,是各類數據屬性的清單。（數據字典是各類數據描述的集合，它通常包括5個部分，即數據項，是數據的最小單位；數據結構；數據流；數據存儲；處理過程）三.數據庫概念設計數據庫概念設計的目的是分析數據間內在的語義關聯,在此基礎上建立一個數據的抽象模型。數據庫概念設計的方法有兩種：集中式模式設計法（統(tǒng)一的模式設計方法）和視圖集成設計法（一種分散到集中的方法）。視圖設計一般有3種設計次序，它們分別是自頂向下、自底向上和由內向外，它們又為視圖設計提供了具體的操作方法，設計者可根據實

際情況靈活掌握,可以單獨使用也可混合使用O視圖集成的常見沖突：命名沖突、概念沖突、域沖突、約束沖突三.數據庫的邏輯設計.從E-R圖向關系模式轉換數據庫邏輯設計的主要工作是將E-R圖轉換成指定RDBMS中的關系模式。首先，從E-R圖到關系模式的轉換是比較直接的，實體與聯系都可以表示成關系，E-R圖中屬性也可以轉換成關系的屬性。實體集也可以轉換成關系。.邏輯模式規(guī)范化及調整、實現.關系視圖設計關系視圖的作用大致有三點:提供數據邏輯獨立性、能適應用戶對數據的不同需求、有一定數據保密功能。四.數據庫的物理設計數據庫物理設計的主要目標是對數據庫內部物理結構作調整并選擇合理的存取路徑，以提高數據庫訪問速度及有效利用存儲空間。留給用戶參與物理設計的內容有：索引設計、集簇設計和分區(qū)設計。五.數據庫管理數據庫管理包括六個內容：數據庫的建立、數據庫的調整、數據庫的重組、數據庫安全性控制與完整性控制、數據庫的故障恢復、數據庫監(jiān)控。數據庫恢復是將數據庫中的數據從錯誤狀態(tài)中恢復到某種邏輯一致的狀態(tài)。如果數據庫中包含成功事務提交的結果，則稱數據庫處于一致性狀態(tài)。數據庫保護分為：安全性控制、完整性控制、并發(fā)性控制、數據的恢復。第一套⑴下面敘述正確的是o（C）A.算法的執(zhí)行效率與數據的存儲結構無關B.算法的空間復雜度是指算法程序中指令（或語句）的條數（指的是算法所占用的空間）C.算法的有窮性是指算法必須能在執(zhí)行有限個步驟之后終止D.以上三種描述都不對(2)以下數據結構中不屬于線性數據結構的是。(C)A.隊列B.線性表C.二叉樹D.棧(3)在一棵二叉樹上第5層的結點數最多是o(B)2n-18163215(4)下面描述中，符合結構化程序設計風格的是o(A)A.使用順序、選擇和重復(循環(huán))三種基本控制結構表示程序的控制邏輯B.模塊只有一個入口，可以有多個出口(可以有0個入口)C.注重提高程序的執(zhí)行效率D.不使用goto語句(只是限制使用)(5)下面概念中，不屬于面向對象方法的是 。(D)A.對象B.繼承C.類D.過程調用(6)在結構化方法中，用數據流程圖(DFD)作為描述工具的軟件開發(fā)階段是o(B)A.可行性分析B.需求分析C.詳細設計D.程序編碼(7)在軟件開發(fā)中，下面任務不屬于設計階段的是o(D)A.數據結構設計B.給出系統(tǒng)模塊結構C.定義模塊算法D.定義需求并建立系統(tǒng)模型(8)數據庫系統(tǒng)的核心是o(B)A.數據模型B.數據庫管理系統(tǒng)C.軟件工具D.數據庫(9)下列敘述中正確的是o(C)A.數據庫是一個獨立的系統(tǒng)，不需要操作系統(tǒng)的支持B.數據庫設計是指設計數據庫管理系統(tǒng)C.數據庫技術的根本目標是要解決數據共享的問題D.數據庫系統(tǒng)中，數據的物理結構必須與邏輯結構一致(10)下列模式中，能夠給出數據庫物理存儲結構與物理存取方法的是o(A)A.內模式B.外模式C.概念模式D.邏哮式套(1)算法的時間復雜度是指o(C)A.執(zhí)行算法程序所需要的時間B.算法程序的長度C.算法執(zhí)行過程中所需要的基本運算次數D.算法程序中的指令條數(2)下列敘述中正確的是o(A)A.線性表是線性結構B.棧與隊列是非線性結構C.線性鏈表是非線性結構D.二叉樹是線性結構⑶設一棵完全二叉樹共有699個結點，則在該二叉樹中的葉子結點數為o(B)349350255351(4)結構化程序設計主要強調的是 。(B)A.程序的規(guī)模B.程序的易讀性C.程序的執(zhí)行效率D.程序的可移植性⑸在軟件生命周期中，能準確地確定軟件系統(tǒng)必須做什么和必須具備哪些功能的階段是o(D)A.概要設計B.詳細設計C.可行性分析D.需求分析(6)數據流圖用于抽象描述一個軟件的邏輯模型，數據流圖由一些特定的圖符構成。下列圖符名標識的圖符不屬于數據流圖合法圖符的是。(A)A.控制流B.加工C.數據存儲D.源和潭⑺軟件需求分析階段的工作，可以分為四個方面：需求獲取、需求分析、編寫需求規(guī)格說明書以及o(B)A.階段性報告B.需求評審C.總結D.都不正確(8)下述關于數據庫系統(tǒng)的敘述中正確的是o(A)A.數據庫系統(tǒng)減少了數據冗余B.數據庫系統(tǒng)避免了一切冗余C.數據庫系統(tǒng)中數據的一致性是指數據類型的一致D.數據庫系統(tǒng)比文件系統(tǒng)能管理更多的數據(9)關系表中的每一橫行稱為一個 。(A)A.元組B.字段C.屬性

D.碼(10)數據庫設計包括兩個方面的設計內容，它們是O(A)A.概念設計和邏輯設計B.模式設計和內模式設計C.內模式設計和物理設計D.結構特性設計和行為和性域計第三套⑴算法而空間復雜度是指。(D)A.度是指。(D)B.算法程序中的指令條數C.算法程序所占的存儲空間D.算法執(zhí)行過程中所需要的存儲空間(2)下列關于棧的敘述中正確的是 。(D)A.在棧中只能插入數據B.在棧中只能刪除數據C.棧是先進先出的線性表D.棧是后進先出的線性表(3)在深度為5的滿二叉樹中，葉子結點的個數為o(C)32B.311615(4)對建立良好的程序設計風格，下面描述正確的是O(A)A.程序應簡單、清晰、可讀性好B.符號名的命名要符合語法C.充分考慮程序的執(zhí)行效率D.程序的注釋可有可無(5)下面對對象概念描述錯誤的是 。(A)A.任何對象都必須有繼承性B.對象是屬性和方法的封裝體C.對象間的通訊靠消息傳遞D.操作是對象的動態(tài)性屬性(6)下面不屬于軟件工程的3個要素的是o(D)A.工具B.過程C.方法D.環(huán)境(7)程序流程圖(PFD)中的箭頭代表的是o(B)A.數據流B.控制流C.調用關系D.組成關系(8)在數據管理技術的發(fā)展過程中，經歷了人工管理階段、文件系統(tǒng)階段和數據庫系統(tǒng)階段。其中數據獨

立性最高的階段是 o(A)A.數據庫系統(tǒng)B.文件系統(tǒng)C.人工管理D.數據項管理(9)用樹形結構來表示實體之間聯系的模型稱為o(B)A.關系模型B.層次模型C.網狀模型D.數據模型(10)關系數據庫管理系統(tǒng)能實現的專門關系運算包括 。(B)A.排序、索引、統(tǒng)計B.選擇、投影、連接C.關聯、更新、排序D.顯示、打印、制表第四套⑴算法一般都可以用哪幾種控制結構組合而成o(D)制表第四套A.循環(huán)、分支、遞歸B.順序、循環(huán)、嵌套C,循環(huán)、遞歸、選擇D.順序、選擇、循環(huán)(2)數據的存儲結構是指o(B)A.數據所占的存儲空間量B.數據的邏輯結構在計算機中的表示C.數據在計算機中的順序存儲方式D.存儲在外存中的數據⑶在面向對象方法中，一個對象請求另一對象為其服務的方式是通過發(fā)送o(D)D.消息A.調用語句B.命令C.口令(4)檢查軟件產品是否符合需求定義的過程稱為O(A)A.確認測試B.集成測試C.驗證測試D.驗收測試⑸下列工具中屬于需求分析常用工具的是o(D)A.PADPFDN-SDFD(6)下面不屬于軟件設計原則的是 。(C)A.抽象B.模塊化C.自底向上D.信息隱蔽(7)索引屬于o(B)A.模式B.內模式C.外模式D.概念模式(8)在關系數據庫中，用來表示實體之間聯系的是o(D)A.樹結構B.網結構C.線性表D.二維表(9)將E-R圖轉換到關系模式時，實體與聯系都可以表示成 。(B)A.屬性B.關系C.鍵D.域第五套(1)在下列選項中，哪個不是一個算法一般應該具有的基本特征 。(C)A.確定性B.可行性C.無窮性D.擁有足夠的情報(2)希爾排序法屬于哪一種類型的排序法o(B)A.交換類排序法B.插入類排序法C.選擇類排序法D.建堆排序法(3)下列關于隊列的敘述中正確的是 。(C)A.在隊列中只能插入數據B.在隊列中只能刪除數據C.隊列是先進先出的線性表D.隊列是先進后出的線性表(4)對長度為N的線性表進行順序查找，在最壞情況下所需要的比較次數為 。(B)A.N+1B.N(N+l)/2N/2(5)信息隱蔽的概念與下述哪一種概念直接相關o(B)A.軟件結構定義B.模塊獨立性C.模塊類型劃分D.模擬耦合度(6)面向對象的設計方法與傳統(tǒng)的的面向過程的方法有本質不同，它的基本原理是o(C)A.模擬現實世界中不同事物之間的聯系B.強調模擬現實世界中的算法而不強調概念C使用現實世界的概念抽象地思考問題從而自然地解決問題D.鼓勵開發(fā)者在軟件開發(fā)的絕大部分中都用實際領域的概念去思考(7)在結構化方法中，軟件功能分解屬于下列軟件開發(fā)中的階段是o(C)A.詳細設計B.需求分析C總體設計D.編程調試(8)軟件調試的目的是o(B)A.發(fā)現錯誤B.改正錯誤C.改善軟件的性能D.挖掘軟件的潛能(9)按條件f對關系R進行選擇，其關系代數表達式為 。(C)R|X|RR|X|R6f(R)d.nm(10)數據庫概念設計的過程中，視圖設計一般有三種設計次序，以下各項中不對的是o(D)A.自頂向下B.由底向上C.由內向外D.若雌到局部第K套(1)在計算機中，算法是指o(C)A.查詢方法B.加工方法C.解題方案的準確而完整的描述D.排序方法(2)棧和隊列的共同點是o(C)A.都是先進后出B.都是先進先出C.只允許在端點處插入和刪除元素D.沒有共同點(3)已知二叉樹后序遍歷序列是dabecy中序遍歷序列是debac,它的前序遍歷序列是o(A)cedbaacbeddecabdeabc(4)在下列幾種排序方法中，要求內存量最大的是o(D)A.插入排序B.選擇排序C.快速排序D.歸并排序(5)在設計程序時，應采納的原則之一是o(A)A.程序結構應有助于讀者理解.不限制goto語句的使用C.減少或取消注解行D.程序越短越好(6)下列不屬于軟件調試技術的是 。(B)A.強行排錯法B.集成測試法C.回溯法D.原因排除法(7)下列敘述中，不屬于軟件需求規(guī)格說明書的作用的是 。(D)A.便于用戶、開發(fā)人員進行理解和交流B.反映出用戶問題的結構，可以作為軟件開發(fā)工作的基礎和依據C.作為確認測試和驗收的依據D.便于開發(fā)人員進行需求分析(8)在數據流圖(DFD)中，帶有名字的箭頭表示o(C)A.控制程序的執(zhí)行順序B.模塊之間的調用關系C.數據的流向D.程序的組成成分9)SQL語言又稱為o(C)A.結構化定義語B.結構化控制語_C.結構化查詢語:D.結構化操縱語言(10)視圖設計一般有3種設計次序，下列不屬于視圖設計的是o(B)A.自頂向下B.由外向內C.由內向外D.基唇迪上

第七套

(1)數據結構中，與所

使用的計算機無關的

是數據的o(C)A.存儲結構B.物理結構C.邏輯結構D.物理和存儲結構(2)棧底至棧頂依次存放元素A、B、C、D,在第五個元素E入棧前，棧中元素可以出棧，則出棧序列可能是o(D)ABCEDDBCEACDABEDCBEA(3)線性表的順序存儲結構和線性表的鏈式存儲結構分別是 。(B)A.順序存取的存儲結構、順序存取的存儲結構B.隨機存取的存儲結構、順序存取的存儲結構C.隨機存取的存儲結構、隨機存取的存儲結構D.任意存取的存儲結構、任意存取的存儲結構(4)在單鏈表中，增加頭結點的目的是 。(A)A.方便運算的實現B.使單鏈表至少有一個結點C.標識表結點中首結點的位置D.說明單鏈表是線性表的鏈式存儲實現(5)軟件設計包括軟件的結構、數據接口和過程設計，其中軟件的過程設計是指。(B)A.模塊間的關系B.系統(tǒng)結構部件轉換成軟件的過程描述C.軟件層次結構D.軟件開發(fā)過程(6)為了避免流程圖在描述程序邏輯時的靈活性，提出了用方框圖來代替?zhèn)鹘y(tǒng)的程序流程圖，通常也把這種圖稱為回PAD圖N-S圖C.結構圖D.數據流圖(7)數據處理的最小單位是o(C)A.數據B.數據元素C.數據項D.數據結構(8)下列有關數據庫的描述，正確的是 。(C)A.數據庫是一個DBF文件B.數據庫是一個關系C.數據庫是一個結構化的數據集合D.數據庫是一組文件(9)單個用戶使用的數據視圖的描述稱為 。(A)A.外模式B.概念模式C.內模式D.存儲模式(10)需求分析階段的任務是確定o(D)A.軟件開發(fā)方法B.軟件開發(fā)工具C.軟件開發(fā)費用D.螯膻統(tǒng)功能⑴算法分析的目的是o(D)A.找出數據結構的合理性B.找出算法中輸入和輸出之間的關系C.分析算法的易懂性和可靠性D.分析算法的效率以求改進n個頂點的強連通圖的邊數至少有 。(C)n-1n