2009年408真题解析【2009.1】为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是。A.栈B.队列C.树D.图【知识点】栈和队列特点及应用。【答案】B【解析】考查栈和队列特点及应用。缓冲区的特点要先进先出，队列符合。【2009.2】设栈S和队列Q的初始状态均为空，元素a，b，c，d，e，f，g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b，d，c，f，e，a，g，则栈S的容量至少是。A.1B.2C.3D.4【知识点】栈最大递归深度。【答案】C【解析】栈先进后出，队列先进先出，则出栈顺序为 b,d,c,f,e,a,g，模拟过程，当 d 入栈后，栈内有 acd；f 入栈后，栈内有 aef；此时栈内元素为 3 个，则栈容量至少为 3。【2009.3】给定二叉树如右图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列是3，1，7，5，6，2，4，则其遍历方式是。A.LRNB.NRLC.RLND.RNL【知识点】二叉树的特殊遍历。【答案】D【解析】结点的相对位置关系：3（N）,1（L），7（R），5（L），6（R），2（L），4（R）。可以看出这是一个右子树优先的先序遍历，因此答案是：NRL(先访问根，然后右子树，最后左子树)【2009.4】下列二叉排序树中，满足平衡二叉树定义的是。【知识点】平衡二叉树。【答案】B【解析】平衡二叉树的定义：任意结点的左右子树高度差绝对值不超过 1。A 中根左 2 右 0；C 中根左 1 右 3；D 中根左 4 右 1；皆不符合定义。【2009.5】已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点，则该完全二叉树的结点个数最多是。A.39B.52C.111D.119【知识点】完全二叉树。【答案】C【解析】完全二叉树比满二叉树只是在最下面一层的右边缺少了部分叶结点，而最后一层之上是个满二叉树，并且只有最后两层有叶结点。第 6 层有叶结点则完全二叉树的高度可能为 6 或 7，显然树高为 7 时结点更多。如果前五层是满二叉树，那么第 6 层的叶子节点为 8 个，总节点数为 25-1+8=39 个结点。若前六层为满二叉树，而第 7 层缺失了 8×2=16 个叶结点，故完全二叉树的结点个数最多为(27-1)-16=111个结点。【注意】叶节点可能在最后一层，也可能在倒数第二层。正如完全二叉树的定义！【2009.6】将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是。I.父子关系Ⅱ.兄弟关系Ⅲ.u的父结点与v的父结点是兄弟关系A.只有ⅡB.I和ⅡC.I和IIID.I、II和III【知识点】森林和二叉树的转换。【答案】B【解析】在将森林转换为对应的二叉树时，具体的关系如下：结点u是结点v的父结点的父结点，表示u是v的祖父结点。如果在二叉树中，结点u是结点v的父结点的父结点，那么在原来的森林中，u和v可能具有的关系是：I. 父子关系（u是v的祖父结点，v是u的孙子结点）Ⅱ. 兄弟关系（u和v的父结点是同一个结点，即u和v是兄弟）【2009.7】下列关于无向连通图特性的叙述中，正确的是。I.所有顶点的度之和为偶数Ⅱ.边数大于顶点个数减1Ⅲ.至少有一个顶点的度为1A.只有IB.只有ⅡC.I和IID.I和III【知识点】无向连通图的特性。【答案】A【解析】I. 所有顶点的度之和为偶数。在无向图中，每条边都会贡献两个度，一个给边的一个端点，另一个给另一个端点。因此，所有顶点的度之和一定是偶数。Ⅱ. 边数大于顶点个数减1。这是树的性质，而无向连通图中边数最少是n-1，其中n是顶点个数。如果边数不大于顶点个数减1，说明图中存在环，不是树。Ⅲ. 至少有一个顶点的度为1。这是树的性质，树中除了叶子结点外，每个结点的度都至少为2。但在一般的无向图中，至少有一个顶点的度为1。因此，正确答案是A。【补充】无向图的度：一个顶点的度是与之相关联的边的数目。树：无向无环图，且是连通图，顶点数为边数加1。连通图：图中任意两个顶点都有路径相连。【2009.8】下列叙述中，不符合m阶B树定义要求的是。A.根结点最多有m棵子树B.所有叶结点都在同一层上C.各结点内关键字均升序或降序排列D.叶结点之间通过指针链接【知识点】m阶B树定义。【答案】D【解析】m阶B树的定义要求：A. 根结点最多有m棵子树。这是B树的定义，确保树的平衡性。B. 所有叶结点都在同一层上。这是B树的特性，使得查找效率更高。C. 各结点内关键字均升序或降序排列。B树要求结点内的关键字有序排列，以便进行二分查找。D. 叶结点之间通过指针链接。这是B+树的特点，将叶结点串联起来，方便范围查询。所以，不符合m阶B树定义要求的是D，因为叶结点之间通过指针链接是B+树的特点，而非B树。【补充】B树：用于数据库和文件系统中的数据结构，有助于提高查找效率。B+树：在B树的基础上做了一些修改，将非叶结点仅用于索引，所有关键字都在叶子结点中出现，叶结点之间通过指针链接，提高范围查询的效率。【2009.9】已知关键字序列5,8,12,19,28,20,15,22是小根堆(最小堆),插入关键字3,调整后得到的小根堆是。A.3,5,12,8,28,20,15,22,19B.3,5,12,19,20,15,22,8,28C.3,8,12,5,20,15,22,28,19D.3,12,5,8,28,20,15,22,19【知识点】小根堆的调整操作。【答案】A【解析】插入关键字 3 时，先将其放在小顶堆的末端。共 k=9 个结点，从第 k/2 个结点开始调整堆，依次调整至根结点。调整后的小顶堆序列为 3，5，12，8，28，20，15，22，19。①初始[5,8,12,19,28,20,15,22]; ②插入[5,8,12,19,28,20,15,22,3]; ③19,3 置换[5,8,12,3,28,20,15,22,19]；④3 和 8 置换[5,3,12,8,28,20,15,22,19]；⑤3 和 5 置换[3,5,12,8,28,20,15,22,19]【补充】小根堆的定义：每个节点的值都小于或等于其子节点的值。堆的调整一般包括插入和删除操作，保持堆的性质。插入时需要向上调整，删除时需要向下调整。【2009.10】若数据元素序列11,12,13,7,8,9,23,4,5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是。A.冒泡排序B.插入排序C.选择排序D.二路归并排序【知识点】排序算法特点。【答案】B【解析】A、C——冒泡排序和选择排序，每一趟过后都能确定一个元素的最终位置。序列中前两个元素 or 后两个元素均不是最值。B——插入排序，每趟结束前面若干元素有序，符合。D——二路归并排序，每一趟排序结束都可以得到若干有序子序列。序列中没有两两元素有序。【2009.11】冯·诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU区分它们的依据是。