2024年808数据结构答案

1.已知带头结点单链表，H为头指针。设计一个算法，查找到链表的第m个结点(不包含头结点)，并将元 素值为X的结点插入到该结点后，形成一个新的链表。

// 定义单链表节点结构
typedef struct Node {int data;struct Node* next;
} Node;// 创建新节点的函数
Node* createNode(int data) {Node* newNode = (Node*)malloc(sizeof(Node));if (newNode == NULL) {printf("内存分配失败！\n");exit(1);}newNode->data = data;newNode->next = NULL;return newNode;
}// 查找链表中第m个节点的函数（不包括头节点）
Node* findMthNode(Node* head, int m) {Node* current = head->next; // 跳过头结点int count = 1;while (current != NULL && count < m) {current = current->next;count++;}if (count == m && current != NULL) {return current;} else {return NULL; // 第m个节点不存在}
}// 在第m个节点后插入新节点的函数
void insertAfterMthNode(Node* head, int m, int X) {Node* mthNode = findMthNode(head, m);if (mthNode == NULL) {printf("链表中不存在第%d个节点！\n", m);return;}Node* newNode = createNode(X);newNode->next = mthNode->next;mthNode->next = newNode;
}

第一题

1.请编写程序，利用非递归的折半查找方法判定某个整数是否在一个有序整数数组 r[n]中。

以下是一个利用非递归折半查找（即二分查找）方法，来判断某个整数是否在一个有序整数数组中的C语言实现：

#include <stdio.h>// 非递归折半查找（即二分查找）函数
int binarySearch(int r[], int n, int target) {int left = 0;int right = n - 1;// 当左指针小于等于右指针时，继续搜索while (left <= right) {int mid = left + (right - left) / 2;  // 计算中间索引，避免溢出if (r[mid] == target) {return mid;  // 找到目标值，返回索引} else if (r[mid] < target) {left = mid + 1;  // 目标值在右半部分} else {right = mid - 1; // 目标值在左半部分}}return -1;  // 未找到目标值，返回-1
}int main() {// 有序整数数组int r[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};int n = sizeof(r) / sizeof(r[0]);  // 计算数组长度// 要查找的目标值int target;printf("请输入要查找的整数：");scanf("%d", &target);// 调用折半查找函数int result = binarySearch(r, n, target);// 输出查找结果if (result != -1) {printf("整数%d在数组中的位置为: %d\n", target, result);} else {printf("数组中不存在整数%d\n", target);}return 0;
}

代码说明：

1. binarySearch函数：这是一个非递归实现的折半查找函数。通过左右指针和中间索引来缩小搜索范围。每次比较中间值后，根据大小调整左右指针，直到找到目标值或范围结束。
2. main函数：定义了一个有序的整数数组r[]，接受用户输入的目标值，调用折半查找函数并输出结果。

示例输出：

请输入要查找的整数：7
整数7在数组中的位置为: 3

如果输入的值不在数组中：

请输入要查找的整数：8
数组中不存在整数8

复杂度分析：

• 时间复杂度：O(log n)，因为每次将搜索范围缩小一半。
• 空间复杂度：O(1)，因为只使用了几个额外的变量。

第二题

2.编写计算二叉树叶子节点个数的算法

以下是一个用C语言实现的计算二叉树叶子节点个数的算法：

#include <stdio.h>
#include <stdlib.h>// 定义二叉树节点结构
typedef struct Node {int data;struct Node* left;struct Node* right;
} Node;// 创建新节点的函数
Node* createNode(int data) {Node* newNode = (Node*)malloc(sizeof(Node));if (!newNode) {printf("内存分配失败\n");exit(1);}newNode->data = data;newNode->left = NULL;newNode->right = NULL;return newNode;
}// 计算二叉树叶子节点个数的函数
int countLeafNodes(Node* root) {if (root == NULL) {return 0;  // 空树没有叶子节点}// 如果左右子节点都为空，则该节点是叶子节点if (root->left == NULL && root->right == NULL) {return 1;}// 递归计算左子树和右子树中的叶子节点数目return countLeafNodes(root->left) + countLeafNodes(root->right);
}int main() {// 创建一个简单的二叉树/*1/   \2     3/ \   / 4   5 6  */Node* root = createNode(1);root->left = createNode(2);root->right = createNode(3);root->left->left = createNode(4);root->left->right = createNode(5);root->right->left = createNode(6);// 计算叶子节点个数int leafCount = countLeafNodes(root);printf("二叉树的叶子节点个数: %d\n", leafCount);return 0;
}

代码说明：

1. Node结构体：定义了二叉树的节点，每个节点包含数据、左子节点和右子节点指针。
2. createNode函数：用于创建一个新的二叉树节点。
3. countLeafNodes函数：这是递归函数，用来计算叶子节点个数。它通过判断节点是否为叶子节点（即左右子节点都为空），递归遍历左右子树，统计所有叶子节点。
4. main函数：构建一个简单的二叉树，并调用countLeafNodes函数计算其叶子节点个数。

示例输出：

二叉树的叶子节点个数: 3

对于上面的示例二叉树，叶子节点为4、5和6，因此叶子节点个数为3。

复杂度分析：

• 时间复杂度：O(n)，n为二叉树的节点个数。每个节点都会被访问一次。
• 空间复杂度：O(h)，h为二叉树的高度，递归调用栈的深度最大为树的高度。

第三题

3.实现栈的基本操作，并利用栈实现十进制到二进制的转换，输入为一个十进制整
数，输出为二进制序列，如十进制85变成二进制1010101(10分)。

以下是一个C语言实现的栈的基本操作，以及利用栈实现十进制到二进制转换的程序：

代码实现：

#include <stdio.h>
#include <stdlib.h>#define MAX 100  // 栈的最大容量// 定义栈结构
typedef struct Stack {int data[MAX];  // 用数组来存储栈中的元素int top;        // 栈顶指针
} Stack;// 初始化栈
void initStack(Stack* s) {s->top = -1;  // 栈为空时，栈顶指针设为-1
}// 判断栈是否为空
int isEmpty(Stack* s) {return s->top == -1;
}// 判断栈是否已满
int isFull(Stack* s) {return s->top == MAX - 1;
}// 入栈操作
void push(Stack* s, int value) {if (isFull(s)) {printf("栈已满，无法执行入栈操作\n");return;}s->data[++(s->top)] = value;  // 将元素压入栈顶
}// 出栈操作
int pop(Stack* s) {if (isEmpty(s)) {printf("栈为空，无法执行出栈操作\n");exit(1);}return s->data[(s->top)--];  // 返回栈顶元素并减少栈顶指针
}// 利用栈将十进制数转换为二进制
void decimalToBinary(int num) {Stack s;initStack(&s);// 当十进制数大于0时，不断取余数，并将余数入栈while (num > 0) {push(&s, num % 2);  // 将余数入栈num /= 2;  // 更新num为其商}// 依次弹出栈中的元素，得到二进制序列printf("二进制序列: ");while (!isEmpty(&s)) {printf("%d", pop(&s));}printf("\n");
}int main() {int decimalNumber;// 输入十进制数printf("请输入一个十进制整数: ");scanf("%d", &decimalNumber);// 将十进制转换为二进制decimalToBinary(decimalNumber);return 0;
}

代码说明：

1. 栈的基本操作：

   • initStack：初始化栈，设置栈顶指针为-1。
   • isEmpty：判断栈是否为空。
   • isFull：判断栈是否已满。
   • push：将元素压入栈顶。
   • pop：从栈顶弹出元素并返回。

2. 十进制到二进制的转换：

   • 利用栈来存储每次除以2的余数，直到商为0。
   • 然后通过依次弹出栈中的元素来构建二进制数。

输入输出示例：

输入：

请输入一个十进制整数: 85

输出：

二进制序列: 1010101

解释：

• 十进制数85转换为二进制为1010101。
• 栈的后进先出的特性帮助我们从最后一个余数到第一个余数依次输出二进制位。

复杂度分析：

• 时间复杂度：O(log n)，因为每次除法操作将十进制数缩小一半。
• 空间复杂度：O(log n)，栈最多会存储log n个二进制位。

第四题

4.设G=(V，E)是一个带权的无向连通网，所有边的权均大于0。编写求解G的最小生成树算法(10分)。

Prim算法的C语言实现：

#include <stdio.h>
#include <limits.h>#define V 5  // 图中顶点的数量// 查找权值最小且不在最小生成树中的顶点
int minKey(int key[], int mstSet[]) {int min = INT_MAX, minIndex;for (int v = 0; v < V; v++) {if (mstSet[v] == 0 && key[v] < min) {min = key[v];minIndex = v;}}return minIndex;
}// 打印生成树
void printMST(int parent[], int graph[V][V]) {printf("边   权值\n");for (int i = 1; i < V; i++) {printf("%d - %d    %d \n", parent[i], i, graph[i][parent[i]]);}
}// Prim算法计算最小生成树
void primMST(int graph[V][V]) {int parent[V];  // 用于存储生成树int key[V];     // 用于存储最小权值int mstSet[V];  // 记录哪些顶点已包含在最小生成树中// 初始化所有顶点的key值为无限大，mstSet值为falsefor (int i = 0; i < V; i++) {key[i] = INT_MAX;mstSet[i] = 0;}// 选择第一个顶点为根节点key[0] = 0;parent[0] = -1;  // 第一个顶点没有父节点// 构造最小生成树for (int count = 0; count < V - 1; count++) {// 从未包括在最小生成树中的顶点选取key值最小的顶点int u = minKey(key, mstSet);// 将选取的顶点u包含到最小生成树中mstSet[u] = 1;// 更新相邻顶点的key值for (int v = 0; v < V; v++) {// graph[u][v]是u和v之间的边的权值if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v]) {parent[v] = u;key[v] = graph[u][v];}}}// 打印最小生成树printMST(parent, graph);
}int main() {// 定义图的邻接矩阵，0表示没有边int graph[V][V] = {{0, 2, 0, 6, 0},{2, 0, 3, 8, 5},{0, 3, 0, 0, 7},{6, 8, 0, 0, 9},{0, 5, 7, 9, 0}};// 计算并打印最小生成树primMST(graph);return 0;
}

代码说明：

1. minKey函数：在未被包括在最小生成树中的顶点集合中，找到权值最小的顶点。
2. primMST函数：实现Prim算法。该函数通过维护两个数组key和mstSet，来选择每次未包括在生成树中的权值最小的顶点，最终构造最小生成树。
3. printMST函数：输出最小生成树的边和它们的权值。

复杂度分析：

• 时间复杂度：O(V²)，其中V是顶点的数量。由于每次需要遍历所有顶点来选择最小的边，因此对于稠密图，时间复杂度为平方级别。
• 空间复杂度：O(V)，需要额外的数组存储最小生成树信息、key值和mstSet。

第五题

5.定义三元组(x,y,z)(x、y、z均为正)的距离 D=|x-y|+|y-z|+|z-x|。给定3个 非空整数集合S1、S2和S3，按升序分别存储在3个数组中。请设计一个算法，计算 并输出所有可能的三元组(x,y,z)(xES1,yES2,zES3)中的最小距离。例如 S1={-1,0，9}，S2={-25，-10,10,11}，S3={2,9,17,30,41}，则最小距离为 2，相应 的三元组为(9,10,9)。给出算法的基本设计思想，并编程实现，要求算法在时间上 尽可能高效，给出算法的时间复杂度和空间复杂度(15分)。

算法设计思想：

给定三个有序数组 S1S1S1, S2S2S2, S3S3S3，目标是寻找最小的三元组距离。由于数组是有序的，我们可以利用双指针/三指针的方法来遍历这些数组，从中找到最小的三元组距离。

基本思想：

1. 初始化三个指针分别指向三个数组的第一个元素。
2. 计算当前指针对应的三元组距离。
3. 通过移动值最小的那个指针来尝试缩小三元组的距离，直到其中一个指针到达数组末尾。
4. 记录并更新最小距离和对应的三元组。

算法步骤：

1. 设指针 i, j, k 分别指向数组 S1, S2, S3 的第一个元素。
2. 计算当前三元组的距离 D = |S1[i] - S2[j]| + |S2[j] - S3[k]| + |S3[k] - S1[i]|。
3. 如果当前距离比最小距离小，则更新最小距离并记录三元组。
4. 通过移动当前最小元素的指针（即 S1[i], S2[j], S3[k] 中最小的那个）来尝试缩小距离。
5. 当其中一个指针达到数组末尾时，停止遍历。

C语言实现

#include <stdio.h>
#include <stdlib.h>
#include <math.h>  // 用于计算绝对值函数// 计算三元组的距离 D = |x - y| + |y - z| + |z - x|
int calculateDistance(int x, int y, int z) {return abs(x - y) + abs(y - z) + abs(z - x);
}// 查找最小的三元组距离
void findMinDistance(int S1[], int n1, int S2[], int n2, int S3[], int n3) {int i = 0, j = 0, k = 0;int minDistance = INT_MAX;int resultX = 0, resultY = 0, resultZ = 0;// 三指针遍历数组while (i < n1 && j < n2 && k < n3) {int x = S1[i], y = S2[j], z = S3[k];int currentDistance = calculateDistance(x, y, z);// 如果找到更小的距离，更新最小距离和对应的三元组if (currentDistance < minDistance) {minDistance = currentDistance;resultX = x;resultY = y;resultZ = z;}// 移动当前最小的指针，尝试缩小距离if (x <= y && x <= z) {i++;} else if (y <= x && y <= z) {j++;} else {k++;}}// 输出结果printf("最小距离为: %d\n", minDistance);printf("对应的三元组为: (%d, %d, %d)\n", resultX, resultY, resultZ);
}int main() {// 示例数据int S1[] = {-1, 0, 9};int S2[] = {-25, -10, 10, 11};int S3[] = {2, 9, 17, 30, 41};int n1 = sizeof(S1) / sizeof(S1[0]);int n2 = sizeof(S2) / sizeof(S2[0]);int n3 = sizeof(S3) / sizeof(S3[0]);// 查找最小三元组距离findMinDistance(S1, n1, S2, n2, S3, n3);return 0;
}

复杂度分析：

• 时间复杂度：O(n1 + n2 + n3)，其中 n1, n2, n3 分别是三个数组的长度。由于我们只需要遍历每个数组一次，因此时间复杂度是线性的。
• 空间复杂度：O(1)，只使用了常数个额外的变量来存储当前最小距离和三元组。

总结：

该算法通过使用三指针的方法，充分利用数组的有序性，使得每次迭代都能有效地缩小可能的距离范围，从而以线性时间复杂度找到最小距离的三元组。

1.设有一个三维数组 a[c1:d1,c2:d2,c3:d3]，其中 ci:di 是第i维的边界(即第维的索引从ci到di)，假设a[cl,c2,c3]的地址为a0，每个数据元素占L个存储单元。
(1)如果采用行优先存储方式，推导变量 a[i1,i2,i3]的地址。
(2)如果采用列优先存储方式，推导变量 a[i1,i2,i3]的地址。

题目分析：

设有一个三维数组 ( a[c1:d1, c2:d2, c3:d3] )，其中 ( c1:d1 ), ( c2:d2 ), ( c3:d3 ) 是每一维的边界，数组以行优先或列优先方式存储，且每个元素占 ( L ) 个存储单元。我们需要推导出数组元素 ( a[i1, i2, i3] ) 的地址。

给定信息：

• 数组维度：三维数组 ( a )
  • 第一维索引范围 ( c1 \leq i1 \leq d1 )
  • 第二维索引范围 ( c2 \leq i2 \leq d2 )
  • 第三维索引范围 ( c3 \leq i3 \leq d3 )
• 基本地址：数组 ( a[c1, c2, c3] ) 的基地址为 ( a0 )
• 每个元素占 ( L ) 个存储单元

为了推导 ( a[i1, i2, i3] ) 的地址，需要基于存储方式分别进行推导。

---

1. 行优先存储方式

在行优先存储中，最右边的维度（第三维）先排布，依次到第二维、第一维。即：

• 第三维的元素相邻存储
• 当第三维遍历完后，移动到下一列（第二维）
• 当第二维遍历完后，移动到下一行（第一维）

地址计算公式推导：

假设 ( c3 \leq i3 \leq d3 ) 对应的是第三维，( c2 \leq i2 \leq d2 ) 对应的是第二维，( c1 \leq i1 \leq d1 ) 对应的是第一维。

1. 第三维偏移量：

   i3 - c3

   该偏移量表示在第三维上的偏移位置。

2. 第二维偏移量：

   (i2 - c2) \times (d3 - c3 + 1)

   第二维上的偏移位置，即跨过整个第三维的元素数。

3. 第一维偏移量：

   (i1 - c1) \times (d2 - c2 + 1) \times (d3 - c3 + 1)

   第一维上的偏移位置，即跨过整个第二维和第三维的元素数。

综上，行优先存储时，变量 ( a[i1, i2, i3] ) 的地址 ( Addr(a[i1, i2, i3]) ) 为：

Addr(a[i1, i2, i3]) = a0 + [(i1 - c1) \times (d2 - c2 + 1) \times (d3 - c3 + 1) + (i2 - c2) \times (d3 - c3 + 1) + (i3 - c3)] \times L

---

2. 列优先存储方式

在列优先存储中，最左边的维度（第一维）先排布，依次到第二维、第三维。即：

• 第一维的元素相邻存储
• 当第一维遍历完后，移动到下一列（第二维）
• 当第二维遍历完后，移动到下一个块（第三维）

地址计算公式推导：

1. 第一维偏移量：

   i1 - c1

   表示在第一维上的偏移位置。

2. 第二维偏移量：

   (i2 - c2) \times (d1 - c1 + 1)

   表示跨过整个第一维的元素数。

3. 第三维偏移量：

   (i3 - c3) \times (d1 - c1 + 1) \times (d2 - c2 + 1)

   表示跨过整个第一维和第二维的元素数。

综上，列优先存储时，变量 ( a[i1, i2, i3] ) 的地址 ( Addr(a[i1, i2, i3]) ) 为：
[
Addr(a[i1, i2, i3]) = a0 + [(i3 - c3) \times (d1 - c1 + 1) \times (d2 - c2 + 1) + (i2 - c2) \times (d1 - c1 + 1) + (i1 - c1)] \times L
]

---

总结：

1. 行优先存储：

   Addr(a[i1, i2, i3]) = a0 + [(i1 - c1) \times (d2 - c2 + 1) \times (d3 - c3 + 1) + (i2 - c2) \times (d3 - c3 + 1) + (i3 - c3)] \times L

2. 列优先存储：
   Addr(a[i1, i2, i3]) = a0 + [(i3 - c3) \times (d1 - c1 + 1) \times (d2 - c2 + 1) + (i2 - c2) \times (d1 - c1 + 1) + (i1 - c1)] \times L

4.已知一组关键字的序列为{45,26,80,9,62,38,56),通过快速排序算法对该序列进 行升序排序，每次选取待排序列首位置为轴值，请列出每次划分之后轴值的索引(索 引从0开始)以及此次划分后的关键字序列

我们使用快速排序（Quick Sort）对给定的关键字序列 {45, 26, 80, 9, 62, 38, 56} 进行升序排序，并且每次选取待排序列首位置为轴值。接下来，我将列出每次划分之后的轴值索引以及此次划分后的关键字序列。

初始序列： {45, 26, 80, 9, 62, 38, 56}

1. 第一次划分：

   • 选择第一个元素 45 作为轴值。
   • 划分后序列为：{9, 26, 38, 45, 62, 80, 56}。
   • 轴值索引：3。

2. 第二次划分（左子序列：{9, 26, 38}）：

   • 选择第一个元素 9 作为轴值。
   • 划分后序列为：{9, 26, 38}。
   • 轴值索引：0（该子序列相对于原序列的全局索引为0）。

3. 第三次划分（右子序列：{26, 38}）：

   • 选择第一个元素 26 作为轴值。
   • 划分后序列为：{26, 38}。
   • 轴值索引：1。

4. 第四次划分（右子序列：{62, 80, 56}）：

   • 选择第一个元素 62 作为轴值。
   • 划分后序列为：{56, 62, 80}。
   • 轴值索引：5。

最终排序后的序列为：{9, 26, 38, 45, 56, 62, 80}。

划分过程中轴值索引及关键字序列：

1. 第一次划分：轴值索引 3，序列 {9, 26, 38, 45, 62, 80, 56}。
2. 第二次划分：轴值索引 0，序列 {9, 26, 38}。
3. 第三次划分：轴值索引 1，序列 {26, 38}。
4. 第四次划分：轴值索引 5，序列 {56, 62, 80}。

(1) 画出散列表的示意图

散列函数为 H(K) = K MOD 11，即关键字除以 11 的余数作为该关键字在散列表中的索引位置。使用拉链法处理冲突，因此每个槽位是一个链表。我们将关键字 {35, 67, 42, 21, 29, 86, 95, 47, 50, 36, 91} 依次插入到散列表中：

计算每个关键字的散列值：

• 35 MOD 11 = 2
• 67 MOD 11 = 1
• 42 MOD 11 = 9
• 21 MOD 11 = 10
• 29 MOD 11 = 7
• 86 MOD 11 = 9
• 95 MOD 11 = 7
• 47 MOD 11 = 3
• 50 MOD 11 = 6
• 36 MOD 11 = 3
• 91 MOD 11 = 3

按照散列值插入散列表并处理冲突：

索引  0: 空
索引  1: 67
索引  2: 35
索引  3: 91 → 36 → 47
索引  4: 空
索引  5: 空
索引  6: 50
索引  7: 95 → 29
索引  8: 空
索引  9: 86 → 42
索引 10: 21

(2) 计算查找成功时的平均查找长度

假设在散列表中的每个关键字被查找的概率相等，平均查找长度是每个槽位的链表长度的平均值。

散列表中每个链表的长度为：

• 索引 0: 0
• 索引 1: 1
• 索引 2: 1
• 索引 3: 3
• 索引 4: 0
• 索引 5: 0
• 索引 6: 1
• 索引 7: 2
• 索引 8: 0
• 索引 9: 2
• 索引 10: 1

平均查找长度的公式为：

平均查找长度=∑(链表长度×链表中每个关键字的查找长度)/总关键字数

在链表中的每个元素的查找长度为它在链表中的位置（从1开始计数）。计算每个链表中关键字的查找长度之和：

• 索引 1: 67 的查找长度 = 1
• 索引 2: 35 的查找长度 = 1
• 索引 3: 91 的查找长度 = 1，36 的查找长度 = 2，47 的查找长度 = 3，查找长度总和 = 1 + 2 + 3 = 6
• 索引 6: 50 的查找长度 = 1
• 索引 7: 95 的查找长度 = 1，29 的查找长度 = 2，查找长度总和 = 1 + 2 = 3
• 索引 9: 86 的查找长度 = 1，42 的查找长度 = 2，查找长度总和 = 1 + 2 = 3
• 索引 10: 21 的查找长度 = 1

查找长度总和 = 1 + 1 + 6 + 1 + 3 + 3 + 1 = 16

共有 11 个关键字，因此：
平均查找长度=∑(链表长度×链表中每个关键字的查找长度)/总关键字数

16/11 = 1.45

成功查找时的平均查找长度为 1.45。

程序片段：

x = 1
while x < n:x = x * 2

时间复杂度分析：

1. 初始化：x = 1 执行一次，时间为常数 ( O(1) )。

2. 循环条件：while x < n，每次检查时，x 会翻倍。也就是说，循环的迭代次数是 x 从 1 变为 n 的次数。因为 x 每次翻倍，循环次数可以表示为：
   [
   x = 2^k \quad \text{(第 k 次循环时)}
   ]
   当 ( x \geq n ) 时，循环终止。因此，我们有：
   [
   2^k \geq n
   ]
   取对数得：
   [
   k \geq \log_2 n
   ]
   因此，循环执行了大约 ( O(\log n) ) 次。

3. 每次循环的操作：在每次循环中，操作 x = x * 2 是常数时间操作 ( O(1) )。

综合分析，整个程序的时间复杂度为 ( O(\log n) )。

空间复杂度分析：

程序中只使用了两个变量：x 和 n。每个变量只占用常数空间，因此空间复杂度为 ( O(1) )。

总结：

• 时间复杂度：( O(\log n) )
• 空间复杂度：( O(1) )