用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。

admin2019-07-18 50

问题用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。

选项 A、
B、
C、
D、

答案D

解析根据折半查找的过程，由于需要栈结构实现递归算法，栈的容量应该保证能存放查找失败时所有未完成运行的算法的活动记录。
第一次调用该算法时，栈中加入了一条查找记录，表示待查有序表中元素的个数为n；
第二次调用时，无论是在前半区还是后半区查找，栈中又加入了一条查找记录，所确定的查找区间中的元素最多为n／2；第三次调用时，栈中又加入了一条查找记录，所确定的查找区间中的元素最多为n／4；依次类推，当所确定的查找区间中的元素为0时，递归调用该算法的次数为Llog₂n」+1次，查找结束。

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。

计算机408

学硕统考专业

试论19世纪末20世纪初的英德矛盾与三国同盟的形成。

余粮收集制

唐玄宗为密切与少数民族的关系采取的措施有()。

中国政府第一次公开提出和平解决台湾问题的方针是在()。

到1869年为止，人类已发现了多少种化学元素()。

1962，中共中央调整计划目标，工业生产值原定950亿元调为880亿元，钢产量755万吨调为600万吨，并按“经济合理，保留骨干的原则，对企业关停并转。这举措目标

据史记《商君传》商鞅变法，“为田开阡陌封疆，而赋税平”其目的

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

在请求页式系统中，一程序的页面走向(访问串或引用串)为2，3，4，5，2，3，6，2，3，4，5，6，设分配给该程序的存储块数为m。试分别计算m=3和m=4时，FIFO和LRU两种替换算法的缺页(页故障)数，并给出：结果说明了什么?

假单极神经元分布在()

普通股东享有的权利是()。

胃、十二指肠溃疡最基本的病因是

托烷类生物碱类药物的特征鉴别反应为

甲签发一张金额为5万元的本票交收款人乙，乙背书转让给丙，丙将本票金额改为8万元后转让给丁，丁又背书转让给戊。如果戊向甲请求付款，甲只应支付5万元，戊所受损失3万元应向丁和丙请求赔偿。()

材料：下面是某高中政治老师的《思想政治课课堂教学评价表》。问题：请根据思想政治课程教学评价的相关理念，说一说该评价表存在哪些不足。

破釜沉舟：项羽

有如下类定义：classFoo{public：Foo(intv)：value(v){}／／①～Foo(){}／／②private：Foo(){}／／③intvalue=0；／／④}；其中存在语法错误的行是()。

A、Onabusystreet.B、InaHongKonghotel.C、Atanairport.D、Atabookingoffice.C细节推理。男士向别人求助，希望被告知飞往香港的910航班的9号登机口怎么走，即可推断