一、选择题
1．栈和队列都是( )。
A.顺序存储的线性结构 B.限制存取点的线性结构
C.链接存储的线性结构 D.限制存取点的非线性结构
2．一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是( )。
A. edcba B. decba C. dceab D. abcde
3．若已知一个栈的入栈序列是l，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则Pi为 ( )。
A.i B. n-i C. n-i+l D.不确定
4．循环队列SQ采用数组空间SQ.data[0，n-l]存放其元素值，已知其头尾指标分别是front和rear，则当前队列中的元素个数是( )。
A. (rear-front+n)%n B. rear-front+l
C. rear-front-l D. rear-front
5．中缀表达式A-(B+C/D)E的后缀形式是( )。
A. AB-C+D／E B. ABC+D／E*
C. ABCD／E*+- D. ABCD／+E*-
6．一个队列的入列序列是1，2，3，4，则队列的输出序列是( )。
A.4，3，2，1 B.1，2，3，4
C.1，4，3，2 D.3，2，4，1
7．若在一个大小为6的数组上实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为( )。
A.1和5 B.2和4 C.4和2 D.5和l
8．用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指标指向队尾结点，则在进行出队运算时( )。
A.仅修改队头指针 B.仅修改队尾指针
C.对头、队尾指针都要修改 D.对头、对尾指针都可能要修改
当队列中只有一个元素时，出队后需要清空对头和队尾指针。
9．若进栈序列为a，b，c，则通过入出栈运算可能得到的a，b，c的不同排列个数为( )。
A.4 B.5 C.6 D.7
10.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队运算后其头指针front值为( )。
A. front=front+l B. front=(front+l) %(m-l)
C.front=(front-1)%m D. front=(front+l)%m
11.在一个链队中，假定front和rear分别为队首指标和队尾指标，则删除一个结点的运算应执行( )。
A. front front->next; B.rear=rear->next;
C.rear=front->next; D. front=rear->next;
12.向一个栈顶指针为hs的链栈中插入结点*s时，应执行( )。
A.hs->next=s； B. s->next=hs; hs=s;
C.s->next=hs->next; hs->next=s; D. s->next=hs; hs=hs->next:
13.在具有n个单元的顺序循环队列中，假定front和rear分别为队首指针和队尾指针，顺序表的下标下界从0开始，则判断队满的条件是( )。
A.(l+rear)%n==front; B.(l+rear)% (n-l)==front;
C.l+rear%n==front; D.(l+front)%n==rear;
14.若已知一个栈的入栈序列是l，2，3，…，30，其输出序列是p1, p2，p3，…，pn，若p1=30，则p10为( )。
A. 11 B. 20 C. 30 D. 21
n-i+1
二、填空题
1．设长度为n的链队列用单循环链表表示，若只设头指针，则入队和出队运算的时间复杂度分别为____和____；若只设尾指针，则入队和出队运算的时间复杂度分别为____和____。
O(n)，O(1) O(1)，O(n)
2．基本线性表，栈和队列都是____ 结构。可以在基本线性表的____插入和删除元素；对于栈只能在____ 插入和删除元素；对于队列只能在____插入元素和删除元素。
线性 任何 栈顶 队尾, 队首
3．一个栈的输入序列是235614，则栈的输出序列54321是____。
不可能的
4．对于顺序循环队列Q[M]，下标从0到M-1，头尾指针分别为F和R表示，出队时，队首指针循环加l可表示F=____。
F=(1+F)%M
5．因为顺序栈的空间是有限的。因此，在进行插入运算时，可能会发生____。
上溢
6．假设以s和x分别表示进栈和退栈运算，则对输入序列a，b，c，d，e进行一系列栈运算ssxsxssxxx之后，得到的输出序列为____。
bceda
7．栈顶的位置是随着____ 运算而变化的。
进栈或出栈
8．有如下递归函数，执行语句printf(”%d\n'’，dunno(3))；的结果是_________。
int dunno (int m)
{
int value；
if(m == 0) value = 3;
else value = dunno (m - l) + 5;
return (value)；
}
18
9．设a是含有N个分量的整数数组，写出求n个整数之和的递归定义________，写出求n个整数之积的递归定义____。
10.设栈S和队列Q的初始状态为空，元素a，b，c，d，e，f依次通过栈S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序是b，d，c，f, e，a，则栈S的容量至少应该是________。
3
三、简答题
1．什么是队列的“假溢出”现象？一般有哪几种处理方法？
假设顺序队列的头指针为front，尾指针为rear，队列的容量为MaxSize，下标下界为0，则最后一个单元的下标为MaxSize-1。
(1)“假溢出”是指rear=MaxSize-l，而front≠0的现象。
(2)处理“假溢出”的方法通常有下列3种：
1)每当从队首删除一个元素时，将队列中剩余的全部元素均向队首方向移动一个位置。
2)当发生假溢出时，将队列中现有的全部元素均向低下标方向移动一个位置。
3)上述两种方法都要进行大量元素的移动，效率低。最巧妙的方法是采用循环队列方式。
循环队列是通过头、尾指针的循环来实现的。入队时，修改尾指针：rear=(l+rear)%MaxSize;出队时，修改队首指针：front=(l+front)%MaxSize。
2．试证明：若借助栈由输入序列1，2，3，…，n，得到输出序列P1，P2，P3，…，Pn（它是输入序列 的一个排列），则输出序列中不可能出现这样的情况：若i<j<k，存在输出序列Pk Pi Pj。
要想得到PkPiPj，则必须先按i，j．k顺序全部进栈以后，再进行出栈操作。
显然，第1个出栈的是最后进栈的Pk，而Pk出栈之后，栈顶元素是Pj，因此第2个出栈的应该是Pj。
最后出栈的才是Pi，即出栈序列应该为PkPjPi，而不是PkPiPj。
3．顺序队列一般应该组织成为环状队列的形式，而且一般队列头或尾其中之一应该特殊处理。例如，队列为listarray[O...n-l]，队列头指针为front，队列尾指针为rear，则listarray[rear]表示下一个可以插入队列的位置。请解释其原因。
一般环状队列头或尾其中之一要进行特殊处理，否则，当队列“空”或“满”时，只凭q.rear= =q.front无法判断。
一般的处理方法是将q.rear指向下一个要插入的位置。
这样，虽牺牲了一个单元的存储空间，但可以很容易地区分队列“空”或“满”。
当q.rear==q.front时，表示队列“满”，当q.rear==(q.front+l)%n时，表示队列“空”。
4．试推导求解n阶Hanoi塔问题至少需执行的move运算的次数。
求解此方程，得M(n)=2n一l。也可以递推得到，并由“数学归纳法”证明。
四、算法设计题
1．利用两个栈S1和S2模拟一个队列时，要求实现该队列的进队、出队、判队空3种运算。
/*
* 用一个栈S1作为输入栈，另一个栈S2作为输出栈。
* 进行入队操作时，总是将数据加入到S1中;进行出队操作时，如果S2不空，则输出S2的元素;
* 如果S2为空，则读取S1的全部元素加入到S2中，然后由S2输出。
* 当S1和S2均为空时，表示队列为空。
* 假设栈的类型为STACK
*/
//(1)进队
void EnQueue(STACK *S, ElemType x)
{
if (SI->top == MaxSize - l)
printf(¨overflow”);
else
Push(Sl，x); //以进栈代替进队
}
//(2)出队
ElemType DeIQueue(STACK *SI, STACK kS2)
{
ElemType x;
if (S2->top ! = -1)
Pop(S2, &x);
else
{
while (1Empty(S1))
{
Pop(S1, &x);
Push(S2, x);
}
Pop(S2, &x);
}
return X;
}
//(3)判断队空
int EmptyQueue(STACK *S1, STACK *S2)
{
if (S1->top == -1 ＆＆S2->top == -l)
return 1; //两个栈同时为空，则表示队空
return O; //队不空，返回O
}
2．假设如题图3-1所示，火车调度站的入口处有n节硬席或软席车厢（分别以H和S表示）等待调度。试编写算法，输出对这n节车厢进行调度的运算（入栈或出栈运算）序列，以使所有的软席车厢都被调整到硬席车厢之前。
//注意两侧的铁道均为单向行驶道，且两侧不相通。故车辆都必须通过“栈道”进行调度。
typedef char ElemType;
int attemper(STACK *p, STACK *q)
{ //将p栈道的车厢，经调度之后入q栈道，使软席车厢调整到硬席车厢之前
STACK *temp;
ElemType e;
InitStack(temp);
while (!Empty(p))
{
P0p(p，＆e);
if (e == 'S')
Push(q，e);
else
Push(temp, e);
}
while (!Empty(temp))
{
Pop(temp; &e);
Push(q, e);
}
}
3．求两个正整数m和n的最大公约数可以用如下gcd (m，n)公式表示：
(1)编写一个计算gcd(m，n)的递归过程。
int gcd（int m，int n）
{
int k;
if (n == O)
return (m);
else
return (gcd(n, m % n));
}
(2)将上述过程转化成非递归过程。
int gcd2(int m，int n)
{
int r;
do
{
r = m % n.m = n;
n = r;
} while (r);
return m;
}
(3)画出计算gcd (20，6)的过程及栈的状态变化，给出计算结果。
在top=3时，n的值为0，退栈，并返回2作为最后结果。
4．如果希望循环队列中的元素都能得到利用，则需设置一个标志域tag，并以tag的值为0或l来区分尾指针和头指针值相同时的队列状态是“空”还是“满”。试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度讨论设标志和不设标志这两种方法的使用范围（如当循环队列容量较小而队列中每个元素占的空间较多时，哪一种方法较好）。
//标志位tag的初值置为“0”。一旦元素入队，使rear==front时，需置tag为“1”;
//反之，一旦元素出队列使front=rear时，需置tag为“0”，以便使下一次进行入队列或出队列操作时(此时front= =rear)
//可由标志位tag的值来区别队列当时的状态是“满”，还是“空”。
#define MaxSize 100
typedef struct
{
ElemType data[MaxSize];
int front，rear;
int tag;
} SqQueue;
int EnQueue(SqQueue *q, ElemType e)
{
// 插入元素e为q的新队尾元素，如队列满，则置tag = l
if (q->rear == q->front && tag == l)
return 0;
q->data[q->rear] = e;
q->rear=(q->rear+l))%MaxSize;
if (q->rear == q->front)
tag = l;
return 1;
}
int DeQueue(SqQueue *q, ElemType *e)
{ //若队列不空，则删除q的队头元素，用e返回;如队列空，则置tag=0
if (q->rear == q->front＆＆tag == 0)
return O;
*e = q->data[q->front];
q->front = (q->front + l) % MaxSize;
if (q->rear == q->front)
tag = 0;
return 1;
}
5．用单链表实现队列，如题图3-2所示，并令front rear FNULL表示队列为空，编写实现队列的如下5种运算的函数：
SetNull:将队列置成空队列。
GetFirst:返回队列的第一个元素。
EnQueue：把元素插入队列的后端。
DeQueue：删除队列的第一个元素。
Empty：判定队列是否为空。
typedef struct Lnode(
ElemType data;
struct Lnode *next;
}
LinkNode;
//根据单链表的特点，实现队列的5种运算的函数如下：
void SetNull(LinkNode **front, LinkNode **rear)
{
*f ront = NULL;
*rear = NULL;
}
int GetFirst(LinkNode *front, ElemType *x)
{
if (front == NULL)
return O;
else
{
x = front->data;
return 1;
}
}
int EnQueue(LinkNode **front, LinkNode **rear, ElemType x)
{
LinkNode *p;
if (*rear == NULL)
{ //若队列为空，则直接建立一个链表
*rear = (LinkNode *)malloc(sizeof(LinkNode));
(*rear)->d.ata = x;
*front = *rear;
}
else
{ //若不为空，则建立一个结点将其链表链接到末尾
p = (LinkNode *)malloc(sizeof(LinkNode));
p->data = x;
p->next = NULL;
(*rear)->next = p;
*rear = p;
}
return 1;
}
int DeQueue(LinkNode **front, LinkNode **rear, ElemType *x)
{
LinkNode *p;
if (*front == NULL)
return O;
else
{
p = *front;
x = p->data;
*front = (*front)->next;
free(p);
if (*front == NULL)
*rear = NULL;
return l;
}
}
int QueueEmpty(LinkNode **front)
{
if (*front == NULL)
return l;
else
return O;
}
6．若使用循环链表来表示队列，p是链表中的一个指针。试基于此结构给出队列的插入( EnQueue)和删除(DeQueue)算法，并给出p为何值时队列空。
//这里使用的循环链表不带头结点，规定p始终指向队尾结点，p->next即为队头结点。
//当p= =NULL时队列为空。队列插入和删除算法如下：
typedef struct node(
ElemType data;
struct node *next;
}
QNode;
void EnQueue(QNode **p, ElemType x) //队列插入
{
QNode *s;
s = (QNode *)malloc(sizeof(QNode));
s->data = x;
if (*p == NULL)
{
*p = s;
(*p) 一 > next = *p;
}
else
{
s->next = (*p)->next; //将s作为*p之后的结点
(*p)->next = s;
*p = s; //*p指向*s
}
}
int DeQueue(QNode **p, ElemType *x) //队列删除
{
QNode *s;
if (*p == NULL)
return 0;
if ((*p)->next == NULL)
{ //只有一个结点的情况
x = (*p)->data;
free(*p);
*p = NUIL;
}
else
{ //将*p之后结点的data域值赋给x，然后删除之
s = (*p)->next;
*x = s->data;
(*p)->next = s->next;
free(s);
}
return 1;
}
7．编写程序将一个循环队列的内容倒置，该循环队列存储在一个数组A[1...N-1]中，例如，题图3-3 (a)中为倒置前的队列，题图3-3 (b)中为倒置后的队列。
//使用一个栈起到过渡的作用。先将sq队列中元素出队并将其入栈ss，直到队列空为止;然后初始化队列
//即sq->front=sq->rear=n;再出栈并将其入队列，直到栈空为止。对应的算法如下：
#define n 100
void reverse(squeue *sq)
{
ElemType x;
STACK *ss;
ss - (STACK *)malloc(sizeof(STACK)); //栈初始化
ss->top = -l;
while (sq->front ! = sq->rear)
{ //队不空时，出队并入栈
sq->front = (sq->front + l) % n;
if (sq->front == 0)
sq->front = n; //队列元素下标从1到n
x = sq->data[sq->front];
ss->top++;
ss->data[ss->top] = x; //将x入栈
}
sq->front = sq->rear = n;
while (ss->top >= 0)
{
x = ss->data[ss->top];
ss->top--;
sq->rear = (sq->rear + l) % n;
sq->data[sq->rear] = x;
}
}
8．已知Ackermann函数的定义如下：写出计算Ack(m, n)的非递归算法
/*
** 计算Ack(m,n)的非递归算法为fun函数。在fun中采用一个二维数组作为栈，其内容如下：
** st (top, O)存储标记，该标记为l(m = 0)、2(m≠O，n = 0)或3 (m + 0, n + 0)。
** st (top, 1)存储Ack (m, n)之值，初值为0。
** st (top, 2)存储m。
** st (top, 3)存储n。
*/
#define MaxSize 5000
int no(int m，int n) //根据m，n之值返回相应的标志
{
if (m == 0)
return 1;
else if (n == O)
return 2;
else
return 3：
}
int fun(int m，int n)
{
int st[MaxSize][4], top = 0, ml, nl; //top初值为O
st[top][0] = no(m, n);
top++; //先移动栈指针
st[top][1] = 0; //初值O入栈
st[top][2] = m; //初值m入栈
st[top][3] = n; //初值n入栈
do
{
if (st[top][1] == O)
f if (st[top][O] == 3)
{
top++; //入栈
st[top][1] = 0;
st[top][2] = st[top - l][2];
st[top][3] = st[top - l][3] - 1;
st[top][0] = no(st[top][2], st[top][3]);
}
else if (st[top][0] == 2)
{
top++; //入栈
st[top][1] = 0;
st[top][2] = st[top - l][2] - 1;
st[top][3] = 1;
st[top][0] = no(st[top][2], st[top][3]);
}
if (st[top][0] == 1)
st[top][1] = st[top][3] + 1; //求值
}
if (top >= l & ＆st[top][1] != 0＆＆st [top - l][0] == 2)
{
st[top - l][1] = st[top][1];
top--; //出栈
}
else if (top >= l＆＆st[top][1] 1 = 0＆ & st[top一1][O] == 3)
{
nl = st[top][1];
ml = st[top - l][2] - 1;
top--; //出栈
st[top][1] = 0;
st[top][2] = ml;
st[top][3] = nl;
st[top][0] = no(st[top][2], st[top][3]);
}
if (top == l＆ & st[top][1] != 0)
break; //栈中只有1个元素，且已计算出值，则退出循环
while (top >= l)
;
return (st[1][1]); //st [1][1]就是所求的函数值
}
网友评论