南京師范大學地理信息系統(tǒng)考研試題2003-2011

南京師范大學2011年研究生入學考試試題-科目名稱：地理信息系統(tǒng)..................1

南京師范大學05~10年研究生入學考試試題-科目名稱：地理信息系統(tǒng).................2

2005...........................................................................................................................................................2

2006...........................................................................................................................................................3

2007...........................................................................................................................................................3

2008...........................................................................................................................................................4

2009...........................................................................................................................................................4

2010...........................................................................................................................................................5

南京師范大學2011年研究生入學考試試題-科目名稱：C語言程序設(shè)計（含數(shù)據(jù)結(jié)構(gòu)）....6

南京師范大學2010年研究生入學考試試題-科目名稱：C語言程序設(shè)計（含數(shù)據(jù)結(jié)構(gòu)）....7

南京師范大學2009年研究生入學考試試題-科目名稱：C語言程序設(shè)計（含數(shù)據(jù)結(jié)構(gòu)）..21

南京師范大學2008年研究生入學考試試題-科目名稱：C語言程序設(shè)計（含數(shù)據(jù)結(jié)構(gòu)）..31

南京師范大學2007年研究生入學考試試題-科目名稱：C語言程序設(shè)計（含數(shù)據(jù)結(jié)構(gòu)）..43

南京師范大學2006年研究生入學考試試題-科目名稱：C語言程序設(shè)計（含數(shù)據(jù)結(jié)構(gòu)）..52

南京師范大學2005年研究生入學考試試題-科目名稱：C語言程序設(shè)計（含數(shù)據(jù)結(jié)構(gòu)）..60

南京師范大學2004年研究生入學考試試題-科目名稱：C語言程序設(shè)計（含數(shù)據(jù)結(jié)構(gòu)）..68

南京師范大學2003年研究生入學考試試題-科目名稱：C語言程序設(shè)計（含數(shù)據(jù)結(jié)構(gòu)）..75

南京師范大學2011年研究生入學考試試題-科目名稱：地理

信息系統(tǒng)

一、名詞解釋（每題5分，共30分）

1、空間尺度（課本50頁）

2、UTM投影（課本46頁）

3、OpenGIS

4、Voronoi圖（課本80頁）

5、SQL查詢（課本134頁）

6、四叉樹數(shù)據(jù)結(jié)構(gòu)（課本98頁）

二、問答題（每題24分，共120分）

1、試說明G1S的發(fā)展使地圖學的理論、技術(shù)與產(chǎn)品的特征發(fā)生了哪些變化？

2、試說明GIS中對空間實體面積進行量算的基本原理與方法。

3、空間關(guān)系包括哪些基本方面，GIS中不同類型的空間數(shù)據(jù)是如何表達其空間關(guān)系的，各

有何特點？舉例說明空間關(guān)系在空間數(shù)據(jù)處理或空間分析中的作用？

4、試分別分析說明不同的地理信息載體是如何表達地形起伏特征的，各自的關(guān)鍵技術(shù)及在

地形分析中的優(yōu)缺點。

5、請總結(jié)你所參加的一項有關(guān)GIS實踐的活動情況。

要求：1）總結(jié)說明該次實踐工作的目的、內(nèi)容、技術(shù)方法、成果以及自己的貢獻：

2）該次實踐可以是你參加的一項科學研究、系統(tǒng)開發(fā)或GIS應(yīng)用實踐，也

可以是某個課程實驗；

3）對于非GIS專業(yè)的同學，亦可利用自己參加所學專業(yè)相關(guān)實踐為案例說

明。

南京師范大學05~10年研究生入學考試試題-科目名稱：地

理信息系統(tǒng)

2005

一、名詞解釋（每題6分，共30分）

L4D產(chǎn)品：數(shù)字正射影像圖（DigitalOrthophotoMap,即DOM）、數(shù)字高程模型（Digital

elevationmodel,即DEM）、數(shù)字柵格地圖（Digitalrastergraphic即DRG）、數(shù)字線劃地圖

（DigitalLineGraphic,即DLG）?

2.空間數(shù)據(jù)引擎：簡稱SDE,是一種空間數(shù)據(jù)庫管理系統(tǒng)的實現(xiàn)方法，即在常規(guī)管理系統(tǒng)之

上一添加一層空間數(shù)據(jù)庫引擎，以獲得常規(guī)數(shù)據(jù)庫管理系統(tǒng)功能之外的空間數(shù)據(jù)存儲和管理能

力，主要是為了解決存儲在關(guān)系數(shù)據(jù)庫中空間數(shù)據(jù)與應(yīng)用程序之間的數(shù)據(jù)接口問題。其中有

代表性的是ESRI的ArcSDEo（參考）

3.LBS：（Location-BasedService,位置服務(wù)）在移動計算機環(huán)境下，利用GIS技術(shù)、空間定

位技術(shù)和網(wǎng)絡(luò)通信技術(shù)，為移動對象提供基于空間位置的信息服務(wù)。（課本P355頁）

4.數(shù)字高程模型：（DigitalElevationModel,簡稱DEM）是通過有限的地形高程數(shù)據(jù)實現(xiàn)對

地形曲面的數(shù)字化模擬（即地形表面形態(tài)的數(shù)字化表示），高程數(shù)據(jù)常采用絕對高程（即從

大地水準面起算的高度）。（課本P236頁）

5.嵌入式GIS：GIS與嵌入式設(shè)備集成應(yīng)用的產(chǎn)物，它以應(yīng)用為中心，以計算機技術(shù)為基礎(chǔ)，

軟件硬件可裁剪，適應(yīng)應(yīng)用系統(tǒng)對功能、可靠性、成本、體積、功耗嚴格要求的微型專用計

算機系統(tǒng)。（課本P350頁）

二、問答題（共120分）

1.闡述地理信息系統(tǒng)的主要特征（10分）

答：①數(shù)據(jù)的空間定位特征：地理數(shù)據(jù)的三要素中，除屬性和時間外，空間位置特征是地理

空間數(shù)據(jù)有別于其他數(shù)據(jù)的本質(zhì)特征。

②空間關(guān)系處理的復雜性：地理信息系統(tǒng)除要完成一般信息系統(tǒng)的工作外，還要處理與之對

應(yīng)的空間位置和空間關(guān)系，以及與屬性數(shù)據(jù)一一對應(yīng)的處理；空間關(guān)系處理復雜性的另一技

術(shù)難點是數(shù)據(jù)的管理，一般事務(wù)性數(shù)據(jù)都是定長數(shù)據(jù)，地理數(shù)據(jù)是不定長的，存儲和管理這

些空間數(shù)據(jù)是GIS數(shù)據(jù)庫設(shè)計必須面對的問題。

③海量數(shù)據(jù)管理能力：地理信息系統(tǒng)海量數(shù)據(jù)特征來自兩個方面，一是地理數(shù)據(jù)，地理數(shù)據(jù)

是地理信息系統(tǒng)管理的對象，其本身就是海量數(shù)據(jù)；二是來自空間分析，GIS執(zhí)行空間分析

的過程中，不斷地產(chǎn)生新的空間數(shù)據(jù)，這些數(shù)據(jù)也具備海量特征。

2.闡述地理信息系統(tǒng)數(shù)據(jù)組織的發(fā)展及趨勢（30分）

3.闡述主要的地理定位數(shù)據(jù)獲取的方法及原理（30分）

4.闡述電子政務(wù)系統(tǒng)與GIS的關(guān)系（30分）

5.闡述通信技術(shù)發(fā)展與GIS發(fā)展的相互關(guān)系（20分）

2006

一、名詞解釋：（每題6分，共30分）

（1）空間數(shù)據(jù)模型：是GIS抽象的中間層，即GIS的邏輯數(shù)據(jù)模型。它是關(guān)于現(xiàn)實世界中

空間實體及其相互間聯(lián)系的概念，建立在對地理空間的充分認識與完整抽象的地理空間認知

模型（或概念模型）的基礎(chǔ)上，并用計算機能夠識別和處理的形式化語言來定義和描述現(xiàn)實

世界地理實體、地理現(xiàn)象及其相互關(guān)系，是現(xiàn)實世界到計算機世界的直接映射?？臻g數(shù)據(jù)模

型為描述空間數(shù)據(jù)組織和設(shè)計空間數(shù)據(jù)庫提供基本方法，是GIS空間數(shù)據(jù)建模的基礎(chǔ)。數(shù)

據(jù)組織的優(yōu)劣直接影響到空間數(shù)據(jù)庫中數(shù)據(jù)查詢、檢索的方式、速度和效率。（張海榮，地

理信息系統(tǒng)原理與應(yīng)用，中國礦業(yè)大學出版社，2008.2第1次印刷）

（2）空間數(shù)據(jù)結(jié)構(gòu)：是指空間數(shù)據(jù)在計算機內(nèi)的組織和編碼形式。它是一種適合于計算機

存貯、管理和處理的空間數(shù)據(jù)邏輯結(jié)構(gòu)，是地理實體的空間排列和相互關(guān)系的抽象描述。它

是對數(shù)據(jù)的?種理解和解釋。

（3）空間數(shù)據(jù)索引：指依據(jù)空間對象的位置和形狀或空間對象之間的某種空間關(guān)系安?定

順序排列的一種數(shù)據(jù)結(jié)構(gòu)，其中包含空間對象的概要信息。

（4）空間數(shù)據(jù)引擎：簡稱SDE,是一種空間數(shù)據(jù)庫管理系統(tǒng)的實現(xiàn)方法，即在常規(guī)管理系

統(tǒng)之上添加一層空間數(shù)據(jù)庫引擎，以獲得常規(guī)數(shù)據(jù)庫管理系統(tǒng)功能之外的空間數(shù)據(jù)存儲和管

理能力，主要是為了解決存儲在關(guān)系數(shù)據(jù)庫中空間數(shù)據(jù)與應(yīng)用程序之間的數(shù)據(jù)接口問題。其

中有代表性的是ESRI的SDE,

（5）GridGIS：利用現(xiàn)有的網(wǎng)格技術(shù)、空間信息基礎(chǔ)設(shè)施、空間信息網(wǎng)絡(luò)協(xié)議規(guī)范形成一

個虛擬的空間信息管理與處理環(huán)境，將空間地理分布的、異構(gòu)的各種設(shè)備與系統(tǒng)進行集成，

為用戶提供一體化的空間信息應(yīng)用服務(wù)的智能化信息平臺。

二、簡答題（120分）

1、試述空間元數(shù)據(jù)及其作用。（20分）

2、試述地理數(shù)據(jù)的互操作技術(shù)。（20分）

3、闡述電子政務(wù)系統(tǒng)的發(fā)展及其與GIS的關(guān)系。（20分）

4、試述電子商務(wù)的發(fā)展及其與GIS的關(guān)系。（20分）

5、闡述“數(shù)字城市”架構(gòu)及數(shù)據(jù)共享需要解決的關(guān)鍵問題。（20分）

6、試述網(wǎng)絡(luò)地理信息系統(tǒng)的發(fā)展過程及趨勢。（20分）

2007

一、名詞解釋（每題6分，共30分）

1、空間數(shù)據(jù)引擎：簡稱SDE,是一種空間數(shù)據(jù)庫管理系統(tǒng)的實現(xiàn)方法，即在常規(guī)管理系統(tǒng)

之上添加一層空間數(shù)據(jù)庫引擎，以獲得常規(guī)數(shù)據(jù)庫管理系統(tǒng)功能之外的空間數(shù)據(jù)存儲和管理

能力，主要是為了解決存儲在關(guān)系數(shù)據(jù)庫中空間數(shù)據(jù)與應(yīng)用程序之間的數(shù)據(jù)接口問題。其中

有代表性的是ESRI的SDEo

2、空間索引：指依據(jù)空間對象的位置和形狀或空間對象之間的某種空間關(guān)系安一定順序排

列的一種數(shù)據(jù)結(jié)構(gòu)，其中包含空間對象的概要信息。

3、網(wǎng)格GIS：利用現(xiàn)有的網(wǎng)格技術(shù)、空間信息基礎(chǔ)設(shè)施、空間信息網(wǎng)絡(luò)協(xié)議規(guī)范形成一個

虛擬的空間信息管理與處理環(huán)境，將空間地理分布的、異構(gòu)的各種設(shè)備與系統(tǒng)進行集成，為

用戶提供一體化的空間信息應(yīng)用服務(wù)的智能化信息平臺。

4、數(shù)字地形分析：（DigitalTerrainanalysis,DTA）指在數(shù)字高程模型上進行地形屬性計算

和特征提取的數(shù)字信息處理技術(shù)。（課本P237頁）

5、正射影像：是指將中心投影的像片，經(jīng)過糾正處理，在一定程序上限制了因地形起伏引

起的投影誤差和傳感器等誤差產(chǎn)生的像點位移的影像。

二、論述題

1、試述空間數(shù)據(jù)模型與空間數(shù)據(jù)結(jié)構(gòu)的聯(lián)系與區(qū)別。

數(shù)據(jù)模型是數(shù)據(jù)表達的概念模型，數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)表達的物理實現(xiàn)，前者是后者的基礎(chǔ)，后

者是前者的實現(xiàn)。

2、什么是GIS的體系架構(gòu)？GIS的體系架構(gòu)是如何演化的。

3、闡述GIS數(shù)據(jù)組織的主要方式，以及它們的特點。

4、闡述當前GIS輔助地學分析的優(yōu)點和缺點，指出存在問題的解決思路。

5、闡述當前電子政務(wù)系統(tǒng)的特點及發(fā)展趨勢，說明GIS如何在電子政務(wù)系統(tǒng)中發(fā)揮作用。

2008

名詞解釋（共30分，每題5分）

1、空間數(shù)據(jù)引擎：簡稱SDE,是一種空間數(shù)據(jù)庫管理系統(tǒng)的實現(xiàn)方法，即在常規(guī)管理系統(tǒng)

之上添加?層空間數(shù)據(jù)庫引擎，以獲得常規(guī)數(shù)據(jù)庫管理系統(tǒng)功能之外的空間數(shù)據(jù)存儲和管理

能力，主要是為了解決存儲在關(guān)系數(shù)據(jù)庫中空間數(shù)據(jù)與應(yīng)用程序之間的數(shù)據(jù)接口問題。其中

有代表性的是ESRI的SDEo

2、空間數(shù)據(jù)結(jié)構(gòu)：是指空間數(shù)據(jù)在計算機內(nèi)的組織和編碼形式。它是一種適合于計算機存

貯、管理和處理的空間數(shù)據(jù)邏輯結(jié)構(gòu)，是地理實體的空間排列和相互關(guān)系的抽象描述。它是

對數(shù)據(jù)的種理解和解釋。

3、空間數(shù)據(jù)模型：是GIS抽象的中間層，即GIS的邏輯數(shù)據(jù)模型。它是關(guān)于現(xiàn)實世界中空

間實體及其相互間聯(lián)系的概念，建立在對地理空間的充分認識與完整抽象的地理空間認知模

型（或概念模型）的基礎(chǔ)上，并用計算機能夠識別和處理的形式化語言來定義和描述現(xiàn)實世

界地理實體、地理現(xiàn)象及其相互關(guān)系，是現(xiàn)實世界到計算機世界的直接映射。空間數(shù)據(jù)模型

為描述空間數(shù)據(jù)組織和設(shè)計空間數(shù)據(jù)庫提供基本方法，是GIS空間數(shù)據(jù)建模的基礎(chǔ)。數(shù)據(jù)

組織的優(yōu)劣直接影響到空間數(shù)據(jù)庫中數(shù)據(jù)查詢、檢索的方式、速度和效率。（張海榮，地理

信息系統(tǒng)原理與應(yīng)用，中國礦業(yè)大學出版社，2008.2第1次印刷）

4、數(shù)字地形模型：

5、空間定位技術(shù)：

6、空間統(tǒng)計技術(shù)：

論述題：（共120分，每題20分）

1、什么是時空數(shù)據(jù)模型？時空數(shù)據(jù)模型有哪些？時空數(shù)據(jù)模型是如何發(fā)展的？

2、地理空間數(shù)據(jù)有哪些傳輸方式？每種傳輸方式的特點是什么？有哪些發(fā)展趨勢？

3、地理信息系統(tǒng)有哪些體系架構(gòu)？每種體系架構(gòu)的特點是什么？有哪些發(fā)展趨勢？

4、地理空間信息有哪些主要的表達方式？每種表達方式的特點是什么？有哪些發(fā)展趨勢？

5、當前地理信息系統(tǒng)的主要用戶群有哪些？這些用戶群的需求特點是什么？當前應(yīng)用地理

信息系統(tǒng)哪些方面不能適應(yīng)用戶需求？如何改進？

6、什么是社會化地理信息系統(tǒng)？發(fā)展社會化地理信息系統(tǒng)存在的問題是什么？如何解決？

2009

一、名詞解釋

1、SOA：面向服務(wù)的體系結(jié)構(gòu)（Service-OrientedArchitecture,SOA）是一個組件模型,它

將應(yīng)用程序的不同功能單元（稱為服務(wù)）通過這些服務(wù)之間定義良好的接口和契約聯(lián)系起來。

接口是采用中立的方式進行定義的，它應(yīng)該獨立于實現(xiàn)服務(wù)的硬件平臺、操作系統(tǒng)和編程語

言。這使得構(gòu)建在各種這樣的系統(tǒng)中的服務(wù)可以一種統(tǒng)一和通用的方式進行交互。

2、Web服務(wù)：是新一代Web應(yīng)用程序，它們是自包含、自描述、模塊化的應(yīng)用程序，能夠

被發(fā)布、定位，并通過Web調(diào)用：Web服務(wù)可以執(zhí)行從簡單的請求到復雜商務(wù)處理的任何

功能，一旦被部署，其他應(yīng)用程序和Web服務(wù)就可以發(fā)現(xiàn)并調(diào)用這些服務(wù)，其通信協(xié)議主

要基于SOAP,服務(wù)的描述通過WSDL,通過UDDI來發(fā)現(xiàn)和獲得服務(wù)的元數(shù)據(jù)。

3、空間數(shù)據(jù)結(jié)構(gòu)：是指空間數(shù)據(jù)在計算機內(nèi)的組織和編碼形式。它是一種適合于計算機存

貯、管理和處理的空間數(shù)據(jù)邏輯結(jié)構(gòu)，是地理實體的空間排列和相互關(guān)系的抽象描述。它是

對數(shù)據(jù)的一種理解和解釋。

4、空間數(shù)據(jù)引擎：簡稱SDE,是一種空間數(shù)據(jù)庫管理系統(tǒng)的實現(xiàn)方法，即在常規(guī)管理系統(tǒng)

之上添加一層空間數(shù)據(jù)庫引擎，以獲得常規(guī)數(shù)據(jù)庫管理系統(tǒng)功能之外的空間數(shù)據(jù)存儲和管理

能力，主要是為了解決存儲在關(guān)系數(shù)據(jù)庫中空間數(shù)據(jù)與應(yīng)用程序之間的數(shù)據(jù)接口問題。其中

有代表性的是ESRI的SDEo

5、地統(tǒng)計學：

6、數(shù)字地形模型：

二、論述題（共120分，每題20分）

1、什么是地理元數(shù)據(jù)？地理元數(shù)據(jù)包括哪些內(nèi)容，有什么用途？

2、什么是組件式GIS?組件式GIS的特征以及存在問題是什么？

3、什么是服務(wù)型GIS?服務(wù)型GIS的特征是什么？

4、支撐GIS的網(wǎng)絡(luò)平臺有哪些類型？這些網(wǎng)絡(luò)平臺之間如何連接？

5、闡述VirtualEarth的特點，VirtualEarth可能對GIS發(fā)展的作用。

6、闡述一個應(yīng)用GIS系統(tǒng)建設(shè)工程所包含的主要內(nèi)容，需要關(guān)注的要點是什么？

2010

一、名詞解釋（每題6分，共30分）

1、網(wǎng)絡(luò)GIS：網(wǎng)絡(luò)GIS有技術(shù)的狹義網(wǎng)絡(luò)GIS和宏觀的廣義網(wǎng)絡(luò)GIS之分。在一定時期內(nèi)

特定形式的計算機網(wǎng)絡(luò)和分布式對象技術(shù)的融合所形成的GIS系統(tǒng)便是狹義的網(wǎng)絡(luò)GIS；廣

義網(wǎng)絡(luò)GIS不僅是所有狹義網(wǎng)絡(luò)GIS的統(tǒng)稱，同時也代表了不同狹義GIS結(jié)合時的產(chǎn)物。

2、服務(wù)型GIS：采用面向服務(wù)的軟件工程方法，把GIS的全部功能封裝為Web服務(wù)（Web

Service）,從而實現(xiàn)了被多種客戶端跨平臺、跨網(wǎng)絡(luò)、跨語言地調(diào)用，并具備了服務(wù)聚合能

力以集成來自其他服務(wù)器發(fā)布的服務(wù)的GIS系統(tǒng)。

3、SOA架構(gòu)：面向服務(wù)的體系結(jié)構(gòu)（Service-OrientedArchitecture,SOA）是-一個組件模型，

它將應(yīng)用程序的不同功能單元（稱為服務(wù)）通過這些服務(wù)之間定義良好的接口和契約聯(lián)系起

來。接口是采用中立的方式進行定義的，它應(yīng)該獨立于實現(xiàn)服務(wù)的硬件平臺、操作系統(tǒng)和編

程語言。這使得構(gòu)建在各種這樣的系統(tǒng)中的服務(wù)可以一種統(tǒng)一和通用的方式進行交互。

4、WebService技術(shù)：是新一代Web應(yīng)用程序，它們是自包含、自描述、模塊化的應(yīng)用程序，

能夠被發(fā)布、定位，并通過Web調(diào)用；Web服務(wù)可以執(zhí)行從簡單的請求到復雜商務(wù)處理的

任何功能，一旦被部署，其他應(yīng)用程序和Web服務(wù)就可以發(fā)現(xiàn)并調(diào)用這些服務(wù)，其通信協(xié)

議主要基于SOAP,服務(wù)的描述通過WSDL,通過UDDI來發(fā)現(xiàn)和獲得服務(wù)的元數(shù)據(jù)。

5、傳感器網(wǎng)絡(luò):傳感器網(wǎng)絡(luò)是由大量部署在作用區(qū)域內(nèi)的具有無線通信與計算能力的微小傳

感器節(jié)點通過自組織方式構(gòu)成的能根據(jù)環(huán)境自主完成指定任務(wù)的分布式智能化網(wǎng)絡(luò)系統(tǒng)。

二、論述題（每題24分）

1、闡述矢量G1S與柵格G1S型GIS的特點與存在問題，如何實現(xiàn)矢柵地理數(shù)據(jù)的一體化存

儲與管理？

2、試從數(shù)據(jù)生產(chǎn)的過程論述4D產(chǎn)品的特征，4D產(chǎn)品對GIS發(fā)展的貢獻和存在問題。

3、在GIS發(fā)展過程中有哪些體系架構(gòu)，各自的特點是什么？

4、闡述基礎(chǔ)地理數(shù)據(jù)更新的主要方法及各自的特點，從技術(shù)和制度上如何保證基礎(chǔ)地理數(shù)

據(jù)的現(xiàn)勢性？

5、地理數(shù)據(jù)共享有哪些模式，如何從體系架構(gòu)、數(shù)據(jù)交換等關(guān)鍵技術(shù)方面，以及法律法規(guī)

和政策方面保證地理數(shù)據(jù)的共享？

南京師范大學2011年研究生入學考試試題-科目名稱：C語

言程序設(shè)計（含數(shù)據(jù)結(jié)構(gòu)）

1、編寫一個程序，求用戶輸入的開始時間到終止時間之間相距的天數(shù)。（本題15分）

2,編寫一個程序，利用遞歸法實現(xiàn)將用戶輸入的字符串逆序排列.（本題15分）

3、找出所有200以內(nèi)（含200）滿足1,1+4,1+10都是素數(shù)的整數(shù)I（1+10也在200以內(nèi)）的

個數(shù)以及這些數(shù)之和sum。井把所有這些數(shù)、個數(shù)和sum按文本文件輸出到文件out.dat中。

（本題20分）

4、編寫程序，判斷兩線段是否相交。（本題20分）

5、假設(shè)以帶頭節(jié)點的循環(huán)鏈表表示隊列，并只設(shè)一個指針指向?qū)ξ苍毓?jié)點（不設(shè)頭指針）,

編寫相應(yīng)的隊列初始化、入隊列和出隊列算法。（本題20分）

6、假設(shè)有兩個按元素值遞增有序排列的線性表A和B,均以單鏈表作存儲結(jié)構(gòu)，請編寫算

法將表A和表B歸并成一個按元素值非遞減有序（允許值相同）排列的線性表C,并要求

利用原表（即表A和表B）的結(jié)點空間存放表。（本題20分）

7、給定一棵樹用二叉鏈表表示的二叉樹，其中的指針t指向根結(jié)點，試寫出從根開始，按

層次遍歷二叉樹的算法，周層的結(jié)點按從左到右的次序訪問。（本題20分）

8、若S是n個元素的集合，則S的騫集P（S）定義為S的所有子集的集合。例如，

S=（a,b,c）,P（S）=｛（）,（a）,（b）,（c）,（a,b）,（a,c）,（b,c）,（a,b,c）｝。給定S,寫一遞歸算法求P（S）.（本題20

分）

1、解題思路：假如計算2005年5月20日至2008年9月12日之間經(jīng)過的天數(shù)，則以2005年1月1

日為起點，分別計算2005年5月20日和2008年9月12日至2005年1月1日的天數(shù)，兩者天數(shù)相減，

則可以求出兩者相距的天數(shù)。

2、解題思路：假如一個字符串有n個字符，用遞歸方法進行第1與第n字符交換、第2與第

n-1個字符交換…直到字符串的中間位置。

3、解題思路：將符合條件的所有元素I存入一個數(shù)組中，并記錄個數(shù)，再求和

4、解題思路：如果兩條線段平行，則兩條線段定不相交；如果不平行，則求兩線段所在的

直線的交點，再判斷該交點是否在線段匕如果在線段上，則表示兩線段相交，如果不在線

段上，則表示兩線段不相交。

5、參照嚴蔚敏的數(shù)據(jù)結(jié)構(gòu)（C語言版）課本64頁循環(huán)隊列-隊列的順序存儲結(jié)構(gòu)

6、參照嚴蔚敏的數(shù)據(jù)結(jié)構(gòu)（C語言版）課本31頁算法2.12

7、參照嚴蔚敏的數(shù)據(jù)結(jié)構(gòu)（C語言版）課本17（）頁算法7.6

8、對照嚴蔚敏的數(shù)據(jù)結(jié)構(gòu)（C語言版）課本149頁例6-3

南京師范大學2010年研究生入學考試試題-科目名稱：C語

言程序設(shè)計(含數(shù)據(jù)結(jié)構(gòu))

1、給出年、月、日，計算該日是該年的第幾天。(本題15分)

參考解法：

#include<stdio.h>

intget_days_of_month(intyear,intmonth)

(

if(month==lllmonth==3llmonth==5llmonth==7llmonth==8llmonth==10llmonth==12)

return31;

elseif(month==2)

if(year%400=0II(year%4==0&&year%100!=0))

return29;

else

return28;

else

return30;

)

voidmain()

{

inti,year,month,day,sum=O,flag=1;

while(flag)

{

printf("pleaseinputthedate(forexample:2005,6,9):M);

scanf(n%d,%d,%dn,&year,&month,&day);

if(year>0)

if(month>=l&&month<=12)

if(day>=l&&day<=get_days_ofLmonth(year,month))

flag=0;

)

for(i=l;i<month;i++)

(

sum+=get_days_oLmonth(year,i);

)

sum+=day;

printf(MThedateis%dday.\nu,sum);

)

2、有幾個學生，每個學生考m門課，要求編一函數(shù)，能檢查n個學生有無不及格的課程，

如

果有某一學生有一門或一門以上課程不及格，就輸出該學生的學號(學號從0開始)和其全

部課程成績。(本題15分)

參考解法：

#include<stdio.h>

#defineN100

voidmain()

(

inta[N][N];

intij,m,n,flag;

printf("pleaseinputthenumberofstudents:'1);

scanf("%d",&n);

printf("pleaseinputthenumberofcourses:");

scanf("％d”,&m);

for(i=0;i<n;i++)

(

printf("pleaseinputNo.%dscores:n,i);

for(j=0;j<m;j++)

scanf(”％d，&a[i][jD;

)

printf("studentswhohavefailedtheircoursesasfollows:'1);

for(i=0;i<n;i++)

(

flag=0;

for(j=0;j<m;j++)

(

if(a[i]|j]<60)

{flag=l;break;}

}

if(flag)

(

printf("No.%d",i);

for(j=0;j<m;j++)

printf("%dM,a[i][j]);

)

printf(”\n")；

}

)

3、用二分法求方程”(2*XA3)?(4*xA2)+(3*x)?6=0”在(-10,10)之間的根。(本題20分)

#include<stdio.h>

#include<math.h>

floatgetresult(floatx)

return(2*x*x*x-4*x*x+3*x-6);

voidmain()

(

floatx0,xl,x2,y0,yl,y2;

do

(

printf("pleaseinputxlandx2:");

scanf(',%f,%f,,&xl,&x2);

yl=getresult(xl);

y2=getresult(x2);

}while(yl*y2>0);

do

(

xO=(xl+x2)/2;

yO=getresult(xO);

if(yO*yl>O)

xl=xO;

else

x2=xO;

}while(fabs(y0)>le-5);

printf(HTherootis%f.\nM,xO);

}

4、請寫出判斷“點是否在簡單多邊形內(nèi)部”的算法。(本題20分)

〃相對正確的解題思路：從該點向某一個方向做一條射線，如果與多邊形相交的點是奇數(shù)個,

則在多邊形內(nèi)；否則，可能在多邊形內(nèi)。

〃不太正確的解題思路：如果一個點在一個多邊形內(nèi)，那么從該點向上、向下、向左、向右

都應(yīng)與簡單

〃多邊有交點，點在某一條邊上算在多邊形內(nèi)(下面的程序代碼也有問題)。

#include<stdio.h>

#defineN10

typedefstructNode

(

floatx;

floaty;

}XYNode,Nodes[N+l];

voidmain()

(

inti,up=0,down=0,left=0,right=0;

intx0,xl,x2,y0,yl,y2;

charflag=Y1;

XYNodepoint;

Nodesa;

for(i=0;i<N;i++)

printf("pleaseinputthe%dstcoordinate:0,i+1);

scanf(H%f,%f',&a[i].x,&a[i].y);

)

a[N].x=a[0].x;〃使起點和終點的坐標相同

a[N].y=a[0].y;

while(flag!=,n,&&flag!='N')

(

printf(nNow,pleaseinputthePoint'scoordinate:");

scanf(n%f,%f',&point.x,&point.y);

for(i=0;i<N;i++)

(

if((a[i].x>point.x&&a[i+l].x<=point.x)ll(a[i].x<point.x&&a[i-i-l].x>=point.x))

(

xl=a[i].x;

yl=a[i].y;

x2=a[i+l].x;

y2=a[i+l].y;

xO=point.x;

yO=(y1-y2)*(x0-x1)/(x1-x2)+yl;

if(yO==point.y)

{

up=1;down=1;left=1;right=1;

break;

)

elseif(yO>point.y)

up=1；

else

down=1;

}//if

if((a[i].y>point.y&&a[i+l].y<=point.y)ll(a[i].y<point.y&&a[i+l].y>=point.y))

(

xl=a[i].x;

yl=a[i].y;

x2=a[i+l].x;

y2=a[i+l].y;

yO=point.y;

xO=(xl-x2)*(y0-yl)/(yl-y2)+xl;

if(xO==point.x)

(

up=1;down=1;left=1;right=1;

break;

)

elseif(xO>point.y)

right=I;

else

left=1;

}//if

}//for

if(up&&down&&left&&right)

printf("Yes,thepointisinthepolygon.\n");

else

printf("No,thepointisnotinthepolygonAn°);

while(getchar()!=\n');〃接收多余的字符

printf(nwouldyouliketogoon?<Y/N>n);

flag=getchar();//flag只接收第一個字符

while(getchar()!=\n');〃接收多余的字符

}//while

）

5、從平均時間、最壞情況，輔助存儲和穩(wěn)定性的角度，對各種內(nèi)部排序方法進行比較。

（建議用表格方式進行比較，本題20分）

嚴蔚敏數(shù)據(jù)結(jié)構(gòu)289頁

6、定義一個雙向循環(huán)鏈表，并寫出其定位、插入和刪除算法。（本題20分）

#include<stdio.h>

#include<stdlib.h>

#defineOK1

#defineERROR0

typedefintStatus;

typedefintElemType;

typedefstructDuLNode

(

ElemTypedata;

structDuLNode*prior;

structDuLNode*next;

)DuLNode,*DuLinkList;

StatusGetElem_DuL(DuLinkListLjnti,ElemType*e)

{

intj=1;

DuLNode*p;

p=L->next;

while(p!=L&&j<i)

p=p->next;

j++；

if(p==Lllj!=i)

returnERROR;

*e=p->data;

returnOK;

)

StatusListInsert_DuL(DuLinkList&L,inti,ElemTypee)

{〃在帶頭結(jié)點的雙鏈循環(huán)鏈表L中第i個位置之前插入元素e

〃i的合法位置為Iv二iv二表長+1

intj;

DuLNode*p,*s;

if(ivl)〃如果i的值小于1,則返回錯誤

returnERROR;

j=1;

p=L->next;

while(p!=L&&j<i)

I

p=p->next;

j++；

}

〃查找完循環(huán)鏈表后，如果j<i,則表明i的位置不合法

returnERROR;

if(!(s=(DuLNode*)malloc(sizeof(DuLNode))))

returnERROR;

s->data=e;

s->prior=p->prior;

p->prior->next=s;

s->next=p;

p->prior=s;

returnOK;

}

StatusListDelete_DuL(DuLinkList&L,inti,ElemType*e)

{//刪除帶頭結(jié)點的雙鏈循環(huán)線性表L的第i個元素，i的合法位置為lv=iv;表長

intj;

DuLNode*p;

if(i<D

returnERROR;

j=1;

p=L->next;

while(p!=L&&j<i)

(

p=p->next;

j++；

if(p==L)

returnERROR;

*e=p->data;

p->prior->next=p->next;

p->next->prior=p->prior;

free(p);

returnOK;

)

voidprint(DuLinkListL)

(

DuLNode*p;

p=L->next;

while(p!=L)

(

printf(''%dM,p->data);

p=p->next;

)

printf(',\n'');

)

voidmain()

(

inti;

ElemTypee;

DuLinkListL;

if(!(L=(DuLNode*)malloc(sizeof(DuLNode))))

exit(O);

L->next=L;

L->prior=L;

for(i=l;i<10;i++)

{

e=(ElemType)i;

if(!(ListInsert_DuL(L,i,e)))

printf("No.%diswrong!\nM,i);

)

print(L);

ListInsert_DuL(L,5,(ElemType)10);

print(L);

ListDeIete_DuL(L,1,&e);

print(L);

printf("pleaseinputanumber:");

scanf(H%dn,&i);

if(GetElem_DuL(L,i,&e))

printf(,,L[%d]=%d\n",i,e);

else

printf（n%disillegal!\nM,i）;

）

7、編制?個程序以模擬銀行窗口接待客戶的排隊業(yè)務(wù)活動（每個窗口在某個時刻只能接待

一個客戶；窗口空閑，則可上前辦理業(yè)務(wù)；窗口均被占，則新客戶便會排在人數(shù)最少的隊伍

前面），并計算一天中客戶在銀行逗留的平均時間。（本題20分）

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

#defineMAX10000

#defineOK1

#defineERROR0

/**********數(shù)據(jù)型定義(Start)**********/

typedefintStatus;

typedefstruct

intOccurTime;〃事件發(fā)生時刻

intNType;〃事件類型，0~5

}Event,ElemType;〃事件類型，有序鏈表LinkList的數(shù)據(jù)元素類型

typedefstructLNode

ElemTypedata;

structLNode*next;

}LNode,*LinkList;

typedefLinkListEventList;〃事件鏈表類型，定義為有序鏈表

typedefstruct

(

intAirivalTime;〃到達時間

intDuration;〃辦理事務(wù)所需時間

JQElemType;〃隊列的數(shù)據(jù)元素類型

typedefstructQNode

(

QElemTypedata;

structQNode*next;

}QNode,*QueuePtr;

typedefstruct

QueuePtrfront;

QueuePtrrear;

JLinkQueue;

/**********數(shù)據(jù)類型定義(Over)**********/

/**********程序中用到的主要變量(Start)**********/

EventListev;〃事件表

Eventen;〃事件

LinkQueueq[5];〃4個客戶隊列

QElemTypecustomer;〃客戶記錄

longTotalTime,CustomerNum;〃累計客戶逗留時間，客戶數(shù)

/**********程序中用至的主要變量（Over）**********/

[**********?芻i^|(Start)**********/

/****鏈表操作部分(start)****/

intcmp(ElemTypea,ElemTypeb)

if(a.OccurTimob.OccurTime)

return1;

elseif(a.OccurTime==b.OccurTime)

return0;

else

return-1;

voidInitList(LinkList&L)

(

L=(LNode*)malloc(sizeof(LNode));

if(!L)

printf—EVENTLISTINITERROR!\nu);

else

{

L->next=NULL;

)

}

voidOrderInsert(LinkListL,ElemTypeen)

(

LNode*p,*q,*s;

p=L;

q=p->next;

while(q&&(cmp(q->data,en)==-1))

(

p二q；

q=p->next;

)

s=(LNode*)malloc(sizeof(LNode));

s->data.OccurTime=en.OccurTime;

s->data.NType=en.NType;

p->next=s;

s->next=q;

)

intListEmpty(LinkListL)

(

if(L->next!=NULL)

return0;

else

return1;

)

voidDelFirst(LinkListL,ElemType*e)

(

LNode*p;

p=L->next;

L->next=p->next;

e->OccurTime=p->data.OccurTime;

e->NType=p->data.NType;

free(p);

)

/****鏈表操作部分(over)****/

/****隊列操作部分(start)****/

voidInitQueue(LinkQueue*Q)

(

Q->front=Q->rear=(QNode*)malloc(sizeof(QNode));

if(!(Q->front))

printf(nLinkQueueINITERROR!\nn);

Q->front->next=NULL;

StatusDelQueue(LinkQueue*Q,QElemType*e)

QNode*p;

if(Q->front==Q->rear)returnERROR;

p=Q->front->next;

e->ArrivalTime=p->data.AnivalTime;

e->Duration=p->data.Duration;

Q->front->next=p->next;

if(Q->rear==p)Q->rear=Q->front;

free(p);

returnOK;

StatusEnQueue(LinkQueue*Q,QElemTypee)

(

QNode*p;

p=(QNode*)malloc(sizeof(QNode));

if(!p)exit(O);

p->data.ArrivalTime=e.ArrivalTime;

p->data.Duration=e.Duration;

p->next=NULL;

Q->rear->next=p;

Q->rear=p;

returnOK;

)

intQueueLength(LinkQueue*Q)

(

inti=0;

QNode*p;

if(Q->front==Q->rear)i=0;

else

{

p=Q->front;

while(p!=Q->rear)

(

p=p->next;

i++；

returni;

/****隊列操作部分(over)****/

/****業(yè)務(wù)操作部分(start)****/

voidRandom(long*durtime,longWintertime)

(

srand(time(NULL));

*durtime=rand();

*intertime=rand();

)

intMinimum(LinkQueueq[])

(

inti,j,k=0,min=MAX;

QNode*p;

for(i=l;i<=4;i++)

(

if(q[i].front==q[i].rear)

j=0；

else

(

p=q[i].front->next;

j=1;

while(p!=q[i].rear)

(

p=p->next;

j++;

)

)

if(min>j)

(

min=j;

k=i;

)

}

returnk;

)

voidOpenForDayO

(

inti;

TotalTime=0;CustomerNum=0;

InitList(ev);

en.OccurTime=0;en.NType=0;

Orderlnsert(ev,en);

for(i=l;i<=4;i++)

InitQueue(&q[i]);

)

voidCustomerArrived(intCloseTime)

(

longdurtime,intertime,i,t;

++CustomerNum;

Random(&durtime,&intertime);

printf("durtime=%ld,intertime=%ld\n",durtime,intertime);

t=en.OccurTime+intertime;

i=Minimum(q);

customer.AmvalTime=en.OccurTime;

customer.Duration=durtime;

EnQueue(&q[i],customer);

if(QueueLength(&q[i])==l)

(

en.OccurTime=en.OccurTime+durtime;

en.NType=i;

Orderlnsert(ev,en);

)

if(t<CloseTime)

(

en.OccurTime=t;

en.NType=0;

Orderlnsert(ev,en);

voidCustomerDeparture()

(

inti;

i=en.NType;DelQueue(&q[i],&customer);

TotalTime+=en.OccurTime-customer.ArrivalTime;

if(QueueLength(&q[i]))

(

QNode*p=q[i].front->next;

QElemTypeqe=p->data;

customer.ArrivalTime=qe.AirivalTime;

custome匚Duration=qe.Duration;

en.OccurTime=en.OccurTime+custome匚Duration;

en.NType=i;

Orderlnsert(ev,en);

voidBank_Simulation(intCloseTime)

inti=0;

OpenForDayO;

while(IListEmpty(ev))

{

DelFirst(ev,&en);

i=en.NType;

if(i==0)

CustomerArrived(CloseTime);

else

CustomerDeparture();

)

printf(HTheAverageTimeis%ld,%ld\n'\TotalTime,CustomerNum);

printf("TheAverageTimeis%f\n'\(float)TotalTime/CustomerNum);

)

/****業(yè)務(wù)操作部分(over)****/

/**********|^|苦B夕》(Over)**********/

voidmain()

Bank_Simulation(99999);

)

8、設(shè)T是正則二叉樹（若根樹T的每個結(jié)點都恰有左右兩個二則，則該樹T被稱為正則二

叉樹）

它具有6片樹葉，那么樹T的高度最多可以是多少，最小可以是多少；樹T的內(nèi)結(jié)點數(shù)是多

少，

如果T又是Huffman最優(yōu)樹，且各片樹葉的數(shù)分別是1,2,3,4,4,6,則最優(yōu)樹T的非

樹葉

結(jié)點的數(shù)之和是多少，數(shù)為1的樹葉的高度是多少。（注：樹的根結(jié)點高度為1;本題寫出答

案即可；本題20分）

參考解答：

〃關(guān)于正則二叉樹在嚴蔚敏的數(shù)據(jù)結(jié)構(gòu)書的146頁最下面一段里，如下：

〃由于赫夫曼沒有度為1的結(jié)點（這類樹又稱為嚴格的（strict）（或正則的）二叉樹），則一棵

〃有n個葉子結(jié)點的赫夫曼樹共有2n-l個結(jié)點，可以存儲在?個大小為2n-l的一維數(shù)組中。

樹T的高度最多可以是6,最小可能是4

樹T的內(nèi)結(jié)點數(shù)是5

最優(yōu)樹T的非樹葉結(jié)點的數(shù)之利是49

數(shù)為1的樹葉的高度是5。

南京師范大學2009年研究生入學考試試題-科目名稱：C語

言程序設(shè)計(含數(shù)據(jù)結(jié)構(gòu))

(1)設(shè)計一個程序，找出1—200之間的所有水仙花數(shù)。所謂水仙花數(shù)是指各個數(shù)字的立方

和恰好

等于該數(shù)本身。例如：153=1*1*1+5*5*5+3*3*3?(本題15分)

參考解法1：

#include<stdio.h>

voidmain()

(

inti,j,k,n;

for(n=1;n<=200;n++)

(

i=n/100;

j=(n-i*100)/10;

k=n%100%10;

if(i*i*i+j*j*j+k*k*k==n)

printf(H%3disanarcissusnumber.\n",n);

)

}

參考解法2：

#include<stdio.h>

voidmain()

(

intij,s,n;

for(n=1;n<=200;n++)

(

j=n;

i=0;

s=0;

while(j!=0)

(

i=j%10;

s+=i*i*i；

j=j/10;

)

if(s==n)

printf("%3disanarcissusnumber.\n*\n);

(2)設(shè)計一個程序，實現(xiàn)輸入一個給定的正整數(shù)N,打卬出所有不超過N的，其平方為回

文

(回文是指字符串兩半的字符左右對稱，例如1,22,121,4224等均是回文)的數(shù)(本題15

分)

參考解法：

#include<stdio.h>

voidtest(intn)

(

inti=O,j=-l,k;

inta[10];

k=n*n;

while(k!=0)

(

a|++j]=k%10;

k=k/10;

)

while(i<j)

(

if(a[i]==a[j])

(

i++；

j-;

)

else

break;

)

if(i>=j)

printf("%d'ssquare%disapalindromenumber!\n",n,n*n);

)

voidmain()

(

inti,n;

printf(Hpleaseinputanumber

scanf("%d',,&n);

for(i=l;i<n;i++)

test(i);

)

(3)編寫程序用于統(tǒng)計字符串中最長單詞的長度和在字符串中的位置，其中單詞由字母組成。

(本題20分)

參考解法：

#include<stdio.h>

voidmain()

(

inti,count=0,pos=0,maxlen=0;

charch;

chars[80]="whatai-eyoudoing'1;

//printf(Minputastring:1');

//gets(s);

i=-l；

do

(

i++；

ch=s[i];

if((ch>='A'&&ch<=,Z,)II(ch>='a,&&ch<=,z,))

(

count++;

)

else

(

if(count>maxlen)

(

maxlen=count;

pos=i-maxlen;

)

count=0;

}

)while(s[i]!=W);

printf(nThemaxlengthwordis\',n);

for(