《数据结构课程课后习题答案.pdf》由会员分享，可在线阅读，更多相关《数据结构课程课后习题答案.pdf（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、练习题 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.求解问题的有限运算序列
2、 D.调度方法 答：C（6）计算机算法必须具备输入、输出和（）等 5个特性。A.可行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 答：B 2.填空题（1）数据结构包括数据的、数据的和数据的这三个方面的内容。答：逻辑结构存储结构运算（2）数据结构按逻辑结构可分为两大类，它们分别是和。答：线性结构非线性结构（3）数据结构被形式地定义为（D,R），其中 D是的有限集合，R是 D上的有限集合。答：数据元素关系（4）在线性结构中，第一个结点前驱结点，其余每个结点有且只有 1 个前驱结点；最后一个结点后继结点，其余每个结点有且只有 1个后继结点
3、。答：没有没有（5）在树形结构中，树根结点没有结点，其余每个结点有且只有个前驱结点；叶子结点没有结点，其余每个结点的后继结点数可以是。答：前驱1后继任意多个（6）在图形结构中，每个结点的前驱结点数和后继结点数可以是（）。答：任意多个（7）数据的存储结构主要有四种，它们分别是、和存储结构。答：顺序链式索引哈希（8）一个算法的效率可分为效率和效率。答：时间空间 3.简答题（1）数据结构和数据类型两个概念之间有区别吗？答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素的集合。数据类型不仅定义了一组数据元素，而且还在其上定义了一组操作。（2）简述线性结构、树形结构和图形结构的不同点。答：线
4、性结构反映结点间的逻辑关系是一对一的，树形线性结构反映结点间的逻辑关系是一对多的，图在结构反映结点间的逻辑关系是多对多的。（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-1000lo
5、g2n T2(n)=3log2n-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(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）执行下面的
6、语句时，语句 s+的执行次数为多少？int s=0;for(i=1;i=i;j-)s+;答：语句s的执行次数2)2)(3(3)1()1(12121nnnninniniinj。（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+语句属基本运算语句，ninijninninnT1112)1()(1)(=O(n2)。（8）设 n 为问题规模，是一个正偶数，试计算以下算法结束时 m 的值，并给出该算法的时间复杂度。void fun2(int n)int m=0;for(i=
7、1;i=n;i+)for(j=2*i;j=n;j+)m+;3log2n 答：由于内循环j的取值范围，所以in/2，则 2/122/124/)12(ninijnininm，该程序段的时间复杂度为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(
8、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);练习题 2 1.单项选择题（1）数据在计算机存储器内表示时，物理地址与逻辑地址相对顺序相同并且是连续的，称之为（）。A.存储结构 B.逻辑结构 C.顺序存储结构 D.链式存储结构 答：C（2）在 n 个结点的顺序表中，算法的时间复杂度是 O（1）的操作是（）。A
9、.访问第 i个结点（1in）和求第 i（2in）个结点的前驱结点 B.在第 i（1in）个结点后插入一个新结点 C.删除第 i个结点（1in）D.将 n个结点从小到大排序 答：A（3）向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。A.8B.C.63D.7 答：B（4）链式存储结构所占存储空间（）。A.分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B.只有一部分，存放结点值 C.只有一部分，存储表示结点间关系的指针 D.分两部分，一部分存放结点值，另一部分存放结点所占单元数 答：A（5）线性表若采用链式存储结构时，要求内存中可用存储单元
10、的地址（）。A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续或不连续都可以 答：D（6）一个线性表在（）情况下适用于采用链式存储结构。A.需经常修改其中的结点值 B.需不断对其进行删除插入 C.其中含有大量的结点 D.其中结点结构复杂 答：B（7）单链表的存储密度（）A.大于 1B.等于 1C.小于 1D.不能确定 答：C 2.填空题（1）在顺序表中插入或删除一个元素时，需要平均移动（）元素，具体移动的元素个数与（）有关。答：表中一半表长和该元素在表中的位置（2）向一个长度为 n 的顺序表的第 i个元素（1in+1）之前插入一个元素时，需向后移动（）个元素。答：n-i+
11、1（3）向一个长度为 n 的顺序表中删除第 i个元素（1in）时，需向前移动（）个元素。答：n-i（4）在顺序表中访问任意一个元素的时间复杂度均为（），因此顺序表也称为（）的数据结构。答：O(1)随机存取（5）顺序表中逻辑上相邻的元素的物理位置（）相邻。单链表中逻辑上相邻的元素的物理位置（）相邻。答：一定不一定（6）在带头结点的单链表中，除头结点外，任一结点的存储位置由（）指示。答：其前驱结点的链域的值（7）在含有 n 个数据结点的单链表中要删除已知结点*p，需找到它的（），其时间复杂度为（）。答：前驱结点的地址O(n)（8）含有 n（n1）个结点的循环双向链表中，为空的指针域数为（）。答：0
12、 3.简答题（1）试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？答：顺序存储结构中，相邻数据元素的存放地址也相邻，并要求内存中可用存储单元的地址必须是连续的。其优点是存储密度大，存储空间利用率高；缺点是插入或删除元素时不方便。链式存储结构中，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。其优点是插入或删除元素时很方便，使用灵活；缺点是存储密度小，存储空间利用率低。顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且
13、其主要操作是插入、删除操作，则采用链表。（2）对于表长为n的顺序表，在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需要移动的元素的平均个数为多少？删除一个元素所需要移动的平均个数为多少？答：插入一个元素所需要移动的元素的平均个数为(n-1)/2，删除一个元素所需要移动的平均个数为n/2。（3）在链表中设置头结点的作用是什么？答：在链表中设置头结点后，不管链表是否为空表，头结点指针均不空，并使得对链表的操作（如插入和删除）在各种情况下统一，从而简化了算法的实现过程。（4）对于双链表和单链表，在两个结点之间插入一个新结点时需修改的指针各为多少个？答：对于双链表，在两个结点之间插入一个新
14、结点时，需修改前驱结点的next域、后继结点的prior域和新插入结点的next、prior域。所以共修改4个指针。对于单链表，在两个结点之间插入一个新结点时，需修改前一结点的next域，新插入结点的next域。所以共修改两个指针。（5）某含有n（n1）结点的线性表中，最常用的操作是在尾结点之后插入一个结点和删除第一个结点，则采用以下哪种存储方式最节省运算时间。单链表；仅有头指针不带头结点的循环单链表；双链表；仅有尾指针的循环单链表。答：在单链表中，删除第一个结点的时间复杂度为O(1)。插入结点需找到前驱结点，所以在尾结点之后插入一个结点，需找到尾结点，对应的时间复杂度为O(n)。在仅有头指针
15、不带头结点的循环单链表中，删除第一个结点的时间复杂度O(n)，因为删除第一个结点后还要将其改为循环单链表；在尾结点之后插入一个结点的时间复杂度也为O(n)。在双链表中，删除第一个结点的时间复杂度为O(1)；在尾结点之后插入一个结点，也需找到尾结点，对应的时间复杂度为O(n)。在仅有尾指针的循环单链表中，通过该尾指针可以直接找到第一个结点，所以删除第一个结点的时间复杂度为O(1)；在尾结点之后插入一个结点也就是在尾指针所指结点之后插入一个结点，时间复杂度也为O(1)。因此最节省运算时间。4.算法设计题（1）设计一个高效算法，将顺序表的所有元素逆置，要求算法空间复杂度为 O(1)。解：遍历顺序表
16、L的前半部分元素，对于元素 L.datai（0i-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）中没有重复的元素。检
17、测 L.datai（ji），若 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）设计一个算法从有序顺序表中删除重复的元素，并使剩余元素间的相对次序保持不变。解：在
18、有序顺序表 L中，所有重复的元素应是相邻存放的，用 k保存不重复出现的元素个数，先将不重复的有序区看成是 L.data0.0，置 e=L.data0，用 i从 1 开始遍历 L的所有元素：当ie时，将它放在 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
19、!=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=
20、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*)mall
21、oc(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的结点，使插入后该链表仍然有序。解：先建立一个待插入的结点，然后依次与链表中的各结点的数
22、据域比较大小，找到插入该结点的位置，最后插入该结点。对应的算法如下：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;else q=L;/寻找插入位置,p指向待比较的结点,q指向p的前驱结点 p=q-next;while(p!=NULL&xp-data)/若x小于p所指结点的data域值
23、 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-dat
24、a=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)/找到重复值的
25、结点 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
26、=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（n1）个数据结点的循环单链表 L，设计一个算法将所有结点逆置。解：采用头
27、插法重建循环单链表 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.h void Union(SLink*L1,SLink*L2,SL
28、ink*&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;else s=(SLink*)m
29、alloc(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)/求交集 SLi
30、nk*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-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)/求差集
31、 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-data p=p-next;q=q-next;while(p!=NULL)s=(SLink*)malloc(sizeof(SLink);s-data
32、=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并集C printf(集合C:);DispList(C);prin
33、tf(求A、B交集Cn);InterSection(A,B,D);/求A、B并集D printf(集合D:);DispList(D);printf(求A、B差集En);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（即元素 AD依次通过该栈）
34、，则借助该栈所得到的输出序列不可能是（）。A.A,B,C,D B.D,C,B,AC.A,C,D,B D.D,A,B,C 答：D（3）一个栈的进栈序列是 a、b、c、d、e，则栈的不可能的输出序列是（）。A.edcba B.decba C.dceab 答：C（4）已知一个栈的进栈序列是 1，2，3，n，其输出序列的第一个元素是 i（1in）则第 j（1jn）个出栈元素是（）。A.i B.n-iC.j-i+1D.不确定 答：D（5）设顺序栈 st的栈顶指针 top的初始时为-1，栈空间大小为 MaxSize，则判定 st栈为栈空的条件为（）。A=-1 B.st.top!=-1 C.st.top!=
35、MaxSize=MaxSize 答：A（6）设顺序栈 st的栈顶指针 top的初始时为-1，栈空间大小为 MaxSize，则判定 st栈为栈满的条件是。op!=-1op=-1 op!=MaxSize-1op=MaxSize-1 答：D（7）队列中元素的进出原则是（）。A.先进先出 B.后进先出 C.栈空则进 D.栈满则出 答：A（8）元素 A、B、C、D顺序连续进入队列 qu后，队头元素是（），队尾元素是（）。答：A D。（9）一个队列的入列序列为 1234，则队列可能的输出序列是（）。答：B（10）循环队列 qu（队头指针 front指向队首元素的前一位置，队尾指针 rear指向队尾元素的位
36、置）的队满条件是（）。A.(qu.rear+1)%MaxSize=(qu.front+1)%MaxSize B.(qu.rear+1)%MaxSize=qu.front+1 答：C（11）循环队列 qu（队头指针 front指向队首元素的前一位置，队尾指针 rear指向队尾元素的位置）的队空条件是（）。A.(qu.rear+1)%MaxSize=(qu.front+1)%MaxSize B.(qu.rear+1)%MaxSize=qu.front+1 D 答：D（12）设循环队列中数组的下标是 0N-1，其头尾指针分别为 f和 r（队头指针 f指向队首元素的前一位置，队尾指针 r指向队尾元素的
37、位置），则其元素个数为（）。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
38、 C.c D.d：A.1 B.2 C.3 D.0 答：B D A B B（14）设栈 S和队列 Q的初始状态为空，元素 e1e6依次通过栈 S，一个元素出后即进队列 Q，若 6 个元素出队的序列是 e2、e4、e3、e6、e5、e1，则栈 S的容量至少应该是（）。答：C 2.填空题（1）栈是一种特殊的线性表，允许插入和删除运算的一端称为（）。不允许插入和删除运算的一端称为（）。答：栈顶栈底（2）一个栈的输入序列是 12345，的输出序列为 12345，其进栈出栈的操作为（）。答：1 进栈，1 出栈，2进栈，2 出栈，3 进栈，3出栈，4 进栈，4 出栈，5进栈，5 出栈。（3）有 5 个元素，
39、其进栈次序为 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
40、为队头指针（它指向队首元素的前一位置），rear 为队尾指针（它指向队尾元素的位置），则元素 x 执行入队的操作是（）。答：rear=(rear+1)%(m+1);Arear=x;（8）设有数组 A0.m作为循环队列的存储空间，front为队头指针（它指向队首元素的前一位置），rear 为队尾指针（它指向队尾元素的位置），则元素出队并保存到 x中的操作是（）。答：front=(front+1)%(m+1);x=Arear;3.简答题（1）简要说明线性表、栈与队的异同点。答：相同点：都属地线性结构，都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限
41、制。不同点：运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表 FIFO。用途不同，栈用于子程调用和保护现场等，队列用于多道作业处理、指令寄存及其他运算等等。（2）顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有进队操作，但其实数组中还有空位置，这就叫“假溢出”。采用循环队列是解决假溢出的途径。另外，解决循环队列是空还是满的办法如下：设置一个布尔变量以区别队满还是队空；浪费一个元素的空间，用于区别队满还是队空。使用一
42、个计数器记录队列中元素个数（即队列长度）。通常采用法，让队头指针 front指向队首元素的前一位置，队尾指针 rear 指向队尾元素的位置，这样判断循环队列队空标志是：front=rear，队满标志是：(rear+1)%MaxSize=front。4.算法设计题（1）假设采用顺序栈存储结构，设计一个算法，利用栈的基本运算返回指定栈中栈底元素，要求仍保持栈中元素不变。这里只能使用栈 st的基本运算来完成，不能直接用 st.data0来得到栈底元素。解：假定采用顺序栈结构。先退栈 st中所有元素，利用一个临时栈 tmpst存放从 st栈中退栈的元素，最后的一个元素即为所求，然后将临时栈 tmpst
43、中的元素逐一出栈并进栈到 st中，这样恢复 st栈中原来的元素。对应算法如下：int GetBottom(SqStack st,ElemType&x)ElemType e;SqStack tmpst;/定义临时栈 InitStack(tmpst);/初始化临时栈 if(StackEmpty(st)/空栈返回0 return 0;while(!StackEmpty(st)/临时栈tmpst中包含st栈中逆转元素 Pop(st,x);Push(tmpst,x);while(!StackEmpty(tmpst)/恢复st栈中原来的内容 Pop(tmpst,e);Push(st,e);return 1
44、;/返回1表示成功 （2）设计一个算法，采用一个顺序栈逆向输出单链表 L中所有元素。解：本题并不需要改变单链表 L 的结构。设置一个顺序栈 st，先遍历单链表并将所有元素进栈，然后栈不空循环并输出栈中所有元素。对应算法如下：void ReverseDisp(SLink*L)ElemType x;struct node ElemType 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(s
45、t.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
46、，进行成功的插入操作后 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(q
47、u.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(
48、QueueEmpty1(qu)=1)/队空 return 0;qu.front=(qu.front+1)%MaxSize;x=qu.dataqu.front;qu.tag=0;/出队一个元素,可能空 return 1;（4）假设用一个循环单链表表示队列，并且只设一个指针 rear指向队尾结点，但不设头指针，设计出相应的队初始化、进队、出队和判队空的算法。解：假设链队是不带头结点的循环单链表，其示意图如图 3.1 所示。队空条件：rear=NULL；进队操作：在*rear结点之后插入结点并让 rear指向该结点；出队操作：删除*rear结点之后的一个结点。对应的算法如下：a1 a2 an rea
49、r 队尾 队首 图 3.1 不带头结点的循环单链表表示队列 typedef struct node ElemType data;struct node*next;QNode;/链队结点类型/-初始化队列-void InitQueue(QNode*&rear)rear=NULL;/-进队算法-void EnQueue(QNode*&rear,ElemType x)QNode*s;s=(QNode*)malloc(sizeof(QNode);/创建新结点 s-data=x;if(rear=NULL)/原链队为空 s-next=s;/构成循环链表 rear=s;else s-next=rear-ne
50、xt;/将*s结点插入到*rear结点之后 rear-next=s;rear=s;/让rear指向这个新插入的结点 /-出队算法-int DeQueue(QNode*&rear,ElemType&x)QNode*q;if(rear=NULL)/队空 return 0;else if(rear-next=rear)/原队中只有一个结点 x=rear-data;free(rear);rear=NULL;else /原队中有两个或以上的结点 q=rear-next;x=q-data;rear-next=q-next;free(q);return 1;/-判队空算法-int QueueEmpty(QN