上海交通大学2000年研究生入学试题
一. 模式匹配算法是在主串中快速寻找模式的一种有效的方法.如果设主串的长度为m，模式的长度为n，则在主串中寻找模式的KMP算法的时间复杂度是多少？如果，某一模式 P=’abcaacabaca’，请给出它的NEXT函数值及NEXTVAL的值。
二. 请推导出在伪随机探测，再散列情况下，在长度为m的哈希表中，装填有n个记录时查找不成功的平均查找长度的公式。注意：假定哈希表函数试均匀的。即产生表中的各个地址的概率相等；处理冲突后产生的地址是随机的，装载系数为：α=n/m.
三. 一棵三次有序树其前序，后序的周游结果为：
前序：A,B,C,D,E,F,G,H,I
后序：B,C,G,H,F,E,I,D,A
则该三次有序数用图形表示为什么？
四．含有n个关键字的m阶B_树的最大深度是什么？请证明。
五．请填充下面的表格：（以大O表示）
最好的情况的时间复杂度 最坏的情况的时间复杂度 平均情况下的时间复杂度 额外空间的需求
快速排序
堆排序
直接插入排序
简单选择排序
六． 利用比较的方法进行排序，在最坏的情况下，能达到的最好时间复杂度是什么？请给出详细证明。
七．设有序表的长度为n=(2^h)-1( 表示为2的h次幂 h 为正整数 如h=1,2,3,……).假设表中每个记录的查找概率相等，则查找成功时的平均查找长度为多少？请证明。在查找不成功时，和表中的记录进行比较的次数最多时多少？请证明。
八．某算法所需要的时间由下述方程表示，试求出算法的时间复杂性的级别（以大O表示）。
注意n 为求解问题的规模，为简单起见，设n是2的正整数幂。
1 如果 n=1
T(n)=
2T(n/2)+n 当 n >1
九．用置换选择排序法产生文件 F（长度为 n）的初始并归段设内存缓冲区的长度为m， （1）平均情况下，初始归并段的长度为多少？为什么？ （2）初始归并段的长度最长与最短时，其长度分别为多少？在和情况下出现，简单解释一下。
十 设中序穿线二叉树的结点由五个域构成
info:给出结点的数据场之值。
LL：当lt 为1 时，这给出该结点的左儿子之地址，当lt为0时，则给出按中序遍历的前驱结点的地址。
LT:标志域为0或为1。
RL：当RT为1时，则给出该结点的右儿子的地址；当RT为0时，则给出按中序遍历的后继结点的地址。
RT: 标志域为0或为1。
请编写程序，在具有上述结点结构的中序穿线二叉树上，求某一结点P的按后序遍历次序的后继结点的地址Q，设该中序穿线二叉树根结点的地址为r.另外请注意必须满足：（1）提升空间的使用只能为O(1),(2)程序为非递归。
十一 . 设排序二叉树中结点的结构为下述三个域结构:
data: 给出结点数据的值
left: 给出本结点的左儿子结点的地址
right: 给出本结点的右儿子结点的地址
设data 域为正整数，该二叉树数据结点地址为T。 现给出一个正整数x。请编写非递归程序，实现将data域的值小于等于的结点x全部删除掉.
十二。 设两棵二叉树的的根结点地址分别为p和q，采用二叉链表的形式存储这两棵树上的结点。请编写程序， 判断它们是否相似。
一. 模式匹配算法是在主串中快速寻找模式的一种有效的方法.如果设主串的长度为m，模式的长度为n，则在主串中寻找模式的KMP算法的时间复杂度是多少？如果，某一模式 P=’abcaacabaca’，请给出它的NEXT函数值及NEXTVAL的值。
二. 请推导出在伪随机探测，再散列情况下，在长度为m的哈希表中，装填有n个记录时查找不成功的平均查找长度的公式。注意：假定哈希表函数试均匀的。即产生表中的各个地址的概率相等；处理冲突后产生的地址是随机的，装载系数为：α=n/m.
三. 一棵三次有序树其前序，后序的周游结果为：
前序：A,B,C,D,E,F,G,H,I
后序：B,C,G,H,F,E,I,D,A
则该三次有序数用图形表示为什么？
四．含有n个关键字的m阶B_树的最大深度是什么？请证明。
五．请填充下面的表格：（以大O表示）
最好的情况的时间复杂度 最坏的情况的时间复杂度 平均情况下的时间复杂度 额外空间的需求
快速排序
堆排序
直接插入排序
简单选择排序
六． 利用比较的方法进行排序，在最坏的情况下，能达到的最好时间复杂度是什么？请给出详细证明。
七．设有序表的长度为n=(2^h)-1( 表示为2的h次幂 h 为正整数 如h=1,2,3,……).假设表中每个记录的查找概率相等，则查找成功时的平均查找长度为多少？请证明。在查找不成功时，和表中的记录进行比较的次数最多时多少？请证明。
八．某算法所需要的时间由下述方程表示，试求出算法的时间复杂性的级别（以大O表示）。
注意n 为求解问题的规模，为简单起见，设n是2的正整数幂。
1 如果 n=1
T(n)=
2T(n/2)+n 当 n >1
九．用置换选择排序法产生文件 F（长度为 n）的初始并归段设内存缓冲区的长度为m， （1）平均情况下，初始归并段的长度为多少？为什么？ （2）初始归并段的长度最长与最短时，其长度分别为多少？在和情况下出现，简单解释一下。
十 设中序穿线二叉树的结点由五个域构成
info:给出结点的数据场之值。
LL：当lt 为1 时，这给出该结点的左儿子之地址，当lt为0时，则给出按中序遍历的前驱结点的地址。
LT:标志域为0或为1。
RL：当RT为1时，则给出该结点的右儿子的地址；当RT为0时，则给出按中序遍历的后继结点的地址。
RT: 标志域为0或为1。
请编写程序，在具有上述结点结构的中序穿线二叉树上，求某一结点P的按后序遍历次序的后继结点的地址Q，设该中序穿线二叉树根结点的地址为r.另外请注意必须满足：（1）提升空间的使用只能为O(1),(2)程序为非递归。
十一 . 设排序二叉树中结点的结构为下述三个域结构:
data: 给出结点数据的值
left: 给出本结点的左儿子结点的地址
right: 给出本结点的右儿子结点的地址
设data 域为正整数，该二叉树数据结点地址为T。 现给出一个正整数x。请编写非递归程序，实现将data域的值小于等于的结点x全部删除掉.
十二。 设两棵二叉树的的根结点地址分别为p和q，采用二叉链表的形式存储这两棵树上的结点。请编写程序， 判断它们是否相似。