考试试题

 

一、给出数组A[3..8,2..6]0F integer,当它在内存中按行存放和按列存放时，分别写出元素A[i,j]的地址计算公式(设每个元素占两个存储单元)。(10分)

 

 

 

 

 

二、已知一棵二叉树的中序序列的结果是BDCEAFHG,后序序列的结果是DECBHGFA,试画出这棵二叉树。(10分)

 

 

 

 

 

三、对下图所示的二叉树分别求出其先序、中序、后序序列。(10分)

 

 

 

四、己知图G如下，给出从顶点V1出发的一个深度优先生成树；给出从顶点V1出发产生的一个广度优先生成树。(10分)

 

 

 

 

五、使用克鲁斯卡尔算法构造出如下图所示的图G的一棵最小生成树。(10分)

 

 

六、试证明有n0个叶子的哈夫曼树共有2n0-1个结点。(10分)

 

 

 

七、给出一组关键字(12,2,16,30,28,10,16,20,6,18),分别写出按下列各种排序方法进行排序时的变化过程：  (15分)

(1)直接排序，每排序一次书写一个次序。

(2)快速排序，每划分一次书写一个次序。

(3)堆排序，先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。

 

 

 

 

 

八、设有一组关键字{19,01,23,14,55,20,84,27,68,11,10,77},采用哈希函数：H(Key)=Key MOD 13采用开放地址法的二次探测再散列方法解决冲突，试在0～18的散列地址空间中对该关键字序列构造哈希表。(15分)

 

 

 

 

九、有一份电文中共使用5个字符：A、B、C、D、E,它们出现的频率依次为4、7、5、2、9。

试画出对应的哈夫曼树(按左子树根结点的权小于等于右子树根结点的权的次序构造)。并求出每个字符的哈夫曼编码和带权路径长度。(15分)

 

 

 

 

• 编一函数，使输入的一个字符串按反序存放，在主函数中输入和输出字符串。(15分)

#include <stdio.h>
#include <string.h>
#include <ctype.h> // 用于isspace函数

// 字符串反序函数
void reverseString(char *str) {
    int len = strlen(str);
    int start = 0;
    int end = len - 1;

    // 交换字符串两端的字符，直到中间
    while (start < end) {
        // 忽略前导空格
        if (isspace((unsigned char)str[start])) {
            start++;
            continue;
        }
        // 忽略尾随空格
        if (isspace((unsigned char)str[end])) {
            end--;
            continue;
        }

        // 交换字符
        char temp = str[start];
        str[start] = str[end];
        str[end] = temp;

        // 移动索引
        start++;
        end--;
    }
}

int main() {
    char str[100]; // 定义一个字符数组

    // 输入字符串
    printf("Enter a string: ");
    fgets(str, sizeof(str), stdin); // 使用fgets读取包含空格的字符串

    // 去掉字符串末尾的换行符
    str[strcspn(str, "\n")] = '\0';

    // 反序字符串
    reverseString(str);

    // 输出反序后的字符串
    printf("Reversed string: %s\n", str);

    return 0;
}

 

 

 

 

• 编写一个程序，用“起泡法”对输入的20个字符按由小到大顺序排序。(15分)

#include <stdio.h>

// 冒泡排序函数
void bubbleSort(char arr[], int n) {
    int i, j;
    char temp;
    for (i = 0; i < n-1; i++) {
        // 每一轮排序后，最大的元素会冒泡到最后
        for (j = 0; j < n-i-1; j++) {
            // 如果当前字符比后面的字符大，则交换它们的位置
            if (arr[j] > arr[j+1]) {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

int main() {
    char arr[20]; // 定义一个字符数组
    int n = 20; // 数组长度

    // 输入20个字符
    printf("Enter 20 characters:\n");
    for (int i = 0; i < n; i++) {
        scanf(" %c", &arr[i]); // 输入字符，空格分隔
    }

    // 调用冒泡排序函数
    bubbleSort(arr, n);

    // 输出排序后的字符
    printf("Sorted characters:\n");
    for (int i = 0; i < n; i++) {
        printf("%c ", arr[i]);
    }
    printf("\n");

    return 0;
}

 

 

 

 

十二、有数组A[4][4],把1到16个整数分别按顺序放入A[0][0],…,A[0][3],A[1][0],…,

A[1][3],A[2][0],…,A[2][3]A[3][0],…,A[3][3]中，编写一个函数获取数据并求出两对角线元素的乘积。(15分)

 

#include <stdio.h>

// 函数声明
void fillAndComputeProducts(int A[4][4]);

int main() {
    int A[4][4]; // 定义一个4x4的二维数组

    // 调用函数来填充数组并计算乘积
    fillAndComputeProducts(A);

    return 0;
}

// 函数定义
void fillAndComputeProducts(int A[4][4]) {
    int i, j, counter = 1;
    int primaryProduct = 1;
    int secondaryProduct = 1;

    // 填充数组
    for (i = 0; i < 4; i++) {
        for (j = 0; j < 4; j++) {
            A[i][j] = counter++;
        }
    }

    // 计算主对角线上的元素乘积
    for (i = 0; i < 4; i++) {
        primaryProduct *= A[i][i];
    }

    // 计算副对角线上的元素乘积
    for (i = 0, j = 3; i < 4; i++, j--) {
        secondaryProduct *= A[i][j];
    }

    // 输出结果
    printf("Primary diagonal product: %d\n", primaryProduct);
    printf("Secondary diagonal product: %d\n", secondaryProduct);
}