编程题ll

编程题

6-1 删除顺序表中的偶数

本题要求实现一个函数,可删除顺序表中的偶数元素。

函数接口定义:

void Del_even(SqList *L);

答案:

void Del_even(SqList *L)
{
    //SqListDelete ( SqList *L, int pos, DataType *item ) 
    DataType k; 
    for(int i=0;i<=L->length;i++)
    {
        if(L->items[i]%2==0)
        {
            SqListDelete (L,i+1,&k);
            i=i-1;
        }
    }
}

舞伴问题

假设男士和女士的记录存放在一个数组中,设计算法实现舞伴配对,要求输出配对的舞伴,并输出没有配对的队头元素的姓名。

函数接口定义:

void DancePartner(DataType dancer[], int num) ;

答案:

void DancePartner(DataType dancer[], int num)
{
    int i,j,k;
    for(i = 0;i < num/2;i++) // 次数
    {
        for(j = 0;j < num;)
        {
            if(dancer[j].sex=='F')
              break;
            else j++; // 找女士
        }
         for(k = 0;k < num;)
        {
            if(dancer[k].sex=='M')
               break;
            else k++;   // 找男士
        }
        if(dancer[j].sex=='F'&&dancer[k].sex=='M')  // 如果找到一男一女
        {
            printf("%s %s\n",dancer[j].name,dancer[k].name);
            dancer[j].sex='A';  // 更换性别做标记
            dancer[k].sex='A';
        }
    }
    printf("\n");
     for(j = 0;j < num;j++)
        {
            if(dancer[j].sex!='A')
               {
                    printf("%s\n",dancer[j].name);  //输出没有配对的头元素
                    break;
               }
        }       
}

判断回文

回文是指正读反读均相同的字符序列,如“abba”和“abdba”均是回文,但“good”不是回文。试写一个程序判定给定的字符向量是否为回文,用栈实现。(提示:将一半字符入栈)

输入格式:

输入任意字符串。

输出格式:

若字符串是回文,输出:xxxx是回文。
若字符串不是回文,输出:xxxx不是回文。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Maxsize 1024
typedef struct{
    int data[Maxsize];
    int top;
}Sq;
//初始化栈
void Init(Sq* stack){
    stack->top=-1;
}
//判断是否为空
int Empty(Sq* stack){
    if(stack->top==-1){
        return 1;
    }else{
        return 0;
    }
}
//入栈
void Push(Sq* stack,char val){
    if(stack->top==Maxsize-1){
        return;
    }
    stack->top++;
    stack->data[stack->top]=val;
}
//出栈
char Pop(Sq* stack){
    if(Empty(stack)==0){
        return stack->data[stack->top--];
    }
 
}
int main(){
    int i,j=0,len=0,flag=0;
    char s[81],temp;
    Sq stack;
    Init(&stack);
    gets(s);
    len= strlen(s);
    //将字符串s入栈
    for(i=0;i<len;i++){
        Push(&stack,s[i]);
    }
    
    while(s[j]!='\0'){
        //使用temp来接收出栈的内容
        temp= Pop(&stack);
        //如果s[j++]正序输出  和  出栈内容相同,则为回文
        if(s[j]==temp){
            flag=1;
        }else{
            flag=0;
            break;
        }
        j++;
    }
    if(flag==1){
        printf("%s是回文。",s);
    }else{
        printf("%s不是回文。",s);
    }
 
    return 0;
}
 

1.二叉树度为2的结点求和

实现一个函数,返回二叉树bt中度为2的结点的数值之和。

函数接口定义:

int sumDCNodes(struct BinTree *bt);

答案:

int sumDCNodes(struct BinTree *bt)
{
    if(bt)
    {
        if(bt->left && bt->right)
        {
            return bt->data + sumDCNodes(bt->left) + sumDCNodes(bt->right);
        }
        return sumDCNodes(bt->left) + sumDCNodes(bt->right);
    }
    return 0;
}

2.计算二叉树的叶子数

本题是计算二叉树中叶子结点的个数。

函数接口定义:

在这里描述函数接口。例如:
int num (Bptr p);

答案:

int num (Bptr p)
 
{
    if(p==NULL)
    {return 0;}
    if(p->Lson==NULL&&p->Rson==NULL)
           return 1;
    
    return num(p->Lson)+num(p->Rson);
}

3.二叉树的递归遍历

要求使用递归算法实现二叉树的先序遍历、中序遍历和后序遍历。

函数接口定义:

void PreorderTraversal(BinTree BT)   /* 二叉树的先序遍历 */ 
void InorderTraversal(BinTree BT)   /* 二叉树的中序遍历 */ 
void PostorderTraversal(BinTree BT)    /* 二叉树的后序遍历 */

答案:

void PreorderTraversal(BinTree BT)   /* 二叉树的先序遍历 */ 
{
    if(BT)
    {
         printf("%c",BT->Data);
         PreorderTraversal(BT->Left);
         PreorderTraversal(BT->Right);
    }
    
}
void InorderTraversal(BinTree BT)   /* 二叉树的中序遍历 */ 
{
     if(BT)
     {
        InorderTraversal(BT->Left);
        printf("%c",BT->Data);
        InorderTraversal(BT->Right);
     }
}
void PostorderTraversal(BinTree BT)    /* 二叉树的后序遍历 */
{

    if(BT)
    {
     PostorderTraversal(BT->Left);
     PostorderTraversal(BT->Right);
     printf("%c",BT->Data);
    }
    
    
}

4.求二叉树高度

本题要求给定二叉树的高度。

函数接口定义:

int GetHeight( BinTree BT );

答案:

/*递归法求二叉树的高度*/
int GetHeight(BinTree BT)
{
    int h1,h2;
    if(BT==NULL)
        return 0;
    else
    {
        h1=GetHeight(BT->Left);
        h2=GetHeight(BT->Right);
        if(h1>h2)
            return h1+1;
         else
            return h2+1;
    }
}

1. 叶结点求和

对给定的有N个节点(N>=0)的二叉树,求叶节点元素之和。

输入格式:

第一行是一个非负整数N,表示有N个节点

第二行是一个整数k,是树根的元素值

接下来有N-1行,每行是一个新节点,格式为 r d e 三个整数,

r表示该节点的父节点元素值(保证父节点存在);d是方向,0表示该节点为父节点的左儿子,1表示右儿子;e是该节点的元素值。

#include<stdio.h>
typedef struct Lnode
{
    int r;
    int d;
    int e;
}Tree,*Treenode;
int main()
{
    int flag=1; // 标记是否能在r中找到
    int i,t,j;
    int n,E,sum=0;
    scanf("%d",&n);
    scanf("%d",&E);
    if(n==0)
    {printf("%d",0);return 0;} // 空树
    if(n==1)
    {printf("%d",E);return 0;} // 仅含有根节点
    t=n-1;
    Tree T[t];
    for(i=0;i<t;i++)
        scanf("%d %d %d",&T[i].r,&T[i].d,&T[i].e);
    for(i=0;i<t;i++)
    {
        flag=1;
        for(j=0;j<t;j++)
            if(T[i].e==T[j].r)
                flag=0;
        if(flag)
        sum+=T[i].e;
    }
    printf("%d",sum);
}

1.最小生成树(普里姆算法)

试实现普里姆最小生成树算法。

函数接口定义:

void Prim(AMGraph G, char u);

答案:

void Prim( AMGraph G, char v )
    { 
        int distance[G.vexnum];
        int parent[G.vexnum];
        //记录v的下标
        int index=0;
        int i,min=MaxInt,imin,count=0;
        // 1.初始化这棵树,即以v为起始点,同时初始化数组distance[]
        //     注:distance数组表示该树的任意一点到该点的最小距离

        //寻找v的下标
        for (i = 0; i < G.vexnum; i++)
        {
            if (G.vexs[i]==v)
            {
                index=i;
            }
            
        }
        for (i = 0; i < G.vexnum; i++)
        {
            if (i==index)
            {
                distance[i]=0;
                parent[i]=index;
            }else
            {
                distance[i]=G.arcs[index][i];
                parent[i]=index;
            }       
        }
        while (1)
        {
            if (count==G.vexnum-1)
            {
                break;
            }
            
            // 2.从小树现有的结点出发,寻找边权值最小的点:
            for ( i = 0; i < G.vexnum; i++){
                if (min>distance[i]&&distance[i]!=0)
                {
                    //记录最小值及其下标
                    min=distance[i];
                    imin=i;
                    
                }
                
            }
            //更新已到达过得节点数
			
            count++;
            // 3.找到后输出该边
            if (count<G.vexnum-1)
            {
                printf("%c->%c\n",G.vexs[parent[imin]],G.vexs[imin]);
            }else
            {
                printf("%c->%c",G.vexs[parent[imin]],G.vexs[imin]);
            }
            
            
            
            
            //初始化min以便下次寻找
            min=MaxInt;
            // 4.将该点的distance数组中的值赋值为0,标记已经遍历过
            distance[imin]=0;
            // 5.循环遍历结点,更新distance[]数组
            for ( i = 0; i < G.vexnum; i++){
                if (distance[i]!=0&&G.arcs[i][imin]<MaxInt)
                {
                    if (distance[i]>G.arcs[i][imin])
                    {
                        distance[i]=G.arcs[i][imin];
                        parent[i]=imin;
                    }                   
                }
            }            
        }
    }

2.统计无向图中各顶点的度

本题要求实现一个函数,统计无向图中各顶点的度。

函数接口定义:

void degree(MGraph Graph,int *num);

答案:

void degree(MGraph Graph,int *num)
{
    int i,j;
    for(i = 0;i < Graph->Nv; i++)
    {
        for(j = 0;j < Graph->Nv; j++)
        {
            if(Graph->G[i][j]!=INFINITY)
                num[i]++;
        }
    }
}

3.基于邻接矩阵表示的广度优先遍历

实现基于邻接矩阵表示的广度优先遍历。

函数接口定义:

void BFS(Graph G, int v);

答案:

void BFS(Graph G, int v) {
    int queue[MVNum];//定义int类型队列
    int front = 0, rear = 0;//首尾初始化
    int flag;//表示队首的顶点坐标
 
    printf("%c ", G.vexs[v]);//打印访问
    visited[v] = 1;
    rear = (rear + 1) % MVNum;//%MVNum防止队列溢出
    queue[rear] = v;//将此节点放入队尾
 
    while (front != rear) {//如果队列不为空
        front = (front + 1) % MVNum;//%MVNum防止队列溢出
        flag = queue[front];//flag接住队首元素的位置
        for (int i = 0; i < G.vexnum; i++) {
            if (G.arcs[flag][i] != 0 && !visited[i]) //两点直接存在边,节点还没遍历
            {
                printf("%c ", G.vexs[i]);//访问打印
                visited[i] = 1;//状态变更为遍历过
                rear = (rear + 1) % MVNum;//队尾后移
                queue[rear] = i;//将其加入队列
            }
        }
    }
}

4.实现基于邻接矩阵表示的深度优先遍历

实现基于邻接矩阵表示的深度优先遍历。

函数接口定义:

void DFS(Graph G, int v);

答案:

void DFS(Graph G, int v)
{
    int i;
    visited[v]=1;
    printf("%c ",G.vexs[v]);
    for(i=0;i<G.vexnum;i++)
        if(!visited[i]&&G.arcs[v][i])
            DFS(G,i);
}

5.最小生成树(克鲁斯卡尔算法)

试实现克鲁斯卡尔最小生成树算法。

函数接口定义:

void Kruskal(AMGraph G);

答案:

/*

void Kruskal(AMGraph G){
       
     printf("0->5\n2->3\n1->6\n1->2\n3->4\n4->5\n");   
}

*/

void Kruskal(AMGraph G){
    /*由于kruskal算法的特点 我们需要放置树成环,所以需要辅助数组*/
    int assists[G.vexnum];
    /*对辅助数组赋值不同的值*/
    for(int i=0;i<G.vexnum;++i){
        assists[i]=i;
    }
    //初始化边结构体
   int temp=0;
    for(int i = 0;i<G.vexnum;++i){
        for(int j=0;j<G.vexnum;++j){
            if(G.arcs[i][j]!=MaxInt&&j>i){
                Edge[temp].Head = G.vexs[i];
                Edge[temp].Tail = G.vexs[j];
                Edge[temp].lowcost = G.arcs[i][j];
                temp++;
            }
        }
    }
    //对结构体进行排序 对每个边进行排序 所以i的条件必须是与边的关系
    for(int i=0;i<G.arcnum-1;++i){
        for(int j=i+1;j<G.arcnum;++j){
            if(Edge[j].lowcost<Edge[i].lowcost){
                 Evode temp2 = Edge[i];
                 Edge[i] =Edge[j];
                 Edge[j] = temp2;
            }
        }
    }
    //printf("0->5\n2->3\n1->6\n1->2\n3->4\n4->5");
    for(int i=0;i<G.arcnum;++i){
        /*获取头顶点与尾顶点在图中的位置*/
        int v1 = LocateVex(G,Edge[i].Head);
        int v2 = LocateVex(G,Edge[i].Tail);
        /*获取对应位置在辅助数组中的元素*/
        int vs1 = assists[v1];
        int vs2 = assists[v2];
 
        /*判断是否成环  如果当前插入的边对应的两个顶点不同那么就不会成环*/
        /*如果相等了那么这两个顶点肯定是把之前的树构成了一个环*/
        if(vs1!=vs2){
            /*满足的打印出来*/
            printf("%c->%c\n",Edge[i].Head,Edge[i].Tail);
 
            /*如果满足, 把头顶点在辅助数组中对应的值赋值给尾结点 代表连接成功*/
            for(int j=0;j<G.vexnum;++j){
                if(assists[j]==vs2){
                    assists[j]=vs1;
                }
            }
        }
    }
}

1.数据结构考题 - 顺序查找

建立一个顺序表,用顺序查找的方法对其实施查找。

顺序表的类型描述:

#define MAXSIZE 50
typedef int ElemType;
typedef  struct
{ 
  ElemType  *R; 
  int  length;
} SSTable;    

函数接口定义:

下面给出了 顺序查找 函数的大部分内容,但缺少了一部分(以下划线____标识出来的部分)。

请先将以下代码中画横线的部分补充完整,然后将完整的函数Search_Seq提交系统,完成题目要求的功能。

int  Search_Seq (SSTable  T,ElemType  k)
{   int i;
    T.R[0]= ____ ;
    for ( i=____ ; T.R[ ____ ]!= k ; ____ );
    return ____ ;
}

答案:

int  Search_Seq(SSTable  T, ElemType  k)
{
	int i;
	T.R[0] = k;
	for (i = T.length; T.R[i] != k; --i);
	return i;
}

2.数据结构考题 - 折半查找

建立一个递增的有序表(用顺序表作存储结构),用折半查找的方法对其实施查找。

顺序表的类型描述:

#define MAXSIZE 50
typedef int ElemType;
typedef  struct
{
  ElemType  *R; 
  int  length;
} SSTable;  

函数接口定义:

下面给出了 折半查找 函数的大部分内容,但缺少了一部分(以下划线____标识出来的部分)。

请先将以下代码中画横线的部分补充完整,然后将完整的函数Search_Bin提交系统,完成题目要求的功能。

int  Search_Bin(SSTable T, ElemType k)
{  
    int low,high,mid;
    low=1;
    high=T.length;
    while ( ____ )
    {  
        mid=____ ;
        if ( ____)  
            return  mid;
        else  if (k< T.R[mid])   
            high=____;
        else   
            low=____;
   }
   return 0 ;
}

答案:

int  Search_Bin(SSTable T, ElemType k)
{  
    int low,high,mid;
    low=1;
    high=T.length;
    while ( low<=high )
    {  
        mid = (low+high)/2;;
        if ( T.R[mid] == k)  
            return  mid;
        else  if (k< T.R[mid])   
            high=mid-1;
        else   
            low=mid+1;
   }
   return 0 ;
}

6-1 折半插入排序

实现折半插入排序。

函数接口定义:

void BInsertSort(SqList &L);

答案:

void BInsertSort(SqList& L)//插入排序
{
	for (int i = 1; i < L.length + 1; i++)
	{
		L.r[0].key = L.r[i].key;
		for (int j = i; j > 1; j--)
		{
			if (L.r[j].key < L.r[j - 1].key)
			{
				L.r[j].key = L.r[j - 1].key;
				L.r[j - 1].key = L.r[0].key;
			}
		}
	}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/601958.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Oracle-一次TX行锁堵塞事件

问题背景&#xff1a; 接用户问题报障&#xff0c;应用服务出现大量会话堆积现象&#xff0c;数据库锁堵塞严重&#xff0c;需要协助进行问题定位和排除。 问题分析&#xff1a; 登录到数据库服务器上&#xff0c;首先查看一下数据库当前的等待事件情况&#xff0c;通过gv$ses…

大学物理实验 期末复习笔记整理(个人复习笔记/侵删/有不足之处欢迎斧正)

一、误差和数据处理 1. 系统误差是指在重复性条件下&#xff0c;对同一被测量进行无限多次测量所得结果的平均值与被测量的真值之差。它通常是由于测量设备、测量方法或测量环境等因素引起的&#xff0c;具有重复性、单向性和可测性。而随机误差则是由于测量过程中一系列有关因…

WRT1900ACS搭建openwrt服务器小记

参考链接 wrt1900acs openwrt wrt1900acs openwrt 刷机 wrt1900acs原生固件刷openwrt-23.05.3-mvebu-cortexa9-linksys_wrt1900acs-squashfs-factory.img wrt1900acs openwrt更新刷openwrt-23.05.3-mvebu-cortexa9-linksys_wrt1900acs-squashfs-sysupgrade.bin 通过WEB UI来…

醛固酮(Aldosterone)/Aldosterone ELISA kit--比色竞争法酶免疫检测试剂盒

醛固酮&#xff08;Aldosterone&#xff09;是一种由肾上腺皮质中的胆固醇合成的类固醇激素。醛固酮在肾脏和肝脏中代谢&#xff0c;并作为控制钠钾平衡的关键盐皮质激素发挥作用。肾上腺合成和释放醛固酮主要受肾素-血管紧张素-醛固酮系统&#xff08;RAAS&#xff09;的调节&…

call, apply , bind 区别详解 及 实现购物车业务开发实例

call 方法&#xff1a; 原理 call 方法允许一个对象借用另一个对象的方法。通过 call&#xff0c;你可以指定某个函数运行时 this 指向的上下文。本质上&#xff0c;call 改变了函数运行时的作用域&#xff0c;它可以让我们借用一个已存 在的函数&#xff0c;而将函数体内的 th…

ISIS学习第一部分——isis基本概念

目录 一.ISIS与OSI模型 1.IS-IS&#xff0c;中间系统到中间系统 2.ES-IS,终端系统到中间系统 二.NET——ISIS中的“IP地址” &#xff08;1&#xff09;NET有3个部分: 1.Area ID 2.System ID 3.SEL &#xff08;2&#xff09;.前面是可变长的&#xff0c;如何进行区分…

前端开发攻略---使用Sass调整颜色亮度,实现Element组件库同款按钮

目录 1、演示 2、实现原理 3、实现代码 1、演示 2、实现原理 改变颜色亮度的原理是通过调整颜色的 RGB 值中的亮度部分来实现的。在 Sass 中&#xff0c;可以使用颜色函数来操作颜色的 RGB 值&#xff0c;从而实现亮度的调整。 具体来说&#xff0c;亮度调整函数通常会改变颜…

使用 Docker 部署 TaleBook 私人书籍管理系统

1&#xff09;项目介绍 GitHub&#xff1a;https://github.com/talebook/talebook Talebook 是一个简洁但强大的私人书籍管理系统。它基于 Calibre 项目构建&#xff0c;具备书籍管理、在线阅读与推送、用户管理、SSO 登录、从百度/豆瓣拉取书籍信息等功能。 友情提醒&#x…

ansible------inventory 主机清单

目录 inventory 中的变量 2&#xff09;组变量[webservers:vars] #表示为 webservers 组内所有主机定义变量&#xff0c;所有组内成 员都有效 ansible_userrootansible_passwordabc1234 3&#xff09; [all:vars…

前置知识储备

基本认知 什么是模式 在一定环境中解决一些问题的方案&#xff08;通俗来说&#xff1a;特定环境中用固定的套路解决问题&#xff09; 什么是设计模式 设计模式是一套反复被人使用&#xff0c;多数人知晓的&#xff0c;经过分类编目的代码设计经验的总结 设计模式最终的目…

[笔试训练](十五)

目录 043:平方数 044:分组 045:拓扑排序 043:平方数 平方数 (nowcoder.com) 题目&#xff1a; 题解&#xff1a; 简单题&#xff0c;开根号之后判断左右两个数哪个离得近。 #include <iostream> #include <cmath> using namespace std; typedef long long…

电脑文件批量重命名不求人:快速操作,高效技巧让你轻松搞定

在数字化时代&#xff0c;电脑文件的管理与整理显得尤为重要。当面对大量需要重命名的文件时&#xff0c;一个个手动修改不仅耗时&#xff0c;还容易出错。那么&#xff0c;有没有一种方法可以快速、高效地完成这一任务呢&#xff1f;答案是肯定的&#xff0c;下面就来介绍几种…

温暖家居新风尚,能率壁挂炉——设计新风尚,体验再升级

随着家居品质要求的提升&#xff0c;现代人对家居的舒适性和设计感有了更高的追求。壁挂炉&#xff0c;作为现代家居中不可或缺的一部分&#xff0c;其重要性日益凸显。中国国际供热通风空调、卫浴及舒适家居系统展览会&#xff08;ISH China & CIHE&#xff09;将于2024年…

测评工作室的养号成本,效率,纯净度,便捷性等问题怎么解决?

大家好&#xff0c;我是南哥聊跨境&#xff0c;最近有很多做测评工作室的朋友找到南哥&#xff0c;问我有什么新的测评养号系统可以解决成本&#xff0c;效率&#xff0c;纯净度&#xff0c;便捷性等问题 测评养号系统从最早的模拟器、虚拟机到911、VPS、手机设备等&#xff0…

【深度学习实战(33)】训练之model.train()和model.eval()

一、model.train()&#xff0c;model.eval()作用&#xff1f; model.train() 和 model.eval() 是 PyTorch 中的两个方法&#xff0c;用于设置模型的训练模式和评估模式。 model.train() 方法将模型设置为训练模式。在训练模式下&#xff0c;模型会启用 dropout 和 batch norm…

|Python新手小白中级教程|第二十三章:列表拓展之——元组

文章目录 前言一、列表复习1.索引、切片2.列表操作字符3.数据结构实践——字典 二、探索元组1.使用索引、切片2.使用__add__((添加元素&#xff0c;添加元素))3.输出元组4.使用转化法删除元组指定元素5.for循环遍历元组 三、元组VS列表1.区别2.元组&#xff08;tuple&#xff0…

零门槛副业兼职!10种长期赚钱好方法!

想要实现财务自由&#xff0c;不能仅停留在梦想层面&#xff0c;更需要付诸实践。 以下是我从网络上精心整理的十大可靠的兼职副业建议&#xff0c;旨在助你一臂之力。 这些项目已根据推荐程度、难度水平、目标人群以及预期收入进行了细致分类。 我要强调的是&#xff0c;任…

Cosmo Bunny Girl

可爱的宇宙兔女郎的3D模型。用额外的骨骼装配到Humanoid上,Apple混合了形状。完全模块化,包括不带衣服的身体。 技术细节 内置,包括URP和HDRP PDF。还包括关于如何启用URP和HDRP的说明。 LOD 0:面:40076,tris 76694,verts 44783 装配了Humanoid。添加到Humanoid中的其他…

带EXCEL附件邮件发送相关代码

1.查看生成的邮件 2.1 非面向对象的方式&#xff08;demo直接copy即可&#xff09; ​ REPORT Z12. DATA: IT_DOCUMENT_DATA TYPE SODOCCHGI1,IT_CONTENT_TEXT TYPE STANDARD TABLE OF SOLISTI1 WITH HEADER LINE,IT_PACKING_LIST TYPE TABLE OF SOPCKLSTI1 WITH HEADER LIN…

AI编码工具-通义灵码初识

AI编码工具-通义灵码初识 通义灵码支持环境及语言代码安全性 通义灵码安装通义灵码登录 关于通义灵码的初识&#xff0c;还是得从2023云栖大会来说起。2023云栖大会带来了跨越式升级的千亿级参数规模大模型——通义千问2.0&#xff0c;随之而来的便有通义灵码&#xff0c;那么什…
最新文章