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

一、填空题

1． 在一个无向图的的邻接表中，若表结点的个数是m ，则图中边的条数是_____条。

【答案】

【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。

2． 设为哈夫曼树的叶结点数目，则该哈夫曼树共有_____个结点。

【答案】

【解析】哈夫曼树只有度为0和2的节点。

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

【答案】

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

4． 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。

第 2 页，共 61 页

a 中存放待排序的关键字

【答案】

【解析】快速排序(quick sort)的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

5． 对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。

:_____:

{_____)

(_____、

:_____；_____；p ＝u ；

【答案】(1)L﹣＞next ＝NULL //置空链表，然后将原链表结点逐个插入到有序表中 (2)p!＝NULL //当链表尚未到尾，p 为工作指针

(3)q!＝NULL //查P 结点在链表中的插入位置，这时q 是工作指针 (4)p﹣＞next ＝r ﹣＞next //将P 结点链入链表中

(5)r﹣＞next ＝p //r是q 的前驱，u 是下个待插入结点的指针

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

【答案】26

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

第 3 页，共 61 页

关键字最多。

7． 设有一个10阶对称矩阵A 采用压缩存储方式(以行为主序存储:a 11＝l) ， 则a 85的地址为_____。

【答案】33

【解析】设存储的元素的行标为i ，列标为j 。若i ＞＝j ，则

的地址为l ＋2＋... ＋i ﹣l ＋j

＝i(i﹣l)/2＋j 。若i ＜j 。则的地址为j(j﹣l)/2＋i 。将i ＝8，j ＝5代入得33。

8． 对n 个元素的序列进行起泡排序时，最少的比较次数是_____。

【答案】n －1

【解析】如果序列是正序，冒泡排序第一次只要进行n －1次比较，发现没有移动元素，说明序列有序。

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

h 为附加头结点指针

(_____)

_____；

【答案】(1)p!＝NULL //链表未到尾就一直进行 (2)q //将当前结点作为头结点后的第一元素结点插入

10．设二维数组A 的行和列的下标范围分别为[0:8]和[0:10]，每个元素占2个单元，按行优先顺序存储，第一个元素的存储起始位置为b ，则存储位置为b+50处的元素为_____。

【答案】A[2][3]

【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是(ll*i＋j ＋l ﹣l)*2＋b 。当其值为b ＋50时，则i ＝2，j ＝3。

二、单项选择题

11．从堆中删除一个元素的时间复杂度为（ ）。

A.O(1) B. C.O(n) D. 【答案】B

【解析】堆中删除一个元素，需要重新调整堆，其时间复杂度为

12．已知程序如下:

第 4 页，共 61 页

。