第一章概述
一、定义
1、数据结构的主要研究内容：通常是研究数据的存储结构（物理结构）和逻辑
结构，以及它们之间的相互联系；对每种结构定义相适应的各种运算，设计出相应的算法，分析算法的效率。
2、从逻辑上可以把数据结构分为线性结构、非线性结构两大类。即：数据逻辑
结构除了集合以外，还包括线性结构、树形结构和图形结构。
3、数据的逻辑结构与数据元素本身的内容和形式无关。
4、数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。
二、算法
1、程序和算法原则上是有区别的。
2、算法分析的两个主要方面是：时间复杂度和空间复杂度
第二章线性表
一、顺序表
1、顺序表中的地址计算公式：第一个元素的存储地址是LOC(a1)，每个元素占
用L个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置，则第i个元素的存储地址为：
LOC(a i)=LOC(a1)+(i-1)* L (1 ≤i ≤n)
2、在顺序表中访问任意一结点的时间复杂度均为 O(1) ，因此，顺序表也
称为随机存取的数据结构。
二、单链表
1、在结点P后插入结构q的语句：q->next=p->next; p->next=q;
2、删除结点P后的结点q的语句：p->next=q->next; free(q);
3、链式存储的存储结构所占存储空间：分两部分，一部分存放结点值，另一
部分存放表示结点间关系的指针
4、在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一
定紧邻。
三、双向链表
1、在双向链表存储结构中，删除p所指的结点时可修改指针：
p->next->prior=p->prior; p->prior->next=p->next;
2、双向链表指针p的结点前插入一个指针q的结点操作是：
q-> next =p;q-> prior =p-> prior ;p-> prior -> next =q;p-> prior =q;
四、各种存储结构综合
1、顺序表结构适宜于进行随机存取，而链表适宜于进行顺序存取。
2、单链表的每个结点包含一个指针域，双向链表的每个结点包含两个指针域。
五、例题和算法设计
例1：顺序表中第一个元素的存储地址是50，每个元素的长度为4，则第10个元素的地址是：LOC(a10)＝LOC(a1)+(10-1)* 4＝86
例2：在带头结点的单链表中删除一个最小值结点的算法。
void delete（Linklist *L）
{ Linklist *p,*q;
p=L；
q= L->next；
while（q&&q->next）
{ if（q->next->data
p= q；
q= q->next；
}
if(p->next)
{ q=p->next；
p->next=q->next;
free（q）；
}
}∥结束算法delete。
例3：已知不带头结点的线性链表list，链表中结点构造为（data、link），其中 data为数据域，link为指针域。请写一算法，将该链表按结点数据域的值的大小从小到大重新链接。
LinkedList LinkListSort(LinkedList list)
∥list是不带头结点的线性链表，链表结点构造为data和link两个域，data是数据域，link是指针域。本算法将该链表按结点数据域的值的大
小，从小到大重新链接。
{p=list->link; ∥p是工作指针，指向待排序的当前元素。
list->link=null;∥假定第一个元素有序，即链表中现只有一个结点。
while(p!=null)
{r=p->link; ∥r是p的后继。
q=list;
if(q->data>p->data、∥处理待排序结点p比第一个元素结点小的情况。 {p->link=list;
list=p;∥链表指针指向最小元素。
}
else∥查找元素值最小的结点。
{while(q->link!=null&&q->link->data
p->link=q->link;∥将当前排序结点链入有序链表中。
q->link=p; }
p=r;∥p指向下个待排序结点。
}
}
例4：将一个带头结点、数据项递增有序的单向链表，重新排列链表，使数据项递减有序。
void invert(Linklist *la）
{ linklist *p,*q;
p=la->next；
la->next= NULL；
while（p!= NULL）
{q= p->next；
p->next=la->next；
la->next=p；
p= q；
}
}
第3章栈和队列
一、栈
1、栈的特点：先进后出或称作后进先出
2、入栈与出栈序列
3、空栈：是不包含任何元素的栈
4、栈的应用
（1）在判别表达式中左，右括号是否配对出现的算法中，采用栈作为数据结构最佳。
（2）在表达式求值、进制转换、函数或过程的调用等算法中，都要用到栈。
二、队列
1、队列的特点：先进先出，在队列中，通常允许删除的一端称为队头，允许插
入的一端称为队尾。
2、队列的应用：解决计算机主机与打印机间速度不匹配问题，通常设一个打印
数据缓冲区，该缓冲区的逻辑结构就是一个队列。
3、循环队列中的元素个数计算公式。
4、对顺序栈作操作运算时，进栈应先判别栈是否满，出栈时应先判别栈是否空。
且顺序队列和循环队列关于队满和队空的判断条件是不一样的。
5、设循环队列存放在向量s.data[M+1]中，设：队头指针为s.front，队尾指
针为s.rear，采用牺牲一个单元的办法来区分队满和队空。则：
出队操作时，队头指针变化可表示为： s.front=(s.front+1)%(M+1)；
队满的条件为：_(s.rear+1)%(M+1)==s.front；
三、栈与队列的存储
栈和队列都是操作受限的线性结构，都可以用顺序存储和链式存储。
四、例题分析
例1：有六个元素6，5，4，3，2，1 的顺序进栈，则：（ 5 4 3 6 1 2）不是合法的出栈序列。
例2：设一个栈的输入序列是 1，2，3，4，5,下列序列中，（ D ）是栈的合法输出序列。
A. 5 1 2 3 4
B. 4 5 1 3 2
C. 4 3 1 2 5
D. 3 2 1 5 4
例3：数组Q［ｎ］用来表示一个循环队列，front为当前队列头元素的前一位置，rear为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为:（n+rear-fron)%n
例4：假设为循环队列分配的向量空间为Q[25]（下标从0开始），若队列的长度和队头指针值分别为15和20，则当前队尾指针的值为： 10。
例5：循环队列存储在数组A[0..m]中，则入队时的操作为（ D ）。
A. rear=rear+1
B. rear=(rear+1) mod (m-1)
C. rear=(rear+1) mod m
D. rear=(rear+1)mod(m+1)
第4、5章串和数组
一、串
1、串的长度的定义：是指串中所含字符的个数
2、子串的定义，例如：“DTA”不是“DATAA”的子串。
3、串的存储结构中，堆分配存储是一种动态存储结构。
4、空串是任意串的字串。
二、数组
1、数组的地址计算公式：
设二维数组是A[c1..d1, c2..d2]，这里c1,c2不一定是0。
则行优先存储时的地址公式为：
LOC(a
i,j )=LOC(a
c1,c2
)+[(i-c
1
)*(d
2
-c
2
+1)+j-c
2
]*L
二维数组列优先存储的通式为：
LOC(a
ij )=LOC(a
c1,c2
)+[(j-c
2
)*(d
1
-c
1
+1)+i-c
1
]*L
2、特殊矩阵的压缩存储及其地址映射公式
三、例题分析
例1：设有数组A[i,j]，数组的每个元素长度为4字节，i的值为1到7，j 的值为1到10，数组从内存首地址Loc开始顺序存放，当用以行为主存放时，元素A[4,6]的存储首地址为（ Loc+140 ）；当用以列为主存放时，元素A[4,6]的存储首地址为（ Loc+152 ）。
例2：设有一个9阶的对称矩阵，采用压缩存储方式，以行序为主存储，a
1，1
为第一元素，其存储地址为1，每个元素占2个地址空间，则a
7，5
的地址
为（ 51 ），则a
5，7
的地址为（ 51 ）。
例3：设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的
次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素a
ij
(1≤i，j≤n，且i≤j)在B中的位置为( B )。
A. i(i-l)/2+j
B. j(j-l)/2+i
C. j(j-l)/2+i-1
D. i(i-l)/2+j-1
例4： A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是
（ B ）。
A. i（i-1）/2+j
B. j（j-1）/2+i
C. i（j-i）/2+1
D. j（i-1）/2+1
例5：有一个二维数组A[0:8,1:5],每个数组元素用相邻的4个字节存储，存储器按字节编址，假设存储数组元素A[0,1]的地址是100，若按行主顺序存储，则A[3,5]的地址是176 和 A[5,3]的地址是208 。若按列存储，则A[7,1] 的地址是128 ，A[2,4]的地址是216 。
第6章树
一、二叉树定义
1、由3个结点可以构造出5种不同的二叉树。
2、二叉树中，指针p所指结点为叶子结点的条件是：
p->lchild==null && p->rchlid==null
3、在二叉树中，每个结点的两棵子树是有序的。
二、二叉树的性质
1、性质2：二叉的高与结点之间的关系
2、性质5：完全二叉树中双亲、左孩子与右孩子之间的关系及其应用
3、完全二叉树和满二叉树的关系：满二叉树一定是完全二叉树，完全二叉树
不一定是满二叉树。
4、在满二叉树中，只有度为0或度为2的结点，不存在度为1的结点。
5、性质3：度为0、1、2三类结点间的关系
三、二叉树的遍历
1、由二叉树的先序序列和中序序列可以唯一确定一棵二叉树。由二叉树的后
序序列和中序序列可以唯一确定一棵二叉树。但由二叉树的先序序列和后序序列不能唯一确定一棵二叉树。
2、在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后
顺序完全相同。
四、树的存储结构、树的遍历、树与二叉树之间的转换
1、把一棵树转换为二叉树后，这棵二叉树的形态是唯一的，且没有右子树。
即：由树转化为二叉树，其根结点的右子树总是空的。
2、树转换成二叉树
3、树的存储形式有：双亲表示法、孩子链表表示法、孩子兄弟表示法等，但
没有顺序存储表示法。
4、树的遍历
5、森林转换成二叉树：注意其左右子树上的结点个数。
设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是m-n。如果森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。则与森林F对应的二叉树根结点的右子树上的结点个数是M2+M3。
五、哈夫曼树
1、特点
2、构成和应用
六、例题分析
1、二叉树性质应用
例1：一个具有1000个结点的二叉树的高h介于10至1000之间，一个具有1000个结点的完全二叉树的高h等于10。
例2：具有256个结点的完全二叉树的深度为 9（注意：不能是8）。
例3：如某二叉树有30个叶子结点，有40个结点仅有一个孩子，则该二叉树的总结点数为：99。
例4：一棵完全二叉树上有1000个结点，其中叶子结点的个数是500个，如果有1000个结点，则其叶子结点的个数是501个。
2、已知中序序列和后序序列确定一棵树，已知中序序列和先序序列确定一棵树
例1：已知一棵二叉树的先序序列是ABDEFCGH，中序序列是DBFEACGH，请画
出这棵二叉树，并给出后序序列。
答：该二叉树如右图
后序序列：DFEBHGCA
例2：已知一棵二叉树的中序序列是DBEFAGHC，后序序列是DFEBHGCA，请画出这棵二叉树，并给出先序序列。
答：该二叉树如右图
先序序列：DFEBHGCA
3、树和二叉之间的转换
例：请按孩子兄弟表示法将下列树结构转换为对应的二叉树，并给出该树的一种先序遍历序列和后序遍历序列。
答：对应的二叉树：
树的一种先序遍历序列：ABEFGCDHI
树的一种后序遍历序列：EFGBCHIDA
4、哈夫曼树生成及哈夫曼编码
例：假设用于通信的电文仅由7个字母组成，字母在电文中出现的次数分别为5,30,8，10,7,16,24。请根据各个字符的出现概率构造一棵哈夫曼树，并为这8个字母设计哈夫曼编码。
答：哈夫曼树如下（形状不唯一）：
哈夫曼编码（编码不唯一）
30:00 5：0100 7：0101 16:011 8：100 10：101 24：11
8
5 7
24
16
30
10
100
58 42
28
12
18
A
B
F
D
C
G
H
E
A
B
F
D
C
G
H
E
第7章图
一、图的定义和存储结构
1、图可以没有边，但不能没有顶点。
2、邻接表和邻接矩阵都可用于存储有向图和无向图。
3、在有向图中，
4、在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于 1。
5、完全图中，顶点数和边数的关系
二、图的遍历
1、图的遍历方法：深度优先遍历、广度优先遍历
2、若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所
有的顶点，则该图一定是连通图。
3、用邻接表表示图进行广度优先遍历时，通常借助队列来实现算法。
4、深度优先遍历算通常采用递归或借助栈来实现。
三、最小生成树
1、带权图最小生成树不一定是唯一的，可以有一棵或多棵，但其最小生成树
的代价是唯一的
2、最小生成树的两种生成算法
四、AOV网与AOE网
1、拓扑排序方法可以判断出一个有向图是否有环。
例1：具有9个顶点的有向完全图有72条弧。具有9
个顶点的无向图，边的总数最多为36。
例2：图的邻接矩阵如右图所示，则从顶点v0出发按
深度优先遍历的结果是（0,3,6,1,5,4,2）
例3：已知一个图的采用二维数组表示的邻接矩阵如下图所示，请回答下列问题：
（1）画出该邻接矩阵对应的图。
（2）请画出自顶点v1出发进行遍历所得的深度优先遍历生成树。
答：该图为：
深度优先遍历生成树
例4：已知一个图的采用二维数组表示的邻接表如下图所示，请回答下列问题：（1）画出该邻接表对应的图
。
（2）请画出自顶点v1出发进行遍历所得的广度优先遍历生成树。
答：该图如下图：广度优先遍历生成树如下图
第9章查找
一、顺序查找和索引（分块）查找的算法思想
1、索引查找中，数据的组织特点是：块内可无序，块间要有序。
2、若查找表的长度为n，则顺序查找法的平均查找长度为（n+1）/2。
v1
V4
v2
V3
V5 V6
v1
V4
v2 V3 V5
V6
v1
V4
v2 V3
V8
V5 V6 V7
3、顺序查找算法可以适用于有序表、无序表，可以采用顺序存储和链式存储。
二、折半查找
1、适用于折半查找的表的存储方式及元素排列要求：
顺序方式存储，元素有序
2、折半查找中，元素的比较次数
3、对有序表而言，采用折半查找并不是总比采用顺序查找法速度快。
三、二叉排序树
1、定义：二叉排序树的左子树不为空，则左子树上所有结点的值均小于它
的根结点值，右子树不为空，则右子树上所有结点的值均大于它的根结
点的值。
2、对于一个二叉排序树，按二叉树层次进行遍历可以得到一个有序序列。
3、对于两棵具有相同关键字但形状不同的二叉排序树，按中序遍历它们得到
的序列的顺序是一样的。
4、平衡二叉树中某一结点左子树的深度减去右子树的深度称为该结点的平衡
因子。
四、哈希查找
1、散列法是一种将关键字转换为存储地址的存储方法。
2、哈希函数的选择要视情况而定，不存在特别好与坏的哈希函数。
3、哈希表的生成
五、例题分析
1、折半查找
例1、在有序表A[1..25]中，按二分查找方法进行查找，查找长度为5的元素个数是10个
例2：在有序表（3，5，8，15，25，34，55，78，90，100）中采用折半查找方法，查找表中元素58，则它将依次与表中（ 25，78，340，55 ）比较大小，查找结果是失败。
2、二叉排序树构造
例1：分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（ B ）。
A．（105，85， 95， 60， 125，110，140）
B．（105，60， 85， 95， 125，110，140）
C．（105，125，110，140，85， 60， 95）
D．(105，85， 60， 95， 125，140，110)
例2：给定关键字序列21，88，20，10，13，12，24，31，若采用二叉排序树查找，请回答下列问题：
（1）画出二叉排序树查找的二叉排序树。
（2）假定每个元素的查找概率相等，则查找成功时的平均查找长度是多少？
答：（1）二叉排序树（关键字顺序已确定，该二叉排序树唯一）如下图所
示：
（2）从上图可以得到二叉排序树查找的成功平均查找长度为：
ASL=(1+2*2+3*2+4*2+5*1)/8=3
3、哈希表构造
例1：设哈希表长为15，哈希函数是H(key)=key%11，表中已有数据的关键
字为26，38，72，84共四个，现要将关键字为49的元素加到表中，用线性探测再散列法解决冲突，则放入的位置是：8；用二次探测法解决冲突，则放入的位置是： 9。
例2：设哈希（Hash ）表的地址范围为0～17，哈希函数为：H （K ）＝K MOD 16。
K 为关键字，用线性探测法再散列法处理冲突，输入关键字序列：
（10，24，32，17，31，30，46，47，40，63，49）
造出Hash 表，试回答下列问题：
(1)按关键字的输入顺序构造哈希表，画出所构造哈希表的示意图。
(2)求所构造哈希表查找成功时的平均查找长度ASL 。
答：（1）最后得到的哈希表示意图如下表所示：
例3、设关键字的输入序列为：（47，7，29，11，16，92，22，8，3），哈希表的地址范围为0～10，哈希函数为：H （K ）＝K MOD 11，K 为关键字值，采用线性探测法处理冲突，请回答下面两个问题：
(1)按关键字的输入顺序构造哈希表，画出所构造哈希表的示意图。
(2)求所构造哈希表查找成功时的平均查找长度ASL 。
答：（1）最后得到的哈希表示意图如下表所示：
21 20 12 10 88 24 31
13
（2）ASL＝（1+2+1+1+1+4+1+2+2）/9＝5/3=1.67
第10章排序
一、各类排序的算法思想
1、内部排序的定义：内部排序就是整个排序过程完全在内存中进行的排序。
2、算法稳定性的定义。
二、插入排序
1、直接插入排序时，关键字的比较次数与记录的初始排列有关，初始序列顺
序时比较次数最少，初始序列倒序时比较次数最多。
2、直接插入排序的思想。
3、希尔排序的算法思想，能写出每一趟排序的结果序列。
4、希尔排序是否是稳定的排序方法，并能说明原因。
三、选择排序
1、定义：从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为
空）的一端的方法，称为选择排序
2、堆排序：对于一个堆，按二叉树层次进行遍历不能得到一个有序序列。
四、交换排序
1、对n个不同的关键字由小到大进行冒泡排序，在从大到小排列好（倒序）
的情况下比较的次数最多，属于最坏的情况，其需要的时间是Ｏ（n2）。
在从小到大排列好（顺序）的情况下比较的次数最少。
2、快速排序算法思想及其应用，能写出每一趟排序的结果序列。
3、快速排序是否是稳定的排序方法，并能说明原因。
五、归并排序
1、对n个记录的集合进行归并排序，所需要的时间是O(nlog2n)。
六、例题分析与算法描述
1、插入排序
例1：给定一组关键字序列{15，25，10，40，25*，35，12，30，20，24，5},其中20和20*表示值相同的两个关键字，采用希尔排序方法由小到
大排序，dk依次取5，3，1。
（1）请写出排序过程（每趟排序的结果序列）。
（2）希尔排序是不是稳定的排序？为什么？
答：（1）每趟排序的结果序列为：
初态： 15，25，10，40，25*，35，12，30，20，24，5 第一趟（Dk=5）: 5，12，10，20，25*，15，25，30，40，24，35
第二趟（Dk=3）：5，12，10，20，25*，15，25，30，40，24，35
第三趟（Dk=1）：5，10，12，20，15，25*，25，24，30，35，40
最后得到的排序序列为：5，10，12，20，15，25*，25，24，30，35，40 （2）希尔排序不是稳定的排序，因为值相同的两个关键字25和25*在排序前后位置发生了改变。
例2：对序列{16，10，7，8，22，1，5}进行排序，进行一趟排序后，得到的排列为{10，16，7，8，22，1，5}，则采用的是（C ）排序算法。
A．简单选择 B. 希尔 C. 直接插入 D. 归并
2、堆排序
例1：若一组记录的排序码为（50，79，56，38，40，90），则利用堆排序的方法建立的初始堆为（90，79，50，38，40，46 ）。
例2：下列关键字序列中，（ D ）是堆。
A．16, 72, 31, 23, 94, 53 B．94, 23, 31, 72, 16, 53
C．16, 53, 23, 94，31, 72 D．16, 23, 53, 31, 94, 72
3、快速排序和冒泡排序
例1：若一组记录的排序码为（50, 79，56，38，40，85），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为：
40，38，50，56，79，85
例2：设有一个整型数组中存放了一个无序的序列k1、k2、…、kn。现要求将kn放在将元素排序后的正确位置上，要求比较关键字的次数不超过n。
则可用快速排序算法。
例3：设有一个整型数组中存放了一个序列k1、k2、…、kn。实现该序列的升序排列。要求：该算法在最好情况下（原始序列为升序时）一趟排序
能够结束，时间复杂度为O(n)。则可用冒泡排序算法。
例4：关键字序列为{20，14， 20*，33，87，22，2，10，72}，其中，18和18*表示两个值相等的关键字，采用快速排序算法由小到大进行排序，请
回答下面两个问题：
(1)写出排序过程（每趟排序后的关键字序列）。
(2)快速排序是不是稳定的排序算法？为什么？
答：（1）每趟排序结果
初始序列：[20，14， 20*，35，90，25，2，10，75]
第一趟：[10 14 20* 2] 20 [25 90 35 75]
第二趟：2 10 [20* 14] 20 25 [90 35 75]
第三趟：2 10 14 20* 20 25 [75 35] 90
第四趟：2 10 14 20* 20 25 35 75 90
最后得到的排序序列为：2 10 14 20* 20 25 35 75 90 （2）快速排序不是稳定的排序算法，因中相同的关键字20与20*在排序
前后，前后位置发生了改变。
4、排序算法
（1）快速排序（一个元素）
void sort(int K[]，int l，int n)
{
int i=l,j=n;
K[0] = K[j];
while(i { while(i K[j]=K[i]; while(i K[i]=K[j]; }//while K[i]=K[0]; } （2）、冒泡排序（一个泡） void Sort(int a[]，int n) { int m,i,j,flag=1; int t; for(i=1;flag&&i for(flag=0, j=1;j<= n-i; j++) if(r[j] > r[j+1]) { flag=1; t=r[j]; r[j]= r[j+1]; r[j+1]=t; } } （3）、直接插入排序 void Insertsort(SqList *L) { int i,j; for(i=2 ; i <= L->length ; i++) { L->r[0] = L->r[i]; for(j=i-1; L->r[0].key < L->r[j].key ; j-- ) L->r[j+1] = L->r[j]; L->r[j+1] = L->r[0]; } } （4）、希尔排序算法（其中某一趟的排序操作） void ShellInsert(SqList *L，int dk) { for(i=dk+1;i<=L->length; ++ i) if(L->r[i].key <= L->r[i-dk].key) { L->r[0]=L->r[i]; for(j=i-dk; j>0 &&(L->r[0].key L->r[j+dk]=L->r[0]； }} （5）、简单选择排序 void SelectSort(SqList *L) { for (i=1; i { //在L.r[i..L.length] 中选择key最小的记录 k=i; for( j=i+1;j<=L->length ; j++) if ( L->r[j].key if(k!=i)L.r[i]←→L.r[j]; } } //SelectSort 《数据结构》考试大纲 I.考查目标 考试目标是了解常见数据结构的概念，掌握数据结构的构造方法以及相应的算法思想，会对重点数据结构的操作方法和算法进行简单的伪代码编写。 II.考试形式和试卷结构 一、试卷总分及考试时间 试卷总分为150分，考试时间180分钟。 二、答题方式 答题方式为闭卷、笔试。 III．考查内容 第一章、线性表 1.线性表的逻辑结构 2.线性表的顺序存储结构 3.线性表的链式存储结构 3.1单链表 3.2循环链表 3.3双向链表 第二章、栈与队列 1.栈 1.1栈的基本概念 1.2顺序栈 1.3链式栈 2.队列 2.1队列的基本概念 2.2链队列 2.3循环队列——队列的顺序存储结构第三章、串 1.串类型的定义 2.字符串的实现 3.字符串模式匹配算法 3.1简单字符串模式匹配算法 3.2首尾字符串模式匹配算法 3.3KMP模式匹配算法 第四章、数组和广义表 1.数组 1.1数组的基本概念 1.2数组的顺序存储方式 2.矩阵 2.1矩阵的定义和操作 2.2特殊矩阵 2.3稀疏矩阵 3.广义表 3.1基本概念 3.2广义表的存储结构 第五章、树和二叉树 1.树的基本概念 1.1树的定义 1.2基本术语 2.二叉树 2.1二叉树的定义 2.2二叉树的性质 2.3二叉树的存储结构 3.二叉树的遍历 3.1遍历的定义 3.2遍历算法 4.树和森林 4.1树的存储表示 4.2森林的存储表示 4.3树和森林的遍历 4.4树和森林与二叉树的转换 5.哈夫曼树与哈夫曼编码 5.1哈夫曼树的基本概念 5.2哈夫曼树构造算法 5.3哈夫曼树编码 第六章、图 1.图的定义和术语 2.图的存储表示 2.1邻接矩阵 2.2邻接表 3.图的遍历 3.1深度优先搜索 3.2广度优先搜索 4.图的最小代价生成树 4.1Prim算法 4.2Kruskal算法 5.有向无环图的应用 5.1拓扑排序 5.2关键路径 6.最短路径问题 6.1单源点最短路径 6.2所有顶点之间的最短路径第七章、查找 南开大学物理化学专业考研大纲和复习经验 南开大学物理化学专业考研复习都是有依据可循的,考研学子关注事项流程为：考研报录比-大纲信息-参考书-资料-真题-复习经验-辅导-复试-导师。缺一不可，考研大纲会在九十月份发布，研友们不要着急，一定要耐心等待，可以参照去年的大纲先复习着，首先呢，南开大学物理化学专业下包含综合化学与物理化学（含结构化学），二者择其一。我个人的复习经验可以简单说一说，首先刚开始的时候，关注了一些考研公众号，在贴吧寻找经验，看到很多学长像我现在一样，分享着自己的考研经验，但是我很不擅长总结这种东西，一个理科生，原谅我吧。我会把该说的都说到。先列出大纲吧，再说一下我如何利用复习资料的，还有复习进度。 下面是南开大学物理化学专业综合化学考试大纲 一、考试目的 综合化学考试是为我校招收化学类、植物保护类专业的硕士研究生而设置的入学考试科目。 二、考试的性质与范围 本考试是测试考生化学水平的尺度参照性水平考试,考试范围包括本大纲规定的内容。 三、考试基本要求 要求考生比较系统地掌握在大学阶段在化学方面的基础理论，基本知识和基本技能，能综合运用所学知识分析问题、解决问题以及考查考生知识面的广度。 四、考试形式 本考试采取客观试题与主观试题相结合，单项技能测试与综合技能测试相结合的方法，强调考生运用化学基本原理解决问题的能力。 考试时间为180分钟，答题方式为闭卷考试（可以使用数学计算器）。 试卷满分150分，分四部分，其中无机化学40分，分析化学30分，有机化学40分，物理化学40分。 五、考试内容 本科目各部分考试内容，请对应参照科目无机化学、分析化学（不含仪器分析内容）、有机化学(化学学院)、物理化学（不含结构化学内容）的考试大纲。 下面是南开大学物理化学专业物理化学(含结构化学)考试大纲 一、考试目的本考试是化学学院全日制物理化学专业硕士学位研究生的入学资格考试之专业基础课。 二、考试的性质与范围本考试是测试考生物理化学（包括结构化学）水平的尺度参照性水平考试。考试范围包括本大纲规定的物理化学和结构化学内容。 三、考试基本要求 1.要求考生具备物理化学和结构化学相应的背景知识。 2.掌握物理化学和结构化学的基本原理，并能应用这些原理和思想方法处理、解决化学中的实际问题。 四、考试形式本考试采取客观试题与主观试题相结合，单项技能测试与综合技能测试相结合的方法，强调考生运用物理化学、结构化学基本原理解决问题的能力。试卷满分为150分，考试时间为180分钟。 五、考试内容本考试包括两个部分：物理化学（占70%）、结构化学（占30%）。 编程技术精品！ 991数据结构与C语言程序设计考试大纲（2013版） 2013年《数据结构与C语言程序设计》考试内容包括"数据结构"与"C语言程序设计"两门课程的内容，各占比例50%，试卷满分为150分。《数据结构》部分指定参考书：《数据结构教程（第二版）》唐发根编著北京航空航天大学出版社一、概述 1．数据的逻辑结构与存储结构的基本概念； 2．算法的定义、基本性质以及算法分析的基本概念，包括采用大?形式表示时间复杂度和空间复杂度。二、线性表 1．线性关系、线性表的定义，线性表的基本操作； 2．线性表的顺序存储结构与链式存储结构(包括单(向链表、循环链表和双向链表的构造原理； 3．在以上两种存储结构的基础上对线性表实施的基本操作，包括顺序表的插入与删除、链表的建立、插入与删除、查找等操作对应的算法设计(含递归算法的设计。三、堆栈与队列 1．堆栈与队列的基本概念与基本操作； 2．堆栈与队列的顺序存储结构与链式存储结构的构造原理； 3．在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作的算法设计； 4．堆栈和队列在解决实际问题中应用。四、树与二叉树 1．树与二叉树的基本概念，基本特征、名词术语； 2．完全二叉树与满二叉树的基本概念，二叉树的基本性质； 3．二叉树与树、树林之间的转换； 4．二叉树的顺序存储结构与二叉链表存储结构； 5．二叉树的前序遍历、中序遍历、后序遍历和按层次遍历，以及在二叉链表基础上各种遍历算法(重点为非递归算法的设计与应用； 6．二叉排序树的基本概念、建立(插入、查找与平均查找长度ASL 的计算； 7．哈夫曼(Huffman树的基本概念，哈夫曼树的构造与带权路径长度(WPL的计算。五、图 1．图的基本概念、名词术语； 2．图的邻接矩阵存储方法和邻接表(含逆邻接表存储方法的构造原理及特点； 3．图的深度优先搜索与广度优先搜索； 4．最小(代价生成树、最短路径、AOV网与拓扑排序以及AOE网与关键路径的基本概念与求解过程。六、文件及查找 1．顺序查找法以及平均查找长度(ASL的计算； 2．折半查找法以及平均查找长度(ASL的计算，包括查找过程对应的"判定树"的构造； 3．B-树和B+树的基本概念，B-树的插入与查找； 4．散列(Hash表的构造、散列函数的构造，散列冲突的基本概念、处理散列冲突的基本方法以及散列表的查找和平均查找长度的计算。七、内排序 1．排序的基本概念，各种内排序方法的基本 《结构化学》期末试卷（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π 628理论化学考试大纲 一、考试目的： 《理论化学》是2014年化学专业硕士研究生入学统一考试的科目之一。《理论化学》考试要力求反映化学专业硕士学位的特点，科学、公平、准确、规范地测评考生的专业基础素质和综合能力，以利于选拔具有发展潜力的优秀人才入学，为国家科技发展和经济腾飞培养综合素质高、复合型的化学专业人才。 二、考试要求： 考生应掌握本科目的基本概念和基础知识，具备对基本概念与基础知识的理解与综合运用能力。 三、考试形式和试卷结构： 《理论化学》试卷满分150分。其中，物理化学（含结构化学）合计100分为必答，另外50分可选择无机化学（50分）或分析化学（含化学分析及仪器分析）（50分）作答。答题方式为闭卷、笔试。答题时允许使用计算器。 四、考试内容： 物理化学（含结构化学）（100分） 该科目大纲共计十九章，其中第一至第十章考题占75分，第十一至第十九章（结构化学部分）考题占25分。 第一章热力学第一定律 1．热力学概论 1.1 热力学的目的、内容和方法 1.2 热力学基本概念：体系与环境，体系的性质；热力学平衡态和状态函数 2．热力学第一定律 2.1 热和功 2.2 热力学能 2.3 热力学第一定律的表述与数学表达式 3．体积功与可逆过程 3.1 等温过程的体积功 3.2 可逆过程与最大功 4．焓与热容 4.1 焓的定义 4.2 焓变与等压热的关系 4.3 等压热容和等容热容 5．热力学第一定律对理想气体的应用 5.1 理想气体的热力学能和焓 5.2 理想气体的Cp与Cv之差 5.3 理想气体的绝热过程 6．热力学第一定律对实际气体的应用 6.1 节流膨胀与焦耳-汤姆逊效应 7．热力学第一定律对相变过程的应用 8．化学热力学 8.1 化学反应热效应等压热效应与等容热效应；反应进度； 8.2 赫斯定律与常温下反应热效应的计算：赫斯定律；标准摩尔生成焓与标准摩尔燃烧焓 03 《数据结构》考试大纲 主要参考教材：严蔚敏、吴伟民编著，《数据结构（C语言版）》，清华大学出版社 谭国律等编著《数据结构》，浙江大学出版社。 总体要求： “数据结构”是一门专业技术基础课。目的就是要培养他们的数据抽象能力，学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及实现应用的相应算法，并掌握分析算法的时间和空间复杂度的技术。 考生在复习时，重点掌握基本概念、基本算法。考题以基本内容为主，题目以基础知识题为主，各章较难内容、较偏内容不考。课本所有加“*”号章节不考，第8章动态存储管理不考。外部排序，文件部分不考。 各章考试内容及要求： 一、绪论：熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之 间的关系；了解抽象数据类型的定义、表示和实现方法；熟悉类C语言的书写规范，特别要注意值调用和引用调用的区别，输入、输出的方式以及错误处理方式；理解算法五个要素的确切含义；掌握计算语句频度和估算算法时间复杂度的方法。 二、线性表：线性表的逻辑结构定义、抽象数据类型定义和各种存储结构的描述方法；在线 性表的两类存储结构（顺序存储和链式存储）上实现基本操作；一元多项式的抽象数据类型定义、表示及加法的实现。 三、栈和队列：栈和队列的结构特性；在两种存储结构上如何实现栈和队列的基本操作和栈 和队列在程序设计中的应用。（离散事件模拟不考） 四、串：串的数据类型定义；串的三种存储表示：定长顺序存储结构、块链存储结构和堆 分配存储结构；串的各种基本操作的实现及应用；串的朴素模式匹配算法。 五、数组：数组的类型定义和表示方法；特殊矩阵和稀疏矩阵的压缩存储方法及运算的实 现；（广义表不考）。 六、树和二叉树：二叉树的定义、性质和存储结构；二叉树的遍历和线索化以及遍历算法 的各种描述形式；树和森林的定义、存储结构、树和森林与二叉树的转换、遍历；树的多种应用；本章是该课程的重点内容之一。 七、图：图的定义和术语；图的邻接矩阵存储结构、邻接表存储结构：图的两种遍历策略： 深度优先搜索和广度优先搜索；图的最小生成树prim算法、Kruskal 算法；拓扑排序算法；单源最短路径问题的Dijstra 算法。 八、查找：讨论查找表（包括静态查找表和动态查找表）的各种实现方法：顺序表、有序表、 树表和哈希表；关于衡量查找表的主要操作——查找的查找效率的平均查找长度的讨论。（静态树表、平衡二叉树、B树不考） 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) 结构化学复习提纲 第一章量子力学基础 了解量子力学的产生背景?黑体辐射、光电效应、玻尔氢原子理论与德布罗意物质波假设以及海森堡测不准原理，掌握微观粒子的运动规律、量子力学的基本假设与一维势阱中粒子的Schr?dinger方程及其解。 重点：微观粒子的运动特征和量子力学的基本假设。一维势阱中粒子的 Schr?dinger方程及其解。 1. 微观粒子的运动特征 a. 波粒二象性：能量动量与物质波波长频率的关系 ε = hνp = h/λ b. 物质波的几率解释：空间任何一点物质波的强度(即振幅绝对值的平方)正比于粒子在该点出现的几率． c. 量子化（quantization）：微观粒子的某些物理量不能任意连续取值, 只能取分离值。如能量,角动量等。 d. 定态：微观粒子有确定能量的状态 玻尔频率规则：微观粒子在两个定态之间跃迁时，吸收或发射光子的频率正比于两个定态之间的能量差。即 e. 测不准原理: 不可能同时精确地测定一个粒子的坐标和动量(速度)．坐标测定越精确(?x =0)，动量测定就越不精确(?px = ∞)，反之动量测定越精确(?px =0)，坐标测定就越不精确 (?x = ∞) f. 微观粒子与宏观物体的区别: (1). 宏观物体的物理量连续取值；微观粒子的物理可观测量如能量等取分离值，是量子化的。(2). 微观粒子具有波粒二象性，宏观物体的波性可忽略。(3). 微观粒子适用测不准原理，宏观物体不必。(4). 宏观物体的坐标和动量可以同时精确测量，因此有确定的运动轨迹，其运动状态用坐标与动量描述；微观粒子的坐标和动量不能同时精确地测量，其运动没有确定的轨迹，运动状态用波函数描述。(5). 宏观物体遵循经典力学；微观粒子遵循量子力学。(6). 宏观物体可以区分；等同的微观粒子不可区分。 2017-2018学年大学结构化学期中考试试卷 注： 一、 选择题 (40分，每题2分) 1、下列分子中，非线性的是 （ ） A 、CO 2 B 、CS 2 C 、SO 2 D 、C 2H 2 2、按照价电子对互斥理论，ClF 3的稳定分子构型是 （ ） A 、三角双锥 B 、”T ”字型 C 、四面体 D 、三角形 3、以下为四个量子数(n, l, m, m s )的四种组合，合理的是 （ ） A 、2，2，0，-1/2 B 、2，1，0，-1/2 C 、2，1，2，+1/2 D 、2，0，1，1 4、已知[Fe(CN)6]3-是低自旋配合物，那么中心离子d 轨道的电子排布为 ( ) A 、t 2g 3e g 2 B 、.t 2g 2e g 3 C 、.t 2g 4e g 1 D 、t 2g 5e g 0 5、设想从乙烷分子的重叠构象出发,经过非重叠非交叉构象,最后变为交叉构象, 点群的变化是 ( ) A 、D 3→D 3h →D 3d B 、D 3h →D 3→D 3d C 、C 3h →C 3→C 3V D 、C 3h →D 3→C 3V 6、基态变分法的基本公式是 ( ) A 、 E ??H ≤∧ * *τ ψψτψψd d B 、 E ??H <∧ 0* *τ ψψτψψd d C 、 E ??H >∧ 0* *τ ψψτψψd d D 、 E ??H ≥∧ 0* *τ ψψτψψd d 7、按照分子轨道理论，下列微粒中最稳定的是 ( ) 学院-------------------------------------- 班级---------------------------------- 姓名------------------------------------- 学号 ------------------------------------ 一、考纲考点展示 《选修3：物质的结构与性质》高考试题中9种常考点 普通高等学校招生全国统一考试理科综合（化学部分）考试大纲的说明（节选） 必修2：物质结构和元素周期律 ①了解元素、核素和同位素的含义。 ②了解原子构成。了解原子序数、核电荷数、质子数、中子数、核外电子数以及它们之间的相互关系。 ③了解原子核外电子排布。 ④掌握元素周期律的实质。了解元素周期表（长式）的结构（周期、族）及其应用。 ⑤以第3周期为例，掌握同一周期内元素性质的递变规律与原子结构的关系。 ⑥以IA和VIIA族为例，掌握同一主族内元素性质递变规律与原子结构的关系。 ⑦了解金属、非金属在元素周期表中的位置及其性质递变的规律。 ⑧了解化学键的定义。了解离子键、共价键的形成。 选修3：物质结构与性质 1．原子结构与元素的性质 ⑴了解原子核外电子的排布原理及能级分布，能用电子排布式表示常见元素（1～36号）原子核外电 子、价电子的排布。了解原子核外电子的运动状态。 ⑵了解元素电离能的含义，并能用以说明元素的某些性质。 ⑶了解原子核外电子在一定条件下会发生跃迁，了解其简单应用。 ⑷了解电负性的概念，知道元素的性质与电负性的关系。 2．化学键与物质的性质 ⑴理解离子键的形成，能根据离子化合物的结构特征解释其物理性质。 ⑵了解共价键的形成，能用键能、键长、键角等说明简单分子的某些性质。 ⑶了解原子晶体的特征，能描述金刚石、二氧化硅等原子晶体的结构与性质的关系。 ⑷理解金属键的含义，能用金属键理论解释金属的一些物理性质。了解金属晶体常见的堆积方式。 ⑸了解杂化轨道理论及常见的杂化轨道类型（sp、sp2、sp3） ⑹能用价层电子对互斥理论或者杂化轨道理论推测常见的简单分子或者离子的空间结构。 3．分子间作用力与物质的性质 ⑴了解化学键和分子间作用力的区别。 ⑵了解氢键的存在对物质性质的影响，能列举含有氢键的物质。 ⑶了解分子晶体与原子晶体、离子晶体、金属晶体的结构微粒、微粒间作用力的区别。 ⑷能根据晶胞确定晶体的组成并进行相关的计算。 西安邮电大学硕士研究生招生考试大纲 科目代码：826 科目名称：《数据结构》 一、课程性质和任务 数据结构是计算机各专业的专业基础课。它是操作系统、数据库、编译原理等所有软件专业基础课和专业课的重要基础；它还是进行程序设计，尤其是进行高水平的应用程序和系统程序必不可少的基础。通过本课程的学习，使学生掌握数据组织、存储和运算的基本原理和方法，培养学生对各类数据结构和相关算法的分析和设计的能力，使学生能够编写出正确、清晰和较高质量的算法和程序。 二、课程教学内容和要求 第一章数据结构和算法 1.了解数据结构、逻辑结构、存储结构和抽象数据类型的基本概念。 2.了解数据结构的发展和地位。 3.了解各种算法描述方法和算法设计的基本要求。 4.掌握对算法的评价标准和算法效率的度量方法。 第二章线性表 1.理解线性表的概念、定义、逻辑结构和存储结构。 2.熟练掌握线性表的顺序结构及其各种基本运算。 3.熟练掌握单链表、循环链表、双向链表的存储结构及其各种基本运算。 4.理解链表的应用——稀疏多项式存储和运算。 第三章栈和队列 1.掌握栈的定义、表示、实现和应用。 2.掌握递归的概念和递归的实现过程。 3.掌握队列的定义以及顺序（循环队列）和链式存储结构的实现。 第四章串 1.了解串的基本概念及顺序和链式存储结构。 2.掌握串的各种基本运算。 3.了解串的模式匹配算法。 第五章数组和广义表 1.掌握数组的顺序存储结构。 2.理解稀疏数组的概念和压缩存储的方法。 3.理解稀疏矩阵的三元组存储结构和基本运算。 4.了解稀疏矩阵的十字链表存储结构。 5.理解广义表的基本概念，掌握广义表的存储结构。 第六章树 1.理解树的基本概念及其存储结构。 2.熟练掌握二叉树的定义、性质以及各种存储结构和遍历算法。 3.掌握线索二叉树的概念、存储结构及线索化算法。 4.掌握树和森林与二叉树间的转换，掌握树和森林的遍历算法。 5.掌握哈夫曼树的概念、存储结构和应用。 第七章图 1.理解图的基本概念，掌握图的邻接矩阵和邻接表的存储结构。 2.了解十字链表，邻接多重表等存储结构。 3.熟练掌握图的深度优先和广度优先遍历算法。 4.理解图的连通性、最小生成树的概念。 5.掌握求最小生成树算法。 6.理解有向无环图的概念，掌握拓扑排序和关键路径算法。 7.理解带权最短路径的概念，掌握求最短路径的算法。 第八章查找 1.理解查找的概念及其效率的评价方法。 2.理解静态查找表的概念，熟练掌握顺序、折半和分块查找算法。 3.理解动态查找表和二叉排序树的概念。 4.了解平衡二叉树的概念。 5.理解哈希表的含义，掌握哈希函数的构造和处理冲突的基本方法。第九章内部排序 1.掌握插入类排序的算法：直接插入排序、希尔排序。 2019年北京交通大学925《数据结构》考试大纲 1、绪论。 （1）掌握相关的基本概念，如数据结构、逻辑结构、存储结构、数据类型、抽象数据类型等； （2）掌握算法设计的原则，掌握计算语句频度和估算算法时间复杂度和空间复杂度的方法； （3）了解使用类C语言描述算法的方法。 2、线性表。 （1）掌握线性表的逻辑结构和存储结构； （2）掌握线性表在顺序结构和链式结构上实现基本操作的方法； （3）理解线性表两种存储结构的不同特点及其适用场合，会针对需求选用合适的存储结构解决实际问题； （4）了解一元多项式的表示方法和基本运算的实现方法。 3、栈和队列。 （1）了解栈和队列的特点； （2）掌握在两种存储结构上栈的基本操作的实现； （3）掌握栈的各种应用，理解递归算法执行过程中栈状态的变化过程；（4）掌握循环队列和链队列的基本运算； （5）会应用队列结构解决实际问题。 4、串。 （1）掌握串的基本运算的定义，了解利用基本运算来实现串的其它运算的方法； （2）了解在顺序存储结构和在堆存储结构以及块链存储结构上实现串的各种操作的方法； （3）理解KMP算法，掌握NEXT函数和改进NEXT函数的定义和计算。 5、数组和广义表。 （1）掌握数组在以行为主和以列为主的存储结构中的地址计算方法；（2）掌握矩阵压缩存储时的下标变换方法，了解以三元组表示稀疏矩阵的方法； （3）理解广义表的定义及其存储结构，理解广义表的头尾和子表两种分析方法。 6、树和二叉树。 （1）熟练掌握二叉树的结构特点和性质，掌握二叉树各种存储结构及 构建方法； （2）掌握按先序、中序、后序和层次次序遍历二叉树的算法，理解二叉树的线索化实质和方法； （3）利用二叉树的遍历求解实际问题； （3）掌握树的各种存储结构及其特点，掌握树的各种运算的实现算法；（4）掌握建立最优二叉树和哈夫曼编码的方法。 7、图。 （1）熟练掌握图的基本概念，会构建各种图的存储结构； （2）掌握深度优先搜索遍历图和广度优先搜索遍历图的算法； （3）灵活运用图的遍历算法求解各种路径问题，包括最小生成树﹑最短路径﹑拓扑排序﹑关键路径等。 南开大学物理化学考研大纲和参考书 大纲对于考研复习来说很重要，南开大学物理化学考研复习都是有依据可循的,考研学子关注事项流程为：考研报录比-大纲-参考书-资料-真题-复习经验-辅导-复试-导师。缺一不可，要按照专业课考研大纲的要求，结合学科特点，进行综合性总复习，总结线索，梳理结构，更好的规划自己的考研复习计划。 南开大学物理化学(含结构化学)考试大纲如下： 一、考试目的本考试是化学学院全日制物理化学专业硕士学位研究生的入学资格考试之专业基础课。 二、考试的性质与范围本考试是测试考生物理化学（包括结构化学）水平的尺度参照性水平考试。考试范围包括本大纲规定的物理化学和结构化学内容。 三、考试基本要求 1.要求考生具备物理化学和结构化学相应的背景知识。 2.掌握物理化学和结构化学的基本原理，并能应用这些原理和思想方法处理、解决化学中的实际问题。 四、考试形式本考试采取客观试题与主观试题相结合，单项技能测试与综合技能测试相结合的方法，强调考生运用物理化学、结构化学基本原理解决问题的能力。试卷满分为150分，考试时间为180分钟。 五、考试内容本考试包括两个部分：物理化学（占70%）、结构化学（占30%）。 一、物理化学部分 1.化学热力学热力学第一、二、三定律及其应用；各种变化过程（单纯pVT变化过程、相变化过程和化学变化过程）的方向和限度的判别、热力学函数增量及热和功的计算；组成恒定及组成变化的封闭体系的热力学基本方程及其应用；热力学基本原理在气体体系、多相体系、混合物及溶液体系、相平衡体系和化学平衡体系中的应用；相律及其应用；单组份体系、二组分体系相图的绘制及解析；克拉贝龙方程及杠杆规则的应用。 2.统计力学统计力学基本原理及玻尔兹曼分布定律在理想气体体系中的应用；理想气体热力学函数的统计力学计算；热力学定律的统计力学解释及相关计算。 3.化学动力学 具有简单级数的反应的特点；反应级数及速率方程的确定；各种因素对反应速率及速率常数的影响；复合反应的近似处理方法及其应用；根据反应机理推导速率方程；化学动力学 复习提纲 第一章数据结构概述 基本概念与术语（P3） 1．数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科. 2．数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合 2．数据元素是数据的基本单位 3．数据对象相同性质的数据元素的集合 4．数据结构包括三方面内容:数据的逻辑结构.数据的存储结构.数据的操作. （1）数据的逻辑结构指数据元素之间固有的逻辑关系. （2）数据的存储结构指数据元素及其关系在计算机内的表示 ( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等. 5.时间复杂度分析 -------------------------------------------------------------------------------------------------------------------- 1、名词解释：数据结构、二元组 2、根据数据元素之间关系的不同，数据的逻辑结构可以分为 集合、线性结构、树形结构和图状结构四种类型。 3、常见的数据存储结构一般有四种类型，它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。 4、以下程序段的时间复杂度为___O(N2)_____。 int i,j,x; for(i=0;i 西南大学结构化学期末考试试卷（ 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、下列函数是算符d2/dx2的本征函数的是：（）；本征值为：（）。 A、3x4 B、SinX C、x2e x D、x3 E、3 F、-1 G、1 H、2 3、单个电子的自旋角动量的值是：（） :12/2:6/2 C: 6/4 D:3/4 A 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 2 O) 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,θ,φ) 数据结构期末复习提纲（2012级） A、总体要求： 1、掌握数据结构的基本概念、基本原理和基本方法。 2、掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度和空间复杂度的分析。 3、能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用C语言和C++语言设计与实现算法的能力。 一、基本概念 1、数据结构、数据元素、数据项、数据类型、抽象数据类型、算法、算法的时间复杂度、算法的空间复杂度、算法的评价标准。 2、数据结构的逻辑结构和存储结构及分类。 3、线性表的定义及特点。 4、顺序表、单链表、双向链表、循环链表、静态链表的存储结构。 5、栈和队列的定义及特点。 6、顺序栈、链栈、顺序队列、链队列的存储结构。 7、字符串的定义及特点。 8、顺序串和链串的存储结构。 9、数组的定义及特点。 10、数组的按行存储与按列存储。 11、对称矩阵、三角矩阵、稀疏矩阵的压缩存储。 12、二叉树的定义、一般术语及特点。 13、二叉树的五个基本性质。 14、完全二叉树与满二叉树的概念。 15、二叉树的顺序存储结构。 16、二叉树的二叉链表与三叉链表存储结构。 17、二叉树的四种遍历方式及特点。 18、线索二叉树的存储结构及特点。 19、树和森林的概念。 20、树的双亲链表和孩子兄弟链表存储结构。 21、树和森林的二种遍历方式。 22、图的定义、一般术语及特点。 23、图的邻接矩阵、邻接表、逆邻接表存储结构。 24、图的二种遍历方式及特点、优先遍历生成树的概念。 25、图的连通性、连通图、连通分量的概念。 26、有向无环图的概念及特点。 27、查找、查找表、关键字的概念。 28、顺序查找、折半查找、分块索引查找的概念。 29、二叉排序树和平衡二叉树的定义及特点，平衡因子的概念。 30、B_树的定义及存储结构特点。 31、哈希函数、哈希表、哈希冲突、哈希查找的概念。 32、哈希表装填因子的定义及作用。 33、内部排序、外部排序、排序方法、传统排序和优化排序的概念。 34、希尔排序、快速排序、堆排序、归并排序、基数排序的概念。 35、排序方法的稳定性概念。 一、填空题（每空2分，共18分） 1能量为100eV 的自由电子的德布罗依波波长为、 cm. 2、氢原子的一个主量子数为n=3的状态有 个简并态。 3、He 原子的哈密顿算符为 4、氢原子的3Px 状态的能量为 eV 。角动量为 角动量在磁场方向的分量为 不确定 ；它有 1 个径向 节面， 1个角度节面。 5、氟原子的基态光谱项为 6、与氢原子的基态能量相同的Li 2+的状态为 3S ；3P ；3d ； 二、计算（共14分） 一维势箱基态l x l πψsin 2=，计算在2l 附近和势箱左端1/4区域内粒子出现的几率。 三、（共14分） 计算环烯丙基自由基的HMO 轨道能量。写出HMO 行列式；求出轨道能级 和离域能；比较它的阴离子和阳离子哪个键能大。 四、（共12分） 求六水合钴（钴2价）离子的磁矩（以玻尔磁子表示）、CFSE ，预测离子 颜色，已知其紫外可见光谱在1075纳米有最大吸收，求分裂能（以波数表示）。 五、（共10分） 金属镍为A1型结构，原子间最近接触间距为2.482m 1010 -?，计算它的晶 胞参数和理论密度。 六、（共14分） 3CaTiO 结晶是pm a 380=的立方单位晶胞，结晶密度4.103/cm g ，相对分子质量为 135.98，求单位晶胞所含分子数，若设钛在立方单位晶胞的中心，写出各原子的分数坐标。 七、简答题（每空3分，共18分） 1、原子轨道；分子轨道；杂化轨道； 2、电子填充三原则；杂化轨道三原则；LCAO-MO 三原则 一、 选择正确答案填空 1、原子轨道是指（ ） （A ）单电子运动的函数 （B ）单电子完全波函数 （C ）原子中电子的运动轨道 （D ）原子中单电子空间运动的状态函数 2、已知一维势箱中粒子的状态为a x x π?sin 2)(=，则粒子出现在4 a x =处几率P 为（ ） （A ）21 （B ）41 （D ）4a 3、具有100eV 能量的自由电子的德布罗意波波长为（ ） （A ）70.7pm （B ）122.5pm （C ）245pm （D ）35.4pm 4、在原子中具有相同主量子数，而不同状态的电子最多有（ ） （A ）2n 个 （B ）n 个 （C ）n 2个 （D ）2n 2个 5、如果氢原子的电离能为13.6eV ，则He +的电离能为（ ） （A ）13.6eV （B ）6.8eV （C ）54.4eV （D ）27.2eV 6、比较O 2和+ 2O 的分子轨道中的电子排布，可以发现（ ） （A ）两者结合能相同 （B ）O 2比+ 2O 结合能大 （C ）+ 2O 比O 2结合能大 （D ）O 2是单重态 7、CaF 2晶体中每个Ca 2+离子周围紧靠着的F -离子的数目为（ ） （A ）12个 （B ）8个 （C ）6个 （D ）4个 8、3种配合物：①-24HgI ②4)(CO Ni ③+ 262)(O H Mn 中有d-d 跃迁光谱的是（ ） （A ）① （B ）② （C ）③ （D ）②和③ 9、Li 原子基态能量最低的光谱支项是（ ） （A ）12P （B ）2/12S （C ）02P （D ）2/32 P 二、填空题 1、氢原子的一个主量子数为n=3的状态有 9 个简并态。 2、He 原子的哈密顿算符为 3、氢原子的3Py 状态的能量为 eV 。角动量为 角动量在磁场方向的分量为 ；它有 个径向节面， 个角度节面。 《数据结构》教学大纲 课程性质专业必修课 课程名称数据结构课程编号*04069 适用专业计算机科学与技术/软件工程开课学期第3学期 总学时64 理论50 学分数 4 实践14 一、课程性质与目标 数据结构课程属于专业必修课。通过本课程数据结构的学习，学生应实现如下目标： 1.知识目标：本课程主要讲述线性表、栈、队列、字符串、数组、树、二叉树、图、查找表、内部排序等常用数据结构的基本概念、操作及其典型应用例子。通过本课程的学习，应使学生掌握数据结构的概念及不同的存储结构、掌握一些典型算法原理和方法，且能够在不同存储结构上实现编程，同时，对于算法设计的方式和技巧也有所体会。 2.能力目标 （1）独立获取知识的能力——逐步掌握科学的学习方法，不断地扩展知识面，增强独立思考的能力，更新知识结构； （2）科学观察和思维的能力——运用数据结构的基本理论，熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构。 （3）分析问题和解决问题的能力——学会利用数据结构原理分析实际问题，提高发现问题与解决问题的能力。对部分优秀的学生，培养其在知名程序设计在线评测系统（如POJ等）中求解实际问题的能力。 （4）求实精神——通过数据结构理论课程教学，培养学生严谨求实的科学态度和刻苦钻研的作风。 （5）实践能力——通过学习，有意识地培养学生编写高质量、高效率程序的能力和风格。 3.素质目标：使学生具备一定的计算思维，热爱算法设计和程序实现，面对实际问题能转换为计算机能够求解的过程并选择合适的数据结构，设计出在时间和空间上具备一定高效率的程序，培养学生学习算法设计与实现的细心和耐心，培养学生坚韧不拔，攀登技术高峰的优秀品质。让部分优秀的学生热爱上湖南省大学生程序设计竞赛，体会ACM程序设计竞赛的魅力。 二、课程教学基本要求 课程前应该认真预习，特别是前导课程相关知识体系; 课中应该认真听课，参与教学过程中的互动、回答问题及联系实际编程; 课后积极做好复习、认真完成作业及课程设计相关实践教学的环节。作业应具备一定实用性的数据结构和算法实现为主，对部分优秀学生，引入一定量的知名程序设计在线评测系统（如POJ等）中与数据结构相关的题目进行编程并在线提交验证正确性与时间、空间效率。 三、教学内容与学时分配 《数据结构》考试大纲 I 考试的性质与目的 本科插班生考试是由专科毕业生参加的选拔性考试。《数据结构》是计算机科学与技术专业（本科）的一门专业基础课程，考试主要检查考生对常用基本数据结构（顺序表、链表、栈、队列、树、二叉树、图等）的存储组织、维护操作、基本应用，以及查找、排序等基本算法的掌握程度，以保证后续课程的学习。 II 考试的内容 一、考试基本要求 1、基本理论知识 （l）、数据结构的基本概念和基本术语，算法的描述方法和算法分析的基本概念。 （2）、线性表的基本概念、线性表的基本操作以及这些操作分别在顺序存储和链式存储结构下的实现及复杂度分析。 （3）、栈和队列的定义、存储结构、实现和典型应用。 （4）、串的定义及其基本操作。 （5）、数组的定义、运算和存储。 （6）、树的定义、基本术语和存储结构，二叉树的定义和性质、二叉树的存储结构及其各种操作，哈夫曼树的概念和应用。 （7）、图的定义和术语、图的存储结构及其基本操作。 （8）、各种查找方法的算法、适用范围及时间复杂度的分析。 （9）、多种内排算法的基本思想和算法的时间复杂度分析，不同排序方法的比较。 2、基本技能 （1）、能用基本数据结构及其算法描述、解决实际的较为简单的问题。 （2）、能阅读“类C”语言编写的算法，能根据要求用“类C”语言编写算法。 （3）、能分析算法所完成的功能、运行结果和时间复杂度。 二、考核知识点及考核要求 第一章绪论 一、考核知识点 1.数据、数据元素、数据项、数据对象、数据结构、逻辑结构、物理结构、元素、结点等基本概念。抽象数据类型的定义、表示和实现方法。 2.算法、算法的特性、如何用类C语言来描述算法。 3.算法设计的基本要求以及计算语句频度和估算算法时间复杂度的方法。 二、考核要求 1.识记：有关数据结构的基本概念，四种基本数据结构的特点。 2.理解：四种基本数据结构的基本运算，算法复杂度度量的基本概念。 3.应用：用类C语言描述算法 第二章线性表 一、考核知识点数据结构与算法考试大纲
南开大学物理化学专业考研大纲和复习经验
991数据结构与C语言程序设计考试大纲(2013版).
结构化学期末试卷(A卷)
2017年山东大学山大理论化学考试大纲
《数据结构》课程考试大纲
结构化学期末试卷及答案
结构化学复习提纲(精心整理)
2017-2018学年大学结构化学期中考试试卷
结构化学 选修3知识点总结(人教版)全国卷适用
2018西安邮电大学初试考试大纲—826数据结构
2019 北京交通大学 925《数据结构》 考试大纲
南开大学物理化学考研大纲和参考书
数据结构复习提纲(整理)
结构化学期末考试试卷( C )
数据结构期末试题提纲
结构化学期末试题
数据结构课程教学大纲
数据结构》考试大纲
相关主题
文本预览