数据结构与算法—递归与非递归转换

递归数据结构
递归是一种解决问题的方法，其中一个函数通过调用自身来解决更小规模的子问题。

在数据结构方面，递归可以应用于以下几个常见的数据结构：
1. 数组：使用递归可以遍历数组中的每个元素，或者对数组进行排序、搜索等操作。

2. 链表：递归可以用于链表的反转、合并等操作。

也可以通过递归来遍历链表中的每个节点。

3. 树：树是递归定义的数据结构，因此递归在树的操作中非常常见。

递归可以用于树的遍历（如前序、中序、后序遍历）、搜索、插入、删除等操作。

4. 图：递归可以应用于图的遍历算法，如深度优先搜索（DFS）和广度优先搜索（BFS）。

在递归的实现中，通常需要定义递归的基本情况（即递归的终止条件）和递归的递推关系（即如何将原问题转化为更小规模的子问题）。

同时，需要注意递归的限制，避免出现无限递归的情况。

总而言之，递归在解决数据结构相关问题时非常有用，可以简化问题的复杂性，但也需要注意递归的边界条件和限制。

数据结构论文——递归算法的讨论所谓递归算法是把问题转化为规模缩小了的同类问题的子问题。

然后递归调用函数（或过程）来表示问题的解。

一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数)。

递归过程一般通过函数或子过程来实现。

递归方法：在函数或子过程的内部，直接或者间接地调用自己的算法。

递归算法是一种直接或者间接地调用自身算法的过程。

在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。

递归算法解决问题的特点：(1) 递归就是在过程或函数里调用自身。

(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。

(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。

递归次数过多容易造成栈溢出等。

所以一般不提倡用递归算法设计程序。

下面就让我们结合例子详细讨论一下递归算法。

一、递归算法的原理递归算法简单的说就是在函数中调用函数自身，不断调用，直到满足函数得出计算结果(某个条件)。

因为其需要不断循环的调用自身，所以称为递归调用。

递归的原理,其实就是一个栈(stack), 比如求5的阶乘,要知道5的阶乘,就要知道4的阶乘,4又要是到3的,以此类推,所以递归式就先把5的阶乘表示入栈, 在把4的入栈,直到最后一个,之后呢在从1开始出栈, 看起来很麻烦,确实很麻烦,他的好处就是写起代码来,十分的快,而且代码简洁,其他就没什么好处了,运行效率出奇的慢。

还有一个十分形象的例子：从前有座山，山里有个庙，庙里有个老和尚正在讲故事：从前有座山，山里有个庙，庙里有个老和尚正在讲故事：从前有座山，山里有个庙，庙里有个老和尚正在讲故事……如此循环往复到最终的要求。

递归分为2种，直接递归和间接递归。

直接递归，比如方法A内部调用方法A自身。

间接递归，比如方法A内部调用方法B，方法B内部调用方法C，方法C 内部调用方法A。

将数组转换成树形的方法将数组转换成树形结构是一种常见的操作，这在数据处理和算法设计中经常用到。

本文将介绍一种有效的方法，帮助读者理解并掌握这个过程。

一、什么是树形结构？树形结构是一种非线性的数据结构，由多个节点（node）组成，这些节点通过边（edge）相连。

每个节点可以有零个或多个子节点，而根节点是这颗树的起点。

树形结构常常用来表示层次关系或者组织结构。

二、数组与树的关系在计算机中，数组是一种线性的数据结构，由一组连续的内存单元组成。

数组的元素可以通过索引（index）来访问，索引从0开始递增。

数组和树之间的转换可以看作是将线性结构转换成非线性结构的过程。

三、转换方法将数组转换成树形结构的方法可以分为递归和非递归两种。

1. 递归方法递归方法是一种简洁而直观的转换方式。

首先，我们需要定义一个递归函数，用来创建节点并连接它们的子节点。

递归函数的输入参数通常包括数组、起始索引和结束索引。

在函数的内部，我们可以通过判断起始索引和结束索引的关系，来确定递归的终止条件。

当起始索引等于结束索引时，说明已经到达叶子节点，不需要再创建子节点了。

否则，我们可以计算出数组中间位置的索引，并根据该索引创建当前节点，并递归调用函数创建左子树和右子树。

2. 非递归方法非递归方法是一种迭代的转换方式。

我们可以借助一个栈（stack）来保存节点和索引的信息。

开始时，我们将根节点入栈，并初始化起始索引和结束索引。

然后，我们进入一个循环，直到栈为空为止。

在循环中，我们首先从栈中弹出一个节点，并获取它的索引。

然后，我们根据索引计算出左子树和右子树的起始索引和结束索引，并创建相应的节点。

最后，我们将新创建的节点入栈，并更新起始索引和结束索引。

通过这种方式，我们可以逐步构建出树形结构。

四、示例分析为了更好地理解数组到树的转换过程，我们以一个具体的示例来说明。

假设有一个数组 arr = [1, 2, 3, 4, 5, 6, 7]，我们希望将其转换成树形结构。

武汉大学数据结构考试题(附答案)编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（武汉大学数据结构考试题(附答案)）的内容能够给您的工作和学习带来便利。

同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。

本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快业绩进步，以下为武汉大学数据结构考试题(附答案)的全部内容。

1. 下面程序段的执行次数为（ A ）for(i=0；i＜n-1；i++)for(j=n；j＞i;j--)state；A. n(n+2）2 B 。

（n-1)(n+2）2 C。

n(n+1)2 D. （n-1)(n+2)2。

一个向量第一个元素的存储地址是100,每个元素的长度为2，则第5个元素的地址是（ B ）A. 110 B 。

108 C. 100 D. 1203. 一个栈的入栈序列是a,b,c，d，e，则栈的不可能的输出序列是（ C ）A。

edcbaB 。

decba C. dceab D. abcde4。

循环队列用数组A[0，m－1]存放其元素值，已知其头尾指针分别是front和rear,则当前队列中的元素个数是（ D ）A. (rear-front+m）％m B .read—front+1C. read-front—1 D. read—front5．不带头结点的单链表head为空的判定条件是（ A ）A. head=NULL B .head—next=NULLC. head-next=head D。

head！=NULL6．在一个单链表中，若p所指的结点不是最后结点,在p之后插入s所指结点，则执行（B)A。

s-next=p;p—next=s； B .s-next=p—next;p—next=s; C。

s—next=p—next;p=s； D. p—next=s;s-next=p;7. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较多少个结点（ D ）A. n B .n2 C。

填空题（10 ＊1' = 10’）一、概念题2。

2。

当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。

2.3.当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。

2。

6。

带头结点的单链表L中只有一个元素结点的条件是L—〉Next-〉Next==Null。

3.6.循环队列的引入,目的是为了克服假溢出。

4.2。

长度为0的字符串称为空串。

4.5.组成串的数据元素只能是字符。

4.8。

设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。

7。

2。

为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。

5。

7。

广义表的深度是广义表中括号的重数7。

8.有向图G可拓扑排序的判别条件是有无回路.7。

9。

若要求一个稠密图的最小生成树,最好用Prim算法求解.8。

8。

直接定址法法构造的哈希函数肯定不会发生冲突。

9.2。

排序算法所花费的时间,通常用在数据的比较和交换两大操作.1.1.通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量.1。

2.对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。

1.3。

存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。

1.4。

抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。

1.5.一个算法具有五大特性:有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。

2.8.在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s->prior= p->prior; s—〉next= p; p-〉prior—next= s; p-〉prior= s;。

2.9。

在单链表中设置头结点的作用是不管单链表是否为空表,头结点的指针均不空，并使得对单链表的操作（如插入和删除）在各种情况下统一.3。

第3章栈和队列3.1栈一、填空题1. 线性表、栈和队列都是________ 结构，可以在线性表的__________ 位置插入和删除元素；对于栈只能___________插入和删除元素；对于队列只在 ____________ 插入元素，并且只在____________ 删除元素。

2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为____________ 。

不允许插入和删除运算的一端称为_________ 。

3. 向栈中压入元素的操作是先____________ ，后 _______ 。

4. 从栈中弹出元素的操作是先____________ ，后 ________ 。

二、选择题：1. （）栈中元素的进出原则是（）。

A.先进先出 B .后进先出C .栈空则进D .栈满则出2. （）若已知一个栈的入栈序列是1 , 2, 3,…，n,其输出序列为pl, p2, p3,…，pn,若p仁n,贝U pi为（）。

A. i B . n=i C . n-i+1 D .不确定3. （）判定一个栈ST （最多元素个数为m0）为空的条件是（）。

A. ST->top<>0 B . ST->top=0 C . ST->top<>mO D . ST->top=mO4. （）有六个元素1,2,3,4,5,6 的顺序进栈，问下列哪一个不是合法的出栈序列？（）A. 1,2,3,4,5,6B. 5,4,3,2,1,6C. 4,3,2,1,5,6D. 6,5,4,3,1,25. （）将递归算法转换成非递归算法时，通常要借助的数据结构是（）。

A.线性表B. 栈C. 队列D. 树6. （）若栈采用顺序存储方式存储，现两栈共享空间V[1..m] , top[i]代表第i个栈（i =1,2）栈顶,栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。

A. |top[2]-top[1]|=0B. top[1]+1=top[2]C. top[1]+top[2]=mD. top[1]=top[2]7. （）一个递归算法必须包括（）。

递归是一种强大的编程技术，它允许函数在其定义中调用自身。

然而，递归并不是解决所有问题的最佳方法。

有时，使用迭代（即循环）或其他算法可能会更有效，更简洁，甚至更快。

下面是一些可以替代递归的算法和方法。

1. 迭代
迭代是递归的一种常见替代方法。

在许多情况下，递归函数可以通过使用循环（如for 循环或while循环）来重写。

迭代通常比递归更容易理解和调试，并且对于某些问题，迭代可能比递归更有效。

2. 动态规划
动态规划是一种用于解决递归问题的强大技术。

它通过将问题的解决方案存储在一个表（或其他数据结构）中，避免了递归中的重复计算。

这种方法通常比递归更快，因为它避免了不必要的重复计算。

3. 尾递归优化
尾递归是一种特殊的递归形式，其中递归调用是函数体中的最后一个操作。

一些编程语言（如Haskell）对尾递归进行了优化，使其具有与迭代相同的效率。

然而，并非所有编程语言都支持这种优化，因此尾递归可能并不总是最佳选择。

4. 栈模拟
对于某些递归问题，可以通过使用栈来模拟递归调用栈。

这种方法允许我们以迭代的方式模拟递归过程，从而避免了递归的深度限制。

5. 非递归数据结构
某些数据结构（如栈、队列、树等）可以以非递归方式实现。

使用这些数据结构可以避免需要递归的算法。

总的来说，选择递归还是其他算法取决于具体的问题和上下文。

在某些情况下，递归可能是最简洁和最直接的方法。

然而，在其他情况下，使用迭代、动态规划或其他技术可能会更有效、更简洁或更快。

因此，了解多种解决问题的方法是非常重要的。

1.对于栈，操作数据的原则是（）。

A.先进先出B.后进先出C.后进后出D.不分顺序2. 一般情况下，将递归算法转换成非递归应通过设置（）实现。

A.数组B.线性表C.队列D.栈3. 栈和队列的共同点是（）。

A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点4. 若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续3次进行退栈操作，则不可能得到的顺序是（）。

A.dcebfaB.cbdaefC.bcaefdD.afedcb5.某队列允许在两端进行入队操作，但仅允许在一端进行出队操作，若入队顺序为abcde，则不可能得到的顺序是（）。

A.bcadeB.dbaceC.dbcaeD.ecbad6.在对栈的操作中，能改变栈的结构是（）。

A.StackLength(S)B.StackEmpty(S)C. GetTop(S)D.ClearStack(S)7.在一个栈顶指针为HS的链栈中将一个S指针所指的结点入栈，应执行（）。

A.HS->next=s;B.S->next=HS->next;HS->next=s;C.S->next=HS;HS=s;D.S->next=HS;HS=HS->next;8.若已知一个栈的入栈序列是1,2,3,…n，其输出序列是p1，p2，p3，…pn，若p1=n，则pi=（）。

A.iB.n-IC.n-i+1D.不确定9.若用一个大小为6的数组来实现循环队列，且当前尾指针rear和头指针front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，尾指针rear和头指针front的值分别是（）。

A.1和5B.2和4C.4和2D.5和110.要使输入序列为ABC变为序列BAC，使用的栈操作序列为（）A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop11.设用一个大小为m=60的顺序表A[m]表示一个循环队列，如果当前的尾指针rear=32，头指针front=15，则当前循环队列的元素个数是（）A.42B.16C. 17D.4112.设用顺序表a[n]表示循环队列，头，尾指针分别为front和rear，则判断队列为空的条件是（），判断队列满的条件是（）（1）A.a.front+1==a.rear B.a.front==a.rear+1C.a.front==0D.a.front==a.rear(2)A.(a.rear-1)%n=a.front B(a.rear+1)%n=a.frontC.a.rear=(a.front-1)%n Da.rear=(a.front+1)%n13.设循环队列存储在数组A[0..m]中，则入队时的操作为（）A.rear=rear+1B.rear=(rear+1)mod(m-1)C,.rear=（rear+1）mod m D.rear=(rear+1)mod(m+1)14在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印，该缓冲区应该是一个（）结构A 栈B队列C数组D线性表15.设栈用向量V[1.…n]存储，初始栈顶指针top为n+1，则下面将x进栈的正确操作是（）A V[++top]=xB V[top++]=xC V[--top]=xD V[top--]=x16.若栈采用顺序存储方式存储，现在俩个共享空间V[1……m]，top[i]代表第i个栈（i=1，2）的栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）A|top[2]-top[1]|=0 B top[1]+1=top[2]C top[1]+top[2]=mD t op[1]=top[2]17.表达式a*（b+c）-d的后缀表达式是（）A. abcd*+ - B abc+*d-C abc*+d- D-+*abcd18一个栈的输入序列为123……n若输出序列的第一个元素是n，则输出第i（1<=i<=n）个元素是（）A 不确定Bn-i+1 C i D n-i二题1.在栈中，可进行插入和删除操作的一端称为（）。