数据结构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）说明你所设计的算法的时间复杂度。
预测题目2：如果还考图的算法题的话
近几年，就只剩MST和最短路径问题算法没有考过了
算法题：
1.给定一个无向带权图，使用Prim算法或Kruskal算法求解最小生成树，并分析其时间复杂度。
2.设计一个算法来解决最短路径问题，如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的有效数据传输速率（不考虑以太网的前导码和帧间隔）。
25年全国院校计算机专业专业目录
【25考研】全国自命题分类统计【例如只考DS或程序设计】
