20161、 程序設計（用C語言編程實現，并給出清楚的注釋。共9題，100分）。1. 張老師有五本不同的新書，要借給A，B，C三位同學，若每人每次只能借一本，則可以有多少種不同的借法？（10分）#include int _tmain(int argc, _TCHAR* argv)int a,b,c,i=0;for(a=0;a5;a+)for(b=0;b5;b+)for(c=0;c5;c+)if(a!=b)&(a!=c)&(b!=c)i+;printf(a: %d,b: %d,c: %dn,a,b,c);printf(Sum of the numbers: %dn,i);system(pause);return 0;2. 已知An為整數數組，試寫出實現下列算法的遞歸算法：A) 求數組的最大整數。B) 求n個整數的和。C) 求n個整數的平均值。（10分）#include int GetArrMax(int A,int n)if(n0)return 0;else if(n=1)return An-1;elsereturn (An-1GetArrMax(A,n-1)?GetArrMax(A,n-1):An-1);int GetArrSum(int A,int n)if(n0)return 0;else if(n=1)return An-1;return An-1+GetArrSum(A,n-1);int GetArrAve(int A,int n)if(n0)return 0;else if(n=1)return An-1;return (An-1+GetArrAve(A,n-1)/2;int _tmain(int argc, _TCHAR* argv)int B10=0;for(int i=0;i10;i+)Bi =1;int Max = GetArrMax(B,10);int Sum = GetArrSum(B,10);int Ave = GetArrAve(B,10);return 0;3. 設ha和hb分別是兩個非遞減有序單鏈表的表頭結點指針，試設計一個算法，將這兩個有序鏈表合并成一個非遞增有序的單鏈表。要求結果鏈表仍使用原來兩個鏈表的存儲空間，不另外占用其他的存儲空間。表中允許有重復數據。（10分）4. 用指向指針的方法對10個字符串排序并輸出。（10分）5. 編寫一個函數getbits,從一個16位的單元中取出某幾位（即該幾位保留原值，其余位為0）。函數調用形式為：getbits(value,n1,n2),value為該16位數的值，n1為欲取出的起始位，n2為欲取出的結束位。例如：getbits(0101675,5,8)表示對八進制打印出來。注意，應當將這幾位數右移到最右端，然后用八進制形式輸出。（10分）6. 魔術師表演節目，她將紅桃和黑桃全部迭在一起，牌面朝下放在手中，對觀眾說：最上面一張是黑桃A，翻開后放在桌上。以后，從上至下每數兩張全依次放在最底下，第三張給觀眾看，便是黑桃2，放在桌上后再數兩張依次放在最底下，第三張給觀眾看，是黑桃3。如此下去，觀眾看到放在桌上上牌的順序是：黑桃 A 2 3 4 5 6 7 8 9 10 J Q K紅桃 A 2 3 4 5 6 7 8 9 10 J Q K問魔術師手中牌的原始順序是什么（12分）？7. 編寫一個算法，檢查一個程序中的花括號、方括號是否配對，若能夠全部配對則返回1，否則返回0.（12分）8. 編寫一個函數，找出一個二維數組的鞍點，即該位置上的元素在該行最大，在該列上最?。ㄒ部赡軟]有鞍點），并分析函數的時間的復雜度。（12分）9. 一個長方體P=（x,y,z）|0=x=L,0=y=W,0=z=H，大小為L*W*H。長方體表面有任意兩點A（x1,y1,z1）和B（x2,y2,z2），A,B兩點可由長方體表面的折線連接。求出A和B的最短距離（L,W,H和點的坐標都是整數，0=L,W,H=1000）。（14分）3. 20151、 程序閱讀題（每題3分，共6分）(1)#define product(x) (x*x)int main()int i=3,j,k;j=product(i+);k=product(+i);printf(j=%d,k=%d,j,k);return 0;以上程序運行結果：_j=9,k=25_(2) 有1020個西瓜，第一天賣了一半多兩個，以后每天賣剩下的一半多兩個，下面的程序統計賣完所需的天數。請填空：#include main()int day,x1,x2;day = 0;x1 = 1020;while(_x1!=0_)x2=_x1/2-2_;x1 = x2;day+;printf(day = %dn,day);2、 程序設計題（寫出完整的C語言程序，在程序中必須給出清楚的注釋，12題共計94分）。1. 寫一個“標準”宏MIN，這個宏輸入兩個參數并返回較小的一個（3分）。#define MIN(a),(b) (a)(b)?(b):(a)2編寫函數將a、b的值進行交換，要求不適用任何中間變量（4分）。Swp(a,b) a=ab; b=ab; a=ab; 3. 編寫函數getbits從一個16位的單元中取出以x1開始至x2結束的某幾位，起始位與結束位都從左向右計算。同時編寫主函數調用getbits進行驗證（6分）。unsigned short getbits(unsigned short value, unsigned char x1,unsigned char x2)unsigned short temp = 0;temp = (tempx1)&(temp(16-x2);return temp;int main(void)unsigned a;unsigned char x1,x2;printf(input a:);scanf(%o,&a);printf(input start bit x1, and end bit x2:);scanf(%d,%d,&x1,&x2);printf(%dn,getbits(a,x1-1,x2);system(pause);return 0; 4. 求兩個正整數m和n的最大公約數，要求采用非遞歸方法與遞歸方法分別實現（5分）。5. 輸入一行文字，找出其中大寫字母、小寫字母、空格、數字及其他字符各有多少（7分）？6. 用指向指針的指針的方法對5個字符串排序并輸出（8分）。7. 自定義字符型指針函數，實現任意兩個字符串的連接，并返回連接之后的新字符串的首地址（8分）。8. 數字螺旋方陣的形式如圖一所示。請將螺旋方陣存放在nxn的二維數組中，并將其打印輸出，要求n由程序讀入，數字螺旋方陣由程序自動生成（而非人為地初始化或賦值）（10分）9. 現有21根火柴，兩人輪流取，每人每次可以取1至4根，不可多取，也不能不取，誰取最后一根火柴誰輸。請編寫一個程序進行人機對弈，要求人先取，計算機后取，計算機一方為“常勝將軍”（10分）。10. 編寫一個函數alloc(n)，用來在內存新開辟一個連續的空間（n個字節）。此函數的返回值是一個指針，指向新開辟的連續空間的起始地址。再寫一個函數free(p),將地址p開始的各單元釋放（不能再被程序使用，除非再度開辟）。（10分）11. 采用單鏈表來存儲多項式的結構，并編寫一個產生多項式鏈表的函數；基于多項式鏈表結構，編寫程序實現兩個多項式相加的運算（10分）。12. 在一個旅館中住著六個不同國籍的人，他們分別來自美國、德國、英國、法國、俄羅斯和意大利。他們的名字叫A、B、C、D、E和F。，名字的順序與上面的國籍不一定互相對應的?，F在已知：（1）A和美國人是醫生。（2）E和俄羅斯人是教書。（3）C和德國人是技師。（4）B和F曾經當過兵，而德國人從未參過軍。（5）法國人比A年齡大；意大利人比C年齡大。（6）B同美國人下周要去西安旅行，而C同法國人下周要去杭州度假。試問由上述已知條件，A、B、C、D、E和F各是哪國人（12分）？2014(1) 用C語言編程實現（寫出完整的C語言程序，在程序中需給出清楚的注釋，共計100分）。1. 編寫兩個函數，分別求兩個數的最大公約數和最小公倍數，用主函數調用這兩個函數輸出結果。（8分）2. 編寫程序輸出1001000內的可逆素數。可逆素數是指：一個素數將其各位數字的順序倒過來構成的飯序數也是素數。如157和751均為素數，它們是可逆素數。（8分）3. 有兩個磁盤文件“A”和“B”,各存放若干個按升序排列的實數。寫一個程序，將“A”和“B”兩個文件中的實數存放到新文件“C”中，且“C”中的實數仍然以升序排列。（10分）4. 將一個5x5的矩陣中最大的元素放在中心，4個角分別放4個最小的元素（順序為從左到右，從上到下順序依次從小到大存放），編寫一個函數實現之，用main函數調用。（10分）5. 用遞歸法將一個整數N轉換成字符串，例如輸入483，應輸出字符串“483”。N的位數不確定，可以是任意位數的整數。（10分）6. 設有一個unsigned long 型整數，現要分別將其前2個字節和后2個字節作為2個unsigned in型整數輸出（設一個int型數據占2個字節），編寫一個函數partition實現上述要求。要求在主函數輸入該long型整數，在函數partition中輸出結果。（10分）7. 在主函數main中輸入10個不等長的字符串，用另一個函數sort對它們進行排序，然后在主函數main中輸出這10個已排好的字符串。要求用指針數組完成。（10分）8. 已知有兩個單鏈表A和B，其頭指針分別為HA何HB，編寫一個函數從單鏈表A中刪除自第i個起的共m個元素，然后將它們插入到單鏈表B的第j個元素之前。（10分）9. M只猴子要選大王，選舉方法如下：所用猴子按照1.M編號圍坐一圈，從第1浩開始按順序1,2，.,N(NM)報數，凡報到N的猴子退出到圈外，再從下一個猴子開始繼續1,2，.，N報數，報到N的猴子退出，如此循環，直到圈內只剩下一只猴子時，這只猴子就是大王。給定M和最后一個出圈者的編號S，求最小的N？（12分）10. 有A、B、C、D、E五人，每人額頭上都貼了一張黑或白的紙，五人對坐。每人都可以看到其它人額頭上的紙的顏色。五人相互觀察后，A說：“我看見有三人額頭上貼的是白紙，一人額頭上貼的是黑紙?！盉說：“我看見其它四人額頭上貼的都是黑紙?！盋說：“我看見一人額頭上貼的是白紙，其它三人額頭上貼的是黑紙。”D說：“我看見四人額頭上貼的都是白紙?！盓什么也沒說?，F在已知額頭上貼黑紙的人說的都是謊話，額頭上貼白紙的人說的都是實話。問這五人誰的額頭是貼白紙，誰的額頭是貼黑紙？用C語言編程實現。（12分）2013（1） 程序閱讀題（每題5分，共20分）1. 當a=1、b=3、c=5、d=4時，執行以下程序段后x的值是_2_ if(ab)if(cd)x=1;elseif(ac)if(bd)x=2;else x=3;else x =6;else x=7;2. 下面程序的功能是在3個字符串中找出最小的。請填空。#include #include main()char s20,str320;int i;for(i=0;i3;i+)gets(stri);strcpy(s,(_);if(strcmp(str2,s)0) strcpy(_);printf(%sn,_);3. 以下程序運行的結果是_main()int a3=1,2,3,4,5,0,(*pa)3,i;pa=a;for(i=0;i3;i+)if(i1_)0;i+);return i;（2） 程序設計題（要求用C語言實現，共80分）1） 已知兩個單鏈表A與B分別表示兩個集合，其元素遞增排列，編寫一個函數求出A和B的交集C，要求C同樣以元素值遞增的單鏈表形式存儲（10分）。2） 編一程序，檢查你所使用的計算機系統的C編譯系統在執行右移時時按照邏輯右移的原則還是按照算術右移的原則？如果是邏輯右移，請編寫一函數實現算術右移；如果是算術右移，請編寫一函數實現邏輯右移（10分）。3） 設有一個數列，包含10個數，已按升序排列?，F要求編寫程序，把從指定位置開始的n個數按逆序重新排列并輸出新的完整數列。進行逆序處理時要求使用指針方法。（例如，2、4、6、8、10、12、14、16、18、20，若要求把從第4個數開始的5個數按逆序重新排列為2、4、6、16、14、12、10、8、18、20）（10分）4） 從3個紅球、5個白球、6個黑球中任意取出8個球，且其中必須要有紅球和白球。請編寫程序，輸出所有方案（10分）。5） 用條件編譯的方法實現以下功能：輸入一行電報文字，可以任選兩種輸出，一為原文輸出；一為將字母變成其下一字母（如“a”變成“b”.,“y”變成“z”，而“z”變成“a”。其它字符不變）（10分）。6） 采用順序結構存儲串，編寫一個函數，求串A和串B的一個最長公共子串（15分）。7） 小張去旅游需要帶一些物品，有5種物品供選擇，每種物品的體積、重量、數量、價值分別如下表所示：物品編號體積（cm3）重量（kg）數量（個）價值（元）130310425081053102102423583513020511現在限制總的體積最多為500cm3，總的總量最多為100kg，請問小張能帶上的物品的最大總價值是多少？要求采用遞歸編程實現（15分）。201220111、 閱讀程序題（每題5分，共20分）1. 當a=1，b=3，c=5，d=4時，執行完下面一段程序段后x的值是_if(ab)if(cd)x=1;elseif(ac)if(bd)x=2;else x=3;else x =6;else x=7;2. 下面程序的運行結果是_#include main()int a,b;for(a=1,b=1;a=20)break;if(b%3=1)b+=3;continue;b-=5printf(%dn,a);3. 下面程序的運行結果是_main()int a66,i,j;for(i=1;i6;i+)for(j=1;j6;j+)aij=(i/j)*(