南京师范大学地理信息系统考研试题2003-2011

南京师范大学2011年研究生入学考试试题-科目名称：地理信息系统..................1

南京师范大学05~10年研究生入学考试试题-科目名称：地理信息系统.................2

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

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

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

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

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

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

南京师范大学2011年研究生入学考试试题-科目名称：C语言程序设计（含数据结构）....6

南京师范大学2010年研究生入学考试试题-科目名称：C语言程序设计（含数据结构）....7

南京师范大学2009年研究生入学考试试题-科目名称：C语言程序设计（含数据结构）..21

南京师范大学2008年研究生入学考试试题-科目名称：C语言程序设计（含数据结构）..31

南京师范大学2007年研究生入学考试试题-科目名称：C语言程序设计（含数据结构）..43

南京师范大学2006年研究生入学考试试题-科目名称：C语言程序设计（含数据结构）..52

南京师范大学2005年研究生入学考试试题-科目名称：C语言程序设计（含数据结构）..60

南京师范大学2004年研究生入学考试试题-科目名称：C语言程序设计（含数据结构）..68

南京师范大学2003年研究生入学考试试题-科目名称：C语言程序设计（含数据结构）..75

南京师范大学2011年研究生入学考试试题-科目名称：地理

信息系统

一、名词解释（每题5分，共30分）

1、空间尺度（课本50页）

2、UTM投影（课本46页）

3、OpenGIS

4、Voronoi图（课本80页）

5、SQL查询（课本134页）

6、四叉树数据结构（课本98页）

二、问答题（每题24分，共120分）

1、试说明G1S的发展使地图学的理论、技术与产品的特征发生了哪些变化？

2、试说明GIS中对空间实体面积进行量算的基本原理与方法。

3、空间关系包括哪些基本方面，GIS中不同类型的空间数据是如何表达其空间关系的，各

有何特点？举例说明空间关系在空间数据处理或空间分析中的作用？

4、试分别分析说明不同的地理信息载体是如何表达地形起伏特征的，各自的关键技术及在

地形分析中的优缺点。

5、请总结你所参加的一项有关GIS实践的活动情况。

要求：1）总结说明该次实践工作的目的、内容、技术方法、成果以及自己的贡献：

2）该次实践可以是你参加的一项科学研究、系统开发或GIS应用实践，也

可以是某个课程实验；

3）对于非GIS专业的同学，亦可利用自己参加所学专业相关实践为案例说

明。

南京师范大学05~10年研究生入学考试试题-科目名称：地

理信息系统

2005

一、名词解释（每题6分，共30分）

L4D产品：数字正射影像图（DigitalOrthophotoMap,即DOM）、数字高程模型（Digital

elevationmodel,即DEM）、数字栅格地图（Digitalrastergraphic即DRG）、数字线划地图

（DigitalLineGraphic,即DLG）»

2.空间数据引擎：简称SDE,是一种空间数据库管理系统的实现方法，即在常规管理系统之

上一添加一层空间数据库引擎，以获得常规数据库管理系统功能之外的空间数据存储和管理能

力，主要是为了解决存储在关系数据库中空间数据与应用程序之间的数据接口问题。其中有

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

3.LBS：（Location-BasedService,位置服务）在移动计算机环境下，利用GIS技术、空间定

位技术和网络通信技术，为移动对象提供基于空间位置的信息服务。（课本P355页）

4.数字高程模型：（DigitalElevationModel,简称DEM）是通过有限的地形高程数据实现对

地形曲面的数字化模拟（即地形表面形态的数字化表示），高程数据常采用绝对高程（即从

大地水准面起算的高度）。（课本P236页）

5.嵌入式GIS：GIS与嵌入式设备集成应用的产物，它以应用为中心，以计算机技术为基础，

软件硬件可裁剪，适应应用系统对功能、可靠性、成本、体积、功耗严格要求的微型专用计

算机系统。（课本P350页）

二、问答题（共120分）

1.阐述地理信息系统的主要特征（10分）

答：①数据的空间定位特征：地理数据的三要素中，除属性和时间外，空间位置特征是地理

空间数据有别于其他数据的本质特征。

②空间关系处理的复杂性：地理信息系统除要完成一般信息系统的工作外，还要处理与之对

应的空间位置和空间关系，以及与属性数据一一对应的处理；空间关系处理复杂性的另一技

术难点是数据的管理，一般事务性数据都是定长数据，地理数据是不定长的，存储和管理这

些空间数据是GIS数据库设计必须面对的问题。

③海量数据管理能力：地理信息系统海量数据特征来自两个方面，一是地理数据，地理数据

是地理信息系统管理的对象，其本身就是海量数据；二是来自空间分析，GIS执行空间分析

的过程中，不断地产生新的空间数据，这些数据也具备海量特征。

2.阐述地理信息系统数据组织的发展及趋势（30分）

3.阐述主要的地理定位数据获取的方法及原理（30分）

4.阐述电子政务系统与GIS的关系（30分）

5.阐述通信技术发展与GIS发展的相互关系（20分）

2006

一、名词解释：（每题6分，共30分）

（1）空间数据模型：是GIS抽象的中间层，即GIS的逻辑数据模型。它是关于现实世界中

空间实体及其相互间联系的概念，建立在对地理空间的充分认识与完整抽象的地理空间认知

模型（或概念模型）的基础上，并用计算机能够识别和处理的形式化语言来定义和描述现实

世界地理实体、地理现象及其相互关系，是现实世界到计算机世界的直接映射。空间数据模

型为描述空间数据组织和设计空间数据库提供基本方法，是GIS空间数据建模的基础。数

据组织的优劣直接影响到空间数据库中数据查询、检索的方式、速度和效率。（张海荣，地

理信息系统原理与应用，中国矿业大学出版社，2008.2第1次印刷）

（2）空间数据结构：是指空间数据在计算机内的组织和编码形式。它是一种适合于计算机

存贮、管理和处理的空间数据逻辑结构，是地理实体的空间排列和相互关系的抽象描述。它

是对数据的•种理解和解释。

（3）空间数据索引：指依据空间对象的位置和形状或空间对象之间的某种空间关系安•定

顺序排列的一种数据结构，其中包含空间对象的概要信息。

（4）空间数据引擎：简称SDE,是一种空间数据库管理系统的实现方法，即在常规管理系

统之上添加一层空间数据库引擎，以获得常规数据库管理系统功能之外的空间数据存储和管

理能力，主要是为了解决存储在关系数据库中空间数据与应用程序之间的数据接口问题。其

中有代表性的是ESRI的SDE,

（5）GridGIS：利用现有的网格技术、空间信息基础设施、空间信息网络协议规范形成一

个虚拟的空间信息管理与处理环境，将空间地理分布的、异构的各种设备与系统进行集成，

为用户提供一体化的空间信息应用服务的智能化信息平台。

二、简答题（120分）

1、试述空间元数据及其作用。（20分）

2、试述地理数据的互操作技术。（20分）

3、阐述电子政务系统的发展及其与GIS的关系。（20分）

4、试述电子商务的发展及其与GIS的关系。（20分）

5、阐述“数字城市”架构及数据共享需要解决的关键问题。（20分）

6、试述网络地理信息系统的发展过程及趋势。（20分）

2007

一、名词解释（每题6分，共30分）

1、空间数据引擎：简称SDE,是一种空间数据库管理系统的实现方法，即在常规管理系统

之上添加一层空间数据库引擎，以获得常规数据库管理系统功能之外的空间数据存储和管理

能力，主要是为了解决存储在关系数据库中空间数据与应用程序之间的数据接口问题。其中

有代表性的是ESRI的SDEo

2、空间索引：指依据空间对象的位置和形状或空间对象之间的某种空间关系安一定顺序排

列的一种数据结构，其中包含空间对象的概要信息。

3、网格GIS：利用现有的网格技术、空间信息基础设施、空间信息网络协议规范形成一个

虚拟的空间信息管理与处理环境，将空间地理分布的、异构的各种设备与系统进行集成，为

用户提供一体化的空间信息应用服务的智能化信息平台。

4、数字地形分析：（DigitalTerrainanalysis,DTA）指在数字高程模型上进行地形属性计算

和特征提取的数字信息处理技术。（课本P237页）

5、正射影像：是指将中心投影的像片，经过纠正处理，在一定程序上限制了因地形起伏引

起的投影误差和传感器等误差产生的像点位移的影像。

二、论述题

1、试述空间数据模型与空间数据结构的联系与区别。

数据模型是数据表达的概念模型，数据结构是数据表达的物理实现，前者是后者的基础，后

者是前者的实现。

2、什么是GIS的体系架构？GIS的体系架构是如何演化的。

3、阐述GIS数据组织的主要方式，以及它们的特点。

4、阐述当前GIS辅助地学分析的优点和缺点，指出存在问题的解决思路。

5、阐述当前电子政务系统的特点及发展趋势，说明GIS如何在电子政务系统中发挥作用。

2008

名词解释（共30分，每题5分）

1、空间数据引擎：简称SDE,是一种空间数据库管理系统的实现方法，即在常规管理系统

之上添加•层空间数据库引擎，以获得常规数据库管理系统功能之外的空间数据存储和管理

能力，主要是为了解决存储在关系数据库中空间数据与应用程序之间的数据接口问题。其中

有代表性的是ESRI的SDEo

2、空间数据结构：是指空间数据在计算机内的组织和编码形式。它是一种适合于计算机存

贮、管理和处理的空间数据逻辑结构，是地理实体的空间排列和相互关系的抽象描述。它是

对数据的种理解和解释。

3、空间数据模型：是GIS抽象的中间层，即GIS的逻辑数据模型。它是关于现实世界中空

间实体及其相互间联系的概念，建立在对地理空间的充分认识与完整抽象的地理空间认知模

型（或概念模型）的基础上，并用计算机能够识别和处理的形式化语言来定义和描述现实世

界地理实体、地理现象及其相互关系，是现实世界到计算机世界的直接映射。空间数据模型

为描述空间数据组织和设计空间数据库提供基本方法，是GIS空间数据建模的基础。数据

组织的优劣直接影响到空间数据库中数据查询、检索的方式、速度和效率。（张海荣，地理

信息系统原理与应用，中国矿业大学出版社，2008.2第1次印刷）

4、数字地形模型：

5、空间定位技术：

6、空间统计技术：

论述题：（共120分，每题20分）

1、什么是时空数据模型？时空数据模型有哪些？时空数据模型是如何发展的？

2、地理空间数据有哪些传输方式？每种传输方式的特点是什么？有哪些发展趋势？

3、地理信息系统有哪些体系架构？每种体系架构的特点是什么？有哪些发展趋势？

4、地理空间信息有哪些主要的表达方式？每种表达方式的特点是什么？有哪些发展趋势？

5、当前地理信息系统的主要用户群有哪些？这些用户群的需求特点是什么？当前应用地理

信息系统哪些方面不能适应用户需求？如何改进？

6、什么是社会化地理信息系统？发展社会化地理信息系统存在的问题是什么？如何解决？

2009

一、名词解释

1、SOA：面向服务的体系结构（Service-OrientedArchitecture,SOA）是一个组件模型,它

将应用程序的不同功能单元（称为服务）通过这些服务之间定义良好的接口和契约联系起来。

接口是采用中立的方式进行定义的，它应该独立于实现服务的硬件平台、操作系统和编程语

言。这使得构建在各种这样的系统中的服务可以一种统一和通用的方式进行交互。

2、Web服务：是新一代Web应用程序，它们是自包含、自描述、模块化的应用程序，能够

被发布、定位，并通过Web调用：Web服务可以执行从简单的请求到复杂商务处理的任何

功能，一旦被部署，其他应用程序和Web服务就可以发现并调用这些服务，其通信协议主

要基于SOAP,服务的描述通过WSDL,通过UDDI来发现和获得服务的元数据。

3、空间数据结构：是指空间数据在计算机内的组织和编码形式。它是一种适合于计算机存

贮、管理和处理的空间数据逻辑结构，是地理实体的空间排列和相互关系的抽象描述。它是

对数据的一种理解和解释。

4、空间数据引擎：简称SDE,是一种空间数据库管理系统的实现方法，即在常规管理系统

之上添加一层空间数据库引擎，以获得常规数据库管理系统功能之外的空间数据存储和管理

能力，主要是为了解决存储在关系数据库中空间数据与应用程序之间的数据接口问题。其中

有代表性的是ESRI的SDEo

5、地统计学：

6、数字地形模型：

二、论述题（共120分，每题20分）

1、什么是地理元数据？地理元数据包括哪些内容，有什么用途？

2、什么是组件式GIS?组件式GIS的特征以及存在问题是什么？

3、什么是服务型GIS?服务型GIS的特征是什么？

4、支撑GIS的网络平台有哪些类型？这些网络平台之间如何连接？

5、阐述VirtualEarth的特点，VirtualEarth可能对GIS发展的作用。

6、阐述一个应用GIS系统建设工程所包含的主要内容，需要关注的要点是什么？

2010

一、名词解释（每题6分，共30分）

1、网络GIS：网络GIS有技术的狭义网络GIS和宏观的广义网络GIS之分。在一定时期内

特定形式的计算机网络和分布式对象技术的融合所形成的GIS系统便是狭义的网络GIS；广

义网络GIS不仅是所有狭义网络GIS的统称，同时也代表了不同狭义GIS结合时的产物。

2、服务型GIS：采用面向服务的软件工程方法，把GIS的全部功能封装为Web服务（Web

Service）,从而实现了被多种客户端跨平台、跨网络、跨语言地调用，并具备了服务聚合能

力以集成来自其他服务器发布的服务的GIS系统。

3、SOA架构：面向服务的体系结构（Service-OrientedArchitecture,SOA）是-一个组件模型，

它将应用程序的不同功能单元（称为服务）通过这些服务之间定义良好的接口和契约联系起

来。接口是采用中立的方式进行定义的，它应该独立于实现服务的硬件平台、操作系统和编

程语言。这使得构建在各种这样的系统中的服务可以一种统一和通用的方式进行交互。

4、WebService技术：是新一代Web应用程序，它们是自包含、自描述、模块化的应用程序，

能够被发布、定位，并通过Web调用；Web服务可以执行从简单的请求到复杂商务处理的

任何功能，一旦被部署，其他应用程序和Web服务就可以发现并调用这些服务，其通信协

议主要基于SOAP,服务的描述通过WSDL,通过UDDI来发现和获得服务的元数据。

5、传感器网络:传感器网络是由大量部署在作用区域内的具有无线通信与计算能力的微小传

感器节点通过自组织方式构成的能根据环境自主完成指定任务的分布式智能化网络系统。

二、论述题（每题24分）

1、阐述矢量G1S与栅格G1S型GIS的特点与存在问题，如何实现矢栅地理数据的一体化存

储与管理？

2、试从数据生产的过程论述4D产品的特征，4D产品对GIS发展的贡献和存在问题。

3、在GIS发展过程中有哪些体系架构，各自的特点是什么？

4、阐述基础地理数据更新的主要方法及各自的特点，从技术和制度上如何保证基础地理数

据的现势性？

5、地理数据共享有哪些模式，如何从体系架构、数据交换等关键技术方面，以及法律法规

和政策方面保证地理数据的共享？

南京师范大学2011年研究生入学考试试题-科目名称：C语

言程序设计（含数据结构）

1、编写一个程序，求用户输入的开始时间到终止时间之间相距的天数。（本题15分）

2,编写一个程序，利用递归法实现将用户输入的字符串逆序排列.（本题15分）

3、找出所有200以内（含200）满足1,1+4,1+10都是素数的整数I（1+10也在200以内）的

个数以及这些数之和sum。井把所有这些数、个数和sum按文本文件输出到文件out.dat中。

（本题20分）

4、编写程序，判断两线段是否相交。（本题20分）

5、假设以带头节点的循环链表表示队列，并只设一个指针指向对尾元素节点（不设头指针）,

编写相应的队列初始化、入队列和出队列算法。（本题20分）

6、假设有两个按元素值递增有序排列的线性表A和B,均以单链表作存储结构，请编写算

法将表A和表B归并成一个按元素值非递减有序（允许值相同）排列的线性表C,并要求

利用原表（即表A和表B）的结点空间存放表。（本题20分）

7、给定一棵树用二叉链表表示的二叉树，其中的指针t指向根结点，试写出从根开始，按

层次遍历二叉树的算法，周层的结点按从左到右的次序访问。（本题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日之间经过的天数，则以2005年1月1

日为起点，分别计算2005年5月20日和2008年9月12日至2005年1月1日的天数，两者天数相减，

则可以求出两者相距的天数。

2、解题思路：假如一个字符串有n个字符，用递归方法进行第1与第n字符交换、第2与第

n-1个字符交换…直到字符串的中间位置。

3、解题思路：将符合条件的所有元素I存入一个数组中，并记录个数，再求和

4、解题思路：如果两条线段平行，则两条线段定不相交；如果不平行，则求两线段所在的

直线的交点，再判断该交点是否在线段匕如果在线段上，则表示两线段相交，如果不在线

段上，则表示两线段不相交。

5、参照严蔚敏的数据结构（C语言版）课本64页循环队列-队列的顺序存储结构

6、参照严蔚敏的数据结构（C语言版）课本31页算法2.12

7、参照严蔚敏的数据结构（C语言版）课本17（）页算法7.6

8、对照严蔚敏的数据结构（C语言版）课本149页例6-3

南京师范大学2010年研究生入学考试试题-科目名称：C语

言程序设计(含数据结构)

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门课，要求编一函数，能检查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、请写出判断“点是否在简单多边形内部”的算法。(本题20分)

〃相对正确的解题思路：从该点向某一个方向做一条射线，如果与多边形相交的点是奇数个,

则在多边形内；否则，可能在多边形内。

〃不太正确的解题思路：如果一个点在一个多边形内，那么从该点向上、向下、向左、向右

都应与简单

〃多边有交点，点在某一条边上算在多边形内(下面的程序代码也有问题)。

#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、从平均时间、最坏情况，辅助存储和稳定性的角度，对各种内部排序方法进行比较。

（建议用表格方式进行比较，本题20分）

严蔚敏数据结构289页

6、定义一个双向循环链表，并写出其定位、插入和删除算法。（本题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)

{〃在带头结点的双链循环链表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++；

}

〃查找完循环链表后，如果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)

{//删除带头结点的双链循环线性表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、编制•个程序以模拟银行窗口接待客户的排队业务活动（每个窗口在某个时刻只能接待

一个客户；窗口空闲，则可上前办理业务；窗口均被占，则新客户便会排在人数最少的队伍

前面），并计算一天中客户在银行逗留的平均时间。（本题20分）

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

#defineMAX10000

#defineOK1

#defineERROR0

/**********数据型定义(Start)**********/

typedefintStatus;

typedefstruct

intOccurTime;〃事件发生时刻

intNType;〃事件类型，0~5

}Event,ElemType;〃事件类型，有序链表LinkList的数据元素类型

typedefstructLNode

ElemTypedata;

structLNode*next;

}LNode,*LinkList;

typedefLinkListEventList;〃事件链表类型，定义为有序链表

typedefstruct

(

intAirivalTime;〃到达时间

intDuration;〃办理事务所需时间

JQElemType;〃队列的数据元素类型

typedefstructQNode

(

QElemTypedata;

structQNode*next;

}QNode,*QueuePtr;

typedefstruct

QueuePtrfront;

QueuePtrrear;

JLinkQueue;

/**********数据类型定义(Over)**********/

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

EventListev;〃事件表

Eventen;〃事件

LinkQueueq[5];〃4个客户队列

QElemTypecustomer;〃客户记录

longTotalTime,CustomerNum;〃累计客户逗留时间，客户数

/**********程序中用至的主要变量（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)****/

/****业务操作部分(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);

)

/****业务操作部分(over)****/

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

voidmain()

Bank_Simulation(99999);

)

8、设T是正则二叉树（若根树T的每个结点都恰有左右两个二则，则该树T被称为正则二

叉树）

它具有6片树叶，那么树T的高度最多可以是多少，最小可以是多少；树T的内结点数是多

少，

如果T又是Huffman最优树，且各片树叶的数分别是1,2,3,4,4,6,则最优树T的非

树叶

结点的数之和是多少，数为1的树叶的高度是多少。（注：树的根结点高度为1;本题写出答

案即可；本题20分）

参考解答：

〃关于正则二叉树在严蔚敏的数据结构书的146页最下面一段里，如下：

〃由于赫夫曼没有度为1的结点（这类树又称为严格的（strict）（或正则的）二叉树），则一棵

〃有n个叶子结点的赫夫曼树共有2n-l个结点，可以存储在•个大小为2n-l的一维数组中。

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

树T的内结点数是5

最优树T的非树叶结点的数之利是49

数为1的树叶的高度是5。

南京师范大学2009年研究生入学考试试题-科目名称：C语

言程序设计(含数据结构)

(1)设计一个程序，找出1—200之间的所有水仙花数。所谓水仙花数是指各个数字的立方

和恰好

等于该数本身。例如：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)设计一个程序，实现输入一个给定的正整数N,打卬出所有不超过N的，其平方为回

文

(回文是指字符串两半的字符左右对称，例如1,22,121,4224等均是回文)的数(本题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)编写程序用于统计字符串中最长单词的长度和在字符串中的位置，其中单词由字母组成。

(本题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(