数据结构课程课后习题答案.doc

练习题及参考答案

《数据结构简明教程》练习题及参考答案
练习题1
1. 单项选择题
（1）线性结构中数据元素之间是（ ）关系。
A.一对多 B.多对多 C.多对一 D.一对一
答：D
（2）数据结构中与所使用的计算机无关的是数据的（ ）结构。
A.存储 B.物理 C.逻辑 D.物理和存储
答：C
（3）算法分析的目的是（ ）。
A.找出数据结构的合理性 B.研究算法中的输入和输出的关系
C.分析算法的效率以求改进 D.分析算法的易懂性和文档性
答：C
（4）算法分析的两个主要方面是（ ）。
A.空间复杂性和时间复杂性 B.正确性和简明性
C.可读性和文档性 D.数据复杂性和程序复杂性
答：A
（5）计算机算法指的是（ ）。
A.计算方法 B. 排序方法 C.求解问题的有限运算序列 D.调度方法
答：C
（6）计算机算法必须具备输入、输出和（ ）等5个特性。
A.可行性、可移植性和可扩充性 B.可行性、确定性和有穷性
C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性
答：B
2. 填空题
（1）数据结构包括数据的 ① 、数据的 ② 和数据的 ③ 这三个方面的内容。
答：①逻辑结构 ②存储结构 ③运算
（2）数据结构按逻辑结构可分为两大类，它们分别是 ① 和 ② 。
答：①线性结构 ②非线性结构
（3）数据结构被形式地定义为（D,R），其中D是 ① 的有限集合，R是D上的 ② 有限集合。
答：①数据元素 ②关系
（4）在线性结构中，第一个结点 ① 前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点 ② 后继结点，其余每个结点有且只有1个后继结点。
答：①没有 ②没有
（5）在树形结构中，树根结点没有 ① 结点，其余每个结点有且只有 ② 个前驱结点；叶子结点没有 ③ 结点，其余每个结点的后继结点数可以是 ④ 。
答：①前驱 ②1 ③后继 ④任意多个
（6）在图形结构中，每个结点的前驱结点数和后继结点数可以是（ ）。
答：任意多个
（7）数据的存储结构主要有四种，它们分别是 ① 、 ② 、 ③ 和 ④ 存储结构。
答：①顺序 ②链式 ③索引 ④哈希
（8）一个算法的效率可分为 ① 效率和 ② 效率。
答：①时间 ②空间
3. 简答题
（1）数据结构和数据类型两个概念之间有区别吗？
答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素的集合。数据类型不仅定义了一组数据元素，而且还在其上定义了一组操作。
（2）简述线性结构、树形结构和图形结构的不同点。
答：线性结构反映结点间的逻辑关系是一对一的，树形线性结构反映结点间的逻辑关系是一对多的，图在结构反映结点间的逻辑关系是多对多的。
（3）设有采用二元组表示的数据逻辑结构S=(D,R)，其中D={a,b,…,i}，R={(a,b),(a,c),(c,d),(c,f),(f,h),(d,e),(f,g),(h,i)}，问相对于关系R，哪些结点是开始结点，哪些结点是终端结点？
答：该逻辑结构为树形结构，其中a结点没有前驱结点，称为根结点，b、e、g、i结点没有后继结点，是终端结点，也称为叶子结点。
（4）以下各函数是算法中语句的执行频度，n为问题规模，给出对应的时间复杂度：
T1(n)=nlog2n-1000log2n
T2(n)=-1000log2n
T3(n)=n2-1000log2n
T4(n)=2nlog2n-1000log2n
答：T1(n)=O(nlog2n)，T2(n)=O( )，T3(n)=O(n2)，T4(n)=O(nlog2n)。
（5）分析下面程序段中循环语句的执行次数。
int j=0,s=0,n=100;
do
{ j=j+1;
s=s+10*j;
} while (j<n && s<n);
答：j=0，第1次循环：j=1，s=10。第2次循环：j=2，s=30。第3次循环：j=3，s=60。第4次循环：j=4，s=100。while条件不再满足。所以，其中循环语句的执行次数为4。
（6）执行下面的语句时，语句s++的执行次数为多少？
int s=0;
for (i=1;i<n-1;i++)
for (j=n;j>=i;j--)
s++;
答：语句s的执行次数。
（7）设n为问题规模，求以下算法的时间复杂度。
void fun1(int n)
{ int x=0,i;
for (i=1;i<=n;i++)
for (j=i+1;j<=n;j++)
x++;
}
答：其中x++语句属基本运算语句，=O(n2)。
（8）设n为问题规模，是一个正偶数，试计算以下算法结束时m的值，并给出该算法的时间复杂度。
void fun2(int n)
{ int m=0;
for (i=1;i<=n;i++)
for (j=2*i;j<=n;j++)
m++;
}
答：由于内循环j的取值范围，所以i≤n/2，则，该程序段的时间复杂度为O(n2)。
上机实验题1
有一个整型数组a，其中含有n个元素，设计尽可能好的算法求其中的最大元素和次大元素，并采用相关数据测试。
解：maxs算法用于返回数组a[0..n-1]中的最大元素值max1和次大元素值max2，max1和max2设计为引用类型。对应的程序如下：
#include <stdio.h>
void maxs(int a[],int n,int &max1,int &max2)
{ int i;
max1=max2=a[0];
for (i=1;i<n;i++)
if (a[i]>max1)
{ max2=max1;
max1=a[i];
}
else if (a[i]>max2)
max2=a[i];
}
void main()
{ int a[]={1,4,10,6,8,3,5,7,9,2};
int n=10;
int max1,max2;
maxs(a,n,max1,max2);
printf("最大元素值=%d,次大元素值=%d\n",max1,max2);
}
练习题2
1. 单项选择题
（1）数据在计算机存储器内表示时，物理地址与逻辑地址相对顺序相同并且是连续的，称之为（ ）。
A.存储结构 B.逻辑结构 C.顺序存储结构 D.链式存储结构
答：C
（2）在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（ ）。
A.访问第i个结点（1≤i≤n）和求第i（2≤i≤n）个结点的前驱结点
B.在第i（1≤i≤n）个结点后插入一个新结点
C.删除第i个结点（1≤i≤n）
D.将n个结点从小到大排序
答：A
（3） 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ ）个元素。
A.8 B.63.5 C.63 D.7
答：B
（4）链式存储结构所占存储空间（ ）。
A.分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
B.只有一部分，存放结点值
C.只有一部分，存储表示结点间关系的指针
D.分两部分，一部分存放结点值，另一部分存放结点所占单元数
答：A
（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。
A.必须是连续的 B.部分地址必须是连续的
C.一定是不连续的 D.连续或不连续都可以
答：D
（6）一个线性表在（ ）情况下适用于采用链式存储结构。
A.需经常修改其中的结点值 B.需不断对其进行删除插入
C.其中含有大量的结点 D.其中结点结构复杂
答：B
（7）单链表的存储密度（ ）
A.大于1 B.等于1 C.小于1 D.不能确定
答：C
2. 填空题
（1）在顺序表中插入或删除一个元素时，需要平均移动（ ① ）元素，具体移动的元素个数与（ ② ）有关。
答：①表中一半 ②表长和该元素在表中的位置
（2）向一个长度为n的顺序表的第i个元素（1≤i≤n+1）之前插入一个元素时，需向后移动（ ）个元素。
答：n-i+1
（3）向一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动（ ）个元素。
答：n-i
（4）在顺序表中访问任意一个元素的时间复杂度均为（ ① ），因此顺序表也称为（ ② ）的数据结构。
答：①O(1) ②随机存取
（5）顺序表中逻辑上相邻的元素的物理位置（ ① ）相邻。单链表中逻辑上相邻的元素的物理位置（ ② ）相邻。
答：①一定 ②不一定
（6）在带头结点的单链表中，除头结点外，任一结点的存储位置由（ ）指示。
答：其前驱结点的链域的值
（7）在含有n个数据结点的单链表中要删除已知结点*p，需找到它的（ ① ），其时间复杂度为（ ② ）。
答：①前驱结点的地址 ②O(n)
（8）含有n（n>1）个结点的循环双向链表中，为空的指针域数为（ ）。
答：0
3. 简答题
（1）试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？
答：顺序存储结构中，相邻数据元素的存放地址也相邻，并要求内存中可用存储单元的地址必须是连续的。其优点是存储密度大，存储空间利用率高；缺点是插入或删除元素时不方便。
链式存储结构中，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。其优点是插入或删除元素时很方便，使用灵活；缺点是存储密度小，存储空间利用率低。
顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。
（2）对于表长为n的顺序表，在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需要移动的元素的平均个数为多少？删除一个元素所需要移动的平均个数为多少？
答：插入一个元素所需要移动的元素的平均个数为(n-1)/2，删除一个元素所需要移动的平均个数为n/2。
（3）在链表中设置头结点的作用是什么？
答：在链表中设置头结点后，不管链表是否为空表，头结点指针均不空，并使得对链表的操作（如插入和删除）在各种情况下统一，从而简化了算法的实现过程。
（4）对于双链表和单链表，在两个结点之间插入一个新结点时需修改的指针各为多少个？
答：对于双链表，在两个结点之间插入一个新结点时，需修改前驱结点的next域、后继结点的prior域和新插入结点的next、prior域。所以共修改4个指针。
对于单链表，在两个结点之间插入一个新结点时，需修改前一结点的next域，新插入结点的next域。所以共修改两个指针。
（5）某含有n（n>1）结点的线性表中，最常用的操作是在尾结点之后插入一个结点和删除第一个结点，则采用以下哪种存储方式最节省运算时间。
①单链表；
②仅有头指针不带头结点的循环单链表；
③双链表；
④仅有尾指针的循环单链表。
答：在单链表中，删除第一个结点的时间复杂度为O(1)。插入结点需找到前驱结点，所以在尾结点之后插入一个结点，需找到尾结点，对应的时间复杂度为O(n)。
在仅有头指针不带头结点的循环单链表中，删除第一个结点的时间复杂度O(n)，因为删除第一个结点后还要将其改为循环单链表；在尾结点之后插入一个结点的时间复杂度也为O(n)。
在双链表中，删除第一个结点的时间复杂度为O(1)；在尾结点之后插入一个结点，也需找到尾结点，对应的时间复杂度为O(n)。
在仅有尾指针的循环单链表中，通过该尾指针可以直接找到第一个结点，所以删除第一个结点的时间复杂度为O(1)；在尾结点之后插入一个结点也就是在尾指针所指结点之后插入一个结点，时间复杂度也为O(1)。因此④最节省运算时间。
4. 算法设计题
（1）设计一个高效算法，将顺序表的所有元素逆置，要求算法空间复杂度为O(1)。
解：遍历顺序表L的前半部分元素，对于元素L.data[i]（0≤i＜L.length/2），将其与后半部分对应元素L.data[L.length-i-1]进行交换。对应的算法如下：
void reverse(SqList &L)
{ int i;
ElemType x;
for (i=0;i<L.length/2;i++)
{ x=L.data[i]; //L.data[i]与L.data[L.length-i-1]交换
L.data[i]=L.data[L.length-i-1];
L.data[L.length-i-1]=x;
}
}
本算法的时间复杂度为O(n)。
（2）设计一个算法从顺序表中删除重复的元素，并使剩余元素间的相对次序保持不变。
解：对于顺序表L，用i从1开始遍历其元素，设L.data[0..j]（j的初值为0）中没有重复的元素。检测L.data[i]（j<i<L.length），若L.data[i]和L.data[0..j]中任何一个元素都不相同，则将L.data[i]存入L.data[j+1]中。对应的算法如下：
void delsame(SqList &L) //L为引用型参数
{ int i,j=0,k;
for (i=1;i<L.length;i++)
{ k=0;
while (k<=j && L.data[k]!=L.data[i])
k++;
if (k>j) //表示L.data[i]和L.data[0..j]中所有元素都不相同
{ j++;
L.data[j]=L.data[i];
}
}
L.length=j+1; //顺序表长度置新值
}
本算法的时间复杂度为O(n2)，空间复杂度为O(1)。
（3）设计一个算法从有序顺序表中删除重复的元素，并使剩余元素间的相对次序保持不变。
解：在有序顺序表L中，所有重复的元素应是相邻存放的，用k保存不重复出现的元素个数，先将不重复的有序区看成是L.data[0..0]，置e=L.data[0]，用i从1开始遍历L的所有元素：当L.data[i]≠e时，将它放在L.data[k]中，k增1，置e=L.data[i]，最后将L的length置为k。对应的算法如下：
void delsame1(SqList &L) //L为引用型参数
{ int i,k=1; //k保存不重复的元素个数
ElemType e;
e=L.data[0];
for (i=1;i<L.length;i++)
{ if (L.data[i]!=e) //只保存不重复的元素
{ L.data[k]=L.data[i];
k++;
e=L.data[i];
}
}
L.length=k; //顺序表长度置新值
}
本算法是一个高效算法，其时间复杂度为O(n)，空间复杂度为O(1)。如果每次遇到重复的元素，都通过移动其后所有元素来删除它，这样的时间复杂度会变成O(n2)。
（4）设计一个算法删除单链表L中第一个值为x的结点。
解：用p、q遍历整个单链表，p指向*q的前驱结点，q用于查找第一个值为x的结点，当找到后将*q结点删除，返回1；否则返回0。对应的算法如下：
int delx(SLink *&L,ElemType x)
{ SLink *p=L,*q=p->next; //p指向*q的前驱结点
while (q!=NULL && q->data!=x)
{ p=q;
q=q->next;
}
if (q!=NULL) //找到值为x的结点
{ p->next=q->next;
free(q);
return 1;
}
else return 0; //未找到值为x的结点
}
（5）设计一个算法判定单链表L是否是递增的。
解：判定链表L从第2个结点开始的每个结点的值是否比其前驱的值大。若有一个不成立，则整个链表便不是递增的；否则是递增的。对应的算法如下：
int increase(SLink *L)
{ SLink *pre=L->next,*p; //pre指向第一个数据结点
p=pre->next; //p指向*pre结点的后继结点
while (p!=NULL)
{ if (p->data>=pre->data) //若正序则继续判断下一个结点
{ pre=p; //pre、p同步后移
p=p->next;
}
else return 0;
}
return 1;
}
（6）有一个整数元素建立的单链表A，设计一个算法，将其拆分成两个单链表A和B，使得A单链表中含有所有的偶数结点，B单链表中所有的奇数结点，且保持原来的相对次序。
解：采用重新单链表的方法，由于要保持相对次序，所以采用尾插法建立新表A、B。用p遍历原单链表A的所有数据结点，若为偶数结点，将其链到A中，若为奇数结点，将其链到B中。对应的算法如下：
void Split(SLink *&A,SLink *&B)
{ SLink *p=A->next,*ra,*rb;
ra=A;
B=(SLink *)malloc(sizeof(SLink)); //建立头结点
rb=B; //r总是指向B链表的尾结点
while (p!=NULL)
{ if (p->data%2==0) //偶数结点
{ ra->next=p; //将*p结点链到A中
ra=p;
p=p->next;
}
else //奇数结点
{ rb->next=p; //将*p结点链到B中
rb=p;
p=p->next;
}
}
ra->next=rb->next=NULL;
}
本算法的时间复杂度为O(n)，空间复杂度为O(1)。
（7）有一个有序单链表（从小到大排列），表头指针为L，设计一个算法向该单链表中插入一个元素为x的结点，使插入后该链表仍然有序。
解：先建立一个待插入的结点，然后依次与链表中的各结点的数据域比较大小，找到插入该结点的位置，最后插入该结点。对应的算法如下：
void inorderList(SLink *&L,ElemType x)
{ SLink *s,*p,*q;
s=(SLink *)malloc(sizeof(SLink)); //建立一个待插入的结点
s->data=x;s->next=NULL;
if (L==NULL || x<L->data) //若单链表为空或x小于第1个结点date域
{ s->next=L; //把*s结点插入到头结点之后
L=s;
}
else
{ q=L; //寻找插入位置,p指向待比较的结点,q指向p的前驱结点
p=q->next;
while (p!=NULL && x>p->data) //若x小于p所指结点的data域值
if (x>p->data)
{ q=p;
p=p->next;
}
s->next=p; //将s结点插入到*q和*p之间
q->next=s;
}
}
（8）有一个单链表L，其中可能出现值域重复的结点，设计一个算法删除值域重复的结点。并分析算法的时间复杂度。
解：用p遍历单链表，用r遍历*p结点之后的结点，q始终指向*r结点的直接前驱结点，若r->data==p->data，则删除*r结点，否则q、r同步后移一个结点。对应的算法如下：
void dels1(SLink *&L)
{ SLink *p=L->next,*q,*r,*t;
while (p!=NULL)
{ q=p;
r=q->next;
while (r!=NULL)
{ if (r->data==p->data) //r指向被删结点
{ t=r->next;
q->next=t;
free(r);
r=t;
}
else
{ q=r;
r=r->next;
}
}
p=p->next;
}
}
本算法的时间复杂度为O(n2)。
（9）有一个递增有序单链表（允许出现值域重复的结点），设计一个算法删除值域重复的结点。并分析算法的时间复杂度。
解：由于是有序表，所以相同值域的结点都是相邻的。用p遍历递增单链表，若*p结点的值域等于其后结点的值域，则删除后者。对应的算法如下：
void dels(SLink *&L)
{ SLink *p=L->next,*q;
while (p->next!=NULL)
{ if (p->data==p->next->data) //找到重复值的结点
{ q=p->next; //q指向这个重复值的结点
p->next=q->next; //删除*q结点
free(q);
}
else p=p->next;
}
}
本算法的时间复杂度为O(n)。
（10）有一个双链表L，设计一个算法查找第一个元素值为x的结点，将其与后继结点进行交换。
解：先找到第一个元素值为x的结点*p，q指向其后继结点，本题是将*p结点移到*q结点之后，实现过程是：删除*p结点，再将其插入到*q结点之后。对应的算法如下：
int swap(DLink *L,ElemType x)
{ DLink *p=L->next,*q;
while (p!=NULL && p->data!=x)
p=p->next;
if (p==NULL) //未找到值为x的结点
return 0;
else //找到值为x的结点*p
{ q=p->next; //q指向*p的后继结点
if (q!=NULL) //*p结点不是尾结点
{ p->prior->next=q; //先删除*p结点
q->prior=p->prior;
p->next=q->next; //将*p结点插入到*q结点之后
if (q->next!=NULL)
q->next->prior=p;
q->next=p;
p->prior=q;
return 1;
}
else //*p结点是尾结点
return 0; //无法与后继结点交换，返回0
}
}
（11）对于有n（n≥1）个数据结点的循环单链表L，设计一个算法将所有结点逆置。
解：采用头插法重建循环单链表L的思路，先建立一个空的循环单链表，用p遍历所有数据结点，每次将*p结点插入到前端。对应的算法如下：
void Reverse(SLink *&L)
{ SLink *p=L->next,*q;
L->next=L; //建立一个空循环单链表
while (p!=L)
{ q=p->next;
p->next=L->next; //将*p结点插入到前端
L->next=p;
p=q;
}
}
上机实验题2
有两个整数集合采用有序单链表存储，设计尽可能高效的算法求两个集合的并集、交集和差集。并用相关数据进行测试。
#include <stdio.h>
#include "SLink.h"
void Union(SLink *L1,SLink *L2,SLink *&L3) //求并集
{ SLink *p,*q,*s,*tc;
L3=(SLink *)malloc(sizeof(SLink));
tc=L3;
p=L1->next;
q=L2->next;
while (p!=NULL && q!=NULL)
{ if (p->data<q->data)
{ s=(SLink *)malloc(sizeof(SLink));
s->data=p->data;
tc->next=s;
tc=s;
p=p->next;
}
else if (p->data>q->data)
{ s=(SLink *)malloc(sizeof(SLink));
s->data=q->data;
tc->next=s;
tc=s;
q=q->next;
}
else
{ s=(SLink *)malloc(sizeof(SLink));
s->data=p->data;
tc->next=s;
tc=s;
p=p->next;
q=q->next;
}
}
while (p!=NULL)
{ s=(SLink *)malloc(sizeof(SLink));
s->data=p->data;
tc->next=s;
tc=s;
p=p->next;
}
while (q!=NULL)
{ s=(SLink *)malloc(sizeof(SLink));
s->data=q->data;
tc->next=s;
tc=s;
q=q->next;
}
tc->next=NULL;
}
void InterSection(SLink *L1,SLink *L2,SLink *&L3) //求交集
{ SLink *p,*q,*s,*tc;
L3=(SLink *)malloc(sizeof(SLink));
tc=L3;
p=L1->next;
q=L2->next;
while (p!=NULL && q!=NULL)
{ if (p->data<q->data)
p=p->next;
else if (p->data>q->data)
q=q->next;
else //p->data=q->data
{ s=(SLink *)malloc(sizeof(SLink));
s->data=p->data;
tc->next=s;
tc=s;
p=p->next;
q=q->next;
}
}
tc->next=NULL;
}
void Subs(SLink *L1,SLink *L2,SLink *&L3) //求差集
{ SLink *p,*q,*s,*tc;
L3=(SLink *)malloc(sizeof(SLink));
tc=L3;
p=L1->next;
q=L2->next;
while (p!=NULL && q!=NULL)
{ if (p->data<q->data)
{ s=(SLink *)malloc(sizeof(SLink));
s->data=p->data;
tc->next=s;
tc=s;
p=p->next;
}
else if (p->data>q->data)
q=q->next;
else //p->data=q->data
{ p=p->next;
q=q->next;
}
}
while (p!=NULL)
{ s=(SLink *)malloc(sizeof(SLink));
s->data=p->data;
tc->next=s;
tc=s;
p=p->next;
}
tc->next=NULL;
}
void main()
{ SLink *A,*B,*C,*D,*E;
ElemType a[]={1,3,6,8,10,20};
CreateListR(A,a,6); //尾插法建表
printf("集合A:");DispList(A);
ElemType b[]={2,5,6,10,16,20,30};
CreateListR(B,b,7); //尾插法建表
printf("集合B:");DispList(B);
printf("求A、B并集C\n");
Union(A,B,C); //求A、B并集C
printf("集合C:");DispList(C);
printf("求A、B交集C\n");
InterSection(A,B,D); //求A、B并集D
printf("集合D:");DispList(D);
printf("求A、B差集E\n");
Subs(A,B,E); //求A、B差集E
printf("集合E:");DispList(E);
DestroyList(A);
DestroyList(B);
DestroyList(C);
DestroyList(D);
DestroyList(E);
}
练习题3
1. 单项选择题
（1）栈中元素的进出原则是（ ）。
A.先进先出 B.后进先出 C.栈空则进 D.栈满则出
答：B
（2）设一个栈的进栈序列是A、B、C、D（即元素A～D依次通过该栈），则借助该栈所得到的输出序列不可能是（ ）。
A.A,B,C,D B.D,C,B,A C.A,C,D,B D.D,A,B,C
答：D
（3）一个栈的进栈序列是a、b、c、d、e，则栈的不可能的输出序列是（ ）。
A.edcba B.decba C.dceab D.abcde
答：C
（4）已知一个栈的进栈序列是1，2，3，…，n，其输出序列的第一个元素是i（1≤i≤n）则第j（1≤j≤n）个出栈元素是（ ）。
A.i B.n-i C.j-i+1 D.不确定
答：D
（5）设顺序栈st的栈顶指针top的初始时为-1，栈空间大小为MaxSize，则判定st栈为栈空的条件为（ ）。
A.st.top==-1 B.st.top!=-1
C.st.top!=MaxSize D.st.top==MaxSize
答：A
（6）设顺序栈st的栈顶指针top的初始时为-1，栈空间大小为MaxSize，则判定st栈为栈满的条件是 。
A.st.top!=-1 B.st.top==-1
C.st.top!=MaxSize-1 D.st.top==MaxSize-1
答：D
（7）队列中元素的进出原则是（ ）。
A.先进先出 B.后进先出 C.栈空则进 D.栈满则出
答：A
（8）元素A、B、C、D顺序连续进入队列qu后，队头元素是（ ① ），队尾元素是（ ② ）。
A.A B.B
C.C D.D
答：①A ②D。
（9）一个队列的入列序列为1234，则队列可能的输出序列是（ ）。
A.4321 B.1234
C.1432 D.3241
答：B
（10）循环队列qu（队头指针front指向队首元素的前一位置，队尾指针rear指向队尾元素的位置）的队满条件是（ ）。
A. (qu.rear+1)%MaxSize==(qu.front+1)%MaxSize
B. (qu.rear+1)%MaxSize==qu.front+1
C.(qu.rear+1)%MaxSize==qu.front
A.qu.rear==qu.front
答：C
（11）循环队列qu（队头指针front指向队首元素的前一位置，队尾指针rear指向队尾元素的位置）的队空条件是（ ）。
A. (qu.rear+1)%MaxSize==(qu.front+1)%MaxSize
B. (qu.rear+1)%MaxSize==qu.front+1
C.(qu.rear+1)%MaxSize==qu.front
D.qu.rear==qu.front
答：D
（12）设循环队列中数组的下标是0～N-1，其头尾指针分别为f和r（队头指针f指向队首元素的前一位置，队尾指针r指向队尾元素的位置），则其元素个数为（ ）。
A.r-f B.r-f-1
C.(r-f)％N+1 D.(r-f+N)％N
答：D
（13）设有4个数据元素a、b、c和d，对其分别进行栈操作或队操作。在进栈或进队操作时，按a、b、c、d次序每次进入一个元素。假设栈或队的初始状态都是空。现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是（ ① ），第二次出栈得到的元素是（ ② ）；类似地，考虑对这4个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是（ ③ ），第二次出队得到的元素是（ ④ ）。经操作后，最后在栈中或队中的元素还有（ ⑤ ）个。
①～④：A.a B.b C.c D.d
⑤： A.1 B.2 C.3 D.0
答：①B ②D ③A ④B ⑤B
（14）设栈S和队列Q的初始状态为空，元素e1～e6依次通过栈S，一个元素出后即进队列Q，若6个元素出队的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（ ）。
A.5 B.4 C.3 D.2
答：C
2. 填空题
（1）栈是一种特殊的线性表，允许插入和删除运算的一端称为（ ① ）。不允许插入和删除运算的一端称为（ ② ）。
答：①栈顶 ②栈底
（2）一个栈的输入序列是12345，的输出序列为12345，其进栈出栈的操作为（ ）。
答：1进栈，1出栈，2进栈，2出栈，3进栈，3出栈，4进栈，4出栈，5进栈，5出栈。
（3）有5个元素，其进栈次序为A、B、C、D、E，在各种可能的出栈次序中，以元素C、D最先出栈（即C第一个且D第二个出栈）的次序有（ ）。
答：CDBAE、CDEBA、CDBEA。
（4）顺序栈用data[0..n-1]存储数据，栈顶指针为top，其初始值为0，则元素x进栈的操作是（ ）。
答：data[top]=x; top++;
（5）顺序栈用data[0..n-1]存储数据，栈顶指针为top，其初始值为0，则出栈元素x的操作是（ ）。
答：top--; x=data[top];
（6）（ ）是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
答：队列
（7）设有数组A[0..m]作为循环队列的存储空间，front为队头指针（它指向队首元素的前一位置），rear为队尾指针（它指向队尾元素的位置），则元素x执行入队的操作是（ ）。
答：rear=(rear+1)%(m+1); A[rear]=x;
（8）设有数组A[0..m]作为循环队列的存储空间，front为队头指针（它指向队首元素的前一位置），rear