空间数据结构期末复习——思考题.pdf

第 1 章 绪论 1 数据结构和数据类型的区别 数据结构研究的是数据之间的逻辑关系 数据类型研究的是每类数据所共有的特性 2 数据的逻辑结构分类 线性结构 树形结构 图状结构 集合结构 3 叙述算法的定义及其重要特性 算法是对特定问题求解步骤的一种描述 它是指令的有限序列 是一系列输入转换为输出的计算步骤 重要特性 有穷性 确定性 可行性 有输入 有输出 4 选择某种问题最佳数据结构的标准是什么 时间复杂度和空间复杂度 5 分析并写出下面的各语句组所代表的算法的时间复杂度 赋值i n i for j 1 j i j for k 1 k j k s i k printf d s O n 3 2 i 1 k 0 2 while i n 1 n 1 k k 10 i 2 n 1 i n 1 O n 3 i 1 k 0 n 100 3 do k k 10 i 2 i 1 while i n 1 O 1 4 i 1 j 0 2 while i jj j n 2 else i n 2 O n 5 x n n 1 1 y 0 1 while x y 1 y 1 根号 n 1 y 1 O 根号 n 6 m 91 n 100 2 while n 0 if m 0 m m 1 n 3 else m 1 O 309 0 1 第 2 章 线性表 1 线性表的定义和基本运算 线性表是指 n n 0 个具有相同类型数据元素 或称结点 的有限序列 基本运算 1 Initiate L 初始化运算 该函数用于设定一个空的线性表 L 2 Length L 求长度函数 该函数返回给定线性表 L 中数据元素的个数 3 Get L i 取元素操作 若 1 i Length L 则函数值为给定线性表中第 i 个数据元素 否则为空元素 NULL 4 Prior L x 求前驱函数 当 x 在线性表 L 中 且其位序大于 1 则函数值为 x 的直接前驱 否则为空元素 5 Next L x 求后继函数 当 x 在线性表 L 中 且其位序小于 Length L 则函数值为 x 的直接后继 否则为空元素 6 Locate L x 定位操作 如线性表中存在和 x 相等的数据元素 则返回该数据元素的位序 若满足条件的元素不惟一 则返回最小的位序 7 Insert L i x 前插操作 若 1 i Length L 1 则在线性表 L 中第 i 个元素之前插入新结点 x 8 Delete L i 删除操作 若 1 i Length L 则删除线性表 L 中第 i 个元素 9 Empty L 判空函数 若 L 为空表 则返回值为 1 表示 真 否则返回值为 0 表示 假 10 Clear L 置空操作 将线性表 L 值为空表 2 试比较顺序存储结构和链式存储结构的区别及各自的优缺点 顺序存储结构的特点是逻辑上相邻的结点在存储结构中也相邻 优点 1 方法简单 各种高级语言中都有数组 容易实现 2 不用为表示结点间的逻辑关系而增加额外的存储开销 3 是随机存取存储结构 缺点 1 在插入和删除结点时 需移动大量元素 2 需要预先分配足够大的存储空间 链式存储结构的特点是逻辑上相邻的数据元素其物理位置不要求紧邻 优点 1 插入 删除运算方便 2 充分利用存储空间 缺点 1 要占用额外的存储空间用来存储元素之间的关系 2 非随机存取存储结构 3 试写出一个计算链表中数据元素结点个数的算法 其中指针 p 指向该链表的第一个结点 int ListLength L LinkList i 0 while p p p next i return i 4 试设计实现在单链表中删去值相同的多余结点的算法 status ListDelete L LinkList while p q p next r p while q if q data p data r next q next free q q r next else r q q q next p p next 5 有一个线性表 a1 a2 an 它存储在有附加表头结点的单链表中 写一个算法 求出该线性表中值为 x 的元 素的序号 如果 x 不存在 则输出序号为 0 int Locate L LinkList L int x k 1 for p L next p p p next k if k n return k else return 0 6 设有两个链表 A B 它们的数据元素分别为 x1 x2 xm 和 y1 y2 yn 写一个算法将它们合并为一个 线性表 C 使得 当 m n 时 C xl y1 x2 y2 xn yn xm 当 mnumber while n n 1 if n 1 head p1 else p2 next p1 p2 p1 p1 struct Node malloc L if a 1 scanf ld a p2 next NULL return head 7 写一个算法将值为 b 的结点插在链表中值为 a 的结点之后 如果值为 a 的结点不存在 则插入在表尾 void Insert LinkList LinkList L DataType a Datatype b LinkList p q s s LinkList malloc sizeof struct node s data b s next NULL q L p L next while p NULLp p next If p s next p next p next s else s next q next q next s 第 3 章 栈和队列 1 假定有编号为 A B C D 的 4 辆列车 顺序开进一个栈式结构的站台 请写出开出车站站台的列车顺序 注 每一列车由站台开出时均可进栈 出栈开出站台 但不允许出栈后回退 写出每一种可能的序列 ABCD ABDC ACBD ACDB ADCB BACD BADC BCAD BCDA BDCA CBAD CBDA CDBA DCBA 2 已知堆栈采用链式存储结构 初始时为空 试画出 a b c d 4 个元素依次以后堆栈的状态 然后再画出此时 的栈顶元素出栈后的状态 初始时 空 1 a 入栈 header a 2 b 入栈 header b a 3 c 入栈 header c b a 3 d 入栈 header d c b a 所以 最后栈项元素是 d 3 写出链栈的取栈顶元素和置空栈的算法 取栈顶元素 ElemType Top SeqStack SeqStack s if Empty SeqStack s return OVERFLOW else return s elem s top 置空栈 void Init LS StackNode top top NULL 4 写出多个链表栈中取第 j 个链表栈顶元素值的算法 5 栈和队列的区别 栈是限定仅在表尾的一端进行插入或删除的线性表 后进先出 盘子 队列是限定仅能在表头进行删除 表尾进行插入的线性表 先进先出 水管 6 何为队列的上溢现象 解决它有哪些方法 队列空间已满 而继续往队列中插入元素 就会使数组越界而导致程序代码被破坏 建立一个足够大的存储空间 但这样做会造成空间的使用效率降低 第 6 章 树 1 找出下图所示树 T 的深度 度 分支结点和叶子结点 树的深度 树中结点的最大层次值 4 树的度 树中结点的度 结点拥有的子树数 的最大值 4 FGH B L C IJK M ED A 分支结点 度不为 0 的结点 ABDEHJ 叶子结点 度为 0 的结点 CFGIKLM 2 对于三个结点 A B C 可组成多少种不同的二叉树 请画出 30 种 a 是根节点 a 的左孩子 b a 的右孩子 c a 是根节点 a 的左孩子 b b 的左孩子 c a 是根节点 a 的左孩子 b b 的右孩子 c a 是根节点 a 的右孩子 b b 的左孩子 c a 是根节点 a 的右孩子 b b 的右孩子 c 3 二叉树链式存储结构的组织方式 在每个链结点中除存储结点本身的数据外 再设置两个指针字段 lchild 和 rchild 分别存放结点的左子女和右子女所在链结 点的存储地址 当结点的某个子女为空时 则相应的指针为空指针 lchild data rchild 4 二叉树的三种遍历方法及其算法 1 先根遍历 若二叉树为空 则返回 否则 访问根结点 先序遍历左子树 先序遍历右子树 2 中根遍历 若二叉树为空 则返回 否则 中序遍历左子树 访问根结点 中序遍历右子树 3 后根遍历 若二叉树为空 则返回 否则 后序遍历左子树 后序遍历右子树 访问根结点 5 分别写出下图所示二叉树的三种遍历次序的序列 先根遍历 ABDEHICFGJ 中根遍历 DBHEIAFCJG 后根遍历 DHIEBFJGCA 6 现有按后根遍历二叉树的结果为 C B A 有几种不同的二叉树可以得到这一结果 5 种 7 画出下图所示二叉树先根 中根 后根线索化树的逻辑表示图 8 有一组数值 14 21 32 15 28 画出哈夫曼树的生成过程及最后结果 9 为什么说一般二叉树一般不采用顺序存储结构 而满二叉树和完全二叉树多采用顺序存储结构 因为一般二叉树采用顺序存储结构时 虽然简单但会造成存储空间的浪费 对满二叉树和完全二叉树而言 顺序存储结构既简单 又节省存储空间 10 用哈夫曼算法构造哈夫曼树时森林中两棵权值最小和次小的子树合并时 哪棵做左子树并不影响 WPL 影响哈 DEFG BC HI J A DEFG BC HI J A 夫曼编码吗 不影响 影响 11 树和二叉树之间有何区别 1 二叉树可以为空树 2 二叉树的度不大于 2 即每个结点至多只有两棵子树 3 二叉树是有序树 其左子树和右子树是严格区分且不能随意颠倒的 第 7 章 图 1 图有哪两种常用的存储结构 它们是如何存储的 邻接矩阵 用一个二维数组来表示图中顶点的相邻关系 邻接链表 是一种顺序分配和链式分配相结合的存储结构 包括向量和链表两部分 2 对于给出的无向图 求 1 每个顶点的自由度 2 4 3 2 3 4 3 2 3 2 图的邻接矩阵 3 图的邻接链表 3 请写出对下图 按深度优先搜索和广度优先搜索从顶点 出发遍历图的结果 DFS BFS 4 设用邻接矩阵来表示无向图 试用 C 语言写出从某一顶点出发 采用广度优先搜索遍历图的程序 首先以一个结构体存储一个图 struct MGraph int vertex maxvertex 存顶点 int arc maxvertex maxvertex 存边 邻接矩阵 int vertexnum arcnum 顶点数和边数 其次是对图的初始化 void CreatMGraph MGraph cin1 G vertexnum G arcnum 输入顶点数和边数 for i 0 ivertexnum i 输入每个顶点的值 cin1 G vertex i for i 0 ivertexnum i 初始化邻接矩阵 for j 0 jvertexnum j G arc i j 0 for i 0 iarcnum i int n m w cin1 n m w 修改邻接矩阵中的值 G arc n m w G arc m n w 在此之前需要定义一个全局变量的visited 数组 int visited maxvertex 标记已被访问过的顶点 全局变量 广度优先遍历 void BFS MGraph int x j if visited v 即为visited v 0 也就是未被访问过 cout vertex v 36 45 7 8 29 1 6 3 5 4 1 2 visited v 1 q push v 被访问的顶点入队 while q empty 队不空进循环 x q front 取队头元素 q pop 队头出队 for j 0 jvertexnum j if G arc x j visited j 1 标记为访问过 q push j 被访问的顶点继续入队 5 迪杰斯特拉 Dijkstra 算法的基本步骤 6 弗洛伊德 Floyd 算法的基本步骤 设立两个矩阵 分别用来记录各顶点间路径和相应的路径长度 矩阵 P 表示路径 矩阵 A 用来表示路径长度 过程如下 1 复制图 G 的邻接矩阵 cost 为矩阵 A 的值 即顶点 vi到顶点 vj的最短路径长度 A i j 就是弧所对应的权值 若 不存在 则 A i j 为 记为 A 1 2 从顶点 vi到顶点 vj的最短路径长度 首先考虑让路径经过顶点 v0 比较路径和的长度 取其短者为当前求 得的最短路径 记 A 0 3 在 A 0 的基础上让路径经过顶点 v 1 比较路径和的长度 取其短者为当前求得的最短路径 记 A 1 4 在 A k 1 的基础上让路径经过顶点 v k 比较路径和的长度 取其短者为当前求得的最短路径 记 A k A k i j 就是当前求得的从顶点 vi到顶点 vj的最短路径长度 5 经过 n 次试探 就把 n 个顶点都考虑到相应的路径中 求得的 A n 1 就一定是各顶点间的最短路径长度 7 用弗洛伊德算法求下图中的每一对顶点间的最短路径 写出其计算过程 第 10 章 空间数据结构 1 空间数据的类型 空间数据根据表示对象的不同 又具体分为七种类型 它们各表示的具体内容如下 1 类型数据 例如考古地点 道路线 土壤类型的分布等 2 面域数据 例如随机多边形的中心点 行政区域界线 行政单元等 3 网络数据 例如道路交点 街道 街区等 1 23 b a c 5 4 1032 4 样本数据 例如气象站 航线 野外样方分布区等 5 曲面数据 例如高程点 等高线 等值区域等 6 文本数据 例如地名 河流名称 区域名称等 7 符号数据 例如点状符号 线状符号 面状符号 晕线 等 所有这些不同类型的数据都可以分为点 线 面三种不同的图形 并可以分别采用 x y 平面坐标 地理经纬度 或者格 网法表示 2 空间数据的基本特征 空间特征 属性特征 时间特征 3 栅格数据结构 栅格数据的特点 栅格数据的获取方法 栅格数据存储压缩编码方法主要有哪几种 每种方法 是如何进行压缩的 栅格数据结构 是最简单最直观的空间数据结构 又称为网格结构或像元结构 栅格数据的特点 1 用离散的量化栅格值表示空间实体 2 描述区域属性明显 位置隐含 3 数据结构简单 易于与遥感 数据等结合 4 难于建立地物间拓扑关系 5 图形质量低且数据量大 栅格数据的获取方法 目读法 矢量数字化法 扫描数字化 分类影像输入 栅格数据存储压缩编码方法 1 链式编码 它把线状地物和面状地物的边界表示为 由某一起始点开始并按某些基本方向确定的单位矢量链 2 游程长度编码 只在各行 或列 数据的代码发生变化时依次记录该代码以及相同代码重复的个数 只在各行 或列 数据的代 码发生变化时依次记录该代码位置以及相应的代码 3 块状编码 采用方形区域作为记录单元 每个记录单元包括相邻的若干栅格 数据编码由初始位置 行 列号 和半径 再加 上记录单元的代码组成 即数据对组成 初始行 列 半径 属性值 4 四叉树编码 将一幅栅格地图或图像等分为四部分 逐块检查其格网属性值 或灰度 如果某个子区的所有格网值都具有相 同的值 则这个子区就不再继续分割 否则还要把这个子区再分割成四个子区 这样依次地分割 递归分割成 2n 2 n 个子区 且 n 1 直到每个子块都只含有相同的属性值或灰度为止 4 矢量数据结构 矢量结构的特点