php网站微信支付怎么做,信用网站建设的必要性,宁波网站建设服务报价,衡水教育行业网站建设1.已知带头结点单链表#xff0c;H为头指针。设计一个算法#xff0c;查找到链表的第m个结点(不包含头结点)#xff0c;并将元 素值为X的结点插入到该结点后#xff0c;形成一个新的链表。
// 定义单链表节点结构
typedef struct Node {int data;struct Node* next;
} Nod…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;
}代码说明
binarySearch函数这是一个非递归实现的折半查找函数。通过左右指针和中间索引来缩小搜索范围。每次比较中间值后根据大小调整左右指针直到找到目标值或范围结束。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;
}代码说明
Node结构体定义了二叉树的节点每个节点包含数据、左子节点和右子节点指针。createNode函数用于创建一个新的二叉树节点。countLeafNodes函数这是递归函数用来计算叶子节点个数。它通过判断节点是否为叶子节点即左右子节点都为空递归遍历左右子树统计所有叶子节点。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;
}代码说明 栈的基本操作 initStack初始化栈设置栈顶指针为-1。isEmpty判断栈是否为空。isFull判断栈是否已满。push将元素压入栈顶。pop从栈顶弹出元素并返回。 十进制到二进制的转换 利用栈来存储每次除以2的余数直到商为0。然后通过依次弹出栈中的元素来构建二进制数。
输入输出示例
输入
请输入一个十进制整数: 85输出
二进制序列: 1010101解释
十进制数85转换为二进制为1010101。栈的后进先出的特性帮助我们从最后一个余数到第一个余数依次输出二进制位。
复杂度分析
时间复杂度O(log n)因为每次除法操作将十进制数缩小一半。空间复杂度O(log n)栈最多会存储log n个二进制位。
第四题
4.设G(VE)是一个带权的无向连通网所有边的权均大于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;
}
代码说明
minKey函数在未被包括在最小生成树中的顶点集合中找到权值最小的顶点。primMST函数实现Prim算法。该函数通过维护两个数组key和mstSet来选择每次未包括在生成树中的权值最小的顶点最终构造最小生成树。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,09}S2{-25-10,10,11}S3{2,9,17,30,41}则最小距离为 2相应 的三元组为(9,10,9)。给出算法的基本设计思想并编程实现要求算法在时间上 尽可能高效给出算法的时间复杂度和空间复杂度(15分)。
算法设计思想
给定三个有序数组 S1S1S1, S2S2S2, S3S3S3目标是寻找最小的三元组距离。由于数组是有序的我们可以利用双指针/三指针的方法来遍历这些数组从中找到最小的三元组距离。
基本思想
初始化三个指针分别指向三个数组的第一个元素。计算当前指针对应的三元组距离。通过移动值最小的那个指针来尝试缩小三元组的距离直到其中一个指针到达数组末尾。记录并更新最小距离和对应的三元组。
算法步骤
设指针 i, j, k 分别指向数组 S1, S2, S3 的第一个元素。计算当前三元组的距离 D |S1[i] - S2[j]| |S2[j] - S3[k]| |S3[k] - S1[i]|。如果当前距离比最小距离小则更新最小距离并记录三元组。通过移动当前最小元素的指针即 S1[i], S2[j], S3[k] 中最小的那个来尝试缩小距离。当其中一个指针达到数组末尾时停止遍历。
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 ) 对应的是第一维。 第三维偏移量 i3 - c3 该偏移量表示在第三维上的偏移位置。 第二维偏移量 (i2 - c2) \times (d3 - c3 1) 第二维上的偏移位置即跨过整个第三维的元素数。 第一维偏移量 (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. 列优先存储方式
在列优先存储中最左边的维度第一维先排布依次到第二维、第三维。即
第一维的元素相邻存储当第一维遍历完后移动到下一列第二维当第二维遍历完后移动到下一个块第三维
地址计算公式推导 第一维偏移量 i1 - c1 表示在第一维上的偏移位置。 第二维偏移量 (i2 - c2) \times (d1 - c1 1) 表示跨过整个第一维的元素数。 第三维偏移量 (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 ] 总结 行优先存储 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 列优先存储 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} 第一次划分 选择第一个元素 45 作为轴值。划分后序列为{9, 26, 38, 45, 62, 80, 56}。轴值索引3。 第二次划分左子序列{9, 26, 38} 选择第一个元素 9 作为轴值。划分后序列为{9, 26, 38}。轴值索引0该子序列相对于原序列的全局索引为0。 第三次划分右子序列{26, 38} 选择第一个元素 26 作为轴值。划分后序列为{26, 38}。轴值索引1。 第四次划分右子序列{62, 80, 56} 选择第一个元素 62 作为轴值。划分后序列为{56, 62, 80}。轴值索引5。
最终排序后的序列为{9, 26, 38, 45, 56, 62, 80}。
划分过程中轴值索引及关键字序列
第一次划分轴值索引 3序列 {9, 26, 38, 45, 62, 80, 56}。第二次划分轴值索引 0序列 {9, 26, 38}。第三次划分轴值索引 1序列 {26, 38}。第四次划分轴值索引 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 267 MOD 11 142 MOD 11 921 MOD 11 1029 MOD 11 786 MOD 11 995 MOD 11 747 MOD 11 350 MOD 11 636 MOD 11 391 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 的查找长度 136 的查找长度 247 的查找长度 3查找长度总和 1 2 3 6索引 6: 50 的查找长度 1索引 7: 95 的查找长度 129 的查找长度 2查找长度总和 1 2 3索引 9: 86 的查找长度 142 的查找长度 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时间复杂度分析 初始化x 1 执行一次时间为常数 ( O(1) )。 循环条件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) ) 次。 每次循环的操作在每次循环中操作 x x * 2 是常数时间操作 ( O(1) )。
综合分析整个程序的时间复杂度为 ( O(\log n) )。
空间复杂度分析
程序中只使用了两个变量x 和 n。每个变量只占用常数空间因此空间复杂度为 ( O(1) )。
总结
时间复杂度( O(\log n) )空间复杂度( O(1) )
