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+)