第2章一维索引组织结构.

第2章数据仓库2.1数据仓库的基本概念1. 数据仓库的数据是面向主题的数据仓库与数据挖掘技术图2-1主题间的重叠关系2. 数据仓库的数据是集成的3. 数据仓库的数据是不可更新的数据仓库与数据挖掘技术4. 数据仓库的数据是随时间不断变化的图2-2数据仓库体系结构2.2数据仓库的体系结构数据仓库与数据挖掘技术图2-3数据仓库数据组织结构2.2.1元数据1. 元数据在数据仓库中的作用2. 元数据的使用3. 元数据的分类4. 元数据的内容2.2.2粒度的概念1. 按时间段综合数据的粒度2. 样本数据库2.2.3分割问题1. 分割的优越性2. 数据分割的标准3. 分割的层次2.2.4数据仓库中的数据组织形式1. 简单堆积结构图2-4简单堆积结构数据组织形式2. 轮转综合结构数据仓库与数据挖掘技术图2-5轮转综合结构数据组织形式3. 简单直接结构图2-6简单直接结构数据组织形式4. 连续结构图2-7连续结构数据组织形式数据仓库与数据挖掘技术2.3数据仓库的数据模型2.3.1概念数据模型图2-8商品、顾客和供应商E-R图2.3.2逻辑数据模型2.3.3物理数据模型2.3.4高层数据模型、中间层数据模型和低层数据模型1. 高层数据模型2. 中间层数据模型3. 低层数据模型数据仓库与数据挖掘技术2.4数据仓库设计步骤图2-9数据仓库设计步骤2.4.1概念模型设计1. 界定系统边界2. 确定主要的主题域3. 实例2.4.2技术准备工作2.4.3逻辑模型设计1. 分析主题域2. 划分粒度层次3. 确定数据分割策略4. 定义关系模式5. 定义记录系统2.4.4物理模型设计1. 确定数据的存储结构数据仓库与数据挖掘技术2. 确定索引策略3. 确定数据存放位置4. 确定存储分配2.4.5数据仓库的生成1. 接口设计2. 数据装入2.4.6数据仓库的使用和维护1. 开发DSS应用图2-10DSS应用开发步骤2. 进一步理解需求，改善系统，维护数据仓库图2-11William H.Inmon数据仓库设计步骤数据仓库与数据挖掘技术2.5利用SQL Server 2005构建数据仓库图2-12使用Visual Studio 2005系统新建项目图2-13新建Analysis Services项目图2-14新建数据源数据仓库与数据挖掘技术图2-15新建数据源向导图2-16选择如何连接数据源图2-17连接管理器图2-18连接管理器连接测试成功窗口图2-19选择已经连接的数据库作为数据源图2-20选择连接数据源的凭证图2-21新建数据源向导完成图2-22右击新建数据源视图图2-23新建数据源视图向导图2-24选择视图的数据源图2-25选择表和视图图2-26完成新建数据源视图向导图2-27新建多维数据集图2-28多维数据集向导图2-29选择生成多维数据集的方法图2-30选择多维数据集的数据源视图图2-31检测事实数据表和维度表图2-32标示事实表和维度表图2-33选择度量值图2-34扫描维度图2-35查看维度结构图2-36完成多维数据集向导图2-37创建完成数据仓库界面习题21. 如何理解数据仓库是面向主题的、集成的、不可更改的和是随时间不断变化的。

第一章：数据结构包含：逻辑结构，数据的存储结构，对数据进行的操作。

数据元素：相对独立的基本单位，即可简单也可复杂，简单的数据元素只有一个数据项，数据项是数据的不可分割的最小单位。

数据对象：性质相同的数据元素的集合。

数据结构：相互存在一种或者多种特定关系的数据元素的集合（集合，线性结构，树结构，图结构）。

顺序存储结构：数据元素按照逻辑顺序依次存放在存储器的一段连续存储单元中。

链式存储结构：存储在存储空间的任意位置上，包含一个数据域和至少一个指针域，要访问，必须从第一个元素开始查找。

数据类型：一组值加一组操作。

第二章：线性表：有限多个性质相同的数据元素构成的一个序列，数据元素的个数就是长度。

线性表的顺序存储结构：用一组地址连续的存储单元能随机存取的结构。

链式存储结构：具有链式存储结构的线性表称为链表，是用一组地址任意的存储单元来存线性表中的数据元素。

每个数据元素存储结构包括数据元素信息域和地址域，存放一个数据元素的存储结构称为结点，每个结点只定义一个指针域，存放的是当前结点的直接后记结点的地址（直接后继结点），线性表的最后一个结点指针域存放空（0，NULL）标志结束。

不支持随机存取，访问必须从第一个结点开始，一次访问。

双向链表：每个结点设置两个方向的指针（直接前驱和直接后继）。

第三章：栈：堆栈的简称，限定在表尾进行插入和删除的线性表。

特点是后进先出。

当栈定指针指向栈底时，为空栈。

队列：限定只能在一端进行插入和在另一端进行删除的线性表，进行插入的是队尾，删除的是队头。

特点是先进先出。

队列的链式结构：用一个链表依次存放从队头到队尾的所有的数据元素。

存放队头地址（队头指针）队尾地址（队尾指针），空链队列：有头结点，空队列条件是头结点存放0，无头结点为队头指针指向空。

队列的顺序存储结构：用一组地址连续的存储空间依次存放从队头到队尾的所有数据元素，再用队头指针和队尾指针记录队头和队尾的位置。

队头指针指向队头元素前一个数组元素的位置，队尾始终指向队尾，当队尾和队头指向同一位置，空队列。

第2章 一维势场中的粒子教材第2章P27～49§ 2.1一维能量本征态的一般性质§ 2.2方势§ 2.3 一维谐振子§ 2.1一维能量本征态的一般性质质量为m 的粒子在一维势)(x V 中运动，能量本征方程为)()(ˆx E x Hψ=ψ )(2ˆ222x V xm H +-=d d 或写成)()()(2222x E x x V x m ψ=ψ+-⎪⎪⎪⎭⎫ ⎝⎛d d注意)(x V 为实。

问题一般分为两类：给定)(x V 求E 和ψ，给定)(x V 和E 求ψ。

下面讨论能量本征方程解的一般性质定理1 . 设)(x ψ是能量本征方程的一个解，对应的能量本征值为E ，则)(*x ψ也是方程的一个解，对应的能量也是E 。

证明：设)(x ψ是能量本征方程的一个解，方程两边取复共轭，因E 和)(x V 为实，则)()()(2**222x E x x V x m ψ=ψ+-⎪⎪⎪⎭⎫ ⎝⎛d d即)(*x ψ也是方程的一个解，对应的能量也是E 。

若能量的某一本征值E 无简并，即只有一个独立的本征波函数)(x ψ，则)(x ψ可取为实函数。

这是因为：由定理1，)(x ψ和)(*x ψ均为与E 对应的本征波函数。

因E 无简并，则)()(*x C x ψ=ψ其中C 为常数。

上式取复共轭)()()(2**x C x C x ψ=ψ=ψ 12=C αi C e =，α为实若取0=α，则)()(*x x ψ=ψ，即)(x ψ可取为实函数。

对于能级有简并情况，有定理2 定理2 . 对应于能量的某个本征值E ，总可以找到能量本征方程的一组实解，属于E 的任何解均可表示为这一组实解的线性叠加。

证明：设)(x ψ是对应能量E 的一个解，若为实解，则可归入实解的集合中去。

若为复解，按定理1， )(*x ψ也是方程的一个解，同属于能量E 。

由线性方程解的叠加定理，实函数)()()(*x x x ψ+ψ=ϕ)]()([)(*x x i x ψ-ψ-=χ也是方程的解，同属于能量E ，并彼此独立。

第1章绪论1.1 数据结构的基本概念数据元是数据的基本单位，一个数据元素可由若干个数据项完成，数据项是构成数据元素的不可分割的最小单位。

例如，学生记录就是一个数据元素，它由学号、姓名、性别等数据项组成。

数据对象是具有相同性质的数据元素的集合，是数据的一个子集。

数据类型是一个值的集合和定义在此集合上一组操作的总称。

•原子类型：其值不可再分的数据类型•结构类型：其值可以再分解为若干成分（分量）的数据类型•抽象数据类型：抽象数据组织和与之相关的操作抽象数据类型（ADT）是指一个数学模型以及定义在该模型上的一组操作。

抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。

通常用（数据对象、数据关系、基本操作集）这样的三元组来表示。

#关键词：数据，数据元素，数据对象，数据类型，数据结构数据结构的三要素：1.逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据，独立于计算机。

分为线性结构和非线性结构，线性表、栈、队列属于线性结构，树、图、集合属于非线性结构。

2.存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构，包括数据元素的表示和关系的表示，依赖于计算机语言，分为顺序存储（随机存取）、链式存储（无碎片）、索引存储（检索速度快）、散列存储（检索、增加、删除快）。

3.数据的运算：包括运算的定义和实现。

运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。

1.2 算法和算法评价算法是对特定问题求解步骤的一种描述，有五个特性：有穷性、确定性、可行性、输入、输出。

一个算法有零个或多个的输入，有一个或多个的输出。

时间复杂度是指该语句在算法中被重复执行的次数，不仅依赖于问题的规模n，也取决于待输入数据的性质。

一般指最坏情况下的时间复杂度。

空间复杂度定义为该算法所耗费的存储空间。

算法原地工作是指算法所需辅助空间是常量，即O(1)。

第2章线性表2.1 线性表的定义和基本操作线性表是具有相同数据类型的n个数据元素的有限序列。

第一章数据结构及算法经过对部分考生的调查以及对近年真题的总结分析，笔试部分常常考查的是算法困难度, 数据结构的概念, 栈, 二叉树的遍历, 二分法查找，读者应对此部分进行重点学习。

具体重点学习知识点：1．算法的概念, 算法时间困难度及空间困难度的概念2．数据结构的定义, 数据逻辑结构及物理结构的定义3．栈的定义及其运算, 线性链表的存储方式4．树及二叉树的概念, 二叉树的基本性质, 完全二叉树的概念, 二叉树的遍历5．二分查找法6．冒泡排序法1.1算法考点1 算法的基本概念考试链接：考点1在笔试考试中考核的几率为30%，主要是以填空题的形式出现，分值为2分，此考点为识记内容，读者还应当了解算法中对数据的基本运算。

计算机解题的过程事实上是在实施某种算法，这种算法称为计算机算法。

1．算法的基本特征：可行性, 确定性, 有穷性, 拥有足够的情报。

2．算法的基本要素：（1）算法中对数据的运算和操作一个算法由两种基本要素组成：一是对数据对象的运算和操作；二是算法的限制结构。

在一般的计算机系统中，基本的运算和操作有以下4类：算术运算, 逻辑运算, 关系运算和数据传输。

（2）算法的限制结构：算法中各操作之间的执行依次称为算法的限制结构。

描述算法的工具通常有传统流程图, N-S结构化流程图, 算法描述语言等。

一个算法一般都可以用依次, 选择, 循环3种基本限制结构组合而成。

考点2 算法困难度考试链接：考点2在笔试考试中，是一个常常考查的内容，在笔试考试中出现的几率为70%，主要是以选择的形式出现，分值为2分，此考点为重点识记内容，读者还应当识记算法时间困难度及空间困难度的概念。

1.算法的时间困难度算法的时间困难度是指执行算法所须要的计算工作量。

同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行，效率均不同。

这表明运用肯定的时间单位衡量算法的效率是不合适的。

撇开这些及计算机硬件, 软件有关的因素，可以认为一个特定算法"运行工作量"的大小，只依靠于问题的规模（通常用整数n表示），它是问题规模的函数。