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

1、第1章緒論5選擇題：CCBDCA6試剖析下邊各程序段的時(shí)間復(fù)雜度。1）O（1）2）O（m*n）3）O（n2）4）O（log3n）（5）由于x+共履行了n-1+n-2+1=n(n-1)/2，所以履行時(shí)間為O（n2）（6）O(n)第2章線性表1選擇題babadbcabdcddac2算法設(shè)計(jì)題（6）設(shè)計(jì)一個(gè)算法，經(jīng)過一趟遍歷在單鏈表中確立值最大的結(jié)點(diǎn)。ElemTypeMax(LinkListL)if(L-next=NULL)returnNULL;pmax=L-next;/假定第一個(gè)結(jié)點(diǎn)中數(shù)據(jù)擁有最大值p=L-next-next;while(p!=NULL)/假以下一個(gè)結(jié)點(diǎn)存在if(p-datapma

2、x-data)pmax=p;p=p-next;returnpmax-data;（7）設(shè)計(jì)一個(gè)算法，經(jīng)過遍歷一趟，將鏈表中全部結(jié)點(diǎn)的鏈接方向逆轉(zhuǎn)，仍利用原表的儲(chǔ)存空間。voidinverse(LinkList&L)/逆置帶頭結(jié)點(diǎn)的單鏈表Lp=L-next;L-next=NULL;while(p)q=p-next;/q指向*p的后繼p-next=L-next;L-next=p;/*p插入在頭結(jié)點(diǎn)以后p=q;（10）已知長(zhǎng)度為n的線性表A采納次序儲(chǔ)存結(jié)構(gòu)，請(qǐng)寫一時(shí)間復(fù)雜度為O(n)、空間復(fù)雜度為O(1)的算法，該算法刪除線性表中全部值為item的數(shù)據(jù)元素。題目剖析在次序儲(chǔ)存的線性表上刪除元素，往常要

3、波及到一系列元素的挪動(dòng)（刪第i個(gè)元素，第i+1至第n個(gè)元素要挨次前移）。此題要求刪除線性表中全部值為item的數(shù)據(jù)元素，并未要求元素間的相對(duì)地點(diǎn)不變。所以能夠考慮設(shè)頭尾兩個(gè)指針（i=1，j=n），從兩頭向中間挪動(dòng)，凡碰到值item的數(shù)據(jù)元素時(shí)，直接將右端元素左移至值為item的數(shù)據(jù)元素地點(diǎn)。voidDelete（ElemTypeA，intn）A是有n個(gè)元素的一維數(shù)組，本算法刪除A中全部值為item的元素。i=1；j=n；設(shè)置數(shù)組低、高端指針（下標(biāo)）。while（ij）while（ij&Ai!=item）i+；若值不為item，左移指針。if（ij）while（ij&Aj=item）j-；若右端

4、元素值為item，指針左移if（ij）Ai+=Aj-；算法議論因元素只掃描一趟，算法時(shí)間復(fù)雜度為O（n）。刪除元素未使用其余協(xié)助空間，最后線性表中的元素個(gè)數(shù)是j。第3章棧和行列1選擇題CCDAADABCDDDBCB2.算法設(shè)計(jì)題（2）回文是指正讀反讀均同樣的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。試寫一個(gè)算法判斷給定的字符向量能否為回文。(提示：將一半字符入棧)依據(jù)提示，算法可設(shè)計(jì)為：以下為次序棧的儲(chǔ)存結(jié)構(gòu)定義#defineStackSize100/假定預(yù)分派的?？臻g最多為100個(gè)元素typedefcharDataType;/假定棧元素的數(shù)據(jù)種類為字符type

5、defstructDataTypedataStackSize;inttop;SeqStack;intIsHuiwen(char*t)/判斷t字符向量能否為回文，假如，返回1，不然返回0SeqStacks;inti,len;chartemp;InitStack(&s);len=strlen(t);/求向量長(zhǎng)度for(i=0;ilen/2;i+)/Push(&s,ti);while(!EmptyStack(&s)將一半字符入棧/每彈出一個(gè)字符與相應(yīng)字符比較temp=Pop(&s);if(temp!=Si)return0;/不等則返回0elsei+;return1;/比較完成均相等則返回1（頭指針7

6、）假定以數(shù)組Qm寄存循環(huán)行列中的元素(front)和隊(duì)尾指針(rear)相等時(shí)，行列狀態(tài)為,同時(shí)設(shè)置一個(gè)標(biāo)記tag，以tag=0和tag=1來差別在隊(duì)“空”仍是“滿”。試編寫與此結(jié)構(gòu)相應(yīng)的插入(enqueue)和刪除(dlqueue)算法?！窘獯稹垦h(huán)行列類定義#includetemplateclassQueue/循環(huán)行列的類定義public:Queue(int=10);Queue()deleteQ;voidEnQueue(Type&item);TypeDeQueue();TypeGetFront();voidMakeEmpty()front=rear=tag=intIsEmpty()cons

7、treturnfront=rear0;/置空行列&tag=0;/判行列空否intIsFull()constreturnfront=rear&tag=1;/判行列滿否private:intrear,front,tag;/隊(duì)尾指針、隊(duì)頭指針和隊(duì)滿標(biāo)記Type*Q;intm;/寄存行列元素的數(shù)組/行列最大可容納元素個(gè)數(shù)結(jié)構(gòu)函數(shù)templateQueue:Queue(intsz):rear(0),front(0),tag(0),m(sz)/成立一個(gè)最大擁有m個(gè)元素的空行列。Q=newTypem;assert(Q!=0);/創(chuàng)立行列空間/斷言:動(dòng)向儲(chǔ)存分派成功與否插入函數(shù)templatevoidQueu

8、e:EnQueue(Type&item)assert(!IsFull();rear=(rear+1)%m;Qrear=item;tag=1;/判行列能否不滿，滿則犯錯(cuò)辦理/隊(duì)尾地點(diǎn)進(jìn)1,隊(duì)尾指針指示實(shí)質(zhì)隊(duì)尾地點(diǎn)/進(jìn)行列/標(biāo)記改1，表示行列不空刪除函數(shù)templateTypeQueue:DeQueue()assert(!IsEmpty();/判斷行列能否不空，空則犯錯(cuò)辦理front=(front+1)%m;/隊(duì)頭地點(diǎn)進(jìn)1,隊(duì)頭指針指示實(shí)質(zhì)隊(duì)頭的前一地點(diǎn)tag=0;/標(biāo)記改0,表示棧不滿returnQfront;/返回原隊(duì)頭元素的值讀取隊(duì)頭元素函數(shù)templateTypeQueue:GetFron

9、t()assert(!IsEmpty();/判斷行列能否不空，空則犯錯(cuò)辦理returnQ(front+1)%m;/返回隊(duì)頭元素的值第4章串、數(shù)組和廣義表1選擇題BBCABBBCBBABDCBC2.綜合應(yīng)用題（1）已知模式串t=abcaabbabcab寫出用KMP法求得的每個(gè)字符對(duì)應(yīng)的next和nextval函數(shù)值。模式串t的next和nextval值以下：j123456789101112t串a(chǎn)bcaabbabcabnextj011122312345nextvalj011021301105（3）數(shù)組A中，每個(gè)元素Ai,j的長(zhǎng)度均為32個(gè)二進(jìn)位,行下標(biāo)從-1到9，列下標(biāo)從開始連續(xù)寄存主儲(chǔ)存器中，主

10、儲(chǔ)存器字長(zhǎng)為16位。求：寄存該數(shù)組所需多少單元？寄存數(shù)組第4列全部元素起碼需多少單元？數(shù)組按行寄存時(shí)，元素A7,4的開端地點(diǎn)是多少？1到11，從首地點(diǎn)S數(shù)組按列寄存時(shí)，元素A4,7的開端地點(diǎn)是多少？每個(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,(banana),peach),pear)H（H（T（H（T（H（T（L）（5）寫一個(gè)算法統(tǒng)計(jì)在輸入字符串中各個(gè)不一樣字符

11、出現(xiàn)的頻度并將結(jié)果存入文件（字符串中的合法字符為A-Z這26個(gè)字母和0-9這10個(gè)數(shù)字）。voidCount（）統(tǒng)計(jì)輸入字符串中數(shù)字字符和字母字符的個(gè)數(shù)。inti，num36；charch；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ù)字字符的個(gè)數(shù)printf（“數(shù)字d的個(gè)數(shù)dn”，i，numi）；for（i10；ilchild=NULL&T-rchild=NULL

12、)return1;/判斷該結(jié)點(diǎn)是不是葉子結(jié)點(diǎn)（左孩子右孩子都為空），假如則返回1elsereturnLeafNodeCount(T-lchild)+LeafNodeCount(T-rchild);（3）互換二叉樹每個(gè)結(jié)點(diǎn)的左孩子和右孩子。voidChangeLR(BiTree&T)BiTreetemp;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選擇題CBBBCBABAADCCD

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

14、(a,b)(a,b)(a,b)(a,b)(a,b)c2(a,c)d12121111(a,d)(a,d)(a,c,f,d)(a,c,f,d)e1010(a,c,e)(a,c,e)f6(a,c,f)g161614(a,c,f,g)(a,c,f,g)(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點(diǎn)集第7章查找1選擇題CDCABCCCDCBCADA2應(yīng)用題1）假定對(duì)有序表：（3，4，5，7，24，30，42，54，63，72，87，95）進(jìn)行折半查找，試回答以下問題：畫出描繪折半查找過程的判斷樹；若查找元素54，需挨次與哪些元

15、素比較？若查找元素90，需挨次與哪些元素比較？假定每個(gè)元素的查找概率相等，求查找成功時(shí)的均勻查找長(zhǎng)度。先畫出判斷樹以下（注：mid=(1+12)/2=6）：30563374287424547295查找元素54，需挨次與30,63,42,54元素比較；查找元素90，需挨次與30,63,87,95元素比較；求ASL以前，需要統(tǒng)計(jì)每個(gè)元素的查找次數(shù)。判斷樹的前3層共查找12243=17次；但最后一層未滿，不可以用84，只好用54=20次，所以ASL1/12（1720）37/123.08（2）在一棵空的二叉排序樹中挨次插入重點(diǎn)字序列為12，7，17，11，16，2，13，9，21，4，請(qǐng)畫出所獲得的二

16、叉排序樹。1271721116214913驗(yàn)算方法：用中序遍歷應(yīng)獲得排序結(jié)果：2,4,7,9,11,12,13,16,17，215）設(shè)哈希表的地點(diǎn)范圍為017，哈希函數(shù)為：H（key）=key%16。用線性探測(cè)法辦理矛盾，輸入重點(diǎn)字序列：（10，24，32，17，31，30，46，47，40，63，49），結(jié)構(gòu)哈希表，試回答以下問題：畫出哈希表的表示圖；若查找重點(diǎn)字63，需要挨次與哪些重點(diǎn)字進(jìn)行比較？若查找重點(diǎn)字60，需要挨次與哪些重點(diǎn)字比較？假定每個(gè)重點(diǎn)字的查找概率相等，求查找成功時(shí)的均勻查找長(zhǎng)度。畫表以下：012345678910111213141516173217634924401030

17、314647查找63,第一要與H(63)=63%16=15號(hào)單元內(nèi)容比較，即63vs31,no;而后順移，與46,47,32,17,63對(duì)比，一共比較了6次！查找60,第一要與H(60)=60%16=12號(hào)單元內(nèi)容比較，但由于12號(hào)單元為空（應(yīng)該有空標(biāo)記），所以應(yīng)該只比較這一次即可。關(guān)于黑色數(shù)據(jù)元素，各比較1次；共6次；對(duì)紅色元素則各不同樣，要統(tǒng)計(jì)移位的位數(shù)?！?3”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=1/11（6233+6）23/116）設(shè)有一組重點(diǎn)字（9，01，23，14，55，20，84，27），采納哈希函數(shù)：H（key）=key

18、%7，表長(zhǎng)為10，用開放地點(diǎn)法的二次探測(cè)法辦理矛盾。要求：對(duì)該重點(diǎn)字序列結(jié)構(gòu)哈希表，并計(jì)算查找成功的均勻查找長(zhǎng)度。散列地點(diǎn)0123456789重點(diǎn)字140192384275520比較次數(shù)11123412均勻查找長(zhǎng)度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8以重點(diǎn)字27為例：H（27）=27%7=6（矛盾）H1=（6+1）%10=7（矛盾）23H2=（6+2）%10=0（矛盾）H3=（6+3）%10=5所以比較了4次。第8章排序1選擇題CDBDCBCDBCBCCCA2應(yīng)用題1）設(shè)待排序的重點(diǎn)字序列為12，2，16，30，28，10，16*，20，6，18，試分別寫出使用以

19、下排序方法，每趟排序結(jié)束后重點(diǎn)字序列的狀態(tài)。直接插入排序折半插入排序希爾排序（增量選用5，3，1）冒泡排序迅速排序簡(jiǎn)單項(xiàng)選擇擇排序堆排序二路合并排序直接插入排序2121630281016*206182121630281016*206182121630281016*206182121628301016*206182101216283016*20618210121616*283020618210121616*202830618261012161618202830折半插入排序排序過程同希爾排序（增量選用5，3，1）102166181216*203028（增量選

20、用5）621210181616*203028（增量選用3）2610121616*18202830（增量選用1）冒泡排序21216281016*2061830212161016*206182830212101616*6182028302101216616*182028302101261616*182028302106121616*182028302610121616*182028302610121616*18202830迅速排序12621012283016*2016186261012283016*20161828261012181616*2028301826101216*161820283016

21、*26101216*1618202830左子序列遞歸深度為1，右子序列遞歸深度為3簡(jiǎn)單項(xiàng)選擇擇排序2121630281016*20618261630281016*201218261030281616*201218261012281616*203018261012162816*2030182610121616182030282610121616*182028302610121616*18202830二路合并排序2121630102816*2061821216301016*2028618210121616*2028306182610121616*18202830堆排序第一步,形成初始大根堆（詳盡過程略），第二步做堆排序。1230216281630281016*20181016*206182612初始排序不是大根堆形成初始大根堆12282816201620181016*12181016*