南京曉莊學(xué)院數(shù)據(jù)結(jié)構(gòu)試題庫答案

...wd......wd......wd...數(shù)據(jù)構(gòu)造與算法習(xí)題冊〔課后局部參考答案〕《數(shù)據(jù)構(gòu)造與算法》課程組目錄課后習(xí)題局部第一章緒論1第二章線性表3第三章棧和隊列5第四章串8第五章數(shù)組和廣義表10第六章樹和二叉樹13第七章圖16第九章查找20第十章排序23第一章緒論一.填空題1.從邏輯關(guān)系上講，數(shù)據(jù)構(gòu)造的類型主要分為集合、線性構(gòu)造、樹構(gòu)造和圖構(gòu)造。2.數(shù)據(jù)的存儲構(gòu)造主要有順序存儲和鏈?zhǔn)酱鎯煞N基本方法，不管哪種存儲構(gòu)造，都要存儲兩方面的內(nèi)容：數(shù)據(jù)元素和數(shù)據(jù)元素之間的關(guān)系。3.算法具有五個特性，分別是有窮性、確定性、可行性、輸入、輸出。4.算法設(shè)計要求中的強健性指的是算法在發(fā)生非法操作時可以作出處理的特性。二.選擇題1.順序存儲構(gòu)造中數(shù)據(jù)元素之間的邏輯關(guān)系是由C表示的，鏈接存儲構(gòu)造中的數(shù)據(jù)元素之間的邏輯關(guān)系是由D表示的。A線性構(gòu)造B非線性構(gòu)造C存儲位置D指針2.假設(shè)有如下遺產(chǎn)繼承規(guī)則：丈夫和妻子可以相互繼承遺產(chǎn)；子女可以繼承父親或母親的遺產(chǎn)；子女間不能相互繼承。則表示該遺產(chǎn)繼承關(guān)系的最適宜的數(shù)據(jù)構(gòu)造應(yīng)該是B。A樹B圖C線性表D集合3.算法指的是A。A對特定問題求解步驟的一種描述，是指令的有限序列。B計算機程序C解決問題的計算方法D數(shù)據(jù)處理三.簡答題1.分析以下各程序段，并用大O記號表示其執(zhí)行時間。(1)(2)i=1;k=0;i=1;k=0;While(i<n-1)do{{k=k+10*i;k=k+10*i;i++;i++;}}while(i<=n)⑴基本語句是k=k+10*i，共執(zhí)行了n-2次，所以T(n)=O(n)。

⑵基本語句是k=k+10*i，共執(zhí)行了n次，所以T(n)=O(n)。2.設(shè)有數(shù)據(jù)構(gòu)造〔D，R〕，其中D={1,2,3,4,5,6}，R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。試畫出其邏輯構(gòu)造圖并指出屬于何種構(gòu)造。其邏輯構(gòu)造圖如下所示，它是一種圖構(gòu)造。3.求多項式A(x)的算法可根據(jù)以下兩個公式之一來設(shè)計：⑴A(x)=anxn+an-1xn-1+…+a1x+a0⑵A(x)=(…(anx+an-1)x+…+a1)x)+a0根據(jù)算法的時間復(fù)雜度分析對比這兩種算法的優(yōu)劣。第二種算法的時間性能要好些。第一種算法需執(zhí)行大量的乘法運算，而第二種算法進(jìn)展了優(yōu)化，減少了不必要的乘法運算。第二章線性表一.填空題1.在順序表中，等概率情況下，插入和刪除一個元素平均需移動表長的一半個元素，具體移動元素的個數(shù)與表長和插入的位置有關(guān)。2.在一個長度為n的順序表的第i〔1≤i≤n+1〕個元素之前插入一個元素，需向后移動n-i+1個元素，刪除第i〔1≤i≤n〕個元素時，需向前移動n-i個元素。3.在單循環(huán)鏈表中，由rear指向表尾，在表尾插入一個結(jié)點s的操作順序是s->next=rear->next;rear->next=s;rear=s;；刪除開場結(jié)點的操作順序為q=rear->next->next;rear->next->next=q->next;deleteq;。二.選擇題1.數(shù)據(jù)在計算機存儲器內(nèi)表示時物理地址與邏輯地址一樣并且是連續(xù)的，稱之為：CA存儲構(gòu)造B邏輯構(gòu)造C順序存儲構(gòu)造D鏈?zhǔn)酱鎯?gòu)造2.在n個結(jié)點的順序表中，算法的時間復(fù)雜度是O〔1〕的操作是：AA訪問第i個結(jié)點〔1≤i≤n〕和求第i個結(jié)點的直接前驅(qū)〔2≤i≤n〕B在第i個結(jié)點后插入一個新結(jié)點〔1≤i≤n〕C刪除第i個結(jié)點〔1≤i≤n〕D將n個結(jié)點從小到大排序3.線性表L在B情況下適用于使用鏈?zhǔn)綐?gòu)造實現(xiàn)。A需經(jīng)常修改L中的結(jié)點值B需不斷對L進(jìn)展刪除插入CL中含有大量的結(jié)點DL中結(jié)點構(gòu)造復(fù)雜4.單鏈表的存儲密度CA大于1B等于1C小于1D不能確定三.判斷題1.線性表的邏輯順序和存儲順序總是一致的。F2.線性表的順序存儲構(gòu)造優(yōu)于鏈接存儲構(gòu)造。F3.設(shè)p，q是指針，假設(shè)p=q，則*p=*q。F4.線性構(gòu)造的基本特征是：每個元素有且僅有一個直接前驅(qū)和一個直接后繼。F四.簡答題1.分析以下情況下，采用何種存儲構(gòu)造更好些。(1)假設(shè)線性表的總長度基本穩(wěn)定，且很少進(jìn)展插入和刪除操作，但要求以最快的速度存取線性表中的元素。(2)如果n個線性表同時并存，并且在處理過程中各表的長度會動態(tài)發(fā)生變化。(3)描述一個城市的設(shè)計和規(guī)劃。⑴應(yīng)選用順序存儲構(gòu)造。很少進(jìn)展插入和刪除操作，所以空間變化不大，且需要快速存取，所以應(yīng)選用順序存儲構(gòu)造。

⑵應(yīng)選用鏈?zhǔn)酱鎯?gòu)造。鏈表容易實現(xiàn)表容量的擴大，適合表的長度動態(tài)發(fā)生變化。

⑶應(yīng)選用鏈?zhǔn)酱鎯?gòu)造。因為一個城市的設(shè)計和規(guī)劃涉及活動很多，需要經(jīng)常修改、擴大和刪除各種信息，才能適應(yīng)不斷開展的需要。而順序表的插入、刪除的效率低，故不適宜。五.算法設(shè)計1.數(shù)組A[n]中的元素為整型，設(shè)計算法將其調(diào)整為左右兩局部，左邊所有元素為奇數(shù)，右邊所有元素為偶數(shù)，并要求算法的時間復(fù)雜度為O(n)。2.線性表存放在整型數(shù)組A[arrsize]的前elenum個單元中，且遞增有序。編寫算法，將元素x插入到線性表的適當(dāng)位置上，以保持線性表的有序性，并且分析算法的時間復(fù)雜度。intinsert(datatypeA[],int*elenum,datatypex)

/*設(shè)elenum為表的最大下標(biāo)*/

{if(*elenum==arrsize-1)

return0;

/*表已滿，無法插入*/

else{i=*elenum;

while(i>=0&&A[i]>x)

/*邊找位置邊移動*/

{A[i+1]=A[i];

i--;

}

A[i+1]=x;

/*找到的位置是插入位的下一位*/

(*elenum)++;

return1;

/*插入成功*/

}

}O〔n〕第三章棧和隊列一.填空題1.設(shè)有一個空棧，棧頂指針為1000H，現(xiàn)有輸入序列為1.2.3.4.5，經(jīng)過push，push，pop，push，pop，push，push后，輸出序列是23，棧頂指針為1003H。2.棧通常采用的兩種存儲構(gòu)造是順序棧、鏈棧；其判定?？盏臈l件分別是TOP=-1、TOP=NULL，判定棧滿的條件分別是TOP=數(shù)組長度、存儲空間滿。3.棧可作為實現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)構(gòu)造。4.表達(dá)式a*(b+c)-d的后綴表達(dá)式是abc+*d-。二.選擇題1.假設(shè)一個棧的輸入序列是1，2，3，…，n，輸出序列的第一個元素是n，則第i個輸出元素是D。A不確定Bn-iCn-i-1Dn-i+12.設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1.e2.e3.e4.e5.e6依次通過棧S，一個元素出棧后即進(jìn)入隊列Q，假設(shè)6個元素出隊的順序是e2.e4.e3.e6.e5.e1，則棧S的容量至少應(yīng)該是C。A6B4C3D23.一個棧的入棧序列是1，2，3，4，5，則棧的不可能的輸出序列是C。A54321B45321C43512D12345三.判斷題1.有n個元素依次進(jìn)棧，則出棧序列有(n-1)/2種。F2.棧可以作為實現(xiàn)過程調(diào)用的一種數(shù)據(jù)構(gòu)造。T3.在棧滿的情況下不能做進(jìn)棧操作，否則將產(chǎn)生“上溢〞。T4.在循環(huán)隊列中，front指向隊頭元素的前一個位置，rear指向隊尾元素的位置，則隊滿的條件是front=rear。F四.簡答題1.設(shè)有一個棧，元素進(jìn)棧的次序為A，B，C，D，E，能否得到如下出棧序列，假設(shè)能，請寫出操作序列，假設(shè)不能，請說明原因。⑴C，E，A，B，D⑵C，B，A，D，E⑴不能，因為在C、E出棧后，A一定在棧中，而且在B的下面，不可能先于B出棧⑵可以，設(shè)Ｉ為進(jìn)棧操作，Ｏ為入棧操作，則其操作序列為IIIOOOIOIO。2.在操作序列push(1).push(2).pop.push(5).push(7).pop.push(6)之后，棧頂元素和棧底元素分別是什么〔push(k)表示k入棧，pop表示棧頂元素出棧。〕棧頂元素為6，棧底元素為1。3.在操作序列EnQueue(1).EnQueue(3).DeQueue.EnQueue(5).EnQueue(7).DeQueue.EnQueue(9)之后，隊頭元素和隊尾元素分別是什么〔EnQueue(k)表示整數(shù)k入隊，DeQueue表示隊頭元素出隊〕。隊頭元素為5，隊尾元素為9。4.簡述以下算法的功能〔棧的元素類型SElemType為int〕。(1)statusalgo1(StackS,inte){ StackT;intd;InitStack(T); while(!StackEmpty(S)){ Pop(S,d); if(d!=e)Push(T,d); } while(!StackEmpty(T)){ Pop(T,d);Push(S,d); }}//S中如果存在e，則刪除它。(2)voidalgo2(Queue&Q) { StackS;intd;InitStack(S); while(!QueueEmpty(Q)) { DeQueue(Q,d);Push(S,d); } while(!StackEmpty(S)) { Pop(S,d);EnQueue(Q,d); } }//隊列逆置五.算法設(shè)計1.試寫一個判別表達(dá)式中開、閉括號是否配對出現(xiàn)的算法BOOLBracketCorrespondency(chara[]){ inti=0; Stacks; InitStack(s); ElemTypex; while(a[i]){ switch(a[i]){ case'(': Push(s,a[i]); break; case'[': Push(s,a[i]); break; case')': GetTop(s,x); if(x=='(') Pop(s,x); elsereturnFALSE; break; case']': GetTop(s,x); if(x=='[')Pop(s,x); elsereturnFALSE; break; default: break; } i++; } if(s.size!=0)returnFALSE; returnTRUE;}2.假設(shè)稱正讀和反讀都一樣的字符序列為“回文〞，例如，‘a(chǎn)bba’和‘a(chǎn)bcba’是回文，‘a(chǎn)bcde’和‘a(chǎn)babab’則不是回文。試寫一個算法判別讀入的一個以‘@’為完畢符的字符序列是否是“回文〞。StatusSymmetryString(char*p){ Queueq; if(!InitQueue(q))return0; Stacks; InitStack(s); ElemTypee1,e2; while(*p){ Push(s,*p); EnQueue(q,*p); p++; } while(!StackEmpty(s)){ Pop(s,e1); DeQueue(q,e2); if(e1!=e2)returnFALSE; } returnOK;}第四章串一.填空題1.不包含任何字符〔長度為0〕的串稱為空串；由一個或多個空格〔僅由空格符〕組成的串稱為空白串。2.設(shè)S=“A;/document/Mary.doc〞，則strlen(s)=20,“/〞的字符定位的位置為3。3.假設(shè)n為主串長，m為子串長，則串的經(jīng)典模式匹配算法最壞的情況下需要對比字符的總次數(shù)為(n-m+1)*m。二.選擇題1.串是一種特殊的線性表，其特殊性表達(dá)在：〔B〕A可以順序存儲B數(shù)據(jù)元素是一個字符C可以鏈?zhǔn)酱鎯數(shù)據(jù)元素可以是多個字符2.設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作：〔B〕A連接B模式匹配C求子串D求串長3.設(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é)果串是：〔D〕A‘BCDEF’B‘BCDEFG’C‘BCPQRST’D‘BCDEFEF’4.假設(shè)串S=〞software〞，其子串的數(shù)目是〔B〕。A8B37C36D9三.計算題1.設(shè)s=’IAMASTUDENT’,t=’GOOD’,q=’WORKER’,求：1〕Replace(s,’STUDENT’,q)2〕Concat(t,SubString(s,7,8)))1、Replace(s,’STUDENT’,q)＝’IAMAWORKER’2、因為SubString(s,7,8)＝‘STUDENT’Concat(t,SubString(s,7,8))＝’GOODSTUDENT’四.算法設(shè)計1.利用C的庫函數(shù)strlen,strcpy〔或strncpy〕寫一個算法voidStrDelete(char*S,intt,intm)，刪除串S中從位置i開場的連續(xù)的m個字符。假設(shè)i≥strlen(S)，則沒有字符被刪除；假設(shè)i+m≥strlen(S)，則將S中從位置i開場直至末尾的字符均被刪去。提示：strlen是求串長(length)函數(shù)：intstrlen(chars);//求串的長度strcpy是串復(fù)制(copy)函數(shù)：char*strcpy(charto,charfrom);//該函數(shù)將串from復(fù)制到串to中，并且返回一個指向串to的開場處的指針。voidStrDelete(char*S,inti,intm)

{//串刪除

charTemp[Maxsize];//定義一個臨時串

if(i+m<strlen(S))

{

strcpy(Temp,&S[i+m]);//把刪除的字符以后的字符保存到臨時串中

strcpy(&S[i],Temp);//用臨時串中的字符覆蓋位置i之后的字符

}

elseif(i+m>=strlen(S)&&i<strlen(S))

{

strcpy(&S[i],"\0");//把位置i的元素置為'\0'，表示串完畢

}

}第五章數(shù)組和廣義表一.填空1.假設(shè)有二維數(shù)組A6×8，每個元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。A的起始存儲位置〔基地址〕為1000，則數(shù)組A的體積〔存儲量〕為288；末尾元素A57的第一個字節(jié)地址為1282；假設(shè)按行存儲時，元素A14的第一個字節(jié)地址為1072；假設(shè)按列存儲時，元素A47的第一個字節(jié)地址為1276。2.三元素組表中的每個結(jié)點對應(yīng)于稀疏矩陣的一個非零元素，它包含有三個數(shù)據(jù)項，分別表示該元素的行下標(biāo)、列下標(biāo)和元素值。。3.廣義表((a),(((b),c)),(d))的長度是3，深度是4，表頭是(a)，表尾是(((b),c)),(d)。4.廣義表LS=(a，(b，c，d)，e)，用Head和Tail函數(shù)取出LS中原子b的運算是Head(Head(Tail(LS)))。二.選擇題1.假設(shè)有60行70列的二維數(shù)組a[1…60,1…70]以列序為主序順序存儲，其基地址為10000，每個元素占2個存儲單元，那么第32行第58列的元素a[32,58]的存儲地址為(A)。〔無第0行第0列元素〕A16902B16904C14454D答案A,B,C均不對2.設(shè)矩陣A是一個對稱矩陣，為了節(jié)省存儲，將其下三角局部按行序存放在一維數(shù)組B[1,n(n-1)/2]中，下三角局部中任一元素ai,j(i≤j),在一維數(shù)組B中下標(biāo)k的值是：(B)Ai(i-1)/2+j-1Bi(i-1)/2+jCi(i+1)/2+j-1Di(i+1)/2+j3.一個n*n的對稱矩陣，用壓縮存儲方法處理其對稱性質(zhì)后存儲，則其容量為：(C)。An*nBn*n/2C(n+1)*n/2D(n+1)*(n+1)/2三.計算題1.設(shè)有一個二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在644，A[2][2]存放位置在676，每個元素占一個空間，問A[3][3]存放在什么位置寫出計算過程。(676-644)/1=32A[2][2]的地址相對A[0][0]偏移量為32，則A[3][3]相較于A[0][0]的偏移量為32*3/2=48A[3][3]地址為48+644=6922.設(shè)A[9][9]是一個10*10對稱矩陣，采用壓縮存儲方式存儲其下三角局部，每個元素占用兩個存儲單元，其第一個元素A[0][0]的存儲位置在1000，求下面問題的計算過程及結(jié)果：給出A[4][5]的存儲位置。A[4][5]是上三角局部，所以存在A[5][4]假設(shè)以行序為主序，則地址為1000+2〔5〔1+5〕/2+4〕=1036假設(shè)以列序為主序，則地址為1000+2〔4〔10+7〕/2+5〕=1062給出存儲位置為1080的元素下標(biāo)。i(i+1)/2+j或j(10+10-j+1)/2+i=40得i=9，j=4或i=8j=5，A[8][5]或A[9][4]3.一個稀疏矩陣如以以下圖，則對應(yīng)的三元組線性表是什么其對應(yīng)的十字鏈表是什么0020300000-0020300000-1500004.以下各三元組表分別表示一個稀疏矩陣，試寫出它們的稀疏矩陣。0202001200030000004006016000四.算法設(shè)計1.設(shè)計一個算法，計算一個三元組表表示的稀疏矩陣的對角線元素之和。2.假設(shè)在矩陣A中存在一個元素ai,j〔0≤i≤n-1，0≤j≤m-1〕，該元素是第i行元素中最小值且又是第j列元素中最大值，則稱此元素為該矩陣的一個鞍點。假設(shè)以二維數(shù)組存儲矩陣A，試設(shè)計一個求該矩陣所有鞍點的算法，并分析最壞情況下的時間復(fù)雜度voidSaddle(intA[m][n])//A是m*n的矩陣,本算法求矩陣A中的馬鞍點.{intmax[n]={0},//max數(shù)組存放各列最大值元素的行號,初始化為行號0;min[m]={0},//min數(shù)組存放各行最小值元素的列號,初始化為列號0;i,j;for(i=0;i<m;i++)//選各行最小值元素和各列最大值元素.{for(j=0;j<n;j++){if(A[max[j]][j]<A[i][j])max[j]=i;//修改第j列最大元素的行號if(A[i][min[i]]>A[i][j])min[i]=j;//修改第i行最小元素的列號.}for(i=0;i<m;i++){j=min[i];//第i行最小元素的列號if(i==max[j])printf(“A[%d][%d]是馬鞍點，元素值是%d〞,i,j,A[i][j]);}}}//Saddle分析算法，外層for循環(huán)共執(zhí)行m次，內(nèi)層第一個for循環(huán)執(zhí)行n次，第二個for循環(huán)最壞情況下執(zhí)行m次，所以，最壞情況下的時間復(fù)雜度為Ｏ(mn+mm)。第六章樹和二叉樹一.填空題1.樹是n〔n≥0〕結(jié)點的有限集合。在一棵空樹中有0個元素；在一棵非空樹中，有且僅有一個個根結(jié)點，其余的結(jié)點分成m〔m＞0〕個互不相交的集合，每個集合都是根結(jié)點的子樹。2.一棵二叉樹的第i〔i≥1〕層最多有2i-1個結(jié)點；一棵有n〔n>0〕個結(jié)點的滿二叉樹共有(n+1)/2個葉子結(jié)點和(n-1)/2個非終端結(jié)點。3.設(shè)深度為k的二叉樹上只有度為0和度為2的結(jié)點，該二叉樹的結(jié)點數(shù)可能到達(dá)的最大值是2k-1，最小值是2k-1。4.深度為k的二叉樹中，所含葉子的個數(shù)最多為2k-1。5.在順序存儲的二叉樹中編號為i和j的兩個結(jié)點處在同一層的條件為：二.選擇題1.前序遍歷和中序遍歷結(jié)果一樣的二叉樹是〔D〕。A根結(jié)點無左孩子的二叉樹B根結(jié)點無右孩子的二叉樹C所有結(jié)點只有左子樹的二叉樹D所有結(jié)點只有右子樹的二叉樹2.序存儲的方法將完全二叉樹中的所有結(jié)點逐層存放在數(shù)組A[1]~A[n]中，結(jié)點A[i]假設(shè)有左子樹，則左子樹的根結(jié)點是〔D〕。AA[2i-1]BA[2i+1]CA[i/2]DA[2i]3.完全二叉樹中的任一結(jié)點，假設(shè)其右分支下的子孫的最大層次為h，則其左分支下的子孫的最大層次為〔C〕。AhBh+1Ch或h+1D任意4.在線索二叉樹中，一個結(jié)點是葉子結(jié)點的充要條件為〔C〕。A左線索標(biāo)志為0，右線索標(biāo)志為1B左線索標(biāo)志為1，右線索標(biāo)志為0C左.右線索標(biāo)志均為0D左.右線索標(biāo)志均為15.由權(quán)值為{3,8,6,2,5}的葉子結(jié)點生成一棵哈夫曼樹，其帶權(quán)路徑長度為〔C〕。A24B48C53D72三.簡答題1.二叉樹的中序和后序序列分別為CBEDAFIGH和CEDBIFHGA，請構(gòu)造出此二叉樹，并寫出此樹的后序遍歷序列。2.將以以以下圖所示的樹轉(zhuǎn)換為二叉樹，3.圖5-17所示的二叉樹轉(zhuǎn)換為樹或森林4.某字符串S中共有8種字符[A,B,C,D,E,F,G,H]，分別出現(xiàn)2次.1次.4次.5次.7次.3次.4次和9次。1〕試構(gòu)造出哈夫曼編碼樹，并對每個字符進(jìn)展編碼EH2〕問該字符串的編碼至少有多少位。EHCGDFBAA:00000B:00001C:100D:001E:11F:0001G:101H:01CGDFBA其帶權(quán)路徑長度=2×5+1×5+3×4+5×3+9×2+4×3+4×3+7×2=98，所以，該字符串的編碼長度至少為98位。四.算法設(shè)計1.設(shè)計算法求二叉樹的結(jié)點個數(shù)2.以二叉鏈表為存儲構(gòu)造，編寫算法求二叉樹中結(jié)點x的雙親3.編寫算法交換二叉樹中所有結(jié)點的左右子樹。第七章圖一.填空題1.設(shè)無向圖G中頂點數(shù)為n，則圖G至少有0條邊，至多有n(n-1)/2條邊；假設(shè)G為有向圖，則至少有0條邊，至多有n(n-1)條邊。2.任何連通圖的連通分量只有一個，即是它自身3.假設(shè)一個有向圖由鄰接矩陣表示，則計算第j個頂點入度的方法是求矩陣第j列元素之和4.圖的深度優(yōu)先遍歷類似于樹的先根遍歷，廣度優(yōu)先遍歷類似于樹的層序遍歷。5.對于含有n個頂點e條邊的連通圖，利用Prim算法求最小生成樹的時間復(fù)雜度為Ｏ(n2)，利用Kruskal算法求最小生成樹的時間復(fù)雜度為Ｏ(elog2e)。二.選擇題1.在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的〔C〕倍。A1/2B1C2D42.n個頂點的強連通圖至少有〔A〕條邊。AnBn+1Cn-1Dn×(n-1)3.含n個頂點的連通圖中的任意一條簡單路徑，其長度不可能超過〔C〕。A1Bn/2Cn-1Dn4.對于一個具有n個頂點的無向圖用鄰接矩陣存儲，則該矩陣的大小是〔D〕。AnB(n-1)2Cn-1Dn25.設(shè)無向圖G=(V,E)和G'=(V',E')，如果G'是G的生成樹，則下面的說法中錯誤的選項是〔B〕。AG'為G的子圖BG'為G的連通分量CG'為G的極小連通子圖且V=V'DG'是G的一個無環(huán)子圖6.判定一個有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以用〔D〕。A求關(guān)鍵路徑的方法B求最短路徑的方法C廣度優(yōu)先遍歷算法D深度優(yōu)先遍歷算法7.下面關(guān)于工程方案的AOE網(wǎng)的表達(dá)中，不正確的選項是〔B〕A關(guān)鍵活動不按期完成就會影響整個工程的完成時間B任何一個關(guān)鍵活動提前完成，那么整個工程將會提前完成C所有的關(guān)鍵活動都提前完成，那么整個工程將會提前完成D某些關(guān)鍵活動假設(shè)提前完成，那么整個工程將會提前完三.計算題1.一個連通圖如以以下圖，試給出圖的鄰接矩陣和鄰接表存儲示意圖，假設(shè)從頂點v1出發(fā)對該圖進(jìn)展遍歷，分別給出一個按深度優(yōu)先遍歷和廣度優(yōu)先遍歷的頂點序列。鄰接矩陣表示如下：

深度優(yōu)先遍歷序列為：v1v2v3v5v4v6

廣度優(yōu)先遍歷序列為：v1v2v4v6v3v5

鄰接表表示如右：2.無向圖G的鄰接表如以以以下圖所示，分別寫出從頂點1出發(fā)的深度遍歷和廣度遍歷序列，并畫出相應(yīng)的生成樹。深度優(yōu)先遍歷序列為：1，2，3，4，5，6

對應(yīng)的生成樹為：

廣度優(yōu)先遍歷序列為：1，2，4，3，5，6

對應(yīng)的生成樹為：3.以以以下圖所示是一個無向帶權(quán)圖，請分別按Prim算法和Kruskal算法求最小生成樹。4.如右圖所示的有向網(wǎng)圖，利用Dijkstra算法求從頂點v1到其他各頂點的最短路徑。從源點v1到其他各頂點的最短路徑如下表所示。源點終點最短路徑最短路徑長度v1v3v1v315

v1v5v1v515

v1v2v1v3v225

v1v6v1v3v2v640

v1v4v1v3v2v4455.一個AOV網(wǎng)如以以以下圖所示，寫出所有拓?fù)湫蛄?。拓?fù)湫蛄袨椋簐0v1v5v2v3v6v4、v0v1v5v2v6v3v4、v0v1v5v6v2v3v4。四.算法設(shè)計1.設(shè)計算法，將一個無向圖的鄰接表轉(zhuǎn)換成鄰接矩陣。2.設(shè)計算法，計算圖中出度為零的頂點個數(shù)。3.一個有向圖的鄰接表，編寫算法建設(shè)其逆鄰接表第九章查找一.填空題1.順序查找技術(shù)適合于存儲構(gòu)造為順序和鏈?zhǔn)酱鎯Φ木€性表，而折半查找技術(shù)適用于存儲構(gòu)造為順序存儲的線性表，并且表中的元素必須是按關(guān)鍵碼有序。2.折半查找有序表〔4，6，12，20，28，38，50，70，88，100〕，假設(shè)查找表中元素20，它將依次與表中元素28，6，12，20對比大小。3.在各種查找方法中，平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法是散列〔哈?！巢檎?。4.為了能有效地應(yīng)用哈希查找技術(shù)，必須解決的兩個問題是構(gòu)造散列函數(shù)和解決沖突。5.有一個表長為m的散列表，初始狀態(tài)為空，現(xiàn)將n〔n<m〕個不同的關(guān)鍵碼插入到散列表中，解決沖突的方法是用線性探測法。如果這n個關(guān)鍵碼的散列地址都一樣，則探測的總次數(shù)是n(n-1)/2=〔1＋2＋…＋n-1〕。二.選擇題1.靜態(tài)查找與動態(tài)查找的基本區(qū)別在于〔B〕。A它們的邏輯構(gòu)造不一樣B施加在其上的操作不同C所包含的數(shù)據(jù)元素的類型不一樣D存儲實現(xiàn)不一樣2.用n個鍵值構(gòu)造一棵二叉排序樹，其最低高度為〔D〕。An/2BnClog2nDlog2n+13.散列技術(shù)中的沖突指的是〔D〕。A兩個元素具有一樣的序號B兩個元素的鍵值不同，而其他屬性一樣C數(shù)據(jù)元素過多D不同鍵值的元素對應(yīng)于一樣的存儲地址4.鏈表適用于A查找A順序B二分法C順序，也能二分法D隨機三.簡答題1.分別畫出在線性表〔a，b，c，d，e，f，g〕中進(jìn)展折半查找關(guān)鍵碼e和g的過程。見下頁2.畫出對長度為10的有序表進(jìn)展折半查找的判定樹，并求其等概率時查找成功的平均查找長度。第1題答案3.設(shè)哈?！睭ash〕表的地址范圍為0～17，哈希函數(shù)為：H〔K〕＝KMOD16。K為關(guān)鍵字，用線性探測法再散列法處理沖突，輸入關(guān)鍵字序列：〔10，24，32，17，31，30，46，47，40，63，49〕構(gòu)造出Hash表，試答復(fù)以下問題：(1)畫出哈希表的示意圖；(2)假設(shè)分別查找關(guān)鍵字63和60，分別需要依次與哪些關(guān)鍵字進(jìn)展對比(3)假定每個關(guān)鍵字的查找概率相等，求查找成功時的平均查找長度。解：〔1〕畫表如下：012345678910111213141516173217634924401030314647〔2〕查找63,首先要與H(63)=63%16=15號單元內(nèi)容對比，即63vs31,no;然后順移，與46,47,32,17,63相比，一共對比了6次！〔3〕查找60,首先要與H(60)=60%16=12號單元內(nèi)容對比，但因為12號單元為空〔應(yīng)當(dāng)有空標(biāo)記〕，所以應(yīng)當(dāng)只對比這一次即可?！?〕對于黑色數(shù)據(jù)元素，各對比1次；共6次；對紅色元素則各不一樣，要統(tǒng)計移位的位數(shù)?！?3〞需要6次，“49〞需要3次，“40〞需要2次，“46〞需要3次，“47〞需要3次，所以ASL=1/11〔6＋2＋3×3〕＝17/11=1.5454545454≈1.55四.算法設(shè)計1.編寫算法求給定結(jié)點在二叉排序樹中所在的層數(shù)2.一個判別給定二叉樹是否為二叉排序樹的算法，設(shè)此二叉樹以二叉鏈表作存儲構(gòu)造。且樹中結(jié)點的關(guān)鍵字均不同。解：注意仔細(xì)研究二叉排序樹的定義。易犯的典型錯誤是按下述思路進(jìn)展判別：“假設(shè)一棵非空的二叉樹其左、右子樹均為二叉排序樹，且左子樹的根的值小于根結(jié)點的值，又根結(jié)點的值不大于右子樹的根的值，則是二叉排序樹〞〔劉注：即不能只判斷左右孩子的情況，還要判斷左右孩子與雙親甚至根結(jié)點的比值也要遵循〔左小右大〕原則〕。假設(shè)要采用遞歸算法，建議您采用如下的函數(shù)首部：boolBisortTree(BiTreeT,BiTree&PRE)，其中PRE為指向當(dāng)前訪問結(jié)點的前驅(qū)的指針。〔或者直接存儲前驅(qū)的數(shù)值，隨時與當(dāng)前根結(jié)點對比〕一個漂亮的算法設(shè)計如下：intlast=0,flag=1;//last是全局變量，用來記錄前驅(qū)結(jié)點值，只要每個結(jié)點都比前驅(qū)大就行。intIs_BSTree(BitreeT)//判斷二叉樹T是否二叉排序樹，是則返回1，否則返回0{if(T->lchild&&flag)Is_BSTree(T->lchild);if(T->data<last)flag=0;//與其中序前驅(qū)相對比,flag=0表示當(dāng)前結(jié)點比直接前驅(qū)小，則立即返回last=T->data;if(T->rchild&&flag)Is_BSTree(T->rchild);returnflag;}//Is_BSTree第十章排序一.填空題1.排序的方法有很多種，插入排序法從未排序序列中依次取出元素，與已排序序列中的元素作對比，將其放入已排序序列的正確位置上。選擇排序法從未排序序列中挑選元素，并將其依次放入已排序序列的一端。交換排序是對序列中元素進(jìn)展一系列對比，當(dāng)被對比的兩元素為逆序時，進(jìn)展交換；冒泡排序和快速排序是基于這類方法的兩種排序方法，而快速排序是比冒泡排序效率更高的方法；堆排序法是基于選擇排序的一種方法，是完全二叉樹構(gòu)造的一個重要應(yīng)用。2.一組記錄〔54,38,96,23,15,72,60,45,83〕進(jìn)展直接插入排序，當(dāng)把第7個記錄60插入到有序表時，為尋找插入位置需對比3次。3.對n個待排序記錄序列進(jìn)展快速排序，所需要的最好時間是O(nlog2n)，最壞時間是O(n2)二.選擇題1.以下序列中，〔A〕是執(zhí)行第一趟快速排序的結(jié)果。A[da，ax，eb，de，bb]ff[ha，gc]B[cd，eb，ax，da]ff[ha，gc，bb]C