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

《数据结构课程课后习题答案.doc》由会员分享，可在线阅读，更多相关《数据结构课程课后习题答案.doc（62页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、如有侵权，请联系网站删除，仅供学习与交流数据结构课程 课后习题答案【精品文档】第 61 页数据结构简明教程练习题及参考答案练习题11. 单项选择题（1）线性结构中数据元素之间是（ ）关系。A.一对多B.多对多C.多对一D.一对一答：D（2）数据结构中与所使用的计算机无关的是数据的（ ）结构。A.存储B.物理C.逻辑D.物理和存储答：C（3）算法分析的目的是（ ）。A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性答：C（4）算法分析的两个主要方面是（ ）。A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程

2、序复杂性答：A（5）计算机算法指的是（ ）。A.计算方法B. 排序方法C.求解问题的有限运算序列D.调度方法答：C（6）计算机算法必须具备输入、输出和（ ）等5个特性。A.可行性、可移植性和可扩充性B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性答：B2. 填空题（1）数据结构包括数据的 、数据的 和数据的 这三个方面的内容。答：逻辑结构 存储结构 运算（2）数据结构按逻辑结构可分为两大类，它们分别是 和 。答：线性结构 非线性结构（3）数据结构被形式地定义为（D,R），其中D是 的有限集合，R是D上的 有限集合。答：数据元素 关系（4）在线性结构中，第一个结点

3、前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点 后继结点，其余每个结点有且只有1个后继结点。答：没有 没有（5）在树形结构中，树根结点没有 结点，其余每个结点有且只有 个前驱结点；叶子结点没有 结点，其余每个结点的后继结点数可以是 。答：前驱 1 后继 任意多个（6）在图形结构中，每个结点的前驱结点数和后继结点数可以是（ ）。答：任意多个（7）数据的存储结构主要有四种，它们分别是 、 、 和 存储结构。答：顺序 链式 索引 哈希（8）一个算法的效率可分为 效率和 效率。答：时间 空间3. 简答题（1）数据结构和数据类型两个概念之间有区别吗？答：简单地说，数据结构定义了一组按某些关系结

4、合在一起的数组元素的集合。数据类型不仅定义了一组数据元素，而且还在其上定义了一组操作。（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结点没有后继结点，是终端结点，也

5、称为叶子结点。（4）以下各函数是算法中语句的执行频度，n为问题规模，给出对应的时间复杂度：T1(n)=nlog2n-1000log2nT2(n)=-1000log2nT3(n)=n2-1000log2nT4(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;doj=j+1;s=s+10*j; while (jn & sn);答：j=0，第1次循环：j=1，s=10。第2次循环：j=2，s=30。第3次循环：j=3，

6、s=60。第4次循环：j=4，s=100。while条件不再满足。所以，其中循环语句的执行次数为4。（6）执行下面的语句时，语句s+的执行次数为多少？int s=0;for (i=1;i=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;

7、i=n;i+)for (j=2*i;j=n;j+)m+;答：由于内循环j的取值范围，所以in/2，则，该程序段的时间复杂度为O(n2)。上机实验题1有一个整型数组a，其中含有n个元素，设计尽可能好的算法求其中的最大元素和次大元素，并采用相关数据测试。解：maxs算法用于返回数组a0.n-1中的最大元素值max1和次大元素值max2，max1和max2设计为引用类型。对应的程序如下：#include void maxs(int a,int n,int &max1,int &max2)int i;max1=max2=a0;for (i=1;imax1)max2=max1;max1=ai;else

8、if (aimax2)max2=ai;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,次大元素值=%dn,max1,max2);练习题21. 单项选择题（1）数据在计算机存储器内表示时，物理地址与逻辑地址相对顺序相同并且是连续的，称之为（ ）。A.存储结构B.逻辑结构C.顺序存储结构D.链式存储结构答：C（2）在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（ ）。A.访问第i个结点（1in）和求第i（2in）个结点的前驱结点B.在第i（1i

9、n）个结点后插入一个新结点C.删除第i个结点（1in）D.将n个结点从小到大排序答：A（3） 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ ）个元素。A.8B.63.5C.63D.7答：B（4）链式存储结构所占存储空间（ ）。A.分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B.只有一部分，存放结点值C.只有一部分，存储表示结点间关系的指针D.分两部分，一部分存放结点值，另一部分存放结点所占单元数答：A（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续或不连续都可

10、以答：D（6）一个线性表在（ ）情况下适用于采用链式存储结构。A.需经常修改其中的结点值B.需不断对其进行删除插入C.其中含有大量的结点D.其中结点结构复杂答：B（7）单链表的存储密度（ ）A.大于1B.等于1C.小于1D.不能确定答：C2. 填空题（1）在顺序表中插入或删除一个元素时，需要平均移动（ ）元素，具体移动的元素个数与（ ）有关。答：表中一半 表长和该元素在表中的位置（2）向一个长度为n的顺序表的第i个元素（1in+1）之前插入一个元素时，需向后移动（ ）个元素。答：n-i+1（3）向一个长度为n的顺序表中删除第i个元素（1in）时，需向前移动（ ）个元素。答：n-i（4）在顺序表

11、中访问任意一个元素的时间复杂度均为（ ），因此顺序表也称为（ ）的数据结构。答：O(1) 随机存取（5）顺序表中逻辑上相邻的元素的物理位置（ ）相邻。单链表中逻辑上相邻的元素的物理位置（ ）相邻。答：一定 不一定（6）在带头结点的单链表中，除头结点外，任一结点的存储位置由（ ）指示。答：其前驱结点的链域的值（7）在含有n个数据结点的单链表中要删除已知结点*p，需找到它的（ ），其时间复杂度为（ ）。答：前驱结点的地址 O(n)（8）含有n（n1）个结点的循环双向链表中，为空的指针域数为（ ）。答：03. 简答题（1）试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？答：顺

12、序存储结构中，相邻数据元素的存放地址也相邻，并要求内存中可用存储单元的地址必须是连续的。其优点是存储密度大，存储空间利用率高；缺点是插入或删除元素时不方便。链式存储结构中，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。其优点是插入或删除元素时很方便，使用灵活；缺点是存储密度小，存储空间利用率低。顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。（2）对于表长为n的顺序表，在任何位置上插入或删除一个元

13、素的概率相等时，插入一个元素所需要移动的元素的平均个数为多少？删除一个元素所需要移动的平均个数为多少？答：插入一个元素所需要移动的元素的平均个数为(n-1)/2，删除一个元素所需要移动的平均个数为n/2。（3）在链表中设置头结点的作用是什么？答：在链表中设置头结点后，不管链表是否为空表，头结点指针均不空，并使得对链表的操作（如插入和删除）在各种情况下统一，从而简化了算法的实现过程。（4）对于双链表和单链表，在两个结点之间插入一个新结点时需修改的指针各为多少个？答：对于双链表，在两个结点之间插入一个新结点时，需修改前驱结点的next域、后继结点的prior域和新插入结点的next、prior域。

14、所以共修改4个指针。对于单链表，在两个结点之间插入一个新结点时，需修改前一结点的next域，新插入结点的next域。所以共修改两个指针。（5）某含有n（n1）结点的线性表中，最常用的操作是在尾结点之后插入一个结点和删除第一个结点，则采用以下哪种存储方式最节省运算时间。单链表；仅有头指针不带头结点的循环单链表；双链表；仅有尾指针的循环单链表。答：在单链表中，删除第一个结点的时间复杂度为O(1)。插入结点需找到前驱结点，所以在尾结点之后插入一个结点，需找到尾结点，对应的时间复杂度为O(n)。在仅有头指针不带头结点的循环单链表中，删除第一个结点的时间复杂度O(n)，因为删除第一个结点后还要将其改为循

15、环单链表；在尾结点之后插入一个结点的时间复杂度也为O(n)。在双链表中，删除第一个结点的时间复杂度为O(1)；在尾结点之后插入一个结点，也需找到尾结点，对应的时间复杂度为O(n)。在仅有尾指针的循环单链表中，通过该尾指针可以直接找到第一个结点，所以删除第一个结点的时间复杂度为O(1)；在尾结点之后插入一个结点也就是在尾指针所指结点之后插入一个结点，时间复杂度也为O(1)。因此最节省运算时间。4. 算法设计题（1）设计一个高效算法，将顺序表的所有元素逆置，要求算法空间复杂度为O(1)。解：遍历顺序表L的前半部分元素，对于元素L.datai（0iL.length/2），将其与后半部分对应元素L.d

16、ataL.length-i-1进行交换。对应的算法如下：void reverse(SqList &L)int i;ElemType x;for (i=0;iL.length/2;i+)x=L.datai;/L.datai与L.dataL.length-i-1交换L.datai=L.dataL.length-i-1;L.dataL.length-i-1=x;本算法的时间复杂度为O(n)。（2）设计一个算法从顺序表中删除重复的元素，并使剩余元素间的相对次序保持不变。解：对于顺序表L，用i从1开始遍历其元素，设L.data0.j（j的初值为0）中没有重复的元素。检测L.datai（jiL.lengt

17、h），若L.datai和L.data0.j中任何一个元素都不相同，则将L.datai存入L.dataj+1中。对应的算法如下：void delsame(SqList &L)/L为引用型参数int i,j=0,k;for (i=1;iL.length;i+)k=0;while (kj)/表示L.datai和L.data0.j中所有元素都不相同j+;L.dataj=L.datai;L.length=j+1;/顺序表长度置新值本算法的时间复杂度为O(n2)，空间复杂度为O(1)。（3）设计一个算法从有序顺序表中删除重复的元素，并使剩余元素间的相对次序保持不变。解：在有序顺序表L中，所有重复的元素应是

18、相邻存放的，用k保存不重复出现的元素个数，先将不重复的有序区看成是L.data0.0，置e=L.data0，用i从1开始遍历L的所有元素：当L.dataie时，将它放在L.datak中，k增1，置e=L.datai，最后将L的length置为k。对应的算法如下：void delsame1(SqList &L)/L为引用型参数int i,k=1;/k保存不重复的元素个数ElemType e;e=L.data0;for (i=1;inext;/p指向*q的前驱结点while (q!=NULL & q-data!=x)p=q;q=q-next;if (q!=NULL)/找到值为x的结点p-next=

19、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 re

20、turn 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链表的

21、尾结点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 inorderL

22、ist(SLink *&L,ElemType x)SLink *s,*p,*q;s=(SLink *)malloc(sizeof(SLink); /建立一个待插入的结点s-data=x;s-next=NULL;if (L=NULL | xdata)/若单链表为空或x小于第1个结点date域s-next=L;/把*s结点插入到头结点之后L=s;elseq=L;/寻找插入位置,p指向待比较的结点,q指向p的前驱结点p=q-next;while (p!=NULL & xp-data)/若x小于p所指结点的data域值if (xp-data) q=p;p=p-next;s-next=p;/将s结点插入

23、到*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

24、;elseq=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结点f

25、ree(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的结点*pq=p-next;/q指

26、向*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（n1）个数据结点的循环单链表L，设计一个算法将所有结点逆置。解：采用头插法重建循环单链表L的思路，先建立一个空的循环单链表，用p遍历所有数据结点，每次将*p结点插入到前端。对应的算法如下：voi

27、d 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 #include SLink.hvoid Union(SLink *L1,SLink *L2,SLink *&L3)/求并集SLink *p,*q,*s,*tc;L3=(SLink *)malloc(sizeof(SLink);

28、tc=L3;p=L1-next;q=L2-next;while (p!=NULL & q!=NULL)if (p-datadata)s=(SLink *)malloc(sizeof(SLink);s-data=p-data;tc-next=s;tc=s;p=p-next;else if (p-dataq-data)s=(SLink *)malloc(sizeof(SLink);s-data=q-data;tc-next=s;tc=s;q=q-next;elses=(SLink *)malloc(sizeof(SLink);s-data=p-data;tc-next=s;tc=s;p=p-nex

29、t;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);t

30、c=L3;p=L1-next;q=L2-next;while (p!=NULL & q!=NULL)if (p-datadata)p=p-next;else if (p-dataq-data)q=q-next;else/p-data=q-datas=(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(si

31、zeof(SLink);tc=L3;p=L1-next;q=L2-next;while (p!=NULL & q!=NULL)if (p-datadata)s=(SLink *)malloc(sizeof(SLink);s-data=p-data;tc-next=s;tc=s;p=p-next;else if (p-dataq-data)q=q-next;else/p-data=q-datap=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;

32、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并集Cn);Union(A,B,C);/求A、B并集Cprintf(集合C:);DispList(C);printf(求A、B交集Cn);InterSection(A,B,D);/

33、求A、B并集Dprintf(集合D:);DispList(D);printf(求A、B差集En);Subs(A,B,E);/求A、B差集Eprintf(集合E:);DispList(E);DestroyList(A);DestroyList(B);DestroyList(C);DestroyList(D);DestroyList(E);练习题31. 单项选择题（1）栈中元素的进出原则是（ ）。A.先进先出B.后进先出C.栈空则进D.栈满则出答：B（2）设一个栈的进栈序列是A、B、C、D（即元素AD依次通过该栈），则借助该栈所得到的输出序列不可能是（ ）。A.A,B,C,DB.D,C,B,AC.

34、A,C,D,BD.D,A,B,C答：D（3）一个栈的进栈序列是a、b、c、d、e，则栈的不可能的输出序列是（ ）。A.edcbaB.decbaC.dceabD.abcde答：C（4）已知一个栈的进栈序列是1，2，3，n，其输出序列的第一个元素是i（1in）则第j（1jn）个出栈元素是（ ）。A.iB.n-iC.j-i+1D.不确定答：D（5）设顺序栈st的栈顶指针top的初始时为-1，栈空间大小为MaxSize，则判定st栈为栈空的条件为（ ）。A.st.top=-1B.st.top!=-1C.st.top!=MaxSize D.st.top=MaxSize答：A（6）设顺序栈st的栈顶指针t

35、op的初始时为-1，栈空间大小为MaxSize，则判定st栈为栈满的条件是 。A.st.top!=-1B.st.top=-1C.st.top!=MaxSize-1D.st.top=MaxSize-1答：D（7）队列中元素的进出原则是（ ）。A.先进先出B.后进先出C.栈空则进D.栈满则出答：A（8）元素A、B、C、D顺序连续进入队列qu后，队头元素是（ ），队尾元素是（ ）。A.AB.BC.CD.D答：A D。（9）一个队列的入列序列为1234，则队列可能的输出序列是（ ）。A.4321B.1234C.1432D.3241答：B（10）循环队列qu（队头指针front指向队首元素的前一位置，队

36、尾指针rear指向队尾元素的位置）的队满条件是（ ）。A. (qu.rear+1)%MaxSize=(qu.front+1)%MaxSizeB. (qu.rear+1)%MaxSize=qu.front+1C.(qu.rear+1)%MaxSize=qu.frontA.qu.rear=qu.front答：C（11）循环队列qu（队头指针front指向队首元素的前一位置，队尾指针rear指向队尾元素的位置）的队空条件是（ ）。A. (qu.rear+1)%MaxSize=(qu.front+1)%MaxSizeB. (qu.rear+1)%MaxSize=qu.front+1C.(qu.rear

37、+1)%MaxSize=qu.frontD.qu.rear=qu.front答：D（12）设循环队列中数组的下标是0N-1，其头尾指针分别为f和r（队头指针f指向队首元素的前一位置，队尾指针r指向队尾元素的位置），则其元素个数为（ ）。A.r-fB.r-f-1C.(r-f)N+1D.(r-f+N)N答：D（13）设有4个数据元素a、b、c和d，对其分别进行栈操作或队操作。在进栈或进队操作时，按a、b、c、d次序每次进入一个元素。假设栈或队的初始状态都是空。现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是（ ），第二次出栈得到的元素是（ ）；类似地，考虑对

38、这4个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是（ ），第二次出队得到的元素是（ ）。经操作后，最后在栈中或队中的元素还有（ ）个。：A.aB.bC.cD.d：A.1B.2C.3D.0答：B D A B B（14）设栈S和队列Q的初始状态为空，元素e1e6依次通过栈S，一个元素出后即进队列Q，若6个元素出队的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（ ）。A.5B.4C.3D.2答：C2. 填空题（1）栈是一种特殊的线性表，允许插入和删除运算的一端称为（ ）。不允许插入和删除运算的一端称为（ ）。答：栈顶 栈底（2）一个

39、栈的输入序列是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）顺序栈用data0.n-1存储数据，栈顶指针为top，其初始值为0，则元素x进栈的操作是（ ）。答：datatop=x; top+;（5）顺序栈用data0.n-1存储数据，栈顶指针为top，其初始值为0，则出栈元素x的操作是（ ）。答：top-; x=d

40、atatop;（6）（ ）是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。答：队列（7）设有数组A0.m作为循环队列的存储空间，front为队头指针（它指向队首元素的前一位置），rear为队尾指针（它指向队尾元素的位置），则元素x执行入队的操作是（ ）。答：rear=(rear+1)%(m+1); Arear=x;（8）设有数组A0.m作为循环队列的存储空间，front为队头指针（它指向队首元素的前一位置），rear为队尾指针（它指向队尾元素的位置），则元素出队并保存到x中的操作是（ ）。答：front=(front+1)%(m+1); x=Arear;3. 简答题（1）简要说明线性表、栈与队的异同点。答：相同点：都属地线性结构，都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。不同点：运算规则不