栈与队列习题与答案(3)

学 1999 一、1 （7分）】 34．一个循环队列的数据结构描述如下： TYPE sequeuetp=RECORD

elem：ARRAY[1..MAXSIZE] OF elemtp； front，rear：0..MAXSIZE； END；

给出循环队列的队空和队满的判断条件，并且分析一下该条件对队列实际存储空间大小的影响，如果为了不损失存储空间，你如何改进循环队列的队空和队满的判断条件？【西北工业大学 1999 三 (8分)】

35. 如果用一个循环数组q[0..m-1]表示队列时，该队列只有一个队列头指针front，不设队列尾指针rear，而改置计数器count用以记录队列中结点的个数。 （1）编写实现队列的三个基本运算：判空、入队、出队（3分） （2）队列中能容纳元素的最多个数是多少？（1分）【东北大学 2002 一、1】 36. 给出循环队列中元素个数的计算式(设队最大长度为N,队首指针FRONT，队尾指针REAR) 【西北大学 2000 二、7 (5分)】

37. 顺序队列一般应该组织成为环状队列的形式，而且一般队列头或尾其中之一应该特殊处理。例如，队列为listarray[0..n-1]，队列头指针为 front，队列尾指针为 rear， 则listarray [rear]表示下一个可以插入队列的位置。请解释其原因。【北京大学 1999 一、3 （20/3分）】

38. 设一个双端队列，元素进入该队列的次序为a，b，c，d。求既不能由输入受限的双端队列得到,又不能由输出受限的双端队列得到的输出序列。【中山大学 1999 一、4 （3分）】 39. 若以1、2、3、4作为双端队列的输入序列，试分别求出以下条件的输出序列： （1）能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列； （2）能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列； （3）既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列。 【山东科技大学 2001 一、3 （6分）】

40. 假设以数组sq[0..7]存放循环队列元素,变量f指向队头元素的前一位置,变量r指向队尾元素，如用A和D分别表示入队和出队操作，请给出： （1） 队空的初始条件; （2） 执行操作序列A3D1A5D2A1D2A4时的状态,并作必要的说明。【北方交通大学 1993 四（12分）】

41、设输入元素为1、2、3、P和A，输入次序为123PA，如图（编者略）。元素经过栈后达输出序列，当所有元素均到达输出序列后，有哪些序列可以作为高级语言的变量名。【中山大学 1997】

五 算法设计题

1. 设有两个栈S1,S2都采用顺序栈方式，并且共享一个存储区[O..maxsize-1],为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。

【哈尔滨工业大学 2001 七 （12分）】 2. 设从键盘输入

一整数的序列：a1, a2, a3，?，an,试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。 【南京航空航天大学 1998 六 （10分）】 3. 设表达式以字符形式已存入数组E[n]中，‘#’为表达式的结束符，试写出判断表达式中括号（‘（’和‘）’）是否配对的C语言描述算法：EXYX(E); (注：算法中可调用栈操作的基本算法。)

【北京科技大学 2001 九、1 （10分）】

4. 从键盘上输入一个逆波兰表达式，用伪码写出其求值程序。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如：234 34+2*$

【山东师范大学 1999 七 （10分）】

5. 假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。 （1）下面所示的序列中哪些是合法的？

A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO （2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。【武汉大学 2000 五、2】 6.设计一个算法，判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的单循环链表中，每个结点有两个域：ch和link，其中ch域为字符类型。【南京邮电大学 2000五】

7. 请利用两个栈S1和S2来模拟一个队列。已知栈的三个运算定义如下：PUSH(ST,x):元素x入ST栈；POP(ST,x)：ST栈顶元素出栈，赋给变量x；Sempty(ST)：判ST栈是否为空。那么如何利用栈的运算来实现该队列的三个运算：enqueue:插入一个元素入队列； dequeue:删除一个元素出队列；queue_empty：判队列为空。（请写明算法的思想及必要的注释） 【西安电子科技大学2001软件五(10分)】【上海交通大学1999 二(12分)【】河海大学1998 三(12分)】

类似本题的另外叙述有：

（1）有两个长度相同的栈S1,S2，已知以下入栈、出栈、判栈满和判栈空操作： PROCEDURE push(Stack:Stacktype;x:Datatype); FUNCTION Pop(Stack:Stacktype ):Datatype; FUNCTION Full (Stack:Stacktype):Boolean; FUNCTION Empty(Stack:Stacktype)Boolean;

现用此二栈构成一个队列，试写出下面入队列、出队列操作算法： PROCEDURE EnQueue(x:Datatype);

FUNCTION DeQueue: Datatype;【北京邮电大学 2000 六（10分）】 8. 设结点结构为(data,link)，试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleteq过程,要求它们的时间复杂性都是O(l)（不计new和dispose时

间）

【东南大学 1996 二 （10分）】

9. 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，如图所示（编者略），请写出相应的入队列和出队列算法。【西安电子科技大学 1999计应用 六 （10分）】

10. 如果允许在循环队列的两端都可以进行插入和删除操作。要求： （1）写出循环队列的类型定义；

（2）写出“从队尾删除”和“从队头插入”的算法。【北方交通大学 1994 三 （12分）】 11. 在一个循环链队中只有尾指针（记为rear，结点结构为数据域data，指针域next），请给出这种队列的入队和出队操作的实现过程。【山东科技大学 2002 一、2 （6分）】

12. 双端队列（duque）是一个可以在任一端进行插入和删除的线性表。现采用一个一维数组作为双端队列的数据存储结构，使用类PASCAL语言描述如下： CONST maxsize=32; {数组中可容纳的元素个数} TYPE duque=RECORD

elem: ARRAY[0..MAXSIZE-1] OF datatype; {环形队列的存放数组} end1,end2:0..MAXSIZE; {环形数组的两端} END;

试编写两个算法add(Qu:duque;x:datatype;tag:0..1)和delete（Qu:duque; var x:datatype; tag:0..1）用以在此双端队列的任一端进行插入和删除。当tag=0时在左端endl端操作，当tag=1时在右端end2端操作。【清华大学 1998 二（10分）】 13. 一个双端队列deque是限定在两端end1，end2都可进行插入和删除的线性表。队空条件是end1=end2。若用顺序方式来组织双端队列，试根据下列要求，定义双端队列的结构，并给出在指定端i（i=1，2）的插入enq和删除deq操作的实现。 （1） 当队满时，最多只能有一个元素空间可以是空的。 （2） 在做两端的插入和删除时，队列中其它元素一律不动。【清华大学 1999 六（12分）】 14. 已知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); 元素value进队 deQueue(q:queue):datatype; 出队列，返回队头值

isEmpty(q:queue):boolean; 判队列空否 【清华大学 2000 六（12分）】

15. 将n个队列顺序映射到数组v[l..m]中，每一队列在v中表示为一循环队列。试画出其示意图并写出对应这种表示的addq和deleteq过程。【东南大学 1993 二（20分）】 16. 设整数序列a1,a2,?,an，给出求解最大值的递归程序。【南京航空航天大学 2000 六】 17．线性表中元素存放在向量A（1,?,n）中，元素是整型数。试写出递归算法求出A中的最大和最小

元素。【北京邮电大学 1994 八 （10分）】

18. 已知求两个正整数m与n的最大公因子的过程用自然语言可以表述为反复执行如下动作：

第一步：若n等于零，则返回m；第二步：若m小于n，则m与n相互交换；否则，保存m，然后将n送m，将保存的m除以n的余数送n。

（1）将上述过程用递归函数表达出来（设求x除以y的余数可以用x MOD y 形式表示）。 （2）写出求解该递归函数的非递归算法。【北京航空航天大学 2001 五（15分）】 19. 写出和下列递归过程等价的非递归过程。 PROCEDURE test(VAR sum:integer); VAR a:integer, BEGIN read(a);

IF a=0 THEN sum:=1

ELSE BEGIN test(sum); sum:=sum*a；END; write(sum)；

END; 【清华大学 1996 二】

20. 试将下列递归过程改写为非递归过程。 void test(int &sum) { int x； scanf(x)；

if(x=0) sum=0 else {test(sum); sum+=x;} printf(sum)；

} 【北京轻工业学院 2000 三 （15分）】 21. 已知Ackermann函数定义如下:

（1） 写出Ack(2,1)的计算过程。

（2） 写出计算Ack(m,n)的非递归算法。 【北京航空航天大学 1999 六 （15分）】 22．设计算法以求解从集合{1..n}中选取k（k<=n）个元素的所有组合。例如，从集合{1..4}中选取2个元素的所有组合的输出结果为：1 2，1 3，1 4，2 3， 2 4，3 4。 【合肥工业大学 2000 五、5（8分）】

习题答案 一、选择题

1.B 2.1B 2.2A 2.3B 2.4D 2.5.C 3.B 4.D 5.D 6.C 7.D 8.B

9.D 10.D 11.D 12.C 13.B 14.C 15.B 16.D 17.B 18.B 19.B 20.D 21.D 22.D 23.D 24.C 25.A 26.A 27.D 28.B 29.BD 30.C 31.B 32.C

33.1B 33.2A 33.3C 33.4C 33.5F 34.C 35.C 36.A 37.AD

二、判断题

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库栈与队列习题与答案(3)在线全文阅读。