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

2011 年全国硕士研究生入学统一考试 计算机科学与技术学科联考 计算机学科专业基础综合试题 一、单项选择题：第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 2 ．元素a，b ，c，d，e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有 的元素都出栈，则在所有可能的出栈序列中，以元素d 开头的序列个数是（ ）。 A ．3 B ．4 C ．5 D ．6 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 4 ．若一棵完全二叉树有768 个结点，则该二叉树中叶结点的个数是（ ）。 A ．257 B ．258 C ．384 D ．385 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 6 ．已知一棵有2011 个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结 点的个数是（ ）。 A ．115 B ．116 C ．1895 D ．1896 7 ．对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（ ）。 A ．95，22 ，91，24 ，94，71 B ．92，20 ，91，34，88，35 C ．21 ，89，77，29 ，36，38 D ．12，25 ，71，68，33，34 8．下列关于图的叙述中，正确的是（ ）。 Ⅰ．回路是简单路径 Ⅱ．存储稀疏图，用邻接矩阵比邻接表更省空间 Ⅲ．若有向图中存在拓扑序列，则该图不存在回路 A ．仅Ⅱ B ．仅Ⅰ、Ⅱ C ．仅Ⅲ D ．仅Ⅰ、Ⅲ 9 ．为提高散列（Hash ）表的查找效率，可以采取的正确措施是（ ）。 Ⅰ．增大装填（载）因子 Ⅱ．设计冲突（碰撞）少的散列函数 Ⅲ．处理冲突（碰撞）时避免产生聚集（堆积）现象 A ．仅Ⅰ B ．仅Ⅱ C ．仅Ⅰ、Ⅱ D ．仅Ⅱ、Ⅲ 10．为实现快速排序算法，待排序序列宜采用的存储方式是（ ）。 A ．顺序存储 B ．散列存储 C ．链式存储 D ．索引存储 11．已知序列25，13，10，12，9 是大根堆，在序列尾部插入新元素18，将其再调整为大根 第 1 页 共 15 页 堆，调整过程中元素之间进行的比较次数是（ ）。 A ．1 B ．2 C ．4 D ．5 12．下列选项中，描述浮点数操作速度指标的是（ ）。 A ．MIPS