2011年计算机统考真题解析.PDFVIP

予人玫瑰 手留余香 王道论坛 王道考研系列 2011 年全国硕士研究生入学统一考试 计算机科学与技术学科联考 计算机学科专业基础综合 （科目代码：408 ） 特别鸣谢： 阿三（casper08，哈工大） 王道考研系列辅导书编写团队 予人玫瑰 手留余香 予人玫瑰 手留余香 王道论坛 一、单项选择题：1-40小题，每小题2分，共80分，下列每小题给出的四个选项中，只有一 项符合题目要求的。请在答题卡上将所选项的字母涂黑。) 1．设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是 x=2； while （xn/2） x=2*x； 2 A．O(log n) B．O(n) C．O(nlog n) D．O(n ) 2 2 t+1 解答：A。程序中，执行频率最高的语句为“x=2*x”。设该语句执行了t次，则2 =n/2， 故t=log (n/2)-1=log n-2= O(log n)。 2 2 2 2．元素a，b，c，d，e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所 有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是 A．3 B．4 C．5 D．6 解答：C。出栈顺序必为d_c_b_a_，e的顺序不定，在任意一个 “_”上都有可能。 3．已知循环队列存储在一维数组A[0...n-1]中，且队列非空时front和rear分别指向队头 元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则 初始时front和rear的值分别是 A．0,0 B．0，n-1 C．n-1,0 D．n-1，n-1 解答：B。插入元素时，front不变，rear+1.而插入第一个元素之后，队尾要指向尾元 素，显然，rear初始应该为n-1,front为0。 4．若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是 A．257 B．258 C．384 D．385 解答：C。叶结点数为n，则度为2的结点数为n-1,度为1的结点数为0或1，本题中为1 （总 结点数为偶数），故而即2n=768。 5．若一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1，则该二叉树的 中序遍历序列不会是 A．1,2,3,4 B．2,3,4,1 C．3,2,4,1 D．4,3,2,1 解答：C。由前序和后序遍历序列可知3为根结点，故 （1,2）为左子树，（4）为右子树， C不可能。或画图即可得出结果。 6．已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结 点个数是 A．115 B．116 C．1895 D．1896 解答：D。本题可采用特殊情况法解。设题意中的树是如下图所示的结构，则对应的二 叉树中仅有前115个叶结点有右孩子。 共 1