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

admin2019-07-18 72

问题用递归算法实现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

学硕统考专业

试论雅尔塔体制与冷战起源的关系。

下列选项中，控制了西域政权的是()。

同盟会成立后的第一次大规模的武装起义是()。

1940年毛泽东的《新民主主义论》:“而所谓民主主义，现在已不是旧范畴的民主主义，已不是日民主主义，而是新范畴的民主主义，而是新民主主义”。毛泽东分民主革命的两个阶段主要依据是

在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(logn)的算法，确定树中第k个结点的位置。

一组记录的关键字为{25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。

在一个双链表中，在p结点之前插入q结点的操作是()。

外显成本是指企业的()

社会历史发展最主要的推动者是

“撤消”命令与快捷键Ctrl＋Z具有同样的功能，当不小心执行错误操作时，可采用“撤消”命令予以补救。()

下列哪些不是房间隔缺损的特征表现

尿淀粉酶增加多见于()。

税法规定的起征点是对纳税对象中的一部分给予减免，只就减除后剩余的部分计征税款。()

简述幼儿思维方式发展变化的趋势。

某日用商品店原需采购洗发水和沐浴露共100瓶，后来调整了采购量，使沐浴露增加12瓶，洗发水减少10％，结果总数增加了8瓶。那么，该商店实际采购沐浴露：

Theyoungemployeehasa(n)________quality—heistotallyhonest.

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

计算机408

学硕统考专业

试论雅尔塔体制与冷战起源的关系。

下列选项中，控制了西域政权的是()。

同盟会成立后的第一次大规模的武装起义是()。

1940年毛泽东的《新民主主义论》:“而所谓民主主义，现在已不是旧范畴的民主主义，已不是日民主主义，而是新范畴的民主主义，而是新民主主义”。毛泽东分民主革命的两个阶段主要依据是

在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(logn)的算法，确定树中第k个结点的位置。

一组记录的关键字为{25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。

在一个双链表中，在*p结点之前插入*q结点的操作是()。

外显成本是指企业的()

社会历史发展最主要的推动者是

“撤消”命令与快捷键Ctrl＋Z具有同样的功能，当不小心执行错误操作时，可采用“撤消”命令予以补救。()

下列哪些不是房间隔缺损的特征表现

尿淀粉酶增加多见于()。

税法规定的起征点是对纳税对象中的一部分给予减免，只就减除后剩余的部分计征税款。()

简述幼儿思维方式发展变化的趋势。

某日用商品店原需采购洗发水和沐浴露共100瓶，后来调整了采购量，使沐浴露增加12瓶，洗发水减少10％，结果总数增加了8瓶。那么，该商店实际采购沐浴露：

Theyoungemployeehasa(n)________quality—heistotallyhonest.

在一个双链表中，在p结点之前插入q结点的操作是()。