华水967数据结构2024真题（回忆版）

一、 选择[10道) (20分).

1、数据结构中，从逻辑结构上可以把数据结构分为()

答案：线性结构和非线性结构

2、给了一个二叉树的中序遍历，求二叉树的后序遍历

解析：
要根据中序遍历的结果来推导后序遍历，需要知道二叉树的根节点。假设中序遍历的结果为inorder = [D, B, E, A, F, C, G]，我们可以通过以下步骤来推导后序遍历：
步骤 1: 找到根节点
后序遍历的最后一个元素是根节点。假设我们知道根节点是 A。
步骤 2: 分割中序遍历
在中序遍历中找到根节点 A，将数组分成左子树和右子树：
左子树的中序遍历：[D, B, E]
右子树的中序遍历：[F, C, G]
步骤 3: 分割前序遍历
假设我们也有前序遍历的结果 preorder = [A, B, D, E, C, F, G]，可以通过前序遍历来确定左右子树的根节点：
左子树的根节点是 B
右子树的根节点是 C
步骤 4: 递归处理左右子树
左子树
中序遍历：[D, B, E]
前序遍历：[B, D, E]
找到左子树的根节点 B，分割中序遍历：
左子树的中序遍历：[D]
右子树的中序遍历：[E]
递归处理：
左子树的根节点是 D，没有子节点
右子树的根节点是 E，没有子节点
右子树
中序遍历：[F, C, G]
前序遍历：[C, F, G]
找到右子树的根节点 C，分割中序遍历：
左子树的中序遍历：[F]
右子树的中序遍历：[G]
递归处理：
左子树的根节点是 F，没有子节点
右子树的根节点是 G，没有子节点
步骤 5: 合并结果
根据后序遍历的定义（左子树、右子树、根节点），我们可以从下往上合并结果：
左子树的后序遍历：[D, E, B]
右子树的后序遍历：[F, G, C]
整棵树的后序遍历：[D, E, B, F, G, C, A]

3、关于邻接表和邻接矩阵适用于稠密图/稀疏图的问题

解析：
邻接表适用于的情况
稀疏图：邻接表在存储稀疏图时更为节省空间。稀疏图的特点是边数远小于顶点数平方，因此使用邻接表可以避免为不存在的边分配空间。
应用场景：邻接表适用于边的数量远小于顶点数的平方的图，如社交网络、网络路由等。

邻接矩阵适用于的情况
稠密图：邻接矩阵在存储稠密图时更为高效。稠密图的特点是边数接近于顶点数平方，使用邻接矩阵可以直接通过矩阵访问判断两个顶点之间是否有边，时间复杂度为O(1)。
应用场景：邻接矩阵适用于边的数量接近于顶点数的平方的图，如完全图、密集网络等

4、给了一个二维数组A[M][N]，计算另外一个数组的地址 例;设有A[6][5]数组,每数组占四个字节，告诉了起始地址，计算A[2][3]。

5、考查广义表head和tail方法使用 例;设广表A=(x,((a,b),c,d))。求Head (Head (Tail(A)))=?

解析：
Tail(A):
A 的尾部是从第二个元素开始的所有元素。
A = (x, ((a, b), c, d))，所以 Tail(A) = (((a, b), c, d))。
Head(Tail(A)):
Tail(A) = (((a, b), c, d))，其头部是第一个元素。
因此，Head(Tail(A)) = (c, d)。
Head(Head(Tail(A))):
Head(Tail(A)) = (c, d)，其头部是第一个元素。
所以，Head(Head(Tail(A))) = ©。

6、中缀表达式和后缀表达式的转换

解析：
中缀表达式转后缀表达式
转换中缀表达式到后缀表达式的过程通常使用栈来实现。以下是转换的步骤：
1.初始化一个空栈和空的后缀表达式列表。
2.从左到右扫描中缀表达式的每个字符：
如果字符是操作数（数字或变量），直接添加到后缀表达式列表。
如果字符是左括号 (，压入栈。
如果字符是右括号 )，弹出栈中的元素直到遇到左括号 (，并将这些元素添加到后缀表达式列表。
如果字符是操作符（如 +, -, *, /），弹出栈中优先级大于或等于当前操作符的所有操作符，并将它们添加到后缀表达式列表，然后将当前操作符压入栈。
3.扫描完所有字符后，将栈中剩余的所有操作符弹出并添加到后缀表达式列表。

其他的记不清了， 24年选择题不难，都是往年真题迭择题中的基础题。

二、 简答题 （共3小问、20分）

1、 简述头指针、头结点、首元结点。

解析：

头指针

定义：头指针是指向链表第一个结点的指针。它并不存储任何数据，只是用来标识链表的起始位置。
作用：头指针是链表的必要元素，它允许我们访问链表中的第一个元素，从而开始遍历整个链表。

头结点

定义：头结点是链表中的一个特殊节点，它位于链表的最开始位置，但通常不存储实际的数据，而是作为链表的一个标识。
作用：头结点的主要作用是为链表提供一个统一的起点，使得链表的操作更加方便。它的存在使得在链表头部进行插入和删除操作时，不需要特别处理空链表的情况。

首元结点

定义：首元结点，也称为第一个元素结点，是链表中实际存储数据的第一个节点。
作用：首元结点是链表中的实际起始点，它后面跟随的是链表中的其他元素。通过首元结点，可以开始遍历链表并访问其数据。

2、 简述树(不是二叉树的三种存储结构，并说明其各自优缺点。

解析：
树（非二叉树）的三种存储结构分别是双亲表示法、孩子表示法和孩子兄弟表示法。以下是它们的优缺点：

双亲表示法

优点：可以很快得到每个结点的双亲结点。
缺点：求结点的孩子时需要遍历整个结构。

孩子表示法

优点：可以很快找到某个结点的所有子女（遍历该结点的孩子链表即可）。
缺点：寻找双亲操作需要遍历每个结点的孩子链表。

孩子兄弟表示法

优点：存储灵活，树转换为二叉树操作实现方便，易于查找结点的孩子等。
缺点：不易从当前结点查找其双亲结点（可以为每个结点增设一个parent域指向其父亲结点，但需要额外的空间开销）

3、详细写出堆排序的过程（题目给了一串数字）。

解析：
堆排序是一种基于二叉堆数据结构的比较排序算法，其基本思想是将待排序的序列构造成一个大顶堆（或小顶堆），然后将堆顶元素（最大值或最小值）与末尾元素交换，再调整剩余部分为新的堆，重复这个过程直到整个序列有序。以下是堆排序的详细过程：
堆排序的基本步骤
1.构建初始堆：将无序数组构造成一个大顶堆（或小顶堆）。这个过程通常从最后一个非叶子节点开始，向上遍历每个节点，如果节点的值小于其子节点的值，则将该节点与其子节点中值较小的一个交换，直到该节点满足大顶堆的条件。

2.堆排序：将堆顶元素（最大值或最小值）与堆的最后一个元素交换，此时末尾元素就成了最大值（或最小值）。然后将剩余元素重新构成一个堆，重复上述过程，直到堆中只剩下一个元素。
3.重复步骤2：每次从堆中取出最大（或最小）元素后，调整堆结构，使其重新满足大顶堆（或小顶堆）的性质，直到整个数组有序。

堆排序的时间复杂度和空间复杂度
时间复杂度：堆排序的时间复杂度为O(n log n)，其中n是数组的大小。这是因为构建初始堆的时间复杂度为O(n)，而每次堆调整的时间复杂度为O(log n)，总共需要进行n-1次堆调整。
空间复杂度：堆排序的空间复杂度为O(1)，因为它只需要一个额外的栈空间来存储原始数据，不需要额外的存储空间。

三、应用题、(共5题，记得4个)

1、利用栈模拟出算术表达式。（与2017年的综合题第一题类似）

解析：
算法步骤
1.初始化两个栈：一个用于存储操作数（operandStack），另一个用于存储运算符（operatorStack）。但在逆波兰表示法中，通常只需要一个操作数栈。

2.读取表达式：逐个读取表达式中的元素。

3.处理操作数：如果当前元素是数字，则将其压入操作数栈。

4.处理运算符：如果当前元素是运算符，则从操作数栈中弹出所需数量的操作数，执行运算，并将结果压回操作数栈。

5.重复步骤3和4，直到表达式处理完毕。

6.返回结果：表达式处理完毕后，操作数栈顶部的元素即为最终结果。

2、用两种方法求最小生成树，给出过程。

解析：

Prim算法

基本思想：从一个顶点开始，每次选择与当前生成树相连的权值最小的边，直到所有顶点都被包含。
步骤：
1.选择任意一个顶点作为起点，将其加入生成树集合。
2.在剩余未加入的顶点中找到与生成树集合中顶点相连的权值最小的边。
3.将这条边加入生成树集合，并将对应的顶点加入。
4.重复步骤2和3，直到所有顶点都被加入生成树集合。

Kruskal算法

基本思想：按照边的权值从小到大排序，依次选择边，如果这条边连接的两个顶点不在同一个连通分量中，则将它们合并，直到所有顶点都在同一个连通分量中。
步骤：
1.将所有边按权值从小到大排序。
2.初始化一个空集合，用来存放最小生成树的边。
3.依次取出权值最小的边，如果这条边的加入不会形成环，则将其加入最小生成树中。
4.重复步骤3，直到所有顶点都被包含在内。

3、 考查哈希函数，给了一组数据、哈希函数，让画哈希表和求平均查找长度。

4、考查关键路径问题

题中没直接给出图，题的大意是给出了顶点集V=S{a.b,c}，边集
E=S{(a,b).(b.c)_}，共三问。
第一问：画出这个图。
第二问：求顶点最早开始时间。
第三问：求顶点最晚开始时间。

24题给的不是边的权值，而是顶点完成所需的时间（之前没考）。

四、代码题（共四个，其中一个算是应用题）

1、代码填空题，共五个空。一个空两分，线性表的插入删除。

解析：

// 在指定位置插入元素
int insertElement(SeqList *list, int position, int element) {
    if (position < 0 || position > list->length || list->length >= MAXSIZE) {
        return -1; // 插入失败
    }
    for (int i = list->length; i > position; i--) {
        list->data[i] = list->data[i - 1];
    }
    list->data[position] = element;
    list->length++;
    return 0; // 插入成功
}

// 删除指定位置的元素
int deleteElement(SeqList *list, int position) {
    if (position < 0 || position >= list->length) {
        return -1; // 删除失败
    }
    for (int i = position; i < list->length - 1; i++) {
        list->data[i] = list->data[i + 1];
    }
    list->length--;
    return 0; // 删除成功
}

2、给了图，让画出迪杰斯特拉的最短路径图。

3、写出查找一个数的代码，若找不出则把这个数插入数据（有序）。

解析：

// 二分查找函数，返回目标值的索引（若存在），否则返回-1
int binarySearch(int arr[], int size, int target) {
    int left = 0, right = size - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1; // 未找到目标值
}
 
// 在有序数组中插入元素，并保持数组有序
void insertSorted(int arr[], int *size, int target) {
    int index = binarySearch(arr, *size, target);
    if (index != -1) {
        // 若已存在目标值，则不进行插入（或根据需要处理）
        printf("元素 %d 已存在于数组中。\n", target);
    } else {
        // 在index位置插入目标值（需移动元素）
        for (int i = *size; i > index; i--) {
            arr[i] = arr[i - 1];
        }
        arr[index] = target;
        (*size)++; // 数组大小加1
    }
}
	

4、写出把一个二叉树中的结点存储到一个一维数组中的代码。

解析：

// 层序遍历函数，将节点值存储到数组中
void levelOrder(TreeNode* root, int* arr, int* index) {
    if (root == NULL) return; 
    // 创建一个队列用于层序遍历
    TreeNode** queue = (TreeNode**)malloc(100 * sizeof(TreeNode*)); // 假设队列大小足够，实际应用中可能需要动态调整
    int front = 0, rear = 0;
    // 将根节点入队
    queue[rear++] = root;
    // 层序遍历
    while (front < rear) {
        TreeNode* currentNode = queue[front++];
        arr[(*index)++] = currentNode->val; // 将当前节点值存入数组
        // 左子节点入队
        if (currentNode->left != NULL) {
            queue[rear++] = currentNode->left;
        }
        // 右子节点入队
        if (currentNode->right != NULL) {
            queue[rear++] = currentNode->right;
        }
    }
    // 释放队列内存
    free(queue);
}