（1）画出所构造的哈希表。

（2）在记录的查找概率相等的前提下，计算该表查找成功时的平均查找长度。

（1）画出所构造的哈希表。 —— 9个结点，每个1分 0 ∧ 1 1 14 27 ∧ 2 ∧ 3 29 55 68 ∧ 4 ∧ 5 ∧ 6 ∧ 7 ∧ 8 ∧ 9 ∧ 10 10 23 ∧ 11 11 ∧ 12 ∧ （2）在记录的查找概率相等的前提下，该表查找成功时的平均查找长度，ASL＝（1×4＋2×3＋3×2）/9=16/9 —— 2分

4、程序设计题

1.二叉排序树的结点结构如下所示： typedef struct node { int data;

struct node *lchild,*rchild; }node；

请编写在二叉排序树T中查找值为x的结点的非递归算法，如果查到，返回指向该结点的指针，否则返回空。函数形式为：

node* Search(node *T, int x)。（10分）

///////////////

2.已知整型数组A，从第一个单元（即A[1]）开始存储数据，且一共存储了n个元素。要求编写折半查找元素e的过程。当数组中存在元素e时，返回其下

标，否则返回0。（10分）

int BinarySearch(int *A,int n,int e)

////////////// 参考程序如下：

int BinarySearch(int *A,int n,int e) {

int low,high,mid; low=1;high=n; （1分） while(1) { }

3.已知整型数组A[101]，其中从A[1]到A[100]存储了100个整数，试编写函数int Find(int A[101],int x)，功能为从数组A中折半查找元素x，如果找到则返回x所对应的下标，否则的话返回0。

mid=(low+high)/2; （2分） if(A[mid]==e) （1分） { return mid;} （1分） else if(A[mid]>e) （1分） { } else

{ low=mid+1;} （1分） if(low>high) （2分）

return 0;

high=mid-1; （1分）

}

第10章内部排序

1、填空题

1.快速排序和堆排序的平均时间复杂度分别为________和________。

2、选择题

1.下面给出的四种排序法中( )排序法是不稳定性排序法。 A．插入 B．冒泡 C．二路归并 D．堆排序

2.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为 排序法。 (A)插入 (B)选择 (C)希尔 (D)二路归并

3.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为______排序法。 (A)插入 (B)选择 (C)谢尔 (D)二路归并

3、判断题

1.从平均性能而言，快速排序最佳，其所需时间最省。 （ ）

4、应用题

1. 对于关键字序列{49，38，65，97，76，13}，回答下述问题。（共12分）

（1）写出一趟冒泡排序的结果。（6分） （2）写出一趟快速排序的结果。（6分） 参考答案如下：

（1）写出一趟冒泡排序的结果。（6分） {38,49,65,76,13,97}

（2）写出一趟快速排序的结果。（6分） {13,38,49,97,76,65}

第11章外部排序 第12章文件