《数据结构与算法》(清华)典型例题.doc

6.3 典型例题一、单项选择题 例6-1 数据结构用集合的观点可以表示为一个二元组DS(D，R)。其中，D是 ( )的有穷集合，R是D上( )的有限集合。 A. 算法 B. 数据元素 C. 数据操作 D. 逻辑结构 A. 操作 B. 映像 C. 存储 D关系 解析：由数据结构的集合形式化定义可知，本题答案为：B； D。 例6-2 数据的常用存储结构中不包括( )。 A顺序存储结构 B线性结构 C索引存储结构 D散列存储结构 解析：数据通常有四种基本的存储方法，即顺序存储方法、链式存储方法、索引存储方法和散列存储方法。由此可知，本题答案为：B。 例6-3 算法指的是( )，它必须具备( )这三个特性。 A计算方法 B排序方法 C解决问题的步骤序列 D调度方法 A可执行性、可移植性、可扩充性 B可执行性、确定性、有穷性 C确定性、有穷性、稳定性 D易读性、稳定性、安全性 解析：算法是对特定问题求解步骤的一种描述，是由若于条指令组成的有限序列。它必须满足以下性质：输人性、输出性、有穷性、确定性、无二义性和可行性。由此可知，本题答案为：B。 例6-4 在下面的程序段中，对x的赋值语句的执行频度为( )。 for(i=0；in；i+) for(j=0；jn；j+) x=x+l： AO(2n) BO(n) CO(n2) DO(1bn) 解析：语句的执行频度即语句重复执行的次数，属于算法的时间复杂度类题目。本题中对x的赋值语句为一个二重循环的循环体，外层循环循环n次，内层循环也循环n次，显然此语句的执行次数为nnn2次。由此可知，本题答案为：C。二、填空题例6-5 是数据的基本单位，通常由若干个 组成， 是数据的最小单位。 解析：本题是基本概念题，知识点为数据结构的相关概念。本题答案为：数据元素；数据项；数据项。三、应用题 例6-6 简述数据结构的定义。 解析：数据结构是指数据元素之间的相互关系，即数据的组织形式。数据结构通常包括三个方面的内容，分别是数据的逻辑结构、数据的存储结构(物理结构)和在这些数据上定义的运算。用集合的观点可以把数据结构表示为一个二元组DS(D，R)。其中，D是数据元素的有穷集合，R是D上关系的有限集合。 例6-7 分析以下程序段的时间复杂度。 for(i=0；in；i+) /语句 x=x+1； /语句for(j=0；j2*n；j+) /语句y+； /语句 解析：语句的执行频度指的是语句重复执行的次数。一个算法中所有语句的执行频度之和构成了该算法的运行时间。在本例算法中，语句的执行频度是n+l，语句的执行频度是n，语句的执行频度是n(2n+2)2n2-2n，语句的执行频度是n(2n+1)2n2+n。该程序段的时间复杂度T(n)(n+1)+n+(2n2+2n)+(2n2+n)4n2+5n+1O(n2)。 实际上，可以用算法中基本操作重复执行的频度作为度量标准，而被视为基本操作的一般是最深层循环内的语句。在上例中，语句为基本操作，其执行频度为2n2+n，因此，该算法的时间复杂度T(n)2n2+nO(n2)。 例6-8 分析以下程序段的时间复杂度。 i=1； while(inextNULL Chead_nexthead Dhead!NULL 解析：在不带头结点的单链表head中，head指向第一个数据结点。空表即该表没有结点，headNULL表示该单链表为空。本题答案为：A。 例7-4 带头结点的单链表head为空的判定条件是( )。 AheadNULL BheadnextNULL Chead nexthead Dhead!NULL 解析：在带头结点的单链表head中，head指向头结点。空表即该表只有头结点，headnextNULL表示该单链表为空。本题答案为：B。 例7-5 带头结点的循环单链表head中，head为空的判定条件是( )。 AheadNULL BheadnextNULL Chead nexthead Dhead!NULL 解析：在带头结点的循环单链表head中，head指向头结点。空表即该表只有头结点，headnexthead表示该单链表为空。本题答案为：C。 例7-6 线性表采用链式存储时其存储地址( )。 A必须是连续的 B部分地址必须是连续的 C一定是不连续的 D连续不连续都可以解析：链式存储采用动态存储，地址一般不连续。本题答案为：D。例7-7 在双向链表的* p结点前插入新结点*s的操作为( )。 Apprior=s；snext=p；ppriornext=s；sprior=pprior； Bpprior=s；ppriornext=s；snext=p；sprior=pprior； Csnext=p；sprior=pprior；pprior=s；ppriornext=s； Dsnext=p；sprior=pprior；ppriornext=s；pprior=s； 解析：在双向链表的 * p结点前插入新结点 * s的操作如图7.12所示，图中虚线为所作的操作，序号为操作顺序。本题答案为：D。图7.12 双向链表插入结点的过程示意图 (例7-8) 若某表最常用的操作是在最后一个结点后插入一个结点和删除第一个结点，则采用( )存储方式最节省运算时间。 A单链表 B双向链表 C给出表头指针的循环单链表 D给出尾指针的循环单链表 解析：在链表中插入或删除一个结点，需修改相邻结点的指针域。上述四个选项中，只有选项D才能从尾指针经过最少的结点来进行题目要求的插入或删除操作。本题答案为：D。 例7-9 若线性表中有2n个元素，算法( )在单链表上实现要比在顺序表上实现效率更高。 A删除所有值为x的元素 B在最后一个元素的后面插入一个新元素 C顺序输出前k个元素 D交换其中某两个元素的值 解析：对于选项A，在单链表上和顺序表上实现的时间复杂度都为O(n)，但后者要移动大量的元素，因此在单链表上实现效率更高。本题答案为：A。 (例7-10) 在长度为n的( )上，删除第一个元素，其算法复杂度为O(n)。 A只有表头指针的不带头结点的循环单链表 B只有尾指针的不带表头结点的循环单链表 C只有表尾指针的带头结点的循环单链表 D只有尾指针的带表头结点的循环单链表 解析：本题答案为：A。具体算法如下： linklist * delfirst(linklist * h) Linklist * ph； while(p next!h) /找到表尾结点 ppnext； pnext=h next； free(h)； returnp一next； /返回头指针 二、填空题 例7-11 在单链表中结点 * p后插入结点 * s的指令序列为 ； 。 解析：在单链表中结点 * p后插入结点 * s，即将 * p 的后继结点变为 * s 的后继结点，* s 则成为 * p的后继结点。操作指令序列为：snextpnext；pnexts。 例7-12 在线性表的链式存储结构中，根据每个结点所含指针的个数，链表可分为 和 ；而根据指针的链接方式，链表又可分为 和 。 解析：本题答案为：单链表；多重链表；循环链表；普通链表(非循环链表)。 例7-13 在单链表中，要删除某一个指定的结点，必须找到该结点的 结点。 解析：由单链表的特点可知，删除某一个结点的操作是将其前驱结点的next指针域指向该结点的后继结点。本题答案为：前驱。 例7-14 在一个长度为n的顺序表中删除第i(0in一1)个元素，需向前移动 个元素。 解析：需将第i个元素后的元素依次前移一个位置，总共移动(n-1)-(i+1)+1个元素。本题答案为：n-i-1。 例7-15 在一个具有n个结点的单链表，在 * p结点后插入一个新结点的时间复杂度是 ；在给定值为x的结点后插入一个新结点的时间复杂度是 。 解析：在 * p结点后插入一个新结点 * s的操作是：s nextp next；pnexts；其时间复杂度为0(1)。 在给定值为x的结点后插入一个结点，首先要找到该结点，然后再进行插入。找到该结点的时间复杂度为O(n)，插入的时间复杂度为O(1)。本题答案为：O(1)；O(n)。三、应用题 (例7-16) 设A是一个线性表(a0，a1，ai，an-1)，采用顺序存储结构，则在等概率情况下平均每插入一个元素需要移动的元素个数是多少?若元素插在ai和ai+1之间(0in-1)的概率为，则平均每插入一个元素所需要移动的元素个数是多少? 解析：在等概率情况下，平均每插入一个元素需要移动的元素个数为：若元素插在ai和ai+l之间(0in-1)的概率为，则平均每插入一个元素所需要移动的元素个数为： (例7-17) 简述线性表采用顺序存储方式和链式存储方式的优缺点。 解析：顺序表的优点是可以随机访问数据元素，而且不需要额外的空间存储元素间的逻辑关系；缺点是表的大小固定，增减结点需要移动大量元素。链表的优点是增减元素非常方便，只需要修改指针内容；缺点是只能进行顺序访问，另外在每个结点上增加指针域会造成存储空间增大。 例7-18 若频繁地对一个线性表进行插入和删除操作，则应采用何种存储结构来存储该线性表?为什么? 解析：应采用链式结构来存储该线性表。采用链式存储结构来存储线性表，在进行插入和删除操作时的复杂度体现在查找插入或删除结点的前驱结点的操作上，查找过程中平均移动指针域的次数为表长的一半；而采用顺序存储结构存储线性表，在进行插入和删除操作时的复杂度则体现在元素的移动上，平均需移动表中的一半元素。因为指针域的移动操作次数比元素的移动操作次数少得多，所以应采用链式结构来存储该线性表。 (例719) (1)写出在双向链表中的结点 * p前插入一个结点 *s的语句序列。 (2)写出判断带头结点的双向循环链表L为空表的条件。 解析：(1)spriorpprior；pprior nexts； snextp；ppriors； (2)(LLnext)&(LLprior) 例7-20 链表所表示的元素是否是有序的?如果有序，则有序性体现在何处?链表所表示的元素是否一定要在物理上是相邻的?有序表的有序性又如何理解? 解析：链表所表示的元素是有序的，其有序性体现在逻辑有序，即指针有指向。链表所表示的元素在物理上不一定相邻。有序表的有序性不仅在逻辑结构上有序，而且在物理结构上也有序。 四、算法设计题 (例7-21) 编写一个算法，将一个带头结点的单链表逆转。要求在原链表空间上进行逆转，即不允许构造新的链表结点； 解析：从单链表的一种构造方法头插法中可以得知，该方法构造的线性表中结点 的顺序与插人次序相反。因此我们可以将表结点从前往后逐个拆下并用头插法插人新表， 所构造的单链表即为原表的逆转。 具体算法如下： linklist * reverse(1inklist * h) linklist * p，*q，*r； phnext； hnext=NULL； /构造空表 while(p!NULL) q=p； /拆下结点 p=p next； qnext=hnext； /用头插法插入 hnext=q； return h； (例7-22) 已知一个顺序表La的元素按值非递减有序，编写一个算法将元素x插人后保持该表仍然按值非递减有序。 解析：要让插入新元素后的顺序表仍然按值非递减有序，必须把x插入到表中第一个大于等于x的元素之前。应先在表中找到该位置，然后后移该元素，空出一个位置，再将x插入。 具体算法如下： insert(sqlist *La，datatype x) /La为指向顺序表的指针 int i=0，j； while(ilast) /查找插入位置i if(xdatai) break； i+； for(j=Lalast+1；ji；j-) /后移所有大于等于x的元素 Ladataj=Ladataj-1； Ladataix； /将x插入 Lalast+； /表长度加1 (例7-23) 用顺序表A、B表示集合，编写算法求集合A和集合B的交集C(假设A、B表内无重复元素)。 解析：求CAB，C中元素是A、B中的公共元素。对于表A中的每个元素，在表B中扫描，若有与它相同的元素，则为交集元素，将其放到C中。 具体算法如下： intersection(sqlist A，sqlist B，sqlist * C) int i，j，k0； for(i0；iA1ast；i+) j=0； while(jB.1ast& A.darai!B.dataj j+； if(jdatak+A.datai Clast=kl； /修改表长度 例7-24 编写一个算法，计算在头指针为head的单链表中数据域值为x的结点个数。 解析：先设一计数器n，初值为0。然后遍历链表中的每个结点，每遇到一个结点都需要判断其数据域值是否为x，如果是，计数器n加1。遍历完成后计数器n的值就是所求的结点数。具体算法如下：int count(linklist * head, datatype x) int n=0； linklist * p； p = head； while(p ! = NULL) if(p data = = x) n+; p=pnext； return n； (例7-25) 用单链表La、Lb表示集合A、B，编写算法求集合A和集合B的差集C，并用链表Lc表示(假设A、B内无重复元素)。 解析：根据集合运算规则可知，集合AB中包含所有属于集合A而不属于集合B的元素。具体做法是：从头到尾扫描单链表La，并判断当前元素是否在单链表Lb中；若不在，则将其插入单链表Lc中。具体算法如下：linklist * difference(linklist * La, linklist * Lb) linklist *Lc, * pa, *pb, * s, * r； pa= Lanext Lc = (linklist * ) malloc (sizeof (linklist) ; r=Lc; while(pa! = NULL) pb=Lb next; while (phb! = NULL & & pb data ! = pa data) pb= pbnext； if(pb = = NULL) s= (linklist * )malloe(sizeof(linklist); s data= padata； rnext=s； rs； pa= panext； rnext = NULL； return Lc； (例7-26) 已知两个头指针分别为La和Lb的单链表，它们的元素按值递增有序。编写一算法将两个单链表合并，要求合并后链表仍然递增有序，不允许开辟另外的链表空间。 解析：由于题目要求不开辟另外的链表空间，所以首先以两个链表中的一个头结点为新链表的头结点构造一个空的单链表。从头到尾逐个比较La和Lb表中的元素，将值较小的元素结点链接到新表的末尾，若结点值相同则将其中一个链接到新表的末尾而释放另一个。当La或Lb为空后，把另一个链表余下的结点链接到新表的末尾。 具体算法如下：linklist * union(linklist * La, linklist * Lb) linklist * pa, * pb, * r； pa = La next； pb= Lbnext； r=La； /以*La为新表头结点，r为新表尾指针 free(Lb); /释放Lb表头结点 while(pa! =NULL & pb! =NULL) if ( pa data data) r=pa; pa= panext； else if(padatadata) r next = pb； r=pb； pb = pb next; rnext= pa； else /pa-data = = Pbdata的情况 r=pa； /将原La表结点插入，原Lb表结点删除 pa = pa next； s=pb； pb = pbnext； free(s)； if(pa=NULL) /将Lb表剩余结点链到新表 rnext=pb； return La； /返回新表头结点地址 (例7-27) 设计个将循环双链表中结点*p与其后继结点交换位置的算法。解析：本题应充分利用双向链表可对前驱结点和后继结点进行操作的特点。具体算法如下： int swap(dlinklist * p) dlinklist * q； if(pnext= = pprior) /只有一个数据结点，不能交换 return 0； /交换失败 q=pnext； /q指向 * p的后继 pnext=qnext； /删除 * q qnextprior= p； qprior= pprior； /把*q插入*p前 qnext=p； ppriornext=q； pprior=q； return 1； /交换成功 8.3 典型例题一、单项选择题例8-1 在一个具有n个单元的顺序栈中，假设以地址高端作为栈底，以top为栈顶指针，则向栈中压入一个元素时top的变化是( )。 Atop不变 Btop=n Ctop=top-1 Dtop=top+1 解析：本题答案为：C。 (例8-2) 一个栈的进栈序列是a，b，c，d，e，则不可能的出栈序列是( )。 Aedcba Bdecba C。dceab Dabcde 解析：栈的特点是先进后出。在选项C中，a、b、c、d进栈，d出栈，c出栈，e进栈，e出栈，此时栈中从栈顶到栈底应该是b、a，不可能a先出栈。本题答案为：C。 例8-3 若已知一个栈的进栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若pl3，则p2为( )。 A可能是2 B不一定是2 C可能是1 D一定是1 解析：当p13时，表示3最先出栈，前面l、2应该在栈中。此时若出栈，则p2为2；此时若进栈，则p2可能为3，4，5，n的任何一个。本题答案为：A。 例 8-4 若一个栈的输入序列为1，2，3，4，n，输出序列的第一个元素是n，则第i个输出元素是( )。 Ani Bni1 Ci Dni+1 解析：本题答案为：D。 (例8-5) 栈和队列的共同点是( )。 A都是先进后出 B都是先进先出 C只允许在表端点处插入和删除元素 D没有共同点 解析：栈和队列都是操作受限的线性表，只允许在表端点处进行插入和删除操作。本题答案为：C。 (例8-6) 向一个栈顶指针为top的链栈中插入一个s所指的结点时，操作语句序列为( )。 Atopnext=top； Bsnext=topnext；topnext=s； Csnexttop；tops； Dsnext=top；toptopnext； 解析：向链栈中插入一个结点，就是在不带头结点的单链表的表头插入一个结点。本题答案为：C。 例8-7 在解决计算机主机与打印机之间速度不匹配的问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据进行打印。该缓冲区应该是一个( )结构。 A栈 B队列 C数组 D线性表 解析：本题答案为：B。 (例8-8) 一个队列的入队序列是1，2，3，4，则队列的输出序列是( )。 A4，3，2，1 B1，2，3，4 C1，4，3，2 D4，1，3，2 解析：本题答案为B。 例8-9 判断一个循环队列Q为满队列的条件是( )。 AQ一front= =Qrear BQ一front!QrearCQ一front= =(Q一rear+1)MaxSizeDQfront!(Qrear+1)MaxSize 解析：由循环队列的结构可知，本题答案为：C。 例8-10 循环队列用数组A0，MaxSize-1存放其元素，已知其头尾指针分别是front和rear，则当前队列元素个数为( )。 A(rearfront + MaxSize)MaxSize Brearfront+1 Crearfrontl Drearfront 解析：本题答案为：A。 (例8-11) 在一个链队列中，假设f和r分别是队头指针和队尾指针，则插入s所指结点的运算是( )。 Af nexts；fs； Br nexts；rs； Cs nextr；rs； Ds nextf；fs； 解析：向链队列插入一个结点即在单链表表尾插入一个结点。本题答案为：B。二、判断题 例8-12 栈是一种先进先出的线性结构。 解析：错误。栈是一种先进后出的线性结构。 例8-13 栈和队列都是线性表。 解析：正确。栈和队列都是操作受限的线性表。 例8-14 即使对不含相同元素的同一输入序列进行两组不同的但合法的人栈和出栈组合操作，所得的输出序列也一定相同。 解析：错误。根据栈的特性，不同的人栈和出栈组合操作所得的输出序列是不相同的。 例8-15 循环队列也存在空间溢出问题。 解析：正确。循环队列的引入只是解决了一般顺序队列的假溢问题，并没有解决溢出问题。 例8-16 循环队列通常用指针来实现队列的头尾相接。 解析：错误。循环队列的首尾相接是假想的，事实上并没有实质上的相接，只是在指针时实现了从最大下标向最小下标的过渡。三、填空题 例8-17 栈的特点是 ，队列的特点是 ，栈和队列都是 。 解析：本题答案为：先进后出FILO(或后进先出LIFO)；先进先出FIFO；操作受限的线性表。 例8-18 一个栈的输入序列是：l，2，3，则不可能的栈输出序列是 。 解析：在栈的操作中，如果输入序列按递增排序号，则在输出序列中，某一个元素后所有比它序号小的元素序号肯定是逆序的。本题答案为：3，1，2。 例8-19 队列是限制了插入操作只能在表的一端，而删除操作只能在表的另一端进行的线性表，其特点是 。解析：本题答案为：先进先出。(例8-20) 若用不带头结点的单链表来表示链栈s，则创建一个空栈所要执行的操作是 。 解析：由链栈的运算过程可知，本题答案为：sNULL。 (例8-21) 在链队列Q中，判定其只有一个结点的条件是 。 解析：只有一个结点时，队头指针和队尾指针都指向链表头结点。 本题答案为：QfrontQrear。四、应用题 例8-22 为什么说栈是一种先进后出表? 解析：栈是一种线性表，如果把所有元素都放人栈中再出栈，则最后插入栈中的那个元素总是最先从栈中移出，因此说栈是一种先进后出表。 (例8-23) 对于一个栈，按顺序输入A，B，C。如果不限制出栈时机(即栈中元素不必等所有输入元素都进栈再输出)，试给出全部可能的输出序列。 解析：本题利用栈的后进先出的特点，有如下几种情况： (1)A进，A出，B进，B出，C进，C出，产生输出序列ABC。 (2)A进，A出，B进，C进，B出，C出，产生输出序列ACB。 (3)A进，B进，B出，A出，C进，C出，产生输出序列BAC。 (4)A进，B进，C进，C出，B出，A出，产生输出序列CBA。 (5)A进，B进，B出，C进，C出，A出，产生输出序列BCA。 不可能产生的序列为：CAB。 (例8-24) 有一字符串次序为-3 * y - a/y2，试利用栈将该字符串次序改为3y-ay2/ * -，写出操作步骤。(可用X代表扫描该字符串并顺序取一字符进栈的操作，用S代表从栈中取出一字符加到新字符串尾的出栈操作) 解析：实现上述转换的进、出栈操作如下： -进 3进 3出 *进 y进 y出 -进 -出 a进 a出 进 y进 y出 进 出 2进 2出 /出 *出 -出 所以操作步骤为：XXSXXSXSXSXXSXSXSSSS。 (例8-25) 什么是顺序队列的上溢现象?什么是假溢现象?解决假溢现象的方法有哪些? 解析：在队列的顺序存储结构中，设队头指针为front，队尾指针为rear，队的容量为MaxSize。当有元素加入队列时，若rearMaxSize-1(初始时rear-1)，则发生队列的上溢现象，该元素不能加入队列。 队列的假溢现象是指队列中尚有空余空间，但此时rearMaxSize-1，元素不能入队。解决队列假溢的方法如下： (1)建立一个足够大的存储空间，但这样做会造成空间浪费。 (2)采用循环队列方式。原理参照8.2.5中的介绍。(3)采用平移元素的方法，即每当队列中删除一个元素肘，依次移动队中元素，始终使front1。 (例8-26) 假设Q011是一个循环队列，初始状态为frontrear0，画出做完下列操作后队列的头、尾指针的状态变化情况。若不能人队，请指出其元素，并说明理由。 d，e，b，g，h入队 d，e出队 i，j，k，l，m人队 b出队 n，o，p，q人队 解析：本题入队和出队的变化如图8.7所示。队列没有产生上溢。五、算法设计题 例8-27 设有两个栈S1和S2，都采用顺序结构表示，并且共享一个存储区Vo. n-1。为尽量利用空间，减少溢出的可能，现采用栈顶相对、迎面增长的方式存储。试设计公用栈的操作算法。 解析：让两个栈迎面增长，只有相遇时才会溢出。另外，用一个变量i(i1表示栈l操作，i2表示栈2操作)来区别S1和S2的操作。 进栈操作算法如下： int push(datatype V ，int top1，int，top2，datatype x，int i) if(i!1& & i!=2) return 0； /参数错误 if(topl+1 !=top2) if(i= =1) /S1进栈操作 V+toplx； else /S2进栈操作 V+top2x； else return 0； /溢出 return l； /成功 例8-28 设单链表中存放着n个字符，试设计判断字符是否中心对称的算法。例如，abcba和xyzzyx是中心对称。 解析： 方法一：将字符串中前一半字符进栈，然后将栈中字符逐个与链表中的后一半字符进 行比较。要注意区分字符个数为奇数和偶数的两种情况。字符串不对称时，返回值为0；反 之，返回值为1。 int mateh(1inklist * h，int n) linklist * p; int i1； datatype x； sqstack s； initstack(&s)； /栈初始化 p=h一next； /p指向链表第一个数据结点 while(i!=n/2+1) /扫描链表前一半 push(s，pdata)； /元素进栈p=p一next；i+； if(n2！0) /n为奇数 p=pnext； while(p!=NULL) x=pop(s)； /元素出栈 if(x!=pdata) /若不相等，则不对称 return 0； p=pnext； return 1； /中心对称 方法二：将字符串中的全部字符进栈，然后将栈中字符逐个出栈，并与链表中字符从前，往后逐个比较。字符串不对称时，返回值为0；反之，返回值为1。 int match(1inklist * h) linklist * p； datatype x； sqstack s； initstack(&s)； /初始化 p=hnext； /p指向链表第一个数据结点 while(p!=NULL) push(s，pdata)； /元素进栈p=pnext； p=hnext； /P重新指向链表第一个数据结点 while(p!=NULL) x=pop(s)； /元素出栈 if(x!=pdata) /若不相等，则不对称 return 0； p=pnext； return 1； /中心对称 例8-29 编写一个算法，利用队列的基本运算返回队列中的最后一个元素。 解析：假设队列为循环顺序队列。建立一个临时队列，将指定队列中所有元素出队并入队到临时队列中，这样指定队列为空，再将临时队列中所有元素出队并入队到指定队列(因为不能破坏原队列结构，所以需要恢复元素)，最后一个元素即为所求。具体算法如下：datatype lastelem (queue * Q) datatype x； queue tmp Q； initqueue(& tmp Q) while(! emty (Q) /将Q中元素放入tmpQ x=dequeue(Q) enqueue(&tmpQ，x)； while (! empty (& tmpQ) /将tmpQ中元素恢复回Q x=dequeue ( & tmpQ)； enqueue(Q，x)； return x； (例8-30) 假定用一个循环单链表表示队列(循环链队，带头结点)，该队列只设一个队尾指针rear，不设队头指针，试编写算法实现下列要求： (1)向循环链队中插入一个元素x。 (2)从循环链队中删除一个结点。 解析：定义本题队列类型如下： typedef struct linklist * rear; Queue2 (1)队列中人队操作是在队尾进行，即在链尾插入一个新结点。 void enqueue (Queue2 * Q，datatype x) linklist * s； s(linklist * )malloe (sizeof (linklist)； /建立新结点 sdatda=x； snext=Qrearnext； /将新结点插入队尾 qrearnext = s； qrear = s； (2)队列中出队操作是在队头进行，即删除链表第一个数据结点。 datatype dequeue (Queue2 * Q) datatype x； linklist * p； if (Qrearnext= =Qrear) /队列为空 return NULL； pQ一rear一next一next； /p指向队头结点 x=p一data； Q一rear一next一nextp一next /删除 * p结点 free (p) return x； /返回原队头元素 注意：队列和栈都是线性表，它们是操作受限的