数据结构 - 机器学习

1、判断：树结构中每个结点最多只有一个直接前驱。答：对2、判断：二叉树中每个结点的度最大为 2，因此二叉树是一种特殊的树。答：对3、判断：由树转化为二叉树，其根结点的右子树总是空的。答：对4、判断：若有一个结点是某二叉树的前序遍历序列中的第一个结点，则它也一定是这棵二叉树的中序遍历序列中的第一个结点。答：错5、判断：若一个树叶是某二叉树的前序遍历序列中的最后一个结点，则它也一定是这棵二叉树的中序遍历序列中的最后一个结点。答：对6、判断：在满二叉树中，存在度为 1的结点。答：对7、判断：在任意一棵二叉树中，终端结点的个数等于度为 2的结点个数加 1。答：对8、判断：在中序线索二叉树中，右线索若不为空，则一定指向其双亲。答：错9、深度为 

1、判断题1）串中任意个字符组成的子序列称为该串的子串。(√)2）设 S串的长度为 n，子串的长度为 m，那么子串定位算法的平均时间复杂度在最好情况下是0(n+m）。(√)3）在顺序存储结构中，串的插入算法是非常方便的。(×)4）设有两个串s1和s2，其中s2是s1的子串，把s2在 s1中首次出现的位置找出来的算法叫作求子串的算法。(×)5）空串是任意串的子串。(×)2、选择1）设有S1,S2,S3,S4,S5,S6六个字符串，其值分别为:S1="Itisabook"，S2＝Φ， S3="tis",S4="boot",

1、堆栈为空（顺序、链式）和满（顺序存储）的判定条件。1）对于单链表：（1）带头节点链表判空条件：        head->next=NULL；（2）不带头节点链表判空条件        head=NULL；（3）对于循环链表判空条件        head->next=head；（4）对于双链表判空条件       head->next=head->prior

1、在单链表和双向链表中，能否从当前结点出发访问任一结点？ 在单链表中只能有当前结点访问其后的任一结点，因为没有指向其前驱结点的指针。在双向链表中既有指向其后继结点的指针又有指向其前驱结点的指针，故可由当前结点出发访问链表中的任一结点。 2、线形表的两种存储结构有哪些优缺点？ 线形表具有两种存储结构，即顺序存储结构和链接存储结构。线形表的顺序存储结构可以直接存取数据元素，方便灵活，效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率；在链接存储结构中，内存采用动态分配，利用率高，但需要增设指示结点之间关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作比较简单。3、向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向

数据的逻辑结构分为线性结构和非线性结构两大类，这两类结构各自的特点是什么？线性结构的特点是：在结构中所有数据成员都处于一个序列中，有且仅有一个开始成员和一个终端成员，并且所有数据成员都最多有一个直接前驱和一个直接后继。例如，一维数组、线性表等就是典型的线性结构。非线性结构的特点是：一个数据成员可能有零个、一个或多个直接前驱和直接后继。例如，树、图或网络等都是典型的非线性结构。什么是数据结构?有关数据结构的讨论涉及哪三个方面?数据结构是指数据以及相互之间的关系。记为：数据结构 ={D,R}。其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。有关数据结构的讨论一般涉及以下三方面的内容： ① 数据成员以及它们相互之间的逻辑关系，也称为数据

前记：这一章中主要对数据排序相关的概念和方法进行了讲解，今天的拓展资源就对排序的基本概念、几种常见排序方法的算法及优缺点、插入排序的算法和C语言实现等，同学们多了解一下。排序：是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。内部排序：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；内部排序的过程是一个逐步扩大记录的有序序列长度的过程。外部排序：若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。　　内排序的方法有许多种，按所用策略不同，可归纳为五类：插入排序、选择排序、交换排序、归并排序和分配排序。　　其中，插入排序主要包括直接插入排序和希尔排序两种；选择排序主要包括直接选择排序和堆排序；交换排

几种查找方法的介绍与比较一、为什么会有不同方式的查找    查找的目的在于从一些数据中寻找一个特定的值，这看似简单的工作之所以产生了形形色色的各种方法，无非都是为了追求更高的效率与更方便的操作。    在范围较小的时候，无论采取什么方法查找，所花费的时间都相差无几，在这种情况下，算法上简单易行，且对存储格式要求较低的线性查找无疑就可以满足我们的要求。    但当所要查找的范围达到了一定程度时，这种方法在耗时上的弱点就逐渐突显，比如我们想在一本字典中查找一个英文单词，如果一页一页一词一词地去搜索，显然是极为愚蠢的。通常，我们会采取这样的方法，比如我们想查找“nature”这个

有趣的七桥问题，以及两种图的遍历方法前记：这一章课件里主要讲了图及其衍生出来的森林、最小生成树等知识点。下面针对图的遍历举一个历史上有趣的问题“七桥问题”，后面还有一个图的两种遍历方法的C++实现，大家多熟悉一下。一题目描述：七桥问题SevenBridgesProblem，18世纪著名古典数学问题之一。在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛及岛与河岸连接起来(如图)。问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点? 发展历程：欧勒于1736年研究并解决了此问题，他把问题归结为如下右图的“一笔画”问题，证明上述走法是不可能的。有关图论研究的热点问题。18世纪初普鲁士的柯尼斯堡，普雷格尔河流经此镇，奈发夫岛位于河中，共有7座桥横跨河上，把全镇连

前记：这一章课件里主要讲了树和二叉树的属性和一些常用的操作。下面针对二叉树的遍历举一个具体的例子，这个题目在等级考试或者面试中都经常出现，大家多思考一下。一题目描述：已知二叉树前序遍历和中序遍历分别为：ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为？答案：DGEBHFCA解题思路：先序遍历的第一个结点是根结点，所以A是根；然后在中序遍历中找到A，（DBGE）A（CHF）；由中序遍历的定义知（DBGE）是左子树的中序遍历，（CHF）是右子树的中序遍历。然后在先序遍历中把左子树和右子树划开，A（BDEG）（CHF），所以B是左子树根，C是右子树根。然后继续在中序遍历中找到B和C，（（D）B（GE））A（C（HF））。对于DBEG，B是根，D是左子树，EG是右子树的中序遍历，对于CH

前记：这一章课件里主要讲了数组和广义表的属性和一些常用的操作。下面针对稀疏矩阵的基本操作做一个具体的实现，大家在运用中可以参考。题目描述：实现一个能进行稀疏矩阵基本运算的运算器，包括相加、相减、相乘。include<time.h>/*用于下面的srand((unsigned)time(NULL));函数的头文件*/#include<stdio.h>#include<stdlib.h>#define MAX_ARRAY_DIM 2#define MAXSIZE 100typedef struct{int aa[MAX_ARRAY_DIM];int dim;