電子科大from知博書(shū)店數(shù)據(jù)結(jié)構(gòu)習(xí)題

數(shù)據(jù)結(jié)構(gòu)典型習(xí)題知博書(shū)店1、下面程序段的時(shí)間復(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ù),分析下列各程序段中加下劃線的語(yǔ)句的程序步數(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時(shí)，i=2，j=j+i=1+2=2+1，i=2時(shí)，i=3，j=j+i=(2+1)+3=3+1+2，i=3時(shí)，i=4，j=j+i=(3+1+2)+4=4+1+2+3，i=4時(shí)，i=5，j=j+i=(4+1+2+3)+5=5+1+2+3+4，……

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

int

f(unsigned

intn){

if(n==0||n==1)return1;elsereturnn*f(n-1);}A.O(1)B.O(n)C.O(n2)D.On!)答案：B棧是一種線性表，它的特點(diǎn)是

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

B；從棧中彈出（POP）一個(gè)元素時(shí)，變量T的值

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

D，變量T的值是

E。供選擇的答案：A：①先進(jìn)先出②后進(jìn)先出 ③進(jìn)優(yōu)于出 ④出優(yōu)于進(jìn) ⑤隨機(jī)進(jìn)出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

在做進(jìn)棧運(yùn)算時(shí)，應(yīng)先判別棧是否

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

B。當(dāng)棧中元素為n個(gè)，做進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說(shuō)明該棧的最大容量為

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

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

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

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

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

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

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

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

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

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

下述算法的功能是什么?

LinkList

Demo(LinkListL){//L是無(wú)頭結(jié)點(diǎn)單鏈表

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答：將開(kāi)始結(jié)點(diǎn)摘下鏈接到終端結(jié)點(diǎn)之后成為新的終端結(jié)點(diǎn)，而原來(lái)的第二個(gè)結(jié)點(diǎn)成為新的開(kāi)始結(jié)點(diǎn)，返回新鏈表的頭指針。

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

答：鏈棧不需要在頭部附加頭結(jié)點(diǎn)，因?yàn)闂６际窃谖膊窟M(jìn)行操作的，如果加了頭結(jié)點(diǎn)，等于要對(duì)頭結(jié)點(diǎn)之后的結(jié)點(diǎn)進(jìn)行操作，反而使算法更復(fù)雜，所以只要有鏈表的頭指針就可以了。

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

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

）

A．front=front+1

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

C．front=(front-1)%m

D．front=(front+1)%mD設(shè)長(zhǎng)度為n的鏈隊(duì)用單循環(huán)鏈表表示，若設(shè)頭指針，則入隊(duì)出隊(duì)操作的時(shí)間為何?若只設(shè)尾指針呢?答：當(dāng)只設(shè)頭指針時(shí)，出隊(duì)的時(shí)間為1，而入隊(duì)的時(shí)間需要n，因?yàn)槊看稳腙?duì)均需從頭指針開(kāi)始查找，找到最后一個(gè)元素時(shí)方可進(jìn)行入隊(duì)操作。若只設(shè)尾指針，則出入隊(duì)時(shí)間均為1。因?yàn)槭茄h(huán)鏈表，尾指針?biāo)傅南乱粋€(gè)元素就是頭指針?biāo)冈兀猿鲫?duì)時(shí)不需要遍歷整個(gè)隊(duì)列。

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

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

SeqStackS1,S2,tmp;

DataTypex;

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

while(!StackEmpty(&S1))

{

x=Pop(&S1);

Push(&tmp,x);

}

while(!StackEmpty(&tmp))

{

x=Pop(&tmp);

Push(&S1,x);

Push(&S2,x);

}

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

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);

}

}

答：程序段的功能是將一個(gè)非空棧中值等于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

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

CirQueueQ1,Q2;//設(shè)DataType

為int

型

intx,i,m=0;

...

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

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);}

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

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

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

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

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

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

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

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

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

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

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

在執(zhí)行下列語(yǔ)句后，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è)有如下的串說(shuō)明：

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

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

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

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

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

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

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

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

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

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

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

若目標(biāo)串的長(zhǎng)度為n，模式串的長(zhǎng)度為[n/3]，則執(zhí)行模式匹配算法時(shí)，在最壞情況下的時(shí)間復(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的從序號(hào)i開(kāi)始的j個(gè)字符組成的子串，len(s)返回串s的長(zhǎng)度，則con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的結(jié)果串是：Ａ．BCDEFＢ．BCDEFGＣ．BCPQRSTＤ．BCDEFEFD假設(shè)有二維數(shù)組A6×8，每個(gè)元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知A的起始存儲(chǔ)位置（基地址）為1000，則數(shù)組A的體積（存儲(chǔ)量）為

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

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

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

。288B1282(8+4)×6+1000=1072(6×7＋4)×6＋1000）＝1276設(shè)數(shù)組a[1…60,1…70]的基地址為2048，每個(gè)元素占2個(gè)存儲(chǔ)單元，若以列序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a[32,58]的存儲(chǔ)地址為

___________________

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

、

和

。

[(58-1)*60+(32-1)]*2+2048=8950行下標(biāo)列下標(biāo)元素值二維數(shù)組M的成員是6個(gè)字符（每個(gè)字符占一個(gè)存儲(chǔ)單元）組成的串，行下標(biāo)i的范圍從0到8，列下標(biāo)j的范圍從1到10，則存放M至少需要（）個(gè)字節(jié)；M的第8列和第5行共占（）個(gè)字節(jié)；若M按行優(yōu)先方式存儲(chǔ)，元素M[8][5]的起始地址與當(dāng)M按列優(yōu)先方式存儲(chǔ)時(shí)的（）元素的起始地址一致。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中，每個(gè)元素A的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)，元素A[8][5]的起始地址為（）

A.SA+141 B.SA+144 C.SA+222 D.SA+225C稀疏矩陣一般的壓縮存儲(chǔ)方式有兩種，即（）答案：三元組和十字鏈表有一個(gè)10階對(duì)稱(chēng)矩陣A，采用壓縮存儲(chǔ)方式（以行序?yàn)橹鞔鎯?chǔ)，且A[0][0]=1），則A[8][5]的地址是（）答案：42若采用三元組壓縮技術(shù)存儲(chǔ)稀疏矩陣，只要把每個(gè)元素的行下標(biāo)和列下標(biāo)互換，就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算，這種觀點(diǎn)（）A.正確 B.錯(cuò)誤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.一個(gè)廣義表的表頭是一個(gè)廣義表,這個(gè)斷言是().A.正確的B.錯(cuò)誤的7.一個(gè)廣義表的表尾是一個(gè)廣義表,這個(gè)斷言是().A.正確的B.錯(cuò)誤的CCBCCDADCBBA利用廣義表的head和tail操作寫(xiě)出函數(shù)表達(dá)式，把以下各題中的單元素banana從廣義表中分離出來(lái)：

(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棵樹(shù)二叉樹(shù)中，（

）不是完全二叉樹(shù)。

ABCDC在線索化二叉樹(shù)中，t所指結(jié)點(diǎn)沒(méi)有左子樹(shù)的充要條件是（

）A.t->left=NULLB.t->ltag=1C.t->ltag=1且t->left=NULLD.以上都不對(duì)二叉樹(shù)按某種順序線索化后，任意結(jié)點(diǎn)均有指向其前驅(qū)和后繼的線索，這種說(shuō)法（

）A.正確B.錯(cuò)誤

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

A.正確B.錯(cuò)誤BBA二叉樹(shù)的前序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面，這種說(shuō)法（

）

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

）

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

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

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

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

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

Ａ不發(fā)生改變Ｂ發(fā)生改變Ｃ不能確定Ｄ以上都不對(duì)AA如果某二叉樹(shù)的前序是ｓｔｕｗｖ，中序是ｕｗｔｖｓ，那么后序?yàn)?/p>

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

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

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

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

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

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

DAC已知一個(gè)圖如圖所示，若從頂點(diǎn)a出發(fā)按深度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）按廣度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）A.a,b,e,c,d,f

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

C.a,e,b,c,f,d

D.a,e,d,f,c,bAa,b,c,e,d,fB.a,b,c,e,f,d

C.a,e,b,c,f,d

D.a,c,f,d,e,bacefbdDB已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如圖所示。根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點(diǎn)v1出發(fā)，所得到的頂點(diǎn)序列是（）

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

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

來(lái)實(shí)現(xiàn)算法的。A．棧B.隊(duì)列C.樹(shù)D.圖

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

來(lái)實(shí)現(xiàn)算法的。A．棧B.隊(duì)列C.樹(shù)D.圖BA判定一個(gè)有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄖ?，還可以利用（）a求關(guān)鍵路徑的方法b求最短路徑的dijkstra方法C廣度優(yōu)先遍歷法d深度優(yōu)先遍歷法任何一個(gè)無(wú)向連通圖的最小生成樹(shù)（）A．只有一棵B.一棵或多棵C.一定有多棵D.可能不存在

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

將矩陣第i行全部置為零

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

____棵生成樹(shù)。n個(gè)頂點(diǎn)e條邊的圖，若采用鄰接矩陣存儲(chǔ)，則空間復(fù)雜度為_(kāi)______。

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

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

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

存儲(chǔ)較省空間。

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

的次序來(lái)得到最短路徑的。拓?fù)渑判蛩惴ㄊ峭ㄟ^(guò)重復(fù)選擇具有

個(gè)前驅(qū)頂點(diǎn)的過(guò)程來(lái)完成的

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

a散列存儲(chǔ)b順序存儲(chǔ)或鏈接存儲(chǔ)

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

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

A；要進(jìn)行二分查找，則線性表

B；要進(jìn)行散列查找，則線性表

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

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

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

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

A

，

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

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

A

來(lái)決定

B

，沖突指的是

C，處理沖突的兩類(lèi)主要方法是

D

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