计算机网络+数据结构
1、按照网络的作用范围分类
广域网(WAN,Wide Area Network)
城域网(MAN,Mertopolitan Area Network)
局域网(LAN,Local Area Network)
(无线)个人区域网(PAN,Personal Area Network)
2、计算机网络的主要性能指标
带宽、时延、利用率
3、OSI七层模型和TCP/IP四层模型
OSI七层网路模型 | TCP/IP四层概念模型 | 对应网络协议 |
应用层(Application) | 应用层 | HTTP、TFTP, FTP, NFS, WAIS、SMTP |
表示层(Presentation) | Telnet, Rlogin, SNMP, Gopher | |
会话层(Session) | SMTP, DNS | |
传输层(Transport) | 传输层 | TCP, UDP |
网络层(Network) | 网络层 | IP, ICMP, ARP, RARP, AKP, UUCP |
数据链路层(Data Link) | 数据链路层 | FDDI, Ethernet, Arpanet, PDN, SLIP, PPP |
物理层(Physical) | IEEE 802.1A, IEEE 802.2到IEEE 802.11 |
4、计算机网络中常用的传输介质
5、IPv4、IPv6
IPv4的IP地址长度是32位
IPv6的IP地址长度是128位
【数据结构篇】
二维数组,多维数组,广义表、树、图都属于非线性结构
1、数据:所有能被输入到计算机中,且能被计算机处理的符号的集合。是计算机操作的对象的总称。
2、线性表:
3、栈、堆、队列
队列是特殊的线性表
4、串
5、数组和广义表
6、树和二叉树
遍历二叉树
- 先序遍历DLR:根节点->左子树->右子树。
- 中序遍历LDR:左子树->根节点->右子树。
- 后续遍历LRD:左子树->右子树->根节点。
7、图
8、内部排序和外部排序
- 内部排序:全部数据可同时放入内存进行的排序。
- 外部排序:文件中数据太多,无法全部调入内存进行的排序。
插入类:
1、直接插入排序。最坏情况是数据递减序,数据比较和移动量最大,达到O(n2),最好是数据是递增序,比较和移动最少为O(n)。趟数是固定的n-1,即使有序,也要依次从第二个元素开始。排序趟数不等于时间复杂度。
2、折半插入排序 。由于插入第i个元素到r[1]到r[i-1]之间时,前i个数据是有序的,所以可以用折半查找确定插入位置,然后插入。
3、希尔排序。缩小增量排序。5-3-1。在实际应用中,步长的选取可简化为开始为表长n的一半(n/2),以后每次减半,最后为1。插入的改进,最后一趟已基本有序,比较次数和移动次数相比直接插入最后一趟更少
交换类:
1、冒泡排序。O(n2)通常认为冒泡是比较差的,可以加些改进,比如在一趟中无数据的交换,则结束等措施。
- 在数据已基本有序时,冒泡是一个较好的方法
- 在数据量较少时(15个左右)可以用冒泡
2、快速排序。
时间复杂度。最好情况:每次支点总在中间,O(nlog2n),平均O(nlog2n)。最坏,数据已是递增或递减,O(n2)。pivotkey的选择越靠近*,即左右两个子序列长度越接近,排序速度越快。越无序越快。
空间复杂度。需栈空间以实现递归,最坏情况:S(n)=O(n);一般情况:S(n)=O(log2n)
在序列已是有序的情况下,时间复杂度最高。原因:支点选择不当。改进:随机选取支点或最左、最右、中间三个元素中的值处于中间的作为支点,通常可以避免最坏情况。所以,快速排序在表已基本有序的情况下不合适。
在序列长度已较短时,采用直接插入排序、起泡排序等排序方法。序列的个数通常取10左右。
选择类排序:
简单选择排序。O(n2)。总比较次数n(n-1)/2。
堆排序。建堆 O(n),筛选排序O(nlogn)。找出若干个数中最大/最小的前K个数,用堆排序是最好。小根堆中最大的数一定是放在叶子节点上,堆本身是个完全二叉树,完全二叉树的叶子节点的位置大于[n/2]。时间复杂度不会因为待排序序列的有序程度而改变,但是待排序序列的有序程度会影响比较次数。
归并排序。时间:与表长成正比,若一个表表长是m,另一个是n,则时间是O(m+n)。单独一个数组归并,时间:O(nlogn),空间:O(n),比较次数介于(nlogn)/2和(nlogn)-n+1,赋值操作的次数是(2nlogn)。归并排序算法比较占用内存,但却是效率高且稳定的排序算法。在外排序中使用。归并的趟数是logn。
基数排序。在一般情况下,每个结点有 d 位关键字,必须执行 t = d次分配和收集操作。分配的代价:O(n);收集的代价:O(rd) (rd是基数);总的代价为:O( d ×(n + rd))。适用于以数字和字符串为关键字的情况。
枚举排序,通常也被叫做秩排序,比较计数排序。对每一个要排序的元素,统计小于它的所有元素的个数,从而得到该元素在整个序列中的位置,时间复杂度为O(n2)