软件设计师高频考点练习题

编译器为一段中间代码构造寄存器干涉图：变量a与b在某程序点同时活跃，因此图中a、b之间存在边。若用图着色进行寄存器分配，下列说法正确的是（）。

操作系统创建子进程时采用Copy-on-Write。fork完成后，父子进程都只读取一块100MB的内存，随后子进程只修改其中一个4KB页面。下列描述正确的是（）。

某伙伴系统的最小内存块为4KB，可用块按2的幂次拆分。进程申请13KB内存，暂不计管理开销，系统应分配的块大小及块内未使用空间分别是（）。

某业务软件功能没有发现缺陷，但服务器操作系统和数据库版本升级后，原驱动接口不再兼容。开发团队修改适配层，使软件能在新环境中继续运行。这主要属于（）。

矩阵A、B、C的维数依次为10×30、30×5、5×60。保持乘法顺序ABC不变，只调整括号位置，标量乘法次数较少的是（）。

按照IEEE 754单精度格式（1位符号、8位阶码、23位尾数），十进制数-13.25的十六进制机器表示是（）。

某分页系统先查TLB再访问主存，TLB查找时间为10ns，主存访问时间为100ns，TLB命中率为90%。TLB未命中时需再访问一次主存读取页表，然后访问目标数据。忽略缺页和Cache，平均有效访问时间为（）。

规定运算符^表示乘方，优先级高于乘除，并且按右结合计算。将中缀表达式a^b^c转换成后缀表达式，正确结果是（）。

求解旅行商问题的最短回路时，算法为每个部分路径计算一个可能总代价的下界；若下界已经不小于当前最优完整回路，就不再扩展该结点。该策略最符合（）。

磁盘柱面编号为0至199，磁头当前位于50号柱面并向编号增大的方向移动。待访问请求为10、20、35、65、80、95。采用C-SCAN，且题目明确将从199回到0的回卷距离计入磁头移动总量，则总移动距离为（）。

某计算机主存地址为32位，Cache数据容量为64KB，块大小为64B，采用二路组相联映射。忽略有效位等附加信息，主存地址中的Tag、组索引和块内偏移位数依次为（）。

0/1背包中，每件物品最多选择一次。将二维状态压缩为一维dp数组后，处理重量为w、价值为v的当前物品时，常写成for(c=C;c>=w;c--)。容量从大到小更新的主要原因是（）。

Kruskal 算法按权值从小到大考察边 (u,v)。使用并查集维护当前连通分量时，若 Find(u) 与 Find(v) 的结果相同，应当（）。

采用线性探测开放定址法的哈希表中，若直接把碰撞簇中间的已删除槽位改成“从未使用”，可能导致后续元素查找提前失败。较合理的删除方式是（）。

某处理器采用指令流水线。相邻两条指令依次为 I1：ADD R1，R2，R3；I2：SUB R4，R1，R5。I2 需要读取 I1 尚未完成写回的 R1。该冲突属于（）。

对序列 [7,2,9,4,3] 做快速排序，明确采用 Lomuto 划分法：以末元素 3 为枢轴，从左到右扫描，把不大于枢轴的元素移到左侧，最后把枢轴放到分界位置。第一趟划分后的序列是（）。

以权值 2、3、7、9 构造哈夫曼树。若根结点深度为 0，则该树的带权路径长度 WPL 为（）。

某系统当前 Available=(3,3,2)。进程 P1 的 Allocation=(2,0,0)，Max=(3,2,2)，现提出 Request=(1,0,2)。按银行家算法，系统还应完成哪一步，才能决定是否正式分配？

二维数组 A[0..3][0..5] 按行优先顺序连续存储，每个元素占 4 字节，A[0][0] 的首地址为 1000。A[2][3] 的首地址是（）。

在 UML 类图中，类 PaymentService 实现接口 Payment。两者之间应使用的关系表示是（）。

某带权有向图可能包含负权边，但不存在负权回路。现在需要求任意两个顶点之间的最短路径。较合适的算法是（）。

红黑树不要求任意节点左右子树高度完全相等，但其查找时间仍为 O(log n)。支撑这一结论的关键理由是（）。

某分治算法把规模为 n 的问题分成 2 个规模为 n/2 的子问题，分解与合并的总工作量为 Θ(n)。其递归式为 T(n)=2T(n/2)+n，则时间复杂度为（）。

最小堆按层序存放为 [10,20,15,30,40,25]。插入元素 12 后，按最小堆规则上滤，最终层序序列是（）。

某读者优先算法使用 mutex 保护 readCount，使用 rw 实现读者组与写者互斥。读者进入时 readCount 加 1，离开时减 1。正确的操作是（）。

某系统采用 32 位虚拟地址、4KB 页面和二级页表。一级页号与二级页号各占 10 位，则虚拟地址的正确划分是（）。

某计算机主存按字节编址，地址长度为 32 位。Cache 容量为 64KB，数据块大小为 64B，采用直接映射方式。主存地址中的 Cache 行号字段应占（）。

某 AOE 网包含以下活动：A：v1→v2，工期3；B：v1→v3，工期2；C：v2→v4，工期4；D：v3→v4，工期5；E：v2→v5，工期3；F：v4→v5，工期2。该项目的关键路径和最短工期为（）。

哈希表长度为 11，哈希函数 H(k)=k mod 11，采用线性探测法处理冲突。按顺序插入关键字 19、14、23、1、68、20。在等概率成功查找的情况下，平均查找长度 ASL 为（）。

模式串 P="ABABAC"。KMP 匹配过程中，前 5 个字符 ABABA 已经匹配成功，但在比较第 6 个字符 C 时发生失配。已匹配部分 ABABA 的最长相等真前缀和真后缀长度为（）。

进程 P1 正在运行，预计还需 8ms 完成。此时新到达进程 P2 只需 3ms。关于 SJF 与 SRTF 调度，下列说法正确的是（）。

某进程因等待磁盘 I/O 从运行态进入阻塞态。当该 I/O 操作完成后，在尚未获得 CPU 的情况下，该进程通常转入（）。

有界缓冲区使用信号量 empty 表示空槽数、full 表示产品数、mutex 表示互斥访问。生产者放入一个产品时，合理的操作顺序是（）。

系统中多个进程频繁发生缺页，磁盘换页活动很重，而 CPU 利用率反而明显下降。更合理的判断和处理方向是（）。

对同一个页面访问序列，采用 FIFO 页面置换算法时，增加分配给进程的页框数后，缺页次数反而增加。这种现象称为（）。

忽略 TLB 和页表访问开销。某系统内存访问时间为 100ns，缺页率为 10^-6，一次缺页处理平均耗时 8ms（该耗时视为完整缺页服务时间）。有效访问时间约为（）。

在采用分页存储的系统中设置 TLB（快表），其主要目的是（）。

某分页存储系统的页面大小为 4KB，逻辑地址为 0x12345。该地址对应的页号和页内偏移分别是（）。

程序的全局作用域声明变量 x，函数内部又声明了同名局部变量 x。在函数体内引用 x 时，编译器进行符号表查找的正确策略是（）。

编译器为布尔表达式生成跳转式中间代码时，某些条件跳转的目标基本块尚未生成。回填技术的主要作用是（）。

对基本块中的表达式 y=a*b+a*b 建立 DAG。若两次 a*b 的操作数和值都相同，DAG 的典型处理是（）。

不考虑公共子表达式优化，将表达式 x=a*b+c 翻译为四元式序列。下列结果正确的是（）。

关于 LR 分析器在正常分析过程中已经压入栈中的文法符号，下列说法正确的是（）。

在自底向上的语法分析过程中，对一个右句型进行正确归约时，本步应被归约的句柄是（）。

某语言同时定义了运算符“>”“=”和“>=”。词法分析器扫描输入 a>=b，并采用最长匹配原则，则在读到“>=”时应当（）。

词法分析器读到源程序中的字符序列 count，并按规则 letter(letter|digit)* 将其识别为标识符。下列对应关系正确的是（）。

关于语法制导定义中的 S 属性定义和 L 属性定义，下列说法正确的是（）。

在 DFA 最小化过程中，状态 p 和 q 对某个输入串 w 的反应不同：从 p 读取 w 后到达接受状态，而从 q 读取 w 后到达非接受状态。由此可知 p 和 q（）。

某带 ε 转移的 NFA 初始状态为 q0，且从 q0 可经 ε 转移到 q1，从 q1 又可经 ε 转移到 q2，除此之外没有新的 ε 转移。使用子集构造法转换为 DFA 时，DFA 的初始状态应为（）。

文法 E→E+T|T 含有直接左递归。保持其生成语言不变，正确的消除结果是（）。

为某文法构造预测分析表时，发现表格单元 M[A,a] 需要同时填入 A→α 和 A→β 两条不同产生式。由此可以直接判断（）。

文法中非终结符 A 有两个候选式 A→α|ε，且 α 不能推出 ε。为了使这两个候选式能够用一个向前看符号进行确定性选择，除基本条件外，还必须满足（）。

给定文法：S→AB，A→a，B→b|ε，S 为开始符号，以 $ 表示输入结束符。FOLLOW(A) 为（）。

给定文法：S→AB，A→aA|ε，B→bB|c。其中 ε 表示空串。FIRST(S) 为（）。

在某静态类型语言中，程序片段的标识符和括号都符合语法规则，但其中变量 total 未声明，且一处函数调用的实参与形参类型不兼容。上述错误主要由编译器的（ ）阶段发现。

按从左到右顺序，用栈计算后缀表达式“6 2 3 + - 3 8 2 / + *”。假设除法按通常算术处理，该表达式的结果为（）。

某权限系统允许管理员编写简单规则，例如“角色为财务并且金额小于 5000”或“部门为研发并且操作为只读”。系统需要为这些规则定义语法，并把每条规则解析为可执行的表达式对象。较适合采用的设计模式是（）。

某编译器已经建立稳定的抽象语法树，树中包含常量节点、变量节点、运算节点等多种元素。团队需要不断增加类型检查、代码生成、格式化输出等操作，但不希望每增加一种操作就修改所有节点类。较适合采用的设计模式是（）。

某图形编辑器中，用户经常需要基于一个已经配置好样式、大小、边框和阴影效果的图形对象，快速创建多个相似对象，并在复制后只修改少量属性。为了避免重复复杂初始化过程，较适合采用的设计模式是（）。

某报表系统生成一份复杂报告时，需要按固定流程设置标题、数据源、图表、页眉页脚和导出格式，但不同客户的具体配置和展示细节不同。设计人员希望把构建过程和最终表示分离，较适合采用的设计模式是（）。

某绘图软件希望在不暴露图形对象内部细节的情况下，保存对象当前状态，便于用户执行撤销操作时恢复到之前的状态。较适合采用的设计模式是（）。

某系统的订单子系统内部包含库存、价格、优惠、物流等多个服务。为了让客户端不必分别调用这些服务，设计人员提供了一个统一的 OrderFacade 接口来完成下单流程。这个设计更接近（）。

某在线文档系统需要显示大量字符对象。很多字符的字体、编码、基本形态可以共享，而位置、颜色、上下文状态由外部传入。为了减少大量相似对象带来的内存开销，较适合采用的设计模式是（）。

某订单对象会经历“待支付、已支付、已发货、已完成、已取消”等状态，不同事件会触发状态转换；另一个图用于描述用户提交订单、系统校验库存、生成支付单、通知仓库发货这一串业务处理步骤。关于这两类 UML 图，下列说法较合理的是（）。

某系统需要根据用户选择的优惠规则，在满减、折扣、返券等算法之间切换；另一个系统中，订单会随着待支付、已支付、已发货、已完成等状态变化而表现出不同操作行为。前者和后者分别更适合使用（）。

在 UML 类图中，订单和订单明细之间通常表现为整体与部分的强拥有关系，订单被删除时订单明细也随之消失；而班级和学生之间虽然也可看作整体与部分，但学生可以脱离某个班级继续存在。前者和后者分别更适合表示为（）。

某 CPU 在执行加法、比较、转移等指令时，需要记录进位、零结果、溢出、中断允许状态等运行状态信息。通常用于保存这些状态和标志位的是（）。

CPU 访问主存时，需要先指出要访问的是哪个存储单元。通常用于保存该主存地址，并把地址送往地址总线的寄存器是（）。

在 CPU 执行程序的过程中，需要保存下一条将要执行指令的地址，以便按顺序取指或在转移后继续执行。通常承担这一功能的寄存器是（）。

某系统中，不同支付方式都需要提供统一的 pay() 能力，但各支付方式内部实现完全不同；另一个场景中，多种报表类有一部分通用字段和通用生成步骤，同时还保留若干需要子类实现的步骤。关于接口和抽象类的使用，下列说法较合理的是（）。

在面向对象程序设计中，同一个类中存在多个同名方法，但参数个数或参数类型不同；而子类重新定义父类中已有的方法，以改变该方法在子类对象上的行为。关于这两种情况，下列说法较合理的是（）。

在一个连通带权无向图中，需要选出若干条边，使所有顶点都连通，且边权之和最小，同时不能形成回路。解决这类问题时，较常用的一组算法是（）。

操作系统采用银行家算法进行资源分配。系统在真正分配资源前，会先判断分配后是否仍存在某种进程执行顺序，使所有进程最终都能获得所需资源并顺利完成。这个判断主要是为了确认系统处于哪种状态？

某绘图软件既支持圆形、矩形等不同图形，又支持 Windows、Linux、Web 等不同绘制平台。如果把每种图形和每个平台都做成一个子类，类数量会迅速膨胀。设计师希望让图形抽象和平台实现可以独立变化。更适合采用哪种设计模式？

某请假审批系统中，1 天以内由组长审批，3 天以内由部门经理审批，更长时间需要总监审批。系统把审批请求沿着处理对象链逐级传递，直到某一级能够处理为止。该设计最接近（）。

某绘图软件把“画线、移动图形、删除对象”等操作封装成独立对象，并记录在命令历史中。用户点击撤销时，系统按历史记录反向执行对应操作。该设计最接近（）。

在订单处理活动图中，设计人员把“提交订单”“审核库存”“支付确认”“安排发货”分别放在用户、库存系统、支付系统、仓储部门等不同区域，以便看清每个活动由谁负责。这些区域通常称为（）。

在平衡二叉排序树 AVL 中，插入一个新结点后，某个结点左右子树高度差超过允许范围。为了恢复二叉排序树的有序性和平衡性，通常需要进行（）。

在哈希表中，两个不同关键字经过哈希函数计算后得到相同的存储地址。某实现把映射到同一地址的元素挂在同一个链表中，查找时先定位桶，再在链表中比较关键字。该冲突处理方法通常称为（）。

在无权图中，从起点开始按层访问相邻顶点，先访问距离起点 1 条边的顶点，再访问距离 2 条边的顶点。为了保持这种“先发现、先扩展”的访问顺序，通常使用的数据结构是（）。

某跨平台界面库需要在 Windows 和 macOS 下分别创建按钮、文本框、菜单等一组风格一致的控件。开发团队希望客户端只依赖统一接口，而不直接关心具体平台控件类。较合适的设计模式是（）。

某系统最初用一个静态工厂方法根据参数创建不同产品。后来产品类型不断增加，团队希望把创建逻辑延迟到具体工厂子类中，由不同工厂负责创建对应产品。后一种设计更接近（）。

在白盒测试中，某覆盖准则要求程序中每条可执行语句至少执行一次；另一覆盖准则要求每个判断的真、假分支至少各执行一次。下列说法正确的是（）。

在 MVC 架构中，用户通过界面提交请求，控制器负责接收请求并协调处理，模型负责业务数据和业务规则，视图负责展示结果。下列说法正确的是（）。

某数据导入流程固定为读取文件、校验数据、转换格式、写入系统四个步骤，但不同文件类型在校验和转换细节上不同。希望父类定义流程骨架，子类实现部分步骤，较适合采用（）。

某个类同时负责用户权限校验、订单计算、报表导出和邮件发送，后续任意一类需求变化都可能导致该类被修改。为了降低修改影响，设计上更应遵循（）。

在分时操作系统中，多个交互式用户进程需要轮流获得 CPU，每个进程运行一个固定时间片后让出处理机。较符合这种思想的调度算法是（）。

在操作系统页面置换中，若内存已满，需要选择一个页面换出。LRU 算法的基本思想是淘汰（）。

某系统需要展示 Web 服务器、应用服务器、数据库服务器之间的部署关系，以及软件构件部署在哪些硬件节点上。此时较适合使用的 UML 图是（）。

某业务服务直接依赖具体的短信发送类，后来需要改成邮件、站内信等多种通知方式，修改成本较高。设计人员希望业务服务依赖通知接口，而具体通知方式实现该接口。这主要体现了（）。

在订单系统中，订单表保存客户编号，客户表保存客户名称。若希望查询订单编号及对应客户名称，需要把两张表按客户编号关联起来，较常使用的 SQL 操作是（）。

在操作系统进程同步中，信号量常配合 P、V 操作使用。一般来说，P 操作会申请资源并可能使进程等待，V 操作会释放资源并可能唤醒等待进程。下列理解正确的是（）。

两个进程分别占有一部分资源，又都等待对方释放资源，导致谁也无法继续执行。操作系统中产生死锁通常需要同时满足互斥、请求并保持、不可剥夺和（）。

在排序算法中，如果两个关键字相同的记录排序前后相对次序不变，就称该排序算法是稳定的。归并排序在合并两个有序子序列时，若相等元素优先取左侧子序列元素，通常可以保持（）。

某数据处理系统的主要流程是输入数据、进行格式检查和转换、生成处理结果并输出。设计人员希望根据数据流图把系统划分为输入、变换中心和输出等模块。较适合采用的方法是（）。

在分析网上报销业务时，分析人员希望描述填写申请、部门审批、财务审核、付款等活动之间的先后顺序、分支和并行处理。此时更适合使用的 UML 图是（）。

某系统后续会不断增加新的报表类型。设计人员希望新增报表时尽量通过增加新类完成，而不是频繁修改已经稳定的核心代码。这种思想主要体现了（）。

用邻接矩阵存储一个有 n 个顶点的图时，无论边数多少，都需要一个 n×n 的矩阵来表示顶点之间是否相邻。其存储空间复杂度通常为（）。

某课程系统中，学习“数据库实践”前必须先学“数据库基础”，学习“项目实训”前必须先完成“程序设计”和“数据库实践”。若要给这些课程排出一个满足先修关系的学习顺序，较适合使用（）。

在数据结构中，若一种线性结构只能在一端进行插入和删除，表现为后进先出；另一种结构在一端插入、另一端删除，表现为先进先出。下列说法正确的是（）。

在一个带权图中，所有边的权值均为非负数。现在需要从某个源点出发，求它到其他各顶点的最短路径。较常用的算法是（）。

快速排序通过选取基准元素，将序列划分为左右两个子序列，再递归排序。通常情况下，快速排序的平均时间复杂度为（）。

某大型软件项目技术难度高、需求存在不确定性，团队希望在每一轮迭代中都进行风险识别、风险分析和风险控制，再逐步推进开发。较适合采用的软件过程模型是（）。

某项目需求比较明确、变更较少，团队希望按需求分析、设计、编码、测试、运行维护等阶段顺序推进。与此相比，另一个项目需求不够清楚，需要先做一个可演示样品让用户确认。下列判断较合理的是（）。

在订单系统中，一个客户可以拥有多个订单，但每个订单通常只属于一个客户。将该 ER 模型转换为关系模式时，较常见的处理方式是（）。

某关系模式已经满足第二范式，但存在“学号 → 系号，系号 → 系名”，从而可以由学号间接推出系名。为了进一步规范化，应重点消除的是（）。

已知 4 个叶子节点的权值分别为 2、3、7、8。按哈夫曼树构造规则，每次选取两个最小权值合并，则最终哈夫曼树的带权路径长度 WPL 为（）。

对一棵二叉树进行遍历时，如果访问顺序是“先访问根节点，再遍历左子树，最后遍历右子树”，这种遍历方式称为（）。

某绘图软件中，单个图形和由多个图形组成的图形组都需要支持移动、缩放、绘制等操作。为了让客户端能够一致地处理单个对象和组合对象，较适合采用的设计模式是（）。

某系统已经有一个文件读取对象，现在希望在不修改原对象的情况下，动态增加缓存、压缩、日志记录等附加功能。若重点是给对象逐层增加职责，更适合采用（）。

在 UML 类图中，班级与学生可以理解为整体和部分，但学生离开某个班级后仍然可以独立存在；而订单与订单明细通常生命周期绑定，订单不存在时明细也没有独立意义。下列说法较合理的是（）。

在图书借阅系统中，“借书”用例每次都必须执行“验证读者身份”；而“借书”在特殊情况下才会触发“缴纳欠费”。从 UML 用例关系看，较合理的判断是（）。

某电商系统需要根据普通会员、VIP 会员、节日活动等不同规则计算折扣。开发人员希望把不同折扣算法封装起来，并在运行时灵活替换。较适合采用的设计模式是（）。

在设计登录功能时，分析人员希望表达用户界面、认证服务、用户数据库之间按时间顺序发送消息的过程。此时更适合使用的 UML 图是（）。

设计一个业务系统时，设计人员希望每个模块内部职责清晰，模块之间依赖尽量少，以便后续修改一个模块时不容易影响其他模块。这体现了（）。

系统需要复用一个已有组件，但该组件提供的接口与当前系统期望的接口不一致。为了在不修改原组件的情况下让它能够被当前系统使用，较适合采用（）。

对一个有序表进行折半查找，表中共有 100 个元素。查找一个元素时，最多需要比较的次数约为（）。

在软件模块设计中，希望一个模块内部功能联系紧密，而模块之间相互依赖尽量少。该设计原则通常概括为（）。

某系统中，一个对象状态发生变化时，需要自动通知多个依赖对象进行更新。为了降低对象之间的直接依赖，适合采用的设计模式是（）。

在 UML 类图中，如果“学生”和“教师”都可以看作“人员”的一种特殊类型，通常应使用哪一种关系表示这种“is-a”关系？

某系统需要根据不同业务场景创建不同类型的产品对象，并希望把对象创建逻辑延迟到子类中完成。此时更适合采用哪一种设计模式？

在数据流图 DFD 中，用来表示对输入数据进行处理、转换，并产生输出数据的成分通常称为什么？

在软件模块设计中，希望一个模块内部职责集中、模块之间依赖尽量少。这个设计原则通常概括为什么？

某算法执行时间与输入规模 n 成正比，通常可将其时间复杂度表示为？

某类在系统运行期间只需要创建一个实例，并提供全局访问点，较适合采用哪种设计模式？