1、计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编 3 及答案解析(总分：48.00，做题时间：90 分钟)一、综合题(总题数：3，分数：6.00)1.给出循环队列中元素个数的计算式(设队最大长度为 N，队首指针 FRONT，队尾指针 REAR)【西北大学2000 二、7(5 分)】（分数：2.00）_2.顺序队列一般应该组织成为环状队列的形式，而且一般队列头或尾其中之一应该特殊处理。例如，队列为 listarray0,n 一 1】，队列头指针为 front，队列尾指针为 rear，则 listarrayrear表示下一个可以插入队列的位置。请解释其原因。【北京大学 1999 一、3(20
2、3 分)】（分数：2.00）_3.设一个双端队列，元素进入该队列的次序为 a，b，c，d。求既不能由输入受限的双端队列得到，又不能由输出受限的双端队列得到的输出序列。【中山大学 1999 一、4(3 分)】（分数：2.00）_二、设计题(总题数：20，分数：42.00)4.设有两个栈 S1、S2 都采用顺序栈方式，并且共享一个存储区0maxsize 一 1，为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计 S1、S2 有关入栈和出栈的操作算法。【哈尔滨工业大学 2001 七(12 分)】（分数：2.00）_5.设从键盘输入一整数的序列：a 1 ，a 2 ，a 3 ，
3、a n ，试编写算法实现：用栈结构存储输入的整数，当 a i 一 1 时，将 a t 进栈；当 a y =1 时，输出栈顶整数并出栈。算法应对异常情况(入栈满等)给出相应的信息。【南京航空航天大学 1998 六(10 分)】（分数：2.00）_6.设表达式以字符形式已存入数组 En中，#为表达式的结束符，试写出判断表达式中括号(和)是否配对的 C 语言描述算法：EXYX(E)。(注：算法中可调用栈操作的基本算法。)【北京科技大学 2001 九、1(10 分)】（分数：2.00）_7.假设称正读和反读都相同的字符序列为“回文”，例如，abcba“是回文，abcde“和“ababab“则不是回文。
4、试写一个算法判别读入的一个以为结束符的字符序列是否是“回文”。【中国海洋大学 2007八(15 分)】（分数：2.00）_8.设计一个算法，判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的单循环链表中，每个结点有两个域：ch 和 link，其中 ch 域为字符类型。（分数：2.00）_9.设整数序列 a 1 ，a 2 ，a n ，给出求解最大值的递归程序。【南京航空航天大学 2000 六】（分数：2.00）_10.线性表中元素存放在向量 A(1，n)中，元素是整型数。试写出递归算法求出 A 中的最大和最小元素。【北京邮电大学 1994 八(10 分)】（分数：2.00）_11.已
5、知求两个正整数 m 与 n 的最大公因子的过程用自然语言可以表述为反复执行如下动作：第一步：若n 等于零，则返回 m；第二步：若 m 小于 n，则 m 与 n 相互交换；否则，保存 m，然后将 n 送 m，将保存的m 除以 n 的余数送 n。(1)将上述过程用递归函数表达出来(设求 x 除以 y 的余数可以用 x MODy 形式表示)。(2)写出求解该递归函数的非递归算法。【北京航空航天大学 2001 五(15 分)】（分数：2.00）_12.已知 Ackermann 函数定义如下： （分数：2.00）_13.设计算法以求解从集合1。n)中选取 k(kn)个元素的所有组合。例如，从集合14)中
6、选取 2 个元素的所有组合的输出结果为：1 2，1 3，1 4，2 3，2 4，3 4。【合肥工业大学 2000 五、5(8 分)】（分数：2.00）_14.对于任意的无符号的十进制整数 m，写出将其转换为十六进制整数的算法(转换仅要求能够输出正确的十六进制的整数即可)。【兰州大学 2000 九(10 分)】（分数：2.00）_15.已知递归函数 F(m)(其中 DIV 为整除)： （分数：2.00）_16.试设计算法，n 为大于等于 0 的整数，利用堆栈设计下列函数的非递归算法。 （分数：2.00）_17.已知有 n 个元素存放在向量 S1.n中，其值各不相同，请写一递归算法，生成并输出 n
7、 个元素的全排列。【中国科学技术大学 1992 十三(20 分)】【苏州大学 2005 五(15 分)】（分数：2.00）_18.请利用两个栈 S1 和 S2 来模拟一个队列。已知栈的三个运算定义如下：PUSH(ST,x)：元素 x 入 ST 栈；POP(ST x)：ST 栈顶元素出栈，赋给变量 x；Sempty(ST：判 ST 栈是否为空。那么如何利用栈的运算来实现该队列的三个运算：enqueue：插入一个元素入队列；dequeue：删除一个元素出队列；queue 一empty：判队列为空。(请写明算法的思想及必要的注释。)【上海交通大学 1999 二(12 分)】【厦门大学2005 六(1
8、5 分)】（分数：2.00）_19.设结点结构为(data，link)，试用一个全局指针 p 和某种链接结构实现一个队列，画出示意图，并给出入队 addq 和出队 deleteq 过程，要求它们的时间复杂性都是 O(1)(不计 new 和 dispose 时间)。【东南大学 1996 二(10 分)】（分数：2.00）_20.编程：假设以数组 Qm存放循环队列中的元素，同时以 rear 和 length 分别指示环形队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件，并写 出相应的初始化(initqueue)、插入(enqueue)和删除(dlqueue)元素的操作。
9、【天津大学 2002 一、5(10 分)】（分数：2.00）_如果允许在循环队列的两端都可以进行插入和删除操作。要求：（分数：4.00）(1).写出循环队列的类型定义；（分数：2.00）_(2).写出“从队尾删除”和“从队头插入”的算法。【北方交通大学 1994 三(12 分)】（分数：2.00）_21.已知 Q 是一个非空队列，S 是一个空栈。仅用队列和栈的 ADT 函数和少量工作变量，使用 Pascal 或 C语言编写一个算法，将队列 Q 中的所有元素逆置。栈的 ADT 函数有： makeEmpty(S：stack)； 置空栈 push(S：stack；value：datatype)； 新
10、元素 value 进栈 pop(S：stack)：datatype； 出栈，返回栈顶值 isEmpty(S：stack)：Boolean； 判栈空否 队列的 ADT 函数有： enQueue(q：queue：value：datatype)； 元素 value 进队 deQueue(q：queue)：datatype； 出队列，返回队头值 isEmpty(q：queue)：boolean； 判队列空否【清华大学 2000 六(12 分)】【华南理工大学 2005 二、7(4 分)】（分数：2.00）_22.将 n 个队列顺序映射到数组 v1m中，每一队列在 v 中表示为一循环队列。试画出其示意图
11、并写出对应这种表示的 addq 和 deleteq 过程。【东南大学 1993 二(20 分)】（分数：2.00）_计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编 3 答案解析(总分：48.00，做题时间：90 分钟)一、综合题(总题数：3，分数：6.00)1.给出循环队列中元素个数的计算式(设队最大长度为 N，队首指针 FRONT，队尾指针 REAR)【西北大学2000 二、7(5 分)】（分数：2.00）_正确答案：(正确答案：循环队列中元素个数为(REARFRONT+N)N。其中 FRONT 是队首指针，指向队首元素的前一位置；REAR 是队尾指针，指向队尾元素；N 是队列最大长
12、度。)解析：2.顺序队列一般应该组织成为环状队列的形式，而且一般队列头或尾其中之一应该特殊处理。例如，队列为 listarray0,n 一 1】，队列头指针为 front，队列尾指针为 rear，则 listarrayrear表示下一个可以插入队列的位置。请解释其原因。【北京大学 1999 一、3(203 分)】（分数：2.00）_正确答案：(正确答案：循环队列解决了用向量表示队列所出现的“假溢出”问题，但同时又出现了如何判断队列的满与空问题。例如：在队列长 10 的循环队列中，若假定队头指针 front 指向队头元素的前一位置，而队尾指针指向队尾元素，则 ffon=3，rear=7 的情况下
13、，连续出队 4 个元素，则 front=rear 为队空；如果连续入队 6 个元素，则 front=rear 为队满。如何判断这种情况下的队满与队空，一般采取牺牲一个单元的做法或设标记法。即假设 front=rear 为队空， 而(rear+1)表长=front 为队满，或通过设标记 tag。若 tag=0，front=rear 则为队空；若 tag=1，因入队而使得 fron=rear，则为队满。本题中队列尾指针 rear，指向队尾元素的下一位置，listarrayrear表示下一个入队的元素。在这种情况下，我们可规定，队头指针 front 指向队首元素。当 front=rear 时为队空，
14、当(rear+1)n=front 时为队满。出队操作(在队列不空情况下)队头指针是 front=(front+1)n。)解析：3.设一个双端队列，元素进入该队列的次序为 a，b，c，d。求既不能由输入受限的双端队列得到，又不能由输出受限的双端队列得到的输出序列。【中山大学 1999 一、4(3 分)】（分数：2.00）_正确答案：(正确答案：对于输入序列 a,b，c，d，无论是输入受限的双端队列，还是输出受限的双端队列，其输出序列中，以 a,b，c 开头的序列都有 6 个，如以 a 开头的有：abcd,abdc，acbd,acdb，adbc，adcb。但以元素 d 开头的只能得到 4 种序列。
15、输入受限的双端队列不能得到 dbac 和 dbca，输出受限的双端队列不能得到 dbca 和 dacb。故两种受限的双端队列均不能得到 dbca 输出序列。)解析：二、设计题(总题数：20，分数：42.00)4.设有两个栈 S1、S2 都采用顺序栈方式，并且共享一个存储区0maxsize 一 1，为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计 S1、S2 有关入栈和出栈的操作算法。【哈尔滨工业大学 2001 七(12 分)】（分数：2.00）_正确答案：(正确答案：两栈共享向量空间，将两栈栈底设在向量两端，初始时，左栈栈顶指针为一 1，右栈栈顶指针为 maxsiz
16、e。两栈顶指针相邻时为栈满。两栈顶相向，迎面增长，栈顶指针指向栈顶元素。 typede f struct ElemType stackmaxsize；栈空间 int top2；top 为两个栈顶指针 stk； 入栈操作的核心语句段如下： if(Stop1一 Stopo=1)coutx； 从键盘读入整数序列 if(x!=一 1) 读入的整数不等于一 1 时入栈 if(top=maxsize 一 1)coutch)；break： case)：if(StackEmpty(8)StackGetTop(s)!=() cout=0) if(maxAn)min：An； MinMaxValue(A，n-i，m
17、ax，min)； 算法结束 初始调用时参数 max 和 min 都赋初值 A0(数组名不一定用 A)。)解析：11.已知求两个正整数 m 与 n 的最大公因子的过程用自然语言可以表述为反复执行如下动作：第一步：若n 等于零，则返回 m；第二步：若 m 小于 n，则 m 与 n 相互交换；否则，保存 m，然后将 n 送 m，将保存的m 除以 n 的余数送 n。(1)将上述过程用递归函数表达出来(设求 x 除以 y 的余数可以用 x MODy 形式表示)。(2)写出求解该递归函数的非递归算法。【北京航空航天大学 2001 五(15 分)】（分数：2.00）_正确答案：(正确答案：两个正整数 m 和 n 的最大公因子的方法叫辗转相除法，也称欧几里德定理。其函数定义为： )解析：12.已知 Ackermann 函数定义如下： （分数：2.00）_正确答案：(正确答案：int Ack(int m，n) if(m=0)return(n+1)； else if(m!=0+)qif=qir=(i一 1)*L； qi是全局变量 (2)入队： int addq(int i；ElemType x) if(in)cout 第 i 个循环队列从下标(i1)L 开始，到 iL 一 1 为止。设每个循环队列均用牺牲一个单元的办法来判断队满，即为(gir+1)L+(i-1)*L=qif 时，判定为队满。)解析：
