精品文档

4．使用哈希函数H(key)=key % 11，把一个整数值转换成哈希表下标，现要把数据1、13、12、34、38、33、27、22插入到哈希表（表1）中。

（1）使用线性探测再散列法构造哈希表，请在表1所示的哈希表中与哈希地址对应的位置上，填写出相应的关键字值和元素插入时的探查次数。

（2）假设查找每个元素的概率相同，求出查找成功时的平均查找长度。 表1 哈希 0 1 2 3 4 5 6 7 8 9 10 地址 关键 字值 探查 次数

四、算法阅读题（每小题9分，共18分）

得分

1、完成二叉树按层遍历的算法。 void leveltravel ( struct treenode *bt) { struct treenode *p,*a[n]; int rear=front = -1; p=bt;

rear =__________; a[rear]=p;

while (rear != front) { front = ___________; p=a[front];

printf(“%c”,p->data);

If ( p->left !=null) { rear =(rear +1)% n

收集于网络，如有侵权请联系管理员删除

------------------------------装---------------------------------------------订----------------------------------------线---------------------------------------- 答 题 勿 超 装 订 线 精品文档

a[rear]= _________; }

If (p->right!= null) {rear = (rear +1)%n ; a[rear]=_________; } } }

2、下面算法是对直接插入排序算法的改进，请填写完整 void weizhisort(struct node r[ n+1],int n) { int low,high,mid,j,i; for(i=2;i<=n;i++) { r[0]=r[i];

low=__________; high=_________; while(low<=high)

{ mid=(low+high)/2; if(r[0].key

for(j=i-1;j>=low;j--) r[j+1]=r[j]; r[low]=r[0]; }}

五、算法设计题（每小题10分，共20分）

1、 已知二叉树中的结点类型BinTreeNode定义为：

struct BinTreeNode{ElemType data；BinTreeNode *left，*right}；

其中data为结点值域，left和right分别为指向左、右子女结点的指针域。 请写一函数，功能是返回二叉树BT中值为x的结点所在的层号。 Int NodeLevel(BinTreeNode * BT，ElemType X) {

收集于网络，如有侵权请联系管理员删除

精品文档

} NodeLevel

2、从一维数组A[n]中二分查找关键字为K的元素的递归算法，若查找成功则返回对应元素的下标，否则返回一1。

int Binsch(ElemType A[]，int low，int high，KeyType K) {

} Binsch

收集于网络，如有侵权请联系管理员删除