『壹』 noip初賽試題 c語言
第十屆全國青少年信息學奧林匹克聯賽初賽試題
（ 普及組 C 語言 二小時完成 ）
●● 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 ●●
一．選擇一個正確答案代碼（A/B/C/D/E）,填入每題的括弧內 (每題1.5分, 共30分)
1. 美籍匈牙利數學家馮·諾依曼對計算機科學發展所做出的貢獻是（ ）。
A. 提出理想計算機的數學模型，成為計算機科學的理論基礎。
B. 是世界上第一個編寫計算機程序的人。
C. 提出存儲程序工作原理，並設計出第一台具有存儲程序功能的計算機EDVAC。
D. 採用集成電路作為計算機的主要功能部件。
E. 指出計算機性能將以每兩年翻一番的速度向前發展。
2. 下列哪個不是CPU（中央處理單元）（ ）。
A. Intel Itanium B. DDR SDRAM C. AMD Athlon64
D. AMD Opteron E. IBM Power 5
3. 下列網路上常用的名字縮寫對應的中文解釋錯誤的是（ ）。
A. WWW（World Wide Web）：萬維網。
B. URL（Uniform Resource Locator）：統一資源定位器。
C. HTTP（Hypertext Transfer Protocol）：超文本傳輸協議。
D. FTP（File Transfer Protocol）：快速傳輸協議。
E. TCP（Transfer Control Protocol）：傳輸控制協議。
4. 下面哪個部件對於個人桌面電腦的正常運行不是必需的（ ）。
A. CPU B. 圖形卡（顯卡） C. 光碟機 D. 主板 E. 內存
5. 下列哪個軟體屬於操作系統軟體（ ）。
A. Microsoft Word B. 金山詞霸 C. Foxmail D. WinRAR E. Red Hat Linux
6. 下列哪個不是計算機的存儲設備（ ）。
A. 文件管理器 B. 內存 C. 高速緩存 D. 硬碟 E. U盤
7. 下列說法中錯誤的是（ ）。
A. CPU的基本功能就是執行指令。
B. CPU訪問內存的速度快於訪問高速緩存的速度。
C. CPU的主頻是指CPU在1秒內完成的指令周期數。
D. 在一台計算機內部，一個內存地址編碼對應唯一的一個內存單元。
E. 數據匯流排的寬度決定了一次傳遞數據量的大小，是影響計算機性能的因素之一。
8. 彩色顯示器所顯示的五彩斑斕的色彩，是由紅色、藍色和（ ）色混合而成的。
A. 紫 B. 白 C. 黑 D. 綠 E. 橙
9. 用靜電吸附墨粉後轉移到紙張上，是哪種輸出設備的工作方式（ ）。
A. 針式列印機 B. 噴墨列印機 C. 激光列印機 D. 筆式繪圖儀 E. 噴墨繪圖儀
10. 一台計算機如果要利用電話線上網，就必須配置能夠對數字信號和模擬信號進行相互轉換的設備，這種設備是（ ）。
A. 數據機 B. 路由器 C. 網卡 D. 網關 E. 網橋
11. 下列哪個不是資料庫軟體的名稱（ ）。
A. MySQL B. SQL Server C. Oracle D. 金山影霸 E. Foxpro
12. 下列哪個程序設計語言不支持面向對象程序設計方法（ ）。
A. C++ B. Object Pascal C. C D. Smalltalk E. Java
13. 由3個a，1個b和2個c構成的所有字元串中，包含子串「abc」的共有（ ）個。
A. 20 B. 8 C. 16 D. 12 E. 24
14. 某個車站呈狹長形，寬度只能容下一台車，並且只有一個出入口。已知某時刻該車站狀態為空，從這一時刻開始的出入記錄為：「進，出，進，進，出，進，進，進，出，出，進，出」。假設車輛入站的順序為1，2，3，……，則車輛出站的順序為（ ）。
A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 3, 5, 4, 6 D. 1, 3, 5, 6, 7 E. 1, 3, 6, 5, 7
15. 二叉樹T，已知其前序遍歷序列為1 2 4 3 5 7 6，中序遍歷序列為4 2 1 5 7 3 6，則其後序遍歷序列為（ ）。
A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 C. 4 2 7 5 3 6 1 D. 4 7 2 3 5 6 1 E. 4 5 2 6 3 7 1
16. 滿二叉樹的葉結點個數為N，則它的結點總數為（ ）。
A. N B. 2 * N C. 2 * N – 1 D. 2 * N + 1 E. 2N – 1
17. 十進制數2004等值於八進制數（ ）。
A. 3077 B. 3724 C. 2766 D. 4002 E. 3755
18. (2004)10 + (32)16的結果是（ ）。
A. (2036)10 B. (2054)16 C. (4006)10 D. (100000000110)2 E. (2036)16
19. 在下圖中，從頂點（ ）出發存在一條路徑可以遍歷圖中的每條邊一次，而且僅遍歷一次。
A. A點 B. B點 C. C點 D. D點 E. E點
20. 某大學計算機專業的必修課及其先修課程如下表所示：
課程代號 C0 C1 C2 C3 C4 C5 C6 C7
課程名稱 高等數學 程序設計語言 離散數學 數據結構 編譯技術 操作系統 普通物理 計算機原理
先修課程 C0, C1 C1, C2 C3 C3, C7 C0 C6
請你判斷下列課程安排方案哪個是不合理的（ ）。
A. C0, C6, C7, C1, C2, C3, C4, C5 B. C0, C1, C2, C3, C4, C6, C7, C5
C. C0, C1, C6, C7, C2, C3, C4, C5 D. C0, C1, C6, C7, C5, C2, C3, C4
E. C0, C1, C2, C3, C6, C7, C5, C4
二．問題求解 （每題5分，共10分）
1. 一個傢具公司生產桌子和椅子。現在有113個單位的木材。每張桌子要使用20個單位的木材，售價是30元；每張椅子要使用16個單位的木材，售價是20元。使用已有的木材生產桌椅（不一定要把木材用光），最多可以賣 元錢。
2. 75名兒童到游樂場去玩。他們可以騎旋轉木馬，坐滑行鐵道，乘宇宙飛船。已知其中20人這三種東西都玩過，55人至少玩過其中的兩種。若每樣乘坐一次的費用是5元，游樂場總共收入700，可知有 名兒童沒有玩過其中任何一種。
三．閱讀程序 （每題8分，共32分）
1．#include <stdio.h>
int main(){
int a = 79, b = 34, c = 57, d = 0, e = -1;
if (a < c || b > c) d = d + e;
else if (d + 10 < e) d = e + 10;
else d = e - a;
printf("%d\n", d);
return 0;
}
輸出： 。
2．#include <stdio.h>
int main(){
int i, j;
char str1[] = "pig-is-stupid";
char str2[] = "clever";
str1[0] = 'd'; str1[1] = 'o';
for (i = 7, j = 0; j < 6; i++, j++)
str1[i] = str2[j];
printf("%s\n", str1);
return 0;
}
輸出： 。
3．#include <stdio.h>
int main(){
int u[4], a, b, c, x, y, z;
scanf("%d %d %d %d",&(u[0]), &(u[1]), &(u[2]), &(u[3]));
a = u[0] + u[1] + u[2] + u[3] - 5;
b = u[0] * (u[1] - u[2] / u[3] + 8);
c = u[0] * u[1] / u[2] * u[3];
x = (a + b + 2) * 3 - u[(c + 3) % 4];
y = (c * 100 - 13) / a / (u[b % 3] * 5);
if ((x + y) % 2 == 0) z = (a + b + c + x + y) / 2;
z = (a + b + c – x - y) * 2;
printf("%d\n", x + y - z);
return 0;
}
輸入：2 5 7 4
輸出： 。
4．#include <stdio.h>
char c[3][200];
int s[10], m, n;
void numara(){
int i, j, cod, nr;
for (j = 0; j < n; j++){
nr = 0; cod = 1;
for (i = 0; i < m; i++){
if (c[i][j] == '1'){
if (!cod){cod = 1; s[nr]++; nr = 0;}
}
else{
if (cod){nr = 1; cod = 0;}
else nr++;
}
}
if (!cod) s[nr]++;
}
}
int main(){
int i;
scanf("%d %d\n", &m, &n);
for (i = 0; i < m; i++) gets(c[i]);
numara();
for (i = 1; i <= m; i++)
if (s[i] != 0) printf("%d %d ", i, s[i]);
return 0;
}
輸入：
3 10
1110000111
1100001111
1000000011
輸出： 。
四、完善程序 (前4空，每空2分，後5空，每空4分，共28分)
1．三角形內切圓的面積
題目描述:
給出三角形三邊的邊長，求此三角形內切圓（如下圖所示，三角形的內切圓是和三角形三邊都相切的圓）的面積。
輸入:
三個正實數a、b、c（滿足a+b>c，b+c>a，c+a>b）, 表示三角形三邊的邊長。
輸出:
三角形內切圓的面積，結果四捨五入到小數點後面2位。
輸入樣例:
3 4 5
輸出樣例:
3.14
程序：
#include <stdio.h>
#include <math.h>
int main(){
float a, b, c, r, s, t;
scanf("%f %f %f", &a, &b, &c);
s = ( ① ) / 2;
t = ② (s * (s - a) * (s - b) * (s - c));
r = t / s;
printf(" ③ \n", 3.1415927 * r * ④ );
return 0;
}
2．Joseph
題目描述:
原始的Joseph問題的描述如下：有n個人圍坐在一個圓桌周圍，把這n個人依次編號為1，…，n。從編號是1的人開始報數，數到第m個人出列，然後從出列的下一個人重新開始報數，數到第m個人又出列，…，如此反復直到所有的人全部出列為止。比如當n=6，m=5的時候，出列的順序依次是5，4，6，2，3，1。
現在的問題是：假設有k個好人和k個壞人。好人的編號的1到k，壞人的編號是k+1到2k。我們希望求出m的最小值，使得最先出列的k個人都是壞人。
輸入:
僅有的一個數字是k（0 < k <14）。
輸出:
使得最先出列的k個人都是壞人的m的最小值。
輸入樣例:
4
輸出樣例:
30
程序：
#include <stdio.h>
long k, m, begin;
int check(long remain){
long result = ( ① ) % remain;
if ( ② ){
begin = result; return 1;
}
else return 0;
}
int main(){
long i, find = 0;
scanf("%ld", &k);
m = k;
while( ③ ) {
find = 1; begin = 0;
for (i = 0; i < k; i++)
if (!check( ④ )){
find = 0; break;
}
m++;
}
printf("%ld\n", ⑤ );
return 0;
}
賽區 市 學校 姓名
========================== 密 封 線 =======================
第九屆全國青少年信息學奧林匹克聯賽初賽試題
普及組答卷紙
閱 卷 記 錄
總閱卷人 總 得 分
第 一 大 題 得 分 第二大題得分
題號 1 2 3 4 5 6 7 8 9 10 第三大題得分
得分 1) 2) 3) 4)
題號 11 12 13 14 15 16 17 18 19 20 第四大題得分
得分 (1) (2)
============================ 以下由考生填寫 ==============================
答卷部分
一. 選擇一個正確答案代碼（A/B/C/D）,填入每題的括弧內 (每題1.5分,多選無分, 共30 分)
題號 1 2 3 4 5 6 7 8 9 10
選擇
題號 11 12 13 14 15 16 17 18 19 20
選擇
二．問題解答 （每題5分，共10分）
1. 答：
2. 答：
三. 閱讀程序，並寫出程序的正確運行結果：（每題8分，共32分）
（1） 程序的運行結果是:
(2) 程序的運行結果是:
賽區 市 學校 姓名
========================== 密 封 線 =======================
（3） 程序的運行結果是:
（4）程序的運行結果是:
四.根據題意, 將程序補充完整 (前4空，每空2分，後5空，每空4分，共28分)
C 語言
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
1.
①
②
③
④
2.
①
②
③
④
⑤
第九屆全國青少年信息學奧林匹克聯賽初賽試題
普及組參考答案
一. 選擇一個正確答案代碼（A/B/C/D/E）,填入每題的括弧內 (每題1.5分,多選無分, 共30 分)
題號 1 2 3 4 5 6 7 8 9 10
選擇 C B D C E A B D C A
題號 11 12 13 14 15 16 17 18 19 20
選擇 D C D E B C B D E D
二．問題解答 （每題5分，共10分）
1. 答： 160
2. 答： 10
三. 閱讀程序，並寫出程序的正確運行結果：（每題8分，共32分）
（1）程序的運行結果是: -80
(2) 程序的運行結果是: dog-is-clever
（3）程序的運行結果是: 263
（4）程序的運行結果是: 1 4 2 1 3 3
四.根據題意, 將程序補充完整 (前4空，每空2分，後5空，每空4分，共28分)
C 語言
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
1.
① a+b+c
② sqrt
③ %.2f
④ r
2.
① begin+m-1
② result>=k (或者k<=result)
③ !find (或者 find==0)
④ 2*k-i
⑤ m-1
『貳』 第16屆NOIP初賽普及組C語言答案
CCF NOIP2010普及組（C語言）參考答案與評分標准
一、單項選擇題（共20題，每題1.5分，共計30分）
1 2 3 4 5 6 7 8 9 10
D A A D A D B D C B
11 12 13 14 15 16 17 18 19 20
D B B B B A A D C D
二、問題求解（共2題，每題5分，共計10分）
1．2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6（或22123113431213536）
2．49
三、閱讀程序寫結果（共4題，每題8分，其中第4題（1）、（2）各4分，共計32分）1．2 20 77 91
2．99 101 111
3．120 112
4．（1）1
（2）4
四、完善程序（前4空，每空2.5分，後6空，每空3分，共計28分）
（說明：以下各程序填空可能還有一些等價的寫法，各省可請本省專家審定和上機驗證，不一定上報科學委員會審查）
1．① tmp = 1
② p[j]
③ p[r] = i
④ p[j] + p[k]（或p[k] + p[j]）
⑤ 1004
2．① num <= 2（或num < 3 或num == 2）
② go(LEFT_TO_RIGHT)
③ pos[i] == LEFT（或LEFT == pos[i]）
④ time[i] + go(RIGHT_TO_LEFT)（或go(RIGHT_TO_LEFT) + time[i]）
⑤ pos[i] = LEFT
本小題中，LEFT可用1代替，LEFT_TO_RIGHT可用1代替，RIGHT_TO_LEFT可用0代替。
『叄』 C語言全國普及組競賽初賽要掌握哪些東西才能進入復賽
基本數據結構、演算法、演算法分析、基本離散數學知識
『肆』 第十五屆信息學奧賽聯賽普及組C語言初賽試題及答案
這個東西好找么？
『伍』 求試題，17屆NOIP（C語言）普及組初賽試題
一、單項選擇題（共20題，每題1.5分，共計30分。每題有且僅有一個正確選項。）
1．在二進制下，1101001 + （ ） = 1110110。
A. 1011 B. 1101 C. 1010 D. 1111
2．字元「0」的ASCII碼為48，則字元「9」的ASCII碼為（ ）。
A. 39 B. 57 C. 120 D. 視具體的計算機而定
3．一片容量為8GB的SD卡能存儲大約（ ）張大小為2MB的數碼照片。
A. 1600 B. 2000 C. 4000 D. 16000
4．摩爾定律（Moore's law）是由英特爾創始人之一戈登•摩爾（Gordon Moore）提出來的。根據摩爾定律，在過去幾十年以及在可預測的未來幾年，單塊集成電路的集成度大約每（ ）個月翻一番。
A. 1 B. 6 C. 18 D. 36
5．無向完全圖是圖中每對頂點之間都恰有一條邊的簡單圖。已知無向完全圖G有7個頂點，則它共有（ ）條邊。
A. 7 B. 21 C. 42 D. 49
6．寄存器是（ ）的重要組成部分。
A. 硬碟 B. 高速緩存 C. 內存 D. 中央處理器（CPU）
7．如果根結點的深度記為1，則一棵恰有2011個葉結點的二叉樹的深度最少是（ ）。
A. 10 B. 11 C. 12 D. 13
8. 體育課的鈴聲響了，同學們都陸續地奔向操場，按老師的要求從高到矮站成一排。每個同學按順序來到操場時，都從排尾走向排頭，找到第一個比自己高的同學，並站在他的後面。這種站隊的方法類似於（ ）演算法 。
A. 快速排序 B. 插入排序 C. 冒泡排序 D. 歸並排序
9．一個正整數在二進制下有100位，則它在十六進制下有（ ）位。
A. 7 B. 13 C. 25 D. 不能確定
10．有人認為，在個人電腦送修前，將文件放入回收站中就是已經將其刪除了。這種想法是（ ）。
A. 正確的，將文件放入回收站意味著徹底刪除、無法恢復
B. 不正確的，只有將回收站清空後，才意味著徹底刪除、無法恢復
C. 不正確的，即使將回收站清空，文件只是被標記為刪除，仍可能通過恢復軟體找回
D. 不正確的，只要在硬碟上出現過的文件，永遠不可能被徹底刪除
11．廣度優先搜索時，需要用到的數據結構是（ ）。
A. 鏈表 B. 隊列 C. 棧 D. 散列表
12．在使用高級語言編寫程序時，一般提到的「空間復雜度」中的「空間」是指（ ）。
A. 程序運行時理論上所佔的內存空間
B. 程序運行時理論上所佔的數組空間
C. 程序運行時理論上所佔的硬碟空間
D. 程序源文件理論上所佔的硬碟空間
13．在含有n個元素的雙向鏈表中查詢是否存在關鍵字為k的元素，最壞情況下運行的時間復雜度是（ ）。
A. O(1) B. O(log n) C. O(n) D. O(n log n)
14．生物特徵識別，是利用人體本身的生物特徵進行身份認證的一種技術。目前，指紋識別、虹膜識別、人臉識別等技術已廣泛應用於政府、銀行、安全防衛等領域。以下不屬於生物特徵識別技術及其應用的是（ ）。
A. 指靜脈驗證 B. 步態驗證 C. ATM機密碼驗證 D. 聲音驗證
15．現有一段文言文，要通過二進制哈夫曼編碼進行壓縮。簡單起見，假設這段文言文只由4個漢字「之」、「乎」、「者」、「也」組成，它們出現的次數分別為700、600、300、200。那麼，「也」字的編碼長度是（ ）。
A. 1 B. 2 C. 3 D. 4
16．關於匯編語言，下列說法錯誤的是（ ）。
A. 是一種與具體硬體相關的程序設計語言
B. 在編寫復雜程序時，相對於高級語言而言代碼量較大，且不易調試
C. 可以直接訪問寄存器、內存單元、以及I/O埠
D. 隨著高級語言的誕生，如今已完全被淘汰，不再使用
17．（ ）是一種選優搜索法，按選優條件向前搜索，以達到目標。當探索到某一步時，發現原先選擇並不優或達不到目標，就退回一步重新選擇。
A. 回溯法 B. 枚舉法 C. 動態規劃 D. 貪心法
18．1956年（ ）授予肖克利（William Shockley）、巴丁（John Bardeen）和布拉頓（Walter Brattain），以表彰他們對半導體的研究和晶體管效應的發現。
A. 諾貝爾物理學獎
B. 約翰•馮•諾依曼獎
C. 圖靈獎
D. 高德納獎（Donald E. Knuth Prize）
19．對一個有向圖而言，如果每個節點都存在到達其他任何節點的路徑，那麼就稱它是強連通的。例如，右圖就是一個強連通圖。事實上，在刪掉邊（ ）後，它依然是強連通的。
A. a B. b C. c D. d
20．從ENIAC到當前最先進的計算機，馮•諾依曼體系結構始終佔有重要的地位。馮•諾依曼體系結構的核心內容是（ ）。
A. 採用開關電路 B. 採用半導體器件
C. 採用存儲程序和程序控制原理 D. 採用鍵盤輸入
二、問題求解（共2題，每題5分，共計10分）
1．每份考卷都有一個8位二進制序列號。當且僅當一個序列號含有偶數個1時，它才是有效的。例如，00000000、01010011都是有效的序列號，而11111110不是。那麼，有效的序列號共有________個。
2．定義字元串的基本操作為：刪除一個字元、插入一個字元和將一個字元修改成另一個字元這三種操作。將字元串A變成字元串B的最少操作步數，稱為字元串A到字元串B的編輯距離。字元串"ABCDEFG"到字元串"BADECG"的編輯距離為________。
三、閱讀程序寫結果（共4題，每題8分，共計32分）
1.
#include<stdio.h>
int main() {
int i, n, m, ans;
scanf("%d%d", &n, &m);
i = n;
ans = 0;
while (i <= m) {
ans += i;
i++;
}
printf("%d\n", ans);
return 0;
}
輸入：10 20
輸出：_________
2．
#include <stdio.h>
#include <string.h>
#define SIZE 20
int main()
{
char map[] = "22233344455566677778889999";
char tel[SIZE];
int i;
scanf("%s", tel);
for (i = 0; i < strlen(tel); i++)
if ((tel[i] >= '0') && (tel[i] <= '9'))
printf("%c", tel[i]);
else if ((tel[i] >= 'A') && (tel[i] <= 'Z'))
printf("%c", map[tel[i] - 'A']);
return 0;
}
輸入：CCF-NOIP-2011
輸出：_________
3．
#include <stdio.h>
#include <string.h>
#define SIZE 100
int main()
{
int n, i, sum, x, a[SIZE];
scanf("%d", &n);
memset(a, 0, sizeof(a));
for (i = 1; i <= n; i++) {
scanf("%d", &x);
a[x]++;
}
i = 0;
sum = 0;
while (sum < (n / 2 + 1)) {
i++;
sum += a[i];
}
printf("%d\n", i);
return 0;
}
輸入：
11
4 5 6 6 4 3 3 2 3 2 1
輸出：_________
4．
#include <stdio.h>
int solve(int n, int m)
{
int i, sum;
if (m == 1)
return 1;
sum = 0;
for (i = 1; i < n; i++)
sum += solve(i, m - 1);
return sum;
}
int main()
{
int n, m;
scanf("%d %d", &n, &m);
printf("%d\n", solve(n, m));
return 0;
}
輸入：7 4
輸出：_________
四、完善程序（前11空，每空2分，後2空，每空3分，共計28分）
1．（子矩陣）輸入一個n1*m1的矩陣a，和n2*m2的矩陣b，問a中是否存在子矩陣和b相等。若存在，輸出所有子矩陣左上角的坐標；若不存在輸出「There is no answer」。
#include <stdio.h>
#define SIZE 50
int n1, m1, n2, m2, a[SIZE][SIZE], b[SIZE][SIZE];
int main()
{
int i, j, k1, k2, good, haveAns;
scanf("%d %d", &n1, &m1);
for (i = 1; i <= n1; i++)
for (j = 1; j <= m1; j++)
scanf("%d", &a[i][j]);
scanf("%d %d", &n2, &m2);
for (i = 1; i <= n2; i++)
for (j = 1; j <= m2; j++)
① ;
haveAns = 0;
for (i = 1; i <= n1 - n2 + 1; i++)
for (j = 1; j <= ② ; j++) {
③ ;
for (k1 = 1; k1 <= n2; k1++)
for (k2 = 1; k2 <= ④ ; k2++) {
if (a[i + k1 - 1][j + k2 - 1] != b[k1][k2])
good = 0;
}
if (good == 1) {
printf("%d %d\n", i, j);
⑤ ;
}
}
if (haveAns == 0)
printf("There is no answer\n");
return 0;
}
2．（大整數開方）輸入一個正整數n（1≤n<10100），試用二分法計算它的平方根的整數部分。
#include <stdio.h>
#include <string.h>
#define SIZE 200
typedef struct node {
int len, num[SIZE];
} hugeint;
//其中len表示大整數的位數；num[1]表示個位、num[2]表示十位，以此類推
hugeint times(hugeint a, hugeint b)
//計算大整數a和b的乘積
{
int i, j;
hugeint ans;
memset(ans.num, 0, sizeof(ans.num));
for (i = 1; i <= a.len; i++)
for (j = 1; j <= b.len; j++)
① += a.num[i] * b.num[j];
for (i = 1; i <= a.len + b.len; i++) {
ans.num[i + 1] += ans.num[i] / 10;
② ;
}
if (ans.num[a.len + b.len] > 0)
ans.len = a.len + b.len;
else
ans.len = a.len + b.len - 1;
return ans;
}
hugeint add(hugeint a, hugeint b)
//計算大整數a和b的和
{
int i;
hugeint ans;
memset(ans.num, 0, sizeof(ans.num));
if (a.len > b.len)
ans.len = a.len;
else
ans.len = b.len;
for (i = 1; i <= ans.len; i++) {
ans.num[i] += ③ ;
ans.num[i + 1] += ans.num[i] / 10;
ans.num[i] %= 10;
}
if (ans.num[ans.len + 1] > 0)
ans.len++;
return ans;
}
hugeint average(hugeint a, hugeint b)
//計算大整數a和b的平均數的整數部分
{
int i;
hugeint ans;
ans = add(a, b);
for (i = ans.len; i >= 2; i--) {
ans.num[i - 1] += ( ④ ) * 10;
ans.num[i] /= 2;
}
ans.num[1] /= 2;
if (ans.num[ans.len] == 0)
ans.len--;
return ans;
}
hugeint plustwo(hugeint a)
//計算大整數a加2後的結果
{
int i;
hugeint ans;
ans = a;
ans.num[1] += 2;
i = 1;
while ((i <= ans.len) && (ans.num[i] >= 10)) {
ans.num[i + 1] += ans.num[i] / 10;
ans.num[i] %= 10;
i++;
}
if (ans.num[ans.len + 1] > 0)
⑤ ;
return ans;
}
int over(hugeint a, hugeint b)
//若大整數a>b則返回1，否則返回0
{
int i;
if ( ⑥ )
return 0;
if (a.len > b.len)
return 1;
for (i = a.len; i >= 1; i--) {
if (a.num[i] < b.num[i])
return 0;
if (a.num[i] > b.num[i])
return 1;
}
return 0;
}
int main()
{
char s[SIZE];
int i;
hugeint target, left, middle, right;
scanf("%s", s);
memset(target.num, 0, sizeof(target.num));
target.len = strlen(s);
for (i = 1; i <= target.len; i++)
target.num[i] = s[target.len - i] - ⑦ ;
memset(left.num, 0, sizeof(left.num));
left.len = 1;
left.num[1] = 1;
right = target;
do {
middle = average(left, right);
if (over( ⑧ ) == 1)
right = middle;
else
left = middle;
} while (over(plustwo(left), right) == 0);
for (i = left.len; i >= 1; i--)
printf("%d", left.num[i]);
printf("\n");
return 0;
}
『陸』 求NOIP C語言 普及組 初賽模擬試題 急!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
信息學奧林匹克聯賽初賽模擬試題
（普及組 C語言 二小時完成）
一、選擇一個正確答案代碼（A/B/C/D/E）,填入每題的括弧內（每題1.5分，共30分）
1．在計算機科學領域，提出「程序=數據結構+演算法」的是（ ）。
A、D.Ritchie B、N.Wirth C、Von Neumann D、Alan Turing E、B.Kernighan
2．下列哪個是最早的計算機程序設計語言（ ）。
A、C++ B、Java C、FORTRAN D、PASCAL E、COBOL
3．下列軟體不是資料庫處理軟體的是（ ）。
A、DB2 B、FoxPro C、Foxmail D、Oracle E、Sybase
4．下列哪個公司是生產CPU（中央處理器）的主要公司（ ）。
A、 Seagate B、AMD C、KINGSTONE D、BENQ E、Sony
5．在微型計算機中，微處理器的主要功能是進行（ ）。
A、算術邏輯運算及全機的控制
B、邏輯運算
C、算術邏輯運算
D、算術運算
6．DRAM存儲器的中文含義是（ ）。
A、靜態隨機存儲器
B、動態只讀存儲器
C、靜態只讀存儲器
D、動態隨機存儲器
7．操作系統的主要功能是（ ）。
A、控制和管理計算機系統軟硬體資源
B、對匯編語言、高級語言和甚高級語言程序進行翻譯
C、管理用各種語言編寫的源程序
D、管理資料庫文件
8．在Windows中，將某個應用程序窗口最小化之後，該應用程序（ ）。
A、仍在後台運行 B、暫時停止運行 C、完全停止運行 D、出錯
9．網路互聯實現在更大的范圍內傳輸數據和共享資源，要解決兩個問題：一是網路之間要有通信鏈路，二是提供（ ）。
A、協議轉換功能 B、資料庫管理功能 C、安全保密功能 D、信息傳輸功能
10．Internet網是目前世界上第一大互聯網，它起源於美國，其雛形是（ ）。
A、NCFC B、CERNET C、GBNET D、ARPANET E、CSTNET
11．下列無符號數中，最小的是（ ）。
A、（11111010110）2 B、（3730）8 C、（2007）10 D、（7D9）16
12．已知集合A={1,2,3,4,5,6,7,8}，則A的不含2和4的非空子集的個數為（ ）。
A、255 B、127 C、63 D、31 E、15
13．C語言中，如果整型變數a=125，則執行操作a>>=2;之後，a的值是（ ）。
A、1000 B、123 C、127 D、31 E、32
14．對於棧來說，若進棧序列為1、2、3、4、5、6，進棧過程中可以出棧，則下列出棧序列中不可能的是。（ ）。
A、134256 B、243165 C、345621 D、145623 E、132465
15．一棵完全二叉樹的結點總數為18，其葉結點數為（ ）。
A、7個 B、8個 C、9個 D、10個 E、11個
16．設G是一個非連通無向圖，共有28條邊，則該圖至少有（ ）個頂點。
A、8 B、9 C、10 D、6
17．對於一個無向帶權圖G=（V，E），其中V={a,b,c,d,e}，E={(a,b),(a,c),(b,d),(c,d),(e,d),(c,e), (a,d),(b,e)},E中邊的權值分別為{1,4,2,5,3,1,2,3}，則其最小生成樹上各邊的權值之和為（ ）。
A、6 B、7 C、8 D、9
18．如右所示的有向無環圖，對該圖進行拓樸排序，得到
的頂點序列正確的是（ ）。
A、1,2,5,3,4,6,8,7
B、1,3,6,5,2,8,7,4
C、1,2,3,4,5,6,7,8
D、1,3,2,4,5,7,8,6
19．給出一組數據：10、18、3、4、9、13、15、2、21、9、8，將它們生成一棵二叉排序樹，所需要的關鍵碼的比較次數為（ ）。
A、25 B、24 C、23 D、22
20．對給定的整數序列（541,132,984,746,518,181,946,314,205,827）進行從小到大的排序時，採用快速排序（以中間元素518為基準）的第一趟掃描結果是（ ）。
A、（181,132,314,205,541,518,946,827,746,984）
B、（205,132,314,181,518,746,946,984,541,827）
C、（541,132,827,746,518,181,946,314,205,984）
D、（541,132,984,746,827,181,946,314,205,518）
二、問題求解（每題5分，共10分）
1．在1,2,3,4中任取2個數，同時要求這兩個數不相鄰，有3種選取方法：1,3；1,4；2,4。那麼在1～9共9個數中，任取3個數，同時要求這4個數中沒有相鄰的數，它的選取方法有 種。
2．下面一個街區，縱向街道m條，橫向街道n條，設A點坐標為(1,1)，則B點坐標為(m,n)，當中有一點C，其坐標為(i,j)。某人從A點走到對角B點，要求必須向上或向右走，則經過其中的C點的走法一共有 種。
三、閱讀程序（每題8分，共32分）
1.#include <stdio.h>
main(){
int a,b,c,x,y,z,u[4];
scanf("%d%d%d%d",&u[0],&u[1],&u[2],&u[3]);
a=u[0]+u[1]+u[2]+u[3]-8;
b=u[0]*(u[1]+u[2]/u[3]-a);
c=u[0]*u[1]/u[2]*u[3];
x=(a+b+c)*3-u[3*c/4];
y=(a*b*c-13)/(u[b/3]*5);
if ((x+y)%2==0) z=(a+b+c+x+y)/2;
else z=(a+b+c-x-y)/2;
printf("%d\n",x-y+z);
}
輸入：2 5 7 4
2.#include <stdio.h>
main(){
int hi,lo,m,n;
scanf("%d%d",&m,&n);
hi=0; lo=0;
do{
n--; lo+=m;
if (lo>=10000) { lo-=10000; hi++; }
} while (n!=0);
printf("%4d,%4d\n",hi,lo);
}
輸入：345 208
輸出：
3.#include <stdio.h>
main(){
int i,j,p,n,q,s,a[21];
scanf("%d%d%d",&p,&n,&q);
j=21;
while (n>0){
j--; a[j]=n%10; n/=10;
}
s=0;
for (i=j;i<=20;i++)
s=s*p+a[i];
printf("%d\n",s);
j=21;
while (s>0){
j--; a[j]=s%q; s/=q;
}
for (i=j;i<=20;i++)
printf("%d",a[i]);
}
輸入：7 3051 8
輸出：
4.#include <stdio.h>
#include <string.h>
main(){
int n,m,i,j;
char x,st[10],a[10][10];
scanf("%s",st);
n=strlen(st);m=n/2;
for (i=0;i<n;i++)
for (j=0;j<n;j++) a[i][j]=' ';
for (i=0;i<=m;i++)
for (j=i;j<n-i;j++){
x=st[j];
a[i][j]=a[n-i-1][n-j-1]=x;
}
for (j=n-1;j>=0;j--){
for (i=0;i<n;i++)
printf("%2c",a[i][j]);
printf("\n");
}
}
輸入：ACEGIKM
輸出：
四、完善程序（前4空每空3分，後4空，每空4分，共28分）
1、對於給定的一個正整數，從其個位數開始，每隔一位取一個數字（即取其個位、百位、萬位等數字），形成一個新的整數並輸出。例如：運行時若輸入「14251382」，則輸出的整數為「4532」。
請完善下列程序：
#include <stdio.h>
main(){
long n,num;
int i,k;
scanf(「%d」,&n);
k=1; num=0;
for (i=1;n>0;i++){
if ①
{
num=num+ ② ;
k=k*10;
}
③ ;
}
printf(「%d\n」,num);
}
2、設某城市有 n 個車站，並有 m 條公交線路連接這些車站，設這些公交車都是單向的，這 n 個車站被順序編號為0 至 n-1 。本程序，輸入該城市的公交線路數、車站個數， 以及各公交線路上的各站編號，求得從站0出發乘公交 車至站 n-1 的最少換車次數。
程序利用輸入信息構建一張有向圖 G (用鄰接矩陣 g 表示)，有向圖的頂點是車站，若有某條公交線路經 i 站能到達 j 站，就在頂點 i 到頂點 j 之間設置一條權為 1 的有向邊<i,j>。如是這樣，從站點 x 至站點 y 的最少上車次數便對應圖 G 中從點 x 至點 y 的最短路徑長度。而程序要求的換車次數就是上車次數減 1 。
程序的輸入格式：
第一行為兩個整數m和n，分別表示公交線路數和公交站數。
接下來m行數據，每一行為沿第m條公交車線路前進方向的各站編號dd（0<=dd<n），每行數字以-1結束。
請完善下面的程序：
#include <stdio.h>
#define M 20
#define N 50
int a[N+1]; /*用於存放一條線路上的各站編號*/
int g[N][N]; /*存儲對應的鄰接矩陣*/
int dist[N]; /*存儲站0到各站的最短路徑*/
int m,n;
void buildG(){
int i,j,k,sc,dd;
scanf("%d%d",&m,&n);
for (i=0; i<n; i++)
for (j=0; j<n; j++) g[i][j]=0;
for (i=0; i<m; i++){
sc=0;
while (1){
scanf("%d", &dd);
if (dd==-1) break;
if (dd>=0 && dd<n) ④ ;
}
a[sc]=-1;
for (k=1; a[k]>=0; k++)
for (j=0; j<k; j++)
g ⑤ =1;
}
}
int minLen(){
int j,k;
for (j=0; j<n; j++) dist[j]=g[0][j];
dist[0]=1;
do {
for (k=-1, j=0 ; j<n; j++)
if (dist[j] > 0 && (k == -1 || dist[j] < dist[k]))
k = j;
if (k<0 || k==n-1) break;
dist[k]=-dist[k];
for (j=1; j<n; j++)
if ( ⑥ && (dist[j]==0 || -dist[k]+1<dist[j]) )
⑦ ;
} while (1);
j = dist [n-1];
return ⑧ ;
}
main ( ){
int t;
buildG();
if ((t=minLen())<0) printf("No answer!\n");
else printf("%d\n",n-1,t);
}
參考答案
一、
1、B 2、C 3、C 4、B 5、A 6、D 7、A 8、A 9、A 10、D
11、C 12、C 13、D 14、D 15、C 16、B 17、B 18、C 19、D 20、B
二、
1、41
2、
三、
1、18
2、7,1760
3、1065
2051
4、（註：每相鄰的兩個字元之間空1格）
M A
K K C C
I I I E E E
G G G G G G G
E E E I I I
C C K K
A M
四、
1、
①(i%2==1)
②(n%10)*k
③n=n/10
2、
④a[sc++]=dd
⑤[a[j]][a[k]]
⑥dist[j]>=0 && g[k][j]==1
⑦-dist[k]+1
⑧k<0 ? -1 : j-1
『柒』 誰有歷屆全國青少年信息學奧賽試題（初賽C語言）
我也是10月20日去參賽NOIP的啊，去在
www.noi.cn
仔細找，有答案有題目
『捌』 求第十四屆信息學奧賽聯賽普及組c語言初賽試題 第三大題第4題解析 詳細點
知道前序遍歷和中序遍歷，求後序遍歷，這就是程序的目的
『玖』 推薦幾本關於C語言的學習的書
覃浩強咯 C語言程序設計
『拾』 求四川歷年NOIP C語言試題 初賽
第十二屆全國青少年信息學奧林匹克聯賽初賽試題
（ 提高組 Pascal 語言 二小時完成 ）
●● 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 ●●
一、 單項選擇題 （共 10 題，每題 1.5 分，共計 15 分。每題有且僅有一個正確答案.）。
1. 在以下各項中。（ ）不是 CPU 的組成部分。
A. 控制器 B. 運算器 C. 寄存器 D. ALU E. RAM
2. BIOS（基本輸入輸出系統）是一組固化在計算機內（ ）上一個 ROM 晶元上的程序。
A. 控制器 B. CPU C. 主板 D. 內存條 E. 硬碟
3.在下面各世界頂級的獎項中，為計算機科學與技術領域作出傑出貢獻的科學家設立的獎項是（ ）。
A. 沃爾夫獎 B. 諾貝爾獎 C. 菲爾茲獎
D. 圖靈獎 E. 南丁格爾獎
4．在編程時（使用任一種高級語言，不一定是 Pascal），如果需要從磁碟文件中輸入一個很大的二維 數組（例如 1000*1000 的 double 型數組），按行讀（即外層循環是關於行的）與按列讀（即外層循 環是關於列的）相比，在輸入效率上（ ）。
A. 沒有區別 B. 有一些區別，但機器處理速度很快，可忽略不計
C. 按行讀的方式要高一些 D. 按列讀的方式要高一些 E. 取決於數組的存儲方式。
5．在 Pascal 語言中，表達式 (21 xor 2)的值是（ ）
A. 441 B. 42 C.23 D.24 E.25
6．在 Pascal 語言中，判斷 a 不等於 0 且 b 不等於 0 的正確的條件表達式是（ ）
A. not a=0 or not b=0 B. not((a=0)and(b=0)) C. not(a=0 and b=0) D. (a<>0)or(b<>0) E. (a<>0)and (b<>0)
7．某個車站呈狹長形，寬度只能容下一台車，並且只有一個出入口。已知某時刻該車站狀態為空，從 這一時刻開始的出入記錄為：「進，出，進，進，進，出，出，進，進，進，出,出」。假設車輛入站的 順序為 1，2，3，……，則車輛出站的順序為（ ）。
A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 4, 3, 7, 6
D. 1, 4, 3, 7, 2 E. 1, 4, 3, 7, 5
8．高度為 n 的均衡的二叉樹是指：如果去掉葉結點及相應的樹枝，它應該是高度為 n-1 的滿二叉樹。在這里，樹高等於葉結點的最大深度，根結點的深度為 0，如果某個均衡的二叉樹共有 2381 個結點， 則該樹的樹高為（ ）。
A. 10 B. 11 C. 12 D. 13 E. 210 – 1
9. 與十進制數 1770.625 對應的八進制數是（ ）。由OIFans.cn收集
A. 3352.5 B. 3350.5 C. 3352.1161
D. 3350.1151 E. 前 4 個答案都不對
10．將 5 個數的序列排序，不論原先的順序如何，最少都可以通過（ ）次比較，完成從小到大的排序。
A. 6 B. 7 C. 8 D. 9 E. 10
二、 不定項選擇題 （共 10 題，每題 1.5 分，共計 15 分。每題正確答案的個數大於或等於 1。多選 或少選均不得分）。
11. 設A=B=D=true，C=E=false，以下邏輯運算表達式值為真的有（ ）。
A. ( A∧B)∨(C∧D)∨E B. (((A∧B)∨C)∧D∧E)
C. A∧(B∨C∨D∨E) D. (A∧(B∨C)) ∧D∧E
12. (2010)16 + (32)8的結果是（ ）。
A. (8234)10 B. (202A)16
C. (100000000110)2 D. (2042)16
13. 設棧S的初始狀態為空，元素a, b, c, d, e 依次入棧，以下出棧序列不可能出現的有（ ）。
A. a, b, c, e, d B. b, c, a, e, d
C. a, e, c, b, d D. d, c, e, b, a
14. 已知 6 個結點的二叉樹的先根遍歷是 1 2 3 4 5 6（數字為結點的編號，以下同），後根遍歷是
3 2 5 6 4 1，則該二叉樹的可能的中根遍歷是（ ）由OIFans.cn收集
A. 3 2 1 4 6 5 B. 3 2 1 5 4 6
C. 2 3 1 5 4 6 D. 2 3 1 4 6 5
15. 在下列各資料庫系統軟體中，以關系型資料庫為主體結構的是（ ）。
A. ACCESS B. SQL Server
C. Oracle D. Foxpro
16.在下列各軟體中，屬於 NOIP 競賽（復賽）推薦使用的語言環境有（ ）。
A. gcc/g++ B. Turbo Pascal
C. Turbo C D. free pascal
17. 以下斷電之後將不能保存數據的有（ ）。
A. 硬碟 B. ROM C. 顯存 D. RAM
18. 在下列關於計算機語言的說法中，正確的有（ ）。
A. Pascal和C都是編譯執行的高級語言
B. 高級語言程序比匯編語言程序更容易從一種計算機移植到另一種計算機上
C. C++是歷史上的第一個支持面向對象的計算機語言
D. 高級語言比匯編語言更高級，是因為它的程序的運行效率更高
19. 在下列關於計算機演算法的說法中，正確的有（ ）。
A. 一個正確的演算法至少要有一個輸入
B. 演算法的改進，在很大程度上推動了計算機科學與技術的進步由OIFans.cn收集
C. 判斷一個演算法的好壞，主要依據它在某台計算機上具體實現時的運行時間
D. 目前仍然存在許多涉及到國計民生的重大課題，還沒有找到能夠在計算機上實施的有效演算法
20. 在下列關於青少年信息學競賽的說法中，你贊成的是（ ）（本題不回答為0分，答題一律滿分）。
A. 舉行信息學競賽的目的，是為了帶動廣大青少年學科學、愛科學，為造就一大批優秀的計算機科學 與技術人才奠定良好的基礎
B. 如果競賽優勝者不能直接保送上大學，我今後就不再參與這項活動了
C. 准備競賽無非要靠題海戰術，為了取得好成績，就得拼時間、拼體力
D. 為了取得好成績，不光要看智力因素，還要看非智力因素。優秀選手應該有堅韌不拔的意志，有 嚴謹求實的作風，既要努力奮進，又要勝不驕敗不餒
三．問題求解（共 2 題，每題 5 分，共計 10 分）
1．將 2006 個人分成若干不相交的子集，每個子集至少有 3 個人，並且：
（1）在每個子集中，沒有人認識該子集的所有人。
（2）同一子集的任何 3 個人中，至少有 2 個人互不認識。
（3）對同一子集中任何 2 個不相識的人，在該子集中恰好只有 1 個人認識這兩個人。 則滿足上述條件的子集最多能有 個？
2．將邊長為 n 的正三角形每邊 n 等分，過每個分點分別做另外兩邊的平行線，得到若干個正三角形， 我們稱為小三角形。正三角形的一條通路是一條連續的折線，起點是最上面的一個小三角形，終點是最 下面一行位於中間的小三角形。在通路中，只允許由一個小三角形走到另一個與其有公共邊的且位於同 一行或下一行的小三角形，並且每個小三角形不能經過兩次或兩次以上（圖中是 n=5 時一條通路的例 子）。設 n=10，則該正三角形的不同的通路的總數為_ __。
四．閱讀程序寫結果（共 4 題，每題 8 分，共計 32 分）
1. Program ex401;
var
u,v:array[0..3] of integer;
i,x,y:integer;
begin
x:=10; y:=10;
for i:=0 to 3 do read(u[i]);
v[0]:=(u[0]+u[1]+u[2]+u[3]) div 7; v[1]:=u[0] div ((u[1]-u[2]) div u[3]); v[2]:=u[0]*u[1] div u[2]*u[3]; v[3]:=v[0]*v[1];
x:=(v[0]+v[1]+2)-u[(v[3]+3) mod 4];
if (x>10) then
y:=y+(v[2]*100-v[3]) div (u[u[0] mod 3]*5)由OIFans.cn收集
else
y:=y+20+(v[2]*100-v[3]) div (u[v[0] mod 3]*5);
writeln (x,',',y);
end. {*註：本例中，給定的輸入數據可以避免分母為 0 或下標越界。 )
輸入：9 3 9 4
輸出：
2.Program ex402;
const
m:array[0..4] of integer=(2,3,5,7,13);
var i,j:integer; t: longint; begin
for i:=0 to 4 do begin
t:=1;
for j:=1 to m[i]-1 do t:=t*2;
t:=(t*2-1)*t; write (t,' '); end;
writeln;
end.
輸出:_____
3. Program ex403;
Const NN=7; Type
Arr1=array[0..30] of char;
var s:arr1;
k,p:integer;
function fun1(s:arr1; a:char;n:integer):integer;
var j:integer; begin
j:=n;
while (a<s[j])and(j>0) do dec(j);
fun1:=j;
end;
Function fun2(s:arr1; a:char; n:integer):integer;
var j:integer; begin
j:=1;
while (a>s[j])and(j<n) do inc(j);
fun2:=j;
end;
begin
for k:=1 to NN do s[k]:=chr(ord('A')+2*k+1);
k:=fun1(s,'M',NN)+fun2(s,'M',NN);
writeln(k);
end.
輸出：
4. program ex404;
var x,x2:longint;由OIFans.cn收集
procere digit(n,m:longint);
var n2:integer;
begin
if(m>0) then begin
n2:=n mod 10;
write(n2:2);
if(m>1) then digit(n div 10,m div 10);
n2:=n mod 10; write(n2:2); end;
end;
begin
writeln('Input a number:');
readln(x);
x2:=1;
while(x2<x) do x2:=x2*10;
x2:=x2 div 10; digit(x,x2); writeln;
end.
輸入：9734526
輸出：
五．完善程序 (前 5 空，每空 2 分，後 6 空，每空 3 分，共 28 分)
1．（選排列）下面程序的功能是利用遞歸方法生成從 1 到 n(n<10)的 n 個數中取 k(1<=k<=n)個數的 全部可能的排列（不一定按升序輸出）。例如，當 n=3，k=2 時，應該輸出（每行輸出 5 個排列）：
12 13 21 23 32
31
程序：
Program ex501; Var i,n,k:integer;
a:array[1..10] of integer;
count:longint;
Procere perm2(j:integer);
var i,p,t:integer;
begin
if ① then
begin
for i:=k to n do begin inc(count);
t:=a[k]; a[k]:=a[i]; a[i]:=t;
for ② do write(a[p]:1);
write(' ');
t:=a[k];a[k]:=a[i];a[i]:=t;
if (count mod 5=0) then writeln;
end; exit; end;
for i:=j to n do begin
t:=a[j];a[j]:=a[i];a[i]:=t;由OIFans.cn收集
③ ;
t:=a[j]; ④ ;
end end; begin
writeln('Entry n,k (k<=n):'); read(n,k);
count:=0;
for i:=1 to n do a[i]:=i;
⑤ ;
end.
2．（TSP 問題的交叉運算元）TSP 問題(Traveling Salesman Problem)描述如下：給定 n 個城 市，構成一個完全圖，任何兩城市之間都有一個代價（例如路程、旅費等），現要構造遍歷所有城市的環 路，每個城市恰好經過一次，求使總代價達到最小的一條環路。
遺傳演算法是求解該問題的一個很有效的近似演算法。在該演算法中，一個個體為一條環路，其編碼方法 之一是 1 到 n 這 n 個數字的一個排列，每個數字為一個城市的編號。例如當 n=5 時，「3 4 2 1 5」 表示該方案實施的路線為 3->4->2->1->5->3。遺傳演算法的核心是通過兩個個體的交叉操作，產生兩 個新的個體。下面的程序給出了最簡單的一種交叉演算法。具體過程如下：
(1)選定中間一段作為互換段，該段的起止下標為 t1，t2，隨機生成 t1，t2 後，互換兩段。
(2)互換後，在每個新的排列中可能有重復數字，因而不能作為新個體的編碼，一般再做兩步處理：
(2.1) 將兩個互換段中，共同的數字標記為 0，表示已處理完。
(2.2) 將兩個互換段中其餘數字標記為 1，按順序將互換段外重復的數字進行替換。 例如：n=12，兩個個體分別是：
a1: 1 3 5 4 * 2 6 7 9 * 10 12 8 11
a2: 3 2 1 12 * 6 7 10 11 * 8 5 4 9
t1=5，t2=8。上述每一行中，兩個星號間的部分為互換段。假定數組的下標從 1 開始，互換後有：
a1: 1 3 5 4 * 6 7 10 11 * 10 12 8 11
a2: 3 2 1 12 * 2 6 7 9 * 8 5 4 9
然後，將數字 6,7 對應的項標記為 0，星號內數字 2,9,10,11 對應的項標記為 1，並且按順序對 應關系為:10<->2，11<->9。於是，將 a1[9]=10 替換為 a1[9]=2，將 a2[2]=2 替換為 a2[2]=10， 類似再做第 2 組替換。這樣處理後，就得到了兩個新個體：
a1: 1 3 5 4 6 7 10 11 2 12 8 9
a2: 3 10 1 12 2 6 7 9 8 5 4 11
（3）輸出兩個新個體的編碼。 程序：
program ex502;
type arr1=array[1..20] of integer;
var a1,a2,kz1,kz2:arr1; n,k,t1,t2:integer;
function rand1(k:integer):integer;
var t:integer;
begin t:=0;
while (t<2) or(t>k) do t:=random(k+1)-2; rand1:=t;
end;
procere read1(var a:arr1;m:integer);
{讀入數組元素 a[1]至 a[m]，a[0]=0，略。}
procere wrt1(var a:arr1;m:integer);
{輸出數組元素 a[1]至 a[m]，略。}
procere cross(var a1,a2:arr1;t1, t2,n:integer);由OIFans.cn收集
var i,j,t,kj:integer; begin
for i:=t1 to t2 do begin
t:=a1[i]; ① ;
end;
for i:=1 to n do
if (i<t1)or(i>t2) then begin
kz1[i]:=-1;kz2[i]:=-1;
end else
begin ② ; end;
for i:=t1 to t2 do for j:=t1 to t2 do
if(a1[i]=a2[j]) then
begin ③ ; break; end;
for i:=t1 to t2 do if(kz1[i]=1) then begin
for j:=t1 to t2 do if(kz2[j]=1) then
begin kj:=j; break; end;
for j:=1 to n do if ④ then
begin a1[j]:=a2[kj];break; end;
for j:=1 to n do if ⑤ then
begin a2[j]:=a1[i]; break; end;
kz1[i]:=0;kz2[kj]:=0;
end; end; begin
writeln('input (n>5):');
readln(n);
writeln('input array 1:'); read1(a1,n);
writeln('input array 2:'); read1(a2,n);
t1:=rand1(n-1);
repeat
t2:=rand1(n-1); until(t1<>t2); if(t1>t2) then
begin k:=t1; t1:=t2; t2:=k; end;
⑥ ;
wrt1(a1,n); wrt1(a2,n);
end.