蘭州大學(xué)數(shù)據(jù)結(jié)構(gòu)上機(jī)試驗(yàn)題目及答案

1、數(shù)據(jù)結(jié)構(gòu)課程實(shí)習(xí)題目實(shí)習(xí)一1、編寫(xiě)一個(gè)讀入一個(gè)字符串，把它存入一個(gè)鏈表，并按相反的次序打印的程序。2、 設(shè)有個(gè)單位的人員工資， 有如下信息: name、department 、 base pay、allowance > total o現(xiàn)從鍵盤(pán)輸入一組人員工資數(shù)據(jù)并將它們存儲(chǔ)到名為paydata的文件中；再?gòu)膒aydata 取出工資數(shù)據(jù)并給每個(gè)人的 base pay增加100元，增加后將工資數(shù)據(jù)顯示于屏幕 （每行1 人）。請(qǐng)編寫(xiě)能夠完成上述工作的程序。實(shí)習(xí)二1、試用分別用線性表的向量存儲(chǔ)結(jié)構(gòu)和鏈表存儲(chǔ)結(jié)構(gòu)來(lái)實(shí)現(xiàn)約瑟夫（Josephu）問(wèn)題。約瑟夫問(wèn)題如下：設(shè)有n個(gè)人圍坐圓桌周?chē)哪硞€(gè)位置

2、上的人開(kāi)始從1報(bào)數(shù)，數(shù)到m的人便出列，下一個(gè)人（第m+1個(gè)）又從1報(bào)數(shù)開(kāi)始，數(shù)到 m的人便是第2個(gè)出列的人，依次類(lèi)推，直到最 后一個(gè)人出列為止，這樣就可以得到一個(gè)人員排列的新次序。例如，n=8,m=4,從第1個(gè)人數(shù)起，得到的新次序?yàn)?48521376.實(shí)習(xí)三編寫(xiě)建立一個(gè)由單鏈表組織存儲(chǔ)的整數(shù)序列的程序，鏈表中每個(gè)結(jié)點(diǎn)存儲(chǔ)一個(gè)整型數(shù) 值，以此為基礎(chǔ)完成將整數(shù)b插入到該鏈表中第一個(gè)數(shù)值為a的結(jié)點(diǎn)之前的程序。實(shí)習(xí)四采用llink-rlink方式存儲(chǔ)二叉排序樹(shù)，編寫(xiě)能夠通過(guò)鍵盤(pán)輸入建立二叉排序樹(shù)，并在建 立完立即在屏幕顯示中序遍歷結(jié)果的程序。實(shí)習(xí)五對(duì)于給定的一個(gè)工程施工圖，該圖以邊為單位從鍵盤(pán)輸入，編

3、寫(xiě)能夠找出該圖的關(guān)鍵路 徑的程序。實(shí)習(xí)六假設(shè)有一個(gè)數(shù)據(jù)類(lèi)型為整型的一維數(shù)組A, A中的數(shù)據(jù)元素呈無(wú)序狀態(tài)，編寫(xiě)一個(gè)采用堆排序法將A中的數(shù)據(jù)元素按由小到大進(jìn)行排序的程序。數(shù)據(jù)結(jié)構(gòu)答案（答案僅供參考）實(shí)驗(yàn)一1、編寫(xiě)一個(gè)讀入一個(gè)字符串，把它存入一個(gè)鏈表，并按相反的次序打印的程序。#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("請(qǐng)輸入一個(gè)字符：");/scanf("%c”,&tem);tem=getchar();h->ch=tem;while(tem!='$')(printf(" 請(qǐng)繼續(xù)輸入：");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、設(shè)有一個(gè)單位的人員工資，有如下信息： name

6、department > base pay、 allowance、total。現(xiàn)從鍵盤(pán)輸入一組人員工資數(shù)據(jù)并將它們存儲(chǔ)到名為 paydata的文件中；再?gòu)膒aydata取出工資數(shù)據(jù)并給每個(gè)人的 base pay增加100 兀，增加后將工資數(shù)據(jù)顯小于屏帚(每行1人)。請(qǐng)編寫(xiě)能夠完成上述工作的程序。 #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<<"請(qǐng)輸入員工的姓名，部門(mén)，基本工資，津貼，總計(jì)工資："<<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();實(shí)驗(yàn)二1、試用分別用線性表的向量存儲(chǔ)結(jié)構(gòu)和鏈表存儲(chǔ)結(jié)構(gòu)來(lái)實(shí)現(xiàn)約瑟夫(Josephu)問(wèn)題。約瑟夫問(wèn)題如下：設(shè)有n個(gè)人圍坐圓桌周?chē)?。從某個(gè)位置上的人開(kāi)始從1報(bào)數(shù)，數(shù)到m的人便出列，下一個(gè)人(第m+1個(gè))乂從1報(bào)數(shù)開(kāi)始，數(shù)到m的人便是第2個(gè)出列的人， 依次類(lèi)推，直到最后一個(gè)人出列為止，這樣就可以得到一個(gè)人員排列的新次序。 例如，n=8,m=4,從第1個(gè)人數(shù)起，得到的新次序?yàn)?48521376.1、數(shù)組#include<stdio.h>void main()(int Josephu1000,m,n,i,j=0,c1=0,c2=1,t;printf("請(qǐng)輸入總?cè)藬?shù)n

11、:");scanf("%d",&n);printf("請(qǐng)輸入 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(" 請(qǐng)輸入總?cè)藬?shù)n:");scanf("%d",&n);printf("請(qǐng)輸入循環(huán)數(shù)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+;實(shí)驗(yàn)三編寫(xiě)建立一個(gè)由單鏈表組織存儲(chǔ)的整數(shù)序列的程序，鏈表中每個(gè)結(jié)點(diǎn)存儲(chǔ)一個(gè)整型數(shù)值，以此為基礎(chǔ)完成將整數(shù) b插入到該鏈表中第一個(gè)數(shù)值為a的結(jié)點(diǎn)之前的程序。#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;"請(qǐng)輸入要插入的數(shù)據(jù)："<<endl;cin>>b;cout<<"請(qǐng)輸入要插入的位置："<<endl;cin>>a;head=insert(head,b,a);show(head);data* creat()(data *h,*t,*s;int choice;h=new data;cout«"請(qǐng)輸入數(shù)據(jù)："«endl;cin»h->men;t=h;cout«" if選擇：1、繼續(xù)輸入2、退出"«e

16、ndl;cin»choice;while(choice!=2)(s=new data;cout«"請(qǐng)輸入數(shù)據(jù)："«endl;cin»s->men;t->next=s;t=s;coutvv”請(qǐng)選擇：1、繼續(xù)輸入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<<"位置輸入錯(cuò)誤！ "<<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;實(shí)驗(yàn)四采用llink-rlink方式存儲(chǔ)二叉排序樹(shù)，編寫(xiě)能夠通過(guò)鍵盤(pán)輸入建立二叉排序樹(shù)，并在建 立完立即在屏幕顯示中序遍歷結(jié)果的程序。#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<<"請(qǐng)選擇：1、輸入數(shù)據(jù)2、退出"<<endl;cin>>choice;while(choice!=2)(s=new tree;s->llink=NULL;s->rlink=NULL;cout<<"請(qǐng)輸入數(shù)據(jù)："<<endl;cin>>s->num;if(h=NULL)h=s;t=h;elseinsert(h,s);cout<<"請(qǐng)選擇：1、輸入數(shù)據(jù)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);實(shí)驗(yàn)五對(duì)于給定的一個(gè)工程施工圖，該圖以邊為單位從鍵盤(pán)輸入，編寫(xiě)能夠找出該圖的關(guān)鍵路 徑的程序。#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("請(qǐng)輸入第d條邊的起點(diǎn)，終點(diǎn)及權(quán)：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(" 有環(huán)！"); 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 關(guā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(-請(qǐng)分別輸入