南京師范大學(xué)GIS專業(yè)研究生入學(xué)考試題集(C語言)

1、1999年南京師范大學(xué)地理信息信息系統(tǒng)C程序設(shè)計(jì)（含數(shù)據(jù)結(jié)構(gòu)）二、程序設(shè)計(jì)1、求下列矩陣的轉(zhuǎn)置，并在屏幕上輸出（15分）2、1357926871010842.整數(shù)N的階乘記作N!,他為整數(shù)1至N的連續(xù)乘積,要求從鍵盤輸入一個(gè)正整數(shù)N,計(jì)算出階乘的結(jié)果，并顯示（15分）3、從鍵盤若干名學(xué)生某門課成績，同幾個(gè)分?jǐn)?shù)段成績的人數(shù)，程序運(yùn)行結(jié)果如下（20分）Studentsnumber：12inputstudent1sscores:92871006094786552964310089results:100:29099:38089:270,9:16069:2059:2注:口中的為用戶輸入4、用篩選發(fā)求出3

2、”00只見的所有素?cái)?shù)，每5個(gè)打印一行,并將結(jié)果輸出到文件result,dal中要求“需用循環(huán)賦值初始化數(shù)組pn,pLn內(nèi)存放3200中的奇數(shù)2用篩選發(fā)篩出pn中的非素?cái)?shù)3打印pn并輸出到文件中（30分）2.voidJiecheng(intnum)(if(num=0)printf(請(qǐng)輸入正整數(shù)!);intjc=0;for(inti=1;inum;i+)(jc*=i;printf(%d!=%d,num,jc);2000年南京師范大學(xué)地理信息信息系統(tǒng)C程序設(shè)計(jì)（含數(shù)據(jù)結(jié)構(gòu)）說明一下二試題可以采用C語言、C+,Pascal.HAS1C或FORTRAN任意一種語言，要求劃出算法流程圖和寫出算法，試卷總分

3、100分）1、有一個(gè)函數(shù)如下：5X（X1）Y（X）=5X-1（K=X10）3X-1（X二10）編寫一個(gè)程序，輸入X,輸出結(jié)果.要求：將其顯示在屏幕上。用文本格式寫入名為HResult,txt,?的文件中口畫出流程圖0（20分）2、“完數(shù)”定義：一個(gè)數(shù)恰好等于它的因子之和。如6的因子是1、2,3,而6=1+2+3,所以6為完數(shù)。編程找出1000以內(nèi)的所有“完數(shù),要求： 將其顯示在屏幕上。 用文本格式寫入名為Rcsult.txt”的文件中.畫出流程圖。（20分）3、數(shù)方陣是這樣的一個(gè)方陣，它的每行、每列和對(duì)角線之和均相等，如三階幻數(shù)方陣為以下方陣.編寫一個(gè)算法，求出3階方陣的所有形式。要求：將其顯

4、示在屏幕上.用文本格式寫入名為“Result.txt”的文件中。畫出流程圖（30分）8163574924、編寫一個(gè)算法，從鍵盤輸入某年某月某天，計(jì)算出該天是星期兒.要求：將其顯示在屏幕上。用文本格式寫入名為Result.txt的文件中，畫出流程圖.（30分）（提示：一年12個(gè)月，1、3、5、7、8“10、12為大月，每月31天；4、6.9、11為小月，每月30天，2月如是閏年為29天，否則28天。每7天為一周.閏年判別：該年能夠被4整除、但不能被100整除，該年為閏年；該年能夠被4整除、又能被100整除，如果該年還能被400整除，該年為閏年，否則，該年不為閏年。2001年南京師范大學(xué)地理信息信

5、息系統(tǒng)C程序設(shè)計(jì)（含數(shù)據(jù)結(jié)構(gòu)）1.設(shè)有4行2列的矩陣A和2行3列的矩陣B,求A和B的乘積C.2、輸入若干姓名，統(tǒng)計(jì)各種姓氏的人數(shù)。3、m只蜃子要選大王，選取辦法如下:所有猴子按1m編號(hào)圍坐成一圈，從第號(hào)開始按順序1、2、3、口報(bào)數(shù)，凡報(bào)n號(hào)的猴子退出圈外，如此循環(huán)報(bào)數(shù)，直到圈內(nèi)只剩下一只猴子時(shí)，這只縫子就是大王.m和口由鍵盤輸入.4,寫出折半查找的遞歸算法.5,寫一個(gè)函數(shù)，以刪除指定的鏈表結(jié)點(diǎn)立6、a和b單項(xiàng)鏈表的每一個(gè)結(jié)點(diǎn)中存放個(gè)正整數(shù)，并在鏈表中按由小到大的順序排列，請(qǐng)寫一個(gè)過程，把b鏈表合并到b鏈表中去，合并后的鏈表仍然有序,2002年南京師范大學(xué)地理信息信息系統(tǒng)C程序設(shè)計(jì)(含數(shù)據(jù)結(jié)構(gòu))

6、1、簡答題(20分)1)頭文件中的ifrulef/definei/enfif干什么用？2)#include和includefilename.!/有什么區(qū)別？3)const有什么用途？4)請(qǐng)簡述以下兩個(gè)for循環(huán)的優(yōu)缺點(diǎn)口第一個(gè)第二個(gè)For(i=0;iN：i+)(If(condition)DoSomething;elseDoOtherthing;If(condition)For(i=0;iN;i+)DoSomething;)Elsefor(i=0:i10(0-1(D)2(2)若已定義：int;并在以后的語句中并未改變P的值，不能表示al的地址的表達(dá)式是(A)p+1(B)a+1(C)a+(D)+p

7、(3)若有以下的說明和語句，則在執(zhí)行for語句后，*(*(pt+l+2)表示的數(shù)組元素是(A)t2H0(B)t22(01121(D)t21(4)ttincludestudio,h”mairf?)inta口二1,2,3,4,5,6,7,8,9,10,11,12);intpf+5,q=NULL：*q=*(p+5);printf(*q);輸出結(jié)果是(A)運(yùn)行后報(bào)錯(cuò)(5)以下不正確的說法是(A)實(shí)參可以是常量、變量或表達(dá)式(C)實(shí)參可以為任意類型二、程序填空(每題5分，共計(jì)20分，請(qǐng)將答案寫在答題卡的相應(yīng)位置)(1)函數(shù)yanghui能夠按以下方式構(gòu)成一個(gè)楊輝三角形t1111 21133114641d

8、efineN11yanghui(intaN)inti,j;for(i=l;iN;i+)66(C)612(D)55(B)形參應(yīng)與其對(duì)應(yīng)的實(shí)參類型一致形參可以是常量、變量或表達(dá)式al=l;a=l;for(A;iN;i+)for(j=2;j+)aj=C+ai-lj;)(2)條件2x=0;-i)(d=c;printf(=0&m=0)|(n=0&m=n)return(1);else(if(nm&n=0&m=0)return(comb(n-l,m)+comb(n-l,m-1);else(printf(n,m值不正確n);return(-1);)一、填空題（每題 5 分，共

9、20 分）（1）數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的（）和（），以及它們之間的相互聯(lián)系，并對(duì)這種結(jié)構(gòu)定義相應(yīng)的（）,設(shè)計(jì)出相應(yīng)的（），而確保經(jīng)過這些運(yùn)算后所得到的新結(jié)構(gòu)是（）結(jié)構(gòu)類型。（2）“43040（）;0.01E-20（）;101（）;0 x3c0（）;-0.5F（）;A:合法的字符常量 B:合法的整形常量 C:合法的浮點(diǎn)數(shù)常量D:合法的字符串常量 E:非法表示請(qǐng)?jiān)诶ㄌ?hào)內(nèi)填入 A、B、C、D、E（3）本題程序輸出結(jié)果是：（）#includestdio.h#degineN5voidmain（void）inti;doublex,s=0;for（i=1,x=1;i=N;i+,x+=0.5）s+=1/x;print

10、f（s=%.2f,s）;（4）根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)形式，每個(gè)結(jié)點(diǎn)所含指針的個(gè)數(shù)，鏈表可分為（）和（）；而根據(jù)指針的聯(lián)接方式，鏈表又可分為（）和（）；棧的特點(diǎn)是（），隊(duì)列的特點(diǎn)是（）。二、選擇題（每題 5 分，共 20 分）（1）在數(shù)據(jù)結(jié)構(gòu)中，與所有的計(jì)算機(jī)無關(guān)的數(shù)據(jù)叫（A）結(jié)構(gòu)；鏈表是一種采用（B）存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表；鏈表適用于（C）查找；在鏈表中進(jìn)行（D）操作的效率比在順序存儲(chǔ)結(jié)構(gòu)中進(jìn)行（D）操作效率高；二分法查找（E）存儲(chǔ)結(jié)構(gòu)。人）1存儲(chǔ)2物理3邏輯4物理和邏輯8）1順序2網(wǎng)狀3星式4鏈?zhǔn)?1順序2二分法3順序，也能二分法4隨機(jī)D）1二分法查找2快速查找3順序查找4查找E)只適用于鏈

11、表只適用于順序即適用于順序,也適用于鏈表即不適用于順序，也不適用于鏈表(2)若一個(gè)棧的輸入序列是 1、2、3、n,輸出序列的第一個(gè)元素是 n,則第 i 個(gè)輸出元素是()A)n-iB)n-i+1C)iD)n+i-1(3)若用 S=NjnuGisc,其子用的數(shù)目是()A)8B)37C)36D)9(4)下列程序段的運(yùn)行結(jié)構(gòu)是()intn=0;while(n+=2);printf(%d,n);A)2B)3C)4D)有語法錯(cuò)誤三、程序設(shè)計(jì)(共計(jì) 110 分，請(qǐng)書寫整潔，卷面有分)(1)利用用的基本運(yùn)算，編寫一個(gè)算法刪除用 S1 中所有 S2 子用。(本題 15 分)(2)編寫一程序，判斷一個(gè)字符串是不是

12、回文數(shù)”。所謂回文數(shù)是從左至右或從右至左讀起來都是一樣的字符串。(本題 15 分)(3)設(shè)計(jì)一個(gè)統(tǒng)計(jì)選票的算法，輸出每個(gè)候選人的得票結(jié)果(假定采用單鏈表存放選票，候選人編號(hào)依次為 1,2,3,N,且每張選票選且只選一人)(本題 15 分)(4)有幾個(gè)人圍成一圈，順序排號(hào)。從第一個(gè)開始報(bào)數(shù)，凡報(bào)到 4 的人退出圈子，問最后留下的是幾號(hào)。(本題 15 分)(5)假設(shè)一個(gè)算術(shù)表達(dá)式中包含圓括號(hào)、方括號(hào)和花括號(hào)三種類型的括號(hào)，編寫一個(gè)算法判斷其中的括號(hào)是否匹配。(本題 15 分)(6)已知 R0n-1為整型數(shù)組，試設(shè)計(jì)實(shí)現(xiàn)下列運(yùn)算的遞歸算法(本題 15 分)求數(shù)組 R 中的最大整數(shù)求 n 個(gè)整數(shù)之和求

13、 n 各整數(shù)的平均值(7)分別寫出下圖樹的先序遍歷、中序遍歷和后序遍歷的結(jié)果。寫出中序遍歷算法，算法中 root 指向二叉樹的根。(本題 20 分)南師 2005 年碩士研究生招生入學(xué)考試初試試卷科目名稱：C語言程序設(shè)計(jì)(含數(shù)據(jù)結(jié)構(gòu))考生注意：所有答案必須寫在答題紙上，否則無效，后果自負(fù)。一、填空題(每題 5 舒，共計(jì) 20 分)(1)每次從無序表中取出一個(gè)元素，把它插入有序表中的適當(dāng)位置，此種排序法叫做排序：每次從無序表中挑選出一個(gè)最小或最大元素，把它交換到有序表的一端，此種排序方法叫做排序；每次直接或通過基準(zhǔn)元素間接比較兩個(gè)元素，若出現(xiàn)逆序排列時(shí)就交換它們的位置，此種排序方法叫做排序：每次

14、使兩個(gè)相鄰的有序表合并成一個(gè)有序表的排序方法叫做排序?？焖倥判蛟谄骄闆r下的時(shí)間復(fù)雜度為。(2)設(shè)輸入元素為 1,2,3,P 和 A,輸入次序?yàn)?123PA,元素經(jīng)過棧后到達(dá)輸出序列。當(dāng)所以元素均到達(dá)輸出序列后序列可以作為 C 語言的標(biāo)識(shí)符.己知 sizeof(int)=4，請(qǐng)分析下面代碼的運(yùn)行過程并寫出輸出結(jié)果unsignedintGetSize(inta,char*strl)(returnsizeof(a)+Sizeof(strl);intmain()(inta1100;char*strl=Welcome!;printf(%d,_%d,_,sizeof(a1),sizeof(strl);p

15、rintf(%d.,GetSize(a1,strl);return0;輸出：。(4)T 是正則二叉樹，即只有度為 2 和度為。的結(jié)點(diǎn)，它具有 6 個(gè)葉結(jié)點(diǎn)，那么樹 T 的高度最多可以是;最小可以是;機(jī)丁的分支結(jié)點(diǎn)數(shù)是。如果 T 又是 Huffman 最優(yōu)二叉樹且各葉結(jié)點(diǎn)的權(quán)分別是 1、2、3、4、5、6,則最優(yōu)二叉樹 T 的非葉結(jié)點(diǎn)的權(quán)之和是;權(quán)為 1 的葉結(jié)點(diǎn)所處層次是?！咀ⅲ簶涞母Y(jié)點(diǎn)高度為 O二、選擇題【每題 5 分.共計(jì) 20 分】(1)下列說法中錯(cuò)誤的是。A)數(shù)據(jù)結(jié)構(gòu)是指相互之間存在-種或多種關(guān)系的數(shù)據(jù)元素的全體，B)數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元索本身的內(nèi)容和形式無關(guān)。C)在索引順序結(jié)構(gòu)上

16、實(shí)施分塊查找，在等概率情況下，其平均查找長度不僅與子表個(gè)數(shù)有關(guān)，而且與每一個(gè)子表中的記錄個(gè)數(shù)有關(guān)。D)每種數(shù)據(jù)結(jié)構(gòu)都應(yīng)具備三種基本運(yùn)算：插入，刪除，搜索。2)隊(duì)列的特點(diǎn)是_A_,設(shè)循環(huán)隊(duì)列用 qn來存放，其頭尾指針分別為 f 和 r,則隊(duì)滿條件是_B_,隊(duì)列中的元素個(gè)數(shù)為 C。A先進(jìn)先出后進(jìn)先出只進(jìn)不出只出不進(jìn)Br=fr=(f+1)%nf=(r+1)%nf=r+1%nCr-fr-f+1(r_f)%n(r-f+n)%n(3)下圖是帶權(quán)的有向圖 G 的鄰接表示法。 從結(jié)點(diǎn) V1 出發(fā)深度遍歷圖 G 所得的結(jié)點(diǎn)序列為_A_:廣度遍歷圖 G 所得的結(jié)點(diǎn)序列為_B_;G 的一個(gè)拓?fù)湫蛄惺莀C_從結(jié)點(diǎn) V

17、1 到 V8 的最短路徑是_D_,從結(jié)點(diǎn) V1 到 V8 的關(guān)鍵路徑是E。AC：:VP.:V5，V九VBa：V4.6；V5r聲；V7s.yP*5$,；,V?,V4，V曲V，0V7.VSjjV；,V、V4，V6，V7,V3-V5-V8V!,V2rU九V&V4,V5，76、V7VI，VLV3,V8tV4,V5,V7,V6VrV2,V3.V8，V5.V7.V4-V6D、E（V!.V2，事*V5fVJ.VS,（VLV&V5;V3-UKjV6.V.篤沿.1V8）（4）下面程序的運(yùn)行結(jié)果是#includemain（）inta=5,b=4,c=3,rl,r2;rl=abc;r2=ab&

18、;bC;printf（%d%dn,rl,r2）;A）00B）01C）10D）11E）有語法錯(cuò)誤三、程序設(shè)計(jì)（共計(jì) 1l0 分，請(qǐng)書寫整潔，卷面有分）設(shè) A 和 B 是兩個(gè)順序表，其元素按從小到大的順序排列。編寫一個(gè)將 A 和 B 中相同元素組成一個(gè)新的從大到小的有序順序表 C 的算法，并分析算法的時(shí)間復(fù)雜度。（本題 15 分）2）若線性表用單鏈表（帶表頭結(jié)點(diǎn)）作為存儲(chǔ)結(jié)構(gòu)，寫出其就地逆置算法。（本題 15 分）設(shè)定串采用順序存儲(chǔ)結(jié)構(gòu)，求串 s1 和 s2 的一個(gè)最長公共子串的長度，并指出該最長公共子串分別在 sl 和 s2 中的起始位置。（水題 15 分）（4）設(shè)單鏈表中存放 n 個(gè)字符，試設(shè)

19、計(jì)一個(gè)算法，使用棧判斷該字符串是否中心對(duì)稱，如 xyzzyx 即為中心對(duì)稱字符串。（小題 15 分）編寫算法找出從自然數(shù) 1,2,n 中任取 r 個(gè)數(shù)的所有組合。（本題 15 分）（6）設(shè)計(jì)一個(gè)計(jì)算二叉樹各結(jié)點(diǎn)的子孫個(gè)數(shù)的的算法。（本題 15 分）已知一棵二叉樹的先序序列和中序序列，則可唯一地確定一棵二叉樹。（本題 20 分）設(shè)計(jì)一個(gè)算法由先序序列和中序序列構(gòu)造二叉樹若先序序列為 abcdefg.中序序列為 cbaefdg,畫圖構(gòu)造對(duì)應(yīng)的二叉樹，并寫出該二叉樹的后序序列。1.設(shè)計(jì)一個(gè)程序，將任何輸入的字符串中的最長單詞輸出，并計(jì)算出其在字符串中的位置。(15 分)2,試采用遞歸函數(shù)實(shí)現(xiàn)將任意位

20、數(shù)的整數(shù)轉(zhuǎn)換為字符串輸出，要求在主函數(shù)中輸入整數(shù)并調(diào)用遞歸函數(shù)實(shí)現(xiàn)轉(zhuǎn)換并輸出結(jié)果，對(duì)于負(fù)數(shù)也能處理(15 分)3,以順序存儲(chǔ)結(jié)構(gòu)表示用，設(shè)計(jì)算法，求用 S 中出現(xiàn)的第一個(gè)最長重復(fù)子用及其位置并分析算法的時(shí)間復(fù)雜度。(20 分)4,利用 2 個(gè)棧 S1 和 S2 模擬一個(gè)隊(duì)列，寫出入隊(duì)和出隊(duì)的算法(可用棧的基本操作)(20 分)5 .編寫一算法，以完成在帶頭節(jié)點(diǎn)單鏈表 M 中第 n 個(gè)位置前插入元素 X 的操作。(20 分)6 .編寫一個(gè)利用二分法查找某值 X 是否存在于一組已知數(shù)據(jù) X1、X2、X3、Xn 中的程序。(20 分)7 .試設(shè)計(jì)一個(gè)算法解決地圖著色判斷問題。 設(shè)一地圖有 n 個(gè)區(qū)域

21、， 用不多于 4 種顏色對(duì)這些區(qū)域進(jìn)行著色，著色應(yīng)滿足的要求是相鄰的區(qū)域顏色不可以相同。 你的算法以一種著色方案(即哪一個(gè)區(qū)域著什么顏色)為輸入，算法對(duì)該著色方案進(jìn)行考察，若滿足著色要求，則輸出true,否則則輸出 false。(20 分)(1)用 C 語言描述你為解決問題而設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)(邏輯結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu))。數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)應(yīng)考慮對(duì)問題的清楚描述和算法的效率；(2)用 C 語言寫出你的算法。算法應(yīng)簡潔、高效。對(duì)算法中的參數(shù)、變量、語句做必要的注釋，以增加可讀性；(3)簡單分析你的算法的空間開銷和時(shí)間開銷。8 .已知一棵樹的邊的結(jié)合為(I,M),(I,N),(E,I),(B,E),(B,D),

22、(C,B),(G,J),(G,K),(A,G),(A,F),(H,L),(A,H),(C,A),試畫出這棵樹，并回答下列問題：(20 分)(1)哪個(gè)是根節(jié)點(diǎn)？(2)哪些是葉子節(jié)點(diǎn)？(3)樹的深度是多少？(4)寫出該樹的前序遍歷序列(1)設(shè) S 為一個(gè)長度為 n 的字符串，其中用的字符各不相同，寫出具體程序并計(jì)算出 S 中互異的非平凡子用，非空且不同于 S 本身的個(gè)數(shù)。(本題 15 分)。(2)編寫一個(gè)程序，對(duì)輸入的任意正整數(shù) n,打印出集合0,1,2,3,.,n-1的所有子集。(本題 15 分)。(3)已知非空線性鏈表第一個(gè)節(jié)點(diǎn)由 list 指出，請(qǐng)寫一個(gè)算法交換 P 所指的節(jié)點(diǎn)與其下一個(gè)節(jié)點(diǎn)

23、在鏈表中白位置(設(shè) P 指向的不是鏈表最后那個(gè)結(jié)點(diǎn))。(本題 20 分)。(4)對(duì)給定的 n(n010)計(jì)算并輸出 K!(K=1,2,3,.,n)的全部有效數(shù)字。(本題 20 分)。(5)用遞歸算法和棧實(shí)現(xiàn) m 個(gè)相異元素構(gòu)成的有序序列的二分查找，并計(jì)算出該棧的最小容量。(本題 20分)。(6)已知平面上(直角坐標(biāo)系)的 m 個(gè)點(diǎn)，請(qǐng)編寫一個(gè)函數(shù)，求同一條直線所能通過的最多點(diǎn)數(shù)。(本題 20 分)。(7)用程序設(shè)計(jì)有 n 個(gè)葉子結(jié)點(diǎn)的 Huffman 樹的結(jié)點(diǎn)個(gè)數(shù)。(本題 20 分)。(8)依次輸入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二

24、*排序樹。(本題 20 分)。試畫出生成之后的二*排序樹。若該二*排序樹作中序編歷，試寫出編歷序列。假設(shè)每個(gè)元素的查找概率相等，試計(jì)算該二*排序樹的平均查找長度。南師大C語言（含數(shù)據(jù)結(jié)構(gòu)）試卷一2008L一個(gè)數(shù)如果恰好等于它的因子之和， 這個(gè)數(shù)就稱為“完數(shù)二例如，6的因子是1,2,3,而6=1+2+3,因此6是“完數(shù):編寫程序找出1000之內(nèi)的所有“完數(shù)二2.采用順序結(jié)構(gòu)存儲(chǔ)串，編寫一個(gè)函數(shù)Substrin虱sl,s2）,用于判定s2是否是的字串3,請(qǐng)用鏈表編程實(shí)現(xiàn)：從鍵盤讀入整數(shù)，并按從大到小的順序輸出輸入整數(shù)中互不相等的那些整數(shù)。4.將一個(gè)5*5的矩陣中最大的元素放在中心， 四個(gè)角分別放四個(gè)最小的元素 （按從左到右,從上到下的順序依次從小到大存放），寫一個(gè)函數(shù)實(shí)現(xiàn)之。5.設(shè)A是有n個(gè)元素的整型數(shù)組5二1）,試寫一個(gè)求A中n個(gè)整數(shù)的平均值的遞歸程序口6 .假設(shè)由終端輸入集合元素， 先建立表示集合X的靜態(tài)鏈表P1,而后在輸入集合Y的元素同時(shí)查找P1表，若存在和丫相同的元素，則從PL表中刪除之，否則將此元素插入P1。請(qǐng)寫出用二叉樹計(jì)算英文文獻(xiàn)中單詞使用頻度的算法。單詞的頻度=該單詞的使用次數(shù)/文獻(xiàn)中單詞的總數(shù)&請(qǐng)寫出如