3.對于圖7-25(a)和(b)，按下列條件試分別寫出從頂點v0出發(fā)按深度優(yōu)先搜索遍歷得

到的頂點序列和按廣度優(yōu)先搜索遍歷得到的頂點序列。

假定它們均采用鄰接矩陣表示；假定它們均采用鄰接表表示，并且假定每個頂點鄰接表中的結點是按頂點序號從大到小的次序

鏈接的。

解：采用鄰接矩陣表示得到的頂點序列如下表所示：采用鄰接表表示得到的頂點序列如下表所示：畫出最小生成樹并求出它的權；

解：從頂點v0出發(fā)，按照普里姆法并入最小生成樹中各邊的次序寫出各條邊；

解：按照克魯斯卡爾算法并入最小生成樹中各邊的次序寫出各條邊。

解：

圖 深度優(yōu)先序列 廣度優(yōu)先序列 (a) 0,1,2,8,3,4,5,6,7,9 0,1,4,2,7,3,8,6,5,9 (b) 0,1,2,5,8,4,7,3,6 0,1,3,4,2,6,7,5,8

圖 深度優(yōu)先序列 廣度優(yōu)先序列 (a) 0,4,3,8,9,5,6,7,1,2 0,4,1,3,7,2,8,6,9,5 (b) 0,4,7,5,8,3,6,1,2 0,4,3,1,7,5,6,2,8

4.對本章第3節(jié)中的dfsl算法做適當?shù)男薷?，得到輸出圖的深度做出先生成樹中各條邊的算法。

解：

void dfstree(adjmatrix GA,int i,int n)

{

visited[i]=True;

for(int j=0;j<n;j++)

if(i!=j&&GA[i][j]!=MaxValue&&!visited[j])

{

cout<<'('<<i<<','<<j<<')';

cout<<GA[i][j]<<end1;

dfstree(GA,j,n);

}

}

5.假定采用鄰接矩陣表示，編寫出進行深度優(yōu)先遍歷的非遞歸算法。

解：

void dfss(adjmatrix GA,int i,int n)

{

stack s;

Initstack(s);

push(s,i);

while(!StackEmpty(s)){

int k=pos(s);

if(!visited[k]){

cout<<k<<'';

visited[k]=True;

for(int j=0;j<n;j++)

if(k!=j&&GA[k][j]!=MaxValue&&!visited[j])

push(s,j);

}

}

}

6.對于圖7-26：

略

(0,1)6,(1,6)4,(6,2)9,(2,3)5,(3,4)10,(0,5)12

(1,6)4,(2,3)5,(0,1)6,(2,6)9,(3,4)10,(0,5)12

7.對于圖7-27(圖略)，試給出一種拓樸序列，若在它的鄰接表存儲結構中，每個頂點鄰接表中的

邊結點都是按照終點序號從大到小鏈接的，則按此給出唯一一種拓樸序列。

解：

唯一一種拓樸序列：1,4,0,2,3,5,7,6,8,9

類別：數(shù)據(jù)結構 .

. 第八章查找習 題 八

一、單選題

1.以順序查找方法從長度為n的線性表中查找一個元素時，平均查找長度為(n+1)/2,時間復

雜度為O(n) 。

2.以二分查找方法從長度為n的線性表中查找一個元素時，平均查找長度小于等于

┍log2(n+1)┑ ，時間復雜度為O(log2n)。

3.以二分查找方法從長度為12的有序表中查找一個元素時，平均查找長度為37/12。

4.以二分查找方法查找一個線性表時，此線性表必須是順序存儲的有序表。

5.從有序表(12,18,30,43,56,78,82,95)中依次二分查找43和56元素時，其查找長度

分別為 1 和 3 。

6.對于二分查找所對應的判定樹，它即是一棵二叉搜索樹，又是一棵理想平衡樹 。

7.假守對長度n=50的有序表進行二分查找，則對應的判斷樹高度為6 ，判定樹前5層的結點數(shù)

為 31 ，最后一層的結點數(shù)為 19 。

8.在索引表中，每個索引向至少包含有 索引值 域和 子表開始 域這兩項。

9.假定一個線性表為(12,23,74,55,63,40,82,36),若按key%3條件進行劃分，使得同一

余數(shù)的元素成為一個子表，則得到的三個子表分別為(12,63,36)、(55,40,82)和(23,74)。

10.假定一個線性表為("abcd","baabd","beef","cfg","ahij","bkwte","ccdt","aayb"),

若按照字符串的第一個字母進行劃分，使得同一個字母被劃分在一個子表中，則得到的a,b,c

三個子表的長度分別為 3 、 3 和 2 。

11.在索引表中，若一個索引項對應主表中的一條記錄，則稱此索引為 稠密 索引，若對應主

表中若干條記錄，則稱此索引為 稀疏 索引。

12.在稀疏索引表上進行二分查找時，若當前查找區(qū)間為空，則不是返回-1表示查找失敗，而

是返回該區(qū)間的 下限值(即low值) 。

13.假定長度n=100的線性表進行索引查找，并假定每個子表的長度為n1/2，則進行索引查找的

平均查找長度為 11 ，時間復雜度為 O(n1/2)。

14.若對長度n=1000的線性表進行二級索引存儲，每級索引表中的索引項是下一級20個記錄的

索引,則一級索引表的長度為 500 ,二級索引表的長度為 25 .

15.在線性表的 散列 存儲中,無常找到一個元素的前驅或后繼元素.

16.在線性表的 鏈接 存儲中,對每一個元素只能采用順序查找.

17.假定對線性表(38,25,74,52,48)進行散列存儲,采用H(K)=K%7作為散列函數(shù),若分別采用線

性探查法和鏈接法處理沖突,則對各自散列表進行查找的平均查找長度分別為 2 和 4/3 .

18.假定要對長度n=100的線性表進行散列存儲,并采用鏈接法處理沖突,則對于長度m=20的散列

表,每個散列地址的單鏈表的長度分別為 5 .

19.在線性表的散列存儲中,裝填因子α又稱為裝填系數(shù),若用m表示散列表的長度,n表示待散列存

儲的元素的個數(shù),則α等于 n/m 。

20.在線性表的散列存儲中,處理沖突有 開放定址法 和 鏈接法 兩種方法。

21.對于線性表(18,25,63,50,42,32,90)進行散列存儲時,若選用H(K)=K%9作為散列函數(shù),則散

列地址為0的元素有 3 個,散列地址為5的元素有 2 個。

22.對于一個含有N個關鍵字的m階B_樹,其最小高度為Гlogm(N+1)┐,最大高度為1+︱log︱m/2︱

(N+1/2)︱。

23.已知一棵3階B_樹中含有50個關鍵字，則該樹的最小高度為 4 ，最大高度為 5 。

24.在一棵9階的B_樹上中，每個非樹根結點的關鍵字數(shù)目最少為 4 個，最多為 8 個。

25.在一棵m階B_樹上，每個非樹根結點的關健字數(shù)目最小為┌m/2┐-1 個，最多為 m-1 個，其子樹

目最小為┌m/2┐，最多為 m 。

26.在一棵B_階樹中，所有葉子結點都處在 同一層 上，所有葉子結點中空指針等于所有 關鍵字 總數(shù)

加1。

27.在對m階B_樹插入元素的過程中，每向一個結點插入一個索引項(葉子結點中的索引項為關鍵字

和空指針)后，若該結點的索引項數(shù)等于 m 個，則必須把它分裂為 兩 個結點。

28.在從m階的B_樹刪除元素的過程中，當一個結點被刪除掉一個索引項后，所含索引項等于┌m/2┐

-2個，并且它的左右兄弟結點中的索引項數(shù)均等于┌m/2┐-1個，則必須進行結點合并。

29.向一棵B_樹插入元素的過程中，若最終引起樹根結點的分裂，則新樹比原樹的高度 增加1 。

30.從一棵B_樹刪除元素的過程中，若最終引起樹根結點的合并，則新樹比原樹的高度 減少1 。

二、普通題

2.編寫一個非遞歸算法，在稀疏有序索引表中二分查找出給定值K所對應的索引項，即索引值剛好大于

等于K的索引項，返回該索引項的star域的值，若查找失敗則返回-1。

解：

int Binsch(indexlist B,int m,IndexkeyType k)

{

int low=0,hight=m=-1;

while(low<=hight){

int mid=(low+hight)/2;

if(k==B[mid].index)

return B[mid].start);

else if(k<B[mid].index)

hight=mid-1;

else

low=mid+1;

}

if(low<m)return B[low].start;

else return -1;

}

5.假定有一個100×100的稀疏矩陣，其中1%的元素為非零元素，現(xiàn)要求對其非零元素進行散列存儲

，使之能夠按照元素的行、列值存取矩陣元素(即元素的行、列值聯(lián)合為元素的關鍵字)，試采用除

留余數(shù)法構造散列函數(shù)和線性探查法處理沖突，分別寫出散列表和查找散列表的算法。

分析：由題意可知，整個稀疏矩陣中非零元素的個數(shù)為100。為了散列存儲這100個非零元素，需要

使用一個作為散列的一維數(shù)組，該數(shù)組中元素的類型應為：

struct ElemType{

int row;//存儲非零元素的行下標

int col;//存儲非零元素的列下標

float val;//存儲非零元素值

};

假定用HT[m]表示這個散列，其中m為散列表的長度，若取裝填因子為0.8左右，則令m為127為宜

(因為127為質數(shù))。

按題目要求，需根據(jù)稀疏矩陣元素的行下標和列下標存取散列表中的元素，所以每個元素的行下

標和列下標同時為元素的關鍵字。假定用x表示一個非零元素，按除留余數(shù)法構造散列函數(shù)，并考慮

盡量讓得到的散列地址分布均勻，所以采用的散列函數(shù)為：

H(x)=(13*x.row+17*x.col)%m

解：

根據(jù)以上分析，建立散列表的算法如下：

int Create(ElemType HT[],int m)

//根據(jù)稀疏矩陣中100個非零元素建立長度為m的散列表

{

int i,d,temp;

ElemType x;

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

{//散列表初始化，使關鍵字域被置為-1，元素值域置為0

HT[i].row=-1;

HT[i].col=-1;

HT[i].val=0;

}

for(i=1;i<=100;i++)

{//每循環(huán)一次從鍵盤上輸入一個非零元素并插入到散列表中

cout<<i<<":";

cin>>x.row>>x.col>>x.val;//輸入非零元素

d=(13*x.row+17*x.col)%m;//計算初始散列地址

temp=d;

while(HT[d].val!=0){//線性探查存儲位置，此循環(huán)條件也可用HT[d].row!=-1或

//HT[d].col!=-1來代替

d=(d+1)%m;

if(d==temp)//無插入位置返回0

return 0;

}

HT[d]=x;//非零元素存入下標d位置

}

return 1;//全部元素插入成功后返回1

}

在散列表上進行查找的算法如下：

int Search(ElemType HT[],int m,int row,int col)

{

//采用與插入時使用的同一散列函數(shù)計算散列地址

int d=(13*row+17*col)%m;

//采用線性探查法查找行、列下標分別為row和col的元素

while(HT[d].val!=0)

{//此循環(huán)條件也可用HT[d].row!=-1或HT[d].col!=-1代替

if(HT[d].row==row&&HT[d].col==col)

return d;//查找成功后返回元素的下標

else

d=(d+1)&m;

if(d==temp) return -1;

}

//查找失敗返回 -1

return -1;

}