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

1、第1章 緒論5選擇題：CCBDCA6試分析下面各程序段的時間復(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í)行時間為O（n2）（6）O()第2章 線性表1選擇題babadbcabdcddac2算法設(shè)計題（6）設(shè)計一個算法，通過一趟遍歷在單鏈表中確定值最大的結(jié)點(diǎn)。ElemType Max (LinkList L )if(L->next=NULL) return NULL;pmax=L->next; /假定第一個結(jié)點(diǎn)中數(shù)據(jù)具有最大值p=L->next->next;while(p

2、 != NULL )/如果下一個結(jié)點(diǎn)存在if(p->data > pmax->data) pmax=p;p=p->next;return pmax->data;（7）設(shè)計一個算法，通過遍歷一趟，將鏈表中所有結(jié)點(diǎn)的鏈接方向逆轉(zhuǎn)，仍利用原表的存儲空間。void inverse(LinkList &L) / 逆置帶頭結(jié)點(diǎn)的單鏈表 L p=L->next; L->next=NULL; while ( p) q=p->next; / q指向*p的后繼 p->next=L->next; L->next=p; / *p插入在頭結(jié)點(diǎn)之后

3、 p = q; （10）已知長度為n的線性表A采用順序存儲結(jié)構(gòu)，請寫一時間復(fù)雜度為O(n)、空間復(fù)雜度為O(1)的算法，該算法刪除線性表中所有值為item的數(shù)據(jù)元素。題目分析 在順序存儲的線性表上刪除元素，通常要涉及到一系列元素的移動（刪第i個元素，第i+1至第n個元素要依次前移）。本題要求刪除線性表中所有值為item的數(shù)據(jù)元素，并未要求元素間的相對位置不變。因此可以考慮設(shè)頭尾兩個指針（i=1，j=n），從兩端向中間移動，凡遇到值item的數(shù)據(jù)元素時，直接將右端元素左移至值為item的數(shù)據(jù)元素位置。void Delete（ElemType A ，int n）A是有n個元素的一維數(shù)組，本算法刪除

4、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-； 算法討論 因元素只掃描一趟，算法時間復(fù)雜度為O（n）。刪除元素未使用其它輔助空間，最后線性表中的元素個數(shù)是j。第3章 棧和隊列1選擇題CCDAADABCDDDBCB2.算法設(shè)計題（2）回文是指正讀反讀均相同的字符序列，如“abba

5、”和“abdba”均是回文，但“good”不是回文。試寫一個算法判定給定的字符向量是否為回文。(提示：將一半字符入棧) 根據(jù)提示，算法可設(shè)計為：/以下為順序棧的存儲結(jié)構(gòu)定義#define StackSize 100 /假定預(yù)分配的棧空間最多為100個元素typedef char DataType;/假定棧元素的數(shù)據(jù)類型為字符typedef structDataType dataStackSize;int top;SeqStack; int IsHuiwen( char *t)/判斷t字符向量是否為回文，若是，返回1，否則返回0SeqStack s;int i , len;c

6、har temp;InitStack( &s);len=strlen(t); /求向量長度for ( i=0; i<len/2; i+)/將一半字符入棧Push( &s, ti);while( !EmptyStack( &s)/ 每彈出一個字符與相應(yīng)字符比較temp=Pop (&s);if( temp!=Si)  return 0 ;/ 不等則返回0else i+; return 1 ; / 比較完畢均相等則返回 1（7）假設(shè)以數(shù)組Qm存放循環(huán)隊列中的元素, 同時設(shè)置一個標(biāo)志tag，以tag = 0和tag = 1來區(qū)別在隊頭指針(fr

7、ont)和隊尾指針(rear)相等時，隊列狀態(tài)為“空”還是“滿”。試編寫與此結(jié)構(gòu)相應(yīng)的插入(enqueue)和刪除(dlqueue)算法?！窘獯稹垦h(huán)隊列類定義#include <assert.h>template <class Type> class Queue /循環(huán)隊列的類定義public: Queue ( int=10 ); Queue ( ) delete Q; void EnQueue ( Type & item ); Type DeQueue ( ); Type GetFront ( ); void MakeEmpty ( ) front = re

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

9、 sz ) : rear (0), front (0), tag(0), m (sz) /建立一個最大具有m個元素的空隊列。 Q = new Typem;/創(chuàng)建隊列空間 assert ( Q != 0 );/斷言: 動態(tài)存儲分配成功與否插入函數(shù)template<class Type> void Queue<Type> : EnQueue ( Type &item ) assert ( ! IsFull ( ) );/判隊列是否不滿，滿則出錯處理rear = ( rear + 1 ) % m;/隊尾位置進(jìn)1, 隊尾指針指示實(shí)際隊尾位置Qrear = item;/進(jìn)

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

11、sert ( ! IsEmpty ( ) );/判斷隊列是否不空，空則出錯處理return Q(front + 1) % m;/返回隊頭元素的值第4章 串、數(shù)組和廣義表1選擇題BBCAB BBCBB ABDCB C2.綜合應(yīng)用題（1）已知模式串t=abcaabbabcab寫出用KMP法求得的每個字符對應(yīng)的next和nextval函數(shù)值。模式串t的next和nextval值如下：j1 2 3 4 5 6 7 8 9 10 11 12 t串a(chǎn) b c a a b b a b c a bnextj0 1 1 1 2 2 3 1 2 3 4 5nextvalj0 1 1 0 2 1 3 0 1 1 0

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

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

14、numi+；/ 字母字符for（i=0；i<10；i+） / 輸出數(shù)字字符的個數(shù)printf（“數(shù)字d的個數(shù)dn”，i，numi）；for（i10；i<36；i+）/ 求出字母字符的個數(shù)printf（“字母字符c的個數(shù)dn”，i55，numi）；/ 算法結(jié)束。第5章 樹和二叉樹1選擇題ADDCA CCBDC CCACC2應(yīng)用題（2）設(shè)一棵二叉樹的先序序列： A B D F C E G H ，中序序列： B F D A G E H C畫出這棵二叉樹。畫出這棵二叉樹的后序線索樹。ABMFD(3)CEMHG將這棵二叉樹轉(zhuǎn)換成對應(yīng)的樹（或森林）。    

15、60;     (1) (2)（3） 假設(shè)用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。 試為這8個字母設(shè)計赫夫曼編碼。 試設(shè)計另一種由二進(jìn)制表示的等長編碼方案。 對于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。解：方案1；哈夫曼編碼先將概率放大100倍，以方便構(gòu)造哈夫曼樹。 w=7,19,2,6,32,3,21,10，按哈夫曼規(guī)則：【（2,3），6, (7,10)】, 19, 21, 32 0 1 0 1 0 119 21 32 0 10 1 0 17 10 6 0 12

16、 3 （100）（40） （60）19 21 32 （28）（17） （11） 7 10 6 （5） 2 3方案比較：字母編號對應(yīng)編碼出現(xiàn)頻率111000.072000.193111100.02411100.065100.326111110.037010.21811010.10字母編號對應(yīng)編碼出現(xiàn)頻率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10方案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的WPL3(0

17、.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3結(jié)論：哈夫曼編碼優(yōu)于等長二進(jìn)制編碼 3算法設(shè)計題以二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，編寫以下算法：（1）統(tǒng)計二叉樹的葉結(jié)點(diǎn)個數(shù)。int LeafNodeCount(BiTree T)if(T=NULL)return 0; /如果是空樹，則葉子結(jié)點(diǎn)個數(shù)為0else if(T->lchild=NULL&&T->rchild=NULL)return 1; /判斷該結(jié)點(diǎn)是否是葉子結(jié)點(diǎn)（左孩子右孩子都為空），若是則返回1elsereturn LeafNodeCount(T->lchi

18、ld)+LeafNodeCount(T->rchild);（3）交換二叉樹每個結(jié)點(diǎn)的左孩子和右孩子。void 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);第6章 圖1選擇題CBBBCBABAADCCDDB2應(yīng)用題（1）已知

19、如圖6.27所示的有向圖，請給出： 每個頂點(diǎn)的入度和出度； 鄰接矩陣； 鄰接表； 逆鄰接表。 （2）已知如圖6.28所示的無向網(wǎng)，請給出： 鄰接矩陣； 鄰接表； 最小生成樹圖6.28 無向網(wǎng) ab4c3ba4c5d5e9ca3b5d5h5db5c5e7f6g5h4eb9d7f3fd6e3g2gd5f2h6hc5d4g6（3）已知圖的鄰接矩陣如6.29所示。試分別畫出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。（4）有向網(wǎng)如圖6.29所示，試用迪杰斯特拉算法求出從頂點(diǎn)a到其他各頂點(diǎn)間的最短路徑，完成表6.9。 圖6.29 鄰接矩陣D終點(diǎn)i=1i=2i=3i=4i=5i=6b15(a

20、,b)15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)c2(a,c)d12(a,d)12(a,d)11(a,c,f,d)11(a,c,f,d)e10(a,c,e)10(a,c,e)f6(a,c,f)g16(a,c,f,g)16(a,c,f,g)14(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）假定對有序表：（3，4，5，7，24，30，42，54，63，72，87，95）進(jìn)行折半查找，試回答下列問題： 畫出描述折半查找過程的判定

21、樹； 若查找元素54，需依次與哪些元素比較？ 若查找元素90，需依次與哪些元素比較？ 假定每個元素的查找概率相等，求查找成功時的平均查找長度。先畫出判定樹如下（注：mid=ë(1+12)/2û=6）：305 633 7 42 87 4 24 54 72 95查找元素54，需依次與30, 63, 42, 54 元素比較；查找元素90，需依次與30, 63,87, 95元素比較；求ASL之前，需要統(tǒng)計每個元素的查找次數(shù)。判定樹的前3層共查找12×24×3=17次；但最后一層未滿，不能用8×4，只能用5×4=20次，所以ASL1/12（17

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

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

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

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

26、18 2 12 16 28 30 10 16* 20 6 18 2 10 12 16 28 30 16* 20 6 18 2 10 12 16 16* 28 30 20 6 18 2 10 12 16 16* 20 28 30 6 18 2 6 10 12 16 16* 20 28 30 18 2 6 10 12 16 16* 18 20 28 30 折半插入排序 排序過程同 希爾排序（增量選取5，3，1）10 2 16 6 18 12 16* 20 30 28 （增量選取5）6 2 12 10 18 16 16* 20 30 28 （增量選取3）2 6 10 12 16 16* 18 20

27、28 30 （增量選取1） 冒泡排序2 12 16 28 10 16* 20 6 18 30 2 12 16 10 16* 20 6 18 28 30 2 12 10 16 16* 6 18 20 28 30 2 10 12 16 6 16* 18 20 28 30 2 10 12 6 16 16* 18 20 28 30 2 10 6 12 16 16* 18 20 28 30 2 6 10 12 16 16* 18 20 28 302 6 10 12 16 16* 18 20 28 30 快速排序12 6 2 10 12 28 30 16* 20 16 18 6 2 6 10 12 28

28、30 16* 20 16 18 28 2 6 10 12 18 16 16* 20 28 30 18 2 6 10 12 16* 16 18 20 28 30 16* 2 6 10 12 16* 16 18 20 28 30左子序列遞歸深度為1，右子序列遞歸深度為3 簡單選擇排序2 12 16 30 28 10 16* 20 6 18 2 6 16 30 28 10 16* 20 12 18 2 6 10 30 28 16 16* 20 12 18 2 6 10 12 28 16 16* 20 30 18 2 6 10 12 16 28 16* 20 30 18 2 6 10 12 16 16* 28 20 30 18 2 6 10 12 16 16* 18 20 30 28 2 6 10 12 16 16* 18 20 28 30 2 6 10 12 16 16* 18 20 28 30 二路歸并排序2 12 16 30 10 28 16 * 20 6 18 2 12 16 30 10 16* 20 28 6 18 2 10