數(shù)據(jù)結(jié)構(gòu)與算法實(shí)例教程課后答案付學(xué)良

《數(shù)據(jù)結(jié)構(gòu)與算法實(shí)例教程》課后答案作者：付學(xué)良李宏慧習(xí)題1答案:數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)的形式定義如下：數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組Data_Structure=(D,S),其中D是數(shù)據(jù)元素的有限集合，S是D上關(guān)系的有限集合。數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集合。答案:數(shù)據(jù)(data)：數(shù)據(jù)是對(duì)客觀(guān)事物的符號(hào)表示，在計(jì)算機(jī)領(lǐng)域指所有能輸入到計(jì)算機(jī)當(dāng)中被計(jì)算機(jī)程序處理的符號(hào)的總稱(chēng)。數(shù)據(jù)元素(dataelement)：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中作為一個(gè)整體進(jìn)行考慮和處理。答案:順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是依據(jù)數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系，并采用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)各個(gè)數(shù)據(jù)元素。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是通過(guò)存儲(chǔ)元素地址來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系，并且每個(gè)數(shù)據(jù)元素在存儲(chǔ)器中的存儲(chǔ)地址可以是不連續(xù)的答案:抽象數(shù)據(jù)類(lèi)型(AbstractDataType，簡(jiǎn)稱(chēng)ADT)是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。答案:算法(algorithm)是為解決某特定問(wèn)題所采取的方法和步驟，是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。算法應(yīng)該具有下列特性：⑴有窮性⑵確定性⑶可行性⑷輸入⑸輸出答案:X2X1X5X4X3X2X1X5X4X3答案:intmax(intb,intc){intm;m=a;if(b>m)m=b;if(c>m)m=c;returnm;}答案:其中V是數(shù)據(jù)元素的有限集合，K是V上關(guān)系的有限集合。習(xí)題2一、單項(xiàng)選擇題1.以下關(guān)于線(xiàn)性表的說(shuō)法不正確的是（C）。

A．線(xiàn)性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類(lèi)型。B．線(xiàn)性表中包含的數(shù)據(jù)元素個(gè)數(shù)不是任意的。C．線(xiàn)性表中的每個(gè)結(jié)點(diǎn)都有且只有一個(gè)直接前趨和直接后繼。D．存在這樣的線(xiàn)性表：表中各結(jié)點(diǎn)都沒(méi)有直接前趨和直接后繼。2.線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)是一種（A）的存儲(chǔ)結(jié)構(gòu)。

A．隨機(jī)存取 B．順序存取 C．索引存取 D．散列存取3.在順序表中，只要知道（D），就可在相同時(shí)間內(nèi)求出任一結(jié)點(diǎn)的存儲(chǔ)地址。A．基地址 B．結(jié)點(diǎn)大小C．向量大小 D．基地址和結(jié)點(diǎn)大小4.在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素(0<=i<=n)時(shí)，需向前移動(dòng)（A）個(gè)元素。A．n-i B．n-i+l C．n-i-1 D．i5.在等概率情況下，順序表的插入操作要移動(dòng)（B）結(jié)點(diǎn)。

A．全部B．1/2

C．1/3

D．1/46.在一個(gè)單鏈表中，已知q結(jié)點(diǎn)是p結(jié)點(diǎn)的前趨結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則須執(zhí)行（B）。A．s->next=p->next;p->next=sB．q->next=s;s->next=pC．p->next=s->next;s->next=pD．p->next=s;s->next=q7.線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址（D）。A．必須是連續(xù)的 B．一定是不連續(xù)的C．部分地址必須是連續(xù)的 D．連續(xù)與否均可以8.從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x的結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較（C）個(gè)元素結(jié)點(diǎn)。A．n/2 B．n C．（n+1）/2 D．（n-1）/29.設(shè)單鏈表中指針p指向結(jié)點(diǎn)m，若要?jiǎng)h除m之后的結(jié)點(diǎn)（若存在），則需修改指針的操作為（A）。A．p->next=p->next->next; B．p=p->next;C．p=p->next->next; D．p->next=p;10.在雙向循環(huán)鏈表中，在p所指的結(jié)點(diǎn)之后插入s指針?biāo)傅慕Y(jié)點(diǎn)，其操作是（D）。A．p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;B．s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;C．p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;D．s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;11.在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并保持該表有序的時(shí)間復(fù)雜度是（B）。

A．O(1)

B．O(n)

C．O(n2) D．O(log2n)12.在（C）運(yùn)算中，使用順序表比鏈表好。

A．插入

B．刪除

C．根據(jù)序號(hào)查找

D．根據(jù)元素值查找二、填空題1.線(xiàn)性表是一種典型的線(xiàn)性結(jié)構(gòu)。2.在一個(gè)長(zhǎng)度為n的順序表的第i個(gè)元素之前插入一個(gè)元素，需要后移_n-i+1__個(gè)元素。3.順序表中邏輯上相鄰的元素的物理位置__相鄰。4.在線(xiàn)性表的順序存儲(chǔ)中，元素之間的邏輯關(guān)系是通過(guò)物理存儲(chǔ)位置決定的；在線(xiàn)性表的鏈接存儲(chǔ)中，元素之間的邏輯關(guān)系是通過(guò)鏈域的指針值決定的。5.在雙向鏈表中，每個(gè)結(jié)點(diǎn)含有兩個(gè)指針域，一個(gè)指向前趨結(jié)點(diǎn)，另一個(gè)指向后繼結(jié)點(diǎn)。6.當(dāng)對(duì)一個(gè)線(xiàn)性表經(jīng)常進(jìn)行存取操作，而很少進(jìn)行插入和刪除操作時(shí)，則采用順序存儲(chǔ)結(jié)構(gòu)為宜。相反，當(dāng)經(jīng)常進(jìn)行的是插入和刪除操作時(shí)，則采用鏈接存儲(chǔ)結(jié)構(gòu)為宜。7.順序表中邏輯上相鄰的元素，物理位置___一定____相鄰，單鏈表中邏輯上相鄰的元素，物理位置___不一定____相鄰。8.根據(jù)線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)所含指針的個(gè)數(shù)，鏈表可分為單鏈表和__雙鏈表_____；而根據(jù)指針的聯(lián)接方式，鏈表又可分為非循環(huán)鏈表和循環(huán)鏈表。9.在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是使空表和非空表算法處理一致。10.對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為_(kāi)_O(1)____，在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為_(kāi)__O(n)____。三、簡(jiǎn)答題1.線(xiàn)性表的兩種存儲(chǔ)結(jié)構(gòu)各有哪些優(yōu)缺點(diǎn)？答：1．線(xiàn)性表具有兩種存儲(chǔ)結(jié)構(gòu)即順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)。線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)可以直接存取數(shù)據(jù)元素，方便靈活、效率高，但插入、刪除操作時(shí)將會(huì)引起元素的大量移動(dòng)，因而降低效率：而在鏈接存儲(chǔ)結(jié)構(gòu)中內(nèi)存采用動(dòng)態(tài)分配，利用率高，但需增設(shè)指示結(jié)點(diǎn)之間關(guān)系的指針域，存取數(shù)據(jù)元素不如順序存儲(chǔ)方便，但結(jié)點(diǎn)的插入、刪除操作較簡(jiǎn)單。2.對(duì)于線(xiàn)性表的兩種存儲(chǔ)結(jié)構(gòu)，如果有n個(gè)線(xiàn)性表同時(shí)并存，而且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)發(fā)生變化，線(xiàn)性表的總數(shù)也會(huì)自動(dòng)改變，在此情況下，應(yīng)選用哪一種存儲(chǔ)結(jié)構(gòu)？為什么？答：應(yīng)選用鏈接存儲(chǔ)結(jié)構(gòu)，因?yàn)殒準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組任意的存儲(chǔ)單元依次存儲(chǔ)線(xiàn)性表中的各元素，這里存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的：這種存儲(chǔ)結(jié)構(gòu)對(duì)于元素的刪除或插入運(yùn)算是不需要移動(dòng)元素的，只需修改指針即可，所以很容易實(shí)現(xiàn)表的容量的擴(kuò)充。3.對(duì)于線(xiàn)性表的兩種存儲(chǔ)結(jié)構(gòu)，若線(xiàn)性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線(xiàn)性表中的元素，應(yīng)選用何種存儲(chǔ)結(jié)構(gòu)？試說(shuō)明理由。答：應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)，因?yàn)槊總€(gè)數(shù)據(jù)元素的存儲(chǔ)位置和線(xiàn)性表的起始位置相差一個(gè)和數(shù)據(jù)元素在線(xiàn)性表中的序號(hào)成正比的常數(shù)。因此，只要確定了其起始位置，線(xiàn)性表中的任一個(gè)數(shù)據(jù)元素都可隨機(jī)存取，因此，線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)，而鏈表則是一種順序存取的存儲(chǔ)結(jié)構(gòu)。4.在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針好嗎？為什么?答：設(shè)尾指針比設(shè)頭指針好。尾指針是指向終端結(jié)點(diǎn)的指針，用它來(lái)表示單循環(huán)鏈表可以使得查找鏈表的開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)都很方便，設(shè)一帶頭結(jié)點(diǎn)的單循環(huán)鏈表，其尾指針為rear，則開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)的位置分別是rear->next->next和rear,查找時(shí)間都是O(1)。若用頭指針來(lái)表示該鏈表，則查找終端結(jié)點(diǎn)的時(shí)間為O(n)。5.下述算法的功能是什么?CLinkList*Demo(LinkList*L){//L是無(wú)頭結(jié)點(diǎn)的單鏈表CLinkList*q,*p;if(L&&L->next){q=L;L=L->next;p=L;while(p->next)p=p->next;p->next=q;q->next=NULL;}returnL;}答：該算法的功能是：將開(kāi)始結(jié)點(diǎn)摘下鏈接到終端結(jié)點(diǎn)之后成為新的終端結(jié)點(diǎn)，而原來(lái)的第二個(gè)結(jié)點(diǎn)成為新的開(kāi)始結(jié)點(diǎn)，返回新鏈表的頭指針。四、算法設(shè)計(jì)題1．設(shè)順序表va中的數(shù)據(jù)元素遞增有序。試設(shè)計(jì)一個(gè)算法，將x插入到順序表的適當(dāng)位置上，以保持該表的有序性。算法源代碼如下：voidInsert_SqList(SqListva,intx)/*把x插入遞增有序表va中*/{inti; if(va.length>maxLen)return; for(i=va.length-1;va.elem[i]>x&&i>=0;i--)va.elem[i+1]=va.elem[i]; va.elem[i+1]=x; va.length++;}2．設(shè)A=（a1，a2，…，am）和B=（b1，b2，…，bn）均為順序表，試設(shè)計(jì)一個(gè)合并算法，將順序表B合并到A中，并確保A中元素是遞增有序的（請(qǐng)注意：在算法中，不要破壞原表A和B）。算法描述：此題并沒(méi)有特別說(shuō)明兩個(gè)順序表A和B是遞增有序的，因此必須充分考慮在不是遞增有序的情況下如何進(jìn)行合并。首先應(yīng)采用SORT排序算法將順序表A進(jìn)行遞增排序，而B(niǎo)可以不必進(jìn)行遞增排序的操作，總之要在保證A是遞增有序的前提下再將順序表B進(jìn)行合并。算法源代碼如下：VoidMergeList（SeqList&A，SeqListB）{intflag;for(inti=0;i<B.length;i++){flag=-1；for(intj=0;j<A.lenght;j++){ If（B.data[i]<A.data[j]） { flag=j；break；}}if(flag==-1){data[A.length]=B.data[i]A.length++;}Else{For(intk=A.length-1;k>=flag;k--)A.data[k+1]=A.data[k];A.data[flag]=B.data[i];A.length++;}}}3.已知線(xiàn)性表的元素按遞增順序排列，并以帶頭結(jié)點(diǎn)的單鏈表作存儲(chǔ)結(jié)構(gòu)。試編寫(xiě)一個(gè)刪除表中所有值大于min且小于max的元素（若表中存在這樣的元素）的算法。算法源代碼如下：delete(CLinkList*head,intmax,intmin){CLinkList*p,*q;q=head;p=head->next;while(p!=NULL){if((p->data<=min)||(p->data>=max)){q=p;p=p->next;}else{q->next=p->next;deletep;p=q->next;}}}4.設(shè)計(jì)將帶頭結(jié)點(diǎn)的鏈表逆置算法。算法源代碼如下：voidinvert(LinkList*head){//逆置head指針?biāo)赶虻膯窝h(huán)鏈表linklist*p,*q,*s;q=head;p=head->next;while(p!=head)//當(dāng)表不為空時(shí)，逐個(gè)結(jié)點(diǎn)逆置{s=q;q=p;p=p->next;q->next=s;}p->next=q;}5.假設(shè)有一個(gè)帶表頭結(jié)點(diǎn)的鏈表，表頭指針為head，每個(gè)結(jié)點(diǎn)含三個(gè)域：data,next和prior。其中data為整型數(shù)域，next和prior均為指針域?，F(xiàn)在所有結(jié)點(diǎn)已經(jīng)由next域連接起來(lái)，試編一個(gè)算法，利用prior域（此域初值為NULL）把所有結(jié)點(diǎn)按照其值從小到大的順序鏈接起來(lái)。算法描述：定義類(lèi)型DLinkList如下：typedefstructnode{intdata;structnode*next,*prior;}LinkList;此題可采用插入排序的方法，設(shè)p指向待插入的結(jié)點(diǎn)，用q搜索已由prior域鏈接的有序表找到合適位置將p結(jié)點(diǎn)鏈入。算法源代碼如下：insert(DLinkList*head){DLinkList*p,*s,*q;p=head->next;//p指向待插入的結(jié)點(diǎn)，初始時(shí)指向第一個(gè)結(jié)點(diǎn)while(p!=NULL){s=head;//s指向q結(jié)點(diǎn)的前趨結(jié)點(diǎn)q=head->prior;//q指向由prior域構(gòu)成的鏈表中待比較的結(jié)點(diǎn)while((q!=NULL)&&(p->data>q->data))//查找插入結(jié)點(diǎn)p的合適的插入位置{s=q;q=q->prior;}s->prior=p;p->prior=q;//結(jié)點(diǎn)p插入到結(jié)點(diǎn)s和結(jié)點(diǎn)q之間p=p->next;}}第三、四章順序隊(duì)列的“假溢出”是怎樣產(chǎn)生的?如何解決假溢出?如何判斷循環(huán)隊(duì)列是空還是滿(mǎn)？

答：對(duì)順序隊(duì)列進(jìn)行多次入隊(duì)和出隊(duì)操作，當(dāng)入隊(duì)元素放入數(shù)組的最后一個(gè)元素后，此時(shí)若再有元素需要入隊(duì)，因?yàn)閞ear已超出數(shù)組最大下標(biāo)，元素不能被插入隊(duì)尾，而此時(shí)隊(duì)列的存儲(chǔ)空間并未占滿(mǎn)，這時(shí)產(chǎn)生假溢出。

為解決這種假溢出現(xiàn)象，一個(gè)較好的辦法是將順序隊(duì)列想象成一個(gè)環(huán)狀的空間，讓第一個(gè)存儲(chǔ)單元緊接在最后一個(gè)存儲(chǔ)單元之后。

判斷循環(huán)隊(duì)列是空還是滿(mǎn)的方法：一種方法是設(shè)一個(gè)標(biāo)志變量flag。初始時(shí)，flag=0，front=rear,表示為空隊(duì)列，當(dāng)有數(shù)據(jù)元素入隊(duì)時(shí)，將flag設(shè)為1，當(dāng)有數(shù)據(jù)元素出隊(duì)時(shí)，將flag設(shè)為0。這樣就可以區(qū)分隊(duì)空和隊(duì)滿(mǎn)了。當(dāng)front=rear且flag=0時(shí)，表示隊(duì)列為空；而front=rear且flag=1時(shí)，表示隊(duì)列滿(mǎn)。另一種方法是少用一個(gè)存儲(chǔ)空間，當(dāng)隊(duì)頭指針在隊(duì)尾指針的下一個(gè)位置時(shí)，作為隊(duì)列已滿(mǎn)的狀態(tài)，也就是說(shuō)隊(duì)頭指針的前一個(gè)存儲(chǔ)空間不能存儲(chǔ)數(shù)據(jù)元素，即有MAX_SIZE個(gè)數(shù)組元素的數(shù)組僅能表示一個(gè)長(zhǎng)度為MAX_SIZE-1的循環(huán)隊(duì)列。當(dāng)front=rear時(shí)表示隊(duì)列為空，而當(dāng)(rear+1)%MAX_SIZE=front時(shí)，表示隊(duì)列滿(mǎn)。若用一個(gè)大小為5的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為2和4，當(dāng)從隊(duì)列中刪除2個(gè)元素，再加入3個(gè)元素后，rear和front的值分別為多少？

答：front=1，rear=0設(shè)循環(huán)隊(duì)列的容量為30（序號(hào)從0到29），,經(jīng)過(guò)一系列的入隊(duì)和出隊(duì)運(yùn)算后，有：front=8，rear=23；front=25，rear=13；問(wèn)在這種情況下,循環(huán)隊(duì)列中分別有多少個(gè)元素？

答：15，18寫(xiě)出下列程序段的輸出結(jié)果。

voidmain(){

SeqQueueQ;

SETypex,y;

x=’L’;

y=’E’;

Q.EnQue(x);

Q.EnQue(‘H’);

x=Q.DeQue();

Q.EnQue(y);

Q.EnQue(x);

Q.EnQue(x);

x=Q.DeQue();

Q.EnQue(‘O’);

cout<<x;

while(!Q.IsEmpty()){

y=Q.DeQue();

cout<<y;

}

}答：輸出HELLO指出下列程序段的功能。

voidfun2(SeqQueue&Q){//假設(shè)棧和隊(duì)列的元素類(lèi)型為SEType相同

SeqStackS;

SETyped;

while(!Q.IsEmpty()){

d=Q.DeQue();

S.Push(d);

}

while(!S.IsEmpty()){

d=S.Pop();

Q.EnQue(d);

}

}

答：將隊(duì)列中的元素逆置。在循環(huán)隊(duì)列中，為解決判斷隊(duì)空隊(duì)滿(mǎn)條件相同的問(wèn)題，本書(shū)提出兩種解決方法。本書(shū)中循環(huán)隊(duì)列的實(shí)現(xiàn)使用了第二種方法，即少用一個(gè)存儲(chǔ)空間。假設(shè)使用第一種方法來(lái)解決該問(wèn)題，即另設(shè)一個(gè)表示變量flag，以flag為0或1來(lái)區(qū)分尾指針和頭指針值相同時(shí)隊(duì)列的狀態(tài)是空還是滿(mǎn)。試編寫(xiě)相應(yīng)的入隊(duì)和出隊(duì)算法。

voidSeqQueue::EnQue(SETypee){if(flag==1)//隊(duì)列滿(mǎn)cout<<"\n隊(duì)列已滿(mǎn)!"<<endl;else{//隊(duì)列不滿(mǎn)elem[rear]=e;//先將要入隊(duì)的元素放入隊(duì)尾指針rear所指的位置rear=(rear+1)%MAX_SIZE;//然后隊(duì)尾指針增1flag=1;}}SETypeSeqQueue::DeQue(){SETypee;if(flag==0){//隊(duì)空cout<<"隊(duì)列已空!"<<endl;e=NULL;}else{//隊(duì)列不空 e=elem[front];//先取出隊(duì)頭指針?biāo)傅年?duì)頭元素，front=(front+1)%MAX_SIZE;//然后將隊(duì)頭指針增flag=0;}returne;}假設(shè)用變量rear和length分別指示循環(huán)隊(duì)列中隊(duì)尾元素的位置和內(nèi)含元素的個(gè)數(shù)。試給出此循環(huán)隊(duì)列的定義，并寫(xiě)出相應(yīng)的入隊(duì)和出隊(duì)算法。

classQueue{

private:intfront,rear,length;

SETypedata[50];

public:

voidcreateQue();

voidEnQue(SETypee);

SETypeDeQue();

......

}

voidSeqQueue::EnQue(SETypee){if((rear+1)%MAX_SIZE==front)//隊(duì)列滿(mǎn)cout<<"\n隊(duì)列已滿(mǎn)!"<<endl;else{//隊(duì)列不滿(mǎn)rear=(rear+1)%MAX_SIZE;//然后隊(duì)尾指針增1elem[rear]=e;//先將要入隊(duì)的元素放入隊(duì)尾指針rear所指的位置length++;}}SETypeSeqQueue::DeQue(){SETypee;if(front==rear){//隊(duì)空cout<<"隊(duì)列已空!"<<endl;e=NULL;}else{//隊(duì)列不空1 e=elem[front];//先取出隊(duì)頭指針?biāo)傅年?duì)頭元素，front=(front+1)%MAX_SIZE;//然后將隊(duì)頭指針增length--;}returne;}第5章串一、選擇題12345678910BECACAD,FCCB二、判斷題123√√√三、填空題1.由空格組成的串，空格的個(gè)數(shù)2.字符3.任意連續(xù)字符組成的子序列4.45.O(n+m)6.011223127.010104218.串的模式匹配，模式串9.這種線(xiàn)性表的數(shù)據(jù)元素類(lèi)型總是字符型，定長(zhǎng)順序存儲(chǔ)和壓縮存儲(chǔ)方式10.長(zhǎng)度相等，并且這兩個(gè)串對(duì)應(yīng)位置上的字符全部相同一、選擇題1.設(shè)有一個(gè)10階的對(duì)稱(chēng)矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)其下三角矩陣中的元素，a11為第一元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間，則a85的地址為(B)。A.13B.33C.18D.40解析：本書(shū)正文公式(6-3)中aij的下標(biāo)(i,j)從(0,0)開(kāi)始，而本題中的aij的下標(biāo)(i,j)從(1,1)開(kāi)始，故應(yīng)用書(shū)中(6-3)公式2.有一個(gè)二維數(shù)組A[1:6，0:7]，每個(gè)數(shù)組元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址，那么這個(gè)數(shù)組的體積是（①）個(gè)字節(jié)。假設(shè)存儲(chǔ)數(shù)組元素A[1，0]的第一個(gè)字節(jié)的地址是0，則存儲(chǔ)數(shù)組A的最后一個(gè)元素的第一個(gè)字節(jié)的地址是（②）。若按行存儲(chǔ)，則A[2，4]的第一個(gè)字節(jié)的地址是（③）。若按列存儲(chǔ)，則A[5，7]的第一個(gè)字節(jié)的地址是（④）。就一般情況而言，當(dāng)（⑤）時(shí)，按行存儲(chǔ)的A[I，J]地址與按列存儲(chǔ)的A[J，I]地址相等。供選擇的答案：①-④：A．12B.66C.72D.96E.114F.120G.156H.234I.276J.282K.283L.288⑤：A．行與列的上界相同B.行與列的下界相同C.行與列的上、下界都相同D.行的元素個(gè)數(shù)與列的元素個(gè)數(shù)相同答案：①L②J③C④I⑤C解析：本題主要考查按行及按列存儲(chǔ)時(shí)，數(shù)組下標(biāo)和數(shù)組元素個(gè)數(shù)的關(guān)系，由數(shù)組元素個(gè)數(shù)就可以推算出某個(gè)數(shù)組元素在存儲(chǔ)時(shí)的位置。通過(guò)分析題意可知：數(shù)組元素A[i,j]第一個(gè)字節(jié)的地址Ad=(n-1)×6，其中n為數(shù)組元素的位置，即當(dāng)前數(shù)組元素在一維的存儲(chǔ)空間上處于第n個(gè)位置。由此可得：①6×8×6=288②(288×1)×6=282③((8+5)-1)×6=72④(((6×7)+5)-1)×6=2763.設(shè)有數(shù)組A[i,j]，數(shù)組的每個(gè)元素長(zhǎng)度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內(nèi)存首地址BA開(kāi)始順序存放，當(dāng)用以列為主存放時(shí)，元素A[5，8]的存儲(chǔ)首地址為(B)。A.BA+141B.BA+180C.BA+222D.BA+225解析：BA+(((8×7)+5)-1)×3=BA+1804.假設(shè)以行序?yàn)橹餍虼鎯?chǔ)二維數(shù)組A=array[1..100，1..100]，設(shè)每個(gè)數(shù)據(jù)元素占2個(gè)存儲(chǔ)單元，基地址為10，則LOC[5，5]=（B）。A.808B.818C.1010D.1020解析：10+(((100×4)+5)-1)×2=8185.數(shù)組A[0..5,0..6]的每個(gè)元素占五個(gè)字節(jié)，將其按列優(yōu)先次序存儲(chǔ)在起始地址為1000的內(nèi)存單元中，則元素A[5，5]的地址是(A)。A.1175B.1180C.1205D.1210解析：1000+(((6×5)+6)-1)×5=11756.將一個(gè)A[1..100，1..100]的三對(duì)角矩陣，按行優(yōu)先存入一維數(shù)組B[1‥298]中，A中元素A6665（即該元素下標(biāo)i=66，j=65），在B數(shù)組中的位置K為（B）。A.198B.195C.197D.196解析：64×3+2+1=1957.有一個(gè)100*90的稀疏矩陣，非0元素有10個(gè)，設(shè)每個(gè)整型數(shù)占2字節(jié)，則用三元組表示該矩陣時(shí)，所需的字節(jié)數(shù)是（B）。A.60B.66C.18000D.33解析：在用三元組表示稀疏矩陣的時(shí)候除了非零元素占用空間外，還需要另外的一個(gè)三元組存儲(chǔ)矩陣的行數(shù)、列數(shù)、非零元個(gè)數(shù)，故答案為10×2×3+2×3=66.8.數(shù)組A[0..4,-1..-3,5..7]中含有元素的個(gè)數(shù)（B）。A.55B.45C.36D.16解析：5×3×3=459.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)目的是（C）。A．便于進(jìn)行矩陣運(yùn)算B．便于輸入和輸出C．節(jié)省存儲(chǔ)空間D．降低運(yùn)算的時(shí)間復(fù)雜度10.已知廣義表L=（（x,y,z），a，（u，t，w）），從L表中取出原子項(xiàng)t的運(yùn)算是（D）。A.GetHead（GetTail（GetTail（L）））B.GetTail（GetHead（GetHead（GetTail（L））））C.GetHead（GetTail（GetHead（GetTail（L））））D.GetHead（GetTail(GetHead（GetTail（GetTail（L）））））解析：這里要注意的是，GetHead得到的是一個(gè)原子，而GetTail得到的卻是原子外組成的新的廣義表，不管是只有一個(gè)元素，但也是一個(gè)廣義表，而不是直接的元素。GetTail(L)得到的是(a,(u,t,w))GetTail(GetTail(L))t得到的就是((u,t,w))GetHead(GetTail(GetTail(L)))得到的就是(u,t,w)GetTail(GetHead(GetTail(GetTail(L))))得到的就是(t,w)GetHead(GetTail(GetHead(GetTail(GetTail(L)))))得到的就是t11.已知廣義表LS＝((a,b,c),(d,e,f)),運(yùn)用GetHead和GetTail函數(shù)取出LS中原子e的運(yùn)算是(C)。A.GetHead(GetTail(LS))B.GetTail(GetHead(LS))C.GetHead(GetTail(GetHead(GetTail(LS)))D.GetHead(GetTail(GetTail(GetHead(LS))))12.廣義表A=(a,b,(c,d),(e,(f,g))),則下面式子的值為（D）。GetHead(GetTail(GetHead(GetTail(GetTail(A)))))A.(g)B.(d)C.cD.d13.已知廣義表:A=(a,b),B=(A,A),C=(a,(b,A),B),求下列運(yùn)算的結(jié)果:GetTail(GetHead(GetTail(C)))=(F)。A.（a）B.AC.aD.(b)E.bF.(A)14.廣義表運(yùn)算式Tail(((a,b),(c,d)))的操作結(jié)果是（C）。A.(c,d)B.c,dC.((c,d))D.d15.設(shè)廣義表L=（（a,b,c）），則L的長(zhǎng)度和深度分別為（C）。A.1和1B.1和3C.1和2D.2和316.下面說(shuō)法不正確的是(A)。A.廣義表的表頭總是一個(gè)廣義表B.廣義表的表尾總是一個(gè)廣義表C.廣義表難以用順序存儲(chǔ)結(jié)構(gòu)D.廣義表可以是一個(gè)多層次的結(jié)構(gòu)二、簡(jiǎn)答題1.設(shè)矩陣（1）若將A視為對(duì)稱(chēng)矩陣，畫(huà)出對(duì)其壓縮存儲(chǔ)的存儲(chǔ)表，并討論如何存取A中元素aij(0<=i,j<4)；（2）若將A視為稀疏矩陣，畫(huà)出A的十字鏈表結(jié)構(gòu)。答：（1）將對(duì)稱(chēng)矩陣按“行優(yōu)先順序”將其下三角中的元素存入一維數(shù)組中，結(jié)果如下：存取A中元素aij(0<=i,j<4)時(shí)，aij=a[k]，k值按照下列公式存取：（2）A的十字鏈表結(jié)構(gòu)：2.畫(huà)出下列廣義表的兩種存儲(chǔ)結(jié)構(gòu)圖((),A,(B,(C,D)),(E,F))。答：廣義表的第一種存儲(chǔ)結(jié)構(gòu)稱(chēng)為頭尾鏈表結(jié)構(gòu)，其理論基礎(chǔ)是，非空廣義表可唯一分解成表頭和表尾兩部分，而由表頭和表尾可唯一構(gòu)成一個(gè)廣義表。這種存儲(chǔ)結(jié)構(gòu)中，原子和表采用不同的結(jié)點(diǎn)結(jié)構(gòu)（“異構(gòu)”，即結(jié)點(diǎn)域個(gè)數(shù)不同）。原子結(jié)點(diǎn)兩個(gè)域：標(biāo)志域tag=0表示原子結(jié)點(diǎn)，域atom表示原子的值；子表結(jié)點(diǎn)三個(gè)域：tag=1表示子表，hp和tp分別是指向表頭和表尾的指針。在畫(huà)存儲(chǔ)結(jié)構(gòu)時(shí)，對(duì)非空廣義表不斷進(jìn)行表頭和表尾的分解，表頭可以是原子，也可以是子表，而表尾一定是表（包括空表）。第一種存儲(chǔ)結(jié)構(gòu)圖如下：廣義表的第二種存儲(chǔ)結(jié)構(gòu)稱(chēng)為擴(kuò)展線(xiàn)性鏈表結(jié)構(gòu)，其理論基礎(chǔ)是，非空廣義表最高層元素間具有邏輯關(guān)系：第一個(gè)元素?zé)o前驅(qū)有后繼，最后一個(gè)元素?zé)o后繼有前驅(qū)，其余元素有唯一前驅(qū)和唯一后繼。有人將這種結(jié)構(gòu)看作擴(kuò)充線(xiàn)性結(jié)構(gòu)。這種存儲(chǔ)結(jié)構(gòu)中，原子和表均采用三個(gè)域的結(jié)點(diǎn)結(jié)構(gòu)（“同構(gòu)”）。結(jié)點(diǎn)中都有一個(gè)指針域指向后繼結(jié)點(diǎn)。原子結(jié)點(diǎn)中還包括標(biāo)志域tag=0和原子值域atom；子表結(jié)點(diǎn)還包括標(biāo)志域tag=1和指向子表的指針hp。在畫(huà)存儲(chǔ)結(jié)構(gòu)時(shí)，從左往右一個(gè)元素一個(gè)元素的畫(huà)，直至最后一個(gè)元素。第二種存儲(chǔ)結(jié)構(gòu)圖如下：3.已知廣義表A=（（（a）），（b），c，（a），（（（d，e））））（1）畫(huà)出其一種存貯結(jié)構(gòu)圖；（2）寫(xiě)出表的長(zhǎng)度與深度；（3）用求頭部，尾部的方式求出e。答：（1）頭尾鏈表結(jié)構(gòu)擴(kuò)展線(xiàn)性鏈表結(jié)構(gòu)（2）表的長(zhǎng)度為5，深度為4（3）A=（（（a）），（b），c，（a），（（（d，e））））tail（A）=（（b），c，（a），（（（d，e））））tail（（tail（A）））=（c，（a），（（（d，e））））tail（tail（（tail（A））））=（（a），（（（d，e））））tail（tail（tail（（tail（A）））））=（（（（d，e））））head（tail（tail（tail（（tail（A））））））=（（（d，e）））head（head（tail（tail（tail（（tail（A）））））））=（（d，e））head（head（head（tail（tail（tail（（tail（A））））））））=（d，e）tail（head（head（head（tail（tail（tail（（tail（A）））））））））=（e）head（tail（head（head（head（tail（tail（tail（（tail（A））））））））））=e第六章樹(shù)和二叉樹(shù)1、畫(huà)出具有3個(gè)結(jié)點(diǎn)的樹(shù)和3個(gè)結(jié)點(diǎn)的二叉樹(shù)的所有不同形態(tài)？參考答案：具有3個(gè)結(jié)點(diǎn)的樹(shù)具有3個(gè)結(jié)點(diǎn)的二叉樹(shù) 2、已知一棵樹(shù)有N1個(gè)度為1的結(jié)點(diǎn)，N2個(gè)度為2的結(jié)點(diǎn)，N3個(gè)度為3的結(jié)點(diǎn)……NK個(gè)度為K的結(jié)點(diǎn)，問(wèn)樹(shù)中有多少個(gè)葉子結(jié)點(diǎn)？參考答案：設(shè)樹(shù)中結(jié)點(diǎn)總數(shù)為n,則n=n0+n1+……+nk樹(shù)中分支數(shù)目為B,則B=n1+2n2+3n3+……+knk因?yàn)槌Y(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)均對(duì)應(yīng)一個(gè)進(jìn)入它的分支，所以有n=B+1即n0+n1+……+nk=n1+2n2+3n3+……+knk+1由上式可得葉子結(jié)點(diǎn)數(shù)為：n0=n2+2n3+……+(k-1)nk+13、假設(shè)用于通訊的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為0.07,0.19,0.02,0.06,0.32,0.21,0.10,試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。參考答案：構(gòu)造哈夫曼樹(shù)如下：

哈夫曼編碼為：I1：11111I5：1100I2：11110I6：10I3：1110I7：01I4：1101I8：004、樹(shù)的存儲(chǔ)方法主要有哪些？任你畫(huà)一個(gè)樹(shù)舉例說(shuō)明具體存儲(chǔ)結(jié)構(gòu)。參考答案：(1)雙親表示法——以一組連續(xù)空間存儲(chǔ)樹(shù)的結(jié)點(diǎn)，在每個(gè)結(jié)點(diǎn)中設(shè)一個(gè)指示器指示雙親結(jié)點(diǎn)的位置。(2)孩子表示法——每個(gè)結(jié)點(diǎn)的孩子以單鏈表的形式存儲(chǔ)，n個(gè)結(jié)點(diǎn)有n個(gè)孩子鏈表，n個(gè)頭指針又組成一個(gè)線(xiàn)性表，并以順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。(3)孩子兄弟表示法——以二叉鏈表作為樹(shù)的存儲(chǔ)結(jié)構(gòu)，鏈表中的結(jié)點(diǎn)的兩個(gè)指針?lè)謩e指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。雙親表示法：

孩子表示法：

孩子兄弟表示法：5、已知二叉樹(shù)有50個(gè)葉子結(jié)點(diǎn)，則該二叉樹(shù)的總結(jié)點(diǎn)數(shù)至少應(yīng)有多少個(gè)？參考答案：n0表示葉子結(jié)點(diǎn)數(shù)，n2表示度為2的結(jié)點(diǎn)數(shù)，則n0=n2+1所以n2=n0–1=49，當(dāng)二叉樹(shù)中沒(méi)有度為1的結(jié)點(diǎn)時(shí)，總結(jié)點(diǎn)數(shù)n=n0+n2=996、給出滿(mǎn)足下列條件的所有二叉樹(shù)：①

前序和后序相同②

中序和后序相同③

前序和后序相同參考答案： (1)前序與中序相同：空樹(shù)或缺左子樹(shù)的單支樹(shù)； (2)中序與后序相同：空樹(shù)或缺右子樹(shù)的單支樹(shù)；(3)前序與后序相同：空樹(shù)或只有根結(jié)點(diǎn)的二叉樹(shù)。7、分別寫(xiě)函數(shù)完成：在先序線(xiàn)索二叉樹(shù)T中，查找給定結(jié)點(diǎn)*p在先序序列中的后繼。在后序線(xiàn)索二叉樹(shù)T中，查找給定結(jié)點(diǎn)*p在后序序列中的前驅(qū)。參考答案：(1)找結(jié)點(diǎn)的先序后繼結(jié)點(diǎn)BiTNode*PreSucc(BiTNode*p)/*在先序線(xiàn)索二叉樹(shù)中查找p的先序后繼結(jié)點(diǎn)，并用succ指針?lè)祷亟Y(jié)果*/{if(p->Ltag==0)succ=p->LChild;elsesucc=p->RChild;return(succ);}(2)找結(jié)點(diǎn)的后序前驅(qū)結(jié)點(diǎn)BiTNode*SuccPre(BiTNode*p)/*在后序線(xiàn)索二叉樹(shù)中查找p的后序前驅(qū)結(jié)點(diǎn)，并用pre指針?lè)祷亟Y(jié)果*/{if(p->Ltag==1)pre=p->LChild;elsepre=p->RChild;return(pre);}8、分別寫(xiě)出算法，實(shí)現(xiàn)在中序線(xiàn)索二叉樹(shù)中查找給定結(jié)點(diǎn)*p在中序序列中的前驅(qū)與后繼。參考答案：（1）找結(jié)點(diǎn)的中序前驅(qū)結(jié)點(diǎn)BiTNode*InPre(BiTNode*p)/*在中序線(xiàn)索二叉樹(shù)中查找p的中序前驅(qū)結(jié)點(diǎn)，并用pre指針?lè)祷亟Y(jié)果*/{if(p->Ltag==1)pre=p->LChild;/*直接利用線(xiàn)索*/else{/*在p的左子樹(shù)中查找“最右下端”結(jié)點(diǎn)*/for(q=p->LChild;q->Rtag==0;q=q->RChild);pre=q;}return(pre);}（2）找結(jié)點(diǎn)的中序后繼結(jié)點(diǎn)BiTNode*InSucc(BiTNode*p)/*在中序線(xiàn)索二叉樹(shù)中查找p的中序后繼結(jié)點(diǎn)，并用succ指針?lè)祷亟Y(jié)果*/{if(p->Rtag==1)succ=p->RChild;/*直接利用線(xiàn)索*/else{/*在p的右子樹(shù)中查找“最左下端”結(jié)點(diǎn)*/for(q=p->RChild;q->Ltag==0;q=q->LChild);succ=q;}return(succ);}9、已知二叉樹(shù)按照二叉鏈表方式存儲(chǔ)，利用棧的基本操作寫(xiě)出先序遍歷非遞歸形式的算法。參考答案：VoidPreOrder(BiTreeroot)/*先序遍歷二叉樹(shù)的非遞歸算法*/{InitStack(&S);p=root;while(p!=NULL||!IsEmpty(S)){if(p!=NULL){Visit(p->data);push(&S,p);p=p->Lchild;}else{Pop(&S,&p);p=p->RChild;}}}10、二叉樹(shù)按照二叉鏈表方式存儲(chǔ)，編寫(xiě)算法，將二叉樹(shù)左右子樹(shù)進(jìn)行交換。

參考答案： Voidexchange(BiTreeroot){p=root; if(p->LChild!=NULL||p->RChild!=NULL){ temp=p->LChild;p->LChild=p->RChild; p->RChild=temp; exchange(p->LChild); exchange(p->RChild); } }

第8章圖一、選擇題1.A2.B3.A4.B5.D6(1)B6(2)D7(1)B7(2)C8.A9.A10(1)C10(2)BDE11.C12.AB13.B14.A15.C16.B二、判斷題12345678910√××××√××××11121314151617181920√××××××√××三、.應(yīng)用題1．G1最多n(n-1)/2條邊，最少n-1條邊2．G2最多n(n-1)條邊，最少n條邊3.G3最多n(n-1)條邊，最少n-1條邊(注：弱連通有向圖指把有向圖看作無(wú)向圖時(shí)，仍是連通的)4．n-1，n5．證明：具有n個(gè)頂點(diǎn)n-1條邊的無(wú)向連通圖是自由樹(shù)，即沒(méi)有確定根結(jié)點(diǎn)的樹(shù)，每個(gè)結(jié)點(diǎn)均可當(dāng)根。若邊數(shù)多于n-1條，因一條邊要連接兩個(gè)結(jié)點(diǎn)，則必因加上這一條邊而使兩個(gè)結(jié)點(diǎn)多了一條通路，即形成回路。形成回路的連通圖不再是樹(shù)（在圖論中樹(shù)定義為無(wú)回路的連通圖）。6．證明：該有向圖頂點(diǎn)編號(hào)的規(guī)律是讓弧尾頂點(diǎn)的編號(hào)大于弧頭頂點(diǎn)的編號(hào)。由于不允許從某頂點(diǎn)發(fā)出并回到自身頂點(diǎn)的弧，所以鄰接矩陣主對(duì)角元素均為0。先證明該命題的充分條件。由于弧尾頂點(diǎn)的編號(hào)均大于弧頭頂點(diǎn)的編號(hào)，在鄰接矩陣中，非零元素（A[i][j]=1）自然是落到下三角矩陣中；命題的必要條件是要使上三角為0，則不允許出現(xiàn)弧頭頂點(diǎn)編號(hào)大于弧尾頂點(diǎn)編號(hào)的弧，否則，就必然存在環(huán)路。（對(duì)該類(lèi)有向無(wú)環(huán)圖頂點(diǎn)編號(hào)，應(yīng)按頂點(diǎn)出度順序編號(hào)。）7．(1)n(n-1)，n(2)106，不一定是稀疏矩陣（稀疏矩陣的定義是非零個(gè)數(shù)遠(yuǎn)小于該矩陣元素個(gè)數(shù)，且分布無(wú)規(guī)律）(3)使用深度優(yōu)先遍歷，按退出DFS過(guò)程的先后順序記錄下的頂點(diǎn)是逆向拓?fù)溆行蛐蛄?。若在?zhí)行DFS(v)未退出前，出現(xiàn)頂點(diǎn)u到v的回邊，則說(shuō)明存在包含頂點(diǎn)v和頂點(diǎn)u的環(huán)。8.K2，K1，K3，K4，K5，K6，K8，K9，K7規(guī)則：開(kāi)始結(jié)點(diǎn)為K1或K2，之后，若遇多個(gè)入度為0的頂點(diǎn)，按頂點(diǎn)編號(hào)順序選擇。（4）(1)2231945876（2）開(kāi)始結(jié)點(diǎn)：（入度為0）K1，K2，終端結(jié)點(diǎn)（出度為0）K6，K7。（3）拓?fù)湫蛄蠯1，K2，K3，K4，K5，K6，K8，K9，K7(4)略9.．圖G的具體存儲(chǔ)結(jié)構(gòu)略。鄰接矩陣表示法，有n個(gè)頂點(diǎn)的圖占用n2個(gè)元素的存儲(chǔ)單元，與邊的個(gè)數(shù)無(wú)關(guān)，當(dāng)邊數(shù)較少時(shí)，存儲(chǔ)效率較低。這種結(jié)構(gòu)下，對(duì)查找結(jié)點(diǎn)的度、第一鄰接點(diǎn)和下一鄰接點(diǎn)、兩結(jié)點(diǎn)間是否有邊的操作有利，對(duì)插入和刪除頂點(diǎn)的操作不利。鄰接表表示法是頂點(diǎn)的向量結(jié)構(gòu)與頂點(diǎn)的鄰接點(diǎn)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)相結(jié)合的結(jié)構(gòu)，頂點(diǎn)的向量結(jié)構(gòu)含有n（n≥0）個(gè)頂點(diǎn)和指向各頂點(diǎn)第一鄰接點(diǎn)的指針，其頂點(diǎn)的鄰接點(diǎn)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是根據(jù)頂點(diǎn)的鄰接點(diǎn)的實(shí)際設(shè)計(jì)的。這種結(jié)構(gòu)適合查找頂點(diǎn)及鄰接點(diǎn)的信息，查頂點(diǎn)的度，增加或刪除頂點(diǎn)和邊（弧）也很方便，但因指針多占用了存儲(chǔ)空間，另外，某兩頂點(diǎn)間是否有邊（?。┮膊蝗玎徑泳仃嚹敲辞宄?duì)有向圖的鄰接表，查頂點(diǎn)出度容易，而查頂點(diǎn)入度卻困難，要遍歷整個(gè)鄰接表。要想查入度象查出度那樣容易，就要建立逆鄰接表。無(wú)向圖鄰接表中邊結(jié)點(diǎn)是邊數(shù)的二倍也增加了存儲(chǔ)量。十字鏈表是有向圖的另一種存儲(chǔ)結(jié)構(gòu)，將鄰接表和逆鄰接表結(jié)合到一起，弧結(jié)點(diǎn)也增加了信息（至少弧尾，弧頭頂點(diǎn)在向量中的下標(biāo)及從弧尾頂點(diǎn)發(fā)出及再入到弧頭頂點(diǎn)的下一條弧的四個(gè)信息）。查詢(xún)頂點(diǎn)的出度、入度、鄰接點(diǎn)等信息非常方便。鄰接多重表是無(wú)向圖的另一種存儲(chǔ)結(jié)構(gòu)，邊結(jié)點(diǎn)至少包括5個(gè)域：連接邊的兩個(gè)頂點(diǎn)在頂點(diǎn)向量中的下標(biāo)，指向與該邊相連接的兩頂點(diǎn)的下一條邊的指針，以及該邊的標(biāo)記信息（如該邊是否被訪(fǎng)問(wèn)）。邊結(jié)點(diǎn)的個(gè)數(shù)與邊的個(gè)數(shù)相同，這是鄰接多重表比鄰接表優(yōu)越之處。10.無(wú)向圖G的鄰接多表，略。已知頂點(diǎn)i，找與i相鄰的頂點(diǎn)j的規(guī)則如下：在頂點(diǎn)向量中，找到頂點(diǎn)i，順其指針找到第一個(gè)邊結(jié)點(diǎn)（若其指針為空，則頂點(diǎn)i無(wú)鄰接點(diǎn)）。在邊結(jié)點(diǎn)中，取出兩頂點(diǎn)信息，若其中有j，則找到頂點(diǎn)j；否則，沿從i發(fā)出的另一條邊的指針（ilink）找i的下一鄰接點(diǎn)。在這種查找過(guò)程中，若邊結(jié)點(diǎn)中有j，則查找成功；若最后ilink為空，，則頂點(diǎn)i無(wú)鄰接點(diǎn)j。12．按各頂點(diǎn)的出度進(jìn)行排序。n個(gè)頂點(diǎn)的有向圖，其頂點(diǎn)最大出度是n-1，最小出度為0。這樣排序后，出度最大的頂點(diǎn)編號(hào)為1，出度最小的頂點(diǎn)編號(hào)為n。之后，進(jìn)行調(diào)整，即若存在弧<i，j>，而頂點(diǎn)j的出度大于頂點(diǎn)i的出度，則將把j編號(hào)在頂點(diǎn)i的編號(hào)之前。11．略。12.鄰接表表示略。深度優(yōu)先遍歷序列：12439875610廣度優(yōu)先遍歷序列：1238491075613.（1）鄰接矩陣存儲(chǔ)法占用空間多。因?yàn)猷徑泳仃囆枰娣?0*10個(gè)頂點(diǎn)編號(hào)，共200字節(jié)，而鄰接表需要10+10個(gè)指針，指針占用80字節(jié)，存放頂點(diǎn)編號(hào)需要2*20=40字節(jié)，共120字節(jié)。（2）略。14.（1）略（2）關(guān)節(jié)點(diǎn)：1，2，3，7，8ABEFABEFCDBBNPLTM（2）ABEFCD16.（1）BNPLTMB109828121124N109585510832P825839792L815539589T211089795113M124329289113(2)略BNPBNPLTM321BNPLTM3BNBNPLTM3215532BNPLTM32132BBNPLTM3215532328117.略。一、選擇題1.若查找每個(gè)記錄的概率均等，則在具有n個(gè)記錄的連續(xù)順序文件中采用順序查找法查找一個(gè)記錄，其平均查找長(zhǎng)度ASL為(C)。A．(n-1)/2B.n/2C.(n+1)/2D.n2.順序查找法適用于查找順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)的線(xiàn)性表，平均比較次數(shù)為（D）,二分法查找只適用于查找順序存儲(chǔ)的有序表，平均比較次數(shù)為（C）。在此假定N為線(xiàn)性表中結(jié)點(diǎn)數(shù)，且每次查找都是成功的。A.N+1B.2log2NC.log2ND.N/2E.Nlog2NF.N2解析：區(qū)別本大題第5小題，本題多了一句“每次查找都是成功的”，可知對(duì)于N個(gè)結(jié)點(diǎn)的鏈表來(lái)說(shuō)最多只需要做N-1次比較。故將公式中的n替換成N-1，可得答案D。同理，將公式1中的n替換成N-1，答案C比較符合要求。3.下面關(guān)于二分查找的敘述正確的是(D)A.表必須有序，表可以順序方式存儲(chǔ)，也可以鏈表方式存儲(chǔ)B.表必須有序且表中數(shù)據(jù)必須是整型，實(shí)型或字符型C.表必須有序，而且只能從小到大排列D.表必須有序，且表只能以順序方式存儲(chǔ)4.具有12個(gè)關(guān)鍵字的有序表，折半查找的平均查找長(zhǎng)度（A）A.3.1B.4C.2.5D.5解析：5.要進(jìn)行順序查找，則線(xiàn)性表（（1）C）；要進(jìn)行折半查詢(xún)，則線(xiàn)性表（（2）D）；若表中元素個(gè)數(shù)為n,則順序查找的平均比較次數(shù)為（（3）G）；折半查找的平均比較次數(shù)為（（4）H）。（1）（2）：A.必須以順序方式存儲(chǔ)；B.必須以鏈?zhǔn)椒绞酱鎯?chǔ)；C.既可以以順序方式存儲(chǔ)，也可以鏈?zhǔn)椒绞酱鎯?chǔ)；D.必須以順序方式存儲(chǔ)，且數(shù)據(jù)已按遞增或遞減順序排好；E.必須以鏈?zhǔn)椒绞酱鎯?chǔ)，且數(shù)據(jù)已按遞增或遞減的次序排好。（3）（4）：A.nB.n/2C.n*nD.n*n/2E.log2nF.nlog2nG.(n+1)/2H.log2(n+1)答案：（1）C；（2）D；（3）G；（4）H解析：

（3）順序查找的平均比較次數(shù)為，（4）折半查找的平均比較次數(shù)為（n>50時(shí)），故答案H比較符合要求。6．分別以下列序列構(gòu)造二叉排序樹(shù)，與用其它三個(gè)序列所構(gòu)造的結(jié)果不同的是(C)A．（100，80，90，60，120，110，130）B.（100，120，110，130，80，60，90）C.（100，60，80，90，120，110，130）D.(100，80，60，90，120，130，110)7.在平衡二叉樹(shù)中插入一個(gè)結(jié)點(diǎn)后造成了不平衡，設(shè)最低的不平衡結(jié)點(diǎn)為A,并已知A的左孩子的平衡因子為0右孩子的平衡因子為1,則應(yīng)作(C)型調(diào)整以使其平衡。A.LLB.LRC.RLD.RR8．下列關(guān)于m階B-樹(shù)的說(shuō)法錯(cuò)誤的是(D)A.根結(jié)點(diǎn)至多有m棵子樹(shù)B.所有葉子都在同一層次上C.非葉結(jié)點(diǎn)至少有m/2(m為偶數(shù))或m/2+1（m為奇數(shù)）棵子樹(shù)D.根結(jié)點(diǎn)中的數(shù)據(jù)是有序的9.下面關(guān)于m階B樹(shù)說(shuō)法正確的是(D)①每個(gè)結(jié)點(diǎn)至少有兩棵非空子樹(shù)；②樹(shù)中每個(gè)結(jié)點(diǎn)至多有m-1個(gè)關(guān)鍵字;③所有葉子在同一層上;④當(dāng)插入一個(gè)數(shù)據(jù)項(xiàng)引起B(yǎng)樹(shù)結(jié)點(diǎn)分裂后，樹(shù)長(zhǎng)高一層。A．①②③B.②③C.②③④D.③10.設(shè)有一組記錄的關(guān)鍵字為{19，14，23，1，68，20，84，27，55，11，10，79}，用鏈地址法構(gòu)造散列表，散列函數(shù)為H（key）=keyMOD13,散列地址為1的鏈中有（D）個(gè)記錄。A．1B.2C.3D.411.下面關(guān)于哈希(Hash，雜湊)查找的說(shuō)法正確的是(C)A．哈希函數(shù)構(gòu)造的越復(fù)雜越好，因?yàn)檫@樣隨機(jī)性好，沖突小B．除留余數(shù)法是所有哈希函數(shù)中最好的C．不存在特別好與壞的哈希函數(shù)，要視情況而定D．若需在哈希表中刪去一個(gè)元素，不管用何種方法解決沖突都只要簡(jiǎn)單的將該元素刪去即可12.若采用鏈地址法構(gòu)造散列表，散列函數(shù)為H（key）=keyMOD17，則需(（1）A)個(gè)鏈表。這些鏈的鏈?zhǔn)字羔槝?gòu)成一個(gè)指針數(shù)組，數(shù)組的下標(biāo)范圍為(（2）C)（1）A．17B.13C.16D.任意（2）A．0至17B.1至17C.0至16D.1至1613.關(guān)于雜湊查找說(shuō)法不正確的有幾個(gè)(B)（1）采用鏈地址法解決沖突時(shí)，查找一個(gè)元素的時(shí)間是相同的（2）采用鏈地址法解決沖突時(shí)，若插入規(guī)定總是在鏈?zhǔn)祝瑒t插入任一個(gè)元素的時(shí)間是相同的（3）用鏈地址法解決沖突易引起聚集現(xiàn)象（4）再哈希法不易產(chǎn)生聚集A.1B.2C.3D.414.設(shè)哈希表長(zhǎng)為14，哈希函數(shù)是H(key)=key%11,表中已有數(shù)據(jù)的關(guān)鍵字為15，38，61，84共四個(gè)，現(xiàn)要將關(guān)鍵字為49的結(jié)點(diǎn)加到表中，用二次探測(cè)再散列法解決沖突，則放入的位置是(D)A．8B．3C．5D．915.將10個(gè)元素散列到100000個(gè)單元的哈希表中，則（C）產(chǎn)生沖突。A.一定會(huì)B.一定不會(huì)C.仍可能會(huì)二、簡(jiǎn)答題1.設(shè)有一組關(guān)鍵字{9,01,23,14,55,20,84,27}，采用哈希函數(shù)：H（key）=keymod7，表長(zhǎng)為10，用開(kāi)放地址法的二次探測(cè)再散列方法Hi=(H(key)+di)mod10(di=12,22,32,…,)解決沖突。要求：對(duì)該關(guān)鍵字序列構(gòu)造哈希表，并計(jì)算查找成功的平均查找長(zhǎng)度。答：散列地址0123456789關(guān)鍵字140192384275520比較次數(shù)11123412平均查找長(zhǎng)度：ASL=（1+1+1+2+3+4+1+2）/8=15/8以關(guān)鍵字27為例：H（27）=27%7=6（沖突）H1=（6+1）%10=7（沖突）H2=（6+22）%10=0（沖突）H3=（6+33）%10=5所以比較了4次。2.對(duì)下面的關(guān)鍵字集{30,15,21,40,25,26,36,37}若查找表的裝填因子為0.8，采用線(xiàn)性探測(cè)再散列方法解決沖突，做：（1）設(shè)計(jì)哈希函數(shù)；（2）畫(huà)出哈希表；（3）計(jì)算查找成功和查找失敗的平均查找長(zhǎng)度；（4）寫(xiě)出將哈希表中某個(gè)數(shù)據(jù)元素刪除的算法。答：由于裝填因子為0.8，關(guān)鍵字有8個(gè)，所以表長(zhǎng)為8/0.8=10。（1）用除留余數(shù)法，哈希函數(shù)為H（key）=key%7（2）散列地址0123456789關(guān)鍵字2115303625402637比較次數(shù)11131126（3）計(jì)算查找失敗時(shí)的平均查找長(zhǎng)度，必須計(jì)算不在表中的關(guān)鍵字，當(dāng)其哈希地址為i（0≤i≤m-1）時(shí)的查找次數(shù)。本例中m=10。故查找失敗時(shí)的平均查找長(zhǎng)度為：ASLunsucc=（9+8+7+6+5+4+3+2+1+1）/10=4.6ASLsucc=（1+1+1+3+1+1+2+6）/8=16/8=2說(shuō)明：查找成功代表找到“待查關(guān)鍵字”所比較的次數(shù)。第n個(gè)位置不成功時(shí)的比較次數(shù)為：第n個(gè)位置到第1個(gè)沒(méi)有數(shù)據(jù)位置的距離。至少要查詢(xún)多少次才能確認(rèn)沒(méi)有這個(gè)值。查詢(xún)hash(x)=0,至少要查詢(xún)9次遇到表值為空的時(shí)候，才能確認(rèn)查詢(xún)失敗。查詢(xún)hash(x)=1,至少要查詢(xún)8次遇到表值為空的時(shí)候，才能確認(rèn)查詢(xún)失敗。查詢(xún)hash(x)=2,至少要查詢(xún)7次遇到表值為空的時(shí)候，才能確認(rèn)查詢(xún)失敗。查詢(xún)hash(x)=3,至少要查詢(xún)6次遇到表值為空的時(shí)候，才能確認(rèn)查詢(xún)失敗。查詢(xún)hash(x)=4,至少要查詢(xún)5次遇到表值為空的時(shí)候，才能確認(rèn)查詢(xún)失敗。查詢(xún)hash(x)=5,至少要查詢(xún)4次遇到表值為空的時(shí)候，才能確認(rèn)查詢(xún)失敗。查詢(xún)hash(x)=6,至少要查詢(xún)3次遇到表值為空的時(shí)候，才能確認(rèn)查詢(xún)失敗。查詢(xún)hash(x)=7,至少要查詢(xún)2次遇到表值為空的時(shí)候，才能確認(rèn)查詢(xún)失敗。查詢(xún)hash(x)=8,至少要查詢(xún)1次遇到表值為空的時(shí)候，才能確認(rèn)查詢(xún)失敗。查詢(xún)hash(x)=9,至少要查詢(xún)1次遇到表值為空的時(shí)候，才能確認(rèn)查詢(xún)失敗。（4）哈希表中某個(gè)數(shù)據(jù)元素刪除的算法如下：intDelete(inth[n],intk){//從哈希表h[n]中刪除元素k，若刪除成功返回1，否則返回0 i=k%7;//哈希函數(shù)假設(shè)為H(key)=key%7 if(h[i]==NULL)//NULL解釋為通過(guò)哈希函數(shù)計(jì)算得出的地址為空地址 { printf("無(wú)關(guān)鍵字%d\n",k); return0; }if(h[i]==k) { h[i]=NULL;//被刪元素所在的地址置為空地址 return1; }else//采用線(xiàn)性探測(cè)再散列解決沖突{ j=i;for(d=1;d<=n-1;d++){ i=(j+d)%n;//n為表長(zhǎng)，本題中n為10 if(h[i]==NULL) return0;i