全国自考数据结构导论（栈和队列）模拟试卷1

35． 如果希望循环队列中的元素都能得到利用，则需要设置一个标志域tag，并以tag的值为0或1来区分尾指针和头指针值相同时的队列状态是“空”还是“满”。试编写与此结构相应的入队列和出队列的算法。

33． 在栈顶指针为HS的链栈中，写出计算该链栈中结点个数的函数。

34． 设从键盘输入一整数的序列：a₁，a₂，a₃，…a_n，试编写算法实现：用栈结构存储输入的整数，当a_i≠一1时，将a_i进栈；当a_i=一1时，输入栈顶整数并出栈。算法应对异常情况(如栈满等)给出相应的信息。

32． 试写出一个判别表达式中开、闭括号是否配对出现的算法。

31． 用一个循环单链表表示队列，该队列只设一个队尾指针rear,不设队首指针。试编写算法，完成入队、出队操作。

30． 借助栈(可用栈的基本运算)来实现单链表上的逆置运算。

26． 从现实生活中举例说明栈和队列的特征。

28． 设有编号为A，B，C，D的四辆列车，顺序进入一个栈式结构的站台，试写出这四辆列车开出车站的所有可能的顺序。

25． 表达式d／(b—c)+a的后缀表达式是_______。

24． 对于栈和队列，无论它们采用顺序存储结构还是链式存储结构，进行插入和删除操作的时间复杂度都是____。

22． 已知链队列Q的头、尾指针分别是front和rear，则出队操作是：p=Q一>front；_______；free(p)。

23． 一般情况下，将递归算法转化成等价的非递归算法应该设置_______。

21． 对带有头结点的链队列lq，判定队列中只有一个数据元素的条件是_______。

20． 已知用数组sq[50]存放循环队列的元素，且头指针和尾指针分别为19和2，则该队列的当前长度为_______。

19． 判别循环队列空和满的方法有_______、_______和_______。

18． 在一个循环队列Q中，判断队空的条件为_______，判断队满的条件为______。

16． 栈的逻辑特点是_____，队列的逻辑特点是______；二者的共同点是只允许在它们的______处插入和删除数据元素；其中_________可以作为实现递归函数调用的一种数据结构。

17． 允许在一端插入，在另一端删除的线性表称为_________。插入的一端为________，删除的一端为_______。

14． 如果以链表作为栈的存储结构，则退栈操作时________。

15． 前缀表达式“一2+8／6 3”的运算结果是_________。

11． 若链队列的队头指针和队尾指针分别为front和rear，则从队列中删除一个结点的操作是_______。

12． 输入序列为ABC，要变为CBA，经过的栈操作为_______。

13． 设有一顺序栈S，元素S1，S2，S3，S4，s5，S6依次进栈，如果6个元素出栈的顺序是s2，s3，S4，S6，s5，s1，则栈的容量至少应该是_________。

10． 设数组A[0，m]作为循环队列sq的存储空间，front为队头指针，rear为队尾指针，则执行入队操作的语句是_____。

9． 若以数组a[k]存放循环队列的元素，则当循环队列满时，队列中有______个元素。

7． 假定一个循环队列的队头和队尾指针分别为P和q，则判断队空的条件为_________。

8． 若以数组a[8]存放循环队列的元素，且当前队尾指针rear的值为0，队头指针front的值为3。当从队列中出队两个元素，再人队一个元素后，rear和front的值分别为_______-。

5． 设有一顺序栈已含3个元素，如下图所示，元素a4正等待进栈。那么下列4个序列中不可能出现的出栈序列是_______。

6． 一个队列的入队序列是“d1，d2，d3，d4，”则队列的出队顺序是_______

4． 从栈顶指针为top的链栈中删除一个结点，并将被删结点的值保存到m中，其操作步骤为______。

3． 链栈与顺序栈相比，有一个较明显的优点是( )。

2． 一个栈的人栈序列为“abcde”，则以下不可能的出栈序列是______。

1． 栈的顺序表示中，用top表示栈顶指针，那么栈空的条件是______。