下星期就要考研了，还有几题不会，大家帮帮忙啊！！！
1.外存储索引为什么采用m阶B树（m> > 2），而不是AVL树？满二叉检索树符合B树定义吗？B-树的插入和删除算法适合于满二叉树吗？为什么？
2.已知存储于数组S中长度n的字符串中含有字母字符，数字字母和空格字符，请使用一中排序算法将所有字母字符移到字符串的前部，将所有空格字符移到字符串的后部。试写出该算法，要求利用字符串的原有空间以及最小时间代价。
3.构造最佳二叉检索树的前提条件是什么?在动态情况下,一般AVL树的查询性能不
如完全二叉检索树的,为什么人们却采用AVL树呢?
4.已知在llink-rlink存储法表示的二叉树中,指针t指向该二叉树的根结点,指针p,q
分别指向树中的二个结点,试写一算法,求距离这两个结点最近的共同的祖先结点.
5.在union-find问题中,控制union操作的权重(weighting)规则是何含义, 有何效
果?控制find操作的倒塌(collapsing)规则是何含义,有何效果?
6.设符号表T重的标识符x满足1 <=x <=m,且n为对T表的最大插入次数.设计符号表T的表
示结构,允许使用O(m+n)空间,并写出T的初始化(init),查找(search),插入
(insert)和删除(delete)算法,要求它们的时间复杂性都是O(1)。
7.最近最少使用(Least-Recently-Used)页替换是虚拟存储系统中常用的策略,试说
明如何利用一页链接表时刻跟踪最近最少使用页?
8.在磁带文件上进行二分查找行吗?为什么?
9.字符序列的子序列由删除该序列任意位置的任意个元素而得.序列x和y的最长公共
子序列记为Lcs(x,y),是x和y的公共子序列,且长度最大.例如,adcbcb是
x=abdcbcbb和y=adacbcb的最长公共子序列.设x长度为n,y长度为m,设计一算法计算
x和y的最长公共子序列的长度,尽可能改进你的算法,使它的时间复杂性为O(n*m).
10.写一改进的递归快速排序算法,要求对于n个记录,该算法的递归深度
<=1+log2(n),并说明你的算法满足这一要求.
11.定义前序排列(preorder permutation)为1,2,……n的全部二叉树的中序排列
(inorder permutation)集合为IP;再定义将1,2,……n从右到左经过一个栈可得到
的全部排列集合为SP.例如,当n=3,SP={123,132,213,231,321}.问:IP包含于SP成立
否?证明你的结论.
12.设胜者树(selection tree)由k个记录缓冲区和k-1个非叶结点构成.概念上非叶
结点表示其两个子女中关键字较小者,而实际上非叶结点存放的是什么?
13.L1={aibj|i> =j> =0},LR（1）文法构造分析表。
14.写出抢占式调度算法的实现。
以上有的是我不会写，有的是我写的答案不敢肯定。
大家帮帮我啊。
[解决办法]
8.不行，因为磁带只能进行顺序访问，不能进行随机访问，不能回溯。
[解决办法]
3.
前提条件是根结点的值应该左右子树值的中间
完全二叉树在插入的时候需要对整个树进行调整，太消耗时间
AVL树能够在插入和最后查找之间找到一个最好的平衡点
[解决办法]
10.写一改进的递归快速排序算法,要求对于n个记录,该算法的递归深度
<=1+log2(n),并说明你的算法满足这一要求
在一般的 快速排序 的基础上，
优化一下 排序终止条件就可以了 ～～
[解决办法]
问题一个一个来，
这样一批发上来，
别人的回复，
你能看清除么？
另外，
应当把你自己的解答也附上 ～～
[解决办法]
//问题好多啊！ 帖一个9的，算法时间复杂度O(m*n),不知道是否满足要求.
#include <iostream>
const int NUM_X = 8; //定义x序列的长度为常量
const int NUM_Y = 7; //定义y序列的长度为常量
int c[NUM_X+1][NUM_Y+1]; //c[i][j]保存(xi,yj)的最长子序列长度
int b[NUM_X][NUM_Y]; //简化最优解的构造
//=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
//计算LCS长度的函数
//=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
template <typename T>
void LcsLength(const T x[NUM_X], const T y[NUM_Y])
{
int m = NUM_X;
int n = NUM_Y;
//如果i=0,或j=0时c[i][j]=0
for(int i=1; i <= m; ++i)
c[i][0] = 0;
for(int j=0; j <= n; ++j)
c[0][j] = 0;
for(int i=1; i <= m; ++i)
{
for(int j=1; j <= n; ++j)
{
if(x[i-1] == y[j-1])
{
c[i][j] = c[i-1][j-1] +1;
b[i-1][j-1] = 1;
}
else if( c[i-1][j] > = c[i][j-1] )
{
c[i][j] = c[i-1][j];
b[i-1][j-1] = 2;
}
else
{
c[i][j] = c[i][j-1];
b[i-1][j-1] = 3;
}
}
}
}
//=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
//输出x,y序列的最长子序列函数
//=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
template <typename T>
void PrintLcs(const T x[NUM_X], int i, int j) //递归调用输出
{
if( i==0 || j==0)
return;
if( b[i-1][j-1] == 1 )
{
PrintLcs(x, i-1, j-1);
std::cout < < " " < <x[i-1] < < " ";
}
else if( b[i-1][j-1] == 2 )
PrintLcs(x, i-1, j);
else
PrintLcs(x, i, j-1);
}
//=============================================================
//主函数
//=============================================================
void main()
{
char x[NUM_X] = { 'a ', 'b ', 'd ', 'c ', 'b ', 'c ', 'b ', 'b ' };
char y[NUM_Y] = { 'a ', 'd ', 'a ', 'c ', 'b ', 'c ', 'b ' };
LcsLength <char> (x, y);
PrintLcs <char> (x, NUM_X, NUM_Y); //输出最长子序列
}
[解决办法]
唉,不懂.顶了.
[解决办法]
考了是哪个学校,怎么考的这么博大啊!
[解决办法]
好多数据结构啊 好多都忘记了!
[解决办法]
8.可以吧,文件是二叉树管理的
[解决办法]
1.m阶B树的平均高度比AVL树小,如果是外存索引,当然要求高度小的,这样可以减少内外存交换的次数.而且I/O操作每次是读一个页进内存,如果你用AVL树,每个结点只有一个关键字,就等于一个页读近来而只用了一个关键字的空间,浪费.m阶B树可以在一个结点尽量安排一个页的数据,这样不会浪费.
满二叉检索树应该是满足B树的,所以可以用B树的算法
[解决办法]
5.第一个问: 控制权重可以使构造出来的树的高度较小,避免了产生退化树的情况,使搜索的平均长度减少.
第二个问忘了,呵呵
[解决办法]
我很想帮助你呀！！可是我才是个大二的学生！都不会呀！祝你考个好成绩！！
[解决办法]
很想帮忙，可惜不是学计算机的。术语基本都不懂。。。只好顶你了
[解决办法]
都忘记了！祝楼主考个好成绩
[解决办法]
看见我都晕了 --b
[解决办法]
哪个学校的题？
我估计就是考试题吧。
一般的学校都会漏题的。
[解决办法]
分点分,考研厉害,我不行
[解决办法]
不懂！！！！！！
