下载文档原格式
散列表练习1．设某目录表的关键码序列为{6097，3485，8129，407，8136，6615，6617，526，12287，9535，9173，2134，1903，99}。
其中结点数n=14,基本区大小设计成能容纳19 个结点（负载因子a=14/19）,散列函数设为h(k)=k mod 19。
分别写出：（1）用线性探查法解决碰撞的散列表；（2）用结合的同义词子表法解决碰撞的散列表。
2．设某目录表的关键码序列为{6097，3485，8129，407，8136，6615，6617，526，12287，9535，9173，2134，1903，99}。
其中结点数n=14，散列函数设为h1(k)=k mod 19，h2(k)=k mod 17+1。
试给出用双散列函数探查法处理碰撞的散列表。
３．使用散列函数H(k)=3k mod 11,并采用开放地址法处理冲突，共求下一地址函数为：d1=h(k)d i=(d i-1+7k) mod 11 (I=2,3,…)试在0-10 的散列地址空间中对关键字序列(22,41,53,46,30,13,01,67)构造散列表，并求等概率情况下查找成功的平均查找长度，并设计构造散列表的完整过程。
4．假设有1000 个值小于10000 的正整数，用构造散列表的方法将1000 个正整数按由小到大的次序放入表中。
负载因子a=1，试写出你的排序算法。
5．AK 的故事之英语学习篇程序名： mistake.pas输入文件名： mistake.in输出文件名： mistake.out问题描述：面对竞争日益激烈的社会，AK 深感自己的英语水平实在是太差了，他决定在英语方面下苦工。
这些日子里，AK 每天都要背大量的英语单词，阅读很多英语文章。
终于有一天，AK 很高兴的对自己说：“我的英语已经没问题了！”他决定写一篇英语文章来显示自己的水平……AK 将自己的文章交给了他的英语老师Mr. Zhu，满以为Mr. Zhu 会大加赞赏。
数据结构习题和答案习题课填空1、对于⼀棵⼆叉树，若⼀个结点的编号为i，则它的左孩⼦结点的编号为，双亲结点的编号为。
2、向⼀个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动个元素。
3、在⼀棵⼆叉树中，若双分⽀结点数为5个，单分⽀结点数为6个，则叶⼦结点数为个。
4、为了实现折半查找，线性表必须采⽤⽅法存储。
顺序5、⼀种抽象数据类型包括数据对象和。
6、在以L为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为__________和_______。
7、数据结构被形式地定义为（D, R），其中D是的有限集合，R是D上的有限集合。
8、队列的插⼊操作在进⾏，删除操作在进⾏。
9、⼆叉搜索树的中序遍历得到的结点序列为____ ____。
10、在顺序表中插⼊或删除⼀个元素，需要平均移动元素，具体移动的元素个数与有关。
11、栈的特点是。
12、在单链表中，除了⾸元结点外，任⼀结点的存储位置由。
13、在⼀个具有n个顶点的⽆向图中，要连通所有顶点则⾄少需要条边。
14、深度为k（设根的层数为1）的完全⼆叉树⾄少有个结点，⾄多有个结点。
15、⼀棵深度为6的满⼆叉树有个分⽀结点和个叶⼦结点。
16、⼀个算法的效率可分为效率和效率。
17、队列的特点是。
18、⼀棵深度为5的满⼆叉树中的结点数为个。
19、在⼀个具有n个顶点的⽆向完全图中，包含有________条边，在⼀个具有n个顶点的有向完全图中，包含有________条边。
简答题1、已知⼀组元素为（38，26，62，94，35，50，28，55），画出按元素排列顺序输⼊⽣成的⼀棵⼆叉搜索树。
答:2、假设有⼆维数组A[0..5,0..7]，每个元素⽤相邻的6个字节存储，存储器按字节编址。
已知A的起始存储位置（基地址）为1000，计算：（1）末尾元素A57的第⼀个字节地址为；（2）若按列存储时，元素A47的第⼀个字节地址为。
(3) 数组A的体积（存储量）；(4) 若按⾏存储时，元素A14的第⼀个字节地址为。
