当前位置： 首页 > article >正文

2015年-2016年 软件工程程序设计题(算法题)实战_c语言程序设计数据结构程序设计分析

article 2025/1/29 13:48:30

文章目录

  • 2015年
    • 1.c语言程序设计部分
    • 2.数据结构程序设计部分
  • 2016年
    • 1.c语言程序设计部分
    • 2.数据结构程序设计部分

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");
}
  1. 写出二叉树的结构体，并基于二叉树查找指定结点的所有祖先结点

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

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

写出二叉树的结构体

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

http://www.kler.cn/a/349881.html

相关文章：

  • Myeclipse最新版本 C1 2019.4.0
  • 【深度之眼cs231n第七期】笔记（三十一）
  • Python3 【函数】水平考试：精选试题和答案
  • Kafka运维宝典 （三）- Kafka 最大连接数超出限制问题、连接超时问题、消费者消费时间超过限制问题详细介绍
  • 03：Heap代码的分析
  • 第4章 神经网络【1】——损失函数
  • Spring Security自定义登录接口处理JSON请求体
  • 开源OpenStack
  • 施磊C++ | 进阶学习笔记 | 5.设计模式
  • H3Linux部署iMC智能管理中心平台PLAT-7.3_E0706实验
  • 基于java SpringBoot和Vue校园食堂网站管理系统设计
  • 51 | 适配器模式：代理、适配器、桥接、装饰，这四个模式有何区别？
  • 【数据结构】之学习路线
  • 【Sceneform-EQR】（手势优化）通过手势事件实现在AR/VR等三维场景中的控制模型旋转、平移与缩放
  • linux_find命令
  • SQL分类中的DCL
  • [LeetCode 题1] 两数之和
  • uni-app中添加自定义相机（微信小程序+app）
  • 三、账号密码存储
  • 企业资产安全之数据防泄密要领
  • 农作物柑橘病虫害识别数据集
  • 双十一数码好物怎么入手最划算？这五款数码好物闭眼入也不踩雷
  • 炸锅了！大语言模型直言能替代 20 种人类工作，你需不需要转行？速看！
  • 数制转换及交换机
  • 数据结构-顺序栈
  • 使用Illustrator软件打印，如何取消上面打印？