《數(shù)據(jù)結(jié)構(gòu)、算法和應(yīng)用(C++語(yǔ)言描述)》習(xí)題參考答案解析

..PAGEPAGE3/31第1章概論數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型的含義分別是什么？數(shù)據(jù)：對(duì)客觀事物的符號(hào)表示,在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并由計(jì)算機(jī)程序處理的符號(hào)的總稱。數(shù)據(jù)元素：數(shù)據(jù)的基本單位,在計(jì)算機(jī)程序中通常作為一個(gè)整體考慮。數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)元素之間的關(guān)系+運(yùn)算,是以數(shù)據(jù)為成員的結(jié)構(gòu),是帶結(jié)構(gòu)的數(shù)據(jù)元素的集合,數(shù)據(jù)元素之間存在著一種或多種特定的關(guān)系。不同的數(shù)據(jù)就必須要分配不同大小的內(nèi)存空間來(lái)存儲(chǔ),所有就要將數(shù)據(jù)劃分成不同的數(shù)據(jù)類型。數(shù)據(jù)類型包含取值范圍和基本運(yùn)算等概念。聯(lián)系是什么？輯結(jié)構(gòu)包含下面兩個(gè)方面的信息：①數(shù)據(jù)元素的信息；②各數(shù)據(jù)元素之間的關(guān)系。物理結(jié)構(gòu)：也叫儲(chǔ)存結(jié)構(gòu),是指邏輯結(jié)構(gòu)的存儲(chǔ)表示,即數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式,包括結(jié)點(diǎn)的數(shù)據(jù)和結(jié)點(diǎn)間關(guān)系的存儲(chǔ)表示。數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)是密不可分的,一個(gè)操作算法的設(shè)計(jì)取決于所選定的邏輯結(jié)構(gòu),,,選擇合理的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)非常重要。數(shù)據(jù)結(jié)構(gòu)的主要操作包括哪些？對(duì)于各種數(shù)據(jù)結(jié)構(gòu)而言,他們?cè)诨静僮魃鲜窍嗨频?最常用的操作有：創(chuàng)建：建立一個(gè)數(shù)據(jù)結(jié)構(gòu)；清除：清除一個(gè)數(shù)據(jù)結(jié)構(gòu)；插入：在數(shù)據(jù)結(jié)構(gòu)中增加新的結(jié)點(diǎn)；刪除：把指定的結(jié)點(diǎn)從數(shù)據(jù)結(jié)構(gòu)中刪除；訪問(wèn)：對(duì)數(shù)據(jù)結(jié)構(gòu)中的結(jié)點(diǎn)進(jìn)行訪問(wèn)；更新：改變指定結(jié)點(diǎn)的值或改變指定的某些結(jié)點(diǎn)之間的關(guān)系；查找：在數(shù)據(jù)結(jié)構(gòu)中查找滿足一定條件的結(jié)點(diǎn)；什么是抽象數(shù)據(jù)類型？如何定義抽象數(shù)據(jù)類型？抽象數(shù)據(jù)類型〔AbstractDataType簡(jiǎn)稱ADT是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。ADT是與具體的物理存儲(chǔ)無(wú)關(guān)的數(shù)據(jù)類型,因此,不論ADT的內(nèi)部結(jié)構(gòu)如何變化,只要其數(shù)據(jù)結(jié)構(gòu)的特性不變,都不影響其外部使用。對(duì)抽象數(shù)據(jù)類型的描述一般用〔D,R,P>三元組表示,抽象數(shù)據(jù)類型的定義格式為：ADT<抽象數(shù)據(jù)類型名>{數(shù)據(jù)對(duì)象D：<數(shù)據(jù)對(duì)象的定義>數(shù)據(jù)關(guān)系R：<數(shù)據(jù)關(guān)系的定義>基本操作P：<基本操作的定義>｝ADT<抽象數(shù)據(jù)類型名>其中,D,R是D,P是對(duì)D的基本操作集。數(shù)據(jù)對(duì)象和數(shù)據(jù)關(guān)系的定義用偽代碼來(lái)描述?；静僮鞯亩x格式為：基本操作名〔參數(shù)表初始條件：<初始條件描述>操作結(jié)果：<操作結(jié)果描述>初始條件說(shuō)明操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件；操作結(jié)果說(shuō)明操作完成后數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。什么是算法？算法的基本特征是什么？算法：是在有限的步驟內(nèi)解決數(shù)學(xué)問(wèn)題的過(guò)程,是以一步接一步的方式來(lái)詳細(xì)描述計(jì)算機(jī)如何將輸入轉(zhuǎn)化為所要求的輸出的過(guò)程,即算法是對(duì)計(jì)算機(jī)上執(zhí)行的計(jì)算過(guò)程的具體描述。一個(gè)有效的算法必須滿足的五個(gè)重要特性：都不能陷入無(wú)窮循環(huán)中。,,,更不允許有二義性。③輸入：算法有00個(gè)輸入是指算法本身給出了運(yùn)算對(duì)象的初始條件。1,有任何意義。⑤可行性：算法中要做的運(yùn)算都是基本運(yùn)算,能夠被精確地進(jìn)行。即算法中執(zhí)行的任何計(jì)算都可以被分解為基本的運(yùn)算步,每個(gè)基本的運(yùn)算步都可以在有限的時(shí)間內(nèi)完成。什么是算法分析？算法分析主要考慮哪幾方面的內(nèi)容？算法的研究與實(shí)際問(wèn)題直接相關(guān),用來(lái)解一個(gè)問(wèn)題可以有很多不同的算法,他們之間的法的性能。分析和評(píng)價(jià)算法的性能主要要考慮以下兩個(gè)方面：價(jià)要小。算法的時(shí)間代價(jià)的大小用算法的時(shí)間復(fù)雜度來(lái)度量。②空間代價(jià)：執(zhí)行算法所耗費(fèi)的存儲(chǔ)空間,主要是輔助空間。算法運(yùn)行所需的空間消耗是衡量算法優(yōu)劣的另一個(gè)重要因素。算法的空間代價(jià)的大小用算法的空間復(fù)雜度來(lái)度量。分析下面算法的時(shí)間復(fù)雜度?！?答：時(shí)間復(fù)雜度為n2〔2時(shí)間復(fù)雜度：nn〔3時(shí)間復(fù)雜度：n〔4時(shí)間復(fù)雜度：n2〔5時(shí)間復(fù)雜度：O<log2n>算法設(shè)計(jì)中的遞歸、窮舉、遞推和迭代等算法的基本思想是什么？,,推法：當(dāng)?shù)玫絾?wèn)題規(guī)模為i-1的解后,,能構(gòu)造出問(wèn)題規(guī)模為i,i=0i=1,i-1,,i的解直至得到問(wèn)題規(guī)模為n的解。n,然后從這些小問(wèn)題的解方便地構(gòu)造出更大問(wèn)題的解,并且這些規(guī)模較小的問(wèn)題也能采用同樣的,窮舉法：窮舉搜索法也稱窮舉法或搜索法是對(duì)可能是解的眾多候選解按某種順序進(jìn)行逐一枚舉和檢驗(yàn),并從中找出那些符合要求的候選解作為問(wèn)題的解。為實(shí)現(xiàn)這一過(guò)程所使用的方法統(tǒng)稱為迭代法。想是什么？分治策略的基本思想是把一個(gè)規(guī)模為n的問(wèn)題劃分為若干個(gè)規(guī)模較小,,所以可以遞歸地使用分治策略來(lái)求解。貪心策略的基本思想是把一個(gè)整體最優(yōu)問(wèn)題分解為一系列的最優(yōu)選擇問(wèn)題,決策一旦做出,就不能再更改。它是通過(guò)若干次的貪心選擇而得出最優(yōu)解〔或較優(yōu)解的一種解題策略。動(dòng)態(tài)規(guī)劃策略,通過(guò)對(duì)相同子問(wèn)題的求,,在貪心策略中,可能得不到問(wèn)題的最優(yōu)解。而在動(dòng)態(tài)規(guī)劃中,,目的是得到問(wèn)題的最優(yōu)解?；厮莶呗砸步性囂椒?它的基本思想是：在一些問(wèn)題求解進(jìn)程中,先選擇某一種可能情況向前探索,當(dāng)發(fā)現(xiàn)所選用的試探性操作不是最佳選擇,需退回一步,重新選擇繼續(xù)進(jìn)行試探,直到找到問(wèn)題的解或者證明問(wèn)題無(wú)解。分支定界策略也經(jīng)常被稱為分支限界策略,它的基本思想是：首先確定目標(biāo)值的上下界,然后一邊搜索一邊剪掉空間樹的某些不可能產(chǎn)生最優(yōu)解的分支,提高搜索效率。PAGEPAGE4/31.第二章線性表具有什么特征的數(shù)據(jù)結(jié)構(gòu)被稱為線性表？線性表〔n0,n稱為線性表的長(zhǎng)度。當(dāng)n=0時(shí)稱為空表。對(duì)于非空線性表,數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系,具體特性如下：第一個(gè)數(shù)據(jù)元素沒(méi)有前驅(qū)；最后一個(gè)數(shù)據(jù)元素沒(méi)有后繼外；其他數(shù)據(jù)元素都是首尾相接、有且只有一個(gè)前驅(qū)和后繼。如何實(shí)現(xiàn)線性表的順序存儲(chǔ)結(jié)構(gòu)？把線性表的結(jié)點(diǎn)按邏輯順序依次存放在一組地址連續(xù)的存儲(chǔ)單元里就構(gòu)成了線性表的順序存儲(chǔ),采用順序存儲(chǔ)結(jié)構(gòu)的線性表簡(jiǎn)稱順序表。線性表的順序存儲(chǔ)結(jié)構(gòu)有如下特點(diǎn)：線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；線性表的邏輯順序與物理順序一致；,即首地址為L(zhǎng)OC<e1>,每一個(gè)數(shù)據(jù)元素占k,則線性表中第i個(gè)元素ei在計(jì)算機(jī)存儲(chǔ)空間中的存儲(chǔ)地址為：LOC<ei>=LOC<e1>+<i-1>k4種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)？,簡(jiǎn)稱結(jié)數(shù)據(jù)域用,指針域,n鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。firste1e2…ei…en單向鏈表：,NULLfirste1e2…ei…en線性表的單向鏈?zhǔn)酱鎯?chǔ)循環(huán)鏈表：將單向鏈表最后一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn),這樣整個(gè)鏈表就構(gòu)成一個(gè)循環(huán),這種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為單向循環(huán)鏈表,簡(jiǎn)稱循環(huán)鏈表。頭結(jié)點(diǎn)的指針域指向線性表的第一個(gè)元素的結(jié)點(diǎn)；循環(huán)鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不再是NULL,而是指向頭結(jié)點(diǎn)。只有頭結(jié)點(diǎn)的循環(huán)鏈表稱為空循環(huán)鏈表。下圖是帶頭結(jié)點(diǎn)的非空循環(huán)鏈表和空循環(huán)鏈表示意圖。..PAGEPAGE31/31prevprevdatanextheadheade1…enhead頭結(jié)點(diǎn)頭結(jié)點(diǎn)〔a帶頭結(jié)點(diǎn)的非空循環(huán)鏈表〔b帶頭結(jié)點(diǎn)的空循環(huán)鏈表帶頭結(jié)點(diǎn)的循環(huán)鏈表雙向鏈表：雙向鏈表的每個(gè)結(jié)點(diǎn)含有兩個(gè)指針域,一個(gè)指針指向其前驅(qū)結(jié)點(diǎn)；另一個(gè)指針指向其后繼結(jié)點(diǎn)。雙向鏈表結(jié)點(diǎn)的結(jié)構(gòu)下圖〔a所示。firstende1e2…enfirst〔b雙向鏈表efirstende1e2…enfirst〔b雙向鏈表e1e2…en〔〔c雙向循環(huán)鏈表〔a〔a雙向鏈表結(jié)點(diǎn)結(jié)構(gòu)順序表和線性鏈表分別有哪些優(yōu)點(diǎn)和缺點(diǎn)？比較內(nèi)容順序存儲(chǔ)比較內(nèi)容順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)結(jié)點(diǎn)存儲(chǔ)空間 少〔不需要為表示結(jié)點(diǎn)的邏輯關(guān)系加開(kāi)銷空間利用率 低〔采用數(shù)組按表的最大長(zhǎng)度靜態(tài)配存儲(chǔ)空間插入、刪除操作 慢〔需要大量移動(dòng)元訪問(wèn)元素快〔直接訪問(wèn)多〔需要增加指針域來(lái)表示結(jié)點(diǎn)之間的邏輯關(guān)系高〔根據(jù)表的實(shí)際長(zhǎng)度動(dòng)態(tài)分配存儲(chǔ)空間快〔僅更改指針指向,不需要移動(dòng)元素慢〔通過(guò)指針移動(dòng)才能訪問(wèn)實(shí)現(xiàn)難易程度相對(duì)容易〔基于數(shù)組操作一般高級(jí)語(yǔ) 相對(duì)困難〔基于指針操作言都提供數(shù)組類型請(qǐng)列舉出一些線性表問(wèn)題的實(shí)例。①按員工號(hào)排序的員工基本情況表；②奧運(yùn)會(huì)各項(xiàng)比賽日程；③按學(xué)號(hào)記錄的學(xué)生的成績(jī)單；等等。在順序表中實(shí)現(xiàn)統(tǒng)計(jì)重復(fù)元素個(gè)數(shù)的操作：在教材[描述2-1]中,增加一個(gè)統(tǒng)計(jì)重復(fù)元素個(gè)數(shù)的成員函數(shù)intCount<constT&x>; 返回x出現(xiàn)的次數(shù)在教材的[描述2-2]中,增加查找重復(fù)元素個(gè)數(shù)的成員函數(shù)的實(shí)現(xiàn)：//實(shí)現(xiàn)統(tǒng)計(jì)重復(fù)元素個(gè)數(shù)template<classT>intLinearList<T>::Count<constT&x>{intcount=0;for<inti=0;i<length;i++>if<element[i]==x>count++;returncount;}在順序表中實(shí)現(xiàn)統(tǒng)計(jì)重復(fù)元素個(gè)數(shù)的操作：在教材[描述2-3]中,增加一個(gè)統(tǒng)計(jì)重復(fù)元素個(gè)數(shù)的成員函數(shù)intCount<constT&x>; 返回x出現(xiàn)的次數(shù)在教材的[描述2-4]中,增加查找重復(fù)元素個(gè)數(shù)的成員函數(shù)的實(shí)現(xiàn)：//實(shí)現(xiàn)統(tǒng)計(jì)重復(fù)元素個(gè)數(shù)template<classT>intLinkList<T>::Count<constT&x>{LinkNode<T>*p=head->next;intcount=0;while<p!=NULL&&>{if<p->data==x>count++;p=p->next;}returncount;}3章棧和隊(duì)列隊(duì)尾的概念是什么？棧：一種插入和刪除都只能在表的同一端進(jìn)行的線性表。隊(duì)列：一種只允許在表的一端進(jìn)行插入操作,而在表的另一端進(jìn)行刪除操作的線性表。先進(jìn)后出：元素是以e1,e2,……en順序進(jìn)入數(shù)據(jù)結(jié)構(gòu),以相反的順序即en,en-1,……e1離開(kāi)數(shù)據(jù)結(jié)構(gòu)。棧頂：允許進(jìn)行插入和刪除操作的一端。棧底：棧中與棧頂相對(duì)的另一端。先進(jìn)先出：元素是以e1,e2,……en以相同的順序即e1,e2,……en離開(kāi)數(shù)據(jù)結(jié)構(gòu)。隊(duì)頭：允許刪除操作的一端。隊(duì)尾：允許插入操作的一端。簡(jiǎn)述在順序棧的棧頂插入一個(gè)元素的操作過(guò)程。息；否則讓top的元素放入top一個(gè)棧的輸入序列為、2、3,可分為三種情況：①、當(dāng)只有一個(gè)存儲(chǔ)空間時(shí),只有一種出棧序列：1、2、3.②、當(dāng)有兩個(gè)存儲(chǔ)空間有：1、23, 1、3, 31等3種出棧序列③、當(dāng)存儲(chǔ)空間大于等于三個(gè),有3, 3, 1, 1等4出棧序列。循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么？在循環(huán)隊(duì)列中,僅依據(jù)頭尾指針相等,無(wú)法判斷隊(duì)列是"空還是"滿"。要解決這個(gè)問(wèn)題,常用的兩種方法是什么？列的存儲(chǔ)空間。兩種判斷隊(duì)列是"空"還是"滿"的方法：一是約定少用一個(gè)元素空間；二是使用計(jì)數(shù)器size記錄當(dāng)前隊(duì)列的實(shí)際長(zhǎng)度。簡(jiǎn)述在鏈接棧中插入一個(gè)元素的操作過(guò)程。然后將棧頂指針,使進(jìn)棧元素結(jié)點(diǎn)成為新的棧頂結(jié)點(diǎn)。6．請(qǐng)列舉出一些可以用棧和隊(duì)列表示的實(shí)際問(wèn)題。所有"<LIFO,LastInFirstOut所有"<FIFO,FirstInFirstOut問(wèn)題各種樹的層次遍歷和圖的廣度優(yōu)先遍歷等。4章數(shù)組、字符串與廣義表具有什么特征的數(shù)據(jù)結(jié)構(gòu)被稱為數(shù)組？數(shù)組可以看成是形如〔index,value的數(shù)據(jù)集合,其中,index是元素的索引,表示數(shù)據(jù)的邏輯位置,任意兩個(gè)數(shù)據(jù)的index都不相同；value表示數(shù)據(jù)元素的值。設(shè)有二維數(shù)組a[5][6],8a的起始地址是1000,試計(jì)算：〔1數(shù)組a的最后一個(gè)元素起始地址；1000+〔30-1*8=1232?！?,元素a[3][5]1000+〔3*6+5*8=1184〔3元素a[4][3]1000+〔3*5+4*8=1152請(qǐng)簡(jiǎn)述數(shù)組和矩陣的關(guān)系。1而不是像數(shù)組那樣從0開(kāi)始,并且使用A〔i,jA[i,j]的形式來(lái)引用矩陣中的元素。矩陣有哪些基本運(yùn)算？矩陣的操作包括轉(zhuǎn)置、加法、減法和乘法等。稀疏矩陣的特點(diǎn)是什么？為什么要對(duì)稀疏矩陣采用壓縮存儲(chǔ)技術(shù)？采用壓縮存儲(chǔ)技術(shù)主要是為了節(jié)省空間。設(shè)AB,請(qǐng)寫出矩陣相加的算法C=A+B。//#include<iostream>usingnamespacestd;#defineM50#defineN50#defineMaxSize20typedefintElemType;typedefstruct{intr;intc;ElemTyped;}TupNode;typedefstruct{introws;intcols;intnums;TupNodedata[MaxSize];}TSMatrix;intA[M][N],B[M][N];//建立三元組voidCreateMat<intA[M][N],TSMatrix&t,introw,intcol>{inti,j;t.rows=row;t.cols=col;t.nums=0;for<i=0;i<M;i++>{for<j=0;j<N;j++>{if<A[i][j]!=0>{t.data[t.nums].r=i;t.data[t.nums].c=j;t.data[t.nums].d=A[i][j];t.nums++;}}}}//矩陣相加intMatAdd<TSMatrix&a,TSMatrix&b,TSMatrix&c>{intElemTypev;if<a.rows!=b.rows||a.cols!=b.cols>return0;c.rows=a.rows;c.cols=a.cols;while<i<a.nums&&j<b.nums>{if<a.data[i].r==b.data[j].r>{if<a.data[i].c<b.data[j].c>{c.data[k].r=a.data[i].r;c.data[k].c=a.data[i].c;c.data[k].d=a.data[i].d;i++;k++;}elseif<a.data[i].c>b.data[j].c>{c.data[k].r=b.data[j].r;c.data[k].c=b.data[j].c;c.data[k].d=b.data[j].d;j++;k++;}else{v=a.data[i].d+b.data[j].d;if<v!=0>{c.data[k].r=a.data[i].r;c.data[k].c=a.data[i].c;c.data[k].d=v;k++;}i++;j++;}}elseif<a.data[i].r<b.data[j].r>{c.data[k].r=a.data[i].r;c.data[k].c=a.data[i].c;c.data[k].d=a.data[i].d;i++;k++;}else{c.data[k].r=b.data[j].r;c.data[k].c=b.data[j].c;c.data[k].d=b.data[j].d;j++;k++;}}if<i==a.nums>while<j<b.nums>{c.data[k].r=b.data[j].r;c.data[k].c=b.data[j].c;c.data[k].d=b.data[j].d;j++;k++;}if<j==b.nums>while<i<a.nums>{c.data[k].r=a.data[i].r;c.data[k].c=a.data[i].c;c.data[k].d=a.data[i].d;i++;k++;}c.nums=k;return1;}//輸出三元組voidDispMat<TSMatrixt>{inti;if<t.nums<=0>{cout<<"此矩陣所有元素都為"<<endl;return;}cout<<t.rows<<'\t'<<t.cols<<'\t'<<t.nums<<endl;cout<<" "<<endl;for<i=0;i<t.nums;i++>cout<<t.data[i].r<<'\t'<<t.data[i].c<<'\t'<<t.data[i].d<<endl<<endl;}//主函數(shù)intmain<>{intTSMatrixa,b,c;cout<<"請(qǐng)輸入矩陣的行、列數(shù)：\n";cin>>row>>col;cout<<"請(qǐng)輸入矩陣A的元素：\n";for<i=0;i<row;i++>for<j=0;j<col;j++>cin>>A[i][j];cout<<"請(qǐng)輸入矩陣B的元素：\n";for<i=0;i<row;i++>for<j=0;j<col;j++>cin>>B[i][j];CreateMat<A,a,row,col>;CreateMat<B,b,row,col>;cout<<"矩陣ADispMat<a>;cout<<"矩陣BDispMat<b>;if<MatAdd<a,b,c>>{cout<<"矩陣A、B相加后得到的三元組表示為：\n";DispMat<c>;}return0;}簡(jiǎn)述字符串與一維字符型數(shù)組的區(qū)別與聯(lián)系。在C/C++中的字符串使用為字符型數(shù)組來(lái)表示。為了便于確定字符\00作為字符串的截止符。列舉一些需要進(jìn)行字符串模式匹配的應(yīng)用場(chǎng)景。例如姓名查找某個(gè)學(xué)生、員工、居民。有效的模式匹配能極大地提高文本編輯程序的能力。9.列舉幾個(gè)字符串的其他操作。求字符串中某個(gè)子串出現(xiàn)的次數(shù),刪除滿足條件的子串,字符串字符移位等。什么是廣義表？廣義表與線性表的區(qū)別是什么？1 2 ,〔n≥0〔e,e……e但與線性表不,廣義表中的元素允許以不同的形式出現(xiàn)：它可以是一個(gè)原子〔邏輯上不能再分解的元素1 2 <a,<a,b,c>,d,e,<m,n>,<w,<i,j>,深度分別是多少？請(qǐng)畫出該廣義表的單鏈表存儲(chǔ)結(jié)構(gòu)示意圖。該廣義表的深度是3,長(zhǎng)度是6。該廣義表的單鏈表存儲(chǔ)結(jié)構(gòu)示意圖如下：headhead01a21d1e22head0head01wx1a1m2head011b1n1i1c1j請(qǐng)列舉出一些可以歸納成數(shù)組、矩陣、字符串和廣義表數(shù)據(jù)結(jié)構(gòu)的實(shí)際問(wèn)題。線性表的順序存儲(chǔ)、學(xué)生編號(hào)和姓名的問(wèn)題、各班級(jí)的學(xué)生編號(hào)和姓名的問(wèn)題等,都可以歸結(jié)為數(shù)組。等,不同職工的工資等都可以歸結(jié)為矩陣。等,都可歸結(jié)為字符串。應(yīng)用高斯消元法求解方程組可以歸結(jié)為廣義表。5章樹和二叉樹請(qǐng)簡(jiǎn)述樹、二叉樹、滿二叉樹和完全二叉樹的結(jié)構(gòu)特性。樹：只有最頂層的結(jié)點(diǎn)沒(méi)有前驅(qū),其余結(jié)點(diǎn)都有且只有一個(gè)前驅(qū)；一個(gè)結(jié)點(diǎn)可以沒(méi)有后繼,也可以有一個(gè)或多個(gè)后繼。二叉樹：一種特殊形態(tài)的樹,每個(gè)結(jié)點(diǎn)至多有兩個(gè)后繼。滿二叉樹：一種特殊形態(tài)的二叉樹,除了最后一層的結(jié)點(diǎn)為葉子結(jié)點(diǎn)外其它結(jié)點(diǎn)都有左、右兩棵子樹的二叉樹。完全二叉樹：一種特殊形態(tài)的二叉樹,其結(jié)點(diǎn)與相同深度的滿二叉樹中的結(jié)點(diǎn)編號(hào)完全一致,即對(duì)于深度為k的完全二叉樹,其前k-1層與深度為k的滿二叉樹的前k-1層完全一樣,只是在第k層上有可能缺少右邊若干個(gè)結(jié)點(diǎn)。請(qǐng)解釋結(jié)點(diǎn)的度、樹的度、結(jié)點(diǎn)的層、樹的深度、分支、路徑、路徑長(zhǎng)度、樹的路徑長(zhǎng)無(wú)序樹和森林等基本術(shù)語(yǔ)的含義。結(jié)點(diǎn)的度和樹的度：一個(gè)結(jié)點(diǎn)的后繼的數(shù)目稱為該結(jié)點(diǎn)的度,樹中各結(jié)點(diǎn)度的最大值稱為樹的度。樹的根結(jié)點(diǎn)所在的層為第1層,1,樹中各結(jié)點(diǎn)的層的最大值稱為樹的深度。分支、路徑、路徑長(zhǎng)度和樹的路徑長(zhǎng)度：從一個(gè)結(jié)點(diǎn)到其后繼結(jié)點(diǎn)之間的連線稱為一,從一個(gè)結(jié)點(diǎn)X到另一個(gè)結(jié)點(diǎn)Y所經(jīng)歷的所有分支構(gòu)成結(jié)點(diǎn)XY,路徑上的分支數(shù)目稱為路徑長(zhǎng)度,從樹的根結(jié)點(diǎn)到其他各個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和稱為樹的路徑長(zhǎng)度。0度不為0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)〔或非終端結(jié)點(diǎn),除根結(jié)點(diǎn)以外的分支結(jié)點(diǎn)也稱為內(nèi)部結(jié)點(diǎn)。孩子和雙親：在樹中,一個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)稱為該結(jié)點(diǎn)的孩子,相應(yīng)地,一個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)稱為該結(jié)點(diǎn)的雙親,即一個(gè)結(jié)點(diǎn)是其孩子結(jié)點(diǎn)的雙親、其雙親結(jié)點(diǎn)的孩子。兄弟和堂兄弟：同一雙親的孩子結(jié)點(diǎn)之間互稱為兄弟,不同雙親但在同一層的結(jié)點(diǎn)之間互稱為堂兄弟。祖先和子孫：從樹的根結(jié)點(diǎn)到某一個(gè)結(jié)點(diǎn)X不包括結(jié)點(diǎn)X稱為結(jié)點(diǎn)X,以某一結(jié)點(diǎn)XX外稱為結(jié)點(diǎn)X的子孫。有序樹和無(wú)序樹：對(duì)于樹中的任一結(jié)點(diǎn),如果其各棵子樹的相對(duì)次序被用來(lái)表示數(shù)據(jù)之間的關(guān)系,即交換子樹位置會(huì)改變樹所表示的內(nèi)容,則稱該樹為有序樹；否則稱為無(wú)序樹。森林：m〔m≥0棵互不相交的樹的集合就構(gòu)成了森林。請(qǐng)簡(jiǎn)述二叉樹的五條基本性質(zhì)。性質(zhì)：在二叉樹的第i層上至多有2i-12：深度為k2k-1個(gè)結(jié)點(diǎn)。性質(zhì)3：在二叉樹中,若度為0的結(jié)點(diǎn)〔即葉子結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2,則n0=n2+1。性質(zhì)4：nlog2n+1log2nlog2n的最大整數(shù)。性質(zhì)5：采用順序編號(hào)的完全二叉樹具有如下性質(zhì)：若一個(gè)分支結(jié)點(diǎn)的編號(hào)為i,則其左子樹的根結(jié)點(diǎn)〔即左孩子結(jié)點(diǎn)編號(hào)為2*i,右子樹的根結(jié)點(diǎn)〔即右孩子結(jié)點(diǎn)編號(hào)為2*i+1；反之,若一個(gè)非根結(jié)點(diǎn)的編號(hào)為i,則其雙親結(jié)點(diǎn)的編號(hào)為i/2〔其中i/2表示不大于i/2的最大整數(shù)。請(qǐng)簡(jiǎn)述二叉樹的常用操作及各操作的含義。創(chuàng)建一棵空二叉樹：創(chuàng)建一棵沒(méi)有任何結(jié)點(diǎn)的二叉樹。在順序表示中,根據(jù)樹的深度為結(jié)點(diǎn)分配內(nèi)存；在二叉鏈表表示中,將指向根結(jié)點(diǎn)的指針賦值為NULL。刪除一棵二叉樹：將二叉樹各結(jié)點(diǎn)所占據(jù)的內(nèi)存釋放。清空二叉樹：將二叉樹的所有結(jié)點(diǎn)刪除,使之成為一棵空二叉樹。以指定元素值創(chuàng)建根結(jié)點(diǎn)：創(chuàng)建根結(jié)點(diǎn),并以指定值作為根結(jié)點(diǎn)的元素值。將一個(gè)結(jié)點(diǎn)作為指定結(jié)點(diǎn)的左孩子插入：根據(jù)指定元素值生成一個(gè)新結(jié)點(diǎn),指定結(jié)點(diǎn)的左孩子。將一個(gè)結(jié)點(diǎn)作為指定結(jié)點(diǎn)的右孩子插入：根據(jù)指定元素值生成一個(gè)新結(jié)點(diǎn),指定結(jié)點(diǎn)的右孩子。,再訪問(wèn)根結(jié)點(diǎn)的左、右子樹；對(duì)于左、右子樹中的結(jié)點(diǎn)仍然是按照先序遍歷方式訪問(wèn),再訪問(wèn)根結(jié)點(diǎn)的左、右子樹。中序遍歷二叉樹：也稱為中根遍歷,其訪問(wèn)方式遞歸定義如下：對(duì)于一棵二叉樹,先訪問(wèn)根結(jié)點(diǎn)左子樹,再訪問(wèn)根結(jié)點(diǎn),最后訪問(wèn)右子樹；對(duì)于左、右子樹中的結(jié)點(diǎn)仍然是按照中序遍歷方式訪問(wèn)。后序遍歷二叉樹：也稱為后根遍歷,其訪問(wèn)方式遞歸定義如下：對(duì)于一棵二叉樹,先訪問(wèn)根結(jié)點(diǎn)的左子樹,后訪問(wèn)右子樹,最后訪問(wèn)根結(jié)點(diǎn)；對(duì)于左、右子樹中的結(jié)點(diǎn)仍然是按照后序遍歷方式訪問(wèn)。逐層遍歷二叉樹：1層開(kāi)始依次對(duì)每層中的結(jié)點(diǎn)按照從左至右的順序進(jìn)行訪問(wèn)。獲取指定結(jié)點(diǎn)的雙親結(jié)點(diǎn)：根據(jù)指定結(jié)點(diǎn)獲取其雙親結(jié)點(diǎn)。在順序表示中,據(jù)指定結(jié)點(diǎn)的位置計(jì)算雙親結(jié)點(diǎn)的位置；在二叉鏈表表示中,則需要從根結(jié)點(diǎn)開(kāi)始遍歷二叉樹直至找到指定結(jié)點(diǎn)的雙親結(jié)點(diǎn)。刪除以指定結(jié)點(diǎn)為根的子樹：將以指定結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹上的所有結(jié)點(diǎn)〔包括指定結(jié)點(diǎn)刪除。按關(guān)鍵字查找結(jié)點(diǎn)：按照某種規(guī)則〔先序、中序、后序或逐層依次訪問(wèn)二叉樹中的每一結(jié)點(diǎn),直至找到與關(guān)鍵字匹配的結(jié)點(diǎn)。判斷二叉樹是否為空：判斷一棵二叉樹是否為空二叉樹。修改指定結(jié)點(diǎn)的元素值：將指定結(jié)點(diǎn)的元素值修改為指定值。計(jì)算二叉樹的深度：按照某種規(guī)則依次訪問(wèn)二叉樹中的每一結(jié)點(diǎn),最大值。,計(jì)算度為0結(jié)點(diǎn)數(shù)。請(qǐng)簡(jiǎn)述順序表示的二叉樹中各結(jié)點(diǎn)的編號(hào)規(guī)則。順序表示的二叉樹中各結(jié)點(diǎn)的編號(hào)與相同深度的完全二叉樹中對(duì)應(yīng)結(jié)點(diǎn)的編號(hào)相同。請(qǐng)簡(jiǎn)述二叉鏈表表示和三叉鏈表表示的二叉樹中結(jié)點(diǎn)的結(jié)構(gòu)。,,雙親結(jié)點(diǎn)的指針。請(qǐng)簡(jiǎn)述二叉樹的四種遍歷方式及每一種遍歷方式中結(jié)點(diǎn)的訪問(wèn)順序。先序遍歷二叉樹：也稱為先根遍歷,其訪問(wèn)方式遞歸定義如下：對(duì)于一棵二叉樹,先訪問(wèn)其根結(jié)點(diǎn),再訪問(wèn)根結(jié)點(diǎn)的左、右子樹；對(duì)于左、右子樹中的結(jié)點(diǎn)仍然是按照先序遍歷方式訪問(wèn),即先訪問(wèn)根結(jié)點(diǎn),再訪問(wèn)根結(jié)點(diǎn)的左、右子樹。中序遍歷二叉樹：也稱為中根遍歷,其訪問(wèn)方式遞歸定義如下：對(duì)于一棵二叉樹,先訪問(wèn)根結(jié)點(diǎn)左子樹,再訪問(wèn)根結(jié)點(diǎn),最后訪問(wèn)右子樹；對(duì)于左、右子樹中的結(jié)點(diǎn)仍然是按照中序遍歷方式訪問(wèn)。后序遍歷二叉樹：也稱為后根遍歷,其訪問(wèn)方式遞歸定義如下：對(duì)于一棵二叉樹,先訪問(wèn)根結(jié)點(diǎn)的左子樹,后訪問(wèn)右子樹,最后訪問(wèn)根結(jié)點(diǎn)；對(duì)于左、右子樹中的結(jié)點(diǎn)仍然是按照后序遍歷方式訪問(wèn)。逐層遍歷二叉樹：從第1層開(kāi)始依次對(duì)每層中的結(jié)點(diǎn)按照從左至右的順序進(jìn)行訪問(wèn)。已知一棵二叉樹的先序遍歷結(jié)果為ABDG、、、、H、中序遍歷結(jié)果為D、G、B、A、E、C、H、F、I,請(qǐng)給出該二叉樹的后序遍歷結(jié)果。G、D、B、E、H、I、F、C、A已知一棵二叉樹的中序遍歷結(jié)果為DGBA、、、、、后序遍歷結(jié)果為G、D、B、E、H、I、F、C、A,請(qǐng)給出該二叉樹的先序遍歷結(jié)果。A、B、D、G、C、E、F、H、I已知一棵二叉樹的先序遍歷結(jié)果為A、GCE、、H、后序遍歷結(jié)果為G、D、B、E、H、I、F、C、A,請(qǐng)給出該二叉樹的中序遍歷結(jié)果。D、G、B、A、E、C、H、F、I請(qǐng)簡(jiǎn)述哈夫曼樹的結(jié)構(gòu)特性。哈夫曼樹,又稱最優(yōu)二叉樹,是指在由n個(gè)葉子結(jié)點(diǎn)構(gòu)成的一類二叉樹中具有最短帶權(quán)路徑長(zhǎng)度的二叉樹。請(qǐng)簡(jiǎn)述結(jié)點(diǎn)的權(quán)、結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度、樹的帶權(quán)路徑長(zhǎng)度等基本術(shù)語(yǔ)的含義。結(jié)點(diǎn)的權(quán)和結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：在實(shí)際應(yīng)用中,往往給樹中的結(jié)點(diǎn)賦予一個(gè)具有某種意義的實(shí)數(shù),該實(shí)數(shù)就稱為是結(jié)點(diǎn)的權(quán)。結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度是指從樹根到該結(jié)點(diǎn)的路徑長(zhǎng)度與結(jié)點(diǎn)的權(quán)的乘積。記為WPLnWLi1 iii,ni

為第i個(gè)葉子結(jié)點(diǎn)的權(quán),L

為根結(jié)點(diǎn)到第i個(gè)葉子結(jié)點(diǎn)的路徑iii長(zhǎng)度WLi個(gè)葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度。iii哈夫曼樹的構(gòu)造方法如下：i〔a已知n個(gè)權(quán)值為W〔i=1,2,…,n的結(jié)點(diǎn),將每個(gè)結(jié)點(diǎn)作為根結(jié)點(diǎn)生成n棵只有根結(jié)點(diǎn)的二叉樹Ti,形成森林F={T1,T2,…,Tn}。i〔b從森林F中選出根結(jié)點(diǎn)權(quán)值最小的兩棵二叉樹Tp和Tq,并通過(guò)添加新的根結(jié)點(diǎn)將它新二叉樹中Tp和Tq,TpTqF中的TpTqF中只存在一棵二叉樹。請(qǐng)簡(jiǎn)述哈夫曼碼的作用及其編碼方法。哈夫曼編碼是指將用其他編碼法表示的字符序列轉(zhuǎn)成用哈夫曼碼表示以減少存儲(chǔ)空間,其具體方法為：〔a以要編碼的字符集C={c1,c2,…,cn}作為葉子結(jié)點(diǎn)、字符出現(xiàn)的頻度或次數(shù)W={w1,w2,…,wn}作為結(jié)點(diǎn)的權(quán),構(gòu)造哈夫曼樹?！瞓規(guī)定哈夫曼樹中,從根結(jié)點(diǎn)開(kāi)始,雙親結(jié)點(diǎn)到左孩子結(jié)點(diǎn)的分支標(biāo)為0,雙親結(jié)點(diǎn)到右孩子結(jié)點(diǎn)的分支標(biāo)為1。從根結(jié)點(diǎn)到某一葉子結(jié)點(diǎn)經(jīng)過(guò)的分支形成的編碼即是該葉子結(jié)點(diǎn)所對(duì)應(yīng)字符的哈夫曼碼。請(qǐng)簡(jiǎn)述樹的四種常用表示方式。雙親表示法：在孩子結(jié)點(diǎn)中設(shè)置一個(gè)指針域記錄其雙親結(jié)點(diǎn)的存儲(chǔ)位置。孩子表示法：在雙親結(jié)點(diǎn)中設(shè)置指向孩子結(jié)點(diǎn)的指針域來(lái)表示一棵樹。孩子雙親表示法：綜合了孩子表示法和雙親表示法的特點(diǎn),既在孩子結(jié)點(diǎn)中設(shè)置記錄雙親結(jié)點(diǎn)位置的指針域,又在雙親結(jié)點(diǎn)中設(shè)置記錄孩子結(jié)點(diǎn)位置的指針域。孩子兄弟表示法：又稱為二叉鏈表表示法,與二叉樹的二叉鏈表表示法存儲(chǔ)結(jié)構(gòu)完全相同,,針域指向該結(jié)點(diǎn)的下一個(gè)兄弟結(jié)點(diǎn)。請(qǐng)簡(jiǎn)述森林轉(zhuǎn)換為二叉樹的具體步驟。,結(jié)點(diǎn)到兄弟結(jié)點(diǎn)的連線作為右子樹的邊。請(qǐng)簡(jiǎn)述二叉樹轉(zhuǎn)化為樹或森林的具體步驟。將一個(gè)結(jié)點(diǎn)左子樹的邊作為該結(jié)點(diǎn)指向第一個(gè)孩子結(jié)點(diǎn)的連線,右子樹的邊作為該結(jié)點(diǎn)到兄弟結(jié)點(diǎn)的連線；在雙親結(jié)點(diǎn)和它的各孩子結(jié)點(diǎn)之間加上連線,并刪除兄弟結(jié)點(diǎn)之間的連線,得到一棵樹或一個(gè)包含若干棵樹的森林。第6章圖請(qǐng)簡(jiǎn)述圖的結(jié)構(gòu)特性。圖GV和邊的集合E組成記為E>所以,E用于表示V至少,但可以沒(méi)有任何邊。路徑長(zhǎng)度、回路、簡(jiǎn)單回路、連通圖、單向連通圖、強(qiáng)連通圖、子圖、連通分量、強(qiáng)連通分量、權(quán)、帶權(quán)圖、生成樹、最小生成樹等基本術(shù)語(yǔ)的含義。若E<G>,向邊此時(shí)圖G,有向邊也簡(jiǎn)稱為弧。在有向圖G中對(duì)于一條從頂點(diǎn)vi到vj,<vi,vj>并有<vi,vj>∈E<G>,vi為弧尾,vj為弧頭。無(wú)向圖：若E<G>,G稱為無(wú)向圖。頂點(diǎn)的度、頂點(diǎn)的入度和頂點(diǎn)的出度：在無(wú)向圖中,與頂點(diǎn)vi相關(guān)聯(lián)的邊的數(shù)目稱為頂點(diǎn)vi的度。在有向圖中,以頂點(diǎn)vi為弧頭的弧的數(shù)目稱為頂點(diǎn)vi的入度；以頂點(diǎn)vi為弧尾的弧的數(shù)目稱為vi的出度；頂點(diǎn)vi的入度和出度之和稱為vi的度。路徑和路徑長(zhǎng)度：在圖G中,若存在一個(gè)頂點(diǎn)序<v0,v1,…, vn-1>,使得對(duì)于任意i i i0≤j<n-1有vjvE(G)〔若G為有向圖或(vjvj1E(G)〔若G,則該序列是i i i i從頂點(diǎn)v0到頂點(diǎn)vn-1的一條路徑。一條路徑中邊的數(shù)目稱為路徑長(zhǎng)度。i i回路和簡(jiǎn)單回路：在一條路徑中,若組成路徑的頂點(diǎn)序列中第一個(gè)頂點(diǎn)與最后一個(gè)頂點(diǎn)相同,則該路徑稱為回路〔或環(huán)；在一個(gè)回路中,若除第一個(gè)頂點(diǎn)與最后一個(gè)頂點(diǎn)外,其他頂點(diǎn)只出現(xiàn)一次,則該回路稱為簡(jiǎn)單回路〔或簡(jiǎn)單環(huán)。連通圖：無(wú)向圖G中,若任意兩個(gè)頂點(diǎn)都是連通的,則稱G為連通圖。G中,,G,G為強(qiáng)連通圖。子圖：對(duì)于圖GG',若滿足'))且,則G的子圖。連通分量和強(qiáng)連通分量：一個(gè)無(wú)向圖的極XX通子圖稱為該無(wú)向圖的連通分量；一個(gè)有向圖的極大強(qiáng)連通子圖稱為該有向圖的強(qiáng)連通分量。權(quán)和帶權(quán)圖：可以為一個(gè)圖中的每條邊標(biāo)上一個(gè)具有某種意義的實(shí)數(shù),該實(shí)數(shù)就稱為是邊的權(quán)。邊上帶權(quán)的圖就稱為帶權(quán)圖。若無(wú)向圖G的一個(gè)子圖是一棵包含圖G,則G'稱為圖G,6-16-2。請(qǐng)簡(jiǎn)述圖的基本操作及各操作的含義。創(chuàng)建圖：創(chuàng)建不包含任何頂點(diǎn)和邊的空?qǐng)D。對(duì)圖作深度優(yōu)先遍歷：類似于樹的先序遍歷,即從某一個(gè)頂點(diǎn)開(kāi)始訪問(wèn),訪問(wèn)后將該頂點(diǎn)去除得到若干子圖,對(duì)每個(gè)子圖再依次進(jìn)行深度優(yōu)先遍歷。對(duì)圖作廣度優(yōu)先遍歷：,然后訪問(wèn)與該頂點(diǎn)相鄰接且未被訪問(wèn)過(guò)的頂點(diǎn)集V1<G>,再訪問(wèn)與V1<G>中頂點(diǎn)相鄰接且未被訪問(wèn)過(guò)的頂點(diǎn)集V2<G>,,直至所有頂點(diǎn)訪問(wèn)完畢。獲取頂點(diǎn)數(shù)目：獲取圖中所包含的頂點(diǎn)的數(shù)目。獲取邊的數(shù)目：獲取圖中所包含的邊的數(shù)目。獲取與指定頂點(diǎn)相關(guān)聯(lián)的第一條邊：對(duì)無(wú)向圖,獲取到與指定頂點(diǎn)相關(guān)聯(lián)的第一條邊；對(duì)有向圖,獲取到以指定頂點(diǎn)作為弧尾的第一條弧。不同表示方法獲取到的結(jié)果會(huì)有所不同〔鄰接矩陣法按頂點(diǎn)編號(hào)順序,鄰接壓縮表和鄰接鏈表按邊的添加順序。獲取與指定邊有相同關(guān)聯(lián)頂點(diǎn)的下一條邊：對(duì)無(wú)向圖,獲取到與指定邊<nV1,nV2>有相同關(guān)聯(lián)頂點(diǎn)nV1的下一條邊；對(duì)有向圖,獲取到與指定弧<nV1,nV2>有相同弧尾nV1的下一條弧。不同表示方法獲取到的結(jié)果會(huì)有所不同〔鄰接矩陣法按頂點(diǎn)編號(hào)順序,鄰接壓縮表和鄰接鏈表按邊的添加順序。添加一個(gè)頂點(diǎn)：向圖中添加一個(gè)新頂點(diǎn)。添加一條邊：對(duì)無(wú)向圖,向圖中添加一條新邊；對(duì)有向圖,向圖中添加一條新弧。獲取一個(gè)頂點(diǎn)中存儲(chǔ)的數(shù)據(jù)：根據(jù)頂點(diǎn)編號(hào)獲取該頂點(diǎn)中存儲(chǔ)的數(shù)據(jù)。判斷一條邊是否存在：對(duì)無(wú)向圖,判斷兩個(gè)頂點(diǎn)nV1和nV2之間是否存在邊；對(duì)有向圖,判斷是否存在從頂點(diǎn)nV1到頂點(diǎn)nV2的弧。設(shè)置一條邊的權(quán)：對(duì)無(wú)向圖,設(shè)置指定邊<nV1,nV2>上的權(quán)；對(duì)有向圖,設(shè)置指定弧<nV1,nV2>上的權(quán)。獲取一條邊的權(quán)：對(duì)無(wú)向圖,獲取指定邊<nV1,nV2>上的權(quán)；對(duì)有向圖,獲取指定弧<nV1,nV2>上的權(quán)。請(qǐng)簡(jiǎn)述圖的三種常用表示方法。鄰接矩陣法：用矩陣來(lái)表示各頂點(diǎn)之間的連接關(guān)系。對(duì)于有n個(gè)頂點(diǎn)的圖G=<V,E>,其鄰接矩陣An*n,元素A[i][j]〔0≤i,j<n其中,wij<vi,vj>或<vi,vj>上的權(quán)。鄰接壓縮表：鄰接矩陣的一種壓縮表示形式,使用3個(gè)順序表來(lái)表示圖中頂點(diǎn)之間的連i接關(guān)系和權(quán)。設(shè)圖中共有n個(gè)頂點(diǎn){v0,v1,…,vn-1},3個(gè)順序表分別為s、w和h。在s中依次記錄與頂點(diǎn)v〔i=0,1,…,n-1相關(guān)聯(lián)的頂點(diǎn)；在w中依次記錄s中存儲(chǔ)的各條邊的權(quán)；在h中依次記錄與頂點(diǎn)vi相關(guān)聯(lián)的頂點(diǎn)在s中的起始存儲(chǔ)位置。i鄰接鏈表：圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。每個(gè)頂點(diǎn)中設(shè)置一個(gè)指向鏈表頭的指針,在鏈表中保存與該頂點(diǎn)相鄰接的頂點(diǎn)信息〔包括頂點(diǎn)位置及兩個(gè)頂點(diǎn)形成的邊的權(quán)。請(qǐng)簡(jiǎn)述圖的兩種常用遍歷方法及每一種遍歷方法中結(jié)點(diǎn)的訪問(wèn)順序。廣度優(yōu)先遍歷：類似于樹的逐層遍歷,即先從某一個(gè)頂點(diǎn)開(kāi)始訪問(wèn),然后訪問(wèn)與該頂點(diǎn)相鄰接且未被訪問(wèn)過(guò)的頂點(diǎn)集V1<G>,再訪問(wèn)與V1<G>中頂點(diǎn)相鄰接且未被訪問(wèn)過(guò)的頂點(diǎn)集V2<G>,重復(fù)該過(guò)程直至與初始頂點(diǎn)連通的所有頂點(diǎn)都被訪問(wèn)完。對(duì)于非連通圖或非強(qiáng)連通圖,還要從某一個(gè)未被訪問(wèn)的頂點(diǎn)開(kāi)始重復(fù)上一過(guò)程,直至所有頂點(diǎn)訪問(wèn)完畢。深度優(yōu)先遍歷：類似于樹的先序遍歷,即從某一個(gè)頂點(diǎn)開(kāi)始訪問(wèn),訪問(wèn)后將該頂點(diǎn)去除得到若干子圖,對(duì)每個(gè)子圖再依次進(jìn)行深度優(yōu)先遍歷。6-16-2。請(qǐng)簡(jiǎn)述Prim算法的作用和具體步驟。Prim算法用于最小生成樹問(wèn)題求解。對(duì)于有n個(gè)頂點(diǎn)的圖G=<V,E>,Prim算法從空樹T開(kāi)始,按照以下規(guī)則將n個(gè)頂點(diǎn)和n-1條邊依次添加到樹中,形成最小生成樹：〔a從某一頂點(diǎn)開(kāi)始,將該頂點(diǎn)作為樹的根結(jié)點(diǎn)加入到T中,使得TD={v0'},數(shù)據(jù)元素關(guān)系集合R={}。〔b對(duì)于一個(gè)頂點(diǎn)在集合D中、另一個(gè)頂點(diǎn)在集合V-D,找出權(quán)最小的一條,將該邊在集合V-D中的頂點(diǎn)'-1加入到集合D<v',v'〔j<ii j i加入到關(guān)系集合R中?！瞔重復(fù)上一步驟直至集合D中包括圖G中所有nR中包括n-1,則說(shuō)明圖G存在最小生成樹。請(qǐng)簡(jiǎn)述Kruskal算法的作用和具體步驟。iKruskal算法用于最小生成樹問(wèn)題求解。對(duì)于有n個(gè)頂點(diǎn)的圖G=<V,E>,Kruskal據(jù)圖G中所有n個(gè)頂點(diǎn)生成一個(gè)包括n棵只有根結(jié)點(diǎn)的樹T〔i=0,1,…,n-1的森林并按i照以下規(guī)則森林F中的樹合并,形成最小生成樹：〔a從邊集合E,的兩個(gè)頂點(diǎn)是否屬于不同的樹,若屬于不同的樹則使用該邊將兩棵樹合并為一棵；若屬于同一棵樹則不做任何處理?！瞓F,G林F則說(shuō)明圖G樹。請(qǐng)簡(jiǎn)述Dijkstra算法的作用和具體步驟。Dijkstra算法用于計(jì)算從某個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑。對(duì)于有n個(gè)頂點(diǎn)的圖G=<V,E>,若要計(jì)算從頂點(diǎn)v0'到其余各頂點(diǎn)vi'〔i=1,2,…,n-1的最短路徑,則其計(jì)算步驟為：〔a令集合S為已計(jì)算出最短路徑的頂點(diǎn)集合〔初始時(shí)S={v0'},w<vj',vi'>表示從頂點(diǎn)vj'到頂點(diǎn)vi'的邊的權(quán)〔這里為方便計(jì)算,令w<vi',vi'>=0,D<v0',vi'>表示當(dāng)前計(jì)算得到的從頂點(diǎn)v0'到頂點(diǎn)vi'的最短路徑長(zhǎng)度〔初始D<v0',vi'>=w<v0',vi'>?！瞓將頂點(diǎn)vm'argmin(D(v0',vi'))加入到集合S中,并將從頂點(diǎn)v0'到頂點(diǎn)vm'的最短路徑vi'VS記錄下來(lái)。若仍有頂點(diǎn)沒(méi)有加到集合S中,則對(duì)集合V-S中的頂點(diǎn)vi計(jì)算D(v0

',vi

')min(D(v0vj'S0

',

')j

',vj

'))?！瞔重復(fù)上一步驟直至圖中所有頂點(diǎn)都加到集合S中。請(qǐng)簡(jiǎn)述Floyd算法的作用和具體步驟。Floyd算法用于計(jì)算每一對(duì)頂點(diǎn)之間的最短路徑。對(duì)于有n個(gè)頂點(diǎn)的圖G=<V,E>,若要計(jì)算任意兩個(gè)頂點(diǎn)vk'〔j,k為[0,n-1]j≠k則其計(jì)算步驟為：〔a令w<vj',vk'>表示連接頂點(diǎn)vj'和頂點(diǎn)vk'的邊的權(quán)〔這里為方便計(jì)算,令w<vj',vj'>=0,D<vj',vk'>表示當(dāng)前計(jì)算得到的從頂點(diǎn)vj'到頂點(diǎn)vk'的最短路徑長(zhǎng)度〔初始D<vj',vk'>=w<vj',vk'>?！瞓'i0,1,…,若D<v',v'>>D<v',v'>+D<v',v

'>,i j k j i i k則表明路徑<vj',…,vi',…,vk'>的長(zhǎng)度更短,此時(shí)令D<vj',vk'>=D<vj',vi'>+D<vi',vk'>并更新從頂點(diǎn)vj'到頂點(diǎn)vk'的路徑。7章排序算法請(qǐng)簡(jiǎn)述排序的作用。排序的作用是將一個(gè)待排序元素集合按關(guān)鍵字遞增〔或遞減順序整理為一個(gè)有序序列。請(qǐng)簡(jiǎn)述穩(wěn)定排序和不穩(wěn)定排序的含義。若采用某種排序算法對(duì)任一組元素進(jìn)行排序,在排序前后,那些具有相同關(guān)鍵字值的元素之間的相對(duì)次序都保持不變,則將這種排序算法稱為是穩(wěn)定的,否則稱為是不穩(wěn)定的。排序算法的適用范圍如下：〔a,它們的時(shí)間復(fù)雜度和空間復(fù)雜度分別為O<n2>和O<1>n較小此時(shí)時(shí)間復(fù)雜度都能達(dá)到O<n>,元素移動(dòng)操作代價(jià)較高,則應(yīng)選用平均移動(dòng)元素次數(shù)最,但它是一種不穩(wěn)定的排序算法?！瞓n當(dāng)待排序元素?cái)?shù)量n,快速排序算法和歸并排序算法經(jīng)常與簡(jiǎn)單排序算法結(jié)合使用〔例如,可以先用快速排序算法將集合劃分為規(guī),,時(shí)間復(fù)雜度為O<nlog2n>的算法中,,但它通常被認(rèn)為是平均性能最好的一種算法,并且通過(guò)優(yōu)化可以降低最壞情況出現(xiàn)的概率。歸并排序是一種穩(wěn)定的排序算法,其時(shí)間性能一般要優(yōu)于堆排序,但它所需要的輔助空間較多,當(dāng)應(yīng)用環(huán)境要求排序前后具有相同值的元素相對(duì)次序不能改變時(shí)可以考慮使用,當(dāng)可用空間非常有限時(shí)可以考慮使用?！瞔待排序元素長(zhǎng)度〔即d,,主要適,序算法按整數(shù)部分將元素分成若干個(gè)子集合,再對(duì)每個(gè)子集合應(yīng)用直接插入排序算法進(jìn)行排序。5.請(qǐng)簡(jiǎn)述插入排序、選擇排序、交換排序、歸并排序和分配排序的原理。插入排序：按關(guān)鍵字大小每次將一個(gè)待排序的元素插入到已排序的序列中,直至所有元素都插入完畢。,直至所有元素都排序完畢。交換排序：從待排序的元素中選擇兩個(gè)次序相反的元素進(jìn)行交換,直至任意兩個(gè)元素的次序都正確。K路歸并排序：每次將K〔K≥2個(gè)已排序的子序列組合在一起,形成一個(gè)有序的序列,重復(fù)該過(guò)程直至得到一個(gè)包含所有待排序元素的有序序列。分配排序：根據(jù)元素本身所具有的值將各元素逐一映射到一組有序空間中,最后再依次從有序空間中將各元素取出即形成了排序結(jié)果。請(qǐng)簡(jiǎn)述直接插入排序的具體步驟。直接插入排序是一種簡(jiǎn)單排序算法,其具體步驟為：〔a初始已排序區(qū)為空,將第一個(gè)待排序的元素插入到已排序區(qū)中?！瞓將后繼每一個(gè)待排序的元素依次取出,使該序列仍然有序。〔c重復(fù)上一步驟直至將待排序的元素都插入到已排序序列中。請(qǐng)簡(jiǎn)述希爾排序的具體步驟。希爾排序,又稱為"縮小增量排序",其具體步驟為：〔a令n,{d0,d1,…,n>d0>d1>…>dk=1?！瞓按增量d〔i0,1,…,k將待排序元素分為d組,將所有下標(biāo)距離為d的i i i倍數(shù)的元素放在同一組中即R[1],R[1+di],R[1+2*di],…在第一組中,R[2],R[2+di],R[2+2*di],,……,依此類推。然后分別在各組內(nèi)進(jìn)行直接插入排序?！瞔重復(fù)上一步驟直至最后以1為增