数据结构期末复习总结

第1章绪论

1.数据(Data) ：是描述客观事物的数字、字符以及所有能输入到计算机中并能被计算机接受的各种符号集合的统称。

包括数值数据和非数值数据（字符串、图形、图像、音频、视频）。

2.数据元素(Data Element) ：表示一个事物的一组数据称为一个数据元素（结点顶点、记录）；数据元素是数据的基本单位。

3.数据项（Data Item）：是数据元素中有独立含义的、不可分割的最小标识单位（字段、域、属性）。一个数据元素可由若干个数据项组成。

4.数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。如字符集合C ={A,B,C,…} 。

数据(Data) ：是描述客观事物的数字、字符以及所有能输入到计算机中并能被计算机接受的各种符号集合的统称。

包括数值数据和非数值数据（字符串、图形、图像、音频、视频）。

数据元素(Data Element) ：表示一个事物的一组数据称为一个数据元素（结点、顶点、记录）；数据元素是数据的基本单位。

数据项（Data Item）：是数据元素中有独立含义的、不可分割的最小标识单位（字段、域、属性）。一个数据元素可由若干个数据项组成。

数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。如字符集合C ={A,B,C,…} 。

●数据的逻辑结构指数据元素之间的逻辑关系，用一个数据元素的集合和定义在此集

合上的若干关系来表示。

●四种逻辑结构：集合、线性结构、树型结构、图状结构。

●数据结构的形式定义是一个二元组：

Data-Structure=(D，S)

其中：D是数据元素的有限集，S是D上关系的有限集。

例1：设数据逻辑结构B=（K，R）

K={k1, k2, …, k9}

R={ ，，，，，，，，，，

有时候关系图不唯一（一般是无向图）

●数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的表示。

●两种不同的存储结构：顺序存储结构和链式存储结构。

●顺序结构：数据元素存放的地址是连续的；

●链式结构：数据元素存放的地址是否连续没有要求，用该指针来表示数据元

素之间的逻辑结构(关系)。

●顺序存储—使用一组连续的内存单元依次存放数据元素，元素在内存中的物理存储

次序体现它们的逻辑次序。通常使用程序设计语言中的数组来实现。

?链式存储—使用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻。数据元素间的逻辑关系通过结点间的链接关系来体现。通常使用指针记载直接前驱元素或直接后继元素的存储地址。

数据操作指对一种数据结构中的数据元素进行各种运算或处理。每种数据结构都有一组数据操作。

?初始化。

?判断是否空状态。

?统计元素的个数。

?遍历：按某种次序访问所有元素，每个元素只被访问一次。

?取值：获取指定元素值。

?置值：设置指定元素值。

?插入：增加指定元素。

?删除：移去指定元素。

?查找：在数据结构中寻找满足给定条件的数据元素。

?排序：将数据元素

?...

数据操作定义在数据的逻辑结构上；

数据操作的实现依赖于数据的存储结构。

?数据结构三方面的关系：

数据的逻辑结构、数据的存储结构及操作这三方面是一个整体

例6：线性表是一种逻辑结构，若采用顺序存储，可称其为顺序表；若采用链式存储，则可称其为链表；若采用散列存储，则可称为散列表。

?在给定了数据的逻辑结构和存储结构之后，按定义的操作集合及其操作的性质不同，也可能导致完全不同的数据结构。

?类型（type）是具有相同逻辑意义的一组值的集合。

?数据类型是指一个类型和定义在这个类型上的操作集合。

数据类型定义了数据的性质、取值范围以及对数据所能进行的各种操作

例7：Java中整型类型int的值集是

[-231,…,-2,-1,0,1,2,…,231-1]

这个值集上的操作集合[+,-,*,/,%,=,==,!=,<,<=,>,>=]

●抽象数据类型(Abstract Data Type ，简称ADT)：是指一个数学模型以及定

义在该模型上的一组操作。

●ADT的定义仅是一组逻辑特性描述，与其在计算机内的表示和实现无关。

因此，不论ADT的内部结构如何变化，只要其数学特性不变，都不影响其外部使用。

●ADT的形式化定义是三元组：ADT=(D，S，P)

●其中：D是数据对象，S是D上的关系集，P是对D的基本操作集。

ADT的一般定义形式是：

ADT <抽象数据类型名>{

数据对象：<数据对象的定义>

数据关系：<数据关系的定义>

基本操作：<基本操作的定义>

} ADT <抽象数据类型名>

例8：复数抽象数据类型描述如下：

ADT Complex{

double real,imag;

Complex(double real, double imag);

Complex add(Complex c);

Complex sub(Complex c);

}

1、算法定义：一个算法（algorithm）是一个有穷规则的集合，其规则确定一个解决某一特定类型问题的操作序列（D.Knuth）。

算法的规则必须满足以下5个特性：

①有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。

②确定性：算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和

一个出口。

③可行性：一个算法是能行的。即算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。

④输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。

⑤输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。

2、算法设计目标

–正确性

–健壮性

–高时间效率

–高空间效率

–可读性

3、算法描述

●自然语言描述

●伪码描述

●传统流程图描述

●程序设计语言描述（本课程选Java）

4、算法与数据结构

?算法建立在数据结构之上，对数据的操作需用算法来描述。

?算法设计依赖数据的逻辑结构，算法实现依赖数据的存储结构。

?实现一种抽象数据类型，需要选择合适的存储结构。

求解同一问题可能有许多不同的算法，如何去评价这些算法的优劣？主要考虑如下三点：

A.执行算法所耗费的时间；

B.执行算法所耗费的存储空间，其中主要考虑辅助存储空间；

C.算法应易于理解，易于编码，易于调试等等。

1、时间代价分析

算法的时间效率指算法的执行时间随问题规模的增长而增长的趋势，通常采用时间复杂度来度量算法的时间效率,用大O表示法来记:

T(n)=O(f(n))

例1 void fun(){

++x;

s=0 ;

}

将x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1) 。

如果将s=0也看成是基本操作，则语句频度为２，其时间复杂度仍为Ｏ(1)，即常量阶。

一个简单语句的时间复杂度为Ｏ(1)。

例2 for(i=1; i<=n; ++i){

++x;

s+=x ;

}

语句频度为：2n，其时间复杂度为：Ｏ(n) ，即为线性阶。

一个循环的时间复杂度为Ｏ(n)。

例3 for(i=1; i<=n; ++i){

for(j=1; j<=n; ++j){

++ x;

s += x;

}

}

语句频度为：2n2 ，其时间复杂度为：O(n2) ，即为平方阶。

定理：若A(n)=a m n m + a m-1 n m-1+…+a1n+a0是一个m次多项式，则A(n)=O(n m)

例4 两个n阶方阵的乘法

for(i=1，i<=n; ++i){

for(j=1; j<=n; ++j){

c[i][j]=0 ;

for(k=1; k<=n; ++k){

c[i][j]+=a[i][k]*b[k][j] ;

}

}

}

由于是一个三重循环，每个循环从1到n，则总次数为：n×n×n=n3时间复杂度为T(n)=Ｏ(n3)

例5 for(i=2;i<=n;++i){

for(j=2;j<=i-1;++j){

++x;

a[i,j]=x;

}

}

语句频度为：1+2+3+…+n-2

=(1+n-2) ×(n-2)/2

=(n-1)(n-2)/2 =n2-3n+2

∴时间复杂度为O(n2)，即此算法的时间复杂度为平方阶。

例6：int n=8, count=0;

for (int i=1; i<=n; i*=2)

for (int j=1; j<=n; j++)

count++;

循环次数为。时间复杂度为O(nlog2n)。

例7：int n=8, count=0;

for (int i=1; i<=n; i*=2)

for (int j=1; j<=i; j++)

count++;

总的循环次数为。时间复杂度为O(n)。

以下六种计算算法时间的多项式是最常用的。其关系为：

O(1)

指数时间的关系为：

O(2n)

当n取得很大时，指数时间算法运算时间远远超过多项式时间算法。

2、空间代价分析

算法的空间效率（空间复杂度）指算法在执行时为解决问题所需要的额外存储空间，不包括输入数据和程序指令所占用的存储空间,用大O表示法来记:

S(n)=o(f(n))

该存储空间一般包括三个方面：

–指令常数变量所占用的存储空间;

–输入数据所占用的存储空间;

–辅助(存储)空间。

?一般地，算法的空间复杂度指的是辅助空间。

?变量i：空间复杂度O(1)

?一维数组a[n]：空间复杂度O(n)

?二维数组a[n][m]：空间复杂度O(n*m)

第2章线性表

线性结构是最常用、最简单的一种数据结构。而线性表是一种典型的线性结构。其基本特点是线性表中的数据元素是有序且是有限的。在这种结构中：

i.①存在一个唯一的被称为“第一个”的数据元素；

ii.②存在一个唯一的被称为“最后一个”的数据元素；

iii.③除第一个元素外，每个元素均有唯一一个直接前驱；

iv.④除最后一个元素外，每个元素均有唯一一个直接后继。

线性表(Linear List) ：是由n(n≧0)个数据元素(结点)a0，a1，…a n-1组成的有限序列。该序列中的所有结点具有相同的数据类型。其中数据元素的个数n称为线性表的长度。

b)当n=0时，称为空表。

c)当n>0时，将非空的线性表记作：(a0，a1，…a n-1)

●线性表的顺序表示指的是一组地址连续的存储单元依次存储线性表的数据元素。

●用顺序存储实现的线性表称之为顺序表。

●线性表的逻辑顺序与物理顺序一致。

?顺序表是一种随机存取结构。通常采用数组存储数据元素。

?设线性表的每个元素需占用c个存储单元。

public boolean isEmpty(){ //时间复杂度O(1)

return this.len == 0;

}

public int length(){ //时间复杂度O(1)

return this.len;

}

public T get(int i){ //时间复杂度O(1)

if(i>=0 && i < this.len)

return (T)this.element[i];

return null;

}

public void set (int i, T x){ //时间复杂度O(1)

if (x==null)return;

if (i>=0 && i

this.element[i] = x;

else throw newIndexOutOfBoundsException(i+“”)；

}

public String toString(){ //时间复杂度O(n)

String st r = “(”;

if(this.len>0)

str += this.element[0].toString();

for(int i = 1; i < this.len; i ++)

str +=“，”+ this.element[i].toString();

return str + “)”;

}

}

?两个线性表相等是指，它们长度相同并且各对应元素相等。

?链式存储：用一组任意的存储单元存储线性表中的数据元素。存储链表中结点的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。

?链表中结点的逻辑顺序和物理顺序不一定相同。

?链表中的结点结构：数据域和地址域

n个结点构成的链表表示为(a0, a1, ..., a n-1)

?链表中每个结点只含一个地址域，又称为线性链表或单链表。

?每个结点有两个地址域的线性链表称为双链表。

?单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。

头结点的作用是，使所有链表（包括空表）的头指针非空，则对单链表的插入、删除操作不需要区分操作位置。

头结点中不存储数据。

头插入和头删除操作不会改变head指针

总结----顺序表和链表的比较

（1）直接访问元素的性能

?顺序表能够直接访问数据元素，即只要给出顺序表底层数组element的下标就可以

访问数组中的任何一个数据元素。（随机存取）

?而链表中不能随机地直接访问大多数元素，只能从链表的第一个结点开始，沿着链

的方向，依次查找后续结点，直至到达所需访问的结点。（顺序存取）

（2）存储空间的利用

?由于需要估计顺序表底层数组element的大小（顺序表的容量），因此顺序表存在存

储空间的浪费问题。

?顺序表在进行插入操作时，要判断顺序表是否为满。如果满，则需要扩充容量。

?而链表每插入一个结点，就向系统申请一个存储单元，只要系统资源足够，系统就

会为该结点分配存储空间。

（3）存储密度

?存储密度（Storage Density）是指结点数据本身所占的存储量和整个结点结构所占的

存储量之比，即：

（结点数据本身所占的存储量）

（整个结点所占的存储总量）

?顺序表的全部空间都用来存放数据元素，因此存储密度=1；

?而链表中每个结点都要包含其后继结点或者前驱结点的链，因此存储密度< 1。（4）插入和删除操作

?顺序表的插入、删除操作很不方便，插入和删除操作有时需要移动大量元素；

?而链表的插入、删除操作很容易进行，只要简单地改动相关结点的链即可，不需要

移动数据元素。

第4章栈和队列

?栈的定义：

–栈(Stack)是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行。通常称允许插入、删除操作的这一端为栈顶(Top)，不允许操作的一端称

为栈底(Bottom)。当表中没有元素时称为空栈。

–假设栈S=(a0，a1，a2，a3，…a n-1)，则a0称为栈底元素，a n-1为栈顶元素，标识栈顶位置的指针称为栈顶指针。栈中元素按a0，a1，a2，a3，… a n-1的次

序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先

出的原则进行的。因此，栈称为后进先出表（LIFO）。

?栈的操作：

–习惯上将每次删除（也称为退栈）操作又称为出栈或弹出（POP）操作。删除的元素总是当前栈中“最新”的元素（栈顶元素）。

–每次插入（称为进栈）操作称为入栈或压入（PUSH）操作，入栈的元素总是当前栈中“最新”的元素。

–在空栈中最先插入的元素总被放在栈的底部，只有所有元素被弹出之后它才能被删除。

?栈的数据元素：

–栈的数据元素和线性表的数据元素完全相同，即栈的数据元素是n（n>=0）个相同类型的数据元素a0，a1，。。。a n-1组成的有限序列，记为：{a0,a1,…a n-1}。

–其中，n为数据元素的个数，称为栈的长度。n=0时，为空栈。

?栈的溢出：

–当栈满时进栈运算称为“上溢”。

–当栈空时退栈运算称为“下溢”。

–栈上溢是一种出错状态，应该设法避免之；而下溢则可能是正常现象，通常下溢用来作为程序控制转移的条件。

?由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。

?栈的顺序存储结构简称为顺序栈（Sequential Stack），它是运算受限的线性表。因此，可用数组来实现顺序栈。

?因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，一般需用一个整型变量top。

栈的顺序存储结构及操作实现

public class SeqStack implements Stack //顺序栈类，实现栈接口

{

Object element[]; //存储栈数据元素的数组

int top; //栈顶元素下标

}

?注意：element数组存储栈的数据元素；top表示当前栈顶元素的下标。

?经典实现：

（1）栈的初始化

public SeqStack(int size) //构造容量为size的空栈

{

this.element = new Object[Math.abs(size)];

this.top= -1;

}

public SeqStack() //构造默认容量的空栈

{

this(64);

}

（2）判读栈是否为空

public boolean isEmpty() //判断栈是否空，若空返回true

{

return this.top==-1;

}

?判读栈是否为满？？？

本实现采用与顺序表同样的处理：当容量不够时，则将数组容量扩充一倍。

（3）入栈

public void push(T x) { //元素x入栈，空对象不能入栈

if (x==null) return; //空对象不能入栈

if (this.top==element.length-1) {//若栈满，则扩充栈容量

Object [] temp = this.element;

//重新申请一个容量更大的数组

this.element = new Object[temp.length*2];

for (int i=0; i

this.element[i] = temp[i];

}

this.top++;

this.element[this.top] = x;

}

（4）出栈

栈不空时，取走top位置处栈顶元素，top减1，下一位置数据元素作为新的栈顶元素public T pop() //出栈，返回栈顶元素，若栈空返回null

{

return this.top== -1 ? null : (T) this.element[this.top --];

}

（5）获得栈顶数据元素

栈不空时，获取top位置处栈顶元素，此时数据元素未出栈，top值不变

public T get() //取栈顶元素，未出栈，若栈空返回null

{

return this.top==-1 ? null : (T)this.element[this.top];

}

//顺序栈类，最终类，实现栈接口，T表示元素类型

public final class SeqStack implements Stack

{

private SeqList list; //顺序表

public SeqStack(int capacity) //构造栈

public SeqStack() //构造空栈

public boolean isEmpty() //判空

public void push(T x) //x入栈

public T peek() //返回栈顶（未出栈）

public T pop() //出栈，返回栈顶元素

}

?栈的链式存储，称为链栈。

?链式栈的基本运算同顺序栈，定义也同线性表的链表定义，它是对链表实现的简单化（因为它只是对链表的头部操作）。

?可用单链表实现链栈。

?它的元素只能在表头进行插入和删除。在链式存储结构中，不需要给出表头结点（head），因为其中惟一的已知条件是栈顶指针top，它是指向链式栈的第一个结点（相当于头指针）。

?栈的各种运算比链式存储的普通线性表运算实现时要方便得多，主要原因是栈的各种运算只能在栈的一端操作，栈是特殊的线性表，我们只要考虑对线性表的一端操作的情况，并且只能在一端插入删除（栈顶）

?而线性表除此之外（不限定一端插入删除），还需要考虑另外一端结点以及中间的结点的插入、删除、查询等操作，理解时，我们可以把栈的入出栈运算当作线性表的一端进行插入删除的特例即可。

链式栈实现（经典实现）

栈的链式存储结构及操作实现

public class LinkedStack implements Stack

{

private Node top;

}

（1）栈的初始化

public LinkedStack() //构造空栈

{

this.top=null;

}

（2）判读栈是否为空

public boolean isEmpty()

//判断栈是否空，若空返回true

{

return this.top==null;

}

（3）入栈

public void push(T x)

//元素x入栈，空对象不能入栈

{

if (x!=null)

this.top = new Node(x, this.top);

//头插入，x结点作为新的栈顶结点

}

（4）出栈

public T pop() //出栈，返回栈顶元素，若栈空返回null

{

if (this.top==null)

return null;

T temp = this.top.data; //取栈顶结点元素

this.top = this.top.next; //删除栈顶结点

return temp;

}

（5）获得栈顶元素

public T get()

//取栈顶元素，未出栈，若栈空返回null

{

return this.top==null ? null : this.top.data;

}

链式栈实现（基于单链表）

//链式栈类，最终类，实现栈接口，T表示数据元素的数据类型

public final class LinkedStack implements Stack

{

private SinglyList list;

//使用单链表（第2章）存储栈元素

public LinkedStack() //构造空栈{

this.list = new SinglyList(); //构造空单链表}

public boolean isEmpty() //判断栈是否空，若空返回true

{

return this.list.isEmpty();

}

public void push(T x) //元素x入栈，空对象不能入栈

{

this.list.insert(0, x); //单链表头插入元素x }

public T peek() //返回栈顶元素（未出栈）；若栈空返回null

{

return this.list.get(0);

}

public T pop() //出栈，返回栈顶元素；若栈空返回null

{

return this.list.remove(0);

//若栈不空，单链表头删除，返回删除元素

}

public String toString()

//返回栈所有元素的描述字符串，形式为“(,)”

{

return this.getClass().getName()+" "+this.list.toString();

}

}

顺序栈和链式栈的比较

?实现链式栈和顺序栈的操作，都是需要常数时间，即时间复杂度为O（1）。主要两者从空间和时间两个方面考虑：

–初始时，顺序栈必须说明一个固定的长度，当栈不够满时，造成一些空间的浪费，而链式栈的长度可变则是长度不需要预先设定，相对比较节省空间，

但是在每个结点中，设置了一个指针域，从而产生了结构开销。

–当需要多个栈共享时，顺序存储中可以充分利用顺序栈的单向延伸性。可以使用一个数组存储两个栈，使每个栈从各自的端点向中间延伸，这样浪费的

空间就会减少。但这种情况只有当两个栈的空间需求有相反的需求时，这种

方法才有效。也就是说，最好一个栈增长，一个栈缩短。反之，如果两个栈

同时增长，则可能比较容易造成栈的溢出。如果多个顺序栈共享空间，则可

能需要大量的数据移动，造成时间的开销增大。而链式栈由于存储的不连续

性，一般不存在栈满的问题，所以一般不需要栈的共享。

?【例3】使用栈计算算术表达式值

算术表达式有三种表示方法：

⑴<操作数> <操作符> <操作数>，如A+B，称为中缀(infix)表示；

⑵<操作符> <操作数> <操作数>，如+AB称为前缀(prefix)表示；

⑶<操作数> <操作数> <操作符>，如AB+，称为后缀(postfix)表示。

中缀表达式：1+2*(3-4)+5 其对应的后缀表达式为1234-*+5+

习题中缀表达式如下，写出后缀表达式。

A+B*(C-D*(E+F)/G+H)-(I+J)*K

【习题解答】ABCDEF+*G/-H+*+IJ+K*

?队列的定义：

–队列(Queue)也是一种运算受限的特殊线性表。其插入和删除操作分别在线性表的两端进行（只允许在表的一端进行插入，而在另一端进行删除）。允

许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。

–当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,…a n之后，a1是队头元素，a n是队尾元素。显然退出队列的次序也只能是a1,a2,…a n，

也就是说队列的修改是依先进先出的原则进行的，例如：排队购物。

–先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。

队列的操作：

–一般情况下，入队(enqueue)操作又称为队列的插入。

–出队(dequeue)操作又称为队列的删除。

队列的数据元素：

–队列的数据元素和线性表的数据元素完全相同，即队列的数据元素是n（n>=0）个相同类型的数据元素a0，a1，。。。a n-1组成的有限序列，记为：{a0,a1,…a n-1}。

–其中，n为数据元素的个数，称为队列的长度。n=0时，为空队列。

–队列的溢出：

–队列在顺序存储时，经常出现“假溢出”现象，解决“假溢出”现象的方法有很多种，但通常采用循环队列方式存储。

–使用顺序表，出队效率低。因此不使用顺序表作为队列的成员变量。

顺序循环队列：

?现在解决“假溢出”比较好的解决方案是使用循环向量，存储在循环向量中的队列称为循环队列（Circular Quene）。

?将顺序队列设计成在逻辑上首尾相接的循环结构，则可循环使用顺序队列的连续存储单元。

?循环队列的操作：

?假设数组的空间是m，只要在入、出队列时，将队首和队尾的指针对m做求模运算即可实现队首和队为指针的循环，即队首和队尾指针的取值范围是

0 到m-1 之间。

●队空：front = rear

●队满：front = (rear + 1) % maxSize或另外设一个标志以区别队空、队满

●入队: rear = (rear + 1) % maxSize

●出队: front = (front + 1) % maxSize;

●求队长: (rear - front + maxSize)%maxSize

链式队列的基本概念：

–定义链队列的存储结构基本和线性表的定义相同，它是对链表实现的简单化。

–队列的各种运算比链式存储的普通线性表运算实现时要方便得多，主要原因是队列的各种运算只能在队列的两端操作。

?队列是特殊的线性表，我们只要考虑对线性表的两端操作的情况，

并且只能一端插入（队首），另一端删除（队尾）。

?而线性表除此之外（不限定一端插入、一端删除），还需要考虑中间

的结点的插入、删除、查询等操作。

?理解时，我们可以把队列的入、出队运算当作线性表两端进行插入

删除的特例即可。

?于是，一个链队列由头指针和尾指针唯一确定。

?使用单链表，入队效率低。

?单链表设计，增加尾指针。

?以不带头结点的单链表实现链式队列。

?队列的应用

–（一）合并两个队列

?假设有两个队列，要求将两个队列合并到一起，合并时交替使用两

个队列中的元素，并把剩余的队列中的元素添加在最后，将产生的

新队列返回。

–（二）模拟客户服务系统

–（三）主机与外部设备之间速度不匹配的问题

?以主机和打印机为例来说明，主机输出数据给打印机打印，主机输

出数据的速度比打印机打印的速度要快得多，若直接把输出的数据

送给打印机打印，由于速度不匹配，显然是不行的。所以解决的方

法是设置一个打印数据缓冲区，主机把要打印输出的数据依此写如

到这个缓冲区中，写满后就暂停输出，继而去做其它的事情，打印

机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印完

后再向主机发出请求，主机接到请求后再向缓冲区写入打印数据，

这样利用队列既保证了打印数据的正确，又使主机提高了效率。

第5章数组和广义表

?数组是数据结构的基本结构形式，它是一种顺序式的结构，数组是存储同一类型数据的数据结构。

?数组是顺序存储的随机存取结构，数组是其他数据结构实现顺序存储的基础。

?使用数组时需要定义数组的大小和存储数据的数据类型。

?数组分为一维数组和多维数组。数组的维数是由数组下标的个数确定的：

? 一个下标称为一维数组 ? 一个下标以上的数组称为多维数组 ? 从这个意义上讲，确定了对于数组的一个下标总有一个相应的数值与之对应的关系；或者说数组是有限个同类型数据元素组成的序列 ?

数组是二元组<下标，值>的一个集合。 ?

一维数组具有线性表的结构，但操作简单，一般不进行插入和删除操作，只定义给定下标读取元素和修改元素的操作。 ?

声明的格式一般是： <数据类型> <变量名称> [ ]= new <数据类型> [<数组大小>]； 如：int element[] = new int[5];

一维数组的存储 一维数组的数据存储按照顺序存储，逻辑地址和物理地址都是连续的。 如果已知第一个数据元素的地址loc(a 0)，则第i 个元素的地址loc(a i )为： Loc(a i )= Loc(a 0)＋i ×c

? 数组分配内存空间的方式有2种：

– 静态数组：声明时给出数组元素个数。当程序开始运行时，数组即获得系统

分配的一块地址连续的内存空间。静态数组所占用的内存空间由系统自动管

理。

int [3] = {1,2,3};

– 动态数组：声明时不指定数组长度。当程序运行中需要使用数组时，向系统

申请数组的存储单元空间，并给出数组长度。当数组使用完之后，需要向系

统归还所占用的内存空间。

? 数组容量不够时，不能就地扩容。前面的做法是，申请一个更大容量的数组并进行

数组元素复制。

? 在Java 中，数组元素既可以简单数据类型，也可以是引用类型。而且Java 中的数组

都是动态数组。

? 多维数组（Multi-Array ）

? 多维数组是指下标的个数有两个以上，我们比较常用的是二维数组（因为三

维以上的数组存储可以简化为二维数组的存储）。

? 多维数组是线性表的扩展。

? 理解：二维数组是“元素为一维数组”的一维数组。

? 二维数组的声明同一维数组。格式为：

<数据类型><数组名称>[][]=new<数据类型>[size1] [size2];

如：int element[][] = new int[4][5];

◆ 例如，设A 是一个有m 行n 列的二维数组，则A 可以表示为：

◆

在此，可以将二维数组A 看成是由m 个行向量[X 0，X 1， …，X m-1]T 组成，其中，X i =( a i0,

a i1, ….,a in-1)， 0≤i≤m -1；也可以将二维数组A 看成是由n 个列向量[y 0, y 1, ……,y n-1]

组成，其中 y i =(a 0i , a 1i , …..,a m-1i )， 0≤i≤n -1。 a 0,j

a 0,n -1a 1,j

a 1,n -1a i ,j

a i ,n -1a m -1,j a m -1,n -1

j

n -1

列前驱列后继

? 二维数组的遍历

? 行优先顺序（行主序）：存储时先按行从小到大的顺序存储，在每一

行中按列号从小到大存储。

? 列优先顺序（列主序）：存储时先按列从小到大的顺序存储，在每一

列中按行号从小到大存储。

? 二维数组的顺序存储结构

? 假设二维数组是m*n 的二维数组（共有m 行，每行有n 列）。第一个数据元

素的地址是loc(a 00)，

? 行主序

? 列主序

? O (1)，随机存取结构

例：

数组A[8][6][9]按行存放，设第一个元素的首地址是54，每个元素的长度为5，求元

素A[2][4][5]的存储地址。

Loc(2,4,5)=54 + 5 *（6*2*9+4*9+5）= 799

? 但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下我们

可以对这类矩阵进行压缩存储，即为多个相同的非零元素只分配一个存储空间；对

零元素不分配空间。

? 三角矩阵的压缩存储：

以主对角线划分，三角矩阵有下三角和上三角两种。如图所示。在大多数情况下，三角矩阵常数为零。

? 1.下三角矩阵

? 重复元素c 可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵

可压缩存储到数组element[0..n(n+1)/2]中，其中c 存放在数组的最后一个元素中。

? （1）线性压缩存储三角矩阵

? 2.上三角矩阵

? 和下三角矩阵的存储类似，共需 n(n+1)/2+1个存贮单元，假设仍按行优先顺序存

放，这时s[k]与a[i][j]的对应关系为：

对称矩阵

? 如果用一维数组存储一个对称矩阵，只要将对称矩阵存储在一个最大下标为

c j n i a Loc a Loc

ij ?+?+=)()()(00c i m j a Loc a Loc ij ?+?+=)()()(00????????????????=----------?1,11,22,21,12,1111,02,00100000000n n n n n n n n n n n n a a a a a a a a a a A n j i j i n i a i j i n n n a a ij <≤≤+--??+=-++-++-++=02)12()(Loc )1(...)1()(Loc )(Loc 0000

n(n+1)/2的一维数组S 中即可。

此时按照行优先顺序存储，数据元素aij 与数组S 的下标k 的对应关系为

? 稀疏矩阵（Sparse Matrix ）

– 对稀疏矩阵很难下一个确切的定义，它只是一个凭人们的直觉来理解的概念。

一般认为，一个较大的矩阵中，零元素的个数相对于整个矩阵元素的总个数

所占比例较大时，该矩阵就是一个稀疏矩阵。

? 稀疏矩阵

稀疏矩阵的压缩存储采用三元组的方法实现。其存储规则：每一个非零元素占有一行，每行中包含非零元素所在的行号、列号、非零元素的数值。

书（120页）

? 稀疏矩阵

– 如果每个非零元素按照此种方法存储，虽然能够完整地描述非零元素，但如

果矩阵中有整行（或整列）中没有非零元素，此时可能不能够还原成原来的

矩阵

– 所以为了完整地描述稀疏矩阵，在以上描述的情况下，如果增加一行的内容，

该行包括矩阵的总的行数、矩阵的总的列数，矩阵中非零元素的个数，就可

以还原为原来的矩阵描述了。

//三元组顺序表类

public class SeqMatrix

{

int rows, columns; //行数、列数

SortedSeqList list; //排序顺序表

}

public int get(int i, int j){ // 返回第i 行第j 列的元素

if (i<0 || i>= rows || j<0 || j>= columns)

throw new IndexOutOfBoundsException(“outofBound”);

Triple item = new Triple(i,j,0);

int k =0;

Triple elem = this.list.get(k);

while(k=0){

if(https://www.doczj.com/doc/b91132882.html,pareTo(elem)==0)

????????????????=----------------?1,12,11,10,11,22,21,20,21,12,11,10,11,02,01,00,0...........................n n n n n n n n n n n n n n n n n n a a a a a a a a a a a a a a a a A ?????<<≤++?+<≤≤++?+=n j i i j j a n i j j i i a a j i 02)1()(Loc 02)1()(Loc )(Loc 0,00,0,

结构化学基础知识点总结

结构化学基础 第一章量子力学基础： 经典物理学是由Newton（牛顿）的力学，Maxwell（麦克斯韦）的电磁场理论，Gibbs（吉布斯）的热力学和Boltzmann（玻耳兹曼）的统计物理学等组成，而经典物理学却无法解释黑体辐射，光电效应，电子波性等微观的现象。 黑体：是一种可以全部吸收照射到它上面的各种波长辐射的物体，带一个微孔的空心金属球，非常接近黑体，进入金属球小孔的辐射，经多次吸收，反射使射入的辐射实际全被吸收，当空腔受热，空腔壁会发出辐射，极少数从小孔逸出，它是理想的吸收体也是理想的放射体，若把几种金属物体加热到同一温度，黑体放热最多，用棱镜把黑体发出的辐射分开就可测出指定狭窄的频率范围的黑体的能量。 规律：频率相同下黑体的能量随温度的升高而增大， 温度相同下黑体的能量呈峰型，峰植大致出现在频率范围是0.6-1.0/10-14S-1。 且随着温度的升高，能量最大值向高频移动. 加热金属块时，开始发红光，后依次为橙，白，蓝白。 黑体辐射频率为v的能量是hv的整数倍. 光电效应和光子学说： Planck能量量子化提出标志量子理论的诞生。 光电效应是光照在金属表面上使金属放出电子的现象，实验证实： 1.只有当照射光的频率超过金属最小频率（临阈频率）时，金属才能发出电子，不同金属的最小频率不同，大多金属的最小频率位于紫外区。 2.增强光照而不改变照射光频率，则只能使发射的光电子数增多，不影响动能。 3.照射光的频率增强，逸出电子动能增强。 光是一束光子流，每一种频率的光的能量都有一个最小单位光子，其能量和光子的频率成正比，即E=hv 光子还有质量，但是光子的静止质量是0，按相对论质能定律光子的质量是 m=hv/c2 光子的动量：p=mc=hv/c=h/波长 光的强度取决于单位体积内光子的数目，即光子密度。 光电效应方程：hv（照射光频率）=W（逸出功）+E（逸出电子动能） 实物微粒的波粒二象性： 由de Broglie（德布罗意）提出：p=h/波长 电子具有粒性，在化合物中可以作为带电的微粒独立存在（电子自身独立存在，不是依附在其他原子或分子上的电子） M.Born（玻恩）认为在空间任何一点上波的强度（即振幅绝对值平方）和粒子出现的概率成正比，电子的波性是和微粒的统计联系在一起，对大量的粒子而言衍射强度（波强）大的地方粒子出现的数目就多概率就大，反之则相反。 不确定度关系： Schrodinger（薛定谔）方程的提出标志量子力学的诞生. 不确定关系又称测不准关系或测不准原理，它是微观粒子本质特性决定的物理量间相互关系原理，反映了微粒波特性。而一个粒子不可能同时拥有确定坐标和动量（也不可以将时间和能量同时确定）[这是由W.Heisenberg（海森伯）提出的] 微观粒子与宏观粒子的比较： 1.宏观物体同时具有确定的坐标和动量可用牛顿力学描述（经典力学），微观粒子不同时具

数据库原理简答题总结

数据库原理简答题总结第一章数据库概论 1.人工管理阶段数据管理的特点： （1）数据不保存在机器中 （2）无专用的软件对数据进行管理 （3）只有程序的概念，没有文件的概念 （4）数据面向程序 2.文件系统阶段数据管理的特点： （1）数据可长期保存在外存的磁盘上 （2）数据的逻辑结构和物理结构有了区别 （3）文件组织已呈多样化。有索引、链接和散列文件 （4）数据不再属于某个特定的程序，可重复使用。 3.文件系统显露出三个缺陷： （1）数据冗余性 （2）数据不一致性 （3）数据联系弱 4.数据库阶段的管理方式具有以下特点： （1）采用复杂的数据模型表示数据结构 （2）有较高的数据独立性 （3）数据库系统为用户提供方便的用户接口 （4）系统提供四方面的数据控制功能 （5）对数据的操作既可以以记录为单位，又可以以数据项为单位 5.数据描述三个领域之间的关系： 从事物的特性到计算机中的数据表示，经历了三个领域：现实世界、信息世界、机器世界。 （1）现实世界：存在于人们头脑之外的客观世界，称为现实世界。 （2）信息世界：是现实世界在人们头脑中的反映。 （3）机器世界：信息世界的信息在机器世界中以数据形式存储。 信息世界中数据描述的术语有：实体、实体集、属性、实体标识符 机器世界中数据描述的术语有：字段、记录、文件、关键码 它们的对应关系是： 在数据库中每个概念都有类型和值之区分，类型是概念的内涵，值是概念的外延 6.数据描述的两种形式： 数据描述有物理描述和逻辑描述两种形式。 物理数据描述指数据在存储设备上的存储方式，物理数据是实际存放在存储设备上的数据。 逻辑数据描述指程序员或用户用以操作的数据形式，是抽象的概念化数据。 数据管理软件的功能之一，就是要把逻辑数据转换成物理数据，以及把物理数据转换成逻辑数据。 7.物理存储介质层次：

数据结构复习题总结

填空题 1.文件可按其记录的类型不同而分成两类，即( 操作系统文件 )和( 数据库 )文件。 2.数据库文件按记录中关键字的多少可分成( 单关键字文件 )和( 多关键字文件 )两种文件。 3.文件由( 记录 )组成，记录由( 数据项 )组成。 4.从用户观点看，文件的逻辑结构通常可以区分为两类：一类是如dBASE中数据库文件那样的文件组织结构，称为( 数据库 )文件；另一种是诸如用各种文字处理软件编辑成的文本文件，称为( 文本 )文件。 从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即( 顺序组织 )、 ( 随机组织 )、( 链组织 )。 B+树适用于组织( 随机组织 )的索引结构， m阶B+树每个结点至多有( m ) 除根结点外每个结点至少有( (m/2)向上取整 )个儿子，根结点至少有( 2 )个儿子，有k个儿子的结点必有( k )个关键码。 5.物理记录之间的次序由指针相链表示的顺序文件称为( 串联文件) 6.顺序文件中，要存取第I个记录，必须先存取( 第I-1 )个记录。 7.索引顺序文件既可以顺序存取，也可以( 随机 )存取。 8.建立索引文件的目的的( 提高查找速度 )。 9.索引顺序文件是最常用的文件组织之一，通常用( 树 )结构来组织索引。 10.倒排文件的主在优点在于( 检索记录块 )。 11.检索是为了在文件中满足一定条件的记录而设置的操作。检索可以按( 关

键字 )检索，也可以按( 记录号 ) 检索； 按( 记录号 ) 检索又可以有( 顺序 ) 检索和( 直接 ) 检索。 12.哈希检索的技术的关键是( 构造哈希函数 )和( 解决冲突的方法 )。结构来组织索引。 13.VSAM系统是由( 索引集 )、( 顺序集 ) 、( 数据集 )构成的。 14.VSAM( 虚拟存储存取方法 )文件的优点是：动态地( 分配和释放存储空间 ) ，不需要文件进行( 重组 ) ，并能较快地( 对插入的记录 ) 进行查找。 一～五章选择题 一 1.学习数据结构的主要目的是( C )。 A．处理数据计算问题 B．研究程序设计技巧 C．选取合适数据结构，写出更有效的算法 D．是计算机硬件课程的基础2.数据结构是一门研究非数值计算的程序设计问题中计算机的逻辑存储以及 它们之间的( B )和运算的科学。 A．结构 B．关系 C．运算 D．算法 3.在计算机中存储一个数据元素的位串称为 ( A ) 。 A. 结点 B. 数据项 C. 数据字段 D. 字符串 4.算法指的是( C ) A.计算机程序 B.排序算法 C.解决问题的有限运算序列 D.解决问题的计算方法 5.( D )是数据不可分割的最小单位。 A．数据结构 B．数据对象 C．数据元素 D．数据项 6.数据结构有 ( D ) 种基本逻辑结构。 A. 1 B. 2 C. 3 D. 4 7.在数据结构中，从逻辑上可以把数据结构分成( C )。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构 8.通常所说的时间复杂度是指( B )。

结构化学期末试卷(A卷)

《结构化学》期末试卷（A 卷） ┄┄┄┄┄┄装┄┄┄┄┄┄┄┄┄┄订┄ ┄┄┄┄┄┄线┄┄┄┄┄ 一、填空题：（25分） 1、氢原子光谱实验中，波尔提出原子存在于具有确定能量的（ ），此时原子不辐射能量，从（ ）向（ ）跃迁才发射或吸收能量；光电效应实验中入射光的频率越大，则（ ）越大。 2、e x （ ）（填是或不是）合格波函数。 3、定态指某状态的电子在空间某点的（ ）不随着时间的变化而变化。 4、电子衍射不是电子之间的相互作用结果，而是电子本身运动所具有的干涉效应。对于大量电子而言，衍射强度大的地方，表明（ ），对于一个电子而言，衍射强度大的地方，表明（ ）。 5、CO 的电子组态为1σ22σ23σ24σ21π45σ2，则前线轨道是（ ）、（ ）。 6、1，3——丁二烯（ ）（填有或无）方香性，原因（ ）。 7、共轭己三烯休克尔行列式为（ ）。 8、事实证明Li 的2s 轨道能和H 的1s 轨道有效的组成分子轨道，说明原因（ ）、（ ）、（ ）。 9、np 2组态的光谱项为（ ）、（ ）、（ ）。 10、一维势箱中的粒子具有（ ），说明该体系的粒子永远运动，其位置算符不具有本征值，具有平均值为（ ）。 11、晶体宏观外形中的对称元素可有（ ）、（ ）、（ ）、（ ）四种类型； 二、单选题：20分 1、下列状态为氢原子体系的可能状态是（ ）；该体系能量为（ ）： A 、2ψ310+3ψ41-1 B 、2ψ221+3ψ32-1 C 、2ψ21-1+3ψ342+3ψ410 D 、3ψ211+5ψ340+5ψ210 111111:() :13() :()139******** R E F R H R -+-+-+ 2、Ψ32-1的节面有（ ）个，其中（ ）个平面。 A 、3 B 、2 C 、1 D 、0 3、类氢体系的某一状态为Ψ43-1，该体系的能量为（ ）eV ，角动量大小为（ ），角动量在Z 轴上的分量为（ ）。 A 、-R/4 B 、-R/16 C 、-2R/9、 D 、 -h/2π E 、-h/π F 、-2h/2π

数据库原理知识总结和期末试卷

数据库知识要点归纳 第1章数据库基础知识 1.数据库（DB）是一个按数据结构来存储和管理数据的计算机软件系统。 数据库是长期储存在计算机内的、有组织的、可共享的数据集合。 数据库管理数据两个特征：1.数据整体性 2.数据库中的数据具有数据共享性 2.数据库管理系统（DBMS）是专门用于管理数据库的计算机系统软件 3.数据库应用系统是在数据库管理系统（DBMS）支持下建立的计算机应用系统，简写为DBAS。数据库应用系统是由数据库系统、应用程序系统、用户组成的。 例如，以数据库为基础的财务管理系统、人事管理系统、图书管理系统,成绩查询系统等等。 4.数据库系统DBS是一个实际可运行的存储、维护和应用系统提供数据的软件系统，是存储介质、处理对象和管理系统的集合体。它通常由软件、数据库和数据管理员组成。 5.数据库中数据独立性数据和程序之间的依赖程度低，独立程度大的特性称为数据独立性高。1、数据的物理独立性数据的物理独立性是指应用程序对数据存储结构的依赖程度。2、数据的逻辑独立性数据的逻辑独立性是指应用程序对数据全局逻辑结构的依赖程度。 6.数据库的三级模式是模式、外模式、内模式。1.模式（Schema）一个数据库只有一个模式 2.外模式（External Schema）一个数据库有多个外模式。3.内模式（Internal Schema）一个数据库只有一个内模式。 7.数据库系统的二级映象技术 第2章数据模型与概念模型 1.实体联系的类型：一对一联系（1:1）一对多联系（1:n）多对多联系（m:n） 2.E-R图描述现实世界的概念模型，提供了表示实体集、属性和联系的方法。 长方形表示实体集椭圆形表示实体集的属性菱形表示实体集间的联系 3.数据模型的三要素数据结构、数据操作、数据约束条件 数据结构分为：层状结构、网状结构和关系结构 常见的数据模型：层次模型、网状模型和关系模型。 层次模型用树形结构来表示各类实体以及实体间的联系

(完整版)非常实用的数据结构知识点总结

数据结构知识点概括 第一章概论 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。 数据结构的定义： ·逻辑结构：从逻辑结构上描述数据，独立于计算机。·线性结构：一对一关系。 ·线性结构：多对多关系。 ·存储结构：是逻辑结构用计算机语言的实现。·顺序存储结构：如数组。 ·链式存储结构：如链表。 ·索引存储结构：·稠密索引：每个结点都有索引项。 ·稀疏索引：每组结点都有索引项。 ·散列存储结构：如散列表。 ·数据运算。 ·对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。 ·常用的有：检索、插入、删除、更新、排序。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 ·结构类型：由用户借助于描述机制定义，是导出类型。 抽象数据类型ADT：·是抽象数据的组织和与之的操作。相当于在概念层上描述问题。 ·优点是将数据和操作封装在一起实现了信息隐藏。 程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。算法取决于数据结构。 算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。 评价算法的好坏的因素：·算法是正确的； ·执行算法的时间； ·执行算法的存储空间（主要是辅助存储空间）； ·算法易于理解、编码、调试。 时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。 渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。 算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。 时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O （n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。

数据结构期末考试复习总结,DOC

《数据结构》期末考试题型及分值 （1）简答题6题*5分=30分简要回答要点 （2）分析题6题*5分=30分给出结果 （3）设计题1题*10分=10分设计思想及结果 （4）编程题1题*10分=10分完整代码 （5）综合题1题*20分=20分抽象数据类型的定义、表示、实现、算法分析{定义=功能（ADT）表示=存储结构体实现=算法（基本操作）算法分析=时间、空间复杂度} 考试概念有：1.数据结构{一、线性表（栈-队-列-串-数组-广义表-逻辑结构-存储结构-运算结构） 二、非线性表（集合-树-图）} 2.抽象数据类型数据对象-数据关系-基本操作 3.算法性质-要求（设计）-效率（度量） 4.实例查找：高效查找算法 排序：高效的排序算法 分析题考试题目参考 （1）1-2-3-4-5-6顺序建BBST （2）6-5-4-3-2-1顺序建BBST 简答题实例 设计题： （1） （2） 数据结构试卷（一）

三、计算题（每题6分，共24分） 1. 在如下数组A 中链接存储了一个线性表，表头指针为A[0].next ，试写出该线性表。 A01234567 dat a 60 50 78 90 34 40 nex t 3 5 7 2 0 4 1 线性表为：（78，50，40，60，34，90）??????? ?????????01110 10 1 11101 11010101110 2. 请画出下图的邻接矩阵和邻接表。 3. 已知一个图的顶点集V 和边集E 分别为：V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。 用克鲁斯卡尔算法得到的最小生成树为： (1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20 4.画出向小根堆中加入数据4,2,5,8,3时，每加入一个数据后堆的变化。见图12 图12 图11 四、阅读算法（每题7分，共14分） 4 4 4 4 4 2 2 2 5 5 5 2 2 8 8 4 3 5 2 8 3 4

数据库原理总结

第一章数据库概论 1.人工管理阶段,文件系统阶段,数据库阶段,高级数据库阶段(对象数据库技术,分布式数据库系统,开放数据库互连技术,xml数据库技术,现代信息集成技术) 2.数据描述:概念设计中:实体,实体集,属性,实体标识符; 逻辑设计中:字段,记录,文件,关键码; 物理设计中:位,字节,字,块,桶,卷; 3.概念模型,逻辑模型(层次,网状,关系,对象),外部模型,内部模型; 4.三层模式(外模式,逻辑模式,内模式),两级映像(外模式/逻辑模式映像，逻辑模式/内模式映像) 5.数据库系统：数据库，硬件，软件，数据库管理员 第二章关系模型和关系运算理论 1.超键：能唯一标识元组的属性或属性集。 候选键：不含有多余属性的超键 主键：用户选作元祖标识的候选键。 外键：是其他模式的主键。 实体完整性规则，参照完整性规则，用户定义的完整性规则 关系模式的三层体系结构：关系模式，子模式，存储模式 2.关系代数的5个基本操作：并，差，笛卡尔积，投影，选择； 关系代数的4个组合操作：交，连接，自然连接，除法。 关系代数的7个扩充操作：改名，广义投影，赋值，外连接，外部并，半连接，聚集操作3.关系代数表达式的启发式优化算法： 尽可能早的执行选择操作； 尽可能早的执行投影操作； 避免直接做笛卡尔积 第三章关系数据库语言SQL 1.SQL的组成：数据定义语言，数据操纵语言，嵌入式，数据控制语言 2.数据定义：数据类型ok，数据库，数据表，索引的创建等ok。 3.数据查询，数据更新ok。 4，视图，嵌入式，动态SQL语句，存储过程。 第四章关系数据库的规范化设计 1.定义1：函数依赖：设有关系模式R（U），U为属性集，x、y为U的子集，函数依赖（FD）是形为X→Y的一个命题，只要r是R的当前关系，对r中任意两个元组t和s,都有t[X]=s[X]蕴涵t[Y]=s[Y],那么称FDX→Y在关系模式R(U)中成立。 定义2：如果X→Y和Y→X同时成立，则可记为X←→Y。 定义3：设F是在关系模式R上成立的函数依赖的集合，X→Y 是一个函数依赖。如果对于R 的每个满足F的关系r也满足X→Y ，那么称F逻辑蕴涵X→Y，记为F ? X→Y。 定义4：设F是函数依赖集，被F逻辑蕴涵的函数依赖全体构成的集合，称为函数依赖集F 的闭包（closure），记为F+。即F+ =｛X→Y | 记为F ? X→Y ｝

数据结构复习要点(整理版).docx

第一章数据结构概述 基本概念与术语 1．数据：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称。 2. 数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。 (补充：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 ) 3．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。(有时候也 叫做属性。) 4．数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 (1)数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。 数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。 依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种： 1. 集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。 2. 线性结构：结构中的数据元素之间存在“一对一“的关系。若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。 3. 树形结构：结构中的数据元素之间存在“一对多“的关系。若数据为非空集，则除了第一个元素 (根)之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直接后继。 4. 图状结构：结构中的数据元素存在“多对多”的关系。若结构为非空集，折每个数据可有多个(或零个)直接后继。 (2)数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射为以下两种存储结构： 1. 顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。 2. 链式存储结构：借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素物理位置上也相邻。 5. 时间复杂度分析：1.常量阶：算法的时间复杂度与问题规模n 无关系T(n)=O(1) 2. 线性阶：算法的时间复杂度与问题规模 n 成线性关系T(n)=O(n) 3. 平方阶和立方阶：一般为循环的嵌套，循环体最后条件为i++ 时间复杂度的大小比较： O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n )

《数据结构》期末考试题带答案(99%能过)

2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为（） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（）

结构化学期末试卷及答案

03级化学专业《结构化学》课程期末试卷(A) （参考答案和评分标准） 一选择题(每题2分，共30分) 1.由一维势箱的薛定谔法方程求解结果所得的量子数n,下面论述正确的是………………………………..............................( C ) A.可取任一整数 B. 与势箱宽度一起决定节点数 C. 能量与n2成正比 D. 对应于可能的简并态 2. 用来表示核外某电子运动状况的下列各组量子数(n,l,m,m s)中,哪一组是合理的?………………………………………...............( A ) A.（2，1，-1，-1/2 ） B. （0，0，0，1/2） C. （3，1，2，1/2） D. （2，1，0，0） 3. 丙二烯分子所属的点群........................................................( D ) A. C2v B. D2 C. D2h D. D2d 4. 2,4,6－三硝基苯酚是平面分子，存在离域键，它是....( E ) A. 1216 B. 1418 C. 1618 D. 1616 E. 1620 5. 对于),(~2,φ θ Y图，下列叙述正确的是...................( B ) φ θ A.曲面外电子出现的几率为0 B.曲面上电子出现的几率相等 C.原点到曲面上某点连线上几率密度相等 D.n不同，图形就不同

6. Mg(1s22s22p63s13p1)的光谱项是..............................................( D ) A. 3P,3S; B. 3P,1S; C. 1P,1S; D. 3P,1P 7. 下列分子中哪一个顺磁性最大................................................( C ) A. N2+ B. Li2 C. B2 D. C2 E. O2- 8. 若以x轴为键轴，下列何种轨道能与p y轨道最大重叠........( B ) A. s B. d xy C. p z D. d xz 9. CO2分子没有偶极矩，表明该分子是：-------------------------------------( D ) (A) 以共价键结合的(B) 以离子键结合的 (C) V形的(D) 线形的，并且有对称中心 (E) 非线形的 10. 关于原子轨道能量的大小，如下叙述正确的是......(D) A.电子按轨道能大小顺序排入原子 B.原子轨道能的高低可用（n+0.7l）判断 C.同种轨道的能量值是一个恒定值 D.不同原子的原子轨道能级顺序不尽相同 11. 已知Rh的基谱项为4F9/2，则它的价电子组态为.....( A ) A. s1d8 B. s0d9 C. s2d8 D. s0d10 12. 线性变分法处理H2+中得到，，S ab积分，对它们的取值，下列论述有错的是……………...........................................(D)

数据库原理与应用期末复习总结含试题及其答案

数据库原理综合习题答案 1.1名词解释 (1) DB：即数据库（Database),是统一管理的相关数据的集合。DB能为各种用户共享，具有最小冗余度，数据间联系密切，而又有较高的数据独立性。 (2) DBMS：即数据库管理系统（Database Management System)，是位于用户与操作系统之间的一层数据管理软件，为用户或应用程序提供访问DB的方法，包括DB的建立、查询、更新及各种数据控制。DBMS总是基于某种数据模型，可以分为层次型、网状型、关系型、面向对象型DBMS。 (3) DBS：即数据库系统（Database System),是实现有组织地、动态地存储大量关联数据，方便多用户访问的计算机软件、硬件和数据资源组成的系统，即采用了数据库技术的计算机系统。 (4) 1：1联系：如果实体集E1中的每个实体最多只能和实体集E2中的一个实体有联系，反之亦然，那么实体集E1对E2的联系称为“一对一联系”，记为“1：1”。 (5) 1：N联系：如果实体集E1中每个实体与实体集E2中任意个（零个或多个）实体有联系，而E2中每个实体至多和E1中的一个实体有联系，那么E1对E2的联系是“一对多联系”，记为“1：N”。 (6) M：N联系：如果实体集E1中每个实体与实体集E2中任意个（零个或多个）实体有联系，反之亦然，那么E1对E2的联系是“多对多联系”，记为“M：N”。 (7) 数据模型：模型是对现实世界的抽象。在数据库技术中，表示实体类型及实体类型间联系的模型称为“数据模型”。它可分为两种类型：概念数据模型和结构数据模型。 (6) 概念数据模型：是独门于计算机系统的模型，完全不涉及信息在系统中的表示，只是用来描述某个特定组织所关心的信息结构。 (9) 结构数据模型：是直接面向数据库的逻辑结构，是现实世界的第二层抽象。这类模型涉及到计算机系统和数据库管理系统，所以称为“结构数据模型”。结构数据模型应包含：数据结构、数据操作、数据完整性约束三部分。它主要有：层次、网状、关系三种模型。 (10) 层次模型：用树型结构表示实体类型及实体间联系的数据模型。 (11) 网状模型：用有向图结构表示实体类型及实体间联系的数据模型。 (12) 关系模型：是目前最流行的数据库模型。其主要特征是用二维表格结构表达实体集，用外鍵表示实体间联系。关系模型是由若干个关系模式组成的集合。 (13) 概念模式：是数据库中全部数据的整体逻辑结构的描述。它由若干个概念记录类型组成。概念模式不仅要描述概念记录类型，还要描述记录间的联系、操作、数据的完整性、安全性等要求。 (14) 外模式：是用户与数据库系统的接口，是用户用到的那部分数据的描述。 (15) 内模式：是数据库在物理存储方面的描述，定义所有的内部记录类型、索引和文件的组成方式，以及数据控制方面的细节。 (16) 模式/内模式映象：这个映象存在于概念级和内部级之间，用于定义概念模式和内模式间的对应性，即概念记录和内部记录间的对应性。此映象一般在内模式中描述。 (17) 外模式/模式映象：这人映象存在于外部级和概念级之间，用于定义外模式和概念模式间的对应性，即外部记录和内部记录间的对应性。此映象都是在外模式中描述。 (18) 数据独立性：在数据库技术中，数据独立性是指应用程序和数据之间相互独立，不受影响。数据独立性分成物理数据独立性和逻辑数据独立性两级。 (19) 物理数据独立性：如果数据库的内模式要进行修改，即数据库的存储设备和存储方法有所变化，那么模式/内模式映象也要进行相应的修改，使概念模式尽可能保持不变。也就是对模式的修改尽量不影响概念模式。

数据结构复习提纲(整理)

复习提纲 第一章数据结构概述 基本概念与术语（P3） 1．数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科. 2．数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合 2．数据元素是数据的基本单位 3．数据对象相同性质的数据元素的集合 4．数据结构包括三方面内容:数据的逻辑结构.数据的存储结构.数据的操作. （1）数据的逻辑结构指数据元素之间固有的逻辑关系. （2）数据的存储结构指数据元素及其关系在计算机内的表示 ( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等. 5.时间复杂度分析 -------------------------------------------------------------------------------------------------------------------- 1、名词解释：数据结构、二元组 2、根据数据元素之间关系的不同，数据的逻辑结构可以分为 集合、线性结构、树形结构和图状结构四种类型。 3、常见的数据存储结构一般有四种类型，它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。 4、以下程序段的时间复杂度为___O(N2)_____。 int i,j,x; for(i=0;i

结构化学知识点汇总

第一章：原子结构 1. S能级有个原子轨道，P能级有个原子轨道，d能级有个原子轨道，同一能级的原子轨道能量，每个原子轨道最多可以排个自旋方向相反的电子。当2P能级有2个未成对电子时，该原子可能是或者，当3d能级有2个未成对电子时，该原子可能是或者。 2. S轨道图形为，P轨道图形为沿三维坐标轴x y z 对称分布的纺锤形。 3. 主族元素的价电子就是电子，副族元素的价电子为与之和（Cu和Zn除外）。 4. 19～36号元素符号是： 它们的核外电子排布是： 5. 元素周期表分，，，，五大区。同周期元素原子半径从左到右 逐渐，原子核对外层电子吸引力逐渐，电负性及第一电离能逐渐，（ⅡA，ⅤA 特殊）；同主族元素原子半径从上到下逐渐，电负性及第一电离能逐渐。 6. 依照洪特规则，由于ⅡA族，ⅤA族元素原子价电子处于稳定状态，故其第一电离能比相邻同周期元素 原子，如：N>O>C ; Mg>Al>Na ,但是电负性无此特殊情况。 7. 电负性最强的元素是，其电负值为4.0 ，其次是，电负值为3.5 第二章化学键与分子间作用力 1.根据共价键重叠方式的不同，可以分为键和键，一个N2分子中有个σ键个П 键，电子式为。根据共价键中共用电子对的偏移大小，可将共价键分为键和键，同种非金属原子之间是，不同原子之间形成。 2.共价键的稳定性与否主要看三个参数中的，越大，分子越稳定。其次是看键长，键长 越短，分子越（键长与原子半径有正比例关系）。键角与分子的空间构型有关，CO2,C2H2分子为直线型，键角是1800；CH4和CCl4为正四面体型，键角为；NH3分子构型为， H2O分子构型为，它们的键角均小于。 3.美国科学家鲍林提出的杂化轨道理论认为：CH4是杂化；苯和乙烯分子为杂化； 乙炔分子为杂化。其他有机物分子中，全单键碳原子为杂化，双键碳原子为杂化，三键碳原子为杂化。 4. 价电子对互斥理论认为ABn型分子计算价电子对公式为，其中H 卤素原 子做配位原子时，价电子为个；O,S做配位原子时，不提供电子；如果带有电荷，做相应加减； 出现点五，四舍五入。 5. 价电子对数目与杂化方式及理想几何构型： 补充：如果配位原子不够，则无法构成理想结构。 6.等电子原理：。 如：CO2与CS2,N2O / N2与CO,CN-,NO+ / CH4与SiH4,NH4+, / NH3与H3O+ / SO42-与PO43-,ClO4- 7.如果分子中正负电荷重心重合，则该分子为非极性分子，否则为极性分子。含有极性共价键的非极性分 子有CO2 CS2 CH4 SiH4 SO3 BeCl2 BF3 CCl4 SiCl4 PCl5 SF6。含有非极性键的极性分子：

《数据库原理》知识点总结

《数据库原理》知识点总结标准化文件发布号：（9312-EUATWW-MWUB-WUNN-INNUL-DQQTY-

目录未找到目录项。 一数据库基础知识（第1、2章） 一、有关概念 1．数据 2．数据库（DB） 3．数据库管理系统（DBMS） Access 桌面DBMS VFP SQL Server Oracle 客户机/服务器型DBMS MySQL DB2 4．数据库系统（DBS） 数据库（DB） 数据库管理系统（DBMS） 开发工具 应用系统 二、数据管理技术的发展 1．数据管理的三个阶段 概念模型 一、模型的三个世界 1．现实世界

2．信息世界：即根据需求分析画概念模型（即E-R图），E-R图与DBMS 无关。 3．机器世界：将E-R图转换为某一种数据模型，数据模型与DBMS相关。 注意：信息世界又称概念模型，机器世界又称数据模型 二、实体及属性 1．实体：客观存在并可相互区别的事物。 2．属性： 3．关键词（码、key）：能唯一标识每个实体又不含多余属性的属性组合。 一个表的码可以有多个，但主码只能有一个。 例：借书表（学号，姓名，书号，书名，作者，定价，借期，还期） 规定：学生一次可以借多本书，同一种书只能借一本，但可以多次续借。 4．实体型：即二维表的结构 例 student(no，name，sex，age，dept) 5．实体集：即整个二维表 三、实体间的联系： 1．两实体集间实体之间的联系 1：1联系 1：n联系 m：n联系 2．同一实体集内实体之间的联系 1：1联系 1：n联系 m：n联系 四、概念模型（常用E-R图表示） 属性： 联系： 说明：① E-R图作为用户与开发人员的中间语言。 ② E-R图可以等价转换为层次、网状、关系模型。 举例： 学校有若干个系，每个系有若干班级和教研室，每个教研室有若干教员，其中有的教授 和副教授每人各带若干研究生。每个班有若干学生，每个学生选修若干课程，每门课程有若干学生选修。用E-R图画出概念模型。

2021年自考02331数据结构重点总结最终修订

自考02331数据构造重点总结(最后修订) 第一章概论 1.瑞士计算机科学家沃思提出：算法+数据构造=程序。算法是对数据运算描述，而数据构造涉及逻辑构造和存储构造。由此可见，程序设计实质是针对实际问题选取一种好数据构造和设计一种好算法，而好算法在很大限度上取决于描述实际问题数据构造。 2.数据是信息载体。数据元素是数据基本单位。一种数据元素可以由若干个数据项构成，数据项是具备独立含义最小标记单位。数据对象是具备相似性质数据元素集合。 3.数据构造指是数据元素之间互有关系，即数据组织形式。 数据构造普通涉及如下三方面内容：数据逻辑构造、数据存储构造、数据运算 ①数据逻辑构造是从逻辑关系上描述数据，与数据元素存储构造无关，是独立于计算机。 数据逻辑构造分类：线性构造和非线性构造。 线性表是一种典型线性构造。栈、队列、串等都是线性构造。数组、广义表、树和图等数据构造都是非线性构造。 ②数据元素及其关系在计算机内存储方式，称为数据存储构造（物理构造）。 数据存储构造是逻辑构造用计算机语言实现，它依赖于计算机语言。 ③数据运算。最惯用检索、插入、删除、更新、排序等。 4.数据四种基本存储办法：顺序存储、链接存储、索引存储、散列存储 （1）顺序存储：普通借助程序设计语言数组描述。 （2）链接存储：普通借助于程序语言指针来描述。 （3）索引存储：索引表由若干索引项构成。核心字是能唯一标记一种元素一种或各种数据项组合。 （4）散列存储：该办法基本思想是：依照元素核心字直接计算出该元素存储地址。 5.算法必要满足5个准则：输入，0个或各种数据作为输入；输出，产生一种或各种输出；有穷性，算法执行有限步后结束；拟定性，每一条指令含义都明确；可行性，算法是可行。 算法与程序区别：程序必要依赖于计算机程序语言，而一种算法可用自然语言、计算机程序语言、数学语言或商定符号语言来描述。当前惯用描述算法语言有两类：类Pascal和类C。 6.评价算法优劣：算法"对的性"是一方面要考虑。此外，重要考虑如下三点： ①执行算法所耗费时间，即时间复杂性； ②执行算法所耗费存储空间，重要是辅助空间，即空间复杂性； ③算法应易于理解、易于编程，易于调试等，即可读性和可操作性。

数据结构期末复习总结超详细1

数据结构复习要点带答案 算法的五大特性：（有零个或多个输入）、（有一个或多个输出）、（有穷性）、（确定性）、（可行性）。 算法指的是（）。 A 对特定问题求解步骤的一种描述，是指令的有限序列；算法分析的目的是（分析算法的效率以求改 进），算法分析的两个主要方面是（空间性能和时间性能）。 1.算法质量的标准：时间复杂度是测量一个算法优劣的重要标准。 时间复杂度的计算：设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（Ο(1)），若为n*log25n，则表示成数量级的形式为（Ο(nlog2n)）。 【分析】：用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2.数据、数据元素、数据项的关系：（数据元素）是数据的基本单位，在计算机程序中通常作为一个整体 进行考虑和处理；（数据项）是数据的最小单位，（数据元素）是讨论数据结构时涉及的最小数据单位。 【分析】数据结构指的是数据元素以及数据元素之间的关系。 3.设有数据结构（D，R），其中D={1, 2, 3, 4, 5, 6}，R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。 试画出其逻辑结构图并指出属于何种结构。 【解答】其逻辑结构图如图1-3所示，它是一种图结构。 4.栈的特性：栈是限定仅在表尾进行插入和删除操作的线性表，允许插入和删除的一段叫做栈顶，另一 端叫做栈底，不含任何数据元素的栈叫做空栈。（栈）可作为实现递归函数调用的一种数据结构。 【分析】递归函数的调用和返回正好符合后进先出性。 栈的特点是先进后出，即：进去的早，出来的晚！ 54321进栈，5在栈底，1在栈顶！ 出一次栈，则栈顶的1先出来，2成为新的栈顶。 ABCD入栈，D成为新的栈顶。 全部出栈：D C B A 2 3 4 5 综上，所有元素退栈顺序为：1 D C B A 2 3 4 5 5.入栈：template V oid SeqStack::Push(T x) { if ( top==StackSize-1) throw “上溢”; top++; data[top]=x; } 6.出栈的指针的操作：template T SeqStack::Pop() { if ( top== -1) throw “下溢”; x=data[top--]; return x; }顺序栈基本操作时间复杂度为O（1）.

结构化学期末试题3说课讲解

西南大学 结构化学期末考试试卷（ C ) 一 判断题 （15 ） 1、( )在光电效应实验中，当入射光的频率增大，光电子的动能增大；入射光的强度越大，则光电流越大。 2、( )某状态的电子在空间某点的几率密度不随着时间的变化而变化，称此状态为定态。 3、( ) 保里原理是指等同粒子体系的波函数必须用slater 行列式描述，符合反对称要求。 4、( ) 由于MO 理论采用单电子近似, 所以在讨论某个电子的运动时完全忽略了其它电子的作用 5、( ) 具有自旋未成对电子的分子是顺磁性分子, 但不一定只有含奇数个电子的分子才能是顺磁性的。 6、( )晶体场理论认为, 中心离子与配位体之间的静电作用是络合物稳定存在的主要原因。 7、( )用HMO 理论处理, 直链共轭烯烃的各π分子轨道都是非简并的。 8、( )顺磁性分子也有反磁性，但顺磁性大于反磁性。 9、( )晶体的所有宏观对称元素都是其微观对称元素。 10、( )某金属原子采用Ａ1堆积型式，其晶胞型式为简单立方。 二 选择题 （20 ） 1、Ψ321的节面有（ ）个，其中（ ）个球面。 A 、3 B 、2 C 、1 D 、0 2、下列函数是算符d 2 /dx2的本征函数的是：（ ）；本征值为：（ ）。 A 、3x 4 B 、SinX C 、x 2e x D 、x 3 E 、3 F 、-1 G 、1 H 、2 3、单个电子的自旋角动量的值是：（ ） :12/2 :6/2 C: 6/4 D:3/4A h B h h h ππππ 4、KCl 属于NaCl 型晶体，一个晶胞中含（ ）个K +。 A 、 1 B 、2 C 、 4 D 、 6 5、下列络离子几何构型偏离正八面体最大的是（ ）： A 、[Cu(H 2O)6]2+ B 、 [Co(H 2O)6]2+ C 、 [Fe(CN)6]3- D 、[Ni(CN)6]4- 6、CH 3-CH 2-OH 中OH 质子的核磁共振峰发生分裂是由于 ( ) A 、 受邻近C 核自旋的影响 B 、 受邻近O 核自旋的影响 C 、受邻近电子自旋的影响 D 、受邻近H 核自旋的影响 7、金属Cu 晶体具有立方面心晶胞，则Cu 的配位数为（ ），堆积类型为（ ）。 A 、4 B 、6 C 、8 D 、12 E 、A 1 F 、A 2 G 、A 3 9、电子云图是下列哪一种函数的图形：（ ） A 、D(r) B 、R(r) C 、ψ2(r,θ,φ) D 、ψ(r,θ,φ) 9、已知测得两个同位素的转动光谱的波数分别为a 1、a 2，若已知1μ，则2μ为（ ）： 121112********* :() : () : :a a a a A B C D a a a a μμμμ 10、晶体对称性可划分为（ ）个晶系、（ ）种空间格子。 A 、7, 14 B 、8, 14 C 、7, 15 D 、32, 14 三、回答问题：（30 ） 1、 说明下列化合物中心原子的杂化类型、分子的几何构型及分子所属点群 NH 3、 BF 3、CH 3CCl 3、 [Fe （CN ）6]3- 2、写出苯的休克尔行列式。 3、什么是核磁共振: 4、什么是分子点群: 5、 写出薛定谔方程的算符表达式,你是怎样理解这个表达式的. 6、怎样表达一个电子的运动状态?怎样表达原子的整体状态/光谱项,光谱支项各代表什么含义? 四．Ar 在20K 的低温下按立方最密堆积形成晶体,晶胞常数为5.43? .已知Ar 原子量M=39.948, N o =6.022×1023 , 试计算:（ 15分 ）