09年408考研真题-数据结构

数据结构

10.【2009统考真题】为解决计算机主机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是(B）。

A.栈        B.队列        C.树        D.图

解析：先进入缓冲区的指令应该先被处理，具有先进先出特点的只有队列。

22.【2009统考真题】设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后，立即进入队列Q，且7个元素出队的顺序是bdcfeag，则栈s的容量至少是(C）。A.1        B.2        C.3        D.4

27.【2009统考真题】给定二叉树如右图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列是3175624，则其遍历方式是(C）。

B. NRL        A.LRN        C. RLN        D. RNL

17.【2009统考真题】下列二叉排序树中，满足平衡二叉树定义的是(B）。

05.已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点，则该完全二叉树的结点个数最多是(C)。

A. 39        B.52        C.111        D.119

解析：

要想该完全二叉树的结点个数最多，就要让树的高度越高。完全二叉树最早在n-1层出现叶子结点，所以最高应该是6+1=7层。

这就意味着前6层是满的。如图所示是每一层的结点个数。

根据等比数列求和公式求出前6层的结点个数是63。

接着计算最后一层第七层的结点个数。

第六层有32个结点，其中有8个是叶子结点。有32-8=24个非叶子结点。

每个非叶子结点都有2个子节点，一共有48个子节点。

结点个数=63+48=111个

11.[2009统考真题]将森林转换为对应的二叉树，若在二叉树中，结点u 是结点v的父结点的父结点，则在原来的森林中，u 和 v 可能具有的关系是(B)。

I.父子关系        II.兄弟关系        III.u 的父结点与v 的父结点是兄弟关系

A.只有I        B.I和II        C.I和III        D.I、II和III

解析：

父子关系：|正确

兄弟关系：||正确

|||不正确。

14.【2009统考真题】下列关于无向连通图特性的叙述中，正确的是(）。

 I.所有顶点的度之和为偶数。

Ⅱ.边数大于顶点个数减。

Ⅲ.至少有一个顶点的度为1。

A.只有I

B.只有Ⅱ

C.Ⅱ和Ⅲ

D.I和Ⅲ

解析：

对于I,一条边有两度，n条边有2n度。

对于Ⅱ：举反例

对于Ⅲ,举反例：

11.[2009统考真题]下列叙述中，不符合m阶B树定义要求的是(D)

A.根结点至多有 m 棵子树

B.所有叶结点都在同一层上

C.各结点内关键字均升序或降序排列

D.叶结点之间通过指针链接

解析：叶结点之间通过指针链接是B+树的特性。

11.【2009统考真题】已知关键字序列5,8,12,19,28,20,15,22是小根堆,插入关键字3,调整好得到的小根堆是(）。

A.3, 5,12,8, 28,20, 15, 22, 19

B. 3, 5, 12, 19, 20,15, 22, 8, 28

C. 3, 8, 12, 5, 20, 15, 22, 28, 19

D. 3, 12, 5, 8, 28, 20, 15, 22, 19

堆的插入：上刀山

15.【2009统考真题】若数据元素序列{11,12,13,7,8,9,23,4,5}是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是(）。

A冒泡排序        B.插入排序        C.选择排序        D.2路归并排序

解析：

A冒泡排序，每一趟排序结束后，都会找到最大或者最小值出现在序列的头或尾。很显然4没有出现在头或尾，A错。

B插入排序，经过插入排序之后，它的前三个元素应该是有序的，B正确。

C选择排序，每一趟排序结束后，都会找到最大或者最小值出现在序列的头或尾。很显然4没有出现在头或尾

D2路归并排序，一趟排序后，你和你附近的元素应该是有序的。D错