數(shù)據(jù)結(jié)構(gòu) 習(xí)題答案

習(xí)題1一、單項(xiàng)選擇題1.數(shù)據(jù)構(gòu)造是指（）。A.數(shù)據(jù)元素的組織形式 B.數(shù)據(jù)類型C.數(shù)據(jù)存儲(chǔ)構(gòu)造D.數(shù)據(jù)定義2.數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表達(dá)時(shí)，物理地址與邏輯地址不相似的，稱之為（）。A.存儲(chǔ)構(gòu)造 B.邏輯構(gòu)造C.鏈?zhǔn)酱鎯?chǔ)構(gòu)造 D.次序存儲(chǔ)構(gòu)造3.樹形構(gòu)造是數(shù)據(jù)元素之間存在一種（）。A.一對(duì)一關(guān)系 B.多對(duì)多關(guān)系C.多對(duì)一關(guān)系 D.一對(duì)多關(guān)系4.設(shè)語(yǔ)句x++的時(shí)間是單位時(shí)間，則如下語(yǔ)句的時(shí)間復(fù)雜度為（）。for(i=1;i<=n;i++)for(j=i;j<=n;j++)x++;A.O(1) B.O() C.O(n) D.O()5.算法分析的目的是（1），算法分析的兩個(gè)重要方面是（2）。（1）A.找出數(shù)據(jù)構(gòu)造的合理性B.研究算法中的輸入和輸出關(guān)系C.分析算法的效率以求改善D.分析算法的易懂性和文檔性（2）A.空間復(fù)雜度和時(shí)間復(fù)雜度B.對(duì)的性和簡(jiǎn)要性C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性6.計(jì)算機(jī)算法指的是（1），它具有輸入，輸出和（2）等五個(gè)特性。（1）A.計(jì)算措施B.排序措施C.處理問題的有限運(yùn)算序列D.調(diào)度措施（2）A.可行性，可移植性和可擴(kuò)充性B.可行性，確定性和有窮性C.確定性，有窮性和穩(wěn)定性D.易讀性，穩(wěn)定性和安全性7.數(shù)據(jù)在計(jì)算機(jī)內(nèi)有鏈?zhǔn)胶痛涡騼煞N存儲(chǔ)方式，在存儲(chǔ)空間使用的靈活性上，鏈?zhǔn)酱鎯?chǔ)比次序存儲(chǔ)要（）。A.低 B.高 C.相似 D.不好說8.數(shù)據(jù)構(gòu)造作為一門獨(dú)立的課程出現(xiàn)是在（）年。A.1946 B.1953 C.19649.數(shù)據(jù)構(gòu)造只是研究數(shù)據(jù)的邏輯構(gòu)造和物理構(gòu)造，這種觀點(diǎn)（）。A.對(duì)的 B.錯(cuò)誤C.前半句對(duì)，后半句錯(cuò) D.前半句錯(cuò)，后半句對(duì)10.計(jì)算機(jī)內(nèi)部數(shù)據(jù)處理的基本單位是（）。A.數(shù)據(jù)B.數(shù)據(jù)元素 C.數(shù)據(jù)項(xiàng) D.數(shù)據(jù)庫(kù)二、填空題1.數(shù)據(jù)構(gòu)造按邏輯構(gòu)造可分為兩大類，分別是______________和_________________。2.數(shù)據(jù)的邏輯構(gòu)造有四種基本形態(tài)，分別是________________、__________________、__________________和__________________。3.線性構(gòu)造反應(yīng)結(jié)點(diǎn)間的邏輯關(guān)系是__________________的，非線性構(gòu)造反應(yīng)結(jié)點(diǎn)間的邏輯關(guān)系是__________________的。4.一種算法的效率可分為__________________效率和__________________效率。5.在樹型構(gòu)造中，樹根結(jié)點(diǎn)沒有__________________結(jié)點(diǎn)，其他每個(gè)結(jié)點(diǎn)的有且只有__________________個(gè)前趨驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有__________________結(jié)點(diǎn)；其他每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以__________________。6.在圖型構(gòu)造中，每個(gè)結(jié)點(diǎn)的前趨結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以__________________。7.線性構(gòu)造中元素之間存在__________________關(guān)系；樹型構(gòu)造中元素之間存在__________________關(guān)系；圖型構(gòu)造中元素之間存在__________________關(guān)系。8.下面程序段的時(shí)間復(fù)雜度是__________________。for(i=0;i<n;i++)for(j=0;j<n;j++)A[i][j]=0;9.下面程序段的時(shí)間復(fù)雜度是__________________。i=s=0;while(s<n){i++;s+=i;}10.下面程序段的時(shí)間復(fù)雜度是__________________。s=0;for(i=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;11.下面程序段的時(shí)間復(fù)雜度是__________________。i=1;while(i<=n)i=i*3;12.衡量算法對(duì)的性的原則一般是____________________________________。13.算法時(shí)間復(fù)雜度的分析一般有兩種措施，即___________和___________的措施，一般我們對(duì)算法求時(shí)間復(fù)雜度時(shí)，采用后一種措施。三、求下列程序段的時(shí)間復(fù)雜度。1.x=0;for(i=1;i<n;i++)for(j=i+1;j<=n;j++)x++;2.x=0;for(i=1;i<n;i++)for(j=1;j<=n-i;j++)x++;3.inti,j,k;for(i=0;i<n;i++)for(j=0;j<=n;j++){c[i][j]=0;for(k=0;k<n;k++) c[i][j]=a[i][k]*b[k][j]}4.i=n-1;while((i>=0)&&A[i]!=k))j--;return(i);5.fact(n){if(n<=1)return(1);elsereturn(n*fact(n-1));}習(xí)題1參照答案一、單項(xiàng)選擇題1.A2.C3.D4.B5.C、A6.C、B7.B8.D9.B10.B二、填空題1.線性構(gòu)造，非線性構(gòu)造2.集合，線性，樹，圖3.一對(duì)一，一對(duì)多或多對(duì)多4.時(shí)間，空間5.前趨，一，后繼，多6.有多種7.一對(duì)一，一對(duì)多，多對(duì)多8.O()9.O()10.O()11.O(logn)12.程序?qū)τ诰脑O(shè)計(jì)的經(jīng)典合法數(shù)據(jù)輸入能得出符合規(guī)定的成果。13.事后記錄，事前估計(jì)三、算法設(shè)計(jì)題 1.O()2.O()3.O(n)4.O(n)5.O(n)

習(xí)題2一、單項(xiàng)選擇題1.線性表是________。A．一種有限序列，可認(rèn)為空 B．一種有限序列，不可認(rèn)為空C．一種無(wú)限序列，可認(rèn)為空 D．一種無(wú)限序列，不可認(rèn)為空2.在一種長(zhǎng)度為n的次序表中刪除第i個(gè)元素(0<=i<=n)時(shí)，需向前移動(dòng)個(gè)元素。A．n-i B．n-i+l C．n-i-1 D．i3.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址________。A．必須是持續(xù)的 B．一定是不持續(xù)的C．部分地址必須是持續(xù)的 D．持續(xù)與否均可以4.從一種具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x的結(jié)點(diǎn)時(shí)，在查找成功的狀況下，需平均比較________個(gè)元素結(jié)點(diǎn)。A．n/2 B．n C．（n+1）/2 D．（n-1）/25.在雙向循環(huán)鏈表中，在p所指的結(jié)點(diǎn)之后插入s指針?biāo)傅慕Y(jié)點(diǎn)，其操作是____。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;6.設(shè)單鏈表中指針p指向結(jié)點(diǎn)m，若要?jiǎng)h除m之后的結(jié)點(diǎn)（若存在），則需修改指針的操作為________。A．p->next=p->next->next; B．p=p->next;C．p=p->next->next; D．p->next=p;7.在一種長(zhǎng)度為n的次序表中向第i個(gè)元素(0<i<n+l)之前插入一種新元素時(shí)，需向后移動(dòng)______個(gè)元素。A．n-i B．n-i+l C．n-i-1 D．i8.在一種單鏈表中，已知q結(jié)點(diǎn)是p結(jié)點(diǎn)的前趨結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則須執(zhí)行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=q9.如下有關(guān)線性表的說法不對(duì)的的是______。

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

A．隨機(jī)存取 B．次序存取 C．索引存取 D．散列存取11.在次序表中，只要懂得_______，就可在相似時(shí)間內(nèi)求出任一結(jié)點(diǎn)的存儲(chǔ)地址。A．基地址 B．結(jié)點(diǎn)大小C．向量大小 D．基地址和結(jié)點(diǎn)大小12.在等概率狀況下，次序表的插入操作要移動(dòng)______結(jié)點(diǎn)。

A．所有 B．二分之一

C．三分之一

D．四分之一13.在______運(yùn)算中，使用次序表比鏈表好。

A．插入

B．刪除

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

D．根據(jù)元素值查找14.在一種具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一種新結(jié)點(diǎn)并保持該表有序的時(shí)間復(fù)雜度是_______。

A．O(1)

B．O(n)

C．O(n2) D．O(log2n)15.設(shè)有一種棧，元素的進(jìn)棧次序?yàn)锳,B,C,D,E,下列是不也許的出棧序列__________。A．A,B,C,D,E B．B,C,D,E,AC．E,A,B,C,D D．E,D,C,B,A16.在一種具有n個(gè)單元的次序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當(dāng)做出棧處理時(shí)，top變化為______。A．top不變 B．top=0 C．top-- D．top++17.向一種棧頂指針為hs的鏈棧中插入一種s結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行______。A．hs->next=s;B．s->next=hs;hs=s;C．s->next=hs->next;hs->next=s;D．s->next=hs;hs=hs->next;18.在具有n個(gè)單元的次序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)滿的條件為________。A．rear％n==front B．（front+l）％n==rearC．rear％n-1==frontD．(rear+l)％n==front19.在具有n個(gè)單元的次序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)空的條件為________。A．rear％n==front B．front+l=rearC．rear==front D．(rear+l)％n=front20.在一種鏈隊(duì)列中，假定front和rear分別為隊(duì)首和隊(duì)尾指針，則刪除一種結(jié)點(diǎn)的操作為________。A．front=front->nextB．rear=rear->nextC．rear=front->nextD．front=rear->next二、填空題1.線性表是一種經(jīng)典的_________構(gòu)造。2.在一種長(zhǎng)度為n的次序表的第i個(gè)元素之前插入一種元素，需要后移____個(gè)元素。3.次序表中邏輯上相鄰的元素的物理位置________。4.要從一種次序表刪除一種元素時(shí)，被刪除元素之后的所有元素均需_______一種位置，移動(dòng)過程是從_______向_______依次移動(dòng)每一種元素。5.在線性表的次序存儲(chǔ)中，元素之間的邏輯關(guān)系是通過_______決定的；在線性表的鏈接存儲(chǔ)中，元素之間的邏輯關(guān)系是通過_______決定的。6.在雙向鏈表中，每個(gè)結(jié)點(diǎn)具有兩個(gè)指針域，一種指向_______結(jié)點(diǎn)，另一種指向_______結(jié)點(diǎn)。7.當(dāng)對(duì)一種線性表常常進(jìn)行存取操作，而很少進(jìn)行插入和刪除操作時(shí)，則采用_______存儲(chǔ)構(gòu)造為宜。相反，當(dāng)常常進(jìn)行的是插入和刪除操作時(shí)，則采用_______存儲(chǔ)構(gòu)造為宜。8.次序表中邏輯上相鄰的元素，物理位置_______相鄰，單鏈表中邏輯上相鄰的元素，物理位置_______相鄰。9.線性表、棧和隊(duì)列都是_______構(gòu)造，可以在線性表的______位置插入和刪除元素；對(duì)于棧只能在_______位置插入和刪除元素；對(duì)于隊(duì)列只能在_______位置插入元素和在_______位置刪除元素。10.根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造中每個(gè)結(jié)點(diǎn)所含指針的個(gè)數(shù)，鏈表可分為_________和_______；而根據(jù)指針的聯(lián)接方式，鏈表又可分為________和_________。11.在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是________。12.對(duì)于一種具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)p后插入一種新結(jié)點(diǎn)的時(shí)間復(fù)雜度為______，在給定值為x的結(jié)點(diǎn)后插入一種新結(jié)點(diǎn)的時(shí)間復(fù)雜度為_______。13.對(duì)于一種棧作進(jìn)棧運(yùn)算時(shí)，應(yīng)先鑒別棧與否為_______，作退棧運(yùn)算時(shí)，應(yīng)先鑒別棧與否為_______，當(dāng)棧中元素為m時(shí)，作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則闡明棧的可用最大容量為_______。為了增長(zhǎng)內(nèi)存空間的運(yùn)用率和減少發(fā)生上溢的也許性，由兩個(gè)棧共享一片持續(xù)的內(nèi)存空間時(shí)，應(yīng)將兩棧的_______分別設(shè)在這片內(nèi)存空間的兩端，這樣只有當(dāng)_______時(shí)才產(chǎn)生上溢。14.設(shè)有一空棧，既有輸入序列1，2，3，4，5，通過push,push,pop,push,pop,push,push后，輸出序列是_________。15.無(wú)論對(duì)于次序存儲(chǔ)還是鏈?zhǔn)酱鎯?chǔ)的棧和隊(duì)列來說，進(jìn)行插入或刪除運(yùn)算的時(shí)間復(fù)雜度均相似為__________。三、簡(jiǎn)答題1.描述如下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，表頭結(jié)點(diǎn)。2.線性表的兩種存儲(chǔ)構(gòu)造各有哪些優(yōu)缺陷？3.對(duì)于線性表的兩種存儲(chǔ)構(gòu)造，假如有n個(gè)線性表同步并存，并且在處理過程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)發(fā)生變化，線性表的總數(shù)也會(huì)自動(dòng)變化，在此狀況下，應(yīng)選用哪一種存儲(chǔ)構(gòu)造？為何？4.對(duì)于線性表的兩種存儲(chǔ)構(gòu)造，若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但規(guī)定以最快的速度存取線性表中的元素，應(yīng)選用何種存儲(chǔ)構(gòu)造？試闡明理由。5.在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針好嗎？為何?6.假定有四個(gè)元素A,B,C,D依次進(jìn)棧，進(jìn)棧過程中容許出棧，試寫出所有也許的出棧序列。7.什么是隊(duì)列的上溢現(xiàn)象？一般有幾種處理措施，試簡(jiǎn)述之。8.下述算法的功能是什么?LinkList*Demo(LinkList*L){//L是無(wú)頭結(jié)點(diǎn)的單鏈表LinkList*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;}return(L);}四、算法設(shè)計(jì)題1.設(shè)計(jì)在無(wú)頭結(jié)點(diǎn)的單鏈表中刪除第i個(gè)結(jié)點(diǎn)的算法。2.在單鏈表上實(shí)現(xiàn)線性表的求表長(zhǎng)ListLength(L)運(yùn)算。3.設(shè)計(jì)將帶表頭的鏈表逆置算法。4.假設(shè)有一種帶表頭結(jié)點(diǎn)的鏈表，表頭指針為head，每個(gè)結(jié)點(diǎn)含三個(gè)域：data,next和prior。其中data為整型數(shù)域，next和prior均為指針域。目前所有結(jié)點(diǎn)已經(jīng)由next域連接起來，試編一種算法，運(yùn)用prior域（此域初值為NULL）把所有結(jié)點(diǎn)按照其值從小到大的次序鏈接起來。5.已知線性表的元素按遞增次序排列，并以帶頭結(jié)點(diǎn)的單鏈表作存儲(chǔ)構(gòu)造。試編寫一種刪除表中所有值不小于min且不不小于max的元素（若表中存在這樣的元素）的算法。6.已知線性表的元素是無(wú)序的，且以帶頭結(jié)點(diǎn)的單鏈表作為存儲(chǔ)構(gòu)造。設(shè)計(jì)一種刪除表中所有值不不小于max但不小于min的元素的算法。7.假定用一種單循環(huán)鏈表來表達(dá)隊(duì)列（也稱為循環(huán)隊(duì)列），該隊(duì)列只設(shè)一種隊(duì)尾指針，不設(shè)隊(duì)首指針，試編寫下列多種運(yùn)算的算法：（1）向循環(huán)鏈隊(duì)列插入一種元素值為x的結(jié)點(diǎn)；（2）從循環(huán)鏈隊(duì)列中刪除一種結(jié)點(diǎn)。8.設(shè)次序表L是一種遞減有序表，試寫一算法，將x插入其后仍保持L的有序性。習(xí)題2參照答案一、單項(xiàng)選擇題1．A2．A3．D4．C5．D6．A7．B8．B9．C10．A11．D12．B13．C14．B15．C16．C17．B18．D19．C 20．A二、填空題1．線性2．n-i+13．相鄰4．前移，前，后5．物理存儲(chǔ)位置，鏈域的指針值6．前趨，后繼7．次序，鏈接8．一定，不一定9．線性，任何，棧頂，隊(duì)尾，隊(duì)頭10．單鏈表，雙鏈表，非循環(huán)鏈表，循環(huán)鏈表11．使空表和非空表統(tǒng)一；算法處理一致12．O(1)，O(n)13．棧滿，?？?，m，棧底，兩個(gè)棧的棧頂在?？臻g的某一位置相遇14．2、315．O(1)三、簡(jiǎn)答題1．頭指針是指向鏈表中第一種結(jié)點(diǎn)（即表頭結(jié)點(diǎn)）的指針；在表頭結(jié)點(diǎn)之前附設(shè)的結(jié)點(diǎn)稱為頭結(jié)點(diǎn)；表頭結(jié)點(diǎn)為鏈表中存儲(chǔ)線性表中第一種數(shù)據(jù)元素的結(jié)點(diǎn)。若鏈表中附設(shè)頭結(jié)點(diǎn)，則不管線性表與否為空表，頭指針均不為空，否則表達(dá)空表的鏈表的頭指針為空。2．線性表具有兩種存儲(chǔ)構(gòu)造即次序存儲(chǔ)構(gòu)造和鏈接存儲(chǔ)構(gòu)造。線性表的次序存儲(chǔ)構(gòu)造可以直接存取數(shù)據(jù)元素，以便靈活、效率高，但插入、刪除操作時(shí)將會(huì)引起元素的大量移動(dòng)，因而減少效率：而在鏈接存儲(chǔ)構(gòu)造中內(nèi)存采用動(dòng)態(tài)分派，運(yùn)用率高，但需增設(shè)指示結(jié)點(diǎn)之間關(guān)系的指針域，存取數(shù)據(jù)元素不如次序存儲(chǔ)以便，但結(jié)點(diǎn)的插入、刪除操作較簡(jiǎn)樸。3．應(yīng)選用鏈接存儲(chǔ)構(gòu)造，由于鏈?zhǔn)酱鎯?chǔ)構(gòu)造是用一組任意的存儲(chǔ)單元依次存儲(chǔ)線性表中的各元素，這里存儲(chǔ)單元可以是持續(xù)的，也可以是不持續(xù)的：這種存儲(chǔ)構(gòu)造對(duì)于元素的刪除或插入運(yùn)算是不需要移動(dòng)元素的，只需修改指針即可，因此很輕易實(shí)現(xiàn)表的容量的擴(kuò)充。4．應(yīng)選用次序存儲(chǔ)構(gòu)造，由于每個(gè)數(shù)據(jù)元素的存儲(chǔ)位置和線性表的起始位置相差一種和數(shù)據(jù)元素在線性表中的序號(hào)成正比的常數(shù)。因此，只要確定了其起始位置，線性表中的任一種數(shù)據(jù)元素都可隨機(jī)存取，因此，線性表的次序存儲(chǔ)構(gòu)造是一種隨機(jī)存取的存儲(chǔ)構(gòu)造，而鏈表則是一種次序存取的存儲(chǔ)構(gòu)造。5．設(shè)尾指針比設(shè)頭指針好。尾指針是指向終端結(jié)點(diǎn)的指針，用它來表達(dá)單循環(huán)鏈表可以使得查找鏈表的開始結(jié)點(diǎn)和終端結(jié)點(diǎn)都很以便，設(shè)一帶頭結(jié)點(diǎn)的單循環(huán)鏈表，其尾指針為rear，則開始結(jié)點(diǎn)和終端結(jié)點(diǎn)的位置分別是rear->next->next和rear,查找時(shí)間都是O(1)。若用頭指針來表達(dá)該鏈表，則查找終端結(jié)點(diǎn)的時(shí)間為O(n)。6．共有14種也許的出棧序列，即為：ABCD,ABDC，ACBD,ACDB，BACD，ADCB，BADC，BCAD,BCDA，BDCA,CBAD,CBDA，CDBA,DCBA7．在隊(duì)列的次序存儲(chǔ)構(gòu)造中，設(shè)隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列的容量（即存儲(chǔ)的空間大?。閙axnum。當(dāng)有元素要加入隊(duì)列（即入隊(duì)）時(shí)，若rear=maxnum，則會(huì)發(fā)生隊(duì)列的上溢現(xiàn)象，此時(shí)就不能將該元素加入隊(duì)列。對(duì)于隊(duì)列，尚有一種“假溢出”現(xiàn)象，隊(duì)列中尚余有足夠的空間，但元素卻不能入隊(duì)，一般是由于隊(duì)列的存儲(chǔ)構(gòu)造或操作方式的選擇不妥所致，可以用循環(huán)隊(duì)列處理。一般地，要處理隊(duì)列的上溢現(xiàn)象可有如下幾種措施：（1）可建立一種足夠大的存儲(chǔ)空間以防止溢出，但這樣做往往會(huì)導(dǎo)致空間使用率低，揮霍存儲(chǔ)空間。（2）要防止出現(xiàn)“假溢出”現(xiàn)象可用如下措施處理：第一種：采用移動(dòng)元素的措施。每當(dāng)有一種新元素入隊(duì)，就將隊(duì)列中已經(jīng)有的元素向隊(duì)頭移動(dòng)一種位置，假定空余空間足夠。第二種：每當(dāng)刪去一種隊(duì)頭元素，則可依次移動(dòng)隊(duì)列中的元素總是使front指針指向隊(duì)列中的第一種位置。第三種：采用循環(huán)隊(duì)列方式。將隊(duì)頭、隊(duì)尾看作是一種首尾相接的循環(huán)隊(duì)列，即用循環(huán)數(shù)組實(shí)現(xiàn)，此時(shí)隊(duì)首仍在隊(duì)尾之前，作插入和刪除運(yùn)算時(shí)仍遵照“先進(jìn)先出”的原則。8．該算法的功能是：將開始結(jié)點(diǎn)摘下鏈接到終端結(jié)點(diǎn)之后成為新的終端結(jié)點(diǎn)，而本來的第二個(gè)結(jié)點(diǎn)成為新的開始結(jié)點(diǎn)，返回新鏈表的頭指針。四、算法設(shè)計(jì)題1．算法思想為：（1）應(yīng)判斷刪除位置的合法性，當(dāng)i<0或i>n-1時(shí)，不容許進(jìn)行刪除操作；（2）當(dāng)i=0時(shí)，刪除第一種結(jié)點(diǎn)：（3）當(dāng)０<i<n時(shí)，容許進(jìn)行刪除操作，但在查找被刪除結(jié)點(diǎn)時(shí)，須用指針記住該結(jié)點(diǎn)的前趨結(jié)點(diǎn)。算法描述如下：delete(LinkList*q,inti){//在無(wú)頭結(jié)點(diǎn)的單鏈表中刪除第i個(gè)結(jié)點(diǎn)LinkList*p,*s;intj;if(i<0)printf("Can'tdelete");elseif(i==0){s=q;q=q->next;free(s);}else{j=0;s=q;while((j<i)&&(s!=NULL)){p=s;s=s->next;j++;}if(s==NULL)printf("Cant'tdelete");else{p->next=s->next;free(s);}}}2．由于在單鏈表中只給出一種頭指針，因此只能用遍歷的措施來數(shù)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)了。算法描述如下：intListLength(LinkList*L){//求帶頭結(jié)點(diǎn)的單鏈表的表長(zhǎng)intlen=0;ListList*p;p=L;while(p->next!=NULL){p=p->next;len++;}return(len);}3．設(shè)單循環(huán)鏈表的頭指針為head，類型為L(zhǎng)inkList。逆置時(shí)需將每一種結(jié)點(diǎn)的指針域作以修改，使其原前趨結(jié)點(diǎn)成為后繼。如要更改q結(jié)點(diǎn)的指針域時(shí)，設(shè)s指向其原前趨結(jié)點(diǎn)，p指向其原后繼結(jié)點(diǎn)，則只需進(jìn)行q->next=s;操作即可，算法描述如下：voidinvert(LinkList*head){//逆置head指針?biāo)赶虻膯窝h(huán)鏈表linklist*p,*q,*s;q=head;p=head->next;while(p!=head)//當(dāng)表不為空時(shí)，逐一結(jié)點(diǎn)逆置{s=q;q=p;p=p->next;q->next=s;}p->next=q;}4．定義類型LinkList如下：typedefstructnode{intdata;structnode*next,*prior;}LinkList;此題可采用插入排序的措施，設(shè)p指向待插入的結(jié)點(diǎn)，用q搜索已由prior域鏈接的有序表找到合適位置將p結(jié)點(diǎn)鏈入。算法描述如下：insert(LinkList*head){LinkList*p,*s,*q;p=head->next;//p指向待插入的結(jié)點(diǎn)，初始時(shí)指向第一種結(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;}}5．算法描述如下：delete(LinkList*head,intmax,intmin){linklist*p,*q;if(head!=NULL){q=head;p=head->next;while((p!=NULL)&&(p->data<=min)){q=p;p=p->next;}while((p!=NULL)&&(p->data<max))p=p->next;q->next=p;}}6．算法描述如下：delete(LinkList*head,intmax,intmin){LinkList*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;free(p);p=q->next;}}7．本題是對(duì)一種循環(huán)鏈隊(duì)列做插入和刪除運(yùn)算，假設(shè)不需要保留被刪結(jié)點(diǎn)的值和不需要回收結(jié)點(diǎn)，算法描述如下：（1）插入（即入隊(duì)）算法：insert(LinkList*rear,elemtypex){//設(shè)循環(huán)鏈隊(duì)列的隊(duì)尾指針為rear,x為待插入的元素LinkList*p;p=(LinkList*)malloc(sizeof(LinkList));if(rear==NULL)//如為空隊(duì)，建立循環(huán)鏈隊(duì)列的第一種結(jié)點(diǎn){rear=p;rear->next=p;//鏈接成循環(huán)鏈表}else//否則在隊(duì)尾插入p結(jié)點(diǎn){p->next=rear->next;rear->next=p;rear=p;}}（2）刪除（即出隊(duì)）算法：delete(LinkList*rear){//設(shè)循環(huán)鏈隊(duì)列的隊(duì)尾指針為rearif(rear==NULL)//空隊(duì)printf("underflow\n");if(rear->next==rear)//隊(duì)中只有一種結(jié)點(diǎn)rear=NULL;elserear->next=rear->next->next;//rear->next指向的結(jié)點(diǎn)為循環(huán)鏈隊(duì)列的隊(duì)頭結(jié)點(diǎn)}8．只要從終端結(jié)點(diǎn)開始往前找到第一種比x大(或相等)的結(jié)點(diǎn)數(shù)據(jù)，在這個(gè)位置插入就可以了。算法描述如下：intInsertDecreaseList(SqList*L,elemtypex){inti;if((*L).len>=maxlen){printf(“overflow");return(0);}for(i=(*L).len;i>0&&(*L).elem[i-1]<x;i--)(*L).elem[i]=(*L).elem[i-1];//比較并移動(dòng)元素(*L).elem[i]=x;(*L).len++;return(1);}

習(xí)題3一、單項(xiàng)選擇題1.空串與空格字符構(gòu)成的串的區(qū)別在于（）。A.沒有區(qū)別 B.兩串的長(zhǎng)度不相等C.兩串的長(zhǎng)度相等 D.兩串包括的字符不相似2.一種子串在包括它的主串中的位置是指（）。A.子串的最終那個(gè)字符在主串中的位置B.子串的最終那個(gè)字符在主串中初次出現(xiàn)的位置C.子串的第一種字符在主串中的位置D.子串的第一種字符在主串中初次出現(xiàn)的位置3.下面的說法中，只有（）是對(duì)的的。A.字符串的長(zhǎng)度是指串中包括的字母的個(gè)數(shù)B.字符串的長(zhǎng)度是指串中包括的不一樣字符的個(gè)數(shù)C.若T包括在S中，則T一定是S的一種子串D.一種字符串不能說是其自身的一種子串4.兩個(gè)字符串相等的條件是（）。A.兩串的長(zhǎng)度相等B.兩串包括的字符相似C.兩串的長(zhǎng)度相等，并且兩串包括的字符相似D.兩串的長(zhǎng)度相等，并且對(duì)應(yīng)位置上的字符相似5.若SUBSTR（S，i，k）表達(dá)求S中從第i個(gè)字符開始的持續(xù)k個(gè)字符構(gòu)成的子串的操作，則對(duì)于S=“Beijing＆Nanjing”，SUBSTR（S，4，5）=（）。A.“ijing” B.“jing＆”C.“ingNa” D.“ing＆N”6.若INDEX（S，T）表達(dá)求T在S中的位置的操作，則對(duì)于S=“Beijing＆Nanjing”，T=“jing”，INDEX（S，T）=（）。A.2B.3C7.若REPLACE（S，S1，S2）表達(dá)用字符串S2替代字符串S中的子串S1的操作，則對(duì)于S=“Beijing＆Nanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（）。A.“Nanjing＆Shanghai” B.“Nanjing＆Nanjing”C.“ShanghaiNanjing” D.“Shanghai＆Nanjing”8.在長(zhǎng)度為n的字符串S的第i個(gè)位置插入此外一種字符串，i的合法值應(yīng)當(dāng)是（）。A.i＞0B.i≤nC.1≤i≤nD.1≤i≤n+19.字符串采用結(jié)點(diǎn)大小為1的鏈表作為其存儲(chǔ)構(gòu)造，是指（）。A.鏈表的長(zhǎng)度為1B.鏈表中只寄存1個(gè)字符 C.鏈表的每個(gè)鏈結(jié)點(diǎn)的數(shù)據(jù)域中不僅只寄存了一種字符D.鏈表的每個(gè)鏈結(jié)點(diǎn)的數(shù)據(jù)域中只寄存了一種字符二、填空題1.計(jì)算機(jī)軟件系統(tǒng)中，有兩種處理字符串長(zhǎng)度的措施：一種是___________，第二種是___________________。2.兩個(gè)字符串相等的充要條件是_____________________和___________________。3.設(shè)字符串S1=“ABCDEF”，S2=“PQRS”，則運(yùn)算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值為___________________。4.串是指___________________。5.空串是指___________________，空格串是指___________________。三、算法設(shè)計(jì)題1.設(shè)有一種長(zhǎng)度為s的字符串，其字符次序寄存在一種一維數(shù)組的第1至第s個(gè)單元中（每個(gè)單元寄存一種字符）?，F(xiàn)規(guī)定從此串的第m個(gè)字符后來刪除長(zhǎng)度為t的子串，m<s，t<(s-m)，并將刪除后的成果復(fù)制在該數(shù)組的第s單元后來的單元中，試設(shè)計(jì)此刪除算法。2.設(shè)s和t是表到達(dá)單鏈表的兩個(gè)串，試編寫一種找出s中第1個(gè)不在t中出現(xiàn)的字符（假定每個(gè)結(jié)點(diǎn)只寄存1個(gè)字符）的算法。習(xí)題3參照答案一、單項(xiàng)選擇題1．B 2．D 3．C 4．D 5．B 6．C 7．D 8．C 9．D二、填空題1.固定長(zhǎng)度，設(shè)置長(zhǎng)度指針2.兩個(gè)串的長(zhǎng)度相等，對(duì)應(yīng)位置的字符相等3.“BCDEDE”4.含n個(gè)字符的有限序列（n≥0）5.不含任何字符的串，僅含空格字符的字符串三、算法設(shè)計(jì)題1．算法描述為：intdelete(r,s,t,m)//從串的第m個(gè)字符后來刪除長(zhǎng)度為t的子串charr[];ints,t,m;{inti,j;for(i=1;i<=m;i++)r[s+i]=r[i];for(j=m+t-i;j<=s;j++)r[s-t+j]=r[j];return(1);}//delete2．算法思想為：（1）鏈表s中取出一種字符；將該字符與單鏈表t中的字符依次比較；（2）當(dāng)t中有與從s中取出的這個(gè)字符相等的字符，則從t中取下一種字符反復(fù)以上比較；（3）當(dāng)t中沒有與從s中取出的這個(gè)字符相等的字符，則算法結(jié)束。設(shè)單鏈表類型為L(zhǎng)inkList；注意，此時(shí)類型LinkList中的data成分為字符類型。LinkStringfind(s,t)LinkString*s,*t;{LinkString*ps,*pt;ps=s;while(ps!=NULL){pt=t;while((pt!=NULL)&&(ps->data!=pt->data))pt=pt->next;if(pt==NULL)ps=NULL;else{ps=ps->next;s=ps;}}returns;}//find

習(xí)題4一、單項(xiàng)選擇題1.設(shè)二維數(shù)組A[0…m-1][0…n-1]按行優(yōu)先次序存儲(chǔ)在內(nèi)存中，第一種元素的地址為p，每個(gè)元素占k個(gè)字節(jié)，則元素aij的地址為（）。A.p+[i*n+j-1]*k B.p+[(i-1)*n+j-1]*kC.p+[(j-1)*n+i-1]*k D.p+[j*n+i-1]*k2.已知二維數(shù)組A10×10中，元素a20的地址為560，每個(gè)元素占4個(gè)字節(jié)，則元素a10的地址為（）。A.520 B.522 C.5243.若數(shù)組A[0…m][0…n]按列優(yōu)先次序存儲(chǔ)，則aij地址為（）。A.LOC(a00)+[j*m+i] B.LOC(a00)+[j*n+i]C.LOC(a00)+[(j-1)*n+i-1] D.LOC(a00)+[(j-1)*m+i-1]4.若下三角矩陣An×n，按列次序壓縮存儲(chǔ)在數(shù)組Sa[0…(n+1)n/2]中，則非零元素aij的地址為（）。（設(shè)每個(gè)元素占d個(gè)字節(jié)）A.[(j-1)*n-+i-1]*dB.[(j-1)*n-+i]*dC．[(j-1)*n-+i+1]*dD．[(j-1)*n-+i-2]*d5.設(shè)有廣義表D=(a,b,D)，其長(zhǎng)度為（），深度為（）。A.無(wú)窮大 B.3 C.2 D.6.廣義表A=（a），則表尾為（）。A.a B.(()) C.空表 D.(a)7.廣義表A=((x,(a,B)),(x,(a,B),y))，則運(yùn)算head(head(tail(A)))的成果為（）。A.x B.(a,B) C.(x,(a,B)) D.A8.下列廣義表用圖來表達(dá)時(shí)，分支結(jié)點(diǎn)最多的是（）。A.L=((x,(a,B)),(x,(a,B),y)) B.A=(s,(a,B))C.B=((x,(a,B),y)) D.D=((a,B),(c,(a,B),D)9.一般對(duì)數(shù)組進(jìn)行的兩種基本操作是（）。A.建立與刪除 B.索引和修改C.查找和修改 D.查找與索引10.假定在數(shù)組A中，每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始持續(xù)寄存在存儲(chǔ)器內(nèi)，寄存該數(shù)組至少需要的單元數(shù)為（）。A.80 B.100 C.24011.數(shù)組A中，每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始持續(xù)寄存在存儲(chǔ)器內(nèi)，該數(shù)組按行寄存時(shí)，元素A[8][5]的起始地址為（）。A.SA+141 B.SA+144 C.SA+222 D.12.稀疏矩陣一般的壓縮存儲(chǔ)措施有兩種，即（）。A.二維數(shù)組和三維數(shù)組 B.三元組和散列C.三元組和十字鏈表 D.散列和十字鏈表13.若采用三元組壓縮技術(shù)存儲(chǔ)稀疏矩陣，只要把每個(gè)元素的行下標(biāo)和列下標(biāo)互換，就完畢了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算，這種觀點(diǎn)（）。A.對(duì)的 B.不對(duì)的14.一種廣義表的表頭總是一種（）。A.廣義表 B.元素 C.空表 D.元素或廣義表15.一種廣義表的表尾總是一種（）。A.廣義表 B.元素 C.空表 D.元素或廣義表16.數(shù)組就是矩陣，矩陣就是數(shù)組，這種說法（）。A.對(duì)的 B.錯(cuò)誤C.前句對(duì)，后句錯(cuò) D.后句對(duì)二、填空題1.一維數(shù)組的邏輯構(gòu)造是______________，存儲(chǔ)構(gòu)造是______________；對(duì)于二維或多維數(shù)組，分為______________和______________兩種不一樣的存儲(chǔ)方式。2.對(duì)于一種二維數(shù)組A[m][n]，若按行序?yàn)橹餍虼鎯?chǔ)，則任一元素A[i][j]相對(duì)于A[0][0]的地址為______________。3.一種廣義表為(a,(a,b),d,e,((i,j),k))，則該廣義表的長(zhǎng)度為_____，深度為_____。4.一種稀疏矩陣為，則對(duì)應(yīng)的三元組線性表為_____________。5.一種n×n的對(duì)稱矩陣，假如以行為主序或以列為主序存入內(nèi)存，則其容量為______________。6.已知廣義表A=((a,b,c),(d,e,f))，則運(yùn)算head(tail(tail(A)))=____________。7.設(shè)有一種10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式以行序?yàn)橹餍虼鎯?chǔ)，a為第一種元素，其存儲(chǔ)地址為0，每個(gè)元素占有1個(gè)存儲(chǔ)地址空間，則a的地址為______________。8.已知廣義表Ls=(a,(b,c,d),e)，運(yùn)用head和tail函數(shù)取出Ls中的原子b的運(yùn)算是______________。9.三維數(shù)組R[c1…d1,c2…d2,c3…d3]共具有______________個(gè)元素。（其中：c1≤d1,c2≤d2,c3≤d3）10.數(shù)組A[1…10，-2…6，2…8]以行優(yōu)先的次序存儲(chǔ)，設(shè)第一種元素的首地址是100，每個(gè)元素占3個(gè)存儲(chǔ)長(zhǎng)度的存儲(chǔ)空間，則元素A[5，0，7]的存儲(chǔ)地址為______________。三、判斷題1.數(shù)組可看作基本線性表的一種推廣，因此與線性表同樣，可以對(duì)它進(jìn)行插入、刪除等操作。（）2.多維數(shù)組可以看作數(shù)據(jù)元素也是基本線性表的基本線性表。（）3.以行為主序或以列為主序?qū)τ诙嗑S數(shù)組的存儲(chǔ)沒有影響。（）4.對(duì)于不一樣的特殊矩陣應(yīng)當(dāng)采用不一樣的存儲(chǔ)方式。（）5.采用壓縮存儲(chǔ)之后，下三角矩陣的存儲(chǔ)空間可以節(jié)省二分之一。（）6.在一般狀況下，采用壓縮存儲(chǔ)之后，對(duì)稱矩陣是所有特殊矩陣中存儲(chǔ)空間節(jié)省最多的。（）7.矩陣不僅是表達(dá)多維數(shù)組，并且是表達(dá)圖的重要工具。（）8.距陣中的數(shù)據(jù)元素可以是不一樣的數(shù)據(jù)類型。（）9.矩陣中的行列數(shù)往往是不相等的。（）10.廣義表的表頭可以是廣義表，也可以是單個(gè)元素。（）11.廣義表的表尾一定是一種廣義表。（）12.廣義表的元素可以是子表，也可以是單元素。（）13.廣義表不能遞歸定義。（）14.廣義表實(shí)際上是基本線性表的推廣。（）15.廣義表的構(gòu)成元素可以是不一樣形式的元素。（）習(xí)題4參照答案一、單項(xiàng)選擇題1.A2.A3.A4.B5.BA6.C7.A8.A9.C10.C11.C12.C13.B14.D15.A16.B二、填空題1.線性構(gòu)造，次序構(gòu)造，以行為主序，以列為主序2.i×n+j個(gè)元素位置3.5，34.（（0，2，2），（1，0，3），（2，2，-1），（2，3，5））5.n×(n+1)/26.e7.418.head(head(tail(Ls)))9.（d-c+1）×（d-c+1）×（d-c+1）10.913三、判斷題1.×2.√3.√4.√5.×6.×7.√8.×9.×10.√11.√12.√13.×14.√15.√

習(xí)題5一、單項(xiàng)選擇題1.在一棵度為3的樹中，度為3的結(jié)點(diǎn)數(shù)為2個(gè)，度為2的結(jié)點(diǎn)數(shù)為1個(gè)，度為1的結(jié)點(diǎn)數(shù)為2個(gè)，則度為0的結(jié)點(diǎn)數(shù)為（）個(gè)。A.4 B.5 C.6 D.2.假設(shè)在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為（）個(gè)。A.15 B.16 C.17 D.3.假定一棵三叉樹的結(jié)點(diǎn)數(shù)為50，則它的最小高度為（）。A.3 B.4 C.5 D.4.在一棵二叉樹上第4層的結(jié)點(diǎn)數(shù)最多為（）。A.2 B.4 C.6 D.5.用次序存儲(chǔ)的措施將完全二叉樹中的所有結(jié)點(diǎn)逐層寄存在數(shù)組中R[1..n]，結(jié)點(diǎn)R[i]若有左孩子，其左孩子的編號(hào)為結(jié)點(diǎn)（）。A.R[2i+1] B.R[2i] C.R[i/2] D.R[2i-1]6.由權(quán)值分別為3,8,6,2,5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)途徑長(zhǎng)度為（）。A.24 B.48 C.72 D.7.線索二叉樹是一種（）構(gòu)造。A.邏輯 B.邏輯和存儲(chǔ) C.物理 D.線性8.線索二叉樹中，結(jié)點(diǎn)p沒有左子樹的充要條件是（）。A.p->lc=NULL B.p->ltag=1C.p->ltag=1且p->lc=NULL D.以上都不對(duì)9.設(shè)n,m為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷序列中n在m前的條件是（）。A.n在m右方 B.n在m左方C.n是m的祖先 D.n是m的子孫10.假如F是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點(diǎn)的前序就是F中結(jié)點(diǎn)的（）。A.中序 B.前序 C.后序 D.層次序11.欲實(shí)現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不必使用棧，最佳方案是二叉樹采用（）存儲(chǔ)構(gòu)造。A.三叉鏈表 B.廣義表 C.二叉鏈表 D.次序12.下面論述對(duì)的的是（）。A.二叉樹是特殊的樹B.二叉樹等價(jià)于度為2的樹C.完全二叉樹必為滿二叉樹D.二叉樹的左右子樹有次序之分13.任何一棵二叉樹的葉子結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序（）。A.不發(fā)生變化B.發(fā)生變化C.不能確定 D.以上都不對(duì)14.已知一棵完全二叉樹的結(jié)點(diǎn)總數(shù)為9個(gè)，則最終一層的結(jié)點(diǎn)數(shù)為（）。A.1 B.2 C.3 D.15.根據(jù)先序序列ABDC和中序序列DBAC確定對(duì)應(yīng)的二叉樹，該二叉樹（）。A.是完全二叉樹 B.不是完全二叉樹C.是滿二叉樹 D.不是滿二叉樹二、判斷題1.二叉樹中每個(gè)結(jié)點(diǎn)的度不能超過2，因此二叉樹是一種特殊的樹。 （）2.二叉樹的前序遍歷中，任意結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)之前。 （）3.線索二叉樹是一種邏輯構(gòu)造。 （）4.哈夫曼樹的總結(jié)點(diǎn)個(gè)數(shù)（多于1時(shí)）不能為偶數(shù)。 （）5.由二叉樹的先序序列和后序序列可以唯一確定一顆二叉樹。 （）6.樹的后序遍歷與其對(duì)應(yīng)的二叉樹的后序遍歷序列相似。 （）7.根據(jù)任意一種遍歷序列即可唯一確定對(duì)應(yīng)的二叉樹。 （）8.滿二叉樹也是完全二叉樹。 （）9.哈夫曼樹一定是完全二叉樹。 （）10.樹的子樹是無(wú)序的。 （）三、填空題1.假定一棵樹的廣義表表達(dá)為A（B（E），C（F（H，I，J），G），D），則該樹的度為_____，樹的深度為_____，終端結(jié)點(diǎn)的個(gè)數(shù)為______，單分支結(jié)點(diǎn)的個(gè)數(shù)為______，雙分支結(jié)點(diǎn)的個(gè)數(shù)為______，三分支結(jié)點(diǎn)的個(gè)數(shù)為_______，C結(jié)點(diǎn)的雙親結(jié)點(diǎn)為_______，其孩子結(jié)點(diǎn)為_______和_______結(jié)點(diǎn)。2.設(shè)F是一種森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個(gè)非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有_______個(gè)。3.對(duì)于一種有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)它為一棵________二叉樹時(shí)具有最小高度，即為_______，當(dāng)它為一棵單支樹具有_______高度，即為_______。4.由帶權(quán)為3，9，6，2，5的5個(gè)葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹，則帶權(quán)途徑長(zhǎng)度為___。5.在一棵二叉排序樹上按_______遍歷得到的結(jié)點(diǎn)序列是一種有序序列。6.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)進(jìn)行鏈接存儲(chǔ)時(shí)，其二叉鏈表中的指針域的總數(shù)為_______個(gè)，其中_______個(gè)用于鏈接孩子結(jié)點(diǎn)，_______個(gè)空閑著。7.在一棵二叉樹中，度為0的結(jié)點(diǎn)個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，則n0=______。8.一棵深度為k的滿二叉樹的結(jié)點(diǎn)總數(shù)為_______，一棵深度為k的完全二叉樹的結(jié)點(diǎn)總數(shù)的最小值為_____，最大值為______。9.由三個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹，共有____種不一樣的形態(tài)。10.設(shè)高度為h的二叉樹中只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包括的結(jié)點(diǎn)數(shù)至少為____。11.一棵具有n個(gè)結(jié)點(diǎn)的k叉樹，______形態(tài)到達(dá)最大深度，____形態(tài)到達(dá)最小深度。12.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，若一種結(jié)點(diǎn)的編號(hào)為i(1≤i≤n)，則它的左孩子結(jié)點(diǎn)的編號(hào)為________，右孩子結(jié)點(diǎn)的編號(hào)為________，雙親結(jié)點(diǎn)的編號(hào)為________。13.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，采用二叉鏈表存儲(chǔ)時(shí)，鏈表中指針域的總數(shù)為_________個(gè)，其中___________個(gè)用于鏈接孩子結(jié)點(diǎn)，_____________個(gè)空閑著。14.哈夫曼樹是指________________________________________________的二叉樹。15.空樹是指________________________，最小的樹是指_______________________。16.二叉樹的鏈?zhǔn)酱鎯?chǔ)構(gòu)造有______________和_______________兩種。17.三叉鏈表比二叉鏈表多一種指向______________的指針域。18.線索是指___________________________________________。19.線索鏈表中的rtag域值為_____時(shí)，表達(dá)該結(jié)點(diǎn)無(wú)右孩子，此時(shí)______域?yàn)橹赶蛟摻Y(jié)點(diǎn)后繼線索的指針。20.本節(jié)中我們學(xué)習(xí)的樹的存儲(chǔ)構(gòu)造有_____________、___________和___________。四、應(yīng)用題1.已知一棵樹邊的集合為{<i，m>，<i，n>，<e，i>，<b，e>，<b，d>，<a，b>，<g，j>，<g，k>，<c，g>，<c，f>，<h，l>，<c，h>，<a，c>}，請(qǐng)畫出這棵樹，并回答問題：（1）哪個(gè)是根結(jié)點(diǎn)？（2）哪些是葉子結(jié)點(diǎn)？（3）哪個(gè)是結(jié)點(diǎn)g的雙親？（4）哪些是結(jié)點(diǎn)g的祖先？（5）哪些是結(jié)點(diǎn)g的孩子？（6）哪些是結(jié)點(diǎn)e的孩子？（7）哪些是結(jié)點(diǎn)e的兄弟？哪些是結(jié)點(diǎn)f的兄弟？（8）結(jié)點(diǎn)b和n的層次號(hào)分別是什么？（9）樹的深度是多少？（10）以結(jié)點(diǎn)c為根的子樹深度是多少？2.一棵度為2的樹與一棵二叉樹有何區(qū)別。3.試分別畫出具有3個(gè)結(jié)點(diǎn)的樹和二叉樹的所有不一樣形態(tài)？4.已知用一維數(shù)組寄存的一棵完全二叉樹：ABCDEFGHIJKL，寫出該二叉樹的先序、中序和后序遍歷序列。5.一棵深度為H的滿k叉樹有如下性質(zhì)：第H層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其他各層上每個(gè)結(jié)點(diǎn)均有k棵非空子樹，假如按層次自上至下，從左到右次序從1開始對(duì)所有結(jié)點(diǎn)編號(hào)，回答問題：（1）各層的結(jié)點(diǎn)數(shù)目是多少？（2）編號(hào)為n的結(jié)點(diǎn)的父結(jié)點(diǎn)假如存在，編號(hào)是多少？（3）編號(hào)為n的結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)假如存在，編號(hào)是多少？（4）編號(hào)為n的結(jié)點(diǎn)有右兄弟的條件是什么？其右兄弟的編號(hào)是多少？6.找出所有滿足下列條件的二叉樹：（1）它們?cè)谙刃虮闅v和中序遍歷時(shí)，得到的遍歷序列相似；（2）它們?cè)诤笮虮闅v和中序遍歷時(shí)，得到的遍歷序列相似；（3）它們?cè)谙刃虮闅v和后序遍歷時(shí)，得到的遍歷序列相似；7.假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ，中序序列為ABCDEFGHIJK，請(qǐng)寫出該二叉樹的后序遍歷序列。8.假設(shè)一棵二叉樹的后序序列為DCEGBFHKJIA，中序序列為DCBGEAHFIJK，請(qǐng)寫出該二叉樹的后序遍歷序列。9.給出如圖5-14所示的森林的先根、后根遍歷結(jié)點(diǎn)序列，然后畫出該森林對(duì)應(yīng)的二叉樹。10．給定一組權(quán)值（5，9，11，2，7，16），試設(shè)計(jì)對(duì)應(yīng)的哈夫曼樹。AABDEFCGHJIKNOML圖5-14五、算法設(shè)計(jì)題1.一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹以一維數(shù)組作為存儲(chǔ)構(gòu)造，試設(shè)計(jì)一種對(duì)該完全二叉樹進(jìn)行先序遍歷的算法。2.給定一棵用二叉鏈表表達(dá)的二叉樹，其中的指針t指向根結(jié)點(diǎn)，試寫出從根開始，按層次遍歷二叉樹的算法，同層的結(jié)點(diǎn)按從左至右的次序訪問。3.寫出在中序線索二叉樹中結(jié)點(diǎn)P的右子樹中插入一種結(jié)點(diǎn)s的算法。4.給定一棵二叉樹，用二叉鏈表表達(dá)，其根指針為t，試寫出求該二叉樹中結(jié)點(diǎn)n的雙親結(jié)點(diǎn)的算法。若沒有結(jié)點(diǎn)n或者該結(jié)點(diǎn)沒有雙親結(jié)點(diǎn)，分別輸出對(duì)應(yīng)的信息；若結(jié)點(diǎn)n有雙親，輸出其雙親的值。習(xí)題5參照答案一、單項(xiàng)選擇題1.C2.B3.C4.D5.B6.D7.C8.B9.B10.B11.A12.D13.A14.B15.A二、判斷題1.×2.√3.×4.√5.×6.√7.√8.√9.×10.×三、填空題1.3，4，6，1，1，2，A，F(xiàn)，G2.n+13.完全，，最大，n4.555.中序6.2n，n-1，n+17.n2+18.2k-1，2k-1，2k-19.510.2h-111.單支樹，完全二叉樹12.2i，2i+1，i/2（或?i/2?）13.2n，n-1，n+114.帶權(quán)途徑長(zhǎng)度最小15.結(jié)點(diǎn)數(shù)為0，只有一種根結(jié)點(diǎn)的樹16.二叉鏈表，三叉鏈表17.雙親結(jié)點(diǎn)18.指向結(jié)點(diǎn)前驅(qū)和后繼信息的指針19.1，RChild20.孩子表達(dá)法，雙親表達(dá)法，長(zhǎng)子兄弟表達(dá)法四、應(yīng)用題1.解答：abcdabcdegfhimnjki圖5-15其中根結(jié)點(diǎn)為a；葉子結(jié)點(diǎn)有：d、m、n、j、k、f、l；c是結(jié)點(diǎn)g的雙親；a、c是結(jié)點(diǎn)g的祖先；j、k是結(jié)點(diǎn)g的孩子；m、n是結(jié)點(diǎn)e的子孫；e是結(jié)點(diǎn)d的兄弟；g、h是結(jié)點(diǎn)f的兄弟；結(jié)點(diǎn)b和n的層次號(hào)分別是2和5；樹的深度為5。2.解答：度為2的樹有兩個(gè)分支，但分支沒有左右之分；一棵二叉樹也有兩個(gè)分支，但有左右之分，左右子樹不能互換。3.解答：略4.解答：先序序列：ABDHIEJKCFLG中序序列：HDIBJEKALFCG后序序列：HIDJKEBLFGCA5.解答：（1）第i層上的結(jié)點(diǎn)數(shù)目是mi-1。（2）編號(hào)為n的結(jié)點(diǎn)的父結(jié)點(diǎn)假如存在，編號(hào)是((n-2)/m)+1。（3）編號(hào)為n的結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)假如存在，編號(hào)是(n-1)*m+i+1。（4）編號(hào)為n的結(jié)點(diǎn)有右兄弟的條件是(n-1)%m≠0。其右兄弟的編號(hào)是n+1。6.解答：（1）先序序列和中序序列相似的二叉樹為：空樹或者任一結(jié)點(diǎn)均無(wú)左孩子的非空二叉樹；（2）中序序列和后序序列相似的二叉樹為：空樹或者任一結(jié)點(diǎn)均無(wú)右孩子的非空二叉樹；（3）先序序列和后序序列相似的二叉樹為：空樹或僅有一種結(jié)點(diǎn)的二叉樹。7.解答：后序序列：ACDBGJKIHFE8.解答：先序序列：ABCDGEIHFJK9.解答：先根遍歷：ABCDEFGHIJKLMNO后根遍歷：BDEFCAHJIGKNOML森林轉(zhuǎn)換成二叉樹如圖5-16所示。10.解答：構(gòu)造而成的哈夫曼樹如圖5-17所示。BBGDCHKEIFJLMNOA圖5-165050920301116147725圖5-17五、算法設(shè)計(jì)題1.解答：這個(gè)問題可以用遞歸算法，也可用非遞歸算法，下面給出的為非遞歸算法。假設(shè)該完全二叉樹的結(jié)點(diǎn)以層次為序，按照從上到下，同層從左到右次序編號(hào)，寄存在一種一維數(shù)組R[1..n]中，且用一種有足夠大容量為maxlen的次序棧作輔助存儲(chǔ)，算法描述如下：preorder(R)//先序遍歷二叉樹RintR[n];{introot;SqStack*s;//s為一種指針棧，類型為seqstack，其中包括top域和數(shù)組datas->top=-1;//s棧置空root=1;while((root<=n)&&(s->top>-1)){while(root<=n){printf(R[root]); s->top++; s->data[s->top]=root; root=2*root;} if(s->top>-1)//棧非空訪問，遍歷右子樹 {root=s->data[s->top]*2+1; s->top--;}}}2.解答：考慮用一種次序隊(duì)que來保留遍歷過程中的各個(gè)結(jié)點(diǎn)，由于二叉樹以二叉鏈表存儲(chǔ)，因此可設(shè)que為一種指向數(shù)據(jù)類型為bitree的指針數(shù)組，最大容量為maxnum，下標(biāo)從1開始，同層結(jié)點(diǎn)從左到右寄存。算法中的front為隊(duì)頭指針，rear為隊(duì)尾指針。levelorder(BiTree*t)//按層次遍歷二叉樹t{BiTree*que[maxnum];intrear,front;if(t!=NULL){front=0;//置空隊(duì)列rear=1;que[1]=t;do {front=front%maxsize+1;//出隊(duì) t=que[front]; printf(t->data); if(t->lchild!=NULL)//左子樹的根結(jié)點(diǎn)入隊(duì) {rear=rear%maxsize+1; que[rear]=t->lchild;} if(t->rchild!=NULL)//右子樹的根結(jié)點(diǎn)入隊(duì) {rear=rear%maxsize+1; que[rear]=t->rchild;}}while(rear==front);//隊(duì)列為空時(shí)結(jié)束}}3.解答：設(shè)該線索二叉樹類型為bithptr，包括5個(gè)域：lchild，ltag，data，rchild，rtag。insert(p,s) //將s結(jié)點(diǎn)作為p的右子樹插入BiThrNode*p,*s;{BiThrNode*q;if(p->rtag==1)//無(wú)右子樹，則有右線索{s->rchild=p->rchild;s->rtag=1;p->rchild=s;p->rtag=0;}else{q=p->rchild;while(q->ltag==0)//查找p所指結(jié)點(diǎn)中序后繼，即為其右子樹中最左下的結(jié)點(diǎn) q=q->lchild;q->lchild=p->rchild;s->rtag=0;p->rchild=s;}s->lchild=p;//將s結(jié)點(diǎn)的左線索指向p結(jié)點(diǎn)s->ltag=1;}4.解答：運(yùn)用一種隊(duì)列來完畢，設(shè)該隊(duì)列類型為指針類型，最大容量為maxnum。算法中的front為隊(duì)頭指針，rear為隊(duì)尾指針，若目前隊(duì)頭結(jié)點(diǎn)的左、右子樹的根結(jié)點(diǎn)不是所求結(jié)點(diǎn)，則將兩子樹的根結(jié)點(diǎn)入隊(duì)，否則，隊(duì)頭指針?biāo)附Y(jié)點(diǎn)即為結(jié)點(diǎn)的雙親。parentjudge(t,n)BiTree*t;intn;{BiTree*que[maxnum];intfront,rear;BiTree*parent;parent=NULL;if(t)if(t->data==n)printf(“noparent!”);//n是根結(jié)點(diǎn)，無(wú)雙親else{front=0;//初始化隊(duì)列 rear=1; que[1]=t;//根結(jié)點(diǎn)進(jìn)隊(duì) do {front=front%maxsize+1; t=que[front]; if((t->lchild->data==n)||(t->rchild->data==n))//結(jié)點(diǎn)n有雙親 {parent=t; front=rear; printf(“parent”,t->data);} else {if(t->lchild!=NULL)//左子樹的根結(jié)點(diǎn)入隊(duì) {rear=rear%maxsize+1; que[rear]=t->lchild;} if(t->rchild!=NULL)//右子樹的根結(jié)點(diǎn)入隊(duì) {rear=rear%maxsize+1; que[rear]=t->rchild;}}}while(rear==front);//隊(duì)空時(shí)結(jié)束 if(parent==NULL) printf(“結(jié)點(diǎn)不存在”);}}

習(xí)題6一、單項(xiàng)選擇題1.在一種具有n個(gè)頂點(diǎn)的有向圖中，若所有頂點(diǎn)的出度數(shù)之和為s，則所有頂點(diǎn)的入度數(shù)之和為()。A.s B.s-1 C.s+1 2.在一種具有n個(gè)頂點(diǎn)的有向圖中，若所有頂點(diǎn)的出度數(shù)之和為s，則所有頂點(diǎn)的度數(shù)之和為()。A.s B.s-1 C.s+1 3.在一種具有n個(gè)頂點(diǎn)的無(wú)向圖中，若具有e條邊，則所有頂點(diǎn)的度數(shù)之和為()。A.n B.e C.n+e D.2e4.在一種具有n個(gè)頂點(diǎn)的無(wú)向完全圖中，所含的邊數(shù)為()。A.n B.n(n-1) C.n(n-1)/2 D.n(n+1)/25.在一種具有n個(gè)頂點(diǎn)的有向完全圖中，所含的邊數(shù)為()。A.n B.n(n-1) C.n(n-1)/2 D.n(n+1)/26.在一種無(wú)向圖中，若兩頂點(diǎn)之間的途徑長(zhǎng)度為k，則該途徑上的頂點(diǎn)數(shù)為()。A.k B.k+1 C.k+2 D.2k7.對(duì)于一種具有n個(gè)頂點(diǎn)的無(wú)向連通圖，它包括的連通分量的個(gè)數(shù)為()。A.0 B.1 C.n D.n+18.若一種圖中包具有k個(gè)連通分量，若要按照深度優(yōu)先搜索的措施訪問所有頂點(diǎn)，則必須調(diào)用()次深度優(yōu)先搜索遍歷的算法。A.k B.1 C.k-1 D.k+19.若要把n個(gè)頂點(diǎn)連接為一種連通圖，則至少需要()條邊。A.n B.n+1 C.n-1 D.2n10.在一種具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖的鄰接矩陣中，表達(dá)邊存在的元素（又稱為有效元素）的個(gè)數(shù)為()。A.n B.ne C.e D.2e11.在一種具有n個(gè)頂點(diǎn)和e條邊的有向圖的鄰接矩陣中，表達(dá)邊存在的元素個(gè)數(shù)為()。A.n B.ne C.e D.2e12.在一種具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖的鄰接表中，邊結(jié)點(diǎn)的個(gè)數(shù)為()。A.n B.ne C.e D.2e13.在一種具有n個(gè)頂點(diǎn)和e條邊的有向圖的鄰接表中，保留頂點(diǎn)單鏈表的表頭指針向量的大小至少為()。A.n B.2n C.e D.2e14.在一種無(wú)權(quán)圖的鄰接表表達(dá)中，每個(gè)邊結(jié)點(diǎn)至少包括()域。A.1 B.2 C.3 D.15.對(duì)于一種有向圖，若一種頂點(diǎn)的度為k1，出度為k2，則對(duì)應(yīng)鄰接表中該頂點(diǎn)單鏈表中的邊結(jié)點(diǎn)數(shù)為()。A.k1 B.k2 C.k1-k2 D.k1+k216.對(duì)于一種有向圖，若一種頂點(diǎn)的度為k1，出度為k2，則對(duì)應(yīng)逆鄰接表中該頂點(diǎn)單鏈表中的邊結(jié)點(diǎn)數(shù)為()。A.k1 B.k2 C.k1-k2 D.k1+k217.對(duì)于一種無(wú)向圖，下面()種說法是對(duì)的的。A.每個(gè)頂點(diǎn)的入度等于出度 B.每個(gè)頂點(diǎn)的度等于其入度與出度之和C.每個(gè)頂點(diǎn)的入度為0 D.每個(gè)頂點(diǎn)的出度為018.在一種有向圖的鄰接表中，每個(gè)頂點(diǎn)單鏈表中結(jié)點(diǎn)的個(gè)數(shù)等于該頂點(diǎn)的()。A.出邊數(shù) B.入邊數(shù) C.度數(shù) D.度數(shù)減119.若一種圖的邊集為{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，則從頂點(diǎn)A開始對(duì)該圖進(jìn)行深度優(yōu)先搜索，得到的頂點(diǎn)序列也許為()。A.A,B,C,F,D,E B.A,C,F,D,E,BC.A,B,D,C,F,E D.A,B,D,F,E,C20.若一種圖的邊集為{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，則從頂點(diǎn)A開始對(duì)該圖進(jìn)行廣度優(yōu)先搜索，得到的頂點(diǎn)序列也許為()。A.A,B,C,D,E,F B.A,B,C,F,D,EC.A,B,D,C,E,F D.A,C,B,F,D,E21.若一種圖的邊集為{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>}，則從頂點(diǎn)1開始對(duì)該圖進(jìn)行深度優(yōu)先搜索，得到的頂點(diǎn)序列也許為()。A.1,2,5,4,3 B.1,2,3,4,5C.1,2,5,3,4 D.1,4,3,2,522.若一種圖的邊集為{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>}，則從頂點(diǎn)1開始對(duì)該圖進(jìn)行廣度優(yōu)先搜索，得到的頂點(diǎn)序列也許為()。A.1,2,3,4,5 B.1,2,4,3,5C.1,2,4,5,3 D.1,4,2,5,323.由一種具有n個(gè)頂點(diǎn)的連通圖生成的最小生成樹中，具有()條邊。A.n B.n-1 C.n+1 D.2n24.已知一種有向圖的邊集為{<a,b>,<a,c>,<a,d>,<b,d>,<b,e>,<d,e>}，則由該圖產(chǎn)生的一種也許的拓?fù)湫蛄袨?)。A.a,b,c,d,e B.a,b,d,e,b C.a,c,b,e,d D.a,c,d,b,e二、填空題1.在一種圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的________倍。2.在一種具有n個(gè)頂點(diǎn)的無(wú)向完全圖中，包具有________條邊，在一種具有n個(gè)頂點(diǎn)的有向完全圖中，包具有________條邊。3.假定一種有向圖的頂點(diǎn)集為{a,b,c,d,e,