南師地理信息系統(tǒng)專業(yè)01方向真題C語言

本文格式為Word版，下載可任意編輯——南師地理信息系統(tǒng)專業(yè)01方向真題C語言

南師大考研

南師大C語言（含數(shù)據(jù)結(jié)構(gòu)）試卷2023

（1）設(shè)S為一個長度為n的字符串，其中串的字符各不一致，寫出具體程序并計算出S中互異的非平凡子串，非空且不同于S本身的個數(shù)。（此題15分）。

（2）編寫一個程序，對輸入的任意正整數(shù)n，打印出集合{0，1，2，3，...，n-1}的所有子集。（此題15分）。

（3）已知非空線性鏈表第一個節(jié)點由list指出，請寫一個算法交換P所指的節(jié)點與其下一個節(jié)點在鏈表中的位置(設(shè)P指向的不是鏈表最終那個結(jié)點）。（此題20分）。

（4）對給定的n（n≤10)計算并輸出K?。↘=1，2，3，...，n)的全部有效數(shù)字。（此題20分）。

（5）用遞歸算法和棧實現(xiàn)m個相異元素構(gòu)成的有序序列的二分查找，并計算出該棧的最小容量。（此題20分）。

（6）已知平面上（直角坐標(biāo)系）的m個點，請編寫一個函數(shù)，求同一條直線所能通過的最多點數(shù)。（此題20分）。

（7）用程序設(shè)計有n個葉子結(jié)點的Huffman樹的結(jié)點個數(shù)。（此題20分）。

（8）依次輸入表（30，15，28，20，24，10，12，68，35，50，46，55）中的元素，生成一棵二叉排序樹。（此題20分）。

①試畫出生成之后的二叉排序樹。

②若該二叉排序樹作中序編歷，試寫出編歷序列。

③假設(shè)每個元素的查找概率相等，試計算該二叉排序樹的平均查找長度

南師大2023C語言（含數(shù)據(jù)結(jié)構(gòu)）

1.設(shè)計一個程序，將任何輸入的字符串中的最長單詞輸出，并計算出其在字符串中的位置。（15分）

2.試采用遞歸函數(shù)實現(xiàn)將任意位數(shù)的整數(shù)轉(zhuǎn)換為字符串輸出，要求在主函數(shù)中輸入整數(shù)并調(diào)用遞歸函數(shù)實現(xiàn)轉(zhuǎn)換并輸出結(jié)果，對于負數(shù)也能處理（15分）

3.以順序存儲結(jié)構(gòu)表示串，設(shè)計算法，求串S中出現(xiàn)的第一個最長重復(fù)子串及其位置并分析算法的時間繁雜度。（20分）

4.利用2個棧S1和S2模擬一個隊列，寫出入隊和出隊的算法（可用棧的基本操作）（20分）

5．編寫一算法，以完成在帶頭節(jié)點單鏈表M中第n個位置前插入元素X的操作。（20分）

6．編寫一個利用二分法查找某值X是否存在于一組已知數(shù)據(jù)X1、X2、X3、Xn中的程序。（20分）

7．試設(shè)計一個算法解決地圖著色判斷問題。設(shè)一地圖有n個區(qū)域，用不多于4種顏色對這些區(qū)域進行著色，著色應(yīng)滿足的要求是相鄰的區(qū)域顏色不可以一致。你的算法以一種著色方案（即哪一個區(qū)域著什么顏色）為輸入，算法對該著色方案進行考察，若滿足著色要求，則輸出true,否則則輸出false。（20分）

（1）用C語言描述你為解決問題而設(shè)計的數(shù)據(jù)結(jié)構(gòu)（規(guī)律結(jié)構(gòu)，存儲結(jié)構(gòu)）。數(shù)據(jù)結(jié)構(gòu)的設(shè)計應(yīng)考慮對問題的明白描述和算法的效率；

（2）用C語言寫出你的算法。算法應(yīng)簡單、高效。對算法中的參數(shù)、變量、語句做必要的解釋，以增加可讀性；

（3）簡單分析你的算法的空間開銷和時間開銷。

8．已知一棵樹的邊的結(jié)合為

{(I,M),(I,N),(E,I),(B,E),(B,D),(C,B),(G,J),(G,K),(A,G),(A,F),(H,L),(A,H),(C,A)},試畫出這棵樹，并回復(fù)以下問題：（20分）

南師大考研

（1）哪個是根節(jié)點？

（2）哪些是葉子節(jié)點？

（3）樹的深度是多少？

（4）寫出該樹的前序遍歷序列

2023年南京師范大學(xué)地理信息信息系統(tǒng)C程序設(shè)計（含數(shù)據(jù)結(jié)構(gòu)）

一、填空題（每題5分，共20分）

（1）數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的（）和（），以及它們之間的相互聯(lián)系，并對這種結(jié)構(gòu)定義相應(yīng)的（），設(shè)計出相應(yīng)的（），而確保經(jīng)過這些運算后所得到的新結(jié)構(gòu)是（）結(jié)構(gòu)類型。

（2）“4：30'40''〞（）；0.01E-20（）；‘\101’（）；0x3c0（）；-0.5F（）；

A:合法的字符常量B:合法的整形常量C:合法的浮點數(shù)常量

D:合法的字符串常量E:非法表示請在括號內(nèi)填入A、B、C、D、E

（3）此題程序輸出結(jié)果是：（）

#includestdio.h

#degineN5

voidmain(void)

{

inti;

doublex,s=0;

for(i=1,x=1;i=N;i++,x+=0.5)

s+=1/x;

printf(s=%.2f\n,s);

}

（4）根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)形式，每個結(jié)點所含指針的個數(shù)，鏈表可分為（）和（）；而根據(jù)指針的聯(lián)接方式，鏈表又可分為（）和（）；棧的特點是（），隊列的特點是

（）。

二、選擇題（每題5分，共20分）

（1）在數(shù)據(jù)結(jié)構(gòu)中，與所有的計算機無關(guān)的數(shù)據(jù)叫（A）結(jié)構(gòu)；鏈表是一種采用（B）存儲結(jié)構(gòu)存儲的線性表；鏈表適用于（C）查找；在鏈表中進行（D）操作的效率比在順序存儲結(jié)構(gòu)中進行（D）操作效率高；二分法查找（E）存儲結(jié)構(gòu)。

A)1存儲2物理3規(guī)律4物理和規(guī)律

B)1順序2網(wǎng)狀3星式4鏈?zhǔn)?/p>

C)1順序2二分法3順序，也能二分法4隨機

D)1二分法查找2快速查找3順序查找4查找

E)1只適用于鏈表2只適用于順序3即適用于順序，也適用于鏈

表4即不適用于順序，也不適用于鏈表

（2）若一個棧的輸入序列是1、2、3、、n,輸出序列的第一個元素是n，則第i個輸出元素是（）

A)n-iB)n-i+1C)iD)n+i-1

（3）若串S='NjnuGisc',其子串的數(shù)目是（）

南師大考研

A)8B)37C)36D)9

（4）以下程序段的運行結(jié)構(gòu)是（）

intn=0;

while(n++=2);

printf(%d,n);

A)2B)3C)4D)有語法錯誤

三、程序設(shè)計（共計110分，請書寫整齊，卷面有分）

（1）利用串的基本運算，編寫一個算法刪除串S1中所有S2子串。（此題15分）

（2）編寫一程序，判斷一個字符串是不是“回文數(shù)〞。所謂回文數(shù)是從左至右或從右至左讀起來都是一樣的字符串。（此題15分）

（3）設(shè)計一個統(tǒng)計選票的算法，輸出每個候選人的得票結(jié)果（假定采用單鏈表存放選票，候選人編號依次為1，2，3，N,且每張選票選且只選一人）（此題15分）

（4）有幾個人圍成一圈，順序排號。從第一個開始報數(shù)，凡報到4的人退出圈子，問最終留下的是幾號。（此題15分）

（5）假設(shè)一個算術(shù)表達式中包含圓括號、方括號和花括號三種類型的括號，編寫一個算法判斷其中的括號是否匹配。（此題15分）

（6）已知R[0n-1]為整型數(shù)組，試設(shè)計實現(xiàn)以下運算的遞歸算法（此題15分）

1求數(shù)組R中的最大整數(shù)

2求n個整數(shù)之和

3求n各整數(shù)的平均值

（7）分別寫出下圖樹的先序遍歷、中序遍歷和后序遍歷的結(jié)果。寫出中序遍歷算法，算法中root指向二叉樹的根。（此題20分）

2023年南京師范大學(xué)地理信息信息系統(tǒng)C程序設(shè)計（含數(shù)據(jù)結(jié)構(gòu)）

一、選擇題（每題4分，共20分）

（1）設(shè)有如下定義：intx=1,y=1;則語句printf(“d%/n〞,(x--++y));的輸出結(jié)果是（A）1(B)0(C)-1(D)2

（2）若已定義：inta[9],*p=a;并在以后的語句中并未改變P的值，不能表示a[1]的地址的表達式是(A)p+1(B)a+1(C)a++(D)++p

（3）若有以下的說明和語句，則在執(zhí)行for語句后，*(*(pt+1+2))表示的數(shù)組元素是

(A)t[2][0](B)t[2][2](C)t[1][2](D)t[2][1]

（4）#include“studio.h〞

main()

{

inta[]={1,2,3,4,5,6,7,8,9,10,11,12};

intp=a+5,q=NULL;

*q=*(p+5);

printf(“%d%d\n〞,*p,*q);

}

輸出結(jié)果是(A)運行后報錯(B)66(C)612(D)55

（5）以下不正確的說法是

(A)實參可以是常量、變量或表達式(B)形參應(yīng)與其對應(yīng)的實參類型一致

(C)實參可以為任意類型(D)形參可以是常量、變量或表達式

南師大考研

二、程序填空（每題5分，共計20分，請將答案寫在答題卡的相應(yīng)位置）

（1）函數(shù)yanghui能夠按以下方式構(gòu)成一個楊輝三角形：

1

11

121

1331

14641

#defineN11

yanghui(inta[][N])

{

inti,j;

for(i=1;iN;i++)

{a[1]=1;a=1;}

for([A];iN;i++)

for(j=2;;j++)

a[j]=[C]+a[i-1][j];

}

（2）條件“2x3或x-10〞的C語言表達式是[A]

（3）以下程序的功能是判斷輸入的年份是不是閏年

main()

{

inty,f;

scanf(“%d〞,y);

if(y%400==0)f=1;

elseif([A])f=1;

else;

if(f)printf(“%dis〞,y);

elseprintf(“%disnot〞,y);

printf(“aleapyear\n〞);

}

（4）以下程序可以把從鍵盤上輸入的十進制數(shù)（long型）以二到十六進制形式輸出，請?zhí)羁铡?/p>

（5）#include“studio.h〞

main()

{

charb[16]={'0'、'1'、'2'、'3'、'4'、'5'、'6'、'7'、'8'、'9'、'A'、'B'、'C'、'D'、'E'、'F'};

intc[64],d,i=0,base;

longn;

printf(“enteranumber:\n〞);

scanf(“%1d〞,n);

printf(“enternewbase:\n〞);

南師大考研

scanf(“%d〞,base);

do{c=[A];

i++;n=n/base;

}while(n!=0);

printf(“transmitenewbase:\n〞);

for(--i;i=0;--i)

{

d=c;

printf(“%c〞,b);

}

}

三、程序設(shè)計題（卷面有分）

（1）從鍵盤輸入10個數(shù)，輸出其中最大數(shù)和最小數(shù)。（此題10分）

（2）求300以內(nèi)的雙素數(shù)，并輸出，判斷一個數(shù)m是否為素數(shù)的方法如下：讓m被2到除，當(dāng)且僅當(dāng)m不能被2~之間的任何一個數(shù)所整除，則m為素數(shù)，而當(dāng)m為素數(shù)，同時m+2也為素數(shù)，則m與m+2就是雙素數(shù)。（此題15分）

（3）編寫一個子程序能將主程序傳過來的數(shù)組按行分別進行從小到大的排序，再編寫一個二分法查找子程序，判定主函數(shù)傳過來的待查數(shù)是否在已排序的數(shù)組中，若查找到則返回它在數(shù)組中的位置（可以在多個位置出現(xiàn)），否則返回-1。（此題15分）

（4）利用遞歸方法找出從自然數(shù)1，2，n中任取r個數(shù)的所有組合，并畫出程序N-S圖，例如n=5，r=3，所有組合為：（此題20分）

543521

542432

541431

532421

531321

（5）利用單項循環(huán)鏈表和順序存儲結(jié)構(gòu)設(shè)計一個算法解決約瑟夫(JOSEHUS)問題。設(shè)有N個人圍坐一圈，現(xiàn)從某個人開始報數(shù)，數(shù)到M的人出現(xiàn)，接著從出列的下一個人開始重新報數(shù)，數(shù)到M的人又出現(xiàn)，如此下去知道所有人都出列為止。試求出他們的出列次序。（此題20分）

（6）編號為A,B,C,D的四輛列車，順序開進一個棧式結(jié)構(gòu)的站臺。問開出車站的順序有多少種可能？請具體寫出來。

（7）試將下面的樹轉(zhuǎn)換成二叉樹，并寫出二叉樹前序遍歷后的結(jié)點序列。（此題15分）

2023年南京師范大學(xué)地理信息信息系統(tǒng)C程序設(shè)計（含數(shù)據(jù)結(jié)構(gòu)）

1、簡答題（20分）

1)頭文件中的ifndef/define/enfif干什么用？

2)#includefilename.h和#includefilename.h有什么區(qū)別？

3)const有什么用途？

4)請簡述以下兩個for循環(huán)的優(yōu)缺點。

第一個其次個

For(i=0;iN;i++)

{

南師大考研

If(condition)

DoSomething;

else

DoOtherthing;

}If(condition)

{For(i=0;iN;i++)

DoSomething;

}

Else

{for(i=0;iN;i++)

DoOtherthing;

}

優(yōu)點：優(yōu)點：

缺點：優(yōu)點：

2、寫一個程序（1）實現(xiàn)mn矩陣的轉(zhuǎn)置；（2）矩陣A（mn）和矩陣B(n1)的相乘。

3、利用格利高利公式求Л.Л/4=1-1/3=1/5-1/7+直到最終一項的值小于0.000001為止。（“Л〞表示圓周率）

4、用一個程序?qū)崿F(xiàn)表達式括號匹配的合法性檢查；對于輸入一個字符串，檢查其括號的使用是否合法。表達式中允許出現(xiàn)圓括號（）、[]、{}，但這些括號的使用必需匹配。假設(shè)輸入的表達式兩端加上#，即以#開始，當(dāng)再次遇到#表示字符串輸入終止。

5、編寫函數(shù)stringReverse,取包含字符串的字符數(shù)組為參數(shù)，逆向打印字符串且不返回任何內(nèi)容。函數(shù)在接收到#終止符時中止處理并返回。

6、編寫遞歸程序recursiveMinimum，取數(shù)組和長度為參數(shù)并返回數(shù)組中最小的元素，當(dāng)函數(shù)在接收但長度為1的數(shù)組時中止處理并返回。

7、寫一個程序，讀入全班學(xué)生的學(xué)號、姓名、成績，用冒泡法對學(xué)生的成績由小到大排序，將排序的好的學(xué)生紀(jì)錄輸出。

2023年南京師范大學(xué)地理信息信息系統(tǒng)C程序設(shè)計（含數(shù)據(jù)結(jié)構(gòu)）

1、設(shè)有4行2列的矩陣A和2行3列的矩陣B，求A和B的乘積C.

2、輸入若干姓名，統(tǒng)計各種姓氏的人數(shù)。

3、m只猴子要選大王，選取方法如下：所有猴子按1m編號圍坐成一圈，從第一號開始按順序1、2、3、、n報數(shù)，凡報n號的猴子退出圈外，如此循環(huán)報數(shù)，直到圈內(nèi)只剩下一只猴子時，這只猴子就是大王。m和n由鍵盤輸入。

4、寫出折半查找的遞歸算法。

5、寫一個函數(shù)，以刪除指定的鏈表結(jié)點。

6、a和b單項鏈表的每一個結(jié)點中存放一個正整數(shù)，并在鏈表中按由小到大的順序排列，請寫一個過程，把b鏈表合并到b鏈表中去，合并后的鏈表依舊有序。

2000年南京師范大學(xué)地理信息信息系統(tǒng)C程序設(shè)計（含數(shù)據(jù)結(jié)構(gòu)）

（說明一下：試題可以采用C語言、C++、Pascal、BASIC或FORTRAN任意一種語言，要求劃出算法流程圖和寫出算法，試卷總分100分）

1、有一個函數(shù)如下：

5X(X1)

Y(X)=5X-1(1=X10)

3X-1(X=10)

南師大考研

編寫一個程序，輸入X，輸出結(jié)果。要求：①將其顯示在屏幕上。②用文本格式寫入名為“Result.txt〞的文件中。③畫出流程圖。（20分）

2、“完數(shù)〞定義：一個數(shù)恰好等于它的因子之和。如6的因子是1、2、3，而6=1+2+3，所以6為完數(shù)。編程找出1000以內(nèi)的所有“完數(shù)〞。要求：①將其顯示在屏幕上。②用文本格式寫入名為“Result.txt〞的文件中。③畫出流程圖。（20分）

3、數(shù)方陣是這樣的一個方陣，它的每行、每列和對角線之和均相等，如三階幻數(shù)方陣為以下方陣。編寫一個算法，求出3階方