数据结构[2016]

一、设有二维数组A[6][8],每个元素占6个字节存储，实现存放，A[0][0]的起始地址为1000,计算： (10分)

(1)数组最后一个元素A[5][7]的起始地址；

(2)按行优先存放时，元素A[1][4]的起始地址；

(3)按列优先存放时，元素A[4][7]的起始地址。

二、若有一棵二叉树，左右子树均有三个结点，其左子树的前序序列与中序序列相同，右子树的中序序列与后序序列相同，试构造该树。 (10分)

三、首先将下图所示的无向图给出其存储结构的邻接链表表示，然后写出对其分别进行深度优先遍历，广度优先遍历的结果。(10分)

四、已知一棵二叉树的前序遍历的结果是ABECDFGHIJ,中序遍历的结果是EBCDAFHIGJ,试画出这棵二叉树。(10分)

五、使用普里姆算法构造出如下图所示的图G的一棵最小生成树。(10分)

六、任意一个有n个结点的二叉树，已知它有m个叶子结点，试证明非叶子结点有(m-1)个度数为2,其余度数为1。(10分)

七、给出一组关键字(29,18,25,47,58,12,51,10),分别写出按下列各种排序方法进行排序时的变化过程：(15分)

(1)归并排序，每归并一次书写一个次序。

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

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

八、对关键字序列7,4,1,14,100,30,5,9,20,134,设哈希函数为H(X)=X MOD 13。试给出表长为13的哈希表(用线性探测开放定址法处理冲突)。(15分)

九、假定用于通信的电文仅由8个字母cl,c2,c3,c4,c5,c6,c7,c8组成，各字母在电文中出现的频率分别为5,25,3,6,10,11,36,4。试为这8个字母设计不等长Huffman编码，并给出该电文的总码数。(15分)

十、试写一个双向冒泡排序的算法，即在排序过程中交替改变扫描方向。(15分)

#include <stdio.h>

// 双向冒泡排序函数

void cocktailSort(int arr[], int n) {

    int swapped, start, end;

    do {

        swapped = 0;

        // 从左到右，类似于普通的冒泡排序

        for (int i = start; i < end - 1; i++) {

            if (arr[i] > arr[i + 1]) {

                int temp = arr[i];

                arr[i] = arr[i + 1];

                arr[i + 1] = temp;

                swapped = 1;

            }

        }

        if (!swapped)

            break;

        swapped = 0;

        end--;

        // 从右到左，反向冒泡

        for (int i = end - 1; i >= start; i--) {

            if (arr[i] > arr[i + 1]) {

                int temp = arr[i];

                arr[i] = arr[i + 1];

                arr[i + 1] = temp;

                swapped = 1;

            }

        }

        start++;

    } while (swapped);

}

int main() {

    int arr[] = {5, 1, 4, 2, 8, 0, 2};

    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");

    for (int i = 0; i < n; i++) {

        printf("%d ", arr[i]);

    }

    printf("\n");

    cocktailSort(arr, n);

    printf("Sorted array: ");

    for (int i = 0; i < n; i++) {

        printf("%d ", arr[i]);

    }

    printf("\n");

    return 0;

}

十一、编写程序求1!+2!+3!+4!+…+30!之和。(15分)

#include <stdio.h>

#include <stdlib.h>

// 计算阶乘

unsigned long long factorial(unsigned int n) {

    unsigned long long fact = 1;

    for (unsigned int i = 1; i <= n; ++i) {

        fact *= i;

    }

    return fact;

}

int main() {

    unsigned long long sum = 0;

    unsigned long long currentFactorial;

    // 计算从 1! 到 30! 的阶乘之和

    for (unsigned int i = 1; i <= 30; ++i) {

        currentFactorial = factorial(i);

        sum += currentFactorial;

        printf("Sum up to %u!: %llu\n", i, sum);

    }

    printf("Sum of factorials from 1! to 30!: %llu\n", sum);

    return 0;

}

十二、定义一个通讯录结构，成员包括：姓名(字符串)、电话(字符串)、生日(日期结构：年、月、日)。编写函数实现数据的输入、输出和按姓名查找。(15分)

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

// 定义日期结构

typedef struct {

    int year;

    int month;

    int day;

} Date;

// 定义通讯录结构

typedef struct {

    char name[50]; // 姓名

    char phone[20]; // 电话

    Date birthday; // 生日

} Contact;

// 输入通讯录信息

void inputContact(Contact *contact) {

    printf("Enter name: ");

    fgets(contact->name, sizeof(contact->name), stdin);

    contact->name[strcspn(contact->name, "\n")] = '\0'; // 去掉换行符

    printf("Enter phone: ");

    fgets(contact->phone, sizeof(contact->phone), stdin);

    contact->phone[strcspn(contact->phone, "\n")] = '\0'; // 去掉换行符

    printf("Enter birthday (YYYY MM DD): ");

    scanf("%d %d %d", &contact->birthday.year, &contact->birthday.month, &contact->birthday.day);

    getchar(); // 吃掉换行符

}

// 输出通讯录信息

void outputContact(const Contact *contact) {

    printf("Name: %s\n", contact->name);

    printf("Phone: %s\n", contact->phone);

    printf("Birthday: %d-%02d-%02d\n", contact->birthday.year, contact->birthday.month, contact->birthday.day);

}

// 按姓名查找通讯录信息

int findContactByName(const Contact *contacts, int n, const char *name) {

    for (int i = 0; i < n; i++) {

        if (strcmp(contacts[i].name, name) == 0) {

            outputContact(&contacts[i]);

            return 1; // 找到了

        }

    }

    return 0; // 没找到

}

int main() {

    int n;

    printf("Enter the number of contacts: ");

    scanf("%d", &n);

    getchar(); // 吃掉换行符

    Contact contacts[n]; // 通讯录数组

    // 输入通讯录信息

    for (int i = 0; i < n; i++) {

        printf("Enter details for contact %d:\n", i + 1);

        inputContact(&contacts[i]);

    }

    // 输出通讯录信息

    printf("\nContacts:\n");

    for (int i = 0; i < n; i++) {

        outputContact(&contacts[i]);

    }

    // 按姓名查找通讯录信息

    char searchName[50];

    printf("\nEnter name to search: ");

    fgets(searchName, sizeof(searchName), stdin);

    searchName[strcspn(searchName, "\n")] = '\0'; // 去掉换行符

    if (findContactByName(contacts, n, searchName)) {

        printf("Contact found.\n");

    } else