2023年计算机408统考真题解析.docx

会员专享推荐 · 你可能也用得上更多

开通会员，畅读全站文档

本篇文档已为你保留

本篇文档价值 ~~¥35.00~~会员免费解锁

全文不限次阅读，剩余内容即刻解锁
高速下载通道，免排队、无等待
专属客服 1 对 1 答疑，优先响应
每日赠送下载券，本篇文档免费送

有 86 篇商业计划书正在上传

下载原文档

2023年全国硕士研究生招生考试计算机学科专业基础试题参考答案及解析一、单项选择题01.D 02.C 03.A 04.B 05.A 06.B 07.B 08.B 09.C 10.C 11.D 12.C 13.A 14.A 15.C 16.B 17.A 18.B 19.C 20.D 21.D 22.C 23.D 24.A 25.C 26.D 27.C 28.D 29.B 30.C 31.B 32.D 33.D 34.C 35.B 36.C 37.D 38.A 39.B 40.D 01.D。【解析】A选项的操作涉及在有序表中搜索给定值元素。在顺序存储结构中，可以通过遍历数组来进行搜索，遍历的时间复杂度为0(n),也可以采用折半查找，遍历的时间复杂度为0(logn)。B选项的操作涉及将给定值元素插入到有序表中的适当位置。在顺序存储结构中，插入一个元素可能需要移动其他元素，以便为新元素腾出空间。这个过程的时间复杂度取决于元素的插入位置，最坏情况下可能需要移动整个数组，时间复杂度为0(n)。C选项涉及从有序表中删除指定位置的元素。在顺序存储结构中，删除一个元素后，后面的元素需要向前移动以填补空缺。这个过程的时间复杂度也取决于删除位置，最坏情况下可能需要移动整个数组，时间复杂度为0(n)。D选项的操作涉及直接访问有序表中指定位置的元素值，在顺序存储结构中，可以通过索引来直接访问数组中的元素，因此这个操作的时间复杂度为0(1)。所以本题的正确选项为D。02.C。【解析】本题选项为C,主要考察双链表的插入操作，解决这类问题可在纸上画出具体的双链表进行模拟。因为s->next已经赋值为p的后一个结点，同时p->next指针已经赋值为s。所以只需要处理s->prev和s->next->prev的赋值，s->prev需要指向p,s->next->prev需要指向s,因为p->next和s指向同一个结点，所以可以用p->next代表s。故本题的正确选项为C。03.A。【解析】存储稀疏矩阵M,我们只需要知道M的行数和列数，便可以算出该矩阵共有多少个元素，三元组存储每个非零元素的位置，当我们需要某个位置的元素，可以先根据M的行数和列数判断是否越界，如果没有越界，在三元组进行查找，如果三元组没有保存对应位置的值，代表矩阵中该位置的值为0。所以正确选项为A。04.B。【解析】计算字符集S构造的哈夫曼编码的加权平均长度，我们需要使用字符的频次来确定每个字符的编码长度，并计算加权平均值。给定字符集S中各字符出现的频次为3,4,5,6,8,10,我们可以按照哈夫曼编码算法构造哈夫曼树。构建的哈夫曼树如下图所示。加权平均长度=(编码长度1×频次1+编码长度2×频次2+…+编码长度n×频次n)/(频次1+频次2+…+频次n),在本题中，加权平均长度=((3+4+5+6)×3+(8+10)×2)/(3+4+5+6+8+10)=2.5。05.A。【解析】如下图所示。对于后序序列fdbeca,a为树的根节点，因此在序号1中，a首先进行绘制。同时，a节点的左子树有4个节点，右子树有1个节点，因此fdbe属于左子树，c节点属于右子树，所以我们在序号2的树中，填充c。a结点左子树的后序遍历序列为fdbe,代表e为左子树的根节点，因此在序号3的树中，填充e。同理e节点的左子树有两个节点，右子树有一个节点，因此fd属于左子树，b属于右子树，在序号4的树中，我们填写b。e的左子树的后序遍历序列为fd,则d为子树的根节点，因此在序号5的树中，我们填充d,最后在序号6的图中，填充f。4 5 6 06.B。【解析】普里姆算法(选项)和克鲁斯卡尔算法(选项)是用于解决最小生成树问题的算法，它们并不直接适用于求解最短路径问题。广度优先遍历(BFS)是一种图遍历算法，可以用于求解单源最短路径问题。在权值均为1的情况下，BFS算法从给定的起始顶点开始遍历，按照层级顺序逐步扩展，每次扩展一层。这样，当BFS遍历到目标顶点时，它所经过的边数就是从起始顶点到目标顶点的最短路径长度。因此，BFS算法可以用于求解图G中从某个顶点到其余各个顶点的最短路径。因此本题正确选项为B。07.B。【解析】B树是一种平衡的多路搜索树，它的特点是可以容纳更多的关键字和子结点。当进行插入操作时；如果插入的关键字导致结点已满，树的高度可能会增加，因为需要进行结点的分裂操作来保持B树的平衡。选项I正确。删除的结点如果为叶节点，则叶结点肯定会发生改变，如果删除的结点为非叶子结点，最终也需要转换为删除叶子结点，所以也会引起叶子结点的变化。选项Ⅱ正确。B树查找操作并不一定会找到叶结点，它会根据关键字的大小选择合适的路径进行搜索，可能会在非叶结点上停止查找，选项Ⅲ错误。关键字插入时的初始位置为叶子结点，但可以会因为结点的关键字超出容量而导致分裂，从而上升到父结点，所以最终的位置不在叶结点。选项IV错误。所以本题的正确选项为B选项。08.B。【解析】在含有600个元素的有序表进行折半查找时，其关键字比较次数最多的情况发生在目标元素不在表中的情况下。在这种情况下，折半查找会进行到最后一步，直到左边界和右边界相遇。因此，关键字比较次数最多的情况是在查找过程中遍历整个表的情况。在进行折半查找时，每次比较会将查找范围缩小一半，直到找到目标元素或确定目标元素不在表中。对于600个元素的有序表，因为log₂(600)=9.22,采用9次遍历并不能查找完成，因此需要10次查找。所以本题的正确选项为B选项。09.C。【解析】线性探测再散列法中删除一个关键字会导致后面的关键字无法通过线性探测找到正确的位置。当删除一个关键字时，为了保持散列表的连续性，通常会将后续的关键字向前移动填充空缺，这样后续的查找操作才能继续正确地找到它们。然而，如果删除的是一个位于中间位置的关键字，后面的关键字需要依次向前移动，这会导致删除操作的时间复杂度较高，因为需要移动大量的关键字。为了解决删除操作中的位置依赖性问题，可以使用删除标记来表示一个位置上的关键字已被删除。如下表所示，查找失败的平均查找长度为(1+3+2+1+2)/5=1.8,所以本题的正确答案选择C选项。地址。