教材：《数据结构》严蔚敏吴伟民清华大学出版社
《数据结构算法实现及解析》高一凡西安电子科技大学出版社
第一部分数据结构概述
一、定义（研究是数据结构的存储和数据的操作的）
如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如查找某个元素，删除某个元素，对所有元素进行排序）而执行的相应操作，这个相应的操作也叫做算法。
数据结构= 个体的存储（从某个角度而言，可忽略）+ 个体与个体之间关系的存储（核心）
算法= 对存储数据的操作
二、算法
解题的方法和步骤
衡量算法的标准
1.时间复杂度
大概程序要执行的次数，而非执行的时间
2.空间复杂度
算法执行过程中大概所占用的最大内存
3.难易程度（即可读性）
4.健壮性
三、数据结构的地位
数据结构是软件中最核心的内容
程序= 数据的存储+ 数据的操作+ 可以被计算机执行的语言
第二部分预备知识
一、指针
指针的重要性：指针是C语言的灵魂
定义
地址：内存单元的编号
从零开始的非负整数
范围：0--FFFFFFFF（即0--4G-1）
指针：
指针就是地址，地址就是指针
指针变量是存放内存单元地址的变量
指针的本质是一个操作受限的非负整数（只能进行减运算）分类：
1.基本类型的指针
2.指针和一维数组的关系
二、结构体
为什么会出现结构体
为了表示一些复杂的数据，而普通的基本类型变量无法满足要求什么叫结构体
结构体是用户根据实际需要自己定义的数据类型
如何使用结构体
两种方式：
struct Student st = {1000, "zhangsan", 20}
struct Student * pst = &st;
1.st.sid
2.pst->sid
pst所指向的结构体变量中的sid这个成员
注意事项
结构体变量不能加减乘除，但可以相互赋值
普通结构体变量和结构体指针变量作为函数传参问题
三、动态内存的分配和释放
假设动态构造一个int型的一位数组
int len；
int * pArr = (int *)malloc (sizeof(int) * len);
①本语句分配了两块内存，一块内存是动态分配的，总共len个字节；另一块是静态分配的，是pArr变量本身所占的内存，总共4个字节。
②malloc只有一个int型的形参，表示要求系统分配的字节数
③malloc函数的功能是请求系统分配len个字节的内存空间，如果分配成功，则返回第一个字节的地址，如果分配不成功，则返回NULL
④malloc函数能且只能返回第一个字节的地址，所以我们需要把这个无任何实际意义的第一个字节的地址（俗称干地址）转化为一个有实际意义的地址，因此，malloc函数前面必须加强制类型转换（数据类型 *），表示把这个无实际意义的第一个字节的地址转化为相应类型的地址。
⑤free（* pArr）
表示把pArr所指向的内存给释放掉
pArr本身的内存是静态的，不能有程序员手动释放，只能在pArr变量所在的函数运行终止时有系统自动释放
⑥跨函数使用内存
静态内存不可以跨函数使用：
静态内存在函数执行期间可以被其它函数使用
静态内存在函数执行完毕之后就不能在被其它函数使用
动态内存可以跨函数使用
动态内存在函数执行完毕之后仍然可以被其它函数使用
第三部分模块一：线性结构[把所有的结点用一条直线穿起来]
一、连续存储[数组]
1.什么叫做数组
元素类型相同，大小相等
2.数组的优缺点（相对于链表）
优点：存取速度快
缺点：实现必须知道数组的长度
需要大块连续的内存块
插入和删除元素很慢
空间通常是有限制的
二、离散存储[链表]
1.定义
N个结点离散分配
彼此通过指针相连
每个结点只有一个前驱结点，每个结点只有一个后续结点
首结点没有前驱结点，尾结点没有后续结点
专业术语：
首结点：第一个存放有效数据的结点
尾结点：最有一个存放有效数据的结点
头结点：头结点的数据类型和首结点的类型是一样的
首结点之前的结点
头结点并不存放有效数据
加头结点的目的是为了方便对链表的操作
头指针：指向头结点的指针变量
尾指针：指向尾结点的指针变量
确定一个链表需要几个参数：
（如果希望通过一个函数来对链表进行处理，我们至少需要接受链表的那些参数）
一个参数，即头指针，因为我们通过头指针可以推算出链表的其它所有的信息
2.分类
单链表
双链表：每一个结点有两个指针域
循环链表：能通过任何一个结点找到其它所有的结点
非循环链表
3.算法
遍历/ 查找/ 清空/ 销毁/ 求长度/ 排序/ 删除结点/ 插入结点
插入结点：(伪算法)
① r = p->pNext; p->pNext = q; q->pNext = r;
② q->pNext = p->pNext; p->pNext = q;(这两行代码不能倒过来)
删除结点：（伪算法）
r = p->pNext; p->pNext = p->pNext->pNext; free(r);
狭义的算法是与数据的存储方式密切相关
广义的算法是与数据的存储方式无关
泛型：
利用某种技术达到的效果就是：不同的存储方式，执行的操作是一样的
同一种逻辑结构（包括线性结构和非线性结构，其中非线性结构包括树和图），无论该逻辑结构物理存储（包括数组和链表）是什么样子的，我们都可以对它执行相同的操作
4.链表的优缺点（相对于数组）
优点：空间没有限制
插入和删除元素很快
缺点：存取的速度很慢
三、线性结构的两种常见应用之一栈
1.定义：一种可以实现“先进后出”的存储结构
栈类似于箱子
2.分类
静态栈：以数组为内核
动态栈：以链表为内核
3.算法
出栈/ 入栈
4.应用
函数调用/ 中断/ 表达式求值/内存分配/ 缓冲处理/ 迷宫
四、线性结构的两种常见应用之一队列
1.定义：一种可以实现“先进先出”的存储结构
队列类似于排队买票
2.分类
链式队列---- 用链表实现
静态队列---- 用数组实现
静态队列通常都必须是循环队列
循环队列的讲解：
①静态队列为什么必须是循环队列
普通队列的参数front和rear只增不减，导致内存浪费
②循环队列需要几个参数来确定
需要两个参数：front / rear
③循环队列各个参数的含义
两个参数在不同的场合有不同的含义
①队列初始化
front 和rear 的值都为零
②队列非空
front 代表的是队列的第一个元素
rear 代表的是队列的最后一个有效元素的下一个元素
③队列空
front 和rear 的值相等，但不一定是零
④循环队列入队伪算法讲解(在尾部入队)
第一步：将值存入rear所指向的位置
第二步：rear = (rear + 1)%数组的长度
⑤循环队列出队伪算法讲解（在头部出队）
front = (front +1)%数组的长度
⑥如何判断循环队列为空
如果front 与rear的值相等，则该队列一定为空
⑦如何判断循环队列为满
第一种方法：多增加一个标识参数，即数组的长度
（常用）第二种方法：少用一个元素，如果front == (rear + 1)%数组的长度，则
循环队列已满
3.算法
出队/ 入队
4.应用
所有和时间有关的操作都有队列的影子
五、专题：递归（使用栈实现的）
1、定义:一个函数自己直接或间接调用自己
2、函数的调用
当在一个函数的运行期间调用另一个函数时，在运行被调函数之前，系统需要完成三件事：
a、将所有的实际参数、返回地址等信息传递给被调函数保存
b、为被调函数的局部变量（包括形参）分配存储空间
c、将控制转移到被调函数的入口
从被调函数返回主调函数之前，系统也要完成三件事：
a、保存被调函数返回结果
b、释放被调函数所占的存储空间
c、依照被调函数保存的返回地址将控制转移到调用函数
当有多个函数相互调用时，按照“后调用先返回”的原则，上述函数之间的信息传递和控制转移必须借助“栈”来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就在栈顶分配一个存储区，进行压栈操作；每当一个函数退出时，就释放它的存储区，进行出栈操作，当前运行的函数永远都在栈顶位置。
A函数调用A函数与A函数调用B函数在计算机看来是没有任何区别的，只不过用我们日常的思维方式理解比较怪异而已。
3、递归必须满足的三个条件：
a、递归必须得有一个明确的终止条件
b、该函数处理的数据规模必须在递减
c、这个转化必须是可解的
4、循环和递归之间的关系
理论上循环能解决的问题，肯定可以转化为递归解决，但是这个过程是复杂的数学转化过程，递归能解决的问题不一定能转化为循环解决
递归的优缺点：
易于理解
速度慢
存储空间大
循环的优缺点：
不易理解
速度快
存储空间小
5、举例：
1.1+2+3+4+...+100的和
2.求阶乘
①使用for循环实现：
求和求阶乘
# include
int main(void) int main(void)
{ {
long sum = 0; long mult = 1;
for（int i = 1;i < = 100;i ++）int val;
sum = sum + i; printf("请输出整数：")
printf("1到100的和是：%ld", sum); scanf ("%d",&val);
return 0; for (int i = 1; i < = val; i ++)
} mult = mult * i;
printf("%d的阶乘是%ld", val, mult);
return 0;
}
②使用递归实现：
#include
long sum (int val) long mult (int val)
{ {
if(1 == val) if(1 == val)
return 1; return 1;
else else
return val+sum(val - 1); return val*mult(val-1);
} }
int man(void) int main(void)
{ {
printf("1到100的和是：%ld",sum(100)); printf("请输出整数：")
return 0; scanf ("%d",&val);
} printf("%d的阶乘是%ld", val, mult(val));
return 0;
}
3.汉诺塔
伪算法：
if（1 == n）
直接将盘子从A移动到C
else
{（三步）
第一步：将A上的前n - 1个盘子借助B移动到C
第二步：将A上的第n个盘子直接移动到C
第三步：将B上的n - 1个盘子借助A移动到C
}
4.走迷宫
6、递归的应用
树和森林就是以递归的方式定义的
树和图的很多算法都是以递归来实现的
很多数学公式就是以递归的方式定义的（例如：斐波拉契序列）
第四部分模块二：非线性结构
一、树
1、定义
（专业定义）有且只有一个称为根的结点；有若干个互不相交的子树，这些子树本身也是一棵树
（通俗定义）树是由结点和边（即指针）组成；每一个结点只有一个父结点但可以有多个子结点；但是有一个结点例外，该结点没有父结点，此结点称为根结点
专业术语
结点/ 父结点（只有一个）/ 子结点/ 子孙/ 堂兄弟
深度:从根结点到最底层结点的层数（根结点是第一层）
叶子结点：没有子结点的结点
非终端结点：实际就是非叶子结点，即有子结点的结点
度：子结点的个数
2、分类
一般树：任意一个结点的子结点的个数都不受限制
二叉树：任意一个结点的子结点的个数最多两个，且子节点的位置不可更改二叉树的分类：
一般二叉树
满二叉树：在不增加树的层数的情况下，无法再多添加一个结点的二叉树就是满二叉树
完全二叉树：如果只是删除满二叉树最底层最右边的连续若干个结点，这样形成的二叉树就是完全二叉树
满二叉树是完全二叉树的特例，完全二叉树包含满二叉树
森林：n个互不相交的树的集合
3、存储（解决非线性结构用线性结构表示的问题）
二叉树的存储
连续存储[完全二叉树]
一般二叉树要以数组的方式存储，要先转化成完全二叉树，因为如果只存有效节点（无论以哪种规则：先序，中序，后序），则无法知道这个树的原本样子。
优点：查找某个结点的父结点和子结点（也包括判断有没有子结点）速度很快
缺点：耗用内存空间过大
链式存储
一般树的存储
双亲表示法（求父结点方便）
孩子表示法（求子结点方便）
孩子双亲表示法（求父结点和子结点都方便）
二叉树表示法
把一棵普通树转化成二叉树来存储
具体转化方法：
设法保证任意一个结点的左指针域指向它的第一个孩子，右指针域指向它的下一个兄弟
一棵普通树转化为的二叉树一定没有右子树
森林的存储
先把森林转化为二叉树，再存储二叉树
具体方式为：根节点之间可以当成是兄弟来看待
4、操作
树的遍历
先序遍历[先访问根结点]
先访问根结点，再先序访问左子树，后先序访问右子树
中序遍历[中间访问根结点]
先中序遍历左子树，再访问根节点，后中序访问右子树
后序遍历[最后访问根结点]
先中序遍历左子树，再中序遍历右子树，后访问根结点已知两种遍历求原始二叉树
通过先序遍历和中序遍历或者中序遍历和后序遍历我们可以还原出原始的二叉树，但是通过先序遍历和后序遍历是无法还原出原始的二叉树的。
换种说法：只有通过先序遍历和中序遍历或者中序遍历和后序遍历我们才可以唯一的确定一个二叉树的。
5、应用
树是数据库中数据组织的一种重要形式
操作系统子父进程的关系本身就是一棵树
面向对象语言中类的继承关系本身就是一棵树
赫夫曼树
二、图
第五部分模块三：查找和排序
两者的关系：排序是查找的前提，排序是重点
折半查找
排序：（考虑三个问题：时间、空间、稳定性）
冒泡
插入
选择
快速排序
归并排序
第六部分Java中容器和数据结构相关知识
Iterator接口
Map
哈希表
教材：《数据结构》严蔚敏吴伟民清华大学出版社 《数据结构算法实现及解析》高一凡西安电子科技大学出版社 第一部分数据结构概述 一、定义（研究是数据结构的存储和数据的操作的） 如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如查找某个元素，删除某个元素，对所有元素进行排序）而执行的相应操作，这个相应的操作也叫做算法。 数据结构= 个体的存储（从某个角度而言，可忽略）+ 个体与个体之间关系的存储（核心） 算法= 对存储数据的操作 二、算法 解题的方法和步骤 衡量算法的标准 1.时间复杂度 大概程序要执行的次数，而非执行的时间 2.空间复杂度 算法执行过程中大概所占用的最大内存 3.难易程度（即可读性） 4.健壮性 三、数据结构的地位 数据结构是软件中最核心的内容 程序= 数据的存储+ 数据的操作+ 可以被计算机执行的语言 第二部分预备知识 一、指针
指针的重要性：指针是C语言的灵魂 定义 地址：内存单元的编号 从零开始的非负整数 范围：0--FFFFFFFF（即0--4G-1） 指针： 指针就是地址，地址就是指针 指针变量是存放内存单元地址的变量 指针的本质是一个操作受限的非负整数（只能进行减运算）分类： 1.基本类型的指针 2.指针和一维数组的关系 二、结构体 为什么会出现结构体 为了表示一些复杂的数据，而普通的基本类型变量无法满足要求什么叫结构体 结构体是用户根据实际需要自己定义的数据类型 如何使用结构体 两种方式： struct Student st = {1000, "zhangsan", 20} struct Student * pst = &st; 1.st.sid 2.pst->sid pst所指向的结构体变量中的sid这个成员
空间数据库概论答案 【篇一：数据库系统概论试题及答案整理版】 >第一章绪论 一、选择题 1. 在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。在这几个 阶段中，数据独立性最高的是a阶段。 a．数据库系 2. 数据库的概念模型独立于a。 a．具体的机器和dbms 3. 数据库的基本特点是b。 a.(1)数据结构化 (2)数据独立性 (3)数据共享性高，冗余大，易移植 b.(1)数据结构化 (2)数据独立性 (3)数据共享性高，冗余小，易扩充 c.(1)数据结构化 (2)数据互换性 (3)数据共享性高，冗余小，易扩充 (4)统一管理和控制(4)统一管理和控制(4)统一管理和控制 b．e-r图 c．信息世界 d．现实世界 b．文件系统 c．人工管理 d．数据项管理 d.(1)数据非结构化 (2)数据独立性 (3)数据共享性高，冗余小，易扩充(4)统一管理和控制 4. b是存储在计算机内有结构的数据的集合。 a．数据库系统 5. 数据库中存储的是c。 a. 数据 6. 数据库中，数据的物理独立性是指c。 a．数据库与数据库管理系统的相互独立 b．用户程序与dbms的相互独立 c．用户的应用程序与存储在磁盘上数据库中的数据是相互独立的d．应用程序与数据库中数据的逻辑结构相互独立 7. 数据库的特点之一是数据的共享，严格地讲，这里的数据共享是指d。
a．同一个应用中的多个程序共享一个数据集合 b．多个用户、同一种语言共享数据 c．多个用户共享一个数据文件 d．多种应用、多种语言、多个用户相互覆盖地使用数据集合 b. 数据模型 c. 数据及数据间的联系 d. 信息 b．数据库 c．数据库管理系统 d．数据结构 8. 数据库系统的核心是b。 a．数据库 9. 下述关于数据库系统的正确叙述是 a 。 a．数据库系统减少了数据冗余b．数据库系统避免了一切冗余 c．数据库系统中数据的一致性是指数据类型一致 d．数据库系统比文件系统能管理更多的数据 10. 数将数据库的结构划分成多个层次，是为了提高数据库的 b ①和 b ②。①a．数据独立性 ②a. 数据独立性 11. 数据库(db)、数据库系统(dbs)和数据库管理系统(dbms)三者之间的关系是 a 。 a．dbs包括db和dbmsc．db包括dbs和dbms 12. 在数据库中，产生数据不一致的根本原因是d。 a．数据存储量太大 b．没有严格保护数据 d．数据冗余 b．ddms包括db和dbs d．dbs就是db，也就是dbms b．逻辑独立性 b．物理独立性 c．管理规范性 c．逻辑独立性 d．数据的共享 b．数据库管理系统 c．数据模型 d．软件工具 d．管理规范性 c．未对数据进行完整性控制 13. 数据库管理系统(dbms)是d。 a．数学软件
复习提纲 第一章数据结构概述 基本概念与术语（P3） 1．数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科. 2．数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合 2．数据元素是数据的基本单位 3．数据对象相同性质的数据元素的集合 4．数据结构包括三方面内容:数据的逻辑结构.数据的存储结构.数据的操作. （1）数据的逻辑结构指数据元素之间固有的逻辑关系. （2）数据的存储结构指数据元素及其关系在计算机内的表示 ( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等. 5.时间复杂度分析 -------------------------------------------------------------------------------------------------------------------- 1、名词解释：数据结构、二元组 2、根据数据元素之间关系的不同，数据的逻辑结构可以分为 集合、线性结构、树形结构和图状结构四种类型。 3、常见的数据存储结构一般有四种类型，它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。 4、以下程序段的时间复杂度为___O(N2)_____。 int i,j,x; for(i=0;i 空间数据挖掘 一、空间数据库概述 空间数据库指的是地理信息系统在计算机物理存储介质上存储的与应用相关的地理空间数据的总和，一般是以一系列特定结构的文件的形式组织在存储介质之上的。空间数据库的研究始于20世纪70年代的地图制图与遥感图像处理领域，其目的是为了有效地利用卫星遥感资源迅速绘制出各种经济专题地图。由于传统的关系数据库在空间数据的表示、存储、管理、检索上存在许多缺陷，从而形成了空间数据库这一数据库研究领域。而传统数据库系统只针对简单对象，无法有效的支持复杂对象（如图形、图像）。 空间数据挖掘是指从空间数据库中抽取没有清楚表现出来的隐含的知识和空间关系，并发现其中有用的特征和模式的理论、方法和技术。空间数据挖掘和知识发现的过程大致可分为以下多个步骤：数据准备、数据选择、数据预处理、数据缩减或者数据变换、确定数据挖掘目标、确定知识发现算法、数据挖掘、模式解释、知识评价等，而数据挖掘只是其中的一个关键步骤。但是为了简便，人们常常用空间数据挖掘来代替空间数据挖掘和知识发现。 空间数据挖掘与传统数据挖掘的不同表现在以下三个方面： 传统数据挖掘处理的是数字和类，而空间数据则是一些更为复杂的数据类型；传统数据挖掘通常具有显式的输入，而空间数据挖掘的输入则常常是隐式的；在传统数据挖掘中，有一个至关重要的前提假设：数据样品是独立生成的。而这一假设在空间数据分析中是不成立的。事实上，空间数据之间是高度自关联的。 二、空间数据挖掘的技术特点 (一)数据挖掘算法具有高效、可测的特点 数据库一般有数千个表和属性以及上百万个元组。数据库中千兆级别的数据已不再罕见，因为万亿级别的数量数据库已经腾空出世，取代了千兆级别的数据库。高维空间的海量数据库不但使搜索的空间变大，而且更容易发现模式存在的错误，所以充分利用相关知识去改变维数，降低维数，删除多余的数据，使数据挖掘的算法更具高效性。海量空间数据提供知识的算法要有可测性、高效性。多项式算法和指数算法没有实际的使用价值，但是若把算法换成以有限的数据做成特定的模型来获取合适的参数，实现的价值将会相当可观。 (二)所挖掘的信息来源于各种数据 用因特网、广域网、局域网与其他数据源组成一个结构复杂、空间庞大的数据库。数据进行挖掘主要是在各种语义的非格式化和格式化的数据中挖掘数据知识，这种数据挖掘可以弥补庞大、复杂的数据库所不能查询的数据知识。数据库本身已拥有分布广、规模大、数据挖掘方法复杂等特性，该特性的要求是要构建一种分布平行的数据挖掘技术。 1 概述 一、选择题： 1、下列算法的时间复杂度是（） for(i=0;i 数据结构概论考核题 C. 0 1 3 2 D.0 3 1 2 （第9题配图：数组的下标为0,1,2,3） 10.对于哈希函数H(key)=key%13,被称为同义词的关键字是( D ) A.35和41 B.23和39 C.15和44 D.25和51 11.图的深度优先遍历类似于二叉树的( A ) A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历 12.下述几种排序方法中，稳定的排序算法是( A ) A.直接插入排序 B.快速排序 C.堆排序 D.希尔排序 13.依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位 置上的方法，称为( C ) A.希尔排序 B.冒泡排序 C.插入排序 D.选择排序 14.二叉树是非线性数据结构，所以 ( A ) A.它不能用顺序存储结构存储 B.它不能用链式存储结构存储 C.顺序存储结构和链式存储结构都能存储 D.顺序存储结构和链式存储结构都不能使用 15.有8个结点的无向图最多有( B )条边。 A.14 B.28 C.56 D.112 二、填空题（每小题1分，共15分） 1 当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的__时间复杂度______。 2 设数组a[M](M为最大空间个数)作为循环队列Q的存储空间，front为队头指针(指向第一个存 （3）重复（2），直到U=V为止。 此时，TE中必含有n-1条边，则T=（V，{TE}）为N的最小生成树。 2. 假设通信电文使用的字符集为{a,b,c,d,e,f,g}，若这些字符在电文中出现的频度分别为：3， 35，13，15，20，5和9，分别求出这些字符的等长编码以及哈夫曼编码，并比较他们的编码长度。 第一章概论自测题答案 一、填空题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象 以及它们之间的关系和运算等的学科。 2. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合， R是D上的关系有限集合。 3. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。 4.数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。 5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 6．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。 7. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。 8. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。 9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。 10. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。 11.一个算法的效率可分为时间效率和空间效率。 二、单项选择题 （B）1. 非线性结构是数据元素之间存在一种： A）一对多关系B）多对多关系C）多对一关系D）一对一关系 （ C ）2. 数据结构中，与所使用的计算机无关的是数据的结构； A) 存储B) 物理C) 逻辑D) 物理和存储 （C）3. 算法分析的目的是： A) 找出数据结构的合理性B) 研究算法中的输入和输出的关系 C) 分析算法的效率以求改进D) 分析算法的易懂性和文档性 （A）4. 算法分析的两个主要方面是： A) 空间复杂性和时间复杂性B) 正确性和简明性 C) 可读性和文档性D) 数据复杂性和程序复杂性 （ C ）5. 计算机算法指的是： A) 计算方法B) 排序方法 C) 解决问题的有限运算序列D) 调度方法 （B）6. 计算机算法必须具备输入、输出和等5个特性。 A) 可行性、可移植性和可扩充性B) 可行性、确定性和有穷性 C) 确定性、有穷性和稳定性D) 易读性、稳定性和安全性 三、简答题 2.【严题集1.2②】数据结构和数据类型两个概念之间有区别吗？ 答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。 第一章数据结构概述 基本概念与术语 1．数据：数据是用来描述现实世界的文字，字符，图像，声音，以及能够输入到计算机中并能被计算机处理的符号。 2.数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。 （补充：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。）3．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。（有时候也叫做属性。） 4．数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 （1）数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。 数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。 依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种： a.集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。 b.线性结构：结构中的数据元素之间存在“一对一“的关系。若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。 c.树形结构：结构中的数据元素之间存在“一对多“的关系。若数据为非空集，则除了第一个元素（根）之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直接后继。 d.图状结构：结构中的数据元素存在“多对多”的关系。若结构为非空集，折每个数据可有多个（或零个）直接后继。 （2）数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。 想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射为以下两种存储结构： a.顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。 b.链式存储结构：借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素物理位置上也相邻。 5.时间复杂度分析：a.常量阶：算法的时间复杂度与问题规模n无关系T(n)=O(1) b.线性阶：算法的时间复杂度与问题规模n成线性关系T(n)=O(n) c.平方阶和立方阶：一般为循环的嵌套，循环体最后条件为i++ 时间复杂度的大小比较： O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n ) 第四章GIS空间数据库 第一节空间数据库概述 一、数据库概念 数据库有三个基本部分组成： ⑴ 数据集（库）：按一定结构组织起来的相关数据的集合，既包括数据与数据间的联系。 ⑵ 物理存储介质：计算机的外存与内存储器，外存存储数据，内存存储操作系统与数据库管理系统，并有一定数量的缓冲区，用于数据处理。 ⑶ 数据库软件：核心是数据库管理系统（DBMS），对数据进行建立、定义、管理与维护，还有数据库应用系统，通过空间分析模型对数据进行分析与决策。 二、数据库特征 ⑴ 数据集中控制维护管理。 ⑵数据独立于应用程序。 ⑶ 数据共享，多用户可同时存续数据，提高使用效率。 ⑷ 减少数据冗余，提高数据的一致性。 ⑸ 数据结构化，数据按一定结构形式构成，数据间具有联系。 ⑹ 数据保护功能，具有使用权限，确保数据安全。 第二节数据模型 一、关系模型 关系模型是以数学理论为基础构建的数据模型，它把复杂的数据结构归纳为简单的二元关系，即把每一个实体集看作是一个二维表。关系模型是用一个单一的二维表结构表示实体及实体间的联系，而满足一定条件的二维表称为一个关系。其中每一行是一个实体（记录），每一列是一个实体属性（字段），表中第一行是各字段的型的集合。 作为一个关系的二维表，必须满足以下条件： ⑴ 表中的每一个属性值都是不可再分的基本单元； ⑵ 表中每一列的属性名必须是唯一的； ⑶ 表中每一列必须有相同的数据类型； ⑷ 表中不能有完全相同的行； 关系模型的最大特点是描述的一致性，结构简单清晰。显然，实体及其联系在关系表中一目了然。也可以通过关系之间的连接运算建立新的关系，对关系数据库的查询和统计操作均通过布尔逻辑与数学关系运算实现。关系模型存取路径完全对用户隐蔽，使程序与数据具有高度的独立性。关系模型使用与维护方便。 由关系数据结构组成的数据库系统称为关系数据库系统。在关系数据库中，对数据的操作几乎全部建立在一个或多个关系表格上，通过对这些表格的操作来实现对数据的管理。 二、层次模型与树结构 层次模型是在数据处理中发展最早、技术上已成熟的一种数据模型。他的特点是将数据组织成一棵有根结点的定向的有序树（树指无回的连通图），它是一棵倒挂的树，树分根、枝、叶。它必须满足两个条件：①有一个结点，没有父结点，②其它结点中有且仅有一个父结点。没有父亲的结点称为根结点，其余的结点称为从属结点。从属结点中有下属的为枝，无下属为叶。从根结点开始按父子联系依次连接的结点序列称为层次路径。如一所高校，它由校、院、系、专业、教师、学生等构成，其结构图就像一棵树，校是树根（称根结点），院、系、师、生等为枝（结点），枝结点向上向下都有联系，向上只能有唯一的联系，向下可有若干联系，向下无任何联系的为叶，如具体某个学生。在层次模型中，必须按照从根开始的某条路径进行访问。 层次模型表达的实体间的联系是一对多关系，当实体具有层次关系时，适宜采用层次型数据库进行管理。一对多关系指一个父属性对应多个子属性，而一个子属性只对应一个父属性。层次模型中一切联系都是向下的。 在树形结构中，表示方法是多样的。如一本书A分为B、C两章，B章又分为D、E、F三节；C章分为G、H两节，E节又分为两小节I、J。 三、网状模型与图结构 用丛结构表示的实体间的联系模型叫网状结构模型。层次模型根结点只有一个，根以外的其它结点只有一个父结点，若打破此限制，则层次模型就形成了网状模型。因此网状模型是在层次模型基础上发展起来的，层次模型是网状模型的特殊形式，网状模型是层次模型的一般形式。 从另一个角度上讲，网状模型是在层次结构的基础发展起来的，它扩充了层次结构对联系的限制，因此可灵活地表示实体间的多种关系。它需满足以下条件： ⑴ 可以有一个以上的结点没有父结点。 ⑵ 至少有一个结点有多于一个的父结点。 ⑶ 结点间可以有多种联系。 第一部分数据结构概论及算法分析 一、选择题 1．数据结构是一门研究计算机中__ __对象及其关系的学科。 （1）数值运算（2）非数值运算（3）集合（4）非集合 2．数据结构的定义为(K，R)，其中K是__ __的集合。 （1）算法（2）数据元素（3）数据操作（4）逻辑结构 3．算法分析的目的是____。 （1）找出数据结构的合理性（2）研究算法中输入和输出的关系 （3）分析算法的效率以求改进（4）分析算法的易懂性和文档性 4. 数据的不可分割的基本单位是_ ___。 A.元素 B.结点 C.数据类型 D.数据项 5．下列算法suanfa2的时间复杂度为____。 int suanfa2(int n) { int t=1； while(t<=n) t=t*2； return t； } (log2n) (2n) (n2) (n) 6.（）是具有相同特性数据元素的集合，是数据的子集。 A 数据符号 B 数据对象 C 数据 D 数据结构 7．与数据元素本身的形式、内容、相对位置、个数无关的是数据的( )。 A. 存储结构 B. 逻辑结构 C. 算法 D. 操作 8．数据结构是研究数据的（）及它们之间的相互联系。 A、理想结构，物理结构b、理想结构，逻辑结构 C、物理结构，逻辑结构d、抽象结构，逻辑结构 9．组成数据的基本单位是（）。 a、数据项 b、数据类型 c、数据元素 d、数据变量 10．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为： （A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构11．算法指的是（） A．计算机程序B．解决问题的计算方法 C．排序算法D．解决问题的有限运算序列 12．下列算法suanfa1中语句"x=x*2；"的执行次数是（）。 void suanfa1(int n) { int i,j,x=1； for(i=1；i<=n；i++) for(j=i；j<=n；j++) x=x*2； printf("%d",x)； } (n-1)/2 (n+1)/2 C.n2 D.?nlog2n? 13. 由____组成的集合是一个数据对象。 A.不同类型的数据项 B.不同类型的数据元素 C.相同类型的数据项 D.相同类型的数据元素 14．在下列选项中，哪个不是一个算法一般应该具有的基本特征_____。 A. 确定性 B. 可行性 C. 无穷性 D. 拥有足够的情报15．在计算机中，算法是指______。 A. 查询方法 B. 加工方法 C. 解题方案准确而完整的描述 D. 排序方法16．算法的时间复杂度是指________。 A. 执行算法程序所需要的时间 B. 算法程序的长度 C. 算法执行过程中所需要的基本运算次数 D. 算法程序中的指令条数17．算法的空间复杂度是指________。 A. 算法程序的长度 B. 算法程序中的指令条数 C. 算法程序所占的存储空间 D. 算法执行过程中所需要的存储空间18．下面叙述正确的是_______。 A. 算法的执行效率与数据的存储结构无关 B. 算法的空间复杂度是指算法程序中指令（或语句）的条数 C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止 D. 以上三种描述都不对 19．数据的存储结构是指______。 第1章 数据结构概论 一、判断题 1 算法可以没有输入语句。 解：对。按照算法定义，它包括输入、输出、确定性、有穷性和有效性这五条。其中，算法允许有零个或多个输入语句，但必须至少有一个输出语句。 2 数据的逻辑结构按照数据元素前驱的个数划分为线性与非线性两类，线性的数据结构指数据元素只有一个前驱，非线性的则有多个前驱。 解：错。正确的表述应为：线性的数据结构是指每个数据元素至多只有一个前驱，至多只有一个后继。 3 数据结构包括数据间的逻辑结构、数据的存储方式和数据的运算三个方面。 解：对。数据结构的研究内容为：数据的逻辑结构、存储方式与数据运算。 二、选择题 1 算法的时间复杂度取决于 。 (A)．问题的规模 (B)．待处理数据的初态 (C)．编码的语言 (D)．占用内存的大小 解：选A 。时间复杂度与空间复杂度均取决于问题规模。 2 算法与程序的主要区别在于程序可以不满足算法的 B 。 (A)．确定性 (B)．有穷性 (C)．可行性 (D)．健壮性 解：选B 。 算法包含有五个特性：（1）输入。（2）输出。（3）确定性。（4）有穷性。（5）有效性 程序可以不满足有穷性，亦即程序允许无限次地运行。例如，在以下程序中，当不输入-1时，程序将无限次地运行。 #include空间数据库报告分析
数据结构习题集
(完整版)数据结构概论
第1章概论答案 数据结构 田鲁怀著
数据结构复习资料复习提纲知识要点归纳
4GIS空间数据库
第一部分数据结构概论及算法分析答案
第1章习题解答 数据结构概论