AlpacaZhou
打这么一段话真是个浩大的工程－ －要应付期末考试最快捷的方法是找到本校历年试卷然后让班上学得比较好的同学给讲题，大概能搞懂三套题的话基本题型你也了解了，自己的话，花三天时间，即使看不懂也把整本书的知识点整成一个纲要在这个过程中你会摸清DS的主要脉络。各个章节简述：第一是绪论，这个没有什么好讲的，把一些关于算法的概念、逻辑结构与物理结构的区别弄清后最重要的就是要会算时间复杂度了。第二章是线性表，这是一种一对一的数据结构，就是一一对应（掌握顺序表、链表的存取存储特点及顺序表，链表的插入删除操作，一定要理解相关代码段，因为这些代码段重要到选择都有可能考啊）第三章是栈和队列 它们是操作受限的线性表，栈是后进先出，队列是先进先出，重点是充分理解后栈的进先出与队列的先进先出，然后就是它们各自的存储（逻辑概念）存取（物理概念）结构，判满判空。然后就是栈和队列的应用，知道什么什么时候用栈什么时候用队列。串和广义表我当初是不考的，这部分要考也考得少，了解一些基本概念就OK；第四章，树与二叉树，这是一种一对多的数据结构，要会计算叶子节点什么的，了解这种结构的特点，重点有树的遍历，树与森林的转换，哈夫曼树，二叉排序树第五章 图，这是一种多对多的数据结构 重点有图的存储表示，图的遍历和最短路径啊关键和拓扑排序，按这些内容出的题都涉及算法，最好是自己能读懂算法然后按照算法操作，如果不行就学会做题，明白一种题怎么做，多做几遍你会发现很简单－ －）第六章 查找，重点是二分查找，哈希表，特别是哈希，学会构造哈希表，要会算查找成功或失败的平易查找长度。仔细看的话你会发现这章挺有意思的第七章 排序，重点掌握各种排序方法的实现，各种排序方法时间复杂度要明确，稳不稳定要清楚，什么时候用哪种排序最好（比如基本有序时用直接插入最好，而这种时候整体较好的快排却是最坏情况）比较好的方法是从网上找到一些算法执行的动态演示图，效果相当好。说实话，当年学DS也是大白，最后渐渐明白就是通过狂做练习。一梳理你会发现其实数据结构就讲了从一对一，到多对多的几种数据结构，向你展示各种数据结构在面对查找啦，插入删除啦这样的操作时是怎样的。对于算法题，这不是速成的，无法提供好的解决方案，见谅。如果有具体的问题还可以问的说，考试加油嗷~
蚊蚊mandy
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）红黑树在插入删除上要优于平衡二叉树，红黑树使用非严格的高度平衡换取增删节点时旋转次数的减少，任何不平衡都会在三次旋转之内解决，但是平衡二叉树旋转次数有时会比红黑树要多。所以红黑树的插入删除效率更高。
考核要求：达到“领会” 层次知识点：有关体系结构的各种概念 1.4.1 三级模式结构数据库的体系结构 分为三级：内部级、概念级和外部级 （数据抽象的三个级
cHeN&Li$Li 2人参与回答 2024-09-20 02142自考数据结构导论今天我们的教务老师给同学来讲讲以下这些问题，如果你觉得还不错，可以收藏我们网站哦，我们专注于自学考试教材购买服务网哦，接下来一起来阅读
爱美食的飘飘 2人参与回答 2024-09-20 队列(Queue)是一种运算受限的线性表 插入在表的一端进行 而删除在表的另一端进行 允许删除的一端称为队头(front) 允许插入的一端称为队尾(rear)
默然回首千百度 2人参与回答 2024-09-20 线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。是随机存取的顺序存储结构。顺序存储指内存地址是一块的，随机存取指访问时可以按下标随机访问，存储和存取是
天才少女JESSICA 2人参与回答 2024-09-19 第六章 树 树是n个结点的有限集合，非空时必须满足：只有一个称为根的结点；其余结点形成m个不相交的子集，并称根的子树。 根是开始结点；结点的子树数称度；度
天天开心好好好 2人参与回答 2024-09-20 