1、计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编 5 及答案解析(总分：80.00，做题时间：90 分钟)一、单项选择题(总题数：28，分数：56.00)1.对于栈操作数据的原则是_。【青岛大学 2001 年】（分数：2.00）A.先进先出B.后进先出C.后进后出D.不分顺序2.在初始为空的堆栈中依次插入元素 f，e，d，c，b，a 以后，连续进行了三次删除操作，此时栈项元素是_。【北京航空航天大学 2002 年】（分数：2.00）A.cB.dC.bD.e3.六个不同元素依次进栈，能得到_种不同的出栈序列。【北京邮电大学 2007 年】（分数：2.00）A.42B.82C.132D.19
2、24.入栈序列为 1，2，3，4，5，则可能得到的出栈序列是_。【上海交通大学 2005】（分数：2.00）A.12534B.31254C.32541D.142355.一个栈的输入序列为 1，2，3，4，5，则下列序列中不可能是栈的输出序列的是_。【北京理工大学2000 年】【北京交通大学 2006 年】【中南大学 2003 年】（分数：2.00）A.23415B.54132C.23145D.154326.若已知一个栈的入栈序列为 1，2，3，4，其出栈序列为 pl，p2，p3，p4，则 p2，p4 不可能是_。【华中科技大学 2007 年】（分数：2.00）A.2、4B.2、1C.4、3D.
3、3、47.某堆栈的输入序列为 a，b，c，d，下面的四个序列中，不可能是它的输出序列的是_。【北京航空航天大学 2005 年】【北京邮电大学 2005 年】（分数：2.00）A.a，c，b，dB.b，c，d，aC.c，d，b，aD.d，c，a，b8.输入序列为 ABC，可以变为 CBA 时，经过的栈操作为_。【中山大学 1999 年】（分数：2.00）A.push，pop，push，pOp，push，popB.push，push，push，pOp，pOp，popC.push，push，pop，pOp，push，popD.push，pOp，push，push，pOp，pop9.若栈采用顺序存储方
4、式存储，现两栈共享空间 V1m，topi代表第 i 个栈(j=1，2)栈顶，栈 1 的底在 V【1】，栈 2 的底在 Vm，则栈满的条件是_。【南京理工大学 1999 年】（分数：2.00）A.1top2top11=0B.top1+1=top2C.top1+top2=mD.top1=top210.向一个栈顶指针为 h 的带头结点的链栈中插入指针 s 所指的结点时，应该执行_。【北京理工大学2005 年】（分数：2.00）A.hnext=s：B.s-next=h；C.snext=h：h-next=s；D.s-next=h 一nexth-next=S；11.执行完下列语句段后，i 值为_。【浙江大
5、学 2000 年】intf(intx)return(x0)?x*f(x 一 1)：2)；inti；i=f(f(1)；（分数：2.00）A.2B.4C.8D.无限递归12.一个递归算法必须包括_。【武汉大学 2000 年】（分数：2.00）A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分13.将递归算法转变成对应非递归算法时，需要使用_保存中间结果。【华中科技大学 2007 年】（分数：2.00）A.栈B.队列C.二叉树D.单链表14.表达式 a*(b+c)一 d 的后缀表达式是_。【南京理工大学 2001 年】（分数：2.00）A.abed*+一B.abc+*dC.abe*
6、+dD.-+*abcd15.中缀表达式(A+B)*(CD)(EF*G)的后缀表达式是_。【北京邮电大学 2005 年】（分数：2.00）A.A+B*CDEF*GB.AB 十 CD 一*EFG*一C.AB+C*DEFG+D.ABCDEFG+*一一*16.中缀表达式 A 一(B+CD)E 的后缀形式是_。【北京航空航天大学 2007 年】（分数：2.00）A.ABCD+E*一B.ABC+D*EC.ABC+DE*D.ABC 一+DE*17.设计一个判别表达式中左、右括号是否配对出现的算法，采用_数据结构最佳。【西安电子科技大学 1996 年】（分数：2.00）A.线性表的顺序存储结构B.队列C.线性
7、表的链式存储结构D.栈18.在链队列的出队操作中，修改尾指针的情况发生在_。【广东工业大学 2002 年】（分数：2.00）A.变成空队列的时候B.变成满队列的时候C.队列只剩一个元素的时候D.任何时候19.对于循环队列，正确的是_。【哈尔滨工业大学 2007 年】（分数：2.00）A.无法判断队列是否为空B.无法判断队列是否为满C.队列不可能满D.以上说法都不对20.循环队列 A0m 一 1存放其元素值，用 front 和 rear 分别表示队头和队尾，则当前队列中的元素数是_。【南京理工大学 2001 年】【华中科技大学 2007 年】（分数：2.00）A.(rearfront+m)mB.
8、rearfront+lC.rearfront 一 1D.rearfront21.循环队列存储在数组 A0m中，则入队时的操作为_。【中山大学 1999 年】（分数：2.00）A.rear=rear+1B.rear=(rear+1)mod(m 一 1)C.rear=(rear+1)modmD.rear=(rear+1)mod(re+1)22.最大容量为 n 的循环队列，队尾指针是 rear，队头是 front，则队空的条件是_。【南京理工大学1999 年】（分数：2.00）A.(rear+1)MODn=frontB.rear=frontC.rear+1=frontD.(rear11MODn=fr
9、ont23.判定一个长度为 M 的循环队列 Q 队满的条件是。【北京交通大学 2007 年】（分数：2.00）A.Qfront+1=QrearB.Qfront=Qrear+1C.Qfront=QrearD.Qfront=(Qrear+1)M24.栈和队列的共同点是。【燕山大学 2001 年】（分数：2.00）A.都是先进先出B.部是先进后出C.只允许在端点处插入和删除元素D.没有共同点25.栈 s 和队列 Q 的初始状态皆为空，元素 a1，a2，a3，a4，a5 和 a6 依次通过 s 栈，一个元素出栈后即进入队列 Q，若 6 个元素出队列的顺序是 a3，a4，a2，a1，a5，a6，则栈 s
10、 至少应该容纳_个元素。【哈尔滨工业大学 2004 年】（分数：2.00）A.6B.4C.3D.226.和顺序栈相比，链栈有一个比较明显的优势是_。【北京理工大学 2006 年】（分数：2.00）A.通常不会出现栈满的情况B.通常不会出现栈空的情况C.插入操作更容易实现D.删除操作更容易实现27.执行_操作时，需要使用队列作辅助存储空间。【华中科技大学 2006 年】（分数：2.00）A.查找散列表B.广度优先搜索网C.前序(根)遍历二叉树D.深度优先搜索网28.对 n 阶对称矩阵作压缩存储时，需要表长为_的顺序表【华中科技大学 2006 年】（分数：2.00）A.n2B.n,n2C.n(n+
11、1)2D.n(n 一 1)2二、综合题(总题数：12，分数：24.00)29.设从键盘输入一整数的序列：al，a2，a3，an，试编写算法实现：用栈结构存储输入的整数，当ai一 1 时，将 ai 进栈；当 ai=一 1 时，输出栈顶整数并出栈。算法应对异常情况(入栈满等)给出相应的信息。【南京航空航天大学 1998 年】（分数：2.00）_30.设有两个栈 s1、s2 都采用顺序栈方式，并且共享一个存储区0maxsize 一 1，为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计 s1、s2 有关入栈和出栈的操作算法。【哈尔滨工业大学 2001 年】（分数：2.00）
12、_31.从键盘上输入一个逆波兰表达式，写出其求值程序。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔，操作符只可能有+、一、*、四种运算。例如：23434+2*$。【山东师范大学 1999 年】（分数：2.00）_32.设整数序列 a1，a2，an，给出求解最大值的递归程序。【南京航空航天大学 2000 年】（分数：2.00）_33.给定一个由英文字母组成的字符串 s(假设 S 用数组实现)，编制一个递归函数，测试 s 是否为回文串，“回文串”是指从左向右读该字符串和从右向左读该字符串完全相同，例如：“noon”、“radar”等。【南京大学 2005 年】（分数
13、：2.00）_34.设一个由字母组成的字符串，编写算法对它们的字母顺序进行调整，使输出时所有大写字母都在小写字母之前，并且同类字母之间的相对位置颠倒。【华南理工大学 2005 年】例如：原有字符串为AbcDEfiglfiJKlmn，输出序列为 KJEDAnmlihgfcb。（分数：2.00）_35.已知求两个正整数 m 与 n 的最大公因子的过程用自然语言可以表述为反复执行如下动作：第一步：若n 等于零，则返回 m。第二步：若 m 小于 n，则 m 与 n 相互交换：否则，保存 m，然后将 n 送 m，将保存的m 除以 n 的余数送 n。1)将上述过程用递归函数表达出来(设求 x 除以 y 的
14、余数可以用 xMODy 形式表示)。2)写出求解该递归函数的非递归算法。【北京航空航天大学 2001 年】（分数：2.00）_36.试将下列递归过程改写为非递归过程。【北京轻工业学院 2000 年】void test(int sum) int x； scanf(”d，x)； 1t(x=0) sum=0； else test(sum)； Sum+=X； printf(“d”，sum)； （分数：2.00）_37.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，请写出相应的入队列和出队列算法。【华东师范大学 2000 年】【苏州大学 2002 年】（分数：2.00）_
15、38.一个双端队列 deque 是限定在两端 endl、end2 都可进行插入和删除的线性表，队空条件是endl+l=end2。若用顺序方式来组织双端队列，试根据下列要求，定义双端队列的结构，并给出在指定端i(i=1，2)的插入 enq 和删除 deq 操作的实现。1)当队满时，最多只能有一个元素空间可以是空的。2)在做两端的插入和删除时，队列中其他元素一律不动。【中南大学 2003 年】（分数：2.00）_39.已知 Q 是一个非空队列，s 是一个空栈。仅用队列和栈的 ADT 函数和少量工作变量，使用 C 语言编写一个算法，将队列 Q 中的所有元素逆置。栈的 ADT 函数有：【清华大学 20
16、00 年】 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)：boolean； 判队列空否（分数：2.00）_40.设单链表的表头指针为 h，结点结构由 data 和 n
17、ext 两个域构成，其中 data 域为字符型。写出算法dc(h，n)，判断该链表的前 n 个字符是否中心对称。例如：xyx、xyyx 都是中心对称。【首都经贸大学1998 年】（分数：2.00）_计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编 5 答案解析(总分：80.00，做题时间：90 分钟)一、单项选择题(总题数：28，分数：56.00)1.对于栈操作数据的原则是_。【青岛大学 2001 年】（分数：2.00）A.先进先出B.后进先出 C.后进后出D.不分顺序解析：解析：考查栈的概念。栈是一种后进先出的数据结构。2.在初始为空的堆栈中依次插入元素 f，e，d，c，b，a 以后，
18、连续进行了三次删除操作，此时栈项元素是_。【北京航空航天大学 2002 年】（分数：2.00）A.cB.d C.bD.e解析：解析：考查栈的基本性质。数据入栈时，先入栈的元素后出栈，只需简单地画图即可看出栈顶元素应是 d。3.六个不同元素依次进栈，能得到_种不同的出栈序列。【北京邮电大学 2007 年】（分数：2.00）A.42B.82C.132 D.192解析：解析：考查栈的基本性质。设有 n 个不同元素时，有 f(n)种出栈序列。若第一个元素是第 i 个出栈的，则在这个元素之前是编号为 2i 的元素出栈，之后是编号为 i+1n 的元素出栈。所以第一个元素是第 i 个出栈对应 f(i-1)*
19、f(ni)种出栈顺序。 f(1)=1 f(2)=2 f(3)=f(2)+f(1)*f(1)+f(2)=5 f(4)=f(3)+f(1)+f(2)十 f(2)+f(1)+f(3)=14 f(5)=f(4)+(1)+f(3)+“2)+f(2)+f(3)*(1)+f(4)=42 f(6)=f(5)+(1)+f(4)+f(2)+f(3)+f(3),f(2)+f(4)+f(1)+f(5)=42+14+10+10+14+42=1324.入栈序列为 1，2，3，4，5，则可能得到的出栈序列是_。【上海交通大学 2005】（分数：2.00）A.12534B.31254C.32541 D.14235解析：解析：
20、考查栈的性质。C 的情况是由以下操作得到：1、2、3 先入栈，接着 3 弹栈，2 弹栈，然后4、5 入栈，5 弹栈，4 弹栈，最后 1 弹栈。其他各种情况，都不可能由栈的操作得到。5.一个栈的输入序列为 1，2，3，4，5，则下列序列中不可能是栈的输出序列的是_。【北京理工大学2000 年】【北京交通大学 2006 年】【中南大学 2003 年】（分数：2.00）A.23415B.54132 C.23145D.15432解析：解析：考查栈的性质。考生可通过画图得出正确答案。A 是可能的：先是 1、2 入栈，然后 2 弹栈，3 入栈，3 弹栈，4 入栈，4 弹栈，1 弹栈，5 入栈，5 弹栈。C
21、 是可能的：1 和 2 入栈，2 弹栈，3 入栈，3弹栈，1 弹栈，4 入栈，4 弹栈，5 入栈，5 弹栈。D 是可能的：1 入栈，l 弹栈，2345 入栈，5432 弹栈。6.若已知一个栈的入栈序列为 1，2，3，4，其出栈序列为 pl，p2，p3，p4，则 p2，p4 不可能是_。【华中科技大学 2007 年】（分数：2.00）A.2、4B.2、1C.4、3 D.3、4解析：解析：考查栈的性质。对于 A，可能的顺序：1 入栈，1 弹栈，2 入栈，2 弹栈，3 入栈，3 弹栈，4入栈，4 弹栈。对于 B，可能的顺序：1 入栈，2 入栈，3 入栈，3 弹栈，2 弹栈，4 入栈，4 弹栈，1 弹
22、栈。对于 D，可能的顺序：1 入栈，1 弹栈，2 入栈，3 入栈，3 弹栈，2 弹栈，4 入栈，4 弹栈。C 则没有对应的序列。7.某堆栈的输入序列为 a，b，c，d，下面的四个序列中，不可能是它的输出序列的是_。【北京航空航天大学 2005 年】【北京邮电大学 2005 年】（分数：2.00）A.a，c，b，dB.b，c，d，aC.c，d，b，aD.d，c，a，b 解析：解析：考查栈的性质。A 可能的序列：a 入栈，a 出栈，b 入栈，c 入栈，c 出栈，b 出栈，d 入栈，d 出栈。B 可能的序列：a、b 入栈，b 出栈，c 入栈，c 出栈，d 入栈，d 出栈，a 出栈。C 可能的序列：a
23、、b、c 入栈，c 出栈，d 入栈，d 出栈，b 出栈，a 出栈。8.输入序列为 ABC，可以变为 CBA 时，经过的栈操作为_。【中山大学 1999 年】（分数：2.00）A.push，pop，push，pOp，push，popB.push，push，push，pOp，pOp，pop C.push，push，pop，pOp，push，popD.push，pOp，push，push，pOp，pop解析：解析：考查栈的性质。本题属于比较简单的类型。正确的顺序：A 入栈，B 入栈，c 入栈，c 弹栈，B 弹栈，A 弹栈。9.若栈采用顺序存储方式存储，现两栈共享空间 V1m，topi代表第 i 个栈
24、(j=1，2)栈顶，栈 1 的底在 V【1】，栈 2 的底在 Vm，则栈满的条件是_。【南京理工大学 1999 年】（分数：2.00）A.1top2top11=0B.top1+1=top2 C.top1+top2=mD.top1=top2解析：解析：考查栈共享空间的问题。可以通过画图来寻找问题的解，当空间 V 装满后，必有栈 1 的栈项+1=栈 2 的栈顶，即 top1+1=top2。10.向一个栈顶指针为 h 的带头结点的链栈中插入指针 s 所指的结点时，应该执行_。【北京理工大学2005 年】（分数：2.00）A.hnext=s：B.s-next=h；C.snext=h：h-next=s；
25、D.s-next=h 一nexth-next=S； 解析：解析：考查链栈的插入操作。实际上考查的是在一个链表的头结点后插入一个新结点的操作，因此如果熟练掌握了链表的插入操作，本题是比较容易的。由于该链表是带头结点的，因此 h 指向的是头结点，所以插入新结点的操作是：s 一lqext=h 一Fiext；h 一rtext=s；11.执行完下列语句段后，i 值为_。【浙江大学 2000 年】intf(intx)return(x0)?x*f(x 一 1)：2)；inti；i=f(f(1)；（分数：2.00）A.2B.4 C.8D.无限递归解析：解析：考查对递归的理解和应用。由题得 f(0)=2；f(1
26、)=1*f(0)=2；f(1)=f(2)=2*f(1)=4，即 f(1)=4。12.一个递归算法必须包括_。【武汉大学 2000 年】（分数：2.00）A.递归部分B.终止条件和递归部分 C.迭代部分D.终止条件和迭代部分解析：解析：考查对于递归的理解。一个递归算法分为终止条件和递归部分两个部分。终止条件是递归算法的出口，也就是终止递归的条件。递归部分是一个递推的关系式。13.将递归算法转变成对应非递归算法时，需要使用_保存中间结果。【华中科技大学 2007 年】（分数：2.00）A.栈 B.队列C.二叉树D.单链表解析：解析：考查递归算法转化为非递归算法的方法。栈的一个重要应用就是实现程序中
27、的递归。14.表达式 a*(b+c)一 d 的后缀表达式是_。【南京理工大学 2001 年】（分数：2.00）A.abed*+一B.abc+*d C.abe*+dD.-+*abcd解析：解析：考查后缀表达式的计算方法。后缀表达式中，每一个计算符号均位于它的两个操作数的直接后面，按这样的方式逐步根据计算的优先级将每个计算式进行变换即可得到后缀表达式。或者还可以采用下面的方法：将表达式构造为一棵树，然后以后序遍历法遍历这棵树即可得到后缀表达式。同理可得前缀表达式、中缀表达式。比如在此题中，表达式 a*(b+c)一 d 构造的树如图 21 所示。15.中缀表达式(A+B)*(CD)(EF*G)的后缀
28、表达式是_。【北京邮电大学 2005 年】（分数：2.00）A.A+B*CDEF*GB.AB 十 CD 一*EFG*一 C.AB+C*DEFG+D.ABCDEFG+*一一*解析：解析：考查由中缀表达式计算后缀表达式的方法。本题给出了中缀表达式，可以通过中缀表达式构建表达式的树结构，然后以后序遍历这棵树，即可得到后缀表达式。16.中缀表达式 A 一(B+CD)E 的后缀形式是_。【北京航空航天大学 2007 年】（分数：2.00）A.ABCD+E*一 B.ABC+D*EC.ABC+DE*D.ABC 一+DE*解析：解析：考查由中缀表达式计算后缀表达式的方法。按照上题的方法，可以很快得出答案。17
29、.设计一个判别表达式中左、右括号是否配对出现的算法，采用_数据结构最佳。【西安电子科技大学 1996 年】（分数：2.00）A.线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈 解析：解析：考查栈和队列的应用领域。栈通常在数制转换、括号匹配检验、表达式求值、行编辑程序设计以及迷宫求解等方面有应用。18.在链队列的出队操作中，修改尾指针的情况发生在_。【广东工业大学 2002 年】（分数：2.00）A.变成空队列的时候B.变成满队列的时候C.队列只剩一个元素的时候 D.任何时候解析：解析：考查链队列的出队操作。链队列是一种特殊的链表。链队列的入队操作是在链表尾部插入一个新的结点，出队操
30、作是在队头删除一个结点。所以只有等到只剩一个元素时，出队操作才会修改尾指针。19.对于循环队列，正确的是_。【哈尔滨工业大学 2007 年】（分数：2.00）A.无法判断队列是否为空B.无法判断队列是否为满C.队列不可能满D.以上说法都不对 解析：解析：考查循环队列的基本概念。考生可以很容易判断 A、B 和 C 三项均不正确。20.循环队列 A0m 一 1存放其元素值，用 front 和 rear 分别表示队头和队尾，则当前队列中的元素数是_。【南京理工大学 2001 年】【华中科技大学 2007 年】（分数：2.00）A.(rearfront+m)m B.rearfront+lC.rearf
31、ront 一 1D.rearfront解析：解析：考查循环队列元素数的计算方法。对于循环队列，计算元素数目的公式就是(rearfront+m)m。21.循环队列存储在数组 A0m中，则入队时的操作为_。【中山大学 1999 年】（分数：2.00）A.rear=rear+1B.rear=(rear+1)mod(m 一 1)C.rear=(rear+1)modmD.rear=(rear+1)mod(re+1) 解析：解析：考查循环队列入队操作。循环队列新元素入队时操作算法为 rear=(rear+1)modmaxsize，本题中 maxsize=m+1。因此入队操作为 rear=(rear+1)m
32、od(m+1)。22.最大容量为 n 的循环队列，队尾指针是 rear，队头是 front，则队空的条件是_。【南京理工大学1999 年】（分数：2.00）A.(rear+1)MODn=frontB.rear=front C.rear+1=frontD.(rear11MODn=front解析：解析：考查循环队列队空的条件。循环队列当队空的时候，rear=front。23.判定一个长度为 M 的循环队列 Q 队满的条件是。【北京交通大学 2007 年】（分数：2.00）A.Qfront+1=QrearB.Qfront=Qrear+1C.Qfront=QrearD.Qfront=(Qrear+1)
33、M 解析：解析：考查循环队列队满的条件。原本队列满和空的时候都是 Qfront=Qrear，但是为了区分两种情况，通常牺牲一个存储空间，即每次入队前先判断(Qrear+1)M 是否等于 Qfront，是的话就认为队列已满。所以，Qfront=(Qrear+1)M 便是队满的条件。24.栈和队列的共同点是。【燕山大学 2001 年】（分数：2.00）A.都是先进先出B.部是先进后出C.只允许在端点处插入和删除元素 D.没有共同点解析：解析：考查栈和队列的特性。25.栈 s 和队列 Q 的初始状态皆为空，元素 a1，a2，a3，a4，a5 和 a6 依次通过 s 栈，一个元素出栈后即进入队列 Q，
34、若 6 个元素出队列的顺序是 a3，a4，a2，a1，a5，a6，则栈 s 至少应该容纳_个元素。【哈尔滨工业大学 2004 年】（分数：2.00）A.6B.4C.3 D.2解析：解析：考查队列和栈的性质。由于队列“先进先出”，所以出队列的序列与进队列的序列是相同的，从而可以得到出栈的次序为 a3，a4，a2，a1，a5，a6：再由栈“先进后出”的特性，进栈的次序为al，a2，a3，a4，a5 和 a6，可见，排在某个元素之后出栈却排在它之前进栈的元素个数，表示之前栈内的元素个数，因此 a3 进栈后，a1 和 a2 在栈中，因此栈的最小容量为 3。26.和顺序栈相比，链栈有一个比较明显的优势是
35、_。【北京理工大学 2006 年】（分数：2.00）A.通常不会出现栈满的情况 B.通常不会出现栈空的情况C.插入操作更容易实现D.删除操作更容易实现解析：解析：考查链栈的特点。顺序栈是用一维数组实现的，链栈是用单链表实现的。当需要存储在顺序栈中的元素超过一维数组所能容纳的大小时，顺序栈是没有办法进行动态分配的。但是链栈就不存在这个问题。另外，当使用顺序栈时，由于栈的插入和删除结点都在栈顶，因此插入和删除只需要改变数组下标即可实现栈顶指针的修改。因此，和顺序栈相比，链栈的最大优势在于它可以动态的分配存储空间。27.执行_操作时，需要使用队列作辅助存储空间。【华中科技大学 2006 年】（分数：
36、2.00）A.查找散列表B.广度优先搜索网 C.前序(根)遍历二叉树D.深度优先搜索网解析：解析：考查队列的应用领域。由于队列具有先进先出的特点，使得队列在树的层次遍历、图的广度优先遍历、离散时间模拟等方面均有应用。28.对 n 阶对称矩阵作压缩存储时，需要表长为_的顺序表【华中科技大学 2006 年】（分数：2.00）A.n2B.n,n2C.n(n+1)2 D.n(n 一 1)2解析：解析：考查矩阵的压缩存储。对称矩阵只需要存储上(下)三角形(含对角线)元素，由题易得答案为n(n+1)2。二、综合题(总题数：12，分数：24.00)29.设从键盘输入一整数的序列：al，a2，a3，an，试编
37、写算法实现：用栈结构存储输入的整数，当ai一 1 时，将 ai 进栈；当 ai=一 1 时，输出栈顶整数并出栈。算法应对异常情况(入栈满等)给出相应的信息。【南京航空航天大学 1998 年】（分数：2.00）_正确答案：(正确答案：算法的基本设计思想：依次输入每个整数，然后判断是否是一 1，如果是，则弹栈；不是，则入栈。算法的代码： void InOutS(int smaxsize) s 是元素为整数的栈，本算法进行入栈和退栈操作 int top=0; top 为栈顶指针，定义 top=0 时为栈空 for(int i=l；i=“0“ x=“0“ xMaxValue(a，n 一 1) max=
38、an； e1Se max=MaxValue(a，n 一 1)； retUrn maX； MaxValue)解析：33.给定一个由英文字母组成的字符串 s(假设 S 用数组实现)，编制一个递归函数，测试 s 是否为回文串，“回文串”是指从左向右读该字符串和从右向左读该字符串完全相同，例如：“noon”、“radar”等。【南京大学 2005 年】（分数：2.00）_正确答案：(正确答案：算法的基本设计思想：利用递归算法，依次比较字符串中前后位置相对的元素是否相等。当字符串只剩一个元素或者两个元素(判断是否相等)时，递归过程终止。算法的代码： int teSt(char*S，int f，int e
39、) 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.设一个由字母组成的字符串，编写算法对它们的字母顺序进行调整，使输出时所有大写字母都在小写字母之前，并且同类字母之间的相对位置颠倒。【华南理工大学 2005 年】例如：原有字符串为AbcDEfiglfiJKlmn，输出序列为 KJEDAnmlihgfcb。（分数：2.00）_正确答案：(正确答案：算法的基本设计思想：利用栈的先进后出的性质，依次读入字符串中的字母，判
40、断是大写还是小写，大写则压入栈 1 中，小写则压入栈 2 中，字符串读完之后分别输出栈 1 和栈 2 内的字母。算法的代码： VOid change(char*s) Stack S1，S2； 假设栈是顺序栈，topl 是 s1 的栈顶指针，top2 是 s2 的栈顶指针 int i=0; while(“a“data=x ; s 一next=rear 一next； 将 S 结点链入队尾 rear 一next=S： rear=s； rear 指向新队尾 2) VOid DeQueue(LinkedLiSt rear) rear是带头结点的循环链队列的尾指针，本算法执行出队操作，操作成功输出队头元素
41、；否则 给出出错信息 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.一个双端队列 deque 是限定在两端 endl、end2 都可进行插入和删除的线性表，队空条件是endl+l=end2。若用顺序方式来组织双端队列，试根据下列要求，定义双端队列的结构，并给出在指定端i(i=1，2)的插
42、入 enq 和删除 deq 操作的实现。1)当队满时，最多只能有一个元素空间可以是空的。2)在做两端的插入和删除时，队列中其他元素一律不动。【中南大学 2003 年】（分数：2.00）_正确答案：(正确答案：双端队列示意图如下(设 maxsize=12)： )解析：39.已知 Q 是一个非空队列，s 是一个空栈。仅用队列和栈的 ADT 函数和少量工作变量，使用 C 语言编写一个算法，将队列 Q 中的所有元素逆置。栈的 ADT 函数有：【清华大学 2000 年】 makeEmpty(s：stack)；置空栈 push(s：stack；value：datatype)； 新元素 value 进栈 p
43、op(s：stack)：datatype； 出栈，返回栈顶值 isEmptys：stack)：Boolean； 判栈空否 队列的 ADT 函数有： enqueue(q：queue；value：datatype)； 元素 value 进队 deQueue(q：queue)：datatype； 出队列，返回队头值 isEmpty(q：queue)：boolean； 判队列空否（分数：2.00）_正确答案：(正确答案：算法的基本设计思想：利用队列先进先出和栈后进先出的性质，先将非空队列中的元素出队，并压入初始为空的栈中。这时栈顶元素是队列中最后出队的元素。然后将栈中元素出栈，依次插入到初始为空的队列中。栈中第一个出栈的元素成为队列中第一个元素，最后出栈的元素(出队时第一个元素)成为最后入队的元素，从而实现了原队列的逆置。算法的代码： VOid Invert(queue Q) Q
