文档介绍：试题七北京邮电学院1994年硕士研究生入学试题
一、(8分)数据结构和抽象数据类型是如何定义的。二者有何相同和不同之处,抽象数据类型的主要特点是什么?使用抽象数据类型的主要好处是什么?
二、(8分)在字符串模式匹配的KMP算法中,求模式的next数组织的定义如下:
0 当j=1时
next[j]= max{k|1<k<j且‘P1…Pk-1=’Pj-k+1…Pj-1}
其他情况
请问:(1)当j=1试,为什么要去next[1]=0,什么意思?;
(2)为什么要取max{K},K最大是多少?
(3)其他情况是什么情况,为什么取next[j]=1?
三、(8分)在二叉树的前序遍历和中序遍历的递归算法中,最后一个递归调用语句在调用示所保留的参数有什么作用?如何清除最后这个递归语句?
四、(8分)和为哈希表?其查找时间是O(1)吗?为什么?在使用线性探测解决冲突的哈希表,能否对表中元素真正删除,为什么?
五、(8分)对图1所示的二叉树,作如下回答:
这是一棵什么样的二叉树。
画出此二叉树三种不同顺序的存储结构图。
对你所画的存储结构图比较各自的优缺点。
如此二叉树是由树或森林转换而来的,请把次数还原成森林。
六、(8分)对图2所示有向图回答下面问题:
在有向图中判别是否存在回路有那些方法,是说明其中两种方法的基本思想。
使用弗洛伊德(Floyd)算法求下面这每一对顶点之间的最短路径,实话出矩阵A0,A1,A2,A3中的情况(即A(0),A(1),A(2),A(3))。
七、(7分)由线性表(a1,a2,…,an),采用单链表存储,头指针为H,每个结点中存放线性表中的一个元素,现查找模个元素值=X的结点。分别写出下面三种情况的查找语句。要求时间尽量少。
线性表中的元素无序。
线性表中的元素按递增有序。
线性表中的元素按递减有序。
八、(10分)线性表中元素存放在向量A(1,…,n)中,元素是整形数。试写一递归算法求出A中的最大和最小元素。
九、(20分)是写一算法判别某二叉树是否是完全二叉树。
十、(15分)写出图的深度优先搜索DFS算法的非递归算法。