王道2013年最后8套模拟题第1套.pdf

王道2013 年最后8 套模拟试题 （一） 一、单项选择题：第 1～40 小题，每小题2 分，共80 分。下列每题给出的四个选项中，只有一 个选项最符合试题要求。 1． 设n 是描述问题规模的正整数，下列程序片段的时间复杂度是（ ）。 y=0; while(n=(y+1)*(y+1)) y++; A ．O(log n) B ．O(n) C ．O(nlog n) D ．O( n ) 2 2 2 ． 利用栈求表达式的值时，设立运算数栈OPEN 。假设OPEN 只有两个存储单元，则在下 列表达式中，不会发生溢出的是（ ）。 A ．A-B*(C-D) B ．(A-B)*C-D C ．(A-B*C)-D D ．(A-B)*(C-D) 3 ． 将5 个字母”ooops”按此顺序进栈，则有（ ）种不同的出栈顺序可以仍然得到”ooops”。 A ．1 B ．3 C ．5 D ．6 4 ． 以下关于二叉排序树的说法中，错误的有（ ）个。 Ⅰ．对一棵二叉排序树按前序遍历得出的结点序列是从小到大的序列 Ⅱ．每个结点的值都比它左孩子的值大、比它右孩子结点的值小，则这样的一棵二叉树 就是二叉排序树 Ⅲ．在二叉排序树中，新插入的关键字总是处于最底层 Ⅳ．删除二叉排序树中的一个结点再重新插入，得到的二叉排序树和原来的相同 A ．1 B ．2 C ．3 D ．4 5 ． 如右图所示为一棵平衡二叉树（字母不是关键字），在结点D 的右子树 A 上插入结点F 后，会导致该平衡二叉树失去平衡，则调整后的平衡二叉 树应为（ ）。 B C E D 6 ． 在下列二叉树中，（ ）的所有非叶结点的度均为2 。 Ⅰ．完全二叉树 Ⅱ．满二叉树 Ⅲ．平衡二叉树 Ⅳ．哈夫曼树 Ⅴ．二叉排序树 A ．Ⅱ和Ⅳ C ．Ⅰ和Ⅲ C ．Ⅱ、Ⅳ和Ⅴ D ．Ⅱ、Ⅲ和Ⅳ 7 ． 设高度为 100 的二叉树上只有度为0 和度为 2 的结点，则此类二叉树中所包含的结点 数最少为（ ）。 A ．100 B．201 C ．199 D．200 8． 已知有向图G=(V，A) ，其中V={a,b,c,d,e} ，A={a,b ，a,c ，d,c ，d,e ，b,e ， c,e} ，对该图进行拓扑排序，下面序列中不是拓扑排序的是（ ）。 『1』 [王道考研]2013 年最后8 套模拟题 A ．a,d,c,b,e B．d,a,b,c,e C ．a,b,d,c,e D．a,b,c,d,e 9 ． 无向图G 有23 条边，度为4 的顶点有5 个，度为3 的顶点有4 个，其余都是度为2 的 顶点，则图G 最多有 （ ）个顶点。 A ．11 B ．12 C ．15 D ．16 10．下列关于m 阶B-树的说法中，正确的有（ ）。 Ⅰ．每个结点至少有两棵非空子树 Ⅱ．非叶结点仅其索引作用，每次查找一定会查找到某个叶结点 Ⅲ．所有叶子在同一层上 Ⅳ．当插入一个数据项引起B 树结点分裂后，树长高一层 A ．Ⅰ、Ⅱ