散列习题课
- 格式:pptx
- 大小:113.14 KB
- 文档页数:13
散列表练习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。
试给出用双散列函数探查法处理碰撞的散列表。
3.使用散列函数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的第⼀个字节地址为。