3. (10分) 编程实现一个数组插入算法（源文件命名insert.c），要求在数组a[]的所有奇数下标里插入某个数x。函数定义如下：
int insert_odd (int a[], int n, int x) {
// n是数组的实际长度，在所有<=n的奇数下标a[1], a[3], …里插入x
// 设a[]的最大长度足够大
// 返回数组的新长度
}
#include
int insert_odd(int a[], int n, int x) { // 检查边界条件和错误情况 if (n <= 0) { printf("错误：数组长度必须是正整数。\n"); return -1; // 返回-1表示错误 } // 计算新数组的长度 int new_n = n+n/2; // 移动奇数下标的元素以腾出空间 int j = new_n-1; for(int i = n-1;i>=0;i--){ if(i%2!=0){ a[j] = a[i]; // 插入新元素x到奇数下标位置 a[j-1] = x; j -= 2; } else { a[j] = a[i]; j--; } } // 返回新数组的长度 return new_n; } int main() { // 测试样例 int a[99] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21}; int n = 11; // 数组长度 int x = 99; // 要插入的数 printf("原始数组："); for (int i = 0; i < n; i++) { printf("%d", a[i]); } printf("\n"); int new_n = insert_odd(a, n, x); if (new_n != -1) { printf("插入后的数组："); for (int i = 0; i < new_n; i++) { printf("%d", a[i]); } printf("\n"); } return 0; } 4. (10分) 编程实现一个数组的删除算法（源文件命名delete_array.c），要求删除数组a[]的所有x。函数定义如下：
int delete_all (int a[], int n, int x) {
// n是数组的实际长度
// 返回数组的新长度
}
#include int delete_all (int a[], int n, int x) { int k=0; for(int i=0;i5. (10分) 编程实现有重复元素的二分查找，并找到所有目标元素的位置（源文件命名bsearch_duplicate.c），函数定义如下。并给出算法的平均时间复杂度（要写出分析过程）。void bsearch_dup (int a[], int n, int x, int res[]) {
// 在a[]的前n个元素中寻找x，返回x的最早位置和最晚位置，存在res[]里
// 因此，res[]是个只有两个元素的数组。若x不存在，令res=[-1, -1]
// a已经排好序，但可能有重复元素
}
#include void bsearch_dup(int a[], int n, int x, int res[]) { int first_occurrence = -1; // 初始值表示未找到 int last_occurrence = -1; // 初始值表示未找到 int left = 0; int right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; if (a[mid] == x) { // 找到x后，更新first_occurrence和last_occurrence first_occurrence = mid; last_occurrence = mid; // 继续在左半部分查找更早的位置 int left_index = mid - 1; while (left_index >= 0 && a[left_index] == x) { first_occurrence = left_index; left_index--; } // 继续在右半部分查找更晚的位置 int right_index = mid + 1; while (right_index < n && a[right_index] == x) { last_occurrence = right_index; right_index++; } break; // 因为a已排序，不必继续查找 } else if (a[mid] < x) { left = mid + 1; } else { right = mid - 1; } } res[0] = first_occurrence; res[1] = last_occurrence; } int main() { int a[] = {1, 2, 2, 3, 3, 3, 4, 5, 5, 6}; int n = sizeof(a) / sizeof(a[0]); int x = 3; int res[2] = {-1, -1}; bsearch_dup(a, n, x, res); if (res[0] != -1 && res[1] != -1) { printf("元素 %d 的最早位置：%d\n", x, res[0]); printf("元素 %d 的最晚位置：%d\n", x, res[1]); } else { printf("元素 %d 不存在。\n", x); } return 0; } 6. (10分) 编程实现（带头结点）链表的一个删除算法，要求删除所有等于x的结点（源文件命名delete_linkedlist.c），函数定义如下：
typedef struct Node {
int data;
struct Node* next;
} Node;
int delete_all (Node** head, int x){
// head是无用的头结点，删除所有等于x的结点
// 返回删除的结点数目
}
#include#include typedef struct Node { int data; struct Node* next; } Node; int delete_all(Node** head, int x) { int deleted_count = 0; // 处理头结点之后的结点 Node* current = *head; while (current->next != NULL) { // 检查下一个结点的数据是否等于x if (current->next->data == x) { Node* temp = current->next; // 保存要删除的结点 current->next = current->next->next; // 删除结点 free(temp); // 释放内存 deleted_count++; } else { current = current->next; // 没有删除结点，继续遍历 } } return deleted_count; } // 打印链表 void print_list(Node* head) { Node* current = head->next; while (current != NULL) { printf("%d ->", current->data); current = current->next; } printf("NULL\n"); } // 创建新结点 Node* create_node(int data) { Node* new_node = (Node*)malloc(sizeof(Node)); if (new_node != NULL) { new_node->data = data; new_node->next = NULL; } return new_node; } int main() { // 创建带头结点的链表 Node* head = create_node(-1); // 头结点 Node* node1 = create_node(1); Node* node2 = create_node(2); Node* node3 = create_node(2); Node* node4 = create_node(3); // 连接结点 head->next = node1; node1->next = node2; node2->next = node3; node3->next = node4; printf("原始链表：\n"); print_list(head); int x = 2; int deleted_count = delete_all(&head, x); if (deleted_count > 0) { printf("删除所有等于 %d 的结点后的链表：\n", x); print_list(head); printf("删除的结点数目：%d\n", deleted_count); } else { printf("没有找到等于 %d 的结点。\n", x); } // 释放链表内存 Node* current = head; while (current != NULL) { Node* temp = current; current = current->next; free(temp); } return 0; } 7. (10分) 编程实现（不带头结点）链表反转的递归算法（源文件命名linkedlist_reverse.c），函数定义如下。并给出算法的时间复杂度（要写出分析过程）
Node** reverse (Node** head){
// 返回新的头结点
}
#include#include typedef struct Node { int data; struct Node* next; } Node; // 反转链表 Node* reverse(Node* head) { if (head == NULL || head->next == NULL) { return head; // 如果链表为空或只有一个结点，直接返回 } Node* new_head = reverse(head->next); // 递归反转剩余部分 // 将当前结点的下一个结点的指针指向当前结点，反转链接 head->next->next = head; head->next = NULL; return new_head; // 返回新的头结点 } // 打印链表 void print_list(Node* head) { Node* current = head; while (current != NULL) { printf("%d ->", current->data); current = current->next; } printf("NULL\n"); } // 创建新结点 Node* create_node(int data) { Node* new_node = (Node*)malloc(sizeof(Node)); if (new_node != NULL) { new_node->data = data; new_node->next = NULL; } return new_node; } int main() { // 创建链表 Node* node1 = create_node(1); Node* node2 = create_node(2); Node* node3 = create_node(3); Node* node4 = create_node(4); // 连接结点 node1->next = node2; node2->next = node3; node3->next = node4; printf("原始链表：\n"); print_list(node1); Node* new_head = reverse(node1); printf("反转后的链表：\n"); print_list(new_head); // 释放链表内存 Node* current = new_head; while (current != NULL) { Node* temp = current; current = current->next; free(temp); } return 0; } 
