编程题ll

news/2024/5/21 0:08:45

编程题

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;elsereturn 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.mrgr.cn/p/13047084

相关文章

Java-线程-线程池

Java-线程-线程池

0.背景参考资料：Java线程池实现原理及其在美团业务中的实践在 Java 早期，每次创建线程时，都要涉及到线程的创建、销毁以及资源管理，这对于系统的性能和资源利用率是一种浪费。 因此，Java 提供了线程池的概念，以提高线程的管理效率和性能。资源管理优化：传统的线程创建和…
阅读更多...
vue2项目升级到vue3经历分享4

vue2项目升级到vue3经历分享4

后端重构&#xff0c;如果接口做好抽象封装&#xff0c;只需要考虑jar之间的兼容性问题&#xff0c;jdk版本不变&#xff0c;基本不用做太大的调整&#xff0c;但是前端就不一样&#xff0c;除了vue框架本身&#xff0c;css的调整&#xff0c;改起来更是让人头疼。前面写了vue2…
阅读更多...
8.2版本Web端移动开发调试强制跳转新移动框架

8.2版本Web端移动开发调试强制跳转新移动框架

解决方案: Common.config文件中增加配置项 <add key="MobileLoginType" value="1" /> 如下图其他注意事项： 没有配置MobileLoginType属性 或 MobileLoginType = "" 或 MobileLoginType = 2 都会执行重定向 MobileLoginType = 3 系…
阅读更多...
SQL 基础 | UNION 用法介绍

SQL 基础 | UNION 用法介绍

在SQL中&#xff0c;UNION操作符用于合并两个或多个SELECT语句的结果集&#xff0c;形成一个新的结果集。 使用UNION时&#xff0c;合并的结果集列数必须相同&#xff0c;并且列的数据类型也需要兼容。 默认情况下&#xff0c;UNION会去除重复的行&#xff0c;只保留唯一的行。…
阅读更多...
cordova build android 下载gradle太慢

cordova build android 下载gradle太慢

一、 在使用cordova run android / cordova build android 的时候 gradle在线下载 对于国内的链接地址下载太慢。 等待了很长时间之后还会报错。 默认第一次编译在线下载 gradle-7.6.1-all.zip 然后解压缩到 C:\Users\Administrator\.gradle 文件夹中，下载慢导致失败。 二…
阅读更多...
【软件工程】需求分析

【软件工程】需求分析

目录 前言需求分析需求获取UML概述用例图用例图的组成用例图中的符号和含义包含的两种使用场景 用例图补充&#xff1a;“系统”用例模型建模确定系统参与者确定系统用例 用例文档用例文档组成部分 活动图组成元素初始节点和终点活动节点转换决策与分支、合并分岔与汇合 类图类…
阅读更多...
Java面试八股文(SpringCloud篇)

Java面试八股文(SpringCloud篇)

****************************************************
阅读更多...
Error: Cannot find module ‘D:\SoftSetupLoaction\nodejs\node_global\node_modules\npm\bin\npm-cli.js‘

Error: Cannot find module ‘D:\SoftSetupLoaction\nodejs\node_global\node_modules\npm\bin\npm-cli.js‘

Error: Cannot find module ‘D:\SoftSetupLoaction\nodejs\node_global\node_modules\npm\bin\npm-cli.js‘ 出现原因: 重新安装可装了nodejs和npm 网上查了很多方法，都建议重装，但是都没有效果(因为我就是重装之后出现的问题) 按照错误提示node_global找不到npm-cli.js,个人…
阅读更多...
初探pinctrl子系统和GPIO子系统

初探pinctrl子系统和GPIO子系统

前言： 在前面的led驱动程序和按键驱动程序中，无论是最传统的方法，还是总线设备驱动模型，还是基于设备树的总线设备驱动模型，都是直接操作寄存器的方法。驱动开发的本质确实是操作寄存器，但是一个芯片有几百个引脚，只是操作少数的几个引脚还好，如果是大量的引脚，比如LC…
阅读更多...
前端开发攻略---使用Sass调整颜色亮度，实现Element组件库同款按钮

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

目录 1、演示 2、实现原理 3、实现代码 1、演示 2、实现原理 改变颜色亮度的原理是通过调整颜色的 RGB 值中的亮度部分来实现的。在 Sass 中&#xff0c;可以使用颜色函数来操作颜色的 RGB 值&#xff0c;从而实现亮度的调整。 具体来说&#xff0c;亮度调整函数通常会改变颜…
阅读更多...
PVE新增硬盘并扩容给 local分区

PVE新增硬盘并扩容给 local分区

PVE安装在120G的固态硬盘，现在加了一块1T的机械硬盘作为虚拟机系统用，需要把磁盘扩容给 local分区 1、ssh连上pve，使用 lsblk 查看硬盘驱动器路径，我这里新加的硬盘是 sda，硬盘还未进行分区 2、fdisk /dev/sda，对硬盘进行分区操作，注意你自己的硬盘名称，千万小心不要搞…
阅读更多...
Windows内核开发：如何使用STL

Windows内核开发：如何使用STL

前言 大家都知道应用层c的STL非常强大&#xff0c;非常好用&#xff0c;但是在内核下就没法用了。针对这个问题&#xff0c;经过我不懈的寻找&#xff0c;终于找到了解决内核无法使用STL的方法。 使用new/delete关键字 先说一下常用关键字如何在内核中使用。其实只需要在一个全…
阅读更多...
simple test

simple test

This is a test
阅读更多...
实验1-波士顿房价预测部分报错解决方法

实验1-波士顿房价预测部分报错解决方法

运行sgd = SGDRegressor()sgd.fit(x_train, y_train)print("r2 score of Linear regression is",r2_score(y_test,sgd.predict(x_test)))时出现 DataConversionWarning: A column-vector y was passed when a 1d array was expected. Please change the shape of y t…
阅读更多...
用栈实现队列——leetcode刷题

用栈实现队列——leetcode刷题

题目要求我们只用栈的基本操作 push to top 入栈&#xff0c;peek from top 返回栈顶元素&#xff0c;pop from top 移除并返回栈顶元素&#xff0c;size 栈的大小&#xff0c;is_empty 判断栈是否为空&#xff0c;这几个函数来实现队列&#xff0c;也就是说&#xff0c;我们在…
阅读更多...
【Java】初识网络编程

【Java】初识网络编程

文章目录 前言✍一、互联网的发展1.独立模式2.网络的出现局域网LAN广域网WAN ✍二、网络编程概述✍三、网络编程中的术语介绍IP地址端口号协议OSI七层模型TCP\IP四层模型 ✍四、协议的层级之间是如何配合工作的 前言 在本文中&#xff0c;会对网络编程的一些术语进行解释&#…
阅读更多...
《最新出炉》系列入门篇-Python+Playwright自动化测试-45-鼠标操作-下篇

《最新出炉》系列入门篇-Python+Playwright自动化测试-45-鼠标操作-下篇

1.简介 鼠标为我们使用电脑提供了很多方便，我们看到的东西就可以将鼠标移动过去进行点击就可以打开或者访问内容，当页面内容过长时，我们也可以使用鼠标滚轮来实现对整个页面内容的查看，其实playwright也有鼠标操作的方法。上一篇文章中已经讲解过鼠标的部分操作了，今天宏哥…
阅读更多...
redux中核心组件有哪些，reducer的作用

redux中核心组件有哪些，reducer的作用

在redux中，核心组件包括Action、Reducer、Store和Middleware。 Action是一个普通的JavaScript对象，用于描述发生了什么事件。它必须包含一个type属性，用于标识事件的类型。可以在Action中添加其他自定义的属性来传递数据。 Reducer是一个纯函数，用于根据收到的Action来更新…
阅读更多...
学习记录+vcode＋GPIO例程+正点原子 DNESP32S3 开发板教程-IDF 版

学习记录+vcode＋GPIO例程+正点原子 DNESP32S3 开发板教程-IDF 版

第一个程序： UART模式和JTAG模式，配置完成不同。配置主要就是.vscode 文件夹中 c_cpp_properties.json，tasks.json，launch.json，settings.json四个文件。 一个想法：备份UART模式和JTAG模式的配置文件，用时直接文件替换。简单粗暴方式是.vscode 文件夹替换。当然每次要选…
阅读更多...
chrome extension插件替换网络请求中的useragent

chrome extension插件替换网络请求中的useragent

感觉Chrome商店中的插件不能很好的实现自己想要的效果，那么就来自己动手吧。 本文以百度为例： 一般来说网页请求如下： 当前使用的useragent是User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/124.0.0.0 Safar…
阅读更多...
推荐文章

Copyright @ 2022~2023