自考数据结构知识点总结高中

1、继承不同

HashMap继承了AbstractMap，AbstractMap实现了Map接口

HashTable继承了Dictionary类

2、线程安全不同

HashMap不是线程安全的，HashTable是线程安全的

3、允许null值

HashMap允许key和value为空，而HashTable不允许

4、遍历方式实现不同

HashMap的迭代器是fail-fast迭代器，HashTable的enumerator迭代器不是fail-fast的

5、哈希值的使用不同

HashMap重新计算哈希值，HashTable直接使用对象的哈希值

6、初始容量和扩容方式不同

HashMap初始大小为16，扩容大小一定是2的指数

HashTable初始大小为11，扩容大小为old*2+1

7、hashmap新增红黑树结构

当碰撞链表过长时，就把链表转为红黑树

1、直接定址法

取关键字或关键字的某个线性函数值为散列地址

特点：关键字连续时较方便，但关键字不连续时将造成内存单元的大量浪费

2、数字分析法

取关键字中取值比较均匀的若干数位作为哈希值。

特点：适用于关键字全部已知，并要对关键字中每一位进行分析

3、平方取中法

取关键字平方后中间几位作为哈希地址

特点：因为平均值的中间部分跟关键字的每一位都有关，出现随机值的概率较大

4、分段叠加法

按哈希表地址位数将哈希表分为位数相等的几段（最后一段可以较短），然后将这几部分相加，舍弃最高位的进位得到哈希值。

具体分为：移位法与折叠法

移位法：将每部分低位对其相加

折叠法：从一段向另一端沿分割线来回折叠（奇数段为正序，偶数段为倒序）

例如关键字123603247112020,哈希表长度为1000，则应把关键字分成3位一段

移位法得到105，折叠法得到907

5、伪随机数法

采用伪随机函数作为哈希函数

6、除留余数法

用关键字除以某个不大于哈希表长度的数，取余数作为哈希值。

1、开放定址法

当关键字key的哈希值p=H（key）出现冲突时，以p为基础产生新的哈希值p1，如果p1仍冲突，则产生p2，以此类推。

函数形式如下：

Hi = (H(key) + di) % m

根据di的不同分为

（1）线性探测

di = 1， 2， 3， …… ，（m-1）

（2）平方探测

d i =1 2 ，-1 2 ，2 2 ，-2 2 ，…，k 2 ，-k 2 ( k<=m/2 )

（3）伪随机探测

di = 伪随机数序列

2、再哈希法

构造多个不同的哈希函数，当出现冲突时，使用新的哈希函数

3、链地址法

将散列到同一位置的冲突元素存入一个链表中

4、建立一个公共溢出区

将哈希表分为基本表和溢出表

左旋：

右旋

红黑树是一颗特殊的二叉查找树，除了二叉查找树的所有性质

1、若任意节点的左子树不为空，则左子树上所有节点的值均小于它的根节点的值

2、若任意节点的右子树不为空，则右子树上所有节点的值均大于它的根节点的值

3、任意节点的左右子树也为二叉查找树

4、没有键值相等的节点

还满足

1、每个节点要么是红的要么是黑的

2、根节点是黑的

3、每个叶节点（null节点）是黑的

4、如果一个节点是红的，那么它的两个儿子都是黑的

5、任意节点到叶节点（null节点）的每条路径都包含相同数目的黑节点

红黑树保证没有一条路径比另一条路径长出两倍，保证了自身是接近平衡的二叉树，能保证在最坏的情况下查找的时间复杂度为O（logN），而二叉查找树最坏为O（N）

红黑树牺牲了严格的高度平衡为代价，只要求部分达到部分平衡条件，降低了对旋转的要求，从而提高了性能。红黑树能够以O（logN）的时间复杂度进行添加，删除，查找。由于它的设计，任何不平衡都可以在三次旋转之内解决。

1、相比BST（二叉搜索树）

红黑树的最长路径不大于最短路径两倍，保证了最差搜索效率为O（logN）,而二叉搜索树最差效率会达到O（N）

2、相比AVL（平衡二叉树）

（1）红黑树的查询性能略逊于平衡二叉树，因为它比平衡二叉树会最多多一层。

（2）红黑树在插入删除上要优于平衡二叉树，红黑树使用非严格的高度平衡换取增删节点时旋转次数的减少，任何不平衡都会在三次旋转之内解决，但是平衡二叉树旋转次数有时会比红黑树要多。所以红黑树的插入删除效率更高。

在计算机考研专业基础课统考科目中，一共考查数据结构、操作系统、计算机组成原理、计算机网络四门课程，满分为150分，其中数据结构占45分。一、考查目标 (1)理解数据结构的基本概念，掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。 (2)掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。 (3)能够选择合适的数据结构和方法进行问题求解。二、知识点解析1.线性表 线性表是一种最简单的数据结构，在线性表方面，主要考查线性表的定义和基本操作、线性表的实现。在线性表实现方面，要掌握的是线性表的存储结构，包括顺序存储结构和链式存储结构，特别是链式存储结构，是考查的重点。另外，还要掌握线性表的基本应用。2.栈、队列和数组 栈和队列是两种特殊的线性表，在这方面，要求我们掌握栈和队列的基本概念，以及他们之间的区别。对于栈和队列的存储结构(包括顺序存储结构、链式存储结构)要有较深的理解，对于栈和队列的应用，例如，排队问题、子程序调用问题、表达式问题等，要搞清楚。 一维数组属于线性表范畴，但多维数组不属于线性表。在这方面，主要掌握数组的存储结构，例如按行优先、按列优先等，某个元素存在的地址是什么。对于特殊矩阵(二维数组)的压缩存储原理也要搞清楚。3、树与二叉树 二叉树和树是两种不同的概念，这一点是必须要搞清楚的。在这个部分，我们要掌握树的定义、二叉树的定义及主要特征(特殊的二叉树、二叉树的性质)。在二叉树的顺序存储结构和链式存储结构方面，特别是链式存储结构，因为很多应用都是建立在链式存储基础上，例如，二叉树的遍历(前序遍历、中序遍历、后序遍历)就是一种典型的应用。 在特殊的二叉树中，完全二叉树的概念是必须要搞清楚的，其次，线索二叉树的基本概念和构造、二叉排序树、平衡二叉树的基本概念和应用，特别是二叉排序树的基本性质和特点要能很好地理解。 多棵独立的树就组成了森林，树的存储结构和遍历、森林的遍历、树和二叉树的转换、森林和二叉树的转换等知识，也要有了了解。 最后就是树的应用，通常会作为综合应用类试题出现，包括等价类问题、哈夫曼(Huffman)树和哈夫曼编码等。 记得采纳啊