2011级计算机学院课程设计题目及参考程序

《2011级计算机学院课程设计题目及参考程序》由会员分享，可在线阅读，更多相关《2011级计算机学院课程设计题目及参考程序（74页珍藏版）》请在装配图网上搜索。

1、问题A:整数排序一时间限制:20 Sec内存限制:128 MB题目描述经过三天的任务1的训练，大家的确辛苦了.因此，在任务2开始时， 我为大家准备了一道令人非常愉快的热身题.即将一个杂乱无序的整数 序列，按照从小到大的顺序排列并输出.输入测试数据不止一组，每组测试数据：1）先输入无序序列的整数个数n； （n不超过1000000）2）然后连续输入n个整数；若n的值输入为0值，则输入结束.输出与每组输入的测试数据相对应，输出其按从小到大排好序后的整数序列.注意：每组输出占一行.样例输入109 8 7 6 5 4 3 2 1 -1588 77 66 55 330样例输出-1 1 2 3 4 5 6

2、7 8 933 55 66 77 88提示本题测试对第10章“内部排序”的理解程度。可采用冒泡排序、插入排序、选择排序、快速排序、希尔排序、堆排序等方法完成此题。警告：目的是让大家熟悉内部排序的各种算法，因此禁止调用sort或qsort等函数！不改正 者降最终成绩等级.简单排序版：#includevstdioh#includevstdlibh#define SIZE 10000void fastsort(int a,int n)int ij，k，temp; for(i=0;ivn-1;i+)k=i; for(j=i+1;jvn;j+) if(ajvak) k=j; if(i!=k) temp=

3、ai; ai=ak;int sortSIZE;int num,i;:咿 scanf(%d,&num); if(num=0) exit(0); for(i=0;inum;i+)fastsort(sort,num); for(i=0;inum;i+)if(i=num-1) printf(%d，sorti);else printf(%d ,sorti);printf(n);return 0;快速排序版:#include#define SIZE 100000 void quick_sort(int a, int low, int high)int i, j, t;if (low high)i = lo

4、w;j = high;t = alow;while (ij)j-;if (ij)ai = aj;while (ij & aiv=t) i+；if (ij)s;J-;ai = t;quick_sort(a,lowj-1);quick_sort(a，i+1,high);_int num,i;:闻 scanf(%d,&num); if(num=0) return 0; for(i=0;inum;i+) ;quick_sort(sort,0,num-1); for(i=0;i:int t, k, j;t = *(x+s);k = s;j = 2*k + 1;w”if (jn-1 & *(x+j) *(

5、x+j+1)if (tv*(x+j) k = j；j = 2*k + 1;elsebreak;void heap_sort(int *x, int n) int i, k, t;int *p;:sift(x,n,i);t = *(x+0);*(x+0) = *(x+k);*(x+k) = t;Z;int *p, i, aMAX,num;:啣P = a;scanf(%d,&num);if(num=0) return 0;for (i=0; ivnum; i+) scanf(%d,p+);P = a;heap_sort(p,num);一if(i=num-1)printf(%d,ai);elsepr

6、intf(n);return 0;问题B：整数排序二时间限制:20 Sec内存限制:128 MB题目描述在完成了任务2的第一个热身题后，很多同学觉得不过瘾，那就用同样 的题目让大家再交一次原来已经AC的程序，看是什么样的结果，应该 怎样应对？题目跟第一个热身题是一样的（但我已经大幅增加了测试数据），还是 要求将一个杂乱无序的整数序列，按照从小到大的顺序排列并输出.输入测试数据不止一组，每组测试数据：1）先输入无序序列的整数个数n； （n不超过1000000）2）然后连续输入n个整数；若n的值输入为0值，则输入结束.输出与每组输入的测试数据相对应，输出其按从小到大排好序后的整数序列.注意：每组输

7、出占一行.样例输入109 8 7 6 5 4 3 2 1 -1588 77 66 55 330样例输出-1 1 2 3 4 5 6 7 8 933 55 66 77 88提示本题测试对第10章“内部排序”的理解程度。但要考虑算法的优化及排序方法的选择（排序速度要快才行）。警告：目的是让大家熟悉内部排序的各种算法，因此禁止调用sort或qsort等函数！不改正 者降最终成绩等级.#define MAX 1000000#includevoid sift(int *x, intn, int s)int t, k, j;t = *(x+s);k = s;j = 2*k + 1;while (jn)if

8、(jn-1 & *(x+j) *(x+j+1) j+;if (t=0; i-)sift(x,n,i);for (k=n-1; k=1; k-)t = *(x+0);*(x+0) = *(x+k);*(x+k) = t;sift(x,k,0);int main()int *p, i, aMAX,num;while(1)p = a; scanf(%d,&num);if(num=0) return 0; for (i=0; inum; i+) scanf(%d,p+);p = a; heap_sort(p,num);for(i=0;inum;i+)if(i=num-1)printf(%d,ai);e

9、lse printf(%d ,ai);printf(n);return 0;问题C:时间复杂度的估算时间限制：1 Sec内存限制：128 MB题目描述在数据结构里面，时间复杂度是决定算法效率的一项重要指标，常见的时间复杂度格式有三种：1、O(n)2、O(lg(n)3、O(sqrt(n)一个算法往往有多种解法，每种解法的复杂度由上述常见的的复杂度组合成，例如排序的两种算法：1、快速排序：时间复杂度为O(n*lg(n)2、冒泡排序：时间复杂度为O(n*n)现在先给定n的值，然后输入一个值m,随后输入m行数据表示有 m个算法的复杂度。请确定这些复杂度是否会超时。若复杂度计算结果 大于10000000

10、0,则为超时(TLE)，否则输出计算的复杂度，输出的结果 保留两位小数。(lg(n)表示求以2为底数的n的对数)输入第一行输入n (1n100000OO), m(1m却中n为表示问题规模 的数，m为算法复杂度的个数。接下来m行，每行为一个串，每个串都包含0()，其中，字符O 后的括号里面的字符串保证仅由n,lg(n),sqrt(n),*组成并且合法。女口 sample input 所示。注意：lg()或sqrt()中只会出现字符n，不会再嵌套lg()或 sqrt()。如 果想做得难一点，可以去做编号为1049的题，1049题要考虑嵌套。输出对于每个串，若计算出来的复杂度大于100000000，

11、则输出TLE,否则输出该复 杂度的计算结果。样例输入10000 5O(n*n)O(n*n*n)O(sqrt(n)O(lg(n)O(n*lg(n)样例输出100000000.00TLE100.0013.29132877.12提示本题主要测试三个方面：1) 对于时间复杂度的理解。2) 字符串处理及数组的合理使用。3) 编码能力。#include#include#define MAX 100int main()_NUM;int N_NUM, L_NUM,int num;char stringMAX;double s;int i,p,n;while(scanf(%d %d,&n,&num)!=EOF)

12、for(s=1.0,N_NUM=0,L_NUM=0,S_NUM=0,p=0;pnum;p+)scanf(%s,string);s=1.0;N_NUM=0;L_NUM=0;S_NUM=0;for( i=2 ; stringi!=0; i+ )if(stringi=n)N_NUM+;if(stringi=l)L_NUM+;i=i+5;if(stringi=s)S_NUM+;i=i+7;for(i=0;iN_NUM;i+)s=s*n;for(i=0;iL_NUM;i+)s=s*(log(n)/log(2.0);for(i=0;i100000000)printf(TLEn);elseprintf(%.

13、2fn,s);问题D：车站调度时间限制：1 Sec内存限制：128 MB题目描述有顺序排列的1,2, 3,.,n节车厢在入站口等待调度。车站设置了一个栈 作为缓冲，这样的话只可能进行下列两个操作之一：(1) 如果还有车厢在入站口，将最前面的入栈缓冲(2) 将栈顶的车厢驶出车站给定一个1至n的排列，问其作为出站序列是否合法。 注意：入站顺序为1,2, 3,.,n，即1先入栈，n最后入栈。输入输入包含若干测试用例。每一个测试用例由多行组成。第一行是两 个整数n (l=n = 100)和m, n表示入站序列为1至n。m表示随后 有m行出站序列。当n, m均为0时表示输入结束。输出对应每一个出站序列，

14、合法则输出一行YES,否则输出一行NO。样例输入3 61 2 31 3 22 1 32 3 13 1 23 2 10 0样例输出YESYESYESYESNOYES提示参见习题集p21题3.1。本题主要测试对栈的理解及灵活运用。解本题推荐采用模拟入栈出栈的方式，以 训练对栈的运用熟练程度。当然也有其它方法，如推导出规律（出栈序列中存在 “大小中,，的组合是不行的）后编程求解。#include#define MAX 100#define SIZE 100int clear(int a,int p)int i;for(i=0;ip-1;i+)if(aiai+1)return 0;return 1;i

15、nt Judge(int a,int num)int judgeSIZE;int p;int i,k,j;for(i=0;inum-2;i+)for(k=i+1,p=0;kak)judgep+=ak;if(clear(judge,p)continue;elseprintf(NOn);return -1;printf(YESn);return 0;int main()int num,time;int aMAX;int i,j;while(1)scanf(%d %d,&num,&time);if(num=0 & time=0) return 0;for(i=0;itime;i+)for(j=0;j

16、num;j+)scanf(%d,&aj);Judge(a,num);return 0;问题 E: Acmers Love AC时间限制：1 Sec内存限制：128 MB题目描述We hate WA! We hate TLE! We hate RE! We hate PE! The only thingwe love is AC!Because we are ACMers! Now we give you a task that you should find how many stringsAcmersLoveAc are there in a string that we input.输入T

17、he input contains several testcases. Each testcase consists of one string(only contains capital letter and Lowercase letter) which is at most 100 characters. Input is terminated by EOF.输出For each testcase output, print an integer which stands for that how many stringsAcmersLoveAc are there in the in

18、put string.样例输入IKnowAcmersLoveAcAcmersDontLoveAcAcmersLoveAcAndAcmersLoveAc样例输出102提示本题是今天的热身题，主要测试对字符串的处理.#include #include#define MAX 100#define SIZE 13int Equals(char a)char strSIZE=AcmersLoveAc;return strcmp(str,a);int NumofAC(char a,int num)int i,j,k=0,p;char bSIZE;for(i=0,j=0;i+SIZE-2num;i+)if(

19、ai=A)p=i;for(j=0;jSIZE-1;)bj+=ap+;bj=0;if(Equals(b)=0)k+;return k;int main()int num;char strMAX;while(scanf(%s,str)!=EOF)for(num=0;strnum!=0;num+);printf(%dn,NumofAC(str,num);return 0;问题F:二叉树遍历时间限制：1 Sec内存限制：128 MB题目描述对于二叉树T，可以有先序遍历、中序遍历和后序遍历三种遍历方式。 我们知道，任意给定一颗二叉树的两种遍历方式，就可以唯一确定该树。 现在我们要求给出一棵二叉树的先序遍

20、历序列和中序遍历序列，输出它 的广度优先遍历序列。输入第一行为一个整数t (OvtvlO)，表示测试用例个数。以下t行，每行输入 一个测试用例，包含两个字符序列sl和s2,其中sl为一棵二叉树的先序遍历序 列，s2为中序遍历序列。sl和s2之间用一个空格分隔。序列只包含大写字母， 并且每个字母最多只会出现一次。输出为每个测试用例单独一行输出广度优先遍历序列。样例输入2DBACEGF ABCDEFGBCAD CBAD样例输出DBEACGFBCAD提示本题主要测试对二叉树遍历的理解.#include #include#include#define SIZE 150#define MAX 150ty

21、pedef struct BiTreechar data;struct BiTree *lchild,*rchild;BiTree;BiTree *CreateBT(char *pre,char *in,int n)BiTree *s;char *p;intk;if(ndata=*pre;for(p=in;plchild=CreateBT(pre+1,in,k); s-rchild=CreateBT(pre+k+1,p+1,n-k-1); return s;void BFS(BiTree *p)BiTree *queueMAX;int front=-1,rear=-1;front=(front

22、+1)%MAX;queuefront=p;while(front!=rear)rear=(rear+1)%MAX;p=queuerear;printf(%c,p-data);if(p-lchild!=NULL)front=(front+1)%MAX;queuefront=p-lchild;if(p-rchild!=NULL)front=(front+1)%MAX;queuefront=p-rchild;printf(n);int main()int t,i,j;char str1SIZE,str2SIZE;char *p,*q;BiTree *k;scanf(%d,&t);for(i=0;i#

23、include vtime.h#include vstdlib.hint a8=0,l,2,4,5,6,7,9;int main()int count=1000000;设置欲生成的测试数据个数int n,i;int weishu=O;int num=0;freopen(c:10.in,w,stdout);srand(time(NULL);while(count-)num=0;n=rand()%7+1;num=num*10+an;第1位数字不为0,单独算 weishu=rand()%9+1;随机确定测试数据的位数for(i=2;iv=weishu;i+)生成完整的测试数据，避免用数字3和8n=r

24、and()%8;num=num*10+an;printf(On);return 0;#include #define SIZE 9intsSIZE=1,2,36,488,5904,67232,737856,7902848,83222784;intkSIZE=1,10,100,1000,10000,100000,1000000,10000000,100000000;int Judge(int num,int p,int j)inti;if(num03 & num08)p=p-2;for(i=1;ij;i+)if(numi3 & numi8)p=p-(numi-2)*si-2*ki;return

25、p;int main()int n,temp,i;int numSIZE;while(1)scanf(%d,&n);if(n=0) return 0;temp=n;i=0;donumi=temp%10;temp=temp/10;i+;while(temp0);printf(%d: %dn,n,Judge(num,n,i);问题I:简单查找时间限制：3 Sec内存限制:22 MB题目描述给定一个集合，查找元素是否在集合中出现。输入每个测试用例由多行组成，第一行是两个整数n和m，这2个数的取值在1到3 000 000之间。自第二行起一共有n+m个整数，其中前面n个整数代表集合的元素， 随后的m个整

26、数是待查询的数。n+m个整数的取值在范围1到10 000 000之间。输出对于每个待查询的数，如果在集合中则输出yes,否则输出no.样例输入5 345 56 23 6 56633 66 63 22934 235 555555 230 0样例输出nonoyesyesno提示是问题1073的加强版，写算法时，注意内存分配及时间效率。数组请定义全局数组.#include#includeusing namespace std;#include#define SIZE 3000000int aSIZE;int main()int m,n,i,j,k;int low,high,mid;while(1)s

27、canf(%d %d,&n,&m);if(n=0 & m=0) return 0;for(i=0;in;i+) scanf(%d,&ai);sort(a,a+n);for(j=0;jm;j+)scanf(%d,&k);low=0,high=n-1;while(lowk)high=mid-1;elselow=mid+1;if(lowhigh)printf(non);return 0;问题J:赫夫曼编码时间限制：1 Sec内存限制：128 MB题目描述赫夫曼编码能够产生最短的报文。以报文“ABCDABCDABCABDABAA” 为例，A编为0, B对应10, C对应110, D对应111,整体的报

28、文长 度为35位二进制。相比于定长的ASCII码,压缩比达到了 18*8/35=4.1。输入输入有一系列的字符串组成，每个字符串占据一行。字符串仅包含大写 字母和下划线。字符串“END”表示处理结束，不应对其处理。输出对每一个字符串，输出其ASCII编码的比特位长度，赫夫曼编码的比特 位长度，以及二者之比，精确到小数点后一位。样例输入ABCDABCDABCABDABAAAAAAAAAAAAAAAAAAAAEND样例输出144 35 4.1144 18 8.0提示#include vstdioh#includevstringh#define N 100#define MAX 1000#defin

29、e OK 1typedef struct /huffman 节点char data;int weight;/权值int parent;/记录父结点下标int lchild;/左孩子int rchild;/右孩子HTNode;int CreateHT(HTNode ht，int n)/构造 huffman 树的代码没有一点错误int i,k,lnode,rnode;int min1,min2;for(i=0;i2*n-1/*一共 2*n-1 个节点 */;i+)hti.parent=hti.lchild=hti.rchild=-1;/*初 始化，所有节点的相关域为-1*/for(i=n;i2*n

30、-1;i+)min1=min2=32767;lnode=rnode=-1;/lnode和 rnode为最小权重的两个节点的位置for(k=0;kv=i-1;k+)if(htk.parent=-1)/只在尚未构造二叉树的结点中查找if(htkweightvmin1)在节点中找到两个最小的,mini和min2记录下标min2=mini;rnode=lnode;min1=htkweight;lnode=k;/记录下最小权重的下标else if(htk.weightvmin2)min2=htk.weight;rnode=k;htlnode.parent=i;htrnode.parent=i;/更 新父

31、结点以及子节点的下标htiweight=htlnodeweight+htrnodeweight;htilchild=lnode;hti rchild=rnode;return OK;int AddNum(HTNode ht,int hcd,int k)int if;if(k=1)结点分两种情况，一种是只有一个结点hcd0=1;return 0;else/另一种是大于等于两个结点 for(i=0;ivk;i+)hcdi=0;f=htiparent;while(f!=-1)/向上回溯寻找父结点,直至找到整棵树的根节点hcdi+;/父结点不为空，那数目就自增1 (Huffman编码长度增1)f=ht

32、f.parent; return OK;int main()char str1MAX;HTNode nodeMAX;int hcdMAX;/用于记录每个编码的长度int ij,k,m;float s;whilek=0;scanf(%s,str1);if(strcmp(str1,END)=0) continue;for(i=0;str1i!=O;i+)nodeiweight=0;for(j=0;j2:2”表示顶点1至顶点2的路径长度为2；2）如果不存在路径，则输出No Path。如“1-2:No Path”。样例输入3,50,1,41,0,61,2,20,2,112,0,3样例输出0-1:40-

33、2:61- 0:51-2:22- 0:32-1:7提示数据结构（C语言版）算法7.16最短路径Floyd算法#include #include#define MAX_NAME 5typedef int VRType;#define OK 1#define FALSE 0#define TRUE 1#define INFINITY 100000#define MAX_VERTEX_NUM 20typedef int DistancMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structint arcsMAX_VERTEX_NUMMAX_VERTEX_NU

34、M;int vexnum,arcnum;MGraph;int CreateDN(MGraph *G)int i,j,k,b;scanf(%d,%d,&(*G).vexnum,&(*G).arcnum);for(i=0;i(*G).vexnum;+i)for(j=0;j(*G).vexnum;+j)(*G).arcsij=INFINITY;for(k=0;k(*G).arcnum;k+)scanf(%d,%d,%d,&i,&j,&b);(*G).arcsij=b;return OK;void ShortestPath_FLOYD(MGraph G,DistancMatrix *D)int u,v

35、,w;for(v=0;vG.vexnum;v+)for(w=0;wG.vexnum;w+)(*D)vw=G.arcsvw;for(u=0;uG.vexnum;u+)for(v=0;vG.vexnum;v+)for(w=0;wG.vexnum;w+)if(*D)vu+(*D)uw(*D)vw)(*D)vw=(*D)vu+(*D)uw;int main()MGraph g;int i,j;DistancMatrix d;CreateDN(&g);for(i=0;ig.vexnum;i+)g.arcsii=0;ShortestPath_FLOYD(g,&d);for(i=0;ig.vexnum;i+

36、)for(j=0;j=g.vexnum)break;if(dij=100000)printf(%d-%d:No Pathn,i,j);elseprintf(%d-%d:%dn,i,j,dij);return 0;问题L:中国象棋中的跳马问题时间限制:2 Sec内存限制：128 MB题目描述现在棋盘的大小不一定，由p, q给出，并且在棋盘中将出现障碍物邙限 制马的行动，与象棋走法相同）输入第一行输入n表示有n组测试数据。每组测试数据第一行输入2个整数p,q，表示棋盘的大小（1=p,q=100）。每组测试数据第二行输入4个整数，表示马的起点位置与终点位置。（位 置的取值范围同p,q）第三行输入m表

37、示图中有多少障碍。接着跟着m行，表示障碍的坐标。输出马从起点走到终点所需的最小步数。如果马走不到终点，则输入“can not reach!”样例输入29 101 1 2 309 101 1 2 381 22 23 33 41 43 22 41 3样例输出1can not reach!提示此题是一个搜索题，可用DFS或BFS，建议选择BFS（广搜）。一开始 把马的起始点加入队列，然后用广搜的思想把此点能到达的其他点加入 队列，这里需要一个数组用来记录此点在之前是否已经加入队列，如果 加入过队列当中，就不需要再加入了，直到队列里的元素为空，或者搜 索到了终点，搜索即停止，然后输出相应答案即可。#i

38、nclude#define MAX 150#define SIZE 10201#define OK 1/马下一步最多能跳的地方的个数#define M 8 /马可能跳的位置的相对横纵坐标,上、右、下、左 int MovexM = -1,1, 2, 2, 1,-1, -2,-2;int MoveyM = 2,2, 1,-1, -2,-2, -1,1;/马跳的时候最多遇到的障碍数#define B 4 /马的障碍的位置的相对总横坐标，上、右、下、左 int BarxB = 0,1,0,-1;int BaryB = 1,0,-1,0;typedef structint step;/记录步数int f

39、lag;/标记Chessboard;/棋盘类型typedef structint lnum;int rnum;/记录元素下标Queue;/队列类型Queue queueSIZE;/队列int reaijfront;/队列指针Chessboard boardMAXMAX;int a,b,c,d,row,line;Z起点，终点坐标以及行列值int BFS()int x0,y0;int mx,my,bx,by;int i;rear=-1;front=-1;/队列指针初始化 boardabstep=0;/起点的步数记为0 boardab.flag=1;/起点标记已经进过队列rear+;queuerea

40、r.lnum=a;queuerear rnum=b;/起 点先进队列while(front!=rear)/队列不为空front+;x0=queuefrontlnum;yO=queuefrontrnum;/出队列if(x0=c & y0=d) return OK;/找到了终点就停止搜索 for(i=0;ivM;i+)m=8共有八个地方可以跳/算出值，利用该值来判断向该方向跳是否有障碍物阻碍 bx = x0+Barxi/2;by = y0+Baryi/2;/用来判断是否有障碍物/算出值，利用该值来判断向该方向上日字的端点处是否有障碍物或已走过/即下一位置的坐标mx = x0 + Movexi;my

41、 = y0 + Moveyi;if(boardbxbyflag!=-1)if(mx0&mx0&my=line& !boardmxmyflag)/不能越界，boardmxmy.flag必为 0rear+;queuerearlnum=mx;queuerearrnum=my;/进队列 boardmxmy|flag=1;/标记为已经走过 boardmxmystep=boardx0yOstep+1;/路径值 是其根部的路径值加1/if/if/for/whilereturn 0;int main()int n,m,e,f;int k,i,j;scanf(%d,&n);/一共n组测试数据for(k=0;kn;k+)scanf(%d %d,&row,&line);/输入棋盘大小行列for(i=1;i=row;i+)for(j=1;j=line;j+)boardij.flag=0;/初始化，全部标记为0scanf(%d %d %d %d,&a,&b,&c,&d);瀚入起点终点坐标 值scanf(%d,&m);/m 个障碍for(i=0;im;i+)scanf(%d %d,&e,&f);boardef.flag=-1;/障碍 点标记为-1if(BFS()printf(%dn,boardcd.step);else printf(can not reach!n);return 0;