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

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

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

3、lt;n;j+)if(aj<ak)k=j;if(i!=k)temp=ai;ai=ak;ak=temp;int main()int sortSIZE;int num,i;while(1)scanf("%d",&num);if(num=0) exit(0);for(i=0;i<num;i+)scanf("%d",&sorti);fastsort(sort,num);for(i=0;i<num;i+)if(i=num-1)printf("%d",sorti);elseprintf("%d &quo

4、t;,sorti);printf("n");return 0;快速排序版：#include<stdio.h>#define SIZE void quick_sort(int a, int low, int high) int i, j, t; if (low < high) i = low; j = high; t = alow; while (i<j) while ( i<j && aj>t) j-; if (i<j) ai = aj; i+; while (i<j && ai<=t)

5、i+; if (i<j)aj = ai; j-; ai = t; quick_sort(a,low,i-1); quick_sort(a,i+1,high); int main()int sortSIZE;int num,i;while(1)scanf("%d",&num);if(num=0) return 0;for(i=0;i<num;i+)scanf("%d",&sorti);quick_sort(sort,0,num-1);for(i=0;i<num;i+)if(i=num-1)printf("%d&q

6、uot;,sorti);elseprintf("%d ",sorti);printf("n");return 0;堆排序版：#define MAX 10000#include<stdio.h>void sift(int *x, int n, int s) int t, k, j; t = *(x+s); k = s; j = 2*k + 1; while (j<n) if (j<n-1 && *(x+j) < *(x+j+1) j+; if (t<*(x+j) *(x+k) = *(x+j); k =

7、j; j = 2*k + 1; else break; *(x+k) = t; void heap_sort(int *x, int n) int i, k, t; int *p; for (i=n/2-1; i>=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) re

8、turn 0; for (i=0; i<num; i+) scanf("%d",p+); p = a; heap_sort(p,num); for(i=0;i<num;i+) if(i=num-1) printf("%d",ai); else printf("%d ",ai); printf("n"); return 0;问题 B: 整数排序二时间限制: 20 Sec  内存限制: 128 MB题目描述在完成了任务的第一个热身题后，很多同学觉得不过瘾，那就用同样的

9、题目让大家再交一次原来已经的程序，看是什么样的结果，应该怎样应对？题目跟第一个热身题是一样的（但我已经大幅增加了测试数据），还是要求将一个杂乱无序的整数序列，按照从小到大的顺序排列并输出输入测试数据不止一组，每组测试数据：）先输入无序序列的整数个数n；(n不超过)）然后连续输入n个整数；若n的值输入为值，则输入结束输出与每组输入的测试数据相对应，输出其按从小到大排好序后的整数序列注意：每组输出占一行样例输入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章“内部排序”的理

10、解程度。但要考虑算法的优化及排序方法的选择(排序速度要快才行)。警告：目的是让大家熟悉内部排序的各种算法，因此禁止调用sort或qsort等函数！不改正者降最终成绩等级#define MAX #include<stdio.h> void sift(int *x, int n, int s) int t, k, j;  t = *(x+s);  k = s;   j = 2*k + 1;   while (j<n)    if(j<n-1 &a

11、mp;& *(x+j) < *(x+j+1) j+;   if (t<*(x+j)        *(x+k) = *(x+j);    k = j;     j = 2*k + 1;      else break;    *(x+k) = t;   void heap_sor

12、t(int *x, int n) int i, k, t; int *p;  for (i=n/2-1; i>=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 mai

13、n()  int *p, i, aMAX,num;   while(1)      p = a;     scanf("%d",&num);     if(num=0) return 0;     for (i=0; i<num; i+)      sca

14、nf("%d",p+);      p = a;     heap_sort(p,num);      for(i=0;i<num;i+)           if(i=num-1)      printf("%d"

15、;,ai);      else      printf("%d ",ai);         printf("n");     return 0;  问题 C: 时间复杂度的估算时间限制: 1 Sec  内存限制: 128 MB题目描述在

16、数据结构里面，时间复杂度是决定算法效率的一项重要指标，常见的时间复杂度格式有三种：1、O(n)2、O(lg(n)3、O(sqrt(n)一个算法往往有多种解法，每种解法的复杂度由上述常见的的复杂度组合成，例如排序的两种算法：1、 快速排序：时间复杂度为O(n*lg(n)2、冒泡排序：时间复杂度为O(n*n)现在先给定n的值，然后输入一个值m，随后输入m行数据表示有m个算法的复杂度。请确定这些复杂度是否会超时。若复杂度计算结果大于，则为超时(TLE)，否则输出计算的复杂度，输出的结果保留两位小数。( lg(n)表示求以2为底数的n的对数 )输入第一行输入n (1n), m(1m

17、100), 其中n为表示问题规模的数，m为算法复杂度的个数。接下来m行，每行为一个串，每个串都包含O( )，其中，字符'O'后的括号里面的字符串保证仅由n,lg(n),sqrt(n),*组成并且合法。如sample input所示。注意：lg()或sqrt()中只会出现字符'n'，不会再嵌套lg()或sqrt()。如果想做得难一点，可以去做编号为1049的题，1049题要考虑嵌套。输出对于每个串，若计算出来的复杂度大于，则输出TLE，否则输出该复杂度的计算结果。样例输入10000 5O(n*n)O(n*n*n)O(sqrt(n)O(lg(n)O(n*l

18、g(n)样例输出.00TLE100.0013.29.12提示本题主要测试三个方面：1）对于时间复杂度的理解。2）字符串处理及数组的合理使用。3）编码能力。#include<stdio.h>#include<math.h>#define MAX 100 int main()    int N_NUM, L_NUM, S_NUM;    int num;    char stringMAX;    doub

19、le s;    int i,p,n;     while(scanf("%d %d",&n,&num)!=EOF)         for(s=1.0,N_NUM=0,L_NUM=0,S_NUM=0,p=0;p<num;p+)             &#

20、160; scanf("%s",string);          s=1.0;          N_NUM=0;          L_NUM=0;          

21、;S_NUM=0;            for( i=2 ; stringi!='0' i+ )                 if(stringi='n')         

22、0;            N_NUM+;            i+;                    if(stringi='l')&

23、#160;                      L_NUM+;             i=i+5;            

24、        if(stringi='s')                       S_NUM+;             i=i+7;

25、                        for(i=0;i<N_NUM;i+)           s=s*n;        for(i=0;i<L_NUM;

26、i+)           s=s*(log(n)/log(2.0);       for(i=0;i<S_NUM;i+)           s=s*sqrt(n);           &#

27、160;  if(s>)          printf("TLEn");        else          printf("%.2fn",s);        &#

28、160;问题 D: 车站调度时间限制: 1 Sec  内存限制: 128 MB题目描述有顺序排列的1,2, 3,n节车厢在入站口等待调度。车站设置了一个栈作为缓冲，这样的话只可能进行下列两个操作之一：      （1）如果还有车厢在入站口，将最前面的入栈缓冲      （2）将栈顶的车厢驶出车站    给定一个1至n的排列，问其作为出站序列是否合法。注意：入站顺序为1,2, 3,n，即1先入栈.，n最后入栈

29、。输入输入包含若干测试用例。每一个测试用例由多行组成。第一行是两个整数n（1<=n <= 100）和m，n表示入站序列为1至n。m表示随后有m行出站序列。当n，m均为0时表示输入结束。输出对应每一个出站序列，合法则输出一行YES，否则输出一行NO。样例输入3 61 2 31 3 22 1 32 3 13 1 23 2 10 0样例输出YESYESYESYESNOYES提示参见习题集p21 题3.1。本题主要测试对栈的理解及灵活运用。解本题推荐采用模拟入栈出栈的方式，以训练对栈的运用熟练程度。当然也有其它方法，如推导出规律（出栈序列中存在“大小中”的组合是不行的）后编程求解。#inc

30、lude<stdio.h>#define MAX 100#define SIZE 100 int clear(int a,int p)   int i;   for(i=0;i<p-1;i+)         if(ai<ai+1)        return 0;     retur

31、n 1; int Judge(int a,int num)   int judgeSIZE;   int p;   int i,k,j;    for(i=0;i<num-2;i+)       for(k=i+1,p=0;k<num;k+)          if(ai>

32、;ak)               judgep+=ak;               if(clear(judge,p)     continue;    else    &#

33、160;           printf("NOn");         return -1;            printf("YESn"); return 0;    int ma

34、in()    int num,time;    int aMAX;    int i,j;    while(1)        scanf("%d %d",&num,&time);    if(num=0 && time=0) return 0; 

35、60;     for(i=0;i<time;i+)                  for(j=0;j<num;j+)             scanf("%d",&aj); 

36、0;           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 onl

37、y thing we love is AC!Because we are ACMers! Now we give you a task that you should find how many strings"AcmersLoveAc" are there in a string that we input.输入  The input contains several testcases. Each testcase consists of one string(only contains capital letter and Lowercase letter)

38、 which is at most 100 characters. Input is terminated by EOF.输出 For each testcase output, print an integer which stands for that how many strings"AcmersLoveAc" are there in the inputstring.样例输入IKnowAcmersLoveAcAcmersDontLoveAcAcmersLoveAcAndAcmersLoveAc样例输出102提示本题是今天的热身题，主要测试对字符串的处理#i

39、nclude <stdio.h>#include<string.h>#define MAX 100#define SIZE 13 int Equals(char a)    char strSIZE="AcmersLoveAc"    return strcmp(str,a); int NumofAC(char a,int num)    int i,j,k=0,p;    

40、;char bSIZE;    for(i=0,j=0;i+SIZE-2<num;i+)            if(ai='A')                    p=i;   &

41、#160;        for(j=0;j<SIZE-1;)                          bj+=ap+;           &

42、#160;             bj='0'            if(Equals(b)=0)                  k+; 

43、;               return k; int main()    int num;    char strMAX;    while(scanf("%s",str)!=EOF)         &

44、#160;       for(num=0;strnum!='0'num+);      printf("%dn",NumofAC(str,num);        return 0; 问题 F: 二叉树遍历时间限制: 1 Sec  内存限制: 128 MB题目描述对于二叉树T，可以有先序遍历、中序遍历

45、和后序遍历三种遍历方式。我们知道，任意给定一颗二叉树的两种遍历方式，就可以唯一确定该树。现在我们要求给出一棵二叉树的先序遍历序列和中序遍历序列，输出它的广度优先遍历序列。 输入第一行为一个整数t（0<t<10），表示测试用例个数。 以下t行，每行输入一个测试用例，包含两个字符序列s1和s2，其中s1为一棵二叉树的先序遍历序列，s2为中序遍历序列。s1和s2之间用一个空格分 隔。序列只包含大写字母，并且每个字母最多只会出现一次。 输出为每个测试用例单独一行输出广度优先遍历序列。样例输入2DBACEGF ABCDEFGBCAD CBAD样例输出D

46、BEACGFBCAD提示本题主要测试对二叉树遍历的理解.#include <stdio.h>#include<malloc.h>#include<string.h>#define SIZE 150#define MAX 150 typedef struct BiTree char data; struct BiTree *lchild,*rchild;BiTree; BiTree *CreateBT(char *pre,char *in,int n)    BiTree *s;&

47、#160;   char *p;    int k;    if(n<=0) return NULL;    s=(BiTree *)malloc(sizeof(BiTree);    s->data=*pre;    for(p=in;p<in+n;p+)        

48、;    if(*p=*pre) break;        k=p-in;    s->lchild=CreateBT(pre+1,in,k);    s->rchild=CreateBT(pre+k+1,p+1,n-k-1);    return s; void BFS(BiTree *p)  BiTree *q

49、ueueMAX;  int front=-1,rear=-1;  front=(front+1)%MAX;  queuefront=p;   while(front!=rear)           rear=(rear+1)%MAX;      p=queuerear;      pri

50、ntf("%c",p->data);      if(p->lchild!=NULL)                front=(front+1)%MAX;          queuefront=p->lchild;  

51、;          if(p->rchild!=NULL)                front=(front+1)%MAX;          queuefront=p->rchild;   

52、;          printf("n"); int main()    int t,i,j;    char str1SIZE,str2SIZE;    char *p,*q;     BiTree *k;     scanf("%d"

53、,&t);     for(i=0;i<t;i+)          scanf("%s",str1);     scanf("%s",str2);     j=strlen(str1);     p=str1;   

54、;  q=str2;     k=CreateBT(p,q,j);     BFS(k);             问题 G: Faulty Odometer（非ACMer做）时间限制: 1 Sec  内存限制: 33 MB题目描述You are given a car odometer which displays

55、the miles traveled as an integer. The odometer has a defect, however: it proceeds from the digit 2 to the digit 4 and from the digit 7 to the digit 9, always skipping over the digit 3 and 8. This defect shows up in all positions (the one's, the ten's, the hundred's, etc.). For example, i

56、f the odometer displays 15229 and the car travels one mile, odometer reading changes to 15240 (instead of 15230).输入Each line of input contains a positive integer in the range 1. which represents an odometer reading. (Leading zeros will not appear in the input.) The end of input is indicated by a lin

57、e containing a single 0. You may assume that no odometer reading will contain the digit 3 and 8.输出Each line of input will produce exactly one line of output, which will contain: the odometer reading from the input, a colon, one blank space, and the actual number of miles traveled by the car. 样例

58、输入15200525015000样例输出15: 122005: 1028250: 1601500: 768: 提示数据没有超过int类型的取值范围，但要注意，消耗时间长的算法是过不了的看我用下面程序生成的测试数据至少个我写的测试数据生成程序如下:#include <stdio.h>#include <time.h>#include <stdlib.h>int a8=0,1,2,4,5,6,7,9;int main()     int count=;/设置欲生成的测试数据个数    

59、; int n,i;     int weishu=0;     int num=0;     freopen("c:10.in","w",stdout);     srand(time(NULL);     while(count-)           &

60、#160;   num=0;          n=rand()%7+1;          num=num*10+an;/第1位数字不为0，单独算          weishu=rand()%9+1;/随机确定测试数据的位数       

61、;   for(i=2;i<=weishu;i+)/生成完整的测试数据，避免用数字3和8                            n=rand()%8;            &#

62、160;     num=num*10+an;                    printf("%dn",num);          printf("0n");     return 0;#includ

63、e <stdio.h>#define SIZE 9 int sSIZE=1,2,36,488,5904,67232,;int kSIZE=1,10,100,1000,10000,; int Judge(int num,int p,int j)    int i;    if(num0>3 && num0<8)        p-;    

64、if(num0>8)        p=p-2;    for(i=1;i<j;i+)            if(numi<3)            p=p-numi*si;   

65、0;    if(numi>3 && numi<8)            p=p-(numi-1)*si-ki;        if(numi>8)            p=p-(numi-2)*si-

66、2*ki;        return p;   int main()    int n,temp,i;    int numSIZE;    while(1)            scanf("%d",&n);

67、0;       if(n=0) return 0;        temp=n;        i=0;        do             

68、0;      numi=temp%10;            temp=temp/10;            i+;        while(temp>0);    

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

70、00 000之间。输出对于每个待查询的数，如果在集合中则输出yes,否则输出no.样例输入5 345 56 23 6 56633 66 63 22934 235 555555 230 0样例输出nonoyesyesno提示是问题1073的加强版，写算法时，注意内存分配及时间效率。数组请定义全局数组#include<stdio.h>#include<iostream>using namespace std;#include<algorithm>#define SIZE  int aSIZE; int main()  &#

71、160; int m,n,i,j,k;    int low,high,mid;    while(1)            scanf("%d %d",&n,&m);        if(n=0 && m=0) return 0;  

72、      for(i=0;i<n;i+)        scanf("%d",&ai);        sort(a,a+n);        for(j=0;j<m;j+)       

73、         scanf("%d",&k);          low=0,high=n-1;          while(low<=high)          

74、60;             mid=(low+high)/2;               if(amid=k)                 

75、               printf("yesn");                 break;             

76、;                   if(amid>k)                 high=mid-1;          

77、;      else                 low=mid+1;                    if(low>high)  

78、         printf("non");                return 0; 问题 J: 赫夫曼编码时间限制: 1 Sec  内存限制: 128 MB题目描述赫夫曼编码能够产生最短的报文。以报文“ABCDABCDABCABDABAA”为例，A编为0，B对应10

79、，C对应110，D对应111，整体的报文长度为35位二进制。相比于定长的ASCII码，压缩比达到了18*8/35=4.1。输入输入有一系列的字符串组成，每个字符串占据一行。字符串仅包含大写字母和下划线。字符串“END” 表示处理结束，不应对其处理。输出对每一个字符串，输出其ASCII编码的比特位长度，赫夫曼编码的比特位长度，以及二者之比，精确到小数点后一位。样例输入ABCDABCDABCABDABAAAAAAAAAAAAAAAAAAAAEND样例输出144 35 4.1144 18 8.0提示#include <stdio.h>#include<string.h&g

80、t;#define N 100#define MAX 1000#define 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;i<2*n-1/*一共2*n-1个节点*/;i+)hti.parent=hti.lchild=hti.rchild=

81、-1;/*初始化，所有节点的相关域为-1*/for(i=n;i<2*n-1;i+)min1=min2=32767;lnode=rnode=-1;/lnode和rnode为最小权重的两个节点的位置for(k=0;k<=i-1;k+)if(htk.parent=-1)/只在尚未构造二叉树的结点中查找if(htk.weight<min1)/在节点中找到两个最小的，min1和min2记录下标min2=min1;rnode=lnode;min1=htk.weight;lnode=k;/记录下最小权重的下标else if(htk.weight<min2)min2=htk.weigh

82、t;rnode=k;htlnode.parent=i;htrnode.parent=i;/更新父结点以及子节点的下标hti.weight=htlnode.weight+htrnode.weight;hti.lchild=lnode;hti.rchild=rnode;return OK;int AddNum(HTNode ht,int hcd,int k)int i,f;if(k=1)/结点分两种情况，一种是只有一个结点hcd0=1;return 0;else/另一种是大于等于两个结点 for(i=0;i<k;i+) hcdi=0; f=hti.parent; while(f!=-1)/向

83、上回溯寻找父结点，直至找到整棵树的根节点 hcdi+;/父结点不为空，那数目就自增1（Huffman编码长度增1） f=htf.parent; return OK;int main() char str1MAX; HTNode nodeMAX;int hcdMAX;/用于记录每个编码的长度int i,j,k,m;float s;while(1) k=0; scanf("%s",str1); if(strcmp(str1,"END")=0) continue; for(i=0;str1i!='0'i+) nodei.weight=0; fo

84、r(j=0;j<k;j+)/从第一位开始搜索，如果找到了相同的字符，那么该字符权值增1 if(nodej.data=str1i) nodej.weight=nodej.weight+1; break;/找到了就不必再循环,读下一个字符 if(j=k)/没找到，就加入node数组 nodek.data=str1i; nodek.weight=nodek.weight+1; k+; /最后得到的k为字符的种类数目 m=i;/记录下i的值，i为输入的总字符的个数 CreateHT(node,k);/构建一棵Huffman树AddNum(node,hcd,k);/获取个个字符HUffman编码的

85、长度for(i=0,s=0.0;i<k;i+)s=s+hcdi*nodei.weight;/获取用Huffman编码时总字符长度printf("%d %.0f %.1fn",m*8,s,m*8/s);return 0;问题 K: 最短路径时间限制: 1 Sec  内存限制: 128 MB题目描述求带权有向图中任意2个顶点之间的最短路径。输入先输入顶点个数及边的条数；然后依次输入各条边的信息，包括起点，终点，权值。输出输出任意2点间的路径长度信息。1）如果存在路径，则输出路径长度，如“1->2:2”表示顶点1至顶点2的路径长

86、度为2；2）如果不存在路径，则输出No Path。如“1->2:No Path”。样例输入3,50,1,41,0,61,2,20,2,112,0,3样例输出0->1:40->2:61->0:51->2:22->0:32->1:7提示数据结构（C语言版）算法7.16_最短路径Floyd算法#include <stdio.h>#include<string.h>   #define MAX_NAME 5 typedef int VRType;    &#

87、160;  #define OK 1 #define FALSE 0 #define TRUE 1   #define INFINITY  #define MAX_VERTEX_NUM 20  typedef int DistancMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;     typedef struct    int arcsMAX_VERTEX_NUMMAX_VERTEX_NUM

88、;    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+)