3.對(duì)于圖7-25(a)和(b)，按下列條件試分別寫出從頂點(diǎn)v0出發(fā)按深度優(yōu)先搜索遍歷得
到的頂點(diǎn)序列和按廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列。
假定它們均采用鄰接矩陣表示；假定它們均采用鄰接表表示，并且假定每個(gè)頂點(diǎn)鄰接表中的結(jié)點(diǎn)是按頂點(diǎn)序號(hào)從大到小的次序
鏈接的。
解：采用鄰接矩陣表示得到的頂點(diǎn)序列如下表所示：采用鄰接表表示得到的頂點(diǎn)序列如下表所示：畫出最小生成樹并求出它的權(quán)；
解：從頂點(diǎn)v0出發(fā)，按照普里姆法并入最小生成樹中各邊的次序?qū)懗龈鳁l邊；
解：按照克魯斯卡爾算法并入最小生成樹中各邊的次序?qū)懗龈鳁l邊。
解：
圖 深度優(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.對(duì)本章第3節(jié)中的dfsl算法做適當(dāng)?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.假定采用鄰接矩陣表示，編寫出進(jìn)行深度優(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.對(duì)于圖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.對(duì)于圖7-27(圖略)，試給出一種拓樸序列，若在它的鄰接表存儲(chǔ)結(jié)構(gòu)中，每個(gè)頂點(diǎn)鄰接表中的
邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從大到小鏈接的，則按此給出唯一一種拓樸序列。
解：
唯一一種拓樸序列：1,4,0,2,3,5,7,6,8,9
類別：數(shù)據(jù)結(jié)構(gòu) .
. 第八章查找習(xí) 題 八
一、單選題
1.以順序查找方法從長(zhǎng)度為n的線性表中查找一個(gè)元素時(shí)，平均查找長(zhǎng)度為(n+1)/2,時(shí)間復(fù)
雜度為O(n) 。
2.以二分查找方法從長(zhǎng)度為n的線性表中查找一個(gè)元素時(shí)，平均查找長(zhǎng)度小于等于
┍log2(n+1)┑ ，時(shí)間復(fù)雜度為O(log2n)。
3.以二分查找方法從長(zhǎng)度為12的有序表中查找一個(gè)元素時(shí)，平均查找長(zhǎng)度為37/12。
4.以二分查找方法查找一個(gè)線性表時(shí)，此線性表必須是順序存儲(chǔ)的有序表。
5.從有序表(12,18,30,43,56,78,82,95)中依次二分查找43和56元素時(shí)，其查找長(zhǎng)度
分別為 1 和 3 。
6.對(duì)于二分查找所對(duì)應(yīng)的判定樹，它即是一棵二叉搜索樹，又是一棵理想平衡樹 。
7.假守對(duì)長(zhǎng)度n=50的有序表進(jìn)行二分查找，則對(duì)應(yīng)的判斷樹高度為6 ，判定樹前5層的結(jié)點(diǎn)數(shù)
為 31 ，最后一層的結(jié)點(diǎn)數(shù)為 19 。
8.在索引表中，每個(gè)索引向至少包含有 索引值 域和 子表開始 域這兩項(xiàng)。
9.假定一個(gè)線性表為(12,23,74,55,63,40,82,36),若按key%3條件進(jìn)行劃分，使得同一
余數(shù)的元素成為一個(gè)子表，則得到的三個(gè)子表分別為(12,63,36)、(55,40,82)和(23,74)。
10.假定一個(gè)線性表為("abcd","baabd","beef","cfg","ahij","bkwte","ccdt","aayb"),
若按照字符串的第一個(gè)字母進(jìn)行劃分，使得同一個(gè)字母被劃分在一個(gè)子表中，則得到的a,b,c
三個(gè)子表的長(zhǎng)度分別為 3 、 3 和 2 。
11.在索引表中，若一個(gè)索引項(xiàng)對(duì)應(yīng)主表中的一條記錄，則稱此索引為 稠密 索引，若對(duì)應(yīng)主
表中若干條記錄，則稱此索引為 稀疏 索引。
12.在稀疏索引表上進(jìn)行二分查找時(shí)，若當(dāng)前查找區(qū)間為空，則不是返回-1表示查找失敗，而
是返回該區(qū)間的 下限值(即low值) 。
13.假定長(zhǎng)度n=100的線性表進(jìn)行索引查找，并假定每個(gè)子表的長(zhǎng)度為n1/2，則進(jìn)行索引查找的
平均查找長(zhǎng)度為 11 ，時(shí)間復(fù)雜度為 O(n1/2)。
14.若對(duì)長(zhǎng)度n=1000的線性表進(jìn)行二級(jí)索引存儲(chǔ)，每級(jí)索引表中的索引項(xiàng)是下一級(jí)20個(gè)記錄的
索引,則一級(jí)索引表的長(zhǎng)度為 500 ,二級(jí)索引表的長(zhǎng)度為 25 .
15.在線性表的 散列 存儲(chǔ)中,無常找到一個(gè)元素的前驅(qū)或后繼元素.
16.在線性表的 鏈接 存儲(chǔ)中,對(duì)每一個(gè)元素只能采用順序查找.
17.假定對(duì)線性表(38,25,74,52,48)進(jìn)行散列存儲(chǔ),采用H(K)=K%7作為散列函數(shù),若分別采用線
性探查法和鏈接法處理沖突,則對(duì)各自散列表進(jìn)行查找的平均查找長(zhǎng)度分別為 2 和 4/3 .
18.假定要對(duì)長(zhǎng)度n=100的線性表進(jìn)行散列存儲(chǔ),并采用鏈接法處理沖突,則對(duì)于長(zhǎng)度m=20的散列
表,每個(gè)散列地址的單鏈表的長(zhǎng)度分別為 5 .
19.在線性表的散列存儲(chǔ)中,裝填因子α又稱為裝填系數(shù),若用m表示散列表的長(zhǎng)度,n表示待散列存
儲(chǔ)的元素的個(gè)數(shù),則α等于 n/m 。
20.在線性表的散列存儲(chǔ)中,處理沖突有 開放定址法 和 鏈接法 兩種方法。
21.對(duì)于線性表(18,25,63,50,42,32,90)進(jìn)行散列存儲(chǔ)時(shí),若選用H(K)=K%9作為散列函數(shù),則散
列地址為0的元素有 3 個(gè),散列地址為5的元素有 2 個(gè)。
22.對(duì)于一個(gè)含有N個(gè)關(guān)鍵字的m階B_樹,其最小高度為Гlogm(N+1)┐,最大高度為1+︱log︱m/2︱
(N+1/2)︱。
23.已知一棵3階B_樹中含有50個(gè)關(guān)鍵字，則該樹的最小高度為 4 ，最大高度為 5 。
24.在一棵9階的B_樹上中，每個(gè)非樹根結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)目最少為 4 個(gè)，最多為 8 個(gè)。
25.在一棵m階B_樹上，每個(gè)非樹根結(jié)點(diǎn)的關(guān)健字?jǐn)?shù)目最小為┌m/2┐-1 個(gè)，最多為 m-1 個(gè)，其子樹
目最小為┌m/2┐，最多為 m 。
26.在一棵B_階樹中，所有葉子結(jié)點(diǎn)都處在 同一層 上，所有葉子結(jié)點(diǎn)中空指針等于所有 關(guān)鍵字 總數(shù)
加1。
27.在對(duì)m階B_樹插入元素的過程中，每向一個(gè)結(jié)點(diǎn)插入一個(gè)索引項(xiàng)(葉子結(jié)點(diǎn)中的索引項(xiàng)為關(guān)鍵字
和空指針)后，若該結(jié)點(diǎn)的索引項(xiàng)數(shù)等于 m 個(gè)，則必須把它分裂為 兩 個(gè)結(jié)點(diǎn)。
28.在從m階的B_樹刪除元素的過程中，當(dāng)一個(gè)結(jié)點(diǎn)被刪除掉一個(gè)索引項(xiàng)后，所含索引項(xiàng)等于┌m/2┐
-2個(gè)，并且它的左右兄弟結(jié)點(diǎn)中的索引項(xiàng)數(shù)均等于┌m/2┐-1個(gè)，則必須進(jìn)行結(jié)點(diǎn)合并。
29.向一棵B_樹插入元素的過程中，若最終引起樹根結(jié)點(diǎn)的分裂，則新樹比原樹的高度 增加1 。
30.從一棵B_樹刪除元素的過程中，若最終引起樹根結(jié)點(diǎn)的合并，則新樹比原樹的高度 減少1 。
二、普通題
2.編寫一個(gè)非遞歸算法，在稀疏有序索引表中二分查找出給定值K所對(duì)應(yīng)的索引項(xiàng)，即索引值剛好大于
等于K的索引項(xiàng)，返回該索引項(xiàng)的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.假定有一個(gè)100×100的稀疏矩陣，其中1%的元素為非零元素，現(xiàn)要求對(duì)其非零元素進(jìn)行散列存儲(chǔ)
，使之能夠按照元素的行、列值存取矩陣元素(即元素的行、列值聯(lián)合為元素的關(guān)鍵字)，試采用除
留余數(shù)法構(gòu)造散列函數(shù)和線性探查法處理沖突，分別寫出散列表和查找散列表的算法。
分析：由題意可知，整個(gè)稀疏矩陣中非零元素的個(gè)數(shù)為100。為了散列存儲(chǔ)這100個(gè)非零元素，需要
使用一個(gè)作為散列的一維數(shù)組，該數(shù)組中元素的類型應(yīng)為：
struct ElemType{
int row;//存儲(chǔ)非零元素的行下標(biāo)
int col;//存儲(chǔ)非零元素的列下標(biāo)
float val;//存儲(chǔ)非零元素值
};
假定用HT[m]表示這個(gè)散列，其中m為散列表的長(zhǎng)度，若取裝填因子為0.8左右，則令m為127為宜
(因?yàn)?27為質(zhì)數(shù))。
按題目要求，需根據(jù)稀疏矩陣元素的行下標(biāo)和列下標(biāo)存取散列表中的元素，所以每個(gè)元素的行下
標(biāo)和列下標(biāo)同時(shí)為元素的關(guān)鍵字。假定用x表示一個(gè)非零元素，按除留余數(shù)法構(gòu)造散列函數(shù)，并考慮
盡量讓得到的散列地址分布均勻，所以采用的散列函數(shù)為：
H(x)=(13*x.row+17*x.col)%m
解：
根據(jù)以上分析，建立散列表的算法如下：
int Create(ElemType HT[],int m)
//根據(jù)稀疏矩陣中100個(gè)非零元素建立長(zhǎng)度為m的散列表
{
int i,d,temp;
ElemType x;
for(i=0;i<m;i++)
{//散列表初始化，使關(guān)鍵字域被置為-1，元素值域置為0
HT[i].row=-1;
HT[i].col=-1;
HT[i].val=0;
}
for(i=1;i<=100;i++)
{//每循環(huán)一次從鍵盤上輸入一個(gè)非零元素并插入到散列表中
cout<<i<<":";
cin>>x.row>>x.col>>x.val;//輸入非零元素
d=(13*x.row+17*x.col)%m;//計(jì)算初始散列地址
temp=d;
while(HT[d].val!=0){//線性探查存儲(chǔ)位置，此循環(huán)條件也可用HT[d].row!=-1或
//HT[d].col!=-1來代替
d=(d+1)%m;
if(d==temp)//無插入位置返回0
return 0;
}
HT[d]=x;//非零元素存入下標(biāo)d位置
}
return 1;//全部元素插入成功后返回1
}
在散列表上進(jìn)行查找的算法如下：
int Search(ElemType HT[],int m,int row,int col)
{
//采用與插入時(shí)使用的同一散列函數(shù)計(jì)算散列地址
int d=(13*row+17*col)%m;
//采用線性探查法查找行、列下標(biāo)分別為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;//查找成功后返回元素的下標(biāo)
else
d=(d+1)&m;
if(d==temp) return -1;
}
//查找失敗返回 -1
return -1;
}
