兰州大学数据结构上机试验题目及答案

1、数据结构课程实习题目实习一1、编写一个读入一个字符串，把它存入一个链表，并按相反的次序打印的程序。2、 设有个单位的人员工资， 有如下信息: name、department 、 base pay、allowance > total o现从键盘输入一组人员工资数据并将它们存储到名为paydata的文件中；再从paydata 取出工资数据并给每个人的 base pay增加100元，增加后将工资数据显示于屏幕 （每行1 人）。请编写能够完成上述工作的程序。实习二1、试用分别用线性表的向量存储结构和链表存储结构来实现约瑟夫（Josephu）问题。约瑟夫问题如下：设有n个人围坐圆桌周围。从某个位置

2、上的人开始从1报数，数到m的人便出列，下一个人（第m+1个）又从1报数开始，数到 m的人便是第2个出列的人，依次类推，直到最 后一个人出列为止，这样就可以得到一个人员排列的新次序。例如，n=8,m=4,从第1个人数起，得到的新次序为 48521376.实习三编写建立一个由单链表组织存储的整数序列的程序，链表中每个结点存储一个整型数 值，以此为基础完成将整数b插入到该链表中第一个数值为a的结点之前的程序。实习四采用llink-rlink方式存储二叉排序树，编写能够通过键盘输入建立二叉排序树，并在建 立完立即在屏幕显示中序遍历结果的程序。实习五对于给定的一个工程施工图，该图以边为单位从键盘输入，编

3、写能够找出该图的关键路 径的程序。实习六假设有一个数据类型为整型的一维数组A, A中的数据元素呈无序状态，编写一个采用堆排序法将A中的数据元素按由小到大进行排序的程序。数据结构答案（答案仅供参考）实验一1、编写一个读入一个字符串，把它存入一个链表，并按相反的次序打印的程序。#include<stdio.h>#include<malloc.h>struct strchar ch;struct str *next;；void main()(char tem;struct str *p,*h,*s;h=malloc(sizeof(struct str);h->next=

4、NULL;if(h!=NULL)(printf("请输入一个字符：");/scanf("%c”,&tem);tem=getchar();h->ch=tem;while(tem!='$')(printf(" 请继续输入：");s=malloc(sizeof(struct str);if(s!=NULL)(tem=getchar();/scanf("%c",&tem);s->ch=tem;if(tem='$')free(s);else(if(h->next=NUL

5、L)h->next=s;elsep->next=s;p=s;p->next=NULL;printf("字符申逆序输出为：n");while(h->next!='0')(p=h;while(p->next!='0')(s=p;p=p->next;printf("%c",p->ch);s->next='0'printf("%c",h->ch);printf("n");2、设有一个单位的人员工资，有如下信息： name

6、department > base pay、 allowance、total。现从键盘输入一组人员工资数据并将它们存储到名为 paydata的文件中；再从paydata取出工资数据并给每个人的 base pay增加100 兀，增加后将工资数据显小于屏帚(每行1人)。请编写能够完成上述工作的程序。 #include <iostream.h>#include <fstream.h>#include <stdlib.h>void main()(char name40;char department40;float basepay;float allowanc

7、e;float total;fstream instuf,outstuf;outstuf.open("c:paydata.txt",ios:out);if(!outstuf)(cout<<"File could not open!"<<endl;abort();cout<<"请输入员工的姓名，部门，基本工资，津贴，总计工资："<<endl;while(cin>>name>>department>>basepay>>allowance>

8、>total)(outstuf<<name<<' '<<department<<' '<<basepay<<' '<<allowance<<' '<<total<<'n'outstuf.close();instuf.open("c:paydata.txt",ios:in);if(!instuf)(cout<<"File could not open!

9、"<<endl; abort();while(instuf>>name>>department>>basepay>>allowance>>total)(cout<<name<<' '<<department<<' '<<basepay+100<<''<<allowance<<' '<<total+100<<endl;instuf.c

10、lose();实验二1、试用分别用线性表的向量存储结构和链表存储结构来实现约瑟夫(Josephu)问题。约瑟夫问题如下：设有n个人围坐圆桌周围。从某个位置上的人开始从1报数，数到m的人便出列，下一个人(第m+1个)乂从1报数开始，数到m的人便是第2个出列的人， 依次类推，直到最后一个人出列为止，这样就可以得到一个人员排列的新次序。 例如，n=8,m=4,从第1个人数起，得到的新次序为 48521376.1、数组#include<stdio.h>void main()(int Josephu1000,m,n,i,j=0,c1=0,c2=1,t;printf("请输入总人数n

11、:");scanf("%d",&n);printf("请输入 m:");scanf("%d",&m);t=n;for(i=0;i<n;i+)(Josephui=i+1;while(c1<t)(if(c2)%m=0)(printf("%dt",Josephuj);c1+;n=n-1;for(i=j;i<n;i+)(if(Josephui+1!=0)Josephui=Josephui+1;j=j-1;c2+;j+；if(j=n)j=0;2、链表#include<stdi

12、o.h>#include<malloc.h>struct Josephuint num;struct Josephu *next;void main()int i=1,m,n,count=1;struct Josephu *head,*s,*t;head=(struct Josephu *)malloc(sizeof(struct Josephu);head->num=1;head->next=NULL;printf(" 请输入总人数n:");scanf("%d",&n);printf("请输入循环数m:&

13、quot;);scanf("%d",&m);t=head;while(i<n)s=(struct Josephu*)malloc(sizeof(struct Josephu);s->num=i+1;t->next=s;t=s;i+;t->next=head;t=head;while(t!=NULL)if(count%m=0)printf("%dt”,t->num);if(t->next!=t)s->next=t->next;t=t->next;count+=1;elset=NULL;else(s=t;t

14、=t->next;count+;实验三编写建立一个由单链表组织存储的整数序列的程序，链表中每个结点存储一个整型数值，以此为基础完成将整数 b插入到该链表中第一个数值为a的结点之前的程序。#include<iostream.h>struct data(int men;struct data *next;void main()(void show(data *st);data* creat();data* insert(data *h,int tem1,int local);data *head;int b,a;head=creat();show(head);cout<&l

15、t;"请输入要插入的数据："<<endl;cin>>b;cout<<"请输入要插入的位置："<<endl;cin>>a;head=insert(head,b,a);show(head);data* creat()(data *h,*t,*s;int choice;h=new data;cout«"请输入数据："«endl;cin»h->men;t=h;cout«" if选择：1、继续输入2、退出"«e

16、ndl;cin»choice;while(choice!=2)(s=new data;cout«"请输入数据："«endl;cin»s->men;t->next=s;t=s;coutvv”请选择：1、继续输入2、退出"«endl; cin»choice;t->next=NULL;return h;data* insert(data *h,int tem1 ,int local)data *t,*s,*bt;bt=new data;bt->men=tem1;t=h;if(h->

17、men=local)bt->next=h;h=bt;elsewhile(t->next!=NULL&&t->men!=local)s=t;t=t->next;if(t->men=local)s->next=bt;bt->next=t;elsecout<<"位置输入错误！ "<<endl;return h;void show(data *st)(data *p;p=st;while(p!=NULL)(cout<<p->men<<"t"p=p-&g

18、t;next;cout<<endl;实验四采用llink-rlink方式存储二叉排序树，编写能够通过键盘输入建立二叉排序树，并在建 立完立即在屏幕显示中序遍历结果的程序。#include<iostream.h>struct tree(int num;struct tree *llink;struct tree *rlink;void main()(tree* create();void show(tree*);tree *head;head=create();show(head);tree* create()(void insert(tree *h,tree *t);t

19、ree *h=NULL,*s,*t;int choice;cout<<"请选择：1、输入数据2、退出"<<endl;cin>>choice;while(choice!=2)(s=new tree;s->llink=NULL;s->rlink=NULL;cout<<"请输入数据："<<endl;cin>>s->num;if(h=NULL)h=s;t=h;elseinsert(h,s);cout<<"请选择：1、输入数据2、退出"<

20、<endl; cin>>choice;return h;void show(tree *h)if(h!=NULL)show(h->llink);cout<<h->num<<'t'show(h->rlink);void insert(tree *h,tree *t)if(h->num<t->num)if(h->rlink=NULL)h->rlink=t;elseinsert(h->rlink,t);elseif(h->llink=NULL)h->llink=t;elsein

21、sert(h->llink,t);实验五对于给定的一个工程施工图，该图以边为单位从键盘输入，编写能够找出该图的关键路 径的程序。#include<stdio.h>#include<stdlib.h>#include<malloc.h>#define MAX 50struct nodeint adjvex;int dut;struct node *next;node;struct vexnodeint vertex,indegree;int ve,vl;struct node *link;vexnode;struct adjliststruct vexn

22、ode AMAX;adjlist;void creatadjlist(struct adjlist *G,int n,int e)int a,b,w,i;struct node *p;for(i=0;i<n;i+)G->Ai.link=NULL;G->Ai.vertex=i+1;G->Ai.indegree=0;G->Ai.ve=0;for(i=0;i<e;i+)printf("请输入第d条边的起点，终点及权：n",i+1);scanf("%d %d %d",&a,&b,&w);printf(&

23、quot;n");p=(struct node *)malloc(sizeof(struct node);p->adjvex=b;p->dut=w;G->Ab-1.indegree+;p->next=G->Aa-1.link;G->Aa-1.link=p;int toporder(struct adjlist *G,int n)int top1=0,top2=0;int m=0,i,k,j;struct node *p;for(i=1;i<=n;i+)if(G->Ai-1.indegree=0)G->Ai-1.indegree=t

24、op1;top1=i;while(top1!=0)j=top1;top1=G->Aj-1.indegree;G->Aj-1.indegree=top2;top2=j;m=m+1;p=G->Aj-1.link;while(p!=NULL)k=p->adjvex;G->Ak-1.indegree=G->Ak-1.indegree-1;if(G->Ak-1.indegree=0)G->Ak-1.indegree=top1;top1=k;if(G->Aj-1.ve+p->dut)>G->Ak-1.ve)G->Ak-1.ve=

25、G->Aj-1.ve+p->dut;p=p->next;if(m<n)printf(" 有环！"); return top2;void critical_path(struct adjlist *G,int top2,int n)int i,v,j;int ei,el;struct node *p;int endnode;endnode=top2;for(i=0;i<n;i+)G->Ai.vl=G->An-1.ve;while(top2!=0)v=top2;top2=G->Av-1.indegree;p=G->Av-1.

26、link;while(p!=NULL)j=p->adjvex;if(G->Aj-1.vl-p->dut<G->Av-1.vl)G->Av-1.vl=G->Aj-1.vl-p->dut; p=p->next;printf("n 关键路径是：n");for(i=0;i<n;i+)p=G->Ai.link;while(p!=NULL)j=p->adjvex;ei=G->Ai.ve;el=G->Aj-1.vl-p->dut;if(ei=el)printf("V%d,”,G->Ai.vertex); p=p->next;printf("V%d n”,G->Aendnode-1.vertex);void main()(int n,e;int top2;struct adjlist *G;printf(-请分别输入