文档介绍：-
. z.
数据结构模拟试题...
一、简答题（15分，每小题3分）
简要说明算法与程序的区别。
在哈希表中，发生冲突的可能性与哪些因= r [ low ]；
while ( low < high )
{
while ( low < high && r [ ]. key >= *.key )
high - -；
if ( low < high )
{ r [ ] = r [ high ]； low++; }
while ( low < high && r [ ]. key < *. key )
low++;
if ( low < high )
{ r [ ] = r [ low ]； high--; }
}
r [ low ] = *； return low ;
}
2. 假设用循环单链表实现队列，若队列非空，且队尾指针为R, 则将新结点S加入队列时，需执行下面语句：；；R=S；
-
. z.
3．通常是以算法执行所耗费的和所占用的来判断一个算法的优劣。
4．已知一个3行、4列的二维数组A（各维下标均从1开始），如果按"以列为主”的顺序存储，则排在第8个位置的元素是：
5．高度为h的完全二叉树最少有个结点。
五、构造题（20 分）
1．（4分）已知数据结构DS的定义如下，请给出其逻辑结构图示。
DS = (D, R)
D = { a, b, c, d, e, f, g }
R = { T }
T = { <a, b>, <a, g>, <b, g>, <c, b>, <d, c>, <d, f>,
<e, d>, <f, a>, <f, e>, <g, c>, <g, d>, <g, f> }
2．（6分）对以下关键字序列建立哈希表：（SUN, MON, TUE, WED, THU, FRI, SAT）,哈希函数为H(K) =（K中最后一个字母在字母表中的序号）MOD 7。用线性探测法处理冲突，，并计算出在等概率情况下查找成功的平均查找长度。
3.（6分）将关键字序列（3，26，12，61，38，40，97，75，53， 87）调整为大根堆。
4．（4分）已知权值集合为：{ 5，7，2，3，6，9 }，要求给出哈夫曼树，并计算其带权路径长度WPL。
六、算法分析题（10分）
阅读下面程序，并回答有关问题。其中BSTree为用二叉链表表示的二叉排序树类型。
简要说明程序功能。（5分）
n个结点的满二叉树的深度h是多少？（3分）
假设二叉排序树*bst是有n个结点的满二叉树,给出算法的时间复杂度。（2分）
int Proc (BSTree *bst, KeyType K)
{ BSTree f, q, s;
s=(BSTree)malloc(sizeof(BSTNode));
s-> key = K; s-> lchild = NULL; s-> r