数据结构DS
近几年命题趋于稳定，由两题组成
第一题考察算法题，题型固定
第一问算法思路
第二问算法代码
第三问分析算法的时间复杂度和空间复杂度
第二题数据结构分析题，题型灵活多变，多为考察数据结构的应用
预测题目1：顺序表的算法题已经5年未曾考过，今年极有可能考
算法题：
1.设单链表的表头指针为h，节点结构由data和next两个域构成，其中data域为字符型。写出算法dc(h,n),判断该链表的前n个字符是否中心对称。
（1）给出算法的基本设计思想
（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
（3）说明你所设计的算法的时间复杂度。
2.假设给定一个长度为n的数组，并且数组中每个值的位置距离排序后该值的位置不超过k（小于或等于k），k<=n。比如数组[2 3 1 4 6 5 7 9 8],每个值的位置距离其排序后的位置不超过2。
（1）给出算法的基本设计思想
（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
（3）说明你所设计的算法的时间复杂度。
3.设计一个算法，用于在一个未排序的链表中查找第k小的元素。分析时间复杂度。
给定一个包含n个整数的数组，设计一个算法找到第k小的元素。
（1）给出算法的基本设计思想
（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
（3）说明你所设计的算法的时间复杂度。
4.单峰向量定义为A[0,n],其中前缀{a1, a2, a3,…, ak}严格递增，后缀{ak+1, ak+2,…,an-1}严格递减。设计算法找到最大值所在的位置k。
（1）给出算法的基本设计思想
（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
（3）说明你所设计的算法的时间复杂度。
5.求一个数组A中连续相同数字的和等于s的最长子数组长度，例如A={1,1,2,1,1,1,2,1}， s=3，则所求子数组长度为 3。
（1）给出算法的基本设计思想
（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
（3）说明你所设计的算法的时间复杂度。
皮皮灰解析：
1. 判断单链表前 n 个字符是否中心对称
（1）基本设计思想
可以利用栈来辅助解决此问题。首先遍历单链表的前
n/2个节点（如果n为奇数，中间节点不用处理），将这些节点的数据域依次入栈。然后接着从第(n/2 + 1)个节点（n为偶数情况）或者第((n + 1)/2)个节点（n为奇数情况）开始往后遍历，同时将栈顶元素依次弹出，比较当前遍历到的节点数据域和弹出的栈顶元素是否相等。如果在整个比较过程中都相等，则该链表的前n个字符是中心对称的，否则不是。这样利用栈先进后出的特性来模拟对称位置元素的对比。
（2）时间复杂度
整个过程主要进行了一次遍历链表前半部分入栈操作以及后半部分与栈元素对比的遍历操作，每次遍历都是对n个节点规模内进行操作，所以时间复杂度是O(n)，其中n为要判断的链表前n个节点的个数。
2. 对位置距离排序后不超过 k 的数组排序
利用堆（优先队列）数据结构：创建一个大小为
k + 1的最小堆（优先队列）。首先将数组的前k + 1个元素放入堆中，堆顶元素就是当前窗口内的最小值。滑动窗口与元素替换：接着从第
k + 1个位置开始遍历数组，每一次将新元素加入堆中，同时弹出堆顶元素（因为它已经不在当前考虑的窗口范围内了）。此时堆顶元素就是当前长度为k + 1的窗口内的最小值，将其放入一个新的辅助数组中对应的位置。不断重复这个过程，直到遍历完整个数组，这样就得到了一个新的数组，其元素顺序是原数组经过一种特殊处理后的顺序，整体是更接近有序的状态。局部插入排序优化：由于每个元素距离其最终排序后的位置不超过
k，对于新得到的这个辅助数组，可以以每个元素为中心，左右扩展长度最多为k的范围，在这个小范围内进行插入排序（类似局部微调让其更加有序）。经过这一轮操作后，数组基本就达到有序状态了，整体利用了堆的高效特性以及局部有序调整的思路来降低时间复杂度。算法的时间复杂度说明
构建堆阶段：最初往堆中插入
k + 1个元素，每次插入操作在堆中的时间复杂度是O(log(k + 1))，总共进行k + 1次插入，所以这部分时间复杂度约为O((k + 1)log(k + 1))。滑动窗口阶段：后续遍历数组剩下的
n - (k + 1)个元素，每次往堆中加入一个元素并弹出堆顶元素的操作时间复杂度都是O(log(k + 1))，所以这部分的时间复杂度为O((n - (k + 1))log(k + 1))，整体这个阶段合起来时间复杂度大致为O(nlog(k + 1))。局部插入排序阶段：对于每个元素进行局部插入排序，每个位置的局部插入排序时间复杂度最多是
O(k)（因为窗口大小最多为k），总共有n个元素，所以这部分时间复杂度是O(nk)。综合来看，由于
k <= n，当k相对较小时（比如常数级别或者log级别的大小相对于n），整个算法的时间复杂度主要由O(nlog(k + 1))这一项决定，相比于普通的O(nk)时间复杂度在一些情况下更优，整体时间复杂度可以近似看作O(nlog(k + 1))，实现了对数级别的时间复杂度优化。
3. 在未排序链表中查找第 k 小的元素
（1）基本设计思想
可以利用类似快速排序中划分的思想。先任选链表中的一个节点的值作为基准值，遍历链表将节点分为两部分，一部分节点的值小于基准值，另一部分节点的值大于基准值。然后统计小于基准值部分的节点个数
count，如果count等于k - 1，那么当前基准值所在的节点就是第k小的元素；如果count大于k - 1，则在小于基准值的那部分链表中继续按照上述方法查找第k小的元素；如果count小于k - 1，则在大于基准值的那部分链表中查找第k - count - 1小的元素，重复这个过程直到找到结果。
（2）时间复杂度
在平均情况下，每次划分可以大致将链表分为两部分，类似快速排序每次划分的时间复杂度是
O(n)（n为链表长度），期望需要划分的次数为O(n)次，所以平均时间复杂度是O(n)。但在最坏情况下（比如链表已经有序），每次划分可能极不均衡，时间复杂度会退化为O(n^2)。
4. 找单峰向量最大值所在位置
（1）基本设计思想
可以采用二分查找的思想来解决。初始化左右指针分别指向向量的两端，然后不断取中间位置
mid，比较A[mid]与A[mid + 1]和A[mid - 1]的大小关系。如果A[mid]大于A[mid + 1]且大于A[mid - 1]，那么mid位置就是最大值所在位置；如果A[mid]小于A[mid + 1]，说明最大值在mid的右侧，更新左指针为mid + 1；如果A[mid]小于A[mid - 1]，说明最大值在mid的左侧，更新右指针为mid - 1，重复上述过程直到找到最大值所在位置。
（2）时间复杂度
每次二分查找可以将查找范围缩小一半，最多需要进行
O(log n)次比较（n为向量长度），所以时间复杂度为O(log n)。
5. 求数组中连续相同数字和等于 s 的最长子数组长度
（1）基本设计思想
可以使用双指针（滑动窗口）的思想。初始化左右指针都指向数组开头，用一个变量
sum来记录当前窗口内数字的和。不断右移右指针，将对应元素加入sum，同时判断sum是否等于s，如果等于，则更新最长子数组长度记录。如果sum大于s，则不断右移左指针，同时从sum中减去左指针移出窗口的元素值，直到sum小于等于s，然后继续右移右指针重复上述过程，直到右指针遍历完整个数组。
（2）时间复杂度
左右指针最多遍历数组一遍，整个过程的操作基本都是线性的，所以时间复杂度为
O(n)，其中n为数组的长度。
预测题目2：如果还考图的算法题的话
近几年，就只剩MST和最短路径问题算法没有考过了
算法题：
1.给定一个无向带权图，使用Prim算法或Kruskal算法求解最小生成树，并分析其时间复杂度。
2.设计一个算法来解决最短路径问题，如Dijkstra算法或Floyd-Warshall算法。分析算法的正确性、时间复杂度和空间复杂度，并讨论算法在实际应用中的优化方法。
皮皮灰解析：
1. 无向带权图使用 Prim 算法或 Kruskal 算法求解最小生成树
（1）Prim 算法基本设计思想
初始化：任选一个顶点作为起始顶点，将其加入到已构建的最小生成树顶点集合中，标记该顶点已访问，同时记录下从该顶点到其他未访问顶点的边的权值（用一个数组或优先队列等数据结构来辅助存储和更新这些边信息）。
迭代扩展：从存储的边信息中选择一条权值最小的边（该边一端在已访问顶点集合中，另一端在未访问顶点集合中），把这条边以及对应的未访问顶点加入到最小生成树顶点集合中，并标记该新顶点已访问，然后更新与这个新加入顶点相连的未访问顶点的边的权值（因为可能出现更短的到达这些未访问顶点的路径了）。
重复操作：不断重复上述选择最小权值边并扩展顶点集合的操作，直到所有顶点都被加入到最小生成树顶点集合中，此时就得到了整个图的最小生成树。
（1）Kruskal 算法基本设计思想
边的排序：首先将图中所有的边按照权值从小到大进行排序，可以使用合适的排序算法来完成这一步骤。
初始化并选边：初始化一个空的最小生成树集合（用并查集数据结构来高效判断顶点是否属于同一个连通分量），然后依次遍历排序好的边，对于每条边，如果这条边的两个端点所在的顶点集合（通过并查集判断）不在同一个连通分量中，那么就把这条边加入到最小生成树集合中，并且合并这两个端点所在的连通分量（通过并查集的合并操作实现）。
重复操作：不断重复上述选边和合并连通分量的操作，直到所有顶点都在同一个连通分量中，也就是形成了一棵包含所有顶点的最小生成树。
（2）时间复杂度分析
Prim 算法：如果使用简单的数组来存储和更新边信息，时间复杂度是 （是顶点个数），每次找最小权值边都要遍历所有未访问顶点的边信息；若使用二叉堆（优先队列）来优化选取最小权值边的操作，时间复杂度可以优化到 （是边的个数），因为每次插入和删除操作在堆中的时间复杂度是 ，总共要处理 个顶点和 条边左右的操作量。
Kruskal 算法：排序边的操作时间复杂度一般是 ，如果使用并查集来高效判断和合并连通分量，每次操作接近常数时间，整体遍历所有边并进行并查集相关操作的时间复杂度是 （ 是一个增长极其缓慢的函数，在实际中可以近似看成常数），所以总的时间复杂度大致为 ，由于 最大是 ，所以也可以写成 。
2. 最短路径问题（以 Dijkstra 算法或 Floyd-Warshall 算法为例）
（1）Dijkstra 算法基本设计思想
初始化：选定一个源点，将源点到自身的距离设为 0，到其他所有顶点的距离初始化为无穷大，同时标记源点已访问，用一个数据结构（如数组或者优先队列等）来存储各个顶点当前的距离信息。
迭代更新：从未访问顶点中选择距离源点最短的那个顶点，标记它已访问，然后检查这个顶点的所有邻接顶点，通过这个顶点来更新其邻接顶点到源点的距离（如果经过当前选定顶点到邻接顶点的距离比原来记录的距离更小，则更新距离）。
重复操作：不断重复选择最短距离未访问顶点以及更新邻接顶点距离的操作，直到所有顶点都被访问，此时就得到了从源点到各个顶点的最短距离。
（1）Floyd-Warshall 算法基本设计思想
初始化距离矩阵：用一个二维矩阵来表示图中任意两个顶点之间的距离，如果两个顶点之间有边直接相连，则矩阵对应位置存储边的权值，若没有边直接相连，则初始化为无穷大，同时对角线上元素（表示顶点到自身的距离）设为 0。
动态规划迭代：通过三重循环进行迭代，最外层循环遍历中间顶点，内层两个循环遍历所有顶点对，对于每一对顶点
i和j，尝试通过中间顶点k来更新从i到j的最短距离，即dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])，通过不断利用已经计算出的部分最短路径信息来更新其他顶点对之间的最短路径，经过所有循环迭代后，最终距离矩阵就存储了图中任意两个顶点之间的最短距离。
（2）算法正确性分析
Dijkstra 算法：基于贪心策略，每次选择当前距离源点最短的未访问顶点，由于权值都是非负的，这样可以保证每次选择的顶点加入到已确定最短路径集合中后，不会影响后续其他顶点最短路径的计算，通过逐步扩展已确定最短路径的顶点集合，最终能正确计算出从源点到所有顶点的最短路径。
Floyd-Warshall 算法：利用了动态规划的思想，通过依次考虑每个顶点作为中间顶点是否能使其他顶点对之间的距离更短，基于最优子结构性质（即如果
i到j的最短路径经过k，那么i到k和k到j的路径也必然是各自的最短路径），通过不断迭代更新距离矩阵，最终能正确计算出图中任意两个顶点之间的最短路径。
（3）时间复杂度分析
Dijkstra 算法：如果使用简单的数组来存储和更新顶点距离信息，时间复杂度是 （ 是顶点个数），每次找最短距离未访问顶点要遍历所有未访问顶点；若使用二叉堆（优先队列）优化，时间复杂度可以优化到 （ 是边的个数），原因和 Prim 算法类似，每次插入和删除操作在堆中的时间复杂度是 ，总共要处理较多的顶点和边相关操作。
Floyd-Warshall 算法：使用了三重循环，外层循环遍历
n次（n为顶点个数），内层两个循环都是遍历n次，所以时间复杂度是 。
（4）空间复杂度分析
Dijkstra 算法：需要一个数组来存储每个顶点到源点的距离信息以及标记顶点是否访问，空间复杂度是 ，如果使用优先队列存储边信息等，还会额外占用一定空间，不过也是和顶点、边数量相关的线性级别空间。
Floyd-Warshall 算法：需要一个二维矩阵来存储所有顶点对之间的距离信息，空间复杂度是 。
（5）实际应用中的优化方法
Dijkstra 算法：
数据结构优化：除了上述提到的优先队列优化选取最短距离顶点的操作外，还可以根据具体场景选择合适的优先队列实现，比如斐波那契堆（理论上可以进一步优化时间复杂度，但实现复杂，实际中使用相对少些）。
提前终止条件：如果只需要计算到部分特定顶点的最短路径，当找到这些目标顶点的最短路径后可以提前终止算法运行，减少不必要的计算。
Floyd-Warshall 算法：
空间优化：由于每次迭代只用到上一层循环的距离矩阵信息，可以只使用两个二维矩阵交替使用，而不是一直保留所有迭代过程的矩阵，从而节省空间，将空间复杂度从 降低到 （只同时保存两份距离矩阵）。
稀疏图处理：对于稀疏图（边数远小于顶点数的平方的图），可以结合邻接表等稀疏图的存储方式来优化算法，减少对不存在边的无效计算，提高效率。
应用题：
1.MST
预测题目4：树，这里面内容就多了，
皮皮灰：可别考红黑树呀，顶多考选择题吧
计算机体系结构基础知识：包括指令格式、寻址方式、寄存器组织、数据通路等。
存储系统：包括虚拟存储管理、Cache、主存、磁盘等存储层次结构及其工作原理。
指令集架构（ISA）：包括RISC与CISC的区别、指令编码、指令功能等。
性能评估：包括CPI、MIPS、Cache命中率、缺页率等性能指标的计算与分析。
流水线与并发执行：包括流水线的基本概念、流水线的性能分析、相关与冲突的处理等。
输入输出系统：包括中断、DMA、I/O接口等输入输出机制的工作原理。
例题1：计算机体系结构基础知识
假定计算机M字长为32位，按字节编址，采用32位定长指令字。指令格式如下：
31-26 | 25-21 | 20-16 | 15-11 | 10-6 | 5-0
OP | rs2 | rs1 | rd | shamt | imm
其中，OP为操作码，rs1、rs2为源操作数寄存器编号，rd为目的操作数寄存器编号，shamt为位移量（仅用于位移指令），imm为立即数（仅用于某些指令）。
（1）M最多可以有多少个通用寄存器？为什么shamt占5位？
（2）若执行一条加法指令（ADD rs1, rs2, rd），控制信号ALUBsrc的取值应是什么？若rs1=0x12345678, rs2=0x87654321，则加法后ALU的输出是什么？
（3）执行位移指令（如SLLI）时，为什么EXT信号可以为0或1？
例题2：存储系统
假定计算机N采用分页存储管理，页大小为4KB，TLB采用全相联映射，Cache采用4路组相联映射，主存块大小为64B。
（1）若虚拟地址为32位，物理地址为24位，则虚拟地址中哪几位表示虚页号？哪几位表示页内偏移？
（2）Cache每行包含哪些字段？若Cache容量为32KB，则Cache共有多少行？
（3）若执行一条加载指令（LW rd, offset(rs1)），且rs1=0x1000，offset=0x100，则访问的物理地址是多少？若TLB命中，是否还需要访问二级页表？
假定计算机P采用RISC架构，指令字长为32位，指令格式如下：
31-26 | 25-21 | 20-16 | 15-11 | 10-6 | 5-0
OP | rs2 | rs1 | rd | fun | imm
其中，OP为操作码，rs1、rs2为源操作数寄存器，rd为目的操作数寄存器，fun为功能码，imm为立即数。
（1）P的指令集最多可以定义多少条不同的指令？
（2）若执行一条逻辑与指令（AND rs1, rs2, rd），且rs1=0xFFFFFFFF, rs2=0x0000FFFF，则rd的内容应是什么？
（3）若添加一条新的指令（如自定义的MUL指令），如何修改指令格式以支持这条新指令？
例题4：性能评估
假定计算机Q的CPU主频为2GHz，CPI为2，Cache命中率为90%，主存访问时间为50ns。
（1）Q的MIPS数是多少？
（2）若某程序执行了10^7条指令，Cache缺失率为10%，则程序的总执行时间是多少纳秒？
（3）为了提高性能，可以采取哪些措施？请简要说明理由。
例题5：流水线与并发执行
假定计算机R采用5段流水线执行指令，各段分别为IF（取指）、ID（译码）、EX（执行）、MEM（访存）、WB（写回）。
（1）若连续执行4条无相关指令，则至少需要多少个时钟周期？
（2）若第3条指令与第1条指令存在数据相关（即第3条指令需要使用第1条指令的结果），且没有采用转发技术，则第3条指令的执行会被阻塞多少个时钟周期？
（3）为了提高流水线效率，可以采取哪些措施来减少或消除相关和冲突？
例题6：输入输出系统
假定计算机S采用中断和DMA方式进行I/O操作，中断服务程序包含10条指令，DMA预处理和后处理各需要5个时钟周期。
（1）若每次I/O操作需要传输1KB数据，且数据传输率为1MB/s，则采用中断方式完成传输需要多少时钟周期？
（2）若改用DMA方式，且DMA控制器与CPU共享总线，每次DMA传输块大小为4KB，则完成相同数据量传输需要多少时钟周期？此时CPU的利用率是多少？
（3）为了提高I/O性能，还可以采取哪些措施？请简要说明理由。
操作系统历年真题考察较为固定
四大金刚轮流考
虚拟内存管理
页式存储管理：
页表结构、虚拟地址到物理地址的映射。
缺页处理、页面置换算法（如LRU、FIFO、CLOCK）。
示例：2024-45, 2020-46, 2015-46, 2013-46, 2009-46。
进程同步与互斥
信号量机制：
wait/signal（P/V）操作。
临界区管理、生产者-消费者问题、哲学家就餐问题。
示例：2024-46, 2023-45, 2023-46, 2022-46, 2021-45, 2020-45, 2019-43, 2019-44, 2017-46, 2016-45，2015-45, 2014-47, 2013-45, 2011-45, 2011-46, 2010-45, 2010-46, 2009-45。
文件系统
文件组织结构：
连续分配、链接分配、索引分配。
目录结构、文件控制块（FCB）。
文件插入与删除：连续分配与链接分配下的文件操作
示例：2022-45, 2016-46, 2014-46，2012-46, 2011-46, 2010-46。
磁盘调度与I/O系统
磁盘结构：
柱面、磁道、扇区。
磁盘调度算法（SSTF、SCAN、C-SCAN）。
示例：2023-46, 2019-44, 2015-46。
系统启动与引导
系统启动过程：
BIOS、主引导记录（MBR）、分区表。
示例：2021-46。
预测题目1：PV操作，必考
预测题目2：虚拟内存管理
预测题目4：磁盘
通过分析近年的考研CN题目，可以发现以下规律和重点：
基础知识与理论：
路由算法与协议（如RIP、OSPF、BGP）的选择与应用。
TCP/IP协议栈的工作原理，特别是TCP的连接管理、流量控制和拥塞控制。
以太网技术，包括CSMA/CD协议、以太网帧结构、MAC地址与IP地址的解析。
网络拓扑与子网划分，包括IP地址分配、子网掩码、广播地址等。
计算与应用：
TTL值、拥塞窗口、发送窗口的计算。
路由表的构建与更新，特别是路由聚合技术的应用。
数据传输速率、有效数据传输速率的计算。
以太网冲突检测与解决的时间计算。
综合分析与设计：
给定网络拓扑，分析并设计路由策略、IP地址分配方案。
根据网络需求，选择合适的网络设备（如路由器、交换机、集线器）和协议。
分析网络性能，如延迟、吞吐量、丢包率等，并提出优化建议
预测题目2：路由表更新与下一跳选择
预测题目3：TCP
预测题目4：某网络拓扑如图所示，包含三个自治系统AS1、AS2、AS3，其中AS1和AS2通过路由器R1和R2相连，AS2和AS3通过路由器R3和R4相连。AS1运行OSPF协议，AS2和AS3运行BGP协议。请回答以下问题：
（1）AS1和AS2之间应选择哪种路由协议进行路由信息交换？为什么？
（2）若AS3中的某主机想要访问AS1中的一个资源，其IP分组在穿越自治系统时，会经过哪些路由器？请写出完整的路径。
（3）在BGP协议中，如何防止路由环路的发生？请简述其工作机制。
预测题目5：某以太网网络中，主机A和主机B通过交换机S相连，主机A的IP地址为192.168.1.1，主机B的IP地址为192.168.1.2，子网掩码均为255.255.255.0。请回答以下问题：
（1）主机A想要向主机B发送一个数据帧，请描述数据帧的封装过程，包括各层的协议和数据。
（2）若主机A和主机B同时发送数据，导致数据在传输过程中发生冲突，请计算从开始发送数据到检测到冲突的最短和最长时间（假设信号传播速度为200000km/s，主机A和主机B之间的距离为1km）。
（3）若主机A以MSS=1000B的段向主机B发送数据，且每次发送后都等待确认再发送下一个段，请计算主机A的有效数据传输速率（不考虑以太网的前导码和帧间隔）。
可打印精选版本【人工答案】
数据结构汇总【答案不保真】
计算机网络模拟卷汇总
计算机组成原理模拟卷汇总
操作系统汇总
C语言模拟卷汇总【答案不保真】
