1、计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编 1 及答案与解析一、单项选择题1 对于栈操作数据的原则是_。【青岛大学 2001 年】（A）先进先出（B）后进先出（C）后进后出（D）不分顺序2 在初始为空的堆栈中依次插入元素 f，e，d，c ，b，a 以后，连续进行了三次删除操作，此时栈项元素是_。【北京航空航天大学 2002 年】（A）c（B） d（C） b（D）e3 六个不同元素依次进栈，能得到_种不同的出栈序列。【北京邮电大学 2007年】（A）42（B） 82（C） 132（D）1924 入栈序列为 1，2，3，4，5，则可能得到的出栈序列是_。【上海交通大学2005】（A）1
2、2534（B） 31254（C） 32541（D）142355 一个栈的输入序列为 1，2，3，4，5，则下列序列中不可能是栈的输出序列的是_。【北京理工大学 2000 年】【北京交通大学 2006 年】【中南大学 2003 年】（A）23415（B） 54132（C） 23145（D）154326 若已知一个栈的入栈序列为 1，2，3，4，其出栈序列为 pl，p2，p3，p4，则p2，p4 不可能是_。【华中科技大学 2007 年】（A）2、4（B） 2、1（C） 4、3（D）3、47 某堆栈的输入序列为 a，b，c ，d，下面的四个序列中，不可能是它的输出序列的是_。【北京航空航天大学 2
3、005 年】【北京邮电大学 2005 年】（A）a，c，b，d（B） b，c，d，a（C） c，d，b，a（D）d，c， a，b8 输入序列为 ABC，可以变为 CBA 时，经过的栈操作为 _。【中山大学 1999年】（A）push，pop，push，pOp，push，pop（B） push， push，push，pOp ，pOp，pop（C） push， push，pop，pOp，push，pop（D）push，pOp，push，push，pOp，pop9 若栈采用顺序存储方式存储，现两栈共享空间 V1m ，topi代表第 i 个栈(j=1，2)栈顶，栈 1 的底在 V【1】，栈 2 的底在
4、 Vm，则栈满的条件是_。【南京理工大学 1999 年】（A）1top2top11=0（B） top1+1=top2（C） top1+top2=m（D）top1=top210 向一个栈顶指针为 h 的带头结点的链栈中插入指针 s 所指的结点时，应该执行_。【北京理工大学 2005 年】（A）hnext=s ：（B） s-next=h；（C） snext=h：h-next=s ；（D）s-next=h 一nexth-next=S；11 执行完下列语句段后，i 值为_。【浙江大学 2000 年】intf(intx)return(x0)?x*f(x 一 1)：2)；inti；i=f(f(1)；（A）
5、2（B） 4（C） 8（D）无限递归12 一个递归算法必须包括_。【武汉大学 2000 年】（A）递归部分（B）终止条件和递归部分（C）迭代部分（D）终止条件和迭代部分13 将递归算法转变成对应非递归算法时，需要使用_保存中间结果。【华中科技大学 2007 年】（A）栈（B）队列（C）二叉树（D）单链表14 表达式 a*(b+c)一 d 的后缀表达式是_。【南京理工大学 2001 年】（A）abed*+一（B） abc+*d（C） abe*+d（D）-+*abcd15 中缀表达式(A+B)*(CD)(EF*G)的后缀表达式是_。【北京邮电大学2005 年】（A）A+B*CDE F*G（B） A
6、B 十 CD 一*EFG*一（C） AB+C*DEF G+（D）ABCDEFG+*一一*16 中缀表达式 A 一(B+CD)E 的后缀形式是_。【北京航空航天大学 2007 年】（A）ABCD+E*一（B） ABC+D*E（C） ABC+DE*（D）ABC 一+D E*17 设计一个判别表达式中左、右括号是否配对出现的算法，采用_数据结构最佳。【西安电子科技大学 1996 年】（A）线性表的顺序存储结构（B）队列（C）线性表的链式存储结构（D）栈18 在链队列的出队操作中，修改尾指针的情况发生在_。【广东工业大学 2002年】（A）变成空队列的时候（B）变成满队列的时候（C）队列只剩一个元素的
7、时候（D）任何时候19 对于循环队列，正确的是_。【哈尔滨工业大学 2007 年】（A）无法判断队列是否为空（B）无法判断队列是否为满（C）队列不可能满（D）以上说法都不对20 循环队列 A0m 一 1存放其元素值，用 front 和 rear 分别表示队头和队尾，则当前队列中的元素数是_。【南京理工大学 2001 年】【华中科技大学 2007 年】（A）(rearfront+m)m（B） rearfront+l（C） rearfront 一 1（D）rearfront21 循环队列存储在数组 A0m中，则入队时的操作为_。【中山大学 1999 年】（A）rear=rear+1（B） rear
8、=(rear+1)mod(m 一 1)（C） rear=(rear+1)modm（D）rear=(rear+1)mod(re+1)22 最大容量为 n 的循环队列，队尾指针是 rear，队头是 front，则队空的条件是_。【南京理工大学 1999 年】（A）(rear+1)MODn=front（B） rear=front（C） rear+1=front（D）(rear11MODn=front23 判定一个长度为 M 的循环队列 Q 队满的条件是。【北京交通大学 2007 年】（A）Qfront+1=Qrear（B） Qfront=Qrear+1（C） Qfront=Q rear（D）Qfro
9、nt=(Qrear+1)M24 栈和队列的共同点是。【燕山大学 2001 年】（A）都是先进先出（B）部是先进后出（C）只允许在端点处插入和删除元素（D）没有共同点25 栈 s 和队列 Q 的初始状态皆为空，元素 a1，a2，a3，a4 ，a5 和 a6 依次通过 s栈，一个元素出栈后即进入队列 Q，若 6 个元素出队列的顺序是a3，a4，a2，a1，a5 ，a6 ，则栈 s 至少应该容纳_个元素。【哈尔滨工业大学2004 年】（A）6（B） 4（C） 3（D）226 和顺序栈相比，链栈有一个比较明显的优势是_。【北京理工大学 2006 年】（A）通常不会出现栈满的情况（B）通常不会出现栈空的
10、情况（C）插入操作更容易实现（D）删除操作更容易实现27 执行_操作时，需要使用队列作辅助存储空间。【华中科技大学 2006 年】（A）查找散列表（B）广度优先搜索网（C）前序 (根)遍历二叉树（D）深度优先搜索网28 对 n 阶对称矩阵作压缩存储时，需要表长为_的顺序表【华中科技大学 2006年】（A）n2（B） n,n2（C） n(n+1)2（D）n(n 一 1)2二、综合题29 设从键盘输入一整数的序列：al，a2 ，a3，an，试编写算法实现：用栈结构存储输入的整数，当 ai一 1 时，将 ai 进栈；当 ai=一 1 时，输出栈顶整数并出栈。算法应对异常情况(入栈满等)给出相应的信息
11、。【南京航空航天大学 1998 年】30 设有两个栈 s1、s2 都采用顺序栈方式，并且共享一个存储区0maxsize 一 1，为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计 s1、s2 有关入栈和出栈的操作算法。【哈尔滨工业大学 2001 年】31 从键盘上输入一个逆波兰表达式，写出其求值程序。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔，操作符只可能有+、一、*、四种运算。例如：23434+2*$ 。【山东师范大学 1999 年】32 设整数序列 a1，a2 ， ，an，给出求解最大值的递归程序。【南京航空航天大学 2000 年
12、】33 给定一个由英文字母组成的字符串 s(假设 S 用数组实现)，编制一个递归函数，测试 s 是否为回文串，“回文串”是指从左向右读该字符串和从右向左读该字符串完全相同，例如：“noon”、 “radar”等。【南京大学 2005 年】34 设一个由字母组成的字符串，编写算法对它们的字母顺序进行调整，使输出时所有大写字母都在小写字母之前，并且同类字母之间的相对位置颠倒。【华南理工大学 2005 年】例如：原有字符串为 AbcDEfiglfiJKlmn，输出序列为KJEDAnmlihgfcb。35 已知求两个正整数 m 与 n 的最大公因子的过程用自然语言可以表述为反复执行如下动作：第一步：若
13、 n 等于零，则返回 m。第二步：若 m 小于 n，则 m 与 n 相互交换：否则，保存 m，然后将 n 送 m，将保存的 m 除以 n 的余数送 n。1) 将上述过程用递归函数表达出来(设求 x 除以 y 的余数可以用 xMODy 形式表示)。2)写出求解该递归函数的非递归算法。【北京航空航天大学 2001 年】36 试将下列递归过程改写为非递归过程。【北京轻工业学院 2000 年】void test(int sum) int x；scanf(”d，x)；1t(x=0)sum=0；elsetest(sum)；Sum+=X；printf(“d”，sum)；37 假设以带头结点的循环链表表示队列
14、，并且只设一个指针指向队尾结点，但不设头指针，请写出相应的入队列和出队列算法。【华东师范大学 2000 年】【苏州大学 2002 年】38 一个双端队列 deque 是限定在两端 endl、end2 都可进行插入和删除的线性表，队空条件是 endl+l=end2。若用顺序方式来组织双端队列，试根据下列要求，定义双端队列的结构，并给出在指定端 i(i=1，2) 的插入 enq 和删除 deq 操作的实现。1)当队满时，最多只能有一个元素空间可以是空的。2)在做两端的插入和删除时，队列中其他元素一律不动。【中南大学 2003 年】39 已知 Q 是一个非空队列，s 是一个空栈。仅用队列和栈的 AD
15、T 函数和少量工作变量，使用 C 语言编写一个算法，将队列 Q 中的所有元素逆置。栈的 ADT 函数有：【清华大学 2000 年】makeEmpty(s：stack)； 置空栈push(s：stack；value：datatype)； 新元素 value 进栈pop(s：stack)：datatype； 出栈，返回栈顶值isEmptys：stack)：Boolean； 判栈空否队列的 ADT 函数有：enqueue(q：queue；value：datatype) ； 元素 value 进队deQueue(q：queue)：datatype； 出队列，返回队头值isEmpty(q：queue)
16、：boolean； 判队列空否40 设单链表的表头指针为 h，结点结构由 data 和 next 两个域构成，其中 data 域为字符型。写出算法 dc(h， n)，判断该链表的前 n 个字符是否中心对称。例如：xyx、xyyx 都是中心对称。【首都经贸大学 1998 年】计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编 1 答案与解析一、单项选择题1 【正确答案】 B【试题解析】 考查栈的概念。栈是一种后进先出的数据结构。【知识模块】 栈和队列2 【正确答案】 B【试题解析】 考查栈的基本性质。数据入栈时，先入栈的元素后出栈，只需简单地画图即可看出栈顶元素应是 d。【知识模块】 栈和队
17、列3 【正确答案】 C【试题解析】 考查栈的基本性质。设有 n 个不同元素时，有 f(n)种出栈序列。若第一个元素是第 i 个出栈的，则在这个元素之前是编号为 2i 的元素出栈，之后是编号为 i+1n 的元素出栈。所以第一个元素是第 i 个出栈对应 f(i-1)*f(ni)种出栈顺序。f(1)=1f(2)=2f(3)=f(2)+f(1)*f(1)+f(2)=5f(4)=f(3)+f(1)+f(2)十 f(2)+f(1)+f(3)=14f(5)=f(4)+(1)+f(3)+“2)+f(2)+f(3)*(1)+f(4)=42f(6)=f(5)+(1)+f(4)+f(2)+f(3)+f(3),f(2
18、)+f(4)+f(1)+f(5)=42+14+10+10+14+42=132【知识模块】 栈和队列4 【正确答案】 C【试题解析】 考查栈的性质。C 的情况是由以下操作得到： 1、2、3 先入栈，接着 3 弹栈，2 弹栈，然后 4、5 入栈，5 弹栈，4 弹栈，最后 1 弹栈。其他各种情况，都不可能由栈的操作得到。【知识模块】 栈和队列5 【正确答案】 B【试题解析】 考查栈的性质。考生可通过画图得出正确答案。A 是可能的：先是1、2 入栈，然后 2 弹栈，3 入栈，3 弹栈，4 入栈，4 弹栈，1 弹栈，5 入栈，5 弹栈。C 是可能的：1 和 2 入栈，2 弹栈，3 入栈，3 弹栈，1 弹
19、栈，4 入栈，4 弹栈，5 入栈，5 弹栈。D 是可能的：1 入栈，l 弹栈，2345 入栈，5432 弹栈。【知识模块】 栈和队列6 【正确答案】 C【试题解析】 考查栈的性质。对于 A，可能的顺序： 1 入栈，1 弹栈，2 入栈，2弹栈，3 入栈，3 弹栈，4 入栈，4 弹栈。对于 B，可能的顺序：1 入栈，2 入栈，3 入栈，3 弹栈，2 弹栈，4 入栈，4 弹栈，1 弹栈。对于 D，可能的顺序：1 入栈，1 弹栈，2 入栈，3 入栈，3 弹栈，2 弹栈，4 入栈，4 弹栈。C 则没有对应的序列。【知识模块】 栈和队列7 【正确答案】 D【试题解析】 考查栈的性质。A 可能的序列：a 入
20、栈，a 出栈，b 入栈，c 入栈，c 出栈，b 出栈，d 入栈， d 出栈。B 可能的序列：a、b 入栈，b 出栈，c 入栈，c出栈，d 入栈， d 出栈，a 出栈。C 可能的序列：a、b 、c 入栈，c 出栈，d 入栈，d 出栈，b 出栈，a 出栈。【知识模块】 栈和队列8 【正确答案】 B【试题解析】 考查栈的性质。本题属于比较简单的类型。正确的顺序：A 入栈，B 入栈， c 入栈，c 弹栈，B 弹栈，A 弹栈。【知识模块】 栈和队列9 【正确答案】 B【试题解析】 考查栈共享空间的问题。可以通过画图来寻找问题的解，当空间 V装满后，必有栈 1 的栈项+1=栈 2 的栈顶，即 top1+1
21、=top2。【知识模块】 栈和队列10 【正确答案】 D【试题解析】 考查链栈的插入操作。实际上考查的是在一个链表的头结点后插入一个新结点的操作，因此如果熟练掌握了链表的插入操作，本题是比较容易的。由于该链表是带头结点的，因此 h 指向的是头结点，所以插入新结点的操作是：s 一lqext=h 一Fiext；h 一rtext=s；【知识模块】 栈和队列11 【正确答案】 B【试题解析】 考查对递归的理解和应用。由题得 f(0)=2；f(1)=1*f(0)=2；f(1)=f(2)=2*f(1)=4，即 f(1)=4。【知识模块】 栈和队列12 【正确答案】 B【试题解析】 考查对于递归的理解。一个
22、递归算法分为终止条件和递归部分两个部分。终止条件是递归算法的出口，也就是终止递归的条件。递归部分是一个递推的关系式。【知识模块】 栈和队列13 【正确答案】 A【试题解析】 考查递归算法转化为非递归算法的方法。栈的一个重要应用就是实现程序中的递归。【知识模块】 栈和队列14 【正确答案】 B【试题解析】 考查后缀表达式的计算方法。后缀表达式中，每一个计算符号均位于它的两个操作数的直接后面，按这样的方式逐步根据计算的优先级将每个计算式进行变换即可得到后缀表达式。或者还可以采用下面的方法：将表达式构造为一棵树，然后以后序遍历法遍历这棵树即可得到后缀表达式。同理可得前缀表达式、中缀表达式。比如在此题
23、中，表达式 a*(b+c)一 d 构造的树如图 21 所示。将此树按照后序遍历，即可得到 abc+*d 一。【知识模块】 栈和队列15 【正确答案】 B【试题解析】 考查由中缀表达式计算后缀表达式的方法。本题给出了中缀表达式，可以通过中缀表达式构建表达式的树结构，然后以后序遍历这棵树，即可得到后缀表达式。【知识模块】 栈和队列16 【正确答案】 A【试题解析】 考查由中缀表达式计算后缀表达式的方法。按照上题的方法，可以很快得出答案。【知识模块】 栈和队列17 【正确答案】 D【试题解析】 考查栈和队列的应用领域。栈通常在数制转换、括号匹配检验、表达式求值、行编辑程序设计以及迷宫求解等方面有应用
24、。【知识模块】 栈和队列18 【正确答案】 C【试题解析】 考查链队列的出队操作。链队列是一种特殊的链表。链队列的入队操作是在链表尾部插入一个新的结点，出队操作是在队头删除一个结点。所以只有等到只剩一个元素时，出队操作才会修改尾指针。【知识模块】 栈和队列19 【正确答案】 D【试题解析】 考查循环队列的基本概念。考生可以很容易判断 A、B 和 C 三项均不正确。【知识模块】 栈和队列20 【正确答案】 A【试题解析】 考查循环队列元素数的计算方法。对于循环队列，计算元素数目的公式就是(rearfront+m)m。【知识模块】 栈和队列21 【正确答案】 D【试题解析】 考查循环队列入队操作。
25、循环队列新元素入队时操作算法为rear=(rear+1)modmaxsize，本题中 maxsize=m+1。因此入队操作为 rear=(rear+1)mod(m+1)。【知识模块】 栈和队列22 【正确答案】 B【试题解析】 考查循环队列队空的条件。循环队列当队空的时候，rear=front。【知识模块】 栈和队列23 【正确答案】 D【试题解析】 考查循环队列队满的条件。原本队列满和空的时候都是Qfront=Qrear ，但是为了区分两种情况，通常牺牲一个存储空间，即每次入队前先判断(Qrear+1)M 是否等于 Qfront，是的话就认为队列已满。所以，Qfront=(Qrear+1)M
26、 便是队满的条件。【知识模块】 栈和队列24 【正确答案】 C【试题解析】 考查栈和队列的特性。【知识模块】 栈和队列25 【正确答案】 C【试题解析】 考查队列和栈的性质。由于队列“先进先出”，所以出队列的序列与进队列的序列是相同的，从而可以得到出栈的次序为 a3，a4，a2，a1，a5，a6：再由栈“先进后出”的特性，进栈的次序为 al，a2， a3，a4，a5 和 a6，可见，排在某个元素之后出栈却排在它之前进栈的元素个数，表示之前栈内的元素个数，因此a3 进栈后，a1 和 a2 在栈中，因此栈的最小容量为 3。【知识模块】 栈和队列26 【正确答案】 A【试题解析】 考查链栈的特点。顺
27、序栈是用一维数组实现的，链栈是用单链表实现的。当需要存储在顺序栈中的元素超过一维数组所能容纳的大小时，顺序栈是没有办法进行动态分配的。但是链栈就不存在这个问题。另外，当使用顺序栈时，由于栈的插入和删除结点都在栈顶，因此插入和删除只需要改变数组下标即可实现栈顶指针的修改。因此，和顺序栈相比，链栈的最大优势在于它可以动态的分配存储空间。【知识模块】 栈和队列27 【正确答案】 B【试题解析】 考查队列的应用领域。由于队列具有先进先出的特点，使得队列在树的层次遍历、图的广度优先遍历、离散时间模拟等方面均有应用。【知识模块】 栈和队列28 【正确答案】 C【试题解析】 考查矩阵的压缩存储。对称矩阵只需
28、要存储上(下)三角形(含对角线)元素，由题易得答案为 n(n+1)2。【知识模块】 栈和队列二、综合题29 【正确答案】 算法的基本设计思想：依次输入每个整数，然后判断是否是一1，如果是，则弹栈；不是，则入栈。算法的代码：void InOutS(int smaxsize) s 是元素为整数的栈，本算法进行入栈和退栈操作int top=0; top 为栈顶指针，定义 top=0 时为栈空for(int i=l； i1)printf(“栈号输入不对n”)；return 0；if(Stop1 一 Stop0=1)printf(“栈已满 n”)；return 0；SWitch(i)case 0：sst
29、ack+stop0=x；return 1；case 1：sstack|一 stop1=x；return 1； push2)出栈操作。算法的基本设计思想：同理设置一个变量来标识入哪个栈，若是 sl 栈出栈，s1 栈顶指针减_1若是 s2栈出栈，s2 栈顶指针加 1 即可。算法的代码：elemtp pop(int i)出栈算法。i 代表栈号，i=0 时为 s1 栈，i=l 时为 s2 栈出栈成功返回出栈元素，否则返回一 1if(i1)printf(“栈号输入错误n”)；return 0；switch(i)case 0：if(Stop0=1)printf(”栈空 n”)；return 一 1；els
30、ereturn(sstackstop0一一) ，case 1：if(Stop1=maxsizeprintf(、栈空n”)；return 一 1；e1Sereturn sstackstop1+ ； pop请注意算法中两栈入栈和出栈时的栈顶指针的计算。sl 栈是通常意义下的栈，而s2 栈入栈操作时，其栈顶指针减 1，出栈时，栈顶指针加 1。【知识模块】 栈和队列31 【正确答案】 算法的基本设计思想：逆波兰表达式(即后缀表达式)求值规则如下：设立运算数栈 OPND，对表达式从左到右扫描(读入)，当表达式中扫描到数时，压入 OPND 栈；当扫描到运算符时，从 OPND 栈退出两个数，进行相应运算，结
31、果再压入 OPND 栈。这个过程一直进行到读出表达式结束符$，这时 OPND 栈中只有一个数，就是结果。算法的代码：float exprO从键盘输入逆波兰表达式，以$表示输入结束，本算法求逆波兰式表达式的值float OPND30； OPND 是操作数栈init(OPND); N 栈初始化float num=00; 数字初始化scanf(”c”，case0：case1：case2：case3：case4：case5：case6：case7：case8：case9：case：while(x=0 x=0 xMaxValue(a，n 一 1)max=an；e1Semax=MaxValue(a，n 一
32、 1)；retUrn maX； MaxValue【知识模块】 栈和队列33 【正确答案】 算法的基本设计思想：利用递归算法，依次比较字符串中前后位置相对的元素是否相等。当字符串只剩一个元素或者两个元素(判断是否相等)时，递归过程终止。算法的代码：int teSt(char*S，int f，int e)f 是字符数组 S 的首元素下标，e 是末元素下标if(e 一 1=fSf=Se) f=e)return 1;if(Sf!=Se)return 0，return teSt(S，f+1，e 一 1); teSt【知识模块】 栈和队列34 【正确答案】 算法的基本设计思想：利用栈的先进后出的性质，依次
33、读入字符串中的字母，判断是大写还是小写，大写则压入栈 1 中，小写则压入栈 2 中，字符串读完之后分别输出栈 1 和栈 2 内的字母。算法的代码：VOid change(char*s)Stack S1，S2 ；假设栈是顺序栈，topl 是 s1 的栈顶指针，top2 是 s2 的栈顶指针int i=0;while(adata=x ;s 一next=rear 一next； 将 S 结点链入队尾rear 一next=S：rear=s； rear 指向新队尾2) VOid DeQueue(LinkedLiSt rear)rear 是带头结点的循环链队列的尾指针，本算法执行出队操作，操作成功输出队头元
34、素；否则给出出错信息if(rear 一neXt=：rear)printf(”队空 n”)；exit(1)，s=rear 一next 一next； S 指向队头元素rear 一next 一next=S 一next； 队头元素出队printf(“出队元素是d“，S-data)；if(S=rear)rear=rear-nextj 空队列free(s)；【知识模块】 栈和队列38 【正确答案】 双端队列示意图如下(设 maxsize=12)：算法的基本设计思想：用一维数组作存储结构，把它看作首尾相接的循环队列，可以在任一端(end1 或 end2)进行插入或删除操作。初始状态 end1+1=end2
35、被认为是队空状态，endl=end2 被认为是队满状态。end1 指向(左端队列 )队尾元素的前一位置，end2 指向(右端队列) 队尾元素的后一位置。入队时判队满，出队(删除)时判队空。删除一个元素时需要返回所删除元素的值。算法的代码： typedef Struct datatype elemmaxsi ze； int endl，end2 ; endl 和 end2 取值范围是0maxsize1 deque; int add(deque Qu，datatype X，int tag) 在双端队列 Qu 中插入元素 X，若插入成功，返回1：若插入失败，返回一 1 tag=0 表示在 end1 端
36、插入，tag=1 表示在 end2 端插入 if(Quendl=Quend2) printf(“ 队满“) ； retL1rn 1； switch(tag) Case 0： Quend1=x ； 插入 x Quencll= Qu endl 一 1+maxsize)maxsi ze; 修改endl return 1： case 1： Quend2=x： Quend2=(Quend2+1)maxsi ze； retuEn 1； add datatype delete(deque Qu，datatype x，int tag) 在双端队列 Qu中删除元素 x，tag=0 时从 endl 端删除，tag
37、=1 时从 encl2 端删除 删除成功返回被删元素的值，否则返回 NULL if(Quendl+1)%maxsize=Quend2) printf(“队空“)； return NULL： switch(tag) case 0： Quendl=(Quend1+1)maxsiZe； return QuelemQuend1; caSe 1： Quend2=(Quend21+maxsize)%maxsize; return QuelemQuenct2； delete 请注意下标运算。(i 十 1)mod maxsize容易理解。考虑到 i 一 1 可能为负的情况，所以求下个 i 时用 T(i 一 1
38、+maxsize)mod maxsize。【知识模块】 栈和队列39 【正确答案】 算法的基本设计思想：利用队列先进先出和栈后进先出的性质，先将非空队列中的元素出队，并压入初始为空的栈中。这时栈顶元素是队列中最后出队的元素。然后将栈中元素出栈，依次插入到初始为空的队列中。栈中第一个出栈的元素成为队列中第一个元素，最后出栈的元素(出队时第一个元素)成为最后入队的元素，从而实现了原队列的逆置。算法的代码：VOid Invert(queue Q)Q 是一个非空队列，本算法利用空栈 S 和已给的几个栈及队列的 ADT 函数将队列 Q 中的元素逆置makempty(S); 置空栈while(!isEmp
39、ty(Q) 队列 Q 中元素出队valHe=deOueue(Q)；push(s，value)； 将出队元素压入栈中while(!isEmpty(s) 栈中元素出栈Value=pop(S)；enQueue(Q，value); 将出栈元素入队列 Q invert【知识模块】 栈和队列40 【正确答案】 算法的基本设计思想：使用栈来判断链表中数据是否中心对称。将链表的前一半元素依次进栈。在处理链表的后一半元素时，当访问到链表的一个元素后，就从栈中弹出一个元素，两元素比较，若相等，则将链表中下一元素与栈中再弹出元素比较，直至链表到尾。这时若栈是空栈，则得出链表中心对称的结论：否则，当链表中一元素与栈中
40、弹出元素不等时，结论为链表非中心对称，结束算法的执行。算法的代码： int dc(Linkedlist h，int n)h 是带头结点的 n 个元素单链表，链表中结点的数据域是字符本算法判断链表是否中心对称char sn2；int,i=1； i 记结点个数，s 是字符栈p=h 一 next; p 是链表的工作指针，指向待处理的当前元素for(i=1；idata；p=p 一next；i 一一; 恢复最后的 i 值if(n2=1)p=p 一next; 若 n 是奇数，后移过中心结点whilep!=NULLsi=p 一data) 测试是否中心对称i 一一：p=p 一next；if(i=0) 栈为空栈return 1; 链表中心对称elsereturn 0， 链表不中心对称/dc本算法中先将“ 链表的前一半 ”元素(字符)进栈。当 n 为偶数时，前一半和后一半的个数相同；当 n 为奇数时，链表中心结点字符不必比较，移动链表指针到下一字符开始比较。比较过程中遇到不相等时，立即退出 while 循环，不再进行比较。【知识模块】 栈和队列
