Ephemeral

第一节：计算机系统层次结构 冯诺依曼体系： 冯诺依曼体系是现代计算机的基本结构，包括存储程序的基本思想依旧应用在现代体系 唯一的区别在于以原先的“运算器”为核心转为了以“主存储器”为核心 虚线表示控制反馈线路，其他都是数据通路，应当与机器字长保持一致性 计算机功能部件可以分为：I/O设备、存储器、运算器和控制器（集成在中央处理器） I/O设备： I/O设备在计组、OS内均有详细的解释和概述，这一节更多是介绍，不做展开 届时可能会做一定的索引 存储器： 存储器是计组的核心内容，尤其是主存，外存则分散在计组、OS内均有部分的内容 内存管理（即主存在OS中有单独的一章作为内容），外存管理和磁盘在OS中也有部分 因而届时应该会根据情况完善该节内容，添加一定量的索引（待完善后） MAR、MDR是后续考察的重点内容，其一般被集成在CPU内，基本和主存是分离的 运算器： 运算器当前主要把握其结构即可，寄存器在P184有更为详细的介绍（指令体系内） 控制器： 控制器只要清楚内部结构含：CU、IR、PC即可，具体的运行流程在指令集内容中阐述 关于总线，外部总线含数据总线 ...

一个排序的算法应该从这些方面去理解、复习、巩固： 时间、空间复杂度（最好情况和最坏情况分别是什么、排序趟数受什么影响 算法运行思想（模拟过程、模拟算法运行、阐述其思路和思想、算法运行特点 稳定性、比较/移动/交换次数与初始序列的相关性、属于什么类型排序 一趟排序能不能必然定下一个最终元素 适用性（适用于什么数据结构、适用的原因）、适用应用场景（什么情况适合用） 最后也是要求最高的一点：能够按照其思想不靠默写能写出代码 这一块的整理因为篇幅较大放在整理文档内部，后续若要补充可以去文档内进行补充 直接插入排序、折半插入排序、希尔排序： 习题分析整理： 6：考虑从性质出发而不是直接模拟运行，最贴近有序的情况下比较/插入/移动次最少 7：插入排序都不能保证排序能够定下某个元素的最终位置 9、11：关于希尔的增量，这个增量的定义可能会遗忘，就是I+D（序号加一个增量） 12：基本还是要考虑模拟的，因为每个子序列内部采用的是直接插入（折半实现较复杂 14：一个比较容易混淆的误区点 直接插入查找本身就是ON^2，移动又是ON^2，总体是ON^2 折半插入查找本身优化到ONlogN，但移动依旧是ON ...

四种存储方式：顺序、链式、索引、散列 本章的线性表可以采用链式、顺序存储，其中二叉查找必须使用顺序的有序表 分块查找是索引存储与线性表（顺序、链式）的结合体 二叉排序树、二叉平衡树、红黑树基于链表实现，B树、B+树基于链表实现 散列表基于散列存储实现，也就是这一整章把所有的存储方式都给覆盖了，是查找结构 随机存取的存储结构：顺序表；散列存储的存储结构：散列表 顺序存取的存储结构：链表；索引存储的存储结构：索引表 顺序查找（链式或者顺序表均可）： 如果真的要分类其实可以分为带哨兵、不带哨兵、从前向后、从后向前、链表分类等 但个人觉得没必要了，直接从最本质的计算出发 失败的ASL在无序情况下是必然需要遍历全部元素的，而有序情况则可以好一些 成功时的ASL，不论有序还是无序都是一样的，每个位置对应需要查找的次数累加即可 具体按照题目给定的分类临场计算即可，这类一般不难 相对而言比较重要的也就是有序表的顺序查找的失败ASL计算了 折半查找（只能顺序表且元素必须有序） 统考命题重点：给定折半查找的数量和取整方式则可以唯一确定一棵折半的判定树 具体画法可以参考纸上面列的，向上取整和向下取整是 ...

图的基本概念： 对书上内容的一些补充： 子图简单来说就是一个充分非必要条件，子图顶点和边必然是图的子集合，反之不然 数据结构里面只讨论简单图，所以不会出特别古怪的题目 同样，最少的有环图也同样不会考虑，只会考一定有环的边数 极大连通子图就是其连通分量，极大强连通子图就是其强连通分量 如果其自身就是连通或者强连通图，那么其自身就是极大连通子图、极大强连通子图 后面也有对有向图进行连通性的讨论（有向图的连通意味着是可达但非双向可达 生成树一般都是对无向图讨论的，生成森林也是一样 极小连通子图并没有对顶点个数的要求，而极大连通子图包含了对顶点个数的要求 要点摘录，根据这些点去复习： 1.无向图： 连通最大边数、最小边数；不连通最大边数、最小边数；一定连通的边数 一定不连通的边数、一定有环的边数 2.有向图： 强连通最大边数、最小边数；不强连通最大边数、最小边数一定强连通的边数 一定不强连通的边数、一定有环的边数 习题补充： 3：每次深搜、广搜都是对图从该顶点向外拓展的可达的分量进行遍历的过程 4：图和树的区别在于定义，一个是一对多，一个是多对多 15：思想就是每次向里面加一条边就可以连接两个 ...

树的定义和性质： 具体的细节书上都已经有所划录，列下重点 树的性质里面概括比较少和不够全面，这些是个人认为需要掌握清楚，复习的要点 1.度M，第i层至少、至多多少个结点；M叉树，第i层至少、至多多少个结点 2.度M，高h，至少、至多多少个结点；M叉树，高h，至少、至多多少个结点 3.度M，N个结点，最低、最高的h分别是多少；M叉树，N个结点，最低、最高的h分别是多少 4.具体再加上一个性质：度和=结点数+1，这样就构成了这一节的主要内容 习题和其他补充： 对于16年统考出的森林和树的关系题，现在其实个人就有比较明确的思路 这类题如果在考场上面一时半会不太反应得过来，记住仍然有最后一个方法去破题 就是直接依靠举例归纳得出结果，不一定要按照题目的来，一个个举例归纳规律 这种方法应该要视作是考场上面最常见的手段，因为不可能都考察熟悉的东西 类似于10年的考题，当时可能都没有这种知识点的概括，怎么办？只能靠临场归纳的 6：注意下公式计算上面尽可能不要有二进制的思维惯性 3：当作一个补充即可，本节内容不多 二叉树的概念： 这一节内容基本都在书上且比较完整，就没有单独列出来提纲（没有书上的完整 ...

栈： 考察点并不多，主要是这样一些： 1.顺序栈指针起始位置和操作的关系、共享栈指针起始和操作的关系，以及判满 2.链栈的具体操作实现问题以及相应带头结点、不带头结点等 其他就是一些比较零散的知识点，书上基本划了重点，这里也就不加以赘述 习题补充： 4、5、6：主要补充下顺序栈、共享栈可能需要注意数组开始或者结束位置的问题 具体其实就是数组的写法和理解上面可能需要注意一下 平时可能多以注意指针的位置为主，对数组的起始和结束位置注意并不够 10：链栈的操作不够熟悉，做的时候依旧会有些生，主要是没清楚数据结构 是一个头插、头删的单链表，这个定义在其实就能清楚很多，保留 至于有没有头结点需要看题目的给定，还是比较容易产生惯性思维导致出错的 出入栈序列问题： 只需要把握某个出栈，另外几个还在栈里面的思路就可以解决 核心思想其实是模拟栈的运行，统考的考察点也均是反套路的基于栈运行的原理去考察 平时做题的时候应该以模拟栈运行的思路去做，而不是套公式，要能模拟栈的运行 23：C语言标识符，即使是当时特意注意，也同样是会忘记的，这类只能靠不断去回忆 31：目前统考里面暂时还没有出现以出序情况凑入序的题 ...

绪论中的逻辑结构、存储结构介绍永远感觉吃不透 时间复杂度习题： 3：空间复杂度截至目前还没有考过，但其的定义这一段理解依旧偏差较为严重 建议多加把握这道题和相关考点，要考察应该会结合计组的递归栈和硬件一起考察吧 9：思维惯性，仿佛认为一定是求解时间复杂度，而实际上也可以是求解执行次数 算是提一个醒吧，审题上面尽可能少一些思维惯性 关于统考题： 最近几年变化的趋势就是越发变得注重计算和推理，相对往年难度略微提升 需要具体列出累加式然后再根据具体情况求解，这是要清楚的事 个人保留了一些统考题，以备下一次复习的时候进一步去思索和研究（应该会有新体会 绪论斐波那契数列的时间复杂度求解可以自底而上递归求解树，而不必自顶向下 这样不管是建树还是归纳法计算时间复杂度都会轻松和容易很多 也算是对递归类型计算时间复杂度的一个概括总结 或者说这类方法也可以拓展到一般求解，可以采用归纳法，如果特别难的情况之下 顺序表： 一般采用数组来实现（数组就是物理上面连续分配的一块空间，C语言中 唯一需要稍微回忆下的就是插入、删除的具体代码实现，别的书上划了相应重点 习题简要补充： 2：依旧是存储结构、逻辑结构、 ...

书上的细节补充： 数组的元素在内存中占用连续的存储空间 一般的矩阵在压缩以后依旧保留了其随机存取的特性，可以逆向解析地址得到位序 这个考察的并不多，但不代表不会考察，对于任意给定的压缩状态都应该会逆向解析 包括对称的行优先、列优先，上、下三角矩阵的行优先、列优先，三对角矩阵对应 其中应该注意一点就是对称矩阵公式推导是和上下三角一样的 但其毕竟还是有两个元素的，对称的两个元素存取所对应的公式是恰相反的 经典的对应统考题，十四题 稀疏矩阵存储的方式可以有多种，但具体看书上为好 数组存储与压缩： 两种映射方式，行优先、列优先，相应公式的推导和应用 其实最本质的基本不变，就是LOC+K-1，LOC是起始地址，K是元素是第K个，中间隔几个 最需要注意的应该是数组本身是零还是一开始，以及内存中存储是零还是一开始 具体公式的推导不难，但结合后面的几种矩阵存储推导过程就会比较多，略微麻烦 总体就是一个计算量和推导过程繁琐容易错，要特别注意细节问题 目前统考那么多年基本限定在了二维数组，基本没有往高维拓展的研究 如果真的要考试的话，其实考前还是可以了解一下的 矩阵下标一般都是从一开始的，一维存储数 ...

对于书上基础算法较为形象的描述： 其实更应该说是一些较为经典的错误案例 单标志法： 如果现在没有轮到我用，我等 如果现在轮到我用 我用 下次给他用 评价： 这个算法的缺点其实比较明显的，如果下次他不用而我要用，那我就得一直等 更何况就算他用了也不一定考虑我用不用的问题，可能转手就把这个机会让给别人用了 极有可能会导致资源的浪费，甚至说长时间得不到使用导致的饥饿问题 违反了“空闲让进”，并且没有实现“让权等待” 其实核心就是，没有考虑到下次给他用的时候，他到底会不会用，以及会不会让给我用 双标志先检查法： 如果现在他想要用，那么给他用，我等 如果他现在不想用 那么我想用 我用 我用完了不想用了 评价： 这个算法同样存在漏洞 检查的时候他可能不想用，但是就在我设置想用的前那么几刻，他也想用了 而这时候我还没想用，他可能就会以为我不想用，于是我们两个一起想用，冲突了 简单来说就是两者检查均通过 违反了“忙则等待”，没有实现“让权等待” 核心是检查和设置中有一个间隔，这个间隔时间就会导致另一者的检查也通过 双标志后检查法： 我想用 如果他现在想用，那么给他用，我等 如果他现在不想用 我 ...

对于补码，真值、原码、移码、反码的全面总结，一共二十种（可以优化表述 具体补位的长度看题目给定，如果给定字长为X位就进一步补位数即可 真值-补码： 正数：即为正数转原码，原码补码相同，数值位高位补0 负数：即为负数转原码，原码转反码，反码转补码 最高位符号位定1，数值位高位补0转为原码 除符号位最高位全部取反转为反码 低位加一转为补码 真值-原码： 正数：数值位高位补0 负数：最高位符号位定1，数值位高位补0 真值-反码： 正数：即为正数转原码，原码反码相同，数值位高位补0 负数：即为负数转原码，原码转反码 最高位符号位定1，数值位高位补0转为原码 除符号位最高位全部取反转为反码 真值-移码(仅适用于偏移量为恰到好处的: 正数：即为正数转原码，原码转补码，补码转移码，而原码补码相同 即为正数转原码，原码补码相同，数值位高位补0，然后符号位取反 负数：即为负数转原码，原码转反码，反码转补码，补码转移码 最高位符号位定1，数值位高位补0转为原码 除符号位最高位全部取反转为反码 低位加一转为补码 符号位取反转为移码 原码-真值： 正数：即数值位，二进制真值 负数：即负号加数值位，负的二进制真 ...

06-T1： In spite of “endless talk of difference,” American society is an amazing machine for homogenizing people. There is “the democratizing uniformity of dress and discourse, and the casualness and absence of deference” characteristic of popular culture. People are absorbed into “a culture of consumption” launched by the 19th-century department stores that offered “vast arrays of goods in an elegant atmosphere. Instead of intimate shops catering to a knowledgeable elite,” these were stores “ ...