数据结构课程课后习题复习资料.docx

数据构造简明教程练习题及参考答案练习题11. 单项选择题（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.易读性、稳定性和平安性答：B2. 填空题（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-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 (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的取值范围，所以in/2，则，该程序段的时间困难度为O(n2)。上机试验题1有一个整型数组a，其中含有n个元素，设计尽可能好的算法求其中的最大元素和次大元素，并采纳相关数据测试。解：maxs算法用于返回数组a0.n-1中的最大元素值max1和次大元素值max2，max1和max2设计为引用类型。对应的程序如下：#include <stdio.h>void maxs(int a,int n,int &max1,int &max2)int i;max1=max2=a0;for (i=1;i<n;i+)if (ai>max1)max2=max1;max1=ai;else if (ai>max2)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（1in）个结点后插入一个新结点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.连续或不连续都可以答：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）在依次表中访问随意一个元素的时间困难度均为（ ），因此依次表也称为（ ）的数据构造。答：O(1) 随机存取（5）依次表中逻辑上相邻的元素的物理位置（ ）相邻。单链表中逻辑上相邻的元素的物理位置（ ）相邻。答：肯定 不肯定（6）在带头结点的单链表中，除头结点外，任一结点的存储位置由（ ）指示。答：其前驱结点的链域的值（7）在含有n个数据结点的单链表中要删除已知结点*p，需找到它的（ ），其时间困难度为（ ）。答：前驱结点的地址 O(n)（8）含有n（n>1）个结点的循环双向链表中，为空的指针域数为（ ）。答：03. 简答题（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.datai（0iL.length/2），将其及后半局部对应元素L.dataL.length-i-1进展交换。对应的算法如下：void reverse(SqList &L)int i;ElemType x;for (i=0;i<L.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（j<i<L.length），若L.datai和L.data0.j中任何一个元素都不一样，则将L.datai存入L.dataj+1中。对应的算法如下：void delsame(SqList &L)/L为引用型参数int i,j=0,k;for (i=1;i<L.length;i+)k=0;while (k<=j && L.datak!=L.datai)k+;if (k>j)/表示L.datai和L.data0.j中全部元素都不一样j+;L.dataj=L.datai;L.length=j+1;/依次表长度置新值本算法的时间困难度为O(n2)，空间困难度为O(1)。（3）设计一个算法从有序依次表中删除重复的元素，并使剩余元素间的相对次序保持不变。解：在有序依次表L中，全部重复的元素应是相邻存放的，用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;i<L.length;i+)if (L.datai!=e)/只保存不重复的元素L.datak=L.datai;k+;e=L.datai;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;elseq=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;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结点free(q);else p=p->next;本算法的时间困难度为O(n)。（10）有一个双链表L，设计一个算法查找第一个元素值为x的结点，将其及后继结点进展交换。解：先找到第一个元素值为x的结点*p，q指向其后继结点，本题是将*p结点移到*q结点之后，实现过程是：删除*p结点，再将其插入到*q结点之后。对应的算法如下：int s *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指向*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结点插入到前端。对应的算法如下：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;elses=(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->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(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->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;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);/求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.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=-1B.st!=-1C.st!=MaxSize D.st=MaxSize答：A（6）设依次栈st的栈顶指针top的初始时为-1，栈空间大小为MaxSize，则断定st栈为栈满的条件是 。A.st!=-1B.st=-1C.st!=MaxSize-1D.st=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指向队首元素的前一位置，队尾指针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+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次序每次进入一个元素。假设栈或队的初始状态都是空。现要进展的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是（ ），第二次出栈得到的元素是（ ）；类似地，考虑对这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）一个栈的输入序列是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=datatop;（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）简要说明线性表、栈及队的异同点。答：一样点：都属地线性构造，都可以用依次存储或链表存储；栈和队列是两种特别的线性表，即受限的线性表，只是对插入、删除运算加以限制。不同点：运算规则不同，线性表为随机存取，而栈是只允许在一端进展插入、删除运算，因此是后进先出表LIFO；队列是只允许在一端进展插入、另一端进展删除运算，因此是先进先出表FIFO。用处不同，栈用于子程调用和爱护现