2013考研计算机真题及答案解析(详细)2013考研计算机真题及答案解析(详细).pdf

2013 年全国硕士研究生入学统一考试 计算机科学与技术学科联考 计算机学科专业基础综合试题 一、单项选择题：第 1～40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只 有一个选项最符合试题要求。 1．已知两个长度分别为 m 和 n 的升序链表，若将它们合并为一个长度为 m+n 的降序链表， 则最坏情 况下的时间复杂度是（ ）。 A．On() B．O() m? n C．O(min( m , n )) D．O(max( m , n )) p, p , p , , p p ? 3 p 2．一个栈的入栈序列为1,2,3, ,n ，其出栈序列是 1 2 3 n 。若 2 ，则 3 可 能取值的个 数是（ ）。 A．n ?3 B．n ? 2 C．n ?1 D．无法确定 3．若将关键字 1，2，3，4，5，6，7 依次插入到初始为空的平衡二叉树 T 中，则 T 中平衡 因子为 0 的 分支结点的个数是（ ）。 A．0 B．1 C．2 D．3 4．已知三叉树 T 中 6 个叶结点的权分别是 2，3，4，5，6，7，T 的带权（外部）路径长度 最小是 （ ）。 A．27 B．46 C．54 D．56 5．若 X 是后序线索二叉树中的叶结点，且 X 存在左兄弟结点 Y，则 X 的右线索指向的是 （ ）。 A．X 的父结点 B．以 Y 为根的子树的最左下结点 C．X 的左兄弟结点 Y D．以 Y 为根的子树的最右下结点 6．在任意一棵非空二叉排序树 T1 中，删除某结点 v 之后形成二叉排序树 T2，再将 v 插入 T2 形成二叉排 序树 T3。下列关于 T1 与 T3 的叙述中，正确的是（ ）。 I．若 v 是 T1 的叶结点，则 T1 与 T3 不同 II． 若 v 是 T1 的叶结点，则 T1 与 T3 相同 III．若 v 不是 T1 的叶结点，则 T1 与 T3 不同 IV．若 v 不是 T1 的叶结点，则 T1 与 T3 相同 A．仅 I、III B．仅 I、IV C．仅 II、III D．仅 II、IV 7．设图的邻接矩阵 A 如下所示。各顶点的度依次是（ ）。 第 1 页 共 16 页 ??0 1 0 1 ??0 0 1 1 A ? ?? ??0 1 0 0 ?? 1 0 0 0 ?? A．1，2，1，2 B．2，2，1，1 C．3，4，2，3