计算机考研专业课_408_2013(含答案)1

计算机科学与技术学科的专业知识广泛，这里以考研408计算机学科专业基础综合试题为例，主要涉及数据结构、算法和操作系统等核心概念。 1. 合并升序链表成降序链表的问题，最坏情况下的时间复杂度是O(m+n)，其中m和n分别代表两个链表的长度。在合并过程中，需要比较每个节点，找到最大值放入结果链表，因此总的时间复杂度是线性的，与两个链表的长度之和成正比。 2. 栈的特性是后进先出（LIFO）。对于入栈序列1,2,3,...,n，出栈序列123...p...pppp，其中23=p，表明在p出栈前，有p-1个数字已经出栈，但不能确定3p的值，因为这取决于p之后还有哪些数字入栈后再出栈。所以3p可能取值的个数无法确定。 3. 平衡二叉树是一种特殊的二叉树，它的左右子树的高度差不超过1，且每个节点的左右子树都是平衡二叉树。将1,2,3,4,5,6,7依次插入到初始为空的平衡二叉树中，平衡因子为0的分支结点意味着左右子树高度相同。当完全平衡时，插入7个节点会形成一个高度为3的平衡二叉树，有2个平衡因子为0的分支结点（第二层的节点）。 4. 三叉树的带权外部路径长度是指所有叶节点的权值乘以其到根节点的路径长度之和。要使带权外部路径长度最小，通常需要尽可能让权值较大的节点靠下。对于给定的权值，2,3,4,5,6,7，最优的分布可以达到56，这是通过适当调整节点位置来最小化路径长度得到的。 5. 后序线索二叉树是一种二叉树的存储结构，便于进行后序遍历。X是叶节点且存在左兄弟Y，根据后序线索二叉树的定义，X的右线索应指向以Y为根的子树的最左下结点。 6. 删除非空二叉排序树中的结点v，然后重新插入v，结果可能会改变树的形态。如果v是叶结点，插入操作不会改变树的形态；如果v不是叶结点，那么插入操作可能改变树的形态。因此正确的叙述是II（若v是叶结点，则T1与T3相同）和III（若v不是叶结点，则T1与T3不同）。 7. 图的邻接矩阵表示边的存在关系。根据给出的邻接矩阵，可以计算各顶点的度（连接该顶点的边的数量），分别是2,2,1,1，对应答案B。 8. 广度优先遍历（BFS）从根节点开始，逐层遍历。对于无向图，B选项e,a,f,g,b,h,c,d不符合广度优先顺序，因为f在d之前，而实际d应该先于f被访问。 9. 在AOE网（活动-on-edge图）中，加快某些活动可以缩短工程工期。根据网络拓扑，加快c和e的进度可以使得整个工程的工期缩短。 10. 5阶B树的最低层最多有5个关键字，高度为2意味着至少两层。在一株高度为2的5阶B树中，所含关键字的个数最少是7，因为第一层可以有2个关键字，第二层最多可以有5个关键字，但至少要有1个。 11. 基数排序是一种按照位数进行排序的方法。对于关键字序列，第2趟分配收集后，应按照中间位（这里可能是十位）进行排序。由于没有给出具体位数，无法准确确定排序后的序列。 12. 计算MIPS（每秒百万指令数）需要知道CPU频率和指令的CPI（每条指令周期数）。给定的指令比例和CPI分别为A:50%,2；B:20%,3；C:10%,4；D:20%,5。总CPI = (0.5 * 2) + (0.2 * 3) + (0.1 * 4) + (0.2 * 5) = 3。CPU频率为1.2GHz，所以MIPS = 1.2 / 3 = 0.4GIPS，即400MIPS。 以上知识点涵盖了链表合并、栈、平衡二叉树、三叉树、后序线索二叉树、二叉排序树、图的遍历、AOE网、B树和基数排序等计算机科学的基础内容。这些知识在考研中尤为重要，理解和掌握它们是成为计算机专业人才的基础。