【北交大906】计算机专业基础考试注意事项

北交大906计算机专业基础考试需从数据结构算法、操作系统计算题两大核心板块把握注意事项，涵盖知识理解、题型应对及细节处理等方面。 具体如下：

• 线性表

  链表结点增加：通常以填空或选择题形式出现，要清晰掌握链表结点增加的操作步骤，比如是在头部、尾部还是中间位置增加结点，以及指针的修改方向等。例如在头部增加结点，需要先创建一个新结点，将新结点的指针指向原链表的头结点，然后更新头指针指向新结点。

  一元多项式相加：属于代码填空题，要理解一元多项式的存储结构，一般采用链表存储。相加时需要遍历两个链表，根据指数的大小关系进行合并操作，注意处理系数相加为0的情况。

• 栈和队列

  数制转换：作为代码填空题，要明白数制转换的原理是利用栈的先进后出特性。例如将十进制数转换为二进制数，通过不断除以2取余数，将余数依次入栈，最后依次出栈得到二进制数。

  循环队列判空判满：以填空或选择题形式考查，要清楚循环队列判空和判满的条件。判空一般是队头指针等于队尾指针；判满有多种方式，如牺牲一个存储单元，当（队尾指针 + 1）% 队列长度等于队头指针时为满。

• 矩阵

  快速转置：属于算法设计题，要掌握快速转置算法的原理和步骤。该算法主要是通过记录原矩阵中非零元素的行和列信息，来快速得到转置后矩阵的非零元素位置，减少遍历次数，提高效率。

• 树

  二叉树创建，遍历：为算法说明题，要理解二叉树的创建方式，如通过先序、中序或后序遍历序列结合递归或非递归方法创建。对于遍历，要熟练掌握先序、中序、后序遍历以及层次遍历的算法流程和特点，能够清晰说明每种遍历的步骤和结果。缺晌

• 图

  图创建，遍历：作为算法说明题，要了解图的多种存储结构，如邻接矩阵、邻接表等，以及根据不同的存储结构进行图的创建。图的遍历包括深度优先遍历和广度优先遍历，要掌握它们的算法思想和实现过程，能够说明遍历的顺序和特点。

  普利姆算法：属于算法设计题，普利姆算法是用于求解最小生成树的算法。要理解其从某个顶点开始，逐步选择与已选顶点集合相连的权值最小的边，将伏枣锋对应的顶点加入集合，直到所有顶点都被包含在内，形成最小生成树的过程。

• 排序

  插入排序：作为算法填空题，要掌握插入排序的基本思想，即将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。要清楚插入排序的代码实现中关键步骤的填空内容，如比较和移动元素的操作。

  希尔排序：同样是算法填空题，希尔排序是插入排序的一种更高效的改进版本，也称为缩小增量排序。要理解其通过将原始列表分成若干子列表，对每个子列表进行插入排序，然后逐步缩小子列表的间隔，最终对整个列表进行插入排序的过程，掌握关键代码的填空。

  快速排序：属于算法设计题，快速排序采用分治的思想，通过选择一个基准元素，将数组分为两部分，使得左边部分的元素都小于等于基准元素，右边部分的元素都大于等于基准元素，然后对左右两部分递归地进行快速排序。要能够完整设计出快速排序的算法代码。

  堆排序：作为算法设计题，堆排序是利用堆这种数据结构来进行排序的。要先将数组构建成一个最大堆（或最小堆），然后将堆顶元素与堆的最后一个元素交换，再对剩余的元素重新构建堆，重复这个过程直到所有元素都有序。要掌握堆排序的算法设计和实现。

• 处理机管理

  典型的几种调度算法以及优缺点是计算题必考内容，包括先来先服务（FCFS）调度算法、短作业优先（SJF）调度算法、优先级调度算法、高响应比优先调度算法、时间片轮转调度算法、多级反馈队列调度算法。要理解每种算法的调度原则和计算方法，例如FCFS算法按照作业到达的先后顺序进行调度，计算平均周转时间等指标时，按照顺序依次计算每个作业的等待时间、运行时间和周转时间，然后求平均值。

• 同步通信及死锁处理

  银行家算法：是重点内容，要掌握银行家算法的原理和计算步骤，通过给定的系统资源分配情况、进程的最大需求和已分配资源等信息，判断系统是否处于安全状态，以及能否为某个进程分配资源。岩漏

  死锁定理：虽然只考过一次，但也要了解其概念和应用，死锁定理用于判断系统是否处于死锁状态，通过对资源分配图进行化简来判断是否存在死锁。

• 储存管理

  非连续分配管理方式：包括基本分页管理方式、基本分段管理方式、段页式管理方式，是重点和难点。要理解逻辑地址到物理地址的变换过程，例如在基本分页管理方式中，通过页表将逻辑地址中的页号转换为物理块号，再加上页内偏移量得到物理地址。

  虚拟内存的三种实现方式：如虚拟分页、请求分页管理方式中的页表项，要掌握其原理和特点。

  页面置换的几种算法及其优缺点：要会画置换图和计算缺页率，例如先进先出（FIFO）页面置换算法、最近最少使用（LRU）页面置换算法等，通过模拟页面置换的过程，记录缺页次数，计算缺页率。

• 文件管理

  文件分配方式：熟悉几种方式的原理，如FAT表、混合索引方式，这是计算题难点。要理解不同文件分配方式下文件的存储结构和空间分配方法，以及如何根据给定的信息进行计算。

  文件存储空间管理：成组链接法是重点，要掌握成组链接法的原理和操作过程，能够根据题目要求进行相关的计算。

  磁盘调度算法和寻道时间、延迟时间、传输时间：要了解不同磁盘调度算法（如先来先服务、最短寻道时间优先等）的特点和计算方法，能够计算磁盘调度的寻道时间、延迟时间和传输时间等指标。

• 多读题目，注意细节：在考试过程中，要认真阅读题目，理解题目的要求和条件，注意细节，避免因为粗心大意而丢分。
• 内存外存多理解：对于操作系统中内存和外存的相关知识，要深入理解其原理和管理方式，这有助于更好地解答计算题和算法设计题。
• 看看书：在考试前，要对教材进行全面复习，巩固知识点，加深对重点和难点内容的理解。