合同范本|数据结构算法的思想总结(分享十六篇)_数据结构算法的思想总结

数据结构算法的思想总结(分享十六篇)。

⬮ 数据结构算法的思想总结

一、单选题(每题 2 分，共20分)

1. 栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素

B.都是先进后出

C.都是先进先出

D.没有共同点

2. 用链接方式存储的队列，在进行插入运算时( ).

A. 仅修改头指针 B. 头、尾指针都要修改

C. 仅修改尾指针 D.头、尾指针可能都要修改

3. 以下数据结构中哪一个是非线性结构( )

A. 队列 B. 栈 C. 线性表 D. 二叉树

4. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在

676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置脚注(10)表示用10进制表示。

A.688 B.678 C.692 D.696

5. 树最适合用来表示( )。

A.有序数据元素 B.无序数据元素

C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据

6. 二叉树的第k层的结点数最多为( ).

kk-1 A.2-1 B.2K+1 C.2K-1 D. 2

7. 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二

分查找，则查找A〔3〕的比较序列的下标依次为( )

A. 1，2，3 B. 9，5，2，3

C. 9，5，3 D. 9，4，2，3

8. 对n个记录的文件进行快速排序，所需要的辅助存储空间大致为

A. O(1) B. O(n) C. O(1og2n) D. O(n2)

9. 对于线性表(7，34，55，25，64，46，20，10)进行散列存储时，若选用H(K)

=K %9作为散列函数，则散列地址为1的元素有( )个，

A.1 B.2 C.3 D.4

10. 设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

A.5 B.6 C.7 D.8

二、填空题(每空1分，共26分)

1. 通常从四个方面评价算法的质量：_________、_________、_________和_________。

2. 一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。

3. 假定一棵树的广义表表示为A(C，D(E，F，G)，H(I，J))，则树中所含的结点数

为__________个，树的深度为___________，树的度为_________。

4. 后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式(3+4X)-2Y/3对应的后缀算式

为_______________________________。

5. 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指

针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。

6. 对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点

分别有_______个和________个。

7. AOV网是一种___________________的图。

8. 在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有

向完全图中，包含有________条边。

9. 假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元

素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。

10. 向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度

___________。

11. 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序

过程的时间复杂度为________。

12. 在快速排序、堆排序、归并排序中，_________排序是稳定的。

三、计算题(每题 6 分，共24分)

1. 在如下数组A中链接存储了一个线性表，表头指针为A [0].next，试写出该线性表。

data next 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};

用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。

4. 画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。

数据结构试卷(一)参考答案

一、选择题(每题2分，共20分)

1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A

二、填空题(每空1分，共26分)

1. 正确性 易读性 强壮性 高效率

2. O(n)

3. 9 3 3

4. -1 3 4 X * + 2 Y * 3 / -

5. 2n n-1 n+1

6. e 2e

7. 有向无回路

8. n(n-1)/2 n(n-1)

9. (12，40) ( ) (74) (23,55，63)

10.增加1

11.O(log2n) O(nlog2n)

12.归并

三、计算题(每题6分，共24分)

1. 线性表为：(78，50，40，60，34，90)

0111

02. 邻接矩阵：11100101101101011110

邻接表如图11所示：

图11

3. 用克鲁斯卡尔算法得到的最小生成树为：

(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20

4. 见图12

26

⬮ 数据结构算法的思想总结

摘要：随着我国信息技术产业日渐成熟，物联网这一新一代信息技术关键技术日渐受到学界重视，基于此，本文就物联网与云计算、物联网数据挖掘需要解决的关键性问题展开分析，并对基于云计算的物联网数据挖掘、实验验证进行了详细论述，期望由此能够为相关业内人士带来必须启发。

随着提出的“数字地球”概念影响力不断扩大，物联网技术与我国民众生活之间的距离日渐拉近，越来越多的物联网应用也开始进入人们视野，各界对物联网的要求也在不断提升，而为了解决物联网领域正面临的数据挖掘难题，正是本文就云计算平台下物联网数据挖掘展开具体研究的原因所在。

物联网作为学界公认的下一代网络发展方向之一，其本身由无所不在的小型传感器设备组成，无论是与我们日常生命联系紧密的计算机与智能手机，还是大型网络的服务器、超级计算机群，均属于物联网的重要组成部分，这也是很多学者将物联网称作新科技革命的原因。在S.Haller等业界权威学者的展望中，其认为物联网技术在未来将实现物理对象无缝集成到信息网络之中并成为参与者，而这些“智能对象”在保护安全与保密的前提下，则能够在网络中找到任何问题的解决方法。对于物联网来说，其具备着全面感知、可靠传递、智能处理三方面特点，而结合现有技术获得基本信息、结合传感器网络和其他通信网络实现物体信息可靠传递、在云计算与模糊识别等技术支持下处理海量异构数据则属于物联网三方面特点的具体表现，由此可见电子元器件、数据处理中心、传输通道三方面能够视作典型物联网应用的组成。

云计算本质上属于一种基于互联网的新计算方式，其能够结合互联网异构、自治服务较好满足用户的计算需要，云计算中的“云”也能够被视作对IT底层基础设施的一种抽象概念。本文研究应用的Hodoop属于典型的云计算基础开发平台，其本质上属于一个分布式系统基础的架构，Hodoop在云计算领域的地位能够说近似于IT产业的Linux系统。Hodoop的核心为分布式文件系统HDFS和MapReduce，前者具备高容错性、高伸缩性等优点，这些就使得Hodoop的布置能够较为简单且低成本的构成分布式文件系统，而后者则具备保证分析和处理的高效性潜力，由此Hodoop即可简单进行数据的整合。总之，Hodoop这一云计算基础开发平台能够透过简单组织计算机资源实现分布式计算云平台搭建，并以此实现云计算相关功用。

简单了解物联网与云计算后，物联网数据挖掘需要解决的关键性问题也应引起人们关注，那里的关键性问题主要由以下几方面构成：

属于较为传统的数据挖掘模式，但是物联网数据不同存储地点的特性则使得该模式的效用无从发挥。

物联网本身具备着数据规模、传感器节点庞大的特点，而为了同时满足其实时处理需求，高性能的中央节点硬件要求务必得到满足。

在有限的节点资源影响下，分布式节点务必负责原始数据的预处理与传递。

由于数据安全性、数据保密、法律约束等因素的影响，物联网不能够将所有数据统一存放在相同数据仓库，这同样对物联网数据挖掘提出了较高挑战。总的来说，现有技术与方式并不能较好满足物联网数据挖掘需要，这也是本文研究开展的原因所在。

结合Hodoop云计算基础开发平台进行基础平台搭建，选取用物联网数据集为例，构成了物联网感知层、传输层、数据层、数据挖掘服务层四部分模块组成的平台，各模块的实现思路与功能如下所示。

物联网感知层主要负责物联网数据的采集，这一采集需要得到目标区域布置的采集节点支持，那里的采集节点主要由摄像头、传感器、其他仪器仪表组成，而由此构成的物联网感知层无线传感器网络，便能够将各采集点采集到的网络数据汇集至节点，数据由此进行汇总储存则能够在传输层的支持下最终传递至云平台的数据中心。

本质上属于具备较高可靠性与高速性、较优无缝性特点的数据传输网络，而基于Hodoop云计算基础开发平台构建的物联网挖掘系统则结合传感器网络、有线网络、无线网络实现了数据传输网络的构建，这就使得物联网感知层所搜集的信息能够更快、更好的传递到云计算数据中心，由此实现的更高质量互通互联，则保证了系统中监测设备的网络化高速数据传输得以实现。

物联网数据具备着异构性、海量性等特点，这就使得基于Hodoop云计算基础开发平台的物联网数据挖掘系统对于物联网数据的存储与处理存在着较高要求，而在本文研究所构建的物联网数据挖掘系统数据层中，该数据层主要由数据源转换模块与分布式存储模块两部分组成，其中前者主要负责物联网异构数据的转换，而后者则主要负责分布式存储物联网所产生的海量数据，由此本文研究的物联网挖掘系统的性能和可行性便得到了较好证实。值得注意的是，分布式存储模块需要结合Hodoop云计算基础开发平台中的HDFS文件系统实现。物联网中的不同对象往往会透过不同的数据类型进行表示，这就使得异构性势必属于物联网的根本性特征，一些相同对象使用不同数据表示便较为直观说明了这一点，而这就使得物联网对数据源转换器有着较高需求。在本文构建的物联网数据挖掘系统中，数据源转换器在其中发挥着保护数据存储完整、保证数据挖掘科学顺利等功能，数据包解码、数据的分布式存储也需要得到该转化器的直接支持，这也是物联网数据挖掘系统中各NameNode节点文件类型为PML的原因。PML能够透过一种通用的方式进行物体描述，而作为基于XML建立的语言，PML在与XML相同核心思想的影响下，其便能够在物品的详细信息带给、物品信息交换等

领域发挥不俗的功能。例如，在本文研究所构建的物联网数据挖掘系统中，PML便在节点数据采集、传输、存储过程中发挥着建模功能，相关建模信息所收录的物体属性信息、位置信息、环境信息、历史元素等资料，便能够保证物品信息实现较高质量的表达，这对于物联网数据挖掘也将带来较为用心影响。

数据挖掘服务层能够细分为数据准备模块、数据挖掘引擎模块、用户模块三部分，三部分模块的具体功用如下所示：

主要负责物联网搜集数据的清理、变换、数据规约。

主要透过数据挖掘算法集、模式评估等功能为物联网数据挖掘系统带给服务，特征、区分、关联、聚类、局外者、趋势和演化分析、偏差分析、类似性分析等能够视作该模块功能的具体组成，这些功能的实现得益于数据挖掘引擎模块中的算法集，Hodoop云计算基础开发平台支持下实现的算法并行化处理则是该模块功能实现的基础。

实现对数据挖掘知识的可视化表示。用户模块是本文研究物联网数据挖掘平台面向使用人员的部分，因此在设计中笔者注重了系统操作的友好性，简单的数据挖掘任务开展、简单获得能够被理解知识均属于设计的优势所在。值得注意的是，为了保证本文研究的物联网数据挖掘系统具备较高的可移植性，设计人员在设计之初便为数据挖掘服务层底层模块设计了开放接口，由此该物联网数据挖掘系统的应用丰富性就能够得到较好保障，表1对本文研究的物联网数据挖掘系统组成进行了直观展示。

基于Hodoop云计算基础开发平台的物联网数据挖掘系统工作流程能够概括为：“用户→主控节点→主控节点允许用户请求→主控节点调用数据挖掘算法→调用数据挖掘算法成功→准备物联网数据→分布式数据挖掘→将结果传递给用户”，而结合这一流程本文将围绕以下几部分开展具体的物联网数据挖掘系统工作流程描述，具体描述如下：

在用户请求物联网数据挖掘系统进行数据挖掘后，系统的主控节点将决定该任务是否能够进行，而在确定能够进行后系统将首先向用户传递能够进行的信息，并随后开始具体的数据挖掘。

在确定物联网数据挖掘系统能够进行数据挖掘后，系统的主控节点将有针对性的选取数据挖掘算法满足用户需要，并结合MapReduce思想与Master/Slave结构进行数据挖掘任务的划分。

在数据挖掘任务的划分下，需要完成具体工作的节点将被分配任务，由此物联网数据挖掘系统的具体数据处理便由此开展，同时JobTracker负责的调度和执行则将最后将数据挖掘结果传递给用户。

为了能够直观决定基于Hodoop云计算基础开发平台物联网数据挖掘系统可行性和性能水平，明晰MapReduce数据挖掘算法在系统中发挥的作用，本文选取了结合Apriori算法开展实验验证的方法，实验验证的环境、过程、结果如下所示。

实验选取了4G内存、500G硬盘、Windows7系统的计算机作为实验基础，并在该计算机中透过虚拟机安装部署了多个分布式节点，其中共3个虚拟机中的一个为NameNodeLinux系统，其余两个则为DateNodeLinux系统。为了保证实验质量与效率，笔者还在该计算机中安装了专门用于Linux系统的Eclipse7.5集成开发环境，在Windows系统中安装了SSHSecureShellClient、各个虚拟机操作系统中安装了SSH服务，由此即可保证本文研究的基于Hodoop云计算基础开发平台物联网数据挖掘系统的顺利使用。

实验环境的搭建后，本文选取了一组用于关联规则算法的实验数据，并将该数据透过C++代码编写的程序透过关键字搜索方式转换成立标准类型大小为1G的PML文件，在HDFS命令下该文件被放入Hadoop平台进行分布式存储，而在运行Java语言编写的Apriori算法后，即可得到物联网数据挖掘系统的运行结果，透过查看系统使用中是否找到了实验数据集中的所有频繁项集便能够直观决定其性能。值得注意的是，为了提升实验的有效性，本文选取了不同大小的文件开展实验，由此实现比较物联网数据挖掘系统运行时间更深入了解其性能。

表2对基于物联网数据挖掘系统的实验结果进行了直观展示，结合该表不难发现，文件大小的提升直接导致物联网数据挖掘系统运行时间的增长，这种增长存在典型的线性趋势，而由于应用Apriori算法的物联网数据挖掘系统实现了频繁项集的发现，本文研究的基于Hodoop云计算基础开发平台物联网数据挖掘系统的扩展性便得到了较为直观展现，其所具备的物联网海量数据挖掘潜力也得到了较好证实。

综上所述，云计算平台能够较好服务于物联网的数据挖掘。而在此基础上，本文研究所提出了完善性与科学性较高的基于Hodoop云计算基础开发平台物联网数据挖掘系统，便直观证明了全文的实践价值。因此，在相关领域的理论研究与实践探索中，本文资料便能够发挥必须参考作用。

[1]汤勇峰.基于云计算平台的物联网数据挖掘研究[J].电脑知识与技术，，1307:218-219.

[2]陈俊丽.基于云计算平台的物联网数据挖掘研究[J].中国新通信，，1821:74-75.

[3]武桂云.基于hadoop平台的分布式数据挖掘系统研究与设计[D].天津大学，.

[4]林昕.基于云计算的大数据挖掘平台构建研究[J].山东工业技术，(17):104.

⬮ 数据结构算法的思想总结

⬮ 数据结构算法的思想总结

一、单项选择题

badcbdcb

二、多项选择题

1.abc

2.abc

3.abe

4.abd

5.ac

6.bcd

三、填空题

(1)物理结构 (2)正确性 (3)先进后出，先进后出 (4)先进先出，先进先出 (5)Preorder(t->lChild);

Preorder(t->rChild); (6) n-1 (7)批处理 (8)A[j-1] = a[j]

四、判断题

ffffffffft

五、简答题

1 答：其好处有：

(1)对带头结点的链表，在表的任何接点之前插入结点或删除表中的任何结点，所要做的都是修改前一个结点的指针域，因为任何元素结点都有前驱结点(若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点和删除结点时操作复杂些)。

(2)对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。

2 答：求该链队中结点个数实际上是计算以hq->front为头指针的单链表中的结点个数。算法如下：

Int Qucount (Lqueue *hq) {

SNode *p=hq->front; Int n=0;

While (p!=NULL) {

n++;

P=P->next; }

Return (n); }

3 ch=getchar(); //取一个数据元素// p=(struct node *)malloc(sizeof(struct node));

//申请一个新结点// p->data=ch;

p->link = pre->link; pre->link = p; 4 答：

Int sum2(int n) {

If (n==0)return 0; Return sum2(n-1)+n*n; }

⬮ 数据结构算法的思想总结

分享：典型的数据结构笔试题，

1. 线性表的顺序存储结构是一种 的存储结构，而链式存储结构是一种___的存储结构。

A.随机存取 B.索引存取 C.顺序存取 D.散列存取

2. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址___。

A. 必须是连续的 B. 部分地址必须是连续的

C. 一定是不连续的 D. 连续或不连续都可以

3. 在一个单链表中p所指结点之前插入一个s (值为e)所指结点时，可执行如下操作：

q=head;

while (q->next!=p) q=q->next;

s= new Node; s->data=e;

q->next= ; //填空

s->next= ; //填空

4. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行____。

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

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

5. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行____。

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

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

6. 在一个单链表中，若删除p所指结点的后续结点，则执行____，

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;

7. 链表不具备的特点是 ____ 。

A 可随机访问任何一个元素 B 插入、删除操作不需要移动元素

C 无需事先估计存储空间大小 D 所需存储空间与线性表长度成正比

8. 在一个长度为n的顺序表中删除第i个元素，要移动 个元素。如果要在第i个元素前插入一个元素，要后移( )个元素。 N-I N-I+1

9. 以下关于线性表的说法不正确的是 。

A 线性表中的数据元素可以是数字、字符、记录等不同类型。

B 线性表中包含的数据元素个数不是任意的。

C 线性表中的每个结点都有且只有一个直接前趋和直接后继。

D 存在这样的线性表：表中各结点都没有直接前趋和直接后继。

答案

1.A/C(这题是考察对概念的理解，可参考第7题，“顺序表才能随即存取，而链表不可以”)

2.D

3.q->next=s;

s->next=p;

4.C

5.B

6.A

7.A(此题绝对选A，因为链表只能根据他的前一个结点才能找到下一个结点，不具备随即访问元素的功能)

8.n-i; n-i+1

9.C

⬮ 数据结构算法的思想总结

(共17分)

1. 单链表结点的 类型定义如下：

typedef str uct LNode {

int data;

struct LNode *next;

} LNode, *Linklist;

写一算法，将带头结点的有 序单链表A和B合并成一新的有序表C。(注:不破坏A和B的原有结构.)

Merge(Linklist A, Linklist B, Linklist &C )

void Merge( Linklist A, Linklist B, Linklist &C)

{ C=(Linklist)malloc(sizeof(LNode));

pa=A->n ext; pb=B->next; pc=C;

while(pa&&pb)

{ pc->next=(Linklist)malloc(sizeof(LNode));

pc=pc->next;

if(pa->data<=pb->data)

{ pc->data=pa->data; pa=pa->next;}

else

{ pc->d ata=pb->data; pb=pb->next;}

}

if(!pa) pa=pb;

while(pa)

{ pc->next=(Linklist)malloc(sizeof(LNode));

pc=pc- >next;

pc->data=pa->data; pa=pa->next;

}

pc->next=NULL;

}

2. 二叉树用二叉链表存储表示。

typedef struct BiTNode {

Tel emType data;

Struct BiTNode *lchild, *rchild;

} BiTNode, *BiTree;

编写一个复制一棵二叉树的递归算法。

BiTree CopyTree(BiTree T) {

if (!T ) return NULL;

if (!( newT = (BiTNode*)malloc(sizeof(BiTNode))))

exit(Overflow);

newT-> data = T-> data;

newT-> lchild = CopyTree(T-> lchild);

newT-> rchild = CopyTree(T-> rchild);

return newT;

1.数据结构试题及答案

2.算法与数据结构答案

⬮ 数据结构算法的思想总结

(每题2分共 20分)

1.有向图的存储结构有(邻接矩阵)、(邻接表)、(十字链表)等方法。

2.已知某二叉树的先序遍历次序为afbcdeg，中序遍历次序为cedbgfa。

其后序遍历次序为(ed cgbfa)。层次遍历次序为(afbcgde)。

3.设有二维数组A 5 x 7 ,每一元素用相邻的4个字节存储，存储器按字节编址。已知A00的存储地址为100。则按行存储时，元素A14的第一个字节的地址是(144);按列存储时，元素A14的第一个字节的地址是(184)。

4.请在下划线上填入适当的语句，完成以下法算。

Status Preordertraverse(Bitree T,Status(*Visit)(Telemtype e)){

//先序非递归遍历二叉树。

Initstack ( S ); Push ( S,T );

While ( !stackempty( S ) )

{ While ( gettop( S, p )&& p ) { visit (p->data ) ; push(S, p->lchild ;}

Pop ( S , p );

If ( !stackempty(s) ) { pop(S, p) ; push( S, p->rchild ); }

}

retu rn ok;

⬮ 数据结构算法的思想总结

1、世界上公认的第一台电子计算机诞生的年代是( 20世纪40年代)

2、20GB的硬盘表示容量约为( 200亿个字节)

3、在微机中，西文字符所采用的编码是( ASCII码)

4、计算机安全是指计算机资产安全，即(计算机信息系统和信息不受自然和人为有害因素威胁和危害)

5、度量计算机运算速度常用的单位是( MIPS)

6、下列设备组中，完全属于计算机输出设备的一组是( 打印机，绘图仪，显示器)

7、计算机操作系统的主要功能是(管理计算机系统的软硬件资源，以充分发挥计算机资源的效率，并为其他软件提供良好的运行环境)

8、计算机软件的确切含义是(计算机程序、数据与相应文档的总称)

9、下列关于计算机病毒的叙述中，错误的是(感染计算机病毒的计算机具有对该病毒的免疫性)

10、在一个非零无符号二进制整数之后添加一个0，则此数的值为原数的( 2倍)

11、以下关于编译程序的说法正确的是( 编译程序完成高级语言程序到低级语言程序的等价翻译)

12、用高级程序设计语言编写的程序(具有良好的可读性和可移植性)

13、一个完整的计算机系统的组成部分的确切提法应该是(计算机硬件和软件 )

14、运算器的完整功能是进行( 算术运算和逻辑运算)

15、计算机网络最突出的优点是(资源共享和快速传输信息)

16、以太网的拓扑结构(总线型)

17、能直接与CPU交换信息的存储器是(内存储器)

18、正确的IP地址是( 202.112.111.1)

19、上网需要在计算机上安装( 浏览器软件)

20、世界上公认的第一台电子计算机诞生在( 美国 )

⬮ 数据结构算法的思想总结

1.设字符串类String具有下列操作：

int Length()const; //计算字符串的长度

chargetData(k); //提取字符串第k个字符的值

若字符串Tar的值为“ababcabcacbab“，的值为‘abcac”时，

(1)给出下面算法执行后返回的结果，

(2)给出下面。算法的功能。

include "String, h"

int unknown(String& Tar, strlng& Pat) coast

{

for (int i

iht j=O;

while (j

if (Tar. getOata(i+j) ==Pat. getData(j)) j+ +

else break;

if (j==Pat. Length()) return i;

return –1;

}

返回结果：

算法功能：

2。已知二叉树中的结点类型BinTrceNode定义为：

struct BinTreeNode {ElemType data; BinTreeNode * left, * right; }

其中data为结点值域，left和right分别为指向左、右子女结点的指针域.下面函数的功能是返回二又树BT中值为X的结点所在的层号.根据题意按标号把合适的内容填写到算法后面相应标号的位置.

int NodeLevel(BinTreeNode * BT, ElemType X)

if (BT==NULL) return -- 1; //空树的层号为一1

else if (BT->data==X) return 0; //根结点的层号为o

//向于树中查找X结点

else {

im cl =NodeLevel(BT->left, X);

if (cl>=0) (1)

iht e2= (2) ;

if ( (3) ) return c2+1;

//若树中不存在K结点则 返回一l

else return -1

}

}

(1)

(2)

(3)

3.假定一个有向无权图采用邻接矩阵存储，请指出F面算法的功能。

Template

void Graph::unknown(int i)

{

int d,j;

d=0;

for (j=0; j

if (Edge[i][j]) {d++ ; Edge[i][j]=0; }

if (Edge[j][i]) {d+ +; Edge[j][i]=0; }

}

CurrentEdges-=d; //CurremEdges //为图中的边数

}

算法功能：

答案

1

返回结果，5

算法功能：字符串的模式匹配算法.

2.

(1)returncl+l

(2)NodeLevel(BT一>,right，X)

(3)=0)

3，从有向无权图中删除所有与顶点i相连的边，包括出边和人边。

⬮ 数据结构算法的思想总结

数据结构报告

引言：

数据结构是计算机科学的一个基础概念，它涉及组织和管理数据的方法和原则。在计算机科学领域，数据结构是一种将数据元素组织为不同形式的数据集合的方法。本报告将介绍数据结构的重要性、主要类型、应用领域以及未来的发展趋势。

一、数据结构的重要性：

数据结构对于计算机科学至关重要。在计算机程序中，数据的组织和存储方式直接影响程序的效率和可维护性。良好的数据结构可以提供高效的数据访问和操作，从而提高程序的执行效率。此外，数据结构还能够帮助开发人员理清程序中各个数据元素之间的关系，提供良好的逻辑结构，使得程序的开发、维护和扩展更加容易。

二、主要类型：

数据结构主要分为线性结构、树结构和图结构三类。

1. 线性结构：包括数组、链表、栈和队列等。数组是一种静态线性结构，具有连续的存储空间，适合随机访问；链表是一种动态线性结构，存储空间可以动态分配，适合插入和删除操作；栈是一种先进后出（LIFO）的线性结构；队列是一种先进先出（FIFO）的线性结构。

2. 树结构：包括二叉树、AVL树、红黑树等。树结构由节点和边组成，每个节点可以有多个子节点。二叉树是一种特殊的树结构，每个节点最多只有两个子节点。

3. 图结构：由节点和边组成，节点之间可以有多条边相连。图结构可以分为有向图和无向图，有向图中的边有方向，无向图中的边没有方向。

三、数据结构的应用领域：

数据结构在计算机科学的各个领域都有广泛应用。

1. 数据库系统：数据结构用于组织和管理数据库中的数据，包括数据表、索引、视图等。

2. 算法设计和分析：数据结构是设计和实现高效算法的基础，不同的数据结构适用于不同的算法问题。

3. 操作系统：数据结构用于管理操作系统中的进程、文件系统和内存等。

4. 网络和图像处理：数据结构可以用于网络路由算法和图像压缩等应用。

5. 人工智能：数据结构在机器学习和深度学习等领域有重要作用。

四、数据结构的发展趋势：

随着计算机科学的不断发展，数据结构也在不断演进和创新。

1. 高性能数据结构：为了提高程序的执行效率，研究人员致力于设计高性能的数据结构，如哈希表、跳表等。

2. 大数据处理：随着大数据时代的到来，数据结构需要能够处理海量的数据，如分布式哈希表、B树等。

3. 数据隐私与安全：在数据共享和隐私保护中，数据结构需要具备安全性，如保护数据的隐私和防止数据泄露。

4. 学科交叉融合：数据结构与其他学科的交叉融合也是未来的发展方向，如数据结构与人工智能、数据结构与生物学等领域的结合。

结论：

数据结构作为计算机科学的基础概念，对于程序的性能和可维护性至关重要。通过良好的数据结构设计，我们可以提高程序的效率，并且使得程序的开发、维护和扩展更加容易。随着计算机科学的发展，数据结构也在不断演变和创新，满足不同应用领域和需求。因此，深入理解和掌握数据结构的原理和应用是每一个计算机科学从业者所必备的基本素质。

⬮ 数据结构算法的思想总结

如果把“数据化”作为人类社会走向信息时代的初级阶段，那么大数据技术的出现则可视为“数据颠覆传统”的中级阶段。在这一阶段，信息无所不在无所不包，随着技术的进步以及大数据的运用，改变了传统认识论模式，出现了从因果关系到相关关系的思维变革，大数据为我们的研究和管理工作带来了“三大变化”：第一，数据只求规模，不求样本；第二，数据求杂求量，不苛求精确度；第三，分析和处理数据只求相关性，不求原因。从教育行业来看，大数据技术将会为教育的发展带来新的挑战与机遇。高等学校在信息化的过程中会产生大量的数据，这当中包含了教师与学生的交流的信息、注册与选课信息、学籍与成绩信息以及各种校园卡信息等，这些大数据完整且客观性强，有非常高的应用价值，应用前景更加广阔。利用大数据技术，可以在很大程度上帮助学校对资源管理、教学模式、教学内容、教学方法进行创新，提升教育理念，进而满足社会对高等教育的个性化需求，为社会培养出更加优秀的人才。目前，高等学校的信息化系统建设正不断发展和完善，除了校园网络、各种数据管理系统、远程教学系统之外，还有数字化校园、图书馆信息管理系统等，如何对这些系统所产生的海量数据进行综合分析，为学校管理提供决策支持和帮助，建立高效的智慧化校园，已成为一个非常突出的问题。数据的价值是巨大的，虽然也会产生大量冗余信息，但是通过精准的分析，大数据将产生巨大作用。从高等教育的角度来看，教育管理、思维方式、学习行为、教学评估等，无不受到大数据的影响。

⬮ 数据结构算法的思想总结

(每题2分共28分)

1.在下列排序方法中，( c )方法平均时间复杂度为0(nlogn)，最坏情况下时间复杂度为0(n2);( d )方法所有情况下时间复杂度均为0(nlogn)。

a. 插入排序 b. 希尔排序 c. 快速排序 d. 堆排序

2. 在有n个结点的二叉树的二叉链表表示中，空指针数为( b )。

a.不定 b.n+1 c.n d.n-1

3. 下列二叉树中，( a )可用于实现符号不等长高效编码。

a.最优二叉树 b.次优查找树 c.二叉平衡树 d.二叉排序树

4. 下列查找方法中，( a )适用于查找有序单链表。

a.顺序查找 b.二分查找 c.分块查找 d.哈希查找

5. 在顺序表查找中，为避免查找过程中每一步都检测整个表是否查找完毕，可采用( a )方法。

a.设置监视哨 b.链表存贮 c.二分查找 d.快速查找

6. 在下列数据结构中， ( c )具有先进先出特性，( b )具有先进后出特性。

a.线性表 b.栈 c.队列 d.广义表

7.具有m个结点的二叉排序树，其最大深度为( f )，最小深度为( b )。

a. log 2 m b. └ log2 m ┘ +1 c. m/2

d .┌ m/2 ┐ -1 e. ┌ m/2 ┐ f. m

8.已知一组待排序的.记录关键字初始排列如下：56,34,58,26,79,52,64,37,28,84,57。

下列选择中( c )是快 速排序一趟排序的结果。

( b )是希尔排序(初始步长为4)一趟排序的结果。

( d )是基数排序一趟排序的结果。

( a )是初始堆(大堆顶)。

a. 84，79，64，37，57，52，58，26，28，34，56。

b. 28，34，57，26，5 6，52，58，37，79，84，64。

c. 28，34，37，26，52，56，64，79，58，84，57。

d. 52，34，64，84，56，26，37，57，58，28，79。

e. 34，56，26，58，52，64，37，28，79，57，84。

f. 34，56，26，58，52，79，37，64，28，84，57。

⬮ 数据结构算法的思想总结

数据结构(C语言版)实验报告;专业：计算机科学与技术、软件工程;学号:____201240703061_____;班级:_________软件二班________;姓名:________朱海霞__________;指导教师:___刘遵仁_____________;青岛大学信息工程学院;2013年10月;实验1;实验题目：顺序存储结构线性表的插入和删除;实验目

数据结构(C语言版) 实验报告

专业：计算机科学与技术、软件工程

学号:____201240703061___________________

班级:_________软件二班______________

姓名:________朱海霞______________

指导教师:___刘遵仁________________

青岛大学信息工程学院

2013年10月

实验1

实验题目：顺序存储结构线性表的插入和删除

实验目的：

了解和掌握线性表的逻辑结构和顺序存储结构，掌握线性表的基本算法及相关的时间性能分析。

实验要求：

建立一个数据域定义为整数类型的线性表，在表中允许有重复的数据;根据输入的数据，先找到相应的存储单元，后删除之。

实验主要步骤：

理解给出的示例程序。

2、调试程序，并设计输入一组数据(3，-5，6，8，2，-5，4，7，-9)，测试程序的如下功能：根据输入的数据，找到相应的存储单元并删除，显示表中所有的数据。

程序代码:

#include

#include

#define OK 1

#define ERROR 0

#define OVERFLOW -2

#define LIST_INIT_SIZE 100

#define LISTINCREMENT 10

typedef struct{

int* elem;

int length;

int listsize;

}Sqlist;

int InitList_Sq(Sqlist &L){

L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));

if(!L.elem) return -1;

L.length=0;

L.listsize=LIST_INIT_SIZE;

return OK;

}

int ListInsert_Sq(Sqlist&L,int i,int e){

if(i<1||i>L.length+1) return ERROR;

if(L.length==L.listsize){

int *newbase;

newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));

if(!newbase) return -1;

L.elem=newbase;

L.listsize+=LISTINCREMENT;

}

int *p,*q;

q=&(L.elem[i-1]);

for(p=&(L.elem[L.length-1]);p>=q;--p)

*(p+1)=*p;

*q=e;

++L.length;

return OK;

}

int ListDelete_Sq(Sqlist &L,int i,int e){

int *p,*q;

if(i<1||i>L.length)return ERROR;

p=&(L.elem[i-1]);

e=*p;

q=L.elem+L.length-1;

for(++p;p<=q;++p)

*(p-1)=*p;

--L.length;

return OK;

}

int main(){

Sqlist L;

InitList_Sq(L);//初始化

int i,a[]={3,-5,6,8,2,-5,4,7,-9};

for(i=1;i<10;i++)

ListInsert_Sq(L,i,a[i-1]);

for(i=0;i<9;i++)

printf(" %d",L.elem[i]);

printf(" ");//插入9个数

ListInsert_Sq(L,3,24);

for(i=0;i<10;i++)

printf(" %d",L.elem[i]);

printf(" ");//插入一个数

int e;

ListDelete_Sq(L,2, e);

for(i=0;i<9;i++)

printf(" %d",L.elem[i]);//删除一个数

printf(" ");

return 0;

}

实验结果：

3，-5,6,8,2，-5,4,7，-9

3，-5,24,6,8,2，-5,4,7，-9

3,24,6,8,2，-5,4,7，-9

心得体会：

顺序存储结构是一种随机存取结构，存取任何元素的时间是一个常数，速度快;结构简单，逻辑上相邻的元素在物理上也相邻;不使用指针，节省存储空间;但是插入和删除元素需要移动大量元素，消耗大量时间;需要一个连续的存储空间;插入元素可能发生溢出;自由区中的存储空间不能被其他数据共享 实验2

实验题目：单链表的插入和删除

实验目的：

了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。

实验要求：

建立一个数据域定义为字符类型的单链表，在链表中不允许有重复的字符;根据输入的字符，先找到相应的结点，后删除之。

实验主要步骤：

理解给出的示例程序。

4、调试程序，并设计输入数据(如：A，C，E，F，H，J，Q，M)，测试程序的如下功能：不允许重复字符的插入;根据输入的字符，找到相应的结点并删除。

5、修改程序：

(1) 增加插入结点的功能。

(“后插”法。

程序代码:

#include

#include

#define NULL 0

#define OK 1

#define ERROR 0

typedef struct LNode{

int data;

struct LNode *next;

}LNode,*LinkList;

int InitList_L(LinkList &L){

L=(LinkList)malloc(sizeof(LNode)); L->next=NULL;

return OK;

}

int ListInsert_L(LinkList &L,int i,int e){ LinkList p,s;

int j;

p=L;j=0;

while(p&&j

p=p->next;++j;

}

if(!p||j>i-1)

return ERROR;

s=(LinkList)malloc(sizeof(LNode)); s->data=e;

s->next=p->next;

p->next=s;

return OK;

}

int ListDelete_L(LinkList&L,int i,int &e){ LinkList p,q;

int j;

p=L;j=0;

while(p->next&&j

p=p->next;++j;

}

if(!(p->next)||j

return ERROR;

q=p->next;p->next=q->next; e=q->data;free(q);

return OK;

}

int main(){

LinkList L,p;

char a[8]={'A','C','E','F','H','J','Q','U'}; int i,j;

InitList_L(L);

for(i=1,j=0;i<=8,j<8;i++,j++) ListInsert_L(L,i,a[j]);

p=L->next;

while(p!=NULL){

printf("%c ",p->data); p=p->next;

}//插入八个字符printf(" ;实验结果：;ACEFHJQU;ABCEFHJQU;ABEFHJQU;心得体会：;单链表是通过扫描指针P进行单链表的`操作;头指针唯;实验掌握栈的顺序存储结构和链式存储结构，以便在实;掌握栈的基本运算，如：入栈与出栈

}

}//插入八个字符 printf(" "); i=2; int e; ListInsert_L(L,i,'B'); p=L->next; while(p!=NULL){ printf("%c ",p->data); p=p->next; }//插入一个字符 printf(" "); i=3; ListDelete_L(L,i,e); p=L->next; while(p!=NULL){ printf("%c ",p->data); p=p->next; } printf(" "); return 0;

实验结果：

A C E F H J Q U

A B C E F H J Q U

A B E F H J Q U

心得体会：

单链表是通过扫描指针P进行单链表的操作;头指针唯一标识点链表的存在;插入和删除元素快捷，方便。

实验3

实验题目：栈操作设计和实现

实验目的：

1、掌握栈的顺序存储结构和链式存储结构，以便在实际中灵活应用。

2、掌握栈的特点，即后进先出和先进先出的原则。

3、掌握栈的基本运算，如：入栈与出栈等运算在顺序存储结构和链式存储结构上的实现。

实验要求：

回文判断：对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如

“abba”是回文，而“abab”不是回文。

实验主要步骤

(1)数据从键盘读入;

(2)输出要判断的字符串;

(3)利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“Yes”，否则输出“No”。

程序代码:

#include

#include

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define OVERFLOW -2

#define N 100

#define STACK_INIT_SIZE 100

#define STACKINCREMENT 10

typedef struct{

int *base; // 在栈构造之前和销毁之后，base的值为NULL int *top; // 栈顶指针

int stacksize; // 当前已分配的存储空间，以元素为单位

} SqStack;

int InitStack(SqStack &S)

{ // 构造一个空栈S

if(!(S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int))))

exit(OVERFLOW); // 存储分配失败

=S.base;

S.stacksize=STACK_INIT_SIZE;

return OK;

}

int StackEmpty(SqStack S)

{ // 若栈S为空栈，则返回TRUE，否则返回FALSE

if(==S.base)

return TRUE;

else

return FALSE;

}

int Push(SqStack &S, int e)

{ // 插入元素e为新的栈顶元素

if(-S.base>=S.stacksize) // 栈满，追加存储空间

{

S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int)); if(!S.base)

exit(OVERFLOW); // 存储分配失败

=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*()++=e;

return OK;

}

int Pop(SqStack &S,int &e)

{ // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK;否则返回ERROR if(==S.base)

return ERROR;

e=*--;

return OK;

}

int main(){

SqStack s;

int i,e,j,k=1;

char ch[N] = {0},*p,b[N] = {0};

if(InitStack(s)) // 初始化栈成功

{

printf("请输入表达式: ");

gets(ch);

p=ch;

while(*p) // 没到串尾

Push(s,*p++);

for(i=0;i

if(!StackEmpty(s)) {// 栈不空

Pop(s,e); // 弹出栈顶元素

b[i]=e;

}

}

for(i=0;i

if(ch[i]!=b[i])

k=0;

}

if(k==0)

printf("NO!");

else

printf("输出:")

printf("YES!");

}

return 0;

}

实验结果：

请输入表达式：

abcba

输出：YES!

心得体会：栈是仅能在表尾惊醒插入和删除操作的线性表，具有先进后出的性质，这个固有性质使栈成为程序设计中的有用工具。

实验4

实验题目：二叉树操作设计和实现

实验目的：

掌握二叉树的定义、性质及存储方式，各种遍历算法。

实验要求：

采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。

实验主要步骤：

理解程序。

中序和后序以及按层次遍历序列，求所有叶子及结点总数。

程序代码:

实验结果：

心得体会：

实验5

实验题目：图的遍历操作

实验目的：

掌握有向图和无向图的概念;掌握邻接矩阵和邻接链表建立图的存储结构;掌握DFS及BFS对图的遍历操作;了解图结构在人工智能、工程等领域的广泛应用。

实验要求：

采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操作。

实验主要步骤：

设计一个有向图和一个无向图，任选一种存储结构，完成有向图和无向图的DFS(深度优先遍历)和BFS(广度优先遍历)的操作。

1. 邻接矩阵作为存储结构

#include"stdio.h"

#include"stdlib.h"

#define MaxVertexNum 100 //定义最大顶点数

typedef struct{

char vexs[MaxVertexNum]; //顶点表

int edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵，可看作边表 int n,e; //图中的顶点数n和边数e

}MGraph; //用邻接矩阵表示的图的类型

//=========建立邻接矩阵=======

void CreatMGraph(MGraph *G)

{

int i,j,k;

char a;

printf("Input VertexNum(n) and EdgesNum(e): ");

scanf("%d,%d",&G->n,&G->e); //输入顶点数和边数

scanf("%c",&a);

printf("Input Vertex string:");

for(i=0;in;i++)

{

scanf("%c",&a);

G->vexs[i]=a; //读入顶点信息，建立顶点表

}

for(i=0;in;i++)

for(j=0;jn;j++)

G->edges[i][j]=0; //初始化邻接矩阵

printf("Input edges,Creat Adjacency Matrix ");

for(k=0;ke;k++) { //读入e条边，建立邻接矩阵

scanf("%d%d",&i,&j); //输入边(Vi，Vj)的顶点序号

G->edges[i][j]=1;;G->edges[j][i]=1;//若为;//=========定义标志向量，为全局变量=;typedefenum{FALSE,TRUE}B;Booleanvisited[MaxVertex;//========DFS：深度优先遍历的递归算;voidDFSM(MGraph*G,inti);{//以Vi为出发点

G->edges[i][j]=1;

G->edges[j][i]=1; //若为无向图，矩阵为对称矩阵;若建立有向图，去掉该条语句 }

}

//=========定义标志向量，为全局变量=======

typedef enum{FALSE,TRUE} Boolean;

Boolean visited[MaxVertexNum];

//========DFS：深度优先遍历的递归算法======

void DFSM(MGraph *G,int i)

{ //以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵

给出你的编码

//===========BFS：广度优先遍历=======

void BFS(MGraph *G,int k)

{ //以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索

给出你的编码

//==========主程序main =====

void main()

{

int i;

MGraph *G;

G=(MGraph *)malloc(sizeof(MGraph)); //为图G申请内存空间

CreatMGraph(G); //建立邻接矩阵

printf("Print Graph DFS: ");

DFS(G); //深度优先遍历

printf(" ");

printf("Print Graph BFS: ");

BFS(G,3); //以序号为3的顶点开始广度优先遍历

printf(" ");

}

2. 邻接链表作为存储结构

#include"stdio.h"

#include"stdlib.h"

#define MaxVertexNum 50 //定义最大顶点数

typedef struct node{ //边表结点

int adjvex; //邻接点域

struct node *next; //链域

}EdgeNode;

typedef struct vnode{ //顶点表结点

char vertex; //顶点域

EdgeNode *firstedge; //边表头指针

}VertexNode;

typedef VertexNode AdjList[MaxVertexNum]; //AdjList是邻接表类型 typedef struct {

AdjList adjlist; //邻接表

int n,e; //图中当前顶点数和边数

} ALGraph; //图类型

//=========建立图的邻接表=======

void CreatALGraph(ALGraph *G)

{

int i,j,k;

char a;

EdgeNode *s; //定义边表结点

printf("Input VertexNum(n) and EdgesNum(e): ");

scanf("%d,%d",&G->n,&G->e); //读入顶点数和边数

scanf("%c",&a);

printf("Input Vertex string:");

for(i=0;in;i++) //建立边表

{

scanf("%c",&a);

G->adjlist[i].vertex=a; //读入顶点信息

G->adjlist[i].firstedge=NULL; //边表置为空表

}

printf("Input edges,Creat Adjacency List ");

for(k=0;ke;k++) { //建立边表

scanf("%d%d",&i,&j); //读入边(Vi，Vj)的顶点对序号

s=(EdgeNode *)malloc(sizeof(EdgeNode)); //生成边表结点

s->adjvex=j; //邻接点序号为j

s->next=G->adjlist[i].firstedge;

G->adjlist[i].firstedge=s; //将新结点*S插入顶点Vi的边表头部

s=(EdgeNode *)malloc(sizeof(EdgeNode));

s->adjvex=i; //邻接点序号为i

s->next=G->adjlist[j].firstedge;

G->adjlist[j].firstedge=s; //将新结点*S插入顶点Vj的边表头部

}

}

//=========定义标志向量，为全局变量=======

typedef enum{FALSE,TRUE} Boolean;

Boolean visited[MaxVertexNum];

//========DFS：深度优先遍历的递归算法======

void DFSM(ALGraph *G,int i)

{ //以Vi为出发点对邻接链表表示的图G进行DFS搜索

给出你的编码

//==========BFS：广度优先遍历=========

void BFS(ALGraph *G,int k)

{ //以Vk为源点对用邻接链表表示的图G进行广度优先搜索

给出你的编码

//==========主函数===========

void main()

{

int i;

ALGraph *G;

G=(ALGraph *)malloc(sizeof(ALGraph));

CreatALGraph(G);

printf("Print Graph DFS: ");

DFS(G);

printf(" ");

printf("Print Graph BFS: ");

BFS(G,3);

printf(" ");

}

实验结果：

1. 邻接矩阵作为存储结构

2. 邻接链表作为存储结构

心得体会：

实验6

实验题目：二分查找算法的实现

实验目的：

掌握二分查找法的工作原理及应用过程，利用其工作原理完成实验题目中的内容。。

实验要求：

编写程序构造一个有序表L，从键盘接收一个关键字key，用二分查找法在L中查找key，若找到则提示查找成功并输出key所在的位置，否则提示没有找到信息。。

实验主要步骤：

1. 建立的初始查找表可以是无序的，如测试的数据为{3，7，11，15，17，21，35，42，50｝或者{11，21，7，3，15，50，42，35，17｝。

2. 给出算法的递归和非递归代码;

3. 如何利用二分查找算法在一个有序表中插入一个元素x，并保持表的有序性?

程序代码

实验结果：

心得体会：

实验7

实验题目：排序

实验目的：

掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根据实际问题的特点和要求选择合适的排序方法。

实验要求：

实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运行速度。

实验主要步骤：

程序代码

⬮ 数据结构算法的思想总结

一、选择题

1. 下面关于算法说法错误的是（ ） A．算法最终必须由计算机程序实现

B.为解决某问题的算法同为该问题编写的程序含义是相同的

C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的

2. 下述哪一条是顺序存储结构的优点？（ A．插入运算方便 B．存储密度大 C．删除运算方便

D．可方便地用于各种逻辑结构的存储表示

3. 线性表是具有n个（ ）的有限序列（n>0）。

A．表元素 B．字符 C．数据项 D. 数据元素

4. 若某线性表最常用的操作是存取任一指定序号的`元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 5. 下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（ ）

A. 直接插入排序 B. 快速排序 C. 直接选择排序 D. 堆排序 6. 输入序列为ABC，可以变为CBA时，经过的栈操作为（ ）

A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop 7. 设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）

A．求子串 B．联接 C．匹配 D．求串长

8. 二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是： （ ）

A、 E B、 F C、 G D、 H

9. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ） A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 10. 已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )

A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE

A,并已0右孩子的平衡因子为1,则应作（ ）型调整以使4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中 ）

．6 C．7 D．8 D ） ．3 C．4 D．

14. 设如左图所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（ ）

a e b d f c a c f d e b

a e d f c b a e f d c b a e f d b c

A．5个 B．4个 C．3个 D．2个

二、填空题

1. 在下面的程序段中，对ｘ的赋值语句的频度为 _ _（表示为n的函数） For(i=1;i<=n;i++)

For(j=1;j<=i;j++) X+=3;

2. 循环队列的引入，目的是为了克服 ____________ ____ 3. 一个栈的输入序列是：1，2，3则不可能的栈输出序列是_______________ 4. 如果结点A有 3个兄弟，而且B是A的双亲，则B的度是_______________。 5. 当使用监视哨顺序查找n个元素的顺序表时，若查找失败，则比较关键字的次数为________________

6. 设一棵完全二叉树具有1000个结点，则它有________个叶子结点，有________个度为2的结点。

7. N个顶点的连通图的生成树含有 _条边

8. 已知一无向图G=（V，E），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是_______________遍历方法

9.分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是 ___算法，最费时间的是 ____算法。 10.若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 _______和记录的 ____ 。

三、应用题

1.考查树和二叉树的应用（本题8分）

2.考查图的方面的应用（本题8分）

3.考查查找方面的应用（本题8分）

四、计算题

1.考查排序方面的应用

2.考查哈希表的应用（本题8分）

一起合同网-hc179.com优质资料:
• 数据结构课件 | 哈夫曼编码算法思想总结 | 店长总结分享 | 店铺销售总结分享 | 数据结构算法思想总结 | 数据结构算法思想总结

五、算法设计题

考查栈、树和二叉树、查找和排序的算法设计与填空。

⬮ 数据结构算法的思想总结

一、实验目的及要求

1)掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们。

本实验训练的要点是“栈”和“队列”的观点;

二、实验内容

1) 利用栈，实现数制转换。

2) 利用栈，实现任一个表达式中的语法检查(选做)。

3) 编程实现队列在两种存储结构中的基本操作(队列的初始化、判队列空、入队列、出队列);

三、实验流程、操作步骤或核心代码、算法片段

顺序栈：

Status InitStack(SqStack &S)

{

S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));

if(!S.base)

return ERROR;

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

return OK;

}

Status DestoryStack(SqStack &S)

{

free(S.base);

return OK;

}

Status ClearStack(SqStack &S)

{

S.top=S.base;

return OK;

}

Status StackEmpty(SqStack S)

{

if(S.base==S.top)

return OK;

return ERROR;

}

int StackLength(SqStack S)

{

return S.top-S.base;

}

Status GetTop(SqStack S,ElemType &e)

{

if(S.top-S.base>=S.stacksize)

{

S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));

if(!S.base) return ERROR;

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*S.top++=e;

return OK;

}

Status Push(SqStack &S,ElemType e)

{

if(S.top-S.base>=S.stacksize)

{

S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));

if(!S.base)

return ERROR;

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*S.top++=e;

return OK;

}

Status Pop(SqStack &S,ElemType &e)

{

if(S.top==S.base)

return ERROR;

e=*--S.top;

return OK;

}

Status StackTraverse(SqStack S)

{

ElemType *p;

p=(ElemType *)malloc(sizeof(ElemType));

if(!p) return ERROR;

p=S.top;

while(p!=S.base)//S.top上面一个...

{

p--;

printf("%d ",*p);

}

return OK;

}

Status Compare(SqStack &S)

{

int flag,TURE=OK,FALSE=ERROR;

ElemType e,x;

InitStack(S);

flag=OK;

printf("请输入要进栈或出栈的元素：");

while((x= getchar())!='#'&&flag)

{

switch (x)

{

case '(':

case '[':

case '{':

if(Push(S,x)==OK)

printf("括号匹配成功!\n\n");

break;

case ')':

if(Pop(S,e)==ERROR || e!='(')

{

printf("没有满足条件\n");

flag=FALSE;

}

break;

case ']':

if ( Pop(S,e)==ERROR || e!='[')

flag=FALSE;

break;

case '}':

if ( Pop(S,e)==ERROR || e!='{')

flag=FALSE;

break;

}

}

if (flag && x=='#' && StackEmpty(S))

return OK;

else

return ERROR;

}

链队列：

Status InitQueue(LinkQueue &Q)

{

Q.front =Q.rear=

(QueuePtr)malloc(sizeof(QNode));

if (!Q.front) return ERROR;

Q.front->next = NULL;

return OK;

}

Status DestoryQueue(LinkQueue &Q)

{

while(Q.front)

{

Q.rear=Q.front->next;

free(Q.front);

Q.front=Q.rear;

}

return OK;

}

Status QueueEmpty(LinkQueue &Q)

{

if(Q.front->next==NULL)

return OK;

return ERROR;

}

Status QueueLength(LinkQueue Q)

{

int i=0;

QueuePtr p,q;

p=Q.front;

while(p->next)

{

i++;

p=Q.front;

q=p->next;

p=q;

}

return i;

}

Status GetHead(LinkQueue Q,ElemType &e)

{

QueuePtr p;

p=Q.front->next;

if(!p)

return ERROR;

e=p->data;

return e;

}

Status ClearQueue(LinkQueue &Q)

{

QueuePtr p;

while(Q.front->next )

{

p=Q.front->next;

free(Q.front);

Q.front=p;

}

Q.front->next=NULL;

Q.rear->next=NULL;

return OK;

}

Status EnQueue(LinkQueue &Q,ElemType e)

{

QueuePtr p;

p=(QueuePtr)malloc(sizeof (QNode));

if(!p)

return ERROR;

p->data=e;

p->next=NULL;

Q.rear->next = p;

Q.rear=p; //p->next 为空

return OK;

}

Status DeQueue(LinkQueue &Q,ElemType &e)

⬮ 数据结构算法的思想总结

1)掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们。

本实验训练的要点是“栈”和“队列”的观点;

1) 利用栈，实现数制转换。

2) 利用栈，实现任一个表达式中的语法检查(选做)。

3) 编程实现队列在两种存储结构中的基本操作(队列的初始化、判队列空、入队列、出队列);

顺序栈：

Status InitStack(SqStack &S)

{

S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));

return ERROR;

=S.base;

S.stacksize=STACK_INIT_SIZE;

return OK;

}

Status DestoryStack(SqStack &S)

{

free(S.base);

return OK;

}

Status ClearStack(SqStack &S)

{

=S.base;

return OK;

}

return OK;

return ERROR;

}

{

return -S.base;

}

Status GetTop(SqStack S,ElemType &e)

{

if(-S.base>=S.stacksize)

{

S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));

if(!S.base) return ERROR;

=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*++=e;

return OK;

}

Status Push(SqStack &S,ElemType e)

{

if(-S.base>=S.stacksize)

{

S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));

return ERROR;

=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*++=e;

return OK;

}

Status Pop(SqStack &S,ElemType &e)

return ERROR;

e=*--;

return OK;

}

{

ElemType *p;

p=(ElemType *)malloc(sizeof(ElemType));

if(!p) return ERROR;

p=;

while(p!=S.base)//上面一个...

{

p--;

printf(“%d ”,*p);

}

return OK;

}

{

int flag,TURE=OK,FALSE=ERROR;

ElemType e,x;

InitStack(S);

flag=OK;

while((x= getchar)!='#'&&flag)

case '{':

printf(“括号匹配成功!nn”);

break;

printf(“没有满足条件n”);

flag=FALSE;

}

break;

break;

break;

}

}

if (flag && x=='#' && StackEmpty(S))

return ERROR;

}

链队列：

Status InitQueue(LinkQueue &Q)

{

Q.front =Q.rear=

(QueuePtr)malloc(sizeof(QNode));

if (!Q.front) return ERROR;

Q.front->next = NULL;

return OK;

}

Status DestoryQueue(LinkQueue &Q)

{

Q.rear=Q.front->next;

free(Q.front);

Q.front=Q.rear;

}

return OK;

}

Status QueueEmpty(LinkQueue &Q)

{

return OK;

return ERROR;

}

{

int i=0;

QueuePtr p,q;

p=Q.front;

{

i++;

p=Q.front;

q=p->next;

p=q;

}

return i;

}

Status GetHead(LinkQueue Q,ElemType &e)

{

QueuePtr p;

p=Q.front->next;

return ERROR;

e=p->data;

return e;

}

Status ClearQueue(LinkQueue &Q)

{

QueuePtr p;

{

p=Q.front->next;

free(Q.front);

Q.front=p;

}

Q.front->next=NULL;

Q.rear->next=NULL;

return OK;

}

Status EnQueue(LinkQueue &Q,ElemType e)

{

QueuePtr p;

p=(QueuePtr)malloc(sizeof (QNode));

return ERROR;

p->data=e;

p->next=NULL;

Q.rear->next = p;

return OK;

}

Status DeQueue(LinkQueue &Q,ElemType &e)

{

QueuePtr p;

return ERROR;

p = Q.front->next;

e = p->data;

Q.front->next = p->next;

Q.rear = Q.front; //只有一个元素时(不存在指向尾指针)

free (p);

return OK;

}

Status QueueTraverse(LinkQueue Q)

{

QueuePtr p,q;

{

printf(“这是一个空队列!n”);

return ERROR;

}

p=Q.front->next;

{

q=p;

printf(“%ddata);

q=p->next;

p=q;

}

return OK;

}

循环队列：

Status InitQueue(SqQueue &Q)

{

Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));

exit(OWERFLOW);

Q.front=Q.rear=0;

return OK;

}

Status EnQueue(SqQueue &Q,QElemType e)

{

if((Q.rear+1)%MAXQSIZE==Q.front)

return ERROR;

Q.base[Q.rear]=e;

Q.rear=(Q.rear+1)%MAXQSIZE;

return OK;

}

Status DeQueue(SqQueue &Q,QElemType &e)

return ERROR;

e=Q.base[Q.front];

Q.front=(Q.front+1)%MAXQSIZE;

return OK;

}

{

return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;

}

Status DestoryQueue(SqQueue &Q)

{

free(Q.base);

return OK;

}

Status QueueEmpty(SqQueue Q) //判空

return OK;

return ERROR;

}

printf(“这是一个空队列!”);

Q.front++;

}

return OK;

}

推荐阅读: 数据结构课件（经典15篇） 大数据培训总结(经典十六篇) 司法行政思想总结（分享十六篇） 算法交易研究员工作总结(范本十六篇) 哈夫曼编码算法思想总结（通用十篇）

想了解更多数据结构算法的思想总结的资讯，请访问：数据结构算法的思想总结

热门标签: 快乐分享的句子 外刊分享活动总结 分享的作文 分享英雄故事活动总结 大数据培训总结 健康达人分享活动总结

文章来源：https://www.hc179.com/hetongfanben/155295.html