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