标题来历答案为手工核对收拾

第一章 序文

1. 简述数据规划的界说和构成

数据规划是指彼此之间存在一种或多种特定联络的数据元素的集结包括逻辑规划、物理规划和数据运算。

2. 数据的存储规划有哪几种

次序存储

特征存储空间的地址接连逻辑联络。

利益存储密度大在o(1)内查询、批改元素。

缺陷标明联络才能弱。

链式存储

特征占用空间任意。

利益空间任意便于动态打点内存。

缺陷空间开支大在o(n)内查找、批改元素。

索引存储

特征存储空间是多段接连空间索引表由若干索引项构成。

利益次序和链式联系保证数据的仅有性。

缺陷创建索引和维护索引需要时刻对数据增删查改的一起也要对索引入行维护。

哈希存储

特征又称散列存储

利益使用数据的某一特征造访和存储在o(1)内遍历元素。

缺陷好的hash很难有时会发生冲突。

3. 啥是算法的时刻凌乱度和空间凌乱度

时刻凌乱度是一个函数”>定量描绘了算法在运转进程中占用存储空间巨细。

算法的时刻凌乱度一般用大o符号表述时刻凌乱度的极限景象称为算法的“渐近时刻凌乱度”。

4. 数据规划的凌乱度o(1)是啥意思

常数阶的凌乱度耗时/耗空间都不变。

5. 啥是笼统数据规划

笼统数据类型abstract?data type,adt是指一个数学模型以及界说在这个模型上的一组操作。笼统数据类型的界说只是取决于它的一组逻辑特性而与它在核算机中的标明和完成无关。

6. 数据的根柢单位和最小单位别离是啥

最小单位是bit1字节等于8个比特。

7. 简述一个好的算法大约抵达哪些方针

正确性算法的输出大约契合预期的成果即算法大约在给定的输入条件下可以发生正确的输出。

可读性算法大约易于阅览和了解这样可以便利其他开发人员或团队成员进行代码的维护和批改。

高效性算法大约在可承受的时刻内结束使命而且在处置很大都据时也可以快速有用地运转。

可拓宽性算法大约可以处置不一样规划的数据和不一样类型的疑问而且可以轻松地进行批改和拓宽。

鲁棒性算法大约具有较强的鲁棒性而且不会因为一些不可以猜测的情况致使程序溃散或犯错。

可重用性算法大约可以在不一样的场景和项目中被重复运用这可以前进代码的可维护性和开发功率。

8. 算法的五个重要特征

输入、输出、有穷性、断定性和可行性

第二章 线性表 栈 行列 串 数组

1. 线性表和次序表以及链表的差异

次序表与链表均归于线性表只是在逻辑规划和存储方法上有所不一样。

次序表线性表选用次序存储的方法存储就称之为次序表次序表是将表中的结点顺次存放在核算机内存中一组地址接连的存储单元中。

链表线性表选用指针联接的方法存储就称之为链表。

2. 次序表和链表存储的优缺陷

① 次序表存储

利益

经过下标来直接存储。

缺陷

刺进和删去比照慢。

空间浪费无量。?

时刻功能查找 o(1)刺进和删去o(n)。

② 链表存储

利益

存取某个元素速度慢。

保存原有的物理次序。

没有空间捆绑,存储元素的个数无上限,根柢只与内存空间巨细有关。

缺陷

占用额定的空间以存储指针

需要从初步节点一个一个节点去查找元素造访。

时刻功能查找 o(n)刺进和删去o(1)。

3. 头指针和头节点的差异简述链表中引入头节点带来的利益

头指针是一个指向链表第一个实践数据节点的指针头节点是链表中的一个额定的、一般不存储有用数据的辅佐节点。

利益不再需要判别是不是在第一个元素之前刺进或删去第一个元素。

4. 头插法和尾插法的差异

头插法是每次生成的链表节点都刺进到链表头部。而尾插规则是刺进到链表尾部。

5. 数组与线性表的联络

数组是次序表次序表是线性表的一种。

6. 循环行列的次序表中

因为入队时尾指针向前追逐头指针。

7. 栈和行列的差异

栈是后进先出行列是 先出。

8. 怎么区别循环行列是队空仍是队满

牺牲一个存储方位

队空front

计数

有元素入队时0. …

树立一个flag

9. 栈和堆的差异

1、栈区部分变量的值等。

2、堆区程序结束时可以由os回

收。

10. 串是一种特别的线性表请从存储和运算两方面来分析它的特别之处

从存储方面来看串一般是用字符数组来标明的。

在c言语中而在其他编程言语中也有类似的方法。

串的存储是次序存储规划经过数组下标来造访。

此外用来标明串的结束。

从运算方面来看串常见的操作包括串的联接、子串的获取、串的比照、串的匹配等。

串的联接可以用字符串拼接的方法完成构成一个新的串。

子串的获取可以经过指定子串的开始方位和长度来完成或许是依照字典序比照两个串的巨细。

串的匹配是指在一个较长的文本串中查找一个较短的方法串常用的算法包括朴素匹配算法、kmp算法、bm算法等。

11. 介绍一下字符串方法匹配算法朴素方法匹配算法和kmp算法

??????

从主串的第一个字符起直到最终看是不是匹配成功。

kmp根柢思维当匹配失利后假定已匹配相等的序列中有某个后缀正好是方法串的前缀那么就可以将方法串向后滑动到与这些相等字符对齐的方位与主串无关。

第三章 树和二叉树

1. 啥是树

树的界说树是n (n≥0)个结点的有限集。当n称为空树。

在任意一棵非空树中应满足:

1有且仅有一个特定的称为根的结点。

2)当n>1时而且称为根的子树。

二叉树界说二叉树是n (n≥0个结点的有限集结:

①或许为空二叉树0。

②或许由一个根结点和两个互不相交的被称为根的左子树和右子树构成。左子树和右子树

又别离是一棵二叉树。

满二叉树概念

一个二叉树但不是满二叉树)

完全二叉树概念

一棵深度为k的有n个结点的二叉树则这棵二叉树称为完全二叉树。

2. 树的存储规划有哪些

双亲标明法:

这种存储方法选用一组接连空间来存储每个结点其伪指针域为-1。

孩子标明法:

孩子标明法是将每个结点的孩子结点都用单链表联接起来构成一个线性规划叶子结点的孩子链表为空表)。

这种存储方法寻找子孙的操作非常直接而寻找双亲的操作需要遍历n个结点中孩子链表指针域所指向的n个孩子链表。

孩子兄弟标明法:

?????? 孩子兄弟标明法又称二叉树标明法沿此域可以找到结点的一切兄弟结点)。

3. 二叉树与度为2的有序树的差异

则这个孩子结点无需分支配。

4. 完全二叉树与满二叉树的差异

满二叉树是叶子节点那一行是满的与对应的满二叉树的序号共同。

5. 啥是平衡二叉树

?????? 任意结点支配子树高度差的必定值不跨越1的二叉树为平衡二叉树。

如何判别平衡二叉树

初始办法

1.判别以根结点的树是不是为平衡二叉树。求出支配子树的高度判别它们的高度差是不是跨越了1

2.递归判别根的左子树是不是为平衡二叉树

3.递归判别根的右子树是不是为平衡二叉树

留心空树也是平衡二叉树

改进办法

1.首要判别它的左子树是不是为平衡二叉树

2.然后在判别它的右子树是不是为平衡二叉树

3.判别它们是不是为平衡二叉树的一起记载它们的支配子树的深度

4.最终在判别以这个结点为根的树是不是为平衡二叉树

6. 二叉排序树平缓衡二叉树的差异

二叉排序树是左子树节点小于根节点小于右子树节点。

平衡二叉树是支配子树的高度差必定值不跨越1。

7.二叉树的遍历

二叉树的先中后序遍历:

先序遍历

若二叉树为空

1

2

3先序遍历右子树。

中序遍历

若二叉树为空否则,

1

2

3中序遍历右子树。

后序遍历

若二叉树为空

1

2

3造访根结点。

8. 啥是带权途径长度

树的带权途径长度就是树中一切的叶结点的权值乘上其到根结点的途径长度。

9. 哈夫曼树和哈夫曼编码的作用是啥

哈夫曼树又称最优二叉树是一种带权途径长度最短的二叉树。哈夫曼编码可用于紧缩数据。

没有一个编码是另一个编码的前缀就叫前缀编码。

第四章 图

1. 线性表、树、图哪些可所以空的

线性表和树都可所以空的但图不得。

图的极点v必定非空但边即e可认为空。此时图中只需极点没有边。

2. 啥是完全图

完全图是一个简略的无向图其间每对不一样的极点之间都恰连有一条边相连。

3. 简述图的存储规划

邻接矩阵法

?????? 指用一个一维数组存储图中极点的信息存储极点之间邻接联络的二维数组称为邻接矩阵。

邻接表法

?????? 指对图g中的每个极点v树立一个单链表所以在邻接表中存在两种结点:极点表结点和边表结点

十字链表法:

十字链表是有向图的一种链式存储规划。在十字链表中对应于每个极点也有一个结点。

弧结点中有5个域:尾域(tailvex弧尾相同的弧也在同一个链表上。

极点结点中有3个域: data域存放极点有关的数据信息firstin和firstout两个域别离指向以该极点为弧头或弧尾的第一个弧结点。

邻接多重表

?????? 邻接多重表存储无向图的方法一起为了便于打点将各个首元节点存储到一个数组中。

4. 啥是极大连通子图

极大连通子图是指图的连通分量再参加任何一个不在该连通分量中的点都会致使它不再连通。

极小连通子图是指连通图的生成树删去任何一条边都会致使无法构成生成树。

5. 简述邻接表和邻接矩阵的差异

邻接表的存储空间比邻接图小。

邻接矩阵遍历图比邻接表快。

邻接表合适存储稀少图邻接矩阵合适存储稠密图。

6. 啥是最短途径

最短途径是指图中两个节点之间之间的最短途径。常用的算法有迪杰斯特拉算法和弗洛伊德算法。

dijkstra算法

根柢思维dijkstra算法设置一个集结s记载已求得的最短途径的极点轮流将每个极点作为源点的时刻凌乱度o(v^3)。

dijkstra进程如下

初始化:集结s初始为{0}, dist[ ]的初始值dist[i]从极点集结v-s中选出 v将其参加到v中批改从v0 到集结v-s就任一极点v可达的最短途径长度:若dist[j] arcs[j][k]。重复2直到一切的极点都包括在s中。

floyd算法

7. 啥是最小生成树

生成树连通图的生成树是包括图中悉数极点的一个极小连通子图则会变成非连通图

最小生成树:生成树的界说权值之和最小的生成树称为最小生成树。

prim算法

初始时从图中任取一极点得到的t就是最小生成树。

kruskal算法

一切的边依照权值先从小到大摆放直到一切的点都归于同一个集结中止。

8. 简述下aov网、aoe网、拓扑排序以及要害途径

aov网

aoe网

在带权有向图中而aov网中的边无权值,仅标明极点之间的前后联络。

性质

只需在某极点所代表的作业发生后只需在进入某极点的各有向边所代表的活动都已结束时该极点所代表的作业才干发生。

拓扑排序拓扑排序是一种关于aov网的排序。关于每个有向无环图构成的aov网,当极点序列满足这些条件时:1.每个极点呈现且只呈现一次;2.若极点a在序列中排在极点b的前面,则在图中不存在从极点b到极点a的途径。则是关于该aov网的一个拓扑排序。拓扑排序的实施进程是:1.从aov网中选择一个没有前驱的极点并输出;2.从网中删去该极点和一亲咴它为起点的有向边;3.重复1和2直到其时aov网为空,假定中途不存在无前驱的极点,则阐明网络存在环。

寻找要害途径的根柢思维整个工程才干提前结束。

最早可以初步时刻 ve[i]最迟答应初步时刻 vl[i]作业 vi 最迟答应的初步时刻。vl[i])}要害活动0 的节点

第五章 排序

1. 啥是算法的平稳性

排序算法的平稳性是指排序算法对要害词巨细相同的元素假定发生改变则阐明是不平稳的排序算法。

2. 简述内部排序和外部排序的差异。

内部排序是指排序文件不大将待排序的数据一次性悉数装入内存进行排序。

外部排序是当待排序文件较大,内存一次放不下时,就需要排序时把数据一有些一有些地调入内存进行排序,在排序进程中需要多次进行表里存数据交流。

一般运用归并排序法。将文件分红若千长度为|的子文件,顺次读入内存运用内部排序办法进行排序,构成归并段,再对各个归并段进行逐趟归并。

3. 数据规划有哪些排序算法并比照时刻凌乱度。

刺进排序、选择排序、冒泡排序、快速排序、堆排序、归并排序、基数排序的时刻凌乱度

前3个为0(n^2),快排、堆排、归并排序为0(nlogn)r))。

第六章 查找

1. 次序查找、减半查找、分块查找的优缺陷。

次序查找

一般线性表的次序查找

根柢思维是从线性表的一端初步则回来查找失利的信息。

有序表的次序查找

若在查找之前就现已晓得表是要害词有序的然后降低次序查找失利的均匀查找长度。

利益普适性强合适多种存储规划

缺陷功能较低

减半查找

减半查找的根柢思维:首要将给定值key与表中中心方位的元素比照,若相等回来查找失利的信息。

时刻凌乱度

利益功能较次序查找更高

缺陷只合适有序表且存储规划有必要撑持随机造访

分块查找

分块查找的根柢思维:将查找表分为若干子块。块内的元素可以无序索引表按要害词有序摆放。

利益速度快而不必移动节点中的数据

缺陷添加了索引表降低了存储空间的使用率

2. 啥是b树

?????? b树又称多路平衡查找树

树中每个结点至多有m棵子树即至多富含m-1个要害词。若根结点不是终端结点则至稀有两棵子树。除根结点外的一切非叶结点至稀有「m/2棵子树即至少富含「m/2- 1个要害词。一切的叶结点都呈如今同一层次上指向这些结点的指针为空)。

b树的特征

一切键值分布在整颗树中任何一个要害词呈现且只呈如今一个结点中查找有可以在非叶子结点结束在要害词全集内做一次查找,功能迫临二分查找

b

b也是一种多路查找树, 它与 b- 树的不一样之处在于:

在b1棵子树。在b不富含该要害词对应记载的存储地址。在b包括的要害词和其他结点包括的要害词是不重复的。

3. 静态查找和动态查找

静态查找就是咱们平常概念中的查找是“真实的查找”。之所以说静态查找是真实的查找这就是所谓的静态查找。

动态查找它更像是一个对表进行“创建、扩展、批改、删去”的进程。动态查找的进程中对表的操作会多两个动作一般并不是那么简略。

4. 啥是哈希表

哈希表又称为散列表是根据要害词码的值直接进行造访的数据规划直接定址法除留余数法数字分析法平方取中法折叠法随机数法。哈希冲突的处置办法包括翻开定址法和拉链法

直接定址法 直接取要害词的某个线性函数值为散列地址。

?????? 除留余数法这是一种最简略、最常用的办法使用以下公式把要害词变换成散列地址。

?????? 翻开定址法所谓翻开定址法又向它的非近义词表项翻开。

?????? 1)线性勘探法

?????? 2)平方勘探法

?????? 3)再散列法

?????? 4)伪随机序列

?????? 拉链法

5. 啥是散列表的装填因子

装填因子是散列表的一个重要参数而过小则会浪费存储空间。