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");
}

2. 写出二叉树的结构体，并基于二叉树查找指定结点的所有祖先结点

什么叫基于二叉树查找指定结点的所有祖先结点？
某一个结点的所有祖先节点，就是二叉树深搜遍历到的那条路径上，除了目标结点本身的其他结点。
祖先结点的定义是：一个结点在从根结点到目标结点的路径上，位于目标结点之上的结点。特别的因此，结点本身不能作为它的祖先结点。

该题本质就是在深搜的基础上进行一些操作。

写出二叉树的结构体

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.计算∑ (x_i-8)⁴，其中i从1到n，n和x_i由键盘输入

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;}