红黑树 算法复杂度_各排序的时间复杂度

【23考研】408——最新最细大纲解读（计算机统考专业课408篇） 　　前言 　　随着时间来到9月份，23考研的考研大纲也随之更新了。此篇文章就是对【23考研–计算机专业课408】学科进行最细最详细的分析与解读，其中包括各位名师的解析归纳与总结。 　　本系列只有一篇，即为【计算机统考专业课408篇】 　　如果文章对您有所帮助，麻烦点赞、喜欢、收藏、一下,多谢了！ 　　祝23考研每一个考研的小伙伴们都能一战成硕、成功上岸！

2023考研408 计算机大纲解析——@Mr丶鹏 　　一、大纲整体分析 　　2022.9.16，2023考研英语大纲终于揭晓。一般而言，每年考研计算机408中的新增考点，往往（基本上一定）也是当年的考查热点重点，其中包括【基本知识】、【题型变化】等内容。 　　本次2023计算机408大纲与2022考纲相比——【考试内容不变，试卷难度稳定】。 　　这对于广大考生来说，是一个好消息！但同时，我们也需要去简单读一读此次23考研计算机408大纲的内容，这样才可以避免“用前朝的尚方宝剑，斩本朝的贪官馋臣”这样的闹剧。

我这尚方宝剑——上斩昏君，下斩馋臣

你用明朝的剑，来斩清朝的官？ 　　二、大纲原文解析 　　1. 考试性质 　　计算机学科专业基础综合考试是为高等院校和科研院所招收计算机科学与技术学科的硕士研究生而设置的具有选拔性质的联考科目，其目的是科学、公平、有效地测试考生掌握计算机科学与技术学科大学本科阶段， 　　【专业知识】、【基本理论】、【基本方法】（即我们常说的计算机能力的“三基”）的水平和分析问题、解决问题的能力，评价的标准是高等院校计算机科学与技术学科优秀本科毕业生所能达到的及格或及格以上水平，以利于各高等院校和科研院所择优选拔，确保硕士研究生的招生质量。

| 考试性质 　　2. 考试目标 　　计算机学科专业基础综合考试涵盖【数据结构】、【计算机组成原理】、【操作系统】和计】算机网络等学科】 　　专业基础课程。要求考生比较系统地掌握上述专业基础课程的【基本概念】、【基本原理】和【基本方法】 ， 　　能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。

Ⅱ 考查目标 　　3. 试题形式与试卷结构 　　一、试卷满分及考试时间 　　本试卷满分为150分，考试时间为180分钟。 　　二、答题方式 　　答题方式为闭卷、笔试。 　　三、试卷内容结构数据结构45分计算机组成原理45分操作系统35分计算机网络25分 　　四、试卷题型结构单项选择题80分(40小题，每小题2分)综合应用题70分

Ⅲ 试题形式与试卷结构 　　4. 试卷分类及使用专业 　　计算机408的介绍计算机408是初试科目的代码，即计算机学科专业基础综合的科目代码，方便考研管理和区分。考研408计算机学科专业基础综合其实就是全国统考科目，如果初试科目的代码是数字8或者9开头的计算机专业课则是各个学校自主命题。计算机考研要查看招生单位公布的专业目录，因为8开头的科目是自主命题的科目，所以不同单位的内容和要求可能不一样。

计算机408的介绍 　　2. 计算机408的使用专业目前，大部分院校的计算机相关专业（>50%），常见计算机相关专业代码如下：1、计算机科学与技术: 080901.2、 软件工程: 080902。3、网络工程: 080903。4、信息安全: 080904K.5、物联网工程: 080905。6、数字媒体技术: 080906。7、智能科学 与技术: 080907T。 .8、空间信息与数字技术: 080908T 。9、 电子与计算机工程: 080909T。10、 数据科学与大数据技术: 080910T。11、网络空间安全: 080911TK。12、电子信息：085400（专硕）

计算机类专业代码 　　5. 考试内容和考试要求 　　Part 1：数据结构 　　【数据结构】——【考查目标】1. 掌握数据结构的基本概念、基本原理和基本方法。2. 掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。3. 能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力。

数据结构-1 　　一、线性表(一) 线性表的基本概念(二) 线性表的实现1 顺序存储⒉ 链式存储(三) 线性表的应用

数据结构-2 　　二、栈、队列和数组(一)栈和队列的基本概念(二)栈和队列的顺序存储结构(三)栈和队列的链式存储结构(四)多维数组的存储(五)特殊矩阵的压缩存储(六)栈、队列和数组的应用

数据结构-3 　　三、树与二叉树(一) 树的基本概念(二) 二叉树1. 二叉树的定义及其主要特征2. 二叉树的顺序存储结构和链式存储结构3. 二叉树的遍历4. 线索二叉树的基本概念和构造(三) 树、森林树的存储结构⒉.森林与二叉树的转换3. 树和森林的遍历(四)树与二叉树的应用(1) 哈夫曼(Huffman)树和哈夫曼编码(2) 并查集及其应用

数据结构-4 　　四、图(一) 图的基本概念(二) 图的存储及基本操作1. 邻接矩阵法2. 邻接表法3. 邻接多重表、十字链表（三）图的遍历 1. 深度优先搜索2. 广度优先搜索（四）图的基本应用1. 最小(代价)生成树2. 最短路径3. 拓扑排序4. 关键路径五、查找（一）查找的基本概念（二) 顺序查找法（三）分块查找法（四）折半查找法(五)B树及其基本操作、B+树的基本概念(六)散列(Hash)表(七)树型查找1. 二叉搜索树2. 平衡二叉树3. 红黑树六、排序

数据结构-5

数据结构-6 　　六、排序(一) 排序的基本概念(二) 插入排序1. 直接插入排序⒉.折半插入排序(三) 气泡排序(bubble sort)(四) 简单选择排序(五) 希尔排序(shell sort)(六) 快速排序(七) 堆排序(八) 二路归并排序(merge sort)(九) 基数排序(十) 外部排序(十一) 排序算法的分析与应用

数据结构-7 　　Part 2：计算机组成原理 　　【计算机组成原理】——【考查目标】1. 理解单处理器计算机系统中各部件的内部工作原理、组成结构以及相互连接方式，具有完整的计算机系统的整机概念。2. 理解计算机系统层次化结构概念，熟悉硬件与软件之间的界面，掌握指令集体系结构的基本知识和基本实现方法。3. 能够综合运用计算机组成的基本原理和基本方法，对有关计算机硬件系统中的理论和实际问题进行计算、分析，对一些基本部件进行简单设计;并能对高级程序设计语言(如C语言)中的相关问题进行分析。

计算机组成原理-1 　　一、计算机系统概述(一) 计算机系统层次结构1. 计算机系统的基本组成2. 计算机硬件的基本结构3. 计算机软件和硬件的关系4. 计算机系统的工作原理“存储程序”工作方式，高级语言程序与机器语言程序之间的转换,程序和指令的执行过程(二)计算机性能指标吞吐量、响应时间;CPU时钟周期、主频、CPI、CPU执行时间;MIPS、MFLOPS 、GFLOPS、TFLOPS、PFLOPS、EFLOPS、ZFLOPS。

计算机组成原理-2 　　二、数据的表示和运算(一) 数制与编码1. 进位计数制及其相互转换2. 真值和机器数3. 字符与字符串(二) 定点数的表示和运算1. 定点数的表示无符号数的表示;有符号整数的表示。2. 定点数的运算定点数的位移运算; 原码定点数的加减运算; 补码定点数的加/减运算; 定点数的乘/除运算; 溢出概念和判别方法。(三) 浮点数的表示和运算1. 浮点数的表示IEEE 754标准2. 浮点数的加/减运算(四) 运算方法和运算电路【表述变更】1. 基本运算部件:加法器、算数逻辑部件ALU⒉.减法运算:补码加减运算器，标志位的生成3. 乘除运算:乘除运算的基本原理，乘除发电路的基本结构

计算机组成原理-3 　　三、存储器层次结构(一) 存储器的分类(二) 层次化存储器的的基本结构(三) 半导体随机存取存储器1. SRAM存储器2. DRAM存储器3. Flash 存储器(四) 主存储器1. DRAM芯片和内存条2. 多模块存储器3. 主存和CPU之间的连接(五) 外部存储器1. 磁盘存储器2. 固态硬盘(SSD)(六) 高速缓冲存储器(Cache)1. Cache 的基本工作原理2. Cache和主存之间的映射方式3. Cache 中主存块的替换算法4. Cache 写策略(七) 虚拟存储器1. 虚拟存储器的基本概念2. 页式虚拟存储器基本原理，页表，地址转换，TLB(快表)。3. 段式虚拟存储器4. 段页式虚拟存储器

计算机组成原理-4 　　四、指令系统(一) 指令系统的基本概念(二) 指令格式(三) 寻址方式(四) 数据的对齐和大/小端存放方式(五) CISC和RISC的基本概念(六) 高级语言程字与机器级代码之间的对应1. 编译器、汇编器和链接器的基本概念2. 选择结构语句的机器级表示3. 循环结构语句的机器级表示4. 过程(函数)调用对应的机器级表示

计算机组成原理-5

计算机组成原理-6 　　五、中央处理器(CPU)(一) CPU的功能和基本结构(二) 指令执行过程(三) 数据通路的功能和基本结构(四) 控制器的功能和工作原理1、硬布线控制器2、微程序控制器微程序、微指令和微命令 ;微指令的编码方式; 微地址的形式方式。(五) 异常和中断机制1. 异常和中断的基本概念2. 异常和中断的分类3. 异常和中断的检测与响应(六) 指令流水线1、指令流水线的基本概念2、指令流水线的基本实现3.、结构冒险、数据冒险和控制冒险的处理4.超标量和动态流水线的基本概念(七) 多处理器基本概念1、SISD、SIMD、MIMD、向量处理器的基本概念2、硬件多线程的基本概念3、多核处理器(multi-core)的基本概念4、共享内存多处理器(SMP)的基本概念

计算机组成原理-7 　　六、总线和输出输出系统（一）总线概述1、总线的基本概念2、总线的组成及性能指标3、总线事务和定时(二) I/O接口(I/O控制器)1、I/O接口的功能和基本结构2、I/O端口及其编址(三) I/O方式1、程序查询方式2、程序中断方式中断的基本概念; 中断响应过程; 中断处理过程; 多重中断和中断屏蔽的概念。3、DMA方式DMA 控制器的组成，DMA传送过程。

计算机组成原理-8 　　Part 3：操作系统 　　【操作系统】——【考查目标】1. 握操作系统的基本概念、基本原理和基本功能，理解操作系统的整体运行过程。2. 掌握操作系统进程、内存、文件和I/O管理的策略、算法、机制以及相互关系。3. 能够运用所学的操作系统原理、方法与技术分析问题和解决问题，并能利用C语言描述相关算法。

操作系统-1 　　一、操作系统概述(一) 操作系统的基本概念(二) 操作系统的发展(三) 程序运行环境1. CPU运行模式内核模式，用户模式2. 中断和异常的处理3. 系统调用4. 程序的链接与装入5. 程序运行时内存映像与地址空间(四) 操作系统结构分层，模块化，宏内核，微内核，外核。(五) 操作系统引导(六) 虚拟机

操作系统-2 　　二、进程管理(一) 进程与线程1. 进程概念。2. 进程的状态与转换。3. 线程的实现内核支持的线程，线程库支持的线程。4. 进程与线程的组织与控制5.进程间通信共享内存，消息传递，管道。(二) CPU调度与上下文切换1. 调度的基本概念2. 调度的目标3. 调度的实现调度器/调度程序(scheduler)，调度的时机与调度方式(抢占式/非抢占式)，闲逛进程，内核级线程与用户级线程调度。4. 典型调度算法先来先服务调度算法; 短作业(短进程、短线程)优先调度算法; 时间片轮转调度算法; 优先级调度算法; 高响应比优先调度算法; 多级反馈列调度算法。5. 上下文及其切换机制(三) 同步与互斥1. 进程同步的基本概念2.实现临界区互斥的基本⽅法——软件实现方法; 硬件实现方法3. 锁4. 信号量5. 条件变量6. 经典同步问题生产者-消费者问题; 读者-写者问题; 哲学家进餐问题。(四) 死锁1. 死锁的概念2. 死锁预防3. 死锁避免4. 死锁检测和解除

操作系统-3

操作系统-4 　　三、内存管理(一) 内存管理基础1. 内存管理的基本概念程序装入与链接; 逻辑地址与物理地址空间; 内存保护，内存分配与回收。2. 连续分配管理方式3. 分页管理方式4. 分段管理方式5. 段页式管理方式。(二) 虚拟内存管理1. 虚拟内存基本概念2. 请求分页管理方式3. 页框分配4. 页面置换算法最佳置换算法(OPT); 先进先出置换算法(FIFO); 最近最少使用置换算法(LRU); 时钟置换算法(CLOCK)。5. 内存映射文件(Memory-Mapped Flies)6. 虚拟存储器性能的影响因素及改进方法

操作系统-5 　　四、文件管理(一) 文件系统基础1. 文件概念2. 文件数据和索引节点3. 文件的操作建立，删除，打开，关闭，读，写。4. 文件共享5. 文件的逻辑结构6. 文件的物理结构(二) 目录1. 目录的基本概念2. 树形目录3. 目录的操作4. 硬链接与软链接(三) 文件系统1. 文件系统的全局结构(layout)文件系统在外存中的结构，文件系统在内存中的结构。2. 外存空闲空间管理方法3. 虚拟文件系统4. 文件系统挂载(mounting)

操作系统-6 　　五、输入输出(I/O)管理(—) 1/O管理基础1. 设备设备的基本概念，设备的分类，I/O接口，I/O端口。2. I/O控制方式轮询方式，中断方式，DMA方式。3. I/O软件层次结构中断处理程序，驱动程序，设备独立软件，用户层IV/O软件。4. 输入输出应用程序接口字符设备接口，块设备接口，网络设备接口，阻塞/非阻塞I/O。(二) 设备独立软件1. 缓冲区管理2. 设备分配与回收3. 假脱机技术(SPOOLing)4. 设备驱动程序接口(三) 外存管理1. 磁盘磁盘结构，格式化，分区，磁盘调度方法。2. 固态硬盘读写性能特性，磨损均衡。

操作系统-7 　　Part 4：计算机网络 　　【计算机网络】——【考查目标】1、掌握计算机网络的基本概念、基本原理和基本方法。2、掌握计算机网络的体系结构和典型网络协议，了解典型网络设备的组成和特点，理解典型网络设备的工作原理。3、能够运用计算机网络的基本概念、基本原理和基本方法进行网络系统的分析、设计和应用。

计算机网络-1 　　一、计算机网络体系结构(一) 计算机网络概述1. 计算机网络的概念、组成与功能2. 计算机网络的分类3. 计算机网络主要性能指标(二) 计算机网络体系结构与参考模型1. 计算机网络分层结构2. 计算机网络协议、接口、服务等概念3. SO/OSI参考模型和TCP/IP模型

计算机网络-2 　　二、物理层(一) 通信基础1. 信道、信号、宽带、码、波特、速率、信源与信宿等基本概念2. 奈奎斯特定理与香农定理3. 编码与调制4. 电路交换、报文交换与分组交换5. 数据报与虚电路(二) 传输介质1. 双绞线、同轴电缆、光纤与无线传输介质2. 物理层接口的特性(三) 物理层设备1. 中继器2. 集线器

计算机网络-3 　　三、数据链路层(一) 数据链路层的功能(二) 组帧(三) 差错控制1. 检错编码⒉纠错编码(四) 流量控制与可靠传输机制1. 流量控制、可靠传输与滑轮窗口机制2. 停止-等待协议3. 后退N帧协议(GBN)4. 选择重传协议(SR)(五) 介质访问控制1. 信道划分频分多路复用、时分多路复用、波分多路复用、码分多路复用的概念和基本原理。2. 随即访问ALOHA协议; CSMA协议; CSMA/CD协议; CSMA/CA协议。3. 轮询访问令牌传递协议(六) 局域网1. 局域网的基本概念与体系结构2. 以太网与IEEE 802.33. IEEE 802.114. VLAN基本概念与基本原理(七) 广域网1. 广域网的基本概念2. PPP协议

计算机网络-4 　　四、网络层(—) 网络层的功能1. 异构网络互联2. 路由与转发3. SDN基本概念4. 拥塞控制(二) 路由算法1. 静态路由与动态路由2. 距离-向量路由算法3. 链路状态路由算法4. 层次路由(三) IPv41. lPv4分组2. IPv4地址与NAT3. 子网划分与子网掩码、CIDR4. ARP协议、DHCP协议与ICMP协议(四) IPv61. lPv6的主要特点2. IPv6地址(五) 路由协议1. 自治系统2. 域内路由与域间路由3. RIP路由协议4. OSPF路由协议5. BGP路由协议(六) IP组播1. 组播的概念2. IP组播地址(七) 移动IP1. 移动IP的概念2. 移动IP的通信过程 (八) 网络层设备1. 路由器的组成和功能2. 路由表与路由转发

计算机网络-5 　　五、传输层(一) 传输层提供的服务1. 传输层的功能2. 传输层寻址与端口3. 无连接服务与面向连接服务。(二) UDP协议1. UDP数据报2. UDP校验(三) TCP协议1. TCP段2. TCP连接管理3. TCP可靠传输4. TCP流量控制与拥塞控制

计算机网络-6 　　六、应用层(一) 网络应用模型1. 客户/服务器模型2. P2P模型(二) DNS系统1. 层次域名空间2. 域名服务器3. 域名解析过程(三) FTP1. FTP协议的工作原理2. 控制连接与数据连接(四) 电子邮件1. 电子邮件系统的组成结构2. 电子邮件格式与MIME3. SMTP协议与POP3协议(五) Www1. WWW的概念与组成结构2. HTTP协议

计算机网络-7 　　三、计算机408大纲解析 　　1. 数据结构变化 　　2022年大纲：领接矩阵法2023年大纲：领接矩阵考试情况预测：大概率选择题，小概率算法设计题考察分析：已考过。基础选择题题，编程题中应用的存储结构。改动共计1处，表述换掉，考查内容不变。

数据结构中大纲变化部分 　　2. 计算机组成原理变化 　　2022年大纲：1.进位计数制及其数据直接的相互转换（共2处）1.进位计数制及其数据直接的相互转换2.有符号整数的表示和运算2023年大纲：1.进位计数制及其数据之间的相互转换2.带符号整数的表示和运算1.进位计数制及其数据之间的相互转换2.带符号整数的表示和运算考试情况预测：选择题考察分析：已考过。改动共计2处，表述换掉，考查内容不变。

计算机组成原理中大纲变化部分 　　3. 操作系统变化 　　2022年大纲：1.多级队列调度算法、多级反馈队列调度算法2023年大纲：1.多级反馈队列调度算法考试情况预测：选择题考察分析：已考过。改动共计1处，表述换掉，考查内容不变。

操作系统中大纲变化部分 　　4. 计算机网络变化 　　计算机网络没有任何变动，可以按照原来的复习进度继续复习。

计算机网络中大纲变化部分 　　5. 408专业课复习指导 　　（1）对于9月份才开启专业课复习的同学或者专业课复习很少的同学。（危险） 　　这部分同学的408科目进度是非常危险的，但是也有希望。这部分同学，接下来想要快速的提升专业课的复习，如果手边有可以听的直播课或录播课可以先跟着录播课听，这样可以快速提升专业课复习的效率。其次就是专业课中要先抓高频考点，对于细枝末节的知识点可以先忽略掉，等到后续再查漏补缺，这样可以在短时间内掌握大部分考点内容，能够保证在考试的时候基础分数拿到。

对于9月份才开启专业课复习的同学或者专业课复习很少的同学。 　　（2）对于暑假前就开始专业课复习的同学。（正常） 　　相信这部分同学已经把408的4们课基础知识复习完了，复习进度正常。那么，在接下来的复习的过程中不要忘记做题！如果手边练习题比较多，可以优选408的考研试题，408考研试题可以反复的做，把错题，难题进行总结，分析出题的要点，做错的原因，把高频点掌握熟练，因为408往年考过的题，有可能在最新一年再次考到，所以多联系408考研试题，可以快速掌握高频考点。如果408题做了很多遍，可以适当的练习些模拟题，提升灵活运用知识的能力。

对于暑假前就开始专业课复习的同学。 　　（3）对于寒假前就开始专业课复习的同学。（优秀） 　　这部分的同学是非常优秀的，对408的难度是非常了解的，也是下足了功夫复习。那么，在接下来的复习中，对于4门课的痛点问题，比如数据结构的编程题，可以采取训练在平时的复习思路，不要把时间都集中在最后一个月再去突击代码，那样时间不够用，所以，可以考虑每周练习一定数量的题目，然后循序渐进的把编程知识扎实了。同样的操作系统的pv操作的练习，也可以采用这样的方法。等到考前，水平一定会有质的提升。

对于寒假前就开始专业课复习的同学。 　　尾言 　　考研【计算机统考专业课408篇】的大纲解析与大纲变动详细已经更新完毕，谢谢大家的观看~！注：需要《研究生考研计算机统考专业课408篇大纲解析(2023版)》，可以直接私信。

我，一定上岸！ 　　如果文章对您有所帮助，麻烦点赞、喜欢、收藏、一下,多谢了！ 　　祝23考研每一个考研的小伙伴们都能一战成硕、成功上岸！