2015年-2016年 软件工程程序设计题(算法题)实战_c语言程序设计&&数据结构程序设计分析
2015年
1.c语言程序设计部分
1.从一组数据中选择最大的和最小的输出。
void print_maxandmin(double a[],int length) //在一组数据中选择最大的或者最小的输出
{
double max=-10000000000; //初始化max是一个极小值
double min=100000000000; // 初始化min是一个极大值
for(int i=0;i<length;i++)
{
if(a[i]>max) max=a[i];
if(a[i]<max) min=a[i];
}
printf("最大值为：%lf\n",max);
printf("最小值为：%lf\n",min);
}
int main()
{
double a[]={22,55,34,2,5,9,11}; //假定一组数据由数组a存储
int length=sizeof(a)/sizeof(a[0]); //取得数组长度
print_maxandmin(a, length); //调用函数
}
运行结果：
本题积累复盘:
如何在未知数组长度的情况下，得到数组的长度
int length=sizeof(a)/sizeof(a[0]); //取得数组长度
2.从一组数据中计算出平均值并输出
double count_avarage(double a[],int length) //计算一组数据的平均值
{
double sum=0;
for(int i=0;i<length;i++)
{
sum+=a[i];
}
return sum/length;
}
int main()
{
double a[]={22,55,34,2,5,9,11}; //假定一组数据由数组a存储
int length=sizeof(a)/sizeof(a[0]); //取得数组长度
printf("平均值为：%lf\n",count_avarage(a, length));
}
3.一个超市有8名员工，每个员工的数据包括员工号、姓名、工资、职位。
请写出描述员工数据的结构体，并编写函数计算工资最高的员工号，工资最低的员工号，以及员工的平均工资，之后将大于平均工资的员工号和姓名输出。
结构体如下:
struct employee{
int ID; //员工号
char name[100]; //姓名
double wage; //工资
char degree[100]; //职位
};
代码如下:
void func_wage(struct employee a[],int length) //在一组数据中选择最大的或者最小的输出
{
double max=-10000000000; //初始化max是一个极小值
double min=10000000000; //初始化max是一个极小值
double sum=0;
double avarage=0;
int flagmax=0; //记录取得最高工资的员工号
int flagmin=0; //记录取得最高工资的员工号
for(int i=0;i<length;i++)
{
if(a[i].wage>max)
{
max=a[i].wage;
flagmax=a[i].ID;
}
if(a[i].wage<min)
{
min=a[i].wage;
flagmin=a[i].ID;
}
sum+=a[i].wage;
}
avarage=sum/length;
printf("工资最高的员工号:%d\n",flagmax);
printf("工资最低的员工号:%d\n",flagmin);
printf("平均工资为:%lf\n",avarage);
//工资大于平均工资的员工号和姓名输出
printf("工资大于平均工资的员工号和姓名如下:\n");
for(int i=0;i<length;i++)
{
if(a[i].wage>avarage)
{
printf("%d %s\n",a[i].ID,a[i].name);
}
}
}
int main()
{
struct employee a[8]={1,"小A",2000,"普通员工",2,"小B",3000,"普通员工",3,"小C",2200,"普通员工",4,"小D",3100,"普通员工"
,5,"小E",4000,"高级员工",6,"小F",4500,"高级员工",7,"小G",5000,"副组长",8,"小H",6000,"副组长"}; //定义一个含有8个员工的员工结构体数组
func_wage(a, 8);
}
2.数据结构程序设计部分
1.写出线性表的结构体，并基于线性表结构体快速排序第一趟排序
typedef int ElemType; //将int定义为元素数据类型
typedef struct Sqlist
{
ElemType *plist; //指向连续的顺序存储空间
int sqListLength; //顺序表元素个数
int sqListSize; //整个表的总存储空间数
}Sqlist;
//手写一个快速排序第一趟的过程
int partation(int a[],int low,int high)
{
while(low<high)
{
int pivot=a[low];
//先移动high指针
while(a[high]>=pivot&&low<high) //假如找不到呢，总得停止,low和high相遇的时候就停止(在没找到的情况下)
{
high--;
} //直到发现指向了一个小的数
a[low]=a[high];
a[high]=pivot;
pivot=a[high]; //交换
//再移动low指针
while(a[low]<=pivot&&low<high)
{
low++;
} //直到发现了一个大的数
a[high]=a[low];
a[low]=pivot;
pivot=a[low]; //交换
}
return low; //一趟已经排好了，需要再进行递归的操作完成接下来的趟，返回的其实就是中间那个轴，它左边的都比他小，右边的都比他大
}
void quicksort(int a[],int low,int high)
{
if(low<high) //在保证low<high的前提下递归
{
int piovt=partation(a, low, high); //每次找轴的过程中把数组都排好
quicksort(a, low, piovt-1);
quicksort(a, piovt+1, high);
}
}
int main()
{
int arr[5]={22,7,1,99,3};
Sqlist L;
L.plist=arr;
L.sqListLength=5;
printf("快速排序结束:\n");
quicksort(L.plist, 0, L.sqListLength-1);
for(int i=0;i<5;i++)
{
printf("%d ",L.plist[i]);
}
printf("\n");
}
- 写出二叉树的结构体，并基于二叉树查找指定结点的所有祖先结点
什么叫基于二叉树查找指定结点的所有祖先结点？
某一个结点的所有祖先节点，就是二叉树深搜遍历到的那条路径上，除了目标结点本身的其他结点。
祖先结点的定义是：一个结点在从根结点到目标结点的路径上，位于目标结点之上的结点。特别的因此，结点本身不能作为它的祖先结点。
该题本质就是在深搜的基础上进行一些操作。
写出二叉树的结构体
Typedef char ElemType;
Typedef struct BiTNode{
ElemType data;
struct BiTNode * lchild;
struct BiTNode * rchild;
}BiTNode,*BiTree;
输出所有的指定祖先结点的函数
bool find(BiTree T,ElemType s) //找s结点的全部祖先结点
{
if(T==NULL) return false;
if(T->data==s) return true;
if(find(T->lchild,s)||find(T->rchild,s))
{
printf("%c ",T->data);
return true;
}
return false;
}
2016年
1.c语言程序设计部分
1.给了一组年龄，求出最高年龄，最低年龄，平均年龄。
这道题没什么好说的，送分题
2.计算∑ (xi-8)4，其中i从1到n，n和xi由键盘输入
int main()
{
int n;
int sum=0; //答案保存在sum中
scanf("%d",&n);
while(n--)
{
int x=0;
scanf("%d",&x);
sum=sum+(x-8)*(x-8)*(x-8)*(x-8);
}
printf("%d\n",sum);
}
3.定义结构体，里面有英语，数学，软件工程，计算机网络四科成绩，有三个学生，计算每个学生总分和每科的平均分。
typedef struct Course{
int English_score;
int Math_score;
int software_score;
int com_net_score;
}Course;
typedef struct student
{
char name[100];
Course course;
int sum_score;
}student;
int main()
{
student stu[3]={"小李",100,68,22,44,0,"小刘",66,55,44,55,0,"小王",77,55,77,77,0};
//计算每个学生的总分并存储下来
for(int i=0;i<3;i++)
{
stu[i].sum_score=stu[i].course.English_score+stu[i].course.Math_score+stu[i].course.com_net_score+stu[i].course.software_score;
printf("%s的总分是：%d\n",stu[i].name,stu[i].sum_score);
}
//计算每科的平均分
double ava_English=0;
double ava_Math=0;
double ava_net=0;
double ava_software=0;
for(int i=0;i<3;i++)
{
ava_English+=stu[i].course.English_score;
ava_Math+=stu[i].course.Math_score;
ava_net+=stu[i].course.com_net_score;
ava_software+=stu[i].course.software_score;
}
ava_English/=3;ava_Math/=3; ava_net/=3;ava_software/=3;
printf("英语平均分为:%lf\n",ava_English);
printf("数学平均分为:%lf\n",ava_Math);
printf("计算机网络平均分为:%lf\n",ava_net);
printf("软件工程平均分为:%lf\n",ava_software);
}
2.数据结构程序设计部分
1.用拉链法处理冲突，写出散列表的创建函数，插入函数，查找函数。
（1）写出拉链法处理冲突时散列表的结构体
（2）写出创建函数，插入函数，查找函数的算法思想并编程。
写出写出拉链法处理冲突时散列表的结构体
首先回忆拉链的结构，是由多个单链表和一个头指针数组表示的，‘
所以，首先定义一个单链表结构体，再定义一个哈希表结构体，这个哈希表结构体中，含有指向指针数组的指针，哈希表的一些信息，如表长，关键字个数。
（1）拉链法处理冲突时散列表的结构体如下
typedef int ELemType;
typedef struct Node
{
ElemType data;
struct Node *next;
}Node;
typedef struct CLHashTable
{
Node ** PList;
int Table_length; //哈希表长度
int kum; //关键字个数
}CLHashTable;
初始化哈希表，思路，定义一个函数，向个函数中传入哈希表名的实参和哈希表长度。
从哈希表的构成三元素考虑，初始化问题。
首先就是为指针数组分配空间，将哈希表传入的长度=哈希表长度，循环遍历每一个指针数组中的头指针，将指针置空，关键字设置为0
void creat_Hash(CLHashTable &CHT,int Hashlength)
{
CHT.PList=(struct Node ** )malloc(sizeof(struct Node *)*Hashlength);
CHT.Table_length=Hashlength;
for(int i=0;i<Hashlength;i++)
{
CHT.PList[i]->next=NULL;
}
CHT.kum=0;
}
链地址法哈希表的插入函数，本质上就是单链表的插入，首先通过Hash函数确定在指针数组中选定哪一个头指针作为待插入的点，注意，此时分情况讨论，如果当前头指针指向空，就直接插入，如果不为空，定义一个pre指针，尾插法将新结点插入，注意传入哈希表的参数为，哈希表，插入的key值，和divisor(Hash函数中的除数)
void insert(CLHashTable &CHT,int key,int divisor)
{
int index=key/divisor;
Node *cur=CHT.PList[index];
Node *pre=NULL;
if(cur==NULL)
{
Node *p=(struct Node *)malloc(sizeof(Node));
p->data=key;
p->next=NULL;
cur->next=p;
}else
{
while(cur!=NULL)
{
pre=cur;
cur=cur->next;
}
Node *p=(struct Node *)malloc(sizeof(Node));
p->data=key;
p->next=pre->next;
pre->next=p;
}
}
哈希表的查找，跟插入很类似
int find_Hashkey(CLHashTable CHT,int key,int divisor)
{
int index=key/divisor;
Node * cur=CHT.PList[index];
if(cur==NULL) return 0; //查找失败
while(cur!=NULL)
{
if(cur->data==key) return 1; //查找成功
cur=cur->next;
}
return 0; //查找失败
}
2.存在一个二叉排序树，给定一个value值，若查找value值，就返回比value值大的所有值中最小的值。若value最大就返回空。
本质就是二叉排序树的搜索，搜索一遍，记录值，由于二叉排序树，保持着左子树小，右子树大的性质，返回比value值大的所有值中最小的值，也就是搜到第一个比value值大的数，若搜索完整个二叉排序树之后还没搜到，就返回空
回顾知识：
二叉排序树的结构体和树的结构体是一样的
二叉排序树的构造是通过递归构造
二叉树排序的遍历跟正常二叉树没有区别
(1)写出二叉树排序树的结构体
typedef int Elemtype;
typedef struct BiTNode
{
Elemtype data;
struct BiTNode *lchild;
struct BiTNode *rchild;
}BiTNode,*BiTree;
(2)说出上述算法思想并编程
给出错误思路:
这个错误思路就是，不去递归，就大于就右子树，小于就左子树，这个不能找到比它大的最小的值，只能找到一个比它大的值
int max_value_min(BiTree T,ElemType value)
{
BiTNode *p=T;
while(p!=NULL)
{
if(p->data<=value)
{
p=p->rchild;
}else if(p->data>value)
{
return p->data;
}
}
return 0; //返回0表明，没有值比它大
}
正确答案：
代码刨析:
这个模版本质就是二叉排序树的中序遍历模版，因为二叉排序树的中序遍历是有序的。
首先明确，最后返回的值，是递归开始那里返回的值，开始递归，层层深入，再逐层返回。
if-else，那里是停止二叉树的继续遍历，如果找到了就停止二叉树的遍历，flag值已经被修改就逐层将flag值传递回去。假如都搜完也没有，还是逐层将flag值传递回去，但是此时flag没有被修改过为0
值得注意的是最后的return flag不能改成return 0，如果return 0了，就没有意义了，只是flag作为全局变量已经被保存下来了，与题目中要求有瑕疵。
if(T==NULL) return 0;这个0其实就是说T是空树，没有什么实际意思，最后怎么返回还都是flag
int flag=0; //标记第一次大于value,为0就是没有这个值，为其他的就是要返回的值
int max_value_min(BiTree T,ElemType value)
{
if(T==NULL) return 0;
max_value_min(T->lchild, value);
if(T->data>value&&flag==0)
{
flag=T->data;
return flag;
}else
{
max_value_min(T->rchild, value);
}
return flag;
}
原文地址：https://blog.csdn.net/weixin_62613321/article/details/142714741
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！