首页 考试资料幻灯片工程技术公务员考试小学教学中学教学大学教学外语资料
数据结构实验书


printf("nThe time of compare is %d",time); } else{ printf("nUnsuccess"); /*查找失败*/

printf("nThe time of compare is %d",time); } printf("nContinue(y/n):n"); ch=getch(); } while (ch=='y' || ch=='Y') ; /*计算表在等概率情况下的平均查找长度,并输出*/ for (stime=0,i=0;i<n;i++) { search(HAXI,ST[i].key,m,&time); stime+=time; }; printf("nThe Average Search Length is%5.2f",(float)stime/n); ch=getch(); } 【测试数据】 1. 按运行提示输入数据(关键字集合)ST,建立 HAXI 表,然后进行多次查找。 Please input n && m(n<=m):12 15 19 14 23 01 68 20 84 27 55 11 10 79 The haxi Table is: 0 1 2 14 3 4 5 6 7 8 9 10 11 12 13 14 /*是否继续查找 yes or no*/

1 68 27 55 19 20 84 79 23 11 10

Input the key you want to search:27 Success,the position is 4 The time of compare is 4; Continue(y/n):y Input the key you want to search:68 Success,the position is 3

The time of compare is 1; Continue(y/n):n The Average Search Length is 2.5 2. 读者可根据运行提示,自己输入数据建立哈希表,然后进行多次查询,注意观察运行结果,对照分析, 以加深学习体会。 【说明】 1. 以上程序采用动态分配的顺序存储结构来表示哈希表,其优越性在于可根据输入的哈希表长动态分配哈 希表所需的存储单元,使得存储单元的应用更为合理。当然,如果事先能确定哈希表长,或你所设计的哈 希表的长度变化不大,你也可采用静态分配的一维数组来表示哈希表,这样在设计函数参数的形式上会简 单一些。 2. 以上程序的功能是对一批关键字集合采用除留余数法和线性探测再散列的方法解决冲突来建立相应的 哈希表和完成查找过程及平均查找长度的计算, 也可选择其它的哈希函数和解决冲突的方法来建立哈希表。 3. 读者结合自己的理解对上述程序进行验证和完善。 【实验题】 1. 对同样一组关键字集合,不同的 HAXI 表长 m,执行以上程序,对应不同的 HAXI 函数,形成不同的 HAXI 表,注意分析和观察运行结果,特别是平均查找长度值的变化; 2. 采用二次探测再散列/链地址法构造哈希表和修改查表程序; 3. 已知哈希表的装填因子小于 1,哈希函数 H(key)为关键字(标识符)的第一个字母在字母表中的序号, 处理冲突的方法为线性探测再散列法。试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。 4. 设有一个 100× 100 的稀疏矩阵,稀疏因子为 0.005,现要求用 HAXI 表作存储结构,对给定非 0 元的行、 列值确定元素在 HAXI 表上的位置,处理冲突的方法可采用开放定址法。试设计这个 HAXI 表并编写相应 的算法。</P><P>

第五节 思考题
1. 设哈希表为 HT[0..12],即表的大小为 m=13。现采用双哈希法解决冲突。哈希函数和再哈希函数分别为: H0(key)=key%13; 注:%是求余数运算(=mod) Hi=(Hi-1+REV(key+1)%11+1)%13; i=1,2,3,…,m-1,

(其中函数 REV(x)表示颠倒 10 进制数 x 的各位,如 REV(37)=73,REV(7)=7 等) 若插入的关键码序列为{2,8,31,20,19,18,53,27} (1)试写出插入这 8 个关键值的哈希表; (2)计算查找成功的平均查找长度 ASL。 (摘自清华大学 2000 年硕士生入学考试, 《数据结构与程序设计》试题)

【简要分析】首先计算每个关键码的直接哈希函数值(即直接哈希地址) ,然后根据冲突解决方法将这些关 键值插入哈希表中。至于平均查找长度的计算,也是结合以上所讲的查找过程,求出平均查找长度 ASL。 2. 在排序连续顺序文件中采用折半查找方法来查找记录是否存在的过程可以借助于一棵平衡二叉树(也称 判定树)来模拟,树中结点的值为记录在文件中的位置序号。 (1) 若文件中有 l9 个记录,请画出这棵判定树; (2) 当文件中有 n 个记录时,求出该判定树的深度。 (摘自北京航空航天大学 1999 年硕士生入学考试, 《数据结构》试题) 【简要分析】结合有序顺序表的折半查找方法形成折半查找树,根据折半查找的过程,可以知道折半查找 树是一棵平衡二叉树。根据结点所在的层次,知道结点在查找成功时的平均查找长度。有 n 个结点的折半 查找树的深度与有 n 个结点的完全二叉树的深度是相同的。 3. 用序列(46,88,45,39,70,58,101,10,66,34)建立一个排序二叉树,画出该树,并求在等概 率情况下查找成功的平均查找长度。 (摘自北京邮电大学 1999 年硕士生入学考试, 《数据结构》试题) 【简要分析】这道题目比较简单,只要掌握本章第三节有关二叉排序树的特点和结点的插入过程,读者不 难画出这棵二叉排序树,并计算平均查找长度。 4. 给定关键码序列(26,25,20,33,21,24,45,204,42,38,29,31) ,要用散列法进行存储,规定 负载因子 a=0.6。 (1) 请给出除留余数法的散列函数; (2) 用开放定址法的线性探测再散列解决碰撞,请画出插入所有的关键码后得到的散列表,并指出发生 碰撞的次数。 (摘自北京大学 1997 年硕士生入学考试, 《数据结构》 试题) 【简要分析】 已知负载因子 a=0.6 和关键码的个数 n, 首先计算出哈希表的长度 m,然后选择 p(p 为小于或等 于 m 的最大质数),构造合适的哈希函数。 5. 设二叉排序中关键字由 l 至 1000 的整数构成,现要检索关键字为 363 的结点 (1) 下述关键字序列中哪些可能是二叉排序树上搜索得到的序列,哪些不可能是二叉排序树上搜索到的 序列? 2,252,401,398,330,344,397,363 924,220,911,244,898,258,362,363 925,202,911,240,912, 45,363 2,399,387,219,266,382,381,278,363

(2) 通过对(1)的分析,写一个算法判定给定的关键字序列(假定关键字互不相同)是否可能是二叉排序树 的搜索序列。若可能是返回真,否则返回假。可假定被判定的序列己存入数组中。 【简要分析】这道题目主要考察二叉排序树的构造和查找过程。 6.设计一个程序读入一个字符串,统计该字符串中出现的字符及其次数,然后以表的形式输出结果。要求 用一个二叉树来保存处理结果,字符串中的每个不同的字符用树中不同的结点描述,每个结点包含四个域, 格式为: 字符 该字符的出现次数 指向 ASCII 码小于该字符的左子树指针 指向 ASCII 码大于该字符的右子树指针 因此程序的功能是依次从输入字符串中取出一个字符,把它们插入到树中(新出现字符)或修改原树中相 应结点的“出现次数域”(已出现字符) 。 (中科院计算机技术研究所 1996 年硕士生入学试题) 【简要分析】这道题目也是考察二叉排序树的构造和查找过程,以及结点的插入和删除算法。

123456789101112131415161718192021222324252627282930

 


 

  【Top

最新搜索

 


 

热点推荐