书面作业： 第三章 栈与队列_queue 所指队列的长度是

## 判断
1

1-2
所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。 F

1-8
队列和栈都是运算受限的线性表，只允许在表的两端进行运算。 F

1-13
An algorithm to check for balancing symbols in an expression uses a stack to store the symbols. T

1-18
在n个元素连续进栈以后，它们的出栈顺序和进栈顺序一定正好相反。 T

1-20
n个元素通过一个栈产生n个元素的出栈序列，其中进栈和出栈操作的次数总是相等的。 T

1-1
通过对堆栈S操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为：123。 F

1-3
在用数组表示的循环队列中，front值一定小于等于rear值。F

1-4
不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑"溢出"情况。 T

1-7
队列是一种插入和删除操作分别在表的两端进行的线性表，是一种先进后出的结构。 F

1-11
“Circular Queue” is defined to be a queue implemented by a circularly linked list or a circular array. F

1-15
栈是插入和删除只能在一端进行的线性表；队列是插入在一端进行，删除在另一端进行的线性表。 T

1-17
n个元素进队的顺序和出队的顺序总是一致的。 T

1-19
栈底元素是不能删除的元素。 F

1-21
顺序栈中元素值的大小是有序的。 F

1-22
栈顶元素和栈底元素有可能是冋一个元素。 T

1-23
栈是一种对进栈、出栈操作总次数做了限制的线性表。 F

1-24
对顺序栈进行进栈、出栈操作不涉及元素的前、后移动问题。 T

1-25
环形队列中有多少个元素可以根据队首指针和队尾指针的值来计算。 T

1-26
若采用“队首指针和队尾指针的值相等”作为环形队列为空的标志，则在设置一个空队时只需将队首指针和队尾指针赋同一个值，不管什么值都可以。 T

1-27
栈和队列的插入和删除操作特殊，所以，栈和队列是非线性结构。F

1-28
两个栈共享一片连续空间，可以将两个栈的栈底分别设在这片空间的两端。 T

1-29
不论是入队还是入栈操作，在顺序存储结构下都应考虑溢出现象。T

1-30
可以通过少用一个存储空间的方法解决循环队列假溢出现象。 F

选择

2-12
设一个栈的输入序列是1、2、3、4、5，则下列序列中，是栈的合法输出序列的是？ ( A )

A.3 2 1 5 4
B.5 1 2 3 4
C.4 5 1 3 2
D.4 3 1 2 5

2-19
下列关于栈的叙述中，错误的是：( C )

1.采用非递归方式重写递归程序时必须使用栈
2.函数调用时，系统要用栈保存必要的信息
3.只要确定了入栈次序，即可确定出栈次序
4.栈是一种受限的线性表，允许在其两端进行操作
A.仅 1
B.仅 1、2、3
C.仅 1、3、4
D.仅 2、3、4

2-21
循环顺序队列中是否可以插入下一个元素（ A ）。

A.与队头指针和队尾指针的值有关
B.只与队尾指针的值有关，与队头指针的值无关
C.只与数组大小有关，与队首指针和队尾指针的值无关
D.与曾经进行过多少次插入操作有关

2-11
设一个堆栈的入栈顺序是1、2、3、4、5。若第一个出栈的元素是4，则最后一个出栈的元素必定是：( D )

A.1
B.3
C.5
D.1或者5

2-13
设栈S和队列Q的初始状态均为空，元素{1, 2, 3, 4, 5, 6, 7}依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是{2, 5, 6, 4, 7, 3, 1}，则栈S的容量至少是： ( D )

A.1
B.2
C.3
D.4

2-1
若借助堆栈将中缀表达式a+bc+(de+f)*g转换为后缀表达式，当读入f时，堆栈里的内容是什么（按堆栈自底向上顺序）？ ( B )

A.+( * +
B.+(+
C.++(+
D.abcde

2-2
表达式a*(b+c)-d的后缀表达式是： ( A )

A.a b c + * d -
B.a b c d * + -
C.a b c * + d -
D.- + * a b c d

2-3
若采用带头、尾指针的单向链表表示一个堆栈，那么该堆栈的栈顶指针top应该如何设置？ ( A )

A.将链表头设为top
B.将链表尾设为top
C.随便哪端作为top都可以
D.链表头、尾都不适合作为top

2-4
利用大小为n的数组（下标从0到n-1）存储一个栈时，假定栈从数组另一头开始且top==n表示栈空，则向这个栈插入一个元素时，修改top指针应当执行： ( C )

A.top=0
B.top++
C.top–
D.top不变

2-6
若已知一队列用单向链表表示，该单向链表的当前状态（含3个对象）是：1->2->3，其中x->y表示x的下一节点是y。此时，如果将对象4入队，然后队列头的对象出队，则单向链表的状态是： ( B )

A.1->2->3
B.2->3->4
C.4->1->2
D.答案不唯一

2-8
若用一个大小为6的数组来实现循环队列，且当前rear和fornt的值分别为0和3。从当前队列中删除一个元素，再加入两个元素后，rear和front的值分别为（ B ）。

A.1和5
B.2和4
C.4和2
D.5和1

2-9
判断一个循环队列QU（最多元素为MaxSize）为空的条件是（ A ）。

A.QU.front == QU.rear
B.QU.front != QU.rear
C.QU.front == (QU.rear + 1) % MaxSize
D.QU.front != (QU.rear + 1) % MaxSize

2-10
用单链表表示的链队的队头在链表的（ A ）位置。

A.链头
B.链尾
C.链中
D.均可以

2-22
Suppose that all the integer operands are stored in the stack S_​1, and all the operators in the other stack S_​2. The function F() does the following operations sequentially:
(1) Pop two operands a and b from S_​1;
(2) Pop one operator op from S_​2;
(3) Calculate b op a; and
(4) Push the result back to S_​1.
Now given { 5, 8, 3, 2 } in S_​1 (where 2 is at the top), and { *, -, + } in S₂ (where + is at the top). What is remained at the top of S_​1 after F() is executed 3 times? ( B )

A.-15
B.15
C.-20
D.20

2-24
假定利用数组a[n]顺序存储一个栈，用top表示栈顶指针，用top==-1表示栈空，并已知栈未满，当元素x进栈时所执行的操作为（ C ）。

A.a[- -top]=x
B.a[top- -]=x
C.a[++top]=x
D.a[top++]=x

2-25
经过以下栈的操作后，变量x的值为（ A ）。
InitStack(st);Push(st,a);Push(st,b);Pop(st,x);Top(st,x);

A.a
B.b
C.NULL
D.FALSE

2-26
若已知一个栈的入栈序列是1，2，3，4，其出栈序列为P_​1，P₂，P₃，P_​4，则P_​2，P₄不可能是（ C ）。

A.2,4
B.2,1
C.4,3
D.3,4

2-27
设有一个顺序共享栈Share[0:n-1]，其中第一个栈顶指针top1的初值为－1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是（ A ）。

A.top2-top1 = =1
B.top1-top2 = =1
C.top1= =top2
D.以上都不对

2-28
循环队列放在一维数组A[0…M-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。初始时为空。下列判断队空和队满的条件中，正确的是（ A ）。

A.队空：end1= =end2;队满：end1==(end2+1)mod M
B.队空：end1= =end2;队满：end2==(end1+1)mod (M-1)
C.队空：end2==(end1+1) mod M;队满：end1==(end2+1) mod M
D.队空：end1==(end2+1) mod M;队满：end2==(end1+1)mod (M-1)

2-29
下列说法中，正确的是（ A ）。

A.消除递归不一定需要使用栈
B.对同一输入序列进行两组不同的合法入栈和出栈组合操作，所得的输出序列也一定相同
C.通常使用队列来处理函数或过程调用
D.队列和栈都是运算受限的线性表，只允许在表的两端进行运算

2-30
数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（ D ）。

A.r-f
B.(n+f-r)%n
C.n+r-f
D.(n+r-f)%n

2-31
设有一个递归算法如下

int fact(int n) { //n大于等于0 
	if(n<=0) 
		return 1; 
	else 
		return n * fact(n-1);
}
1
2
3
4
5
6

则计算fact(n)需要调用该函数的次数为（ A ）。

A.n+1
B.n-1
C.n
D.n+2

2-32
若一个栈以向量V[1…n]存储，初始栈顶指针top设为n+1，则元素x进栈的正确操作是( C )。

A.top++; V[top]=x;
B.V[top]=x; top++;
C.top- -; V[top]=x;
D.V[top]=x; top- -;

2-33
下列与队列结构有关联的是( D )

A.函数的递归调用
B.数组元素的引用
C.多重循环的执行
D.先到先服务的作业调度

程序填空题

5-1
本题要求求出不带头结点的单链表中的最大值并返回。

/* 求单链表值最大的结点 */
int getMaxNode(LinkNode* head)
{
	if (head == NULL)
		return INT_MIN;
	int first = head->data;
	int m = getMaxNode(head->next);
	if (m > first)return m;
	else return first;
}
1
2
3
4
5
6
7
8
9
10

5-2
本题要求采用递归方式求不带头结点的单链表的长度。

其中, 单链表结点类型定义如下:

typedef struct LNode {
	int data;
	struct LNode* next;
} LinkNode;
///求单链表长度
int getLength(LinkNode* L) {
	if (L == NULL)
		return 0;
	return 1 + getLength(L->next);
}
1
2
3
4
5
6
7
8
9
10

5-3
已知循环队列的结构定义如下：

typedef struct
{
    int size, front, rear;
    int *element;
} AQUEUE;
1
2
3
4
5

说明：element 为存储队列数据元素的动态数组，size 为动态数组的尺寸，front 为队首元素的下标，rear 为队尾元素下一位置的下标。

假设有以下定义：

AQUEUE *queue;
1

判断 queue 所指队列为空的条件是：queue->front == queue->rear;

判断 queue 所指队列为满的条件是：(queue->rear + 1) % queue->size == queue->front;

queue 所指队列的长度是：(queue->rear - queue->front + queue->size) % queue->size

注：请填写正确的C表达式，以便于检查答案是否正确。