數(shù)據(jù)結(jié)構(gòu)(c語(yǔ)言版)課后習(xí)題標(biāo)準(zhǔn)答案完整版

1、數(shù)據(jù)結(jié)構(gòu)（c語(yǔ)言版）課后習(xí)題標(biāo) 準(zhǔn)答案完整版作者:日期:第1章緒論5 .選擇題：CCBDCA6 .試分析下面各程序段的時(shí)間復(fù)雜度。(1) O (1)(2) O (m*n)(3) O (n2)(4) O (log3n)(5)因?yàn)閤+共執(zhí)行了 n-1+n-2+1= n(n-1)/2 ,所以執(zhí)行時(shí)間為 O ( n2)(6) O( J)第2章線性表1 .選擇題babadbcabdcddac2 .算法設(shè)計(jì)題(6)設(shè)計(jì)一個(gè)算法，通過(guò)一趟遍歷在單鏈表中確定值最大的結(jié)點(diǎn)。ElemType Max (LinkList L )if(L->next=NULL) return NULL;pmax=L->n

2、ext; 假定第一個(gè)結(jié)點(diǎn)中數(shù)據(jù)具有最大值p=L->next->next;while(p != NULL )/如果下一個(gè)結(jié)點(diǎn)存在if(p->data > pmax->data) pmax=p;p=p->next;return pmax->data;(7)設(shè)計(jì)一個(gè)算法，通過(guò)遍歷一趟，將鏈表中所有結(jié)點(diǎn)的鏈接方向逆轉(zhuǎn)，仍利用原表 的存儲(chǔ)空間。void inverse(LinkList &L) /逆置帶頭結(jié)點(diǎn)的單鏈表Lp=L->next; L->next=NULL;while ( p) q=p->next; / q指向*p的后繼p-&g

3、t;next=L->next;L->next=p; / *p插入在頭結(jié)點(diǎn)之后p = q;(10)已知長(zhǎng)度為n的線性表A采用順序存儲(chǔ)結(jié)構(gòu)，請(qǐng)寫(xiě)一時(shí)間復(fù)雜度為O(n)、空間復(fù)雜度為0(1)的算法，該算法刪除線性表中所有值為item的數(shù)據(jù)元素。題目分析在順序存儲(chǔ)的線性表上刪除元素，通常要涉及到一系列元素的移動(dòng)(刪第i個(gè)元素，第i+1至第n個(gè)元素要依次前移)。本題要求刪除線性表中所有值為 item的數(shù)據(jù) 元素，并未要求元素間的相對(duì)位置不變。因此可以考慮設(shè)頭尾兩個(gè)指針(i=1 , j=n ),從兩端向中間移動(dòng)，凡遇到值item的數(shù)據(jù)元素時(shí)，直接將右端元素左移至值為 item的數(shù)據(jù)元素 位置。

4、void Delete (ElemType A , int n )/A是有n個(gè)元素的一維數(shù)組，本算法刪除A中所有值為item的元素。i=1 ; j=n ; /設(shè)置數(shù)組低、高端指針(下標(biāo))。while (i<j ) while (i<j && Ai!=item ) i+;/若值不為 item,左移指針。if (i<j ) while (i<j && Aj=item ) j- ; / 若右端元素值為 item ,指針左移 if (i<j ) Ai+=Aj-；算法討論因元素只掃描一趟，算法時(shí)間復(fù)雜度為O (n)。刪除元素未使用其它輔助空間

5、，最后線性表中的元素個(gè)數(shù)是jo第3章棧和隊(duì)列1 .選擇題CCDAADABCDDDBCB2 .算法設(shè)計(jì)題(2)回文是指正讀反讀均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。試寫(xiě)一個(gè)算法判定給定的字符向量是否為回文。(提示：將一半字符入棧)根據(jù)提示，算法可設(shè)計(jì)為：/以下為順序棧的存儲(chǔ)結(jié)構(gòu)定義#define StackSize 100 /假定預(yù)分配的?？臻g最多為100個(gè)元素typedef char DataType;/假定棧元素的數(shù)據(jù)類型為字符typedef structDataType dataStackSize;int top;SeqStack;int IsH

6、uiwen( char *t)/判斷t字符向量是否為回文，若是，返回 1,否則返回0SeqStack s;int i , len;char temp;InitStack( &s);len=strlen(t); / 求向量長(zhǎng)度f(wàn)or ( i=0; i<len/2; i+)將一半字符入棧Push( &s, ti);while(丘mptyStack( &s)/每彈出一個(gè)字符與相應(yīng)字符比較temp=Pop (&s);if( temp!=Si) return 0 ;/不等則返回 0else i+;return 1 ; /比較完畢均相等則返回1(7)假設(shè)以數(shù)組 Qm存

7、放循環(huán)隊(duì)列中的元素，同時(shí)設(shè)置一個(gè)標(biāo)志tag,以tag = 0和 tag = 1來(lái)區(qū)別在隊(duì)頭指針(front)和隊(duì)尾指針(rear)相等時(shí)，隊(duì)列狀態(tài)為 空"還是 滿”。試編 寫(xiě)與此結(jié)構(gòu)相應(yīng)的插入(enqueue)和刪除(dlqueue)算法?！窘獯稹垦h(huán)隊(duì)列類定義#include <assert.h>template <class Type> class Queue 循環(huán)隊(duì)列的類定義public:Queue (int =10 );Queue ( ) delete Q; void EnQueue ( Type & item );Type DeQueue (

8、);Type GetFront ();void MakeEmpty ( ) front = rear = tag = 0;/置空隊(duì)列int IsEmpty ( ) const return front = rear && tag = 0; 判隊(duì)列空否int IsFull ( ) const return front = rear && tag = 1; 判隊(duì)列滿否 private:int rear, front, tag;隊(duì)尾指針、隊(duì)頭指針和隊(duì)滿標(biāo)志Type *Q ;存放隊(duì)列元素的數(shù)組int m;隊(duì)列最大可容納元素個(gè)數(shù)構(gòu)造函數(shù)template <class

9、 Type>Queue<Type>: Queue (int sz ) : rear (0), front (0), tag(0), m (sz) 建立一個(gè)最大具有m個(gè)元素的空隊(duì)列。Q = new Typem;/創(chuàng)建隊(duì)列空間assert ( Q != 0 );/斷言：動(dòng)態(tài)存儲(chǔ)分配成功與否 插入函數(shù) template<class Type> void Queue<Type> : EnQueue ( Type & item ) assert ( ! IsFull ();rear = ( rear + 1 ) % m;Qrear = item;tag

10、= 1;刪除函數(shù)template<class Type>Type Queue<Type> : DeQueue ( ) assert ( ! IsEmpty ();front = ( front + 1 ) % m;tag = 0;return Qfront;讀取隊(duì)頭元素函數(shù)template<class Type>Type Queue<Type> : GetFront ( ) assert ( ! IsEmpty ();return Q(front + 1) % m;判隊(duì)列是否不滿，滿則出錯(cuò)處理隊(duì)尾位置進(jìn)1,隊(duì)尾指針指示實(shí)際隊(duì)尾位置/進(jìn)隊(duì)列標(biāo)志改1

11、,表示隊(duì)列不空判斷隊(duì)列是否不空，空則出錯(cuò)處理隊(duì)頭位置進(jìn)1,隊(duì)頭指針指示實(shí)際隊(duì)頭的前一位置標(biāo)志改0,表示棧不滿/返回原隊(duì)頭元素的值判斷隊(duì)列是否不空，空則出錯(cuò)處理/返回隊(duì)頭元素的值第4章串、數(shù)組和廣義表1 .選擇題BBCABBBCBBABDCBC2 .綜合應(yīng)用題(1)已知模式串 t= ' abcaabbabcab '寫(xiě)出用 KMP法求得的每個(gè)字符對(duì)應(yīng)的next和nextval 函數(shù)值。模式串t的next和nextval值如下:j12345678910 11 12t串a(chǎn)bcaabbabcabnextj011122312345nextvalj011021301105(3)數(shù)組A中，每個(gè)

12、元素Ai,j的長(zhǎng)度均為32個(gè)二進(jìn)位，行下標(biāo)從-1到9,列下標(biāo)從1到11,從首地址S開(kāi)始連續(xù)存放主存儲(chǔ)器中，主存儲(chǔ)器字長(zhǎng)為16位。求：存放該數(shù)組所需多少單元？存放數(shù)組第4列所有元素至少需多少單元？數(shù)組按行存放時(shí)，元素 A7,4的起始地址是多少？數(shù)組按列存放時(shí)，元素 A4,7的起始地址是多少？每個(gè)元素32個(gè)二進(jìn)制位，主存字長(zhǎng) 16位，故每個(gè)元素占2個(gè)字長(zhǎng)，行下標(biāo)可平移至1到11。(1) 242(2) 22(3) s+182(4) s+142(4)請(qǐng)將香蕉banana用工具H( ) Head( ) , T( ) Tail() 從L中取出。L=(apple,(orange,(strawberry,(b

13、anana),peach),pear)H (H (T (H (T (H (T (L)(5)寫(xiě)一個(gè)算法統(tǒng)計(jì)在輸入字符串中各個(gè)不同字符出現(xiàn)的頻度并將結(jié)果存入文件(字 符串中的合法字符為 A-Z這26個(gè)字母和0-9這10個(gè)數(shù)字)。void Count ()/統(tǒng)計(jì)輸入字符串中數(shù)字字符和字母字符的個(gè)數(shù)。int i , num36;char ch ;for (i=0; i<36 ; i+) numi =0; / 初始化while (ch = getchar ()!=#') /' #'表示輸入字符串結(jié)束。if ('0' <=ch<= '9&#

14、39;) i=ch 48;numi+ ;/ 數(shù)字字符else if ('A' <=ch<= 'Z') i=ch-65+10;numi+; / 字母字符for (i=0; i<10; i+) /輸出數(shù)字字符的個(gè)數(shù)printf("數(shù)字% d 的個(gè)數(shù)=% dn ”, i , numi);for (i=10; i<36 ; i+) / 求出字母字符的個(gè)數(shù)printf("字母字符% c 的個(gè)數(shù)=% dn ”, i+55, numi); /算法結(jié)束。第5章樹(shù)和二叉樹(shù)1 .選擇題ADDCACCBDCCCACC2 .應(yīng)用題(2)設(shè)一棵

15、二叉樹(shù)的先序序列：A B D F C E G H ,中序序列：B F D A G E H C畫(huà)出這棵二叉樹(shù)。畫(huà)出這棵二叉樹(shù)的后序線索樹(shù)。將這棵二叉樹(shù)轉(zhuǎn)換成對(duì)應(yīng)的樹(shù)(或森林)。null(1)(2)(3)假設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為0.07,0.19, 0.02, 0.06, 0.32, 0.03, 0.21 , 0.10。試為這8個(gè)字母設(shè)計(jì)赫夫曼編碼。試設(shè)計(jì)另一種由二進(jìn)制表示的等長(zhǎng)編碼方案。 對(duì)于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。解：方案1;哈夫曼編碼先將概率放大100倍，以方便構(gòu)造哈夫曼樹(shù)。w=7,19,2,6,32,3,21,10,按哈夫曼規(guī)則：(2,3),

16、6, (7,10)1 ,19, 21,3219(40廠2119 21 32字母 編R對(duì)應(yīng) 編碼出現(xiàn)頻率111000.072000.193111100.02411100.065100.32方案比較:字母編R對(duì)應(yīng) 編碼出現(xiàn) 頻率10000.0720010.1930100.0240110.0651000.32610003的WPL方案12(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61方案 2 的 WPL = 3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3結(jié)論：哈夫曼編碼優(yōu)于

17、等長(zhǎng)二進(jìn)制編碼3 .算法設(shè)計(jì)題以二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，編寫(xiě)以下算法： (1)統(tǒng)計(jì)二叉樹(shù)的葉結(jié)點(diǎn)個(gè)數(shù)。int LeafNodeCount(BiTree T) if(T=NULL)return 0;/如果是空樹(shù)，則葉子結(jié)點(diǎn)個(gè)數(shù)為0else if(T->lchild=NULL&&T->rchild=NULL)return 1; /判斷該結(jié)點(diǎn)是否是葉子結(jié)點(diǎn)(左孩子右孩子都為空)，若是則返回1elsereturn LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild);(3)交換二叉樹(shù)每個(gè)結(jié)點(diǎn)的左孩子和右孩子。v

18、oid ChangeLR(BiTree &T) BiTree temp;if(T->lchild=NULL&&T->rchild=NULL)return;elsetemp = T->lchild;T->lchild = T->rchild;T->rchild = temp;ChangeLR(T->lchild);ChangeLR(T->rchild);1 .選擇題CBBBCBABAADCCDDB2 .應(yīng)用題(1)已知如圖6.27所示的有向圖，請(qǐng)給出: 每個(gè)頂點(diǎn)的入度和出度；鄰接矩陣；鄰接表；19逆鄰接表。（£）靠

19、觸陣七0 0。0I。a1oo010001oo1o11100000J1001ft.(2)已知如圖6.28所示的無(wú)向網(wǎng)，請(qǐng)給出:鄰接矩陣；鄰接表；最小生成樹(shù)434535559595576547363252646ab4c3ba4c5ca3b5db5c5eb9d7fd6e3gd5f2hc5d4圖6.28 無(wú)d5e9AAd5h5e7f6g5一h4Af3Ag2Ah6Ag6A(3)已知圖的鄰接矩陣如 6.29所示。試分別畫(huà)出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù)。深度優(yōu)先生成樹(shù)廣度優(yōu)先生成樹(shù)(4)有向網(wǎng)如圖6.29所示，試用迪杰斯特拉算法求出從頂點(diǎn)a到其他各頂點(diǎn)間的最短路徑，完成表6.9。

20、圖6.29 鄰接矩陣、弋 點(diǎn) 、i=1i=2i=3i=4i=5i=6b15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)c2(ac)d12(a,d)12(a,d)11(a,c,f,d)11(a,c,f,d)eoo10(a,c,e)10(a,c,e)foo6(a,c,f)gooOO16(a,c,f,g)16(a,c,f,g)衛(wèi)(a,c,f,d,g)S終 點(diǎn)集a,ca,c,fa,c,f,ea,c,f,e,da,c,f,e,d,ga,c,f,e,d,g,b第7章查找1 .選擇題CDCABCCCDCBCADA2 .應(yīng)用題(1)假定對(duì)有序表：(3,4, 5, 7,24,

21、30,42,54, 63, 72,87,95)進(jìn)行折半查找,試回答下列問(wèn)題： 畫(huà)出描述折半查找過(guò)程的判定樹(shù)；若查找元素54,需依次與哪些元素比較？若查找元素90,需依次與哪些元素比較？ 假定每個(gè)元素的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。先畫(huà)出判定樹(shù)如下(注：mid= (1+12)/2 =6):4 24查找元素 54,需依次與 30, 63, 42, 54元素比較；查找元素 90,需依次與 30, 63,87, 95元素比較；3 層共查找 1+2X2+4X 3=17求ASL之前，需要統(tǒng)計(jì)每個(gè)元素的查找次數(shù)。判定樹(shù)的前次；但最后一層未滿，不能用 8X 4,只能用5X4=20次, 所以 ASL

22、= 1/12 (17 + 20) = 37/12=3.08(2)在一棵空的二叉排序樹(shù)中依次插入關(guān)鍵字序列為12, 7, 17, 11, 16, 2, 13, 9, 21,4,請(qǐng)畫(huà)出所得到的二叉排序樹(shù)。12 雙2 J1/16214913驗(yàn)算方法：用中序遍歷應(yīng)得到排序結(jié)果：2,4,7,9,11,12,13,16,17, 21(5)設(shè)哈希表的地址范圍為 017,哈希函數(shù)為：H (key) =key%16。用線性探測(cè)法 處理沖突，輸入關(guān)鍵字序列：(10,24,32, 17, 31,30,46, 47,40,63,49),構(gòu)造哈希表，試回答下列問(wèn)題：畫(huà)出哈希表的示意圖；若查找關(guān)鍵字63,需要依次與哪些關(guān)

23、鍵字進(jìn)行比較？若查找關(guān)鍵字60,需要依次與哪些關(guān)鍵字比較？ 假定每個(gè)關(guān)鍵字的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。畫(huà)表如下：012345678910111213141516173217634924401030314647查找63,首先要與H(63)=63%16=15號(hào)單元內(nèi)容比較，即63 vs 31 ,no;然后順移，與46,47,32,17,63 相比，一共比較了 6次！查找60,首先要與H(60)=60%16=12號(hào)單元內(nèi)容比較， 但因?yàn)?2號(hào)單元為空(應(yīng)當(dāng)有空標(biāo) 記)，所以應(yīng)當(dāng)只比較這一次即可。對(duì)于黑色數(shù)據(jù)元素，各比較1次；共6次；對(duì)紅色元素則各不相同，要統(tǒng)計(jì)移位的位數(shù)?！?3”需要

24、6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以 ASL=1/11 (6+2+3X3+6) = 23/11(6)設(shè)有一組關(guān)鍵字 (9, 01, 23, 14, 55, 20, 84, 27),采用哈希函數(shù)：H(key) =key %7 , 表長(zhǎng)為10,用開(kāi)放地址法的二次探測(cè)法處理沖突。要求：對(duì)該關(guān)鍵字序列構(gòu)造哈希表，并 計(jì)算查找成功的平均查找長(zhǎng)度。散列地址0123456789關(guān)鍵字140192384275520比較次數(shù)11123412平均查找長(zhǎng)度： ASLcc= (1 + 1+1+2+3+4+1+2) /8=15/8以關(guān)鍵字 27 為例：H (27) =27%

25、7=6(沖突) H 1= (6+1) %10=7(沖突)H2= (6+22) %10=0(沖突)H 3= (6+33) %10=5 所以比較了 4 次。第8章排序1 .選擇題CDBDCBCDBCBCCCA2 .應(yīng)用題(1)設(shè)待排序的關(guān)鍵字序列為 12, 2, 16, 30, 28, 10, 16*, 20, 6, 18,試分別寫(xiě) 出使用以下排序方法，每趟排序結(jié)束后關(guān)鍵字序列的狀態(tài)。直接插入排序折半插入排序希爾排序(增量選取 5, 3, 1)冒泡排序快速排序簡(jiǎn)單選擇排序堆排序二路歸并排序直接插入排序2121630281016*206182121630281016*2061821216302810

26、16*206182121628301016*206182101216283016*20618210121616*28302061821012*1616*202830618261012166101216 16*折半插入排序排序過(guò)程同希爾排序（增量選取 5, 3, 1）16*1820202828301830102166181216*203028 （增量選取5）621210181616*203028 （增量選取3）261012冒泡排序2121621216212102101221012210626102610快速排序12 62 1062 61028 261018 261016*261628101616612 121212121212