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

一、填空题

1． 阅读下列程序，指出其功能，并写出空格处应填上的语句。

【答案】

【解析】本题是在哈希表ht[]中插入值为的元素，如该元素已在哈希表中，报告出错。

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

【答案】26

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

3． N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。

【答案】2（N-1）

【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N-1条边就可 以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2（N-1）个非零元素。

4．

设单链表的结点结构为

为指针域，已知指针px 指向单链表中data 为x 的结

_____；点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，贝懦要执行以下语句：

_____;

【答案】

5． 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。

【答案】

第 2 页，共 36 页

6． 起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32，则其伙伴块的起始地址为_____。

【答案】

【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下：

根据上述公式起始地址就为488。

7． 对n 个记录的表r[l..n]进行简单选择排序，所需进行的关键字间的比较次数为_____。

【答案】n （n-1）/2

【解析】第一次需要n-1次比较，第i 此需要n-i 此比较，所以共需要、n-l+n-2+...+l=n（n-l ）/2。

8． 求图的最小生成树有两种算法，_____算法适合于求稀疏图的最小生成树e

【答案】克鲁斯卡尔

【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。

9． 设有个结点的完全二叉树顺序存放在向量中，其下标值最大的分支结点为_____。

【答案】

【解析】最大的分支结点是最后一个叶子结点的父结点。

10．克鲁斯卡尔算法的时间复杂度为_____，它对_____图较为适合。

【答案】O （eloge ）; 边稀疏

11．有五个数据依次入栈：1，2, 3, 4, 5。在各种出栈的序列中，以3, 4先出栈的序列有_____。（3在4之前出栈）

【答案】3个

【解析】以3, 4先出栈的序列有34521、34215、34251共3个。

12．设数组数组中任一元素均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么

（1）存放该数组至少需要的单元数是_____；

（2）存放数组的第8列的所有元素至少需要的单元数_____； （3）数组按列存储时，元素【答案】270; 27; 2204

第 3 页，共 36 页

的起始地址是_____。

【解析】

数组的元素个数为需要

第8列有9个元素，共占

因为每个元素占内存48个二进制位，即6个字节。故总

个单元数。

个字节，因此至少需要

个单元数。由题知，每个元素占3

个字节，因为主内存字长为16位，即2个字节，所以至少需要

个单元。按列存储时，的起始地址为

13．己知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需_____次查找成功，查找47时_____成功，查找100时，需_____次才能确定不成功。

【答案】2；4；3

【解析】二分法查找元素次数列表

查

找100是找到115就停止了。

14．组成串的数据元素只能是_____。

【答案】字符

15．当广义表中的每个元素都是原子时，广义表便成了_____。

【答案】线性表

【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。

二、算法设计题

16．已知关键字序列

（1）试写出一算法将

（2）利用（1）的算法写一个建大根堆的算法。 【答案】（1）算法如下：

17．用邻接多重表存储结构，编写FIRST-ADJ （G ，V ）函数，函数返回值为第一个邻接点，若V 没有邻接点，返回零。

【答案】算法如下：

第 4 页，共 36 页

是大根堆。

调整为大根堆；