【正文】 。 //當(dāng)前長度（存儲(chǔ)元素個(gè)數(shù)） }SqList。（3） 求A、B、C、D、E、F的Huffman編碼。（2）分別畫出以A為起點(diǎn)的DFS生成樹和BFS生成樹。3． 已知二個(gè)稀疏矩陣A和B的壓縮存儲(chǔ)三元組表如下： A BijVijV135252246337252413421529529558寫出AB壓縮存儲(chǔ)的三元組表。(6分)(1) 構(gòu)造HASH表。3． 線性表（a1,a2,…,an）的順序存儲(chǔ)結(jié)構(gòu)中，設(shè)每個(gè)單元的長度為L，元素ai的存儲(chǔ)地址LOC(ai)為 4． 已知一雙向鏈表如下(指針域名為next和prior)： y x e q p現(xiàn)將p所指的結(jié)點(diǎn)插入到x和y結(jié)點(diǎn)之間，其操作步驟為： ； ； ； ；5．n個(gè)結(jié)點(diǎn)無向完全圖的的邊數(shù)為 ， n個(gè)結(jié)點(diǎn)的生成樹的邊數(shù)為 。 Qnext=pnext。 next=pnext。 （A）、k1 （B）、k （C）、k1和k （D）、1至k6．具有60個(gè)結(jié)點(diǎn)的二叉樹，其葉子結(jié)點(diǎn)有12個(gè)，則度過1的結(jié)點(diǎn)數(shù)為（ ）（A）、11 （B）、13 （C）、48 （D）、377．圖的DepthFirst Search(DFS)遍歷思想實(shí)際上是二叉樹（ ）遍歷方法的推廣。 (A)、正確性 (B). 可行性 (C). 健壯性 (D). 輸入性2．設(shè)S為C語言的語句,計(jì)算機(jī)執(zhí)行下面算法時(shí)，算法的時(shí)間復(fù)雜度為（ ）。for(i=n1；i=0；i) for(j=0；ji；j++) S； (A)、n2 (B). O(nlgn) (C). O(n) (D). O(n2)3．折半查找法適用于（ ）。 （A）、先序 （B）、中序 （C）、后序 （D）、層序8．在下列鏈隊(duì)列Q中，元素a出隊(duì)的操作序列為（ ）b c d ∧afrontrear Q （A）、p=next。 （C）、p=next。9． Huffman樹的帶權(quán)路徑長度WPL等于（ ）（A）、除根結(jié)點(diǎn)之外的所有結(jié)點(diǎn)權(quán)值之和 （B）、所有結(jié)點(diǎn)權(quán)值之和（C）、各葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和 （D）、根結(jié)點(diǎn)的值10．線索二叉鏈表是利用（ ）域存儲(chǔ)后繼結(jié)點(diǎn)的地址。6．已知一有向無環(huán)圖如下： BACDFEG 任意寫出二種拓?fù)渑判蛐蛄校? 、 。(2) 分別求查找成功和不成功時(shí)的平均查找長度。（5分）4． 已知一維數(shù)組中的數(shù)據(jù)為（18,12,25,53,18）, 試寫出插入排序（升序）過程。6．已知數(shù)據(jù)六個(gè)字母及在通信中出現(xiàn)頻率如下表：ABCDEF把這些字母和頻率作為葉子結(jié)點(diǎn)及權(quán)值，完成如下工作(7分，要有過程)。7． 已知有如下的有向網(wǎng)： 2 5 36 4 10 6 1 2 2 AEBDC求頂點(diǎn)A到其它各頂點(diǎn)的最短路徑（采用Dijkstra算法，要有過程）。設(shè)計(jì)一個(gè)算法，刪除其元素值為x的結(jié)點(diǎn)（假若x是唯一的）。 其中結(jié)點(diǎn)定義如下： top typedef struct { Elemtype *base。 typedef struct node{ Elemtype data。root,int amp。pprior=q。 for(i=0。 for(j=i。} （8分）平均時(shí)間復(fù)雜度：（2分）設(shè)元素個(gè)數(shù)記為n，則平均時(shí)間復(fù)雜度為：2（10分）void pop(Stack amp。 e=*。!( Trchild)) n++。 2. 數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址不相同的，稱之為（ ）。 i=n。(1) ( ) (n) ( )5. 算法分析的目的是（1），算法分析的兩個(gè)主要方面是（2）。 9. 數(shù)據(jù)結(jié)構(gòu)只是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，這種觀點(diǎn)（ ）。3. 線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是__________________的，非線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是__________________的。7. 線性結(jié)構(gòu)中元素之間存在__________________關(guān)系；樹型結(jié)構(gòu)中元素之間存在__________________關(guān)系；圖型結(jié)構(gòu)中元素之間存在__________________關(guān)系。i++)for(j=0。i=s=0。s=0。jn。i=1。三、求下列程序段的時(shí)間復(fù)雜度。i++)for(j=i+1。for(i=1。j++) x++。i++)for(j=0。kn。A[i]!=k))j。}習(xí)題1參考答案一、單項(xiàng)選擇題1. A 2. C 3. D 4. B 5. C、A 6. C、B 7. B 8. D 9. B 10. B二、填空題1. 線性結(jié)構(gòu)，非線性結(jié)構(gòu)2. 集合，線性，樹，圖3. 一對一，一對多或多對多4. 時(shí)間，空間5. 前趨，一，后繼，多6. 有多個(gè)7. 一對一，一對多，多對多8. O( )9. O( )10. O( )11. O(log n)12. 程序?qū)τ诰脑O(shè)計(jì)的典型合法數(shù)據(jù)輸入能得出符合要求的結(jié)果。A．必須是連續(xù)的 B．一定是不連續(xù)的C．部分地址必須是連續(xù)的 D．連續(xù)與否均可以 4. 從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x的結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較________個(gè)元素結(jié)點(diǎn)。 pnextprior=s。 pnext=s。 sprior=p。 pnextprior=s。 B．p=pnext。A．ni B．ni+l C．ni1 D．i8. 在一個(gè)單鏈表中，已知q結(jié)點(diǎn)是p結(jié)點(diǎn)的前趨結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則須執(zhí)行A．snext=pnext。 snext=q9. 以下關(guān)于線性表的說法不正確的是______。D．存在這樣的線性表：表中各結(jié)點(diǎn)都沒有直接前趨和直接后繼。 A．全部 B．一半 C．三分之一 D．四分之一13. 在______運(yùn)算中，使用順序表比鏈表好。A．top不變 B．top=0 C．top D．top++17. 向一個(gè)棧頂指針為hs的鏈棧中插入一個(gè)s結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行______。C．snext=hsnext。 18. 在具有n個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)滿的條件為________。2. 在一個(gè)長度為n的順序表的第i個(gè)元素之前插入一個(gè)元素，需要后移____個(gè)元素。6. 在雙向鏈表中，每個(gè)結(jié)點(diǎn)含有兩個(gè)指針域，一個(gè)指向_______結(jié)點(diǎn)，另一個(gè)指向_______結(jié)點(diǎn)。9. 線性表、棧和隊(duì)列都是_______結(jié)構(gòu)，可以在線性表的______位置插入和刪除元素；對于棧只能在_______位置插入和刪除元素；對于隊(duì)列只能在_______位置插入元素和在_______位置刪除元素。 13. 對于一個(gè)棧作進(jìn)棧運(yùn)算時(shí)，應(yīng)先判別棧是否為_______，作退棧運(yùn)算時(shí)，應(yīng)先判別棧是否為_______，當(dāng)棧中元素為m時(shí)，作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說明棧的可用最大容量為_______。三、簡答題1. 描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，表頭結(jié)點(diǎn)。8. 下述算法的功能是什么?LinkList *Demo(LinkList *L){ // L是無頭結(jié)點(diǎn)的單鏈表LinkList *q,*p。 L=Lnext。 qnext=NULL。3. 設(shè)計(jì)將帶表頭的鏈表逆置算法。5. 已知線性表的元素按遞增順序排列，并以帶頭結(jié)點(diǎn)的單鏈表作存儲(chǔ)結(jié)構(gòu)。7. 假定用一個(gè)單循環(huán)鏈表來表示隊(duì)列（也稱為循環(huán)隊(duì)列），該隊(duì)列只設(shè)一個(gè)隊(duì)尾指針，不設(shè)隊(duì)首指針，試編寫下列各種運(yùn)算的算法：（1）向循環(huán)鏈隊(duì)列插入一個(gè)元素值為x的結(jié)點(diǎn)；（2）從循環(huán)鏈隊(duì)列中刪除一個(gè)結(jié)點(diǎn)。2．線性表具有兩種存儲(chǔ)結(jié)構(gòu)即順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)。因此，只要確定了其起始位置，線性表中的任一個(gè)數(shù)據(jù)元素都可隨機(jī)存取，因此，線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)，而鏈表則是一種順序存取的存儲(chǔ)結(jié)構(gòu)。6．共有14種可能的出棧序列，即為：ABCD, ABDC，ACBD, ACDB，BACD，ADCB，BADC，BCAD, BCDA，BDCA,CBAD, CBDA，CDBA, DCBA7．在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，設(shè)隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列的容量（即存儲(chǔ)的空間大?。閙axnum。（2）要避免出現(xiàn)“假溢出”現(xiàn)象可用以下方法解決： 第一種：采用移動(dòng)元素的方法。將隊(duì)頭、隊(duì)尾看作是一個(gè)首尾相接的循環(huán)隊(duì)列，即用循環(huán)數(shù)組實(shí)現(xiàn)，此時(shí)隊(duì)首仍在隊(duì)尾之前，作插入和刪除運(yùn)算時(shí)仍遵循“先進(jìn)先出”的原則。 int j。 q=qnext。 while((ji) amp。j++。 free(s)?！?p=L。}3．設(shè)單循環(huán)鏈表的頭指針為head，類型為LinkList。 q=head。 p=pnext。 struct node *next,*prior。 p=headnext。amp。 pprior=q。 p=headnext。p=pnext。 qnext=p。 while (p!=NULL) if((pdata=min) || (pdata=max)) { q=p。p=qnext。rearnext=p。}}（2）刪除（即出隊(duì)）算法：delete(LinkList *rear){ //設(shè)循環(huán)鏈隊(duì)列的隊(duì)尾指針為rearif (rear= =NULL) //空隊(duì) printf(underflow\n)。算法描述如下：int InsertDecreaseList( SqList *L, elemtype x ){ int i。 i0 amp。 // 比較并移動(dòng)元素 (*L).elem[ i ] =x。 2. 一個(gè)子串在包含它的主串中的位置是指（ ）。A. “ijing” B. “jing＆” C. “ingNa” D. “ing＆N”6. 若INDEX（S，T）表示求T在S中的位置的操作，則對于S=“Beijing＆Nanjing”，T=“jing”，INDEX（S，T）=（ ）。 二、填空題1. 計(jì)算機(jī)軟件系統(tǒng)中，有兩種處理字符串長度的方法：一種是___________，第二種是___________________。5. 空串是指___________________，空格串是指___________________。習(xí)題3參考答案一、單項(xiàng)選擇題1．B 2．D 3．C 4．D 5．B 6．C 7．D 8．C 9．D二、填空題1. 固定長度，設(shè)置長度指針2. 兩個(gè)串的長度相等，對應(yīng)位置的字符相等3. “BCDEDE”4. 含n個(gè)字符的有限序列 （n≥0）5. 不含任何字符的串，僅含空格字符的字符串三、算法設(shè)計(jì)題1．算法描述為：int delete(r,s,t,m) //從串的第m個(gè)字符以后刪除長度為t的子串char r[ ]。i=m。j++)r[st+j]=r[j]。LinkString