第1页 / 共49页
第2页 / 共49页
第3页 / 共49页
第4页 / 共49页
第5页 / 共49页
第6页 / 共49页
第7页 / 共49页
第8页 / 共49页
考研复试整理.pdf
数据结构
1. 时间复杂度
2. 循环队列的顺序表中，为什么要空一个位置？
3. 什么是二叉排序树？以及它的原理，算法。（二叉排序树的查找过程）
4. 哈夫曼树
5. 什么是哈希冲突？以及如何解决。
6. 深度优先搜索遍历和广度优先搜索遍历的过程
7. 迪杰斯特拉算法的过程
8. 链表查找某个元素，平均的时间复杂度是多少？
9. 图的存储方式
10. 图的深度遍历是否唯一
11. 图的相关概念
12. 最小生成树的概念
13. 平衡二叉树
14. 二叉树的存储
15. M阶B-树和M阶B+树的主要区别
16. 折半查找，以及其适用范围和时间复杂度
17. 完全二叉树
18. 什么是堆？有什么作用？
19. 如何实现循环队列？有何好处？
20. 深度优先搜索形成的是什么？森林唯一么？
21. 满二叉树的结点个数（n层）
22. 二叉查找树查找的时间复杂度以及中序遍历后得到什么样的序列
23. 什么图可以进行拓扑排序？
24. 顺序队列的特征
25. 非连通图如何访问每一个结点？
26. 排序总结
27. 查找：相关章节过一遍。
操作系统
1. 进程和程序的区别
2. 进程和线程的区别
3. 什么是微内核？
基本功能：
4. 什么是DMA？什么是中断？两者的区别。
5. 硬中断和软中断是什么？区别是什么？
6. 页面置换算法有哪些？什么是LRU？
7. 操作系统中的磁盘调度算法
8. 操作系统中的信号量
9. PV操作
10. 什么是操作系统？
11. 操作系统的组成
12. 操作系统中用到了哪些数据结构中的数据结构？请举例说明
13. 简述操作系统中系统调用过程
14. 虚拟存储器，以及相关算法。
15. 存储器管理应具有的功能
16. 什么是TLB？
17. 程序的装入方式有哪些？
18. 程序的链接方式有哪些？
19. 交换技术，覆盖技术，以及两者的区别。
20. 内存连续分配管理方式有哪些？
21. 动态分区分配的算法有哪些？
22. 什么叫拼接技术？
23. 什么叫原子操作？
24. 内部碎片和外部碎片
25. 常用的存储保护方法
26. 连续分区分配和非连续分区分配的比较
27. 什么是页表？有什么作用。
28. 什么是段寄存器？
29. 进程线程树图
30. 作业和进程的区别
31. 进程的三个状态以及转换过程
32. 进程调度算法有哪些？（再详细了解其中的算法思想）
33. 死锁
死锁原因：
产生死锁的必要条件：
处理死锁的基本方法：
34. 什么是饥饿？与死锁有什么差别？
35. 分段和分页的区别
36. 银行家算法
37. RAID磁盘阵列
38. 控制管理模块是写在哪个文件里的？那个文件叫做什么文件？
计算机网络
1. 连接2个局域网需要用什么 在那一层
2. TCP与UDP的连接区别及适用情况
1. 基于连接vs无连接
2. 可靠性
3. 有序性
4. 速度
5. 重量级vs轻量级
6. 流量控制和拥塞控制
7. TCP是面向字节流，UDP是面向报文的
8. TCP只能单播，不能广播和组播；UDP可以广播和组播
3. 路由和交换的区别
一、 第二层交换机和路由器的区别
二、第三层交换机和路由器的区别
4. 七层网络结构
5. 时分复用的时隙
6. IPV4**和IPV6的位数**
7. 单工、半双工、全双工
9. 网络通信过程
10. 简述一下停等协议
11. 应用层有什么协议，举出两个协议的作用
12.数据链路层的作用
13.路由协议有哪些
14. 频分复用如何避免各路信号间的干扰
15. 简述计算机网络中各层作用 这问题回答之后 老师一直追着网络层问了好多 问得我发懵了。。
16. 列举数据链路层的协议。。2个即可
17. 网络各层的设备分别是什么
18. 什么是滑动窗口协议
19. PPP协议
20. 网络按地理范围分
21. 保护频带 就是插入一些 空白的频段
22. 一个网络安全有哪些方面，还有个p2p协议
23. DNS DHCP DNS倒是记得是让网址转换IP地址的 映射IP地址 动态主机。。协议 DHCP是动态分配ip吗
24. 流量控制在哪些层实现
25. 频分复用 时分复用 波分复用 码分复用
26. CSMA/CD 协议 如果两端同时发送信息会出现什么情况，为什么？
27. 电路交换，分组交换
29. 简述下CSMA/CD协议的实现原理
30. 描述网络某一层的原理
31. 说一下路由器的原理
计算机网络
1. 网络里时延和带宽的概念
2. 网络拥塞
3. CSMA/CD的原理（载波侦听多路访问/冲突检测方法）
4. 三网指哪三网？
5. 组成网络协议的三个要素
6. 电路交换，报文交换，分组交换之间的区别以及联系
7. 分组交换的优点和缺点
优点：
缺点：
8. 流量控制在哪些层实现？
9. CDMA及原理
10. 二层交换机和三层交换机的区别
11. 频分复用如何避免频带间的干扰，保护频带？
12. 停止等待协议
13. IPv4地址缺乏的解决办法以及IPv4的替代方案以及IPv4和IPv6如何相互通信？
IPV6
表示方法
报文内容
扩展头部：
14. 传统的搜索引擎基本原理，基于内容的搜索？原理和实现？
从互联网上抓取网页：
建立索引数据库：
在索引数据库中搜索排序：
对搜索结果进行处理排序：
15. 什么是非对称加密？什么是数据安全的特征？
对称加密与非对称加密
数据安全的特征
1）机密性（Confidentiality）
2）完整性（Integrity）
3）可用性（Availability）
16. 网络安全有哪些方面
1、系统安全
2、网络的安全
3、信息传播安全
4、信息内容安全
维护网络安全的工具有VIEID、数字证书、数字签名和基于本地或云端的杀毒软体等构成。
1、Internet防火墙
2、VIEID
3、数字证书
17. 网络的分类
18. 有关于信道划分的问题
信道共享技术：
19. 曾经问到过的协议
ICMP
响应请求
目标不可到达、源抑制和超时报文
时间戳
PPP
DNS
DHCP
21. 计算机网络各层设备及工作原理总结
22.计算机网络协议总结（按层总结：什么层，协议，作用，特点等）
计算机组成，微机原理，通信原理
1. RAM和ROM的原理和区别（在基本存储单元上存在本质区别）
RAM:
ROM：
2. 一位全加器的真值表以及逻辑表达式
3. 什么是芯片组
4. 触发器相关的问题
5. 中断的软件实行过程
6. 查询传输和中断传输，解释比较
7. 过程调用具体执行了哪些操作
8. PC机的端口是同步的还是异步的？什么是异步？
9. 控制单元设计··分为组合逻辑和微程序··两者区别··优缺点·
10. 关于IO接口的，微机原理中的内容，要仔细看下。
11. 中断（概念，补充：中断可不可以被打断，有哪些情况）
23. 简述RAM、ROM、PROM、EPROM、EEPPROM的区别（第一题说过了。。。）
24. 什么是指令，时钟，总线周期，有什么关系
25. 80x86的硬件组成
26. 80x86的寻址方式
27. 条件查询的工作方式
28. call和return 具体做了哪些工作
29. DMA和中断数据传输有什么区别
30. 选择回答了cache的相关知识
计算机组成，微机原理，通信原理
1. 电子线路，集成电路设计流程
2. 单片机和PC机的cpu区别
3. N、P型半导体和PN结原理
4. 传递函数里并联环节的等效
5. 能控性、能观性概念（属于信号系统学科或控制学科）
Controllability：可控性。（起始状态一定，输入不一定的情况下）
Observability：可观性。（起始状态不一定，给定输入）
6. AD转换后的精度由什么决定（这个没回答出来），DA转换的具体过程。
7. 老师看我考的是自动控制原理，问的我渐进稳定的问题。
8. 说一下什么是波长，波长的计算方法是什么。
9. 多普勒（老师说看你物理学的不错）
10. 无线通信的3种方式。（这个问的有歧义。。给两种答案）
11. 奈奎斯特定律
12. 解释单工 全双工 半双工
13. 数据传输方式
中科大复试准备
数据结构->操作系统->计算机网络->通信原理->微机原理->
软件工程，编译原理，数据库
数据结构
1. 时间复杂度
时间复杂度 是指执行算法所需要的计算工作量，因为整个算法的执行时间与基本操作重复执行的次数成
正比，所以将算法中基本操作的次数作为算法时间复杂度的度量，一般情况下，按照基本操作次数最多
的输入来计算时间复杂度，并且多数情况下我们去最深层循环内的语句所描述的操作作为基本操作。
2. 循环队列的顺序表中，为什么要空一个位置？
这是为了用来区分队空与队满的情况。如果不空一个位置，则判断队空和队满的条件是一样的。
3. 什么是二叉排序树？以及它的原理，算法。（二叉排序树的查找过程）
二叉排序树又称二叉查找树，它或者是一颗空树，或者满足一下性质的二叉树：
① 若左子树不空，则左子树上所有结点的值均小于根节点的值；
② 若右子树不空，则右子树上所有结点的值均大于根节点的值；
③ 左右子树也分别是二叉排序树。
原理步骤：
若根结点的 关键字 值等于查找的关键字，成功。
否则，若小于根结点的 关键字 值， 递归 查左子树。
若大于根结点的 关键字 值， 递归 查右子树。
若子树为空，查找不成功。
4. 哈夫曼树
定义：
给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二
叉树，也称为哈夫曼树(Hu man tree)。
构造方法：
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼
树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值
为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
特点：
① 权值越大的结点，距离根节点越近；
② 树中没有度为一的结点。
应用：
哈夫曼编码，减少编码的长度。哈夫曼编码就是长度最短的前缀编码。
5. 什么是哈希冲突？以及如何解决。
散列（哈希）表：
根据关键码值(Key value)而直接进行访问的 数据结构 。根据给定的关键字来计算出关键字在表中的地
址，以加快查找的速度。
冲突：指的是多个关键字映射同一个地址的情况。
解决办法：
（1） 开放定址法
① 线性探查法（产生堆积问题）；
② 平方探查法（不能探查到哈希表上所有的地址，但至少能探查到一半的地址）
（2） 链地址法
把所有的同义词用单链表连接起来。
补充（常见的哈希函数构造方法）
直接定址法，数字分析法，平方取中法，除留余数法。
6. 深度优先搜索遍历和广度优先搜索遍历的过程
深度优先搜索遍历
基本思想：首先访问出发点V，并将其标记为已访问；然后选取与V邻接的未被访问的邻接顶点W，访问
W；再选取与W邻接的未被访问的顶点访问，以此类推。当一个顶点所有的邻接顶点都被访问过时，则
依次退回最近被访问过的顶点，若该顶点还有其他邻接顶点未被访问，则从这些顶点中去一个顶点进行
上述的过程，直至图中所有顶点都被访问过为止。
广度优先搜索遍历
基本思想：首先访问起始顶点V，然后选取与V邻接的全部顶点w1，w2，….，wn进行访问，再一次访问
与w1，w2，…
，wn邻接的全部顶点（不包括已访问过的顶点），以此类推，直至所有顶点都被访问过为止。
7. 迪杰斯特拉算法的过程
该算法可以求得某一顶点到其余各顶点的最短路径。
算法思想：设有两个顶点集合S和T，其中集合S中存放的是图中已找到最短路径的顶点，集合T中存放的
是图中的剩余顶点。
初始状态时，集合S中只包含源点V0，然后不断从集合T中选取到顶点V0路径最短的顶点Vu并加入集合S
中。集合S每加入一个新的顶点Vu，都要修改V0到集合T中各个顶点的最短路径的长度值。不断重复这个
过程，直至集合T中的顶点全部并入到S中为止。
8. 链表查找某个元素，平均的时间复杂度是多少？
O(n) 链表是顺序存储，故（1+n）/2。
9. 图的存储方式
① 邻接矩阵：是图的顺序存储结构，用两个数组分别存储数据元素（顶点）信息和数据元素之间的关
系（边/弧）的信息。图的邻接矩阵表示是唯一的，无向图的邻接矩阵是对称的。
② 邻接表：是图的链式存储结构，由单链表的表头形成的顶点表和单链表其余结点所形成的边表两部
分组成。
③ 十字链表：有向图的另一种链式存储结构。
④ 邻接多重表：无向图的链式存储结构。
10. 图的深度遍历是否唯一
不一定是不唯一。我们可以取图中任一顶点进行深度遍历。
11. 图的相关概念
图：由结点的有穷集合V和边的集合E组成。
类别：有向图和无向图。
顶点的度：出度和入度。
有向完全图和无向完全图： 若有向图有n个顶点，则最多有n(n-1)条边，则称为有向完全图；
若无向图有n个顶点，则最多有n(n-1)/2条边，则称为无向完全图。
路径：相邻顶点序偶所构成的序列。
简单路径：序列中的顶点和路径不重复出现的路径。
回路：路径中第一个顶点和最后一个顶点相同的路径。
连通： 无向图中，如果Vi到Vj有路径，则称这两个顶点连通。如果图中任意两个顶点之间都连通，则称
改图为连通图。
有向图中，如果Vi到Vj有路径，则称这两个顶点连通。如果图中每一对顶点Vi和Vj，从Vi到Vj和Vj到Vi都有
路径，则称改图为强连通图。
12. 最小生成树的概念
一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持
图联通的最少的边。如果在最小生成树中添加一条边，必定成一个环。
相关算法：
① 普里姆算法
② 克鲁斯卡尔算法
N个结点的最小生成树有几个结点，几条边：n个结点，n-1 条边。
13. 平衡二叉树
平衡二叉树又称AVL树，是一种特殊的二叉排序树，其左右子树都是平衡二叉树，且左右子树的高度差
的绝对值不超过1.
平衡因子： 左子树高度减去右子树高度的差。
平衡调整： 先找到失去平衡的最小子树，即以距离插入结点最近，且平衡因子绝对值大于1的结点最为
根节点的子树，分为LL,LR,RL,RR四中调节方式。
14. 二叉树的存储
① 顺序存储结构：用一个数组来存储一颗二叉树，二叉树中的结点值按照编号依次存入一个一维数组
中。适用于完全二叉树，若用于一般的二叉树则会浪费大量存储空间。
Lchild
Data
Rchild
② 链式存储结构：二叉树中的每一个结点用一个链结点来存放。
15. M阶B-树和M阶B+树的主要区别
① B+树所有有效数据全在叶子节点，而B-树所有节点分散在树中，B-树中的关键字不重复。
② B+树种有几个关键字就有几个子树，B-树中具有n 个关键字的节点含有(n+1)棵子树。
③ B+树有两个指针，根指针和只想最小节点的指针，叶子节点连接成一个不定长的线性链表
④ B+树中，每个节点（除根节点外）中的关键字个数n 的取值范围是⌈m/2⌉<=n<=m，根节点n 的取值
⑤ 范围是2<=n<=m。B-树中，每个节点（除根节点外的所有最底层非叶子节点）中的关键字取值范围是
⑥ ⌈m/2⌉-1<=n<=m-1，根节点n 的取值范围是1<=n<[m-1]。
⑦ B+树中的所有非叶子节点仅仅起到索引的作用，节点中的每个索引项只包含对应子树的最大关键字
和
指向该子树的指针，不含有该关键字对应记录的存储地址。而在B-树中，每个关键字对应记录的存储
地址。
16. 折半查找，以及其适用范围和时间复杂度
又称二分查找，基本思路：
在当前的查找区间[low…high]中，首先确定mid=(low+high)/2，然后拿关键字与mid比较，若相等则查找
成功，返回该位置，否则确定新的查找区间， mid>K，[low…mid-1]
mid
好处：循环队列是顺序队列的改进，在顺序队列中，在元素进队的时候，rear要向后移动，元素出队的
时候，front也要向后移动，这样经过一系列的出队和入队操作之后，两个指针最后会达到数组的末端，
此时虽然队中已经没有元素了，但是还是不能让元素入队，即出现了“假溢出”的现象。循环队列就能避
免出现这个现象。
20. 深度优先搜索形成的是什么？森林唯一么？
（森林，不能说树）（不唯一，因为邻接表可能不唯一）
21. 满二叉树的结点个数（n层）
2的n次方减一（2n-1）
22. 二叉查找树查找的时间复杂度以及中序遍历后得到什么样的序列
递增有序序列
23. 什么图可以进行拓扑排序？
有向无环图
24. 顺序队列的特征
队列是一种操作受限的线性表，只允许队尾入队，在队头进行出队。最大的特点是先进先出。
25. 非连通图如何访问每一个结点？
节点循环，DFS或者BFS。
26. 排序总结
排序方法
时间复杂度
空间 复杂度
稳定性
平均情况
最坏情况
最好情况
插入排序
直接插入
折半插入
O(n2)
O(n2)
O(n2)
希尔排序
O(nlog2n)
交换排序
冒泡排序
快速排序
O(nlog2n)
O(n2)
O(n2)
O(n)
O(1)
O(1)
O(n)
O(n2)
O(n2)
O(nlog2n)
O(n2)
O(1)
稳定
不稳定
稳定
O(1)
稳定
O(nlog2n)
O(log2n)
不稳定
选择排序
简单选择
排序方法
O(n2)
时间复杂度
O(n2)
空间 复杂度
O(n2)
稳定性
O(1)
不稳定
堆积排序
O(nlog2n)
O(nlog2n)
O(nlog2n)
O(1)
不稳定
其他排序
二路归并
O(nlog2n)
O(nlog2n)
O(nlog2n)
基数排序
O(d（n+r）)
O(d（n+r）)
O(d（n+r）)
O(r)
O(n)
稳定
稳定
各类排序的算法详见书本。（需要说出每个算法的基本思想）
27. 查找：相关章节过一遍。
操作系统
1. 进程和程序的区别
① 进程是动态的，程序是静止的。进程是程序的执行，程序是有序代码的集合。
② 进程是暂时的，程序是永久的。进程是一个状态变化的过程，程序可以长久保存。
③ 进程和程序的组成不同：进程包括程序，数据和进程控制块。
④ 进程和程序是密切相关的。通过多次执行，一个程序可以对应多个进程；通过调度关系，一个进程
可以包括多个程序。
⑤ 进程可以创建其他进程，但是程序不能形成新的程序。
2. 进程和线程的区别
① 调度：线程是独立调度的基本单位，进程是资源拥有的基本单位。在同一进程中，线程的切换不会
引起进程切换。在不同进程中进行线程切换，将会引起进程切换。
② 拥有资源：进程是拥有资源的基本单位，而线程不拥有系统资源（除了少量资源，比如栈，程序计
数器，寄存器），不过线程可以访问其隶属进程的系统资源。
③ 并发性：在引入线程的操作系统中，不仅进程之间可以并发执行，而且同一个进程内的多个线程之
间也可以并发执行，能提高系统的吞吐量，系统的并发性也更好。
④ 系统开销：在创建进程和撤销进程时，系统都要为之分配或回收资源，所以操作系统为进程付出的
系统开销远大于创建线程或撤销线程的开销。
⑤ 同步和通信：多线程之间的同步和通信容易实现。
3. 什么是微内核？
微内核操作系统能有效地支持多处理机运行，非常适用于分布式系统环境。
什么是微内核操作系统到现在没有一致公认的定义，但是可以从四个方面对微内核操作系统进行描述：
① 足够小的内核：在微内核操作系统中，内核是指精心设计的，能实现现代OS最基本核心功能的部
分，并非是一个完整的OS，而只是OS中最基本的部分。
② 基于C/S模式：将操作系统中最基本的部分放入内核中，而把操作系统的绝大部分功能都放于微内核
外面的一组服务器中实现。
③ 应用“极致与策略分离”原理：在传统OS中，讲极致放在OS的内核的较低层，把策略放在内核的较高
层中。而在微内核OS中，通常把机制放在OS的微内核中，这样才有可能将内核做得很小。
④ 采用面向对象技术。
基本功能：
① 进程（线程）管理
② 低级存储器管理
③ 中断和陷入处理
优点：
① 提高了系统的可扩展性
② 增强系统的可靠性
③ 可移植性
④ 提供了对分布式系统的支持
⑤ 融入了面向对象技术
4. 什么是DMA？什么是中断？两者的区别。
① 中断方式是在数据缓冲寄存器满之后发出中断，要求CPU进行，而DMA方式则是在所要求传送的数据
块全部传送结束时要求CPU 进行中断处理。这就大大减少了CPU进行中断处理的次数。
② 中断方式的数据传送是在中断处理时由CPU控制完成的，而DMA方式则是在DMA控制器的控制下，不
经过CPU控制完成的。这就排除了CPU因并行设备过多而来不及处理以及因速度不匹配而造成数据丢失
等现象。
5. 硬中断和软中断是什么？区别是什么？
软中断：
1、编程异常通常叫做软中断
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
