设记录R1，R2，…，Rn按关键字值从小到大顺序存储在数组r[1．．n]中，在r[n+1]处设立一个监督哨，其关键字值为+∞。试写一查找给定关键字k的算法，并画出此查找过程的判定树，求出在等概率情况下查找成功时的平均查找长度。

admin2017-01-04 36

问题设记录R₁，R₂，…，R_n按关键字值从小到大顺序存储在数组r[1．．n]中，在r[n+1]处设立一个监督哨，其关键字值为+∞。试写一查找给定关键字k的算法，并画出此查找过程的判定树，求出在等概率情况下查找成功时的平均查找长度。

选项

答案intSearch(rectype r[]，int n，keytype k){ ／／在n个关键字从小到大排列的顺序表中，查找关键字为k的结点 r[n+1]．key=MAXINT；／／在高端设置监视哨 int i=1： while(r[i]．key＜k)i++； if(r[n+1]．key==k)return(i％(n+1))； else return(0)； } 查找过程的判定树是单枝树。本题中虽然表按关键字有序，但进行顺序查找，查找成功的平均查找长度亦为(n+1)／2。

解析

转载请注明原文地址:https://kaotiyun.com/show/iQRi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

论述斯巴达的阶级结构、政治制度和社会风尚

近代自然科学产生的条件及其发展情况。

十六国时期的历史，可以划分为前后两个时期，其分界线是()。

中国封建社会后期的第一个启蒙学派是由王艮开创的()。

“钟鸣鼎食”往往用来形容贵族生活。考古发现的青铜乐器“钟”始见于周代遗址，可能存在于()

在下面哪本著作中以异化劳动理论的形式阐述了一种新的科学世界观的雏形?()

印度种姓制度中，处于被剥削被压迫地位的两个瓦尔那是()①婆罗门②刹帝利③首陀罗④吠舍

对斯大林时期形成的高度集中的社会主义经济政治体制的叙述，不确切的是()。

高度为4的4阶B树最多可容纳()个关键字(根是第1层)。

“上下来去”政策过程模型的亚模型有()

在分层测试调整配注的过程中，提高注水压力的方法有两种：一是在泵压能够满足注水压力需求的情况下，放大注水；二是()。

组织成员表达情感和情绪的主要途径是()

“碘缺乏病”的概念是Hetzel于哪年正式提出的

根据《建设工程质量管理条例》的规定，()是勘察、设计单位应承担的责任和义务。

在一次联欢晚会上，小李登台表演了一段越剧，博得满堂喝彩。老张道：“小李的越剧唱得这么好，一定是南方人。”以下哪项是老张的话所不包含的意思?()

若f(1＋χ)＝af(χ)总成立，且f′(0)＝b．(a，b为非零常数)则f(χ)在χ＝1处【】

[A]What,precisely,qualifiessomeoneasaworkaholic?There’sstillnosingleacceptedmedicaldefinition.Butpsychologistsh

一个人越是伟大，就越不会去炫耀自己的伟大。