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

《C語言程序設(shè)計(jì)》考試試題（含數(shù)據(jù)結(jié)構(gòu)）南師1999年GIS專業(yè)研究生入學(xué)《C語言程序設(shè)計(jì)》考試試題（含數(shù)據(jù)結(jié)構(gòu)）2.voidJiecheng(intnum){ if(num<=0) printf("請(qǐng)輸入正整數(shù)！"); intjc=0; for(inti=1;i<num;i++) { jc*=i; } printf("%d!=%d",num,jc);}南師2023年GIS專業(yè)研究生入學(xué)《C語言程序設(shè)計(jì)》考試試題（含數(shù)據(jù)結(jié)構(gòu)）南師2023年GIS專業(yè)研究生入學(xué)《C語言程序設(shè)計(jì)》考試試題（含數(shù)據(jù)結(jié)構(gòu)）

南師2023年GIS專業(yè)研究生入學(xué)《C語言程序設(shè)計(jì)》考試試題（含數(shù)據(jù)結(jié)構(gòu)）

南師2023年GIS專業(yè)研究生入學(xué)《C語言程序設(shè)計(jì)》考試試題（含數(shù)據(jù)結(jié)構(gòu)）

南師2023年GIS專業(yè)研究生入學(xué)《C語言程序設(shè)計(jì)》考試試題（含數(shù)據(jù)結(jié)構(gòu)）一、填空題（每題5分，共20分）

（1）數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的（

）和（

），以及它們之間的互相聯(lián)系，并對(duì)這種結(jié)構(gòu)定義相應(yīng)的（

），設(shè)計(jì)出相應(yīng)的（

），而保證通過這些運(yùn)算后所得到的新結(jié)構(gòu)是（

）結(jié)構(gòu)類型。

（2）“4：30'40''”（

）；0.01E-20（

）；‘101’（

）；0x3c0（

）；-0.5F（

）；

A:合法的字符常量

B:合法的整形常量

C:合法的浮點(diǎn)數(shù)常量

D:合法的字符串常量

E:非法表達(dá)

請(qǐng)?jiān)诶ㄌ?hào)內(nèi)填入A、B、C、D、E

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

）

#include<stdio.h>

#degineN5voidmain(void)

{

inti;

doublex,s=0;

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

s+=1/x;

printf("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)。

A)<1>存儲(chǔ)

<2>物理

<3>邏輯

<4>物理和邏輯

B)<1>順序

<2>網(wǎng)狀

<3>星式

<4>鏈?zhǔn)?/p>

C)<1>順序

<2>二分法

<3>順序，也能二分法

<4>隨機(jī)

D)<1>二分法查找

<2>快速查找

<3>順序查找

<4>查找

E)<1>只合用于鏈表

<2>只合用于順序

<3>即合用于順序，也合用于鏈表

<4>即不合用于順序，也不合用于鏈表

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

）

A)n-i

B)n-i+1

C)i

D)n+i-1

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

）

A)8

B)37

C)36

D)9

（4）下列程序段的運(yùn)營結(jié)構(gòu)是（

）

int

n=0;

while(n++<=2);

printf("%d",n);

A)

2

B)3

C)4

D)有語法錯(cuò)誤三、程序設(shè)計(jì)（共計(jì)110分，請(qǐng)書寫整潔，卷面有分）

（1）運(yùn)用串的基本運(yùn)算，編寫一個(gè)算法刪除串S1中所有S2子串。（本題15分）

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

（3）設(shè)計(jì)一個(gè)記錄選票的算法，輸出每個(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）已知R[0……n-1]為整型數(shù)組，試設(shè)計(jì)實(shí)現(xiàn)下列運(yùn)算的遞歸算法（本題15分）

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

<2>求n個(gè)整數(shù)之和

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

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

南師2023年碩士研究生招生入學(xué)考試初試試卷科目名稱：C語言程序設(shè)計(jì)（含數(shù)據(jù)結(jié)構(gòu)）考生注意：所有答案必須寫在答題紙上，否則無效，后果自負(fù)。一、填空題（每題5舒，共計(jì)20分）

(1)

每次從無序表中取出一個(gè)元素，把它插入有序表中的適當(dāng)位置，此種排序法叫做____排序：每次從無序表中挑選出一個(gè)最小或最大元素，把它互換到有序表的一端，此種排序方法叫做____排序;每次直接或通過基準(zhǔn)元素間接比較兩個(gè)元素，若出現(xiàn)逆序排列時(shí)就互換它們的位置，此種排序方法叫做_______排序：每次使兩個(gè)相鄰的有序表合并成一個(gè)有序表的排序方法叫做________排序?？焖倥判蛟谄骄闆r下的時(shí)間復(fù)雜度為____。（2）設(shè)輸入元素為1,2,3，P和A，輸入順序?yàn)?23PA，元素通過棧后到達(dá)輸出序列。當(dāng)所以元素均到達(dá)輸出序列后_____________________________________序列可以作為C語言的標(biāo)記符．(3)

己知sizeof(int)==4，請(qǐng)分析下面代碼的運(yùn)營過程并寫出輸出結(jié)果

unsigned

int

GetSize(int

a[],char

*strl)

{

return

sizeof(a)

+

Sizeof(strl);

}

int

main(){

int

a1[100];

char

*

strl="Welcome!";

printf("%d,_%d,_",sizeof(a1),

sizeof(strl));

printf("%d.",GetSize(a1,

strl));return0;}輸出：________________________。(4)T是正則二叉樹，即只有度為2和度為O的結(jié)點(diǎn)，它具有6個(gè)葉結(jié)點(diǎn)，那么樹T的高度最多可以是____；最小可以是_____;樹T的分支結(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)上實(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ì)列用q[n]來存放，其頭尾指針分別為f和r，則隊(duì)滿

條件是__B__,隊(duì)列中的元素個(gè)數(shù)為C

。

A<1>先進(jìn)先出<2>后進(jìn)先出

<3>只進(jìn)不出

<4>只出不進(jìn)

B

<1>r=f

<2>r=(f+1)%n

<3>f=(r+1)%n

<4>f=r+1%n

C<1>r-f<2>r-f+1

<3>(r_f)%n

<4>(r-f+n)%n(3)

下圖是帶權(quán)的有向圖G的鄰接表達(dá)法。從結(jié)點(diǎn)V1出發(fā)深度遍歷圖G所得的結(jié)點(diǎn)

序列為__A__：廣度遍歷圖G所得的結(jié)點(diǎn)序列為__B__;G的一個(gè)拓?fù)湫蛄惺莀_C__

從結(jié)點(diǎn)V1到V8的最短途徑是__D__，從結(jié)點(diǎn)V1到V8的關(guān)鍵途徑是___E___。(4)下面程序的運(yùn)營結(jié)果是____#include<stdio.h>main(){

int

a=5,

b=4,c=3,rl,r2;rl=a>

b>c;r2=a>b&&b>C;printf

("%d

%d\n",rl,r2);}A)0

0

B)0

1

C)

10

D)11

E)有語法錯(cuò)誤三、程序設(shè)計(jì)（共計(jì)1l0分，請(qǐng)書寫整潔，卷面有分）(1)

設(shè)A和B是兩個(gè)順序表，其元素按從小到大的順序排列。編寫一個(gè)將A和B中相同元素組成一個(gè)新的從大到小的有序順序表C的算法，并分析算法的時(shí)間復(fù)雜度。(本題15分）2）若線性表用單鏈表(帶表頭結(jié)點(diǎn))作為存儲(chǔ)結(jié)構(gòu)，寫出其就地逆置算法。(本題15分）(3)設(shè)定串采用順序存儲(chǔ)結(jié)構(gòu)，求串s1和

s2的一個(gè)最長公共子串的長度，并指出該最長公共子串分別在sl和s2中的起始位置。（水題15分）(4)設(shè)單鏈表中存放

n個(gè)字符，試設(shè)計(jì)一個(gè)算法，使用棧判斷該字符串是否中心對(duì)稱，如xyzzyx即為中心對(duì)稱字符串。（小題15分）(5)

編寫算法找出從自然數(shù)1,2，…．n中任取r個(gè)數(shù)的所有組合。（本題15分）(6)

設(shè)計(jì)一個(gè)計(jì)算二叉樹各結(jié)點(diǎn)的子孫個(gè)數(shù)的的算法。（本題15分）(7)

已知一棵二叉樹的先序序列和中序序列，則可唯一地?cái)M定一棵二叉樹。（本題20分）<1>設(shè)計(jì)一個(gè)算法由先序序列和中序序列構(gòu)造二叉樹<2>若先序序列為abcdefg．中序序列為cbaefdg，畫圖構(gòu)造相應(yīng)的二叉樹，并寫出該二叉樹的后序序列。

南師2023年GIS專業(yè)研究生入學(xué)《C語言程序設(shè)計(jì)》考試試題（含數(shù)據(jù)結(jié)構(gòu)）

1.設(shè)計(jì)一個(gè)程序，將任何輸入的字符串中的最長單詞輸出，并計(jì)算出其在字符串中的位置。（15分）2.試采用遞歸函數(shù)實(shí)現(xiàn)將任意位數(shù)的整數(shù)轉(zhuǎn)換為字符串輸出，規(guī)定在主函數(shù)中輸入整數(shù)并調(diào)用遞歸函數(shù)實(shí)現(xiàn)轉(zhuǎn)換并輸出結(jié)果，對(duì)于負(fù)數(shù)也能解決（15分）3.以順序存儲(chǔ)結(jié)構(gòu)表達(dá)串，設(shè)計(jì)算法，求串S中出現(xiàn)的第一個(gè)最長反復(fù)子串及其位置并分析算法的時(shí)間復(fù)雜度。（20分）4.運(yùn)用2個(gè)棧S1和S2模擬一個(gè)隊(duì)列，寫出入隊(duì)和出隊(duì)的算法（可用棧的基本操作）（20分）5．編寫一算法，以完畢在帶頭節(jié)點(diǎn)單鏈表M中第n個(gè)位置前插入元素X的操作。（20分）6．編寫一個(gè)運(yùn)用二分法查找某值X是否存在于一組已知數(shù)據(jù)X1、X2、X3、……Xn中的程序。（20分）7．試設(shè)計(jì)一個(gè)算法解決地圖著色判斷問題。設(shè)一地圖有n個(gè)區(qū)域，用不多于4種顏色對(duì)這些區(qū)域進(jìn)行著色，著色應(yīng)滿足的規(guī)定是相鄰的區(qū)域顏色不可以相同。你的算法以一種著色方案（即哪一個(gè)區(qū)域著什么顏色）為輸入，算法對(duì)該著色方案進(jìn)行考察，若滿足著色規(guī)定，則輸出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)簡(jiǎn)潔、高效。對(duì)算法中的參數(shù)、變量、語句做必要的注釋，以增長可讀性；（3）簡(jiǎn)樸分析你的算法的空間開銷和時(shí)間開銷。

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)},試畫出這棵樹，并回答下列問題：（20分）（1）哪個(gè)是根節(jié)點(diǎn)？

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

（3）樹的深度是多少？

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

南師2023年GIS專業(yè)研究生入學(xué)《C語言程序設(shè)計(jì)》考試試題

（1）設(shè)S為一個(gè)長度為n的字