数据结构习题及答案

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