数据结构课后练习题汇编.doc

数据结构课后练习题第一章 绪论一、 选择题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、正确性和简明性 F、分析算法的易懂性和文档性4、在数据结构中，从逻辑上可以把数据结构分成（ ）。A、 动态和静态结构 B、紧凑接和非紧凑结构C、线性与非线性结构 D、内部结构和外部结构5、计算机算法指的是（ ），它必具备输入、输出和（ ）5个特性。A、计算方法 B、排序方法 C、解决问题的有限运算序列 D、可行性、可移植性和可扩充性 E、可行性、确定性和有穷性6、线性表的顺序存储结构是一种（ ）的存储结构，线性表的链式存储结构是一种（ ）A、随机存取 B、顺序存取 C、索引存取 D、散列存取7、算法的时间复杂度取决于（ ）A、 问题的规模 B、待处理数据的初态 C、问题的规模和待处理数据的初态8、线性表若采用链表存储结构时，要求内存中可用存储单元的地址（ ）A、必须是连续的 B、部分地址必须是连续的C、一定是不连续的 D、连续不连续都可以9、在以下的叙述中，正确的是（ ）A、线性表的线性存储结构优于链式存储结构B、二维数组是它的每个数据元素为一个线性表的线性表C、栈的操作方式是先进先出D、队列的操作方式是先进后出10、根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数据组织形式。以下解释错误的是 ( )A、集合中任何两个结点之间都有逻辑关系但组织形式松散B、线性结构中结点按逻辑关系依次排列形成一条锁链C、树形结构具有分支、层次特性，其形态有点像自然界中的树D、图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接11、以下说法正确的是( )A、数据元素是数据的最小单位B、数据项是数据的基本单位C、数据结构是带有结构的各数据项的集合D、数据结构是带有结构的数据元素的集合二、 填空题1、数据逻辑结构包括（ ）四种类型，树型和图型结构合称（ ）。2、对于给定的n个元素，可以构造出的逻辑结构有（ ）、（ ）、（ ）和（ ）四种。3、算法的五个重要特性是（ ）。4、评价算法的性能从利用计算机资源角度看主要从（ ）方面进行分析。5、线性结构中元素之间存在（ ）关系，树型结构中元素之间存在（ ）关系，图型结构中元素之间存在（ ）关系。6、下面程序段的时间复杂度是（ ）。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、存储结构是逻辑结构的_实现。14、从数据结构的观点看，通常所说的数据应分成三个不同的层次，即_、_和_。15、根据需要，数据元素又被称为_、_、_或_。16、通常，存储结点之间可以有_、_、_、_四种关联方式，称为四种基本存储方式。17、通常从_、_、_、_等几方面评价算法的(包括程序)的质量。18、一个算法的时空性能是指该算法的_和_，前者是算法包含的_，后者是算法需要的_。19、在一般情况下，一个算法的时间复杂性是_的函数。20、常见时间复杂性的量级有：常数阶O(_)、对数阶O(_)、线性阶O ( _)、平方阶O(_)、和指数阶O(_)。通常认为，具有指数阶量级的算法是_的。21、数据结构的基本任务是数据结构的_和_。22、数据对象是性质相同的 的集合。23、抽象数据类型是指一个 以及定义在该模型上的一组操作。三、判断题1. 数据元素是数据的最小单位。2. 数据结构是带有结构的数据元素的集合。3. 数据结构，数据元素，数据项在计算机中的映象分别称为存储结构，结点，数据域。4. 数据项是数据的基本单位。5. 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。6. 数据的物理结构是数据在计算机中实际的存储形式。7. 算法和程序没有区别，所以在数据结构中二者是通用的。8. 顺序存储结构属于静态结构，链式存储结构属于动态结构。四、计算应用题1、 设n为正正数。确定下列各程序段中前置以记号的语句的频度。（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、写出下面算法中带标号语句的频度。 Void perm(int a,k,n) int x,I;(1) if(k=n)(2) for(I=1;I=n;I+)(3) printf(“%d”,aI);else(4) for(I=k;I=n;I+)(5) aI+=I*I;(6) perm(a,k+1,n);执行函数调用语句perm(a,1,n)3、指出下列两个算法的时间复杂度。（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;returm(sum);4、有下列几种用二元组表示的数据结构，画出它们对应的逻辑图形表示，并指出它们属于哪种结构。（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=,5、设有如图所示的逻辑结构图，给出它的逻辑结构。6、简述下列术语：数据，数据元素，数据结构，数据对象。7、逻辑结构与存储结构是什么关系?8、将数量级，n，n2，n3，nlog2n，log2n，2n，n!，按增长率进行排列。五、算法设计题1. 已知输入x,y,z三个不相等的整数，设计一个算法，使得这三个数按从大到小输出，并考虑所用算法的比较次数和元素移动次数。2. 编写在输入10个数中找出最小或最大的数的算法。3. 在数组An中查找值为k的元素,若找到则输出其位置i(1in),否则输出0作为标志。设计求解此问题的类C语言算法，并分析其最坏情况时间复杂度。第二章 线性表练习题一、 选择题1、表长为N的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（ ），删除一个元素需要移动的元素个数为（ ）。A. (N-1)/2 B. N C. N+1 D. N-1 E. N/2 F. (N+1)/2 G. (N-2)/22、线性表是具有N个（ ）的有限序列。A、表元素 B、字符 C、数据元素 D、数据项 E、信息3、“线性表的逻辑顺序和物理顺序总是一致的。”这个结论是（ ）。A、正确的 B、错误的 C、不一定，与具体结构有关。4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（ ）。A、必须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、连续或不连续都可以。5、带头结点的单链表为空的判定条件是（ ）。 A、head=NULL B、head-next=NULL C、head-next=head D、head!=NULL6、不带头结点的单链表head为空的判定条件是（ ）。 A、head=NULL B、head-next=NULL C、head-next=head D、head!=NULL7、非空的循环单链表head的尾结点P满足（ ）。A、P-NEXT=NULL B、p=NULL C、p-next=head D、p=head8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ ）。A、O(1) B、O(n) C、O(n2) D、O(nlog2n)9、在一个单链表中，若删除P所指结点的后继结点，则执行（）。、p-next=p-next-next 、p=p-next;p-next=p-next-next 、p-next=p-next; 、p=p-next-next; 10、在一个单链表中，若在所指结点之后插入所指结点，则执行（）。、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，则执行（）。、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、假设双链表结点的类型如下：typedef 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-rlink=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的单链表上，设有头和尾两个指针，执行（）操作与链表的长度无关。、删除单链表中的第一个元素、删除单链表中最后一个元素、在单链表第一个元素前插入一个新元素、在单链表最后一个元素后插入一个新元素15、线性结构中的一个结点代表一个（ ）A、数据元素 B、数据项 C、数据 D、数据结构16、非空线性表L=(a1,a2,ai,an)，下列说法正确的是（ ）A、每个元素都有一个直接前驱和直接后继B、线性表中至少要有一个元素C、表中诸元素的排列顺序必须是由小到大或由大到小的D、除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继17、顺序表是线性表的（ ）A、链式存储结构 B、顺序存储结构 C、索引存储结构 D、散列存储结构18、对于顺序表，以下说法错误的是（ ）A、顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址 B、顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列C、顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻D、顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中19、对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（ ）为标准操作。A、插入操作 B、结点移动 C、算术表达式 D、删除操作20、对于顺序表的优缺点，以下说法错误的是（ ）A、无需为表示结点间的逻辑关系而增加额外的存储空间B、可以方便地随机存取表中的任一结点C、插入和删除运算较方便D、由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)21、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。A、顺序表 B、单链表 C、双链表 D、单循环链表22、循环链表主要优点是（ ）A、不再需要头指针了B、已知某个结点的位置后，能够容易找到它的直接前趋C、在进行插入、删除运算时，能更好地保证链表不断开D、从表中任一结点出发都能扫描到整个链表23、在线性表的下列存储结构中，读取元素花费时间最少的是（ ）A、单链表 B、双链表 C、循环链表 D、顺序表二、填空题、在线性结构中，第一个结点（）前趋结点，其余每个结点有且只有（）个前趋结点。、在顺序表中插入或删除一个元素，需要平均移动（）元素，具体移动的元素个数与（）有关。、已知是无表头结点的单链表，试从下列提供的答案中选择合适的语句序列，分别实现：（）表首插入结点的语句序列是（）。（）表尾插入结点的语句序列是（）。、-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）删除首元结点的语句序列是（ ） ,（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结点的直接前趋结点的语句序列是（ ）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所指结点后插入一个新结点的时间复杂度是（ ）；在值域为给定值的结点后插入一个新结点的时间复杂度是（ ）。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称为_结点，an称为_结点，i称为ai在线性表中的_。对任意一对相邻结点ai、ai1(1in),ai称为ai1的直接_，ai1称为ai的直接_。15、线性结构的基本特征是：若至少含有一个结点，则除起始结点没有直接_外，其他结点有且仅有一个直接_；除终端结点没有直接_外，其它结点有且仅有一个直接_.16、所有结点按1对1的邻接关系构成的整体就是_结构。17、线性表的逻辑结构是_结构。其所含结点的个数称为线性表的_。18、在单链表中，指针p所指结点为最后一个结点的条件是_。三、判断题1. 顺序存储的线性表可以随机存取。2. 顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动。3. 线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。4. 在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。5. 在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。6. 在单链表中，可以从头结点进行查找任何一个元素。7. 线性表的链式存储结构优于顺序存储结构。8. 在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。9. 在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。10. 顺序存储方式只能用于存储线性结构。四、简答题1、 若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用哪种存储结构？为什么？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、若线性表的总数基本稳定，且很少进行插入删除操作，但要求以最快的方式存取线性表的元素，应该用哪种存储结构。为什么？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为元素递增有序排列的单链表（同一表中可能有相同元素），编写算法另建一单链表C，保存两个表的公共元素，要求C的元素值各不相同且递增有序。4、设有一个由正整数组成的无序单链表，编写算法实现下列功能：（1） 找出最小值结点，且显示该数值。（2） 若该数值为奇数，则将其与直接后继结点的数值交换。（3） 若为偶数，则将其直接后继结点删除。 六、编程附加题1. 试分别用顺序表和单链表作为存储结构，实现将线性表（a0,a1,a2,.an-1）就地逆置的操作，所谓“就地”指辅助空间为O（1）。2. 设顺序表L是一个递增（允许有相同的值）有序表，试写一算法将x 插入L中，并使L仍为一个有序表。3. 设单链表L是一个非递减有序表，试写一个算法将x插入其中后仍保持L的有序性。4. 试写出在无头结点的单链表的第i个元素之前插入一个元素的算法。5. 设A、B是两个线性表，其表中元素递增有序，长度分别为m和n。试写一算法分别以顺序存储和链式存储将A和B归并成一个仍按元素值递增有序的线性表C，请分析算法的时间复杂度。6. 设指针la和lb分别指向两个无头结点的单链表的首结点，设计从表la中删除第i个元素起共len个元素，并将这些元素插入到lb中第j个结点之前的算法。7. 单链表L是一个递减有序表，试写一高效算法，删除表中值大于min且小于max的结点（若表中有这样的结点），同时释放被删结点空间，这里min和max是两个给定的参数。请分析你的时间复杂度。8. 编写一个算法将一个头结点指针为pa的单链表A分解成两个单链表A和B，其头结点指针分别为pa和pb，使得A链表中含有链表A中的序号为奇数的元素，而B链表中含有原链表A中的序号为偶数的元素，且保持原来的相对顺序。9. 假设以两个元素依值递增有序排列的线性表A,B分别表示两个集合，先要求另辟空间构造一个线性表C,其元素为两集合的交集，且表C中的元素也依值递增有序排列。是对顺序表编写求C的算法。10. 设有线性表A=(a1,a2,. .,am)和B=(b1,b2,. .,bn)。试写合并A、B为线性表C的算法，使得：C=线性表A,B和C均以单链表作存储结构，且C表利用A表和B表的结点空间。11. 假设在长度大于1的单循环链表中，既无头结点也无头指针。S为指向链表中某个结点的指针，试编写算法删除结点*s 的直接前驱结点。12. 计算带头结点的循环链表的结点个数。13. 已知由单链表表示的线性表中，含有三类字符的数据元素（如：字母字符、数字字符和其他字符），试编写算法构造三个以循环链表表示的线性表使得每个表中只含有同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。14. 已知A,B和C为三个递增有序的线性表，现要求对A表作如下操作：删去那些既在B表中出现又在C表中出现的元素。试对顺序表编写实现上述操作的算法，并分析你的算法的时间复杂度（注：题中没特别指明同一表中的元素值各不相同）。15. 双向循环链表中，设计满足下列条件的算法。（1）在值为x的结点之前插入值为y的结点。（2）删除值为x的结点。16. 设有一个循环双链表，其中有一结点的指针为P，编写算法将P与其右边的一个结点进行交换。17. 设有一个双链表，每个结点中除有prior、data和next三个域外，还有一个可访问频度域freq，在链表被起用之前，其值均初始为0。每当链表进行一次LocateNode（L，x）运算时令元素值为x的结点中freq域的值加1，并调整表中结点的次序，使其按访问频度的递减次序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode的运算的算法。18. 给出用单链表存储多项式的结构，并编写一个按指数值递增次序输入所产生的多项式链表的过程。19. 根据上题的多项式链表结构，编写一个过程实现两个多项式相加的运算。20. （Josephus环）任给正整数n、k，按下述方法可得排列1，2，n的一个置换:将数字1，2，n环形排列，按顺时针方向从1开始 计数；计满K时输出该位置上的数字(并从环中删去该数字)，然后从下一个数字开始继续计数，直到环中所有数字均被输出为止。例如，n=10，k=3时，输出的置换是3，6，9，2，7，1，8，5，10。分别以数组和以不带头结点的、已知尾指针的单循环链表为存储结构解决上述问题。21 已知在一维数组A1.m+n中依次存放着两个向量（a1,a2,.am）和（b1,b2,.bn），编写算法将两个向量的位置互换，即把（b1,b2,.bn）放到（a1,a2,.am）之前。22 给定一个不带头结点的单链表，编写计算此链表长度的算法。23 设ha和hb分别是两个带头结点的非递减有序单链表的表头指针， 试设计一个算法， 将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其它的存储空间。表中允许有重复的数据。 24 设有一个由正整数组成的无序（向后）单链表，编写完成下列功能的算法：(1)找出最小值结点，且打印该数值；(2)若该数值是奇数，则将其与直接后继结点的数值交换；(3)若该数值是偶数，则将其直接后继结点删除；25 利用顺序表的操作，实现以下的函数。(1) 从顺序表中删除具有最小值的元素并由函数返回被删元素的值，空出的位置由最后一个元素填补。(2) 从顺序表中删除具有给定值x的所有元素。(3) 从有序顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素。26 如果以单链表表示集合，设计算法建立先后输入的两个集合的差。27 已知一个线性表中的元素按元素值非递减有序排列，分别以顺序存储和链式存储编写一个算法删除表中多余的值相同的元素。28 设A=（a1,a2,a3,.an）和B=(b1,b2,. .,bm)是两个顺序表（假定所含数据元素均为整数）。若n=m且ai=bi(i=1,. .,n),则称A=B;若ai=bi(i=1,.,j)且aj+1bj+1（jnm）, 则称AB。是编写一个比较A和B的算法，当AB是分别输出-1，0或者1。a1a2anhead29 已知一个循环单链表如图2.1所示，编写一个算法将所有箭头方向取反。图2.1 30 假设有一个单循环链表，其结点含有三个域：prior，data，和next。其中data为数据域，next指向后继结点，prior为指针域，它的值为空指针，试编写算法将此表改为双向循环链表。31 设A是一个双向循环链表，其表中元素递增有序。试写一算法插入一个元素x，使表A中的元素依然递增有序。32写出将双向循环链表倒置的算法。33 设计一算法，将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式各自仅有奇次幂或偶次幂项，并要求利用原链表中的结点空间来构造这两个链表。34 设以带头结点的双向链表表示的线性表L=(a1,a2,an)，试写一时间复杂度为O(n)的算法，将L改造为L=(a1,a3,an,a4,a2)。35 设一单向链表的头指针为head，链表的记录中包含着整数类型的key域，试设计算法，将此链表的记录按照key 递增的顺序进行就地排序。第三章栈与队列 练习题一、 选择题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; 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/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存放其元素值，已知其头尾指针分别是front和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 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.