保研笔试复习——nju_计算机保研笔试题

免责声明：题目源自于网络，侵删。

就在今天2024-5-18，考的题下面的只有一道AVL的原题，其他都不是原题，然后操作系统并没有那么难的概念，考了很多编译原理，也考了离散（群和格，两三道吧）。

建议：先把数据结构算法的题会的做了，分值一样，但至少这些是会一点的，然后做其他的，编译原理是真的不会，其他也不太会（忘完了），基本上能做的是数据结构算法。

考得最多的估计是数据结构算法，编译原理，计网，操作系统这些，离散考的少，计组也少。没记错的话单选题40道，多选题35道。（单选也可能是35道，记不得了）

一、单选

计算机网络

分析和知识点复习：

传输层的拥塞控制：AIMD(加法增加，乘法减小）

• 慢启动阈值ssthresh，无论是超时还是收到三个重复确认，都是变为当前拥塞窗口cwnd的一半。
  • 慢启动：拥塞窗口小于ssthresh时，每次拥塞窗口翻倍增加，直到达到ssthresh
  • 拥塞避免 ：当达到ssthresh时，每次增加1
• 若是超时，则直接从拥塞窗口cwnd=1，慢启动开始，
• 若是收到三个重复确认，则拥塞窗口cwnd从乘法减小后的ssthresh开始。（快重传，此时收到三个重复确认，直接将重复确认的报文段重发，并且采用快速恢复算法，即cwnd=ssthresh）。

答案：
本题超时：16->1->2->4->8（若是超时，则直接从拥塞窗口cwnd=1，慢启动开始，）
甲是发送端：应该是服务器发送网页资源给客户端，因此甲是服务器。

• 所以选D

计算机网络：传输层

---

答案：
同一个网络号的IP地址组成一个“CIDR块”。
A. 120.128.1.100/24

• 这个CIDR块的掩码/24比所给的掩码/16更具体，所以这不是最佳选择。

B. 120.128.1.0/24

• 同上，掩码/24比需要的掩码/16更小。

C. 120.128.1.100/16

• 这个网络从120.128.0.0扩展到120.128.255.255，确实包括120.128.1.100，并与子网掩码255.255.0.0匹配。

D. 120.128.0.0/16

• 这个CIDR块也从120.128.0.0扩展到120.128.255.255，包括120.128.1.100，且与子网掩码255.255.0.0完美匹配。

正确答案是 D. 120.128.0.0/16，因为它提供了从120.128.0.0到120.128.255.255的正确网络地址，与子网掩码255.255.0.0完全对应。

---

分析
在无线局域网中，如IEEE 802.11标准，调整优先级的一种有效方法是通过改变帧间隔（Frame Spacing），尤其是在处理媒体访问控制（MAC）层时。帧间隔的调整可以通过以下几种方式进行：

1. 帧间间隔类型

• Distributed Inter-Frame Space (DIFS)：用于常规数据帧的发送前等待时间。
• Arbitration Inter-Frame Space (AIFS)：用于支持服务质量（QoS）的改进版本，基于802.11e标凈，允许不同的优先级设置。AIFS被设计来替代或修改DIFS，使得高优先级的流量可以有更短的等待时间。

2. 调整AIFS

AIFS的设置可以根据数据的优先级不同而不同。在802.11e标准中，AIFS的长度是动态可调的，通常表达为：
$\text{AIFS}=\text{AIFSN}\times \text{时间槽}+\text{SIFS}$
其中AIFSN（Arbitration Inter-Frame Space Number）是根据数据流的优先级设置的一个因子，时间槽（Slot Time）是传输介质上两次传输之间的时间间隔，SIFS（Short Inter-Frame Space）是最短帧间间隔，用于确认帧和清空帧的快速回复。

• 高优先级的流量：如实时视频或VoIP通话，会被分配较低的AIFSN值，因此计算出的AIFS更短，这意味着这类流量在遭遇拥堵时能更快地获得传输机会。
• 低优先级的流量：如背景数据下载，会被分配较高的AIFSN值，从而有更长的AIFS，使得在网络拥塞时其等待时间更长。

答案：
选C。如果不知道使用排除法，不同长度数据包，确认包只能说明数据内容多少不一样，但是数据流的优先级不能确定，冲突避免时间是整个局域网中相同的对优先级没啥用，因此选C。

---

计算机组成原理

分析：

• $时钟周期=\frac{1}{时钟频率}$
• 线宽：表示同一时间能传送的数据大小
• 在时钟的每个上升沿和下降沿传输数据，这意味着每个时钟周期可以传输两次数据。（猜都可以猜出来题意的）
• 一个字节=8bit
• KB,MB,GB
  答案：
  $时钟周期时间T=\frac{1}{f}=\frac{1}{800MHZ}=\frac{1}{8\times 10^{8}HZ}=1.25\times 10^{-9}s$
  $一秒的时钟周期数量C=\frac{1}{T}=8\times 10^8$
  $一秒的最大数据量=一秒的时钟周期数量\times 线宽\times 2=8\times 10^8\times 64\times 2bit=1.024\times 10^{11}bit=1.28\times 10^{10}B=12.8GB$
• 所以选12.8GB

---

数字逻辑电路

模拟题：

分析：
由于是选择题本题要求能看出答案是否满足要求，因此只要能看出答案是否满足要求即可，不需要自己设计。

• 与，或，非，异或
• 异或：参与运算的对应位相同为0，不同为1
  模拟题答案：

1. 根据给定的输入，使用逻辑表达式计算 $Z(i)$：
   $Z(i)=1\oplus 0\oplus (1\cdot 1)=1\oplus 0\oplus 1=0$
2. $Z(i)$的输出受到所有输入的影响。$A(i)$ 和 $B(i)$ 直接通过异或运算相互影响，而$C(i)$和$D(i)$的影响则通过与运算后的结果参与到最终的异或运算中。当$C(i)$ 和 $D(i)$两者均为1时，它们的输出将改变$Z(i)$的最终值。
3. 设计 $Z^{\prime }(i)$ 如下：
   $Z^{\prime }(i)=(C(i)\cdot D(i))\vee ((C(i)\cdot D(i){)}^{\prime }\cdot (A(i)\oplus B(i)))$

---

数据结构

分析：
既然没有100，也没有其他信息，那就选个质数吧~

选择 97（一个质数）作为模数 $P$ 有助于散列函数 $H(k)=k\%P$ 产生均匀分布的散列值，减少散列冲突，并提高散列表的整体性能和效率。这种方法确保了输入值 $k$在散列过程中的随机性和均匀性，降低了因为数学特性（如因数分解）导致的预测性和冲突问题。

答案：

• 选C，其他选项都能看出来不是质数，C经过验证确实是质数。

---

分析：

• 二叉搜索树：对于任意节点，其左子树的所有节点的值小于该节点的值，其右子树的所有节点的值大于等于该节点的值。因此不一定有序
• 哈夫曼树：按照出现频率排的，根关键码没啥关系
• 堆：优先队列，堆排序，对于任何结点，它作为根的子树，其儿子都小于等于 或 大于等于它。
• 完全二叉树：只是树的形状被规定了

答案：

• 选C

---

分析：

• $A[i][j]=1$表示顶点$i$有一条边指向$j$。

因此求顶点$i$的入度，就看有多少条边指向$i$，因此${\sum }_k^{n}A[k][i]$
答案：

• 选B

---

AVL：
AVL树：高度平衡树：每个节点的左子树和右子树的高度最多相差1。这种高度上的平衡称为“平衡因子”，平衡因子是节点的左子树高度减去右子树高度（有时相反）。每个节点的平衡因子只能是 -1, 0, 或 +1。

• 插入方式：AVL树是二叉查找树，故可使用二叉查找树的插入方法插入结点，但插入一个新结点后，有可能破坏AVL树的平衡性
  • 如果发生这种情况，就需在插入结点后对平衡树进行调整，恢复平衡的性质。实现这种调整的操作称为“旋转”。
  • 我们只需要看最上面失去平衡的结点及其以下的两个结点共三个结点即可。

    • 单旋
      

    • 双旋
      

分析：
要解决这个问题，我们需要先插入关键码 2、4、6、8 和 10 到一个初始为空的 AVL 树中，并观察插入后每个节点的平衡因子。

1. 插入 2:

   • 树现状：2
   • 平衡因子：0（无左右子树）

2. 插入 4:

   • 直接插入为2的右子节点。
   • 树现状：

       2
        \
         4
     1
     2
     3

   • 平衡因子：2 的平衡因子为 -1（右子树高度1，无左子树），4 的平衡因子为 0。

3. 插入 6:

   • 插入后，将会触发 AVL 树的平衡操作，因为插入6在4的右子节点会导致从2开始的路径不平衡（2, 4, 6 路径）。
   • 应用右旋（RR旋转）于节点2，然后节点4成为新的根。
   • 树现状：

       4
      / \
     2   6
     1
     2
     3

   • 平衡因子：所有节点的平衡因子均为 0。

4. 插入 8:

   • 插入8到节点6的右子节点。
   • 树现状：

       4
      / \
     2   6
          \
           8
     1
     2
     3
     4
     5

   • 平衡因子：4 的平衡因子为 -1，2 的平衡因子为 0，6 的平衡因子为 -1，8 的平衡因子为 0。

5. 插入 10:

   • 插入10到节点8的右子节点，这将导致从4到8的路径（4, 6, 8, 10）不平衡。
   • 应用右旋（RR旋转）于节点6，然后节点8成为新的根。
   • 树现状：

       4
      / \
     2   8
        / \
       6  10
     1
     2
     3
     4
     5

   • 平衡因子：4 的平衡因子为 -1，2 和 10 的平衡因子均为 0，8 的平衡因子为 0，6 的平衡因子为 0。

在最终的 AVL 树中，节点2、6、10和8的平衡因子都为 0。

但是分支结点必须是有儿子的结点，因此满足题意的只有结点8。
数据结构基础知识。

答案：

• 答案选B

---

分析：
沿着选项给出的边集走就行，能走完的就是答案。
答案：

• 选A

---

if(x < ptr->data){
	return Search(x,ptr->left);//在左子树里面查找
}else if(x > ptr->data){
	return Search(x,ptr->right);
}else
	return ptr;//x既不大于，也不小于，就是等于ptr->data == x
1
2
3
4
5
6

---

操作系统

知识：

  加载器将可执行目标文件中的代码和数据从磁盘复制到内存中，然后通过跳转到程序的第一条指令或入口点来运行该程序。这个将程序复制到内存并运行的过程叫做加载。加载器是驻留在存储器中的操作系统代码。
  任何Linux程序都可以通过系统调用execve函数来调用加载器。


execve的执行过程：

• shell（或其他父进程）运行一个程序时，会先调用fork，创建一个一模一样的子进程副本。
• 这个子进程副本调用execve系统调用加载和执行一个新的程序。
  • execve系统调用开始会先调用加载器（也就是题目说的第一条指令是加载器的入口地址，也就是调用加载器）加载器先将该子进程的虚拟内存（如堆栈、代码数据等）都清空，然后将该虚拟地址空间映射到需要调用的程序磁盘页上，方便之后执行程序。（这里在执行程序时才会将使用的页真正调入内存中（虚拟地址空间已经指向了，只是发生缺页中断。））

17.分析：
在 Linux 中使用 execve 系统调用加载并执行一个动态链接的 ELF（Executable and Linkable Format）二进制文件时，执行流程是比较复杂的。它涉及到不仅仅是程序代码的直接执行，还包括多个阶段的准备工作。具体到该问题，我们要确定执行 execve 后执行的第一条指令位于哪里。以下是每个选项的解析：

• A. ELF文件头：这不是指令的位置，而是文件的元数据信息，如魔数、版本号、入口点地址等。
• B. ELF文件指定的入口地址：这通常指向程序的起始代码，但对于动态链接的程序，这通常是动态链接器的一部分，而不是程序本身的 main 函数。
• C. libc的初始化代码：在动态链接的程序中，libc 的初始化代码会在程序的主体执行之前运行，但这不是 execve 后执行的第一条指令。
• D. main函数的第一条指令：这是程序逻辑开始的地方，但不是 execve 后立即执行的第一条指令，因为需要先进行一系列的初始化和设置步骤。
• E. 加载器的入口地址：对于动态链接的 ELF 文件，execve 后执行的第一条指令实际上位于动态链接器（如 Linux 的 /lib/ld-linux.so.2）中。这是因为动态链接器负责加载所有必要的共享库，并进行符号解析和重定位，然后才会跳转到程序的实际入口点。
• F. 堆栈上生成的代码：这不是 execve 执行后的第一条指令的典型位置。

17.答案：
根据这些信息，正确的答案是 E。加载器的入口地址是 execve 调用后执行的第一条指令的位置，因为动态链接器首先介入，处理必要的库加载和准备工作，然后将控制权转交给程序本身的入口点。这个过程是必要的，以确保所有的库依赖和符号都正确解析，使程序能够正确运行。
6.答案：
需要注意的是函数中的filename可以使用。绝对路径也可以使用相对路径
根据函数容易知道，参数有path、args、Envp。

---

---

分析：
A. 互斥锁

• 互斥锁提供了一种基本的互斥机制，允许一个线程在同一时间内独占对资源的访问。如果一个线程已经锁定了互斥锁，其他任何试图开始临界区的线程都必须阻塞等待直到互斥锁被释放。
• 缺点是如果持锁时间过长，会导致其他线程长时间等待，增加响应时间。

B. 自旋锁

• 自旋锁对于保护非常短的代码段（如只有几条指令的临界区）是非常有效的。线程在获取锁之前会进行忙等（busy-wait），不断检查锁的状态，这避免了线程在等待期间的上下文切换开销。
• 自旋锁特别适用于多处理器系统，其中线程可以真正并行运行在不同的处理器上。

C. 信号量

• 信号量是一个更复杂的同步机制，可以控制对临界区的访问，允许多个线程根据信号量的计数同时进入临界区。
• 信号量通常用于控制资源的有限访问数量，而不是保护短临界区。

D. 条件变量

• 条件变量通常与互斥锁一起使用，用于线程之间的协调，当某种状态改变时通知其他线程。条件变量本身并不用于保护数据结构。

E. 管程

• 管程是一个将数据结构和操作该数据结构的操作封装起来的高级同步机制。管程内的所有操作都是原子的，管程自身处理所有的锁定和解锁。
• 管程适用于更复杂的同步需求，不一定适合延迟敏感的简短临界区。

F. Peterson算法

• Peterson算法是一种软件同步算法，适用于两个线程的互斥。它不适合多处理器系统或实际的多线程环境中使用。

答案：
自旋锁 (B)

---

微机系统

分析：
在x86和x86-64体系结构中，当发生页面错误（Page Fault）时，引起该错误的虚拟地址会被保存在特定的寄存器中。对于这种情况，正确的选项是 E. CR2寄存器。

以下是每个选项的具体解释和分析：

A. TSS (Task State Segment)

• TSS（任务状态段）用于存储任务执行时机器状态，包括栈指针和程序计数器等，但不用于存储引发页面错误的虚拟地址。

B. 内核栈

• 内核栈用于处理内核级的函数调用和异常处理，但不直接用于存储引发页面错误的虚拟地址。

C. 用户栈

• 用户栈是为应用程序代码执行而保留的栈空间，同样，它不用于存储页面错误的虚拟地址。

D. CR1寄存器

• 在x86体系结构中，并没有使用名为CR1的控制寄存器。这是一个不存在的寄存器。

E. CR2寄存器

• CR2寄存器正是用于存储发生页面错误时的虚拟地址。当CPU检测到一个访问违规或者无法翻译的虚拟地址时，该地址就会被立即保存到CR2寄存器中。

F. CR3寄存器

• CR3寄存器包含当前使用的页目录基址寄存器（Page Directory Base Register，PDBR）。这是物理内存中页目录的基地址，用于页面翻译过程中的内存管理，而不是用来存储引起页面错误的虚拟地址。

答案：
E.CR2

---

分析：
A. 设备驱动程序必然对应连接在外部总线上的I/O设备

• 错误。虽然许多设备驱动程序确实是为连接在外部总线上的I/O设备（如USB设备、硬盘驱动器等）设计的，但也存在为系统内部设备（如虚拟设备、集成在主板上的设备、内置显卡等）提供支持的设备驱动程序。

B. 设备驱动程序必须运行在操作系统内核态

• 错误。设备驱动程序通常需要运行在内核态，因为它们需要直接访问硬件资源和执行与硬件交互的操作，这些操作通常是受保护的，只能在内核模式下执行。但是也存在 在某些情况下，设备驱动程序也可以运行在用户态。这种设计被称为用户态驱动程序（User-Space Driver）。

C. 必须拥有root权限才能调用设备驱动程序

• 错误。不一定需要root权限才能调用设备驱动程序。用户程序通常通过系统调用与设备驱动程序交互，系统调用会代表用户程序在安全的环境中执行必要的设备操作。然而，对某些设备文件的直接访问确实可能需要更高的权限。

D. 设备驱动程序实现了设备到一组固定接口的抽象

• 正确。设备驱动程序的主要职能之一是抽象硬件细节，向上层提供一组统一和固定的接口。这允许操作系统和应用程序无需关心硬件的具体实现细节。

E. 键盘是一种块设备

• 错误。键盘是一种字符设备，它处理的是字符流，而非存储块。块设备如硬盘和USB存储设备，以数据块的形式进行数据读写。

F. 显示控制器是一种块设备

• 错误。显示控制器通常被分类为字符设备，而非块设备。它们用于输出信息到显示屏，操作通常基于像素或字符流，而非数据块。
  答案：
  根据上述分析，正确的选项是 D。

---

多选题

计算机网络

---

答案：
选C、D。（当然这是我的答案，这个不太确定）
B的话它不适用于高速以太网。并且可以思考一下使用CSMA/CD只是进行了一个最短帧长要求，并没有提高传输速度。
A的话，以太网数据包首部好像大差不差。

---

计算机系统结构

---

GPT分析：
循环展开（Loop Unrolling）是一种常用的代码优化技术，通过减少循环迭代次数来减少循环控制开销，并可能增加程序的并行度。在循环展开中，循环体中的操作被重复多次，以减少循环迭代次数。我们可以逐一审视每个选项，看看哪些是循环展开的优点或不具备的特性：

A. 提高Cache命中率

• 循环展开有助于提高Cache命中率，因为它通过减少循环控制的开销（如计数器更新和跳转指令）并可能更有效地使用数据局部性，从而减少每次迭代的开销。

B. 减小代码长度

• 错误。循环展开通常会增加代码长度，因为它涉及到在编译时静态地复制循环体中的指令。这意味着同样的操作会在编译后的代码中重复出现，从而增加总体的代码量。没展开时使用Loop跳转即可，展开后循环变成一段代码。

C. 增加基本块大小，方便编译器进行静态调度

• 正确。循环展开通过减少循环次数并扩大每次迭代处理的工作量，实际上增加了单个基本块（循环体）的大小。这更容易让编译器进行指令调度和其他优化，如指令重排以隐藏延迟或增加指令级并行。

D. 减少寄存器使用量

• 错误。循环展开往往会增加对寄存器的需求，因为更多的数据和中间结果需要在寄存器中保存，以支持更大的基本块中的操作。这可能导致寄存器溢出，进而需要更多的内存访问，尤其是在寄存器数量有限的架构中。

因此，正确的选项（循环展开不具备的优点）是 B 和 D：减小代码长度和减少寄存器使用量。这两个选项描述了循环展开可能带来的负面效果，而非优点。

---

操作系统

---

GPT分析：
在计算机体系结构中，中断和异常是用来处理特定事件或错误情况的机制。这两者虽然在功能上类似，但在触发原因和处理方式上存在区别。以下是对所提供选项的分析：

A. 发生外部中断时处理器可以继续执行完流水线中的指令后再处理中断

• 正确。外部中断通常允许当前执行的指令完成其执行周期。这意味着处理器可以完成当前流水线中的指令执行，然后在处理下一个指令之前响应中断。这是为了保证处理过程的一致性和数据的完整性。

B. 除硬件故障外的内部异常的产生与当前执行的指令有关

• 正确。内部异常通常与正在执行的指令直接相关。例如，算术溢出、无效操作码、访问违规等都是由于特定指令的执行而触发的。

C. 在流水线检测到内部异常时，应当立即停止流水线并冲刷流水线中所有正在执行的代码

• 错误。虽然在检测到内部异常时确实需要采取措施处理异常情况，但并不一定总是立即停止和冲刷流水线。处理器可能会完成某些指令的执行，特别是那些与异常无关的指令。此外，如何处理取决于异常的类型和严重性。在某些情况下，处理器会尝试完成无冲突的指令或者推迟异常的处理直到安全的点。

D. 缺页是一种常见的中断，需要操作系统介入处理

• 错误。缺页（Page Fault）实际上是一种常见的内部异常，而不是中断。它发生在访问未映射到物理内存的虚拟内存页时。操作系统确实需要介入处理，比如通过从磁盘加载缺失的页到物理内存来解决这个问题，但这是作为异常处理的一部分，而非中断处理。

因此，错误的选项是 C 和 D。这些描述要么误解了中断和异常的处理机制，要么错误地分类了特定的事件。

---

分析：
A. 一个文件描述符对应了一个磁盘上的文件

• 错误。一个文件描述符对应的时系统打开文件表中的一个文件，文件描述符是文件打开时分配的。

B. 文件描述符是属于进程的

• 正确。文件描述符是与特定进程相关联的，每个进程都有自己的文件描述符表。

C. fork时父子进程共享文件描述符的偏移量

• 正确。在fork()调用后，父进程和子进程确实共享文件描述符和其对应的偏移量。如果一个进程改变了文件偏移量，这一改变对另一个进程也是可见的。

D. 文件描述符之间不能共享偏移量

• 错误。文件描述符之间可以共享偏移量，尤其是在它们指向由dup、dup2或在fork之后继承的同一个文件描述符的情况下。

E. 可以通过procfs访问其他进程的文件描述符

• 正确。在许多Unix-like系统中，/proc 文件系统（procfs）提供了一种机制来检查系统及进程的状态，包括访问特定进程的文件描述符信息。例如，/proc/[pid]/fd/目录包含了对应进程的所有文件描述符的符号链接。

F. 文件描述符是可以在进程内复制的

• 正确。使用dup和dup2系统调用，进程可以复制其文件描述符，从而使多个文件描述符指向相同的文件表项。

答案：
正确的选项是 B, C, E, F。