【刷题】算法设计题+程序设计题【2】2019-2024

11.20	2019年真题*2	BST二叉排序树分裂、双向冒泡排序

2019 真题

【2019 1】编写算法，将一棵二叉排序树 分解成两棵二叉排序树 t1和t2，使得t1中的所有结点关键字的值都小于x，t2中所有结点关键字都大于x。

typedef struct BSTNode{int data;struct BSTNode *left,*right;
}BSTNode;

void splitBST(BSTNode* t,int x, BSTNode *&A,BSTNode *&B){if(t == NULL){A = NULL;B = NULL;return ;}if(t->data <= x){//当前结点属于A，且左子树都属于AA = t;//递归处理右子树splitBST(t->right , x , A->right , B);}else{//当前节点属于B，且右子树都属于BB = t;//递归处理左子树，判断是否还有大于x的值splitBST(t->left , x , A , B->left);}
}

【2019 2】传统的冒泡排序始终从低位开始往高位索引方向扫描元素进行排序，但是有一种改进的冒泡排序既能从低位往高位扫描元素，也能从高位往低位双向扫描元素，请编写算法实现这种双向冒泡排序。

//默认是升序
void DoubleBubble(int arr[] , int n){int begin = 0 , end = n-1;while(begin < end){//低位往高位，将大的往后for(int i = begin ; i < end ; i++){if(arr[i] > arr[i+1])swap(arr[i] , arr[i+1]);}end--;//高位往低位，将小的往前for(int j = end; j > begin ; --j){if(arr[j] < arr[j-1])swap(arr[j] , arr[j-1]);}begin++;}
}