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

文章目录

• • • 第一题
    • 第二题
    • 第三题

第一题

1.编写算法，利用队列实现二叉树按层次遍历。

(10分)
二叉树的结点数据类型定义如下

typedef struct node {
    int val; 
    struct node* lchild; 
    struct node*rchild; 
}bitree;

队列可直接使用，无需给出其实现细节( 即假设队列已有正确定义，所用 *** 作请加适当注释即可)。

(1)算法依次输出所有遍历的结点
如： 1
2 3
输出 123

(2)算法按层次输出每层遍历的结点
输出 1
2 3

第一问

#include 
#include 
using namespace std;
typedef struct node {
    int val;
    struct node *lchild;
    struct node *rchild;
} bitree;
void LeveOrder_one(bitree *root) {
    // 第一问
    if (root == NULL) return;
    queue<bitree *> q; //定义队列
    while (q.size()) {
        bitree *top = q.front(); // 取队头元素
        q.pop(); // 出队
        if (top == NULL) continue;
        printf("%d", top->val);
        q.push(top->lchild), q.push(top->rchild); // 讲左右孩子入队
    }
}

第二问

void LeveOrder_two(bitree *root) {
    
    if (root == NULL) return;
    queue<bitree *> q; //定义队列
    while (q.size()) {
        int cnt = q.size(); // 记录此时队列中元素
        while (cnt--) {
            bitree *top = q.front();
            q.pop();
            if (top == NULL) continue;
            printf("%d", top->val);
            q.push(top->lchild), q.push(top->rchild);
        }
        printf("\n");
    }
}

第二题

2.输入三个1位非负整数，输出由这三个1位整数组成的一一个三位整数( 能构成十进制3位整数)，且该三位整数的百位数、十位数、个位数分别按升序排列。

如:
输入:3 9 6 输出: 369
输入:9 0 3 输出: error

#include 
int get_max(int a, int b) {
    return a > b ? a : b;
}
int get_min(int a, int b) {
    return a > b ? b : a;
}
int main() {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    int max = get_max(get_max(a, b), c);
    int min = get_min(get_min(a, b), c);
    int mid = a ^ b ^ c ^ max ^ min;
    if (min == 0)
        puts("error");
    else
        printf("%d", min * 100 + mid * 10 + max);
    return 0;
}

第三题

3.给定程序中，函数fun的功能是:将NXN矩阵主对角线元素中的值与反向对角线对应位置上元素中的值进行交换。

例如，若N=3,有下列矩阵:
1 2 3
4 5 6
7 8 9

交换后为:
3 2 1
4 5 6
9 8 7

要求: (1) N要在程序中通过常量定义给出;
(2)按照上述题目要求，定义函数fun()完成相应的功能;
(3)NXN矩阵在main函数中给出，在main函数中铜用函数fun( )完成交换，
并在main函数中输出交换后的矩车.

#include 
#define N 4
void func(int arr[N][N], int n) {
    for (int i = 0; i < n; i++) {
        int temp = arr[i][i];
        arr[i][i] = arr[i][n - 1 - i];
        arr[i][n - i - 1] = temp;
    }
}

void main() {
    int arr[N][N];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            arr[i][j] = i * N + j + 1;
            printf("%d ", arr[i][j]);
        }
        puts("");
    }
    func(arr, N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%d ", arr[i][j]);
        }
        puts("");
    }
}