數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言版課后習(xí)題答案資料

1、WOR格式緒論n-1+n-2+ ?+ 1= n(n-第1章5 .選擇題：CCBDCA6 .試分析下面各程序段的時(shí)間復(fù)雜度。（1）O（ 1）（2）O （ m*n ）（3）O（ n2）（4） O（ log 3n）（5 ）因?yàn)閤+共執(zhí)行了1）/2 ，所以執(zhí)行時(shí)間為 0（ n2）r（6）0（ n ）第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->next; /假定第一個(gè)結(jié)點(diǎn)中數(shù)據(jù)具有最

2、大值p=L->next->next;專(zhuān)業(yè)資料整理WOR格式專(zhuān)業(yè)資料整理WOR格式while(p != NULL )/如果下一個(gè)結(jié)點(diǎn)存在if(p->data > pmax->data) pmax=p;p=p->n ext;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 的

3、后繼 p->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ù)雜度為0(n)復(fù)雜度為0(1)的算法，該算法刪除線性表中所有值為item的數(shù)據(jù)元素。題目分析在順序存儲(chǔ)的線性表上刪除元素，通常要涉及到一系列元素的移動(dòng)(刪第專(zhuān)業(yè)資料整理WOR格式專(zhuān)業(yè)資料整理WOR格式個(gè)元素， 第i+1至第n個(gè)元素要依次前移)。本題要求刪除線性表中所有值為item的數(shù)據(jù)元素，并未要求元素間的相對(duì)位置不變。因此可以考慮設(shè)頭尾兩個(gè)指針(i=1 ，j=n )，從兩端向中間移動(dòng)，凡遇到值item的數(shù)據(jù)元素時(shí)，

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

5、除元素未使用其它輔助空間，最后線性表中的元素個(gè)數(shù)是 j。第3章棧和隊(duì)列1 .選擇題CCDAADABCDDDBCB2.算法設(shè)計(jì)題(2 )回文是指正讀反讀均相同的字符序列，如“abba ”和abdba “”均是回文，但“ good不是回文。試寫(xiě)一個(gè)算法判定給定的字符向量是否為回文。(提示：將一半字符入棧)專(zhuān)業(yè)資料整理WOR格式根據(jù)提示，算法可設(shè)計(jì)為：/以下為順序棧的存儲(chǔ)結(jié)構(gòu)定義#define StackSize 100 /假定預(yù)分配的 100個(gè)元?？臻g最多為素typedef char DataType;/假定棧元素的數(shù)據(jù)類(lèi)型為字符typedef structDataType dataStackSi

6、ze;int top;SeqStack;int lsHuiwen( 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( !EmptyStack( &s)/每彈出一個(gè)字符與相應(yīng)字符比較temp=Pop (&s);if( temp!=Si)return 0 ;/ 不等則返回 0專(zhuān)業(yè)資料整理WOR格式專(zhuān)業(yè)

7、資料整理WOR格式else i+;return 1 ; /比較完畢均相等則返回1tag =(7 )假設(shè)以數(shù)組 Q m存放循環(huán)隊(duì)列中的元素，同時(shí)設(shè)置一個(gè)標(biāo)志tag，以tag = 0 和1來(lái)區(qū)別在隊(duì)頭指針(front )和隊(duì)尾指針(rear)相等時(shí)，隊(duì)列狀態(tài)為“空”還是“滿”。試編寫(xiě)與此結(jié)構(gòu)相應(yīng)的插入(enqueue )和刪除(dlqueue ) 算法?！窘獯稹垦h(huán)隊(duì)列類(lèi)定義#include <assert.h>template <class Type> classQueue / 循環(huán)隊(duì)列的類(lèi)定義public:Queue ( int =10 );Queue ( ) dele

8、te Q; void EnQueue ( Type & item );Type DeQueue ();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:專(zhuān)業(yè)資料整理WOR格式int rear, front, tag ;/隊(duì)尾

9、指針、隊(duì)頭指針和隊(duì)滿標(biāo)志專(zhuān)業(yè)資料整理WOR格式Type *Q;int m;/存放隊(duì)列元素的數(shù)組/隊(duì)列最大可容納元素個(gè)數(shù)構(gòu)造函數(shù)template vclass Type>Queue <Type>: Queue ( int sz ) : rear (0), front (0), tag(O) , m (sz ) /建立一個(gè)最大具有 m個(gè)元素的空隊(duì)列。new Type ; Q =massert ( Q != 0 );/創(chuàng)建隊(duì)列 空間/斷言：動(dòng)態(tài)存儲(chǔ)分配成功與否插入函數(shù)templatevclass Type>void Queue <Type > : EnQueue

10、( Type & item ) assert ( ! IsFull ();rear = ( rear + 1 ) % m;Qrear = item;tag = 1 ;刪除函數(shù)templatevclass Type>Type QueuevType > : DeQueue ( ) assert ( ! IsEmpty ();/判隊(duì)列是否不滿，滿則出錯(cuò)處理/隊(duì)尾位置進(jìn)1,隊(duì)尾指針指示實(shí)際隊(duì)尾位置/進(jìn)隊(duì)列/標(biāo)志改1，表示隊(duì)列不空/判斷隊(duì)列是否不空，空則出錯(cuò)處理專(zhuān)業(yè)資料整理WOR格式專(zhuān)業(yè)資料整理WOR格式front = ( front + 1 ) % m; 位置tag = 0;ret

11、urn Qfront;/隊(duì)頭位置進(jìn)1,隊(duì)頭指針指示實(shí)際隊(duì)頭的前一/標(biāo)志改0, 表示棧不滿/返回原隊(duì)頭元素的值讀取隊(duì)頭元素函數(shù)templatevclass Type>Type QueuevType > : GetFront ( ) assert ( ! IsEmpty ();return Q(front + 1) % m;/判斷隊(duì)列是否不空，空則出錯(cuò)處理/返回隊(duì)頭元素的值第4章串、數(shù)組和廣義表1 .選擇題BBCAB BBCBB ABDCB C2.綜合應(yīng)用題'寫(xiě)出用KMP法求得的每個(gè)字符1 )已知模式串 t= abcaabbabcab 對(duì)應(yīng)的next和nextval函數(shù)值。式串

12、t 的next 和nextval 值如下:12345678910 11專(zhuān)業(yè)資料整理WOR格式專(zhuān)業(yè)資料整理WOR格式12t串a(chǎn)bcaabbabc abnextj0111223123 45nextvalj011021301105(3 )數(shù)組A中，每個(gè)元素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)，

13、行下標(biāo)可平移至1到11。(1)242( 2 )22( 3) s+182( 4) s+142 請(qǐng)將香蕉banana 用工具H( ) Head( )，T( ) Tail() 從L中取出L=(apple,(orange,(strawberry,(banana),peach),pear)H( H( T( H( T( H ( T( L)專(zhuān)業(yè)資料整理WOR格式專(zhuān)業(yè)資料整理WOR格式（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ù)。 i nt i ，n

14、um36 ； charch ;for ( i = 0 ; i<36; i+) numi =0;/ 初始化while ( ch = getchar () != #')/#'表示輸入字符串結(jié)束。if ( 0' <=ch<=9)'else if ( A' <=ch<= i=ch 48;numi+; Z') i=ch-65+10;numi+/ 數(shù)字字符; / 字母字符for(i=0 ；i<10； i+)/ 輸出數(shù)字字符的個(gè)數(shù)printf(“數(shù)字 d 的個(gè)數(shù)=% dn ，” i , numi）；for(i = 10;i&

15、lt;36 ; i+）/ 求出字母字符的個(gè)數(shù)printf（“字母字符c 的個(gè)數(shù)=% dn ”，i + 55,numi); /算法結(jié)束。第5章樹(shù)和二叉樹(shù)1.選擇題專(zhuān)業(yè)資料整理WOR格式專(zhuān)業(yè)資料整理WOR格式ADDCA CCBDC CCACC2 .應(yīng)用題A B D F C E G H，中序序列：B F D A G E H C(2)設(shè)一棵二叉樹(shù)的先序序列: 畫(huà)出這棵二叉樹(shù)。 畫(huà)出這棵二叉樹(shù)的后序線索樹(shù)將這棵二叉樹(shù)轉(zhuǎn)換成對(duì)應(yīng)的樹(shù)(或森 林)FGHDH(3)假設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別 為0.070.19 ，0.02，0.06 ，0.32，0.03，0.21，0.10

16、試為這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)， 6, (7,10)】,? 19, 21,32專(zhuān)業(yè)資料整理WOR格式專(zhuān)業(yè)資料整理WOR格式192132(28)(17)(11)710 6( 5 )方案比較.宀m1r rirr字母彳良口-對(duì) 應(yīng)厶七TT!出現(xiàn)止百編號(hào)編碼 S 亠J頻率十11000.072000.193411110-144007020065100.32出TlTt子母對(duì)應(yīng)現(xiàn)Zt±r

17、 口厶七TT!編號(hào)«編碼1頻率C C71C000CC A0.07r a r20010.19o0100.024011f0.0651000.3261010.03方案1的WPL2(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)于等長(zhǎng)二進(jìn)制編碼專(zhuān)業(yè)資料整理WOR格式專(zhuān)業(yè)資料整理WOR格式3 .算法設(shè)計(jì)題以二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，編寫(xiě)以下算法：(1)統(tǒng)計(jì)二叉樹(shù)的葉結(jié)點(diǎn)個(gè)數(shù)。

18、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)的左孩子和右孩子。void ChangeLR(BiTree &T)BiTree temp;if(T->lchild=

19、NULL&&T->rchild=NULL)return;elsetemp = T->lchild;專(zhuān)業(yè)資料整理WOR格式專(zhuān)業(yè)資料整理WOR格式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)的入度和出度； 鄰接矩陣； 鄰接表； 逆鄰接表。專(zhuān)業(yè)資料整理WOR格式專(zhuān)業(yè)資料整理WOR格式(2)(3)韓表(2)已知如圖6.28所

20、示的無(wú)向網(wǎng)，請(qǐng)給出: 鄰接矩陣； 鄰接表； 最小生成樹(shù)圖 6.28無(wú)°C3-4曲 5異 5X -X576專(zhuān)業(yè)資料整理WOR格式專(zhuān)業(yè)資料整理WOR格式TdeT6T-gba 4a -b Jb 9ddc4dTdT5TTc3c5b5c5d73f21rJATTTTe9.h .5f6T4A(3 )已知圖的鄰接矩陣如6.29探度優(yōu)先生成樹(shù)D1Dio00 1 0巾6 .6度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù)。廣攬憂先生成樹(shù)所示。試分別畫(huà)出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深專(zhuān)業(yè)資料整理WOR格式(4 )有向網(wǎng)如圖 6.29所示，試用迪杰斯特拉算法求出從頂點(diǎn)a到其他各頂點(diǎn)間的最短路徑，完成表6.9 。圖6.29鄰接矩

21、陣占八、i=1i=2i=3i=4i=5i=6151515151515(a,b)(a,c)12(a,d)ooooooJ廣Ia,c(a,b)(a,b)(a,b)(a,b)(a,b)121111(a,d)10(a,c,e)(a,c,f)ooa,c,f(a,c,f,d)10(a,c,e)16(a,c,f,g)a,c,f,e(a,c,f,d)16(a,c,f,g)a,c,f,e,d專(zhuān)業(yè)資料整理14(a,c,f,d,g)a,c,f,e,d,ga,c,f,e, d,g,bWOR格式終點(diǎn)集查找1.選擇題CDCABCCCDCBCADA2 .應(yīng)用題(1)假定對(duì)有序表：(3, 4 , 5, 7 , 24 , 30

22、, 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):3 742874 2454729554，需依次 查找元素與90，需依次 查找元素與63, 42，元素比30, 54較；30, 63,87, 95 元素比較;專(zhuān)業(yè)資料整理WOR格式專(zhuān)業(yè)資料整理WOR格式 求ASL之前，需要統(tǒng)計(jì)每個(gè)元素的查找次數(shù)。判定樹(shù)的前3層共查找1 + 2 X

23、 2 + 4X 3=17次；但最后一層未滿，不能用 8X 4,只能用5 X 4=20次，所以 ASL = 1/12(17 + 20 ) = 37/123.0812, 7, 17 , 11, 16, 2 , 13 , 9,4，請(qǐng)畫(huà)出所得到的二叉排序樹(shù)。717(2)在一棵空的二叉排序樹(shù)中依次插入關(guān)鍵字序列 為21 ,211162149132,4,7,9,11,12,13,16,17驗(yàn)算方法：用中序遍歷應(yīng)得到排序結(jié)果:21017，哈希函數(shù)為：H (key ) =key%16。用線性探測(cè)(5 )設(shè)哈希表的地址范圍為法處理沖突，輸入關(guān)鍵字序列：(10, 24, 32, 17, 31 , 30, 46 ,

24、 47, 40 , 63, 49),構(gòu)造哈希表，試回答下列問(wèn)題：畫(huà)出哈布表的示意圖；若查找關(guān)鍵63，需要依次與哪些關(guān)鍵字進(jìn)行比字較？若查找關(guān)鍵60，需要依次與哪些關(guān)鍵字比字較？假定每個(gè)關(guān)鍵字的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。專(zhuān)業(yè)資料整理WOR格式專(zhuān)業(yè)資料整理WOR格式然后順移，與相比，一共比較了46,47,32,17,636 次！ 查找60,首先要與H(60)=60%16=12號(hào)單元內(nèi)容比較，但因?yàn)?12號(hào)單元為空(應(yīng)當(dāng)有空標(biāo)記)，所以應(yīng)當(dāng)只比較這一次即可。 對(duì)于黑色數(shù)據(jù)元素，各比較1次；共6次；對(duì)紅色元素則各不相同，要統(tǒng)計(jì)移位的位數(shù)。“63 ”需要6次，“ 49”需要3次，“ 40

25、 ”需要2次，“ 46”需要3次，“ 47”需要3次，所以 ASL=1/11(6 + 2 + 3X 3+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)度：ASL succ = ( 1+1+1+2+3+4+1+2 ) /8=15/8以關(guān)鍵字 27 為例：H ( 27

26、 ) =27%7=6 (沖突)H 1= ( 6+1 ) %10=7 (沖突)H2= ( 6+2 2) %10=0 (沖突)H3= (6+3 3) %10=5所以比較了 4 次。專(zhuān)業(yè)資料整理WOR格式專(zhuān)業(yè)資料整理WOR格式第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)單選擇排序 堆排序 二路歸并排序直接插入排序212163

27、0281016*206182121630281016*206182121630281016*206182121628301016*206182101216283016*20618專(zhuān)業(yè)資料整理WOR格式210121616*283020618210121616*202830618261012161618202830折半插入排序排序過(guò)程同希爾排序（增量選取 5, 3 , 1 ）102166181216*621210181616*2610121616*18冒泡排序21216281016*212161016*20212101616*62101216616*2101

28、261616*2106121616*2610121616*2610121616*快速排序12 62101228306 2610122830203028 （增量選取5）203028（增量選取3）202830（增量選取1）20618306182830182028301820283018202830182028301820283018202830* 20161818* 201628 26 10 12 18 1616*20 28 30 專(zhuān)業(yè)資料整理WOR格式1826 1012*161820283016*2 6101216* 1618 2028 301，右子序列遞歸深度左子序列遞歸深度為為3簡(jiǎn)單選擇排1221630281016*20618261630281016*