数据结构习题册fsdfggs

1、数据结构课后练习题第一章 绪论一、 选择题1、数据结构被形式定义为（D，S），其中D是（ ）的有限集合，S是D上的（ ）有限集合。A、 算法 B、数据元素 C、数据操作 D、逻辑关系 E、操作 F、映象 G、存储 H、关系2、数据结构是一门研究非数值计算的程序设计问题中计算机的（ （1） ）以及它们之间的（ ）和运算的学科。（1）A、操作对象 B、计算方法 C、逻辑存储 D、数据映象（2）A、结构 B、关系 C、运算 D、算法3、算法分析的目的是（ ），算法分析的二个主要方面是（ ）。A、给出数据结构的合理性 B、研究算法中输入输出的关系C、空间复杂性和时间复杂性 D、分析算法的效率以求改进E

2、、正确性和简明性 F、分析算法的易懂性和文档性4、在数据结构中，从逻辑上可以把数据结构分成（ ）。A、 动态和静态结构 B、紧凑接和非紧凑结构C、线性与非线性结构 D、内部结构和外部结构5、计算机算法指的是（ ），它必具备输入、输出和（ ）5个特性。A、计算方法 B、排序方法 C、解决问题的有限运算序列 D、可行性、可移植性和可扩充性 E、可行性、确定性和有穷性6、线性表的顺序存储结构是一种（ ）的存储结构，线性表的链式存储结构是一种（ ）A、随机存取 B、顺序存取 C、索引存取 D、散列存取7、算法的时间复杂度取决于（ ）A、 问题的规模 B、待处理数据的初态 C、问题的规模和待处理数据的初

3、态8、线性表若采用链表存储结构时，要求内存中可用存储单元的地址（ ）A、必须是连续的 B、部分地址必须是连续的C、一定是不连续的 D、连续不连续都可以9、在以下的叙述中，正确的是（ ）A、线性表的线性存储结构优于链式存储结构B、二维数组是它的每个数据元素为一个线性表的线性表C、栈的操作方式是先进先出D、队列的操作方式是先进后出10、根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数据组织形式。以下解释错误的是 ( )A、集合中任何两个结点之间都有逻辑关系但组织形式松散B、线性结构中结点按逻辑关系依次排列形成一条锁链C、树形结构具有分支、层次特性，其形态有点像自然界中的树D

4、、图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接11、以下说法正确的是( )A、数据元素是数据的最小单位B、数据项是数据的基本单位C、数据结构是带有结构的各数据项的集合D、数据结构是带有结构的数据元素的集合二、 填空题1、数据逻辑结构包括（ ）四种类型，树型和图型结构合称（ ）。2、对于给定的n个元素，可以构造出的逻辑结构有（ ）、（ ）、（ ）和（ ）四种。3、算法的五个重要特性是（ ）。4、评价算法的性能从利用计算机资源角度看主要从（ ）方面进行分析。5、线性结构中元素之间存在（ ）关系，树型结构中元素之间存在（ ）关系，图型结构中元素之间存在（ ）关系。6、下面程序段的时

5、间复杂度是（ ）。i=s=0; while(sn) i+;s+;7、下面程序段的时间复杂度是（ ）。s=0; for(I=0;In;I+) for(j=0;jm;j+) s+=aij;8、所谓数据的逻辑结构指的是数据元素之间的 _。9、数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容_。10、在线性结构中，开始结点_直接前驱结点，其余每个结点有且只有_个直接前驱结点。11、在树形结构中，根结点只有_，根结点无前驱，其余每个结点有且只有_直接前驱结点；叶子结点没有_结点，其余每个结点的后继结点可以_。12、在图形结构中，每个结点的前驱结点和后继结点可以有_。13、存储

6、结构是逻辑结构的_实现。14、从数据结构的观点看，通常所说的数据应分成三个不同的层次，即_、_和_。15、根据需要，数据元素又被称为_、_、_或_。16、通常，存储结点之间可以有_、_、_、_四种关联方式，称为四种基本存储方式。17、通常从_、_、_、_等几方面评价算法的(包括程序)的质量。18、一个算法的时空性能是指该算法的_和_，前者是算法包含的_，后者是算法需要的_。19、在一般情况下，一个算法的时间复杂性是_的函数。20、常见时间复杂性的量级有：常数阶O(_)、对数阶O(_)、线性阶O ( _)、平方阶O(_)、和指数阶O(_)。通常认为，具有指数阶量级的算法是_的。21、数据结构的基

7、本任务是数据结构的_和_。22、数据对象是性质相同的 的集合。23、抽象数据类型是指一个 以及定义在该模型上的一组操作。三、判断题1. 数据元素是数据的最小单位。2. 数据结构是带有结构的数据元素的集合。3. 数据结构，数据元素，数据项在计算机中的映象分别称为存储结构，结点，数据域。4. 数据项是数据的基本单位。5. 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。6. 数据的物理结构是数据在计算机中实际的存储形式。7. 算法和程序没有区别，所以在数据结构中二者是通用的。8. 顺序存储结构属于静态结构，链式存储结构属于动态结构。四、计算应用题1、 设n为正正数。确定下列各程

8、序段中前置以记号的语句的频度。（1） I=1;k=0;While(In-1) k+=10*I;I+; k=0;for(I=1;I=n;I+) for(j=I;j=n;j+) k+;(2) I=1;j=0;While(I+jj)j+;else I+;2、指出下列两个算法的时间复杂度。（1） int sum1(int n)int p=1,sum=0,I;for(I=1;I=n;I+)p*=I;sum+=p;return(sum);(2) int sum2(int n) int sum=0,I,j;for(I=1;I=n;I+)p=1;for(j=1;j=I;j+)p*=j;sum+=p;retur

9、m(sum);3、有下列几种用二元组表示的数据结构，画出它们对应的逻辑图形表示，并指出它们属于哪种结构。（1）A=（K，R），其中：K=a,b,c,d,e,f,g,h R=(r) r=, (2) B=(K,R),其中：K=a,b,c,d,e,f,g,h R=(r) r=,(3)C=(K,R),其中：k=1,2,3,4,5,6 R=r r=(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)(4)D=(K.R), K=48,25,64,57,82,36,75,R=r1,r2r1=,r2=,4、设有如图所示的逻辑结构图，给出它的逻辑结构。5、简述下列术语：

10、数据，数据元素，数据结构，数据对象。6、逻辑结构与存储结构是什么关系?7、将数量级，n，n2，n3，nlog2n，log2n，2n，n!，按增长率进行排列。五、算法设计题1. 已知输入x,y,z三个不相等的整数，设计一个算法，使得这三个数按从大到小输出，要求：最佳情况：比较2次，无移动；最差情况：比较3次，7次移动。 第二章 线性表练习题一、 选择题1、表长为N的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（ E ），删除一个元素需要移动的元素个数为（ A ）。A. (N-1)/2 B. N C. N+1 D. N-1 E. N/2 F. (N+1

11、)/2 G. (N-2)/22、线性表是具有N个（ C ）的有限序列。A、表元素 B、字符 C、数据元素 D、数据项 E、信息3、“线性表的逻辑顺序和物理顺序总是一致的。”这个结论是（ B ）。A、正确的 B、错误的 C、不一定，与具体结构有关。4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（ D ）。A、必须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、连续或不连续都可以。5、带头结点的单链表为空的判定条件是（ B ）。 A、head=NULL B、head-next=NULL C、head-next=head D、head!=NULL6、不带头结点的单链表head

12、为空的判定条件是（ A ）。 A、head=NULL B、head-next=NULL C、head-next=head D、head!=NULL7、非空的循环单链表head的尾结点P满足（ C ）。A、P-NEXT=NULL B、p=NULL C、p-next=head D、p=head8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ B ）。A、O(1) B、O(n) C、O(n2) D、O(nlog2n)9、在一个单链表中，若删除P所指结点的后继结点，则执行（A）。、p-next=p-next-next 、p=p-next;p-next=p-next-next

13、 、p-next=p-next; 、p=p-next-next; 10、在一个单链表中，若在所指结点之后插入所指结点，则执行（B）。、s-next=p;p-next=s; 、s-next=p-next;p-next=s; 、s-next=p-next;p=s; 、p-next=s;s-next=p;11、在一个单链表中，已知q是p的前趋结点，若q和p之间插入结点s，则执行（C）。、s-next=p-next;p-next=s; 、p-next=s-next;s-next=p; 、q-next=s;s-next=p;、p-next=s;s-next=q;12、假设双链表结点的类型如下：typed

14、ef struct linknodeint data;数据域struct linknode *llink;指向前趋结点的指针域struct linknode *rlink;指向后继结点的指针域bnode现将一个q所指新结点作为非空双向链表中的p所指结点的前趋结点插入到该双链表中，能正确完成此要求的语句段是（）。、q-rlink=p;q-llink=p-llink;p-llink=q;p-llink-rlink=q;、p-llink=q;q-rlink=p;p-llink-rlink=q;q-llink=p-llink、q-llink=p-rlink;q-rlink=p;p-llink-rlin

15、k=q;p-llink=q;、以上都不对、如上题结点结构，如在此非空循环双向链表的结点p之后插入结点s的操作序列是（）。、p-rlink=s;s-llink=p;p-rlink-llink=s;s-rlink=p-rlink;、p-rlink-s;p-rlink-llink=s;s-llink=p;s-rlink=p-rlink;、s-llink=p;s-rlink=p-rlink;p-rlink=s;p-rlink-llink=s;、s-llink=p;s-rlink=p-rlink;p-rlink-llink=s;p-rlink=s;14、在一个长度为n的单链表上，设有头和尾两个指针，执行

16、（）操作与链表的长度无关。、删除单链表中的第一个元素、删除单链表中最后一个元素、在单链表第一个元素前插入一个新元素、在单链表最后一个元素后插入一个新元素15、线性结构中的一个结点代表一个（ ）A、数据元素 B、数据项 C、数据 D、数据结构16、非空线性表L=(a1,a2,ai,an)，下列说法正确的是（ ）A、每个元素都有一个直接前驱和直接后继B、线性表中至少要有一个元素C、表中诸元素的排列顺序必须是由小到大或由大到小的D、除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继17、顺序表是线性表的（ ）A、链式存储结构 B、顺序存储结构 C、索引存储结构 D、散列存储

17、结构18、对于顺序表，以下说法错误的是（ ）A、顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址 B、顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列C、顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻D、顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中19、对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（ ）为标准操作。A、插入操作 B、结点移动 C、算术表达式 D、删除操作20、对于顺序表的优缺点，以下说法错误的是（ ）A、无需为表示结点间的逻辑关系而增加额外的存储空间B、可以方便地随机存取表中的任一结点C、插入和删除运算较方便

18、D、由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)21、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。A、顺序表 B、单链表 C、双链表 D、单循环链表22、循环链表主要优点是（ ）A、不再需要头指针了B、已知某个结点的位置后，能够容易找到它的直接前趋C、在进行插入、删除运算时，能更好地保证链表不断开D、从表中任一结点出发都能扫描到整个链表23、在线性表的下列存储结构中，读取元素花费时间最少的是（ ）A、单链表 B、双链表 C、循环链表 D、顺序表二、填空题、在线性结构中，第一个结点（）前趋结点，其余每个结点有且只有（）个前趋结

19、点。、在顺序表中插入或删除一个元素，需要平均移动（）元素，具体移动的元素个数与（）有关。、已知是无表头结点的单链表，试从下列提供的答案中选择合适的语句序列，分别实现：（）表首插入结点的语句序列是（）。（）表尾插入结点的语句序列是（）。、-next=S; 、P=L; 、L=S; 、P-next=S-next; 、S-next=P-next; 、S-next=L; 、S-next=NULL; 、while(P-next!=Q)p=p-next; 、while(P-next!=NULL)P=P-next;4、已知L是带表头结点的非空单链表，试从下列提供的答案中选择合适的语句序列。（1）删除首元结点的

20、语句序列是（ ） ,（2）删除尾元结点的语句序列是（ ）A、P=P-next; B、P-next=P-next-next; C、while(P!=NULL)p=p-next; D、while(Q-next!=NULL)P=Q;Q=Q-next; E、while(P-next!=Q)P=P-next;F、Q=P; G、Q=P-next; H、P=L; I、L=L-next; J、free(Q);5、已知L是带表头结点的非空链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 （1）删除P结点的直接后继结点的语句序列是（ ）, （2）删除P结点的直接前趋结点的语句

21、序列是（ ）A、P-next=P-next-next; B、P=P-Pnext-next; C、while(P-next!=Q)P=P-next;D、while(P-next-next!=Q)P=P-next; E、Q=P; F、Q=P-next; G、P=L;H、L=L-next; I、free(Q);6、已知结点编号，在各结点查找概率相等的情况下，从n个结点的单链表中查找一个结点，平均要访问（ ）个结点，从n个结点的双链表中查找一个结点，平均要访问（ ）个结点。7、对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是（ ）；在值域为给定值的结点后插入一个新结点的时间

22、复杂度是（ ）。8、单链表是（ ）的链接存储表示。9、单链表中设置头结点的作用是（ ）。10、在单链表中，除首元结点外，任一结点的存储位置由（ ）指示。11、在非空双向循环链表中，在结点q的前面插入结点p的过程如下： p-prior=q-prior; q-prior-next=p;p-next=q;( );12、在双向链表中，每个结点有两个指针域，一个指向（ ），另一个指向（ ）。13、顺序表中逻辑上相邻的元素的物理位置（ ）相邻。单链表中逻辑上相邻的元素的物理位置（ ）相邻。 14、为了便于讨论，有时将含n(n0)个结点的线性结构表示成(a1，a2,an)，其中每个ai代表一个_。a1称为_

23、结点，an称为_结点，i称为ai在线性表中的_。对任意一对相邻结点ai、ai1(1in),ai称为ai1的直接_，ai1称为ai的直接_。15、线性结构的基本特征是：若至少含有一个结点，则除起始结点没有直接_外，其他结点有且仅有一个直接_；除终端结点没有直接_外，其它结点有且仅有一个直接_.16、所有结点按1对1的邻接关系构成的整体就是_结构。17、线性表的逻辑结构是_结构。其所含结点的个数称为线性表的_。18、在单链表中，指针p所指结点为最后一个结点的条件是_。三、判断题1. 顺序存储的线性表可以随机存取。2. 顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半

24、的元素需要移动。3. 线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。4. 在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。5. 在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。6. 在单链表中，可以从头结点进行查找任何一个元素。7. 线性表的链式存储结构优于顺序存储结构。8. 在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。9. 在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。10. 顺序存储方式只能用于存储线性结构。四、简答题1、 若

25、较频繁地对一个线性表进行插入和删除操作，该线性表宜采用哪种存储结构？为什么？2、 描述概念：头指针、头结点、首元结点的区别？3、 设A是一个线性表（a1a2an），采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为多少？若元素插在ai与ai+1之间（0=Inext)q=L ; L=L-next; p=L;while(p-next) p=p-next;p-next=q; q-next=NULL;return L;7、如果有n个线性表同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度也会自动地改变。在此情况下，应选择哪一种存储结构。为什么？8、若线性表的总

26、数基本稳定，且很少进行插入删除操作，但要求以最快的方式存取线性表的元素，应该用哪种存储结构。为什么？9、设有多项式a(x)=9+8x+9x4+5x10b(x)=-2x+22x7-5x10（1） 用单链表给出a(x)、b(x)的存储表示；（2） 设c (x)=a(x)+b(x)，求得c(x)并用单链表给出其存储表示。五、设计题1、编写一个函数将一个顺序表A（有多个元素且任何元素不为0）分拆成两个顺序表，使A中大于0的元素存放在B中，小于0的元素存放在C中。2、设顺序表L中的数据元素递增有序。试写一算法，将e插入到顺序表的适当位置，插入后保持该表的有序性。3、A、B为元素递增有序排列的单链表（同一

27、表中可能有相同元素），编写算法另建一单链表C，保存两个表的公共元素，要求C的元素值各不相同且递增有序。4、设有一个由正整数组成的无序单链表，编写算法实现下列功能：（1） 找出最小值结点，且显示该数值。（2） 若该数值为奇数，则将其与直接后继结点的数值交换。（3） 若为偶数，则将其直接后继结点删除。 六、编程附加题1. 试分别用顺序表和单链表作为存储结构，实现将线性表（a0,a1,a2,.an-1）就地逆置的操作，所谓“就地”指辅助空间为O（1）。2. 设单链表L是一个非递减有序表，试写一个算法将x插入其中后仍保持L的有序性。3. 设A、B是两个线性表，其表中元素递增有序，长度分别为m和n。试写

28、一算法分别以顺序存储和链式存储将A和B归并成一个仍按元素值递增有序的线性表C，请分析算法的时间复杂度。4. 单链表L是一个递减有序表，试写一高效算法，删除表中值大于mink且小于maxk的结点（若表中有这样的结点），同时释放被删结点空间，这里mink和maxk是两个给定的参数, 它们可以和表中元素相同，也可以不同。5. 假设以两个元素依值递增有序排列的线性表A,B分别表示两个集合，先要求另辟空间构造一个线性表C,其元素为两集合的交集，且表C中的元素也依值递增有序排列。是对顺序表编写求C的算法。6. 假设在长度大于1的单循环链表中，既无头结点也无头指针。S为指向链表中某个结点的指针，试编写算法删

29、除结点*s 的直接前驱结点。7. 计算带头结点的单循环链表的结点个数。8. 给定一个不带头结点的单链表，编写计算此链表长度的算法第三章栈与队列 练习题一、 选择题1、栈结构通常采用的两种存储结构是（ ）。A、顺序存储结构和链表存储结构 B、散列和索引方式 C、链表存储结构和数组 D、线性链表结构和非线性存储结构2、设栈ST用顺序存储结构表示，则栈ST为空的条件是（ ）A、ST.top-ST.base0 B、ST.top-ST.base=0 C、ST.top-ST.basen D、ST.top-ST.base=n3、向一个栈顶指针为HS的链栈中插入一个s结点时，则执行（ ）A、HS-next=s

30、; B、s-next=HS-next;HS-next=s; C、s-next=HS;HS=s; D、s-next=HS;HS=HS-next;4、从一个栈顶指针为HS的链栈中删除一个结点，用x保存被删除结点的值，则执行（ ）A、x=HS;HS=HS-next; B、HS=HS-next;x=HS-data; C、x=HS-data;HS=HS-next; D、s-next=Hs;Hs=HS-next;5、表达式a*(b+c)-d的后缀表达式为（ ）A、abcdd+- B、abc+*d- C、abc*+d- D、-+*abcd6、中缀表达式A-（B+C/D）*E的后缀形式是（ ）A、AB-C+D

31、/E* B、ABC+D/E* C、ABCD/E*+- D、ABCD/+E*-7、一个队列的入列序列是1，2，3，4， 则队列的输出序列是（ ）A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，18、循环队列SQ采用数组空间SQ.base0,n-1存放其元素值，已知其头尾指针分别是front和rear，则判定此循环队列为空的条件是（ ）A、Q.rear-Q.front=n B、Q.rear-Q.front-1=n C、Q.front=Q.rear D、Q.front=Q.rear+19、循环队列SQ采用数组空间SQ.base0,n-1存放其元素值，已知其头尾指针分别是f

32、ront和rear，则判定此循环队列为满的条件是（ ）A、Q.front=Q.rear B、Q.front!=Q.rear C、Q.front=(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n10、若在一个大小为6的数组上实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（ ）A、1，5 B、2, 4 C、4，2 D、5，111、用单链表表示的链式队列的队头在链表的（ ）位置A、链头 B、链尾 C、链中12、判定一个链队列Q（最多元素为n个）为空的条件是（ ）A、Q.front=Q.rear

33、 B、Q.front!=Q.rear C、Q.front=(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n13、在链队列Q中，插入s所指结点需顺序执行的指令是（ ）A、Q.front-next=s;f=s; B、Q.rear-next=s;Q.rear=s; C、s-next=Q.rear;Q.rear=s; D、s-next=Q.front;Q.front=s;14、在一个链队列Q中，删除一个结点需要执行的指令是（ ）A、Q.rear=Q.front-next; B、Q.rear-next=Q.rear-next-next; C、Q.front-next=Q.fron

34、t-next-next; D、Q.front=Q.rear-next;15、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（ ）A、仅修改队头指针 B、仅修改队尾指针 C、队头尾指针都要修改 D、队头尾指针都可能要修改。16、栈和队列的共同点是（ ）A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点17、消除递归（ ）需要使用栈。A、一定 B、不一定18、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1，则栈的容量至少应该是（ ）A、2 B

35、、 3 C、 5 D、 6 19、若一个栈的输入序列是a,b,c，则通过入、出栈操作可能得到a,b,c的不同排列个数为（ ）A、 4 B、 5 C、 6 D、 7 20、设有一顺序栈已经含有3个元素，如图3.1所示元素a4正等待进栈。下列不可能出现的出栈序列是（ ）0 maxsize-1A、a3,a1,a4,a2 B、 a3,a2,a4,a1 C、 a3,a4,a2,a1 D、 a4,a3,a2,a1 a1a2Topa3 图3.121、链栈和顺序栈相比，有一个比较明显的优势是（ ）A、通常不会出现栈满的情况 B、 通常不会出现栈空的情况 C、 插入操作更容易实现 D、 删除操作更加容易实现22

36、、若一个栈的输入序列是1,2,3,4,n，输出序列的第一个元素是n，则第i个输出元素是（ ）A、不确定 B、 n-i C、 n-i+1 D、n-i-123、以下说法正确的是( )A、因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况B、因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况C、对于链栈而言,在栈满状态下,如果此时再作进栈运算，则会发生“上溢”D、对于顺序栈而言在栈满状态下如果此时再作进栈运算，则会发生“下溢”。二、 判断题1、 在顺序栈栈满情况下，不能做进栈运算，否则会产生“上溢”。2、 链栈与顺序栈相比的一个优点是链栈插入和删除操作更加方便。3、 若

37、一个栈的输入序列为1，2，3，n，其输出序列的第一个元素为n，则其输出序列的每个元素ai一定满足ai=i+1(i=1,2, ,n)。4、 在链队列中，即使不设置尾指针也能进行入队操作。5、 在对链队列（带头指针）做出队操作时，不会改变front指针的值。6、 循环队列中元素个数为rear-front。7、 一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到4,3,1,2。8、 一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到1,2,3,4。9、 若以链表作为栈的存储结构，则进栈需要判断栈是否满。10、 若以链表作为栈的存储结构，则出栈需要判断栈是否空。三、 填空题1、栈的

38、特点是（ ），队列的特点是（ ）。2、线性表、栈、队列都是（ ）结构，可以在线性表的（ ）位置插入和删除元素；对于栈只能在（ ）插入和删除元素；对于队列只能在（ ）插入元素和在（ ）位置删除元素。3、有程序如下，则此程序的输出结果（栈的元素类型是SelemType为char）是（ ）。Void main() stack s; char x,y; initstack (s); x=c;y=k;push(s,x);push(s,a);push(s,y);pop(s,x);push(s,t);push(s,x);pop(s,x);push(s,s);while(!stackempty(s)pop(s

39、,y);printf(y);printf(x);4、在栈顶指针为HS的链栈中，判定栈空的条件是（HS=NULL）。5、向栈中压入元素的操作是先（ ）后（ ）。6、对栈进行退栈操作是先（ ）后（ ）。7、用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是（ ）和（ ）；若只设尾指针，则出队和入队的时间复杂度分别是（ ）和（ ）。8、从循环队列中删除一个元素时，其操作是（ ）。9、在一个循环队列中，队首指针指向队首元素的（ ）。10、在具有n个单元的循环队列中，队满时共有（ ）个元素。11、在HQ的链队列中，判断只有一个结点的条件是（ ）。12、设栈S和队列Q的出始状态为空

40、，元素a,b,c,d,e,f依次通过栈S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序是b,d,c,f,e,a 则栈S的容量至少应该是（ ）。13、有程序如下，则此程序的输出结果（队列的元素类型是QSelemType为char）是（ ）。Void main() char x=e,y=c;enqueue(q,h);enqueue(q,r);enqueue(q,y);dequeue(q,x);enqueue(q,x);degueue(q,x);enqueue(q,a);while(!queueempty(q)dequeue(q,y);printf(y);printf(x);14、有如下递归

41、函数：int dunno(int m)int value;if(m=0)value=3;else value=dunno(m-1)+5;return(value); 执行语句printf(“%dn”,dunno(3);的结果是（ ）。 四、 简答题1、 对于堆栈，给出三个输入项A，B，C，如果输入项序列为ABC，试给出全部可能的输出序列，并写出每种序列对应的操作。例如：A进B进C进C出B出A出，产生的序列为CBA。2、 简述以下算法的功能（栈的元素类型是SelemType为int）。（1） status algo1(stack s)int I,n,a255;n=0;while(!stackem

42、pty(s)n+;pop(s,an);for(I=1;I=n;I+)push(s,aI);(2) status algo2(stack s,int e)stack t;int d;initstack(t);while(!stackempty(s)pop(s,d);if(d!=e)push(t,d);while(!stackempty(t)pop(t,d);push(s,d);3、 内存中一片连续空间（不妨假设地址从0到m-1）提供给两个栈s1和s2使用，怎样分配这部分存储空间，使得对任一栈仅当这部分空间全满时才发生溢出。4、 有递归过程如下：void print(int w)int I;if(

43、w!=0)print(w-1)for(I=1;I=w;I+)printf(“%3d”,w);printf(“n”); 问：调用语句print(4)的结果是什么？5、 简述以下算法的功能（栈和队列的元素类型均为int）void algo(queue &q) stack s;int d;initstack(s);while(!queueempty(q)dequeue(q,d);push(s,d);while(!stackempty(s)pop(s,d);enqueue(q,d);6、 假设Q0，9是一个非循环线性队列，初始状态为front=rear=0，画出做完下列操作后队列的头尾指针的状态变化情

44、况，如果不能入队，请指出其元素，并说明理由。 d,e,b,g,h入队 d,e出队 I,j,k,l,m入队 b出队 n,o,p,q,r入队。7、按照运算符优先数法，画出对下面算术表达式求值时，操作数栈和运算符栈的变化过程：9-2*4+(8+1)/3。8、设栈S（1，2，3，4，5，6，7），其中7为栈顶元素。写出调用algo后栈S的状态。void algo(Stack *S)int i=0; Queue Q; Stack T; InitQueue(Q); InitStack(T); while(!StackEmpty(S) if(i%2=0) Push(T,Pop(S); else EnQueu

45、e(Q,Pop(S); i+; while(!QueueEmpty(Q) Push(S,DeQueue(Q); while(!StackEmpty(T) Push(S,Pop(T); 五、 设计题1、 在栈顶指针为HS的链栈中，写出计算该链栈中结点个数的函数？2、 已知Q是一个非空队列，S是一个空栈，使用C语言编写一个算法，仅用队列和栈的ADT函数和少量工作变量，将队列Q中的所有元素逆置。 栈的ADT函数有 void SetEmpty(stack s); /置空栈 void Push(stack s,ElemTye value); /新元素value进栈 ElemType Pop(stack

46、s); /出栈，返回栈顶值 Boolean IsEmptyS(stack s); /判断栈空否 队列ADT的函数有： void EnQueue(Queue q,ElemType value); /元素入队 ElemType DeQueue(Queue q); /出队列返回队头值 Boolean IsEmptyQ(Queue q); /判断队列是否为空3、 用单链表实现队列，如下图所示，并令front=rear=NULL表示队列为空，编写实现队列的如下五种运算的函数。Setnull:将队列置成空队列。getfirst:返回队列的第一个元素。enqueue:把元素插入队列的后端。dequeue:删

47、除队列的第一个元素。empty:判定队列是否为空。4.有A,B,C三个塔座，A上套有n个直径不同的圆盘，按直径从大到小叠放，形如宝塔,编号1,2,3n。要求将n个圆盘从A移到C，叠放顺序不变，移动过程中遵循下列原则：a.每次只能移一个圆盘b.圆盘可在三个塔座上任意移动c.任何时刻，每个塔座上不能将大盘压到小盘上5. 回文游戏：顺读与逆读字符串一样（不含空格）6数制转换：对于输入的任意一个非负十进制数,打印输出与其等值的八进制数。（利用栈）7括号匹配检验：假设在表达式中有三种括号（ ） ，检查表达式括号是否配对。8行编辑程序问题：在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时

48、更正。要求： 设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，并假设“#”为退格符，“”为退行符。（利用栈来完成）第四章 串 复习题一、 选择题1、设串s1=ABCDEFG，s2=PQRST，函数Concat(x,y)返回x和y串的连接串，Substr(s,i,j)返回串s从序号I开始的j个字符组成的子串，length(s)返回串s的长度，则Concat(Substr(s1,2,length(s2),Substr(s1,length(s2),2)的结果串是（ ）。 A、BCDEF B、BCDEFG C、BCPQRST D、BCDEFEF2、空串和空格是相同的。A、正确 B、错误3、若串S1=ABCDEFG，S2=9898，S3=#，S4=012345，则执行replace(s1,Substr(s1,4,length(s3),s3),Concat(s1,Substr(s4,index(s2,8),length(s2)后，其结果为（ ）。 A、ABC#G0123 B、ABCD#2345 C、A