当前位置：问答库＞考研试题

一、填空题

1． 高度为4的3阶B-树中，最多有_____个关键字。

【答案】26

【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。

2． 假定查找有序表

【答案】37/12

【解析】折半查找时每个的次数如表所示：

表

平均查找次数为

3． 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。

【答案】（1）（2）

链表未到尾就一直进行

将当前结点作为头结点后的第一元素结点插入

中每个元素的概率相等，则进行折半查找时的平均查找长度为_____

4． 数据结构中评价算法的两个重要指标是_____。

【答案】算法的时间复杂度和空间复杂度

5． 设数组储，则元素为_____。

【答案】9174；8788

【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，

则它的存储地址为

若以列序为主存储顺序，则它的存储地址为

的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存

的存储地址为_____；若以列序为主序顺序存储，则元素

的存储地址

6． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度，当它为一棵_____ 时. 具有最大高度

【答案】完全；只有一个叶结点的二叉树

7．

给定一组数据

的值为_____。 【答案】5；96

【解析】每次找两个最小的权值构建哈夫曼树：

以它构造一棵哈夫曼树，则树高为_____，

带权路径长度

8． 在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____分别设在内存空间的两端，这样只有当_____时才产生溢出。

【答案】满；空；n ; 栈底；两栈顶指针相邻（即值之差的绝对值为1）

9． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。

【答案】

【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测 的次数最小。总次数为

10．数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____，设计出相应的_____。

；算法 【答案】逻辑结构；物理结构；操作（运算）

二、选择题

11．排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（ ）。

I. 简单选择排序II. 希尔排序III. 快速排序IV . 堆排V. 二路归并排序 A. 仅 I 、III 、IV B. 仅 I 、II 、III

C. 仅 II 、III 、IV D •仅III 、IV 、V 【答案】A 。

【解析】其中简单选择排序、堆排序属于选择类排序，每一趟排序结束时将确定最大（或最小）关键字所在的位置。快速排序每一趟排序结束时将确定基准关键字所在的位置。希尔排序、二路归并排序每一趟排序结束时不一定能确定一个元素的最终位置。

12．稀疏矩阵一般的压缩存储方法有两种，即（ ）。

A. 二维数组和三维数组 B. 三元组和散列 C. 三元组和十字链表 D. 散列和十字链表 【答案】C

【解析】稀疏矩阵一般的压缩方法为三元组表和十字链表。三元组表就是将非零元素及其对应的行和列构成一个三元组（行标，列标，值）。十字链表相比三元组表而言，主要是对每个结点增加了两个链域。如果数组经常运算时，会产生大量数据元素的移动，此时，采用链表存储结构更为恰当。

13．数据链路层采用后退N 帧（GBN ）协议，发送方已经发送了编号为0〜7的倾。当计时器超时，若发送方只收到0、2、3号帧的确认，则发送方需要重发的帧数是（ ）。

A.2 B.3 C.4 D.5

【答案】C

【解析】后退N 帧协议，即GO-BACK-N 策略的基本原理是，当接收方检测出失序的信息帧后，要求发送方重发最后一个正确接收的信息帧之后的所有未被确认的帧；或者当发送方发送了N 个帧后，若发现该N 帧的前一个帧在计时器超时后仍未返回其确认信息，则该帧被判为出错或丢失，此时发送方就不得不重新发送出错帧及其后的N 帧。本题收到3号帧的确认，说明0，1，2，3号帧已经收到，丢失的是4，5，6, 7号帧，共4帧。因此答案为C 项。

14．向一个栈顶指针为h 的带头结点的链栈中插入指针S 所指的结点时，应执行（ ）。

【答案】D

【解析】本题是向一个链栈中插入结点，可从头结点后插入。先将s 结点指向第一个头结点之后的结点之前，再将头结点指向s 结点。