题目内容
(请给出正确答案)
[单选题]
下列关于递归错误的说法是()。
A.递归函数可以没有返回值
B.递归算法一定有终结条件
C.递归算法执行时会在内存中自动维护一个工作栈
D.递归算法一定包含循环结构
答案
查看答案
A.递归函数可以没有返回值
B.递归算法一定有终结条件
C.递归算法执行时会在内存中自动维护一个工作栈
D.递归算法一定包含循环结构
第1题
设f是三元原始递归全函数,g定义为
(1)若h(x)=,(8(x,y))=0),则此时称h为 递归函数是否妥当?为什么?
(2)证明下列函数h是μ-递归函数:
第7题
关于kd-树查找算法kdSearch()(教244页算法8.2),试证明以下结论:
a)在树中某一节点发生递归,当且仅当与该节点对应的子区域,与查询区域的边界相交;
b)若令Q(n)=规模为n的子树中与查询区域边界相交的子区域(节点)总数,则有:Q(n)=2+2Q(n/4)=o(√n)。
c)kdSearch()的运行时间为:o(r+√n),其中r为实际命中并被报告的点数。
d)进一步地,试举例说明,单次查询中的确可能有多达Ω(√n)个节点发生递归,故以上估计是紧的。
e)若矩形区域不保证与坐标轴平行,甚至不是矩形(比如圆),则上述结论是否依然成立?
第11题
求解平方根√A的迭代函数定义如下:
其中,p是A的近似平方根,e是结果允许误差。试写出相应的递归算法,并消除递归。