数据结构复习提纲
复习内容：
基本概念掌握：数据结构，逻辑结构，存储结构；数据类型；算法；T（n），S（n）的理解。
要学习的数据结构定义形式：
n（n>=0）个数据元素的有限集合。
将约束：1、数据元素本身。2、数据元素之间的关系。3、操作子集。
大多有两种存储（表示、实现）方式：1、顺序存储。2、链式存储。
一、线性结构：
1、线性表：n（n>=0）个相同属性的数据元素的有限序列。12种基本操作。
顺序表：9种基本操作算法实现。单链表：11种基本操作算法实现。（重点：插入、删除）
顺序表与单链表之时间性能、空间性能比较。
循环链表：类型定义与单链表同。算法实现只体现在循环终止的条件不同。
双向链表：重点插入、删除算法。
2、操作受限的线性表有：栈、队列。
栈：顺序栈；链栈（注意结点的指针域指向）。（取栈顶元素、入栈、出栈）
队列：循环队列（三个问题的提出及解决）；链队列（注意头结点的作用）。（取队头元素、入队、出队。链队列中最后一个元素出队）
3、数据元素受限的线性表有：串、数组、广义表。
串：定长顺序存储；堆分配存储。块链存储（操作不方便）
数组：顺序存储。特殊矩阵的压缩存储；稀疏矩阵（三元组表示、十字链表）
广义表：长度、深度。取表头（可以是原子也可以是子表）；取表尾（肯定是子表）。链式存储。
二、树型结构：
1、树：n（n>=0）个数据元素的有限集合。这些数据元素具有以下关系：……。（另有递归定义。）
术语；存储（双亲表示、孩子表示、孩子双亲表示、孩子兄弟表示）。
2、二叉树：n（n>=0）个数据元素的有限集合。这些数据元素具有以下关系：……。（另有递归定义）
5个性质（理解、证明；拓展）。遍历二叉树（定义、序列给出、递归算法、非递归算法）；遍历二叉树应用：表达式之前序表达式、后序表达式、中序表达式转换。
线索二叉树（中序线索二叉树）。树森林与二叉树的转换。树与森林的遍历。
赫夫曼树及其应用：定义、构造、赫夫曼编码。
三、图形结构：n（n>=0）个数据元素的有限集合。这些数据元素具有以下关系：……。
术语掌握。
存储结构（数组表示法、邻接表；无向图的邻接多重表）。
图的遍历及应用：无向图的最小生成树（普里姆算法、克鲁斯卡尔算法）；拓扑排序、关键路径。
四、查找（查找表）：相关概念掌握。
静态查找表：顺序表的查找；有序表的查找；
动态查找表：二叉排序树、A VL树的定义及调整。
哈希表：定义及概念；HASH函数；
五、内部排序：概念掌握。
插入排序：直接插入排序、折半插入排序、希尔排序
交换排序：起泡排序、快速排序
选择排序：冒泡、简单选择排序
归并排序（外部排序基础）
基数排序（链式基数排序）
要求：1、排序算法。2、各种排序算法的O（n）、稳定性。
模拟卷
一、填空题
1、在用于表示有向图的邻接矩阵中，对第i行的元素进行累加，可得到第i 个顶点的（出）度，而对第j列的元素进行累加，可得到第j个顶点的（入）度。
2、一个连通图的生成树是该图的（极小）连通子图。若这个连通图有n个顶点，则它的生成树有（N-1）条边。
3、对算法从时间和空间两方面进行度量，分别称为（）、（）分析。
4、二叉树第i层上最多有（ 2i-1 ）个结点。一个二叉树中每个结点最多只有（ 2 ）个孩子。
5、一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有（）个。
6.设一棵二叉树结点的先根序列为A BDECFGH，中根序列为DEBAFCHG，则二叉树中叶子结点是（）
7.设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该容纳（ 4 ）个元素。
8、循环队列判断队满的条件为（）。
9、将两个长度分别m和n(m>n)的排好序的表归并成一个排好序的表，至少要进行（n ）次键值比较。
10. 已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为((2+NK-2N)/K。)。
度：一个结点含有的子树的个数称为该节点的度；
公式：一个有限图中，各点的度数总和是边数的2倍；而树中的边数为点数减1。
设有x个叶节点，那么分支节点数为N-x
各点度数总和为：x*0+(N-x)*K=2*(N-1);
最后计算得到叶节点个数为(2+NK-2N)/K。
11. 采用散列技术实现散列表时，需要考虑的两个主要问题是：构造( )和解决( )。
12. 试计算下面程序段时间复杂度( )。
for(i = 1; i <= n; i++)
for(j = 1; j<=i; j++)
x = x + delta;
13. 已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有( )个叶子结点。
出度＝入度。
一个结点的度是指它的儿子结点的个数，因此实际是指它的出度。而每个结点的入度有且仅有一个（根结点入度为0，除外）。叶子结点的出度为0。据此可得：
入度＝结点个数－1；设叶子结点数为X个，则根据题意，
入度＝X＋4＋2＋2＋1－1＝X＋8；
出度＝0×X＋1×4＋2×2＋3×2＋4×1＝18；（结点×结点度数）
故X＋8＝18 X＝10；
14. G是一个非连通无向图，共有28条边，则该图至少有( 9 )个顶点。
假设有8个顶点,则8个顶点的无向图最多有28条边且该图为连通图
连通无向图构成条件:边=顶点数*(顶点数-1)/2
顶点数>=1,所以该函数存在单调递增的单值反函数
所以边与顶点为增函数关系
所以28个条边的连通无向图顶点数最少为8个
所以28条边的非连通无向图为9个(加入一个孤立点)
15. 己知有序表为(12,18,24,35,47,50,62,83,90,115，134)，当用折半查找方法查找90时，需比较( )次查找成功，47需比较( )次查找成功，查100时，需比较_( )次才能确定不成功。
二、选择题：
1.下列有关线性表的叙述中，正确的是(a )
A、线性表中的元素之间隔是线性关系
B、线性表中至少有一个元素
C、线性表中任何一个元素有且仅有一个直接前趋
D、线性表中任何一个元素有且
仅有一个直接后继
2.分别用front和rear表示顺序循环队列的队首和队尾指针,则判断队空的条件是___.
A.front+1==rear
B.(rear+1) % maxSize == front
C.front==0
D.front==rear
3.下列关于串的叙述中，正确的是( )
A、一个串的字符个数即该串的长度
B、一个串的长度至少是1
C、空串是由一个空格字符组成的串
D、两个串S1和S2若长度相同，则这两个串相等
4.设结点x和结点y是二叉树T中的任意两个结点，若在先根序列中x在y之前，而在后根序列中x在y之后，则x和y的关系是( )
A、x是y的左兄弟
B、x是y的右兄弟
C、x是y的祖先
D、x是y的后代
5. 广义表A=( a, b, ( c, d ), ( e, ( f, g ) ) ),则Head( Tail( Head( Tail( Tail( A ) ) ) ) ) 的值为.
A. (g)
B. (d)
C. c
D. d
6. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（）
A. 2 3 4 1 5
B. 5 4 1 3 2
C. 2 3 1 4 5
D. 1 5 4 3 2
7. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ D ）
A．250 B．500 C．254 D．501
对于满二叉树来讲，高度为9得总结点数是511个，高度为10得总结点数是1023个。
这样题目中要求的完全二叉树应是高度为10的完全二叉树，完全二叉树的叶结点在最
下面两层，本题中就是在第9、第10两层出现。
第10层叶结点数目是：1001-511=490（即总结点数-前9层结点的总数目）。
第9层叶结点数目是：对于满二叉树，第10层的结点数应该是512个，而现在的完全
二叉树的第10层有490个结点，相对于完全二叉树少了22个结点，少的这22个结点将
导致第9层出现22/2=11个叶结点。
所以这棵完全二叉树得总的叶子结点数是：490+11=501。
8. 三维数组A[5][6][7]按行优先存储方法存储在内存中，若每个元素占2个存储单元，数组元素下标从0开始，且数组中第一个元素的存储地址为120，则元素A[4][4][5]的存储地址为（）
A. 518
B. 520
C. 522
D. 524
9. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则
利用（ C ）存储方式最节省时间。
A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表选择C，明显带头节点的双向链表，查找尾元素最简单。这样插入元素最为方便。
10. 在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为（A）
A. n-i+1
B. n-i
C. i
D. i-1
(1)顺序表中访问任意一个结点的时间复杂度均为0（1）
(2)在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为0（n）.
(3)在一个长度为n的顺序表中删除第i个元素，要移动n-i个元素。
(4)在一个长度为n的顺序表，如果要在第i个元素前插入一个元素，要后移
n-i+1。
(5)等概率情况下，在有n个结点的顺序表上做插入结点运算，需平均移动结点的数为n/2.
(6)等概率情况下，在有n个结点的顺序表上做删除结点运算，需平均移动结点的数目为(n-1)/2.
11. 已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结
果为（）。
A．CBEFDA B．FEDCBA C．CBEDFA D．不定
已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历是什么？先序遍历的第一个结点是根结点，所以A是根，然后在中序遍历中找到A，（DBGE）A（CHF），由中序遍历的定义知（DBGE）是左子树的中序遍历，（CHF）是右子树的中序遍历。然后在先序遍历中把左子树和右子树划开，A（BDEG）（CHF），所以B是左子树根，C是右子树根。然后继续在中序遍历中找到B和C，（（D）B（GE））A（C（HF））。对于DBEG，B是根，D是左子树，EG是右子树的中序遍历，对于CHF，C是根，H F是右子树的中序遍历。因为仍然有没划分完的部分，所以继续看先序。对于BDEG，B是根已知，D是整个左子树已知，所以EG是右子树的先序遍历，E是右根，再对照中序可知G是E 的左子树，CHF同理。
所以树的结构是A（B（D，E（G，）），C（，F（H，）））
把它画成图，后序遍历就是DGEBHFCA
12. 一个n个顶点的连通无向图，其边的个数至少为（A ）。
A．n-1 B．n C．n+1 D．nlogn
13. 下面关于折半查找的叙述正确的是( )
A. 表必须有序，表可以顺序方式存储，也可以链表方式存储
B. 表必须有序，而且只
能从小到大排列
C. 表必须有序且表中数据必须是整型，实型或字符型
D. 表必须有序，且表只
能以顺序方式存储
14. 以下哪个是不稳定的排序方法。( )
A．起泡排序B．归并排序C．Shell排序D．直接插入排序
15. n 个权构成一棵Huffman树，其节点总数为：（）
A、2n-1
B、2n
C、2n+1
D、不确定
三、应用题：
1. 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。
void reverse(pointer h)
/* h为附加头结点指针；类型pointer包括一个数据域data＆一个指针域next*/
{
pointer p, q;
p=h->next;
h->next=NULL;
while( P!=NULL )
{
q=p; p=p->next; q->next=h->next;
h->next= q ;
}
}
2．在带头结点的head单链表的结点a之后插入新元素x
struct node
{ elemtype data;
node *next;
};
void lkinsert (node *head, elemtype x)
{ node *s, *p;
s= ;
s->data= ;
p=head->next;
while (p!=NULL) &&( p->data!=a )
;
if (p==NULL)
cout<<“不存在结点a”;
else { ;
;}}
3、
写出3种拓扑排序的序列
4、快速排序
void qksort (int R[], int p, int q)//按递增序对R[p]～R[q]进行快速排序
{ int i=p, j=q;
R[ 0 ]=R [i ]; //R[0]作临时单元
while ( )
{
while (j>i )&&( R[ j ] R[ 0 ]) j- -;
if (j>i)
{ R[ i ]=R[ j ]; i++;}
while (i if (i }; R[ i ]= ; i++; j--; if (j>p) qksort(R,p,j); if (i } 5. 设有一组关键字{19,01,23,14,55,20,84,27,68,11,10,77}，采用散列函数：H(key) = key MOD 13，采用线性探测法解决冲突，试在0～18的散列地址空间中对该关键字序列构造散列表。H(19)=19%13=6 H(01)=1%13=1 H(23)=23%13=10 H(14)=14%13=1 H(55)=55%13=3 H(20)=20%13=7 H(84)=84%13=6 H(27)=27%13=1 H(68)=68%13=3 H(11)=11%13=11 H(10)=10%13=10 H(77)=77%13=12 6 有一份电文中共使用五个字符：a、b、c、d、e，它们的出现频率依次为8、6、10、4、7，请构造相应的哈夫曼树（要求：左子树根结点的权小于等于右子树根结点的权），求出每个字符的哈夫曼编码。 6. 画出下图的一棵最小生成树，并写出其邻接矩阵。 四、综合设计题： 1、2叉排序树构造过程 2、关键路径（如课件例题） 3、排序算法。 4．在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如：（7，10，10，21，30，42，42，42，51，70）将变作（7，10，21，30，42，51，70） 复习提纲 第10章 1、建筑结构以室外地面为界分为上部结构和下部结构，上部结构分为水平结构和竖向结构。 2、结构类型分类：①按结构材料分为：砌体结构、混凝土结构、钢结构、组合结构、混合结构。②按竖向结构体系分为：排架结构、框架结构、剪力墙结构、框架-剪力墙结构、筒体结构。 3、①工程建设的三个环节：勘察、设计、施工。②结构设计的三个阶段：初步设计、技术设计、施工图设计。③建筑结构设计的一般原则：安全、适用、耐久、经济合理。 4、①作用——使结构产生内力或变形的原因，分为直接作用和间接作用。②作用效应（荷载效应）——结构上的作用使结构产生的内力、变形、裂缝等。 5、荷载分类：①按时间分为：永久、可变、偶然。②按空间分为：固定、移动。 ③按反应分为：静力、动力。 6、设计基准期：一般结构的设计适用年限50年作为规定荷载最大值的时域。 7、荷载代表值：①标准值——在结构的适用期间（一般结构的设计基准期为50年）可能出现的最大荷载值。②组合值——有两种以上可变荷载同时作用。③频遇值——在设计基准期内，其超越的总时间为规定的较小比率，或超越频率为规定频率的荷载值。④准永久值——在设计基准期内，其超越的总时间约为设计基准期一半的荷载值。 8、竖向荷载分为恒载和活载，屋面活荷载不与雪荷载同时组合。 9、①基本雪压：根据年最大雪压进行统计分析确定，在我国，基本雪压是以一般空旷平坦地面上统计的50年一遇重现期的最大积雪自重给出的。②屋面积雪分布系数：屋面水平投影面积上的雪荷载与基本雪压的比值。与屋面形式、朝向及风力有关。 10、①风荷载：由压力、吸力、横风向干扰力和合力构成。②基本风压以当地空旷平坦地面上高出错误!未找到引用源。的平均风速观测数据，经概率统计得到的50年一遇的最大风速，按计算得到。不得小于0.3。风速受高度、地面粗糙度影响，。 11、结构的设计使用年限：指设计规定的结构或结构构件不需进行大修即可按其预定目的使用的时期。一般为50年。 12、建筑结构的功能：①安全性——建筑结构应能承受正常施工和正常使用时可能出现的各种荷载和变形，在偶然事件发生时和发生后保持其整体稳定性。②适用性——结构在正常使用过程中应具有良好的工作性能，不产生影响使用的过大变形或振幅，不发生足以让使用者不安的过宽裂缝。③耐久性——结构在正常维护条件下应有足够的耐久性，完好使用到设计使用年限。 1.一元稀疏多项式计算器 [问题描述] 设计一个一元稀疏多项式简单计算器。 [基本要求] 输入并建立多项式； 输出多项式，输出形式为整数序列：n, c1, e1, c2, e2,……, cn, en ，其中n是多项式的项数，ci, ei分别是第i项的系数和指数，序列按指数降序排序； 多项式a和b相加，建立多项式a+b; 多项式a和b相减，建立多项式a-b; [测试数据] (2x+5x8-3.1x11)+(7-5x8+11x9)=(-3.1x11+11x9+2x+7) (6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2-x2+7.8x15)=(-7.8x15-1.2x9-x+12x-3) (1+x+x2+x3+x4+x5)+(-x3-x4)=(x5+x2+x+1) (x+x3)+(-x-x3)=0 (x+x2+x3)+0=(x3+x2+x) [实现提示] 用带头结点的单链表存储多项式，多项式的项数存放在头结点中。 2.背包问题的求解 [问题描述] 假设有一个能装入总体积为T的背包和n件体积分别为w1, w2, …,wn的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1+w2+…+wn=T，要求找出所有满足上述条件的解。例如：当T=10，各件物品的体积为{1，8，4，3，5，2}时，可找到下列4组解：（1，4，3，2）、（1，4，5）、（8，2）、（3，5，2） [实现提示] 可利用回溯法的设计思想来解决背包问题。首先，将物品排成一列，然后顺序选取物品转入背包，假设已选取了前i件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品“太大”不能装入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入背包的那件物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，直至求得满足条件的解，或者无解。 由于回溯求解的规则是“后进先出”因此自然要用到栈。 3.完全二叉树判断 用一个二叉链表存储的二叉树，判断其是否是完全二叉树。 4.最小生成树求解（1人） 任意创建一个图，利用克鲁斯卡尔算法，求出该图的最小生成树。 5.最小生成树求解（1人） 任意创建一个图，利用普里姆算法，求出该图的最小生成树。 6.树状显示二叉树 编写函数displaytree(二叉树的根指针，数据值宽度，屏幕的宽度)输出树的直观示意图。输出的二叉树是垂直打印的，同层的节点在同一行上。 [问题描述] 假设数据宽度datawidth=2,而屏幕宽度screenwidth为64=26,假设节点的输出位置用 （层号，须打印的空格数）来界定。 第0层：根在（0，32）处输出； 校园基础地理空间数据库建设设计方案 遥感1503班第10组 （杨森泉张晨欣杨剑钢熊倩倩） 测绘地理信息技术专业 昆明冶金高等专科学校测绘学院 2017年5月 一．数据来源 二. 目的 三 .任务 四. 任务范围 五 .任务分配与计划六．小组任务分配七. E-R模型设计八．关系模式九．属性结构表十．编码方案 一．数据来源 原始数据为大二上学期期末实训数字测图成果（即DWG格式的校园地形图） 导入GIS 软件数据则为修改过的校园地形图 二．目的 把现实世界中有一定范围内存在着的应用数据抽象成一个数据库的具体结构的过程。空间数据库设计要满足用户需求，具有良好的数据库性能，准确模拟现实世界，能够被某个数据库管理系统接受。 三．任务 任务包括三个方面：数据结构、数据操作、完整性约束 具体为： ①静态特征设计——结构特性，包括概念结构设计和逻辑结构设计； ②动态特性设计——数据库的行为特性，设计查询、静态事务处理等应用程序； ③物理设计，设计数据库的存储模式和存储方式。 主要步骤：需求分析→概念设计→逻辑设计→物理设计 原则：①尽量减少空间数据存储冗余；②提供稳定的空间数据结构，在用户的需要改变时，数据结构能够做出相应的变化；③满足用户对空间数据及时访问的需求，高校提供用户所需的空间数据查询结果；④在空间元素间为耻复杂的联系，反应空间数据的复杂性；⑤支持多种决策需要，具有较强的应用适应性。 四、任务范围 空间数据库实现的步骤、建库的前期准备工作内容、建库流程 步骤：①建立实际的空间数据库结构；②装入试验性数据测试应用程序；③装入实际空间数据，建立实际运行的空间数据库。 前期准备工作内容：①数据源的选择；②数据采集存储原则；③建库的数据准备；④数据库入库的组织管理。 建库流程：①首先必须确定数字化的方法及工具；②准备数字化原图，并掌握该图的投影、比例尺、网格等空间信息；③按照分层要求进行 03 《数据结构》考试大纲 主要参考教材：严蔚敏、吴伟民编著，《数据结构（C语言版）》，清华大学出版社 谭国律等编著《数据结构》，浙江大学出版社。 总体要求： “数据结构”是一门专业技术基础课。目的就是要培养他们的数据抽象能力，学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及实现应用的相应算法，并掌握分析算法的时间和空间复杂度的技术。 考生在复习时，重点掌握基本概念、基本算法。考题以基本内容为主，题目以基础知识题为主，各章较难内容、较偏内容不考。课本所有加“*”号章节不考，第8章动态存储管理不考。外部排序，文件部分不考。 各章考试内容及要求： 一、绪论：熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之 间的关系；了解抽象数据类型的定义、表示和实现方法；熟悉类C语言的书写规范，特别要注意值调用和引用调用的区别，输入、输出的方式以及错误处理方式；理解算法五个要素的确切含义；掌握计算语句频度和估算算法时间复杂度的方法。 二、线性表：线性表的逻辑结构定义、抽象数据类型定义和各种存储结构的描述方法；在线 性表的两类存储结构（顺序存储和链式存储）上实现基本操作；一元多项式的抽象数据类型定义、表示及加法的实现。 三、栈和队列：栈和队列的结构特性；在两种存储结构上如何实现栈和队列的基本操作和栈 和队列在程序设计中的应用。（离散事件模拟不考） 四、串：串的数据类型定义；串的三种存储表示：定长顺序存储结构、块链存储结构和堆 分配存储结构；串的各种基本操作的实现及应用；串的朴素模式匹配算法。 五、数组：数组的类型定义和表示方法；特殊矩阵和稀疏矩阵的压缩存储方法及运算的实 现；（广义表不考）。 六、树和二叉树：二叉树的定义、性质和存储结构；二叉树的遍历和线索化以及遍历算法 的各种描述形式；树和森林的定义、存储结构、树和森林与二叉树的转换、遍历；树的多种应用；本章是该课程的重点内容之一。 七、图：图的定义和术语；图的邻接矩阵存储结构、邻接表存储结构：图的两种遍历策略： 深度优先搜索和广度优先搜索；图的最小生成树prim算法、Kruskal 算法；拓扑排序算法；单源最短路径问题的Dijstra 算法。 八、查找：讨论查找表（包括静态查找表和动态查找表）的各种实现方法：顺序表、有序表、 树表和哈希表；关于衡量查找表的主要操作——查找的查找效率的平均查找长度的讨论。（静态树表、平衡二叉树、B树不考） 第一章数据结构概述 基本概念与术语 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 ) 课程设计说明书 课程名称：数据结构 专业：班级： 姓名：学号： 指导教师：成绩： 完成日期：年月日 任务书 题目：黑白棋系统 设计内容及要求： 1.课程设计任务内容 通过玩家与电脑双方的交替下棋，在一个8行8列的方格中，进行棋子的相互交替翻转。反复循环下棋，最后让双方的棋子填满整个方格。再根据循环遍历方格程序，判断玩家与电脑双方的棋子数。进行大小判断，最红给出胜负的一方。并根据y/n选项，判断是否要进行下一局的游戏。 2.课程设计要求 实现黑白两色棋子的对峙 开发环境：vc++6.0 实现目标： （1）熟悉的运用c语言程序编写代码。 （2）能够理清整个程序的运行过程并绘画流程图 （3）了解如何定义局部变量和整体变量； （4）学会上机调试程序，发现问题，并解决 （5）学习使用C++程序来了解游戏原理。 （6）学习用文档书写程序说明 摘要 本文的研究工作在于利用计算机模拟人脑进行下黑白棋，计算机下棋是人工智能领域中的一个研究热点，多年以来，随着计算机技术和人工智能技术的不断发展，计算机下棋的水平得到了长足的进步 该程序的最终胜负是由棋盘上岗双方的棋子的个数来判断的，多的一方为胜，少的一方为负。所以该程序主要运用的战术有削弱对手行动战术、四角优先战术、在游戏开局和中局时，程序采用削弱对手行动力战术，即尽量减少对手能够落子的位置；在游戏终局时则采用最大贪吃战术，即尽可能多的吃掉对手的棋子；而四角优先战术则是贯穿游戏的始终，棋盘的四角围稳定角，不会被对手吃掉，所以这里是兵家的必争之地，在阻止对手进角的同时，自己却又要努力的进角。 关键词：黑白棋；编程；设计 复习提纲 第一章数据结构概述 基本概念与术语（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、简述世界包装组织（WPO）的“世界之星”包装大奖评奖标准。 答：由世界包装组织（WPO）一年一度颁发的“世界之星”包装大奖评奖标准如下：保护内装物；方便携带、装填、封闭、开启和再封；销售吸引力；图案设计；必要的信息；产品的质量；材料经济性、成本降低、环境责任、可回用性；结构新颖；地域特色；技术创新 2、怎样学习包装结构设计？ 答：在学习包装结构设计之前，应全面了解包装材料、包装机械及包装工艺等其他方面的知识，掌握造型和装潢设计的基本知识和基本技能，具备一定的审美情趣和鉴赏能力。 在包装结构设计课程学习中，要不断加强立体空间物体的想象能力，特别是纸、箔、膜类由平面到立体成型的包装结构，必须掌握2D到3D之间的相互思维转换。同时要加强实践环节的练习，多模仿，多设计，多思考，多创新。通过融知识学习、能力培养和素质提高为一体，理论与实践相结合的学习方法，培养提出问题、分析问题和解决问题的能力，尤其注重培养动手能力和创新能力。任何一种结构都是科技进步的产物，必然留下时代的烙印，可以从中发现历史的局限，所以需要用批判的眼光认真地审视它们，改正缺陷，修补不足，就可能设计出一种创新的结构。总之，拓宽思路，注重实践，加强创新，才能在包装结构设计中有所建树。 3、请用绘图线型画出（1）纸箱（盒）的轮廓线（2）用于区域开槽切断的开槽线（3）用于盒盖装饰波纹切断的软边裁切线（4）内折压痕线（5）外折压痕线（6）内折切痕线（7）外折切痕线（8）对折压痕线（9）打孔线（10）撕裂打孔线答：见表2-1（此略） *4、什么是内折、外折与对折？ 答：在折叠压痕线中，内折、外折和对折可以这样理解：不论是普通纸板还是瓦楞纸板均具有两面性，普通纸板有面层和底层、瓦楞纸板有外面纸盒内面纸之分。一般情况下，纸板面层或瓦楞纸板外面纸纤维质量较高，亮度、平滑度及适印性能较好。根据结构需要，如果纸盒（箱）折叠成型后，纸板底层为盒（箱）内角的两个边，而面层为盒（箱）内角的两个边，而面层为盒（箱）外角的两个边，则为内折，反之为外折。如果纸板180度折叠后，纸板两底层相对，则为内对折，反之为外对折。（最好结合画图完成图2-4） *5．打孔线的作用是什么？，成盒后原盖封死，会在撕裂打孔线形成什么？回答：打孔线的作用是方便开启，成盒后原盖封死，会在撕裂打孔线形成新盖。*6．在制作折叠纸盒时，纸板纹向与主要压痕线的关系如何？在管式折叠纸盒 和盘式折叠纸盒中具体如何？ 回答：纸板纹向应垂直于折叠纸盒的主要压痕线。对于管式折叠纸盒，纸板纹向应垂直于纸盒高度方向；对于盘式折叠纸盒，则纸板纹向应垂直于纸盒长度方向。 无锡市基础空间数据SHP格式设计方案 （大比例尺） 1、综述 1.1目的 为无锡市规划局基础空间数据建库提供标准。 1.2适用范围 1：500、1：1000、1：2000基础地形图数据 1.3制定原则 ●保证按本方案生产的数据可以实现同SHP数据的高效互转； ●保证按本方案生产的数据在转入数据库后可以实现标准图的输出； ●操作方便。 1.4类型约定 ● ● 1.5引用标准 《GB/T 14804-93 1：500 1：1000 1：2000 地形图要素分类与代码》（1994-08-01）《GB/T 7929-1995 1：500 1：1000 1：2000 地形图图式》（1996-05-01） 《GB 1：500 1：1000 1：2000 地形图数字化规范》（1998-08-01） 《GB/T14804-93 1：500 1：1000 1：2000 地形图要素分类与代码》（1994-08-01）《GT地籍数据库标准》 《GB/T 13923-92 国土基础信息数据分类与代码》（1993-07-01） 2、实体的划分 数据在SDE的服务器里是按照点、线、面和注记划分的，每一个SDE图层（FEATURECLASS）只能存储上述的一种空间对象。由于这种存储模型的限制，势必造成很多国标中的复杂地物被拆分到不同的SDE图层。为了在编码中体现设计的合理性、对实体的物理存储进行统一的管理，特在数据库的设计中在对空间实体做逻辑的划分。 2.1简单点 ●简单点实体只记录插入点的位置和相关属性，所有的简单点实体都必须以插入符号 的形式采集。 ●简单点状实体对应ARCOBJECT体系的IPOINT对象。 ●采集单位在使用点符号的时候要保证简单点的符号要和本方案提供的符号描述一 致，符号的插入点一致。 2.2简单无向线 ●简单线需要作业单位针对每一种实体制作线符号，这里所指的线符号必须是采集系 统提供的线符号库，不能用程序绘制。 结构化学复习提纲 第一章量子力学基础 了解量子力学的产生背景?黑体辐射、光电效应、玻尔氢原子理论与德布罗意物质波假设以及海森堡测不准原理，掌握微观粒子的运动规律、量子力学的基本假设与一维势阱中粒子的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). 宏观物体可以区分；等同的微观粒子不可区分。 《数据结构课程设计》报告 题目：课程设计题目2教学计划编制 班级：700 学号：09070026 姓名：尹煜 完成日期：2011年11月7日 一．需求分析 本课设的任务是根据课程之间的先后的顺序，利用拓扑排序算法，设计出教学计划，在七个学期中合理安排所需修的所有课程。 （一）输入形式：文件 文件中存储课程信息，包括课程名称、课程属性、课程学分以及课程之间先修关系。 格式：第一行给出课程数量。大于等于0的整形，无上限。 之后每行按如下格式“高等数学公共基础必修6.0”将每门课程的具体信息存入文件。 课程基本信息存储完毕后，接着给出各门课程之间的关系，把每门课程看成顶点，则关系即为边。 先给出边的数量。大于等于0的整形。 默认课程编号从0开始依次增加。之后每行按如下格式“1 3”存储。此例即为编号为1的课程与编号为3的课程之间有一条边，而1为3的前驱，即修完1课程才能修3课程。 例： （二）输出形式：1.以图形方式显示有向无环图 2.以文本文件形式存储课程安排 （三）课设的功能 1.根据文本文件中存储的课程信息（课程名称、课程属性、课程学分、课程之间关系） 以图形方式输出课程的有向无环图。 拓展：其显示的有向无环图可进行拖拽、拉伸、修改课程名称等操作。 2.对课程进行拓扑排序。 3.根据拓扑排序结果以及课程的学分安排七个学期的课程。 4.安排好的教学计划可以按图形方式显示也可存储在文本文件里供用户查看。 5.点击信息菜单项可显示本人的学好及姓名“09070026 尹煜” （四）测试数据（见六测设结果） 二．概要设计 数据类型的定义： 1.Class Graph即图类采用邻接矩阵的存储结构。类中定义两个二维数组int[][] matrix 和Object[][] adjMat。第一个用来标记两个顶点之间是否有边，为画图服务。第二个 是为了实现核心算法拓扑排序。 2.ArrayList 复习题（一） 一．填空题（每空1分，共15分） 1.一个算法的效率可分为___________________效率和___________________效率。 2.__________________是被限定为只能在表的一端进行插入运算，在表的另一端 进行删除运算的线性表。 3.设S=“A;/document/Mary.doc”，则strlen(S)= _______________，“/”的字符定位 的位置为_______________。 4.设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列 序为主序顺序存储，则元素a[32,58]的存储地址为_______________。 5.一棵深度为6的满二叉树有_______________个分支结点和_______________个 叶子。 6.用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度 是。 7.设有一稀疏图G，则G采用存储较省空间。 8.快速排序算法是对算法的一种改进。 9.在数据的存放无规律而言的线性表中进行检索的最佳方法 是。 10.大多数排序算法都有两个基本的操作： 和。 11.设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重 新排列，则：快速排序一趟扫描的结果是。 二．选择题（每题2分，共30分） （）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为： （A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构 （）2. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要 钢结构期末复习资料整理 第一章绪论 1 ?钢结构和其他材料的结构相比，钢结构具有哪些特点？答：钢材的强度高，塑性和韧性好；钢结 构的质量轻；钢材材质均匀，接近各向同性；钢结构制作简便，施工工期短；钢结构的密闭性好；钢结构的耐腐蚀性差，耐火性差；在低温和其他条件下可能发生脆性断裂。 2. 钢结构在工程中的应用：工业厂房；大跨度结构；高耸结构；多层和高层建筑；承受荷载影响及地震作用的结构；板壳结构；其他特种结构；可拆卸或移动的结构；轻型钢结构；和混凝土组合成的组合结构。 3. 结构的极限状态：当结构或其组成超过某一特定状态就不能满足设计规定的某一功能要求时，此特定状态就称为该功能的极限状态。 4.承载能力极限状态: 指结构或构件达到最大承载能力或出现不适于继续承载的变形时的极限状态; 正常使用极限状态：指结构或构架达到正常使用或耐久性能的某项规定限值时的极限状态）。 5.结构可靠度Ps：结构在规定的时间内，在规定的条件下完成预定功能的概率 第二章钢结构的材料 1. 钢结构中所用钢材应具有哪些性能？①钢材应具有较高的屈服强度？y和抗拉强度？u：?y是衡量结构承载能力的指标，？y高则可减轻结构自重，节约钢材和降低造价。？u是衡量钢材经过较大变形后的抗拉能力，它直接反映钢材内部组织的优劣，同时？u高可以增加结构的安全储备。②较高的塑性和韧性：塑性和韧性好，结构在静载和动载作用下有足够的应变能力，既可减轻结构脆性破坏的倾向，又能通过较大的塑性变形调整局部应力，同时又具有较好的抵抗重复荷载作用的能力。③良好的工艺性能（包括冷加工、热加工和焊接性）：良好的工艺性能不但要易于加工成各种形式的结构，而且不致因加工而对结构的强度、塑性、韧性等造成较大的不利影响。此外，根据结构的具体工作条件，有时还要求钢材具有适应低温、高温和腐蚀性环境的能力。 2. 塑性破坏：钢材在超过屈服点即有明显的塑性变形产生，超过抗拉强度时将在很大变形的情况下断裂。后果：塑性变形的断口平直，并因晶体在剪切之下相互滑移的结果而呈纤维状，塑性破坏之前，结构有明显的塑性变形产生，且有较长的持续时间，可便于发现和补救。 3. 脆性破坏：钢材没有的塑性变形产生或只有很小塑性变形而发生破坏。后果：脆性破坏之前，结构 没有明显的塑性变形产生，且发生很突然，后果很危险。 4. 强度：屈强比是衡量钢材强度储备的一个系数。屈强比越低安全储备越大，但屈强比过小时，不经济。当屈强比过大时，安全储备较小，且构件的塑性变形能力较小。 5. 塑性：指钢材在应力超过屈服点后，能产生显著残余变形而不立即断裂的性质。 6. 冲击韧性：指在钢材塑性变形和断裂过程中吸收能量的能力，是衡量钢材抵抗动力荷载能力的指标。①是钢材塑性和强度的综合表现，可以用来判断钢材在动力荷载作用下是否会发生脆性破坏；②冲击 韧性好表示在动力荷载作用下破坏时吸收能量多；③对于需要验算疲劳的结构所用的钢材应具有不同 试验温度下的冲击韧性的合格保证；④冲击韧性受温度的影响较大，钢材具有低温冷脆性。 7. 冷弯性能：指钢材在常温下加工发生塑性变形时，对产生裂纹的抵抗能力。①冷弯性能用冷弯试验来检测，检测时如果时间弯曲180度，无裂纹、断裂或分层，即试件冷弯合格。②制作结构构件和非结构构件的钢材的冷加 《数据结构》 课程设计报告 学号 姓名 班级 指导教师 安徽工业大学计算机学院 2010年6月 建立二叉树和线索二叉树 1.问题描述： 分别用以下方法建立二叉树并用图形显示出来： 1）用先序遍历的输入序列 2）用层次遍历的输入序列 3）用先序和中序遍历的结果 2.设计思路： 分三个方式去实现这个程序的功能，第一个实现先序遍历的输入数列建立二叉树；第二个是用层次遍历的方法输入序列；第三个是用先序和后序遍历的结果来建立二叉树；三种方法建立二叉树后都进行输出。关键是将这三个实现功能的函数写出来就行了；最后对所建立的二叉树进行中序线索化，并对此线索树进行中序遍历（不使用栈）。 3.数据结构设计： 该程序的主要目的就是建立二叉树和线索二叉树，所以采用树的存储方式更能完成这个程序； 结点的结构如下： typedef struct bnode { DataType data; int ltag,rtag; struct bnode *lchild, *rchild; } Bnode, *BTree; 4.功能函数设计： BTree CreateBinTree() 用先序遍历的方法讲二叉树建立； BTree CREATREE() 用队列实现层次二叉树的创建； void CreatBT()； 用先序和中序遍历的结果建立二叉树； void InThread(BTree t,BTree pre) 中序线索化； 5.编码实现： #include 一、高校社团管理 在高校中，为了丰富学生的业余生活，在学校的帮助下，会成立许多社团，少则几个，多则几十个。为了有效管理这些社团，要求编写程序实现以下功能：1．社团招收新成员； 2．修改社团相应信息 3．老成员离开社团 4．查询社团情况； 5．统计社团成员数； 二、简单文本编辑器 设计一个文本编辑器，允许将文件读到内存中，也就是存储在一个缓冲区中。这个缓冲区将作为一个类的内嵌对象实现。缓冲区中的每行文本是一个字符串，将每行存储在一个双向链表的结点中，要求设计在缓冲区中的行上执行操作和在单个行中的字符上执行字符串操作的编辑命令。 基本要求： 包含如下命令列。可用大写或小写字母输入。 R：读取文本文件到缓冲区中，缓冲区中以前的任何内容将丢失，当前行是文件的第一行； W：将缓冲区的内容写入文本文件，当前行或缓冲区均不改变。 I：插入单个新行，用户必须在恰当的提示符的响应中键入新行并提供其行号。 D：删除当前行并移到下一行； F：可以从第1行开始或从当前行开始，查找包含有用户请求的目标串的第一行； C：将用户请求的字符串修改成用户请求的替换文本，可选择是仅在当前行中有效的还是对全文有效的。 Q：退出编辑器，立即结束； H：显示解释所有命令的帮助消息，程序也接受？作为H的替代者。 N：当前行移到下一行，也就是移到缓冲区的下一行； P：当前行移到上一行，也就是移到缓冲区的上一行； B：当前行移到开始处，也就是移到缓冲区的第一行； E：当前行移到结束处，也就是移到缓冲区的最后一行； G：当前行移到缓冲区中用户指定的行； V：查看缓冲区的全部内容，打印到终端上。 三、电话客户服务模拟 一个模拟时钟提供接听电话服务的时间(以分钟计),然后这个时钟将循环的 自增1(分钟)直到达到指定时间为止。在时钟的每个"时刻"，就会执行一次检查来看看对当前电话服务是否已经完成了,如果是,这个电话从电话队列中删除,模 拟服务将从队列中取出下一个电话(如果有的话)继续开始。同时还需要执行一个检查来判断是否有一个新的电话到达。如果是,其到达时间被记录下来,并为其产生一个随机服务时间,这个服务时间也被记录下来,然后这个电话被放入电话队列中,当客户人员空闲时,按照先来先服务的方式处理这个队列。当时钟到达指定时间时,不会再接听新电话,但是服务将继续,直到队列中所偶电话都得到处理为止。 基本要求： （1）程序需要的初始数据包括：客户服务人员的人数，时间限制，电话的到达速率，平均服务时间 （2）程序产生的结果包括：处理的电话数，每个电话的平均等待时间 四、停车场管理 设停车场是一个可停放n辆车的狭长通道，且只有一个大门可供汽车进出。在停车场内，汽车按到达的先后次序，由北向南依次排列（假设大门在最南端）。若停车场内已停满n辆车，则后来的汽车需在门外的便道上等候，当有车开走时，便道上的第一辆车即可开入。当停车场内某辆车要离开时，在它之后进入的车辆必须先退出停车场为它让路，待该辆车开出大门后，其他车辆再按原次序返回车场。每辆车离开停车场时，应按其停留时间的交费（从进入便道开始计时）。在这里假设汽车从便道上开走时不收取任何费用 基本要求： （1）汽车的输入信息格式为（到达/离去的标识，汽车牌照号码，到达/离去的时间） 数据库基础知识试题 部门____________ __________ 日期_________ 得分__________ 一、不定项选择题（每题1.5分，共30分） 1.DELETE语句用来删除表中的数据,一次可以删除( )。D A .一行 B.多行 C.一行和多行 D.多行 2.数据库文件中主数据文件扩展名和次数据库文件扩展名分别为( )。C A. .mdf .ldf B. .ldf .mdf C. .mdf .ndf D. .ndf .mdf 3.视图是从一个或多个表中或视图中导出的（）。A A 表 B 查询 C 报表 D 数据 4.下列运算符中表示任意字符的是( )。B A. * B. % C. LIKE D._ 5.（）是SQL Server中最重要的管理工具。A A．企业管理器 B.查询分析器 C.服务管理器 D.事件探察器 6.（）不是用来查询、添加、修改和删除数据库中数据的语句。D A、SELECT B、INSERT C、UPDATE D、DROP 7.在oracle中下列哪个表名是不允许的（）。D A、abc$ B、abc C、abc_ D、_abc 8.使用SQL命令将教师表teacher中工资salary字段的值增加500，应该使用的命令 是（）。D A、Replace salary with salary+500 B、Update teacher salary with salary+500 C、Update set salary with salary+500 D、Update teacher set salary=salary+500 9.表的两种相关约束是（）。C 复习提纲： 第一章： 1．数据结构的基本概念； 2．数据结构的4类基本结构及其特性； 3．存储结构的分类及特点； 4．算法的时间复杂度计算； 第二章： 1．线性表的基本概念； 2．线性表的顺序存储结构的特点和插入删除算法； 3．顺序存储结构的应用； 4．单循环链表的存储结构特点，链表空的判断方法、插入、删除结点算法实现，报数游戏算法实现；5．循环双链表的存储特点，插入、删除结点算法实现。 第三章： 1．栈的特点、对同一序列根据栈的特点进行不同入栈、出栈操作所得结果的判断；栈的实现的相关操作；2．顺序栈的4各要素和相关操作关键语句；链栈的4个要素和相关操作关键语句； 3．了解队列的特点和可执行的基本操作，并能做相关判断； 4．顺序循环队列的队空、队满判断条件，入队、出队操作的相关关键语句； 5．顺序循环队列中对同一序列根据队列进行不同的入队、出队操作后队头和队尾指针的变化判断。 第四章： 1．串的定义、串长的定义和计算、子串个数计算（注意区分：子串与非空且不同于S本身的子串）； 2．串的模式匹配（区分BF算法和KMP算法），掌握使用KMP算法计算next数组的值，并且要求掌握匹配过程（BF和KMP的匹配过程不同！）。 前三章程序重点掌握作业四、作业五、作业六、作业八、作业九 第五章： 1．特殊矩阵的压缩存储地址计算，稀疏矩阵的压缩存储结构图。 2．广义表的定义、区分原子和子表，求表头和表尾，深度和层次计算，存储结构图绘制； 3．提供一广义表，写出通过head()和tail()操作求出某个原子的表达式。 4．注意：取表头时即广义表的第一个元素，外面不再加括号；而取表尾时，要将除表头元素外的其他元素一起用圆括号括起来，即将原广义表去掉表头； 第七章： 结构化学复习提纲第一章量子力学基础 了解量子力学的产生背景?黑体辐射、光电效应、玻尔氢原子理论与德布罗意物质波假设 以及海森堡测不准原理，掌握微观粒子的运动规律、量子力学的基本假设与一维势阱中 粒子的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). 宏观物体可以区分；等同的微观粒子不可区分。 2. 微观粒子运动状态的描述 a. 品优波函数的三个要求: 单值连续平方可积 波函数exp(i m?) m的取值？ b. 将波函数归一化? = 0?2? c. 波函数的物理意义??(x, y, z, t)?2d x d y d z表示在t时刻在空间小体积元(x?x+d x, y?y+d y, z?z+d z)中找到粒子的几率 d. 波函数的单位* 3. 物理量与厄米算符 每个物理可观测量都可以用一个厄米算符表示 a. 线性算符与厄米算符 b. 证明id/dx是厄米算符* c. 写出坐标，动量，能量，动能，势能与角动量的算符 数据结构课程设计报告 题目：5 班级:计算机1102 学号：4111110030 姓名：陈越 指导老师：王新胜 一：需求分析 1.运行环境 TC 2.程序所需实现的功能 几种排序算法的演示，要求给出从初始开始时的每一趟的变化情况，并对各种排序算法性能作分析和比较： （1）直接插入排序； （2）折半插入排序； （3）冒泡排序； （4）简单选择排序； （5）快速排序； （6）堆排序； （7）归并排序. 二：设计说明 1.算法设计的思想 1）、直接插入排序 排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。 2)、折半插入排序 排序过程：用折半查找方法确定插入位置的排序叫折半插入排序。 3)、冒泡排序 排序过程：将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r[1].key>r[2].key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上。对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置。重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止 4)、简单选择排序 排序过程：首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换。再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换。重复上述操作，共进行n-1趟排序后，排序结束。 5)、快速排序 基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序。 排序过程：对r[s……t]中记录进行一趟快速排序，附设两个指针i和j，设枢轴记录rp=r[s]，x=rp.key。初始时令i=s,j=t。首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换。再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和rp交换。重复上述两步，直至i==j为止。再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止。 6)、堆排序 排序过程：将无序序列建成一个堆，得到关键字最小（或最大）的记录；输《混凝土结构》复习提纲中册
数据结构课程设计
校园基础地理空间数据库建设设计方案
《数据结构》课程考试大纲
数据结构复习要点整理版
数据结构课程设计报告模板
数据结构复习提纲(整理)
包装结构复习资料
无锡市基础空间数据库SHP格式方案(大比例尺)
结构化学复习提纲(精心整理)
数据结构课程设计报告
数据结构复习题及答案
最新钢结构期末复习资料整理
数据结构课程设计
数据结构课程设计
数据库基础知识试题(含答案)
数据结构数据结构复习提纲(新)
结构化学复习提纲 ()
数据结构课程设计报告
相关主题
文本预览