自学内容网 自学内容网

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,则其遍历方式是(D)。

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

解析: 序列第一个数字是3,3是右子树,接着是1,1是根,答案已经很明显了,选D

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

解析:平衡二叉树左右子树的高度相差不大于1,选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统考真题】下列关于无向连通图特性的叙述中,正确的是(A)。

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

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

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

A.只有I

B.只有Ⅱ

C.Ⅱ和Ⅲ

D.I和Ⅲ

解析:

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

对于:下图举反例,有等于顶点个数减1。

对于,举反例:下图所有顶点度都为2

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

解析:

小根堆的插入:上刀山。

可以看出3最小,依次和19,8,5交换位置,到达根的位置。此过程称为上刀山。

插入后的小根堆是:3,5,12,8,28,20,15,22,19,选A。

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

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

解析:

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

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

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

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


原文地址:https://blog.csdn.net/weixin_62182040/article/details/142286393

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!