2022年数据结构题库归纳 .pdf

第一章绪 论一，选择题1组成数据的基本单位是（C ）A数据项B数据类型C数据元素D数据变量2数据结构是研究数据的（C ）以及它们之间的相互关系。A理想结构，物理结构B理想结构，抽象结构C物理结构，逻辑结构D抽象结构，逻辑结构3算法分析的两个主要方面是（D ）A正确性和简单性B可读性和文档性C数据复杂性和程序复杂性D时间复杂度和空间复杂度4算法分析的目的是（C ）。A 找出数据结构的合理性B研究算法中的输入和输出的关系C分析算法的效率以求改进D分析算法的易懂性和文档性5.算法的时间复杂度取决于（C ）A问题的规模B. 待处理数据的初态C. A和 B以上都不是6一个算法应该是（B）。A程序B问题求解步骤的描述C要满足五个基本特性DA 和 C.7.下面关于算法说法错误的是（D ）A算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的8从逻辑上可以把数据结构分为（C ）两大类。A动态结构、静态结构B顺序结构、链式结构C线性结构、非线性结构D初等结构、构造型结构9程序段for(i=n-1;i=1;i-)for(j=1;jAj+1)Aj 与 Aj+1 对换；其中 n 为正整数，则最后一行的语句频度在最坏情况下是（D ）A O（n）B O(nlogn)C.O(n3)DO(n2)10连续存储设计时，存储单元的地址（A ）。A一定连续B一定不连续C不一定连续D部分连续，部分不连续二，判断题1数据结构的抽象操作的定义与具体实现有关。( )2数据结构是数据对象与对象中数据元素之间关系的集合。（ ）3在顺序存储结构中，有时也存储数据结构中元素之间的关系。( )4数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用的需要建立的。（ ）5算法和程序原则上没有区别，在讨论数据结构是两者是通用的。( )6同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数都相等。( )7数据的逻辑结构与数据元素本身的内容和形式无关。（ ）8算法的优劣与算法描述语言无关，但与所用计算机有关。()9健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（ ）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 22 页 - - - - - - - - - 10算法可以用不同的语言描述，如果用C 语言或 PASCAL 语言等高级语言来描述，则算法实际上就是程序了。()三，填空1数据的物理结构包括数据元素的表示和数据元素间关系的表示。2.对于给定的n 个元素, 可以构造出的逻辑结构有集合， 线性结构， 树形结构，_图状结构或网状结构_四种。3一个数据结构在计算机中表示（又称映像）称为存储结构。4抽象数据类型的定义仅取决于它的一组_逻辑特性 _，而与_在计算机内部如何表示和实现_无关，即不论其内部结构如何变化，只要它的_数学特性_不变，都不影响其外部使用。5线性结构中元素之间存在一对一关系,树形结构中元素之间存在一对多关系 ,图形结构中元素之间存在多对多关系。6一个算法有5 个特性:有穷性、确定性、可行性，有零个或多个输入、有一个或多个输出。7已知如下程序段for （i= n；i=1;i+）语句 1x:=x+1；语句 2for( j=n;j=i ;j+)语句 3y:=y+1;语句 4语句 1 执行的频度为n+1；语句 2 执行的频度为n；语句3 执行的频度为n(n+3)/2；语句 4 执行的频度为n(n+1)/2。8在下面的程序段中， 对的赋值语句的频度为_O(n3)_ （表示为 n的函数） /1+ （1+2+（1+2+3）+（1+2+n）=n(n+1)(n+2)/6for(i1;i=n;i+)for(j;j=i;j+)for(k 1;k=j;j+) delta ；9.计算机执行下面的语句时，语句s 的执行次数为_(n+3)(n-2)/2_ 。for(i=l；i=i;j-)s;10.下面程序段的时间复杂度为_O(n)_。(n1)sum=1 ；for(i=0;sumn;i+)sum+=1;四，应用题11什么是数据 ? 它与信息是什么关系?信息就是消息。信息的特征为：可识别、可存储、可变换、可处理、可传递、可再生、可压缩、可利用、可共享。什么是数据？数据(data)是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。在计算机中， 信息必须以数据的形式出现。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 22 页 - - - - - - - - - 2 什么是数据结构? 数据结构是研究什么内容的学科？有关数据结构的讨论涉及哪三方面?数据结构是指数据以及相互之间的关系。记为：数据结构= D, R。其中， D 是某一数据对象， R是该对象中所有数据成员之间的关系的有限集合。数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象及对象间的关系和施加于对象的操作等的学科。有关数据结构的讨论一般涉及以下三方面的内容：（1）数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构；（2）数据成员及其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构；（3）施加于该数据结构上的操作。数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储不是一码事，是与计算机存储无关的。 因此， 数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型，是数据的应用视图。数据的存储结构是逻辑数据结构在计算机存储器中的实现（亦称为映像），它是依赖于计算机的， 是数据的物理视图。数据的操作是定义于数据逻辑结构上的一组运算，每种数据结构都有一个运算的集合。例如搜索、插入、删除、更新、排序等。3评价一个好的算法，从哪几方面考虑？评价好的算法有四个方面。一是算法的正确性；二是算法的易读性；三是算法的健壮性；四是算法的时空效率（运行）。4若将数据结构定义为一个二元组（D，R）, 说明符号D，R应分别表示什么？D是数据元素的有限集合，R是 D上数据元素之间关系的有限集合。5解释算法与程序的区别？算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性：有穷性确定性可行性有输入有输出算法与程序的联系和区别：（1）算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个程序不一定满足有穷性。例如，操作系统，只要整个系统不遭破坏，它将永远不会停止。因此，操作系统不是一个算法。（2）程序中的指令必须是机器可执行的，而算法中的指令则无此限制。（3）算法是面向功能的，通常用面向过程的方式描述；程序可以用面向对象方式搭建它的框架。（4）算法与数据结构是相辅相承的：解决某一特定类型问题的算法可以选定不同的数据结构， 而且选择恰当与否直接影响算法的效率。反之， 一种数据结构的优劣由各种算法的执行来体现。6 有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种结构。（1）A= （K，R），其中：K=a ，b，c，d，e，f，gR=rr= a，b， b，c， c，d， d，e， e，f， f，g名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 22 页 - - - - - - - - - （2）B=（K，R），其中：K=a ，b，c，d，e，f，g，hR=rr= d，b， d，g， d，a， b，c， g， e， g，h， a，f（3）C=（K，R），其中：K=1 ，2，3，4，5，6R=rr=(1, 2)，(2, 3)，（ 2，4），（ 3，4），（ 3，5），（ 3，6），（ 4，5），（ 4,6） 这里的圆括号对表示两结点是双向的。（1）A 对应逻辑图形如下，它是一种线性结构。（2）B 对应逻辑图形如下，它是一种树形结构。（3）C 对应逻辑图形如下，它是一种图形结构。7 分析以下程序段的时间复杂度。（1）a=0；b=1；for（i=2；i=n；i+ ）s=a+b；b=a；a=S；（2）inti ，j，k；for（i=0；in；i+for（j=0；jn；j+cij=0 ；for（k=0；kn；k+名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 22 页 - - - - - - - - - cij=cij+aik+bkj；（1）解：语句的频度是2；语句的频度是n；语句的频度是n-1；语句的频度是n-1；语句的频度是n-1；故，该程序段的时间复杂度T（n）=2+n+3* （ n-1）=4n-1=O （n）。（2）解：语句的频度为n+1；语句作为语句循环体内的语句应该执行n 次，但语句本身要执行n+1 次，故语句的频度是n（n+1）；同理可得语句、和的频度分别是n2， n2（n+1）和 n3。该程序段所有语句的频度之和为：T（n）=2n3+3n2+2n+1其复杂度为O （n3）。8求下列算法段的语句频度及时间复杂度（1）for(i=1;i=n;i+)for(j=1; j=i; j+)x=x+1;（2）for（i=1;i=n;i+）for(j=1;j=i;j+)for(k=1;knext=hB. p-next=NILC. p-next-next=hD. p-data=-12下面关于线性表的叙述中，错误的是哪一个？（B）A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 22 页 - - - - - - - - - 3线性表是具有n 个（C）的有限序列（ n0）。A表元素B字符C数据元素D数据项4若某线性表最常用的操作是存取任一指定 序号的元素和在最后进行插入和删除运算，则利用（A）存储方式最节省时间。A顺序表B双链表C带头结点的双循环链表D单循环链表5某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D）存储方式最节省运算时间。A单链表B仅有头指针的单循环链表C双链表D仅有尾指针的单循环链表6设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用(D ) 最节省时间。A. 单链表B.单循环链表C. 带尾指针的单循环链表D.带头结点的双循环链表7在带有头结点的单链中插入一个新结点时不可能修改（A）。A 头指针B头结点指针域C 开始结点指针域D其它结点指针域8 双向链表中有两个指针域，llink和 rlink，分别指向前驱及后继，设p 指向链表中的一个结点，q 指向一待插入结点，现要求在p 前插入 q，则正确的插入为（D）。A.p-llink=q;q-rlink=p;p-llink-rlink=q;q-llink=p-llink;B. q-llink=p-llink;p-llink-rlink=q;q-rlink=p;p-llink=q-rlink;C.q-rlink=p;p-rlink=q;p-llink-rlink=q;q-rlink=p;D.p-llink-rlink=q;q-rlink=p;q-llink=p-llink;p-llink=q;9对于一个头指针为head 的带头结点的单链表，判定该表为空表的条件是（B）。Ahead=NULLBheadnext=NULLCheadnext=headDhead!=NULL10在顺序表中查找第i 个元素的时间效率最高的算法时间复杂度是（A）。AO(1)BO(n)CO(log2n)DO(n)11最好的情况下，在顺序表中按值查找一个元素的算法时间复杂度是（D ）。AO(n)BO(n)C O(log2n)DO(1)12.若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为（C ）(1=ilink=headBp-link=NILCp=NILDp= head二，判断1.链表中的头结点仅起到标识的作用。()2线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( )3顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。()4顺序存储方式只能用于存储线性结构。()5线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。( )6.线性表的特点是每个元素都有一个前驱和一个后继。( )7.取线性表的第i 个元素的时间同i 的大小有关。( )名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 22 页 - - - - - - - - - 8.循环链表不是线性表。( )9.线性表就是顺序存储的表。( )10.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( )三，填空1当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用顺序存储结构。2线性表L=（a1,a2, ,an ）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是（n-1）/2。3在一个长度为n 的顺序表中第i 个元素（ 1=inext=p-next、f-prior=p、p-next-prior=f、p-next=f。6.在双向链表结构中，若要求在 p 指针所指的结点之前插入指针为s 所指的结点， 则需执行下列语句：s-next=p ；s-prior=p-prior；p-prior=s ； s-prior-next=s；7. 顺序存储结构通过物理上相邻表示元素之间的关系 ; 链式存储结构通过指针表示元素之间的关系。8.对于双向链表 , 在两个结点之间插入一个新结点需修改的指针共4 个，单链表为2 个。9.已知指针p 指向单链表L 中的某结点，则删除其后继结点的语句是：u=p-next;p-next=u-next;free(u);, 时间复杂度是O(1) ; 。10.带头结点的双循环链表L 中只有一个元素结点的条件是L-next-next=L。四，算法设计1试写一算法在带头结点的单链表结构上实现线性表操作LOCATE （L，X）。LNode* Locate(LinkList L,int x)/ 链表上的元素查找,返回指针for(p=l-next;p&p-data!=x;p=p-next);returnp;/Locate2试写一算法在带头结点的单链表结构上实现线性表操作LENGTH （L）。int Length(LinkList L)/ 求链表的长度for(k=0,p=L;p-next;p=p-next,k+);return k;/Length3试写一算法实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1,a2, ,an）逆置为（ an,an-1, ,a1）。voidreverse(SqList&A)/ 顺序表的就地逆置名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 22 页 - - - - - - - - - for(i=0,j=A.length-1;ij;i+,j-)A.elemiA.elemj;/reverse4试写一算法，对单链表实现就地逆置void LinkList_reverse(Linklist &L)/ 链表的就地逆置;为简化算法 ,假设表长大于2p=L-next;q=p-next;s=q-next;p-next=NULL;while(s-next)q-next=p;p=q;q=s;s=s-next; / 把 L 的元素逐个插入新表表头q-next=p;s-next=q;L-next=s;/LinkList_reverse分析 :本算法的思想是,逐个地把 L 的当前元素q 插入新的链表头部,p 为新表表头 .5.设线性表A =（ a1，a2， ,an）， B=（b1,b2, ,bn），试写一个按下列规则合并A，B为线性表 C的算法，即使得C=（a1,b1, am,bm,bm+1, ,bn）当 mn 时；线性表 A，B 和 C均以单链表作存储结构，且C 表利用 A 表和 B 表中的结点空间构成。注意：单链表的长度值m 和 n 均未显式存储。void merge1(LinkList &A,LinkList &B,LinkList &C)/ 把链表 A 和 B 合并为 C,A和 B的元素间隔排列,且使用原存储空间p=A-next;q=B-next;C=A;while(p&q)s=p-next;p-next=q; / 将 B 的元素插入if(s)t=q-next;q-next=s; / 如 A 非空 ,将 A 的元素插入p=s;q=t;/while/merge1第三章栈和队列一，选择1.对于栈操作数据的原则是（B ）。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 22 页 - - - - - - - - - A. 先进先出B. 后进先出C. 后进后出D. 不分顺序2.已知输入序列为abcd 经过输出受限的双向队列后能得到的输出序列有（B ）。A. dacbB. cadbC. dbcaD. badc3.最大容量为n 的循环队列，队尾指针是rear ，队头是front ，则队空的条件是（ B ）。A. (rear+1)MODn=frontB. rear=frontCrear+1=frontD. (rear-l)MODn=front4 当利用大小为n 的数组顺序存储一个栈时，假定用top= =n 表示栈空，则向这个栈插入一个元素时首先应执行语句修改top 指针。（B ）Atop+Btop-Ctop=0Dtop5.若已知一个栈的入栈序列是1,2,3, ,n ，其输出序列为p1,p2,p3，pN, 若 pN是 n，则pi是( D ) 。A. iB. n-iC. n-i+1D. 不确定6.一个递归算法必须包括（B ）。A. 递归部分B. 终止条件和递归部分C. 迭代部分D.终止条件和迭代部分7.执行完下列语句段后，i值为：（B ）intf(intx)return(x0)? x*f(x-1):2);inti;i=f(f(1);A2B. 4C. 8D. 无限递归8.设栈 S和队列 Q的初始状态为空，元素e1，e2，e3，e4,e5和 e6 依次通过栈S，一个元素出栈后即进队列Q ，若 6 个元素出队的序列是e2，e4，e3,e6,e5,e1则栈 S的容量至少应该是(C) 。A 6B. 4C. 3D. 29.栈和队列的共同点是（C ）。A. 都是先进先出B. 都是先进后出C. 只允许在端点处插入和删除元素D. 没有共同点10.设计一个判别表达式中左，右括号是否配对出现的算法，采用（D ）数据结构最佳。A 线性表的顺序存储结构B. 队列C. 线性表的链式存储结构D. 栈11.用不带头结点的单链表存储队列时, 其队头指针指向队头结点, 其队尾指针指向队尾结点，则在进行删除操作时(D ) 。A仅修改队头指针B. 仅修改队尾指针C. 队头、队尾指针都要修改D. 队头, 队尾指针都可能要修改12.递归过程或函数调用时，处理参数及返回地址，要用一种称为（C）的数据结构。A队列B多维数组C栈D. 线性表13.假设以数组Am存放循环队列的元素 , 其头尾指针分别为front和 rear ， 则当前队列中的元素个数为（A）。A(rear-front+m)%mBrear-front+1C(front-rear+m)%mD(rear-front)%m14.循环队列存储在数组A0.m 中，则入队时的操作为（D）。A. rear=rear+1B. rear=(rear+1)mod (m-1)C. rear=(rear+1)mod mD. rear=(rear+1)mod(m+1)15.若用一个大小为6 的数组来实现循环队列，且当前rear和 front的值分别为0 和 3，当从队列中删除一个元素，再加入两个元素后，rear和 front的值分别为多少？(B)A. 1 和 5B. 2 和 4C. 4 和 2D. 5 和 1名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 22 页 - - - - - - - - - 二，判断1.任何一个递归过程都可以转换成非递归过程。（）2.只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈。（）3.队列逻辑上是一个下端和上端既能增加又能减少的线性表。（）4.循环队列也存在空间溢出问题。（）循环队列只是一个大小为maxsize的数组空间有限自然存在溢出问题5.栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（）三，填空1 栈是限定仅在表尾进行插入或删除操作的线性表。3中缀表达式3*（x+2）-5 所对应的后缀表达式为3x 2 + * 5 - ；后缀表达式“45*32+- ”的值为15。4.顺 序 栈 用 data1.n存 储 数 据 ， 栈 顶 指 针 是 top, 则值 为 x 的 元 素入 栈 的操 作 是data+top=x ； 。5 向 一 个 循 环 队 列 中 插 入 一 元 素 时 ， 需 首 先 移动队 尾 指 针 ，然 后 再 向 所指 位 置写入新插入的元素。6用下标 0 开始的 N元数组实现循环队列时，为实现下标变量M加 1 后在数组有效下标范围内循环，可采用的表达式是：M= (M+1) MODN(M+1)% N7 用长度为 n 的数组顺序存储一个栈时，若用 top= =n 表示栈空，则表示栈满的条件为top=0 。四，应用题1 链栈中为何不设置头结点?链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。2指出下列程序段的功能(1) void Demo1(SeqStack*S)int i; arr64 ; n=0 ;while ( StackEmpty(S)arrn+=Pop(S);for (i=0, i n; i+) Push(S,arri);/Demo1(1)程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在64 个以内。(2) SeqStackS1,S2,tmp;DataTypex;./ 假设栈 tmp 和 S2已做过初始化while ( ! StackEmpty (&S1)x=Pop(&S1);Push(&tmp,x);while ( ! StackEmpty(&tmp) )x=Pop( &tmp);名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 22 页 - - - - - - - - - Push(&S1,x);Push(&S2, x);(2)程序段的功能是利用tmp 栈将一个非空栈s1 的所有元素按原样复制到一个栈s2 当中去。3.试证明： 若借助栈由输入序列1,2, ,n 得到输出序列为P1,P2, ,Pn（它是输入序列的一个排列），则在输出序列中不可能出现这样的情形：存在着ijk,使 PjPkPi。如果 i j ，则对于pipj的情况，则说明要将 pj压到 pi之上，也就是在pj出栈之后pi才能出栈。这就说明，对于i j k，不可能出现 pjpkpi的输出序列。换句话说，对于输入序列1，2，3，不可能出现3，1，2 的输出序列.具体解答(提示：用反证法)：因为借助栈由输入序列1, 2, 3, , n，可得到输出序列p1, p2, p3, , pn，如果存在下标i,j, k，满足 i j k，那么在输出序列中，可能出现如下5 种情况： i 进栈， i 出栈， j 进栈， j 出栈， k 进栈， k 出栈。此时具有最小值的排在最前面pi位置，具有中间值的排在其后pj位置，具有最大值的排在pk位置，有pipj pk, 不可能出现 pj pk pi的情形； i 进栈， i 出栈， j 进栈， k 进栈， k 出栈， j 出栈。此时具有最小值的排在最前面pi位置，具有最大值的排在pj位置，具有中间值的排在最后pk位置，有 pi pk pj, 不可能出现 pj pk pi的情形； i 进栈， j 进栈， j 出栈， i 出栈， k 进栈， k 出栈。此时具有中间值的排在最前面pi位置，具有最小值的排在其后pj位置，有pj pi pk, 不可能出现pj pk pi的情形； i 进栈， j 进栈， j 出栈， k 进栈， k 出栈， i 出栈。此时具有中间值的排在最前面pi位置，具有最大值的排在其后pj位置，具有最小值的排在pk位置，有 pk pi pj,也不可能出现 pj pk pi的情形； i 进栈， j 进栈， k 进栈， k 出栈， j 出栈， i 出栈。此时具有最大值的排在最前面pi位置，具有中间值的排在其后pj位置，具有最小值的排在pk位置，有 pk pj pi,也不可能出现 pj pk pi的情形；4 举例说明顺序队的“假溢出”现象，并给出解决方案。设顺序存储队列用一维数组qm表示，其中m为队列中元素个数，队列中元素在向量中的下标从0 到 m-1。设队头指针为front ，队尾指针是rear ，约定 front指向队头元素的前一位置， rear指向队尾元素。当front等于-1 时队空， rear等于 m-1 时为队满。由于队列的性质 （“删除” 在队头而 “插入” 在队尾） ，所以当队尾指针rear等于 m-1 时，若 front不等于 -1，则队列中仍有空闲单元，所以队列并不是真满。这时若再有入队操作，会造成假“溢出”。其解决办法有二，一是将队列元素向前“平移”（占用0 至 rear-front-1）；二是将队列看成首尾相连，即循环队列（0.m-1 ）。在循环队列下，仍定义front=rear时为队空，而判断队满则用两种办法，一是用“牺牲一个单元”，即rear+1=front（准确记是（rear+1 ）%m=front，m 是队列容量）时为队满。另一种解法是“设标记”方法，如设标记 tag ，tag 等于 0 情况下，若删除时导致front=rear为队空； tag=1 情况下，若因插入导致 front=rear则为队满。五，算法设计题名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 22 页 - - - - - - - - - 1 回文是指正读反读均相同的字符序列，如 abba和abdba 均是回文， 但good 不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)根据提示，算法可设计为：/ 以下为顺序栈的存储结构定义#defineStackSize100 / 假定预分配的栈空间最多为100 个元素typedefcharDataType;/ 假定栈元素的数据类型为字符typedefstructDataType dataStackSize;inttop;SeqStack;intIsHuiwen(char*t)/ 判断 t 字符向量是否为回文，若是，返回1，否则返回0SeqStack s;inti,len;char temp;InitStack(&s);len=strlen(t);/ 求向量长度for( i=0;itop0= -1;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 22 页 - - - - - - - - - S-top1= StackSize;/top2也指出了向量空间，但由于是作为栈底，因此不会出错intEmptyStack(DblStack*S,inti) / 判栈空( 栈号i)return(i= 0 & S-top0= -1|i= 1 & S-top1=StackSize);intFullStack(DblStack*S) / 判栈满, 满时两头相遇return(S-top0= S-top1-1);voidPush(DblStack*S,inti,DataType x) / 进栈( 栈号i)if(FullStack(S )Error(Stackoverflow);/上溢、退出运行if( i= 0) S-Data+ S-top0=x;/ 栈 0 入栈if( i= 1) S-Data-S-top1=x;/栈 1入栈DataType Pop(DblStack*S,inti) / 出栈( 栈号 i)if(EmptyStack(S,i)Error(Stackunderflow);/下溢退出if(i=0)return( S-DataS-top0-);/返回栈顶元素，指针值减1if(i=1)return( S-DataS-top1+);/ 因这个栈以另一端为底，所以指针值加1。第四章串一，选择1下面关于串的的叙述中，哪一个是不正确的？（B ）A串是字符的有限序列B空串是由空格构成的串C模式匹配是串的一种重要运算D串既可以采用顺序存储，也可以采用链式存储2设有两个串p 和 q，其中 q 是 p 的子串，求q 在 p 中首次出现的位置的算法称为（C ）A求子串B联接C匹配D求串长3串的长度是指（B ）A串中所含不同字母的个数B串中所含字符的个数C串中所含不同字符的个数D串中所含非空格字符的个数4若串 S=software , 其子串的数目是（B ）。A8B37C36D9二，填空1空格串是指由空格字符（ ASCII值 32）所组成的字符串，其长度等于空格个数。2组成串的数据元素只能是_字符 。3一个字符串中任意个连续的字符组成的子序列称为该串的子串。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 22 页 - - - - - - - - - 4INDEX （DATASTRUCTURE，STR ）=5 。5设正文串长度为n，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为O(m+n)。6模式串 P=abaabcac的next 函数值序列为01122312 。7设 T 和 P是两个给定的串，在T 中寻找等于P的子串的过程称为模式匹配 ，又称 P为模式串 。第五章数组和广义表一，选择1.已知广义表L=（x,y,z ），a，（u，t ，w），从 L 表中取出原子项t 的运算是（D ） 。A. head（tail（tail（L）B. tail（head（head（tail（L）C. head（tail （head（tail （L）D. head（tail(head（tail （tail（L） ） ） ) ）2.广义表 A=(a,b,(c,d),(e,(f,g),则下面式子的值为（D ）。Head(Tail(Head(Tail(Tail(A)A. (g)B. (d)C. cD. d3. 稀疏矩阵一般的压缩存储方法有两种, 即（C ）A 二维数组和三维数组B三元组和散列C三元组和十字链表D散列和十字链表4.二 维 数 组 A 的 每 个 元 素 是 由 6 个 字 符 组 成 的 串 ， 其 行 下 标 i=0,1, ,8,列 下 标j=1,2, ,10 。若 A按行先存储，元素A8,5 的起始地址与当A按列先存储时的元素（B ）的起始地址相同。设每个字符占一个字节。A. A8,5B. A3,10C. A5,8D. A0,95.对稀疏矩阵进行压缩存储目的是（C ）。A便于进行矩阵运算B便于输入和输出C节省存储空间D降低运算的时间复杂度6.设 A是 n*n 的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组 B1.n(n+1)/2中，对上述任一元素aij(1i ，j n，且i j) 在 B中的位置为(B ) 。A. i(i-l)/2+jB. j(j-l)/2+iC. j(j-l)/2+i-1D. i(i-l)/2+j-17. AN，N是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组TN（N+1 ）/2中，则对任一上三角元素aij对应 Tk 的下标k 是（B ）。A i （i-1 ）/2+jB j （j-1 ）/2+iC i （j-i）/2+1D j （i-1 ）/2+18.设广义表 L=（a,b,c ），则L 的长度和深度分别为（C ）。A. 1 和 1B. 1 和 3C. 1 和 2D. 2 和 39.数组 A0.4,-1.-3,5.7中含有元素的个数（B ）。A 55B45C 36D1610.下面说法不正确的是(A) 。A. 广义表的表头总是一个广义表B. 广义表的表尾总是一个广义表C. 广义表难以用顺序存储结构D. 广义表可以是一个多层次的结构二，判断1 一个稀疏矩阵Am*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把 m和 n 的值互换，则就完成了Am*n的转置运算。（ ）2.从逻辑结构上看，n维数组的每个元素均属于n 个向量。（）3.稀疏矩阵压缩存储后，必会失去随机存取功能。（ ）4.对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。（ ）5.数组可看成线性结构的一种推广，因此与线性表一样可对它进行插入，删除操作。（）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 22 页 - - - - - - - - - 6.所谓取广义表的表尾就是返回广义表中最后一个元素。（）7.二维以上的数组其实是一种特殊的广义表。（）8.广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（ ）9.若一个广义表的表头为空表，则此广义表亦为空表。（）10.广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。（）四应用题1.画出下列广义表的两种存储结构图(),A,(B,(C,D),(E,F)。2.设某表 H如下：ABCXa1a2b1c1c2其中 A,B,C 为子表名， a1,a2,b1,c1,c2,x为其元素。试用广义表形式表示H,并写出运算HEAD(H) 和 TAIL(H)函数从 H中取出单元素a2 的运算；（1）H(A(a1,a2）,B(b1）,C(c1，c2）,x ）HEAD(TAIL(HEAD(H)=a2五，算法设计1 设任意 n 个整数存放于数组A(1:n) 中，试编写程序，将所有正数排在所有负数前面本题属于排序问题，只是排出正负，不排出大小。可在数组首尾设两个指针i 和 j ，i自小至大搜索到负数停止，j自大至小搜索到正数停止。然后i 和 j 所指数据交换，继续以上过程，直到i=j为止。voidArrange(in