计算机专业基础综合数据结构(栈和队列)历年真题试卷汇编3.pdfVIP

计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编3

(总分：48.00，做题时间：90分钟)

一、综合题(总题数：3，分数：6.00)

1.给出循环队列中元素个数的计算式(设队最大长度为N，队首指针FRONT，队尾指针REAR)【西北大学2000

二、7(5分)】

__________________________________________________________________________________________

正确答案：(正确答案：循环队列中元素个数为(REAR—FRONT+N)％N。其中FRONT是队首指针，指向队首元

素的前一位置；REAR是队尾指针，指向队尾元素；N是队列最大长度。)

2.顺序队列一般应该组织成为环状队列的形式，而且一般队列头或尾其中之一应该特殊处理。例如，队列

为listarray[0,n一1】，队列头指针为front，队列尾指针为rear，则listarray[rear]表示下一个可以

插入队列的位置。请解释其原因。【北京大学1999一、3(20／3分)】

__________________________________________________________________________________________

正确答案：(正确答案：循环队列解决了用向量表示队列所出现的“假溢出”问题，但同时又出现了如何判

断队列的满与空问题。例如：在队列长10的循环队列中，若假定队头指针front指向队头元素的前一位置，

而队尾指针指向队尾元素，则ffon=3，rear=7的情况下，连续出队4个元素，则front==rear为队空；如

果连续入队6个元素，则front==rear为队满。如何判断这种情况下的队满与队空，一般采取牺牲一个单

元的做法或设标记法。即假设front==rear为队空，而(rear+1)％表长==front为队满，或通过设标记tag。

若tag=0，front=rear则为队空；若tag=1，因入队而使得fron==rear，则为队满。本题中队列尾指针rear，

指向队尾元素的下一位置，listarray[rear]表示下一个入队的元素。在这种情况下，我们可规定，队头指

针front指向队首元素。当front==rear时为队空，当(rear+1)％n==front时为队满。出队操作(在队列

不空情况下)队头指针是front==(front+1)％n。)

3.设一个双端队列，元素进入该队列的次序为a，b，c，d。求既不能由输入受限的双端队列得到，又不能

由输出受限的双端队列得到的输出序列。【中山大学1999一、4(3分)】

__________________________________________________________________________________________

正确答案：(正确答案：对于输入序列a,b，c，d，无论是输入受限的双端队列，还是输出受限的双端队列，

其输出序列中，以a,b，c开头的序列都有6个，如以a开头的有：abcd,abdc，acbd,acdb，adbc，adcb。

但以元素d开头的只能得到4种序列。输入受限的双端队列不能得到dbac和dbca，输出受限的双端队列

不能得到dbca和dacb。故两种受限的双端队列均不能得到dbca输出序列。)

二、设计题(总题数：20，分数：42.00)

4.设有两个栈S1、S2都采用顺序栈方式，并且共享一个存储区[0．．maxsize一1]，为了尽量利用空间，

减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S1、S2有关入栈和出栈的操作算法。【哈

尔滨工业大学2001七(12分)】

__________________________________________________________________________________________

正确答案：(正确答案：两栈共享向量空间，将两栈栈底设在向量两端，初始