2017-941

2017-941

1.（15分）A和B是长度为n的两个数组。设计一个算法，该算法输出长度为n的数组C。

• 要求1：数组C中的每一个元素$C[i] = || \{ A[j]|A[j]≤B[i],1≤j≤n\}||$，其中$||S||$表示集合S中的元素个数。例如：下表给出了长度为4的两个数组A和B，以及满足要求的数组C
• 要求2：所设计算法的时间复杂性低于$O(n^2)$

i	1	2	3	4
A[i]	6	17	9	10
B[i]	8	2	17	13
C[i]	1	0	4	3

（1）描述算法的基本设计思想（3分）；

C[1]的意思就是，A数组中小于等于B[1]的个数；C[2]就是，A数组中小于等于B[2]的个数。以此类推

先将A利用快速排序排好顺序，再用b进行折半查找

（2）用算法描述语言描述算法（8分）；

//折半查找来确定有序序列A中有多少元素不大于x
int binarySearch(int A[],int n,int x){
    int l = 0,r = n-1,m = (l+r)/2;
    while(l <= r){
        if(A[m] > x){
            r = m - 1;
        }else{
            l = m + 1;
        }
        m = (l+r)/2;
    }
    return l;//最后l为小于等于x元素的个数
}
//先采用快速排序排列A数组，时间复杂度（nlogn），要求不能超过n方
int Partition(int A[],int low,int high){     //一趟划分
    int pivot = A[low];                      //将当前表中第一个元素设为枢轴，对表进行划分
    int t = low;
    while(low<high){
        low++;
        while(A[low]<=pivot){                //从前往后找到一个比枢轴大的数
            low++;
        }
        while(A[high]>pivot){                //从后往前找到一个比枢轴小的数
            high--;
        }
        if(low<high){
            int w = A[low];                  //用临时变量w储存值，交换两个数
        	A[low] = A[high];                //用临时变量w储存值，交换两个数
        	A[high] = w;                     //用临时变量w储存值，交换两个数
        }
    }
    A[t] = A[high];                          //找到枢轴的正确位置，交换这两个元素
    A[high] = pivot;
    return high;                             //返回枢轴正确的位置
}
void QuickSort(int &A[],int low,int high){   //开始快排
    if(low<high){
        int mid = Partition(A,low,high);
        QuickSort(A,low,mid-1);              //枢轴左半边继续快排
        QuickSort(A,mid+1,high);
    }
}

void getArrayC(int A[],int B[],int C[],int n){
    Partition(A,0,n);//快排排序
    for(int i = 0; i < n; ++i){
        C[i] = binarySearch(A, n, B[i]);//查找
    }
}

（3）给出算法的时间复杂性分析（4分）。

• 排序时间$O(nlogn)+$查找时间$O(logn)$，符合要求

2.（10分）写出求二叉树宽度的非递归算法

• 二叉树的宽度定义为具有结点数最多的那一层上的结点总数。如下图所示，以a为根的二叉树宽度为3。假设二叉树以链接结构存储，指针T指向二叉树的根，树中结点的结构为（left，data，right）

（1）描述算法的基本设计思想（3分）；

• 利用主要层次遍历

• 再加上last指针：指向当前层数最右结点

（2）用算法描述语言描述算法（7分）；

int MaxBreadth(BiTree T){
    int front = -1,rear = -1;//队头尾指针
    int level =1,last = 0;//last指向当前层数最右结点，level为当前层数
    int width[];//储存每层最大宽度的数组
    BiTree p = T;//用p遍历二叉树
    Queue[++rear] = p;//根结点入队
    if(p == NULL){
        return 0;
    }
    width[level] = 1;//第一层一个结点
    while(rear > front){ //队列不为空
        p = Queue[++front];//层次遍历，出队元素
        if(p->lchild != NULL){
            Queue[++rear] = p->lchild; //左子树不为空，则左子树根结点入队 
        } 
        if(p->rchild != NULL){ 
            Queue[++rear] = p->rchild; //右子树不为空，则右子树根节点入队 
        }
        if(front == last){//出队元素和last所指向的最右结点相同时
            width[++level] = rear - last;//该层元素个数等于此时队列的尾指针减去上一层最右结点的位置
            last = rear;
        } 
    }
    //最后得到的层数会多一层 
    int max=0;
    for(int i=1;i<=level;i++){
        if(width[i]>max){
            max=width[i];
        }
    } 
    return max; 
}