數(shù)據(jù)結(jié)構(gòu)試題集(包含答案-完整版)

第一章 概論一、選擇題1、研究數(shù)據(jù)結(jié)構(gòu)就是研究（ D ）。A. 數(shù)據(jù)的邏輯結(jié)構(gòu)C. 數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)

B.數(shù)據(jù)的存儲結(jié)構(gòu)D.數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其基本操作2、算法分析的兩個主要方面是（ A ）。A. 空間復雜度和時間復雜度 B.正確性和簡單性檔性 D. 數(shù)據(jù)復雜性和程序復雜性3、具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是（ D ）。A. 圖 B. 樹 C.廣義表 D. 棧

C. 可讀性和文4、計算機中的算法指的是解決某一個問題的有限運算序列，它必須具備輸入、輸出、（

B

）等5個特性。A. 可執(zhí)行性、可移植性和可擴充性

B. 可執(zhí)行性、有窮性和確定性C. 確定性、有窮性和穩(wěn)定性 D. 易讀性、穩(wěn)定性和確定性5、下面程序段的時間復雜度是（ C ）。for(i=0;i<m;i++)for(j=0;j<n;j++)a[i][j]=i*j;2B.O(n2C.O(m*n)D.O(m+n)A.O(m))6、算法是（D）。A.計算機程序B.解決問題的計算方法C.排序算法解決問題的有限運算序列7、某算法的語句執(zhí)行頻度為（2C）。3n+nlog2n+n+8）,其時間復雜度表示（A.O(n)B.O(nlog2n)2D.O(log2n)C.O(n)8、下面程序段的時間復雜度為（C）。i=1;while(i<=n)i=i*3;3A.O(n)B.O(3n)C.O(log3n))D.O(n9、數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的數(shù)據(jù)元素以及它們之間的（B）和運算等的學科。A.結(jié)構(gòu)B.關(guān)系C.運算D.算法10、下面程序段的時間復雜度是（A）。i=s=0;while(s<n){i++;s+=i;根號（n）}23A.O(n)B.O(nC.O(log2n))D.O(n)11、抽象數(shù)據(jù)類型的三個組成部分分別為（A）。A.數(shù)據(jù)對象、數(shù)據(jù)關(guān)系和基本操作B.數(shù)據(jù)元素、邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)C.數(shù)據(jù)項、數(shù)據(jù)元素和數(shù)據(jù)類型 D.數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型12、通常從正確性、易讀性、健壯性、高效性等 4個方面評價算法的質(zhì)量，以下解釋錯誤的是（ D ）。正確性算法應(yīng)能正確地實現(xiàn)預定的功能易讀性算法應(yīng)易于閱讀和理解，以便調(diào)試、修改和擴充健壯性當環(huán)境發(fā)生變化時，算法能適當?shù)刈龀龇磻?yīng)或進行處理，不會產(chǎn)生不需要的運行結(jié)果高效性即達到所需要的時間性能13、下列程序段的時間復雜度為（ B ）。x=n;y=0;while(x>=(y+1)*(y+1))y=y+1;A.O(n)B.O(n)C.O(1)D.O(n2)二、填空題1、程序段“i=1;while(i<=n)i=i*2;”的時間復雜度為。2、數(shù)據(jù)結(jié)構(gòu)的四種基本類型中，樹形結(jié)構(gòu)的元素是一對多關(guān)系。三、綜合題23N按增長率由小到大排1、將數(shù)量級O(1),O(N),O(N),O(N),O(NLOG2N),O(LOG2N),O(2)序。23N答案：O(1)O(log2N)O(N)O(Nlog2N)O(N)O(N)O(2)第二章線性表一、選擇題1、若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素算法的時間復雜度（）。2A.O(log2n)B.O(1)C.O(n)D.O(n)2、若一個線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素，則采用（）存儲方式最節(jié)省時間。A.順序表B.單鏈表C.雙鏈表D.單循環(huán)鏈表3、具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是（）。A.圖B.樹C.廣義表D.棧4、在一個長度為n的順序表中，在第i個元素之前插入一個新元素時，需向后移動（）個元素。A.n-iB.n-i+1C.n-i-1D.i5、非空的循環(huán)單鏈表head的尾結(jié)點p滿足（）。A.p->next==headB.p->next==NULLC.p==NULLD.p==head6、鏈表不具有的特點是（ ）。A.可隨機訪問任一元素 B.插入刪除不需要移動元素C.不必事先估計存儲空間 D.所需空間與線性表長度成正比7、在雙向循環(huán)鏈表中，在 p指針所指的結(jié)點后插入一個指針 q所指向的新結(jié)點，修改指針的操作是（ ）。p->next=q;q->prior=p;p->next->prior=q;q->next=q;p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;D.q->next=p->next;q->prior=p;p->next=q;p->next=q;8、線性表采用鏈式存儲時，結(jié)點的存儲地址（）。A.必須是連續(xù)的B.必須是不連續(xù)的C.連續(xù)與否均可D.和頭結(jié)點的存儲地址相連續(xù)9、在一個長度為n的順序表中刪除第i個元素，需要向前移動（）個元素。A.n-iB.n-i+1C.n-i-1D.i+110、線性表是n個（）的有限序列。A.表元素B.字符C.數(shù)據(jù)元素D.數(shù)據(jù)項11、從表中任一結(jié)點出發(fā)，都能掃描整個表的是（）。A.單鏈表B.順序表C.循環(huán)鏈表D.靜態(tài)鏈表12、在具有n個結(jié)點的單鏈表上查找值為x的元素時，其時間復雜度為（）。A.O(n)B.O(1)C.O(n2D.O(n-1))13、線性表L=(a1,a2,??,an)，下列說法正確的是（）。每個元素都有一個直接前驅(qū)和一個直接后繼線性表中至少要有一個元素表中諸元素的排列順序必須是由小到大或由大到小除第一個和最后一個元素外，其余每個元素都由一個且僅有一個直接前驅(qū)和直接后繼14、一個順序表的第一個元素的存儲地址是 90，每個元素的長度為 2，則第6個元素的存儲地址是（ ）。A.98B.100C.102D.10615、在線性表的下列存儲結(jié)構(gòu)中，讀取元素花費的時間最少的是（）。A.單鏈表B.雙鏈表C.循環(huán)鏈表D.順序表16、在一個單鏈表中，若刪除p所指向結(jié)點的后續(xù)結(jié)點，則執(zhí)行（）。p->next=p->next->next;p=p->next;p->next=p->next->next;p=p->next;p=p->next->next;17、將長度為n的單鏈表連接在長度為m的單鏈表之后的算法的時間復雜度為（）。A.O(1)B.O(n)C.O(m)D.O(m+n)18、線性表的順序存儲結(jié)構(gòu)是一種（）存儲結(jié)構(gòu)。A.隨機存取B.順序存取C.索引存取D.散列存取19、順序表中，插入一個元素所需移動的元素平均數(shù)是（）。A.(n-1)/2B.nC.n+1D.(n+1)/210、循環(huán)鏈表的主要優(yōu)點是（ ）。A.不再需要頭指針 B. 已知某結(jié)點位置后能容易找到其直接前驅(qū)在進行插入、刪除運算時能保證鏈表不斷開在表中任一結(jié)點出發(fā)都能掃描整個鏈表11、不帶頭結(jié)點的單鏈表 head為空的判定條件是（

A ）。A.head==NULL

B.head->next==NULLC.head->next==head

D.head!=NULL答案B是帶頭結(jié)點的12、在下列對順序表進行的操作中，算法時間復雜度為

O(1)

的是（

）。A. 訪問第i個元素的前驅(qū)（ 1<i n） B. 在第i個元素之后插入一個新元素(1 i n)C. 刪除第i個元素(1 i n) D.對順序表中元素進行排序答案是A.假設(shè)順序表

L,

長度為

n，求第

i

個節(jié)點

L[i],

直接前驅(qū)

L[i-1],

因此為

O（1）答案答案答案

BCD

需要移動 n-i+1 個節(jié)點，因此為也需要移動 n-i 個節(jié)點根據(jù)排序方法不同最慢 O(n^2)

O(n)，最快

O(nlogn)13、已知指針p和q分別指向某單鏈表中第一個結(jié)點和最后一個結(jié)點。假設(shè)指針另一個單鏈表中某個結(jié)點， 則在s所指結(jié)點之后插入上述鏈表應(yīng)執(zhí)行的語句為A.q->next=s->next ；s->next=p ；B.s->next=p ；q->next=s->next ；C.p->next=s->next ；s->next=q ；D.s->next=q ；p->next=s->next ；

s指向（ ）。14、在以下的敘述中，正確的是（ ）。線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)B.線性表的順序存儲結(jié)構(gòu)適用于頻繁插入 /刪除數(shù)據(jù)元素的情況C.線性表的鏈表存儲結(jié)構(gòu)適用于頻繁插入 /刪除數(shù)據(jù)元素的情況線性表的鏈表存儲結(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)15、在表長為 n的順序表中，當在任何位置刪除一個元素的概率相同時，刪除一個元素所需移動的平均個數(shù)為（ ）。A.(n-1)/2

B.n/2

C.(n+1)/2

D.n16、在一個單鏈表中，已知入一個結(jié)點 s，則執(zhí)行（

q所指結(jié)點是）。

p所指結(jié)點的前驅(qū)結(jié)點，若在

q和

p之間插A.s->next=p->next;p->next=s;p->next=s->next;s->next=p;q->next=s;s->next=p;p->next=s;s->next=q;17、在單鏈表中，指針p指向元素為x的結(jié)點，實現(xiàn)刪除x的后繼的語句是（）。A.p=p->next;B.p->next=p->next->next;C.p->next=p;D.p=p->next->next;18、在頭指針為head且表長大于1的單循環(huán)鏈表中，指針p指向表中某個結(jié)點，若p->next->next==head，則（）。A.p指向頭結(jié)點B.p指向尾結(jié)點C.p的直接后繼是頭結(jié)點D.p的直接后繼是尾結(jié)點二、填空題1、設(shè)單鏈表的結(jié)點結(jié)構(gòu)為（ data,next ）。已知指針 p指向單鏈表中的結(jié)點， q指向新結(jié) 點 ， 欲 將 q 插 入 到 p 結(jié) 點 之 后 ， 則 需 要 執(zhí) 行 的 語句： ； 。答案：q->next=p->next p->next=q2、線性表的邏輯結(jié)構(gòu)是 ，其所含元素的個數(shù)稱為線性表的答案：線性結(jié)構(gòu) 長度3、寫出帶頭結(jié)點的雙向循環(huán)鏈表 L為空表的條件

。

。答案：L->prior==L->next==L4、帶頭結(jié)點的單鏈表 head

為空的條件是

。答案：head->next==NULL5、在一個單鏈表中刪除 p所指結(jié)點的后繼結(jié)點時，應(yīng)執(zhí)行以下操作：q=p->next;p->next=_q->next___;三、判斷題1、單鏈表不是一種隨機存儲結(jié)構(gòu)。2、在具有頭結(jié)點的單鏈表中，頭指針指向鏈表的第一個數(shù)據(jù)結(jié)點。3、用循環(huán)單鏈表表示的鏈隊列中，可以不設(shè)隊頭指針，僅在隊尾設(shè)置隊尾指針。4、順序存儲方式只能用于存儲線性結(jié)構(gòu)。5、在線性表的順序存儲結(jié)構(gòu)中，邏輯上相鄰的兩個元素但是在物理位置上不一定是相鄰的。6、鏈式存儲的線性表可以隨機存取。 X四、程序分析填空題1、函數(shù)GetElem實現(xiàn)返回單鏈表的第 i個元素，請在空格處將算法補充完整。intGetElem(LinkListL,inti,Elemtype*e){LinkListp ；intjp=L->next;j=1;while(p&&j<i){(1) ;++j;

；}if(!p||j>i)returnERROR;*e= (2) ;returnOK;}答案：(1)p=p->next (2)p->data2、函數(shù)實現(xiàn)單鏈表的插入算法，請在空格處將算法補充完整。intListInsert(LinkListL,inti,ElemTypee){LNode*p,*s;intj;p=L;j=0;while((p!=NULL)&&(j<i-1)){ p=p->next;j++;}if(p==NULL||j>i-1)returnERROR;s=(LNode*)malloc(sizeof(LNode));s->data=e;(1) ;(2) ;returnOK;}/*ListInsert*/答案：(1)s->next=p->next (2)p->next=s3、函數(shù)ListDelete_sq 實現(xiàn)順序表刪除算法，請在空格處將算法補充完整。intListDelete_sq(Sqlist*L,inti){intk;if(i<1||i>L->length)returnERROR;for(k=i-1;k<L->length-1;k++)L->slist[k]=（1）;（2） ;returnOK;}答案：（1）L->slist[k+1] （2）--L->Length4、函數(shù)實現(xiàn)單鏈表的刪除算法，請在空格處將算法補充完整。intListDelete(LinkListL,inti,ElemType*s){LNode*p,*q;intj;p=L;j=0;while(( （1） )&&(j<i-1)){p=p->next;j++;}if(p->next==NULL||j>i-1)returnERROR;q=p->next;（2） ;*s=q->data;free(q);returnOK;}/*listDelete*/答案：(1)p->next!=NULL (2)p->next=q->next5、寫出算法的功能。intL(head){node*head;intn=0;node*p;p=head;while(p!=NULL){p=p->next;n++;}return(n);}答案：求單鏈表 head的長度五、綜合題1、編寫算法，實現(xiàn)帶頭結(jié)點單鏈表的逆置算法。答案：voidinvent(Lnode*head){Lnode*p,*q;if(!head->next)returnERROR;p=head->next;q=p->next;p->next=NULL;while(q){p=q;q=q->next;p->next=head->next;head->next=p;}}2、有兩個循環(huán)鏈表， 鏈頭指針分別為 L1和L2，要求寫出算法將 L2鏈表鏈到 L1鏈表之后，且連接后仍保持循環(huán)鏈表形式。答案：voidmerge(Lnode*L1,Lnode*L2){Lnode*p,*q;while(p->next!=L1)p=p->next;while(q->next!=L2)q=q->next;q->next=L1;p->next=L2;}3、設(shè)一個帶頭結(jié)點的單向鏈表的頭指針為 head，設(shè)計算法，將鏈表的記錄， 按照data域的值遞增排序。答案：voidassending(Lnode*head){Lnode*p,*q,*r,*s;p=head->next;q=p->next;p->next=NULL;while(q){r=q;q=q->next;if(r->data<=p->data){r->next=p;head->next=r;p=r;}else{while(!p&&r->data>p->data){s=p;p=p->next;}r->next=p;s->next=r;}p=head->next;}}4、編寫算法 ,將一個頭指針為 head不帶頭結(jié)點的單鏈表改造為一個單向循環(huán)鏈表，并分析算法的時間復雜度。答案：voidlinklist_c(Lnode*head){Lnode*p;p=head;if(!p)returnERROR;while(p->next!=NULL)p=p->next;p->next=head;}設(shè)單鏈表的長度（數(shù)據(jù)結(jié)點數(shù)）為N，則該算法的時間主要花費在查找鏈表最后一個結(jié)點上（算法中的while循環(huán)），所以該算法的時間復雜度為O（N）。5、已知head為帶頭結(jié)點的單循環(huán)鏈表的頭指針，鏈表中的數(shù)據(jù)元素依次為（a1，a2,a3,a4,?,an）,A為指向空的順序表的指針。閱讀以下程序段，并回答問題：（1）寫出執(zhí)行下列程序段后的順序表A中的數(shù)據(jù)元素；（2）簡要敘述該程序段的功能。if(head->next!=head){p=head->next;A->length=0;while(p->next!=head){p=p->next;A->data[A->length++]=p->data;if(p->next!=head)p=p->next;}}答案：(1)(a2, a4, ?,) (2) 將循環(huán)單鏈表中偶數(shù)結(jié)點位置的元素值寫入順序表A6、設(shè)順序表 va中的數(shù)據(jù)元數(shù)遞增有序。試寫一算法，將 x插入到順序表的適當位置上，以保持該表的有序性。答案：voidInsert_sq(Sqlistva[],ElemTypex){inti,j,n;n=length(va[]);if(x>=va[i])va[n]=x;else{i=0;while(x>va[i])i++;for(j=n-1;j>=I;j--)va[j+1]=va[j];va[i]=x;}n++;}7、假設(shè)線性表采用順序存儲結(jié)構(gòu)，表中元素值為整型。閱讀算法 f2，設(shè)順序表L=(3,7,3,2,1,1,8,7,3), 寫出執(zhí)行算法 f2后的線性表 L的數(shù)據(jù)元素，并描述該算法的功能。voidf2(SeqList*L){inti,j,k;k=0;for(i=0;i<L->length;i++){for(j=0;j<k&&L->data[i]!=L->data[j];j++);if(j==k){if(k!=i)L->data[k]=L->data[i];k++;}}L->length=k;}答案：(3,7,2,1,8) 刪除順序表中重復的元素8、已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試寫一算法，刪除表中所有大于x且小于y的元素（若表中存在這樣的元素）同時釋放被刪除結(jié)點空間。答案：voidDelete_list(Lnode*head,ElemTypex,ElemTypey){Lnode*p,*q;if(!head)returnERROR;p=head;q=p;while(!p){if(p->data>x)&&(p->data<y)}i++;if(p==head){head=p->next;free(p);p=head;q=p;}else{q->next=p->next;free(p);p=q->next;}else{q=p;p=p->next;}}}9、在帶頭結(jié)點的循環(huán)鏈表 L中，結(jié)點的數(shù)據(jù)元素為整型，且按值遞增有序存放。給定兩個整數(shù)a和b，且a<b，編寫算法刪除鏈表L中元素值大于a且小于b的所有結(jié)點。第三章 棧和隊列一、選擇題1、一個棧的輸入序列為：

a，b，c，d，e，則棧的不可能輸出的序列是（

）。A.a,b,c,d,e

B.d,e,c,b,aC.d,c,e,a,b

D.e,d,c,b,a2、判斷一個循環(huán)隊列

Q（最多

n個元素）為滿的條件是（

）。A.Q->rear==Q->front

B.Q->rear==Q->front+1C.Q->front==(Q->rear+1)%n

D.Q->front==(Q->rear-1)%n3、設(shè)計一個判別表達式中括號是否配對的算法，采用（A.順序表 B. 鏈表 C.隊列4、帶頭結(jié)點的單鏈表 head為空的判定條件是（ ）。

）數(shù)據(jù)結(jié)構(gòu)最佳。D.棧A.head==NULL

B.head->next==NULLC.head->next!=NULL

D.head!=NULL5、一個棧的輸入序列為：

1,2,3,4

，則棧的不可能輸出的序列是（

）。A.1243

B.2134

C.1432

D.4312

E.32146、若用一個大小為 6的數(shù)組來實現(xiàn)循環(huán)隊列，且當從隊列中刪除一個元素，再加入兩個元素后， rearA.1和5 B.2和4

rear和front 的值分別為 0，3。當和front 的值分別為（ ）。C.4和2 D.5和17、隊列的插入操作是在（

）。A. 隊尾

B.隊頭

C.隊列任意位置

D. 隊頭元素后8、循環(huán)隊列的隊頭和隊尾指針分別為 front 和rear，則判斷循環(huán)隊列為空的條件是（ ）。A.front==rearB.front==0C.rear==0D.front=rear+19、一個順序棧S，其棧頂指針為top，則將元素e入棧的操作是（）。A.*S->top=e;S->top++;B.S->top++;*S->top=e;C.*S->top=eD.S->top=e;10、表達式a*(b+c)-d的后綴表達式是（）。A.abcd+-B.abc+*d-C.abc*+d-D.-+*abcd11、將遞歸算法轉(zhuǎn)換成對應(yīng)的非遞歸算法時，通常需要使用（）來保存中間結(jié)果。A.隊列B.棧C.鏈表D.樹12、棧的插入和刪除操作在（）。A.棧底B.棧頂C.任意位置D.指定位置13、五節(jié)車廂以編號1，2，3，4，5順序進入鐵路調(diào)度站（棧），可以得到（）的編組。A.3，4，5，1，2B.2，4，1，3，5C.3，5，4，2，1D.1，3，5，2，414、判定一個順序棧S（?？臻g大小為n）為空的條件是（）。A.S->top==0B.S->top!=0C.S->top==nD.S->top!=n15、在一個鏈隊列中，front和rear分別為頭指針和尾指針，則插入一個結(jié)點s的操作為（）。A.front=front->nextB.s->next=rear;rear=sC.rear->next=s;rear=s;D.s->next=front;front=s;16、一個隊列的入隊序列是1，2，3，4，則隊列的出隊序列是（）。A.1，2，3，4B.4，3，2，1C.1，4，3，2D.3，4，1，217、依次在初始為空的隊列中插入元素a,b,c,d以后，緊接著做了兩次刪除操作，此時的隊頭元素是（）。A.aB.bC.cD.d18、正常情況下，刪除非空的順序存儲結(jié)構(gòu)的堆棧的棧頂元素，棧頂指針top的變化是（）。A.top不變B.top=0C.top=top+1D.top=top-119、判斷一個循環(huán)隊列Q（空間大小為M）為空的條件是（A）。A.Q->front==Q->rearB.Q->rear-Q->front-1==MC.Q->front+1=Q->rearD.Q->rear+1=Q->front20、設(shè)計一個判別表達式中左右括號是否配對出現(xiàn)的算法，采用（C）數(shù)據(jù)結(jié)構(gòu)最佳。A.線性表的順序存儲結(jié)構(gòu)B.隊列C.棧D.線性表的鏈式存儲結(jié)構(gòu)21、當用大小為N的數(shù)組存儲順序循環(huán)隊列時，該隊列的最大長度為（C）。A.NB.N+1C.N-1D.N-222、隊列的刪除操作是在（A）。A.隊首B.隊尾C.隊前D.隊后23、若讓元素1，2，3依次進棧，則出棧次序不可能是（C）。A.3，2，1B.2，1，3C.3，1，2D.1，3，224、循環(huán)隊列用數(shù)組A[0，m-1]存放其元素值，已知其頭尾指針分別是front和rear，則當前隊列中的元素個數(shù)是（A）。A.(rear-front+m)%mB.rear-front+1C.rear-front-1D.rear-front25、在解決計算機主機和打印機之間速度不匹配問題時，通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則從該緩沖區(qū)中取走數(shù)據(jù)打印。該緩沖區(qū)應(yīng)該是一個（B）結(jié)構(gòu)。A.堆棧B.隊列C.數(shù)組D.線性表26、棧和隊列都是（C）。A.鏈式存儲的線性結(jié)構(gòu)B.鏈式存儲的非線性結(jié)構(gòu)C.限制存取點的線性結(jié)構(gòu)D.限制存取點的非線性結(jié)構(gòu)27、在一個鏈隊列中，假定front和rear分別為隊頭指針和隊尾指針，刪除一個結(jié)點的操作是（A）。A.front=front->nextB.rear=rear->nextC.rear->next=frontD.front->next=rear28、隊和棧的主要區(qū)別是（D）。A.邏輯結(jié)構(gòu)不同B.存儲結(jié)構(gòu)不同C.所包含的運算個數(shù)不同D.限定插入和刪除的位置不同二、填空題1、設(shè)棧S和隊列Q的初始狀態(tài)為空，元素 e1,e2,e3,e4,e5,e6 依次通過棧S，一個元素出棧后即進入隊列 Q，若6個元素出隊的序列是 e2,e4,e3,e6,e5,e1 ，則棧的容量至少應(yīng)該是 。答案：32、一個循環(huán)隊列 Q的存儲空間大小為 M,其隊頭和隊尾指針分別為 front 和rear，則循環(huán)隊列中元素的個數(shù)為： 。答案：(rear-front+M)%M3、在具有n個元素的循環(huán)隊列中，隊滿時具有 個元素。答案：n-14、設(shè)循環(huán)隊列的容量為 70，現(xiàn)經(jīng)過一系列的入隊和出隊操作后，11，則隊列中元素的個數(shù)為 。

front

為20，rear

為答案：

615、已知循環(huán)隊列的存儲空間大小為 20，且當前隊列的頭指針和尾指針的值分別為 8和3，且該隊列的當前的長度為 ____15___。三、判斷題1、棧和隊列都是受限的線性結(jié)構(gòu)。2、在單鏈表中，要訪問某個結(jié)點，只要知道該結(jié)點的地址即可；因此，單鏈表是一種隨機存取結(jié)構(gòu)。3、以鏈表作為棧的存儲結(jié)構(gòu)，出棧操作必須判別?？盏那闆r。四、程序分析填空題1、已知棧的基本操作函數(shù)：intInitStack(SqStack*S);//intStackEmpty(SqStack*S);//intPush(SqStack*S,ElemTypee);//intPop(SqStack*S,ElemType*e);//

構(gòu)造空棧判斷?？杖霔３鰲：瘮?shù)conversion 實現(xiàn)十進制數(shù)轉(zhuǎn)換為八進制數(shù)，請將函數(shù)補充完整。voidconversion(){InitStack(S);scanf(“%d”,&N);while(N){（1） ;N=N/8;}while(（2）){Pop(S,&e);printf( “%d”,e);}}//conversion答案：（1）Push(S,N%8) （2）!StackEmpty(S)2、寫出算法的功能。intfunction(SqQueue*Q,ElemType*e){if(Q->front==Q->rear)returnERROR;*e=Q->base[Q->front];Q->front=(Q->front+1)%MAXSIZE;returnOK;}若循環(huán)隊列非空，隊頭元素出隊列且返回其值，否則返回空元素。3、閱讀算法 f2,并回答下列問題：1）設(shè)隊列Q=（1，3，5，2，4，6）。寫出執(zhí)行算法f2后的隊列Q;2）簡述算法f2的功能。voidf2(Queue*Q){DataType e;if(!QueueEmpty(Q)){e=DeQueue(Q);f2(Q);EnQueue(Q,e);}}答案：（1）6,4,2,5,3,1 （2）將隊列倒置五、綜合題1、假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個指針指向隊尾結(jié)點，但不設(shè)頭指針，請寫出相應(yīng)的入隊列算法（用函數(shù)實現(xiàn)） 。rear答案：voidEnQueue(Lnode*rear,ElemTypee){Lnode*new;New=(Lnode*)malloc(sizeof(Lnode));If(!new)returnERROR;new->data=e;new->next=rear->next;rear->next=new;rear=new;}2、已知Q是一個非空隊列，S是一個空棧。編寫算法，僅用隊列和棧的ADT函數(shù)和少量工作變量，將隊列Q的所有元素逆置。棧的ADT函數(shù)有：voidmakeEmpty(SqStacks);

置空棧voidpush(SqStacks,ElemTypee); 元素e入棧ElemTypepop(SqStacks); 出棧，返回棧頂元素intisEmpty(SqStacks); 判斷?？贞犃械?/p>

ADT函數(shù)有：voidenQueue(Queueq,ElemTypee); 元素e入隊ElemTypedeQueue(Queueq); 出隊，返回隊頭元素intisEmpty(Queueq); 判斷隊空答案：voidQueueInvent(Queueq){ElemTypex;makeEmpty(SqStacks);while(!isEmpty(Queueq)){x=deQueue(Queueq);push(SqStacks,ElemTypex);}while(!isEmpty(SqStacks)){x=pop(SqStacks);enQueue(Queueq,ElemTypex);}}3、對于一個棧，給出輸入項

A,B,C,D

，如果輸入項序列為

A,B,C,D

，試給出全部可能的輸出序列。 4,1,4,1,2,1,1答案：出棧的可能序列：ABCDABDCACDB

ACBD

ADCB

BACD

BADC

BCAD

BCDABDCACBDA CBAD CDBA

DCBA第四章

串一、選擇題1、設(shè)有兩個串 S1和S2，求串S2在S1中首次出現(xiàn)位置的運算稱作（A. 連接 B.求子串 C.模式匹配2、已知串S=’aaab’，則next數(shù)組值為（ A ）。

C ）。D.判斷子串A.0123

B.1123

C.1231

D.12113、串與普通的線性表相比較，它的特殊性體現(xiàn)在（A.順序的存儲結(jié)構(gòu) B. 鏈式存儲結(jié)構(gòu)

C ）。

C. 數(shù)據(jù)元素是一個字符4、設(shè)串長為A.O(m)

D.數(shù)據(jù)元素任意n，模式串長為 m，則KMP算法所需的附加空間為（ AB.O(n) C.O(m*n) D.O(nlog

）。

2m)5、空串和空格串（

B ）。A. 相同

B.

不相同

C. 可能相同

D.

無法確定6、與線性表相比，串的插入和刪除操作的特點是（A.通常以串整體作為操作對象 B.C.算法的時間復雜度較高 D.7、設(shè)SUBSTR(S,i,k) 是求S中從第i個字符開始的連續(xù)對于S=’Beijing&Nanjing ’，SUBSTR(S,4,5)=（B

B ）。需要更多的輔助空間涉及移動的元素更多k個字符組成的子串的操作，則）。A.‘ijing

’

B. ‘jing&

’

C.‘ingNa

’

D.‘ing&N’二、判斷題（×）1、造成簡單模式匹配算法BF算法執(zhí)行效率低的原因是有回溯存在。（√ ）2、KMP算法的最大特點是指示主串的指針不需要回溯。（√ ）3、完全二叉樹某結(jié)點有右子樹，則必然有左子樹。三、填空題1、求子串在主串中首次出現(xiàn)的位置的運算稱為 模式匹配 。2、設(shè)s=’I︺AM︺A︺TEACHER’,其長度是__14__。3、兩個串相等的充分必要條件是兩個串的長度相等且同 。四、程序填空題1、函數(shù)kmp實現(xiàn)串的模式匹配，請在空格處將算法補充完整。intkmp(sqstring*s,sqstring*t,intstart,intnext[]){inti=start-1,j=0;while(i<s->len&&j<t->len)if(j==-1||s->data[i]==t->data[j]){i++;j++;

對應(yīng)位置字符相}elsej=

next[j]

;if(j>=t->len)return(

i=t->len+1

);elsereturn(-1);}2、函數(shù)實現(xiàn)串的模式匹配算法，請在空格處將算法補充完整。intindex_bf(sqstring*s,sqstring*t,intstart){inti=start-1,j=0;while(i<s->len&&j<t->len)if(s->data[i]==t->data[j]){i++;j++;}else{i= i-j+1 ;j=0;}if(j>=t->len)return i-t->len+1 ;elsereturn-1;}}/*listDelete*/3、寫出下面算法的功能。intfunction(SqString*s1,SqString*s2){inti;for(i=0;i<s1->length&&i<s1->length;i++)if(s->data[i]!=s2->data[i])returns1->data[i]-s2->data[i];returns1->length-s2->length;}答案：.串比較算法4、寫出算法的功能。intfun(sqstring*s,sqstring*t,intstart){inti=start-1,j=0;while(i<s->len&&j<t->len)if(s->data[i]==t->data[j]){i++;j++;}else{i=i-j+1;j=0;}if(j>=t->len)returni-t->len+1;elsereturn-1;}答案：串的模式匹配算法第五章

數(shù)組和廣義表一、選擇題1、設(shè)廣義表 L=((aA.1和12、廣義表((a),a)

，b，c))，則B.1的表尾是（ B

L的長度和深度分別為（和3 C.1和2）。

C ）。

D.2

和3A.a

B.(a)

C.()

D.((a))3、稀疏矩陣的常見壓縮存儲方法有（ C ）兩種。A. 二維數(shù)組和三維數(shù)組 B.三元組和散列表 C. 三元組和十字鏈表 D.散列表和十字鏈表4、一個非空廣義表的表頭（ D ）。A. 不可能是子表 B. 只能是子表 C.只能是原子 D.可以是子表或原子5、數(shù)組A[0..5,0..6] 的每個元素占1000的內(nèi)存單元中，則元素 A[5][5]

5個字節(jié)，將其按列優(yōu)先次序存儲在起始地址為的地址是（A）。A.1175

B.1180

C.1205

D.12106、廣義表

G=(a,b(c,d,(e,f)),g)

的長度是（

A ）。A.3

B.4

C.7

D.87、采用稀疏矩陣的三元組表形式進行壓縮存儲，若要完成對三元組表進行轉(zhuǎn)置，只要將行和列對換，這種說法（ B ）。A. 正確 B.錯誤 C.無法確定 D. 以上均不對8、廣義表

(a,b,c)

的表尾是（

B

）。A.b,c

B.(b,c)

C.c

D.(c)9、常對數(shù)組進行兩種基本操作是（

C ）。A.建立和刪除

B. 索引和修改

C.查找和修改

D.查找與索引10、對一些特殊矩陣采用壓縮存儲的目的主要是為了（ D ）。A.表達變得簡單 B.對矩陣元素的存取變得簡單C.去掉矩陣中的多余元素 D.減少不必要的存儲空間的開銷11、設(shè)有一個10階的對稱矩陣 A，采用壓縮存儲方式，以行序為主存儲，元素，其存儲地址為 1，每元素占1個地址空間，則 a85的地址為（ B

a11為第一個）。A.13

B.33

C.18

D.4012、設(shè)矩陣A是一個對稱矩陣，為了節(jié)省存儲，將其下三角部分按行序存放在一維數(shù)組B[1,n(n-1)/2] 中，對下三角部分中任一元素 ai,j(i>=j) ，在一維數(shù)組B的下標位置k的值是（B）。A.i(i-1)/2+j-1B.i(i-1)/2+jC.i(i+1)/2+j-1D.i(i+1)/2+j13、廣義表A=((a),a)的表頭是（B）。A.aB.(a)C.bD.((a))14、稀疏矩陣一般的壓縮存儲方法有兩種，即（C）。A.二維數(shù)組和三維數(shù)組B.三元組和散列C.三元組和十字鏈表D.散列和十字鏈表15、假設(shè)以三元組表表示稀疏矩陣，則與如圖所示三元組表對應(yīng)的4×5的稀疏矩陣是（注：矩陣的行列下標均從1開始）（B）。0806008060A.700007000300000B.04005504000000008060080600000370000C.0000D.040375504000000016、以下有關(guān)廣義表的表述中，正確的是（A.由0個或多個原子或子表構(gòu)成的有限序列

A ）。

B. 至少有一個元素是子表C.不能遞歸定義17、對廣義表L=((a,b),((c,d),(e,f)))是（D ）。A.的 B.e

執(zhí)行C.(e)

D.不能為空表head(tail(head(tail(L)))) 操作的結(jié)果D.（e,f）二、判斷題（× ）1、廣義表中原子個數(shù)即為廣義表的長度。（×）2、一個稀疏矩陣采用三元組表示，若把三元組中有關(guān)行下標與列下標的值互換，并把mu和nu的值進行互換，則完成了矩陣轉(zhuǎn)置。（√ ）3、稀疏矩陣壓縮存儲后，必會失去隨機存取功能。（× ）4、廣義表的長度是指廣義表中括號嵌套的層數(shù)。（√ ）5、廣義表是一種多層次的數(shù)據(jù)結(jié)構(gòu)，其元素可以是單原子也可以是子表。三、填空題1、已知二維數(shù)組 A[m][n]一個 元 素的 存 儲Loc(A[0][0])+(i*N+j)*k____

采用行序為主方式存儲，每個元素占地址 是 LOC(A[0][0]) ， 則。

A[i][j]

k個存儲單元，并且第的 地 址是 ___2、廣義表運算式 HEAD(TAIL((a,b,c),(x,y,z)))3、二維數(shù)組，可以按照 列序為主和行序為主

的結(jié)果是：

(x,y,z)

。兩種不同的存儲方式。4、稀疏矩陣的壓縮存儲方式有：

三元組

和十字鏈表

。四、綜合題1、現(xiàn)有一個稀疏矩陣，請給出它的三元組表。0310100002100020答案：i j v1 2 31 3 12 1 13 2 23 3 14 3 -2第六章樹一、選擇題1、二叉樹的深度為k，則二叉樹最多有（C）個結(jié)點。A.2kk-1C.2kD.2k-1B.2-12、用順序存儲的方法，將完全二叉樹中所有結(jié)點按層逐個從左到右的順序存放在一維數(shù)組R[1..N]中，若結(jié)點R[i]有右孩子，則其右孩子是（B）。A.R[2i-1]B.R[2i+1]C.R[2i]D.R[2/i]3、設(shè)a,b為一棵二叉樹上的兩個結(jié)點，在中序遍歷時，a在b前面的條件是（B）。A.a在b的右方B.a在b的左方C.a是b的祖先D.a是b的子孫4、設(shè)一棵二叉樹的中序遍歷序列：badce，后序遍歷序列：bdeca，則二叉樹先序遍歷序列為（D）。A.adbce

B.decab

C.debac

D.abcde5、在一棵具有

5層的滿二叉樹中結(jié)點總數(shù)為（

A ）。A.31

B.32

C.33

D.166、由二叉樹的前序和后序遍歷序列（A. 能 B. 不能

B ）惟一確定這棵二叉樹。7、某二叉樹的中序序列為 ABCDEFG，后序序列為 BDCAFGE，則其左子樹中結(jié)點數(shù)目為（C ）。A.3

B.2

C.4

D.58、若以

{4,5,6,7,8}

作為權(quán)值構(gòu)造哈夫曼樹，則該樹的帶權(quán)路徑長度為（

C ）。A.67

B.68

C.69

D.709、將一棵有100個結(jié)點的完全二叉樹從根這一層開始， 每一層上從左到右依次對結(jié)點進行編號，根結(jié)點的編號為 1，則編號為49的結(jié)點的左孩子編號為（ A ）。A.98

B.99

C.50

D.4810、表達式

a*(b+c)-d

的后綴表達式是（

B ）。A.abcd+-

B.abc+*d-

C.abc*+d-

D.-+*abcd11、對某二叉樹進行先序遍歷的結(jié)果為歷的結(jié)果是（ B ）。

ABDEFC，中序遍歷的結(jié)果為

DBFEAC，則后序遍A.DBFEACB.DFEBCAC.BDFECAD.BDEFAC12、樹最適合用來表示（C）。A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)13、表達式A*(B+C)/(D-E+F)的后綴表達式是（C）。A.A*B+C/D-E+FB.AB*C+D/E-F+C.ABC+*DE-F+/D.ABCDED*+/-+14、在線索二叉樹中，t所指結(jié)點沒有左子樹的充要條件是（B）。A.t->left==NULLB.t->ltag==1C.t->ltag==1&&t->left==NULLD.以上都不對15、任何一棵二叉樹的葉結(jié)點在先序、中序和后序遍歷序列中的相對次序（A）。A.不發(fā)生改變B.發(fā)生改變C.不能確定D.以上都不對16、假定在一棵二叉樹中，度為2的結(jié)點數(shù)為15，度為1的結(jié)點數(shù)為30，則葉子結(jié)點數(shù)為（B）個。A.15B.16C.17D.4717、在下列情況中，可稱為二叉樹的是（B）。A.每個結(jié)點至多有兩棵子樹的樹B.哈夫曼樹C.每個結(jié)點至多有兩棵子樹的有序樹D.每個結(jié)點只有一棵子樹18、用順序存儲的方法，將完全二叉樹中所有結(jié)點按層逐個從左到右的順序存放在一維數(shù)組R[1..n]中，若結(jié)點R[i]有左孩子，則其左孩子是（C）。A.R[2i-1]B.R[2i+1]C.R[2i]D.R[2/i]19、下面說法中正確的是（D）。A.度為2的樹是二叉樹B.度為2的有序樹是二叉樹C.子樹有嚴格左右之分的樹是二叉樹度不超過2的樹是二叉樹20、樹的先根序列等同于與該樹對應(yīng)的二叉樹的（A.先序序列 B. 中序序列

D.子樹有嚴格左右之分，A ）。C.后序序列 D.

且層序序列21、按照二叉樹的定義，具有

3個結(jié)點的二叉樹有（

C ）種。A.3

B.4

C.5

D.622、由權(quán)值為

3，6，7，2，5的葉子結(jié)點生成一棵哈夫曼樹，

它的帶權(quán)路徑長度為 （

A

）。A.51

B.23

C.53

D.74二、判斷題（√）1、存在這樣的二叉樹，對它采用任何次序的遍歷，結(jié)果相同。（× ）2、中序遍歷一棵二叉排序樹的結(jié)點，可得到排好序的結(jié)點序列。（√）3、對于任意非空二叉樹，要設(shè)計其后序遍歷的非遞歸算法而不使用堆棧結(jié)構(gòu)，最適合的方法是對該二叉樹采用三叉鏈表。（×）4、在哈夫曼編碼中，當兩個字符出現(xiàn)的頻率相同時，其編碼也相同，對于這種情況應(yīng)做特殊處理。（√ ）5、一個含有n個結(jié)點的完全二叉樹，它的高度是 log

2n

＋1。（√ ）6、完全二叉樹的某結(jié)點若無左孩子，則它必是葉結(jié)點。三、填空題1、具有n個結(jié)點的完全二叉樹的深度是 log2n+12、哈夫曼樹是其樹的帶權(quán)路徑長度 最小3、在一棵二叉樹中，度為 0的結(jié)點的個數(shù)是 n0，度為N2+1 。

。的二叉樹。2的結(jié)點的個數(shù)為

n2，則有

n0=4、樹內(nèi)各結(jié)點度的

最大值

稱為樹的度。四、代碼填空題1、函數(shù)InOrderTraverse(Bitreebt) 實現(xiàn)二叉樹的中序遍歷，請在空格處將算法補充完整。voidInOrderTraverse(BiTreebt){if( ){InOrderTraverse(bt->lchild);printf( “%c”,bt->data);;}}2、函數(shù)depth實現(xiàn)返回二叉樹的高度，請在空格處將算法補充完整。intdepth(Bitree*t){if(t==NULL)return0;else{hl=depth(t->lchild);hr= depth(t->rchild) ;if( hl>hr )returnhl+1;elsereturnhr+1;}}3、寫出下面算法的功能。Bitree*function(Bitree*bt){Bitree*t,*t1,*t2;if(bt==NULL)t=NULL;else{t=(Bitree*)malloc(sizeof(Bitree));t->data=bt->data;t1=function(bt->left);t2=function(bt->right);t->left=t2;t->right=t1;}return(t);}答案：交換二叉樹結(jié)點左右子樹的遞歸算法4、寫出下面算法的功能。voidfunction(Bitree*t){if(p!=NULL){function(p->lchild);function(p->rchild);printf( “%d”,p->data);}}答案：二叉樹后序遍歷遞歸算法五、綜合題1、假設(shè)以有序?qū)?<p,c>表示從雙親結(jié)點到孩子結(jié)點的一條邊， 若已知樹中邊的集合為{<a,b>,<a,d>,<a,c>,<c,e>,<c,f>,<c,g>,<c,h>,<e,i>,<e,j>,<g,k>}, 請回答下列問題：（1）哪個結(jié)點是根結(jié)點？（2）哪些結(jié)點是葉子結(jié)點？（3）哪些結(jié)點是 k的祖先？（4）哪些結(jié)點是 j的兄弟？（5）樹的深度是多少？。2、假設(shè)一棵二叉樹的先序序列為 EBADCFHGIKJ，中序序列為 ABCDEFGHIJK，請畫出該二叉樹。3、假設(shè)用于通訊的電文僅由 8個字母A、B、C、D、E、F、G、H組成，字母在電文中出現(xiàn)的頻率分別為：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。請為這8個字母設(shè)計哈夫曼編碼。100A00001B1010380621C10000121321730

D 10010G01E1E1171019011AH1BF10001答案：

65 G 010 D1H 0012 3C F4、已知二叉樹的先序遍歷序列為ABCDEFGH，中序遍歷序列為CBEDFAGH，畫出二叉樹。答案：二叉樹形態(tài)AB GC D HE F5、試用權(quán)集合 {12,4,5,6,1,2} 構(gòu)造哈夫曼樹，并計算哈夫曼樹的帶權(quán)路徑長度。答案：301218711456312WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=696、已知權(quán)值集合為{5,7,2,3,6,9}，要求給出哈夫曼樹，并計算帶權(quán)路徑長度WPL。答案：(1)樹形態(tài)：321319679105523(2)帶權(quán)路徑長度： WPL=(6+7+9)*2+5*3+(2+3)*4=44+15+20=797、已知一棵二叉樹的先序序列： ABDGJEHCFIKL；中序序列： DJGBEHACKILF。畫出二叉樹的形態(tài)。AB CD E FG H IJ K L答案：8、一份電文中有 6種字符：A,B,C,D,E,F ，它們的出現(xiàn)頻率依次為 16，5，9，3，30，1，完成問題：1）設(shè)計一棵哈夫曼樹；（畫出其樹結(jié)構(gòu)）2）計算其帶權(quán)路徑長度WPL；答案：(1)樹形態(tài)：643034161899541 3帶權(quán)路徑長度：WPL=30*1+16*2+9*3+5*4+(1+3)*5=30+32+27+20+20=1299、已知某森林的二叉樹如下所示，試畫出它所表示的森林。AB DC E HFG答案：A D HB C E FG10、有一分電文共使用 5個字符;a,b,c,d,e ，它們的出現(xiàn)頻率依次為 4、7、5、2、9，試構(gòu)造哈夫曼樹，并給出每個字符的哈夫曼編碼。11、畫出與下圖所示的森林相對應(yīng)的二叉樹，并指出森林中的葉子結(jié)點在二叉樹中具有什么特點。A I MB C D JNE F G K LH12、如下所示的二叉樹，請寫出先序、中序、后序遍歷的序列。FD GB E IA C H J答案：先序： FDBACEGIHJ中序：ABCDEFGHIJ后序：ACBEDHJIGF六、編程題1、編寫求一棵二叉樹中結(jié)點總數(shù)的算法。答案： （以先序遍歷的方法為例）voidcount_preorder(Bitree*t,int*n){if(t!=NULL){*n++;count_preorder(t->lchild);count_preorder(t->lchild);}}第七章 圖一、選擇題1、12、對于具有n個頂點的圖，若采用鄰接矩陣表示，則該矩陣的大小為（）。A.nB.n2D.(n-1)2C.n-12、如果從無向圖的任一頂點出發(fā)進行一次深度優(yōu)先搜索即可訪問所有頂點，則該圖一定是（ ）。A.完全圖

B. 連通圖

C.有回路

D.一棵樹3、關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中（ ）。A.從源點到匯點的最長路徑 B.從源點到匯點的最短路徑C.最長的回路 D.最短的回路4、下面（ ）可以判斷出一個有向圖中是否有環(huán)（回路） 。A.廣度優(yōu)先遍歷 B. 拓撲排序C.求最短路徑 D.求關(guān)鍵路徑5、帶權(quán)有向圖 G用鄰接矩陣A存儲，則頂點 i的入度等于 A中（ ）。A.第i行非無窮的元素之和 B.第i列非無窮的元素個數(shù)之和C.第i行非無窮且非 0的元素個數(shù) D. 第i行與第i列非無窮且非

0的元素之和6、采用鄰接表存儲的圖，其深度優(yōu)先遍歷類似于二叉樹的（A.中序遍歷 B. 先序遍歷 C.后序遍歷

）。

D. 按層次遍歷7、無向圖的鄰接矩陣是一個（A.對稱矩陣 B. 零矩陣

）。

C.上三角矩陣

D.對角矩陣8、當利用大小為

N的數(shù)組存儲循環(huán)隊列時，該隊列的最大長度是（

）。A.N-2

B.N-1

C.N

D.N+19、鄰接表是圖的一種（

）。A.順序存儲結(jié)構(gòu)

B.鏈式存儲結(jié)構(gòu)

C. 索引存儲結(jié)構(gòu)

D. 散列存儲結(jié)構(gòu)10、下面有向圖所示的拓撲排序的結(jié)果序列是（ ）。A.125634 B.516234 C.123456 D.5216431325 6 411、在無向圖中定義頂點vi與vj之間的路徑為從vi到vj的一個（）。A.頂點序列B.邊序列C.權(quán)值總和D.邊的條數(shù)12、在有向圖的逆鄰接表中，每個頂點鄰接表鏈接著該頂點所有（）鄰接點。A.入邊B.出邊C.入邊和出邊D.不是出邊也不是入邊13、設(shè)G1=(V1,E1)和G2=(V2,E2)為兩個圖，如果V1V2,E1E2則稱（）。A.G1是G2的子圖B.G2是G1的子圖C.G1是G2的連通分量D.G2是G1的連通分量14、已知一個有向圖的鄰接矩陣表示，要刪除所有從第i個結(jié)點發(fā)出的邊，應(yīng)（）。A.將鄰接矩陣的第i行刪除B.將鄰接矩陣的第i行元素全部置為0C.將鄰接矩陣的第i列刪除D.將鄰接矩陣的第i列元素全部置為015、任一個有向圖的拓撲序列（）。A.不存在B.有一個C.一定有多個D.有一個或多個16、在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（ ）倍。A.1/2 B.1 C.2 D.417、下列關(guān)于圖遍歷的說法不正確的是（ ）。連通圖的深度優(yōu)先搜索是一個遞歸過程圖的廣度優(yōu)先搜索中鄰接點的尋找具有“先進先出”的特征非連通圖不能用深度優(yōu)先搜索法圖的遍歷要求每一頂點僅被訪問一次18、帶權(quán)有向圖G用鄰接矩陣A存儲，則頂點i的入度為A中：（）。A.第i行非的元素之和B.第i列非的元素之和C.第i行非且非0的元素個數(shù)D.第i列非且非0的元素個數(shù)19、采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的（）。A.先序遍歷B.中序遍歷C.后序遍歷D.按層次遍歷20、一個具有n個頂點的有向圖最多有（）條邊。2A.n×(n-1)/2B.n×(n-1)C.n×(n+1)/2D.n21、已知一個有向圖的鄰接表存儲結(jié)構(gòu)如圖所示，根據(jù)深度優(yōu)先遍歷算法，從頂點v1出發(fā)，所得到的頂點序列是（）。1 3 2 423 4 545 2 4A.v1,v2,v3,v5,v4

B.v1,v2,v3,v4,v5C.v1,v3,v4,v5,v2

D.v1,v4,v3,v5,v222、關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中（A.從源點到匯點的最長路徑C.最長的回路

）。B.從源點到匯點的最短路徑D.最短的回路23、以下說法正確的是（ ）。連通分量是無向圖中的極小連通子圖強連通分量是有向圖中的極大強連通子圖C.在一個有向圖的拓撲序列中若頂點 a在頂點b之前，則圖中必有一條弧 <a,b>D.對有向圖G，如果以任一頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先搜索能訪問到每個頂點，則該圖一定是完全圖24、假設(shè)有向圖含 n個頂點及 e條弧，則表示該圖的鄰接表中包含的弧結(jié)點個數(shù)為（ ）。A.n B.e C.2e D.n*e0 1 125、設(shè)圖的鄰接矩陣為 0 0 1 ，則該圖為（ ）。0 1 0A.有向圖B.無向圖C.強連通圖D.完全圖26、為便于判別有向圖中是否存在回路，可借助于（）。A.廣度優(yōu)先搜索算法B.最小生成樹算法C.最短路徑算法D.拓撲排序算法27、任何一個無向連通圖的最小生成樹（）種。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在28、已知一有向圖的鄰接表存儲結(jié)構(gòu)如圖所示，根據(jù)有向圖的廣度優(yōu)先遍歷算法，從頂點v1出發(fā)，所得到的頂點序列是（ ）。1 3 2 ^^345^^524^A.v1,v2,v3,v4,v5

B.v1,v3,v2,v4,v5

C.v1,v2,v3,v5,v4

D.v1,v4,v3,v5,v229、對于一個有向圖，若一個頂點的入度為單鏈表中的結(jié)點數(shù)為（ ）。

k1,

、出度為

k2，則對應(yīng)鄰接表中該頂點A.k1

B.k2

C.k1+k2

D.k1-k230、一個具有8個頂點的有向圖中，所有頂點的入度之和與所有頂點的出度之和的差等于（ ）。A.16

B.4

C.0

D.231、無向圖中一個頂點的度是指圖中（A.通過該頂點的簡單路徑數(shù)C.與該頂點連通的頂點數(shù)

）。

B.與該頂點相鄰接的頂點數(shù)D.通過該頂點的回路數(shù)二、填空題1、n個頂點的連通圖至少有 邊。答案：n-1條2、一個連通圖的生成樹是一個足以構(gòu)成一棵樹的 n-1條邊。答案：極小連通子圖3、一個圖的 表示法是惟一的。

，它包含圖中所有頂點，但只有答案：鄰接矩陣4、遍歷圖的基本方法有深度優(yōu)先搜索和廣度優(yōu)先搜索，其中

是一個遞歸過程。答案：深度優(yōu)先搜索5、在無向圖G的鄰接矩陣

A中，若

A[i][j]

等于

1，則A[j][i]

等于

。答案：16、判定一個有向圖是否存在回路，可以利用

。答案：拓撲排序7、已知一個圖的鄰接矩陣表示，計算第i個結(jié)點的入度的方法是 。8、n個頂點的無向圖最多有9、已知一個圖的鄰接矩陣表示， 刪除所有從第10、若以鄰接矩陣表示有向圖，則鄰接矩陣上第的 。

邊。i個結(jié)點出發(fā)的邊的方法是i行中非零元素的個數(shù)即為頂點

。vi三、判斷題1、圖的連通分量是無向圖的極小連通子圖。2、一個圖的廣度優(yōu)先搜索樹是惟一的。3、圖的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列不是惟一的。4、鄰接表只能用于存儲有向圖，而鄰接矩陣則可存儲有向圖和無向圖。5、存儲圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點個數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)。6、AOV網(wǎng)是一個帶權(quán)的有向圖。7、從源點到終點的最短路徑是唯一的。8、鄰接表只能用于存儲有向圖，而鄰接矩陣則可存儲有向圖和無向圖。9、圖的生成樹是惟一的。四、程序分析題1、寫出下面算法的功能。typedefstruct{intvexnum,arcnum;charvexs[N];intarcs[N][N];}graph;voidfuntion(inti,graph*g){intj;printf("node:%c\n",g->vexs[i]);visited[i]=TRUE;for(j=0;j<g->vexnum;j++)if((g->arcs[i][j]==1)&&(!visited[j]))function(j,g);}答案：實現(xiàn)圖的深度優(yōu)先遍歷算法五、綜合題1、已知圖 G的鄰接矩陣如下所示：1）求從頂點1出發(fā)的廣度優(yōu)先搜索序列；2）根據(jù)prim算法，求圖G從頂點1出發(fā)的最小生成樹，要求表示出其每一步生成過程。（用圖或者表的方式均可）。61565315564552366426答案：(1)廣度優(yōu)先遍歷序列：1;2,3,4;5;6(2)最小生成樹（prim算法）111111111212553333335444422264646462、設(shè)一個無向圖的鄰接矩陣如下圖所示：1）畫出該圖；2）畫出從頂點0出發(fā)的深度優(yōu)先生成樹；011100101000110110101011001101000110答案：(1)圖形態(tài)(2)深度優(yōu)先搜索樹01013 2 3 25 4 5 43、寫出下圖中全部可能的拓撲排序序列。1 2 3 456答案：1，5，2，3，6，41，5，6，2，3，45，1，2，3，6，45，1，6，2，3，45，6，1，2，3，44、AOE網(wǎng)G如下所示，求關(guān)鍵路徑。（要求標明每個頂點的最早發(fā)生時間和最遲發(fā)生時間，并畫出關(guān)鍵路徑）v13v4322v0v32v5243v2答案：(1)最早發(fā)生時間和最遲發(fā)生時間： (2) 關(guān)鍵路徑：頂點vevl3v000v1v42v1333v5v222v02v366v32v466v24v5885、已知有向圖G如下所示，根據(jù)迪杰斯特拉算法求頂點v0到其他頂點的最短距離。（給出求解過程）v012v1454v29274v3v42答案：終點從v0到各終點的d值和最短路徑的求解過程i=1i=2i=3i=4v112(v0,v1)12(v0,v1)7(v0,v4,v1)v24(v0,v2)v39(v0,v3)877(v0,v2,v3)(v0,v4,v3)(v0,v4,v3)v45(v0,v4)5(v0,v4)vjv2v4v1v3s{v0,v2}{v0,v4}{v0,v4,v1}{v0,v4,v3}6、已知圖 G如下所示，根據(jù) Prim算法，構(gòu)造最小生成樹。 （要求給出生成過程）8v0 v1867v24v3v44v52728v65v7答案：prim算法求最小生成樹如下：v0v0v0v0v0v0v0v166666667v4v44v44v5v44v3v44v5v3v44v5v3v44v5v5v57727275275v6v222v62v6v72v6v7v6v2v2v27、已知有向圖如下所示，請寫出該圖所有的拓撲序列。v2 v3v1 v4 v5 v8v6 v7答案：拓撲排序如下：v1,v2,v4,v6,v5,v3,v7,v8 v1,v2,v4,v6,v5,v7,v3,v8v1,v2,v6,v4,v5,v3,v7,v8 v1,v2,v6,v4,v5,v7,v3,v8v1,v6,v2,v4,v5,v3,v7,v8 v1,v6,v2,v4,v5,v7,v3,v88、如下圖所示的 AOE網(wǎng)，求：（1）求事件的最早開始時間 ve和最遲開始時間 vl；事件 1 2 3 4 5 6 7 8 9VeVl（2）求出關(guān)鍵路徑；V2V7a4a7a101a1926V5a5a8a27V1V31V8a11V9源點44匯點a3a954V4a6V62答案：(1)求ve和vl(2)關(guān)鍵路徑事件123456789v29v7612ve064577161418vl0668710161418v1v5v9******74v8如下所示的有向圖，回答下面問題：v1 v2v4 v3（1）該圖是強連通的嗎？若不是，給出強連通分量。（2）請給出圖的鄰接矩陣和鄰接表表示。答案：(1)是強連通圖(2)鄰接矩陣和鄰接表為：0101v1v2v40010v2v31000v3v10010v4v31126101899、已知圖G的鄰接矩陣A=1282，試畫出它所表示的圖G，并根據(jù)Prim6941024算法求出圖的的最小生成樹（給出生成過程）。答案：(1)圖形態(tài)：(2)prim算法求最小生成樹：v11v11v21v2v11v2v1v21288810v3v11v2v3v329822v54v3v5v54v4v410、如下圖所示的 AOV網(wǎng)，寫出其中三種拓撲排序序列。v0 v1v2v3 v4v5v7v611、已知圖 G如下，根據(jù)克魯斯卡爾算法求圖 G的一棵最小生成樹。（要求給出構(gòu)造過程）答案：kruskal 算法的最小生成樹BBDBDBAD22323243FFKFKFCK33HHBADBADBAD243254325435FCKFCKFCK343434HEHEHE12、已知圖 G如下所示，求從頂點 a到其余各頂點的最短路徑。（給出求解過程）b5d36a232f3 5ce4答案：終點最短路徑求解過程b65(a,c,b)(a,b)c3(a,c)d6(a,c,d)6(a,c,d)e7(a,c,e)77(a,c,e)(a,c,e)f99(a,c,d,f)(a,c,d,f)vjcbdefS{a,c}{a,c,b}{a,c,d}{a,c,e}{a,c,d,f}第九章 查找一、選擇題1、已知一個有序表為（11，22，33，44，55，66，77，88，99），則折半查找55需要比較（A）次。A.1B.2C.3D.42、有一組關(guān)鍵字序列{13,16,6,34,32,98,73,1,27}，哈希表的表長為13，哈希函數(shù)為H(key)=keyMOD13, 沖突解決的辦法為鏈地址法，請構(gòu)造哈希表（用圖表示） 。3、解決哈希沖突的主要方法有（ ）。A.數(shù)字分析法、除余法、平方取中法 B. 數(shù)字分析法、除余法、線性探測法C.數(shù)字分析法、線性探測法、再哈希法

D.線性探測法、再哈希法、鏈地址法4、在一棵深度為 h的具有n個元素的二叉排序樹中，查找所有元素的最長查找長度為（ ）。A.n5、已知表長為

B.log 2n C.(h+1)/2 D.h25的哈希表，用除留取余法，按公式 H(key)=keyMODp

建立哈希表，則p應(yīng)取（

）為宜。A.23

B.24

C.25

D.266、設(shè)哈希表長 m=14,哈希函數(shù)H(key)=keyMOD11addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7

。表中已有4個結(jié)點：其余地址為空，如用二次探測再散列處理沖突，則關(guān)鍵字為

49的地址為（

A

）。A.8

B.3

C.5

D.97、在散列查找中，平均查找長度主要與（ C ）有關(guān)。A.散列表長度 B. 散列元素個數(shù)

C.裝填因子處理沖突方法8、根據(jù)一組記錄（ 56，42，50，64，48）依次插入結(jié)點生成一棵 AVL樹，當插入到值為的結(jié)點時需要進行旋轉(zhuǎn)調(diào)整。9、m階B-樹中的m是指（）。A.每個結(jié)點至少具有m棵子樹B.每個結(jié)點最多具有m棵子樹C.分支結(jié)點中包含的關(guān)鍵字的個數(shù)D.m階B-樹的深度10、一個待散列的線性表為k={18,25,63,50,42,32,9}，散列函數(shù)為H(k)=kMOD9，與18發(fā)生沖突的元素有（）個。A.1B.2C.3D.411、在對查找表的查找過程中，若被查找的數(shù)據(jù)元素不存在，則把該數(shù)據(jù)元素插到集合中，這種方式主要適合于（）。A.靜態(tài)查找表B.動態(tài)查找表C.靜態(tài)查找表和動態(tài)查找表D.兩種表都不適合12、有一個有序表為{1,3,9,12,32,41,45,62,75,77,82,95,100},當折半查找值為82的結(jié)點時，（B）次比較后查找成功。A.1B.4C.2D.813、在各種查找方法中，平均查找承擔與結(jié)點個數(shù)n無關(guān)的查找方法是（C）。A.順序查找B.折半查找C.哈希查找D.分塊查找14、下列二叉樹中，不．平衡的二叉樹是（C）。15、對一棵二叉排序樹按（B）遍歷，可得到結(jié)點值從小到大