数据结构试题(3)

3 V

V6V7 8

23、已知某二叉树的前序序列为EBADCFHGI，中序序列为ABCDEFGHI，请给出二叉树的后序序列。（构造出二叉树7分，后序遍历3分，共10分）

24、将关键码53，78，65，17，87，09，81，45，23依次插入到一棵初始为空的二叉搜索树中，画出每插入一个关键码后的二叉搜索树。（9分）

25、设有150个记录要存储到散列表中，并利用线性探查法解决冲突，要求找到所需记录的平均比较次数不超过2次。试问散列表需要设计多大？（设α是散列表的装载因子，则有ASLsucc=（1+1/（1-α））/ 2）。（8分）

五、综合算法题（每小题5分，共15分）

一个一维整数数组A[m]中有n (n≤m)个非空整数，它们相继存放于数组的前端并已按非递减顺序排列，针对下列三种情况，分别编写相应的函数。

26、在数组A[ ]中插入一个新的整数x ，并使得插入后仍保持非递减有序。要求x 插在值相等的整数后面。（5分）

void InsertSort (int A[ ], int m , int & n , int x)

{

}

27、将数组中所有整数原地逆置，即利用原数组空间将数组中全部元素反转。（5分）

void reverse (int A [ ], int n ) { }

28、删除数组中多余的值相等的整数（只保留第一次出现的那个整数）。（5分）

Void delDuplicate (int A [ ] , int & n) { }

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库数据结构试题(3)在线全文阅读。