当前位置：文档库 › 数据结构复习提纲

数据结构复习提纲

复习提纲

第一章数据结构概述

基本概念与术语

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 )

--------------------------------------------------------------------------------------------------------------------

6.算法与程序：

1、输入：有零个或多个输入

2、输出：有一个或多个输出

3、有穷性：要求序列中的指令是有限的；每条指令的执行包含有限的工作量；

整个指令序列的执行在有限的时间内结束。（程序与算法的区别

在于，程序不需要有有穷性）

4、确定性：算法中的每一个步骤都必须是确定的，而不应当含糊、模棱两

可。没有歧义。

5、可行性：算法中的每一个步骤都应当能被有效的执行，并得到确定的结

果。

7.算法设计的准则：

1、正确性（达到预期效果，满足问题需求）

2、健壮性（能处理合法数据，也能对不合法的数据作出反应，不会产生不

可预期的后果）

3、可读性（要求算法易于理解，便于分析）

4、可修改可扩展性

5、高效率（较好的时空性能）

1、名词解释：数据结构、二元组

数据结构就是相互之间存在一种或多种特定关系的数据元素的集合。

二元组就是一种用来表示某个数据对象以及各个元素之间关系的有限集合。

2、根据数据元素之间关系的不同，数据的逻辑结构可以分为集合、线性结构、树形结构和图状结构四种类型。

3、常见的数据存储结构一般有两种类型，它们分别是顺序存储结构、链式存储结构

4.以下说法中，正确的是（D）

A.数据元素是数据这个集合中的个体

B.数据元素均由数据项组成

C．数据项是数据的基本单位

D.数据元素是数据的最小单位

5.以下有关抽象数据类型的描述中，正确的是（B）

A.抽象数据类型是一个值的集合

B.抽象数据类型是数据的逻辑结构及操作的组合

C.抽象数据类型的操作可以没有操作结果

D.抽象数据类型只能够用C语言来描述

6.在一般情况下，一个算法的时间复杂度是问题规模的函数

7.常见时间复杂度有：常数阶O（1）、线性阶O（n）、对数阶O（log 2 n）、平方阶O(n^2)、指数阶O(2^n)。通常认为，具有常数阶量级的算法是好算法，而具有指数阶量级的算法是差算法。

------------------------------------------------------------------------------------------------------------------

第二章线性表

1.顺序表结构

线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称为顺序表。

2.单链表

（1）链表结点结构

线性表中的数据元素可以用任意的一组存储单元来存储，用指针表示逻辑关系

逻辑相邻的两元素的存储空间可以是不连续的。

（2）结点遍历

（3）链表操作算法：初始化、插入、输出、删除

----------------------------------------------------------------------------------------------------------------

1、线性表中，第一个元素没有直接前驱，最后一个元素没有直接后驱。

2、在一个单链表中，若p所指结点是q所指结点的前驱结点，则删除结点q的操作语句为P->next = q->next ; free(q);

3、在长度为N的顺序表仲，插入一个新元素平均需要移动表中N/2个元素，删除一个元素平均需要移动（N-1）/2个元素。

4、若线性表的主要操作是在最后一个元素之后插入一个元素或删除最后一个元素，则采用数序表存储结构最节省运算时间。

5、已知顺序表中每个元素占用3个存储单元，第13个元素的存储地址为336，则顺序表的首地址为300。

6、设有一带头结点单链表L，请编写该单链表的初始化，插入、输出和删除函数。（函数名自定义）

结点定义：

typedef int datatype; //结点数据类型，假设为int

typedef struct node { //结点结构

datatype data;

struct node *next;

} Lnode, * pointer ; //结点类型,结点指针类型

typedef pointer lklist; //单链表类型，即头指针类型

1.初始化函数：

lklist initlist() {

pointer head;

head=new node;

head?>next=NULL;

return head;

}

2.插入函数：

int insert(lklist head,datatype x,int i){

pointer q,s;

q=get(head,i?1); //找第i?1个点

if(q==NULL) //无第i?1点，即i<1或i>n+1时

{cout<<”非法插入位置!\n”;return 0;}

s=new node; //生成新结点

s?>data=x;

s?>next=q?>next; //新点的后继是原第i个点

q?>next=s; //原第i?1个点的后继是新点

return 1; //插入成功

}

3.删除函数：

int delete(lklist head,int i) {

pointer p,q;

q=get(head,i?1); //找待删点的直接前趋

if(q==NULL || q?>next==NULL) //即i<1或i>n时

{cout<<”非法删除位置!\n”;return 0;}

p=q?>next; //保存待删点地址

q?>next=p?>next; //修改前趋的后继指针

delete p; //释放结点

return 1; //删除成

1.不带头结点的单链表head为空的判定条件是(A )

A. head=NULL

B. head->next=NULL

C. head->next=head

D. head!=NULL

2.带头结点的单链表head为空的判定条件是(B )

A. head=NULL

B. head->next=NULL

C. head->next=head

D. head!=NULL

3.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行(B )

A. s->next=p; p->next=s;

B. s->next=p->next; p->next=s;

C. s->next=p->next; p=s;

D. p->next=s; s->next=p;

4.在一个单链表中，若删除p所指结点的后续结点，则执行(A )

A. p->next=p->next->next;

B. p=p->next; p->next=p->next->next;

C. p->next=p->next

D. p=p->next->next

5.从一个具有n个结点的有序单链表中查找其值等于x结点时，在查找成功的情况下，需

平均比较（B ）个结点。

A. n

B. n/2

C. (n-1)/2

D. O(n㏒2n)

6.给定有n个元素的向量，建立一个有序单链表的时间复杂度（B）

A.O(1)

B.O(n)

C.O(n2)

D.O(n㏒2n)

7.在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是(B)

A.O(1)

B.O(n)

C.O(n2)

D.O(n㏒2n)

8. 在一个单链表中删除q所指结点时，应执行如下操作：

q=p->next;

p->next=( p->next->next );

free(q);//这种题目靠一根指针是没有办法完成的，必须要借助第二根指针。

9. 在一个单链表中p所指结点之后插入一个s所指结点时，应执行：

s->next=( p->next )

p->next=(s)操作。

10. 对于一个具有n个节点的单链表,在已知所指结点后插入一个新结点的时间复杂度是(O

（1）)；在给定值为x的结点后插入一个新结点的时间复杂度是（O(n)）。

11.问答题

线性表可用顺序表或链表存储。试问：

(1) 两种存储表示各有哪些主要优缺点?

顺序表的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间不会发生改变，因此，不易扩充。同时，由于在插入或删除时，为保持原有次序，平均需要移动一半(或近一半)元素，修改效率不高。

链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。

(2) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？

应采用顺序存储表示。因为顺序存储表示的存取速度快，但修改效率低。若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时采用顺序存储表示较好。

----------------------------------------------------------------------------------------------------------------

第三章栈和队列

1.栈

（1）栈的结构与定义

（2）顺序栈操作算法：入栈、出栈、判断栈空等

（3）链栈的结构与定义

2.队列

（1）队列的定义

----------------------------------------------------------------------------------------------------------------

1、一个栈的入栈序列为“ABCDE”，则以下不可能的出栈序列是（B）

A. BCDAE

B. EDACB

C. BCADE

D. AEDCB

2、栈的顺序表示中，用TOP表示栈顶元素，那么栈空的条件是（D）

A. TOP==STACKSIZE

B. TOP==1

C. TOP==0

D. TOP==-1

3、允许在一端插入，在另一端删除的线性表称为队列。插入的一端为表头，删除的一端为表尾。

4、栈的特点是先进后出，队列的特点是先进先出。

5、对于栈和队列，无论他们采用顺序存储结构还是链式存储结构，进行插入和删除操作的时间复杂度都是O(1)。

6、已知链栈Q，编写函数判断栈空，如果栈空则进行入栈操作，否则出栈并输出。（要求判断栈空、出栈、入栈用函数实现）

考点1：队列的编程：

考点2：栈的编程：

7.出队与取队头元素的区别：出队就是删除对头的数据元素，取队头元素是获取对头的数据

元素值，不需要删除。

8.链栈与顺序栈相比，比较明显的优点是：（D）

A.插入操作比较容易

B.删除操作比较容易

C.不会出现栈空的情况

D.不会出现栈满的情况

---------------------------------------------------------------------------------------------------------------------

第六章树和二叉树

1．树

（1）树的概念及术语

树：n（n≥0）个结点的有限集合。当n＝0时，称为空树；任意一棵非空树满足以下条件：

⑴有且仅有一个特定的称为根的结点；

⑵当n＞1时，除根结点之外的其余结点被分成m（m>0）个互不相交的有限集合

T1,T2,… ,Tm，其中每个集合又是一棵树，并称为这个根结点的子树。

（2）结点的度：结点所拥有的子树的个数。

树的度：树中所有结点的度的最大值。

（3）叶子结点：度为0的结点，也称为终端结点。

分支结点：度不为0的结点，也称为非终端结点。

（4）孩子、双亲：树中某结点的子树的根结点称为这个结点的孩子结点，这个结点称

为它孩子结点的双亲结点；

兄弟：具有同一个双亲的孩子结点互称为兄弟。

（5）路径：如果树的结点序列n1, n2, …, nk有如下关系：结点ni是ni+1的双亲（1<=i

为路径长度。

（6）祖先、子孙：在树中，如果有一条路径从结点x到结点y，那么x就称为y的祖

先，而y称为x的子孙。

（7）结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第k层，则其

孩子结点在第k+1层。

树的深度：树中所有结点的最大层数，也称高度。

（8）层序编号：将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以

从1开始的连续自然数。

（9）有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的，称这棵树为

有序树；反之，称为无序树。数据结构中讨论的一般都是有序

树

（10）树通常有前序（根）遍历、后序（根）遍历和层序（次）遍历三种方式（树，不是二叉树，没中序遍历。

2．二叉树

（1）二叉树的定义：二叉树是n（n≥0）个结点的有限集合，该集合或者为空集（称为

空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点

的左子树和右子树的二叉树组成。

满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。

（满二叉树的特点：叶子只能出现在最下一层；只有度为0和度为2的结点。）

完全二叉树：对一棵具有n个结点的二叉树按层序编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相

同。

（完全二叉树的特点：1.在满二叉树中，从最后一个结点开始，连续去掉任意个结点，

即是一棵完全二叉树。

2.叶子结点只能出现在最下两层，且最下层的叶子结点都集

中在二叉树的左部；

3. 完全二叉树中如果有度为1的结点，只可能有一个，且该

结点只有左孩子。

4. 深度为k的完全二叉树在k-1层上一定是满二叉树。

）

（3）二叉树的性质：性质1：二叉树的第i层上最多有2i-1个结点（i≥1）。

性质2：一棵深度为k的二叉树中，最多有2k-1个结点，最少

有k个结点。深度为k且具有2k-1个结点的二叉树一

定是满二叉树

性质3：在一棵二叉树中，如果叶子结点数为n0，度为2的结点

数为n2，则有: n0＝n2＋1。（一个结点的度就是指它放

出的射线）

性质4：具有n个结点的完全二叉树的深度为log2n +1。

性质5：对一棵具有n个结点的完全二叉树中从1开始按层序编

号，则对于任意的序号为i（1≤i≤n）的结点（简称为结

点i），有：

（1）如果i＞1，则结点i的双亲结点的序号为i/2；如果i＝1，则结点i是根结点，无双亲结点。

（2）如果2i≤n，则结点i的左孩子的序号为2i；如果2i＞n，则结点i无左孩子。

（3）如果2i＋1≤n，则结点i的右孩子的序号为2i＋1；如果2i＋1＞n，则结点i无右孩子。

3．二叉树的遍历

（1）前序遍历

（2）中序遍历

（3）后序遍历

4. 森林

（1）森林的遍历：先序遍历森林和中序森林

先序遍历：若森林不空，则

访问森林中第一棵树的根结点；

先序遍历森林中第一棵树的子树森林；

先序遍历森林中（除第一棵树之外）其余树构成的森林。

（约定：依次从左至右对森林中的每一棵树进行先根遍历。）

后序遍历：若森林不空，则

后序遍历森林中第一棵树的子树森林；

访问森林中第一棵树的根结点；

后序遍历森林中（除第一棵树之外）其余树构成的森林。

（约定：依次从左至右对森林中的每一棵树进行后根遍历。）

（2）森林：m (m ≥0)棵互不相交的树的集合。

5. 二叉搜索树

（1）二叉搜索树的定义及构建：

6. 哈夫曼树

（1）哈夫曼树的基本概念：

哈夫曼树：给定一组具有确定权值的叶子结点，带

权路径长度最小的二叉树。

（2）哈夫曼树的特点：

1. 权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。

2. 只有度为0（叶子结点）和度为2（分支结点）的结点，不存在度为1的结点.

（3）哈夫曼树的构造算法思想及构造过程（7森林与哈夫曼编码）

----------------------------------------------------------------------------------------------------------------------

1、已知一棵完全二叉树有47个结点，则该二叉树有（）个叶子结点。

A. 6

B. 12

C. 24

D.48

2、已知遍历一棵二叉树的前序序列ABCDEFG 和中序序列CBEDAFG ，那么是下面哪棵

树（C ）。

h i

C D

3、如下图所示的一棵二叉树进行遍历，得到的遍历序列是CADREFB，则该遍历序列是哪种遍历（B）的结果。

A. 前序遍历

B. 中序遍历

C. 后序遍历

D. 层次遍历

4、完全二叉树必须满足的条件为: ：一棵具有n个结点的二叉树，它的结构与满二叉树的前n个结点的的结构相同。

5、哈夫曼树不存在度为1的结点。

6、有5个带权结点，其权值分别为2，5，3，7，11，根据哈夫曼算法构建该树，并计算该树的带权路径长度。（构建哈夫曼树，很简单，从小开始，计算相加，然后把所有叶子结点乘以等级数字然后相加。也即是：带权路径长度=叶结点的权值*路径长度）

8、写出前序和后序遍历下面森林得到的序列，并将森林转化成二叉树

前序：abdj ce fhi

后序：djba ec hif

1．前序遍历和中序遍历结果相同的二叉树是（D ）。

A 根结点无左孩子的二叉树

B 根结点无右孩子的二叉树

C 所有结点只有左子树的二叉树

D 所有结点只有右子树的二叉树

2．用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组A[1] ~ A[n]中，结点A[i]若有左子树，则左子树的根结点是（D ）。

A A[2i-1]

B A[2i+1]

C A[i/2]

D A[2i]

3.对任何一棵二叉树T，如果其终端结点的个数为n0，度为2的结点个数为n2，则（C）。

A . n0=n2-1

B . n0=n2 C. n0=n2+1 D. 没有规律

5.对于完全二叉树中的任一结点，若其右分支下的子孙的最大层次为h，则其左分支下的子孙的最大层次为（C ）。

A . h

B . h+1 C. h或h+1 D 任意

6. 假定一棵度为3的树的结点个数为50，则它的最小深度为5 ，最大深度为50 。

A 3

B 4

C 5

D 6

7.试找出分别满足下列条件的所有二叉树：

⑴前序序列和中序序列相同：只有右子树

⑵中序序列和后序序列相同：只有左子树

⑶前序序列和后序序列相同：只有根，空二叉树

8 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法（A）

（A）正确（B）错误

9.由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法（B）

（A）正确（B）错误

10.已知某二叉树的后序遍历序列是dabec。中序遍历序列是debac，它的前序遍历序列是（D）。

（A）acbed （B）decab（C）deabc （D）cedba

11.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（D）。

（A）bdgcefha （B）gdbecfha （C）bdgaechf （D）gdbehfca

12.在一非空二叉树的中序遍历序列中，根结点的右边（C）

（A）只有右子树上的所有结点（B）只有右子树上的部分结点

（C）只有左子树上的部分结点（D）只有左子树上的所有结点

15.任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序(B )

（A）不发生改变（B）发生改变（C）不能确定（D）以上都不对

-----------------------------------------------------------------------------------------------------------

第七章图

1. 图的基本概念：图的基本术语及推论

2. 邻接矩阵：邻接矩阵的定义

3. 图的遍历

（1）深度优先遍历

（2）广度优先遍历

-----------------------------------------------------------------------------------------------------------

1、对于上图所示的有向图，其深度优先搜索遍历序列为ADFCEB，广度优先搜索遍历序列为ABCDEF，其拓扑排序序列为A(去掉A发出的射线)B(去掉B发出的射线)EDFC。

2、一个具有N个顶点的完全无向图的边数为1/2N(N-1)；一个具有N个顶点的完全有向图的弧数为N(N-1)。

3、在有向图中，总入度、总出度和总边数相等。在无向图中，总度数是总边数的两倍。

4、一个有16个顶点的无向图，至少应该有15（n-1）条边才能确保它是连通图。

5、给出下面所示有向图的邻接矩阵。

---------------------------------------------------------------------------------------------------------------------

第九章排序

1. 直接排序：直接插入、直接选择算法思想

直接插入排序法：依次将待排序数据元素按其关键字的大小插入到有序区的适当位置

上，这就是直接插入排序法。

Eg:（25，6，23，11，67，45）

25，6，23，11，67，45

6, 25，23，11，67，45

6, 23, 25, 11，67，45

(在有序区内进行比较排序)

直接选择排序法：每趟排序在当前待排序序列中选出关键码最小的记录，添加到有序

序列中。

Eg:(70, 89, 3, 8, 25, 18)

先固定第一个元素，然后从剩下的元素中选出最小的，与固定元素比较，交换

(3, 89 ,70 ,8 ,25 ,18)

(3, 8 ,70 ,89, 25 ,18)

……

3.冒泡排序：

算法思想:两两比较相邻记录的关键码，如果反序则交换，直到没有反序的记录为止。

Eg(98, 25, 70, 36, 13, 85)

首先，我们假设是升序排序，98先出来与25比，若大于25，交换继续比较，直到遇见比它大的数字或者到了最后，停下。

详细参考书本P295笔记

3. 快速排序：算法思想

首先选一个轴值（即比较的基准），通过一趟排序将待排序记录分割成独立的两部分，前一部分记录的关键码均小于或等于轴值，后一部分记录的关键码均大于或等于轴值，然后分别对这两部分重复上述方法，直到整个序列有序。

快速排序比较难以理解，（31，68，45，90，23，39，54，12，87，76）

31<76,指向31的左指针不用移动；指向76的右指针移动87，12。当到了12之后，因为31>12,交换，（12，68，45，90，23，39，54，31，87，76）

68与31按照前面的，交换！

……

4.堆排序：堆的定义

首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者，然后将它从堆中移走，并将剩余的记录再调整成堆，然后又将它从堆中移走，这样又找出了次小的记录，以此类推，直到堆中只有一个记录。

（大根堆：越往上越大；小根堆：越往下越大）

1.按照给出的数据的顺序由上往下建一个堆；

2.根据题目要求，看是要大根堆还是小根堆；

3.从最下面的支点开始调整；

-----------------------------------------------------------------------------------------------------------------

1、排序方法的稳定性是指（B）

A. 排序算法能在规定的时间内完成排序

B. 排序算法能得到确定的结果

C. 排序算法不允许有相同关键字的数据元素

D. 以上都不对

2、在对一组关键字序列｛70，55，100，15，33，65，50，40，95｝进行直接插入排序时，把65插入到有序序列需要比较（B）次。

A. 2

B. 4

C. 6

D. 8

3、若有关键字序列｛42，70，50，33，40，80｝，则利用快速排序的方法，以第一个关键字为基准元素得到的一次划分结果为（A）。(指着第一个原始元素的那个指针成为不动指针，又叫做伴随指针，另一个指针叫做比较指针)

A. 40,33,42,50,70,80

B. 40,33,80,42,50,70

C. 40,33,42,80,50,70

D. 33,40,42,50,70,80

4、以下排序方法中，排序过程中的比较次数与排序方法无关的是（A）

A. 直接选择排序

B. 快速排序法

C. 堆排序

D.直接插入排序

5、以下（B）排序方法是不稳定的排序方法

A. 冒泡

B.堆

C. 直接插入

D.二路归并

6、以下各种排序方法中，最好情况下时间复杂度为O(n)的是（D）。

A. 归并排序

B. 快速排序

C. 堆排序

D. 直接插入排序和冒泡排序

7、在待排序序列局部有序时，效率最高的排序方法是（C）。

A. 直接选择排序

B. 快速排序

C. 直接插入排序和冒泡排序

D. 归并排序

8、已知关键字序列｛52，43，78，99，85，30，40｝，请给出快速排序的第一趟和第二趟的结果。

9、已知关键字序列｛500，10，200，800，150，250，70，30，300｝，请给出构建大根堆的过程。

10.当待排序序列基本有序或个数较小的情况下，最佳的内部排序方法是（A），就平均时间而言，（D ）最佳。

A 直接插入排序

B 起泡排序C简单选择排序D快速排序

11.下述排序方法中，比较次数与待排序记录的初始状态无关的是（C），有关的是（A ）。

A 插入排序

B 归并排序

C 选择排序

D 交换排序

12.判断下列序列是否为堆，若是堆则进一步指出是大根堆还是小根堆。

（1）(50,36,41,19,23,4,20,18,12,22)-大根堆

（2）(43,5,47,1,19,11,59,15,48,41)-不是堆

（3）(50,36,41,19,23,20,18,12,22)-不是堆

（4）(9,13,17,21,22,31,33,24,27,23)-小根堆

13.设有5000个元素，希望用最快的速度挑选出前10个最大的，采用（B）方法最好。

A快速排序B堆排序C希尔排序 D 归并排序

14.排序的方法有很多种，（C ）法从未排序序列中依次取出元素，与已排序序列中的元素作比较，将其放入已排序序列的正确位置上。（A ）法从未排序序列中挑选元素，并将其依次放入已排序序列的一端。交换排序是对序列中元素进行一系列比较，当被比较的两元素为逆序时，进行交换；（B ）和（D）是基于这类方法的两种排序方法，而（B）是比（D ）效率更高的方法；（F）法是基于选择排序的一种方法，是完全二叉树结构的一个重要应用。

A 选择排序

B 快速排序

C 插入排序

D 起泡排序

E 归并排序

F 堆排序

15.快速排序在（C）情况下最不利于发挥其长处。

A 待排序的数据量太大

B 待排序的数据中含有多个相同值

C 待排序的数据已基本有序

D 待排序的数据数量为奇数

16.以下序列属于堆的是( B )

A 79，46，56，38，40，84

B 84,79,56,38,40,46

C 79，40，56，38，46，84

D 38,84,79,56,40,46

17.已知一组数据的排序码为：{11，50，16，70，1，3}，要求排序后数据从小到大升序排列，写出利用简单选择排序的

方法排序的全部排序过程

第1趟：

第2趟：

第3趟：

第4趟：

第5趟：

第6趟：

18 当待排序序列基本有序或个数较小的情况下，最佳的内部排序方法是（C ），就平均时间而言，（D ）最佳。

A 直接插入排序

B 起泡排序C简单选择排序D快速排序

算法题：链表合并，创建树，数制转换，表达式求值，排序算法

《混凝土结构》复习提纲中册

复习提纲第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=0)个具有相同性质的数据元素a1,a2,a3……,an组成的有穷序列 //顺序表结构 #define MAXSIZE 100 typedef int DataType; Typedef struct{ DataType items[MAXSIZE]; Int length; }Sqlist,*LinkList; //初始化链表 void InitList(LinkList *L){ (*L)=(LinkList)malloc(sizeof(LNode)); if(!L){ cout<<”初始化失败!”; return;

包装结构复习资料

包装结构设计复习提纲 *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格式方案(大比例尺)

无锡市基础空间数据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 list用来存储课程信息。DrawInfo类是一个辅助画图的类，其中包括成员变量num、name、shuxing、xuefen分别代表课程的编号、名称、属性、学分。ArrayList是一个DrawInfo类型的数组，主要用来在ReadFile、DrawG、DrawC、SaveFile、Window这些类之间辅助参数传递，传递课程信息。 3.Class DrawInfo, 包括int num;String name;String shuxing;float xuefen;四个成员变量。 4.Class Edge包括int from;int to;double weight;三个成员变量。 5.Class Vertex包括int value一个成员变量。主要程序的流程图： //ReadFile.java

数据结构复习题及答案

复习题（一）一．填空题（每空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个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要

数据结构课程设计

《数据结构》课程设计报告学号姓名班级指导教师安徽工业大学计算机学院 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 #include #define max 100 typedef struct bnode { char data; int ltag,rtag; struct bnode *lchild,*rchild; }Bnode,*BTree; BTree Q[max]; BTree CREATREE() { char ch; int front=1,rear=0;

数据结构课程设计

一、高校社团管理在高校中，为了丰富学生的业余生活，在学校的帮助下，会成立许多社团，少则几个，多则几十个。为了有效管理这些社团，要求编写程序实现以下功能：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．注意：取表头时即广义表的第一个元素，外面不再加括号；而取表尾时，要将除表头元素外的其他元素一起用圆括号括起来，即将原广义表去掉表头；第七章：

结构化学复习提纲 ()

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格式方案(大比例尺)

结构化学复习提纲(精心整理)

数据结构课程设计报告

数据结构复习题及答案

最新钢结构期末复习资料整理

数据结构课程设计

数据结构课程设计

数据库基础知识试题(含答案)

数据结构数据结构复习提纲(新)

结构化学复习提纲 ()

数据结构课程设计报告