南京曉莊學院數據結構試題庫答案

...wd......wd......wd...數據構造與算法習題冊〔課后局部參考答案〕《數據構造與算法》課程組目錄課后習題局部第一章緒論1第二章線性表3第三章棧和隊列5第四章串8第五章數組和廣義表10第六章樹和二叉樹13第七章圖16第九章查找20第十章排序23第一章緒論一.填空題1.從邏輯關系上講，數據構造的類型主要分為集合、線性構造、樹構造和圖構造。2.數據的存儲構造主要有順序存儲和鏈式存儲兩種基本方法，不管哪種存儲構造，都要存儲兩方面的內容：數據元素和數據元素之間的關系。3.算法具有五個特性，分別是有窮性、確定性、可行性、輸入、輸出。4.算法設計要求中的強健性指的是算法在發(fā)生非法操作時可以作出處理的特性。二.選擇題1.順序存儲構造中數據元素之間的邏輯關系是由C表示的，鏈接存儲構造中的數據元素之間的邏輯關系是由D表示的。A線性構造B非線性構造C存儲位置D指針2.假設有如下遺產繼承規(guī)則：丈夫和妻子可以相互繼承遺產；子女可以繼承父親或母親的遺產；子女間不能相互繼承。則表示該遺產繼承關系的最適宜的數據構造應該是B。A樹B圖C線性表D集合3.算法指的是A。A對特定問題求解步驟的一種描述，是指令的有限序列。B計算機程序C解決問題的計算方法D數據處理三.簡答題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.設有數據構造〔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)}。試畫出其邏輯構造圖并指出屬于何種構造。其邏輯構造圖如下所示，它是一種圖構造。3.求多項式A(x)的算法可根據以下兩個公式之一來設計：⑴A(x)=anxn+an-1xn-1+…+a1x+a0⑵A(x)=(…(anx+an-1)x+…+a1)x)+a0根據算法的時間復雜度分析對比這兩種算法的優(yōu)劣。第二種算法的時間性能要好些。第一種算法需執(zhí)行大量的乘法運算，而第二種算法進展了優(yōu)化，減少了不必要的乘法運算。第二章線性表一.填空題1.在順序表中，等概率情況下，插入和刪除一個元素平均需移動表長的一半個元素，具體移動元素的個數與表長和插入的位置有關。2.在一個長度為n的順序表的第i〔1≤i≤n+1〕個元素之前插入一個元素，需向后移動n-i+1個元素，刪除第i〔1≤i≤n〕個元素時，需向前移動n-i個元素。3.在單循環(huán)鏈表中，由rear指向表尾，在表尾插入一個結點s的操作順序是s->next=rear->next;rear->next=s;rear=s;；刪除開場結點的操作順序為q=rear->next->next;rear->next->next=q->next;deleteq;。二.選擇題1.數據在計算機存儲器內表示時物理地址與邏輯地址一樣并且是連續(xù)的，稱之為：CA存儲構造B邏輯構造C順序存儲構造D鏈式存儲構造2.在n個結點的順序表中，算法的時間復雜度是O〔1〕的操作是：AA訪問第i個結點〔1≤i≤n〕和求第i個結點的直接前驅〔2≤i≤n〕B在第i個結點后插入一個新結點〔1≤i≤n〕C刪除第i個結點〔1≤i≤n〕D將n個結點從小到大排序3.線性表L在B情況下適用于使用鏈式構造實現。A需經常修改L中的結點值B需不斷對L進展刪除插入CL中含有大量的結點DL中結點構造復雜4.單鏈表的存儲密度CA大于1B等于1C小于1D不能確定三.判斷題1.線性表的邏輯順序和存儲順序總是一致的。F2.線性表的順序存儲構造優(yōu)于鏈接存儲構造。F3.設p，q是指針，假設p=q，則*p=*q。F4.線性構造的基本特征是：每個元素有且僅有一個直接前驅和一個直接后繼。F四.簡答題1.分析以下情況下，采用何種存儲構造更好些。(1)假設線性表的總長度基本穩(wěn)定，且很少進展插入和刪除操作，但要求以最快的速度存取線性表中的元素。(2)如果n個線性表同時并存，并且在處理過程中各表的長度會動態(tài)發(fā)生變化。(3)描述一個城市的設計和規(guī)劃。⑴應選用順序存儲構造。很少進展插入和刪除操作，所以空間變化不大，且需要快速存取，所以應選用順序存儲構造。

⑵應選用鏈式存儲構造。鏈表容易實現表容量的擴大，適合表的長度動態(tài)發(fā)生變化。

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

/*設elenum為表的最大下標*/

{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.設有一個空棧，棧頂指針為1000H，現有輸入序列為1.2.3.4.5，經過push，push，pop，push，pop，push，push后，輸出序列是23，棧頂指針為1003H。2.棧通常采用的兩種存儲構造是順序棧、鏈棧；其判定?？盏臈l件分別是TOP=-1、TOP=NULL，判定棧滿的條件分別是TOP=數組長度、存儲空間滿。3.?？勺鳛閷崿F遞歸函數調用的一種數據構造。4.表達式a*(b+c)-d的后綴表達式是abc+*d-。二.選擇題1.假設一個棧的輸入序列是1，2，3，…，n，輸出序列的第一個元素是n，則第i個輸出元素是D。A不確定Bn-iCn-i-1Dn-i+12.設棧S和隊列Q的初始狀態(tài)為空，元素e1.e2.e3.e4.e5.e6依次通過棧S，一個元素出棧后即進入隊列Q，假設6個元素出隊的順序是e2.e4.e3.e6.e5.e1，則棧S的容量至少應該是C。A6B4C3D23.一個棧的入棧序列是1，2，3，4，5，則棧的不可能的輸出序列是C。A54321B45321C43512D12345三.判斷題1.有n個元素依次進棧，則出棧序列有(n-1)/2種。F2.?？梢宰鳛閷崿F過程調用的一種數據構造。T3.在棧滿的情況下不能做進棧操作，否則將產生“上溢〞。T4.在循環(huán)隊列中，front指向隊頭元素的前一個位置，rear指向隊尾元素的位置，則隊滿的條件是front=rear。F四.簡答題1.設有一個棧，元素進棧的次序為A，B，C，D，E，能否得到如下出棧序列，假設能，請寫出操作序列，假設不能，請說明原因。⑴C，E，A，B，D⑵C，B，A，D，E⑴不能，因為在C、E出棧后，A一定在棧中，而且在B的下面，不可能先于B出棧⑵可以，設Ｉ為進棧操作，Ｏ為入棧操作，則其操作序列為IIIOOOIOIO。2.在操作序列push(1).push(2).pop.push(5).push(7).pop.push(6)之后，棧頂元素和棧底元素分別是什么〔push(k)表示k入棧，pop表示棧頂元素出棧?！硹ｍ斣貫?，棧底元素為1。3.在操作序列EnQueue(1).EnQueue(3).DeQueue.EnQueue(5).EnQueue(7).DeQueue.EnQueue(9)之后，隊頭元素和隊尾元素分別是什么〔EnQueue(k)表示整數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); } }//隊列逆置五.算法設計1.試寫一個判別表達式中開、閉括號是否配對出現的算法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.假設稱正讀和反讀都一樣的字符序列為“回文〞，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’則不是回文。試寫一個算法判別讀入的一個以‘@’為完畢符的字符序列是否是“回文〞。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.設S=“A;/document/Mary.doc〞，則strlen(s)=20,“/〞的字符定位的位置為3。3.假設n為主串長，m為子串長，則串的經典模式匹配算法最壞的情況下需要對比字符的總次數為(n-m+1)*m。二.選擇題1.串是一種特殊的線性表，其特殊性表達在：〔B〕A可以順序存儲B數據元素是一個字符C可以鏈式存儲D數據元素可以是多個字符2.設有兩個串p和q，求q在p中首次出現的位置的運算稱作：〔B〕A連接B模式匹配C求子串D求串長3.設串s1=’ABCDEFG’，s2=’PQRST’，函數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))的結果串是：〔D〕A‘BCDEF’B‘BCDEFG’C‘BCPQRST’D‘BCDEFEF’4.假設串S=〞software〞，其子串的數目是〔B〕。A8B37C36D9三.計算題1.設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’四.算法設計1.利用C的庫函數strlen,strcpy〔或strncpy〕寫一個算法voidStrDelete(char*S,intt,intm)，刪除串S中從位置i開場的連續(xù)的m個字符。假設i≥strlen(S)，則沒有字符被刪除；假設i+m≥strlen(S)，則將S中從位置i開場直至末尾的字符均被刪去。提示：strlen是求串長(length)函數：intstrlen(chars);//求串的長度strcpy是串復制(copy)函數：char*strcpy(charto,charfrom);//該函數將串from復制到串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'，表示串完畢

}

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

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

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

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

對應的生成樹為：

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

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

v1v5v1v515

v1v2v1v3v225

v1v6v1v3v2v640

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