$[3 填空 1]
$题目
向栈中压入元素的操作是______;
$答案
先移动栈顶指针,后存入元素

$[3 填空 2]
$题目
对栈进行退栈时的操作是______;
$答案
先取出元素,后移动栈顶指针

$[3 填空 3]
$题目
一个栈的输入序列是12345,则栈的输出序列43512是_______;
$答案
不可能的

$[3 填空 4]
$题目
在一个循环队列中,队首指针指向队首元素的_______;
$答案
前一个位置

$[3 填空 5]
$题目
从循环队列中删除一个元素的操作是______;
$答案
先移动队首元素,后取出元素

$[3 填空 6]
$题目
在具有n个单元的循环队列中,队满时共有_____个元素;
$答案
n-1

$[3 填空 7]
$题目
在栈顶指针为HS的链栈中,判定栈空的条件是________;
$答案
HS==NULL

$[3 填空 8]
$题目
在栈顶指针为HS的链栈中,计算该栈中结点个数的函数是______;
$答案
int count(node *HS){
   node *p;
   int n=0;
   p=HS;
   while(p!=NULL){
      n++;
      p=p->next;
   }
   return n;
}

$[3 填空 9]
$题目
在HQ链队中,判断只有一个结点的条件是______;
$答案
HQ->front==HQ->rear

[3 填空 10]
$题目
在HQ链队中,计算该链队中结点个数的函数是_______;
$答案
int count(struct linkqueue *HQ){
   struct linkqueue *p;
   int n;
   p=HQ->first;
   if(p==NULL) return(0);
   n=1;
   while(p!=HQ->rear){
      n++;
      p=p>next;
   }
   return n;
}

$[3 选择 1]
$题目
一个栈的入栈序列是a,b,c,d,e,则栈的不可能输出序列是________;
A. edcba           B. decba          C.dceab             D.abcde
$答案
C
$[3 选择 2]
$题目
若一直一个栈的入栈序列是1,2,3, ... ,n,其输出序列为p1,p2,p3, ... ,pn,若p1=n,则pi为_____;
A.i                B.n-i             C.n-i+1             D.不确定
$答案
C

$[3 选择 3]
$题目
判定一个栈ST(最多元素为m0)为空的条件是______;
A.ST->top!=0       B.ST->top==0      C.ST->top!=m0      D.ST->top==m0
$答案
B
$[3 选择 4]
$题目
判定一个栈ST(最多元素为m0)为满的条件是______;
A.ST->top!=0       B.ST->top==0      C.ST->top!=m0-1    D.ST->top==m0-1
$答案
D
$[3 选择 5]
$题目
判断一个队列QU(最多元素为m0)为空的条件是______;

A.QU->rear-QU->font==m0                 B.QU->rear-QU->font-1==m0  
C.QU->font==QU->rear                    D.QU->font=QU->rear+1 

$答案

C

$[3 选择 6]

$题目

判断一个队列QU(最多元素为m0)为满队列的条件是_____;

A.QU->rear-QU->font==m0                 B.QU->rear-QU->font-1==m0  
C.QU->font==QU->rear                    D.QU->font=QU->rear+1 

$答案

A

$[3 选择 7]

$题目

判断一个循环队列QU(最多元素为m0)为空的条件是_______;

A.QU->font==QU->rear                    B.QU->font!=QU->rear
C.QU->font=(QU->rear+1)%m0              D.QU->font!=(QU->rear+1)%m0  

$答案

A

$[3 选择 8]

$题目

判断一个循环队列QU(最多元素为m0)为满队列的条件是_______;

A.QU->font==QU->rear                    B.QU->font!=QU->rear
C.QU->font=(QU->rear+1)%m0              D.QU->font!=(QU->rear+1)%m0  

$答案

C

$[3 选择 9]

$题目

循环队列用数组A[0,m-1]存放其元素值,已知其头尾指针分别是front和rear,则当前队列中元素个数是_____;

A.(rear-front+m)%m         B.rear-front+1            C.rear-front-1          D.rear-front

$答案

A

$[3 选择 10]

$题目

表达式a*(b+c)-d的中缀表达式是____;

A.abcdd+-                  B.abc+*d-                 C.abc*+d-               D.-+*abcd

$答案

B

$[3 选择 11]

$题目

向一个栈顶指针为HS的链栈中插入一个s所指结点时,则执行____;

A. HS->next=s;                          B. s->next=HS->next;  HS->next=s;
C. s->next=HS; HS=s;                    D. x=HS->data;   HS=HS->next;

$答案

C

$[3 选择 12]

$题目

从一个栈顶指针为HS的链栈中删除一个结点时,用x保存被删结点的值,则执行_______;

A. x=HS; HS=HS->next;                   B.x=HS->data;
C. HS=HS->next; x=HS->data;             D.x=HS->data; HS=HS->next;   

$答案

D

$[3 选择 13]

$题目

在一个链队中,假设f和r分别为队首和队尾指针,则插入s所指结点的运算时_____;

A. f->next=s; f=s;       B.r->next=s; r=s;      C.s->next=r; r=s;      D.s->next=f; f=s;

$答案

B

$[3 选择 14]

$题目

在一个链队中,假设f和r分别为队首和队尾指针,则删除一个结点的运算时_____;
              
A.r=f->next;             B.r=r->next;           C.f=f->next;           D.f=r->next;

$答案

C




















$[3 应用 1]
$题目
	已知一个向量中的元素
按元素值非递减有序排列,
编写一个函数删除向量中多
余的值相同的元素.
$解释
	本题的算法思想是: 由于向量中的元素按元素值非
递减有序排列,值相同的元素必为相邻元素,因此依次比较
两个相邻的元素,若值相等,则删除其中一个,否则继续向后
查找,最后返回向量新长度.
$答案
	实现本题功能的函数如下:
int del(vector A,int n){
   int i=0,j;
   while(i<=n-1)
      if(A[i]!=A[i+1]) i++;
      else{
         for(j=i;j<n;j++) A[j]=A[j+1];
         n--;
      }
   return n;
}


$[3 应用 2]
$题目
	有两个栈s1和s2共享存
储空间c(1,m0),其中一个栈
底设在c[1]处,另一个栈底设
在c[m0]处,分别编写s1和s2
进栈push(i,x),退栈pop(i)
和设置栈空setnull(i)的函
数,其中i=1,2.注意:仅当整
个空间c[1,m0]栈满时才产
生上溢.
$答案
	该共享栈的结构如图所示,两栈的最多元素
个数为m0,top1是栈1的栈指针,top2是栈2的栈
指针,当top2=top1+1时出现上溢出,当top1=0时
栈1出现下溢出,当top2=m0+1时栈2出现下溢出.
	根据上述原理得到如下函数:

//top1,top2和m0均为已赋值的int型全局变量
void push(Elemtype x,int i){
   if(top1==top2-1) printf("上溢出!\n");
   else if(i==1){ //对第一个栈进行入栈操作
      top1++;
      c[top1]=x;
   }      
   else{ //对第二个站进行入栈操作
      top2--;
      c[top2]=x;
   }
}

//函数pop
void pop(int i){
   if(i==1){ //对第一个栈进行出栈操作
      if(top1==0)      printf("栈1下溢出!\n");   
      else{
         pop=c[top1];
         top1--;
      }
   else{ //对第二个栈进行出栈操作
      if(top2==m0+1)    printf("栈2下溢出!\n"); 
      else{
         pop=c[top2];
         top2++;
      }
}

//函数setnull
setnull(int i){
   if(i==1) top1=0;
   else top2=m0+1;
}


$[3 应用 3]
$题目
	假定有n个"栈"的铁路专
轨网络,如图2.4所示n=4时的
情况.初始时有2^n列列车位于
网络右边.试证明:通过实施一
系列适当的操作(要求操作的
方向与图中箭头方向一致),
最终在左边可形成2^(n+1)!种
不同的列车排列线性.
$答案
证明:本题如能证明在上述条件下,对于输入序列:
        a1,a2,......,am  (a表示一列列车,m=2^n)
     产生的输出序列可以是任意的a1,a2,......,am的排列组合,那么根据排列组合原理,输出的
排列线性是2^!种.
     当n=1时,输入序列为a1,a2,显然通过一个栈后的输出序列可以为a1,a2和a2,a1,即输出序列有
2^1!=2种.
     假设当m=n时成立,即2^(n-1)列列车通过n个"栈"后的可以产生这2^n列列车的任意排列序列.
     当m=n+1时,对于要求产生的任意输出序列:
         a11,a12,......,aik,aj1,aj2,......,ajk(k=2^n,共有k+k=2k=2^(n+1)列列车)
     先通过第一个"栈",将初始序列:     a1,a2,......,am   (m=2^(n+1))
中的aj1,aj2,......,ajk,这k列列车不考虑线性进入第一个"栈",余下的ai1,ai2,......,aik(不考
虑顺序)不入第一个"栈",这样将输入序列分为两部分,现在还余下n个"栈",依前面的假设,先可以将
未入第一个"栈"的ai1,ai2,......,aik(不考虑顺序)通过后面的N-1"栈"产生有序的输出序列:
         ai1,ai2,......,aik
     然后对于入第一个"栈"的序列aj1,aj2,......ajk(不考虑顺序)通过后面的n-1"栈"产生有序的
输出序列:           aj1,aj2,......ajk
     这样便产生最终输出序列: ai1,ai2,......aik,aj1,aj2,......ajk
本题得证.


$[3 应用 4]
$题目
编写一个函数将一般算术表
达式转化为逆波兰表达式.
$答案
解: 假设表达式中的符号以字符形式由键盘输入(为简单起见,设算术表达式中的参加运算的数字都只有一位数字),
该算术表达式存放在字符型数组str中,其逆波兰表示式依次存放在字符型数组exp中,在处理函数中用一个字符型数组
stack作为栈.设字符"#"为表达式的终止符,将算术表达式转换成逆波兰表示的方法如下:
    依次从键盘输入表达式中的字符c,对于每一个c:
    (1)若c为数字,则将c依次存入数组exp种;
    (2)若c为左括弧"(",则将此括弧压入栈stack;
    (3)若c为右括弧")",则将栈stack中左括弧"("以前的字符依次弹出存入数组exp中,然后将左括弧"("弹出;
    (4)若c为"+"或"-",则将当前栈stack中"("以前的所有字符(运算符)依次弹出存入数组exp中,然后将c压入栈stack中;
    (5)若c为"*"或"/",则将当前栈stack中的栈顶端连续的"*"或"/"弹出并依次存入数组exp中,然后将c压入栈stack中;
    (6)若c为"#",则将栈stack中所有运算符依次弹出并存如数组exp中,然后再将c存入数组exp钟,最后可得到表达式的逆
波兰表示在数组exp中. 
根据上述转换原理得到的函数如下:

#define Maxsize  100                 //Maxsize为算术表达式中最多字符个数
void trans(){
   char str[Maxsize];                //存储原算术表达式
   char exp[Maxsize];                //存储转换成的逆波兰表达式
   char stack[Maxsize];              //作为栈使用
   char ch;
   int i,j,t,top=0;                  //t作为exp下标,top作为stack的下标,i 作为str下标
   i=0;                              //获取用户输入的表达式
   do{
      i++;
      scanf("%c",&str[i]);
   }while(str[i]!="#"&&i<Maxsize);
   t=0;i=0;
   ch=str[i];
   i++;
   while(ch!="#"){
      if(ch>='0'&&ch<='9'){          //判定为数字 
         exp[t]=ch;
         t++;
      }
      else if(ch=='('){              //判定为左括号
         top++;
         stack[top]=ch;
      }
      else if(ch==')'){              //判定为右括号
         while(stack[top]!='('){
            exp[t]=stack[top];
            top--;
            t++;
         }
         top--;
      }
      else if(ch=='+'||ch=='-'){     //判定为加减号  
         while(top!=0&&stack[top]!='('){
            exp[t]=stack[top];
            top--;
            t++;
         }
         top++;
         stack[top]=ch;
      }
      else if(ch=='*'||ch=='/'){     //判定为乘除号 
         while(stack[top]=='*'||stack[top]=='/'){
            exp[t]=stack[top];
            top--;
            t++;
         }
         top++;
         stack[top]=ch;
      }
      ch=str[i];
      i++;
   }
   while(top!=0){
      exp[t]=stack[top];
      t++;
      top--;
   }
   exp[t]='#';
   for(j=1;j<=t;j++)
      printf("%c",exp[j]);
   printf("\n");
}       
 

$[3 应用 5]
$题目
	假设CQ[0,10]是一个循
环队列,初始状态为
front=rear=1,画出做完下列
操作后队列的头尾指针的状
态变化情况,若不能入队,请
指出元素,并说明理由.
	d,e,b,g,h入队
	d,e,出队
	i,j,k,l,m入队
	b出队
	n,o,p,q,r入队
$答案
解: 本题入队和出队的变化函数如图所示,当元素
d,e,b,g,h入队后,rear=6,front=1;元素d,e,出队,
rear=6,front=3;元素i,j,k,l,m入队,rear=0,
front=3;元素b出队后,rear=0,front=4,此时让
n,o,p入队,当q入列时,由于rear=3,front=4,有
rear+1=front,故栈上溢出.


$[3 应用 6]
$题目
编写向顺序分配的环形队列
QU[0,m0-1]中插入一个结点
的函数enqueue和从该队列
中取出一个结点的dequeue
函数.
$答案
解: 队列的特点是在队列尾部入队,顶部出队,
在循环队列中,最初队列为空时front和rear都
指向同一位置,当元素入队时,由于是循环的,
所以rear位置前移,即:
	QU->rear=(QU->rear+1)%m0
把插入的元素放到rear的新位置;当出队时,先将
front前移一个位置,即:
	QU->front=(QU->front+1)%m0
将front新位置的元素取出即可.根据上述原理
得到如下函数:

#define m0 100
enqueue(queue *QU,ElemType x){
   if(QU->rear+1)%m0==QU->front)
      printf("队列上溢出!\n");
   else{
      QU->rear=(QU->rear+1)%m0;
      QU->q[QU->rear]=x;
   }
}

dequeue(queue QU,ElemType *x){
   if(QU->rear==QU->front)
      printf("队列下溢出!\n");
   else{
      QU->front=(QU->front+1)%m0;
      *x=QU->q[front]; 
   }
}


$[3 程序 1]
$题目
	如果用一个循环数组
qu[0,m0-1]表示队列时,该
队列只有一个头指针front,
不设队尾指针rear,而改置
计数器count用以记录队列
中结点个数.
(1) 编写实现队列的五个基
本运算;
(2) 队列中能容纳元素的最
多个数还是m0-1个吗?
$答案
解: 
(1)依题意有如下条件:
   队列为空: count==0,front==1;                             队列为满: count==m0;
   队列尾的第一个元素位置==(front+count)%m0;                队列首的第一个元素位置==(front+1)%m0;   
   队列类型定义如下:                   typedef int qu[m0];
   由此得到如下的对应上述基本运算的五个函数下:

//m0定义为全局变量
void makenull(int front,int count){                      //使队列q为空
   front=1;
   count=0;
}

int empty(int count){                                   //判定队列里的元素是否为空 
   if(count==0)    return 1;
   else            return 0;
}

void pop(qu q,int front,int count,ElemType *x){         //取队列头元素给x
   if(count==0)     printf("队列下溢出\n");
   else{
      front=(front+1)%m0;
      *x=q[front];
   }
}

void enqueue(qu q,ElemType x,int front,int count){      //将元素x入列
   int place;
   if(count==m0)    printf("队列上溢出\n");
   else{
      count++;
      place=(front+count)%m0;
      q[place]=x;
   }
}

void dequeue(qu q,int front,int count){                 //删除队列头元素
   if(count==0)     printf("队列下溢出\n");
   else{
      front=(front+1)%m0;
      count--;
   }
}

(2)队列中可容纳最多元素个数为m0个.  

$[3 程序 2]
$题目
假定用一个循环单链表表示队列(称为循环队列),该队列只设一个队尾指针rear,不设队首指针,编写如下函数:
(1) 向循环链队中插入一个元素为x的结点;
(2) 从循环队列中删除一个结点.
$答案
解:
(1)依题意,定义本题队列的结点类型如下:
typedef struct linknode{
   int data;
   struct linknode *next;
}qu;
队列插入一个结点的操作是在队尾进行的,所以应在该循环链队的尾部插入一个结点,其函数如下:
inqueue(qu *rear,ElemType x){
   qu *head,*s;
   s=(qu*)malloc(size(qu));                            //建立一个新结点
   s->data=x;
   if(rear==NULL){                                     //循环队列为空,则建立一个结点的循环队列
      rear=s;
      rear->next=s;
   }  
   else{                                               //循环队列不为空,则s插到后面
      head=rear->next;
      rear->next=s;
      rear=s;                                          //rear始终指向最后一个结点
      rear->next=head;
   }
}
(2)队列的删除结点是在队首进行的,所以应删除该循环链表的第一个结点,其函数如下:
void delqueue(qu *rear,qu *head){
   if(rear==NULL)       printf("队列下溢出\n");
   else{
      head=rear->next;                                //head指向队首结点
      if(head==rear)   rear=NULL;                     //只有一个结点则直接删除该点
      else  rear->next=head->next;                    //否则删除第一个结点
      free(head);                                     //释放队首结点
   }
}


$[3 程序 3]
$题目
用单链表实现队列如图所示,并令front=rear=NULL表示队列为空,编写队列的如下五种运算的函数:
makenull:      将队列置成空队列               front:    返回队列的第一个元素
enqueue:       把元素x插入盗队列的后端        dequeue:  删除队列的第一个元素
empty:         判断队列是否为空
$答案
解: 依题意,定义单链表结点类型如下:
typedef struct linknode{
   int data;
   struct linknode *next;
}node;
根据单连表的特点,实现队列的五种运算函数如下:
void makenull(node *front,node *rear){
   front=NULL;
   rear=NULL;
}

void front(node *front,node *rear,int *x){
   if(front==NULL)      printf("队列下溢出\n");
   else *x=front->data;
}

void enqueue(node *front,node *rear,ElemType x){
   node *p;
   if(rear==NULL){                              // 若队列为空,则直接建立一个链表
      rear=(node*)malloc(sizeof(node));         //建立一个新结点,由rear所指向
      rear->data=x;
      front=rear;
   }
   else{                                        //若不为空,则建立一个结点将其链表链接到末尾
      p=(node *)malloc(sizeof(node));           //建立一个新结点,由p所指向
      p->data=x;
      rear->next=p;
      rear=p;
   }
}

void dequeue(node *front,node *rear){
   node *p;
   if(front==NULL)      printf("队列下溢出\n");
   else{
      p=front;
      front=front->next;
      free(p);
   }
}

int empty(node *front){
   if(front==NULL)   return 1;
   else              return 0;
}
