当前位置:首页 >> 计算机软件及应用 >>

数据结构简单问答


1.比较线性探测、随机探测和链地址法解决冲突的优缺点。
?
解:线性探测:简单,但可能导致记录的聚集而使探测效率降低;此外记录的个数必须在哈希表允许的范围内。?
随机探测:可以克服记录聚集的现象,但需要选取合适的随机函数且记录的个数也有限制。?
链地址法:只要空间允许就可插入任意多个记录,并且链表的插入和删除都很方便。?

2.在哈希表存储中,发生哈希冲突的可能性与哪些因素有关?为什么??
答:在哈希表存储中,发生哈希冲突的可能性与装填因子α、所采用的哈希函数、解决冲突的哈希冲突函数三个因素有关。?
这是因为:(1)装填因子α是哈希表中已存入的数据元素n与哈希地址空间大小m的比值,即n/m,显然,当α越小时,冲突的可能性就越小,α越大(最大可取1)时,冲突的可能性就越大;(2)若哈希函数选择得当,就可使哈希地址尽可能均匀地分布在哈希地址空间上,从而减少冲突的发生;否则,若哈希函数选择不当,就可能使哈希地址集中于某些区域,从而加大冲突的发生;(3)若哈希冲突函数选择得当,可以减少再次发生哈希冲突的可能性。??

3.?对含有n个数据元素的集合,要找出最大元素和最小元素,请问最少需要多少次比较运算(执行if语句的次数)。?
答:我们可以设立两个变量max和min用于存放最大元素和最小元素的位置,第一次取两个元素进行比较,大的放入max,小的放入min,从第2次开始,每次取一个元素先和max比较,如果大于max则以它替换max,并结束本次比较;若小于max则再与min相比较,在最好的情况下,一路比较下来都不用和min相比较,所以这种情况下,至少要进行n-1次比较就能找到最大元素和最小元素。(最坏情况下,要进行2n-3次比较才能结果)??

4.请问:对有序的单链表能否进行折半查找?为什么??
答:有序的单链表不能进行折半查找的。因为链表无法进行随机访问,如果要访问链表的中间结点,就必须先从头结点开始进行依次访问,这就要浪费很多时间,






?
5?
还不如顺序查找,而且,用链存储结构将无法判定折半的过程是否结束,因此无法用链表实现折半查找。

相关文章:
数据结构问题
数据结构问题_计算机软件及应用_IT/计算机_专业资料。常见的数据结构问题动态数组...} } 测试结果 简单约瑟夫环: 问题描述罗马人攻占了乔塔帕特,41 个人藏在山洞...
数据结构经典问题和算法分析_图文
数据结构经典问题和算法分析( 数据结构经典问题和算法分析(一)-迭代法 迭代法...这种问题最简单的方法就是找出这个向量 的所有子集,如同找出幂集中的子集 一...
《数据结构(C语言版)》习题指导与解答
数据结构(C语言版)》习题指导与解答_理学_高等...问答题 (1)栈是一种先进后出的线性表, 栈的插入...不可能在链表中间插入和删除结点,算法实现很 简单,...
数据结构 串问答答案
数据结构 串问答答案_学科竞赛_小学教育_教育专区。对数据结构那本书的测试题 ...数据结构简单问答 暂无评价 1页 免费 线性表问答试题 数据... 暂无评价 1页...
《数据结构(C语言版)》习题指导与解答
数据结构(C语言版)》习题指导与解答_理学_高等...问答题 (1) 【解答】 栈是一种先进后出的线性表...不可能在链表中间插入和删除结点,算法实现很简单,...
数据结构经典问题和算法分析
字串 9 数据结构经典问题和算法分析(八)动态规划法八、动态规划法 经常会遇到复杂问题不能简单地分解成几个子问题,而会分解出一系列的子问题。简单地 采用把大...
数据结构课后习题答案
1 绪论 1.1 回答下列概念:数据结构,数据的逻辑结构,数据的存储结构,算法 数据...算法的定性评价标准有:正确性、可读性、健壮性、简单性。 1.6 算法的定量评价...
数据结构教材之习题解答
数据结构教材之习题解答_理学_高等教育_教育专区。数据...问答题 (1) 【解答】 栈是一种先进后出的线性表...不可能在链表中间插入和删除结点,算法实现很简单, ...
数据结构知识点总结(详细无题目)
数据结构知识点总结(详细无题目)_计算机软件及应用_IT/计算机_专业资料。数据...(n*n) O(nlbn) O(n) O(1) O(1) 简单选择排序 稳定 堆排序 基数排序...
数据结构课程设计-学生-21个题目
测试数据】 【测试数据】 由随机数产生器生成 “数据结构”课程设计-指导书 2011-6-2 选题九: 选题九:简单行编辑程序【问题描述】 问题描述】 文本编辑器程序...
更多相关标签: