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

第 1 页 共 4 页 南京信息工程大学期中试卷 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 环绕数是非零时，点在多边形外部；否则，为零时，在多边形内部。 第 2 页 共 4 页 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、按照下图多边形边界按顺时针方向的链式编码为 。 第 3 页 共 4 页

三、公式计算题(共30分) 1、根据下面代码，求算执行次数和算法时间复杂度。（10分） int i, j; for(i=0; i