『73』 王道2013 年最后8 套模拟试题（七） 一、 单项选择题：第 1～40小题，每小题 2分，共 80分。下列每题给出的四个选项中，只有一个选项最符合试题要求。 1. 执行（ ）操作时，需要使用队列作为辅助存储空间。 A．查找哈希表 B．广度优先搜索图 C．前序（根）遍历二叉树 D．深度优先搜索图 2. 若已知一个栈的入栈序列是1,2,3,4。其出栈序列为p1,p2,p3,p4，则p2,p4 不可能是（ ）。 A．2、 4 B．2、 1 C．4、 3 D．3、 4 3. 在常用的描述二叉排序树的存储结构中，关键字值最大的结点是（ ）。 A．左指针一定为空 B．右指针一定为空 C．左右指针均为空 D．左右指针均不为空 4. 由4 棵树组成的森林中，第一、第二、第三和第四棵树中的结点数分别为30、10、20、5，当把森林转换成二叉树后，对应二叉树中根结点的右子树的左子树的结点数为（ ）。 A．29 B．9 C．25 D．19 5． 在下列遍历算法中，在遍历序列中叶结点之间的次序可能与其他算法不同的算法 是（ ）。 A．先序遍历算法 B．中序遍历算法 C．后序遍历算法 D．层次遍历算法 6． 在一棵非空二叉树的中序遍历序列中，根结点的右边（ ）。 A．只有右子树上的所有结点 B．只有右子树上的部分结点 C．只有左子树上的部分结点 D．只有左子树上的所有结点 7. 如果具有 n个顶点的图是一个环，则它有（ ）棵生成树。 A．n2 B．n C．n-1 D．1 8. 具有 12 个关键字的有序表中，对每个关键字的查找概率相同，折半查找查找成功和查找失败的平均查找长度依次为（ ）。 A．37/12,49/13 B．35/12,39/13 C．37/13,49/13 D．37/12,49/12 9. 在一棵含有 n个关键字的m 阶 B-树中进行查找，至多需要读盘（ ）次（假设读一次盘就能将整个结点取出）。 A．log2n B．1+log2n C．1+log m/2 [(n+1)/2] D．1+log n/2 [(m+1)/2] 10. 对一组数据（25,84,21,47,15,27,68,35,20）进行排序，前三趟的排序结果如下： 第一趟：20,15,21,25,47,27,68,35,84 第二趟：15,20,21,25,35,27,47,68,84 第三趟：15,20,21,25,27,35,47,68,84 则所采用的排序方法是（ ）。 A．选择排序 B．希尔排序 C．归并排序 D．快速排序 [王道考研]2013 年最后8 套模拟题 『74』 11． 一组经过第一趟2-路归并排序后的记录的关键字为｛25,50,15,35,80,85,20,40,36,70｝，其中包含5 个长度为2 的有序表，用2-路归并排序方法对该序列进行第...
