数据结构模拟试题
一、从下列有关树的叙述中选出5条正确的叙述(10分)
（1）栈与队列都是限制存取点的表，只是它们的存取特征不一样。

（2）高度为h的k叉树至多有kh-1个结点。

（3）由树的中序表示和前序表示可以导出树的后序表示。

（4）将一棵树转换为二叉树表示后,该二叉树的根结点没有右子树。

（5）一棵含有n个结点的完全二叉树，它的高度为élog2n ù+1。

（6）采用二叉树来表示树时，树的先根次序遍历结果与其对应的二叉树的前序遍历结果是一样的。

（7）在二叉树中插入新结点，该二叉树就不再是二叉树了。

（8）一棵Huffman树是带权路径长度最短的扩充二叉树，权值较大的外结点离根较（9）在用k叉链表示的n个结点的k叉树中,空的链指针有n*(k-1)+1个。

（10）用一维数组存储树时，总是以先根遍历的次序存储结点。

二、单项选择题（15分）
1．最佳二叉搜索树是（）
A 关键码个数最少的二叉搜索树。

B 搜索时平均比较次数最少的二叉搜索树。

C 所有结点的左子树都为空的二叉搜索树。

D 所有结点的右子树都为空的二叉搜索树。

2．倒排表的主要优点在于（）
A 便于进行插入、删除运算。

B 便于进行文件的合并。

C 能大大提高基于忏悔的查找的速度。

D 能大大节省存储空间。

3．设有两个串p和q，求q在p中首次出现的位置的运算称作（）
A 连接
B 模式匹配
C 求子串
D 求串长
4.设只含根结点的二叉树的高度为0,则高度为k的二叉树的最大结点数为( )
A 2k
B 2k+1-1
C 2k -1
D 2k-1-1
5．在已知待排序文件已基本有序的前提下，效率最高的排序方法是（）
A 直接插入排序
B 直接选择排序
C 快速排序
D 归并排序
三、回答下列有关二叉搜索树的问题。

（15分）
（1）直接在二叉搜索树中查找关键码K与从中序遍历输出的有序序列中用折半搜索法查找关键码K，其数据比较次数是否相同？
（2）对于同一组有n个关键码的集合,以不同的输入序列建立二叉搜索树，有多少种不同的二叉搜索树？
（3）若输入关键码序列是一个有n个结点的有序序列,以此构造二叉搜索树，它的搜索成功的平均搜索长度是多少？
四、求解下列有关散列的问题。

（30分）
(1)(5分)设已有13个关键码,将它们散列到一个散列表HT中.采用双散列法解决冲突，要求在表中插入新关键码的平均搜索次数不超过3次。

试问该散列表的大小m应设计多大？（双散列解决冲突时的ASLsucc=-loge(1-α)/α,ASLunsucc=1/(1-α)
(2)(8分)用除留余数法设计散列函数和寻找下一个空位时所用的再散列函数。

五、下面的程序是在快速排序中对数组list[low..high]进行一趟划分的算法。

template <class Tyte> int Partition (datalist <Type> &list,const int low,const int high)
{
int pivotpos=low; Element <Type> pivot=list.Vector[low]; //基准对象for ( int i=low+1; i<=high; i++) //检测整个序列，进行划分
if (list.V ector[i].getKey( )< pivot.getKey( )) //小于基准的交换到左侧去
Swap (list.V ector[++pivotpos], list.V ector[i] );
Swap (list.Vector[low], list.Vector[pivotpos] ); //将基准对象就位
return pivotpos ; //返回基准对象位置
}
（1）（10分）若待排序数组中的数据为{10，20，30，40，50，60，70}和{70，60，50，40，30，20，10}，试分别统计该划分算法的数据比较次数和数据移动次数。

（2）（5分）能否对算法稍加修改，使得对{10，20，30，40，50，60，70}和{70，60，50，40，30，20，10}，使用划分算法的数据比较次数和数据移动次数相同。

六、画出在一个初始为空的A VL树中依次插入
{16，3，7，11，9，26，18，14，15}时每一步插入后A VL树的形态。

若做了某种旋转，说明旋转的类型。

然后给出在这棵插入后得到的A VL树中删去根结点后的结果。

（15分）。