数据结构习题集(包含全部答案).pdf

《数据结构习题集(包含全部答案).pdf》由会员分享，可在线阅读，更多相关《数据结构习题集(包含全部答案).pdf（52页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构习题集自编数据结构习题集自编第一章第一章 绪论绪论一、选择题1数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的和运算的学科。A结构B关系 C运算 D算法2在数据结构中，从逻辑上可以把数据结构分成。A动态结构和静态结构 B紧凑结构和非紧凑结构C线性结构和非线性结构 D逻辑结构和存储结构3线性表的逻辑顺序和存储顺序总是一致的，这种说法。A正确B不正确 C无法确定 D以上答案都不对4算法分析的目的是。A找出算法的合理性 B研究算法的输人与输出关系C分析算法的有效性以求改良 D分析算法的易懂性5.算法的时间复杂度取决于 A问题的规模 B 待处理数据的初态 C.A 和 B6一

2、个算法应该是。A程序B问题求解步骤的描述 C要满足五个基本特性 DA 和 C.7.下面关于算法说法错误的选项是A算法最终必须由电脑程序实现B.为解决某问题的算法与为该问题编写的程序含义是相同的C.算法的可行性是指指令不能有二义性D.以上几个都是错误的8以下与数据的存储结构无关的术语是。A循环队列 B.链表 C.哈希表D.栈9在下面的程序段中，对 x 的赋值语句的频度为fori=0;in;i+for(j=0;jn;j+)x=x+1;A 2n BnCn2 Dlog2n10以下数据结构中，是非线性数据结构A树 B字符串 C队列 D栈11.以下数据中，是线性数据结构。A哈夫曼树 B.有向无环图 C.二

3、叉排序树 D.栈12以下属于逻辑结构的是。A顺序表 B.哈希表C.有序表 D.单链表二、填空题1、_是信息的载体，是对客观事物的符号表示，它能够被电脑识别、存储、加工和处理，_是对能够有效的输人到电脑中并且能够被电脑处理的符号的总称。数据、数据 2、数据元素是数据的_，有些情况下也称为元素、结点、顶点、记录等。基本单位3、_是数据不可分割的最小单元，是具有独立含义的最小标识单位。1 1/5252例如构成一个数据元素的字段、域、属性等都可称之为_。数据项、数据项 4、数据的逻辑结构是指数据之间的_。逻辑结构是从_上描述数据，它与具体存储无关，是独立于电脑的。因此逻辑结构可以看作是从具体问题抽象出

4、来的_。逻辑关系、逻辑关系、数学模型 5、数据的_指数据元素及其关系在电脑存储器内的表示。_是逻辑结构在电脑里的实现，也称之为映像。存储结构、存储结构 6、数据逻辑结构可以分为四种基本的类型，_结构中的元素除了仅仅只是同属于一个_，不存在什么关系。集合、集合 7、数据逻辑结构的四种基本类型中，_中的元素是一种一对一的关系，这种结构的特征是：假设结构是非空集，则有且只有一个开始结点和一个终端结点，并且所有结点最多只能有一个直接前驱和一个直接后继。线性结构 8、数据逻辑结构的四种基本类型中，_中的元素是一种一对多的关系。树形结构 9、图型结构或图状结构是一种_的关系。在这种逻辑结构中，所有结点均可

5、以有多个前驱和多个后继。多对多 10、有时也可将树型结构、集合和图型结构称为_，这样数据的逻辑结构就可以分为_和_两大类。非线性结构、线性结构、非线性机构 11、_方式是指逻辑上相邻的结点被存储到物理上也相邻的存储单元中。这种存储结构只存储结点的数值，不存储结点之间的关系，结点之间的关系是通过存储单元的相邻关系隐含的表示出来的。顺序存储 12、_方式是种存储方法，不要求逻辑上相邻的结点在物理上也相邻，即数据元素可以存储在任意的位置上。链式存储 13、_方式是利用结点关键字的值直接计算出该结点存储单元地址，然后将结点按某种方式存人该地址的一种方法。散列存储或哈希存储 14、所谓算法Algorit

6、hm是对特定问题求解步骤的一种描述，它是指令的其中每个指令表示一个或多个操作。算法的五个重要特性是_、_、_、_和_。有限序列、有穷性、确定性、可行性、输入、输出15、算法的_性是指算法必须能够在执行有限个步骤之后结束，并且每个步骤都必须在有穷的时间内完成。有穷性16、算法的_性是指算法中的每一个步骤必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。并且，在任何条件下，算法只能有惟一的一条执行路径，即只要输人是相同的就只能得到_的输出结果。确定性、相同 17、算法的_性又称为算法的能行性，是指算法中描述的操作是可以通过已经实现的基本运算执行有限次来实现。可行性 18、判断一个算法的

7、好坏主要以下几个标准：_、_、_、_。正确性、可读性、健壮性、时间效率和空间效率 19、算法分析是对一种算法所消耗的电脑资源的估算，其中包括电脑_的长短和_的大小。运行时间、所占据空间 20、空间复杂度SPace ComPlexity也是度量一个算法好坏的标准，它所描述的是算法在运行过程中所占用_的大小。存储空间2 2/5252三、判断题 1顺序存储方式只能用于存储线性结构。2数据元素是数据的最小单位。3算法的优劣与算法描述语言无关，但与所用电脑有关。()4健壮的算法不会因非法的输入数据而出现莫名其妙的状态。()5数据的逻辑结构是指各元素之间的逻辑关系，是根据用户需要而建立的。6数据结构、数据

8、元素、数据项在电脑中的映像分别称为存储结构、结点、数据域。7数据的物理结构是指数据在电脑中实际的存储形式。8具有存取任一元素的时间相等这一特点的存储结构称为随机存取结构。9算法实际上就是程序，程序也一定是算法。()10.在顺序存储结构中，有时也存储数据结构中元素之间的关系。()11.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。()12.数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。()13.数据的逻辑结构说明数据元素之间的顺序关系,它依赖于电脑的储存结构。()14.判断一个算法的好坏主要以下几个标准：正确性、有穷性、健壮性和可行性。()15算法的时间复杂度

9、Tn=O(f(n)表示随问题规模 n 的增大，算法执行时间的增长率与函数 f(n)的增长率相同。四、综合题 1用大 O 形式表示下面算法的时间复杂度：fori=0；im；i 十十 forj=0；jn；j Aij=i*j；2写出下面算法的时间复杂度：i0；s=0；while(sn i+;s+=i;3写出以下算法的时间复杂度：fori0;im;iforj0;jt;j cij=0；fori=0；im；i forj=o;jt;j+fork=0；kn；k ci jai k*bkj;4写出下面算法的时间复杂度：i=1;whilein i=i*3;5求下面函数中各条语句的频度和算法的时间复杂度：3 3/52

10、52primeint n int i2；while(ni！=0isqrt(n)i+;ifisqrt(n)printf”d is a prime number.n”，n；else printf”d is not a prime number.n”，n；1.该算法的时间复杂度为：O(mn)。2.该算法的时间复杂度为：O(n)3.该算法的时间复杂度为：O(mnt)。4.该算法的时间复杂度为：log3(n)。5.该算法的时间复杂度为：O(n)。6将以下函数，按它们在 n时的无穷大阶数，从小到大排序。n,n-n3+7n5,nlogn,2n/2,n3,logn,n1/2+logn,(3/2)n,n!,n2

11、+logn从小到大排列为：logn,n1/2+logn,n,nlogn,n2+logn，n3,n-n3+7n5,2n/2,(3/2)n,n!,4 4/5252第二章第二章 线性表线性表一、选择题 1在一个长度为 n 的顺序表中删除第 i 个元素0inext=p-next-nextBp-next=p-nextCp=p-next-nextDp=p-next;p-next=p-next-next14在一个单链表中，已知 q 所指结点是 p 所指结点的前驱，假设在 q 和 p之间插入 s 所指的结点，则执行操作。5 5/5252As-next=p-next;p-next=s;Bq-next=s;s-n

12、ext=p;Cp-next=s-next;s-next=p;Dp-next=s;s-next=q;15在单链表中附加头结点的目的是为了。A保证单链表中至少有一个节点B标识单链表中首结点的位置C方便运算的实现D说明单链表是线性表的链式存储16循环单链表的主要优点是。A不再需要头指针了B从表中任意一个结点出发都能扫描到整个链表C已知某个结点的位置后，能够容易找到它的前驱D在进行插入、删除操作时，能更好地保证链表不断开17非空的循环单链表 L 的尾结点 p 满足。Ap-next=NULLBp=NULLCp-next=LDp=L18在双向循环链表中,在 p 指针所指向的结点前插入一个指针 q 所指向的

13、新结点,其修改指针的操作是()。注:双向链表的结点结构为(prior,data,next)。供选择的答案：A p-prior=q；q-next=p；p-prior-next=q；q-prior=q；B p-prior=q；p-prior-next=q;q-next=p；q-prior=p-prior；Cq-next=p；q-prior=p-prior；p-prior-next=q;p-prior=q;Dq-prior=p-prior；q-next=p；p-prior=q；p-prior=q；19在双向链表存储结构中，删除 p 所指的结点时须修改指针。Ap-prior-next=p-next;p

14、-next-prior=p-prior;Bp-prior=p-prior-prior;p-prior-next=p;(删 p 的前趋)Cp-next-prior=p;p-next=p-next-next;Dp-next=p-prior-prior;p-prior=p-next-next;二、填空题1线性表Linear List是最简单、最常用的一种数据结构。线性表中的元素存在着_的相互关系。一对一2线性表中有且仅有一个开始结点，表中有且仅有一个终端结点，除开始结点外，其他每个元素有且仅有一个_，除终端结点外，其他每个元素有且仅有一个_。3线性表是 nn=0个数据元素的_。其中 n 为数据元素的

15、个数，定义为线性表的_。当 n 为零时的表称为_。4所谓顺序表Sequential LISt是线性表的_，它是将线性表中的结点按其_依次存放在内存中一组连续的存储单元中，使线性表中相邻的结点存放在_的存储单元中。5单链表不要求逻辑上相邻的存储单元在物理上也一定要相邻。它是分配一些_的存储单元来存储线性表中的数据元素，这些存储单元可以分散在内存中的_的位置上，它们在物理上可以是一片连续的存储单元，也可以是_的。因此在表示线性表这种数据结构时，必须在存储线性表元素的同时，也存储线性表的。6 6/52526线性表的链式存储结构的每一个结点Node需要包括两个部分：一部分用来存放元素的数据信息，称为结

16、点的_；另一部分用来存放元素的指向直接后继元素的指针(即直接后继元素的地址信息)，称为 _或_。7线性链表的逻辑关系是通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不再一致，而是一种_存储结构，又称为_。8如果将单链表最后一个结点的指针域改为存放链表中的头结点的地址值，这样就构成了_。9为了能够快速地查找到线性表元素的直接前驱，可在每一个元素的结点中再增加一个指向其前驱的指针域，这样就构成了_。10双向链表某结点的指针 P，它所指向结点的后继的前驱与前驱的后继都是p_。11在单链表中，删除指针 P 所指结点的后继结点的语句是_。12在双循环链表中，删除指针P 所指结点的语句序列是

17、 P-prior-nextp-next 及_。13单链表是_的链接存储表示。14可以使用_表示树形结构。15向一个长度为 n 的向量的第 i 个元素(lin+1之前插人一个元素时，需向后移动_个元素。16删除一个长度为n 的向量的第 i 个元素lin时，需向前移动_个元素。17在单链表中，在指针P 所指结点的后面插人一个结点S 的语句序列是_。18在双循环链表中，在指针 P 所指结点前插人指针 S 所指的结点，需执行语句_。19取出广义表 A x，a，b，c，d 中原子 c 的函数是_。20 在一个具有 n 个结点的有序单链表中插人一个新结点并使之仍然有序的时间复杂度为_。21写出带头结点的双

18、向循环链表 L 为空表的条件_。22线性表、栈和队列都是_结构。23向栈中插人元素的操作是先移动栈_针，再存人元素。1.一对一2.直接前驱、直接后继3.有限序列、长度、空表4.顺序存储结构、逻辑顺序、地址相邻5.任意、任意、不连续、逻辑关系6.数据域、指针域、链域7.非顺序、非顺序映像8.循环链表9.双向链表10.所指向的结点本身11.P-next=p-next-next12.P-next-prior=P-prior13.线性表7 7/525214.双链表15.n-i+116.n-i17.S-next=P-next;P-next=S18.p-prior-next=S;s-prior=p-pri

19、or;s-next=p;p-prior=s;19.head(tail(tail(head(tail(head(A)20.O(n)21.(L=L-Next)&(L=L-Prior)22.线性23.顶三、判断题1线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。()2 在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。()3顺序存储的线性表不可以随机存取。()4单链表不是一种随机存取结构。5顺序存储结构线性表的插入和删除运算所移动元素的个数与该元素的位置无关。()6顺序存储结构是动态存储结构，链式存储结构是静态存储结构。()7线性表的长度是线性表所占用的存储空间的大小。(

20、)8双循环链表中，任意一结点的后继指针均指向其逻辑后继。()9线性表的惟一存储形式是链表。()1.错误：链表存储中，结点之间可以连续也可以不连续，但结点内部是连续的。2.错误：头指针指向头结点而不是数据结点。3.错误：顺序存储的线性表可以随机存取。4.正确。5.错误。6.错误：顺序存储结构是静态存储结构，链式存储结构是动态存储结构。7.错误：先行表的长度是线性表中结点的个数。8.错误：注意最后一个结点。9.错误：也可以有顺序存储的形式。8 8/5252第三章第三章 栈和队列栈和队列一、选择题 l一个栈的序列是：a，b，c，d，e，则栈的不可能输出的序列是。Aa，b，c，d，e Bd，e，c，b

21、，a Cd，c，e，a，b De，d，c，b，a 2假设一个栈的输人序列是 1，2，3，n，输出序列的第一个元素是 n，则第 k 个输出元素是。Ak Bn-k-1 Cn-k+1 D不确定3判定一个栈 S最多有 n 个元素为空的条件是。AS-top！0BS-top=0 CS-top!=n DS-top=n4判定一个栈 S最多有 n 个元素为满的条件是。AS-top!=0 BS-top=0 CS-top!=nDS-top=n5向一个栈顶指针为top 的不带头结点的链栈中插人一个*S 结点的时候，应当执行语句。Atop-next=S；BS-next=top；top=S；CS-nexttop-next

22、；top-nextS；DS-nexttop；topS-next；6向一个带头结点、栈顶指针为top 的链栈中插人一个*S 结点的时候，应当执行语句。Atop-next=S；BS-next=top；top=S；CS-next=top-next；top-next=S；DS-next=top；top=S-next；7判定一个队列 Q最多有 n 个元素为空的条件是。AQ-rear-Q-front=n BQ-rear-Q-front+1=nCQ-rear=Q-front DQ-rear+1=Q-front8判定一个队列 Q最多有 n 个元素为满的条件是。AQ-rear-Q-front=n BQ-rear

23、-Q-front+1=n CQ-rear=Q-front DQ-rear+1=Q-front9判定一个循环队列 Q最多有 n 个元素为空的条件是。AQ-rear=Q-front BQ-rear=Q-frontl CQ-front=(Q-rear+1)n DQ-front=(Q-rear-1)n10判定一个循环队列 Q最多有 n 个元素为满的条件是。AQ-rear=Q-front BQ-rear=Q-frontlCQ-front=(Q-rear+1)n DQ-front=(Q-rear-1)n11在一个链队列中，假定 front 和 rear 分别为头指针和尾指针，则插入一个结点*S 的操作是。

24、Afrontfront-next BS-next=rear；rear=SCrear-next=S；rear=S DS-next=front；frontS12在一个链队列中，假定 front 和 rear 分别为头指针和尾指针，删除一个结点的操作是。Afront=front-next Brear=rear-next Crear-next=front Dfront-nextrear 13栈与队列都是。A链式存储的线性结构 B链式存储的非线性结构 C限制存取点的线性结构 D限制存取点的非线性结构 14假设进栈序列为 l，2，3，4，则不可能是一个出栈序列。A3，2，4，1 Bl，2，3，4C4，2，

25、3，1 D4，3，2，l9 9/5252 15在解决电脑主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写人该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个结构。A堆栈B队列 C数组 D线性表1.C2.C 3.B4.D5.B6.C7.C 8.A9.A10.C11.C12.A 13.C 14.C 15.B二、填空回1栈stack是限定在_一端进行插人或删除操作的线性表。在栈中，允许插人和删除操作的一端称为_，而另一端称为_。不含元素的栈称为_。2在栈的运算中，栈的插人操作称为_或_，栈的删除操作称为_或_。3根据栈的定义，每一次进栈的元素都在原_

26、之上，并成为新的_；每一次出栈的元素总是当前的_，因此最后进栈的元素总是_，所以栈也称为_线性表，简称为_表。4栈是一种操作受到限制的线性表，是一种特殊的线性表，因此栈也有_和_两种存储结构，分别称为_和_5当栈满的时候，再进行人栈操作就会产生_，这种情况的溢出称为_；当栈空的时候，如果再进行出栈操作，也会 _，这种情况下的溢出称为_。6栈的链式存储结构简称为_，是一种_。7人们日常计算用到的表达式都被称为_，这是由于这种算术表达式的运算符被置于两个操作数中间。8 电脑中通常使用_，这是一种将运算符置于两个操作数后面的算术表达式。这种表达式是由波兰科学家谢维奇提出的，因此又称为_9队列Queu

27、e也是一种_，但它与栈不同，队列中所有的插人均限定在表的一端进行，而所有的删除则限定在表的另一端进行。允许插人的一端称为_，允许删除的一端称为_。10队列的特点是_，因此队列又被称为_的线性表，或称为_表。11队列的_又称为_，是用一组地址连续的存储单元依次存放队列中的元素。12 由于队列中的元素经常变化，对于队列的删除和插人分别在队头和队尾进行，因此需要设置两个指针分别指向_和_，这两个指针又称为_和_。13循环顺序队列Circular Sequence Queue经常简称为_，它是将存储顺序队列的存储区域看成是一个首尾相连的一个环，即将队首和队尾元素连接起来形成一个环形表。首尾相连的状态是

28、通过数学上的_来实现的。14 在算法或程序中，当一个函数直接调用自己或通过一系列语句间接调用自己的时候，则称这个函数为，也称为_。函数直接调用自己，则称为_；当一个函数通过另一个函数来调用自己则称为_。15 在循环队列中规定：当 Q-rear=Q-front 的时候循环队列为_，1010/5252当Q-rear+1MAXSIZEfront 的时候循环队列为_。16用链表方式表示的队列称为_。17已知栈的输人序列为 1，2，3，n，输出序列为 a1，a2，an，符合a2=n 的输出序列共有_。18一个栈的输人序列是 12345，则栈的输出序列为 43512 是_填是否可能。19一个栈的输人序列是

29、 12345，则栈的输出序列为 12345 是_填是否可能。20设 sq1 maxsize为一个顺序存储的栈，变量 top 指示栈顶元素的位置，则作入栈操作的条件是_。21设 sq1 maxsize为一个顺序存储的栈，变量 top 指示栈顶元素的位置，如果把栈顶元素弹出并送到 X 中，则需执行语句_。22栈的特性是_。23对栈进行退栈时的操作是先取出元素，后移动_。24设 s1 max为一个顺序存储的栈，变量 top 指示栈顶位置，栈为满的条件是_。25设链栈的栈顶指针为 top，则栈非空的条件是_。26已知循环队列用数组 data1.n存储元素值，用 f，r 分别作为头尾指针，则当前元素个数

30、为_。27在一个循环队列中，队首指针指向队首元素的_位置。前一个或后一个28队列中允许进行删除的一端称为_。29链队列实际上是一个同时带有头指针和尾指针的单链表1 n，尾指针指向该单链表的第_个元素。30设双向链表链列为 lq，lq 的头指针为 lq.Front，尾指针为 lq.Rear，则队列为空的条件是_。31 从循环队列中删除一个元素，其操作是先取出一个元素，后移动_32队列中允许进行插入的一端称为_。1.表尾、栈顶、栈底、空栈2.进栈、入栈、退栈、出栈3.栈顶元素、栈顶元素、栈顶元素、最先出栈、后进先出、LIFO4.顺序、链式、顺序栈、链栈5.溢出、上溢、溢出、下溢6.链栈、特殊的单链

31、表7.中缀表达式8.后缀表达式、波兰式9.特殊的线性表、队尾、队头10.先进先出、先进先出、FIFO11.顺序存储结构、顺序队列12.队头元素、队尾元素、队头指针、队尾指针13.循环队列、取模运算14.递归函数、自调用函数、直接递归调用、间接递归调用15.空、满16.链队列1111/525217.n-118.不可能的19.可能的20.top!=maxsize21.x=sqtop;top=top-122.先进后出23.栈顶指针24.top=max25.top!=nil26.(n+r-f)mod n27.前一个28.队首29.n30.lq-front=lq-rear31.栈顶指针32.队尾三、判断

32、题1栈和队列都是限制存取点的线性结构。2不同的入栈和出栈组合可能得到相同输出序列。3消除递归一定要用栈。4循环队列是顺序存储结构。5循环队列不会产生溢出。6循环队列满的时候 rear=front。7在对链队列带头结点做出队操作时不会改变 front 指针的值。1.正确。2.错误：不同的入栈和出栈组合得到不同输出序列。3.错误：某些情况如尾递归可以转换为递推的形式。4.正确。5.错误：循环队列不会产生假溢出。6.错误。7.正确。四、综合题1设有 4 个元素 A、B、C 和 D 进栈，给出它们所有可能的出栈秩序。可能的出栈序列：共 14 个ABCDABDCACBDACDBADCBBACDBADCB

33、CADBCDABDCACBADCBDACDBADCBA不可能的出栈序列：共 10 个ADBCBDACCABDCADBCDABDABCDACBDBACDBCADCAB1212/5252习题四习题四一、选择项一、选择项l l空串与空格串空串与空格串。A A相同相同 B B不相同不相同 C C可能相同可能相同 D D无法确无法确定定2 2 设有两个申设有两个申S1S1与与S2S2，求串求串S2S2在在S1S1中首次出现位置的运算称作中首次出现位置的运算称作 。A A连接连接 B B求子串求子串 C C模式匹配模式匹配 D D判子串判子串3 3串与普通的线性表相比较，它的特殊性表达在串与普通的线性表相

34、比较，它的特殊性表达在。A A顺序的存储结构顺序的存储结构 B B链接的存储结构链接的存储结构 C C数据元素是一个字符数据元素是一个字符 D D数据元素可以任意数据元素可以任意4 4设有串设有串 S=S=ComputerComputer，则其子串的数目是，则其子串的数目是。A A36 B36 B37 C37 C8 D8 D9 91.B1.B2.C2.C3.C3.C4.B4.B二、境空题二、境空题1 1 串是由零个或多个字符组成的串是由零个或多个字符组成的_。通常记作：通常记作：s s“c1c1，c2c2，cncn”(n=0)(n=0)，其中，其中，S S 称为称为_；串中的；串中的 CiCi

35、1=i=n1=i=n可以是字母、数字可以是字母、数字字格或其他字符。用双引号括起来的部分是字格或其他字符。用双引号括起来的部分是_即串即串 S S 的内容。的内容。2 2串中字符的个数称为串的串中字符的个数称为串的_。3 3不含有任何字符的串称为不含有任何字符的串称为_，它的长度为，它的长度为_。4 4 由一个或多个空格构成的串称为由一个或多个空格构成的串称为_，它的长度为它的长度为_。5 5串中任意多个连续字符组成的子序列称为该串的串中任意多个连续字符组成的子序列称为该串的_；包含；包含_的串称为主串。的串称为主串。6 6字符在序列中的序号称为该字符在串中的字符在序列中的序号称为该字符在串中

36、的_。7 7两个字符串相等是指两个字符串的，也就是说这两个字符串不仅两个字符串相等是指两个字符串的，也就是说这两个字符串不仅_，而且对应位置上的字符也。，而且对应位置上的字符也。8 8两个串的比较实际上是两个串的比较实际上是_的比较。的比较。两个串从第一个位置上的两个串从第一个位置上的字符开始进行比较，当第一次出现字符开始进行比较，当第一次出现_大的串为大，假设比较过程中大的串为大，假设比较过程中出现一个字符串结束的情况，则另一个串为出现一个字符串结束的情况，则另一个串为_。9 9串的串的_就是把串所包含的字符序列，就是把串所包含的字符序列，依次存人连续的依次存人连续的存储单元中去。存储单元中

37、去。10 10有些电脑系统中为了充分利用存储空间，有些电脑系统中为了充分利用存储空间，允许一个存储单元可以存允许一个存储单元可以存放多个字放多个字符，串的这种存储方式是一种符，串的这种存储方式是一种_。11 11串的串的_是以存储单元为存储单位，是以存储单元为存储单位，一个存储单元中只一个存储单元中只存放存放_。在这种情况下，即使一个存储单元能存放多个字符，这时候。在这种情况下，即使一个存储单元能存放多个字符，这时候也只存放也只存放_。12 12串在非紧缩方式下，串长度的存储是隐式的，串在非紧缩方式下，串长度的存储是隐式的，_即串的长即串的长度。度。13 13一些电脑是以字节为存取单位，恰好一

38、个字符占用一个字节，自然一些电脑是以字节为存取单位，恰好一个字符占用一个字节，自然形形成成了了每每个个存存储储单单元元存存放放_ 的的分分配配方方式式，这这种种方方式式就就是是一一种种_。这种方式一般不需要存放。这种方式一般不需要存放 _的存储单元，而需要以程的存储单元，而需要以程序中各变量值所、的字符为结束符。序中各变量值所、的字符为结束符。1313/5252 14 14串的链式存储结构是将存储区域分成一系列大小相同的结点，串的链式存储结构是将存储区域分成一系列大小相同的结点，每个每个结点有两个城：结点有两个城：_域和域和_域。其中域。其中_域用于存放数域用于存放数据，据，_域用于存放下一个

39、结点的指针。域用于存放下一个结点的指针。15 15子串定位子串定位 StrIndex(sStrIndex(s，t)t)，也称为，也称为_，是返回串，是返回串 t t 在在 s s 主主串中的位置。串中的位置。1.1.有限序列、串名、串值有限序列、串名、串值2.2.长度长度3.3.空串、零空串、零4.4.空格串、空格的个数空格串、空格的个数5.5.子串、子串子串、子串6.6.位置位置7.7.值相等、长度相等、相等值相等、长度相等、相等8.ASCII8.ASCII 码、码、ASCIIASCII 码、较大者码、较大者9.9.顺序存储结构顺序存储结构10.10.紧缩式存储方式紧缩式存储方式11.11.

40、非紧缩存储方式、一个字符、一个字符非紧缩存储方式、一个字符、一个字符12.12.串所占用的存储单元的个数串所占用的存储单元的个数13.13.一个字符、单字节存储方式、串长、不包含一个字符、单字节存储方式、串长、不包含14.14.数据、指针、数据、指针数据、指针、数据、指针15.15.模式匹配模式匹配三、判断回三、判断回 1 1子串是主串中字符构成的有限序列。子串是主串中字符构成的有限序列。2 2KMPKMP 算法的最大特点是指示主串的指针不需要回溯。算法的最大特点是指示主串的指针不需要回溯。3 3串中的元素只能是字符。串中的元素只能是字符。4 4串中的元素只可能是字母。串中的元素只可能是字母。

41、5 5串是一种特殊的线性表。串是一种特殊的线性表。6 6串中可以包含有空白字符。串中可以包含有空白字符。7 7串的长度不能为零。串的长度不能为零。8 8两个串相等必有串长度相同。两个串相等必有串长度相同。9 9两个串相等则各位置上字符必须对应相等。两个串相等则各位置上字符必须对应相等。1414/5252习题五习题五一、选择题一、选择题 l l数组常用的两种基本操作是数组常用的两种基本操作是。A A建立与查找建立与查找 B B删除与查找删除与查找 C C插人与索引插人与索引D D查找与修改查找与修改2 2对稀疏矩阵进行压缩存储，常用的两种方法是对稀疏矩阵进行压缩存储，常用的两种方法是。A A二元

42、组和散列表二元组和散列表B B三元组表和十字链表三元组表和十字链表 C C三角矩阵和对角矩阵三角矩阵和对角矩阵 D D对角矩阵和十字链表对角矩阵和十字链表3 3采用稀疏矩阵的三元组表形式进行压缩存储，假设要完对三元组表进行采用稀疏矩阵的三元组表形式进行压缩存储，假设要完对三元组表进行成转置，只要将行和列对换，这种说法成转置，只要将行和列对换，这种说法。A A正确正确B B错误错误 C C 无法确定无法确定 D D以上均不对以上均不对4 4一个广义表的表头总是一个广义表，这种说法一个广义表的表头总是一个广义表，这种说法。A A正确正确 B B错误错误 C C无法确定无法确定 D D以上均不以上均

43、不对对5 5一个广义表的表尾总是一个广义表，这种说法一个广义表的表尾总是一个广义表，这种说法。A A正确正确 B B错误错误 C C无法确定无法确定 D D以上均不对以上均不对6 6广义表广义表(a)(a)的表头是的表头是。A A B B a aC C a a D D a a 7 7广义表广义表 a a 的表尾是的表尾是。A A B B a Ca C a a D D a a 8 8广义表广义表 a a，a a的表头是的表头是。A A B B a aC C a a D D a a 9 9广义表广义表 a a，a a的表尾是的表尾是。A A()B)B a a C Ca a D D a a 1010

44、广义表广义表a a，b b，c c的表头是的表头是。A Aa Ba B a a C Ca a，b Db D b b，c c1111广义表广义表a a，b b，c c的表尾是的表尾是。A Ab b，c c B B b b，c c C Ca ab b，c Dc D a a，b b，c c1212广义表广义表 A A 满足满足 HeadHead=Tail=Tail，则，则 A A 为为。A A B B C C ，D D ，1.D1.D2.B2.B3.B3.B4.B4.B5.A5.A6.C6.C7.A7.A8.C8.C9.C9.C10.A10.A11.B 12.B11.B 12.B二、填空题二、填空题

45、1 1数组数组arrayarray是是 n nn n1 1个个_的有序组合，数组中的数据是的有序组合，数组中的数据是按顺序存储在一块按顺序存储在一块_的存储单元中。的存储单元中。2 2数组中的每一个数据通常称为数组中的每一个数据通常称为_，_用下标区分，其中下标的用下标区分，其中下标的个数由数组的个数由数组的_决定。决定。3 3由于电脑内存中的存储单元是一个一维的存储结构，因此对于多维数组由于电脑内存中的存储单元是一个一维的存储结构，因此对于多维数组要想按顺要想按顺序存储到电脑存储单元中就必须有一个排列顺序问题。序存储到电脑存储单元中就必须有一个排列顺序问题。对于二维数组，对于二维数组，有两有

46、两种排列形式：一种是种排列形式：一种是_；另一种是；另一种是_。4 4对于需要压缩存储的矩阵可以分为对于需要压缩存储的矩阵可以分为_和和_。对那些具有对那些具有1515/5252相相同同值值元元素素或或零零元元素素在在矩矩阵阵中中分分布布具具有有一一定定规规律律的的矩矩阵阵，我我们们称称之之为为_；而对于那些零元素数目远远多于非零元素数目，并且非零元素的；而对于那些零元素数目远远多于非零元素数目，并且非零元素的分布没有规律的矩阵称为分布没有规律的矩阵称为_。5 5在一个在一个 n n 阶方阵阶方阵 a a 中，假设元素满足性质：中，假设元素满足性质：a aijija ajiji0=i0=i，j

47、=n-lj=0n=0个元素的序列。记作：个元素的序列。记作：A Aa1a1，a2a2，anan，其，其中中，A A 是是广广义义表表的的_，n n 是是它它的的_，当当 n=0n=0 的的时时候候称称为为_。9 9在一个非空的广义表中，其元素在一个非空的广义表中，其元素 a ai i可以是某一确定类型的单个元素，称可以是某一确定类型的单个元素，称为为_，也可以又是一个广义表，称为，也可以又是一个广义表，称为_。1010广义表的定义是一种递归的定义，广义表是一种递归的数据结构。当广广义表的定义是一种递归的定义，广义表是一种递归的数据结构。当广义表非空的时候，称第一个元素义表非空的时候，称第一个元

48、素 a a1 1为广义表为广义表 A A 的的_，称其余元素组成，称其余元素组成的表的表a2a2，a3a3，anan是是 A A 的的_。1111广义表的深度一般定义为广义表元素广义表的深度一般定义为广义表元素_，或者说是广义表，或者说是广义表_。利利 用用 递递 归归 的的 定定 义义，广广 义义 表表 的的 深深 度度 就就 是是 所所 有有 子子 表表 中中_。1.1.相同类型数据、地址连续相同类型数据、地址连续2.2.数组元素、数组元素、维数数组元素、数组元素、维数3.3.以行序为主、以列序为主以行序为主、以列序为主4.4.特殊矩阵、稀疏矩阵、特殊矩阵、稀疏矩阵特殊矩阵、稀疏矩阵、特殊

49、矩阵、稀疏矩阵5.5.对称矩阵对称矩阵6.6.三元组顺序表、三元组三元组顺序表、三元组7.7.矩阵转置矩阵转置8.8.名称、长度、空表名称、长度、空表9.9.原子、子表原子、子表10.10.表头、表尾表头、表尾11.11.最大的层数、括号的重数、最大深度加最大的层数、括号的重数、最大深度加 1 1三、判断题三、判断题1 1十字链表不是顺序存储结构。十字链表不是顺序存储结构。2 2三元组表不是一个随机存取结构。三元组表不是一个随机存取结构。3 3稀疏矩阵压缩存储后，必然会失去随机存取功能。稀疏矩阵压缩存储后，必然会失去随机存取功能。4 4假设一个广义表的表头为空表，则此广义表也为空表。假设一个广

50、义表的表头为空表，则此广义表也为空表。5 5广义表是线性表的推广，是一类线性数据结构。广义表是线性表的推广，是一类线性数据结构。6 6任何一个非空广义表，其表头可能是单元素或广义表，其表尾必定是广任何一个非空广义表，其表头可能是单元素或广义表，其表尾必定是广义义表表。7 7一个稀疏矩阵一个稀疏矩阵 Am*nAm*n 采用三元组形式表示，采用三元组形式表示，假设把三元组中有关行下标与假设把三元组中有关行下标与列下标的值互换，列下标的值互换，并把并把 m m 和和 n n 的值互换，的值互换，则就完成了则就完成了 Am*nAm*n 的转置运算。的转置运算。1616/52528 8数组中每个元素必定