數(shù)據(jù)結構 習題答案

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

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

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

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

A．所有 B．二分之一

C．三分之一

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

A．插入

B．刪除

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

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

A．O(1)

B．O(n)

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

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

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

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

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