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

数据结构简单问答


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

赞助商链接
相关文章:
《数据结构(C语言版)》习题指导与解答
数据结构(C语言版)》习题指导与解答_理学_高等...问答题 (1) 【解答】 栈是一种先进后出的线性表...不可能在链表中间插入和删除结点,算法实现很简单,...
《数据结构(C语言版)》习题指导与解答
数据结构(C 语言版)附录 2 习题指导与解答 附录 ...问答题 (1)栈是一种先进后出的线性表, 栈的插入...不可能在链表中间插入和删除结点,算法实现很 简单,...
数据结构教材之习题解答
数据结构教材之习题解答_理学_高等教育_教育专区。数据...问答题 (1) 【解答】 栈是一种先进后出的线性表...不可能在链表中间插入和删除结点,算法实现很简单, ...
数据结构习题解答(新)
11.在有些书里,数据的“存储结构”也称为数据的...A.8 B.15 C.16 D.32 三、问答 1.试问满...2.试述简单回路、回路两者间的联系与不同。 答:...
线性表问答试题 数据结构
数据结构复习题:线性表 问答题 1、线性表有两种存储结构:一是顺序表,二是链表。试问: (1)两种存储表示各有哪些主要优缺点? (2)如果有 n 个线性表同时并存,...
数据结构之线性表详细解答
线性表问答答案 数据结... 暂无评价 3页 免费 线性表问答试题 数据结... 暂无...详细讲解先行结构。线性表是最简单、最基本、也是最常用的一种线性结构。它有...
更多相关标签: