數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題集耿國華第二版版C語言描述

第一章復(fù)習(xí)題1.簡述次序存儲構(gòu)造與鏈式存儲構(gòu)造在表達數(shù)據(jù)元素之間關(guān)系上的重要區(qū)別。答：在次序構(gòu)造中，邏輯關(guān)系上相鄰的兩個元素在物理位置上也相鄰。而鏈式存儲構(gòu)造中，數(shù)據(jù)元素之間關(guān)系是由結(jié)點中指針指示的。2.數(shù)據(jù)構(gòu)造是一門……的學(xué)科。3.在數(shù)據(jù)構(gòu)造中，從邏輯上可以把數(shù)據(jù)構(gòu)造提成（C）。A、動態(tài)構(gòu)造與靜態(tài)構(gòu)造B、緊湊構(gòu)造和非緊湊構(gòu)造C、線性構(gòu)造和非線性構(gòu)造D、內(nèi)部構(gòu)造和外部構(gòu)造4.編寫一種函數(shù)，用不多于3n/2的平均比較次數(shù)，在一種數(shù)組中找出最大和最小值元素。voidmaxmin(inta[],intn){max=min=a[0];for(i=1;i<n;i++){if(a[i]>max)max=a[i];elseif(a[i]<min)min=a[i];}printf(“max=%d,min=%d”,max,min);}第二章復(fù)習(xí)題1．下述哪一條是次序存儲構(gòu)造的長處？（A）A．存儲密度大B．插入運算以便C．刪除運算以便D．可以便地用于多種邏輯構(gòu)造的存儲表達2．下面有關(guān)線性表的論述中，錯誤的是哪一種？（B）A．線性表采用次序存儲，必須占用一片持續(xù)的存儲單元。B．線性表采用次序存儲，便于進行插入和刪除操作。C．線性表采用鏈接存儲，不必占用一片持續(xù)的存儲單元。D．線性表采用鏈接存儲，便于插入和刪除操作。3．線性表是具有n個（C）的有限序列（n>=0）。A．表元素B．字符C．數(shù)據(jù)元素D．數(shù)據(jù)項4．若某線性表最常用的操作是存取任一指定序號的元素和在最終進行插入和刪除運算，則運用（A）存儲方式最節(jié)省時間。A．次序表B．單循環(huán)鏈表C．帶頭結(jié)點的雙循環(huán)鏈表D．雙鏈表5．某線性表中最常用的操作是在最終一種元素之后插入一種元素和刪除第一種元素，則采用（D）存儲方式最節(jié)省運算時間。A．單鏈表B．僅有頭指針的單循環(huán)鏈表C．雙鏈表D．僅有尾指針的單循環(huán)鏈表6．若某表最常用的操作是在最終一種結(jié)點之后插入一種結(jié)點或刪除最終一種結(jié)點。則采用（D）存儲方式最節(jié)省運算時間。A．單鏈表B．雙向鏈表C．單循環(huán)鏈表D．帶頭結(jié)點的雙向循環(huán)鏈表鏈表不具有的特點是（B）A．插入、刪除不需要移動元素B．可隨機訪問任一元素C．不必事先估計存儲空間D．所需空間與線性長度成正比8.下面的論述不對的的是（BC）A.線性表在鏈式存儲時，查找第i個元素的時間同i的值成正比B.線性表在鏈式存儲時，查找第i個元素的時間同i的值無關(guān)C.線性表在次序存儲時，查找第i個元素的時間同i的值成正比D.線性表在次序存儲時，查找第i個元素的時間同i的值無關(guān)9.若長度為n的線性表采用次序存儲構(gòu)造，在其第i個位置插入一種新元素的算法的時間復(fù)雜度為（C）(1<=i<=n+1)。A.O(0)B.O(1)C.O(n)D.O(n2)10.對于次序存儲的線性表，訪問結(jié)點和增長、刪除結(jié)點的時間復(fù)雜度為（C）。A．O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)11．線性表（a1,a2,…,an）以鏈接方式存儲時，訪問第i位置元素的時間復(fù)雜性為（C）A．O（i）B．O（1）C．O（n）D．O（i-1）12．非空的循環(huán)單鏈表head的尾結(jié)點p滿足（A）。A．p->next==headB．p->next==NULLC．p==NULLD．p==head13．循環(huán)鏈表H的尾結(jié)點P的特點是（A）。A．P->NEXT==HB．P->NEXT==H->NEXTC．P==HD．P==H->NEXT14．完畢在雙循環(huán)鏈表結(jié)點p之后插入s的操作是（D）；A．p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;B．p->next->prior=s;p->next=s;s->prior=p;s->next=p->next;C．s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;D．s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;15．在雙向循環(huán)鏈表中,在p指針所指向的結(jié)點前插入一種指針q所指向的新結(jié)點,其修改指針的操作是(D)。A.p->prior=q;q->next=p;p->prior->next=q;q->prior=p->prior;B.q->prior=p->prior;p->prior->next=q;q->next=p;p->prior=q->next;C.q->next=p;p->next=q;p->prior->next=q;q->next=p;D.p->prior->next=q;q->next=p;q->prior=p->prior;p->prior=q;16．在單鏈表指針為p的結(jié)點之后插入指針為s的結(jié)點，對的的操作是：（Ｂ）。A．p->next=s;s->next=p->next;B．s->next=p->next;p->next=s;C．p->next=s;p->next=s->next;D．p->next=s->next;p->next=s;17．對于一種頭指針為head的帶頭結(jié)點的單鏈表，鑒定該表為空表的條件是（Ｂ）A．head==NULLB．Head->next==NULLC．Head->next==headD．head!=NULL18在雙向鏈表中，刪除p所指的結(jié)點時須修改指針（A）。A．p->prior->next=p->next;p->next->prior=p->prior;B．p->prior=p->prior->prior;p->prior->next=p;C．p->next->prior=p;p->next=p->next->nextD．p->next=p->prior->prior.p->prior=p->next->next;19．當線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但規(guī)定以最快的速度存取線性表中的元素時，應(yīng)采用次序存儲構(gòu)造。20．線性表L=（a1,a2,…,an）用數(shù)組表達，假定刪除表中任一元素的概率相似，則刪除一種元素平均需要移動元素的個數(shù)是（n-1)/221．設(shè)單鏈表的結(jié)點構(gòu)造為(data,next)，next為指針域，已知指針px指向單鏈表中data為x的結(jié)點，指針py指向data為y的新結(jié)點,若將結(jié)點y插入結(jié)點x之后，則需要執(zhí)行如下語句:py->next=px->next;px->next=py22．在一種長度為n的次序表中第i個元素（1<=i<=n）之前插入一種元素時，需向后移動n-i+1個元素。23．對于一種具有n個結(jié)點的單鏈表，在已知的結(jié)點p后插入一種新結(jié)點的時間復(fù)雜度為O(1),在給定值為x的結(jié)點后插入一種新結(jié)點的時間復(fù)雜度為O(n)24．根據(jù)線性表的鏈式存儲構(gòu)造中每一種結(jié)點包括的指針個數(shù)，將線性鏈表提成單鏈表，和多重鏈表；而又根據(jù)指針的連接方式，鏈表又可提成（動態(tài)）鏈表和靜態(tài)鏈表25.循環(huán)單鏈表的最大長處是：從任一結(jié)點出發(fā)都可訪問到鏈表中每一種元素26.已知指針p指向單鏈表L中的某結(jié)點，則刪除其后繼結(jié)點的語句是q=p->next;p->next=q->next;free(q);27.帶頭結(jié)點的雙循環(huán)鏈表L中只有一種元素結(jié)點的條件是：L->next->next==L28.在單鏈表L中，指針p所指結(jié)點有后繼結(jié)點的條件是：p->next!=null29.帶頭結(jié)點的雙循環(huán)鏈表L為空表的條件是：L->next==L&&L->prior==L30.在單鏈表p結(jié)點之后插入s結(jié)點的操作是：s->next=p->next;p->next=s;第三章復(fù)習(xí)題1.一種棧的輸入序列為123…n，若輸出序列的第一種元素是n，輸出第i（1<=i<=n）個元素是（B）。A.不確定B.n-i+1C.iD.n-I2.一種棧的輸入序列為12345，則下列序列中不也許是棧的輸出序列的是（B）。A.23415B.54132C.23145D.154323.輸入序列為ABC，可以變?yōu)镃BA時，通過的棧操作為（B）A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop4.若一種棧以向量V[1..n]存儲，初始棧頂指針top為n+1，則下面x進棧的對的操作是(C)。A．top=top+1;V[top]=xB.V[top]:=x;top:=top+1C.top:=top-1;V[top]:=xD.V[top]:=x;top:=top-15.設(shè)計一種鑒別體現(xiàn)式中左，右括號與否配對出現(xiàn)的算法，采用（D）數(shù)據(jù)構(gòu)造最佳。A．線性表的次序存儲構(gòu)造B.隊列C.線性表的鏈式存儲構(gòu)造D.棧6.用鏈接方式存儲的隊列，在進行刪除運算時（D）。A.僅修改頭指針B.僅修改尾指針C.頭、尾指針都要修改D.頭、尾指針也許都要修改7.假設(shè)以數(shù)組A[m]寄存循環(huán)隊列的元素,其頭尾指針分別為front和rear，則目前隊列中的元素個數(shù)為（A）。A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m8.循環(huán)隊列存儲在數(shù)組A[0..m]中，則入隊時的操作為（D）。A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)9.若用一種大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且目前rear和front的值分別為0和3，當從隊列中刪除一種元素，再加入兩個元素后，rear和front的值分別為多少？(B)A.1和5B.2和4C.4和2D.5和110.棧和隊列的共同點是（C）。A.都是先進先出B.都是先進后出C.只容許在端點處插入和刪除元素D.沒有共同點11.棧和隊都是（）A．次序存儲的線性構(gòu)造B.鏈式存儲的非線性構(gòu)造C.限制存取點的線性構(gòu)造D.限制存取點的非線性構(gòu)造12.設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1，e2，e3，e4,e5和e6依次通過棧S，一種元素出棧后即進隊列Q，若6個元素出隊的序列是e2，e4，e3,e6,e5,e1則棧S的容量至少應(yīng)當是(C)。A．6B.4C.3D.213.設(shè)有一種空棧，棧頂指針為1000H(十六進制)，既有輸入序列為1，2，3，4，5，通過PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，輸出序列是_23_，而棧頂指針值是100CH。（設(shè)棧為次序棧，每個元素占4個字節(jié)。）14.若棧采用次序存儲方式存儲，現(xiàn)兩棧共享空間V[1..m]，top[i]代表第i個棧(i=1,2)棧頂，棧1的底在v[1]，棧2的底在V[m]，則棧滿的條件是（B）。A.|top[2]-top[1]|=0B.top[1]+1=top[2]C.top[1]+top[2]=mD.top[1]=top[2]15.循環(huán)隊列的引入，目的是為了克服_假上溢_。第五章復(fù)習(xí)題1.設(shè)有一種10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲下三角，a11為第一元素，其存儲地址為1，每個元素占一種地址空間，則a85的地址為（B）。A.13B.33C.18D.402.數(shù)組A[0..5,0..6]的每個元素占五個字節(jié)，將其按列優(yōu)先次序存儲在起始地址為1000的內(nèi)存單元中，則元素A[5，5]的地址是(A)。A.1175B.1180C.1205D.12103.將一種A[1..100，1..100]的三對角矩陣，按行優(yōu)先存入一維數(shù)組B[1‥298]中，A中元素A66,65，在B數(shù)組中的位置K為195。4.設(shè)二維數(shù)組A[1..m，1..n]（即m行n列）按行存儲在數(shù)組B[1..m*n]中，則二維數(shù)組元素A[i，j]在一維數(shù)組B中的下標為(A)。A.（i-1）*n+jB.（i-1）*n+j-1C.i*（j-1）D.j*m+i-15.有一種100*90的稀疏矩陣，非0元素有10個，設(shè)每個整型數(shù)占2字節(jié)，則用三元組表達該矩陣時，所需的字節(jié)數(shù)是（B）。A.60B.66C.18000D.336.已知廣義表LS＝((a,b,c),(d,e,f)),運用head和tail函數(shù)取出LS中原子e的運算是(C)。A.head(tail(LS))B.tail(head(LS))C.head(tail(head(tail(LS)))D.head(tail(tail(head(LS))))7.廣義表A=(a,b,(c,d),(e,(f,g))),則下面式子Head(Tail(Head(Tail(Tail(A)))))的值為（D）。A.(g)B.(d)C.cD.d8.廣義表（（a,b,c,d））的表頭是（C），表尾是（B）。A.aB.（）C.（a,b,c,d）D.（b,c,d）9.廣義表（a,(b,c),d,e）的表頭為（A）。A.aB.a,(b,c)C.(a,(b,c))D.(a)10.設(shè)廣義表L=（（a,b,c）），則L的長度和深度分別為（C）。A.1和1B.1和3C.1和2D.2和311.已知廣義表LS＝((a,b,c),(d,e,f)),運用head和tail函數(shù)取出LS中原子e的運算是(C)。A.head(tail(LS))B.tail(head(LS))C.head(tail(head(tail(LS)))D.head(tail(tail(head(LS))))12.廣義表A=(a,b,(c,d),(e,(f,g))),則下面式子的值為（D）。Head(Tail(Head(Tail(Tail(A)))))A.(g)B.(d)C.cD.d13.線性表中元素寄存在向量A（1,…,n）中，元素是整型數(shù)。試寫出遞歸算法求出A中的最大和最小元素。intMinMaxValue(intA[],intn,int*max,int*min){if(n>0){if(*max<A[n])*max=A[n];if(*min>A[n])*min=A[n];MinMaxValue(A,n-1,max,min);}//算法結(jié)束算法調(diào)用格式MinMaxValue(arr,n,&max,&min);arr是具有n個整數(shù)的一維數(shù)組，max=-32768是最大數(shù)的初值,min=32767是最小數(shù)的初值。voidmaxmin(intA[],int*e_max,int*e_min,intlow,inthigh){if((high-low)<=1){//個數(shù)if(A[high]>A[low]){*e_max=A[high];*e_min=A[low];}else{*e_max=A[low];*e_min=A[high];}}else{mid=(low+high)/2;maxmin(A,&x1,&y1,low,mid);maxmin(A,&x2,&y2,mid+1,high);*e_max=max(x1,x2);*e_min=min(y1,y2);}}第六章復(fù)習(xí)題1．算術(shù)體現(xiàn)式a+b*（c+d/e）轉(zhuǎn)為后綴體現(xiàn)式后為（B）A．a(chǎn)b+cde/*B．a(chǎn)bcde/+*+C．a(chǎn)bcde/*++D．a(chǎn)bcde*/++2.設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點個數(shù)分別為4，2，1，1則T中的葉子數(shù)為（D）A．5B．6C．7D．83.設(shè)森林F對應(yīng)的二叉樹為B，它有m個結(jié)點，B的根為p,p的右子樹結(jié)點個數(shù)為n,森林F中第一棵樹的結(jié)點個數(shù)是（A）A．m-nB．m-n-1C．m-n+1D．條件局限性，無法確定4．若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是（B）A．9B．11C．15D．不確定5．設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點個數(shù)分別為M1，M2和M3。與森林F對應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是（D）。A．M1B．M1+M2C．M3D．M2+M36.一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（C）A．499B．500C．501D．5057.設(shè)給定權(quán)值總數(shù)有n個，其哈夫曼樹的結(jié)點總數(shù)為(D)A．不確定B．2nC．2n+1D．2n-18.有關(guān)二叉樹下列說法對的的是（B）A．二叉樹的度為2B．一棵二叉樹的度可以不不小于2C．二叉樹中至少有一種結(jié)點的度為2D．二叉樹中任何一種結(jié)點的度都為29.一種具有1025個結(jié)點的二叉樹的高h為（C）A．11C．11至1025之間B．10D．10至1024之間10．一棵二叉樹高度為h,所有結(jié)點的度或為0，或為2，則這棵二叉樹至少有(B)結(jié)點A．2hB．2h-1C．2h+1D．h+111．對于有n個結(jié)點的二叉樹,其高度為（D）A．nlog2nB．log2nC．log2n|+1D．不確定12．高度為K的二叉樹最大的結(jié)點數(shù)為（B）。A．2k B．2k-1C．2k-1 D．2k-1-113.一棵樹高為K的完全二叉樹至少有（C）個結(jié)點.A.2k–1B.2k-1–1C.2k-1D.2k14.運用二叉鏈表存儲樹，則根結(jié)點的右指針是（C）。A．指向最左孩子B．指向最右孩子C．空D．非空15．對二叉樹的結(jié)點從1開始進行持續(xù)編號，規(guī)定每個結(jié)點的編號不小于其左、右孩子的編號，同一結(jié)點的左右孩子中，其左孩子的編號不不小于其右孩子的編號，可采用(C)次序的遍歷實現(xiàn)編號。A．先序B.中序C.后序D.從根開始按層次遍歷16．樹的后根遍歷序列等同于該樹對應(yīng)的二叉樹的(B).A.先序序列B.中序序列C.后序序列17．若二叉樹采用二叉鏈表存儲構(gòu)造，要互換其所有分支結(jié)點左、右子樹的位置，運用(AC)遍歷措施最合適。A．前序B．中序C．后序D．按層次18．已知一棵二叉樹的前序遍歷成果為ABCDEF,中序遍歷成果為CBAEDF,則后序遍歷的成果為（A）。A．CBEFDAB．FEDCBAC．CBEDFAD．不定19．對于前序遍歷與中序遍歷成果相似的二叉樹為（F）;對于前序遍歷和后序遍歷成果相似的二叉樹為（B）。A．一般二叉樹B．只有根結(jié)點的二叉樹C．根結(jié)點無左孩子的二叉樹D．根結(jié)點無右孩子的二叉樹E．所有結(jié)點只有左子數(shù)的二叉樹F．所有結(jié)點只有右子樹的二叉樹20．一棵非空的二叉樹的先序遍歷序列與后序遍歷序列恰好相反，則該二叉樹一定滿足（C）A．所有的結(jié)點均無左孩子B．所有的結(jié)點均無右孩子C．只有一種葉子結(jié)點D．是任意一棵二叉樹21.一棵左子樹為空的二叉樹在先序線索化后，其中空的鏈域的個數(shù)是：(D)A．不確定B.0C.1D.222.一棵左右子樹均不空的二叉樹在先序線索化后，其中空的鏈域的個數(shù)是：(B)。A.0B.1C.2D.不確定23.若X是二叉中序線索樹中一種有左孩子的結(jié)點，且X不為根，則x的前驅(qū)為(C)A.X的雙親B.X的右子樹中最左的結(jié)點C.X的左子樹中最右結(jié)點D.X的左子樹中最右葉結(jié)點24.引入二叉線索樹的目的是（A）A．加緊查找結(jié)點的前驅(qū)或后繼的速度B．為了能在二叉樹中以便的進行插入與刪除C．為了能以便的找到雙親D．使二叉樹的遍歷成果唯一25．n個結(jié)點的線索二叉樹上具有的線索數(shù)為（C）A．2nB．n－lC．n＋lD．n26．由3個結(jié)點可以構(gòu)造出多少種不一樣的二叉樹？（D）A．2B．3C．4D．527.設(shè)F是一種森林，B是由F變換得的二叉樹。若F中有n個非終端結(jié)點，則B中右指針域為空的結(jié)點有（C）個。A．n-1B．nC．n+1D．n+228．下面幾種符號串編碼集合中，不是前綴編碼的是（B）。A．{0,10,110,1111}B．{11,10,001,101,0001}C．{00,010,0110,1000}D．{b,c,aa,ac,aba,abb,abc}29.一棵有n個結(jié)點的二叉樹，按層次從上到下，同一層從左到右次序存儲在一維數(shù)組A[1..n]中，則二叉樹中第i個結(jié)點（i從1開始用上述措施編號）的右孩子在數(shù)組A中的位置是（D）A．A[2i](2i<=n)B．A[2i+1](2i+1<=n)C．A[i-2]D．條件不充足，無法確定30．若以{4，5，6，7，8}作為葉子結(jié)點的權(quán)值構(gòu)造哈夫曼樹，則其帶權(quán)途徑長度是__69__。31．具有n個結(jié)點的滿二叉樹，其葉結(jié)點的個數(shù)是__（n+1）/2__。33．樹的孩子兄弟表達法存儲，可以將一棵樹轉(zhuǎn)換為_二叉樹_。34．8層完全二叉樹至少有___128___個結(jié)點，擁有100個結(jié)點的完全二叉樹的最大層數(shù)為__7__。35．如某二叉樹有20個葉子結(jié)點，有30個結(jié)點僅有一種孩子，則該二叉樹的總結(jié)點數(shù)為__69__。36．已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點，則該樹有__12__個葉子結(jié)點。第七章復(fù)習(xí)題1．圖中有關(guān)途徑的定義是（A）。A．由頂點和相鄰頂點序偶構(gòu)成的邊所形成的序列B．由不一樣頂點所形成的序列C．由不一樣邊所形成的序列D．上述定義都不是2．設(shè)無向圖的頂點個數(shù)為n，則該圖最多有（B）條邊。A．n-1B．n(n-1)/2C．n(n+1)/2D．n23．一種n個頂點的連通無向圖，其邊的個數(shù)至少為（A）。A．n-1B．nC．n+1D．nlogn4．要連通具有n個頂點的有向圖，至少需要（B）條邊。A．n-lB．nC．n+lD．2n5．n個結(jié)點的完全有向圖具有邊的數(shù)目（D）。A．n*nＢ．n（n＋１）C．n／2D．n*（n－l）6．一種有n個結(jié)點的圖，至少有（B）個連通分量，最多有（D）個連通分量。A．0B．1C．n-1D．N7．在一種無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)（B）倍，在一種有向圖中，所有頂點的入度之和等于所有頂點出度之和的（C）倍。A．1/2B．2C．1D．48．下列哪一種圖的鄰接矩陣一定是對稱矩陣？（B）A．有向圖B．無向圖C．AOV網(wǎng)D．AOE網(wǎng)9.下列說法不對的的是（C）。A．圖的遍歷是從給定的源點出發(fā)每一種頂點僅被訪問一次B．遍歷的基本算法有兩種：深度遍歷和廣度遍歷C．圖的深度遍歷不合用于有向圖D．圖的深度遍歷是一種遞歸過程10．無向圖G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，對該圖進行深度優(yōu)先遍歷，得到的頂點序列對的的是（D）A．a(chǎn),b,e,c,d,fB．a(chǎn),c,f,e,b,dC．a(chǎn),e,b,c,f,dD．a(chǎn),e,d,f,c,b11．下面哪一措施不能判斷出一種有向圖與否有環(huán)（C）：A．深度優(yōu)先遍歷B.拓撲排序C.求最短途徑D.求關(guān)鍵途徑12.在有向圖G的拓撲序列中，若頂點Vi在頂點Vj之前，則下列情形不也許出現(xiàn)的是（D）。A．G中有弧<Vi，Vj>B．G中有一條從Vi到Vj的途徑C．G中沒有弧<Vi,Vj>D．G中有一條從Vj到Vi的途徑14．已知有向圖G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓撲序列是（A）。A．V1,V3,V4,V6,V2,V5,V7B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7D．V1,V2,V5,V3,V4,V6,V715.關(guān)鍵途徑是事件結(jié)點網(wǎng)絡(luò)中（A）。A．從源點到匯點的最長途徑C．最長回路B．從源點到匯點的最短途徑D．最短回路16.下面有關(guān)求關(guān)鍵途徑的說法不對的的是（C）。A．求關(guān)鍵途徑是以拓撲排序為基礎(chǔ)的B．一種事件的最早開始時間同以該事件為尾的弧的活動最早開始時間相似C．一種事件的最遲開始時間為以該事件為尾的弧的活動最遲開始時間與該活動的持續(xù)時間的差D．關(guān)鍵活動一定位于關(guān)鍵途徑上17．下列有關(guān)AOE網(wǎng)的論述中，不對的的是（B）。A．關(guān)鍵活動不按期完畢就會影響整個工程的完畢時間B．任一種關(guān)鍵活動提前完畢，整個工程都將會提前完畢C．所有的關(guān)鍵活動提前完畢，則整個工程將會提前完畢D．某些關(guān)鍵活動提前完畢，會使整個工程提前完畢18.G是一種非連通無向圖，共有28條邊，則該圖至少有9個頂點。19．假如含n個頂點的圖形形成一種環(huán)，則它有n棵生成樹。20.為了實現(xiàn)圖的廣度優(yōu)先搜索，除了一種標志數(shù)組標志已訪問的圖的結(jié)點外，還需隊列寄存被訪問的結(jié)點以實現(xiàn)遍歷。21.設(shè)無向圖G有n個頂點和e條邊，每個頂點Vi的度為di（1<=i<=n〉，則e=______22.Prim（普里姆）算法合用于求______的網(wǎng)的最小生成樹；kruskal（克魯斯卡爾）算法合用于求______的網(wǎng)的最小生成樹。23.AOV網(wǎng)中,結(jié)點表達______,邊表達______。AOE網(wǎng)中,結(jié)點表達______,邊表達______。24.有向圖G可拓撲排序的鑒別條件是______。25.在AOE網(wǎng)中，從源點到匯點途徑上各活動時間總和最長的途徑稱為______。26.已知一無向圖G=（V，E），其中V={a,b,c,d,e}E={(a,b),(a,d),(a,c),(d,c),(b,e)}現(xiàn)用某一種圖遍歷措施從頂點a開始遍歷圖，得到的序列為abecd，則采用的是______遍歷措施。第八章復(fù)習(xí)題1.若查找每個記錄的概率均等，則在具有n個記錄的持續(xù)次序文獻中采用次序查找法查找一種記錄，其平均查找長度ASL為(C)。A.(n-1)/2B.n/2C.(n+1)/2D.n2.對線性表進行二分查找時，規(guī)定線性表必須（B）A.以次序方式存儲B.以次序方式存儲,且數(shù)據(jù)元素有序C.以鏈接方式存儲D.以鏈接方式存儲,且數(shù)據(jù)元素有序3.具有12個關(guān)鍵字的有序表，折半查找的平均查找長度（A）A.3.1B.4C.2.5D.54.哈希查找中k個關(guān)鍵字具有同一哈希值，若用線性探測法將這k個關(guān)鍵字對應(yīng)的記錄存入哈希表中，至少要進行(C)次探測。A．kB.k+1C.k(k+1)/2D.1+k(k+1)/5．分別如下列序列構(gòu)造二叉排序樹，與用其他三個序列所構(gòu)造的成果不一樣的是(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)6.將10個元素散列到100000個單元的哈希表中，則（C）產(chǎn)生沖突。A.一定會B.一定不會C.仍也許會7.下面有關(guān)m階B樹說法對的的是(B)①每個結(jié)點至少有兩棵非空子樹；②樹中每個結(jié)點至多有m一1個關(guān)鍵字;③所有葉子在同一層上;④當插入一種數(shù)據(jù)項引起B(yǎng)樹結(jié)點分裂后，樹長高一層。A．①②③B.②③C.②③④D.③8.設(shè)哈希表長為14，哈希函數(shù)是H(key)=key%11,表中已經(jīng)有數(shù)據(jù)的關(guān)鍵字為15，38，61，84共四個，現(xiàn)要將關(guān)鍵字為49的結(jié)點加到表中，用二次探測再散列法處理沖突，則放入的位置是(D)A．8B．3C．5D．99.在次序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找關(guān)鍵碼值20，需做的關(guān)鍵碼比較次數(shù)為410．在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比較的元素下標依次為6,9,11,1211.在一棵m階B-樹中,若在某結(jié)點中插入一種新關(guān)鍵字而引起該結(jié)點分裂,則此結(jié)點中原有的關(guān)鍵字的個數(shù)是m-1,若在某結(jié)點中刪除一種關(guān)鍵字而導(dǎo)致結(jié)點合并,則該結(jié)點中原有的關(guān)鍵字的個數(shù)是「m/2ù-1。12.直接定址法法構(gòu)造的哈希函數(shù)肯定不會發(fā)生沖突。13.高度為8的平衡二叉樹的結(jié)點數(shù)至少有54個。14.高度為5（除葉子層之外）的三階B-樹至少有31個結(jié)點15.按{12，24，36，90，52，30}的次序構(gòu)成的平衡二叉樹，其根結(jié)點是（C）。A.12B.24C.36D.5216.輸入序列為{20，11，12，……}，構(gòu)造一棵平衡二叉樹，當插入12時，應(yīng)進行（B）型調(diào)整。A.LLB.LRC.RRD.RL17.一棵深度為K的平衡二叉樹，其每個非葉子結(jié)點的平衡因子均為0，則該平衡樹共有()個結(jié)點。18.一棵5階的B樹上，每個非終端結(jié)點所含子樹至少3個第九章復(fù)習(xí)題1．某內(nèi)排序措施的穩(wěn)定性是指(D)。A．該排序算法不容許有相似的關(guān)鍵字記錄B．該排序算法容許有相似的關(guān)鍵字記錄C．平均時間為0（nlogn）的排序措施D．以上都不對2．下列排序算法中，其中（D）是穩(wěn)定的。A.堆排序，冒泡排序B.迅速排序，堆排序C.直接選擇排序，歸并排序D.歸并排序，冒泡排序3．若需在O(nlog2n)的時間內(nèi)完畢對數(shù)組的排序，且規(guī)定排序是穩(wěn)定的，則可選擇的排序措施是（C）。A.迅速排序B.堆排序C.歸并排序D.直接插入排序4．排序趟數(shù)與序列的原始狀態(tài)有關(guān)的排序措施是(CD)排序法。A．插入B.選擇C.冒泡D.迅速5．對下列四種排序措施，在排序中關(guān)鍵字比較次數(shù)同記錄初始排列無關(guān)的是(B)。A．直接插入B.二分法插入C.迅速排序D.歸并排序6．數(shù)據(jù)序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的(C)的兩趟排序后的成果。A.選擇排序B.冒泡排序C.插入排序D.堆排序7．數(shù)據(jù)序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的(A)的兩趟排序后的成果。A.迅速排序B.冒泡排序C.選擇排序D.插入排序8．對一組數(shù)據(jù)（84，47，25，15，21）排序，數(shù)據(jù)的排列次序在排序的過程中的變化為（1）8447251521（2）1547258421（3）1521258447（4）1521254784則采用的排序是(A)。A.選擇B.冒泡C.迅速D.插入9．對序列{15，9，7，8，20，-1，4}進行排序，進行一趟后數(shù)據(jù)的排列變?yōu)閧4，9，-1，8，20，7，15}；則采用的是（C）排序。A.選擇B.迅速C.希爾D.冒泡10．若上題的數(shù)據(jù)經(jīng)一趟排序后的排列為{9，15，7，8，20，-1，4}，則采用的是（C）排序。A．選擇B.堆C.直接插入D.冒泡11．下列排序算法中(B)不能保證每趟排序至少能將一種元素放到其最終的位置上。A.迅速排序B.shell排序C.堆排序D.冒泡排序12．一組記錄的關(guān)鍵碼為（46，79，56，38，40，84），則運用迅速排序的措施，以第一種記錄為基準得到的一次劃提成果為（C）。A．(38,40,46,56,79,