>>>计算机408考研真题及解析，点击立即领取！<<<

 

　　随着计算机科学的快速发展，计算机408考研已成为越来越多考生追求的目标。在考前冲刺阶段，掌握必备知识点是提高考试成绩的关键。本文将为大家点拨10个必备知识点，帮助大家更好地备考。

加小助手微信（备注vip）：jcxz666xj，领取PDF版招生简章及考情分析和历年考研真题解析，进备考答疑微信群。

 

 

　　1.数据结构算法题的三种思路：

 

　　（1）遍历，主要解决树和图类算法

 

　　2014年第41题：带树高的遍历 + 收集叶节点的带权路径长度。

 

　　2017年第41题：中序遍历 + 括号。

 

　　2021年第41题：遍历邻接矩阵，统计度为奇数的顶点个数。

 

　　2022年第41题：中序遍历，判断是否升序。

 

　　2023年第41题：遍历邻接矩阵，统计每个顶点的出度和入度。

 

　　（2）双指针法

 

　　2009年第42题：定义两个指针p、q，p指针先走k步然后p、q同时走，直至p指向空，此时q指向倒数第k个结点（要判断k是否小于等于链表的长度）。

 

　　2011年第42题：折半查找（双指针，一左一右）：比较两个序列的中位数midA和midB。

 

　　2012年第42题：str1和str2为分别指向两个链表的头指针，假设一个链表比另一个链表长k个结点，我们先在长链表上遍历k个结点，之后同步遍历两个链表，这样就能够保证它们同时到达最后一个结点。

 

　　2019年第41题：快慢指针，快指针一次走两步，慢指针一次走一步，当快指针指向链尾时，慢指针指向中间结点。将L后半段原地逆置。从链表前后两段各取一个结点重排。

 

　　（3）辅助空间法

 

　　2010年第42题：法一：创建大小为p的辅助数组S，将R中前p个数依次暂存在S中，同时将R中后n-p个整数左移，然后将S中暂存的p个数依次放回到R中的后续单元。法二：数组翻转。

 

　　2013年第41题：法一：开辟一个大小为n的数组count，用于统计每个数出现的次数。法二：Boyer-Moore投票算法。

 

　　2015年第41题：使用辅助数组记录链表中已出现的数值。

 

　　2018年第41题：法一：分配一个标记数组B[n]，用来记录数组中是否出现了1~n中的正整数。法二：将数组本身改造成标记数组。法三：置换。

 

　　2022年第42题：定义一个含10个元素的数组或大根堆用于保存最后的结果。

 

　　2.排序算法的性质

 

　　3.红黑树

 

　　（1）红黑树的性质

 

　　节点不是黑色，就是红色（非黑即红）。

 

　　根节点为黑色。

 

　　叶节点（虚构的外部结点、NULL结点）为黑色。

 

　　一个节点为红色，则其两个子节点必须是黑色的（根到叶子的所有路径，不可能存在两个连续的红色节点）。

 

　　从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点，且

 

　　将从某节点（不包含该节点）到叶子的任意一条路径上黑色节点的个数称为该节点的黑高。

 

　　（2）红黑树的定理

 

　　从根到叶节点的最长路径不大于最短路径的2倍。

 

　　有n个内部结点的红黑树的高度h≤2log2(n+1)。

 

　　4.中断处理过程

 

　　（1）关中断

 

　　进入不可再次响应中断的状态，由硬件自动实现。在保存现场过程中，即使有更高级的中断源申请中断，CPU也不应该响应。否则，如果现场保存不完整，在中断服务程序结束之后，也就不能正确地恢复现场并继续执行现行程序。

 

　　（2）保存断点和现场

 

　　现场信息一般指的是程序状态字，中断屏蔽寄存器和CPU中某些寄存器的内容。

 

　　（3）判别中断源，转向中断服务程序。

 

　　在多个中断源同时请求中断的情况下。本次实际响应的只能是优先权最高的那个中断源，所以需进一步判别中断源，并转入相应的中断服务程序入口。

 

　　（4）开中断。

 

　　接下去就要执行中断服务程序，开中断将允许更高级中断请求得到响应。实现中断嵌套。

 

　　（5）执行中断服务程序。

 

　　（6）退出中断。

 

　　在退出时，又应进入不可中断状态，即关中断，恢复现场、恢复断点，然后开中断，返回原程序执行。

 

　　进入中断时执行的关中断、保存断点等操作一般是由硬件实现的，它类似于一条指令，但它与一般的指令不同，不能被编写在程序中。因此，常常称为‘中断隐指令’。

 

　　5.数据的寻址方式

 

　　6.常用汇编指令

 

　　7.操作系统中的各类算法

 

　　（1）处理机调度算法

 

　　先来先服务（FCFS）

 

　　短作业优先（SJF）

 

　　优先级调度算法

 

　　高响应比优先

 

　　时间片轮转

 

　　多级队列

 

　　多级反馈队列

 

　　（2）页面置换算法

 

　　最佳（OPT）置换算法

 

　　先进先出（FIFO）页面置换算法

 

　　最近最久未使用（LRU）置换算法

 

　　时钟（CLOCK）置换算法

 

　　（3）磁盘调度算法

 

　　先来先服务（First Come First Served, FCFS）算法

 

　　最短寻找时间优先（Shortest Seek Time First, SSTF）算法

 

　　扫描（SCAN）算法（又称电梯调度算法

 

　　循环扫描（Circular SCAN, C-SCAN）算法

 

　　8.经典同步问题

 

　　（1）生产者-消费者问题

 

　　（2）读写者问题

 

　　一位读者，一位写者

 

　　多位读者

 

　　（3）哲学家进餐问题

 

　　9.三次握手和四次挥手

 

　　（1）三次握手连接

 

　　（2）四次挥手释放

 

　　10.拥塞控制

 

 

　本文内容整理于网络，由玊尔编辑，如有侵权请联系（3023557942）删除文章。

 

　　推荐阅读：各大院校2024考研硕士研究生招生简章汇总

　　　　　　　2023考研各大院校硕士研究生拟录取名单汇总

　　　　　　　热门院校2023年考研复试分数线汇总

 

真题/大纲/更多考研备考资料

扫码直接领取（无套路）