练习题8参考答案.doc

3. 简答题
（1）简述顺序查找法、折半查找法和分块查找法对被查找的表中元素的要求。对长度为n的表来说，三种查找法在查找成功时的平均查找长度各是多少？
答：三种方法对查找的要求分别如下。
① 顺序查找法：表中元素可以任意次序存放。
② 折半查找法：表中元素必须按关键字递增或递减排列，且最好采用顺序存储结构。
③ 分块查找法：表中元素每块内的元素可以任意次序存放，但块与块之间必须以关键字的大小递增（或递减）排列，即前一块内所有元素的关键字都不能大（或小）于后一块内任何元素的关键字。
三种方法的平均查找长度分别如下。
① 顺序查找法：查找成功的平均查找长度为(n+1)/2。
② 折半查找法：查找成功的平均查找长度为log2(n+1)-1。
③ 分块查找法：若用顺序查找确定所在的块，平均查找长度为：(+s)+1；若用二分查找确定所在块，平均查找长度为log2(+1)+。其中，s为每块含有的元素个数。
（2）折半查找适不适合链表结构的序列，为什么？用折半查找的查找速度必然比线性查找的速度快，这种说法对吗？
答：不适合。虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构为单链表，查找结点时只能从头指针开始逐步搜索，故不能进行折半查找。
折半查找的速度在一般情况下是快些，但在特殊情况下未必快。例如所查数据位于首位时，则线性查找快；而二分查找则慢得多。
（3）给定关键字序列为{3,5,7,9,11,13,15,17}，回答以下问题：
① 按表中元素的顺序依次插入一棵初始值为空的二叉排序树。画出插入完成后的二叉排序树，并求其在等概率情况下查找成功的平均查找长度。
答：① 按输入顺序构造的二叉排序树如图8.1所示。在等概率情况下查找成功的平均查找长度为：
ASLsucc==4.5
由此可见在同样序列的查找中，平衡二叉树比二叉排序树的平均查找长度要小，查找效率要高。

图8.1 一棵二叉排序树 图8.2 一棵平衡二叉树
（4）输入一个正整数序列{40,28,6,72,100,3,54,1,80,91,38}，建立一棵二叉排序树，然后删除结点72，分别画出该二叉树及删除结点72后的二叉树。
答：构造的二叉排序树如图8.3所示。为了删除结点72，在其左子树中找到最大结点54（只有一个结点），用其代替结点72。删除之后的二叉排序树如图8.4所示。

图8.3 二叉排序树 图8.4 删除72后的二叉排序树
（6）对一个固定的数据集，用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是什么？如果要求时间复杂度更小，你采用什么方法？此方法的时间复杂度是多少？
答：查找某个元素的时间复杂度下限，如果理解为最短查找时间，则当关键字值与表头元素相同时，比较1次即可。要想降低时间复杂度，可以改用Hash查找法。此方法对表内每个元素的比较次数都是O(1)。
（7）设有一组关键字{19,01,23,14,55,20,84,27,68,11,10,77}，采用哈希函数：
H(key)=key % 13
采用开放地址法的线性探测法解决冲突，试在0～18的哈希地址空间中对该关键字序列构造哈希表，并求成功和不成功情况下的平均查找长度。
解：依题意，m=19，线性探测法计算下一地址计算公式为：
d1=H(key)
dj+1=(dj+1) % m; j=1, 2, ...
其计算函数如下：
H(19)=19 mod 13=6
H(01)=01 mod 13=1
H(23)=23 mod 13=10
H(14)=14 mod 13=1 冲突
H(14)=(1+1) mod 19 =2
H(55)=55 mod 13=3
H(20)=20 mod 13=7
H(84)=84 mod 13=6 冲突
H(84)=(6+1) mod 19=7 仍冲突
H(84)=(7+1) mod 19=8
H(27)=27 mod 13=1 冲突
H(27)=(1+1) mod 19=2 冲突
H(27)=(2+1) mod 19=3 仍冲突
H(27)=(3+1) mod 19=4
H(68)=68 mod 13=3 冲突
H(68)=(3+1) mod 19=4 仍冲突
H(68)=(4+1) mod 19=5
H(11)=11 mod 13=11
H(10)=10 mod 13=10 冲突
H(10)=(10+1) mod 19=11 仍冲突
H(10)=(11+1) mod 19=12
H(77)=77 mod 13=12 冲突
H(77)=(12+1) mod 19=13
因此，构建的哈希表如表8.1所示。
表8.1 哈希表
下标
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
k

01
14
55
27
68
19
20
84

23
11
10
77

探测次数

1
2
1
4
3
1
1
3

1
1
3
2

ASL成功=(1+2+1+4+3+1+1+3+1+1+3+2)/12=23/12
ASL不成功=(1+9+8+7+6+5+4+3+2+1+5+4+3)/13=58/13
（8）线性表的关键字集合{87,25,310,08,27,132,68,95,187,123,70,63,47}，共有13个元素，已知哈希函数为：
H(k) = k mod 13
采用拉链法处理冲突。设计出这种链表结构，并计算该表的成功和不成功情况下的平均查找长度。
解：依题意，得到：
H(87)=87 mod 13=9
H(25)=25 mod 13=12
H(310)=310 mod 13=11
H(08)=08 mod 13=8
H(27)=27 mod 13=1
H(132)=132 mod 13=2
H(68)=68 mod 13=3
H(95)=95 mod 13=4
H(187)=187 mod 13=5
H(123)=123 mod 13=6
H(70)=70 mod 13=5
H(63)=63 mod 13=11
H(47)=47 mod 13=8
采用拉链法处理冲突的哈希表如图8.7所示。成功查找的平均查找长度：
ASL成功=(1×10+2×3)/10=1.6
ASL不成功=(1×7+2×3)/13=1

图8.7 采用拉链法处理冲突的哈希表
4. 算法设计题
（1）对含有n个元素的整型数组A，设计一个较优的算法同时找最大元素和最小元素。
解：通过一趟扫描并比较，可以找出最大元素max和最小元素min。对应的算法如下：
void MaxMin(int A[],int n,int &min,int &max)
{ int i;
min=max=A[0];
for (i=1;i<n;i++)
if (R[i]<min)
min=R[i];
else if (R[i]>max)
max=R[i];
}
（2）设计二分查找的递归算法。
解：对应的递归算法如下：
int BinSearch1(SqType R[],KeyType k,int low,int high)
{ int mid;
if (low>high)
return(-1);
else
{ mid=(low+high)/2;
if (k==R[mid].key)
return(mid);
else if (k>R[mid].key)
return(BinSearch1(R,k,mid+1,high));//在左子树中递归查找
else
return(BinSearch1(R,k,low,mid-1)); //在右子树中递归查找
}
}
（3）假设二叉排序树bt的各元素值均不相同，设计一个算法按递增次序输出所有结点值。
解：按中序序列遍历二叉排序树即按递增次序遍历，对应值的算法如下：
void incrorder(BSTNode *bt)
{ if (bt!=NULL)
{ incrorder(bt->lchild);
printf("%d ",bt->data);
incrorder(bt->rchild);
}
}
（4）设计一个递归算法，从大到小输出二叉排序树中所有其值不小于k的关键字。
解：由二又排序树的性质可知，右子树中所有结点值大于根结点值，左子树中所有结点值小于根结点值。为了从大到小输出，要先遍历右子树，再访问根结点，后遍历左子树。对应的算法如下：
void Output(BSTNode *bt,KeyType k)
{ if (bt!=NULL)
{ Output(bt->rchild,k);
if (bt->key>=k)
printf("%d ",bt->key);
Output(bt->lchild,k);
}
}
（5）假设二叉排序树中所有结点关键字不同，设计一个算法，求出指定关键字的结点所在的层次。
解：设二叉排序树采用二叉链存储结构。采用二叉排序树非递归查找算法，用h保存查找层次。对应的算法如下：
int level(BSTNode *bt, KeyType k)
{ int h=0;
if (bt!=NULL)
{ h++;
while (bt->data!=k)
{ if (k<bt->data)
bt=bt->lchild; //在左子树中查找
else
bt=bt->rchild; //在右子树中查找
h++; //层数增1
}
return h;
}
}
上机实验题8
假设二叉树的数据域为int类型，由其括号表示建立对应的二叉链存储结构，设计一个算法判断该二叉树是否为一棵二叉排序树。并用相关数据进行测试。
解：结合第6章的二叉树基本运算算法和二叉排序树的特点设计对应的程序如下：
#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
typedef int ElemType; //二叉树的data域设为int类型
typedef struct tnode
{ ElemType data; //数据域
struct tnode *lchild,*rchild; //指针域
} BTNode; //二叉树结点类型
BTNode *pre=NULL; //pre为全局变量,保存当前结点中序前驱结点地址,初值为NULL
int judgeBST(BTNode *bt) //判断二叉树bt是否是一棵二叉排序树
{ int b1,b2;
if (bt==NULL) //空树是BST
return 1;
else
{ b1=judgeBST(bt->lchild);
if (b1==0) //左子树不是BST,整个二叉树也不是BST
return 0;
if (pre!=NULL && pre->data>=bt->data)
return 0;
pre=bt; //pre指向当前访问的结点
b2=judgeBST(bt->rchild); //判断右子树是否为BST
return b2; //返回右子树的判断结果
}
}
void CreateBTree(BTNode * &bt,char *str) //由str建立二叉链bt
{ BTNode *St[MaxSize],*p=NULL;
ElemType d;
int top=-1,k,j=0;
char ch;
bt=NULL; //建立的二叉树初始时为空
ch=str[j];
while (ch!='\0') //str未扫描完时循环
{ switch(ch)
{
case '(':top++;St[top]=p; //为'(',其后结点为栈顶结点的左孩子
k=1; break;
case ')':top--;break; //为')',当前子树结束
case ',':k=2; break; //为',',其后结点为栈顶结点的右孩子
default: //为数字符,提取数字并建相应的结点
d=0;
while (str[j]>='0' && str[j]<='9')
{ //str[j]为数字符,将数字串转换成数值d
d*=10;
d+=str[j]-'0';
j++;
}
j--; //后退一个字符
p=(BTNode *)malloc(sizeof(BTNode));
p->data=d; p->lchild=p->rchild=NULL;
if (bt==NULL) //*p为二叉树的根结点
bt=p;
else //已建立二叉树根结点
{ switch(k)
{
case 1:St[top]->lchild=p;break;
case 2:St[top]->rchild=p;break;
}
}
break;
}
j++;
ch=str[j];
}
}
void DestroyBTree(BTNode *&bt) //销毁二叉树
{ if (bt!=NULL)
{ DestroyBTree(bt->lchild);
DestroyBTree(bt->rchild);
free(bt);
}
}
void DispBTree(BTNode *bt) //输出二叉树
{ if (bt!=NULL)
{ printf("%d",bt->data);
if (bt->lchild!=NULL || bt->rchild!=NULL)
{ printf("("); //有子树时输入'('
DispBTree(bt->lchild); //递归处理左子树
if (bt->rchild!=NULL) //有右子树时输入'.'
printf(",");
DispBTree(bt->rchild); //递归处理右子树
printf(")"); //子树输出完毕，再输入一个')'
}
}
}
void main()
{ BTNode *bt;
char a[]="25(18(2(,4(,11))),46(39(32),53(,74(67(60)))))";
CreateBTree(bt,a);
printf("二叉树:"); DispBTree(bt); printf("\n");
if (judgeBST(bt))
printf("该二叉树是一棵BST\n");
else
printf("该二叉树不是一棵BST\n");
DestroyBTree(bt);
}