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

一、算法设计题

1． 已知无向图采用邻接表存储方式，试写出删除边(i, j) 的算法。

【答案】算法如下:

在用邻接表方式存储的无向图g 中，删除边(i,

j)

删顶点i 的边结点(i, j) , pre 是前驱指针

释放空间

沿链表继续査找

删顶点j 的边结点(j,

i)

释放空间

沿链表继续査找

2． 给出以十字链表作存储结构，建立图的算法，输入(i, j , V) , 其中i , j 为顶点号，v 为权值。

【答案】算法如下:

建立有向图的十字链表存储结构

假定权值为整型

建立顶点向量

当输入i 、j 、v 之一为0时，结

束算法运行

申请结点

弧结点中权值域

第 2 页，共 38 页

算法结束

3． 设给定关键字输入序列为(100，90，120，60，78，35，42，31，15) 用哈希法散列0-10的地址区间。要求设计一合理的哈希函数；冲突时用链表法解决，写出哈希算法，并构造出哈希表，在等概率查找情况下查找成功的平均查找长度是多少？

【答案】算法如下:

关键字

链指针

用链地址法解决冲突，构造哈希表，哈希函数用

初始化

输入n(本例中n=9)

个关键字按题意x 互不相同

4等插入结点链入同义词表

构造的哈希表如图所示:

图构造的哈希表

查找成功时的平均查找长度

。

第 3 页，共 38 页

4． 已知深度为h 的二叉树，以一维数组应的算法。

【答案】算法如下:

作为其存储结构，试编写一算法，求该二叉

树中叶结点的个数，为简单起见，设二叉树中元素结点为非负整数，要求写出算法基本思想及相

计算深度为h 、以一维数组BT 作为其存储结构的二叉树的叶结点数，n 为数组长度

记叶结点数

若结点无孩子，则

是叶子

存储在数组后一半的元素是叶结点

5． 已知L 为没有头结点的的单链表中第一个结点的指针，每个结点数据域存放一个字符，该字符可能是英文字母字符、数字字符或其他字符，编写算法构造三个以带头结点的单循环链表表示的线性表，使每个表中只含同一类字符(要求用最少的时间和最少的空间) 。

【答案】算法如下:

L 是不带头结点的单链表第一个结点的指针，链表中的数据域存放字符

//本算法将链表L 分解成含有英文字母字符、数字字符和其他幸符的带头结点的三个循环链表

//建立三个链表的头结点

//置三个循环链表为空表

//分解原链表

//L指向待处理结点的后继

//处理字母字符

//处理数字字符

//处理其他符号

//结束while(L!＝

null) //算法结束

二、应用题

第 4 页，共 38 页