計算機軟件基礎(chǔ)-資料下載頁

　　

【正文】 。當(dāng)無向圖G的頂點度數(shù)的最大值大于或等于頂點數(shù)的2倍時，G至少有一條回路。已知一個圖的鄰接矩陣表示，刪除所有從第i個節(jié)點出發(fā)的邊的方法是將第i行的值置0。在圖的鄰接表示存儲結(jié)構(gòu)上執(zhí)行深度優(yōu)先遍歷類似于二叉樹的先序遍歷。在圖的鄰接表示存儲結(jié)構(gòu)上執(zhí)行廣度優(yōu)先遍歷類似于二叉樹的按層次遍歷。一個圖的鄰接矩陣表示法是唯一的，而鄰接表表示法是不唯一的。在一個具有n個頂點的有向完全圖中，所含的邊數(shù)為n（n1）。n個頂點的連通圖中邊的條數(shù)至少為n1條。表示圖常用的存儲結(jié)構(gòu)為鄰接矩陣和鄰接鏈表。對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊節(jié)點分別有e個和2e個。在一個圖中，所有定點的度數(shù)之和等于所有邊數(shù)的兩倍。在一個有向圖中，所有定點的入度之和等于所有頂點的出度之和的1倍。一個有n個頂點的無向圖最多有n（n1）/2條邊。常用的查找方法假定對節(jié)點個數(shù)n=50的有序表進行折半查找，則對應(yīng)的折半查找判定樹高度為6，最后一層的節(jié)點個數(shù)為19。對于節(jié)點個數(shù)為n的線性表，若順序查找關(guān)鍵字為k的節(jié)點，則成功查找的時間復(fù)雜度為O（n）。在插入排序和選擇排序中，若原始數(shù)據(jù)已基本有序，則較適合選用插入排序。在最好情況下，對于具有n個元素的正序序列，若采用冒泡排序，所需的比較次數(shù)為n1。對有序表進行折半查找的過程可用判定樹來描述，其判定樹的形態(tài)只取決于元素的輸入順序。順序查找法適合于存儲結(jié)構(gòu)為順序存儲或鏈接存儲的線性表。對節(jié)點個數(shù)為18的順序存儲有序表，若采用折半查找，則查找第15個節(jié)點的成功查找次數(shù)為3。在一顆深度為h的具有n個節(jié)點的二叉排序樹中，查找所有節(jié)點的最大查找次數(shù)為h。設(shè)有一個長度為100的已排好序的表，用折半查找進行查找，若查找不成功，至少比較7次。從一顆二叉排序樹中查找一個元素時，若元素的值等于根節(jié)點的值，則表明查找成功，若元素的值小于根節(jié)點的值，則繼續(xù)向左子樹查找，若元素的值大于根節(jié)點的值，則繼續(xù)向右子樹查找。二分查找的存儲結(jié)構(gòu)僅限于順序存儲結(jié)構(gòu)，且是有序。采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為（n+1）/2。二叉排序樹上的查找長度不僅與節(jié)點個數(shù)有關(guān)，也與二叉排序樹的樹形有關(guān)。常用的排序方法什么是內(nèi)部排序？什么是外部排序？內(nèi)部排序是指待排序的數(shù)據(jù)量不大，在內(nèi)存中進行的排序。外部排序是指待排序的數(shù)據(jù)量較大，內(nèi)存中一次放不下，借助于外存進行排序。學(xué)習(xí)過的排序方法中哪些排序方法是穩(wěn)定的？直接插入排序、冒泡排序是穩(wěn)定的。排序的目的是為了對已排序的數(shù)據(jù)元素進行查找運算。若對一組記錄（475380、350、74）進行直接插入排序，當(dāng)把第8個記錄插入到前面已排序的有序表時，為尋找插入位置比較5次。具有24個記錄的序列，采用冒泡排序最少的比較次數(shù)是23次。在對n個元素進行直接插入排序的過程中，最多需要進行n1趟。在對n個元素進行直接冒泡排序的過程中，至少需要n1趟完成。排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列的一端的方法，稱為選擇排序。冒泡排序算法在最好的情況下的元素交換次數(shù)為0。在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是選擇排序。在待排序的元素序列基本有序的前提下，效率最高的排序方法是插入排序。排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列的一端的方法稱為選擇排序。設(shè)待排序數(shù)據(jù)元素序列有n個記錄，應(yīng)用冒泡排序方法，進行一趟排序，所需比較和交換記錄的最多次數(shù)分別為nn1。在插入排序、選擇排序、冒泡排序中，排序時不穩(wěn)定的有選擇排序。在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用插入排序；若初始數(shù)據(jù)基本反序，則選用選擇排序。對n個元素的序列進行冒泡排序時，最少的比較次數(shù)是n1。軟件工程概論什么是軟件危機？軟件危機產(chǎn)生的原因及其主要表現(xiàn)是什么？軟件危機是指軟件開發(fā)和維護工程中遇到的一系列嚴(yán)重問題，主要包括2個方面：如何高效的開發(fā)軟件以滿足日益增長的應(yīng)用需求；如何維護數(shù)量不斷膨脹的已有軟件。軟件開發(fā)與程序設(shè)計有什么不同？軟件開發(fā)是指一個軟件項目的開發(fā)，如市場調(diào)查，需求分析，可行性分析，初步設(shè)計，詳細(xì)設(shè)計，形成文檔，建立初步模型，編寫詳細(xì)代碼，測試修改，發(fā)布等。程序設(shè)計是軟件開發(fā)中的一個子過程。就是根據(jù)前期的調(diào)查，分析，設(shè)計文檔來進行程序設(shè)計。應(yīng)該按什么原則來劃分軟件生存周期的階段？按照軟件產(chǎn)品從開發(fā)、使用、維護、直至被淘汰的過程定義人家的生存周期。分為軟件定義、軟件開發(fā)和軟件維護三個階段。一般來說，應(yīng)該從技術(shù)、經(jīng)濟和操作三個方面研究目標(biāo)系統(tǒng)的可行性。模塊的獨立程序度可以由兩個定性標(biāo)準(zhǔn)度量，這兩個標(biāo)準(zhǔn)分別是耦合和內(nèi)聚。軟件過程包括3個要素：方法、工具和過程。軟件測試的目的是查找程序中的錯誤。為了提高測試效率，應(yīng)該選擇有代表性的數(shù)據(jù)作為測試數(shù)據(jù)。使用白盒測試法時，確定測試數(shù)據(jù)應(yīng)根據(jù)邏輯結(jié)構(gòu)和指定的覆蓋標(biāo)準(zhǔn)。結(jié)構(gòu)化分析方法是面向數(shù)據(jù)流進行需求分析的方法，使用DFD和數(shù)據(jù)字典（DD）構(gòu)成系統(tǒng)的邏輯模型。數(shù)據(jù)流圖的4種基本成分：終點、加工、數(shù)據(jù)流和數(shù)據(jù)存儲。從工程管理的角度看，軟件設(shè)計分兩步完成，首先總體設(shè)計然后詳細(xì)設(shè)計。軟件測試分4個步驟：單元測試、集成測試、確認(rèn)測試和系統(tǒng)測試。模塊內(nèi)聚度越高，說明模塊內(nèi)各成分彼此結(jié)合的程度越緊密。軟件設(shè)計階段的輸出主要是模塊。軟件需求分析是保證軟件質(zhì)量的重要步驟，它的實施應(yīng)該是在軟件定義階段。軟件文檔在軟件工程實施過程中十分重要，它不僅是軟件開發(fā)各階段的重要依據(jù)，而且影響軟件的可維護性。在瀑布模型中，將軟件劃分為若干個階段，軟件項目的可行性研究一般歸屬于計劃階段。程序的三種基本控制結(jié)構(gòu)是順序、選擇、循環(huán)。在結(jié)構(gòu)化分析中，用以表達系統(tǒng)內(nèi)部數(shù)據(jù)的運動情況的工具是數(shù)據(jù)流圖。在軟件生命周期中，能準(zhǔn)確地確定軟件系統(tǒng)必須做什么和必須具備哪些功能的階段是需求分析。檢查軟件產(chǎn)品是否符合需求定義的過程稱為確認(rèn)測試。在結(jié)構(gòu)化方法中，軟件功能分解屬于總體設(shè)計這個階段。軟件維護工作包括：正性維護、適應(yīng)性維護、完善性維護、預(yù)防性維護。軟件生命周期可分為軟件定義、軟件開發(fā)和軟件維護三個階段。模塊是程序中相對獨立的成分，其應(yīng)有良好的接口定義。軟件需求分析方法有：結(jié)構(gòu)化分析方法和軟件設(shè)計的分析方法。數(shù)據(jù)流圖的類型有交換型和事物型。從是否需要執(zhí)行被測軟件的角度，軟件測試可分為靜態(tài)測試和動態(tài)測試方法；若按功能劃分可分為白盒測試和黑盒測試。 整理分享