南京信息工程大学期中GIS算法试卷(2019-2020-2)

南京信息工程大学期中试卷
2019－2020学年 第 2 学期 地理信息系统算法基础 课程试卷 本试卷共 4 页；考试时间 100 分钟；任课教师王 勇；出卷时间 2020 年 4 月
学院专业年级班学号姓名得分
一、选择题(每小题3分，共24分)
1、算法设计原则有哪些？（）
A正确性确定性清晰性
B正确性准确性清晰性
C正确性确定性合理性
D正确性准确性合理性
2、在维数扩展的9交集模型空间关系的判定中，定义了一系列DE-9IM的空间关系命名，
分别为（）。

A 相离、相接、相交、包含、相等
B 相离、相接、相交、真包含、叠置
C 相离、相接、相交、真包含、相等
D 相离、相接、相交、包含、叠置
3、射线法用来判断点是否在多边形内，从点开始一条射线，穿过多边形的边界的次数称
为交点数目，通过判断交点数目来确定点在多边形的内外。

具体判定规则为（）。

A 交点数目是偶数时，点在多边形外部；否则，为奇数时，在多边形内部。

B 交点数目是奇数时，点在多边形外部；否则，为偶数时，在多边形内部。

C 交点数目是零时，点在多边形外部；否则，为非零时，在多边形内部。

D 交点数目是非零时，点在多边形外部；否则，为零时，在多边形内部。

4、矢量线的栅格化中的三种不同方法有（ ）。

A 八方向栅格化、全路径栅格化、恒密度栅格化
B 内部点扩散算法、全路径栅格化、恒密度栅格化
C 八方向栅格化、全路径栅格化、密度栅格化
D 内部点扩散算法、全路径栅格化、密度栅格化
5、转角法用来判定一个点是否在多边形的内部，计算多边形绕点的次数（环绕数），通
过环绕数来确定点在多边形的内外。

具体判定规则为（ ）。

A 环绕数是偶数时，点在多边形外部；否则，为奇数时，在多边形内部。

B 环绕数是奇数时，点在多边形外部；否则，为偶数时，在多边形内部。

C 环绕数是零时，点在多边形外部；否则，为非零时，在多边形内部。

D 环绕数是非零时，点在多边形外部；否则，为零时，在多边形内部。

6、下面列出矢量数据的压缩方法，其中哪种方法最优？（）
A间隔取点法
B道格拉斯-普克法
C偏角法
D垂距法
7、下列矢量数据的压缩方法中不正确一组是（）。

A、间隔取点法、道格拉斯-普克法、垂距法
B、道格拉斯-普克法、偏角法、光栏法
C、间隔取点法、道格拉斯-普克法、射线法
D、垂距法、偏角法、光栏法
8、在空间数据组织算法中，下列哪个编码方法不是无损压缩算法。

（）
A、差分映射法
B、块式编码
C、游程长度编码
D、间隔取点法
二、填空题(共16分)
1、给出下面几种常见的算法时间复杂性的函数，并按照其随数据规模增大而增大的速度
进行排序：
n, 2n n2, n3, logn, nlogn
排序结果：＞＞＞＞＞
2、根据下面的维数扩展的9交集模型，判断空间关系，请填入下表：
DE-9IM模型几何对象 空间关系
FF*FF**** All
T*T***T** A/A
T*F**F*** ALL
3、已知一直线上两端点分别为A（x1，y1）, B（x2，y2）,请写出直线AB隐式方程。

4、矢量面栅格化有算法、算法、算法和算法。

5、按照下图多边形边界按顺时针方向的链式编码为。

三、公式计算题(共30分)
1、根据下面代码，求算执行次数和算法时间复杂度。

（10分） int i, j;
for(i=0; i<n; i++) for (j=0; j<n; j++) c[i][j] =a[i][j]+b[i][j];
2、已知线段P 0P 1，求该线段所在的参数方程，并讨论参数在什么区间时该方程式能够表达P 0P 1线段、P 0P 1线段的延长线、P 0P 1线段的反向延长线、以及代表端点P 0和端点P 1。

（10分）
3、有一点P 其矢量坐标为（9.5，15.6），若网格的宽与高都是2，栅格起始行列号（1，1）的矢量坐标为（2，20），请写出换算公式，并求P 点栅格化的行列号。

（10分）
四、算法题(共 30 分)
1、根据下图，判断折线段的拐向，写出折线段的拐向判断方法。

（15分）
P 0
P
1
P 01
P 2
P 1 P 2
P 0 P 0
P 1
P 2
(3)
(1)
(2)
2、点P到线段P0P1的距离，根据下图和伪代码，用文字写出求算思路。

（15分）
伪代码求算思路。