早教吧 育儿知识 作业答案 考试题库 百科 知识分享
早教吧考试题库频道 --> 计算机类考试 -->软考中级 -->

用递归算法实现n个相异元素构成的有序序列的二分查找,采用一个递归工作栈时,该栈的最小容量应为(

题目

用递归算法实现n个相异元素构成的有序序列的二分查找,采用一个递归工作栈时,该栈的最小容量应为(11)。

A.n

B.[n/2]

C.[log2n]

D.[log2(n+1)]

参考答案
正确答案:D
解析:根据二分查找的过程,由于需要栈结构实现递归算法,栈的容量应该要保证能存放查找失败时所有未完成运行的算法的活动记录。第一次调用该算法时,栈中加入了一条查找记录,表示待查有序表中元素的个数为n:第二次调用时,无论是在前半区还是在后半区进行查找,栈中又加入了一条查找记录,所确定的查找区间中的元素最多为n/2:第三次调用时,栈中又加入了—条查找记录,所确定的查找区间中的元素最多为n/4。依次类推,当所确定的查找区间中的元素为。时,递归调用该算法的次数为log2(n+1)次,查找结束。
看了用递归算法实现n个相异元素构成...的网友还看了以下:

一家公司为全体员工投保团体人身意外伤害保险,保险金额为每人5万元.按每年保险费率的0.8%计算,每 数学 2020-04-27 …

数学初一不等式,应用题。。!求解!7.某工厰前年有员工280人,去年经过结构改革减员40人,全场年 其他 2020-05-13 …

手工制作电子设备,焊接元件顺序是什么手工制作电子设备,有各种元件焊接元件顺序是什么比如说制作收音机 其他 2020-05-17 …

一家公司为全体员工投保团体人身意外伤害保险,保险金额为每人5万元.按每年保险费率的0.8%计算,每 其他 2020-06-16 …

李老师工作已有12年,手上攒有30万元现金。她将28万元全部投入股市,2万元留在身边以防不时之需。 政治 2020-07-01 …

某工程咨询公司技术部门有总工程师1人,工程师1人,技术员7人,见习技术员1人,现需招聘技术员1人, 数学 2020-07-15 …

1.某种商品的进价是215元,标价是258元,现要最低获得14%的利润,这种商品应最低打几折销售? 数学 2020-07-19 …

工伤休假时间应计入总工时吗员工入职劳动合同约定:“每月基本工时为176小时,底薪1500元,超过基 其他 2020-07-25 …

某公司举行一个游戏,规则如下:有4张背面相同的卡片,分别对应1000元、600元、400元、200元 数学 2020-12-02 …

A公司有经理1名,副经理2名,对外招聘职员5名,A公司称所有员工每月平均工资3200元,如果你去应聘 数学 2020-12-10 …