3.对于图7-25(a)和(b)，按下列条件试分别写出从顶点v0出发按深度优先搜索遍历得
到的顶点序列和按广度优先搜索遍历得到的顶点序列。
假定它们均采用邻接矩阵表示；假定它们均采用邻接表表示，并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序
链接的。
解：采用邻接矩阵表示得到的顶点序列如下表所示：采用邻接表表示得到的顶点序列如下表所示：画出最小生成树并求出它的权；
解：从顶点v0出发，按照普里姆法并入最小生成树中各边的次序写出各条边；
解：按照克鲁斯卡尔算法并入最小生成树中各边的次序写出各条边。
解：
图 深度优先序列 广度优先序列 (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
图 深度优先序列 广度优先序列 (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节中的dfsl算法做适当的修改，得到输出图的深度做出先生成树中各条边的算法。
解：
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.假定采用邻接矩阵表示，编写出进行深度优先遍历的非递归算法。
解：
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
类别：数据结构 .
. 第八章查找习 题 八
一、单选题
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层的结点数
为 31 ，最后一层的结点数为 19 。
8.在索引表中，每个索引向至少包含有 索引值 域和 子表开始 域这两项。
9.假定一个线性表为(12,23,74,55,63,40,82,36),若按key%3条件进行划分，使得同一
余数的元素成为一个子表，则得到的三个子表分别为(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.在稀疏索引表上进行二分查找时，若当前查找区间为空，则不是返回-1表示查找失败，而
是返回该区间的 下限值(即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作为散列函数,若分别采用线
性探查法和链接法处理冲突,则对各自散列表进行查找的平均查找长度分别为 2 和 4/3 .
18.假定要对长度n=100的线性表进行散列存储,并采用链接法处理冲突,则对于长度m=20的散列
表,每个散列地址的单链表的长度分别为 5 .
19.在线性表的散列存储中,装填因子α又称为装填系数,若用m表示散列表的长度,n表示待散列存
储的元素的个数,则α等于 n/m 。
20.在线性表的散列存储中,处理冲突有 开放定址法 和 链接法 两种方法。
21.对于线性表(18,25,63,50,42,32,90)进行散列存储时,若选用H(K)=K%9作为散列函数,则散
列地址为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_树上中，每个非树根结点的关键字数目最少为 4 个，最多为 8 个。
25.在一棵m阶B_树上，每个非树根结点的关健字数目最小为┌m/2┐-1 个，最多为 m-1 个，其子树
目最小为┌m/2┐，最多为 m 。
26.在一棵B_阶树中，所有叶子结点都处在 同一层 上，所有叶子结点中空指针等于所有 关键字 总数
加1。
27.在对m阶B_树插入元素的过程中，每向一个结点插入一个索引项(叶子结点中的索引项为关键字
和空指针)后，若该结点的索引项数等于 m 个，则必须把它分裂为 两 个结点。
28.在从m阶的B_树删除元素的过程中，当一个结点被删除掉一个索引项后，所含索引项等于┌m/2┐
-2个，并且它的左右兄弟结点中的索引项数均等于┌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%的元素为非零元素，现要求对其非零元素进行散列存储
，使之能够按照元素的行、列值存取矩阵元素(即元素的行、列值联合为元素的关键字)，试采用除
留余数法构造散列函数和线性探查法处理冲突，分别写出散列表和查找散列表的算法。
分析：由题意可知，整个稀疏矩阵中非零元素的个数为100。为了散列存储这100个非零元素，需要
使用一个作为散列的一维数组，该数组中元素的类型应为：
struct ElemType{
int row;//存储非零元素的行下标
int col;//存储非零元素的列下标
float val;//存储非零元素值
};
假定用HT[m]表示这个散列，其中m为散列表的长度，若取装填因子为0.8左右，则令m为127为宜
(因为127为质数)。
按题目要求，需根据稀疏矩阵元素的行下标和列下标存取散列表中的元素，所以每个元素的行下
标和列下标同时为元素的关键字。假定用x表示一个非零元素，按除留余数法构造散列函数，并考虑
尽量让得到的散列地址分布均匀，所以采用的散列函数为：
H(x)=(13*x.row+17*x.col)%m
解：
根据以上分析，建立散列表的算法如下：
int Create(ElemType HT[],int m)
//根据稀疏矩阵中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++)
{//每循环一次从键盘上输入一个非零元素并插入到散列表中
cout<<i<<":";
cin>>x.row>>x.col>>x.val;//输入非零元素
d=(13*x.row+17*x.col)%m;//计算初始散列地址
temp=d;
while(HT[d].val!=0){//线性探查存储位置，此循环条件也可用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)
{
//采用与插入时使用的同一散列函数计算散列地址
int d=(13*row+17*col)%m;
//采用线性探查法查找行、列下标分别为row和col的元素
while(HT[d].val!=0)
{//此循环条件也可用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;
}
