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

一、填空题

1． G 是一个非连通无向图，共有28条边，则该图至少有_____个顶点。

【答案】9

【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。

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

【答案】26

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

3． —棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_____个结点。

【答案】

【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉树。故结点个数为。

4． 根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_____和_____；而又根据指针的连接方式，链表又可分成_____和_____。

【答案】单链表；双链表；(动态) 链表；静态链表

【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和后续元素。根据指针的连接方式，链表可分为动态链表和静态链表。静态链表的指针指向下一个元素的编号，动态链表的指针指向下一个元素的物理位置。

5．

给定一组数据以它构造一棵哈夫曼树，则树高为_____，带权路径长度WPL 的值为_____。

【答案】5；96

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

第 2 页，共 52 页

6． 堆是一种有用的数据结构。堆排序是一种_____排序，堆实质上是一棵_____结点的层次序列。对含有N 个元素的序列进行排序时，堆排序的时间复杂度是_____，所需的附加存储结点是_____。关键码序列05, 23, 16, 68, 94, 72, 71, 73是否满足堆的险质_____ 。

【答案】选择；完全二叉树；

；O(1)；满足堆的性质

在B

7． 假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素中的存储位置k ＝_____。(注:矩阵元素下标从1开始)

【答案】93

【解析】对于上三角矩阵，k ＝(i﹣l)(2n﹣i ＋2)/2＋(j﹣i) ＋l 。将i ＝j ＝9，n ＝15代入得93。 8． 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。

【答案】O(1)；O(n)

【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。

9． 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。

【答案】4；2

10．属于不稳定排序的有_____。

【答案】希尔排序、简单选择排序、快速排序、堆排序等

二、算法设计题

11．辅助地址表的排序是不改变结点物理位置的排序。辅助地址表实际上是一组指针，用它来指出结点排序后的逻辑顺序地址。设

用

表示辅助地址表。初始时

减序) 算法的语句序列。

【答案】算法如下:

一趟排序无交换发生，结束

第 3 页，共 52 页

表示n 个结点的值，用

，在排序中，凡需对结点交换就用它的地址

来进行。例如当n=3时，对K(31，11，19) 则有T(2，3，1) 。试编写实现辅助地址表排序(按非递

12．已知两个线性表A , B 均以带头结点的单链表作存储结构，且表中元素按值递增有序排列。设计算法求出A 与B 的交集C ，要求C 另开辟存储空间。，并同样以元素值的递增有序的单链表形式存储。

【答案】算法如下:

//线性表A 和B 以带头结点的单链表作为存储结构。本算法求A 和B 的交集C , C 另辟空间

//pa、pb 是两链表的工作指针

//监视哨

//pa指针后移

//pb指针后移

//处理交集元素

//删除重复元素

//交集元素并入结果表

//置结果链表尾

13．在一棵以二叉链表表示的二叉树上，试写出按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目的算法。

【答案】算法如下:

层次遍历二叉树，并统计度为1的结点的个数

统计度为1的结点的个数

是以二叉树结点指针为元素的队列

出队，访问结点

度为1的

结点

非空左子女入队

非空右子女入队

返回度为1的结点的个数

第 4 页，共 52 页