1、计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编 7 及答案与解析一、综合题1 给出循环队列中元素个数的计算式(设队最大长度为 N，队首指针 FRONT，队尾指针 REAR)【西北大学 2000 二、7(5 分)】2 顺序队列一般应该组织成为环状队列的形式，而且一般队列头或尾其中之一应该特殊处理。例如，队列为 listarray0,n 一 1】，队列头指针为 front，队列尾指针为rear，则 listarrayrear表示下一个可以插入队列的位置。请解释其原因。【北京大学 1999 一、3(203 分) 】3 设一个双端队列，元素进入该队列的次序为 a，b，c ，d。求既不能由输入受
2、限的双端队列得到，又不能由输出受限的双端队列得到的输出序列。【中山大学1999 一、4(3 分) 】二、设计题4 设有两个栈 S1、S2 都采用顺序栈方式，并且共享一个存储区0maxsize 一1，为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计 S1、S2 有关入栈和出栈的操作算法。 【哈尔滨工业大学 2001 七(12 分)】5 设从键盘输入一整数的序列：a 1，a 2，a 3，a n，试编写算法实现：用栈结构存储输入的整数，当 ai一 1 时，将 at 进栈；当 ay=1 时，输出栈顶整数并出栈。算法应对异常情况(入栈满等) 给出相应的信息。【南京航空航天大学
3、 1998 六(10 分)】6 设表达式以字符形式已存入数组 En中，# 为表达式的结束符，试写出判断表达式中括号(和)是否配对的 C 语言描述算法：EXYX(E) 。(注：算法中可调用栈操作的基本算法。)【北京科技大学 2001 九、1(10 分)】7 假设称正读和反读都相同的字符序列为“回文” ，例如， abcba是回文，abcde和ababab则不是回文。试写一个算法判别读入的一个以为结束符的字符序列是否是“回文”。【中国海洋大学 2007 八(15 分)】8 设计一个算法，判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的单循环链表中，每个结点有两个域：ch 和 link，
4、其中 ch 域为字符类型。9 设整数序列 a1，a 2， an，给出求解最大值的递归程序。【南京航空航天大学2000 六】10 线性表中元素存放在向量 A(1，n)中，元素是整型数。试写出递归算法求出 A 中的最大和最小元素。【北京邮电大学 1994 八(10 分)】11 已知求两个正整数 m 与 n 的最大公因子的过程用自然语言可以表述为反复执行如下动作：第一步：若 n 等于零，则返回 m；第二步：若 m 小于 n，则 m 与 n 相互交换；否则，保存 m，然后将 n 送 m，将保存的 m 除以 n 的余数送 n。(1)将上述过程用递归函数表达出来(设求 x 除以 y 的余数可以用 x MO
5、Dy 形式表示)。(2)写出求解该递归函数的非递归算法。【北京航空航天大学 2001 五(15 分)】12 已知 Ackermann 函数定义如下：(1)写出 Ack(2，1)的计算过程。(2)写出计算 Ack(m，n) 的非递归算法。【北京师范大学 2005 六、2(15 分)】【北京航空航天大学 1999 六(15 分)】13 设计算法以求解从集合1。n)中选取 k(kn)个元素的所有组合。例如，从集合14)中选取 2 个元素的所有组合的输出结果为： 1 2，1 3，1 4，2 3，2 4，3 4。【合肥工业大学 2000 五、5(8 分)】14 对于任意的无符号的十进制整数 m，写出将其
6、转换为十六进制整数的算法 (转换仅要求能够输出正确的十六进制的整数即可)。【兰州大学 2000 九(10 分)】15 已知递归函数 F(m)(其中 DIV 为整除)：(1)写出求 F(m)的递归算法；(2)写出求 F(m)的非递归算法。【北京师范大学 2003 五、3(1 5 分)】16 试设计算法，n 为大于等于 0 的整数，利用堆栈设计下列函数的非递归算法。【天津大学 2006 二、2(7 分)】17 已知有 n 个元素存放在向量 S1.n中，其值各不相同，请写一递归算法，生成并输出 n 个元素的全排列。【中国科学技术大学 1992 十三(20 分)】【苏州大学2005 五(15 分) 】
7、18 请利用两个栈 S1 和 S2 来模拟一个队列。已知栈的三个运算定义如下：PUSH(ST,x)：元素 x 入 ST 栈；POP(ST x)：ST 栈顶元素出栈，赋给变量x；Sempty(ST：判 ST 栈是否为空。那么如何利用栈的运算来实现该队列的三个运算：enqueue：插入一个元素入队列；dequeue ：删除一个元素出队列；queue 一empty：判队列为空。( 请写明算法的思想及必要的注释。)【上海交通大学 1999 二(12 分)】【厦门大学 2005 六(15 分) 】19 设结点结构为(data，link)，试用一个全局指针 p 和某种链接结构实现一个队列，画出示意图，并给
8、出入队 addq 和出队 deleteq 过程，要求它们的时间复杂性都是O(1)(不计 new 和 dispose 时间)。【东南大学 1996 二(10 分)】20 编程：假设以数组 Qm存放循环队列中的元素，同时以 rear 和 length 分别指示环形队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件，并写 出相应的初始化(initqueue)、插入(enqueue)和删除(dlqueue)元素的操作。【天津大学 2002 一、5(10 分)】20 如果允许在循环队列的两端都可以进行插入和删除操作。要求：21 写出循环队列的类型定义；22 写出“从队尾删除 ”
9、和“从队头插入”的算法。【北方交通大学 1994 三(12 分)】23 已知 Q 是一个非空队列，S 是一个空栈。仅用队列和栈的 ADT 函数和少量工作变量，使用Pascal 或 C 语言编写一个算法，将队列 Q 中的所有元素逆置。栈的 ADT 函数有：makeEmpty(S：stack)； 置空栈push(S：stack；value：datatype)； 新元素 value 进栈pop(S：stack)：datatype； 出栈，返回栈顶值isEmpty(S：stack)：Boolean； 判栈空否队列的 ADT 函数有：enQueue(q：queue：value ：datatype) ；
10、元素 value 进队deQueue(q：queue)：datatype； 出队列，返回队头值isEmpty(q：queue) ：boolean； 判队列空否 【清华大学 2000 六(12 分)】【华南理工大学 2005 二、7(4 分)】24 将 n 个队列顺序映射到数组 v1m中，每一队列在 v 中表示为一循环队列。试画出其示意图并写出对应这种表示的 addq 和 deleteq 过程。【东南大学 1993 二(20 分)】计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编 7 答案与解析一、综合题1 【正确答案】 循环队列中元素个数为(REARFRONT+N)N 。其中 FRONT
11、 是队首指针，指向队首元素的前一位置；REAR 是队尾指针，指向队尾元素；N 是队列最大长度。2 【正确答案】 循环队列解决了用向量表示队列所出现的“假溢出” 问题，但同时又出现了如何判断队列的满与空问题。例如：在队列长 10 的循环队列中，若假定队头指针 front 指向队头元素的前一位置，而队尾指针指向队尾元素，则ffon=3，rear=7 的情况下，连续出队 4 个元素，则 front=rear 为队空；如果连续入队 6 个元素，则 front=rear 为队满。如何判断这种情况下的队满与队空，一般采取牺牲一个单元的做法或设标记法。即假设 front=rear 为队空， 而(rear+1
12、)表长=front 为队满，或通过设标记 tag。若 tag=0，front=rear 则为队空；若 tag=1，因入队而使得 fron=rear，则为队满。本题中队列尾指针 rear，指向队尾元素的下一位置，listarrayrear表示下一个入队的元素。在这种情况下，我们可规定，队头指针 front 指向队首元素。当 front=rear 时为队空，当(rear+1)n=front 时为队满。出队操作(在队列不空情况下)队头指针是 front=(front+1)n。3 【正确答案】 对于输入序列 a,b，c ，d，无论是输入受限的双端队列，还是输出受限的双端队列，其输出序列中，以 a,b，
13、c 开头的序列都有 6 个，如以 a 开头的有：abcd,abdc，acbd,acdb，adbc，adcb。但以元素 d 开头的只能得到 4 种序列。输入受限的双端队列不能得到 dbac 和 dbca，输出受限的双端队列不能得到 dbca 和dacb。故两种受限的双端队列均不能得到 dbca 输出序列。二、设计题4 【正确答案】 两栈共享向量空间，将两栈栈底设在向量两端，初始时，左栈栈顶指针为一 1，右栈栈顶指针为 maxsize。两栈顶指针相邻时为栈满。两栈顶相向，迎面增长，栈顶指针指向栈顶元素。typede f structElemType stackmaxsize；栈空间int top2
14、；top 为两个栈顶指针stk；入栈操作的核心语句段如下：if(Stop1 一 Stopo=1)coutx； 从键盘读入整数序列if(x!=一 1) 读入的整数不等于一 1 时入栈if(top=maxsize 一 1)coutch)； break：case)：if(StackEmpty(8)StackGetTop(s)!=()coutMaxValue(a，n 一 1)maxn=an； else maxn=MaxValue(a，n 一 1)；10 【正确答案】 只是结果要最大和最小元素，现给出完整函数。void MinMaxValue(int A，int n，int stop1=t； retur
15、n(stop0)； 算法结束 由于是尾递归，可以不使用栈，其非递归算法如下： int gcd(int m，n) 求正整数 m 和 rl 的最大公因子 if(mn)t=m;m=n；n=t；) 若 mrl，则 m 和n 互换 while(n!=0)t=tn；tll=n；n=七n； reLurn(m)； 算法结束12 【正确答案】 int Ack(int m，n)if(m=0)return(n+1)；else if(m!=0&n=0)return(Ack(m-1，1)；else return(Ack(m-1，Ack(m，m 一 1)；算法结束Ack(2，1)的计算过程：Ack(2，1)=Ack(1，
16、Ack(2，0) 因 m0 而得=Ack(1，Ack(1，1) 因 m0，n0，n=0 而得=Ack(1，Ack(0，2) 因 m=0 而得=Ack(1，3) 因 m=0 而得=Ack(0，Ack(1，2) 因 m0 而得=Ack(0，Ack(0，Ack(1 ，1) 因 m0 而得=Ack(0，Ack(0，Ack(0 ，Ack(1，0) 因 m0 而得=Ack(0，Ack(0，Ack(0 ，Ack(0，1) 因 mnext=p 一next；P 一next=s； 将 S 结点链入队尾p=s； P 指向新队尾出队的核心语句段如下：if(p-next=p) coutnext 一next；p-next
17、-next=s-next； s 指向队头元素，出队coutdatanext ； 空队列delete(s)； 回收空间20 【正确答案】 循环队列的定义：typedef structElemType Qm；int rear，length；)SeQueue；rear 指向队尾元素，length 为元素数(1)设 cq 是 SeQueue 类型变量，当 cqlength=0 时队空，当 cq1ength=m 时队满。(2)SeQueue initqueue(SeQueue cq) cq 为循环队列，本算法进行队列初始化cqrear=0；cq 1ength=0； return cq；(3)SeQueu
18、e enqueue(SeQueue cq，ElemType x)入队算法，元素 x 入队if(cq1ength=m)return(0)； 队满else fcqrear=(cq rear+1)m； 计算插入元素位置cqQcq rear=x； 将元素 x 入队列cq1ength+ ； 修改队列长度return(cq)；) 算法结束(4)ElemType dlqueue(SeQueue cq) 出队算法，且返回出队元素if(cq1ength=0)return(0)； 队空else(int front=(cqrearcq1ength+1+m)m； 出队元素位置cq1ength- 一； 修改队列长度re
19、turn(cqQfront)； 返回队头元素 else) 算法结束21 【正确答案】 用一维数组 v0M-1实现循环队列，其中 M 是队列长度。设队头指针 front 和队尾指针 rear，约定 front 指向队头元素的前一位置，rear 指向队尾元素。定义 front=rear 时为队空，(rear+1)m=front 为队满。约定队头端入队向下标小的方向发展，队尾端入队向下标大的方向发展。(1)从队尾删除元素的核心语句段如下：if(Qfront=Qrear) Gout“队列空”end1；exit(0)；)Qrear=(Q rear 一 1+M)M； 修改队尾指针return(Q data
20、(Qrear+1+M)M)； 返回出队元素22 【正确答案】 从队头插入元素 X 的核心语句段如下：if(Qrear=(Qfront 一 1+M)M) cout“ 队满 ”endl； exit(0)；)QdataQ front=x； x 入队列Qfront=(Qfront 一 1+M)M； 修改队头指针23 【正确答案】 根据队列先进先出和栈后进先出的性质，先将非空队列中的元素出队，并压入初始为空的栈中。这时栈顶元素是队列中最后出队的元素。然后将栈中元素出栈，依次插入初始为空的队列中。栈中第一个退栈的元素成为队列中第一个元素，最后退栈的元素(出队时第一个元素)成了最后入队的元素，从而实现了原队
21、列的逆置。核心语句段如下：makempty(s)； 置空栈while(!isEmpty(Q) 队列 Q 中元素出队value=deQueue(Q)；push(s ，value) ； 将出队元素压入栈中while(!isEmpty(s) 栈中元素退栈value=pop(s)； enQueue(Q，value)；) 将出栈元素入队列 Q24 【正确答案】 设数组下标从 0 开始，即数组 v0m 一 1。设每个循环队列长度(容量 )为 L，则循环队列的个数为 n=mL为了指示每个循环队列的队头和队尾，设如下结构类型： typedef structint f，r；)scq； scq qn； (1)初始化的核心语句： for(i=1；in)coutn)fprintf C 队列号错误n”) ；exit(0)；) if(qir=qif) cout 第i 个循环队列从下标(i1)L 开始，到 iL 一 1 为止。设每个循环队列均用牺牲一个单元的办法来判断队满，即为(gir+1)L+(i-1)*L=qif 时，判定为队满。
