数据结构考研分类复习真题 第三章 答案[6]

（）能得到在依次进栈后和出栈得部分输出序列然后入栈出栈得部分出栈序列入栈并出栈得部分输出序列最后退栈直到栈空得输出序列其操作序列为AAADDAADADDD

（）不能得到输出顺序为的序列部分合法操作序列为ADAAAADDAD得到部分输出序列后栈中元素为在栈顶故不可能先出栈得不到输出序列

（）一个函数在结束本函数之前直接或间接调用函数自身称为递归例如函数f在执行中又调用函数f自身这称为直接递归若函数f在执行中调用函数g而g在执行中又调用函数f这称为间接递归在实际应用中多为直接递归也常简称为递归

（）递归程序的优点是程序结构简单清晰易证明其正确性缺点是执行中占内存空间较多运行效率低

（）递归程序执行中需借助栈这种数据结构来实现

（）递归程序的入口语句和出口语句一般用条件判断语句来实现递归程序由基本项和归纳项组成基本项是递归程序出口即不再递归即可求出结果的部分归纳项是将原来问题化成简单的且与原来形式一样的问题即向着基本项发展最终到达基本项

函数调用结束时vol=执行过程图示如下

过程p递归调用自身时过程p由内部定义的局部变量在p的次调用期间不占同一数据区每次调用都保留其数据区这是递归定义所决定用递归工作栈来实现

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []