3. 答案：判定树为二叉树，其中每一结点对应表中一个记录，但结点值不是记录的关键字，而是记录在表中的位置序号。根结点对应当前区间的中间记录，左子树对应前一子表，右子树对应后一子表。
4. 答案：折半查找方法的优点是，比较次数少，查找速度快，平均性能好。其缺点是，要求待查表为顺序有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序表。
5. 答案：分块查找的过程如下： 首先将查找表分成若干个块（子表）。一般情况下，块的长度相等，最后一块可以不等。每块中元素任意排列，即块内无序，但前一块中的最大关键字必须小于后一块中的最小关键字，即块与块之间有序。
然后构造一个索引表。其中每个索引项对应一个块，并记录每块的起始位置，以及每块中的最大关键字。索引表按关键字有序排列。
6. 答案：二叉排序树（Binary Sort Tree）或者是一棵空树，或者是满足下列性质的二叉树：
1）若它的左子树非空，则左子树上所有结点的值均小于根结点的值； 2）若它的右子树非空，则右子树上所有结点的值均大于根结点的值； 3）左、右子树也分别为二叉排序树。 7. 答案：冒泡排序（Bubble Sort）的基本思想是：通过对无序序列中相邻记录关键字的比较和位置的交换，使得关键字较小的记录向一头漂移，关键字较大的记录向另一头下沉，从而使无序序列变成有序序列。
8. 答案：插入排序（Insertion Sort）的基本思想是：每次将一个待排序的记录按其关键字的大小插入到已排好序的有序表中，使得插入之后得到的表仍然是有序表，如此反复，直到全部记录插入完成为止。
9. 答案：快速排序的基本思想是：首先在待排序的记录中确定一个记录Ri，经过比较和移动，将Ri放到“中间”某个位置上，使得Ri左边所有记录的关键字小于或等于Ri的关键字，Ri右边所有记录的关键字大于或等于Ri的关键字。于是，以Ri所在的位置为界，将记录序列划分为左、右两个子序列。然后，用同样的方法分别对这两个子序列进行划分，得到4个更小的子序列。继续进行下去，直到每个子序列只有一个记录为止。
10. 答案：归并排序（Merge Sort）的基本思想是：把K（K ≥2）个已排序的子序列组合在一起，形成一个有序的序列。同时归并K个有序子序列为一个有序序列的排序过程叫做K路归并排序。为简单起见。这里仅讨论二路归并排序（简称归并排序）。
四、算法设计
1. 从顺序存储的有序表中，顺序查找键值为k的元素。
int SqSearch(int a[],int k)
{ int i=0;
a[n]=k; //把k的值赋给a[n]
while(a[i]< k) i++ ; //从表头开始顺序查找值为k的元素
if(a[i]==k && i!=n) //若查找成功则返回元素的位置，否则返回 -1 return i; else
36
return -1; }
2. 二分查找的递归算法。
int BinSearch(int a[],int low,int high,int k)
{ //初始调用时，low和high所对应的实参值为待查区间的下界和上界
int mid; if(low<=high) {
mid=(low+high)/2; //mid存放查找区中间元素的下标 if(a[mid]==k)
return mid; //查找成功返回元素的下标 else
if(k
return BinSearch(a,low,mid-1,k); //在左子表继续查找
else
return BinSearch(a,mid+1,high,k); //在右子表继续查找
}
return 0; //查找失败 }
3. 求出二叉排序树中，元素值为k的结点所在的层数。
int LevelsNode(BiTree r,KeyType k)
{
if(r!=NULL) //若为空树，则查找结束 {
cout<<\结点不存在！\ exit(1); } else
if(r->data==k)
return 1; //若根结点元素值等于k,则返回层数1 else
37
if(r->data >k)
return 1+LevelsNode(r->lchild,k); //在左子树继续找
eles
return 1+LevelsNode(r->rchild,k); //在右子树继续找 }
4. 将线性表中的元素值存于数组a[]中，并将正、负元素值分开。
void separate(int a[],int n)
{
int x,i=1,j=n; while(i while(a[i]<=0 && i i++; //从前向后查找一个正数 while(a[j]>=0 && j>i) j--; //从后向前查找一个负数 if(i==j) break; //当从两端向中间扫描到相遇时退出循环 x=a[i]; //交换i和j位置上的元素值 a[i]=a[j]; a[j]=x; i++; //重新修改i和j的值 j--; } } 5.采用另一种直接选择排序的方法对数组a[]中的n个元素排序。 void SelectSort(int a[],int n) { int x,i,j,k; for(i=1;i<=n/2;i++) //共需进行n/2趟 { k=i; //k存放最小值元素的下标，初值为i 38 for(j=i+1;j<=n - i+1;j++) //从当前排序区间中找出具有最小值的元素a[k] if(a[j] k=j; if(k!=i) { //把a[k]对调到该排序区间的第一个位置 x=a[i]; a[i]=a[k]; a[k]=x; } k=n -i+1; //用k存放当前区间最大值元素的下标，初值为n -i+1 for(j=n -i;j>=i+1;j--) if(a[j]>a[k]) k=j; //从当前排序区间中找出具有最大值的元素a[k] if(k!=n -i+1) { //把a[k]对调到该排序区间的最后一个位置 x=a[n -i+1]; a[n -i+1]=a[k]; a[k]=x; } } } 6. 本程序中包括的基类有Employee(职工)、Date(日期)和派生类Boss(经理)、Sale Boss(销售经理)、Commission Worker(推销员)、Piece Worker(计件工)和Hourly Worker(计时工)。它们的关系如下图所示： 39 职工月薪管理程序的类关系图 下列程序清单中每个类的说明分别存人H文件，每个类的成员函数的实现分别存入Cpp文件，主函数及相关功能函数存人Empmain.cpp文件。需求分析和设计过程从略。 程序如下： //EMPLOY2. H # ifndef EMPLOY2_H # define EMPLOY2_H //职工基类Employee # include < fstream.h > # include \class Employee { public: char EmpKind [ 20 ]; Employee ( ); Employee(char *empKind,int empNo,char *name,char *sex, float totalMounthPay, int yl, int ml, int dl, int y2, int m2, int d2); int getEmpNo( ); //取职工号 //职工种别 40