🧊🧊🧊单项选择题（共40道）
🧊数据结构（10道）
🥥1.打印机的缓冲区逻辑结构
栈：先进后出；
队列：先进先出。
缓冲区的作用是解决主机与打印机之间速度不匹配的问题，而不应改变打印数据的顺序。
🥥2.入栈（队）出栈（队）顺序
因为队列是先进先出，所以出队顺序就是出栈顺序。
复现出入详情：
- a,b在（入）栈，这样才能b出栈；
- a,c,d在栈，d出栈，c出栈；
- a,e,f在栈，f,e,a出栈；
- g入栈，g出栈。
结合上述过程，栈的容量至少要能容纳3个元素。
🥥3.树的遍历方式
观察这道题目给到的序列，先遍历了3，也就是1的右子树，再遍历了1自身，最后遍历了1的左子树同时也满足右根左，所以这道题目的遍历方式就是右根左。
🥥4.平衡二叉树判断
平衡二叉树：任意结点的左、右子树高度差的绝对值不超过1。
🥥5.完全二叉树节点个数
完全二叉树：前边层全满，只有最后一层可以不满，并且左边全满（也就是说确实的叶子必须是从右边往左边顺序缺失）
这道题目的坑在于，只告诉了我们第6层有多少叶节点，但是这棵完全二叉树的高度其实可以是6层也可以是7层，是7层的话，按照上边的描述，前6层全满，也就是1+2+4+8+16+32，第7层缺失的是第6层的这8个节点下方的叶子节点，也就是缺失了2*8=16个叶子节点，那么总节点个数为1+2+4+8+16+32+(64-16)=111个节点
🥥6.森林和二叉树的转换
❓❓❓这道题目的解析是这样的，但是我个人感觉III也是对的，就逆向法的（4）左上角再接上u的父节点，这样两个父节点不就是兄弟关系了吗？有没有懂的uu能帮忙解答一下~~评论区见~~
🥥7.无向连通图的特性
无向图的度：每个结点连接的边数总和；
有向图的度：入度，指向我的边数；出度，从我指出去的边数
度之和是偶数是因为“无向”；n个节点，n-1条边的树也能构成无向连通图；顶点数大于等于1的无向完全图也是无向连通图（完全图：每个点都与其他所有点有连边）
🥥8.m阶树+B树
m阶树：每个节点最多可有m个子节点；
B树：自平衡树，特点包括：
- 多路平衡查找树： 每个节点可以拥有多于两个子节点，适用于高效处理大量数据。
- 平衡性： 所有叶子节点到根节点的距离相同，确保了每个查找操作的时间复杂度为O(log n)。
- 节点容量： 每个节点有固定数量的子节点，通常在实现时通过参数m来定义。
B+树：B树的一种变体，与B树的特点包括：
- 叶子节点存储数据： 所有数据项都存储在叶子节点中，非叶子节点仅存储键值。
- 叶子节点之间有指针相连： 叶子节点通过指针形成一个链表，便于范围查询和顺序访问。
- 内部节点不存储数据： 内部节点只存储键值和指向子节点的指针，这减少了非叶子节点的空间开销。
🥥9.堆的插入
关键字序列是层次遍历，插入的关键字在最后一层从左到右第一个空位，然后每棵子树进行调整，将三个节点中的最小数换到根节点，具体如下：
🥥10.排序算法
冒泡排序：比较相邻的元素，如果前面的元素大于后面的元素，则交换它们。每一轮遍历都会将最大的元素沉到最后。
选择排序：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。
二路归并排序：归并排序是一种分治算法，将待排序数组递归地分成两半，直到每个子数组的大小为1。然后将相邻的子数组进行合并，直到整个数组排序完成。
- 冒泡排序和选择排序：每一趟都能确定一个元素的最终位置；
- 二路归并排序：每一趟排序结束都可以得到若干个有序子序列，而此时的序列中并没有两两元素有序排列；
- 插入排序：在每趟排序后能确定前面的若干元素是有序的。
根据上述描述，该题目采用的是插入排序
🍨🍨🍨需要排序算法总结的宝子评论区告诉我，呼声高的话整理各类排序算法哦~~~
🧊计算机组成原理（13道）
🥥1.冯诺依曼指令和数据的区分
数据、指令存储区分方法：
- 通过不同的时间段区分：取指令阶段取出的是指令，执行指令阶段取出的是数据；
- 通过地址来源区分：PC提供的存储单元地址中的是指令，指令地址码提供的是操作数（数据）
注意，第二点说的是地址来源，不是D选项中的所在地址
🥥2.补码加法
- C语言中的整型数据为补码形式，int为32位，short为16位：x 、y转换成十六进制为 0000007FH 、FFF7H。
- 执行 z = x+y 时，由于 x是 int型，y 为 short型，需将短字长数据转换成 长字长数据，称之为 “符号扩展” 。 由于y 的符号位为 1, 故在y 的前面添加 16 个 1, 即可将 y 上升为 int型，其十六进制形式为 FFFFFFF7H。
- 最后执行加法，即 0000007FH + FFFFFFF7H = 00000076H, 其中最高位的进位 1 自然丢弃。 故选D。
🥥3.浮点加法计算
浮点加减法基本步骤：
据此，本题步骤：
- X的浮点数格式为 00,111;00,11101 (分号前为阶码，分号后为尾数），Y 的浮点数格式为 00,101;00,10100。 然后根据浮点数的加法步骤进行运算。
- 第一步：对阶。 X、Y 阶码相减， 即 00, 111-00, 101 = 00, 111+11, 0111 = 00, 010, 可知 X 的阶码比 Y 的价码大 2 (这一步可直接目测）。根据小阶向大阶看齐的原则，将Y 的阶码加 2, 尾数右移2 位，将Y 变为 00, 111; 00, 00101。
- 第二步： 尾数相加。 即 00, 11101 + 00, 00101 = 01, 00010, 尾数相加结果符号位为 01, 故 需右规。
- 第三步： 规格化。 将尾数右移l位，阶码加 1, 得 X+Y 为 01, 000; 00, 10001。
- 第四步： 判溢出。 阶码符号位为 01, 说明发生溢出。
🥥4.主存与Cache的映射
映射方式分为：直接映射、组相联映射、全相联映射 三种
直接映射：将主存中的每个块映射到缓存中的一个唯一位置（或称为缓存行）
- 映射规则： 对于一个给定的主存块，它的地址会通过某种映射函数（通常是取模运算）直接映射到缓存的一个特定位置。
- 优点： 实现简单，硬件开销低，适用于大多数寻址模式。
- 缺点： 容易发生冲突（即不同的主存块可能映射到相同的缓存位置），可能导致高的替换率和较低的缓存命中率。
组相联映射：介于直接映射和全相联映射之间的一种策略，它将缓存划分为多个组（sets），每个组包含多个缓存行
- 映射规则： 主存中的块可以映射到任意一个组内的某个缓存行，而不是像直接映射那样只能映射到一个确定的位置。
- 优点： 相比直接映射，能够降低冲突率，提高缓存命中率。
- 缺点： 硬件复杂度和成本较高，相对于直接映射来说，实现和管理都更复杂。
全相联映射：一种高度灵活的映射策略，它允许主存中的任何块映射到缓存中的任何位置
- 映射规则： 每个主存块可以映射到缓存的任何一个空闲位置，不受限于特定位置或组。
- 优点： 可以避免冲突完全，最大化缓存命中率。
- 缺点： 硬件复杂度非常高，成本昂贵，对于替换算法的实现也更为复杂。
本题解题过程：
- 由于Cache共有16块，采用 2路组相联，因此共分为8组，组号为0,1, 2, …，7。
- 主存的某一字块按模8映射到Cache某组的任一字块中，即主存的第0, 8, 16, …字块可以映射到Cache第0组的任一字块中。
- 每个主存块大小为32字节，故129号单元位于第4块 主存块（注意是从0开始），因此 将映射到Cache第4组的任一字块中。
🥥5.ROM和RAM芯片数量
存储容量的扩展方式：
AK×B，A称为字，B称为位
字扩展：B相同，2K×8 / 1K×8 = 2片
位扩展：A相同，2K×8 / 2K×4 = 2片
字位同时扩展：A、B都不同，60Kx8 / 4Kx4 = 15×2 = 30片
- 首先确定 ROM的个数，ROM区为4KB, 选用 2Kx8位的ROM芯片，需要4Kx8 / 2Kx8 = 2片，采用字扩展方式；
- RAM区为60KB, 选用 4Kx4位的 RAM芯片，需要 60Kx8 / 4Kx4 = 30片，采用字和位同时扩展方式。
🥥6.指令寻址&转移
相对寻址EA=(PC)+A, 首先要求的是取指令后PC的值。转移指令由两个字节组成，每取一个字节 PC值自动加1, 因此取指令后PC值为2000H + 2H = 2002H , 故EA=(PC)+A=2002H + 06H =2008H。
🍨🍨🍨需要指令寻址方法总结的宝子评论区告诉我，呼声高的话整理各类指令寻址方式哦~~~
🥥7.RISCvsCISC
相对千CISC, RISC的特点是指令条数少；指令长度固定，指令格式和 寻址种类少；只有取数I存数指令访问存储器，其余指令的操作均在寄存器之间进行；CPU中通用寄存器多；大部分指令在一个或者小于一个机器周期内完成；以硬布线逻辑为主，不用或者少用微程序控制。
RISC（精简指令集计算）：
特点和设计原则：
- 精简指令集： RISC处理器的指令集非常精简和统一，每条指令执行的操作非常简单和基本。
- 硬件实现简单： RISC处理器的硬件设计相对简单，指令执行时间通常较短。
- 流水线执行： RISC处理器常常采用流水线（pipeline）技术来实现指令并行执行，提高整体性能。
- 寄存器数量多： RISC架构通常拥有更多的通用寄存器，减少了对内存的访问次数，提高了效率。
优点：
- 执行速度快：简单的指令执行和流水线技术使得RISC处理器能够更快地执行指令。
- 硬件设计简单：更易于设计和制造，成本通常较低。
- 适合高性能计算和嵌入式系统：对于需要高效处理器和低能耗的应用领域非常合适。
缺点：
- 指令数目有限：需要更多的指令来完成复杂的任务，可能需要更多的指令周期。
- 可能需要更多的编译优化：编译器在RISC架构上需要更多的工作来优化代码。
CISC（复杂指令集计算）：
特点和设计原则：
- 复杂指令集： CISC处理器的指令集更加复杂，可以支持较为复杂的操作，一个指令可以执行多个低级操作。
- 硬件实现复杂： CISC处理器的硬件设计较为复杂，通常包含多个执行单元和微码控制。
- 多功能指令： 单条指令可以实现多个功能，包括内存访问、算术运算等。
- 少量寄存器： CISC处理器通常拥有较少的寄存器。
优点：
- 高级语言代码紧凑：可以通过复杂的指令集直接支持高级语言的指令，减少了编译器的工作量。
- 减少内存访问次数：一些复杂操作可以在一条指令内完成，减少了对内存的访问次数。
缺点：
- 硬件设计复杂：由于指令集的复杂性，CISC处理器的硬件设计复杂，难以实现高速和低功耗。
- 指令执行速度慢：复杂的指令可能需要多个时钟周期才能完成，导致执行效率不如RISC高。
🥥8.CPU时钟周期
流水线的时钟周期应以最长的执行时间为准，否则用时长的流水段的功能将不能正确完成。
🥥9.微程序控制器vs硬布线控制器
- 微程序控制器采用了 “存储程序 ” 的原理， 每条机器指令对应 一个微程序，因此修改和扩充容易，灵活性好，但每条指令的执行都要访问控制存储器，所以速度慢；
- 硬布线控制器采用专门的逻辑电路实现，其速度主要取决于逻辑电路的延迟，因此速度快，但修改和扩展困难，灵活性差。
硬件普遍要比软件快，软件普遍要比硬件灵活
🥥10.总线带宽
总线带宽：单位时间内总线上传输数据的位数，通常用每秒钟传送信息的字节数来衡量， 单位Bis。
由题意可知，在1个总线周期(=2个时钟周期）内传输了4字节信息，时钟周期=1110MHz = 0.1µs, 故总线带宽为4B/(2x0.1µs) = 4B/(0.2x10^-6 s) = 20MB/s。
🥥11.cache命中率
命中率=Cache命中次数I总访问次数
🥥12.引起中断的事件
- 外部中断指的是CPU执行指令以外的事件产生的中断，通常是指来自CPU与内存以外的中断。
- A中键盘输入属于外部事件，每次键盘输入CPU都需要执行中断以读入输入数据，所以能引起外部中断。
- B中除数为0属于异常，也就是内中断，发生在CPU内部。
- C中浮点运算下溢将按机器零处理，不会产生中断。
- 而D访存缺页属于CPU执行指令时产生的中断，也不属于外部中断。
🥥13.处理机系统并行问题
单处理机系统（不包含多核的情况）：同一时刻只能有一个进程占用处理机。
因此进程之间不能并行执行。 通道是独立于CPU的控制输入／输出的设备，两者可以并行，显然，设备与设备之间也是可以并行的。
🧊创作不易，点个赞吧~
🧊点赞收藏不迷路~
