【第 44-47 题】（题型：选择题）题目：股票交易中，股票代理 (Broker) 根据客户发出的股票操作指示进行股票的买卖，设计如下所示类图。该设计模式采用 (44) 模式将一个请求封装为一个对象，从而使得以不同的请求对客户进行参数化；对请求排队或记录请求日志，以及支持可撤销的操作，其中，(45) 声明执行操作的接口。该模式属于 (46) 模式，该模式适用于：(47)。(44) A. 命令 (Command) B. 观察者 (Observer) C. 状态 ( State) D. 中介者 (Mediator)(45) A.Operation B.SellOperation/BuyOperation/ViewOperation C.Broker D.Stock(46) A. 结构类型 B. 结构型对象 C. 创建类型 D. 行为型对象(47) A. 一个对象必须通知其他对象，而它又不能假定其他对象是谁B. 抽象出执行的动作以参数化某对象C. 一个对象的行为决定于其状态且必须在运行时刻根据状态改变行为D. 一个对象引用其他很多对象并且直接与这些对象通信，导致难以复用该对象【答案】(44) A；(45) A；(46) D；(47) B【解析】第 (44) 题解析命令模式的核心是将请求封装为对象，使得可以用不同的请求对客户端进行参数化，支持请求排队、日志记录和撤销操作，符合题干描述，选项 A 正确。观察者模式：对象之间的一对多依赖，当一个对象状态改变时通知其他对象。状态模式：对象的行为根据状态改变而改变。中介者模式：通过中介对象减少对象之间的直接交互。第 (45) 题解析在命令模式中，抽象命令角色（Operation）声明执行操作的接口（execute () 方法），具体命令角色（BuyOperation 等）实现该接口，选项 A 正确。第 (46) 题解析命令模式属于行为型设计模式，关注对象之间的交互和行为分配，选项 D 正确。结构型模式：关注对象的组合结构。创建型模式：关注对象的创建方式。第 (47) 题解析命令模式的适用场景包括：抽象出执行的动作以参数化对象，支持请求的排队、撤销、日志记录等，选项 B 正确。选项 A 是观察者模式的适用场景。选项 C 是状态模式的适用场景。选项 D 是中介者模式的适用场景。【第 48 题】（题型：选择题）题目：设有描述简单算术表达式的上下文无关文法如下，其中 id 表示单字母。E→ E+T|TT→ FT|FF→ id与使用该文法描述的表达式 a+bc*d 相符的语法树为 (48)。【答案】A【解析】
第 (55) 题解析需要筛选出商品名为 “HUWEI Mate40” 的商品，商品关系 C 的第 2 列是商品名，筛选后需要商品号和商品名（第 1、2 列），所以选择 π1,2 (σ2='HUAWEI Mate40'(C))，选项 B 正确。第 (56) 题解析需要筛选出销售日期为 2020 年 11 月 11 日的销售记录，销售关系 EC 的第 4 列是销售日期，所以选择 σ4='2020 年 11 月 11 日 '(EC)，选项 C 正确。最终的关系代数表达式是将这三个关系进行自然连接，然后投影需要的列。【第 57 题】（题型：选择题）题目：设有栈 S 和队列 Q 初始状态为空，数据元素序列 a,b,c,d,e,f 依次通过栈 S，且多个元素从 S 出栈后立即进入队列 Q，若出队的序列是 b,d,f,e,c,a，则 S 中的元素最多时，栈底到栈顶的元素依次为（57）A. a,b,c B. a,c,d C. a,c,e,f D. a,d,f,e【答案】C【解析】本题需要模拟栈的入栈和出栈过程，结合队列先进先出的特性推导栈的状态变化：初始状态：栈 S 为空，队列 Q 为空。元素 a 入栈，栈 S：[a]；元素 b 入栈，栈 S：[a,b]；此时 b 出栈进入队列 Q，队列 Q：[b]，栈 S：[a]；元素 c 入栈，栈 S：[a,c]；元素 d 入栈，栈 S：[a,c,d]；此时 d 出栈进入队列 Q，队列 Q：[b,d]，栈 S：[a,c]；元素 e 入栈，栈 S：[a,c,e]；元素 f 入栈，栈 S：[a,c,e,f]；此时 f 出栈进入队列 Q，队列 Q：[b,d,f]，栈 S：[a,c,e]；元素 e 出栈进入队列 Q，队列 Q：[b,d,f,e]，栈 S：[a,c]；元素 c 出栈进入队列 Q，队列 Q：[b,d,f,e,c]，栈 S：[a]；元素 a 出栈进入队列 Q，队列 Q：[b,d,f,e,c,a]，栈 S 为空。从过程中可以看到，栈中元素最多的时刻是 f 入栈后，此时栈底到栈顶的元素依次为 a,c,e,f。【第 58 题】（题型：选择题）题目：当二叉树的结点数目确定时，（58）的高度一定是最小的。A. 二叉排序树 B. 完全二叉树 C. 线索二叉树 D. 最优二叉树【答案】B【解析】本题考察不同类型二叉树的结构特性：选项 A：二叉排序树的高度取决于插入顺序，最坏情况下会退化为单链表，高度为 n-1（n 为节点数），不是最小；选项 B：完全二叉树的定义是除最后一层外，每一层的节点数都达到最大值，最后一层的节点都集中在左侧。当节点数确定时，完全二叉树的高度为⌊log₂n⌋+1，是所有二叉树中高度最小的；选项 C：线索二叉树是对二叉树的存储结构优化，仅增加了线索指针，不改变树的高度；选项 D：最优二叉树（哈夫曼树）的高度取决于节点的权值分布，不一定是高度最小的结构。【第 59 题】（题型：选择题）题目：（59）是对稀疏矩阵进行压缩存储的方式。A. 二维数组和双向链表 B. 三元组顺序表和十字链表C. 邻接矩阵和十字链表 D. 索引顺序表和双向链表【答案】B【解析】稀疏矩阵的特点是大部分元素为 0，压缩存储的核心是只存储非零元素：选项 A：二维数组是稀疏矩阵的常规存储方式，未实现压缩；选项 B：三元组顺序表通过存储非零元素的行号、列号和值来实现压缩；十字链表则是在三元组基础上，增加行指针和列指针，便于矩阵的遍历和修改，两者都是稀疏矩阵的典型压缩存储方式；选项 C：邻接矩阵是图的存储结构，不是稀疏矩阵的压缩方式；选项 D：索引顺序表和双向链表主要用于线性表的存储，与稀疏矩阵压缩无关。【第 60 题】（题型：选择题）题目：设用线性探查法解决冲突构造哈希表，且哈希函数为 H (key)=key% m，若在该哈希表中查找某关键字 e 是成功的且与多个关键字进行了比较，则（60）。A. 这些关键字形成一个有序序列B. 这些关键字都不是 e 的同义词C. 这些关键字都是 e 的同义词D. 这些关键字的第一个可以不是 e 的同义词【答案】D【解析】线性探查法的冲突解决机制是：当发生冲突时，依次探查下一个存储位置，直到找到空位置或查找到目标关键字。同义词指的是哈希函数计算结果相同的关键字，即 H (key)=H (e)。查找关键字 e 时，若发生多次比较，说明 e 的初始哈希位置被其他关键字占据，这些关键字可能是同义词（哈希值相同），也可能是非同义词（哈希值不同但后续探查时占用了位置）。例如：哈希表大小 m=5，H (3)=3，H (8)=3（同义词），H (9)=4，若先插入 9，再插入 8，最后插入 3，查找 3 时会先比较 9（非同义词），再比较 8（同义词），最后找到 3。因此这些关键字的第一个可以不是 e 的同义词。【第 61 题】（题型：选择题）题目：对于一个初始无序的关键字序列，在下面的排序方法中，(61) 第一趟排序结束后，一定能将序列中的某个元素在最终有序序列中的位置确定下来。①直接插入排序②冒泡排序③简单选择排序④堆排序⑤快速排序⑥归并排序A. ①②③⑥ B. ①②③⑤⑥C. ②③④⑤ D. ③④⑤⑥【答案】C【解析】逐一分析各排序方法第一趟的特性：直接插入排序：第一趟仅将第二个元素插入到前面的有序子序列，无法确定任何元素的最终位置；冒泡排序：第一趟会将最大（或最小）的元素交换到序列末尾，该元素的最终位置确定；简单选择排序：第一趟会找到最小（或最大）的元素，与第一个位置交换，该元素的最终位置确定；堆排序：第一趟构建大顶堆（或小顶堆）后，将堆顶元素与最后一个元素交换，堆顶元素的最终位置确定；快速排序：第一趟根据基准元素划分序列，基准元素的最终位置确定；归并排序：第一趟仅将相邻的两个元素合并为有序子序列，无法确定任何元素的最终位置。因此满足条件的是②③④⑤，对应选项 C。【第 62 题】（题型：选择题）题目：对数组 A=(2,8,7,1,3,5,6,4) 构建大顶堆为（62）。(用数组表示)A. (1,2,3,4,5,6,7,8) B. (1,2,5,4,3,7,6,8)C. (8,4,7,2,3,5,6,1) D. (8,7,6,5,4,3,2,1)【答案】C【解析】大顶堆的定义是：每个节点的值都大于或等于其左右子节点的值，数组存储时，父节点索引 i 的左子节点为 2i+1，右子节点为 2i+2。构建大顶堆的步骤为：从最后一个非叶子节点（索引为⌊n/2⌋-1=3，对应元素 1）开始调整：节点 1 的子节点为 3（索引 7）和无右子节点，1<4，交换 1 和 4，数组变为 (2,8,7,4,3,5,6,1)；调整索引 2 的节点 7：子节点为 5（索引 5）和 6（索引 6），7≥5 且 7≥6，无需调整；调整索引 1 的节点 8：子节点为 4（索引 3）和 3（索引 4），8≥4 且 8≥3，无需调整；调整索引 0 的节点 2：子节点为 8（索引 1）和 7（索引 2），2<8，交换 2 和 8，数组变为 (8,2,7,4,3,5,6,1)；调整交换后的节点 2（索引 1）：子节点为 4（索引 3）和 3（索引 4），2<4，交换 2 和 4，数组变为 (8,4,7,2,3,5,6,1)；节点 2（索引 3）无大于它的子节点，调整完成。最终得到的大顶堆为 (8,4,7,2,3,5,6,1)，对应选项 C。【第 63 题】（题型：选择题）题目：最大尺寸和问题描述为，在 n 个整数 (包含负数) 的数组 A 中，求之和最大的非空连续子数组，如数组 A=(-2,11,-4,13,-5,-2)，其中子数组 B=(11,-4,13) 具有最大子段和 20 (11-4+13=20)。求解该问题，可以将数组分为两个 n/2 个整数的子数组最大子段或或者在前半段，或者在后半段，或者跨越中间元素，通过该方法继续划分问题，直至最后求出最大子段和，该算法的时间复杂度为 (63)。A. O (nlgn) B. O (n²) C. O (n²lgn) D. O (n³)【答案】A【解析】题目描述的是分治法求解最大子段和的思路：将数组划分为前后两个子数组，分别求解两个子数组的最大子段和；求解跨越中间元素的最大子段和（即包含中间元素的连续子数组的最大和）；比较三个结果，取最大值作为整个数组的最大子段和。分治法的时间复杂度满足递推公式：T (n)=2T (n/2)+O (n)，根据主定理，该递推式的解为 T (n)=O (nlgn)。【第 64-65 题】（题型：选择题）题目：在求解某问题时，经过分析发现该问题具有最优子结构和重叠子问题性质。则适合 (64) 算法设计策略得到最优解。若了解问题的解空间，并以广度优先的方式搜索解空间，则采用的是 (65) 算法策略。(64) A. 分治 B. 贪心 C. 动态规划 D. 回溯(65) A. 动态规划 B. 贪心 C. 回溯 D. 分支限界【答案】(64) C；(65) D【解析】(64) 题：分治法的核心是将问题划分为独立的子问题，不强调重叠子问题；贪心算法仅需最优子结构，不需要重叠子问题；动态规划的核心就是利用问题的最优子结构和重叠子问题性质，通过记录子问题的解避免重复计算，从而得到最优解；回溯法是试探性搜索解空间，不依赖这两个性质。(65) 题：动态规划是通过状态转移求解，不是广度优先搜索解空间；贪心算法是局部最优选择，不搜索解空间；回溯法是深度优先搜索解空间；分支限界法是广度优先搜索解空间，通过剪枝策略减少搜索范围。【第 66 题】（题型：选择题）题目：IPv6 地址长度为 (66) bit。A.16 B.32 C.64 D.128【答案】D【解析】IPv4 地址长度为 32bit，而 IPv6 为了解决 IPv4 地址枯竭的问题，将地址长度扩展到 128bit，提供了极大的地址空间。【第 67 题】（题型：选择题）题目：在地址栏输入www.abc.com，浏览器默认的应用层协议是 (67)。A.HTTP B.DNS C.TCP D.FTP【答案】A【解析】浏览器在地址栏输入域名后，首先会通过 DNS 协议解析域名对应的 IP 地址，但 DNS 是辅助协议；TCP 是传输层协议，不是应用层；FTP 是文件传输协议，不是浏览器默认的网页访问协议；HTTP（超文本传输协议）是浏览器访问网页默认的应用层协议，默认使用 80 端口。【第 68 题】（题型：选择题）题目：使用电子邮件客户端向服务器发送邮件的协议是 (68)。A.SMTP B.POP3 C.IMAP4 D.MIME【答案】A【解析】SMTP（简单邮件传输协议）用于电子邮件客户端向邮件服务器发送邮件，以及邮件服务器之间的邮件传输；POP3 和 IMAP4 是用于电子邮件客户端从邮件服务器接收邮件的协议；MIME 是多用途互联网邮件扩展，用于定义邮件的内容格式，不是传输协议。【第 69 题】（题型：选择题）题目：以下 Windows 系统中用于清除本地 DNS 缓存的命令是 (69)。A.ipconfig/release B.ipconfig/flushdnsC.ipconfig/displaydns D.ipconfig/registerdns【答案】B【解析】各 ipconfig 参数的功能：ipconfig/release：释放当前获取的 IP 地址；ipconfig/flushdns：清除本地 DNS 缓存；ipconfig/displaydns：显示本地 DNS 缓存的内容；ipconfig/registerdns：刷新 DNS 客户端注册信息。【第 70 题】（题型：选择题）题目：在网络系统设计时，不可能使所有设计目标都能达到最优，下列措施中最为合理的是 (70)。A. 尽量让最低建设成本目标达到最优B. 尽量让最短的故障时间达到最优C. 尽量让最大的安全性目标达到最优D. 尽量让优先级较高的目标达到最优【答案】D【解析】网络系统设计的多个目标（成本、可靠性、安全性、性能等）之间往往存在冲突，例如高安全性可能导致成本上升、性能下降。在无法同时优化所有目标的情况下，合理的策略是根据需求确定目标的优先级，优先满足优先级较高的目标。【第 71-75 题】（题型：选择题）题目：Designing object-oriented software is hard,and designing (71) object-oriented software is even harder.You must find pertinent (相关的) objects,factor them into class at the right granularity,define class interfaces and inheritances,and establish key relationships among them.You design should be specific to the problem at hand but also (72) enough to address future problems and requirements.You also want to avoid redesign,or at least minimize it.Experienced object-oriented designers will tell you that a reusable and flexible design is difficult if not impossible to get "right" the first time.Before a design is finished,they usually try to reuse it several times, modifying it each time.Yet experienced object-oriented designers do make good designs.Meanwhile new designers are (73) by the options available and tend to fall back on non-object-oriented techniques they've used before.It takes a long time for novices to learn what good object-oriented design is all about.Experienced designers evidently know something inexperienced ones don't.What is it?One thing expert designers know not to do is solve every problem from first principles.Rather,they reuse solutions that have worked for them in the past.When they find a good (74).They use it again and again.Such experience is part of what makes them experts.Consequently,you'll find (75) patterns of classes and communicating objects in many object-oriented systems.(71) A.runnable B.right C.reusable D.pertinent(72) A.clear B.general C.personalized D.customized(73) A.excited B.shocken C.surprised D.overwhelmed(74) A.tool B.component C.system D.solution(75) A.recurring B.right C.experienced D.past【答案】(71) C；(72) B；(73) D；(74) D；(75) A【解析】(71)：根据后文提到的 "reusable and flexible design"，此处应填 reusable，意为设计可复用的面向对象软件更难。(72)：设计需要针对当前问题，同时也要足够通用（general）以应对未来的需求，与 "specific" 形成对比。(73)：新设计师会被众多可选方案压垮（overwhelmed），从而退回到之前使用的非面向对象技术。(74)：专家设计师会重复使用之前有效的解决方案（solution）。(75)：因此在很多面向对象系统中会发现重复出现的（recurring）类和对象交互模式，即设计模式。
