★ FEATURED ARTICLE 简介这份PDF面向备战杭州电子科技大学计算机考研复试的考生系统梳理数据结构、计算机组成原理、操作系统、计算机网络、数据库、编译原理与软件工程七门专业课的常见面试问答。内容以数据结构为核心覆盖关键路径与关键活动、栈与队列区别、BFS与DFS复杂度、度为2的树与二叉树差异、四种逻辑结构、Prim与Kruskal最小生成树、各类排序算法时间与空间复杂度、二叉排序树、Dijkstra与Floyd最短路径等高频考点并延伸至二叉树加密、MD5完整性验证、公交最少换乘等实际应用场景。资源包共1个PDF文件大小约1.01MB轻量便携适合碎片化查阅与考前速记。目前已有2750人学习下载可作为复试问答自测与知识点查漏补缺的参考清单。1. 杭电计算机考研复试专业课七门课的知识地图长什么样杭电计算机考研复试的专业课面试覆盖面比初试更散、更偏口头表达。这份资料把问题按数据结构、计算机组成原理、操作系统、计算机网络、数据库、编译原理、软件工程七门课拆开其中前四门给出了对应教材的页码索引后三门需要自己翻本科教材定位。梳理下来会发现它的价值不在“押题”而在于把每门课里面试官最爱追问的那批核心概念集中到了一起。适合已经过了一遍教材、需要快速建立问答反射的人也适合初试刚结束、对复试范围还没什么概念的人拿来当索引。整份资料的结构是“题目页码部分答案”页码指向的是教材里答案所在的那一页不是题号——这个设计本身就说明它默认你手边有书它负责帮你定位不负责替你理解。2. 数据结构从线性表到外部排序的问答重点2.1 逻辑结构与存储结构三要素和四种关系数据结构这门课在复试里被问得最多因为它最容易从任何一个概念延伸出一串追问。最底层的一组概念是数据结构三要素逻辑结构、存储结构、数据的运算。逻辑结构回答“元素之间是什么关系”存储结构回答“在内存里怎么放”运算回答“能对它做什么”。这三者不是并列的逻辑结构决定你能做哪些运算存储结构决定运算的效率。四种逻辑结构必须能脱口而出逻辑结构元素关系典型例子集合结构同属一个集合别无关系哈希表中的桶线性结构一对一数组、链表、栈、队列树形结构一对多二叉树、B树、哈夫曼树图状结构多对多有向图、无向图、AOV网存储结构则分顺序存储和链式存储两大类外加索引存储和散列存储。顺序存储密度大、支持随机访问但插入删除要搬元素链式存储插入删除灵活但存储密度小、不能随机访问。面试里如果被问到“为什么数组查询快”要能落到“连续内存下标计算直接得到地址”这个层面而不是只说“数组就是快”。2.2 树与图遍历方式的联系与区别树和图的遍历是高频追问区。二叉树的先序、中序、后序遍历本质上都是DFS层序遍历是BFS。树的遍历不需要visited数组因为树没有环、不会重复访问图的遍历必须要有visited标记因为图可能有环、可能不连通。树的遍历一般从根节点出发图的遍历可以从任意顶点出发。图的两种遍历要能说出完整参数# BFS使用队列适合找最短路径无权图 from collections import deque def bfs(graph, start): visited set([start]) queue deque([start]) while queue: node queue.popleft() for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) # 时间复杂度邻接表O(VE)邻接矩阵O(V^2) # 空间复杂度O(V)队列最坏存所有顶点DFS用递归或栈实现空间复杂度同样是O(V)但递归深度受栈限制。面试官常追问“BFS和DFS分别适合什么场景”——BFS适合找最短路径、遍历附近节点DFS适合判断连通性、拓扑排序、找所有路径。2.3 排序算法复杂度、稳定性与适用场景排序是数据结构里最容易出对比题的地方。面试官不会只问“快排的时间复杂度”而是会追问“哪些排序最好最坏一样”“哪些比较次数与初始序列无关”。下面这张表建议直接背下来排序算法最好平均最坏空间稳定性直接插入nn²n²1稳定冒泡nn²n²1稳定简单选择n²n²n²1不稳定希尔———1不稳定快速排序nlog₂nnlog₂nn²log₂n不稳定堆排序nlog₂nnlog₂nnlog₂n1不稳定2路归并nlog₂nnlog₂nnlog₂nn稳定基数排序————稳定几个容易在面试里翻车的追问点比较次数与初始序列无关的是二路归并、简单选择、基数排序排序趟数与初始序列有关的是冒泡和快排一趟结束后能选出一个元素到最终位置的是简单选择、快排、冒泡、堆排序。这些结论不要死记理解“为什么”才能在被追问时自圆其说。2.4 图的应用最小生成树与最短路径最小生成树两个算法的对比是必考项。Prim算法从一个顶点开始每次在已选顶点集和未选顶点集之间找权值最小的边时间复杂度O(V²)适合边稠密的图。Kruskal算法把所有边排序每次选权值最小且不构成环的边时间复杂度O(ElogE)适合边稀疏的图。面试官常问“为什么稠密图用Prim”——因为Prim的复杂度只和顶点数有关边多边少不影响它的开销。最短路径两个算法要分清Dijkstra求单源最短路径不能处理负权边Floyd求各顶点对之间的最短路径三重循环时间复杂度O(V³)。Dijkstra基于贪心策略每轮选一个dist最小的未访问顶点加入已确定集合。2.5 易漏点那些你以为会了但一追问就卡住的地方易漏点一度为2的树和二叉树的区别。很多人只记得“二叉树分左右”但面试官会追问“从度的角度看有区别吗”。度为2的树要求每个节点要么没有子节点要么有两个子节点度一定是2二叉树可以是0、1、2。补法把“二叉树可以为空、度为2的树至少有一个结点有两棵子树”这句话练到条件反射。易漏点二关键路径的适用范围。关键路径不是所有图都能求只有有向无环图DAG才有。AOE网中从源点到汇点的最长路径就是关键路径关键路径上的活动叫关键活动。补法把AOV网顶点表示活动和AOE网边表示活动的定义放在一起记面试时先确认是哪种网再回答。易漏点三B树和B树的区别。很多人只记得“B树数据都在叶子”但面试官会追问“B树的两种查找运算是什么”“为什么数据库索引用B树不用B树”。补法从“B树叶子节点包含全部关键字且有序链接”这个特性出发推导出范围查询效率高、I/O次数稳定这两个优势。易漏点四外部排序的优化手段。减少平衡归并中外存读写次数的方法、增大归并路数的方法、减少归并段个数的方法这三个问题经常被混在一起问。补法把“增大归并路数用败者树”“减少归并段个数用置换-选择排序”“组织不等长归并段用最佳归并树”这三条对应清楚。易漏点五排序算法的适用场景。直接插入、直接选择、冒泡都适合基本有序的数据快排适合无序且元素较多归并适合对象排序但辅存大基数排序适合位数多的数据但不适合负数。补法不要只背复杂度把“适合什么数据”和“不适合什么数据”成对记忆。3. 计算机组成原理从数据表示到I/O控制的硬件主线3.1 数据表示与运算补码、浮点数与校验码计组的第一条主线是“数据在机器里怎么表示”。补码是核心0的表示唯一减法可以转成加法运算器只需要加法器就能同时处理加减。溢出的三种判别方法要能说清楚——单符号位法、双符号位法、进位判断法。浮点数的IEEE754格式是高频考点要能说出符号位、阶码、尾数各占多少位以及规格化的目的。校验码三种奇偶校验、海明校验、CRC校验。面试官常问“海明码的检错纠错能力”——2位检错、1位纠错需要满足2^k ≥ nk1。3.2 存储系统Cache、虚拟存储器与多级结构存储系统的核心是“速度、容量、成本的平衡”。Cache解决CPU和主存的速度差虚拟存储器解决主存和辅存的容量差。Cache的三种映射方式——直接映射、全相联映射、组相联映射——要能画出地址划分。替换算法有FIFO、LRU、LFU、随机写策略有写回法和写直达法。虚拟存储器和Cache的比较是经典对比题两者都利用了局部性原理但Cache对程序员透明、由硬件实现虚拟存储器对应用程序员透明、由OS和硬件共同实现。3.3 指令系统与CPU寻址方式、流水线与控制器指令格式和寻址方式是基础。数据寻址方式有立即寻址、直接寻址、间接寻址、寄存器寻址、寄存器间接寻址、基址寻址、变址寻址、相对寻址等要能说出每种的有效地址怎么算。流水线是重点影响流水线的因素有三类——结构相关、数据相关、控制相关。性能指标包括吞吐率、加速比、效率。超标量流水线每个时钟周期发射多条指令超流水线提高时钟频率。硬布线控制器和微程序控制器的对比硬布线速度快但修改困难微程序速度慢但灵活、易修改。面试官常问“哪种容易变更”——微程序因为改微指令只需要改控制存储器内容。3.4 总线与I/O四种控制方式与DMAI/O控制方式四种程序查询、程序中断、DMA、通道。程序查询方式CPU利用率最低DMA方式数据传送不经过CPU、由DMA控制器直接控制总线。中断处理过程中断隐指令不是指令是硬件自动完成的动作。多重中断要能说出中断屏蔽字的作用。3.5 易错点那些容易混淆的硬件概念易错点一串行和并行的速度关系。很多人还停留在“并行一定比串行快”的旧认知里。实际上随着时钟频率提高并行导线间干扰严重高速传输反而采用串行方式。补法把“串行总线USB、SATA并行总线ISA、EISA、PCI、AGP”这组例子和“为什么高速传输用串行”的原因绑在一起记。易错点二中断和异常的区别。中断是外部事件引起异常是内部事件引起。中断隐指令不是指令是硬件在中断响应周期自动完成的操作。补法把“中断向量”“中断隐指令”“中断处理过程”三个概念串成一条线。易错点三DMA和中断的区别。DMA在数据传送阶段不需要CPU干预中断方式每条指令执行完都要检查。DMA的传送方式有停止CPU访问、周期挪用、交替访问三种。补法从“谁在控制数据传输”这个角度区分。易错点四大端和小端的区别。大端方式高位字节存放在低地址小端方式低位字节存放在低地址。边界对齐是为了提高访存效率。补法用一个具体数字比如0x12345678在两种方式下的内存布局来验证。易错点五Cache写策略的选择。写直达法每次写都更新主存写回法只在替换时才写回主存。写回法需要脏位标记。补法把“写直达适合什么场景、写回适合什么场景”和“多核CPU中Cache一致性问题”联系起来。4. 操作系统进程、内存、文件与I/O的四大模块4.1 进程与线程状态、通信与调度操作系统的第一条主线是进程管理。进程的基本状态有就绪、运行、阻塞三种加上创建和终止共五种。PCB包含进程标识符、状态、程序计数器、寄存器、内存指针、优先级、资源清单等信息。线程和进程的比较要从“拥有资源”和“调度单位”两个角度说进程是资源分配的基本单位线程是调度的基本单位。进程通信三种方式共享存储、消息传递、管道通信。调度算法要能说出FCFS、SJF、HRRN、时间片轮转、多级反馈队列的特点和适用场景。4.2 同步与互斥P、V操作与管程临界资源一次只允许一个进程使用。同步是协作关系互斥是竞争关系。P操作申请资源、V操作释放资源。用P、V操作实现互斥时信号量初值为1实现同步时信号量初值根据资源数量确定。管程是一种高级同步机制把共享变量和对它的操作封装在一起同一时刻只有一个进程在管程内执行。4.3 内存管理分页、分段与虚拟内存连续分配管理方式有单一连续分配、固定分区分配、动态分区分配。动态分区分配的四种策略首次适应、最佳适应、最坏适应、邻近适应。非连续分配的核心是分页和分段。分页对用户透明、页面大小固定分段对用户可见、段长可变。段页式是两者的结合。地址转换过程中分页需要查页表引入快表TLB后可以减少访存次数。虚拟内存的三个特征多次性、对换性、虚拟性。页面置换算法有OPT、FIFO、LRU、CLOCK。Belady异常只有FIFO会出现。4.4 文件管理与磁盘调度文件的逻辑结构有顺序文件、索引文件、索引顺序文件。目录结构有多级目录。索引节点inode存放文件的元数据目的是加快文件检索。文件分配方式连续分配、链接分配隐式、显式FAT、索引分配普通、链接、多层索引、混合索引。磁盘调度算法FCFS、SSTF、SCAN、LOOK、C-SCAN、C-LOOK。减少延迟的方法有交替编号、错位命名、合理的磁盘地址结构设计。4.5 易漏点那些在面试里容易答偏的操作系统问题易漏点一外设编址方式。外设单独编址和外设统一编址的区别经常被问到。单独编址时I/O地址可以和内存地址重叠需要标志位区分统一编址时I/O端口占据部分主存地址空间。补法从“访问时怎么区分是内存还是端口”这个角度记忆。易漏点二进程和线程的“为什么”。面试官不只问“有什么区别”还会问“为什么要有进程”“为什么要有线程”。补法从“并发执行需要保存现场”推导出进程从“进程切换开销大”推导出线程。易漏点三死锁的四个必要条件。互斥、不可剥夺、请求并保持、循环等待。死锁预防是破坏这四个条件之一死锁避免是银行家算法死锁检测是资源分配图化简。补法把“预防、避免、检测、解除”四个策略和对应的具体方法对应清楚。易漏点四分页和分段的访存次数。基本分页存储访问一个数据需要两次访存查页表访问数据引入快表后可能只需一次。多级页表会增加访存次数。补法画一个地址转换的流程图把每一步的访存次数标出来。易漏点五抖动现象和工作集。抖动是页面频繁换入换出导致CPU利用率下降。工作集是进程在某段时间内实际访问的页面集合。补法把“驻留集”“工作集”“抖动”三个概念串起来理解。5. 计算机网络从物理层到应用层的协议栈5.1 分层模型与地址体系OSI七层模型和TCP/IP四层模型的对应关系是基础。OSI有物理层、数据链路层、网络层、传输层、会话层、表示层、应用层TCP/IP有网络接口层、网际层、传输层、应用层。五层模型是教学用的折中方案。各层的地址物理层用MAC地址48位网络层用IP地址32位传输层用端口号16位。MAC地址烧录在网卡上IP地址基于网络拓扑分配。IP转MAC用ARPMAC转IP用RARP。5.2 数据链路层与网络层数据链路层的可靠传输机制有停止-等待、后退N帧GBN、选择重传SR。介质访问控制分三类信道划分频分、时分、波分、码分、随机访问ALOHA、CSMA、CSMA/CD、CSMA/CA、轮询访问令牌传递。网络层的核心协议IP、ARP、DHCP、ICMP。IP数据报分片涉及标识、标志、片偏移三个字段。子网掩码和CIDR用于划分子网。NAT用于地址转换。路由协议RIP基于距离矢量算法OSPF基于链路状态算法BGP用于自治系统之间。RIP认为“跳数少的路由好”OSPF认为“带宽高的路由好”。5.3 传输层与应用层TCP和UDP的区别是必考项。TCP面向连接、可靠、有流量控制和拥塞控制UDP无连接、不可靠、开销小。TCP三次握手和四次挥手的过程要能画出来。流量控制是端到端的拥塞控制是全局的。应用层协议HTTP、DNS、FTP、SMTP、POP3。常用端口号HTTP 80、HTTPS 443、DNS 53、FTP 21、SMTP 25、POP3 110。5.4 易错点那些容易记混的网络概念易错点一CSMA/CD和CSMA/CA的区别。CSMA/CD用于有线以太网检测碰撞CSMA/CA用于无线局域网避免碰撞。补法从“有线可以检测、无线难以检测”这个物理原因出发记忆。易错点二IPv4和IPv6的区别。地址长度32位 vs 128位表示方法十进制 vs 十六进制分片由路由器和主机 vs 仅由发送主机ARP vs NDP。补法把四个区别做成对比表。易错点三流量控制和拥塞控制的区别。流量控制解决发送方和接收方速度不匹配拥塞控制解决网络中的资源不足。补法从“谁和谁之间的协调”这个角度区分。易错点四局域网和广域网的协议。局域网用TCP/IP或IPX/SPX广域网用PPP或HDLC。补法把“局域网三要素”传输介质、拓扑结构、介质访问控制方式和广域网协议分开记。易错点五路由协议的分类。RIP和OSPF是内部网关协议IGPBGP是外部网关协议EGP。补法从“自治系统内部还是之间”这个角度区分。6. 复习清单从查漏补缺到面试口述的落地方法这份资料的使用方式梳理下来可以分成三步。第一步是定位拿到题目后先看有没有页码有页码的翻到对应教材页把答案用自己的话复述一遍没有页码的数据库、编译原理、软件工程部分按题目关键词去本科教材目录里找对应章节。第二步是串联把同一门课里相关的题目放在一起看比如数据结构的排序算法题有十几道集中过一遍比分散看效率高得多。第三步是口述面试和笔试最大的区别是你需要在没有纸笔的情况下把思路讲清楚所以每道题都要练到能对着空气说出一段完整的话。下面是我自己用的查漏补缺清单按“能不能口述”而不是“有没有看过”来标记检查项标准不达标怎么办复杂度脱口而出排序、图遍历、查找的复杂度能直接说回到第2章表格重背对比题能分点树vs图、进程vs线程、TCP vs UDP能说3点以上每对概念写3条差异算法步骤能画Prim、Kruskal、Dijkstra能画出执行过程手动画一遍协议层次能对应各层设备、协议、地址能对应画一张分层表易错点能识别看到题目知道面试官想考什么重读各章易漏点最后说一个血泪经验不要等到面试前一天才开始练口述。我见过太多人笔试能写出来但一开口就卡壳因为“心里知道”和“嘴上说清楚”是两回事。从那以后我每次复习完一个模块都强制自己合上书用手机录音讲一遍回放时专门听哪里卡了、哪里说错了。这个习惯看起来笨但比反复看书有效得多。希望帮到你。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
