数据结构习题集(包含全部答案)精编版

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

2、度取决于（）A.问题白规模B待处理数据的初态C. A和B6 . 一个算法应该是（）。A.程序B.问题求解步骤的描述C .要满足五个基本特性D . A和C.7 .下面关于算法说法错误的是（）A.算法最终必须由计算机程序实现B.为解决某问题的算法与为该问题编写的程序含义是相同的C.算法的可行性是指指令不能有二义性D.以上几个都是错误的8 .以下与数据的存储结构无关的术语是（）。A.循环队列 B. 链表 C. 哈希表D.栈9 .在下面的程序段中，对x的赋值语句的频度为（）for （i=0;i<n;i+ ）for（j=0;j<n;j+）x=x+1;A. 2n B . n C. n2 D .

3、 log 2n10 .以下数据结构中，（）是非线性数据结构A.树 B .字符串 C .队列 D .栈11 .下列数据中，（）是线性数据结构。A.哈夫曼树 B.有向无环图C.二叉排序树D.栈12 .以下属于逻辑结构的是（）。A.顺序表 B. 哈希表C.有序表D. 单链表二、填空题1、 是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储、加工和处理，是对能够有效的输人到计算机中并且能够被计算机处理的符号的总称。（数据、数据）2 、数据元素是数据的,有些情况下也称为元素、结点、顶点、记录 等。（基本单位）3、 是数据不可分割的最小单元，是具有独立含义的最小标识单位。23例如构成一个数据元

4、素的字段、域、属性等都可称之为。 （数据项、数据项）4 、数据的逻辑结构是指数据之间的。逻辑结构是从 上描述数据， 它与具体存储无关，是独立于计算机的。因此逻辑结构可以看作是从具体问题抽象出来的。 （逻辑关系、逻辑关系、数学模型）5 、 数据 的 指 数 据元素 及 其关系在计算机 存储器内的表示。是逻辑结构在计算机里的实现， 也称之为映像。（存储结构、存储结构）6 、 数据逻辑结构可以分为四种基本的类型，结构中的元素除了仅仅只是同属于一个，不存在什么关系。 （集合、集合）7 、数据逻辑结构的四种基本类型中，中的元素是一种一对一的关系， 这种结构的特征是：若结构是非空集，则有且只有一个开始结点

5、和一个终端结点，并且所有结点最多只能有一个直接前驱和一个直接后继。（线性结构）8 、数据逻辑结构的四种基本类型中，中的元素是一种一对多的关系。 （树形结构）9 、图型结构或图状结构是一种的关系。在这种逻辑结构中，所有结点均可以有多个前驱和多个后继。（多对多）10 、 有时也可将树型结构、集合和图型结构称为， 这样数据的逻辑结构就可以分为和 两大类。 （非线性结构、线性结构、非线性机构）11 、 方式是指逻辑上相邻的结点被存储到物理上也相邻的存储单元中。 这种存储结构只存储结点的数值，不存储结点之间的关系，结点之间的关系是通过存储单元的相邻关系隐含的表示出来的。（顺序存储）12 、 方式是种存储

6、方法， 不要求逻辑上相邻的结点在物理上也相邻，即数据元素可以存储在任意的位置上。（链式存储）13 、 方式是利用结点关键字的值直接计算出该结点存储单元地址，然后将结点按某种方式存人该地址的一种方法。（散列存储或哈希存储）14 、所谓算法（Algorithm ）是对特定问题求解步骤的一种描述，它是指令的其中每个指令表示一个或多个操作。算法的五个重要特性是、 、 和 。 （有限序列、有穷性、确定性、可行性、输入、输出）15、算法的 性是指算法必须能够在执行有限个步骤之后结束，并且每个步骤都必须在有穷的时间内完成。（有穷性）16、算法的 性是指算法中的每一个步骤必须是有明确定义的，不允许有模棱两可的

7、解释，也不允许有多义性。并且，在任何条件下，算法只能有惟一的一条执行路径，即只要输人是相同的就只能得到的输出结果。（确定性、相同）17 、 算法的 性又称为算法的能行性， 是指算法中描述的操作是可以通过已经实现的基本运算执行有限次来实现。（可行性）18 、 判断一个算法的好坏主要以下几个标准：、 、 、。 （正确性、可读性、健壮性、时间效率和空间效率）19 、算法分析是对一种算法所消耗的计算机资源的估算，其中包括计算机的长短和 的大小。 （运行时间、所占据空间）20 、空间复杂度（SPaceComPlexity ）也是度量一个算法好坏的标准，它所描述的是算法在运行过程中所占用的大小。 （存储空

8、间）三、判断题1 .顺序存储方式只能用于存储线性结构。(X)2 .数据元素是数据的最小单位。(X)3 .算法的优劣与算法描述语言无关，但与所用计算机有关。(X)4 健壮的算法不会因非法的输入数据而出现莫名其妙的状态。()5数据的逻辑结构是指各元素之间的逻辑关系，是根据用户需要而建立的。6数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、结点、数据域。()7 数据的物理结构是指数据在计算机中实际的存储形式。()8 具有存取任一元素的时间相等这一特点的存储结构称为随机存取结构。9 .算法实际上就是程序，程序也一定是算法。(X)10 .在顺序存储结构中，有时也存储数据结构中元素之间的关系。

9、(X)11 .顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(X)12 . 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。()13 .数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的储存结构。(X)14 . 判断一个算法的好坏主要以下几个标准：正确性、有穷性、健壮性和可行性。(X)15算法的时间复杂度T( n) =O(f(n) 表示随问题规模n 的增大，算法执行时间的增长率与函数f(n) 的增长率相同。()四、综合题1 .用大O形式表示下面算法的时间复杂度：for (i=0 ; i <nn； i 十十)for(j=0 ; j < n；

10、j + + )Aij=i*j；2 写出下面算法的时间复杂度：i = 0;s=0；while(s <n) i+；s+=i;3写出以下算法的时间复杂度：for (i =0； i <m; i + + )for (j = 0 ; j <t; j + + )cij=0；for (i=0 ； i < nn； i + + )for ( j=o; j<t; j+)for(k=0; k<n； k+ + )ci j +=a i k *bkj;4写出下面算法的时间复杂度：i=1;while (i < = n)i=i*3;5求下面函数中各条语句的频度和算法的时间复杂度：pri

11、me (int n ) int i=2；while (n%i)! =0& &i<sqrt(n)i+；if (i >sqrt(n)printf(" d d is a prime number.n"，n)；elseprintf(" d d is not a prime number.n"， n)；1 .该算法的时间复杂度为：O(mx n)02 .该算法的时间复杂度为：O(/)3 .该算法的时间复杂度为：O(mx nxt)。4 .该算法的时间复杂度为：log 3(n) 05 .该算法的时间复杂度为：O(/)。6 .将下列函数，按它们

12、在n-8时的无穷大阶数，从小到大排序。n, n-n3+7n5, nlogn, 2 n/2, n 3, logn, n 1/2+logn, (3/2)n, ,n!, n2+logn从/、至ij大歹！J为：logn, n1/2+logn, n, nlogn, n2+logn , n3, n-n 3+7n5, 2n/2, (3/2) n, n!,第二章 线性表一、选择题1 .在一个长度为n的顺序表中删除第i个元素(0<i<=n)时，需要向前移 动 ( ) 个元素。A n-i B n-i+1 C n-i-1 D i+12从一个具有n 个元素的线性表中查找其值等于x 的结点时，在查找成功(

13、) 个元素结点。A n/2 B n C (n-1)/2D (n +1)/23 对一个具有n 个元素的线性表，建立其单链表的时间复杂度为( ) 。A O(n) B O(1) C O(n 个结点及其前驱，则采用( ) 存储 C 单循环链表D 顺序表9一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6 个元素的存储地址是()。A 98B 100 C 102 D 10610.在顺序存储的线性表(aian)中，删除任意一个结点所需移动结点的平均移动次数为()A n B n 2C (n-1)/2 D ( n l ) /211 在线性表的下列存储结构中，读取第i 个元素花费的时间最少

14、的是()。A 单链表B 双链表C 循环链表D 顺序表12 若某链表中最常用的操作为在最后一个结点之后插入一个结点和删除最后一个结点，则采用()存储方式最节省时间。A 双链表B 单链表C 单循环链表D 带头结点的双 循环链表13在单链表中删除指针p 所指结点的后继结点，则执行()操作。A p->next=p->next->nextB p->next=p->nextC p=p->next->nextD p=p->next; p->next=p->next->next14在一个单链表中，已知q 所指结点是p 所指结点的前驱，若在q 和

15、 p 之间插入 s 所指的结点，则执行()操作。)D O( long 2n)4 线性表采用链式存储时，其地址( ) 。A 必须是连续的B 一定是不连续的D 连续与否均可以C 部分地址必须连续5 在一个具有n 个结点的有序单链表中插人一个新的结点，使得链表仍然有序，该算法的时间复杂度是( ) 。A O( long 2n)B O( l )6线性表是( ) 。A 一个有限序列，可以为空C 一个无限序列，可以为空7在一个长度为n 的顺序表中，向第元素时，需要向后移动( ) 个元素。A n-iB n-i 1C O( n2)D O( n)B 一个有限序列，不可以为空D 一个无限序列，不可以为空I i个位置

16、(0 1<n+1)插入一个新C n i 1 D i 18如果某链表中最常用的操作是取第方式最节省时间。A 单链表B 双向链表A s->next=p->next;p->next=s;B q->next=s; s->next=p;C p->next=s->next;s->next=p;D p->next=s; s->next=q;15在单链表中附加头结点的目的是为了（） 。A.保证单链表中至少有一个节点B.标识单链表中首结点的位置C 方便运算的实现D.说明单链表是线性表的链式存储16循环单链表的主要优点是（） 。A.不再需要头指针了

17、B 从表中任意一个结点出发都能扫描到整个链表C.已知某个结点的位置后，能够容易找到它的前驱D.在进行插入、删除操作时，能更好地保证链表不断开17非空的循环单链表L 的尾结点p 满足（） 。A p->next=NULL B p=NULLC p->next=LD p=L18在双向循环链表中, 在 p 指针所指向的结点前插入一个指针q 所指向的新结点 , 其修改指针的操作是（ ）。注 : 双向链表的结点结构为（prior,data,next） 。 供选择的答案：A p->prior=q ； q->next=p ； p->prior->next=q ； q->

18、prior=q ；B p->prior=q ； p->prior->next=q; q->next=p ； q->prior=p->prior ；C q->next=p ； q->prior=p->prior ； p->prior->next=q; p->prior=q;D q->prior=p->prior ； q->next=p ； p->prior=q ； p->prior=q ；19在双向链表存储结构中，删除p 所指的结点时须修改指针（） 。A p->prior->next

19、=p->next; p->next->prior=p->prior;B p->prior=p->prior->prior; p->prior->next=p;（删 p 的前趋 ）C p->next->prior=p; p->next=p->next->next;D p->next= p->prior->prior; p->prior= p->next->next;二、填空题1线性表（Linear List ）是最简单、最常用的一种数据结构。线性表中的元素存在着 的相互关系。

20、（ 一对一 ）2线性表中有且仅有一个开始结点，表中有且仅有一个终端结点，除开始结点外，其他每个元素有且仅有一个，除终端结点外，其他每个元素有且仅有一个。3.线性表是n （n>=0）个数据元素的 o其中n为数据元素的个数，定义为线性表的。当 n 为零时的表称为。4所谓顺序表（Sequential LISt ）是线性表的，它是将线性表中的结点按其依次存放在内存中一组连续的存储单元中，使线性表中相邻的结点存放在的存储单元中。5单链表不要求逻辑上相邻的存储单元在物理上也一定要相邻。它是分配一些的存储单元来存储线性表中的数据元素， 这些存储单元可以分散在内存中的 的位置上， 它们在物理上可以是一片

21、连续的存储单元，也可以是 的。因此在表示线性表这种数据结构时，必须在存储线性表元素的同时，也存储线性表的。6.线性表的链式存储结构的每一个结点（Node）需要包括两个部分：一部分用来存放元素的数据信息，称为结点的； 另一部分用来存放元素的指向直接后继元素的指针（ 即直接后继元素的地址信息） ，称为 或7线性链表的逻辑关系是通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不再一致，而是一种 存储结构， 又称为 。8如果将单链表最后一个结点的指针域改为存放链表中的头结点的地址值，这样就构成了。9为了能够快速地查找到线性表元素的直接前驱，可在每一个元素的结点中再增加一个指向其前驱的指针域

22、，这样就构成了。10.双向链表某结点的指针P,它所指向结点的后继的前驱与前驱的后继都是p。11在单链表中，删除指针P 所指结点的后继结点的语句是。12.在双循环链表中，删除指针 P所指结点的语句序列是P->prior->next =p->next 及 。13单链表是的链接存储表示。14可以使用表示树形结构。15 .向一个长度为n的向量的第i个元素（l <i <n+1）之前插人一个元素时，需向后移动 个元素。16 .删除一个长度为n的向量的第i个元素（iwiwn）时，需向前移动 个元素。17在单链表中，在指针P 所指结点的后面插人一个结点S 的语句序列是18 在双循

23、环链表中，在指针P 所指结点前插人指针S 所指的结点，需执行语句19 取出广义表A= （x, （a, b, c, d）中原子c的函数是。20 在一个具有n 个结点的有序单链表中插人一个新结点并使之仍然有序的时间复杂度为。21写出带头结点的双向循环链表L 为空表的条件。22线性表、栈和队列都是结构。23向栈中插人元素的操作是先移动栈针，再存人元素。1. 一对一2. 直接前驱、直接后继3. 有限序列、长度、空表4. 顺序存储结构、逻辑顺序、地址相邻5. 任意、任意、不连续、逻辑关系6. 数据域、指针域、链域7. 非顺序、非顺序映像8. 循环链表9. 双向链表10. 所指向的结点本身11. P-&g

24、t;next=p->next->next12. P->next->prior=P->prior13. 线性表14. 双链表15. n-i+116. n-i17. S->next=P->next; P->next=S18. p->prior->next=S;s->prior=p->prior;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

25、. 线性23. 顶 三、判断题1 .线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（X）2 .在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。（X）3 .顺序存储的线性表不可以随机存取。（X）4单链表不是一种随机存取结构。（）5顺序存储结构线性表的插入和删除运算所移动元素的个数与该元素的位置无关。（X）6 .顺序存储结构是动态存储结构，链式存储结构是静态存储结构。（x）7 .线性表的长度是线性表所占用的存储空间的大小。（X）8 .双循环链表中，任意一结点的后继指针均指向其逻辑后继。（X）9 .线性表的惟一存储形式是链表。（X）1. 错误：链表存储中，结点之间可以

26、连续也可以不连续，但结点内部是连续的。2. 错误：头指针指向头结点而不是数据结点。3. 错误：顺序存储的线性表可以随机存取。4. 正确。5. 错误。6. 错误：顺序存储结构是静态存储结构，链式存储结构是动态存储结构。7. 错误：先行表的长度是线性表中结点的个数。8. 错误：注意最后一个结点。9. 错误：也可以有顺序存储的形式。第三章 栈和队列 一、选择题l . 一个栈的序列是：a, b, c, d, e,则栈的不可能输出的序列是（）。Aa，b，c，d，e B d，e，c，b，aCd，c，e，a， b D e，d，c，b，a2 .若一个栈的输人序列是1, 2, 3,，n,输出序列的第一个元素是n

27、,则第 k 个输出元素是（） 。A k B n-k-1 C n-k+1 D 不确定3 .判定一个栈S （最多有n个元素）为空的条件是（）。A . S->top ! = 0 B. S->top= =0 C . S->top!=n D . S->top= =n4 .判定一个栈S （最多有n个元素）为满的条件是（）。A S->top!=0 B S->top= =0 C S->top!=nD S->top= =n5向一个栈顶指针为top 的不带头结点的链栈中插人一个*S 结点的时候，应当执行语句（） 。A top->next=S ；B S->

28、next=top ； top=S；C . S->next =top->next ； top->next =S; D. S->next =top ； top=S->next；6向一个带头结点、栈顶指针为top 的链栈中插人一个*S 结点的时候，应当执行语句（） 。A top->next=S ；B S->next=top ； top=S；C S->next=top->next ； top->next=S ； D S->next=top ； top=S->next ；7 .判定一个队列Q （最多有n个元素）为空的条件是（）。A

29、Q->rear-Q->front= =n B Q->rear-Q->front+1= =nC Q->rear = = Q->front D Q->rear +1= = Q->front8 .判定一个队列Q （最多有n个元素）为满的条件是（）。A Q->rear-Q->front= =n B Q->rear-Q->front+1= =nC Q->rear = = Q->front D Q->rear +1= = Q->front9 .判定一个循环队列Q （最多有n个元素）为空的条件是（）。A Q-&g

30、t;rear = = Q->front B Q->rear = = Q->front lC Q->front= =（Q->rear +1） n D Q->front= =（Q->rear -1） n10 .判定一个循环队列Q （最多有n个元素）为满的条件是（）。A Q->rear = = Q->front B Q->rear = = Q->front lC Q->front= =（Q->rear +1） n D Q->front= =（Q->rear -1） n11在一个链队列中，假定front 和 re

31、ar 分别为头指针和尾指针，则插入一个结点 *S 的操作是（） 。A . front =front->nextB. S->next=rear ； rear=SC. rear->next=S ; rear=S D . S->next=front ； front =S12在一个链队列中，假定front 和 rear 分别为头指针和尾指针，删除一个结点的操作是（） 。A front=front->nextB rear=rear->nextC . rear->next=frontD. front->next = rear13 .栈与队列都是（）。A.链式

32、存储的线性结构B .链式存储的非线性结构C 限制存取点的线性结构D 限制存取点的非线性结构14 若进栈序列为l ， 2， 3， 4，则（）不可能是一个出栈序列。A 3，2，4，1 B l ，2，3，4C4，2，3，1 D 4，3，2，l15 在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区， 主机将要输出的数据依次写人该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个（）结构。A 堆栈B 队列C 数组D 线性表I. C2.C 3.B 4.D5. B6.C7.C 8.A 9.A10. CII. C 12. A 13. C 14. C 15. B二、填空回1栈（

33、 stack ）是限定在一端进行插人或删除操作的线性表。在栈中，允许插人和删除操作的一端称为，而另一端称为 。不含元素的栈称为。2在栈的运算中，栈的插人操作称为或 ，栈的删除操作称为或 。3根据栈的定义，每一次进栈的元素都在原之上，并成为新的；每一次出栈的元素总是当前的 ，因此最后进栈的元素总是 ， 所以栈也称为线性表， 简称为 表。4栈是一种操作受到限制的线性表，是一种特殊的线性表，因此栈也有和 两种存储结构， 分别称为 和 _5当栈满的时候，再进行人栈操作就会产生，这种情况的溢出称为 ；当栈空的时候，如果再进行出栈操作，也会 ，这种情况下的溢出称为。6栈的链式存储结构简称为，是一种 。7人

34、们日常计算用到的表达式都被称为，这是由于这种算术表达式的运算符被置于两个操作数中间。8 计算机中通常使用， 这是一种将运算符置于两个操作数后面的算术表达式。这种表达式是由波兰科学家谢维奇提出的，因此又称为9 .队列（QueuR也是一种,但它与栈不同，队列中所有的插人均限定在表的一端进行，而所有的删除则限定在表的另一端进行。允许插人的一端称为 ，允许删除的一端称为 。10队列的特点是，因此队列又被称为 的线性表，或称为 表。11队列的 又称为 ，是用一组地址连续的存储单元依次存放队列中的元素。12 由于队列中的元素经常变化，对于队列的删除和插人分别在队头和队尾进行，因此需要设置两个指针分别指向和

35、 ，这两个指针又称为和 。13 循环顺序队列（Circular SequenceQueue经常简称为,它是将存储顺序队列的存储区域看成是一个首尾相连的一个环，即将队首和队尾元素连接起来形成一个环形表。首尾相连的状态是通过数学上的来实现的。14 在算法或程序中，当一个函数直接调用自己或通过一系列语句间接调用自己的时候，则称这个函数为，也称为。函数直接调用自己，则称为； 当一个函数通过另一个函数来调用自己则称为。15 在循环队列中规定：当 Q->rear= =Q->front 的时候循环队列为， 当（Q->rear+1） %MAXSIZ&front的时候循环队列为 16用

36、链表方式表示的队列称为。17.已知栈的输人序列为1, 2, 3,，n,输出序列为al, a2,，an,符合a2= =n 的输出序列共有。18一个栈的输人序列是12345，则栈的输出序列为43512 是 （填是否可能） 。19一个栈的输人序列是12345，则栈的输出序列为12345是 （填是否可能） 。20设sq1 maxsize 为一个顺序存储的栈，变量top 指示栈顶元素的位置，则作入栈操作的条件是。21设sq1 maxsize 为一个顺序存储的栈，变量top 指示栈顶元素的位置，如果把栈顶元素弹出并送到 X中，则需执行语句 o22栈的特性是。23对栈进行退栈时的操作是先取出元素，后移动。2

37、4.设s1 . max为一个顺序存储的栈，变量top指示栈顶位置，栈为满的条件是 。25设链栈的栈顶指针为top ，则栈非空的条件是。26已知循环队列用数组data1.n 存储元素值，用f， r 分别作为头尾指针，则当前元素个数为。27在一个循环队列中，队首指针指向队首元素的位置。 （前一个或后一个）28队列中允许进行删除的一端称为。29链队列实际上是一个同时带有头指针和尾指针的单链表（1 n） ，尾指针指向该单链表的第个元素。30设双向链表链列为lq ， lq 的头指针为lq.Front ，尾指针为lq.Rear ，则队列为空的条件是。31 从循环队列中删除一个元素，其操作是先取出一个元素，

38、后移动 32队列中允许进行插入的一端称为。1. 表尾、栈顶、栈底、空栈2. 进栈、入栈、退栈、出栈3. 栈顶元素、栈顶元素、栈顶元素、最先出栈、后进先出、LIFO4. 顺序、链式、顺序栈、链栈5. 溢出、上溢、溢出、下溢6. 链栈、特殊的单链表7. 中缀表达式8. 后缀表达式、波兰式9. 特殊的线性表、队尾、队头10. 先进先出、先进先出、FIFO11. 顺序存储结构、顺序队列12. 队头元素、队尾元素、队头指针、队尾指针13. 循环队列、取模运算14. 递归函数、自调用函数、直接递归调用、间接递归调用15. 空、满16. 链队列17. n-118. 不可能的19. 可能的20. top!=m

39、axsize21. x=sqtop; top=top-122. 先进后出23. 栈顶指针24. top=max25. top!=nil26. （n+r-f）mod n27. 前一个28. 队首29. n30. lq->front=lq->rear31. 栈顶指针32. 队尾三、判断题1栈和队列都是限制存取点的线性结构。（）2不同的入栈和出栈组合可能得到相同输出序列。（）3消除递归一定要用栈。（）4循环队列是顺序存储结构。（）5循环队列不会产生溢出。（）6循环队列满的时候rear= =front 。 （）7在对链队列（带头结点）做出队操作时不会改变front 指针的值。（）1. 正确

40、。2. 错误：不同的入栈和出栈组合得到不同输出序列。3. 错误：某些情况如尾递归可以转换为递推的形式。4. 正确。5. 错误：循环队列不会产生假溢出。6. 错误。7. 正确。四、综合题1设有 4 个元素A、 B、 C 和 D 进栈，给出它们所有可能的出栈秩序。可能的出栈序列：（共 14 个）ABCDABDCACBDACDBADCBBACDBADCBCADBCDABDCACBADCBDACDBADCBA不可能的出栈序列：（共 10 个）ADBCBDACCABD CADB CDABDABC DACB DBAC DBCA DCAB习题四一、选择项l 空串与空格串（） 。A 相同B 不相同C 可能相同

41、D 无法确2.设有两个中S1与S2,求用S2在S1中首次出现位置的运算称作（）<A 连接B 求子串C 模式匹配D 判子串3串与普通的线性表相比较，它的特殊性体现在（） 。A 顺序的存储结构B 链接的存储结构C 数据元素是一个字符D 数据元素可以任意4设有串S= Computer ，则其子串的数目是（） 。A 36 B 37 C 8D 91. B 2. C3. C 4. B二、境空题1 .用是由零个或多个字符组成的 通常记作：s= "cl , c2, cn"（n=>0）,其中，S称为;用中的Ci （1<=i<=n）可以是字母、数字 字格或其他字符。用双

42、引号括起来的部分是即串 S 的内容。2串中字符的个数称为串的。3不含有任何字符的串称为，它的长度为 。4 由一个或多个空格构成的串称为， 它的长度为。5串中任意多个连续字符组成的子序列称为该串的；包含的串称为主串。6字符在序列中的序号称为该字符在串中的。7 两个字符串相等是指两个字符串的，也就是说这两个字符串不仅，而且对应位置上的字符也。8 两个串的比较实际上是的比较。 两个串从第一个位置上的字符开始进行比较，当第一次出现大的串为大，若比较过程中出现一个字符串结束的情况，则另一个串为。9 串的 就是把串所包含的字符序列， 依次存人连续的存储单元中去。10 有些计算机系统中为了充分利用存储空间，

43、允许一个存储单元可以存放多个字符，串的这种存储方式是一种。11 串的 是以存储单元为存储单位， 一个存储单元中只存放 。在这种情况下，即使一个存储单元能存放多个字符，这时候也只存放。12 串在非紧缩方式下，串长度的存储是隐式的，即串的长度。13 一些计算机是以字节为存取单位，恰好一个字符占用一个字节，自然 形 成 了 每 个 存 储 单 元 存 放 的 分 配 方 式 ， 这 种 方 式 就 是 一 种。这种方式一般不需要存放 的存储单元，而需要以程序中各变量值所、的字符为结束符。14 串的链式存储结构是将存储区域分成一系列大小相同的结点，每个结点有两个城：域和 域。其中 域用于存放数据， 域

44、用于存放下一个结点的指针。15 子串定位StrIndex （s ， t） ，也称为 ，是返回串 t 在 s 主串中的位置。1. 有限序列、串名、串值2. 长度3. 空串、零4. 空格串、空格的个数5. 子串、子串6. 位置7. 值相等、长度相等、相等8. ASCII 码、 ASCII 码、较大者9. 顺序存储结构10. 紧缩式存储方式11. 非紧缩存储方式、一个字符、一个字符12. 串所占用的存储单元的个数13. 一个字符、单字节存储方式、串长、不包含14. 数据、指针、数据、指针15. 模式匹配三、判断回1 .子用是主审中字符构成的有限序列。（X）2 . KMPT法的最大特点是指示主审的指针

45、不需要回溯3 串中的元素只能是字符。（）4.用中的元素只可能是字母。（X）5串是一种特殊的线性表。（）6串中可以包含有空白字符。（）7.用的长度不能为零。（X）8两个串相等必有串长度相同。（）9两个串相等则各位置上字符必须对应相等。（）习题五一、选择题l 数组常用的两种基本操作是（） 。A.建立与查找B .删除与查找C .插人与索引D.查找与修改2对稀疏矩阵进行压缩存储，常用的两种方法是（） 。A.二元组和散列表B.三元组表和十字链表C 三角矩阵和对角矩阵.对角矩阵和十字链表3采用稀疏矩阵的三元组表形式进行压缩存储，若要完对三元组表进行成转置，只要将行和列对换，这种说法（） 。A.正确B.错误

46、 C .无法确定 D .以上均不对4一个广义表的表头总是一个广义表，这种说法（） 。A 正确B 错误C 无法确定D 以上均不。D 以上均不对5一个广义表的表尾总是一个广义表，这种说法（A 正确B 错误C 无法确定6广义表（a） 的表头是（）。A （） B a7广义表（ a） ）的表尾是（） 。A （）B a8 .广义表（a）, a）的表头是（A （） B a9 .广义表（a）, a）的表尾是（A （ ） B a10 .广义表（a, b, c）的表头是（A a B （ a）11 .广义表（a, b, c）的表尾是（ A b， cB （ b， c）C （ a）C （ a） ）。C （ a）。C （

47、 a）。C a， b）。C a b， cD（a） ）D（a） ）D（a） ）D （a） ）D （b， c）D （a，b，c）12.广义表 A满足 Head （） = Tail （） , WJ A为（）B （ （）4. B5. A9. C10. AC （ （）， （） D （ （），A （）， （）1. D2. B3. B6. C7. A8. C11. B 12. B二、填空题1 .数组（array ）是n （n>1）个 的有序组合，数组中的数据是按顺序存储在一块的存储单元中。2数组中的每一个数据通常称为， 用下标区分，其中下标的个数由数组的决定。3由于计算机内存中的存储单元是一个一维的存

48、储结构，因此对于多维数组要想按顺序存储到计算机存储单元中就必须有一个排列顺序问题。对于二维数组，有两种排列形式：一种是；另一种是 。4 对于需要压缩存储的矩阵可以分为和 。 对那些具有相同值元素或零元素在矩阵中分布具有一定规律的矩阵，我们称之为；而对于那些零元素数目远远多于非零元素数目，并且非零元素的分布没有规律的矩阵称为。5 .在一个n阶方阵a中，若元素满足性质：aj=aji （0<=i, j<=n-l ）,则称 A 为 n 阶 。6采用顺序存储结构表示三元组表（Trope Table） ，以实现对稀疏矩阵的一种压缩存储形式，称为，简称 表。7 . 运算是矩阵运算中最基本的一项，

49、它是将一个m*n的矩阵变成另外一个n*m 的矩阵，同时使原来矩阵中元素的行和列的位置互换而值保持不变。8 .广义表是n （n>=0）个元素的序列。记作：A= （al, a2,，an）,其中 ， A 是 广 义 表 的 ， n 是 它 的 ， 当 n=0 的 时 候 称 为9在一个非空的广义表中，其元素ai 可以是某一确定类型的单个元素，称为 ，也可以又是一个广义表，称为 。10广义表的定义是一种递归的定义，广义表是一种递归的数据结构。当广义表非空的时候，称第一个元素a1 为广义表A 的 ，称其余元素组成的表（a2, a3,，an）是A的11广义表的深度一般定义为广义表元素，或者说是广义表

50、。 利 用 递 归 的 定 义 ， 广 义 表 的 深 度 就 是 所 有 子 表 中1. 相同类型数据、地址连续2. 数组元素、数组元素、维数3. 以行序为主、以列序为主4. 特殊矩阵、稀疏矩阵、特殊矩阵、稀疏矩阵5. 对称矩阵6. 三元组顺序表、三元组7. 矩阵转置8. 名称、长度、空表9. 原子、子表10. 表头、表尾11. 最大的层数、括号的重数、最大深度加1三、判断题1 十字链表不是顺序存储结构。（）2三元组表不是一个随机存取结构。（）3稀疏矩阵压缩存储后，必然会失去随机存取功能。（）4若一个广义表的表头为空表，则此广义表也为空表。（）5广义表是线性表的推广，是一类线性数据结构。（）

51、6任何一个非空广义表，其表头可能是单元素或广义表，其表尾必定是广义表。 （）7. 一个稀疏矩阵Am*n采用三元组形式表示，若把三元组中有关行下标与列 下标的值互换，并把 m和n的值互换，则就完成了 Am*n的转置运算。（8数组中每个元素必定具有相同的数据类型。（）9线性表是广义表的特例。（）10如果广义表中的每个元素都是原子，则广义表便成为线性表。（）11 广义表中原子个数即为广义表的长度。（）12广义表最大子表的深度为广义表的深度。（）13广义表中元素最大的层数称为广义表的深度。（）14广义表是一种多层次结构。（）15广义表是一种线性结构。（）16广义表是一种共享结构。（）17广义表是一种递

52、归结构。（）18广义表是一种单链表结构。（）1. 正确：十字链表是链接存储结构。2. 正确： 具有存取任一元素的时间相等这一特点的存储结构称为随机存取结构，三元组表存储矩阵的时候，要访问第i 行 j 列元素必须扫描三元组表，显然查找三元组表前面的元素与后面元素所耗费的时间不同，因此三元组表不是一个随机存取结构。3. 正确：随机存取结构是指存取任一元素的时间相等这一特点的存储结构，对稀疏矩阵压缩存储所用的存储结构是十字链表和三元组，而这两种存储结构都不是随机存取结构。4. 错误：如广义表L=（）,（A, B） 为非空，而表头为空表。5. 错误：广义表是线性表的推广，是一类非线性数据结构。6. 正确：表尾的定义是除表头元素以外其余元素（可以为空）构成的表，所以必定是广义表。7. 错误：应该在互换行列后再按照行优先重新存储。8. 正确。9. 正确。10. 正确。11. 错误：广义表中元素个数为广义表的长度。12. 错误：广义表最大子表的深度加1 为广义表的深度。13. 正确。14. 正确。15. 错误：广义表是一种非线性结构。16. 正确。17. 正确。18. 正确：注意单链表结构不一定是线性的。第六章 树和二叉树一、选择题l 在二叉树后序遍历中，任一个结点均在其子女结点后面，这种说法 （） 。A.正确 B .不正确 C .无法判断 D .以上均不对2