數(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）因為x+共執(zhí)行了n-1+n-2+1= n(n-1)/2，所以執(zhí)行時間為O（n2）（6）O()第2章 線性表1選擇題babadbcabdcddac2算法設(shè)計題（6）設(shè)計一個算法，通過一趟遍歷在單鏈表中確定值最大的結(jié)點。ElemType Max (LinkList L )if(L-next=NULL) return NULL;pmax=L-next; /假定第一個結(jié)點中數(shù)據(jù)具有最大值p=L-next-next;while(p != NULL )/如果下一個

2、結(jié)點存在if(p-data pmax-data) pmax=p;p=p-next;return pmax-data;（7）設(shè)計一個算法，通過遍歷一趟，將鏈表中所有結(jié)點的鏈接方向逆轉(zhuǎn)，仍利用原表的存儲空間。void inverse(LinkList &L) / 逆置帶頭結(jié)點的單鏈表 L p=L-next; L-next=NULL; while ( p) q=p-next; / q指向*p的后繼 p-next=L-next; L-next=p; / *p插入在頭結(jié)點之后 p = q; （10）已知長度為n的線性表A采用順序存儲結(jié)構(gòu)，請寫一時間復(fù)雜度為O(n)、空間復(fù)雜度為O(1)的算法，該算法刪除

3、線性表中所有值為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ù)組，本算法刪除A中所有值為item的元素。i=1；j=n；設(shè)置數(shù)組低、高端指針（下標）。 while（ij） while（ij & Ai!=it

4、em）i+； 若值不為item，左移指針。 if（ij）while（ij & Aj=item）j-；若右端元素值為item，指針左移 if（ij）Ai+=Aj-； 算法討論 因元素只掃描一趟，算法時間復(fù)雜度為O（n）。刪除元素未使用其它輔助空間，最后線性表中的元素個數(shù)是j。第3章 棧和隊列1選擇題CCDAADABCDDDBCB2.算法設(shè)計題（2）回文是指正讀反讀均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。試寫一個算法判定給定的字符向量是否為回文。(提示：將一半字符入棧)根據(jù)提示，算法可設(shè)計為：/以下為順序棧的存儲結(jié)構(gòu)定義#define StackSize

5、100 /假定預(yù)分配的?？臻g最多為100個元素typedef char DataType;/假定棧元素的數(shù)據(jù)類型為字符typedef structDataType dataStackSize;int top;SeqStack;int IsHuiwen( char *t)/判斷t字符向量是否為回文，若是，返回1，否則返回0SeqStack s;int i , len;char temp;InitStack( &s);len=strlen(t); /求向量長度for ( i=0; ilen/2; i+)/將一半字符入棧Push( &s, ti);while( !EmptyStack( &s)/ 每

6、彈出一個字符與相應(yīng)字符比較temp=Pop (&s);if( temp!=Si) return 0 ;/ 不等則返回0else i+;return 1 ; / 比較完畢均相等則返回 1（7）假設(shè)以數(shù)組Qm存放循環(huán)隊列中的元素, 同時設(shè)置一個標志tag，以tag = 0和tag = 1來區(qū)別在隊頭指針(front)和隊尾指針(rear)相等時，隊列狀態(tài)為“空”還是“滿”。試編寫與此結(jié)構(gòu)相應(yīng)的插入(enqueue)和刪除(dlqueue)算法。【解答】循環(huán)隊列類定義#include template class Queue /循環(huán)隊列的類定義public: Queue ( int=10 ); Qu

7、eue ( ) delete Q; void EnQueue ( Type & item ); Type DeQueue ( ); Type GetFront ( ); void MakeEmpty ( ) front = rear = tag = 0; /置空隊列 int IsEmpty ( ) const return front = rear & tag = 0; /判隊列空否 int IsFull ( ) const return front = rear & tag = 1; /判隊列滿否private: int rear, front, tag;/隊尾指針、隊頭指針和隊滿標志 Ty

8、pe *Q;/存放隊列元素的數(shù)組 int m;/隊列最大可容納元素個數(shù)構(gòu)造函數(shù)template Queue: Queue ( int sz ) : rear (0), front (0), tag(0), m (sz) /建立一個最大具有m個元素的空隊列。 Q = new Typem;/創(chuàng)建隊列空間 assert ( Q != 0 );/斷言: 動態(tài)存儲分配成功與否插入函數(shù)template void Queue : EnQueue ( Type &item ) assert ( ! IsFull ( ) );/判隊列是否不滿，滿則出錯處理rear = ( rear + 1 ) % m;/隊尾位

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

10、是否不空，空則出錯處理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 5（3）數(shù)組A中，每個元素Ai,j的長度均為32個二進

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

12、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；i36；i+）numi；/ 初始化while（chgetchar（）!=#） /#表示輸入字符串結(jié)束。if（0=ch=9）i=ch48;numi+； / 數(shù)字字符 elseif（A=ch=Z）i=ch-65+10;numi+；/ 字母字符for（i=0；i10；i+） / 輸出數(shù)字字符的個數(shù)printf（“數(shù)

13、字d的個數(shù)dn”，i，numi）；for（i10；ilchild=NULL&T-rchild=NULL)return 1; /判斷該結(jié)點是否是葉子結(jié)點（左孩子右孩子都為空），若是則返回1elsereturn LeafNodeCount(T-lchild)+LeafNodeCount(T-rchild);（3）交換二叉樹每個結(jié)點的左孩子和右孩子。void ChangeLR(BiTree &T)BiTree temp;if(T-lchild=NULL&T-rchild=NULL)return;elsetemp = T-lchild;T-lchild = T-rchild;T-rchild = te

14、mp;ChangeLR(T-lchild);ChangeLR(T-rchild);第6章 圖1選擇題CBBBCBABAADCCDDB2應(yīng)用題（1）已知如圖6.27所示的有向圖，請給出： 每個頂點的入度和出度； 鄰接矩陣； 鄰接表； 逆鄰接表。 （2）已知如圖6.28所示的無向網(wǎng)，請給出： 鄰接矩陣； 鄰接表； 最小生成樹圖6.28 無向網(wǎng) ab4c3ba4c5d5e9ca3b5d5h5db5c5e7f6g5h4eb9d7f3fd6e3g2gd5f2h6hc5d4g6（3）已知圖的鄰接矩陣如6.29所示。試分別畫出自頂點1出發(fā)進行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。（4）有向網(wǎng)如圖6.29

15、所示，試用迪杰斯特拉算法求出從頂點a到其他各頂點間的最短路徑，完成表6.9。 圖6.29 鄰接矩陣D終點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(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終點集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

16、應(yīng)用題（1）假定對有序表：（3，4，5，7，24，30，42，54，63，72，87，95）進行折半查找，試回答下列問題： 畫出描述折半查找過程的判定樹； 若查找元素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層共查找12243=1

17、7次；但最后一層未滿，不能用84，只能用54=20次，所以ASL1/12（1720）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ī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)造哈希表，試回答下列問題： 畫出哈希表的示意圖；

18、 若查找關(guān)鍵字63，需要依次與哪些關(guān)鍵字進行比較？ 若查找關(guān)鍵字60，需要依次與哪些關(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)容比較，但因為12號單元為空（應(yīng)當有空標記），所以應(yīng)當只比較這一次即可。對于黑色數(shù)據(jù)元素，各比較1次；共6次；對紅色元素則各不相同，

19、要統(tǒng)計移位的位數(shù)?！?3”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=1/11（6233+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（沖突） H

20、1=（6+1）%10=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

21、16* 20 6 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 1

22、6* 18 20 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

23、10 12 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 12 16 16* 20 28 30 6 18 2 6 10 12 16 16* 18 20 28 30 堆排序第一步,形成初始大根堆（詳細過程略），第二步做堆排序。1221620103016*286183028