贵州大学计算机考研831840历年算法题及答案整理.docx
- 文档编号:15170027
- 上传时间:2023-07-02
- 格式:DOCX
- 页数:23
- 大小:312.25KB
贵州大学计算机考研831840历年算法题及答案整理.docx
《贵州大学计算机考研831840历年算法题及答案整理.docx》由会员分享,可在线阅读,更多相关《贵州大学计算机考研831840历年算法题及答案整理.docx(23页珍藏版)》请在冰点文库上搜索。
贵州大学计算机考研831840历年算法题及答案整理
1历年编程题
1.1递归阶乘
1.2结构体编程-求成绩高于平均成绩的学生学号
1.3打印杨辉三角
1.4统计单链表中等于给定值的结点数
#include
#include
typedefintElemType;
//结构体定义
typedefstructLNode{
ElemTypedata;
structLNode*next;
}LNode;
intCountX(LNode*HL,ElemTypex){
intcount;
while(HL->next!
=NULL){
if(HL->data==x){
++count;
}
HL=HL->next;
}
returncount;
}
//初始化结构体
voidInit(LNode*&head,ElemTypea[],intn){
LNode*s,*r;
head=(LNode*)malloc(sizeof(LNode));
head->next=NULL;
r=head;
inti;
for(i=0;i s=(LNode*)malloc(sizeof(LNode)); s->data=a[i]; s->next=r->next; r->next=s; r=r->next; } r->next=NULL; } //输出内容 voidPrint(LNode*head){ head=head->next; while(head! =NULL){ printf("%d",head->data); head=head->next; } printf("\n"); } /* Directions: 统计单链表中值=x的个数 */ intmain(){ intn=5; LNode*head; ElemTypea[n]={6,4,2,4,6}; Init(head,a,n); Print(head); //实际编程时,先给出结构体定义,然后直接编写函数即可,Init、Print可省略 intcount=CountX(head,2); printf("count=%d",count); return0; } 1.5链式存储方法构建二叉树 //结构体定义 typedefstructBiTNode { TElemTypedata; structBiTNode*lchild,*rchild; }BiTNode,*BiTree; //创建代码 voidcreateBitree(Bitree&T){ charch; if((ch=getchar())=='#') T=NULL; else{ T=(Bitnode*)malloc(sizeof(Bitnode)); T->data=ch; createBitree(T->Lchild); createBitree(T->Rchild); } } /*先序遍历*/ voidpreTraverse(BitreeT) { if(T! =NULL) { printf("%c",T->data); preTraverse(T->Lchild); preTraverse(T->Rchild); } } 1.6链表实现A交B 因为是回忆版,不确定题目是不是有序列表,或者题目有没有要求释放空间,或者不破坏原链表的结构,这些在做题时都需要注意,会影响到算法的实现。 无序求交集的写法。 //A、B有序,且要释放空间,写法。 LinkListUnion_Link(LinkList&la,LinkList&lb){ pa=la->next;//设工作指针分别为pa和pb pb=lb->next; LinkListpc=la;//结果表中当前合并结点的前驱指针 while(pa! =NULL&&pb! =NULL){ if(pa->data==pb->data){//交集并入结果表中 pc->next=pa;//A中结点链接到结果表 pc=pa; pa=pa->next; u=pb;//B中结点释放 pb=pb->next; free(u); } elseif(pa->data u=pa; pa=pa->next;//A后移 free(u);//释放A中当前结点 }else{//若B中当前结点值小于A中当前结点值 u=pb; pb=pb->next;//B后移 free(u);//释放B中当前结点 } } while(pa! =NULL){//A未遍历完 u=pa; pa=pa->next; free(u); } while(pb! =NULL){//B未遍历完 u=pb; pb=pb->next; free(u); } pc->next=NULL;//置结果链表尾指针为NULL free(lb);//释放B表的头结点,A表的头结点现在用在C表了。 returnla; } 无序时求交集。 //结构体定义 typedefintElemType; typedefstructNode{ ElemTypedata; structNode*next; }Link,*LinkList; //函数声明 boolisPresent(LinkListB,ElemTypedata);//判断给定结点是否在链表B中 LinkListgetIntersection(LinkListA,LinkListB);//求交集函数 LinkListgetUnion(LinkListA,LinkListB);//求并集函数 //函数实现 LinkListgetIntersection(LinkListA,LinkListB)//求交集函数 { structNode*tail=NULL; structNode*C=(structNode*)malloc(sizeof(structNode)); C->next=NULL; tail=C; structNode*t1=A; while(t1! =NULL) { if(isPresent(B,t1->data)){ structNode*new_node=(structNode*)malloc(sizeof(structNode)); new_node->data=t1->data; new_node->next=tail; tail=new_node; } t1=t1->next; } returnC; } boolisPresent(LinkListB,intdata){//判断是否存在 structnode*t=head; while(t! =NULL){ if(t->data==data) return1; t=t->next; } return0; } LinkListgetUnion(LinkListA,LinkListB)//求并集函数 { structNode*tail=NULL; structNode*C=(structNode*)malloc(sizeof(structNode)); C->next=NULL; tail=C; structNode*t1=A,*t2=B; while(t1! =NULL){ structNode*new_node=(structNode*)malloc(sizeof(structNode)); new_node->data=t1->data; new_node->next=tail; tail=new_node; t1=t1->next; } while(t2! =NULL){ if(! isPresent(result,t2->data)){ structNode*new_node=(structNode*)malloc(sizeof(structNode)); new_node->data=t2->data; new_node->next=tail; tail=new_node; } t2=t2->next; } returnC; } 1.7邻接矩阵转邻接表 #include #include typedefintInfoType; #defineMAXV100//最大顶点个数 #defineINF32767//INF表示∞ //以下定义邻接矩阵类型 typedefstruct{ intno;//顶点编号 InfoTypeinfo;//顶点其他信息 }VertexType;//顶点类型 typedefstruct{//图的定义 intedges[MAXV][MAXV];//邻接矩阵 intn,e;//顶点数,边数 VertexTypevexs[MAXV];//存放顶点信息 }MGraph;//图的邻接矩阵类型 //以下定义邻接表类型 typedefstructANode{//边的节点结构类型 intadjvex;//该边的终点位置 structANode*nextarc;//指向下一条边的指针 InfoTypeinfo;//该边的相关信息,这里用于存放权值信息 }ArcNode; typedefintVertex; typedefstructVnode{//邻接表头节点的类型 Vertexdata;//顶点信息 ArcNode*firstarc;//指向第一条边 }VNode; typedefVNodeAdjList[MAXV];//AdjList是邻接表类型 typedefstruct {AdjListadjlist;//邻接表 intn,e;//图中顶点数n和边数e }ALGraph;//图的邻接表类型 //将邻接矩阵g转换成邻接表G,转换函数 voidMatToList(MGraphg,ALGraph*&G){ inti,j; ArcNode*p; G=(ALGraph*)malloc(sizeof(ALGraph)); for(i=0;i G->adjlist[i].firstarc=NULL; for(i=0;i for(j=g.n-1;j>=0;j--) if(g.edges[i][j]! =0){//存在一条边 p=(ArcNode*)malloc(sizeof(ArcNode));//创建一个节点*p p->adjvex=j; p->nextarc=G->adjlist[i].firstarc;//采用头插法插入*p G->adjlist[i].firstarc=p; } G->n=g.n;G->e=g.e; } //将邻接表G转换成邻接矩阵g voidListToMat(ALGraph*G,MGraph&g){ inti; ArcNode*p; for(i=0;i p=G->adjlist[i].firstarc; while(p! =NULL){ g.edges[i][p->adjvex]=1; p=p->nextarc; } } g.n=G->n;g.e=G->e; } //输出邻接矩阵g voidDispMat(MGraphg){ inti,j; for(i=0;i { for(j=0;j printf("%3d",g.edges[i][j]); printf("\n"); } } //输出邻接表G voidDispAdj(ALGraph*G){ inti; ArcNode*p; for(i=0;i { p=G->adjlist[i].firstarc; printf("%3d: ",i); while(p! =NULL) { printf("%3d",p->adjvex); p=p->nextarc; } printf("\n"); } } //以下主函数用作调试,实际题目时不用写 intmain() { inti,j; MGraphg,g1; ALGraph*G; intm,n; scanf("%d%d",&n,&m); intA[n][n]; for(inti=0;i { for(intj=0;j { scanf("%d",&A[i][j]); } } g.n=n;g.e=m; for(i=0;i for(j=0;j g.edges[i][j]=A[i][j]; //printf("\n"); ///printf("有向图G的邻接矩阵: \n"); //DispMat(g); G=(ALGraph*)malloc(sizeof(ALGraph)); //printf("图G的邻接矩阵转换成邻接表: \n"); MatToList(g,G); DispAdj(G); /*printf("图G的邻接表转换成邻接邻阵: \n"); for(i=0;i for(j=0;j g1.edges[i][j]=0; ListToMat(G,g1); DispMat(g1); printf("\n");*/ //system("pause"); } 1.8结构体编程-求工资最少的职工姓名 #include //数据结构定义 structnode{ charnumber[30];//职工号 charname[30];//职工姓名 floatwage;//薪水,大于等于0 }people[5]; voidFind(){ inti; intmin_id=0; floatmin_wage=people[0].wage; for(i=1;i<5;i++){ if(people[i].wage min_wage=people[i].wage; min_id=i; } } printf("%s\n",people[min_id].name); //检查有无与当前薪水一样的职工,同时输出.这一点要注意,大部分同学想不到 for(i=1;i<5;i++){ if(people[i].wage==min_wage&&people[i].id! =min_id){ printf("%s\n",people[i].name); } } } intmain(){ inti; for(i=0;i<5;i++) scanf("%s%s%f",people[i].number,people[i].name,&people[i].wage); Find(); return0; } 1.9一个不超过5位的正整数,编程实现数有多少位以及逆序输出这个数 #include //求给定输入的不超过5位的整数有多少位,并逆序输出。 intmain() { intn; scanf("%d",&n); intlen=0;//位数初值给0 while(n>0){ intbit_num=n%10; n=n/10; printf("%d",bit_num); len++; } printf("\n"); printf("%d\n",len); return0; } 1.10双向冒泡排序算法 #include //双向冒泡排序算法核心逻辑 voidbubblesort(ints[],intlen){ intl=0,r=len-1,temp,flag; while(l flag=0; for(inti=l;i if(s[i]>s[i+1]){ temp=s[i]; s[i]=s[i+1]; s[i+1]=temp; flag=1; } } if(flag==0){ break;//此次没有发生交换,则跳出循环,冒泡排序的一个优化技巧。 } --r; for(inti=r;i>l;i--){ if(s[i] temp=s[i]; s[i]=s[i-1]; s[i-1]=temp; } } ++l; } } intmain(){ ints[]={9,8,7,6,5,4,3,2,1}; intlen=sizeof(s)/sizeof(s[0]); bubblesort(s,len); for(inti=0;i printf("%d",s[i]); } printf("\n"); return0; } 双向冒泡也不算一种全新的算法,算是冒泡排序的优化,时间复杂度跟原冒泡排序是一样的。 1.11编程实现给定一个有向无环图,求图的最长路径,并估计时间复杂度 #include constintN=105; intG[N][N]={0}; intn,ans=0,sum; //深度优先访问x点,记录最大值 voiddfs(intx){ for(inti=1;i<=n;i++){ if(G[x][i]>0){ sum+=G[x][i]; dfs(i); sum-=G[x][i]; } } if(ans ans=sum; } intmain(){ scanf("%d",&n); inti,j; for(inti=1;i<=n;i++) for(intj=1;j<=n;j++) scanf("%d",&G[i][j]); for(inti=1;i<=n;i++){ sum=0; dfs(i); } printf("%d\n",ans); return0; } 优化版: memset(vis,0,sizeof(vis));//标记数组 vis[0]=1; dpx[0]=0; intsolve(intS)//搜索最少需要多少步 { if(vis[S])//是否已经找过此种状态 { returndpx[S]; } vis[S]=1; int&ans=dpx[S];//dpx[S]声明一个引用ans,这样任何对ans的读写实际上都是在对dpx[S]进行 ans=INF;//初始化到此状态无穷大 for(inti=1;i<=n;i++) { if(S>=v[i]) { ans=min(ans,solve(S-v[i])+1); } } returnans; } voidpint(intdp[],intS) { for(inti=1;i<=n;i++) { if(S>=v[i]&&(dp[S]==dp[S-v[i]]+1)) { printf("%d",i); pint(dp,S-v[i]); break; } } }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 贵州 大学计算机 考研 831840 历年 算法 答案 整理
![提示](https://static.bingdoc.com/images/bang_tan.gif)