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

数据结构简明教程练习题及参考答案练习题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 (jn & sn);答：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=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 void maxs(int a,int n,int &max1,int &max2)int i;max1=max2=a0;for (i=1;imax1)max2=max1;max1=ai;else 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（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（n1）个结点的循环双向链表中，为空的指针域数为（ ）。答：03. 简答题（1）试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？答：顺序存储结构中，相邻数据元素的存放地址也相邻，并要求内存中可用存储单元的地址必须是连续的。其优点是存储密度大，存储空间利用率高；缺点是插入或删除元素时不方便。链式存储结构中，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。其优点是插入或删除元素时很方便，使用灵活；缺点是存储密度小，存储空间利用率低。顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。（2）对于表长为n的顺序表，在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需要移动的元素的平均个数为多少？删除一个元素所需要移动的平均个数为多少？答：插入一个元素所需要移动的元素的平均个数为(n-1)/2，删除一个元素所需要移动的平均个数为n/2。（3）在链表中设置头结点的作用是什么？答：在链表中设置头结点后，不管链表是否为空表，头结点指针均不空，并使得对链表的操作（如插入和删除）在各种情况下统一，从而简化了算法的实现过程。（4）对于双链表和单链表，在两个结点之间插入一个新结点时需修改的指针各为多少个？答：对于双链表，在两个结点之间插入一个新结点时，需修改前驱结点的next域、后继结点的prior域和新插入结点的next、prior域。所以共修改4个指针。对于单链表，在两个结点之间插入一个新结点时，需修改前一结点的next域，新插入结点的next域。所以共修改两个指针。（5）某含有n（n1）结点的线性表中，最常用的操作是在尾结点之后插入一个结点和删除第一个结点，则采用以下哪种存储方式最节省运算时间。单链表；仅有头指针不带头结点的循环单链表；双链表；仅有尾指针的循环单链表。答：在单链表中，删除第一个结点的时间复杂度为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;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.length），若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中，所有重复的元素应是相邻存放的，用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=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 | 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结点插入到*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 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指向*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 #include SLink.hvoid 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-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-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-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(sizeof(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;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.top=-1B.st.top!=-1C.st.top!=MaxSize D.st.top=MaxSize答：A（6）设顺序栈st的栈顶指针top的初始时为-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指向队首元素的前一位置，队尾指针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。用途不同，栈用于子程调用和保护现场等，队列用于多道作业处理、指令寄存及其他运算等等。（2）顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有进队操作，但其实数组中还有空位置，这就叫“假溢出”。采用循环队列是解决假溢出的途径。另外，解决循环队列是空还是满的办法如下： 设置一个布尔变量以区别队满还是队空； 浪费一个元素的空间，用于区别队满还是队空。 使用一个计数器记录队列中元素个数（即队列长度）。通常采用法，让队头指针front指向队首元素的前一位置，队尾指针rear指向队尾元素的位置，这样判断循环队列队空标志是：front=rear，队满标志是：(rear+1)%MaxSize=front。4. 算法设计题（1）假设采用顺序栈存储结构，设计一个算法，利用栈的基本运算返回指定栈中栈底元素，要求仍保持栈中元素不变。这里只能使用栈st的基本运算来完成，不能直接用st.data0来得到栈底元素。解：假定采用顺序栈结构。先退栈st中所有元素，利用一个临时栈tmpst存放从st栈中退栈的元素，最后的一个元素即为所求，然后将临时栈tmpst中的元素逐一出栈并进栈到st中，这样恢复st栈中原来的元素。对应算法如下：int GetBottom(SqStack st,ElemType &x)ElemType e;SqStack tmpst;/定义临时栈InitStack(tmpst);/初始化临时栈if (StackEmpty(st)/空栈返回0return 0;while (!StackEmpty(st)/临时栈tmpst中包含st栈中逆转元素Pop(st,x);Push(tmpst,x);while (!StackEmpty(tmpst)/恢复st栈中原来的内容Pop(tmpst,e);Push(st,e);return 1;/返回1表示成功（2）设计一个算法，采用一个顺序栈逆向输出单链表L中所有元素。解：本题并不需要改变单链表L的结构。设置一个顺序栈st，先遍历单链表并将所有元素进栈，然后栈不空循环并输出栈中所有元素。对应算法如下：void ReverseDisp(SLink *L)ElemType x;struct nodeElemType dataMaxSize;int top; st;/定义一个顺序栈st.top=-1;SLink *p=L-next;while (p!=NULL)/遍历单链表，将所有元素进栈st.top+;st.datast.top=p-data;p=p-next;while (st.top!=-1)/栈不空循环，输出栈中所有元素x=st.datast.top;st.top-;printf(%d ,x);printf(n);（3）设计一个循环队列，用front和rear分别作为队头和队尾指针，另外用一个标志tag标识队列可能空（0）或可能满（1），这样加上front=rear可以作为队空或队满的条件。要求设计队列的相关基本运算算法。解：设计的队列的类型如下：typedef struct ElemType dataMaxSize;int front,rear;/队头和队尾指针int tag;/为0表示队空,为1时表示不空 QueueType;初始时tag=0，进行成功的插入操作后tag=1，进行成功的删除操作后tag=0；因为只有在插入操作后队列才有可能满，只有在删除操作后队列才有可能空，因此，这样的队列的基本要素如下：初始时：tag=0，front=rear队空条件：qu.front=qu.rear & qu.tag=0队满条件：qu.front=qu.rear & qu.tag=1对应的算法如下：/-初始化队列算法-void InitQueue1(QueueType &qu)qu.front=qu.rear=0;qu.tag=0;/为0表示队空可能为空/-判队空算法-int QueueEmpty1(QueueType qu)return(qu.front=qu.rear & qu.tag=0);/-判队满算法-int QueueFull1(QueueType qu) return(qu.tag=1 & qu.front=qu.rear);/-进队算法-int enQueue1(QueueType &qu,ElemType x)if (QueueFull1(qu)=1)/队满return 0;qu.rear=(qu.rear+1)%MaxSize;qu.dataqu.rear=x;qu.tag=1;/至少有一个元素,可能满return 1;/-出队算法-int deQueue1(QueueType &qu,ElemType &x)/出队if (QueueEmpty1(qu)=1)/队空return 0;qu.front=(qu.front+1)%MaxSize;x=qu.dataqu.front;qu.tag=0;/出队一个元素,可能空return 1;（4）假设用一个循环单链表表示队列，并且只设一个指针rear指向队尾结点，但不设头指针，设计出相应的队初始化、进队、出队和判队空的算法。解：假设链队是不带头结点的循环单链表，其示意图如图3.1所示。队空