数据结构[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
原文地址：https://blog.csdn.net/mufengzhiyu666/article/details/143506142
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！