數(shù)據(jù)結(jié)構(gòu)與算法(吳躍)習(xí)題

數(shù)據(jù)結(jié)構(gòu)習(xí)題從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（

）兩大類。A．動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)

B．順序結(jié)構(gòu)、鏈式結(jié)構(gòu)

C．線性結(jié)構(gòu)、非線性結(jié)構(gòu)

D．初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)答案：C下面程序段的時間復(fù)雜度為（）

for(inti=0;i<m;i++)for(intj=0;j<n;j++)a[i][j]=i*j;A.O(m2)B.O(n2)C.O(m*n)D.O(m+n)答案：C設(shè)n為正整數(shù),分析下列各程序段中加下劃線的語句的程序步數(shù)。for(inti=1;i<=n;i++) for(intj=1;j<=n;j++){ c[i][j]=0.0; for(intk=1;k<=n;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j];

}（2）x=0;y=0; for(inti=1;i<=n;i++)for(intj=1;j<=i;j++) for(intk=1;k<=j;k++)

x=x+y;

(3)inti=1,j=1; while(i<=n&&j<=n){

i=i+1;j=j+i; }

i=1時，i=2，j=j+i=1+2=2+1，i=2時，i=3，j=j+i=(2+1)+3=3+1+2，i=3時，i=4，j=j+i=(3+1+2)+4=4+1+2+3，i=4時，i=5，j=j+i=(4+1+2+3)+5=5+1+2+3+4，……

i=k時，i=k+1，j=j+i=(k+1)+(1+2+3+4+…+k)，下面算法的時間復(fù)雜度為（）

intf(unsignedintn){if(n==0||n==1)return1;elsereturnn*f(n-1);}A.O(1)B.O(n)C.O(n2)D.O(n!)答案：B下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是：(1)i=1；

do{i=i*2;}while(i<n);(2)i=n*n;while(i!=1)i=i/2;Log2nLog2n2=2log2n

棧是一種線性表，它的特點是

A。設(shè)用一維數(shù)組A[1,…,n]來表示一個棧，A[n]為棧底，用整型變量T指示當前棧頂位置，A[T]為棧頂元素。往棧中推入（PUSH）一個新元素時，變量T的值

B；從棧中彈出（POP）一個元素時，變量T的值

C。設(shè)?？諘r，有輸入序列a，b，c，經(jīng)過PUSH，POP，PUSH，PUSH，POP操作后，從棧中彈出的元素的序列是

D，變量T的值是

E。供選擇的答案：A：①先進先出②后進先出 ③進優(yōu)于出 ④出優(yōu)于進 ⑤隨機進出B，C： ①加1②減1③不變 ④清0⑤加2⑥減2D：①a,b②b,c ③c,a ④b,a⑤c,b⑥a,cE：①n+1②n+2③n ④n-1⑤n-2ABCDE=2,2,1,6,4

在做進棧運算時，應(yīng)先判別棧是否

A；在做退棧運算時，應(yīng)先判別棧是否

B。當棧中元素為n個，做進棧運算時發(fā)生上溢，則說明該棧的最大容量為

C。為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個棧共享一片連續(xù)的內(nèi)存空間時，應(yīng)將兩棧的

D分別設(shè)在這片內(nèi)存空間的兩端，這樣，只有當

E時，才產(chǎn)生上溢。供選擇的答案：A，B：①空②滿③上溢④下溢C： ①n-1②n③n+1④n/2D：①長度②深度③棧頂④棧底E：①兩個棧的棧頂同時到達?？臻g的中心點②其中一個棧的棧頂?shù)竭_?？臻g的中心點③兩個棧的棧頂在達?？臻g的某一位置相遇④兩個棧均不空，且一個棧的棧頂?shù)竭_另一個棧的棧底ABCDE＝2,1,2,4,3

從一維數(shù)組a[n]中順序查找出一最大值元素的時間復(fù)雜度為（），輸出一個二維數(shù)組b[m][n]中所有元素的時間復(fù)雜度為（）在順序表中插入和刪除一個結(jié)點需平均移動多少個結(jié)點?具體的移動次數(shù)取決于哪兩個因素?答：在等概率情況下，順序表中插入一個結(jié)點需平均移動n/2個結(jié)點。刪除一個結(jié)點需平均移動(n-1)/2個結(jié)點。具體的移動次數(shù)取決于順序表的長度n以及需插入或刪除的位置i。i越接近n則所需移動的結(jié)點數(shù)越少。O(n)O(m*n)何時選用順序表、何時選用鏈表作為線性表的存儲結(jié)構(gòu)為宜?答：1.基于空間的考慮。當要求存儲的線性表長度變化不大，易于事先確定其大小時，為了節(jié)約存儲空間，宜采用順序表；反之，當線性表長度變化大，難以估計其存儲規(guī)模時，采用動態(tài)鏈表作為存儲結(jié)構(gòu)為好。

2.基于時間的考慮。若線性表的操作主要是進行查找，很少做插入和刪除操作時，采用順序表做存儲結(jié)構(gòu)為宜；反之，若需要對線性表進行頻繁地插入或刪除等的操作時，宜采用鏈表做存儲結(jié)構(gòu)。并且，若鏈表的插入和刪除主要發(fā)生在表的首尾兩端，則采用尾指針表示的單循環(huán)鏈表為宜。為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好？答：尾指針是指向終端結(jié)點的指針，用它來表示單循環(huán)鏈表可以使得查找鏈表的開始結(jié)點和終端結(jié)點都很方便，設(shè)一帶頭結(jié)點的單循環(huán)鏈表，其尾指針為rear，則開始結(jié)點和終端結(jié)點的位置分別是rear->next->next和rear,查找時間都是O(1)。

若用頭指針來表示該鏈表，則查找終端結(jié)點的時間為O(n)。

在單鏈表、雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結(jié)點，不知道頭指針，能否將結(jié)點*p從相應(yīng)的鏈表中刪去?若可以，其時間復(fù)雜度各為多少?答：我們分別討論三種鏈表的情況。

1.單鏈表。當我們知道指針p指向某結(jié)點時，能夠根據(jù)該指針找到其直接后繼，但是由于不知道其頭指針，所以無法訪問到p指針指向的結(jié)點的直接前趨。因此無法刪去該結(jié)點。

2.雙鏈表。由于這樣的鏈表提供雙向鏈接，因此根據(jù)已知結(jié)點可以查找到其直接前趨和直接后繼，從而可以刪除該結(jié)點。其時間復(fù)雜度為O(1)。

3.單循環(huán)鏈表。根據(jù)已知結(jié)點位置，我們可以直接得到其后相鄰的結(jié)點位置(直接后繼)，又因為是循環(huán)鏈表，所以我們可以通過查找，得到p結(jié)點的直接前趨。因此可以刪去p所指結(jié)點。其時間復(fù)雜度應(yīng)為O(n)。

下述算法的功能是什么?

LinkListDemo(LinkListL){//L是無頭結(jié)點單鏈表

ListNode*Q,*P;

if(L&&L->next){

Q=L;L=L->next;P=L;

while(P->next)P=P->next;

P->next=Q;

Q->next=NULL;

}

returnL;

}//Demo答：將開始結(jié)點摘下鏈接到終端結(jié)點之后成為新的終端結(jié)點，而原來的第二個結(jié)點成為新的開始結(jié)點，返回新鏈表的頭指針。

鏈棧中為何不設(shè)置頭結(jié)點?

答：鏈棧不需要在頭部附加頭結(jié)點，因為棧都是在尾部進行操作的，如果加了頭結(jié)點，等于要對頭結(jié)點之后的結(jié)點進行操作，反而使算法更復(fù)雜，所以只要有鏈表的頭指針就可以了。

循環(huán)隊列的優(yōu)點是什么?如何判別它的空和滿?答：循環(huán)隊列的優(yōu)點是：它可以克服順序隊列的“假溢出”現(xiàn)象，能夠使存儲隊列的向量空間得到充分的利用。判別循環(huán)隊列的“空”或“滿”不能以頭尾指針是否相等來確定，一般是通過以下幾種方法：一是另設(shè)一變量來區(qū)別隊列的空和滿。二是少用一個元素的空間。每次入隊前測試入隊后頭尾指針是否會重合，如果會重合就認為隊列已滿。三是設(shè)置一計數(shù)器記錄隊列中元素總數(shù)，不僅可判別空或滿，還可以得到隊列中元素的個數(shù)。

設(shè)數(shù)組data[m]作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作后其頭指針front值為（

）

A．front=front+1

B．front=(front+1)%(m-1)

C．front=(front-1)%m

D．front=(front+1)%mD設(shè)長度為n的鏈隊用單循環(huán)鏈表表示，若設(shè)頭指針，則入隊出隊操作的時間為何?若只設(shè)尾指針呢?答：當只設(shè)頭指針時，出隊的時間為1，而入隊的時間需要n，因為每次入隊均需從頭指針開始查找，找到最后一個元素時方可進行入隊操作。若只設(shè)尾指針，則出入隊時間均為1。因為是循環(huán)鏈表，尾指針所指的下一個元素就是頭指針所指元素，所以出隊時不需要遍歷整個隊列。

在一個帶頭結(jié)點的單循環(huán)鏈表中，p指向尾結(jié)點的直接前驅(qū)，則指向頭結(jié)點的指針head可用p表示為head=_____。p－>next－>next數(shù)組Ｑ［ｎ］用來表示一個循環(huán)隊列，ｆ為當前隊列頭元素的前一位置，ｒ為隊尾元素的位置，假定隊列中元素的個數(shù)小于ｎ，計算隊列中元素的公式為（Ａ）r－f;（Ｂ）（n＋f－r）%n;（Ｃ）n＋r－f;（Ｄ）（n＋r－f）%nD為了提高內(nèi)存的利用效率，減少溢出機會，可以讓兩個棧共享一段連續(xù)內(nèi)存空間，應(yīng)如何設(shè)置兩個棧？棧底分別設(shè)在內(nèi)存的兩端設(shè)有編號為1，2，3，4的四輛列車，順序進入一個棧式結(jié)構(gòu)的車站，具體寫出這四輛列車開出車站的所有可能的順序。①全進之后再出情況，只有1種：4，3，2，1②進3個之后再出的情況，有3種，3,4,2,13,2,4,13,2,1,4③進2個之后再出的情況，有4種，2,4,3,12,3,4,12,1,3,42,1,4,3④進1個之后再出的情況，有5種，1,4,3,21,3,2,41,3,4,21,2,3,41,2,4,3設(shè)有一個順序棧S，元素s1，s2，s3，s4，s5，s6依次進棧，如果6個元素的出棧順序為s2，s3，s4，s6，s5，s1，則順序棧的容量至少應(yīng)為多少？3指出下述程序段的功能是什么?voidDemo1(SeqStack*S){

inti;arr[64];n=0;

while(!StackEmpty(S))arr[n++]=Pop(S);

for(i=0,i<n;i++)Push(S,arr);

}答：程序段的功能是將一棧中的元素按反序重新排列，也就是原來在棧頂?shù)脑胤诺綏５?，棧底的元素放到棧頂。此棧中元素個數(shù)限制在64個以內(nèi)。

SeqStackS1,S2,tmp;

DataTypex;

...//假設(shè)棧tmp和S2已做過初始化

while(!StackEmpty(&S1))

{

x=Pop(&S1);

Push(&tmp,x);

}

while(!StackEmpty(&tmp))

{

x=Pop(&tmp);

Push(&S1,x);

Push(&S2,x);

}

答：程序段的功能是利用tmp棧將一個非空棧的所有元素按原樣復(fù)制到一個空棧當中去。

voidDemo2(SeqStack*S,intm)

{

//設(shè)DataType為int型

SeqStackT;inti;

InitStack(&T);

while(!StackEmpty(S))

if((i=Pop(S))!=m)Push(&T,i);

while(!StackEmpty(&T))

{

i=Pop(&T);Push(S,i);

}

}

答：程序段的功能是將一個非空棧中值等于m的元素全部刪去。

voidDemo3(CirQueue*Q)

{

//設(shè)DataType為int型

intx;SeqStackS;

InitStack(&S);

while(!QueueEmpty(Q))

{x=DeQueue(Q);Push(&S,x);}

while(!StackEmpty(&s))

{x=Pop(&S);EnQueue(Q,x);}

}//Demo3

答：程序段的功能是將一個循環(huán)隊列反向排列，原來的隊頭變成隊尾，原來的隊尾變成隊頭。

CirQueueQ1,Q2;//設(shè)DataType為int型

intx,i,m=0;

...

//設(shè)Q1已有內(nèi)容，Q2已初始化過

while(!QueueEmpty(&Q1))

{x=DeQueue(&Q1);EnQueue(&Q2,x);m++;}

for(i=0;i<m;i++)

{x=DeQueue(&Q2);

EnQueue(&Q1,x);EnQueue(&Q2,x);}

答：這段程序的功能是將隊列1的所有元素復(fù)制到隊列2中去，但其執(zhí)行過程是先把隊列1的元素全部出隊，進入隊列2，然后再把隊列2的元素復(fù)制到隊列1中。

假設(shè)有如下的串說明：

chars1[30]="Stocktom,CA",s2[30]="March51999",s3[30];intp;

(1)在執(zhí)行如下的每個語句后p的值是什么?

p=index(s1,'t‘,2);p=index(s2,'9‘,1);p=index(s2,'6‘,1);

答：index(*s,*c,pos)函數(shù)的功能是查找在串s第pos個字符后第一次出現(xiàn)串c的位置，若找到，則返回該位置，否則返回NULL。因此:

執(zhí)行p=index(s1,'t‘,1);后p的值是指向字符t的位置,也就是p=6。

執(zhí)行p=index(s2,'9‘,1);后p的值是指向s2串中第一個9所在的位置,也就是p=10。

執(zhí)行p=index(s2,'6‘,1);之后，p的返回值是0。

假設(shè)有如下的串說明：

chars1[30]="Stocktom,CA",s2[30]="March51999",s3[30];intp;

在執(zhí)行下列語句后，s3的值是什么?

strcpy(s3,s1);strcat(s3,",");strcat(s3,s2);

答：strcpy函數(shù)功能是串拷貝，strcat函數(shù)的功能是串聯(lián)接。所以:

在執(zhí)行strcpy(s3,s1);后，s3的值是"Stocktom,CA"

在執(zhí)行strcat(s3,",");后，s3的值變成"Stocktom,Ca,"

在執(zhí)行完strcat(s3,s2);后，s3的值就成了"Stocktom,Ca,March5,1999"

假設(shè)有如下的串說明：

chars1[30]="Stocktom,CA",s2[30]="March51999",s3[30];intp;

調(diào)用函數(shù)strcmp(s1,s2)的返回值是什么?

答：函數(shù)strcmp(串1，串2)的功能是串比較，按串的大小進行比較，返回大于0，等于0或小于0的值以表示串1比串2大，串1等于串2，串1小于串2。因此在調(diào)用函數(shù)strcmp(s1,s2)后，返回值是大于0的數(shù)(字符比較是以ascii碼值相比的)

假設(shè)有如下的串說明：

chars1[30]="Stocktom,CA",s2[30]="March51999",s3[30];intp;

調(diào)用函數(shù)strcmp(&s1[5],"ton")的返回值是什么?

答：首先，我們要知道&s1[5]是一個地址，當放在函數(shù)strcmp中時，它就表示指向以它為首地址的一個字符串，所以在strcmp(&s1[5],"ton")中，前一個字符串值是"tom,CA",用它和"ton"比較，應(yīng)該是后者更大，所以返回值是小于0的數(shù)。

假設(shè)有如下的串說明：

chars1[30]="Stocktom,CA",s2[30]="March51999",s3[30];intp;

調(diào)用函數(shù)strlen(strcat(s1,s2))的返回值是什么?

答：strlen是求串長的函數(shù)，我們先將s1,s2聯(lián)接起來，值是"Stocktom,CAMarch5,1999",數(shù)一數(shù)有幾個字符,返回值是23。

若目標串的長度為n，模式串的長度為[n/3]，則執(zhí)行模式匹配算法時，在最壞情況下的時間復(fù)雜度是（

）

A．O（1）

B．O（n）

C．O（n2）

D．O（n3）C設(shè)串s1=’ABCDEFG’，s2=’PQRST’，函數(shù)con(x,y)返回x和y串的連接串，subs(s,i,j)返回串s的從序號i開始的j個字符組成的子串，len(s)返回串s的長度，則con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的結(jié)果串是：Ａ．BCDEFＢ．BCDEFGＣ．BCPQRSTＤ．BCDEFEFD假設(shè)有二維數(shù)組A6×8，每個元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。已知A的起始存儲位置（基地址）為1000，則數(shù)組A的體積（存儲量）為

；末尾元素A57的第一個字節(jié)地址為

；若按行存儲時，元素A14的第一個字節(jié)地址為

；若按列存儲時，元素A47的第一個字節(jié)地址為

。288B1282(8+4)×6+1000=1072(6×7＋4)×6＋1000）＝1276設(shè)數(shù)組a[1…60,1…70]的基地址為2048，每個元素占2個存儲單元，若以列序為主序順序存儲，則元素a[32,58]的存儲地址為

___________________

三元數(shù)組表中的每個結(jié)點對應(yīng)于稀疏矩陣的一個非零元素，它包含有三個數(shù)據(jù)項，分別表示該元素的

、

和

。

[(58-1)*60+(32-1)]*2+2048=8950行下標列下標元素值二維數(shù)組M的成員是6個字符（每個字符占一個存儲單元）組成的串，行下標i的范圍從0到8，列下標j的范圍從1到10，則存放M至少需要（）個字節(jié)；M的第8列和第5行共占（）個字節(jié)；若M按行優(yōu)先方式存儲，元素M[8][5]的起始地址與當M按列優(yōu)先方式存儲時的（）元素的起始地址一致。A.90 B.180 C.240 D.540A.108 B.114 C.54 D.60A.M[8][5] B.M[3][10] C.M[5][8] D.M[0][9]答案：DAB數(shù)組A中，每個元素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.SA+225C稀疏矩陣一般的壓縮存儲方式有兩種，即（）答案：三元組和十字鏈表有一個10階對稱矩陣A，采用壓縮存儲方式（以行序為主存儲，且A[0][0]=1），則A[8][5]的地址是（）答案：42若采用三元組壓縮技術(shù)存儲稀疏矩陣，只要把每個元素的行下標和列下標互換，就完成了對該矩陣的轉(zhuǎn)置運算，這種觀點（）A.正確 B.錯誤B1.廣義表((a),a)的表頭是(),表尾是().A.aB.bC.(a)D.((a))2.廣義表((a))的表頭是(),表尾是().A.aB.(a)C.()D.((a))3.廣義表((a,b),c,d)的表頭是(),表尾是().A.aB.bC.(a,b)D.(c,d)4.廣義表(a,b,c,d)的表頭是(),表尾是().A.aB.bC.(a,b)D.(b,c,d)5.廣義表((a,b,c,d))的表頭是(),表尾是().A.aB.()C.(a,b,c,d)D.((a,b,c,d))6.一個廣義表的表頭是一個廣義表,這個斷言是().A.正確的B.錯誤的7.一個廣義表的表尾是一個廣義表,這個斷言是().A.正確的B.錯誤的CCBCCDADCBBA利用廣義表的head和tail操作寫出函數(shù)表達式，把以下各題中的單元素banana從廣義表中分離出來：

(1)L1(apple,pear,banana,orange) (2)L2((apple,pear),(banana,orange)) (3)L3(((apple),(pear),(banana),(orange))) (4)L4((((apple))),((pear)),(banana),orange) (5)L5((((apple),pear),banana),orange) (6)L6(apple,(pear,(banana),orange))L1(apple,pear,banana,orange)T(L1)L(pear,banban,orange)T(L)L(banana,orange)H(L)bananaH(T(T(L1)))L2((apple,pear),(banana,orange))T(L2)L((banana,orange))H(L)L(banana,orage)H(L)bananaH(H(T(L2)))L3(((apple),(pear),(banana),(orange)))H(L3)L((apple),(pear),(banana),(orange))T(L)L((pear),(banana),(orange))T(L)L((banana),(orange))H(L)L(banana)H(L)bananaH(H(T(T(H(L3)))))L4((((apple))),((pear)),(banana),orange)T(L4)L(((pear)),(banana),orange)T(L)L((banana),orange)H(L)L(banana)H(L)bananaH(H(T(T(L4))))L5((((apple),pear),banana),orange)H(L5)L(((apple),pear),banana)T(L)L(banana)H(L)bananaH(T(H(L5)))(6)L6(apple,(pear,(banana),orange))T(L6)L((pear,(banana),orange))H(L)L(pear,(banana),orange)T(L)L((banana),orange)H(L)L(banana)H(L)bananaH(H(T(H(T()))))如圖的4棵樹二叉樹中，（）不是完全二叉樹。

ABCDC在線索化二叉樹中，t所指結(jié)點沒有左子樹的充要條件是（）A.t->left=NULLB.t->ltag=1C.t->ltag=1且t->left=NULLD.以上都不對二叉樹按某種順序線索化后，任意結(jié)點均有指向其前驅(qū)和后繼的線索，這種說法（）A.正確B.錯誤

用二叉鏈表法存儲包含n個結(jié)點的二叉樹，結(jié)點的2n個指針區(qū)域中有n+1個為空指針。

A.正確B.錯誤BBA二叉樹的前序遍歷序列中，任意一個結(jié)點均處在其子女結(jié)點的前面，這種說法（）

A.正確B.錯誤設(shè)深度為h的二叉樹上只有度為0和度為2的結(jié)點，則此類二叉樹中所包含的結(jié)點數(shù)至少為（）

A.2hB.2h-1C2h+1Dh+1AB某二叉樹的前序遍歷節(jié)點訪問順序是ａｂｄｇｃｅｆｈ，中序遍歷訪問順序是ｄｇｂａｅｃｈｆ，則其后序遍歷的節(jié)點訪問順序是

ＡｂｄｇｃｅｆｈａＢｇｄｂｅｃｆｈａＣｂｄｇａｅｃｈｆＤｇｄｂｅｈｆｃａD按照二叉樹的定義，具有３個節(jié)點的二叉樹有

種Ａ３Ｂ４Ｃ５Ｄ６一棵二叉樹如圖所示，其中序遍歷是

ＡａｂｄｇｃｅｆｈＢｄｇｂａｅｃｈｆＣｇｄｂｅｈｆｃａＤａｂｃｄｅｆｇｈCdｈabcｅｇｆB在一非空二叉樹的中序遍歷序列中，根節(jié)點的右邊

Ａ只有右子樹上的所有節(jié)點Ｂ只有右子樹上的部分節(jié)點Ｃ只有左子樹的部分節(jié)點Ｄ只有左子樹上的所有節(jié)點任何一棵二叉樹的葉子節(jié)點在先序，中序和后序遍歷序列中的相對次序

Ａ不發(fā)生改變Ｂ發(fā)生改變Ｃ不能確定Ｄ以上都不對AA如果某二叉樹的前序是ｓｔｕｗｖ，中序是ｕｗｔｖｓ，那么后序為

ＡｕｗｖｔｓＢｖｗｕｔｓＣｗｕｖｔｓＤｗｕｔｓｖ設(shè)n，m為一棵二叉樹上的兩個節(jié)點，在中序遍歷是，n在m前面的條件是

An在m右方Bn是m祖先Cn在m左方Dn是m子孫CC.線索二叉樹是一種

結(jié)構(gòu)。A邏輯B邏輯和存儲C物理D線性一棵度為2的樹與一棵二叉樹有何區(qū)別？

C在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的（）倍。a.1/2b.1c.2d.4在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（）倍。a.1/2b.1c.2d.4CB一個有n個頂點的無向圖最多有（）條邊。a.nb.n(n-1)c.n(n-1)/2d.2n在一個具有n個頂點的無向圖中，要連通全部頂點至少需要（）條邊

a.nb.n+1c.n-1d.n-2CC對于一個具有ｎ個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是（）a.nb.(n-1)2c.n-1d.n

2對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為（），所有鄰接表中的結(jié)點總數(shù)是（）。1：a.nb.n+1c.n-1dn+e2:a.e/2b.ec.2ed.n+e

DAC已知一個圖如圖所示，若從頂點a出發(fā)按深度搜索法進行遍歷，則可能得到的一種頂點序列為（）按廣度搜索法進行遍歷，則可能得到的一種頂點序列為（）A.a,b,e,c,d,fB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,bAa,b,c,e,d,fB.a,b,c,e,f,dC.a,e,b,c,f,dD.a,c,f,d,e,bacefbdDB已知一有向圖的鄰接表存儲結(jié)構(gòu)如圖所示。根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點v1出發(fā)，所得到的頂點序列是（）

a.v1,v2,v3,v5.v4b.v1,v2,v3,v4,v5c.v1,v3,v4,v5,v2d.v1,v4,v3,v5,v2123453244524C已知一有向圖的鄰接表存儲結(jié)構(gòu)如圖所示。根據(jù)有向圖的廣度優(yōu)先遍歷算法，從頂點v1出發(fā)，所得到的頂點序列是（）a.v1,v2,v3,v4,v5b.v1,v3,v2,v4,v5c.v1,v2,v3,v5,v4dv1,v4,v3,v5,v2123453244524B采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的（）a先序遍歷b中序遍歷c后序遍歷d按層遍歷采取鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的（）a先序遍歷b中序遍歷c后續(xù)遍歷d按層遍歷

AD用鄰接表表示圖進行廣度優(yōu)先遍歷時，通常是采用

來實現(xiàn)算法的。A．棧B.隊列C.樹D.圖

用鄰接表表示圖進行深度優(yōu)先遍歷時，通常是采用

來實現(xiàn)算法的。A．棧B.隊列C.樹D.圖BA判定一個有向圖是否存在回路除了可以利用拓撲排序方法之外，還可以利用（）a求關(guān)鍵路徑的方法b求最短路徑的dijkstra方法C廣度優(yōu)先遍歷法d深度優(yōu)先遍歷法任何一個無向連通圖的最小生成樹（）A．只有一棵B.一棵或多棵C.一定有多棵D.可能不存在

DB在無權(quán)圖G的鄰接矩陣A中，若（vi,vj）或<vi,vj>屬于圖G的邊集合，則對應(yīng)元素A[i][j]等于（）否則等于（）已知一個圖用鄰接矩陣表示，計算第i個結(jié)點的入度的方法是_____________刪除所有從第i個結(jié)點出發(fā)的邊的方法是___________10第i列非零元素之和

將矩陣第i行全部置為零

如果n個頂點的圖是一個環(huán)，則它有

____棵生成樹。n個頂點e條邊的圖，若采用鄰接矩陣存儲，則空間復(fù)雜度為_______。

n個頂點e條邊的圖，若采用鄰接表存儲，則空間復(fù)雜度為

。設(shè)有一稀疏圖G，則G采用

存儲較省空間。設(shè)有一稠密圖G，則G采用

存儲較省空間。

nO(n2)O(n+e)鄰接表鄰接矩陣用Dijkstra算法求某一頂點到其余各頂點間的最短路徑是按路徑長度

的次序來得到最短路徑的。拓撲排序算法是通過重復(fù)選擇具有

個前驅(qū)頂點的過程來完成的

遞增0在數(shù)據(jù)的存放無規(guī)律而言的線性表中進行檢索的最佳方法是__________順序查找法適合于存儲結(jié)構(gòu)為（）的線性表

a散列存儲b順序存儲或鏈接存儲

c壓縮存儲d索引存儲對線性表進行二分查找時，要求線性表必須（）a以順序方式存儲b以鏈接方式存儲c以順序方式存儲，且結(jié)點按關(guān)鍵字有序排序d以鏈接方式存儲，且結(jié)點按關(guān)鍵字有序排序順序查找

bC采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為（）a.nb.n/2c(n+1)/2d.(n-1)/2采用二分法查找長度為n的線性表時，每個元素的平均查找長度為（）a.O(n2)bO(nlog2n)cO(n)dO(log2n)二分法查找和二叉排序樹的時間性能（）a相同b不相同Cdb有一個有序表為(n=13){1,3,9,12,32,41,45,62,75,77,82,95,100},當二分查找值82為的結(jié)點時（）次比較后查找成功a1b2c4d8設(shè)哈希表長m＝14，哈希函數(shù)H（key）＝key％11。表中已有4個結(jié)點：addr（15）＝4addr（38）＝5addr（61）＝6addr（84）＝7其余地址為空,如用二次探測再散列處理沖突，關(guān)鍵字為49的結(jié)點的地址是（）a8b3c5d9Cd有一個長度為12的有序表，按二分查找發(fā)對該表進行查找，在表內(nèi)個元素等概率情況下查找成功所需的平均比較次數(shù)為（）a35/12b37/12c39/12d43/12順序查找法的平均查找長度為（）；二分查找法的平均查找長度（）;分塊查找法（以順序查找確定塊）的平均查找長度（）;分塊查找法（以二分法查找確定塊）的平均查找長度（）b(n+1)/2((n+1)*log2(n+1))/n-1(s^2+2s+n)/2slog(n/s+1)+s/2在各種查找方法中，平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法是在分塊查找法首先查找（）再查找相應(yīng)的（）在散列函數(shù)Ｈ（key）=key%p中p應(yīng)?。ǎ┘僭O(shè)在有序線性表A[1.20]上進行二分查找，則比較一次查找成功的結(jié)點數(shù)為(),則比較二次查找成功的結(jié)點數(shù)為（），則比較三次查找成功的結(jié)點數(shù)為（）則比較4次查找成功的結(jié)點數(shù)為（）則比較5次查找成功的結(jié)點數(shù)為（）平均查找長度為（）哈希表查找法索引塊素數(shù)1個2個4個8個5個3.7在散列存儲中，裝填因子α的值越大則存取元素時發(fā)生沖突的可能性就（）α值越小則（）

折半查找有序表（4，6，10，12，20，30，50，70，88，100）（n=10）。若查找表中元素58，則它將依次與表中

比較大小，查找結(jié)果是失敗。A．20，70，30，50B．30，88，70，50C．20，50D．30，88，50

越大越小A要進行線性查找，則線性表

A；要進行二分查找，則線性表

B；要進行散列查找，則線性表

C。某順序存儲的表格，其中有90000個元素，已按關(guān)鍵項的值的上升順序排列。現(xiàn)假定對各個元素進行查找的概率是相同的，并且各個元素的關(guān)鍵項的值皆不相同。當用順序查找法查找時，平均比較次數(shù)約為

D，最大比較次數(shù)為

E。供選擇的答案：A~C：①必須以順序方式存儲②必須以鏈表方式存儲③必須以散列方式存儲④既可以以順序方式，也可以以鏈表方式存儲⑤必須以順序方式存儲且數(shù)據(jù)元素已按值遞增或遞減的次序排好⑥必須以鏈表方式存儲且數(shù)據(jù)元素已按值遞增或遞減的次序排好D，E：①25000②30000③45000④90000答案：A=④B=⑤C=③D＝③E＝④

在二叉排序樹中，每個結(jié)點的關(guān)鍵碼值

A

，

B一棵二叉排序，即可得到排序序列。同一個結(jié)點集合，可用不同的二叉排序樹表示，人們把平均檢索長度最短的二叉排序樹稱作最佳二叉排序，最佳二叉排序樹在結(jié)構(gòu)上的特點是

C。供選擇的答案A：①比左子樹所有結(jié)點的關(guān)鍵碼值大，比右子樹所有結(jié)點的關(guān)鍵碼值?、诒茸笞訕渌薪Y(jié)點的關(guān)鍵碼值小，比右子樹所有結(jié)點的關(guān)鍵碼值大③比左右子樹的所有結(jié)點的關(guān)鍵碼值都大④與左子樹所有結(jié)點的關(guān)鍵碼值和右子樹所有結(jié)點的關(guān)鍵碼值無必然的大小關(guān)系B:①前序遍歷②中序（對稱）遍歷③后序遍歷④層次遍歷C：①除最下二層可以不滿外，其余都是充滿的②除最下一層可以不滿外，其余都是充滿的③每個結(jié)點的左右子樹的高度之差的絕對值不大于1④最下層的葉子必須在最左邊答案：A＝①B＝②C＝②散列法存儲的基本思想是根據(jù)

A

來決定

B

，沖突指的是

C，處理沖突的兩類主要方法是

D

。供選擇的答案A，B：①存儲地址②元素的符號③元素個數(shù)④關(guān)鍵碼值⑤非碼屬性⑥平均檢索長度⑦負載因子⑧散列表空間C:①兩個元素具有相同序號②兩個元素的關(guān)鍵碼值不同，而非碼屬性相同③不同關(guān)鍵碼值對應(yīng)到相