2010-2011学年第二学期GIS算法基础

算法的设计原则是 正确性 、 确定性 、 清晰性 。

算法的复杂度包括 算法的时间复杂度 、 算法的空间复杂度 。 Egenhofer(1993)构造出一个由 边界 、 内部 、 外部 的点集组成的9—交空间关系模型(9IM)。

折线段的拐向判断方法可以直接由矢量叉积的性质推出。对于有公共端点的线段P0P1和P1P2，通过计算(P2 - P0)×(P1 - P0)的符号便可以确定折线段的拐向：若(P2 - P0)×(P1 - P0) > 0,则P0P1在P1点拐向 右侧 后得到P1P2；若(P2 - P0)×(P1 - P0) < 0,则P0P1在P1点拐向 左侧 后得到P1P2；若(P2 - P0)×(P1 - P0) = 0,则 P0、P1、P2三点共线 。 在空间查询中，最常用的两种查询是 按属性信息的要求来查询定位空间位置

和 根据对象的空间位置查询有关的属性信息. 。

实现一种地图投影点的坐标变换为另一种地图投影点的坐标，就是要

?x?f1(?,?)找出 关系式，其方法有 解析变换法 、 数值解析

??y?f2(?,?)

变换法 和 数值变化法 。

设面状物体的轮廓边界由一个点的序列P1 (x1 , y1), P2 ( x2, y2 ), ?，

Pn (xn, yn)表示，其面积为 。

轴线或边界上的相邻三点Pi-1、Pi 、Pi+1，用 右手螺旋 法则判断轴线（边界）转折点的凸凹性，若拇指向下，则Pi点左侧为 凸 ，右侧为凹 。

在下面选项中，不属于数据挖掘步骤的是( B )。

1nxiS??2i?1xi?1yiyi?1

A数据变换 B数据分类 C数据清理 D知识表示 有六种多项式时间算法最为常见，其关系为 ( D )。 A O(1)

B O(1)

我国现在采用的1980国家大地坐标系应用的是哪种地球椭球体参数( B )。

A克拉索夫斯基椭球 B 1975国际椭球 C WGS-84系椭球 D 1980国际椭球

磁盘访问次数是影响空间索引性能的关键指标，下面哪种空间索引方法是比较优秀的空间索引方法。（A ）

A CELL树 B R树 C B+树 D R+树 （ A）反映城市的带状延伸程度，带状延伸越明显则延伸率越大，反映城市的离散程度越大。

A 伸延率 B 紧凑度 C 紧凑度指数 D 放射状指数 在矢量缓冲区的实现算法中对于双线问题最简单的方法是（ C ）。 A 凸角圆弧法 B 叠置算法 C 角平分线法 D 圆弧拟合法 下图按照前序遍历的方法写出结果。( A ) A a + b * c - d - e / f B - + a * b - c d / e f C a b c d - * + e f / - D 没有正确答案

在下面选项中，不属于数据挖掘算法的是(B )。

A聚类分析 B叠置分析 C主成分分析 D层次分析法 下面关于点缓冲区边界生成算法的叙述哪一条正确?( A ) A 等分的圆心角越小，步长越小，误差越小； B等分的圆心角越大，步长越小，误差越小； C等分的圆心角越大，步长越小，误差越大； D等分的圆心角越小，步长越大，误差越小。 在下面选项中，不属于B-树的性质的是( D )。

A 多叉树 B 查找树 C 平衡树 D 二叉树 无向图的邻接矩阵是不对称的。 (× ) 在多边形的方向判断中，多边形边界顺时针方向称为负方向。 ( × ) 同样的一个算法可以用几种不同的形式来描述，也可能存在几种解决相同问题的算法。 ( ) 判断圆在矩形中的充要条件是：圆心在矩形中且圆的半径小于等于圆心到矩四边的距离的最小值。 （ ）

网络数据结构的基本组成部分和属性是链和结点。 （ ） 所有元素存放在一片连续的存贮单元中，逻辑上相邻的元素存放到计算机内存仍然相邻这种存储方式是链接存储方式。 (× ) 紧凑度是反映城市的紧凑程度，其中圆形区域被认为最紧凑，紧凑度为1。其它形状的区域，其离散程度越小则紧凑度越低。 (× ) 缓冲区实现算法有矢量方法和栅格方法两种。 ( ) 对于块式编码来说，图斑越碎，压缩比越高。 (× ) 矢量数据的压缩往往是不可逆的，数据压缩后数据量变小了， 但数据的精度不变。 (× )

维述扩展的9交集模型关系非常复杂,通过对大量的空间关系进行归纳和分类,得出5种基本的空间关系，这5种关系定义为空间关系的最小集,他们具有哪些特征？

（1）相互之间不能进行转化；（2）能覆盖所有的空间关系模式；（3）能应用于同维与不同维的几何目标；（4）每一种关系对应于唯一的DE-9IM矩阵；

（5）任何其它的DE-9IM关系可以通过用这5种基本关系进行表达。 简述Dijkstra算法的步骤。

（1）引进一个辅助向量D，它的每个分量D[i]表示当前所找到的从起点

vm 到每个终点vi的最短路径的长度。

假设用带权的邻接矩阵arcs来表示带权有向图，arcs[i][j]表示弧 上的权值。

若 不连通，则arcs[i][j]=∞。 那么D[i]的初值为：D[i]=arcs[m][i] vi∈V

此外，将已找到的从vm 出发的最短路径的终点的集合记为S，它的初始状态为空集。

（2）选择 vj 使得 D[j]=Min{D[i] | vi∈V-S}

Vj就是当前求得的一条从vm出发的最短路径的终点。其中j为这条最短路径的终点，将其加入到终点集合S，令S=S∪{j}

（3）修改辅助向量D，即修改从vm出发到集合V-S上任一顶点vk可达的最短路径长度。