数据结构试题库教材

PAGE50-1绪论沈阳理工大学应用技术学院信息与控制学院计算机科学与技术教研室2011-5-8

数据结构复习题：绪论单选题1、在数据结构中，与所使用的计算机无关的数据叫____结构。A存储|B物理|C逻辑|D物理和存储2、在数据结构中，从逻辑上可以把数据结构分成______。A动态结构和静态结构|B紧凑结构和非紧凑结构|C线性结构和非线性结构|D内部结构和外部结构图3、数据结构在计算机内存中的表示是指_______。数据的存储结构|数据结构|数据的逻辑结构|数据元素之间的关系4、在数据结构中，与所使用的计算机无关的是数据的______结构。逻辑|存储|逻辑和存储|物理5、在以下的叙述中，正确的是_____。线性表的线性存储结构优于链表存储结构|二维数组是其数据元素为线性表的线性表|栈的操作方式是先进先出|队列的操作方式是先进后出6、在决定选取何种存储结构时，一般不考虑_______。各结点的值如何|结束个数的多少|对数据有哪些运算|所用编程语言实现这种结构是否方便7、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储_______。数据的处理方法|数据元素的类型|数据元素之间的关系|数据的存储方法8、下面说法错误的是_______。(1)算法原地工作的含义是指不需要任何额外的辅助空间(2)在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法(3)所谓时间复杂度是指最坏情况下，估计算法执行时间的一个上界(4)同一个算法，实现语句的级别越高，执行效率越低(1)|(1)、(2)|(1)、(4)|(3)9、通常要求同一逻辑结构中的所有数据元素具有相同的特性。这意味着______。数据元素具有同一特点|不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致|每个数据元素都一样|数据元素所包含的数据项的个数要相等10、以下说法正确的是_______。数据元素是数据的最小单位|数据项是数据的基本单位|数据结构是带结构的数据项的集合|一些表面上很不相同的数据可以有相同的逻辑结构11、数据项是数据的最小单元,数据元素是数据的基本单位.数据项|数据元素|信息项|表元素12、数据结构是指__数据元素__以及它们之间的__结构___.(1)数据元素(2)结构|(1)计算方法(2)关系|(1)逻辑存储(2)运算|(1)数据映像(2)算法13、计算机所处理的数据一般具备某种内在的关系,这是的指_____.数据和数据之间存在的某种关系|元素和元素之间存在某种关系|元素内部具有某种结构|数据项和数据项之间存在某种关系14、数据的逻辑结构可以分为_____两类.动态结构和表态结构|紧凑结构和非紧凑结构|线性结构和非线性结构|内部结构和外部结构15、数据的逻辑结构是指_____关系的整体.数据元素之间逻辑|数据项之间逻辑|数据类型之间|存储结构之间16、在存储数据时,通常不仅要存储各数据元素的值,而且还要存储_____.数据的处理方法|数据元素的类型|数据元素之间的关系|数据的存储方法17、在数据的存储结构中,一个存储结点存储一个_____.数据项|数据元素|数据结构|数据类型18、在计算机的存储器中表示时,物理地址和逻辑地址直接对应并且是连续的,称之为_____.逻辑结构|顺序存储结构|链式存储结构|以上都对19、数据采用链式存储结构时,要求_____.每个结点用占一片连续的存储区域|所有结点占用一片连续的存储区域|结点的最后一个数据域是指针类型|每个结点有多少个后继,就设多少个指针域20、数据的运算_____.效率与采用何种存储结构有关|是根据存储结构来定义的|有算术运算和关系运算两大类|必须用程序设计语言来描述21、下列说法中,不正确的是_____.数据元素是数据的基本单位|数据项是数据中不可分割的最小可标识单位|数据可由若干个数据元素构成|数据项可由若干个数据元素构成22、_____不是算法的基本特性.可行性|长度有限|在规定的时间内完成|确定性23、计算机中算法指的是解决某一问题的有限运算序列,它必须具备输入、输出、_____.可行性、可移植性和可扩充性|可行性、有穷性和确定性|确定性、有穷性和稳定性|易读性、稳定性和确定性24、以下不属于算法特性的是_____.可行性|有输入|确定性|健壮性25、下面关于算法的说法正确的是_____.算法最终必须由程序实现|算法的有穷性是对于任意的一组输入值必须在有穷步骤后结束|算法的可行性是指指令不能有二义性|以上几个都是错误的26、算法的时间复杂度与______有关问题规模|计算机硬件性能|编译程序质量|程序设计语言27、算法分析的主要任务是分析_____.算法是否具有较好的可读性|算法中是否存在语法错误|算法的功能是否符合设计要求|算法的执行时间和问题规模之间的关系28、某算法的时间复杂度为O(n2),表明该算法的_____.问题规模是n2|执行时间等于n2|执行时间与n2成正比|问题规模与n2成正比29、算法分析的目的是_____.找出数据结构的合理性|研究算法中输入和输出关系|分析算法的效率以求改进|分析算法的易读性和文档性30、线性表是具有n个______的有限序列。表元素|字符|数据元素|数据项31、线性表是______。一个有限序列，可以为空|一个有限序列，不可以为空|一个无限序列，可以为空|一个无限序列，不可以为空32、线性表采用链表存储时，其地址______。必须是连续的|一定是不连续的|部分地址必须是连续的|连续与否均可以33、链表不具备的特点是______。可随机访问任一结点|插入删除不需要移动元素|不必事先估计存储空间|所需空间与其长度成正比34、线性表的静态存储结构与顺序存储结构相比优点是_______。所有的操作算法实现简单|便于随机存取|便于插入和删除|便于利用零散的存储器空间35、设线性表有n个元素，以下操作中，_______在顺序表上实现比在链表上实现效率更高。输出第i(1<=i<=n)个元素值|交换第1个元素与第2个元素的值|顺序输出这n个元素的值|输出与给定值x相等的元素在线性表中的序号36、对于一个线性表，既要求能够较快地进行插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应采用_______存储结构。顺序|链式|散列|索引37、设线性表中有2n个元素，以下操作中，______在单链表上实现要比在顺序表上实现效率更高。删除指定的元素|在最后一个元素的后面插入一个新元素|顺序输出前k个元素|交换第i个元素和第2n-i-1个元素的值(i=0，1，…，n-1)38、需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是______。单链表|静态链表|线性链表|顺序存储结构39、如果最常用其所长的操作是取第i个结点及其前驱，则采用______结构方式最节省时间。单链表|双链表|单循环链表|顺序表40、与单链表相比，双链表的优点之一是______。插入、删除操作更简单|可以进行随机访问|可以省略表头指针或表尾指针|访问前后相邻结点更灵活41、数据结构在计算机内存中的表示是指______.数据的存储结构|数据结构|数据的逻辑结构|数据元素之间的关系42、下面程序段的时间复杂度为_________．O(m)|O(n)|O(m*n)|O(m+n)for(inti=0;i<m;i++)for(intj=0;j<n;j++)a[i][j]=i*j;数据结构复习题：绪论判断题1、数据元素是数据的最小单位。2、数据项是数据的基本单位。3、数据元素是数据的最小单位4、数据对象就是一组任意数据元素的集合5、任何数据结构都具备3个基本运算:插入、删除和查找.6、数据是由一些类型相同的数据元素构成的7、数据是逻辑结构与各数据元素在计算机中如何存储有关8、如果数据元素值发生改变,则数据的逻辑结构也随之改变.9、逻辑结构相同的数据,可以采用多种不同的存储方法.10、逻辑结构相同的数据,结点类型也一定相同11、逻辑结构不相同的数据,必须采用不同的存储方式来存储12、数据的逻辑结构是指数据的各数据项之间的逻辑关系.13、算法的优劣与算法描述语言有无关，但与所有计算机有关。14、算法可以用不同的语言描述，如果用C或Pascal等高级语言来描述，则算法实际上就是程序了。15、程序一定是算法。16、算法最终必须由计算机程序实现。F19、健壮的算法不会因非法入输数据而出现莫名其妙的执行结果。数据结构复习题：绪论算法分析题1、求两个n阶矩形的乘法C=A*B,其算法如下:#defineMAX100voidmaxtrixmult(int,floata[MAX][MAX],b[MAX][MAX],floatc[MAX][MAX]){inti,j,k;floatx;for(i=1;i<=n;i++)//①{for(j=1;j<=n;j++)//②{x=0;//③for(k=1;k<=n;k++)//④x+=a[i][k]*b[k][j];//⑤c[i][j]=x;//⑥}}}计算①～⑥各语句的频度,并分析该算法的时间复杂度。2、设n是偶数,试计算运行下列程序段后m的值并给出该程序段的时间复杂度。m=0;for(i=1;i<=n;i++)for(j=2*1;j<=n;j++)m++;3、阅读下列算法:voidsuan_fa(intn){inti,j,k,s,x;for(s=0,i=0;i<n;i++)for(j=i;j<n;j++)s++;i=1;j=n;x=0;while(i<j){i++;j--;x+=2;}pirntf("s=%d,x=%d",s,x);}(1)分析算法中语句"s++;"的执行次数;(2)分析算法中语句"x+=2;"的执行次数;(3)分析该算法的时间复杂度;(4)假定n=5,试指出执行该算法的输出结果。6、设n是偶数,试计算运行下列程序段后m的值并给出该程序段的时间复杂度。intm=0,i,j;for(i=1;i<=n;i++)for(j=2*i;j<=n;j++)m++;m=n*n/4O()数据结构复习题：绪论填空题1、一个数据结构在计算机中___映像___称为存储结构。2、数据逻辑结构包括、和三种类型，树形结构和图形结构合称为________。3、在线性结构中，第一个结点________前驱结点，其余每个结点有且只有_______个前驱结点：最后一个结点______后续结点，其余每个结点有且只有______个后续结点。4、在树形结构中，树根结点没有______结点，其余每个结点有且只有______个前驱结点:叶子结点没有______结点,其余每个结点后的后续结点可以_______5、在图形结构中，每个结点的前驱结点数和后续结点数可以___任意多个_____。6、线性结构中元素之间存在___一对一______关系，树形结构中元素之间存在___一对多____关系，图形结构中元素之间存在____多对多____关系。7、算法的5个重要特性是_________、__________、__________、输入和输出。8、算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实现上就是程序了。这个断言是________。9、数据结构、数据元素和数据项在计算机中的映射(或表示)分别称为存储结构、结点和数据域。这个断言是_______。10、下面程序段的时间复杂度是_______。for(i=0;i<n;i++)for(j=0;j<m;j++)A[i][j]=0;11、下面程序段的时间复杂度是__O(sqrt(n))_____。i=s=0;while(s<n){i++;s+=i;}12、下面程序段的时间复杂度是_______。s=0;for(i=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;13、下面程序段的时间复杂度是___O(log3n)_____。i=1;while(i<=n)i=i*3;14、有如下递归函数fact(n),分析其时间复杂度。intfact(intn){if(n<=1)return1;elsereturn(n*fact(n-1));}15、指出下列各算法的时间复杂度(1)prime(intn){inti=2;while(n%i!=0&&i<sqrt(n))i++;if(i*1.0>sqrt(n))printf"是一素数";elseprintf"不是一素数";}O(sqrt(n))(2)sum1(intn){intp=1,sum=0,i;for(i=1;i<=n;i++){p*=i;sum+=p;}returm(sum);}(3)sum2(intn){intsum=0,i,j;for(i=1;i<=n;i++){p=1;for(j=1;j<=i;j++)p*=j;sum+=p;}return(sum);}16、数据的逻辑结构是指_____.17、一个数据结构在计算机中的_表示_____称为存储结构.18、顺序存储方法是把逻辑上__相邻的结点___存储在物理位置上___相邻的存储单元___里;链式存储方法中结点间的逻辑关系是由附加的指针字段表示____的.19、数据结构是指研究数据的__存储结构___和__逻辑结构___以及它们之间的相互关系,并对这种结构定义相应的__运算___,设计出相应的__算法___,从而确保经过这些运算后所得到的新结构是原来的结构类型.20、一个算法具有5个特性:_____、_____、_____、输入和输出。21、算法的执行时间是_____的函数。22、数据的逻辑结构是从逻辑上描述数据,它与数据的___存储结构、物理结构___无关,是独立于计算机的.23、数据的逻辑结构被分为____________、____________、___________和____________４种。24、数据的存储结构被分为____________、____________、____________和____________４种。25、在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着____1:1________、____1：N________、_____M:N_______的联系。26、一种抽象数据类型包括______数据______和____操作_______两个部分。27、从一维数组a[n]中顺序查找出一个最大值元素的时间复杂度为____________，输出一个二维数组b[m][n]中所有元素值的时间复杂度为____________28、在下面程序段中，s=s+p语句的执行次数为______n______，p*=j语句的执行次数为______n*(n+1)/2______，该程序段的时间复杂度为______O(n*n)______。inti=0,s=0;while(++i<=n){intp=1;for(intj=1;j<=i;j++)p*=j;s=s+p;}29、一个算法的时间复杂度为（3*n*n+2nlog2n+4n-7)/(5n)，其数量级表示为_____O(n)_______。30、从一个数组a[10]中顺序查找元素时，假定查找每个元素的概率都相同，则进行一次查找运算时的平均查找长度（即同元素的平均比较次数）为____________。31、从一个数组a[7]中顺序查找元素时，假定查找第1个元素a[0]的概率为1/3，查找第2个元素a[1]的概率为1/4，其找其余元素的概率均相同，则在查找成功时同元素的平均比较次数为____35/12________。32、对于一个n*n的矩阵Ａ的任意矩阵元素a[i][j]，按行存储时和按列存储时的地址之差是____(i-j)*(n-1)*d______。设两种存储时的开始存储地址均为ＬＯＣ(0,0)，每个元素所占存储单元数均为d。33、设有一个二维数组A[10][20]，按行存放于一个连续的存储空间中，A[0][0]的存储地址是200，每个数组元素占1个存储字，则A[6][2]的存储字地址是____________34、设有一个二维数组A[10][20]，按列为主序存放于一个连续的存储空间中，A[0][0]的存储地址是200，每个数组元素占1个存储字，则A[6][2]的存储字地址是____________。37、在线性表的单链接存储结构中，每个结点包含有两个域，一个叫____________，另一个叫____________域。数据结构复习题：绪论问答题1、当你为解决某一问题而选择数据结构时,应从哪些方面考虑?2、简述逻辑结构与存储结构的关系.3、数据运算是数据结构的一个重要方面,试举例说明两个数据结构的逻辑结构和存储方式完全相同,只是对于运算的定义不同,因而两个结构具有显著不同的特性,则这两个数据结构是不同的.数据结构复习题答案：绪论问答题1、解答：通常从两方面考虑：第一是算法所需的存储空间量；第二是算法所需的时间。对算法所需的时间又涉及以下三点：（1）程序运行时所需输入的数据总量。（2）计算机执行每条指令所需的时间。（3）程序中指令重复执行的次数。2、答：数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。3、答：栈和队列的逻辑结构相同，其存储表示也可相同（顺序存储和链式存储），但由于其运算集合不同而成为不同的数据结构。2线性表沈阳理工大学应用技术学院信息与控制学院计算机科学与技术教研室2011-5-8

数据结构复习题：线性表单选题1、在一个长度为n的顺序表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需向后移动_____个元素。2、从一个具有n个节点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较__(n+1)/2___个结点。3、在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q和*p之间插入*s结点，则执行_____。4、线性表是_____。5、对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的，删除一个元素时大约要移动表中的_____个元素。6、线性表采用链式存储时，其地址_____。7、设单链表中指针p指着结点m，指针f指着将要插入的新结点x，当x插在链表中最后一个结点m之后时，只要先修改_____后修改p->link=f即可。8、在双向链表存储结构中，删除p所指的结点时需修改指针_____。9、在双向链表存储结构中，删除p所指的结点的前趋结点（若存在）时需修改指针_____。10、根据线性表的链式存储结构，每个结点所含指针的个数，链表分为单链表和_____。11、在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上_____。12、链表不具备的特点是_______。13、不带头结点的单链表head为空的判定条件是______。14、带头结点的单链表的head为空的判定条件是______。15、带头结点的双循环表L为空表的条件是__L->next==L____。16、非空的循环单链表head的尾结点(由p所指向)满足_______。17、在循环双链表的p所指结点之前插入s所指结点的操作是_______。18、若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用___带头结点的双循环链表___存储方式最节省运算时间。19、某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，故采用___仅有尾指针的单循环链表__存储方式最节省运算时间。20、需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是_______。21、如果最常用的操作是取第i个结点及其前驱，则采用___顺序表___存储方式最节省时间。22、在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是______。23、在一个长度为n(n>1)的单链表上，设有头和尾两个指针，执行____删除单链表中的最后一个元素____操作与链表的长度有关。24、设线性表有n个元素，以下算法中，_______在顺序表上实现比在链表上实现效率更高。25、设线性表中有2n个元素，算法___删除所有值为x的元素____，在单链表上实现要比在顺序表上实现效率更高。26、与单链表相比，双链表的优点之一是________。27、如果对线性表的运算只有4种，即删除第一个元素，删除最后一个元素，在第一个元素前面插入新元素，在最后一个元素的后面插入新元素，则最后使用___只有表头指针没有表尾指针的循环双链表_____。28、如果对线性表的运算只有两种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用_______。29、设有两个长度为n的单链表，结点类型相同。若以h1为表头指针的链表是非循环的，以h2为表头指针的链表是循环的，则_______。30、在长度为n的______上，删除第一个结点，其算法的时间复度为O(n)。31、将两个各有n个元素的有序顺序表归并成一个有序顺序表，其最少的比较次数是__n___。32、带头结点的单链表L为空的判定条件是______。33、在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是_______。34、在一个长度为n(n>1)的带头结点的单链表h上，，另设有尾指针r(指向尾结点)，执行_______操作与链表的长度有关。35、在一个双链表中，在*p结点之后插入结点*q的操作是______。36、在一个双链表中，在*p结点之前插入*q结点的操作是______。37、在一个双链表达式，删除*p结点的操作是_______。38、在一个双链表中，删除*p结点之后的一个结点的操作是________。39、非空的循环单链表L的尾结点(由p所指向)满足______。40、带头结点的双循环链表L为空表的条件是______。41、若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用_____带头结点的循环双链表____存储方式最节省运算时间。42、如果对含有n(n>1)个元素的线性表的运算只有4种:删除第一个元素；删除最后一个元素；在第一个元素前面插入新元素；在最后一个元素的后面插入新元素，则最好使用____只有头结点指针没有尾结点指针的循环双链表____。43、某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，则采用____仅有尾结点指针的单循环链表___存储方式最节省运算时间。44、设有两个长度为n的单链表，结点类型相同，若以h1为头结点的链表是非循环的，以h2为头结点指针的链表是循环的，则________。45、在长度驎n(n>1)的___只有首结点指针h的不带头结点的循环单链表___上，删除第一个元素，其算法的时间复杂度为O(n)。46、元素A、B、C、D依次进顺序栈后，栈顶元素是_______，栈底元素是______。47、经过以下栈运算后，X的值是______。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s,x);48、经过以下的栈运算后，StackEmpty(s)的值是______。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);Pop(s,y)49、设一个栈的输入序列为A、B、C、D，则借助一个栈所得到的输出序列不可能是______。50、若线性表最常用的运算是存取第i个元素及其前驱的值,则采用______存储方式节省时间.51、链表不具备的特点是______.52、在一个长度为n的顺序存储的线性表中，向第i个元素(1<=i<=n+1)位置插入一个新元素时，需要从后向前依次后移_________个元素．53、在一个长度为n的顺序存储的线性表中，删除第i个元素(1<=i<=n)时，需要从前向后依次前移____n-i_____个元素．54、在一个长度为n的线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x同元素的平均比较次数，查找每个元素的概率都相等）为（）．57、在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行_________。数据结构复习题：线性表判断题1、顺序存储的线性表可以随机存取。2、线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此，是属于同一数据对象。T3、在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点查找任何一个元素。4、在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。5、链表的每个结点中，都恰好包含一个指针。6、线性表中每个元素都有一个直接前驱和直接后继。7、线性表中所有元素的排列顺序必须由小到大或由大到小。8、静态链表的存储空间在运算中可以改变大小。9、静态链表既有顺序存储结构的优点，又有动态链表的优点。所以，它存取表中的第i个元素的时间与i无关。10、静态链表中能容纳元素个数的最大数在定义时就确定了，以后不能增加。11、静态链表与动态链表的插入、删除操作类似，不需做元素的移动。12、线性表的顺序存储结构优于链式存储结构。15、在双链表中，可以从任一结点开始沿同一方向查找任何其他结点。F数据结构复习题：线性表算法分析题1、己知一个顺序表L,其中的元素按值非递减有序排列,设计一个算法插入一个元素x后保持该顺序表仍按递减有序排列。要求算法的空间复杂度为O(1)。2、设计一个算法从顺序表L中删除所有值为X的元素。要求算法的空间复杂度为O(1)。3、从顺序表L中删除重复的元素,并使剩余元素间的相应次序保持不变.要求本算法的空间复杂记度为O(1)。4、有一个单链表(不同结点的数据域值可能相同),其头指针为head,设计一个算法计算数据域为x的结点个数。5、己知线性表元素递增有序,并以带头结点的单链表作存储结构,设计一个高效算法,删除表中所有值大于mink且小于maxk的元素(若表中存在这样的元素)。并分析所写算法的时间复杂度。6、设计一个在带头结点的单链表中删除一个最小值结点的高效算法。7、有一个不带头结点的单链表L(至少有1人结点),其头指针为head,设计一个算法将L逆置,即最后一个结点变成第一个结点,原来倒数第二个结点变成第二个结点,如此等等。8、用单链表表示集合,设计一个算法求两个集合的差。要求不破坏原有的结点。9、用单链表表示集合,设计一个算法求两个集合的并。要求不破坏原有的结点。10、设计一个算法,将一个头结点指针为a的单链表A分解成两个单链表A和B,其头结点指针分别为a和b,使得A链表中含有原链表A中序号为奇数的元素,而B链表中含有原链表A中序号为倒数的元素,且保持原来的相对顺序。11、有一个单链表,其结点的元素值以递增有序排列,设计一个算法删除该单链表中多余的元素值相同的结点。12、己知两个存放整数的有序单链表(己按整数从小至大的顺序排序),指针L1和L2分别指向这两个单链表的头结点。设计一个算法,将L1和L2合并成一个单链表,且新的链表仍按整数由小到大的顺序排列,新的单链表的结点由L1和L2的结点构成。要求合并后的单链表利用原来单链表的存储空间。13、设计一个算法,将线性表lb连接到la之后,要求其时间复杂度为O(1),占用的辅助空间尽量小。描述所用的结构。14、设指针p指向双链表中的结点X,指针f指向将要插入的新结点Y,Y要插入在结点X之后,写出指针需要修改的有关步骤。15、有一个循环双链表,每个结点由两个指针(prior和next)以及关键字(data)构成,p指向其中某一结点,设计一个算法从该循环双链表中删除p所指的结点。16、设有一个循环双链表,其中有一结点的指针为p,设计一个算法将p与其后续结点进行交换。19、设A和B是两个单链表(带头结点)，其表中元素递增有序。设计一个算法将A和B归并成一个按元素值递增有序的单链表C，要求辅助空晨为O(1)，并分析算法的时间复杂度。数据结构复习题：线性表填空题1、在线性结构中第一结点_____前驱结点，其余每个结点有且只有______个前驱结点；最后一个结点______后继结点。2、对于顺序存储的线性表，当随机插入或删除一个元素时，约需平均移动表长______的元素。3、对于长度为n的顺序表，插入或删除元素的时间复杂性为________；对于顺序栈或队列，插入或删除元素的时间复杂性为_________。4、在线性表的顺序存储中，元素之间的逻辑关系是通过_____相邻位置_____决定的；在线性表的链接存储中，元素之间的逻辑关系是通过______连接指针______决定的。5、一个单链表中删除*p结点时，应执行如下操作:(1)q=p->next;(2)p->data=p->next->data;(3)p->next=__________;(4)free(q);6、对于线性表的顺序存储，需要预先分配好存储空间，若分配太多则容易造成存储空间的__________，若分配太少又容易在算法中造成_____溢出_____，因此适应于数据量变化不大的情况；对于线性表的链接存储(假定采用动态结点)，不需要__________存储空间，存储器中的整个____动态存储区______都可供使用，分配和回收结点都非常方便，能够有效地利用存储空间，在算法中不必考虑_____溢出_____的发生，因此适应数据量变化较大的情况。7、从顺序表中删除第i个元素时，首先把第i个元素赋给_____变参或函数名_____带回，接着从______连接指针_______开始向后的所有元素均___________一个位置，最后使线性表的长度_____________。8、向一个长度为n的顺序表中的第i个元素(0<=i<=n-1)之前插入一个元素时，需向后移动______个元素。9、在一个长度为n的顺序表删除第i个元素(0<=i<=n-1)时，需向前移动______个元素。10、在单链表中设置头结点的作用是_____简化插入、删除算法______。11、在单链表中，要删除某一指定的结点，必须找到该结点的_______结点。12、访问单链表中的结点，必须沿着_____指针链___依次进行。13、在双链表中，每个结点有两个指针域，一个指向________，另一个指向_________。14、在___循环双___链表上，删除最后一个结点，其算法的时间复杂度为O(1)。15、在一个单链表中的p所指结点之前插入一个s所指结点时，可执行如下操作。(1)s->next=_________。(2)p->next=s;(3)t=p->data;(4)p->data=_________。(5)s-.data=_________。16、在一个单链表中删除p所指结点时，应执行以下操作：q=p->next;p_data=p->next->data;p->next=______;free(q);17、在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=_______和p->next=________的操作。18、对于一个具有n个结点的单链表，在*p结点后插入一个新结点的时间复杂度是____O(1)____；在给定值为x的结点后插入一后新结点的时间复杂度是________。19、在线性表的顺序存储中，元素之间的逻辑关系是通过___物理存储位置___决定的；在线性表的链式存储中，元素之间的逻辑关系是通过___链域的指针值___决定的。20、在一个长度为n的顺序表中删除第i个元素(1<=i<=n)时，需向前移动_______个元素。21、为了设置一个空的顺序表L，采用的操作是___L->length=0___。22、删除顺序表的______元素，不需要移动任何元素。23、删除顺序表的___最后一个___元素，不需要移动的元素最多。24、在顺序表_____元素后面插入一个元素，不需要移动任何元素。25、插入顺序表的______元素，需要移动的元素最多。26、在长度为n的顺序表L中查找指定元素值的元素，其时间复杂度为______。27、求单链表长度的时间复杂度为_______。28、删除单链表L中某结点*p之后的一个结点，其时间复杂度为______。29、删除单链表L中某结点*p之前的一个结点，其时间复杂度为___O(n)___。30、在一个单链表(己知每个结点含有数据域data和指针域next)中删除p所指结点时，应执行以下操作：(1)q=p->next;(2)p->data=q->data;(3)p->next=_____;(4)free(q);31、在一个单链表中的p所指结点之后插入*s结点时，应执行s->next=_____和p->next=______的操作。32、对于一个具有n个结点的单链表，在*p结点后插入一个新结点的时间复杂度是_______;在给定值为x的结点后插入一个新结点的时间复杂度是_______。33、删除双链表L中某结点*p之后的一个结点，其时间复杂度为_______。34、删除双链表L中某结点*p之前的一个结点，其时间复杂度为_______。35、在非循环的______链表中，可以用表尾指针代替表头指针。36、对于双链表，在两个结点之间插入一个新结点需要修改的指针共______。37、在一个双链表中，若要在*p结点之前插入结点*q，则执行的操作是______。38、循环单链表L为空的条件是_____。39、在单链表中,结点与结点之间的逻辑关系不是通过存储单元的顺序来表示的,而是通过___指向下一个结点的指针___来实现的.40、对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为____________，在表尾插入元素的时间复杂度为____________。41、对于一个单链接存储的线性表，在表头插入结点的时间复杂度为____________，在表尾插入元素的时间复杂度为____________。42、在线性表的顺序存储中，若一个元素的下标为i，则它的前驱元素的下标为____________，后继元素的下标为____________。43、在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为_____p->next_______，若p为一个数组a中的下标，则其后继结点的下标的______a[p]->next______。44、在循环单链表中，最后一个结点的指针域指向____________结点。45、在双向链表中每个结点包含有两个指针域，一个指向其____________结点，另一个指向其____________结点。46、在循环双向链表中表头结点的左指针域指向____________结点，最后一个结点的右指针域指向____________结点。47、在以ＨＬ为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为____________和____________。50、在由数组a中元素结点构成的单链表中，在下标为i的结点的后面插入一个下标为j的结点时，需要进行的操作为____________和____________语句。数据结构复习题：线性表问答题1、线性表有两种存储结构：一是顺序表，二是链表。试问：(1)两种存储表示各有哪些主要优缺点?(2)如果有n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构?为什么?(3)若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么，应采用哪种存储结构?为什么?解答：(1)顺序存储是按索引（隐含的）直接存取数据元素，方便灵活，效率高，但插入、删除操作时将引起元素移动，因而降低效率；链接存储内存采用动态分配，利用率高，但需增设指示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作十分简单。(2)应选用链接表存储结构。其理由是，链式存储结构用一组任意的存储单元依次存储线性表里各元素，这里存储单元可以是连续的，也可以是不连续的。这种存储结构，在对元素作插入或删除运算时，不需要移动元素，仅修改指针即可。所以很容易实现表的容量扩充。(3)应选用顺序存储结构。其理由是，每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。由此，只要确定了起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。而链表则是一种顺序存取的存储结构。用线性表的顺序结构来描述一个城市的设计和规划合适吗?为什么?不合适。因为一个城市的设计和规划涉及非常多的项目，很复杂，经常需要修改、扩充和删除各种信息，才能适应不断发展的需要。有鉴于此，顺序线性表不能很好适应其需要，故是不合适的。在单链表和双向表中，能否从当前结点出发访问到任一结点?在单链表中只能由当前结点访问其后的任一结点，因为没有指向其前驱结点的指针。而在双向链表中，既有指向后继结点的指针又有指向前驱结点的指针，故可由当前结点出发访问链表中任一结点。4、编写下列算法(1)向类型有list的线性表L的第i个元素（0≤i≤L.len）之后插入一个新元素x。(2)从类型为list的线性表L中删除其值等于x的所有元素。(3)将两个有序表A和B合并成一个有序表C，其中A，B，C均为list类型的变参。(1)解答:statusinsert(SqListL,inti,ElemTypex){//向线性表L中第i个元素之后插入值为x的新元素(1)if(L.len==m0)error('overflow');(2)if(i<0)||(i>L.len)error('outofrange');(3)for(j=L.len;j>=i＋1;--j)L.vec[j＋1]＝L.vec[j];}(4)L.vec[i＋1]＝x;(5)L.len＝len＋1;}(2)解答:statusdelete(L,x){//从线性表L中删除其值等于x的所有元素i＝1;while(i<＝L.len)if(L.vec[i]==x){(Ⅰ)for(j＝i＋1;j<=L.len;++j)L.vec[5、编写下列算法，假定单链表的表头指针用HL表示，类型为linklist。(1)将一个单链表中的所有结点按相反次序链接。(2)删除单链表中第i个（i≥1）结点。(3)删除单链表中由指针p所指向的结点。(4)从带有附加表头结点的循环单链表中删除其值等于x的第一个结点。(5)在单链表中指针p所指结点之前插入一个值为x的新结点。(6)从循环单链表中查找出最小值。(7)根据一维数组A(1:n)中顺序存储的具有n个元素的线性表建立一个带有附加表头结点的单链表。解答：(1)将一个单链表中的所有结点按相反次序链接。(1)解答:statuscontrary(HL){//使HL单链表中的所有结点按相反次序链接p＝HL;//p指向未被逆序的第一个结点，初始指向原表头结点HL＝nil;//HL指向逆序后的表头结点，初始值为空while(p!=nil){(1)q＝p;//q指向将被逆序链接的结点(2)p＝p＾.next;(3)q＾.next＝HL;(4)HL＝q;}}(2)删除单链表中第i个（i≥1）结点。(2)解答:statusdelete(HL,i){(1)if(i<＝0)or(HL＝nil)error('noth&&le');(2)if(i＝1){HL＝HL->next;return;}(3)j＝1;p＝HL;//p指针所指向的结点，是单链表中第j对链表设置头结点的作用是什么?(至少说出两条好处)解答：(1)对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一结点的指针域，因为任何元素结点都有前驱结点。若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点或删除该结点时操作会复杂些。(2)对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。在单链表、双链表和单循环表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去？若可以，其时间复杂度各为多少？解答：1.单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。2.双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。3.单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。简述顺序表和链表存储方式的特点。答：顺序表可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率；而链表内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序表方便，但结点的插入、删除操作较简单。有两个递增有序表，设计一个算法将它们归并成一个有序表(假设每个表中没有重复关键字的元素，归并时重复关键字的元素只归并一次)。答：voidMerge(LinkList&La,LinkListLb){pa=La->next;pb=Lb->next;p=La;while(pa&&pb){if(pa->data<=pb->data){p->next=pa;p=pa;pa=pa->next;}else{p->next=pb;p=pb;pb=pb->next;}}if(pa)p->next=pa;elsep->next=pb;free(Lb);}3栈和队列沈阳理工大学应用技术学院信息与控制学院计算机科学与技术教研室2011-5-8数据结构复习题：栈和队列单选题1、在一个具有n个单元的顺序栈中，假定以地址低端作为栈底，以top作为栈顶指针，则当做退栈处理时，top变化为_____。2、向顺序栈中压入元素时，是__先移动栈顶指针，后存入元素___。3、在一个顺序存储的循环队列中，队首指针指向队首元素的__前一个位置___。4、若进栈序列为1,2,3,4,进栈过程中可以出栈，则_____不可能是一个出栈序列。5、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件是_____。6、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队满的条件是_____。7、向一个栈项指针为hs的链栈中插入一个*s结点时，则执行_____。8、在一个链队列中，假定front和rear分别为队首指针和队尾指针，则进行插入*s结点的操作时应执行_____。9、栈的特点是_______队的特点是______10、栈和队列的共同点是_______。11、一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是________。12、若己知一个栈的进栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,…,pn,若p1=n,则pi(1<i<=n)为________。13、若己知一个栈的进栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,…,pn,若pn=n,则pi(i<=i<n)为_______。14、若己知一个栈的进栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,…,pn，若p1=3,则p2_______。15、若己知一个栈的进栈序列p1,p2,p3,…,pn,输出序列是1,2,3,…,n,若p3=1,则p1________。16、若己知一个栈的进栈序列p1,p2,p3,…,pn，输出序列是1,2,3,…,n。若pn=1,则pi(1<=i<n)为______。17、判定一个顺序栈st(最多元素为MaxSize)为空的条件是_______。18、判定一个顺序栈st(最多元素为MaxSize)为栈满的条件是_______。19、最不适合用作链栈的链表是___只有表头指针没有表尾指针的循环单链表_____。20、向一个栈项指针为hs的链栈中插入一个s所指结点时，则执行_______。21、从一个栈项指针为hs的链栈中删除一个结点时，用x保存被删结点的值，则执行__x=hs->data;hs=hs->next____。22、一个队列的入队序列是1,2,3,4,则队列的输出序列是_______。23、判定一个环形队列qu(最多元素为MaxSize)为空的条件是________。24、判定一个环形队列qi(最多元素为MaxSize)为满队列的条件是________。25、环形顺序队列中是否可以插入下一个元素,________。26、环形队列用数组A[0...MaxSize-1]存放其元素值,己知其头尾指针分别是front和rear,则当前队列的元素个数是_______。27、若用一个大小为6的一维数组来实现环形队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是______。28、最不适合用作链队的链表是__只带队头指针的非循环双链表____。29、在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算是_______。30、在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算是_______。31、用单链表表示的链队的队头在链用不着的____链头____位置。32、中缀表达式A*(B+C)/(D-E+F)的后缀表达式是________。33、己知一个栈的进栈序列是ABC,出栈序列为CBA,经过的栈操作是________。34、判定一个顺序栈st为(元素个数最多为MaxSize)空的条件为______。35、判定一个顺序栈st(元素个数最多为MaxSize)为栈满的条件是______。36、表达式a*(b+c)-d的后缀表达式是______。37、表达式(2+2*3)*2+6*3/2的后缀表达式是______。38、链栈与顺序栈相比有一个明显的优点,即___通常不会出现栈满的情况___。39、最不适合用作链栈的链表是__只有表头指针没有表尾指针的循环单链表____。40、如果以链表作为栈的存储结构,则退链栈操作时___必须差别链栈是否空___。41、向一个不带头结点的栈指针为1st的链栈中插入一个s所指结点时,则执行______。42、从一个不带头结点的栈顶指针为1st的链栈中删除一个结点时,用x保存被删结点的值,则执行______。43、一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是______.44、在一个长度为n的顺序存储的集合中查找值为x的元素时，在等概率情况下，查找成功时的平均查找长度为_________。45、在一个长度为n的链接存储的集合中查找值为x的元素时，算法的时间复杂度为___O(n)______。46、已知一个元素x不属于一个长度为n的顺序或链接存储的集合Ｓ中的元素，把它插入集合Ｓ时不进行比较过程，则插入过程的时间复杂度为_________。47、设一个具有t个非零元素的m*n大小的稀疏矩阵采用顺序存储，求其转置矩阵的普通转置算法的时间复杂度为____O(n*t)_____。数据结构复习题：栈和队列判断题1、栈底元素是不能删除的元素。2、顺序栈中元素值的大小是有序的。3、在n个元素进栈后,它们的出栈顺序和进栈顺序一定正好相反。4、栈顶元素和栈底元素有可能是同一个元素。5、若用S[1]-S[m]表示顺序栈的存储空间,则对栈的进栈、出栈操作最多只能进行m次。F6、空栈没有栈顶指针。数据结构复习题答案：栈和队列判断题1、False2、False3、True4、True5、False6、False数据结构复习题：栈和队列算法分析题设计一个算法,利用栈的基本运算将指定栈中的内容进行逆转。statusNizhuan(sqstacks,inta,intb,intt){If(s.top==s.base)error(‘nodata’);for(i=0;i<s.stacksize/2;i++){a=*--top;b=*s.base;a=t;t=b;b=a;s.top--;s.base++;}}设计一个算法,利用栈的基本运算返回指定栈中的栈底元素。statusGetbase(Aqstacks,int&e){If(s.top==s.base)Error(‘nodata’)elsee=*s.base;returne;}有两个栈s1和s2共享存储空间c[1..MaxSize],其中一个栈底设在c[1]处,另一个栈底设在c[MaxSize]处,分别编写s1和s2的进栈push(i,x)、退栈pop(i)和设置栈空setnull(i)的函数,其中i=1,2。注意:仅当整个空间c[1..MaxSize]占满时才产生上溢。（1）初始化操作【共享栈的初始化】intinitDupStack(dupsqstack*s){/*创建两个共享邻接空间的空栈由指针S指出*/if((s=(dupsqstack*)malloc(sizeof(dupsqstack)))==NULL)returnFALSE;s->lefttop=-1;s->righttop=MAXNUM;returnTRUE;}（2）入栈操作【共享栈的入栈操作】intpushDupStack(dupsqstack*s,charstatus,Elemtypex){*把数据元素x压入左栈（status=’L’）或右栈（status=’R’）*/if(s->lefttop+1==s->righttop)returnFALSE;/*栈满*/if(status=’L’)s->stack[++s->lefttop]=x;/*左栈进栈*/elseif(status=’R’)s->stack[--s->lefttop]=x;/*右栈进栈*/elsereturnFALSE;/*参数错误*/returnTRUE;}（3）出栈操作【共享栈的出栈操作】ElemtypepopDupStack(dupsqstack*s,charstatus){/*从左栈（status=’L’）或右栈（status=’R’）退出栈顶用不带头结点的单链表存储链栈,设计初始栈、判断栈是否为空、进栈和出栈等相应的算法。（1）入栈操作【单个链栈的入栈操作】intpushLstack(slStacktype*top,Elemtypex){//将元素x压入链栈top中slStacktype*p;if((p=(slStacktype*)malloc(sizeof(slStacktype)))==NULL)returnFALSE;//申请一个结点p->data=x;p->next=top;top=p;returnTRUE;}（2）出栈操作【单个链栈的出栈操作】ElemtypepopLstack(slStacktype*top){//从链栈top中删除栈顶元素slStacktype*p;Elemtypex;if(top==NULL)returnNULL;//空栈p=top;top=top->next;x=p->data;free(p);returnx;}数据结构复习题：栈和队列填空题1、在具有n个单元、顺序存储的循环队列中，队满时共有___n-1___个元素。2、栈和队列的区别仅在于____删除运算的不同____。3、通常元素进栈的操作是________。4、通常元素退栈的操作是________。5、一个栈的输入序列是12345,则栈的输出序列432512是__________。6、一个栈的输入序列是12345,则栈的输出序列12345是________。7、设有一个顺序栈S,元素s1,s2,s3,s4,s5,s6依次进栈,如果6个元素的出栈顺序为s2,s3,s4,s6,s5,s1,则顺序栈的容量至少应为________。8、设栈采用顺序存储结构,若己知i-1个元素进栈,则将第i个元素进栈时,进栈算法的时间复杂度为________。9、若用不带头结点的单链表来表示链栈S,则创建一个空栈所要执行的操作是___S==null_____。10、从环形队列中插入一个元素时,通常的操作是________。11、在具有n个单元的环形队列(共有MaxSize个单元)中,队满时共有___MaxSize-1_____个元素。12、在链表qu中,判定只有一个结点的条件是____qu->front==qu->rear&&qu->front!=NULL____。13、设栈S和队列Q的初始状态为空,元素a1,a2,a3,a4,a5,a6,a7和a8依次通过栈S,一个元素出栈后立即进入队列Q,若8个元素出队列的顺序是a3,a6,a7,a5,a8,a4,a2,a1,则栈S的容量至少应该是多少(即至少应该容纳多少个元素)?14、设有算术表达式x+a*(y-b)-c/d,该表达式的前缀表达为____-+x*a-yb/cd____。后缀表示为______。15、栈是一种具有______特性的线性表。16、顺序栈和链栈的区别仅在于___存储结构___的不同。17、如果栈的最大长度难以估计,则最好使用______。18、一个栈的输入序列是12345,则栈的输出序列12345是______。19、设栈采用顺序存储结构,若己知i-1个元素进栈,则将第i个元素进栈时,进栈算法的时间复杂度为______。20、表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是______。21、若用不带头结点的单链表来表示链栈1st,则创建一个空栈所要执行的操作是______。22、对于链栈1st,进栈操作在___链栈头___端进行,出栈操作在__链栈头___端进行。23、将递归算法转换为非递归算法时,通常使用___栈___这种数据结构。24、有如下递归算法:voidprint(intw){inti;if(w!=0){print(w-1);for(i=1;i<=w;i++)printf("%3d",w);printf("\n");}}调用语句printf(4)的结果是______。122333444425、有如下递归过程:voidreverse(intm){printf("%d",n%10);if(n/10!=0)reverse(n/10);}调用语句reverse(582)的结果是______。26、求顺序存储的集合的长度的时间复杂度为____________。27、求链接存储的集合的长度的时间复杂度为______O(n)______。28、设集合S的长度为n，则判断x是否属于集合Ｓ的时间复杂度为____________31、在稀疏矩阵的顺序存储中，利用一个数组来存储非零元素，该数组的长度应______大于等于______对应三元组线性表的长度。数据结构复习题：栈和队列问答题试述栈的基本性质?解答：由栈的定义可知，这种结构的基本性质综述如下：(1)集合性。栈是由若干个元素集合而成，当没有元素的空集合称为空栈；(2)线性结构。除栈底元素和栈顶元素外，栈中任一元素均有唯一的前驱元素和后继元素；(3)受限制的运算。只允许在栈顶实施压入或弹出操作，且栈顶位置由栈指针所指示；(4)数学性质。当多个编号元素依某种顺序压入，且可任意时刻弹出时，所获得的编号元素排列的数目，恰好满足卡塔南数列的计算，即：Ｃn＝Ｃn2n/(n＋1)其中，n为编号元素的个数，Cn是可能的排列数目。何谓队列的上溢现象?解决它有哪些方法，且分别简述其工作原理。解答：在队列的顺序存储结构中，设队头指针为front,队尾指针为rear,队的容量（存储空间的大小）为m。当有元素要加入队列时，若rear＝m（初始时reat＝0），则发生队列的上溢现象，该元素不能加入队列。这里要特别注意的是：队列的假溢出现象，队列中还有空余的空间，但元素不能进队列。造成这种现象的原因是由于队列的操作方式所致。解决队列的上溢有以下几种方法：(1)建立一个足够大的存储空间，但这样做往往会造成空间使用的效率低。(2)当出现假溢出时，可采用以下几种方法：①采用平移元素的方法。每当队列中加入一个元素时，队列中已有的元素向队头移动一个位置（当然要有空余的空间可移）；②每当删去一个队头元素时，则依次序移队中的元素，始终使front指针指向队列中的第一个位置；③采用循环队列方式。把队头队尾看成是一个首尾相邻的循环队列，虽然物理上队3、假定用一个循环单链表表示队列（称此为循环链队），该队列只设一个队尾指针，不设队首指针，试编写下列算法：(1)向循环链队插入一个元素为x的结点。(2)从循环链队中删除一个结点（假定不需要保留被删除结点的值和不需要回收结点）。解答：(1)解答:statusinsert(Rear,x){//假定Rear为循环链队的队尾指针，x为待插入的元素(1)malloc(p);p->data＝x;//建立值为x的新结点p＾(2)if(Rear＝nil){Rear＝p;Rear->next＝p;}else{p->next＝Rear->next;Rear->next＝p;Rear＝p;}//若条件成立则建立循环链队的第一个结点，否则在队尾插入p＾结点}(2)解答:statusdelete(Rear){if(Rear＝nil)error('underflow');if(Rear->next==Rear)Rear＝nil;elseRear->next＝Rear->next->next;}//Rear＾.next所指向的结点为循环链队的队首结点为什么说栈是一种后进先出表?栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表（LIFO--LastINFirstOut表）。对于一个栈,给出输入项A,B,C。如果输入项序列由A,B,C所组成,试给出全部可能的输出序列。AＢＣ，ＢＡＣ，ＣＢＡ有字符串次序为3*y-a/y↑2,试利用栈给出将次序改变为3y-*ay2↑/-的操作步骤。(可用X代表扫描该字符串函数中顺序取一字符进栈的操作,用S代表从栈中取出一个字符加到新字符串尾的出栈的操作)。例如:ABC变为BCA,则操作步骤为XXSXX。X:进栈S:出栈XSXXXSSSXXSXXSXXSSSS7、跟踪以下代码,显示每次调用后队列中的内容。InitQueue(qu);EnQueue(qu,'A');EnQueue(qu,'B);EnQueue(qu,'C);EnQueue(qu,x;EnQueue(qu,x;EnQueue(qu,'D);EnQueue(qu,'E);EnQueue(qu,'F);EnQueue(qu,x)EnQueue(qu,'G);EnQueue(qu,X)EnQueue(qu,X)EnQueue(qu,X)解答：InitQueue(qu);队列为空EnQueue(qu,'A');队列为AEnQueue(qu,'B);队列为ABEnQueue(qu,'C);队列为ABCEnQueue(qu,x;队列为ABCxEnQueue(qu,x;队列为ABCxxEnQueue(qu,'D);队列为ABCxxDEnQueue(qu,'E);队列为ABCxxDEEnQueue(qu,'F);队列为ABCxxDEFEnQueue(qu,x)队列为ABCxxDEFxEnQueue(qu,'G);队列为ABCxxDEFxGEnQueue(qu,X)队列为ABCxxDEFxGXEnQueue(qu,X)队列为ABCxxDEFxGXXEnQueue(qu,X)队列为ABCxxDEFxGXXX8、假设Q[0..10]是一个线性队列,初始状态为front=rear=0,画出做完下列操作后队列的头尾指针的状态变化情况,若不能入队,请指出其元素,并说明理由。d,e,b,g,h入队d,e出队i,j,k,l,m入队n,o,p入队解答：d,e,b,g,h入队d e b g h Frd,e出队b g h