软件设计师考前20问，注意啦！！

备战2022年下半年软件设计师的小伙伴或正在备考的兄弟姊妹，建议点赞收藏哦

第1问 地址码为什么不存入程序计数器（PC）中？

答：首先要区分地址码和地址，地址码属于指令的构成部分，而地址一般是指存储的指令地址。其次需要弄清楚PC和IR的区别，程序计数器PC是存放下一条指令的地址，而指令寄存器是存放正在执行的指令。指令实质上是由操作码和地址码两部分进行组成，自热对应整个指令部分，故都存放在指令寄存器（IR）中。

第2问 流水线技术中的吞吐率怎么算？

答：首先流水线的吞吐率有实际吞吐率和最大吞吐率之分。

（1）实际吞吐率：指在单位时间内流水线所完成的任务数量或输出的结果数量。公式：吞吐率=指令条数/流水线执行时间。例如10条指令，流水线执行时间为35，那吞吐率=10/35。

（2）最大吞吐率：为流水线周期（指令分段执行中时间最长的一段）的倒数。例如10条指令，流水线周期为5，那它的最大吞吐率=1/5（跟指令条数没有关系）。

第3问 CISC和RISC的各自特点是什么？

答：（1）CISC（复杂指令集）的特点：指令数量多，指令频率差别大，变长，多种寻址方式，使用微码（微程序）实现。

（2）RISC（精简指令集）的特点：指令数量少，频率接近，定长，单周期，多寄存器寻址，多通用寄存器，硬布线逻辑控制，适用于流水线。有效支持高级程序语言，优化编译。

第5问 图的遍历方式有几种？

答：（1）深度优先遍历：首先访问出发顶点V；依次从V出发搜索V的任意一个邻接点W；W未访问过，则从该点出发继续深度优先遍历。

（2）广度优先遍历：首先访问出发顶点V；然后访问与顶点V邻接的全部未访问顶点W、X、Y…；然后再依次访问W、X、Y…邻接的未访问的顶点。

两者区别在于一个不断的去遍历临近的1个结点，直达临近结点遍历完成，才会有返回的过程。而另外一个呢，一次性遍历该结点的所有临近结点，依次类推。回溯法对应深度优先，而分支限界法对应广度优先。

第6问 常见的常见算法策略其各个特点是什么？

答：

算法名称	关键点	特征	典型问题
分治法	递归技术	把一个问题拆分成多个小规模的相同子问题，一般可用递归解决。	归并排序、快速排序、二分搜索
贪心法	一般用于求满意解，特殊情况可求最优解（部分背包）	局部最优，但整体不见得最优。每步有明确的、既定的策略。	背包问题（如装箱）、多机调度、找零钱问题
动态规划法	最优子结构和递归式	划分子问题（最优子结构），并把子问题结果使用数组存储，利用查询子问题结果构造最终问题结果。	矩阵乘法、背包问题、 LCS最长公共子序列
回溯法	探索和回退	系统地搜索一个问题的所有解或任一解。有试探和回退的过程。	N皇后问题、迷宫、背包问题

第7问 常见的排序算法有哪些，其特点、时间复杂度、空间复杂度是多少？

答：（1）直接插入排序：即当插入第i个记录时，R1，R2，…，Ri-1均已排好序，因此，将第i个记录Ri依次与Ri-1，…，R2，R1进行比较，找到合适的位置插入。

（2）希尔排序：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1（dt<dt–1<…<d2<d1），即所有记录放在同一组中进行直接插入排序为止。

（3）冒泡排序：通过相邻元素之间的比较和交换，将排序码较小的元素逐渐从底部移向顶部。

（4）快速排序：采用分治法，其基本思想是将原问题分解成若干个规模更小但结构与原问题相似的子问题。通过递归解决这些子问题，然后再将这些子问题的解组合成原问题的解。

（5）选择排序：首先在所有记录中选出排序码最小的记录，把它与第1个记录交换，然后在其余的记录内选出排序码最小的记录，与第2个记录交换，依次类推，直到所有记录排完为止。

（6）堆排序：基本步骤先开始初建堆，其次取出堆顶元素，然后重建堆，最后再完成排序。

（7）归并排序：归并也称为合并，是将两个或两个以上的有序子表合并成一个新的有序表。若将两个有序表合并成一个有序表，则称为二路合并。

（8）基数排序：基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。基数排序不是基于关键字比较的排序方法，它适合于元素很多而关键字较少的序列。

 

第8问 PV操作都必须要成对出现吗？

答：PV一定是成对出现的，PV可以简单理解为加锁和解锁，如果只加锁也就是只有P操作，可能会形成死锁。如果没有加锁，只有解锁也就是V操作，那么相当于系统中资源无端增多，也就没有意义了。

以打印机为例，如果对打印机加上PV操作，P操作相当于，每个人用之前都锁定一次打印机（S=S-1），此时其他人去打印时进行申请，会发现资源不足（S<0），此时就进入阻塞队列去排队了；而V操作相当于，能够使用打印机的人，用完之后，之前占有的打印机就会释放给其他人用（S=S+1），此时如果发现有人排队（S<=0），就会通知排队的人，可以使用了。

太多了，发不过来。。。。。。可以私信留言！