西南交通大学840数据结构编程大题-2021年

• • • 第一题
    • 第二题

1.己知二叉树采用二叉链表存储结构，结点及结点指针数据类型定义如:

typedef struct node {
    int data;
    struct node *Ichild, *rchild;
} BTNode, *BT;

试写出C++算法函数void fmin(BT root, int &min);求二叉树结点data域的最小值存于形参变量min中。其中，root表示二叉树根结点地址。
也可以写出C语言函数void fmin(BT root, int *pmin);
己知int型长度为4字节，则int型可以表示的最大整数为2147483647.
调用时，int min=2147483647;
fmin(root, min); //C++语言
或fmin(root, &min);//C语言
调用结束后，变量min值为二叉树中所有结点data 域的最小值。

#include 
typedef struct node {
    int data;
    struct node *lchild, *rchild;
} BTNode, *BT;
void fmin(BT root, int *pmin) {
    if (root == NULL) return;
    if (root->data < *pmin) *pmin = root->data;
    fmin(root->lchild, pmin);
    fmin(root->rchild, pmin);
}

2.编写程序，定义一个一维整型数组，从键盘输入10个互不相同的整数，将数组中的最大值与数组中的第一个元素交换,数组中最小值与最后一个元素交换,输出交换后的数组元素。
要求:
(1) main()函数的调用形式如下:

void main() {
    int number[10];
    input(number, 10);
    max_min_change(number, 10);
    output(number, 10);
}

(2)要求数据输入格式为:4,5,1,6,7,9,10,8,3,2
数据的输出格式为:10,5,2,6,7,9.,4,8,3,1
请编写相关函数，完成输入、查找并按要求交换最大和最小值、输出等功能。

#include 

void input(int *number, int n) {
    for (int i = 0; i < n - 1; i++) {
        scanf("%d,", &number[i]);
    }
    scanf("%d", &number[n - 1]);
}
void max_min_change(int *number, int n) {
    int minidx = 0, maxidx = 0;
    for (int i = 1; i < n; i++) {
        if (number[i] < number[minidx]) minidx = i;
        if (number[i] > number[maxidx]) maxidx = i;
    }

    // 交换最大的和第一个两个元素
    int temp = number[maxidx];
    number[maxidx] = number[0];
    number[0] = temp;

    // 交换最大的和第一个两个元素
    temp = number[minidx];
    number[minidx] = number[n - 1];
    number[n - 1] = temp;
}
void output(int *number, int n) {
    for (int i = 0; i < n - 1; i++) {
        printf("%d,", number[i]);
    }
    printf("%d", number[n - 1]);
}
void main() {
    int number[10];
    input(number, 10);
    max_min_change(number, 10);
    output(number, 10);
}