直接插入排序在有序数组上的比较次数为 n-1，简单选择排序的比较次数为 1+ 2+...+n-1=n(n-1)/2。II，辅助空间都是 O(1)，没差别，III，因为本身已经有序，移动次数均为 0

   边建边调，堆的要求，根结点大于或小于左右结点即可，不要求左右结点也有序

方法一：填表 先正向（从源点往汇点）推导事件（顶点）的最早发生时间 ve(i) 。 再逆向（从汇点往源点）推导事件（顶点）的最晚发生时间 vl(i) 。 再正向（从源点往汇点）推导活动（有向边）的最早发生时间 e(i) ，即...

解答： m 阶B树每个结点（除根结点外）关键字数量 n 为 ⌈m/2⌉−1≤n≤m−1 。本题5阶B树， 2≤n≤4 。 注意，这道题考察不可能。我...

解答： 设原来插入新结点前指向 p 的直接后继结点的指针为 q ，题目要求在 p 和 q 之间插入新的结点 s 。 双向链表插入结点的时候要修改四个指针，这四个指针的修改顺序没有强制要求，也就是有 4!=24 种连接顺序，但是这里注意要按照题目要求的顺序连线。 初...

三元组存储矩阵的表示方法出现在2017年第3题，三元组表的表项存储了行row、列col、值value三种信息，我们还需要知道矩阵 M 的规模 rows × cols，即 M 的行数 rows 和 M 的列数 cols，这个信息应该直接给出，即 I 和 III 。

解答： 构建哈夫曼树： 每个关键字的查找长度为： 频次查找长度频次3456810查找长度333322 注意，题目要求求加权平均长度，这里的权重就是频次。 加权平均长度为 (3×3+3×4+3×5+3×6+2×8...

无向连通图 G 中各边的权值均为 1 ，G 可以视为无权图，可以用广度优先搜索求单源最短路径，在求无权图的单源最短路径问题中，广度优先搜索比Dijkstra算法更加高效。III正确。 I 和 II 是最小生成树算法，也可直接排除。  

若采用折半查找法查找一个顺序表中不存在的元素，最大比较次数为对应二叉搜索树的高度，设结点数为 n ，   二叉搜索树高度为 h=⌈log⁡(n+1)⌉=⌊log⁡n⌋+1 。 代入&nb...

散列函数为 H(k)=(k+4)mod5 ，处理冲突采用线性探测再散列法，依次填入关键字 ⟨20,22,12,25⟩ 。   插入 2022 ， H(20)=(2022+4)mod5=1&n...

代4进去

i=i*3;  时间t   3t=n  t=long3n

抽象数据类型：一般由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分①数据对象②数据对象上关系的集合③数据对象的基本操作的集合

1、正确性：满足具体问题的解，基本目标。 2、可读性：有利于人去理解算法。 3、健壮性：输入非法数据，能适当做出处理，不产生莫名其妙的输出。 4、高效性：包括时间的高效性和空间的高效性。  

2的n次方<n！<n*n最大 代4要注意这三个

（D，R）data数据元素 relation关系

数据结构按逻辑结构可分为两大类，它们分别是  线性结构  和  非线性结构   数据结构按存储结构可分为四大类，它们分别是顺序存储 链式存储 散列存储 索引存储

在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。

数据的存储结构可用四种基本的存储方法表示，它们分别是  顺序、链式、索引、散列  。

数据的运算最常用的有5种，它们分别是  插入、删除、修改、查找、排序  。