2022年数据结构与算法习题及答案终稿 .pdf

《2022年数据结构与算法习题及答案终稿 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构与算法习题及答案终稿 .pdf（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精心整理精心整理第 1 章绪论习题1简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。2试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。3简述逻辑结构的四种基本关系并画出它们的关系图。4存储结构由哪两种基本的存储方法实现？5选择题（ 1）在数据结构中，从逻辑上可以把数据结构分成（）。A动态结构和静态结构B紧凑结构和非紧凑结构C线性结构和非线性结构D内部结构和外部结构（ 2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。A存储结构B存储实现C逻辑结 构 D运算实现（ 3）通常要求同一逻辑结构中的所有数据元素具有相同

2、的特性，这意味着（）。A数据具有同一特点B不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C每个数据元素都一样D数据元素所包含的数据项的个数要相等（ 4）以下说法正确的是（）。A数据元素是数据的最小单位B数据项是数据的基本单位C数据结构是带有结构的各数据项的集合D 一些表面上很不相同的数据可以有相同的逻辑结构（ 5）以下与数据的存储结构无关的术语是（）。A顺序队列B.链表 C.有序表 D.链栈（ 6）以下数据结构中， （）是非线性数据结构A树 B字符串 C队 D栈6试分析下面各程序段的时间复杂度。（ 1）x=90;y=100;? while(y0) if(x100) x=x-

3、10;y-; elsex+; （ 2）for(i=0;in;i+) for(j=0;jm;j+) aij=0; （ 3）s=0; fori=0;in;i+) for(j=0;jn;j+) s+=Bij; sum=s; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 44 页 - - - - - - - - - 精心整理精心整理（ 4）i=1; while(i=n) i=i*3; （ 5）x=0; for(i=1;in;i+) for(j=1;j1 y=0; while(x

4、 (y+1)*(y+1) y+; （ 1）O（1）（ 2）O（m*n ）（ 3）O（n2）（ 4）O（log3n）（ 5）因为 x+共执行了n-1+n-2+ 1=n(n-1)/2 ，所以执行时间为O（n2）（ 6）O(n) 第 2 章线性表1选择题（ 1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第 5 个元素的地址是（） 。A 110B108C100D 120 （ 2）在 n 个结点的顺序表中，算法的时间复杂度是O(1) 的操作是（）。A访问第 i 个结点（ 1i n）和求第 i 个结点的直接前驱（2 in）B在第 i 个结点后插入一个新结点（1in）C删除第 i 个结点（

5、 1in）D将 n 个结点从小到大排序（ 3）向一个有127 个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。A 8B63.5C 63D7 （ 4）链接存储的存储结构所占存储空间（）。A分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B只有一部分，存放结点值C只有一部分，存储表示结点间关系的指针D分两部分，一部分存放结点值，另一部分存放结点所占单元数（ 5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。A必须是连续的B部分地址必须是连续的C一定是不连续的D连续或不连续都可以（ 6）线性表在（）情况下适用于使用链式结构实现。A需经常修改中

6、的结点值需不断对进行删除插入C中含有大量的结点中结点结构复杂（ 7）单链表的存储密度（）。A大于 1B等于 1 C小于 1D不能确定名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 44 页 - - - - - - - - - 精心整理精心整理（ 8）将两个各有n 个元素的有序表归并成一个有序表，其最少的比较次数是（）。AnB2n-1 C 2nDn-1 （ 9）在一个长度为n 的顺序表中，在第i 个元素（ 1 in+1）之前插入一个新元素时须向后移动（）个元素。An-i B

7、 n-i+1 Cn-i-1D i (10)线性表 L=(a1，a2, an)，下列说法正确的是（）。A每个元素都有一个直接前驱和一个直接后继B线性表中至少有一个元素C表中诸元素的排列必须是由小到大或由大到小D除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。(11)若指定有 n 个元素的向量，则建立一个有序单链表的时间复杂性的量级是（）。AO(1)B O(n) CO(n2)DO(nlog2n) (12)以下说法错误的是（） 。A求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低B顺序存储的线性表可以随机存取C由于顺序存储要求连续的存

8、储区域，所以在存储管理上不够灵活D线性表的链式存储结构优于顺序存储结构(13)在单链表中，要将s 所指结点插入到p 所指结点之后，其语句应为（）。As-next=p+1;p-next=s; B(*p).next=s;(*s).next=(*p).next; Cs-next=p-next;p-next=s-next; Ds-next=p-next;p-next=s; (14)在双向链表存储结构中，删除p 所指的结点时须修改指针（）。Ap-next-prior=p-prior;p-prior-next=p-next; Bp-next=p-next-next;p-next-prior=p; Cp-p

9、rior-next=p;p-prior=p-prior-prior; Dp-prior=p-next-next;p-next=p-prior-prior; (15)在双向循环链表中，在p 指针所指的结点后插入q 所指向的新结点，其修改指针的操作是（）。Ap-next=q;q-prior=p;p-next-prior=q;q-next=q; Bp-next=q;p-next-prior=q;q-prior=p;q-next=p-next; Cq-prior=p;q-next=p-next;p-next-prior=q;p-next=q; Dq-prior=p;q-next=p-next;p-ne

10、xt=q;p-next-prior=q; 2算法设计题（ 1）将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。表中不允许有重复的数据。voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc) pa=La-next;pb=Lb-next; Lc=pc=La;/用 La 的头结点作为Lc 的头结点while(pa&pb) if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next; elseif(pa-datapb-data)pc-next=pb;pc=pb;

11、pb=pb-next; else/相等时取 La 的元素，删除Lb 的元素pc-next=pa;pc=pa;pa=pa-next; q=pb-next;deletepb;pb=q; pc-next=pa?pa:pb;/插入剩余段名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 44 页 - - - - - - - - - 精心整理精心整理deleteLb;/释放 Lb 的头结点 （ 2）将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空

12、间, 不另外占用其它的存储空间。表中允许有重复的数据。voidunion(LinkList&La,LinkList&Lb,LinkList&Lc,) pa=La-next;pb=Lb-next;/初始化Lc=pc=La;/用 La 的头结点作为Lc 的头结点Lc-next=NULL; while(pa|pb) if(!pa)q=pb;pb=pb-next; elseif(!pb)q=pa;pa=pa-next; elseif(pa-datadata)q=pa;pa=pa-next; elseq=pb;pb=pb-next; q-next=Lc-next;Lc-next=q;/插入 delete

13、Lb;/释放 Lb 的头结点 （ 3）已知两个链表A和 B分别表示两个集合，其元素递增排列。请设计算法求出A与 B的交集，并存放于A链表中。voidMix(LinkList&La,LinkList&Lb,LinkList&Lc,)pa=la-next;pb=lb-next; 设工作指针pa 和 pb；Lc=pc=La;/用 La 的头结点作为Lc 的头结点while (pa&pb) if (pa-data=pb-data) 交集并入结果表中。pc-next=pa;pc=pa;pa=pa-next; u=pb;pb=pb-next;deleteu; elseif(pa-datadata)u=pa

14、;pa=pa-next;deleteu; else u=pb;pb=pb-next;deleteu; while (pa)u=pa;pa=pa-next;deleteu; 释放结点空间while (pb)u=pb;pb=pb-next;deleteu; 释放结点空间pc- next=null;置链表尾标记。deleteLb;注：本算法中也可对B表不作释放空间的处理（ 4）已知两个链表A和 B分别表示两个集合，其元素递增排列。 请设计算法求出两个集合A和 B的差集（即仅由在 A中出现而不在B中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数。void Difference（

15、LinkedListA，B，*n）A和 B均是带头结点的递增有序的单链表，分别存储了一个集合，本算法求两集合的差集，存储于单链表A中， *n 是结果集合中元素个数，调用时为0 p=A-next ； p 和 q 分别是链表A和 B的工作指针。q=B-next ；pre=A； pre 为 A中 p 所指结点的前驱结点的指针。while （p!=null&q!=null）if （p-datadata）pre=p ；p=p-next ；*n+；A链表中当前结点指针后移。elseif（p-dataq-data）q=q-next ； B链表中当前结点指针后移。else pre-next=p-next；处理

16、 A，B中元素值相同的结点，应删除。u=p；p=p-next ； deleteu ；删除结点（ 5）设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中 B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用 A表的结点）。（ 6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 44 页 - - - - - - - - - 精心整理精心整理El

17、emTypeMax(LinkListL) if(L-next=NULL)returnNULL; pmax=L-next;/假定第一个结点中数据具有最大值p=L-next-next; while(p!=NULL)/如果下一个结点存在if(p-datapmax-data)pmax=p; p=p-next; returnpmax-data; （ 7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。voidinverse(LinkList&L) / 逆置带头结点的单链表L p=L-next;L-next=NULL; while(p) q=p-next;/q指向 *p

18、的后继p-next=L-next; L-next=p;/*p插入在头结点之后p=q; （ 8）设计一个算法，删除递增有序链表中值大于mink 且小于 maxk 的所有元素（ mink 和 maxk 是给定的两个参数，其值可以和表中的元素相同，也可以不同）。voiddelete(LinkList&L,intmink,intmaxk) p=L-next;/首元结点while(p&p-datanext;/查找第一个值 mink 的结点if(p) while(p&p-datanext; / 查找第一个值maxk的结点q=pre-next;pre-next=p;/修改指针while(q!=p) s=q-

19、next;deleteq;q=s;/释放结点空间/if （ 9） 已知 p 指向双向循环链表中的一个结点，其结点结构为data 、 prior、 next 三个域，写出算法change(p),交换 p 所指向的结点和它的前缀结点的顺序。知道双向循环链表中的一个结点，与前驱交换涉及到四个结点（p 结点，前驱结点，前驱的前驱结点，后继结点）六条链。void Exchange（LinkedListp）p 是双向循环链表中的一个结点，本算法将p 所指结点与其前驱结点交换。q=p-llink；q-llink-rlink=p； p 的前驱的前驱之后继为p p-llink=q-llink； p 的前驱指向其

20、前驱的前驱。q-rlink=p-rlink； p 的前驱的后继为p 的后继。q-llink=p； p 与其前驱交换p-rlink-llink=q； p 的后继的前驱指向原p 的前驱名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 44 页 - - - - - - - - - 精心整理精心整理p-rlink=q；p 的后继指向其原来的前驱 算法 exchange 结束。（ 10）已知长度为n 的线性表 A采用顺序存储结构，请写一时间复杂度为O(n) 、空间复杂度为O(1) 的

21、算法，该算法删除线性表中所有值为item 的数据元素。 题目分析 在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（删第 i 个元素， 第 i+1 至第n 个元素要依次前移） 。本题要求删除线性表中所有值为item 的数据元素，并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针（i=1 ，j=n ） ，从两端向中间移动，凡遇到值item 的数据元素时，直接将右端元素左移至值为 item 的数据元素位置。void Delete （ElemTypeA ，int n）A是有 n 个元素的一维数组，本算法删除A中所有值为item 的元素。i=1 ；j=n ；设置数组低、高端指针（下标）

22、。while （ij ） while （ij&Ai!=item）i+ ；若值不为item ，左移指针。if （ij ） while （ ij&Aj=item）j-；若右端元素值为item ，指针左移if （idata;top=top-link；B top=top-link;x=top-link；Cx=top;top=top-link ；Dx=top-link ；（ 5）设有一个递归算法如下?intfact(intn)?/n 大于等于 0 ?if(n=0)return1; ?elsereturnn*fact(n-1);? 则计算 fact(n)需要调用该函数的次数为（）。? A?n+1? B?n

23、-1? Cn? Dn+2 （ 6）栈在 ?（）中有所应用。A递归调用B函数调用C表达式求值D前三个选项都有名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 44 页 - - - - - - - - - 精心整理精心整理（ 7）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）。A队列 B栈 C线性表 D有序表（ 8）设栈 S 和队列 Q 的初始状态为空，元素

24、e1、e2、e3、e4、 e5 和 e6 依次进入栈S，一个元素出栈后即进入 Q，若 6 个元素出队的序列是e2、e4、e3、e6、 e5和 e1，则栈 S 的容量至少应该是（） 。A2B 3 C4D6（ 9）在一个具有n 个单元的顺序栈中，假设以地址高端作为栈底，以top 作为栈顶指针，则当作进栈处理时， top 的变化为（） 。Atop 不变 Btop=0 Ctop-Dtop+（ 10）设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。A线性表的顺序存储结构B队列C.线性表的链式存储结构D. 栈（ 11）用链接方式存储的队列，在进行删除运算时（） 。A.仅修改头指针B

25、.仅修改尾指针C.头、尾指针都要修改D.头、尾 指针可能都 要修改（ 12）循环队列存储在数组A0.m 中，则入队时的操作为（） 。A.rear=rear+1B.rear=(rear+1)%(m-1) C.rear=(rear+1)%mD.rear=(rear+1)%(m+1)（ 13）最大容量为n 的循环队列，队尾指针是rear ，队头是front，则队空的条件是（） 。A.(rear+1)%n=frontB.rear=frontCrear+1=frontD.(rear-l)%n=front （ 14）栈和队列的共同点是（） 。A.都是先进先出B.都是先进后出C.只允 许在端点处插入和删除元

26、素D.没有共同点（ 15）一个递归算法必须包括（） 。A.递归部分 B.终止条件和 递归部分C.迭代部分 D.终止条件和迭代部分（ 2）回文是指正读反读均相同的字符序列，如“abba”和“ abdba”均是回文，但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)? 根据提示，算法可设计为：/ 以下为顺序栈的存储结构定义#defineStackSize100/假定预分配的栈空间最多为100 个元素typedefcharDataType;/假定栈元素的数据类型为字符typedefstruct DataTypedataStackSize; inttop; 名师

27、资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 44 页 - - - - - - - - - 精心整理精心整理SeqStack;? intIsHuiwen(char*t) /判断 t 字符向量是否为回文，若是，返回1，否则返回0 SeqStacks; inti,len; chartemp; InitStack(&s); len=strlen(t);/求向量长度for(i=0;ilen/2;i+)/将一半字符入栈Push(&s,ti); while(!EmptyStack(&s

28、) /每弹出一个字符与相应字符比较temp=Pop(&s); if(temp!=Si)?return0;/不等则返回0 elsei+; ? return1;/比较完毕均相等则返回1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 44 页 - - - - - - - - - 精心整理精心整理（ 3）设从键盘输入一整数的序列：a1,a2,a3， ，an，试编写算法实现：用栈结构存储输入的整数，当ai-1时，将 ai进栈；当 ai=-1 时，输出栈顶整数并出栈。算法应对异常情

29、况（入栈满等）给出相应的信息。#definemaxsize栈空间容量void InOutS( int smaxsize) /s是元素为整数的栈，本算法进行入栈和退栈操作。 int top=0;/top为栈顶指针，定义top=0 时为栈空。for (i=1;i=n;i+)/n个整数序列作处理。scanf( “%d ”,&x);/从键盘读入整数序列。if (x!=-1)/读入的整数不等于-1 时入栈。if (top=maxsize-1)printf(“栈满n”);exit(0);else s+top=x;/x入栈。else / 读入的整数等于-1 时退栈。 if (top=0)printf(“栈空

30、n”);exit(0);else printf(“出栈元素是n”,stop-)； /算法结束。（ 4）从键盘上输入一个后缀表达式，试编写算法计算表达式的值。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔,操作符只可能有+、- 、 *、/ 四种运算。例如：23434+2*$。 题目分析 逆波兰表达式( 即后缀表达式) 求值规则如下：设立运算数栈OPND, 对表达式从左到右扫描( 读入) ，当表达式中扫描到数时，压入OPND 栈。当扫描到运算符时，从OPND 退出两个数，进行相应运算，结果再压入 OPND 栈。这个过程一直进行到读出表达式结束符$，这时 OPND 栈中

31、只有一个数，就是结果。floatexpr() / 从键盘输入逆波兰表达式，以$表示输入结束，本算法求逆波兰式表达式的值。 floatOPND30;/OPND 是操作数栈。init(OPND);/两栈初始化。floatnum=0.0;/数字初始化。scanf( “%c ”,&x);/x是字符型变量。while (x!= $) switch case0=x= 0&x=0&xj)printf(“序列非法n ”) ； exit(0); i+;/不论 Ai 是 I 或 O ，指针 i 均后移。 if (j!=k)printf(“序列非法n ”) ；return(false); else printf(“

32、序列合法n ”) ；return (true); /算法结束。 算法讨论 在入栈出栈序列（即由I 和 O组成的字符串）的任一位置，入栈次数（I 的个数）都必须大于等于出栈次数（即O的个数），否则视作非法序列，立即给出信息，退出算法。整个序列（即读到字符数组中字符串的结束标记0 ） ，入栈次数必须等于出栈次数（题目中要求栈的初态和终态都为空），否则视为非法序列。(6）假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点( 注意不设头指针) ，试编写相应的置空队、判队空、入队和出队等算法。? 算法如下：/ 先定义链队结构: typedefstructqueuenode Datatyp

33、edata; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 44 页 - - - - - - - - - 精心整理精心整理structqueuenode*next; QueueNode;/ 以上是结点类型的定义typedefstruct queuenode*rear; LinkQueue;/只设一个指向队尾元素的指针(1) 置空队voidInitQueue(LinkQueue*Q) / 置空队：就是使头结点成为队尾元素QueueNode*s; Q-rear=Q-rea

34、r-next;/将队尾指针指向头结点while(Q-rear!=Q-rear-next)/当队列非空，将队中元素逐个出队s=Q-rear-next; Q-rear-next=s-next; free(s); / 回收结点空间 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 44 页 - - - - - - - - - 精心整理精心整理(2) 判队空 ? intEmptyQueue(LinkQueue*Q) / 判队空/ 当头结点的next 指针指向自己时为空队retur

35、nQ-rear-next-next=Q-rear-next; (3) 入队voidEnQueue(LinkQueue*Q,Datatypex) / 入队/ 也就是在尾结点处插入元素QueueNode*p=(QueueNode*)malloc(sizeof(QueueNode);/申请新结点p-data=x;p-next=Q-rear-next;/初始化新结点并链入Q-rear-next=p;? Q-rear=p;/将尾指针移至新结点 (4) 出队DatatypeDeQueue(LinkQueue*Q) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - -

36、 - - - - - 名师精心整理 - - - - - - - 第 12 页，共 44 页 - - - - - - - - - 精心整理精心整理/ 出队 , 把头结点之后的元素摘下Datatypet; QueueNode*p; if(EmptyQueue(Q) Error(Queueunderflow); p=Q-rear-next-next;/p指向将要摘下的结点x=p-data;/保存结点中数据if(p=Q-rear) / 当队列中只有一个结点时，p 结点出队后，要将队尾指针指向头结点Q-rear=Q-rear-next;Q-rear-next=p-next; else? Q-rear-n

37、ext-next=p-next;/摘下结点 p free(p);/释放被删结点returnx; （ 7）假设以数组Qm存放循环队列中的元素,同时设置一个标志tag，以 tag= 0 和 tag= 1 来区别在队头指针(front)和队尾指针 (rear)相等时，队列状态为 “ 空” 还是 “ 满 ” 。 试编写与此结构相应的插入(enqueue)和删除 (dlqueue)算法。【解答】循环队列类定义 #include templateclass Queue /循环队列的类定义public:Queue(int=10);Queue()delete Q;名师资料总结 - - -精品资料欢迎下载 -

38、- - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 44 页 - - - - - - - - - 精心整理精心整理voidEnQueue(Type&item);TypeDeQueue();TypeGetFront(); voidMakeEmpty()front=rear=tag= 0;/置空队列intIsEmpty()constreturnfront=rear & tag= 0;/判队列空否intIsFull ()constreturnfront=rear & tag= 1;/判队列满否private:intrear,

39、front,tag; /队尾指针、队头指针和队满标志Type*Q ; /存放队列元素的数组intm; /队列最大可容纳元素个数构造函数template Queue: Queue(intsz):rear(0),front(0),tag(0),m(sz)/建立一个最大具有m 个元素的空队列。Q=newTypem; /创建队列空间assert(Q!=0) ; /断言 :动态存储分配成功与否插入函数template voidQueue:EnQueue(Type&item) assert (!IsFull ();/判队列是否不满，满则出错处理rear= (rear+1)%m;/队尾位置进1,队尾指针指示

40、实际队尾位置Qrear=item;/进队列tag=1;/标志改 1，表示队列不空 删除函数template TypeQueue:DeQueue() assert (!IsEmpty();/判断队列是否不空，空则出错处理front=(front+1)%m;/队头位置进1,队头指针指示实际队头的前一位置tag=0;/标志改 0,表示栈不满returnQfront; /返回原队头元素的值 读取队头元素函数template TypeQueue:GetFront() assert (!IsEmpty();/判断队列是否不空，空则出错处理returnQ(front+1)%m; /返回队头元素的值 (8 ）

41、如果允许在循环队列的两端都可以进行插入和删除操作。要求：写出循环队列的类型定义；写出“从队尾删除”和“从队头插入”的算法。 题目分析 用一维数组v0.M-1实现循环队列，其中M是队列长度。设队头指针front和队尾指针rear ，约定 front指向队头元素的前一位置，rear指向队尾元素。 定义 front=rear时为队空， (rear+1)%m=front为队满。约定队头端入队向下标小的方向发展，队尾端入队向下标大的方向发展。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14

42、 页，共 44 页 - - - - - - - - - 精心整理精心整理（ 1）#defineM 队列可能达到的最大长度typedefstructelemtpdataM; int front,rear; cycqueue; （ 2）elemtpdelqueue(cycqueueQ) /Q 是如上定义的循环队列，本算法实现从队尾删除，若删除成功，返回被删除元素，否则给出出错信息。 if (Q.front=Q.rear)printf(“队列空” );exit(0);Q.rear=(Q.rear-1+M)%M;/修改队尾指针。return (Q.data(Q.rear+1+M)%M);/返回出队元素

43、。/从队尾删除算法结束void enqueue(cycqueueQ,elemtpx) /Q 是顺序存储的循环队列，本算法实现“从队头插入”元素x。 if (Q.rear=(Q.front-1+M)%M)printf( “队满” ;exit(0);) Q.dataQ.front=x;/x入队列Q.front=(Q.front-1+M)%M;/修改队头指针。/结束从队头插入算法。（ 9）已知 Ackermann 函数定义如下 : 写出计算Ack(m,n) 的递归算法，并根据此算法给出出Ack(2,1)的计算过程。写出计算Ack(m,n) 的非递归算法。int Ack( int m,n) if (m

44、=0)return(n+1); elseif(m!=0&n=0)return(Ack(m-1,1); elsereturn(Ack(m-1,Ack(m,m-1); /算法结束（1）Ack(2,1)的计算过程Ack(2,1)=Ack(1,Ack(2,0)/因 m0,n0 而得=Ack(1,Ack(1,1)/因 m0,n=0 而得=Ack(1,Ack(0,Ack(1,0)/因 m0,n0 而得=Ack(1,Ack(0,Ack(0,1)/因 m0,n=0 而得=Ack(1,Ack(0,2)/因 m=0而得=Ack(1,3)/因 m=0而得=Ack(0,Ack(1,2)/因 m0,n0 而得=Ack(

45、0,Ack(0,Ack(1,1)/因 m0,n0 而得=Ack(0,Ack(0,Ack(0,Ack(1,0)/因 m0,n0 而得=Ack(0,Ack(0,Ack(0,Ack(0,1)/因 m0,n=0 而得=Ack(0,Ack(0,Ack(0,2)/因 m=0而得=Ack(0,Ack(0,3)/因 m=0而得=Ack(0,4)/因 n=0 而得=5/ 因 n=0 而得（2）int Ackerman(int m,int n) int akmMN;int i,j; for (j=0;jN;j+)akm0j;=j+1; for (i=1;im;i+) akmi0=akmi-11; for (j=1

46、;jN;j+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 44 页 - - - - - - - - - 精心整理精心整理akmij=akmi-1akmij-1; return(akmmn); /算法结束（ 10）已知 f 为单链表的表头指针,链表中存储的都是整型数据，试写出实现下列运算的递归算法：求链表中的最大整数；求链表的结点个数；求所有整数的平均值。#include/定义在头文件 RecurveList.h 中class List; class ListNod

47、e/链表结点类friendclassList; private: intdata;/结点数据ListNode*link ;/结点指针ListNode(constintitem):data(item),link(NULL )/构造函数;class List /链表类private: ListNode* first,current;intMax(ListNode*f );intNum(ListNode*f );floatAvg(ListNode*f ,int& n); public: List():first (NULL ),current(NULL )/构造函数List()/析构函数ListNo

48、de*NewNode(constintitem);/创建链表结点 ,其值为 itemvoidNewList(constintretvalue);/建立链表 ,以输入 retvalue 结束voidPrintList ();/输出链表所有结点数据intGetMax()return Max(first);/求链表所有数据的最大值intGetNum()returnNum(first );/求链表中数据个数floatGetAvg()return Avg(first );/求链表所有数据的平均值; ListNode*List :NewNode(constintitem)/创建新链表结点ListNode*

49、newnode=newListNode(item);returnnewnode; voidList:NewList(constintretvalue)/建立链表 ,以输入 retvalue 结束first=NULL;int value;ListNode*q ;coutvalue; /输入while(value!=retvalue) /输入有效q=NewNode(value); /建立包含 value 的新结点if(first=NULL )first=current=q ;/空表时 ,新结点成为链表第一个结点elsecurrent-link=q ;current=q ; /非空表时 ,新结点链入

50、链尾名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 44 页 - - - - - - - - - 精心整理精心整理cinvalue;/再输入 current-link=NULL ; /链尾封闭 voidList:PrintList ()/输出链表coutnTheListis:n ;ListNode* p=first ;while(p!=NULL ) coutdatalink; coutlink=NULL )returnf-data; /递归结束条件inttemp=Max