南师2007数据结构试卷

南京师范大学地理信息系统试题南京师范大学2007年研究生入学考试试题-地理信息系统一、名词解释（每题6分，共30分）1、空间数据引擎2、空间索引3、网格GIS4、数字地形分析5、正射影像二、论述题1、试述空间数据模型与空间数据结构的联系与区别。

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

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

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

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

6、你知道Google Earth吗？阐述Google Earth的特点，说明Google Earth使用了哪些关键技术。

南京师大2006年GIS名词解释：1.空间数据模型2.空间数据结构3.空间数据索引4.空间数据引擎5.GridGis论述：1.简述空间元数据2.试述地理信息共享技术内涵3.电子政务与GIS4.电子商务与gis5.数字城市建设框架与共享需要解决的关键技术问题6.简述网络发展与GIS的关系南师大2005年GIS一、名词解释1.4D产品2.空间数据引擎3.LBS4.数字高程模型5.嵌入式GIS二、问答题1.阐述地理信息系统的主要特征2.阐述地理信息系统数据组织的发展及趋势3.阐述主要的地理定位数据获取方法和原理4.阐述电子政务系统与GIS的关系5.阐述通信技术发展与GIS的相互关系南师大2004年GIS一、名词解释：XML OGC SIG 空间数据融合虚拟地理环境二、简述题：1、论述GIS的主要特点2、论述GIS的主要数据模型3、论述GIS主要的空间索引方法4、论述地理数据转换与互操作的内涵及发展过程5、论述GIS体系结构的发展以及当前GIS体系结构的特点6、论述GIS融入信息技术主流的特点7、论述数字城市建设中GIS共享需要解决的关键技术问题南师大2003年GIS一、名词解释（30）1 地理信息系统（7）2 四叉树数据结构（7）3 放射变换（8）4 狄洛尼（Delaunay）三角网（8）二、试述GIS数据质量和空间数据的不决定性包含了哪些方面？你认为那几方面的数据质量是难以保证和最需要注意的？（30）三、试述矢量格式向栅格格式数据转换有那几种方法？写出各自算法的要点，并比较他们的优缺点。

2007年1月高等教育自学考试全国统一命题考试数据结构导论试题课程代码2142一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1．关于栈和队列的说法中正确的是（）A．栈和队列都是线性结构B.栈是线性结构，队列不是线性结构C.栈不是线性结构，队列是线性结构D.栈和队列都不是线性结构2．关于存储相同数据元素的说法中正确的是（）A．顺序存储比链式存储少占空间B.顺序存储比链式存储多占空间C.顺序存储和链式存储都要求占用整块存储空间D.链式存储比顺序存储难于扩充空间3．从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（）A．线性结构 B.树形结构C.线性结构和树型结构D.线性结构和图状结构4．已知一个单链表中，指针q指向指针p的前趋结点，若在指针q所指结点和指针p所指结点之间插入指针s所指结点，则需执行（）A．q→next=s；p→next=s； B.q→next=s；s→next=p；C.q→next=s；q→next=p；D.q→next=s；s→next=q；5．在长度为n的线性表中删除一个指针p所指结点的时间复杂度是（）A．O(n) B.O(1)C.O(log2n)D.O(n2)6．设一个栈的输入序列是a，b，c，d，则所得到的输出序列（输入过程中允许出栈）不可能出现的是（）A．a，b，c，d B.a，b，d，cC.d，c，b，aD.c，d，a，b7．关于串的叙述中，正确的是（）A．空串是只含有零个字符的串B.空串是只含有空格字符的串C.空串是含有零个字符或含有空格字符的串D.串是含有一个或多个字符的有穷序列8．在具有m 个单元的循环队列中，队头指针为front ，队尾指针为rear ，则队满的条件是（ ）A ．front==rear B.(front+1)%m==rear C.rear+1==frontD.(rear+1)%m==front9．设有二维数组A ［n ］［n ］表示如下：⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡ 653421， 则A ［i ］［i ］（0≤i ≤n-1）的值为（ ） A ．i*(i-1)/2 B.i*(i+1)/2 C.(i+2)*(i+1)/2D.i 2/210．高度为h 的完全二叉树中，结点数最多为（ ） A ．2h-1 B.2h+1 C.2h -1D.2h11．由m 棵结点数为n 的树组成的森林，将其转化为一棵二叉树，则该二叉树中根结点的右子树上具有的结点个数是（ ） A ．mn B.mn-1 C.n(m-1)D.m(n-1)12．在一个具有n 个顶点的无向图中，每个顶点度的最大值为（ ） A ．n B.n-1 C.n+1D.2(n-1)13．关于无向图的邻接矩阵的说法中正确的是（ ） A ．矩阵中非全零元素的行数等于图中的顶点数 B.第i 行上与第i 列上非零元素总和等于顶点V i 的度数 C.矩阵中的非零元素个数等于图的边数D.第i 行上非零元素个数和第i 列上非零元素个数一定相等14．设一组记录的关键字key 值为{62，50，14，28，19，35，47，56，83}，散列函数为H(key)=key mod 13，则它的开散列表中散列地址为1的链中的结点个数是（ ） A ．1 B.2 Ｃ．3D.415．设有一组初始关键字值序列为（49，81，55，36，44，88），则利用快速排序的方法，以第一个关键字值为基准得到的一次划分为（ ）A．36，44，49，55，81，88 B.44，36，49，55，81，88C.44，36，49，81，55，88D.44，36，49，55，88，81二、填空题(本大题共13小题，每小题2分，共26分)请在每小题的空格中填上正确答案。

2007年硕士研究生入学考试初试试题科目代号：613科目名称：C语言与Web技术一、 C语言填空题:(每小题3分，共45分)：1、完整的C程序中至少应包括一个( )函数。

2、宏定义命令是( )，文件包含命令是( )。

3、构造类型数据是由基本类型数据按一定规则组成的。

C语言中构造类型数据有三种，它们是( )、( )和( )。

4、在一个32位系统(如Windows 2000)中，若已定义char*s=”010\010\\010\n”;则sizeof(s)的值为( )，strlen(s)的值为( )。

5、表达式1234 == 1234/3*3 的值为( )。

6、表达式4 && 3 && 2 && 1的值为( )。

7、为表示关系x < y < z,应使用C语言表达式( )。

8、若有int i=5，j=0；则执行完语句if (j=0) i++;else i-- ;后,i的值为( )。

9、若有int i = 10，j = 2;则执行完语句i / = j + 8;后, i 的值( )。

10、下列程序的执行结果为a = ( ), z = ( )。

main() {int a = -1, b = -1, z = 0;if (a>0) if (b>0) z = 1;else z = -1;if (b) --a;else ++a;printf(“ a=%d,z=%d”,a,z);}11、若有int i = 5, j = 10; 则执行完语句switch(i){case 4: j ++;case 5: j --;case 6:case 7: j ++;j -= 2;default:;} 后j 的值为( )。

12、下列程序输出的两个数值分别是( )和( )。

#include <stdio.h>void main( ){int a[5] = {1,2,3,4,5},*p,**q;p = a;q = &p;printf(“%d\t”,*(p++));printf(“%d”,**q); }13．下面程序把数组元素中的最大值放a[0]中，并打印出来，则在if 语句中的条件表达式应该是( ),main(){int a[10]={6,8,2,9,1,10,5,7,4,3},*p=a, i;for(i=0;i<10;i++,p++)if ( *p > a[i] ) *a = *p;printf(“%d”, *a);}14．如下函数计算并返回字符串s的长度，语句while和return后面的括号中的内容应当分别为()和()。

2008－2009学年第二学期 计算机科学学院《数据结构》期末考试试卷（A 卷） 答案与评分标准 年级：07级 专业： 班级： 学号： 姓名： 题号 一 二 三 四 五 六 总分 签名 得分 注：1、共100分，考试时间120分钟。

2、此试卷适用于计算机科学与技术本科、信息管理与信息系统专业。

一 得 分 阅卷教师 2分，共20分） 1．数据是对客观事物的符号的表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的（ 符号的总称 ）。

2．抽象数据类型是指一个（ 数学模型 ）以及定义在该模型上的一组操作。

3. 在顺序表中插入或删除一个元素，需要平均移动（ 表中一半 ）元素，具体移动的元素个数与（ 表长和该元素在表中的位置 ）有关。

4. 顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（ 108 ）。

5．循环队列的引入是为了克服（ 假溢出 ）。

6．head(tail(head(((a ，b)，(c ，d)))))= b 。

7．已知一棵完全二叉树共有768个结点，则该树中有（ 384 ）个叶子结点。

8．某二叉树的先序遍历序列是8，5，1，3，2，4，6，7，10，9，11 ，中序遍历序列是1，2，3，4，5，6，7，8，9，10，11，则其后序遍历序列是（2，4，3，1，7，6，5，9，11，10，8）。

9．有向图G 用邻接矩阵存储，其第i 行的所有元素之和等于顶点i 的（ 出度 ）。

10．对n 个待排序记录序列进行快速排序，其最坏时间复杂度为（ O （n 2） ）。

二 得 分 阅卷教师 2分，共10分） 1．算法是指 （ A ） A ．对特定问题求解步骤的一种描述，是指令的有限序列 B ．计算机程序 C ．解决问题的计算方法 D ．数据处理 ——————————————装————————————————订————————————————线————————————2．若某线性表中最常用的操作是取第i个元素和查找第i个元素的前驱，则采用（A ）存储方法最节省时间。

南京师范大学研究生招生入学考试试卷2007年硕士研究生招生入学考试试卷专业名称：基础数学 研究方向： 科目代码：334科目名称：数学分析考生注意： 答案必须写在答题纸上，否则无效，后果自负。

一．（每小题10分）计算下列极限：（1）xtdtx xx ⎰⨯+∞→2ln ln lim; （2）yx y x y x ++→→2200lim;（3）设()1,01∈x ，()n n n x x x -=+11() ,2,1=n ，证明{}n nx 收敛并求极限。

二．（20分）（1）设函数()x f 在点0x 的某邻域()0x U 内有1+n 阶的连续导函数。

证明对任意的()0x U x ∈有()()()()()()()(),!0000'0x R x x n x f x x x f x f x f n n n +-++-+= 其中()()()()()()100011!1++---+=n n n n x x x x x fn x R θθ，且10≤≤θ； （2）求()()11ln 2≤+x x的麦克劳林级数展开，并加以证明。

三．（20分） 设()x f 为()+∞,0内的连续函数且，()+∞=+→x f x lim 0，()0lim =+∞→x f x ，试证：（1）()x x f 1sin在[)+∞,a ()0>a 内一致连续； （2） ()xx f 1sin 在()+∞,0内不一致连续。

四．（15分）利用Stokes 公式计算：()()()⎰-+-++Ldz x y dy z x dx z y 2，其中L 为平面1=++z y x 与各坐标面的交线，取逆时针方向为正向。

五．（10分）证明：试研究方程()0ln >=a x ax 实根的个数。

六．（10分）设函数()v u F ,有连续的二阶偏导数，求证由方程0,0000=⎪⎪⎭⎫ ⎝⎛----z z y y z z x x F 所确定的隐函数()y x z z ,=满足下列两个方程：()()000z z yz y y xz x x -=∂∂-+∂∂-；222222⎪⎪⎭⎫⎝⎛∂∂∂=∂∂⋅∂∂y x z y z x z 。

数据结构试题库及答案第一章概论一、选择题1、研究数据结构就是研究（ D ）。

A. 数据的逻辑结构B. 数据的存储结构C. 数据的逻辑结构和存储结构D. 数据的逻辑结构、存储结构及其基本操作2、算法分析的两个主要方面是（ A ）。

A. 空间复杂度和时间复杂度B. 正确性和简单性C. 可读性和文档性D. 数据复杂性和程序复杂性3、具有线性结构的数据结构是（ D ）。

A. 图B. 树C. 广义表D. 栈4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（ B ）等5个特性。

A. 可执行性、可移植性和可扩充性B. 可执行性、有穷性和确定性C. 确定性、有穷性和稳定性D. 易读性、稳定性和确定性5、下面程序段的时间复杂度是（ C ）。

for(i=0;i<m;i++)for(j=0;j<n;j++)a[i][j]=i*j;A. O(m2)B. O(n2)C. O(m*n)D. O(m+n)6、算法是（ D ）。

A. 计算机程序B. 解决问题的计算方法C. 排序算法D. 解决问题的有限运算序列7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（ C ）。

A. O(n)B. O(nlog2n)C. O(n2)D.O(log2n)8、下面程序段的时间复杂度为（ C ）。

i=1;while(i<=n)i=i*3;A. O(n)B. O(3n)C. O(log3n)D. O(n3)9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（）和运算等的学科。

A. 结构B. 关系C. 运算D. 算法10、下面程序段的时间复杂度是（）。

i=s=0;while(s<n){i++;s+=i;}A. O(n)B. O(n2)C. O(log2n)D. O(n3)11、抽象数据类型的三个组成部分分别为（）。

A. 数据对象、数据关系和基本操作B. 数据元素、逻辑结构和存储结构C. 数据项、数据元素和数据类型D. 数据元素、数据结构和数据类型12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量，以下解释错误的是（）。

2006级(嵌入式软件与系统、计算机应用方向)《数据结构》期终考试试卷答案一、单项选择题 (每题1分，共15分)答案：C, A, B, B, C, D, D, C, D, A, B, B, A, C, A二、已知一个无向图的顶点集为{ a , b , c , d , e , f }，其邻接矩阵如下所示(0-无边,1-有边)。

⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡00110001101110110111010001101010010fe d c b af e d c b a(1). 画出该图的图形；(2). 根据邻接矩阵从顶点a 出发进行广度优先遍历，画出相应的广度优先遍历树。

(15分) 解：(1). 该邻接矩阵所对应的的图2.1所示(2). 从顶点a 出发进行广度优先遍历的遍历树如图2.2所示三、已知一个散列表如下图所示：其散列函数为h (key ) = key % 13，处理冲突的方法为双重散列法，探查序列为:h i = (h (key ) + i * 3) % 13, i = 1, 2, …问：对表中关键字61进行查找时，所需进行的比较次数为多少？依次写出每次的计算公式和值。

(10分)解：在表中查找关键字61时，所需进行的计算公式如下:h (61) = 61 % 13 = 9h 1 = (9 + 1 * 3) % 13 = 12图2.1 图2.2 a b e d f ch 2 = (9 + 2 * 3) % 13 = 15 % 13 = 2由上过程可知：在表中查找关键字61时，需要进行3次比较。

四、阅读下面程序，回答问题 (10分)void function(Link **Head) {Link *pt1, *pt2, *tmp; pt1 = *Head;if (pt1 == NULL) return;pt2 = pt1->next; pt1->next = NULL;// 语句行S 1while (pt2 != NULL) { tmp = pt2->next;pt2->next = pt1; pt1 = pt2; pt2 = tmp; }*Head = pt1;// 语句行S 2}回答下列问题：(1). 说明语句行S 1和S 2的作用(指对单向链表中所起的作用)；(2). 简洁地给出函数function 的功能描述(非每条语句的语义说明)；(3). 若链表Head 的线性表形式为(a 1, a 2, …, a n )，写出函数执行后链表Head 的线性表形式。

数据结构试题库及答案第一章概论一、选择题1、研究数据结构就是研究（D ）。

A. 数据的逻辑结构B. 数据的存储结构C. 数据的逻辑结构和存储结构D. 数据的逻辑结构、存储结构及其基本操作2、算法分析的两个主要方面是（ A ）。

A. 空间复杂度和时间复杂度B. 正确性和简单性C. 可读性和文档性D. 数据复杂性和程序复杂性3、具有线性结构的数据结构是（ D ）。

A. 图B. 树C. 广义表D. 栈4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B ）等5个特性。

A. 可执行性、可移植性和可扩充性B. 可执行性、有穷性和确定性C. 确定性、有穷性和稳定性D. 易读性、稳定性和确定性5、下面程序段的时间复杂度是（ C ）。

for(i=0;i<m;i++)for(j=0;j<n;j++)a[i][j]=i*j;A. O(m2)B. O(n2)C. O(m*n)D. O(m+n)6、算法是（D ）。

A. 计算机程序B. 解决问题的计算方法C. 排序算法D. 解决问题的有限运算序列7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（C ）。

A. O(n)B. O(nlog2n)C. O(n2)D. O(log2n)8、下面程序段的时间复杂度为（ C ）。

i=1;while(i<=n)i=i*3;A. O(n)B. O(3n)C. O(log3n)D. O(n3)9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（）和运算等的学科。

A. 结构B. 关系C. 运算D. 算法10、下面程序段的时间复杂度是（）。

i=s=0;while(s<n){i++;s+=i;}A. O(n)B. O(n2)C. O(log2n)D. O(n3)11、抽象数据类型的三个组成部分分别为（）。

A. 数据对象、数据关系和基本操作B. 数据元素、逻辑结构和存储结构C. 数据项、数据元素和数据类型D. 数据元素、数据结构和数据类型12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量，以下解释错误的是（）。

数据结构试题库及答案第一章概论一、选择题1、研究数据结构就是研究（ D ）。

A. 数据的逻辑结构B. 数据的存储结构C. 数据的逻辑结构和存储结构D. 数据的逻辑结构、存储结构及其基本操作2、算法分析的两个主要方面是（ A ）。

A. 空间复杂度和时间复杂度B. 正确性和简单性C. 可读性和文档性D. 数据复杂性和程序复杂性3、具有线性结构的数据结构是（ D ）。

A. 图B. 树C. 广义表D. 栈4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（ B ）等5个特性。

A. 可执行性、可移植性和可扩充性B. 可执行性、有穷性和确定性C. 确定性、有穷性和稳定性D. 易读性、稳定性和确定性5、下面程序段的时间复杂度是（ C ）。

for(i=0;i<m;i++)for(j=0;j<n;j++)a[i][j]=i*j;A. O(m2)B. O(n2)C. O(m*n)D. O(m+n)6、算法是（ D ）。

A. 计算机程序B. 解决问题的计算方法C. 排序算法D. 解决问题的有限运算序列7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（ C ）。

A. O(n)B. O(nlog2n)C. O(n2)D.O(log2n)8、下面程序段的时间复杂度为（ C ）。

i=1;while(i<=n)i=i*3;A. O(n)B. O(3n)C. O(log3n)D. O(n3)9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（）和运算等的学科。

A. 结构B. 关系C. 运算D. 算法10、下面程序段的时间复杂度是（）。

i=s=0;while(s<n){i++;s+=i;}A. O(n)B. O(n2)C. O(log2n)D. O(n3)11、抽象数据类型的三个组成部分分别为（）。

A. 数据对象、数据关系和基本操作B. 数据元素、逻辑结构和存储结构C. 数据项、数据元素和数据类型D. 数据元素、数据结构和数据类型12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量，以下解释错误的是（）。

2006/2007 学年 第 2 学期课程名称：数据结构 共 8 页 试卷： A 考试形式： 闭 卷一、单项选择题 (共10小题，每小题2分，共20分) 1．设某数据结构的二元组形式表示为A=(D ，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A 是（ ）。

(A) 线性结构 (B) 树型结构(C) 物理结构 (D) 图型结构2．设一维数组中有n 个数组元素，则读取第i 个数组元素的平均时间复杂度为（ ）。

(A) O(n) (B) O(nlog 2n) (C) O(1) (D) O(n 2) 3．设指针变量front 表示链式队列的队头指针，指针变量rear 表示链式队列的队尾指针，指针变量s 指向将要入队列的结点X ，则入队列的操作序列为（ ）。

(A) front->next=s ； front=s ； (B) s->next=rear ； rear=s ； (C) rear->next=s ； rear=s ； (D) s->next=front ；4. 设哈夫曼树中的叶子结点总数为m ，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ ）个空指针域。

(A) 2m-1 (B) 2m (C) 2m+1 (D) 4m5. n个顶点的带权无向连通图的最小生成树包含（）个顶点。

(A) n-1 (B) n (C) n/2 (D) n+16. 一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列？（）(A) 1，3，2，4 (B) 2，3，4，1(C) 4，3，1，2 (D) 3，4，2，17．设二叉排序树中有n个结点，则二叉排序树的平均查找长度为（）。