数据结构习题集（自编）
第一章 绪论
一、选择题
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和B 6．一个算法应该是（ ）。
A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 7. 下面关于算法说法错误的是（ ）
A．算法最终必须由计算机程序实现
B.为解决某问题的算法与为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的
8．以下与数据的存储结构无关的术语是（ ）。
A．循环队列 B. 链表 C. 哈希表 D. 栈 9．在下面的程序段中，对x的赋值语句的频度为（ ）
for（i=0;i A． 2n B．n C．n2 D．log2n 10．以下数据结构中，（ ）是非线性数据结构 A．树 B．字符串 C．队列 D．栈 11. 下列数据中，（ ）是线性数据结构。 A．哈夫曼树 B.有向无环图 C. 二叉排序树 D. 栈 12．以下属于逻辑结构的是（ ）。 A．顺序表 B. 哈希表 C.有序表 D. 单链表 二、填空题 1、_______是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储、加工和处理，________是对能够有效的输人到计算机中并且能够被计算机处理的符号的总称。（数据、数据） 2、数据元素是数据的______，有些情况下也称为元素、结点、顶点、记录等。（基本单位） 3、________是数据不可分割的最小单元，是具有独立含义的最小标识单位。例如构成一个数据元素的字段、域、属性等都可称之为________。（数据项、数据项） 4、数据的逻辑结构是指数据之间的________。逻辑结构是从________上描述数据，它与具体存储无关，是独立于计算机的。因此逻辑结构可以看作是从具体问题抽象出来的______________。（逻辑关系、逻辑关系、数学模型） 5、数据的________指数据元素及其关系在计算机存储器内的表示。_________是逻辑结构在计算机里的实现，也称之为映像。（存储结构、存储结构） 6、数据逻辑结构可以分为四种基本的类型，_______结构中的元素除了仅仅只是同属于一个_________________，不存在什么关系。（集合、集合） 7、数据逻辑结构的四种基本类型中，________中的元素是一种一对一的关系，这种结构的特征是：若结构是非空集，则有且只有一个开始结点和一个终端结点，并且所有结点最多只能有一个直接前驱和一个直接后继。（线性结构） 8、数据逻辑结构的四种基本类型中，____________中的元素是一种一对多的关系。（树形结构） 9、图型结构或图状结构是一种________的关系。在这种逻辑结构中，所有结点均可以有多个前驱和多个后继。（多对多） 10、有时也可将树型结构、集合和图型结构称为__________，这样数据的逻辑结构就可以分为__________和________两大类。（非线性结构、线性结构、非线性机构） 11、____________方式是指逻辑上相邻的结点被存储到物理上也相邻的存储单元中。这种存储结构只存储结点的数值，不存储结点之间的关系，结点之间的关系是通过存储单元的相邻关系隐含的表示出来的。（顺序存储） 12、_______方式是种存储方法，不要求逻辑上相邻的结点在物理上也相邻，即数据元素可以存储在任意的位置上。（链式存储） 13、_________方式是利用结点关键字的值直接计算出该结点存储单元地址，然后将结点按某种方式存人该地址的一种方法。（散列存储或哈希存储） 14、所谓算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的其中每个指令表示一个或多个操作。算法的五个重要特性是__________、__________、__________、__________和__________。（有限序列、有穷性、确定性、可行性、输入、输出） 15、算法的_______性是指算法必须能够在执行有限个步骤之后结束，并且每个步骤都必须在有穷的时间内完成。（有穷性） 16、算法的________性是指算法中的每一个步骤必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。并且，在任何条件下，算法只能有惟一的一条执行路径，即只要输人是相同的就只能得到____________的输出结果。（确定性、相同） 17、算法的____________性又称为算法的能行性，是指算法中描述的操作是可以通过已经实现的基本运算执行有限次来实现。（可行性） 18、判断一个算法的好坏主要以下几个标准：________、________、________、_________。（正确性、可读性、健壮性、时间效率和空间效率） 19、算法分析是对一种算法所消耗的计算机资源的估算，其中包括计算机_________的长短和___________________的大小。（运行时间、所占据空间） 20、空间复杂度（SPace ComPlexity）也是度量一个算法好坏的标准，它所描述的是算法在运行过程中所占用_____________的大小。（存储空间） 三、判断题 1．顺序存储方式只能用于存储线性结构。（×） 2．数据元素是数据的最小单位。（×） 3．算法的优劣与算法描述语言无关，但与所用计算机有关。(×) 4．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。() 5．数据的逻辑结构是指各元素之间的逻辑关系，是根据用户需要而建立的。（） 6．数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、结点、数据域。（） 7．数据的物理结构是指数据在计算机中实际的存储形式。（） 8．具有存取任一元素的时间相等这一特点的存储结构称为随机存取结构。（） 9．算法实际上就是程序，程序也一定是算法。(×) 10. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。(×) 11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(×) 12. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。() 13. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。 (×) 14. 判断一个算法的好坏主要以下几个标准：正确性、有穷性、健壮性和可行性。(×) 15．算法的时间复杂度T（n）=O(f(n))表示随问题规模n的增大，算法执行时间的增长率与函数f(n)的增长率相同。（） 四、综合题 1．用大O形式表示下面算法的时间复杂度： for（i=0；i＜m；i十十） for（j=0；j＜n；j＋＋） A[i][j]=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＋＋） c[i][j]=0； for（i=0；i＜m；i＋＋） for（j=o; j for（k=0；k＜n；k＋＋） c［i］［j］＋＝a［i］［k］*b[k][j]; 4．写出下面算法的时间复杂度： i=1; while（i＜＝n） i=i*3; 5．求下面函数中各条语句的频度和算法的时间复杂度： prime（int n） ｛ int i＝2； while ((n％i）！=0＆＆i＜sqrt(n) ) i++; if（i＞sqrt(n) ) printf（”％d is a prime number.＼n”，n）； else printf（”％d is not a prime number.＼n”，n）；｝ 1. 该算法的时间复杂度为：O(m×n)。 2. 该算法的时间复杂度为：O(n) 3. 该算法的时间复杂度为：O(m×n×t)。 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 +logn 从小到大排列为：logn, n1/2+logn, n, nlogn, n2+logn，n3, n-n3+7n5, 2 n/2, (3/2)n, n!, 第二章 线性表 一、选择题 1．在一个长度为n的顺序表中删除第i个元素（0 2．从一个具有n个元素的线性表中查找其值等于x的结点时，在查找成功的情况下，需平均比较( )个元素结点。 A．n/2 B．n C．(n-1)/2 D．(n +1)/2 3．对一个具有n个元素的线性表，建立其单链表的时间复杂度为( )。 A．O(n) B．O(1) C．O(n2） D．O（long2n） 4．线性表采用链式存储时，其地址( )。 A． 必须是连续的 B．一定是不连续的 C．部分地址必须连续 D．连续与否均可以 5．在一个具有n个结点的有序单链表中插人一个新的结点，使得链表仍然有序，该算法的时间复杂度是( )。 A．O（long2n） B．O（l） C．O（n2） D．O（n） 6．线性表是( )。 A．一个有限序列，可以为空 B．一个有限序列，不可以为空 C．一个无限序列，可以为空 D．一个无限序列，不可以为空 7．在一个长度为n的顺序表中，向第i个位置（0一1＜n＋1）插入一个新元素时，需要向后移动( )个元素。 A．n-i B．n-i＋1 C．n－i－1 D．i＋1 8．如果某链表中最常用的操作是取第i个结点及其前驱，则采用( )存储方式最节省时间。 A．单链表 B．双向链表 C．单循环链表 D．顺序表 9．一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（）。 A．98 B．100 C．102 D．106 10．在顺序存储的线性表（a1??an）中，删除任意一个结点所需移动结点的平均移动次数为( ) A．n B．n／2 C．(n-1)/2 D．（n＋l）/2 11．在线性表的下列存储结构中，读取第i个元素花费的时间最少的是（）。 A．单链表 B．双链表 C．循环链表 D．顺序表 12．若某链表中最常用的操作为在最后一个结点之后插入一个结点和删除最后一个结点，则采用（）存储方式最节省时间。 A．双链表 B．单链表 C．单循环链表 D．带头结点的双循环链表 13．在单链表中删除指针p所指结点的后继结点，则执行（ ）操作。 A．p->next=p->next->next B．p->next=p->next C．p=p->next->next D．p=p->next; p->next=p->next->next 14．在一个单链表中，已知q所指结点是p所指结点的前驱，若在q和p之间插入s所指的结点，则执行（ ）操作。 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．不再需要头指针了 B．从表中任意一个结点出发都能扫描到整个链表 C．已知某个结点的位置后，能够容易找到它的前驱 D．在进行插入、删除操作时，能更好地保证链表不断开 17．非空的循环单链表L的尾结点p满足（ ）。 A．p->next=NULL B．p=NULL C．p->next=L D．p=L 18．在双向循环链表中,在p指针所指向的结点前插入一个指针q所指向的新结点,其修改指针的操作是( )。 注:双向链表的结点结构为(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； 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=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）是最简单、最常用的一种数据结构。线性表中的元素存在着__________的相互关系。（一对一） 2．线性表中有且仅有一个开始结点，表中有且仅有一个终端结点，除开始结点外，其他每个元素有且仅有一个__________，除终端结点外，其他每个元素有且仅有一个______。 3．线性表是n（n>=0）个数据元素的________。其中n为数据元素的个数，定义为线性表的__________。当n为零时的表称为_________。 4．所谓顺序表（Sequential LISt）是线性表的__________，它是将线性表中的结点按其____________依次存放在内存中一组连续的存储单元中，使线性表中相邻的结点存放在____________的存储单元中。 5．单链表不要求逻辑上相邻的存储单元在物理上也一定要相邻。它是分配一些_______的存储单元来存储线性表中的数据元素，这些存储单元可以分散在内存中的_________的位置上，它们在物理上可以是一片连续的存储单元，也可以是__________的。因此在表示线性表这种数据结构时，必须在存储线性表元素的同时，也存储线性表的。 6．线性表的链式存储结构的每一个结点（Node）需要包括两个部分：一部分用来存放元素的数据信息，称为结点的_________；另一部分用来存放元素的指向直接后继元素的指针(即直接后继元素的地址信息)，称为________或____________。 7．线性链表的逻辑关系是通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不 再一致，而是一种_________存储结构，又称为__________。 8．如果将单链表最后一个结点的指针域改为存放链表中的头结点的地址值，这样就构成了______________。 9．为了能够快速地查找到线性表元素的直接前驱，可在每一个元素的结点中再增加一个指向其前驱的指针域，这样就构成了___________。 10．双向链表某结点的指针P，它所指向结点的后继的前驱与前驱的后继都是p_______。 11．在单链表中，删除指针P所指结点的后继结点的语句是____________。 12．在双循环链表中，删除指针P所指结点的语句序列是P->prior->next＝p->next及__________。 13．单链表是___________的链接存储表示。 14．可以使用___________表示树形结构。 15．向一个长度为n的向量的第i个元素(l≤i≤n+1）之前插人一个元素时，需向后移动__________个元素。 16．删除一个长度为n的向量的第i个元素（l≤i≤n）时，需向前移动_______个元素。 17．在单链表中，在指针P所指结点的后面插人一个结点S的语句序列是__________。 18．在双循环链表中，在指针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->next=p->next->next 12. P->next->prior=P->prior 13. 线性表 14. 双链表 15. n-i+1 16. n-i 17. S->next=P->next; P->next=S 18. 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. 线性 23. 顶 三、判断题 1．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。(×) 2．在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。(×) 3．顺序存储的线性表不可以随机存取。(×) 4．单链表不是一种随机存取结构。（） 5．顺序存储结构线性表的插入和删除运算所移动元素的个数与该元素的位置无关。6．顺序存储结构是动态存储结构，链式存储结构是静态存储结构。(×) 7．线性表的长度是线性表所占用的存储空间的大小。(×) 8．双循环链表中，任意一结点的后继指针均指向其逻辑后继。(×) 9．线性表的惟一存储形式是链表。(×) 1. 错误：链表存储中，结点之间可以连续也可以不连续，但结点内部是连续的。 2. 错误：头指针指向头结点而不是数据结点。 3. 错误：顺序存储的线性表可以随机存取。 4. 正确。 5. 错误。 6. 错误：顺序存储结构是静态存储结构，链式存储结构是动态存储结构。 7. 错误：先行表的长度是线性表中结点的个数。 8. 错误：注意最后一个结点。 9. 错误：也可以有顺序存储的形式。 ×)( 第三章 栈和队列 一、选择题 l．一个栈的序列是：a，b，c，d，e，则栈的不可能输出的序列是（）。 A．a，b，c，d，e B．d，e，c，b，a C．d，c，e，a，b D．e，d，c，b，a 2．若一个栈的输人序列是1，2，3，?，n，输出序列的第一个元素是n，则第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= =n 4．判定一个栈S（最多有n个元素）为满的条件是（ ）。 A．S->top!=0 B．S->top= =0 C．S->top!=n D．S->top= =n 5．向一个栈顶指针为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； 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．Q->rear-Q->front= =n B．Q->rear-Q->front+1= =n C．Q->rear = = Q->front D．Q->rear +1= = Q->front 8．判定一个队列Q（最多有n个元素）为满的条件是（）。 A．Q->rear-Q->front= =n B．Q->rear-Q->front+1= =n C．Q->rear = = Q->front D．Q->rear +1= = Q->front 9．判定一个循环队列Q（最多有n个元素）为空的条件是（ ）。 A．Q->rear = = Q->front B．Q->rear = = Q->front＋l C．Q->front= =(Q->rear +1)％n D．Q->front= =(Q->rear -1)％n 10．判定一个循环队列Q（最多有n个元素）为满的条件是（ ）。 A．Q->rear = = Q->front B．Q->rear = = Q->front＋l C．Q->front= =(Q->rear +1)％n D．Q->front= =(Q->rear -1)％n 11．在一个链队列中，假定front和rear分别为头指针和尾指针，则插入一个结点*S的操作是（ ）。 A．front＝front->next B．S->next=rear；rear=S C．rear->next=S；rear=S D．S->next=front；front＝S 12．在一个链队列中，假定front和rear分别为头指针和尾指针，删除一个结点的操作是（ ）。 A．front=front->next B．rear=rear->next C．rear->next=front D．front->next＝rear 13．栈与队列都是（ ）。 A．链式存储的线性结构 B．链式存储的非线性结构 C．限制存取点的线性结构 D．限制存取点的非线性结构 14．若进栈序列为l，2，3，4，则（ ）不可能是一个出栈序列。 A．3，2，4，1 B．l，2，3，4 C．4，2，3，1 D．4，3，2，l 15．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写人该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个 （ ）结构。 A．堆栈 B．队列 C．数组 D．线性表 1. C 2. C 3. B 4. D 5. B 6. C 7. C 8. A 9. A 10. C 11. C 12. A 13. C 14. C 15. B 二、填空回 1．栈（stack）是限定在________一端进行插人或删除操作的线性表。在栈中，允许插人和删除操作的一端称为__________，而另一端称为_________。不含元素的栈称为_______。 2．在栈的运算中，栈的插人操作称为________或________，栈的删除操作称为_________或__________。 3．根据栈的定义，每一次进栈的元素都在原___________之上，并成为新的__________；每一次出栈的元素总是当前的_____________，因此最后进栈的元素总是__________，所以栈也称为___________线性表，简称为____________表。 4．栈是一种操作受到限制的线性表，是一种特殊的线性表，因此栈也有__________和_________________两种存储结构，分别称为______________和____________。 5．当栈满的时候，再进行人栈操作就会产生____________，这种情况的溢出称为___________；当栈空的时候，如果再进行出栈操作，也会_____________，这种情况下的溢出称为__________________。 6．栈的链式存储结构简称为____________，是一种__________________。 7．人们日常计算用到的表达式都被称为____________，这是由于这种算术表达式的运算符被置于两个操作数中间。 8．计算机中通常使用___________，这是一种将运算符置于两个操作数后面的算术表达式。这种表达式是由波兰科学家谢维奇提出的，因此又称为__________________。 9．队列（Queue）也是一种___________，但它与栈不同，队列中所有的插人均限定在表的一端进行，而所有的删除则限定在表的另一端进行。允许插人的一端称为_________，允许删除的一端称为_______________。 10．队列的特点是_________，因此队列又被称为_______________．的线性表，或称为_________________表。 11．队列的_________又称为__________，是用一组地址连续的存储单元依次存放队列中的元素。 12．由于队列中的元素经常变化，对于队列的删除和插人分别在队头和队尾进行，因此需要设置两个指针分别指向__________和__________，这两个指针又称为__________和_____________。 13．循环顺序队列（Circular Sequence Queue）经常简称为___________，它是将存储顺序队列的存储区域看成是一个首尾相连的一个环，即将队首和队尾元素连接起来形成一个环形表。首尾相连的状态是通过数学上的_________________来实现的。 14．在算法或程序中，当一个函数直接调用自己或通过一系列语句间接调用自己的时候，则称这个函数为，也称为____________。函数直接调用自己，则称为__________；当一个函数通过另一个函数来调用自己则称为_________________。 15．在循环队列中规定：当Q->rear= =Q->front的时候循环队列为___________， 当（Q->rear+1）％MAXSIZE＝front的时候循环队列为____________________。 16．用链表方式表示的队列称为____________________。 17．已知栈的输人序列为1，2，3，?，n，输出序列为a1，a2，?，an，符合a2= =n的输出序列共有__________________。 18．一个栈的输人序列是12345，则栈的输出序列为43512是________（填是否可能）。 19．一个栈的输人序列是12345，则栈的输出序列为12345是_________（填是否可能）。 20．设sq[1．．maxsize]为一个顺序存储的栈，变量top指示栈顶元素的位置，则作入栈操作的条件是______________。 21．设sq[1．．maxsize]为一个顺序存储的栈，变量top指示栈顶元素的位置，如果把栈顶元素弹出并送到X中，则需执行语句______________。 22．栈的特性是__________________。 23．对栈进行退栈时的操作是先取出元素，后移动_________。 24．设s[1．．max]为一个顺序存储的栈，变量top指示栈顶位置，栈为满的条件是____。 25．设链栈的栈顶指针为top，则栈非空的条件是___________。 26．已知循环队列用数组data[1...n]存储元素值，用f，r分别作为头尾指针， 则当前元素个数为____________。 27．在一个循环队列中，队首指针指向队首元素的________位置。（前一个或后一个） 28．队列中允许进行删除的一端称为_______________。 29．链队列实际上是一个同时带有头指针和尾指针的单链表（1．．n），尾指针指向该单链表的第___________个元素。 30．设双向链表链列为lq，lq的头指针为lq.Front，尾指针为lq.Rear，则队列为空的条件是____________。 31．从循环队列中删除一个元素，其操作是先取出一个元素，后移动______________。 32．队列中允许进行插入的一端称为_________。 1. 表尾、栈顶、栈底、空栈 2. 进栈、入栈、退栈、出栈 3. 栈顶元素、栈顶元素、栈顶元素、最先出栈、后进先出、LIFO 4. 顺序、链式、顺序栈、链栈 5. 溢出、上溢、溢出、下溢 6. 链栈、特殊的单链表 7. 中缀表达式 8. 后缀表达式、波兰式 9. 特殊的线性表、队尾、队头 10. 先进先出、先进先出、FIFO 11. 顺序存储结构、顺序队列 12. 队头元素、队尾元素、队头指针、队尾指针 13. 循环队列、取模运算 14. 递归函数、自调用函数、直接递归调用、间接递归调用 15. 空、满 16. 链队列 17. n-1 18. 不可能的 19. 可能的 20. top!=maxsize 21. x=sq[top]; top=top-1 22. 先进后出 23. 栈顶指针 24. top==max 25. top!=nil 26. (n+r-f)mod n 27. 前一个 28. 队首 29. n 30. lq->front==lq->rear 31. 栈顶指针 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个） ABCD ABDC ACBD ACDB ADCB BACD BADC BCAD BCDA BDCA CBAD CBDA CDBA DCBA 不可能的出栈序列：（共10个） ADBC BDAC CABD CADB CDAB DABC DACB DBAC DBCA DCAB 习题四 一、选择项 l．空串与空格串（ ）。 A．相同 B．不相同 C．可能相同 D．无法确定 2．设有两个申S1与S2，求串S2在S1中首次出现位置的运算称作（ ）。 A．连接 B．求子串 C．模式匹配 D．判子串 3．串与普通的线性表相比较，它的特殊性体现在（ ）。 A．顺序的存储结构 B．链接的存储结构 C．数据元素是一个字符 D．数据元素可以任意 4．设有串S=‘Computer’，则其子串的数目是（ ）。 A．36 B．37 C．8 D．9 1. B 2. C 3. C 4. B 二、境空题 1．串是由零个或多个字符组成的____________。通常记作：s＝“c1，c2，?，cn”(n=>0)，其中，S称为________；串中的Ci（1<=i<=n）可以是字母、数字 字格或其他字符。用双引号括起来的部分是_________．即串S的内容。 2．串中字符的个数称为串的________。 3．不含有任何字符的串称为_________，它的长度为___________。 4．由一个或多个空格构成的串称为____________，它的长度为___________。 5．串中任意多个连续字符组成的子序列称为该串的____________；包含___________的串称为主串。 6．字符在序列中的序号称为该字符在串中的________________。 7．两个字符串相等是指两个字符串的，也就是说这两个字符串不仅__________，而且对应位置上的字符也。 8．两个串的比较实际上是_________的比较。两个串从第一个位置上的字符开始进行比较，当第一次出现_____________大的串为大，若比较过程中出现一个字符串结束的情况，则另一个串为_________________。 9．串的_______________就是把串所包含的字符序列，依次存人连续的存储单元中去。 10．有些计算机系统中为了充分利用存储空间，允许一个存储单元可以存放多个字 符，串的这种存储方式是一种__________________。 11．串的______________是以存储单元为存储单位，一个存储单元中只存放__________。在这种情况下，即使一个存储单元能存放多个字符，这时候也只存放________________。 12．串在非紧缩方式下，串长度的存储是隐式的，__________即串的长度。 13．一些计算机是以字节为存取单位，恰好一个字符占用一个字节，自然形成了每个存储单元存放__________的分配方式，这种方式就是一种__________。这种方式一般不需要存放____________的存储单元，而需要以程序中各变量值所、的字符为结束符。 14．串的链式存储结构是将存储区域分成一系列大小相同的结点，每个结点有两个城：____________域和________域。其中___________域用于存放数据，___________域用于存放下一个结点的指针。 15．子串定位StrIndex (s，t)，也称为_______，是返回串t在s主串中的位置。 1. 有限序列、串名、串值 2. 长度 3. 空串、零 4. 空格串、空格的个数 5. 子串、子串 6. 位置 7. 值相等、长度相等、相等 8. ASCII码、ASCII码、较大者 9. 顺序存储结构 10. 紧缩式存储方式 11. 非紧缩存储方式、一个字符、一个字符 12. 串所占用的存储单元的个数 13. 一个字符、单字节存储方式、串长、不包含 14. 数据、指针、数据、指针 15. 模式匹配 三、判断回 1．子串是主串中字符构成的有限序列。（×） 2．KMP算法的最大特点是指示主串的指针不需要回溯。（ 3．串中的元素只能是字符。（ ） 4．串中的元素只可能是字母。（×） 5．串是一种特殊的线性表。（ ） 6．串中可以包含有空白字符。（ ） 7．串的长度不能为零。（×） 8．两个串相等必有串长度相同。（ ） 9．两个串相等则各位置上字符必须对应相等。（ ） ） 习题五 一、选择题 l．数组常用的两种基本操作是（ ）。 A．建立与查找 B．删除与查找 C．插人与索引 D．查找与修改 2．对稀疏矩阵进行压缩存储，常用的两种方法是（ ）。 A．二元组和散列表 B．三元组表和十字链表 C．三角矩阵和对角矩阵 D．对角矩阵和十字链表 3．采用稀疏矩阵的三元组表形式进行压缩存储，若要完对三元组表进行成转置，只要将行和列对换，这种说法（ ）。 A．正确 B．错误 C． 无法确定 D．以上均不对 4．一个广义表的表头总是一个广义表，这种说法（ ）。 A．正确 B．错误 C．无法确定 D．以上均不对 5．一个广义表的表尾总是一个广义表，这种说法（ ）。 A．正确 B．错误 C．无法确定 D．以上均不对 6．广义表((a))的表头是（ ）。 A．（ ） B．a C．（a） D．（（a）） 7．广义表（（a））的表尾是（ ）。 A．（） B．a C．（a） D．（（a）） 8．广义表（（a），a）的表头是（ ）。 A．（ ） B．a C．（a） D．（（a）） 9．广义表（（a），a）的表尾是（ ）。 A．( ) B．a C．（a） D．（（a）） 10．广义表（a，b，c）的表头是（ ）。 A．a B．（a） C．a，b D．（b，c） 11．广义表（a，b，c）的表尾是（ ）。 A．b，c B．（b，c） C．a．b，c D．（a，b，c） 12．广义表A满足Head（）= Tail（），则A为（）。 A．（） B．（（）） C（（），（）） D．（（），（），（）） 1. D 2. B 3. B 4. B 5. A 6. C 7. A 8. C 9. C 10. A 11. B 12. B 二、填空题 1．数组（array）是n（n＞1）个__________的有序组合，数组中的数据是按顺序存储在一块______________的存储单元中。 2．数组中的每一个数据通常称为_____，________用下标区分，其中下标的个数由数组的________________决定。 3．由于计算机内存中的存储单元是一个一维的存储结构，因此对于多维数组要想按顺 序存储到计算机存储单元中就必须有一个排列顺序问题。对于二维数组，有两种排列形式：一种是___________；另一种是_____________。 4．对于需要压缩存储的矩阵可以分为__________和_________。对那些具有相同值元素或零元素在矩阵中分布具有一定规律的矩阵，我们称之为___________；而对于那些零元素数目远远多于非零元素数目，并且非零元素的分布没有规律的矩阵称为_____________。 5．在一个n阶方阵 a中，若元素满足性质：aij＝aji（0<=i，j<=n-l），则称A为n阶_______。 6．采用顺序存储结构表示三元组表(Trope Table)，以实现对稀疏矩阵的一种压缩存储形式，称为______________，简称________________表。 7．________________运算是矩阵运算中最基本的一项，它是将一个m*n的矩阵变成另外一个n*m的矩阵，同时使原来矩阵中元素的行和列的位置互换而值保持不变。 8．广义表是n（n>=0）个元素的序列。记作：A＝（a1，a2，?，an），其中，A是广义表的_________，n是它的_________，当n=0的时候称为____________。 9．在一个非空的广义表中，其元素ai可以是某一确定类型的单个元素，称为__________，也可以又是一个广义表，称为_____________________。 10．广义表的定义是一种递归的定义，广义表是一种递归的数据结构。当广义表非空的时候，称第一个元素a1为广义表A的__________，称其余元素组成的表（a2，a3，?，an）是A的______________。 11．广义表的深度一般定义为广义表元素_________，或者说是广义表___________。利用递归的定义，广义表的深度就是所有子表中_________________________。 1. 相同类型数据、地址连续 2. 数组元素、数组元素、维数 3. 以行序为主、以列序为主 4. 特殊矩阵、稀疏矩阵、特殊矩阵、稀疏矩阵 5. 对称矩阵 6. 三元组顺序表、三元组 7. 矩阵转置 8. 名称、长度、空表 9. 原子、子表 10. 表头、表尾 11. 最大的层数、括号的重数、最大深度加1 三、判断题 1．十字链表不是顺序存储结构。（ ） 2．三元组表不是一个随机存取结构。（ ） 3．稀疏矩阵压缩存储后，必然会失去随机存取功能。（ ） 4．若一个广义表的表头为空表，则此广义表也为空表。（ ） 5．广义表是线性表的推广，是一类线性数据结构。（ ） 6．任何一个非空广义表，其表头可能是单元素或广义表，其表尾必定是广义表。 （ ） 7．一个稀疏矩阵Am*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。（ ） 8．数组中每个元素必定具有相同的数据类型。（ ） 9．线性表是广义表的特例。（ ） 10．如果广义表中的每个元素都是原子，则广义表便成为线性表。（） 11．广义表中原子个数即为广义表的长度。（） 12．广义表最大子表的深度为广义表的深度。（） 13．广义表中元素最大的层数称为广义表的深度。（） 14．广义表是一种多层次结构。（） 15．广义表是一种线性结构。（） 16．广义表是一种共享结构。（） 17．广义表是一种递归结构。（） 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．在二叉树先序遍历中，任一个结点均在其子女结点前面，这种说法（ ）。 A．正确 B．不正确 C．无法判断 D．以上均不对 3．设深度为h的二叉树上只有叶子结点和同时具有左右子树的结点，则此类二叉树中所包含的结点数目至少为（ ）。 A．2h B．2h C．2h＋1 D．2h-l 4．二叉村第k层上最多有（ ）个结点。 A．2k B．2k-1 C．2k-1 D．2k+1 5．二叉树的深度为k，则二叉树最多有（ ）个结点。 A．2k B．2k-1 C．2k-1 D．2k -1 6．设某一二叉树先序遍历为abdec，中序遍历为dbeac，则该二叉树后序遍历的顺序是（ ）。 A．abdec B．debac C．debca D．abedc 7．设某一二叉树中序遍历为badce，后序遍历为bdeca，则该二叉树先序遍历的顺序是（ ）。 A．adbec B．decab C．debac D．abode 8．将一棵树T转换为一棵二叉树T2，则T的先序遍历是T2的（ ）。 A．先序 B．中序 C．后序 D．无法确定 9．将一棵树T转换为一棵二叉树T2，则T的后序遍历是T2的（ ）。 A．先序 B．中序 C．后序 D．无法碉定 l0．树最适合于用来表示（ ）。 A．线性结构的数据 B．顺序结构的数据 C．元素之间无前驱和后继关系的数据 D．元素之间有包含和层次关系的数据 11．二叉树的叶子结点在先序、中序和后序遍历过程中的相对秩序（ ）。 A．发生改变 B．不发生改变 C．无法确定 D．以上均不正确 12． 设一棵二叉树度为2的结点数是7，度为1的结点数是6，则叶子结点数是（ ）。 A．6 B．7 C．8 D．9 13．用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1．．n]中，若结点R[i]有左孩子，则其左孩子是（ ）。 A．R[2i-1] B．R[2i+1] C．R[2i] D．R[2/i] 144．用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1．．n]中，若结点R[i]有右孩子，则其右孩子是（ ）。 A．R[2i-1] B．R[2i＋l] C．R[2i] D．R[2/i] 15．一棵非空的二叉树，先序遍历与后序遍历正好相反，则该二叉树满足（ ）。 A．无左孩子 B．无右孩子 C．只有一个叶子结点 D．任意二叉树 16．设a、b为一棵二叉树的两个结点，在后序遍历中，a在b前的条件是（ ）。 A．a在b上方 B．a在b下方 C．a在b左方 D．a在b右方 17．线索二叉树是一种（ ）。 A．逻辑结构 B．线性结构 C．逻辑和线性结构 D．物理结构 18．N个结点的线索二叉树中，线索的数目是（ ）。 A．N-1 B．N＋1 C．2N D．2N－1 19．权值为｛l，2，6，8｝的四个结点构成的哈夫曼树的带权路径长度是（ ）。 A．18 B．28 C．19 D．29 20．实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉村采用（ ）存储结构。 A．二叉链表 B．广义表存储结构 C．三叉链表 D．顺序存储结构 21．对一个满二叉树，m个树叶，k个分枝结点，n个结点，则（ ）。 A．n＝m＋1 B．m+1=2n C．m＝k-1 D．n=2k+1 23．具有五层结点的二叉平衡树至少有（ ）个结点。 A．10 B．12 C．15 D．17 24．设n，m为一棵二叉树上的二个结点，在中序遍历时，n在m前的条件是（ ）。 A．n在m右方 B．n是m祖先 C．n在m左方 D．n是m子孙 25．线索二又树是一种（ ）结构。 A．逻辑 B．逻辑和物理 C．物理 D．线性 26．将一棵有100个结点的完全二又树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（ ）。 A．98 B．99 C．50 D．48 二、填空题 1．树(Tree)是n(n≥0)个结点的_____________集。 2．任何一个非空树中：有且仅有一个特定的结点，称为该树的______________的结点，___________结点之外的其余结点可分为m(m≥0)个互不相交的有限集合T1，T2，?，Tm，且其中每一个集合又是一棵树，称之为__________的______________。 3．树的__________是指一个数据元素及指向其子树的分支。通常通过一个__________来描述，在树型表示中，用一个圆圈及短线表示。 4．结点的度是指结点所拥有的________________。 5．树内各结点度的___________________为树的度。 6．度大于0的结点称为________________或______________________。 7．____________称为叶子结点，简称为叶子，又称作终端结点。 8．一个结点的____________，或者说一个结点的____________称为该结点的孩子结点，简称为孩子。 9．一个结点称为其后继结点（即孩子结点）的______________。 10．一个结点的子树中的任一结点都称为该结点的_______________。 11．从根到该结点所经分支上的所有结点称为该结点的_____________。 12．具有_____________________的结点互称为兄弟结点，简称为兄弟。 13．从根结点开始定义，根为________层，根的孩子为__________层，依次往下类推，若某结点在第k层，则其子树的根就在______________层。 14．其双亲在同一层次上的结点互称为___________________。 15．树中结点的___________称为树的深度，又称为树的高度。 16．如果树中各结点的各子树从左至右是有序排列，不可互换的，则称该树为______。 17．如果树中各结点的各子树无排列顺序，即可以互换位置，则称为该树为_________。 18．n(n≥0)棵互不相交的树的集合称为______________________。 19．二又树（Binary Tree）是结点的有限集合，这个集合或者是空，或者是由一个根结点和__________的称为______________和____________的二叉树构成。 20．二叉树第i层上最多有____________个结点。 21．深度为k的二又树最多有____________个结点(k≥l)。 22．在任意二叉树中，叶子结点的数目(即度为0的结点数)等于度为2的结点数____________。 23．一棵深度为k且具有2k-1个结点的二叉树称为__________。这类二叉树的特点是，二叉树中每一层结点的个数都是______________的个数。 24．_________是那种在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者所缺少的结点都在右边。 25．具有n个结点的完全二叉树的深度是_______________。 26．对于一棵有n个结点的完全二叉树的结点进行编号（自上而下，自左至右），则对任一结点 i（l≤i≤n），如果结点i=l，则结点i是二叉树的____________，无双亲；如果结点i>l，则其双亲Parent(i)的序号是结点_______________；如果2i≤n，则结点i的左孩子Lchild(BT,，i）是_________，否则结点i无左孩子(结点i必为叶子结点)；如果2i＋l≤n，则结点i的右孩子 RChild（BT，i）的序号是____________；否则该结点无右孩子。 27．二叉树的顺序存储结构是用_________________存储二叉树的数据元素。 28．____________是指按照某条搜索路径访问树中的某个结点，使得树中每个结点均被访问一次，而且仅被访问一次。 29．先序遍历二叉树的操作定义为：若二叉树为空，则为空操作；否则进行如下操作：访问二叉树____________；先序遍历二叉树____________；先序遍历二叉树_________。 30．中序遍历二叉树的操作定义为：若二叉树为空，则为空操作；否则进行如下操作：中序遍历二叉树__________；访问二又树__________；中序遍历二又树____________。 31．后序遍历二叉树的操作定义为：若二叉树为空，则为空操作；否则进行如下操作：后序遍历二叉树___________；后序遍历二叉树_________；访问二叉树_____________。 32．线索二叉树（Threaded Binary Tree）是充分利用二义链表的 n+1个空的指针域作为线索来标志每一个结点的________和__________信息。当某个结点有左孩子的时候，使其___________指向其左孩子，无左孩子的时候，使其左指针域指向该结点的___________；当某个结点有有孩子的时候，使其右指针域指向该结点的__________，无右孩子的时候，使其有指针域指向该结点的_____________。 33．线索二叉树的线索链表中，指向结点前驱和后继的指针称为___________；加上线索的二叉树称为_____________；对二叉树以某种次序进行遍历使其成为线索二叉树的过程称为_______________________。 34．树的存储结构常见的有____________、____________和________________。 35．树的先序遍历过程如下：若树为空，则进行空操作；若树非空，则：访问树的__________；依次先序遍历树的__________。 36．树的后序遍历过程为：若树为空，则进行空操作；若树非空，则：依次后序遍历__________；访问_________________。 37．森林的先序遍历过程为：若森林非空，则： （1）访问森林中第一棵树的___________。 （2）先序遍历第一棵树中_____________。 （3）先序遍历_______________________。 38．森林的后序遍历过程为：若森林非空，则： （l）后序遍历森林中第一棵树的_______________。 （2）访问第一棵树的_________________________。 （3）后序遍历_______________________________。 39．从树中一个结点到另一个结点之间的_________称为这两个结点的路径。 40．路径上的分支数目称为______________。 41．树的路径长度是指从树根到每一结点的__________________。 42．将树中的结点赋上一个有着某种意义的实数，称此实数为该结点的____________。 43．树的带权路径长度为树中所有叶子结点的____________。 44．哈夫曼树（Huffman Tree）又称___________。它是n个带权叶子结点构成的所有二叉树中，带权路径长度WPL__________________。 45，所谓前缀编码是指在所有对字符的编码中，任何一个字符都不是____________。 46．已知完全二叉树的第八层有8个结点，则其叶子结点数是__________________。 47．在有n个叶子结点的哈夫曼树中，总结点数是___________。 48．已知完全二又树的第7层有10个叶子结点，则整个二又树的结点数最多是__________。 49．已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为__________。 50．一棵树T采用二叉链表BT存储，如果树T中某结点为叶子结点，则在二叉链表BT中所对应的结点一定满足___________________。 51．在二叉链表中，判断某指针P所指结点为叶子结点的条件是__________。 52．若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是___________。 53．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是______________。 54．3个结点可构成___________________棵不同形态的树。 55．已知完全二叉树的第七层有8个结点，则其叶子结点数是______________. 56．将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结 点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为____________。 57．若要对某二叉排序树进行遍历，保证输出的所有结点序列按键值递增次序排列， 应对该二叉树采用_______________遍历法。 1. 有限 2. 根、根、根、子树 3. 结点、记录 4. 子树数目 5. 最大值 6. 分支结点、非终端结点 7. 度为零的结点 8. 后继结点、子树的根 9. 双亲结点 10. 子孙结点 11. 祖先结点 12. 同一双亲 13. 第一、第二、第k+1 14. 堂兄弟 15. 最大层次 16. 有序树 17. 无序树 18. 森林 19. 两棵互不相交、左子树、右子树 20. 2i-1 21. 2k-1 22. 加1 23. 满二叉树、最大结点 24. 完全二叉树 25. ?log2n??1 26. 根、?i/2?、2i、2i+1 27. 一组连续的存储单元 28. 遍历二叉树 29. 根结点、左子树、右子树 30. 左子树、根结点、右子树 31. 左子树、右子树、根结点 32. 前驱、后继、左指针域、直接前驱结点、右孩子、直接后继结点 33. 线索、线索二叉树、线索化 34. 双亲表示法、孩子表示法、孩子兄弟表示法 35. 根结点、各子树 36. 根的各子树、根结点 37. 根结点、根结点的子树、除第一棵树之外剩余的树构成的森林 38. 根结点的子树、根结点、除第一棵树之外剩余的树构成的森林 39. 分支 40. 路径长度 41. 路径长度之和 42. 权 43. 带权路径长度之和 44. 最优二叉树、最小的二叉树 45. 另一个字符的前缀 46. 68 47. 2n-1 48. 74 49. 129 50. 左子树为空 51. (p->lchild==nil)&&(p->rchild==nil) 52. 69 53. 99 54. 2 55. 36 56. 98 57. 中序 三、判断题 1．完全二叉树的某个结点若无左孩子，则它必然是叶结点。（ ） 2．存在这样一种二叉树，对它采用任何次序的遍历结果相同。（ ） 3．度为二的树称为二叉树。（× ） 4．二叉树中不存在度大于2的结点。（ ） 5．当二叉树中某个结点只有一棵子树的时候，无左右子树之分。（× ） 6．任何一棵二叉树都可以不用栈实现前序线索树的前序遍历。（ ） 7．哈夫曼编码是一种前缀编码，不允许出现两个字符编码相同的情况。（ ） 8．完全二叉树某结点有右子树，则必然有左子树。（ ） 9．前序遍历一棵二叉树的结点就可以得到排好序的结点序列。（× ） 10．将一棵拥有子树的树转换为二叉树后，根结点可能没有左子树。（× ） 11．根据二叉树的前序遍历和中序遍历可以得到二又树的后序遍历。（ ） 12．哈夫曼树是带权路径长度最短的二叉树。（ ） 13．哈夫曼树上权值较大的结点离根较远。（× ） 14．中序遍历森林与后序遍历与森林相对应的二叉树结果相同。（× ） 15．在二叉树中，具有一个孩子的结点，在中序遍历序列中，没有后继子女结点。 （× ） 16．先序遍历森林与先序遍历相对应的二叉树结果不同。（× ） 17．若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树。（× ） 18．二叉树只能采用二叉链表来存储。（× ） 19．给定结点数的平衡二叉树的高度是惟一的。（× ） 1. 正确：根据完全二叉树定义可以知道，若完全二叉树无左孩子，则它必然无右孩子。 2. 正确：二叉树只有一个结点的时候。 3. 错误：二叉树子树还有左右次序之分。 4. 正确。 5. 错误。 6. 正确。 7. 正确。 8. 正确：根据完全二叉树定义可以知道， 9. 错误：中序遍历一棵二叉树的结点就可以得到排好序的结点序列。 10. 错误：将一棵拥有子树的树转换为二叉树后，根结点必然有左子树。 11. 正确。 12. 正确。 13. 错误：哈夫曼树的路径上权值较大的结点离根较近。 14. 错误：后序遍历森林与中序遍历与森林相对应的二叉树结果相同。 15. 错误：在二叉树中，具有一个左孩子的结点，在中序遍历序列中，没有后继子女结点。 16. 错误：前序遍历森林与前序遍历与森林相对应的二叉树结果相同。 17. 错误：任一非叶子结点的度为2也不能保证满足满足满二叉树的定义。 18. 错误：也可以采用顺序存储和三叉链表等形式进行表示。 19. 错误：给定结点数的平衡二叉树的高度不一定是惟一的。 四、综合题 1．一棵树表达成如下形式： D＝{A，B，C，D，E，F，G， H，I，J，K，L，M，N，O} R=＜A，B＞，＜A，C＞，＜A，D＞，＜B，E＞，＜B，F＞，＜C，G＞，＜D，H＞，＜D，I＞，＜D，J＞，＜K，F＞，＜K，L＞，＜F，M＞，＜I，N＞，＜I，O＞｝ 其中D为结点集合，R为边的集合。请根据以上内容回答以下问题： (1) 画出这棵树。 (2) 该树的根结点是哪一个？ (3) 哪些是叶子结点？ (4) F结点的双亲是谁？ (5) F结点的祖先是哪些？ (6) F结点的孩子是哪些？ (7) F结点的兄弟是哪些？ (8) F结点的堂兄弟是哪些？ (9) F结点的度是多少？ (10)F结点的层次是多少？ (11)D结点的子孙有哪些？ (12) 以结点D为根的子树度是多少？ (13) 以结点D为根的子树层是多少？ (14) 该树的层是多少？ (15) 该树的度是多少？ 2．画出图6-1中树的二叉树表示形式。 （a） （b） （c） 图6-l 3．已知某二叉树的先序遍历的结果是：A，B，D，QC，E，H，L，I，K，M，F和J，它的中序遍历的结果是：QD，B，A，L，H，E，K，LM，C，F和J，请画出这棵二叉树，并且写出该二叉树后序通历的结果。 4．写一个将一棵二叉树复制给另一棵二又树的算法。 5．已知—个二叉树用二叉链表表示，其根指针为t，请写一个算法，从根结点开始按层次通历该二叉树，同层的结点接从左到右的次序进行访问。 6．已知一棵二叉树的先序遍历序列和中序遍历序列，请写出根据二又树先序遍历序列和中序遍历序列构造一棵二叉树的算法。 7．假设一棵哈夫曼树共有n0个叶子结点，试证明树中共有2no-l个结点。 8．假设通信用的报文由9个字母A、B、C、D、E、F、G、H和I构成，它们出现的频率分别是：10、20、5、15、8、2、3、7和30。请用这9个字母出现得频率作为权值求： （l）设计一棵哈夫曼树。 （2）计算其带权路径长度WPL值。 （3）写出每个字符的哈夫曼编码。 1. （1）该树的图形如图B-1所示。 ABCDEFGHIJKLMNO 图B-1 （2）该树的根结点是A。 （3）叶子结点是：E、K、L、M、G、H、N、O和J。 （4）F结点的双亲是B。 （5）F结点的祖先是A和B。 （6）F结点的孩子是K、L和M。 （7）F结点的兄弟是E。 （8）F结点的堂兄弟是G、H、I和J。 （9）F结点的度是3。 （10）F结点的层是3。 （11）D结点的子孙有I、N和O。 （12）以结点D为根的子树度为3。 （13）以结点D为根的子树层为3。 （14）该树的层是4。 （15）该树的度是3。 2. 本题树对应的二叉树形式如图B-2所示。 AAABBBCDCECEFGDKHLMIJN(a)(b)(c) 图B-2 3. 该二叉树的图形表示如图B-3所示，该二叉树后序遍历的结果是：G、D、B、L、H、K、M、I、E、J、F、C和A。 ABDGLHKEIMCFJ 图B-3 4. 用递归方法建立二叉树并求其深度的算法如下所示： define NULL 0 typedef struct btnode { elemtype data; struct btnode *lchild, *rchild; }bitnode, *bitree; bitnode *CreateBiTree() { /*用递归方法建立一棵二叉树*/ bitnode *t; char c; printf(\ c=getchar(); if ( c=='#' ) return(NULL); else { t=( bitnode * )malloc (sizeof(bitnode)); /*生成新结点*/ t->data=c; /*为数据域赋值*/ t->lchild=CreateBiTree(); /*递归创建左子树*/ t->rchild=CreateBiTree(); /*递归创建右子树*/ return(t); } }/*CreateBiTree()*/ int TreeDepth(bitnode *p) { /*递归求二叉树深度*/ int hl,hr,h; if ( p!=NULL ) { hl=TreeDepth(p->lchild); /*递归求左子树深度*/ hr=TreeDepth(p->rchild); /*递归求右子树深度*/ if ( hl>hr ) h=hl; else h=hr; return(h＋1);/*返回较大左右子树深度加1*/ } else return(0); }/*TreeDepth*/ 5. 将一棵二叉树复制给另一棵二叉树的算法如下所示： define NULL 0 typedef struct btnode { elemtype data; struct btnode *lchild, *rchild; }bitnode, *bitree; bitree *CopyTree( bitnode *p ) { /*复制一棵二叉树*/ bitnode *t; if ( p!=NULL ) { t=(bitnode *)malloc (sizeof (bitnode)); t->data=p->data; t->lchild=CopyTree(p->lchild); t->rchild=CopyTree(p->rchild); return(t); } else return(NULL); }/*CopyTree*/ 6. 可以使用队列Q来保存遍历过程中的各个结点，队列可以设定为bitree类型的指针数组，下标从1开始，同层结点按从左到右的顺序存放。算法如下： define NULL 0 define MAXSIZE 100 typedef char elemtype; typedef struct btnode { elemtype data; struct btnode *lchild, *rchild; }bitnode, *bitree; void LevelOrderTraverse( bitree t ) { /*使用队列对二叉树进行按层序遍历*/ bitree *Q[MAXSIZE]; /*队列Q是一个指向bitree类型的指针数组，下标从1开始*/ int rear, front; if (t!=NULL) { front=0; /*置空队列*/ rear=1; Q[1]=t; do { front=front%MAXSIZE+1; /*元素出队列*/ t=Q[front]; printf(\ if ( t->lchild!=NULL ) /*左子树根结点入队*/ { rear=rear%MAXSIZE+1; Q[rear]=t->lchild; } if( t->rchild!=NULL ) /*右子树根结点入队*/ { rear=rear%MAXSIZE+1; Q[rear]=t->rchild; } }while(rear=front); } }/*LevelOrderTraverse*/ 7. 一棵二叉树的先序遍历序列和中序遍历序列可以惟一确定一棵二叉树。现已知一棵二叉树的先序遍历序列和中序遍历序列，可依次从先序遍历序列中取结点，每次取出一个结点就与中序遍历的序列进行比较，当相等的时候，中序遍历序列就被分成以该结点为根的二叉树子树，该结点左部分为左子树，右部分为右子树，直到取完先序列里的所有结点，则二叉树构造完毕。可设数组A存放先序遍历序列，数组B存放中序遍历序列，为处理方便可设B为结构体类型，包括lchild、rchild和ch三个域。同时可设立一个顺序栈作为工作单元。 int CreaBitree( char A[], char B[] ) { /*根据二叉树先序遍历序列和中序遍历序列构造一棵二叉树的算法*/ seqstack *s; int i, j, k; s->top==-1; for( i=1; i<=n; i++ ) { j=1; while( B[j].ch != A[i] ) j++; if(s->top==-1) { s->top++; s->data[s->top]=j;/*j入栈*/ } else if (j B[s->data [s->top]].lchild =j; s->top++; s->data[s->top]=j; } else { while((j k=s->data[s->top]; /*栈不空时退栈*/ s->top--; } B[k].rchild=j; s->top++; s->data[s->top]=j; } } return(1); }/*CreaBitree*/ 8. 设该哈夫曼树中度为1的结点个数是n1，度为2的结点个数是n2，总的结点数目是n，根据二叉树的定义有： n=n0+n1+n2 （1） 根据二叉树的性质又有： n0=n2+1 （2） 又由于在哈夫曼树中不存在度为1的结点，因此上面的式子（1）中n1=0，即： n=n0+n2 （3） 再由（2）式得： n2=n0-1 （4） 将（4）代入（3）得到结论：n=2n0-1 命题证毕。 9. （1）哈夫曼树如图B-4所示。 01120105C02F13G1B0015D08E11130I010A07H 图B-4 （2）其带权路径长度WPL值为280。 （3）每个字符的哈夫曼编码为：A:100, B:11, C:1010, D:000, E:0010, F:10110, G:10111, H:0011, I:01。 第七章 一、选择题 1．在一个无向图G中，所有顶点的度数之和等于所有边数之和的（ ）倍。 A．l/2 B．1 C．2 D．4 2．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。 A．l/2 B．1 C．2 D．4 3．一个具有n个顶点的无向联通图至少包含（ ）条边。 A．n B．n＋1 C．n-1 D．n/2 4．一个具有n个顶点的无向完全图包含（ ）条边。 A．n(n-l) B．n(n+l) C．n(n-l)/2 D．n(n+l)/2 5． 一个具有n个顶点的有向完全图包含（ ）条边。 A．n(n-1) B．n(n+l) C．n(n-l)/2 D．n(n+l)/2 6．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（ ）。 A．n B．n2 C．n-1 D．(n-l)2 7．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（ ）。 A．n B．e C．2n D．2e 8．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（ ）。 A．n B．e C．2n D．2e 9．在有向图的邻接表中，每个顶点邻接链表链接着该顶点所有（ ）邻接点。 A．入边 B．出边 C．入边和出边 D．不是入边也不是出边 10．在有向图的逆邻接表中，每个顶点邻接链表链接着该顶点所有（ ）邻接点。 A．入边 B．出边 C．入边和出边 D．不是人边也不是出边 11．下列说法中不正确的是（ ）。 A．无向图中的极大连通子图称为连通分量 B．连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D．有向图的遍历不可采用广度优先搜索方法 12．设无向连通图 G=(V, E) 和G’= (V’, E’)，如果 G’为G的生成树，则下列说法中不正确的是（ ）。 A．G’为G的连通分量 B．G’为G的无环子图 C．G’为G的子图 D．G’为G的极小连通子图且V’＝V 13．如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是（ ）。 A．G肯定不是完全图 B．G一定不是连通图 C．G中一定有回路 D．G有二个连通分量 14．邻接表是图的一种（ ）。 A．顺序存储结构 B． 链式存储结构 C．索引存储结构 D． 散列存储结构 15．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ ）。 A．完全图 B．连通图 C．有回路 D．一棵树 16．下列有关图遍历的说法不正确的是（ ）。 A．连通图的深度优先搜索是一个递归过程 B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C．非连通图不能用深度优先搜索法 D．图的遍历要求每一顶点仅被访问一次 17． 一个无向连通图的生成树是含有该连通图的全部顶点的（ ）。 A．极小连通子图 B．极小子图 C．极大连通子图 D．极大子图 18．无向图的邻接矩阵是一个（ ）。 A．对称矩阵 B．零矩阵 C．上三角矩阵 D．对角矩阵 19． 已知一个图如下图所示，若从顶点a出发按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。 A、abecdf B、acfebd C、acebfd D、acfdeb abcedf 二、填空题 1．在图中，任何两个数据元素之间都可能存在关系，因此图的数据元素之间是一种________________的关系。 2．在图G中，如果代表边的顶点偶对是_____________，则称G为无向图。 3．在图G中，如果代表边的顶点偶对是_____________，则称G为有向图。 4．在图G中，＜vi，vj＞表示从vi到vj的一条边，在有向图中又称为一条____，且称vi为______或_________，称vj为_________或__________。显然在有一向图中 5．具有n (n-1)/2条边的无向图称为__________，简称为_________，其中n表示无向图中顶点的个数，n(n-1)/2是具有n个顶点无向图所拥有边的___________。 6．具有n个顶点的有向图，如果它同时具有n(n-1)条狐，则称该图为____________，其中n(n-1)是具有n个顶点有向图所拥有弧的___________________。 7． 有很少条边或弧（如边数少于nlogn）的图称为________________。 8． 如果图中的边或弧带有权，则称这种图为_______________。 9． 如果有两个网G=(V, E)，G’=(V’,E’)，若满足V(G’) V(G)，并且E(G’) E(G)，则称图G’为图G的__________。 10． 在无向图中，若存在一条边(v, w)，则称v和w这两个端点互为___________，同时称边(v,w)__________顶点v和w，或者说边(v,w)和顶点v和w_______________。 11．在有向图中，若存在一条弧 12．顶点v的度定义为_________________的数目，记为D(v)。 13．在有向图中，顶点v的度又分为_____________和_________，__________是以顶点v为头的弧的数目，或者说是以该顶点为终点的边的数目，记为ID(v)；____________是以顶点v为尾的弧的数目，或者说是以顶点为起点的边的数目，记为OD(v)；顶点v的度是它的___________和__________之和，即D(v)=ID(v)＋OD(v)。 14．____________是指一条路径上所经过的边或弧的数目。 15．若一条路径上除开始结点和结束结点外(开始结点和结束结点也可以为不同顶点），其余顶点均不相同，则称该路径为_____________。 16． 若一条路径上的开始结点和结束结点为同一个顶点，则称该路径为________或_______。同时除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路称_________或__________。 17．在无向图G中，如果从顶点v到顶点v’有路径，则称v和v’是______________的。如果对于图中任意两个顶点v和v’都是连通的，则称图G是________，否则称为__________。无向图中，极大的连通子图称为___________________。 18．在有向图中，若任意两个顶点vi，vj∈V，vi≠vj，从vi到vj和从vj到vi都存在路径，则称该图是____________。有向图中的极大强连通子图称为有向同的___________。 19．一个连通图的生成树是一个__________，它含有图中全部以点，但只有构成一棵树的__________条边。如果在一棵生成树添加一条边，必定构成一个___________，因为新添加的这条边使得依附在它两端的两个顶点有了____________。 20．如果有一个有向图恰有一个顶点的人度_______，其余以顶点的人度均________，则该有向图是一棵有向树。一个有向图的___________由若干棵有向树构成，含有图中全部顶点，但只有构成若干棵不相交的有向树的弧。 21．图的邻接矩阵（Adjacency Matrix）表示法是用一个________来表示图中顶点之间的相邻关系。 22．邻接表(Adjacency List)是图的一种_______存储结构。在邻接表中，对图中每个顶点建立一个_________，第i个单链表中的结点表示依附于顶点vi的边(对无向图)或弧（对有向图）。 23．逆邻接表只有______图才具有。是为了便于确定有向图中顶点的_______而建立的。 24．一个图的邻接矩阵的表示是_________，但是图的邻接表的表示并_____________。这是因为邻接表中各边结点的连接次序取决于建立邻接表时输入的次序，由于输入的时候是随机的，所以图的邻接表建立的结果也有可能____________。 25．从邻接表的定义可以看到，若无向图有n个结点和e条边，则它的邻接表需要________个头结点和______________个表结点。 26．图的遍历(Traversing Graph)是从图的某一顶点出发访问图中___________，并且使每一个顶点___________________的过程。 27．图的深度优先搜索的基本思想是：从中某个顶点v出发，首先访问_________，然后访问_________顶点w，接着访问一个_____________的顶点，依此类推，直到图中所有和v有路径相通的顶点都被访问到；若此时图中仍有顶点未被访问，则选择图中未被访问的顶点作为___________，重复上述过程，直到图中所有顶点_______________为止。 28．图的深度优先搜索遍历类似于树的__________________遍历。 29．图的广度优先搜索的基本思想是：从某个顶点v出发，首先访问此顶点，然后按广度优先搜索依次访问所有v的__________，接着从这些___________出发仍然进行广度优先搜索依次访问其他结点，直至图中所有已被访问的顶点的_________全部被访问到。若此时图中依然有未被访问的顶点。则另选一个图中____________作为起始点，重复上述过程，直到图中所有顶点___________为止。 30．图的广度优先搜索类似于树的_______________遍历。 31．如果连通图是一个网络，生成树的_______称为这棵生成树的代价，则称该网络中所有生成树中权值最小的生成树为____________，简称为__________。 32．构造一棵最小生成树往往都要利用最小生成树的一种简称为MST的性质。常见的构造最小生成树的______________算法和___________算法都利用了MST性质。 33． 路径上的第一个顶点称为____________，最后一个顶点称为____________。 34． 迪杰斯特拉算法是求____________的最短路径，弗洛伊德（Floyd）算法是求_________的最短路径。 35．一个____________称为有向无环图，简称为DAG图。 36．DAG图比有向树更一般，因为在有向树中不允许出现____________的结点，而在DAG图中则可以；另外DAG图不允许_____________，因此又是一种特殊的图。 37．用顶点表示_________，用弧表示活动之间________的有向图，称为顶点表示活动的网（Activity On Vertex Network），简称 AOV网。 38．在AOV网中不可以出现有向环或回路，如果出现环或回路，这意味着某项活动是_________，这样的工程无法进行，对于计算机中的程序流程图来说就是_____________，也相当于操作系统中的______________。 39．检测AOV网是否有回路的方法是构造_________。从构造拓扑序列过程中可以发现是否有______________。 40．拓扑排序是对AOV网构造一个__________，使得所有结点的________在序列中得以体现，即在序列中某个结点的前驱必须在后继之前。拓扑排序的序列__________。 41．如果用数学上的术语进行描述，拓扑排序是由某个集合上的一个__________关系得到该集合上的一个__________的操作。 42．构造拓扑有序序列的过程可以发现有向图中________，同时构造拓扑有序序列的过程就是利用拓扑排序算法进行________________的过程。 43．拓扑排序的结果使得当前图中_________全部被输出，但仍然有结点未被输出，这说明有向图中存在_______________。 44．如果含n个顶点的图形成一个环，则它有___________棵生成树。 45．有n个结点的无向图的边数最多为____________。 46．有n个顶点的强连通有向图G至少有___________条边。 47．用邻接矩阵存储有向图G，其第i行的所有元素之和等于顶点i的_________。 48．设有向图G的邻接矩阵为 A，图中i和j之间不存在弧，则A[i,j］的值为______。 49．有n个顶点的连通图的边数至少为____________。 50．在有n个顶点的有向图中，每个顶点的度最大可达___________。 51．在无向图G的邻接矩阵A中，若(vi,vj)属于图G的边集，则对应元素A[i,j]为______， 否则等于_____________（用逗号分开）。 52．已知一个有向图用邻接矩阵表示，计算第i个结点的人入度的方法是__________。 53．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为________________，所有邻接表中的结点总数是________________。 1. 多对多 2. 无序的 3. 有序的 4. 弧、弧尾、初始点、弧头、终端点、不同的边 5. 无向完全图、完全图、最大数目 6. 有向完全图、最大数目 7. 稀疏图 8. 网 9. 子图 10. 邻接点、依附于、相关联 11. 邻接到、相关联 12. 以该顶点为一个端点的边 13. 入度、出度、入度、出度、入度、出度 14. 路径长度 15. 简单路径 16. 回路、环、简单回路、简单环 17. 连通、连通图、非连通图、连通分量 18. 强连通图、强连通分量 19. 极小连通子图、n-1、环、第二条路径 20. 为0、为1、生成森林 21. 二维数组 22. 链式、单链表 23. 有向、入度 24. 惟一的、不惟一、不一样 25. n、2e 26. 所有顶点、仅被访问一次 27. 顶点v、与v相邻的、与w相邻且未被访问、起始点、全部被访问完 28. 先序 29. 未被访问过的邻接点、邻接点、邻接点、未被访问的顶点、均被访问完 30. 按层次 31. 各边权值之和、最小代价生成树、最小生成树 32. 普里姆（Prim）、克鲁斯卡尔（Kruskal） 33. 源点（Source）、终点(Destination) 34. 某个源点到其余各顶点、每一对顶点之间 35. 无环的有向图 36. 入度大于1、出现环或回路 37. 活动、优先关系 38. 自己的先决条件、死循环、死锁 39. 拓扑有序序列、有向环或回路 40. 线性序列、优先关系、并不一定惟一 41. 偏序、全序 42. 是否有环、拓扑排序 43. 无前驱的顶点、环 44. n 45. n(n-1)/2 46. n 47. 出度 48. 0 49. n-1 50. 2(n-1) 51. 1,0 52. 求矩阵第i 列（非0）元素之和 53. n,2e 三、判断题 1．有n个结点的无向图中，若边数大于n-1，则该图是连通的。（× ） 2．若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑有序序列必定存。 （ ） 3．AOV网拓扑排序的结果是惟一的。（× ） 4．图的广度优先搜索序列是惟一的。（× ） 5．具有n个顶点的无向图采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素之和的一半。（ ） 6．若连通图上各边权值均不相同，则该图的最小生成树是惟一的。（ ） 7．无向图的邻接矩阵一定是对称的。（ ） 8．有向图的邻接矩阵一定是非对称的。（× ） 9．用邻接矩阵存储图的时候，占用空间大小不但与图的结点个数有关还与图的边数有关。（× ） 10．图的连通分量是无向图的极小连通子图。（× ） 11．图的强连通分量是无向图的极大连通子图。（× ） 12．对任意一个图从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。（× ） 13．一个有向图的邻接表和逆邻接表中的节点个数一定相等。（ ） 14．有向图用邻接矩阵表示后，顶点i的出度等于第i行中非0且非无穷的元素个数。（ ） 15．图G的某一最小生成树的代价一定小于其他生成树的代价。（×） 1. 错误：有n各结点的无向图中，图是连通的则边数大于n-1，但反过来不正确。 2. 正确：有向图的邻接矩阵中对角线以下元素均为零，说明一定不存在回路并满足偏序关系，故拓扑有序序列必定存在。 3. 错误：AOV网拓扑排序的结果是不惟一的。 4. 错误：图的广度优先搜索序列不是惟一的，一个图中可能存在多个子图，即使在一个图中从不同的结点出发其遍历结果也可能不同。 5. 正确。 6. 正确：由图的最小生成树定义可以得到。 7. 正确。 8. 错误：有向图的邻接矩阵也可能是对称的。 9. 错误：用邻接矩阵存储图的时候，占用空间大小与图的结点个数有关，而与图的边数无关。 10. 错误：图的连通分量是无向图的极大连通子图。 11. 错误：强连通分量是有向图的极大连通子图。 12. 错误：该图不一定是连通的。 13. 正确。 14. 正确。 15. 错误：图中可能存在多个相同权值的边，图的最小生成树可能不只一棵。 四、综合题 l．请写出如图7-1所示无向图的邻接矩阵和邻接表两种存储结构。 邻接矩阵如图B-5所示。 ?0?0??0??0?0A???0?0??1?0??0?100000100?010000001??001000001??010100000?001010000??000001010?000010100??000001010?000010100???110000000? 图B-5 邻接表如图B-6所示。 datafirstarcadjvexdatanext1234567891023434761622343476162810105698783810105698783^^^^^^^9^^9^55^1212^^ 图B-6 2．依据无向图7-1，请写出： （1）从顶点1出发图的深度优先搜索序列。 （2）从顶点回出发图广度优先搜索的序列。 （3）写出图的深度优先搜索算法。 （4）写出图的广度优先搜索算法。 （1）从顶点1出发图的深度优先搜索序列为： 1→8→7→6→9→5→4→3→2→10 （2）从顶点1出发图广度优先搜索的序列为： 1→8→2→7→9→10→3→6→4→5 （3）图的深度优先搜索算法参考例题7-1的内容。 （4）图的广度优先搜索算法参考例题7.2节内容。 3．使用Prim算法，依据无向图7-2做以下问题； 图7-2 （l）写出构造该图的最小生成树的过程。 (2) 写出相应的构造最小生成树算法。 （1）使用Prim算法，构造该图的最小生成树的过程如图B-7所示。 190206507570511041201082580530367548310026012（a）12067554583650752120（b）2834（c）1206507554583650751002120（d）100210834（e）12065075548255100210365075120（f）1002103082543（g）（h） 图B-7 4．使用Kruskal算法，依据无向图7-2做以下问题： （l）写出构造该图的最小生成树的过程。 (2) 写出相应的构造最小生成树算法的形式描述。 （1）使用Kruskal算法，构造该图的最小生成树的过程如图B-8所示。 100190206507570526010301212082536755838011044（a）121067554583675120（b）210834（c）1206755482552103675120（d）2108254303（e）1205067554825521030365075120（f）1002103082543（g）（h） 图B-8 5． 假设图采用邻接表表示，写出一个从顶点v0对图按深度优先搜索遍历的非递归算法。 6．有一个无向图采用邻接表的存储结构，请编写算法，以遍历的形式输出从顶点v到顶点w的路径中长度为len的简单路径。 7．以邻接表作为存储结构，编写一个算法，利用深度优先搜索法，求出在无向图中通过给定点w的简单回路的算法。 第九章 一、选择题 1.顺序查找方法适合于存储结构为（ ）的线性表 A.散列存储 B.索引存储 C.散列存储或索引存储 D.顺序存储或链接存储 2.对线性表进行二分查找的时候，要求线性表必须（ ）。 A.以顺序存储方式 B.以链接存储方式 C.以顺序存储方式，且数据元素有序 D.以链接存储方式，且数据元素有序 3. 如果要求一个线性表既能较快地查找，又能动态适应变化要求，可以采用（ ）查找方法。 A.顺序 B.分块 C.折半 D.散列 4. 对于一个线性表，若要求既能进行较快地插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该( ) 。 A.以顺序存储方式 B.以链接存储方式 C.以索引存储方式 D.以散列存储方式 5. 在线性表的存储结构中,（ ）查找、插入和删除速度慢，但顺序存储和随机存取第i个元素速度快。 A.顺序表 B.链接表 C.散列表 D.索引表 6. 在( )上查找和存取速度快,但插入和删除速度慢。 A.顺序表 B.链接表 C.顺序有序表 D.散列表 7. 在( )上查找、插入和删除速度快,但不能进行顺序存取。 A.顺序表 B.链接表 C.顺序有序表 D.散列表 8. 在( )上插入、删除和顺序存取速度快,但查找速度慢。 A.顺序表 B.链接表 C.顺序有序表 D.散列表 9. 采用顺序查找方法查找长度为n的线性表,查找每个元素的平均比较次数为( ) A. n B. n/2 C. (n+1)/2 D.(n-1)/2 10.顺序查找具有n个元素的线性表,其时间复杂度为( ) 。 A.O(n) B.O(log2n) C.O(n2) D.O(nlog2n) 11.折半查找具有n个元素的线性表,其时间复杂度为( ) 。 A.O(n) B.O(log2n) C.O(n2) D.O(nlog2n) 12.己知一个有序表为(11,22,33,44,55,66,77, 88,99), 则折半查找元素55需要比较( )次。 A.1 B.2 C.3 D.4 13.已知一个有序表为(11,22,33,44,55,66,77,88,99), 则顺序查找元素 55 需要比较( )次。 A.3 B.4 C.5 D.6 14.顺序查找法与二分查找法对存储结构的要求是( ) 。 A. 顺序查找与二分查找均只是适用于顺序表 B. 顺序查找与二分查找均既适用于顺序表 , 也适用于链表 C. 顺序查找只是适用于顺序表 D. 二分查找适用于顺序表 15.在对查找表的查找过程中,若被查找的数据元素不存在,则把该数据元素插到集合中。这种方式主要适合于( ) 。 A.静态查找表 B. 动态查找表 C.静态查找表与动态查找表 D. 两种表都不适合 16.若用二分查找取得的中间位置元素关键字值大于被查找值，则说明被查找值位于中间值的前面,下次的查找区间为从原开始位置至( ) 。 A.该中间位置 B.该中间位置-1 C.该中间位置+1 D.该中间位置1/2 17.二叉排序树（ ）遍历序列是从小到大有序的。 A. 先序 B.中序 C. 后序 D.层序 二、填空题 1.查找表是由同一类型的数据元素 ( 或记录 ) 组成的 , 是查找所依 赖 。 2. 如果对查找表只进行查询某个\特定的\数据元素是否在查找表中, 以及查找某 \特定的\数据元素的各种属性两种类型的基本操作,而不进行插入和删除数据元素的查找表称为 。 3. 如果在查找表中进行查找的过程中，同时插入查找表中不存在的数据元素，或者 查找表中删除已存在的某个数据元素，则称此类查找表为 。 4. 关键字是数据元素(或记录)中某个 ，用它可以标识(识别)一个查表中 5. 在一个查找表中，能够惟一的标识一个数据元素(或记录)的关键字称为 。 6. 次关键字也称为 或 ，是在查找表中可以标识 的关键字。 7. 查找又称 ，它是根据给定的某个值，在查找表中确定是否有元素(或记 录)的关键字的操作。若操作之后确定表中存在这样的记录，则称为查找 的，否则称为 。 8. 平均查找长度是指为确定所查找的记录在查找表中的位置，需要与给定值进行比较关键字个数的 。 9. 最大查找长度是指为确定所查找的记录在查找表中的位置，需要与给定值进行比较关键字个数的 。最大查找长度随所查找的 、 和 都有关系。最大查找长度通常是在考虑查找给定值在查找表中的情况。 10. 是一种最简单、最基本的查找方法，它的基本思想是：从表的一端开始，依次顺序扫描线性表，将扫描到记录的关键字逐个与给定值进行比较，若某个记录的关键字和给定的值相等，则说明找到所要的记录，查找成功；若扫描结束后，仍未找到关键字等于给定值的记录，则说明表中没有所查找的记录，查找不成功。 11. 折半查找( Binary Search)又称为 ， 是一种效率较高的一种查找算法。 12. 折半查找的思路是：每次将给定值与查找表中所要查找区域 的关键字进行比较，而不是查找表中的第一条或最后一条。 13. 分析折半查找的性能可以用二叉树来进行描述。把当前查找区间的中间位置上的结点作为根结点，左半区间和右半区间中结点分别作为左子树和右子树，由此得到的二叉可称为 。 14.分块查找(Blocking Search)又称为 ，是一种以 的形式来来进行的查找方法。分块查找是 的一种改进，它是一种介于 和折半查找之间的查找方法。 15. 二叉排序树(Binary Sort Tree)，又称为 ，它或者是一棵空树，或者是具有下列性质的一棵二叉树： (1) 若左子树不空，则左子树上所有结点的值 。 (2) 若右子树不空，则右子树上所有结点的值 。 (3) 左右子树又分别是 。 16.平衡二叉树定义为：它或者是一棵空树；或者是具有这样性质的二叉树:它的左子树和右 子树都是 且左子树和右子树的深度之差的绝对值 。 17. 我们称在构造平衡二叉排序树的过程中，离插入结点最近，且以平衡因子绝对值大 于1 的结点作为根结点的子树为 。 18. 哈希表查找就是一种通过某种映射建立起 之间的对应关系，希望 或经过很少次比较即可获得所要查找的记录。 19. 哈希(Hash)表查找又称为 查找，它是一种重要的查找技术。哈希表查找因使用哈希函数(又称为 ) 而得名。哈希函数是一种 的函数。 20. 利用哈希函数可以实现记录关键字和关键字所对应记录存储地址的转换或映像，这种映像过程称为 或 ，映像结果产生的哈希函数值h (key)作为存储位置称为 或 ，利用哈希函数映像哈希地址，所得到的存储表称为 21. 有时候在向哈希表中存储关键字的时候，会出现一个待插入关键字的记录已经被占用的情况，这种 的现象称为冲突 ( Collision) 。 22.具有相同哈希函数值的关键字对相应的哈希函数来说称为 ，由同义词产生的冲突称为 。 23. 构造哈希函数的 是取关键字或关键字的某个线性函数作为哈希地址。 24. 构造哈希函数的 是对关键字中数字进行分析，然后用提取其中一部分分布较为均匀的数字位作为哈希地址的方法。 25. 构造哈希函数的 是用关键字key除以某个正整数p，所得余数作为哈希地址的方法。 26. 构造哈希函数的 是取关键字平方的中间几位作为哈希地址的方法。 27. 构造哈希函数的 是先将关键字分割成位数相等的几段(其中最后一段的位数可以不相等)，然后取这几位的叠加和作为哈希地址。 中数位的叠加可以分为移位叠加和间界叠加两种。所谓移位叠加是 ，然后相加；间界叠加是 然后对齐相加。 28. 构造哈希函数应当尽量减少冲突，但是还是无法避免冲突的发生。一旦冲突发生了， 就必须寻求合适的方法来解决冲突。通常解决冲突可以采用 和 。 29. 开放定址法(Open Addressing)是指将哈希表中的空单元向处理冲突开放。开放定址法解决冲突，形成下一个地址的形式是：Hi=(h(key)+di)%m, i=1,2, ? ,k(k≤m-l)其中，h (key) 为哈希函数，m为哈希表长，di为增量序列。根据上式形成增量序列di的不同，开放定址法又可以分成如下三种形式： 、 、 。 30. 分析哈希表的查找过程可以知道，造成哈希表冲突的首要因素是 ，第二个因素是 ，第三个因素是 。 31. 在有序表A[1..18]中，采用二分查找算法查找元素值等于A[7]的元素，所比较过的元素的下标依次为 。 32. 有17个元素的有序表A[1..17]作二分查找，在查找其等于A[8]的元素时，被比较的元素的下标依次是 。 33. 假定有K个关键字互为同义词，若用线性探测再散列法把这K个关键字存入散列表中，至少要进行 次探测。 34. 一个无序序列可以通过构造一个 树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。 35. 在有序表a [1..20]中，采用二分查找算法查找元素值等于a[12]的元素，所比较过的元素的下标依次为 。 36. 对于长度为 n 的线形表 , 若进行顺序查找 , 则时间复杂性为 ；若用二分法 查找，则复杂性为 ；若用分块法查找(假定总块数和每块长度均接近 )，则时间复杂性为 。 37. 对长度为 L 的顺序表，采用设置岗哨方式顺序查找，若查找不成功，其查找程 为 。 38. 对有序表 (25,30,32,38,47,54,62,68,90,95) 用二分查找法查找32，则所需的比较次数为 。 1. 集合、数据结构 2. 静态查找表 3. 动态查找表 4. 数据项的值、数据元素（或记录） 5. 主关键字 6. 从关键字、辅助关键字、若干条记录 7. 检索、等于给定值、成功、查找不成功 8. 期望值 9. 最大值、内容、所查找的表、所用的查找算法、最坏情况下 10. 顺序查找（Sequential Search） 11. 二分查找、有序表 12. 中间那条记录 13. 折半查找判定树 14. 索引顺序查找、索引顺序表、顺序查找、顺序查找 15. 二叉查找树、均小于根结点的值、均大于根结点的值、二叉排序树 16. AVL树、平衡二叉树、不超过1 17. 最小不平衡树 18. 关键字和关键字所在记录的存储地址、不经过比较 19. 散列表、散列函数、把关键字映射成记录存储地址 20. 哈希造表、散列、哈希地址、散列地址、哈希表、散列表 21. 不同的关键字具有相同地址 22. 同义词、同义词冲突 23. 直接定地址法（或Immediately allocate） 24. 数字分析法（或Digital Analysis method） 25. 除留余数法（或Division Method） 26. 平方取中法（或Mid-square method） 27. 折叠法（或Folding Method）、折叠法（或Folding Method）、将分割后的每一部分的最低位对齐、从每段的一端向另一端沿分割界来回折叠 28. 开放定址法、链地址法等方法 29. 线性探测再散列、二次探测再散列、随机探测再散列 30. 哈希函数、处理冲突的方法、装填因子 31. 9 4 6 7 32. 9，4，6，7，8 33. 1+2+??+k=k(k+1)/2 34. 二叉排序 35. 10,15,12 36. O(n);O(log2n);O(n) 37. L+1 38. 3 39. 左子树 三、判断题 1. 用向量表示的有序表可以使用折半查找。 ( ) 2. 用单链表表示的有序表可以使用折半查找。（×） 3. 顺序查找的平均查找长度ASL与数据的排列有关。（×） 4. 在任意非空的二叉排序树中，删除某个结点之后，再将该结点插入在二叉排序树中，则所得到的二叉排序树与原二叉排序树相同。（×） 5. 哈希表的装载因子越小则发生冲突的可能性越大。（×） 6. 二叉排序树中，关键字最小的结点必然无右孩子，关键字最大的结点必然无左孩子。（×） 7. 在分块查找、折半查找和顺序查找中，分块查找平均查找长度最大、折半查找平均查找长度最小。（×） 8. 顺序查找的方法适合于顺序存储结构而不适合于链接存储结构。（×） 9. 前序遍历一棵二叉排序树的结点 , 就可以得到排好序的结点序列。（×）10. AVL树是一棵二叉树，该树上的任意一个结点的平衡因子的绝对值均不大于1。 （ ） 11. 在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表的个数有关，而且与每一块中的元素的个数有关。 ( ) 12. 对一个堆按层次遍历，不一定能得到一个有序序列。（ ） 1. 正确。 2. 错误：用单链表表示的有序表不可以使用折半查找。 3. 错误：顺序查找的平均查找长度ASL与数据的排列无关。 4. 错误：由于二叉排序树插入结点均在二叉排序树的叶子结点上，因此若删除的结点不是叶子结点则删除再重新插入后是不同于原来二叉树的。 5. 错误：哈希表的负载因子越小则发生冲突的可能性越小。 6. 错误：二叉排序树中，关键字最小的结点必然无左孩子，关键字最大的结点必然无右孩子。 7. 错误：在分块查找、折半查找和顺序查找中，顺序查找平均查找长度最大、折半查找平均查找长度最小。 8. 错误：顺序查找的方法适合于顺序存储结构和链接存储结构。 9. 错误：中序遍历一棵二叉排序树的结点，就可以得到排好序的结点序列。 10. 正确。 11. 正确。 12. 正确。 四、综合题 l. 用 C 语言写出顺序查找算法。 2. 用 C 语言写出折半查找算法。 3. 用 C 语言写出分块查找算法。 4. 写出二叉排序树的插入结点的递归算法，并利用插入算法写出建立一个有n个结点的二叉排序树算法。 5. 简述平衡二叉树调整平衡的具体方法。 6. 关键字序列A=(36,27,68,33,97,40,81,24,23,90,32,14)共12个数据，哈希表长为13，采用的哈希函数为：h (key) = key % 13。如果采用开放定址的线性探测再散列方法解决冲突，请构造哈希表并求其平均查找长度。 7. 写出折半查找的递归算法。 8. 编写算法，用折半查找算法在一个有序的顺序表中插入 x 结点，并保持结点的有序性。 9. 编写判定给定的二叉树是否是二叉排序树的算法。 10. 设哈希函数为 h (key)=key % 19，编写一个用链接表解决冲突的哈希表插入函数。 11. 设哈希函数为h (key)=key ，解决冲突的方法是链地址方法，编写一个从哈希表中删除关键字为 key 的一个记录的算法。 习题十 一、选择题 1．在所有的排序方法中，关键字比较的次数与记录初始排列秩序无关的是（）。 A．冒泡排序 B．希尔排序 C．直接选择排序 D．直接插人排序 2．从未排序序列中依次取出元素与已经排好序的序列中的元素作比较，将其放入已排序序列的正确位置上，此方法称为（）。 A．插人排序 B．选择排序 C．交换排序 D．归并排序 3．从未排序序列中挑选元素，并将其放人已排序序列的一端，此方法称为（）。 A．插入排序 B．交换排序 C．选择排序 D．归并排序 4．依次将每两个相邻的有序表合并成一个有序表的排序方法称为（）。 A．插人排序 B．交换排序 C．选择排序 D．归并排序 5．当两个元素出现逆序的时候就交换位置，这种排序方法称为（）。 A．插人排序 B．交换排序 C．选择排序 D．归并排序 6．每次把待排序的区间划分为左、右两个子区间，其中左区间中的记录的关键字均 小于等于基准记录的关键字，右区间中记录的关键字均大于等于基准记录的关键字，这种 排序称为（）。 A 插人排序 B．快速排序 C．堆排序 D．归并排序 7．在正常情况下，直接插人排序的时间复杂度为（）。 A．O(log2n) B．O(n) C．O(n log2n) D．O(n2) 8．在正常情况下，冒泡排序的时间复杂度为（）。 A．O(log2n) B．O(n) C．O(nlog2n) D．O(n2) 9．在归并排序中，归并趟数的数量级为（）。 A．O(log2n） B．O(n) C．O(nlog2n) D．O(n2) 10．在归并排序中，每趟需要进行的记录比较和移动次数的数量级为（）。 A．O(log2n） B．O(n) C．O(nlog2n) D．O(n2) 11．归并排序算法时间复杂度为（）。 A．O(log2n） B．O(n) C．O(nlog2n) D．O(n2) 12．平均情况下，快速排序的时间复杂度为（）。 A．O(log2n） B．O(n) C．O(nlog2n) D．O(n2) 13．最坏情况下，快速排序的时间复杂度为（）。 A．O（log2n） B．O(n) C．O(nlog2n) D．O(n2) 14．堆排序中，在每次筛运算中，记录比较和移动次数的数量级为（）。 A．O（log2n） B．O(n) C．O(nlog2n) D．O(n2) 15．堆排序算法时间复杂度为（）。 A．O（log2n） B．O(n) C．O(nlog2n) D．O(n2) 16．设有 800条记录，希望用最快的方法挑选出其中前10个最大的元素，最好选用（）。 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．若构造一棵具有n个结点的二又树排序，在最坏的情况下，其深度不会超过（）。 A．n/2 B．n C．（n＋l）/2 D．n＋l 23.考察下列排序算法的稳定性，（ ）是稳定的排序算法。 A．直接插人排序归并排序冒泡排序 B．简单选择排序 C．快速排序 D．堆排序、希尔排序 二、填空题 1．假设对记录的次关键字进行排序，记录之中有两条记录Ri和Rj，它们的关键字Ki和 Kj相等，在排序之前记录 Ri在 Rj之前，若排序之后记录 Ri仍在Rj之前，则称排序方法是___________; 相反，若经过某种排序之后 Ri在Rj之后，则称所用的排序方法是____________。 2．根据所排序过程中所用存储器的不同，可以将排序方法分为__________和__________。 3．如果按排序过程中所需要的工作量来分，又可以分为__________、__________ 和__________，其中__________的时间复杂度为 O(n2),__________的时间复杂度为O(nlogn)，__________时间复杂度为O（d·n）。 4．__________的基本思想是：每一趟将一个待排序的记录按其关键字的大小，插入到已经排好序的部分记录之中，使之构成一个新的有序序列，直到所有记录全部插入完成，所有待排记录的关键字都成为一个有序序列。 5．直接插人排序是一种__________．（填是否稳定）的排序算法。 6．希尔排序（Shell’s Sort）又称__________，它是由 D．L．Shell于 1959年提出来的一种改进的插入排序方法。希尔排序属于__________的一种，但比普通的插人排序效率要 高。 7．希尔排序是一种__________（填是否稳定）的排序算法. 8．__________是通过两两比较待排序记录的关键字，若发现两个记录关键字的大小次序相反，即进行交换，直到所有记录关键字全部满足排序要求为止。 这种排序方法可以包括有__________和__________两种交换排序方法。 9．__________是通过无序区中相邻记录关键字之间相互比较和交换位置，使之关键字 较小的记录在关键字较大的记录之上，从下标较大的单元逐步向下标较小的位置移动。 10．冒泡排序是一种__________（填是否稳定）的排序算法。 11．快速排序（Quick Soft）又称___________是由霍尔 (Hoare) 提出的的一种对冒泡 排序改进的交换排序。 因其排序速度快，故而称为快速排序。 12．快速排序是一种__________（填是否稳定）的排序算法。 13．__________的基本思想是：每一趟排序在待排序的记录中选关键字最小的记录，依次放在已经排序记录序列的最后，直至全部记录的关键字成为一个有序序列为止。 这种排序方法又可以分为：__________和__________。 14．堆排序的关键是构造堆。R．W．FIOyd提出了一个__________算法来建堆。 15．归并就是将两或两个或两个以上的有序数据序列合并成一个有序数据序列的过程。归并排序有__________和__________，可以用于__________，也可以用于__________，但一般情况下说归并排序都是指__________．它是最简单也是最基础的一种归并排序方法。 16．归并排序是一种__________（填是否稳定）的排序算法。 17.是利用关键字本身的结构，借助于多关键字排序的思想，通过“分配”和“收集”的方法实现排序。 18．基数排序是一种__________（填是否稳定）的排序方法。 19．对于多关键字排序，可以有两种方法。一种称为__________法，简称__________法，另一种方法称为__________法。 20．当排序的记录数量很多，可能出现正序或逆序情况的时候，并且要求排序方法稳定的时候，则要选择__________。 21．直接选择排序算法在最好情况下所作的交换元素的次数为__________。 22．简单选择排序方法所执行的元素交换次数最多为__________。 23．简单选择排序方法在最好的情况下所做的交换元素的次数为__________。 24．冒泡排序方法在最好情况下的元素交换次数为__________。 25．有n个求队参加的足球联赛按主、客场进行比赛，共需进行__________场比赛。 26．在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序若干趟后，当需要把第7个记录60插入到有序表时，为寻找60的插入位置需比较__________次。 27．分别采用选择排序、堆排序、快速排序和归并排序方法对初始状态为递增序列按递增顺序排序，最省时间的是__________排序，最浪费时间的是__________排序。 三、判断题 1．快速排序在所有排序方法中最快，而且所需要的附加空间也最少。 （×） 2．外部排序是把外存文件调入内存，可利用内部排序方法进行排序，因此排序所花 费的时间取决于内部排序的时间。 （×） 3．一般来说，外排序所需要的时问取决于内部排序时间、外存信息读写时间和内部 归井所需要的时间。 （ ） 4．外排序过程主要分为两个阶段：生成初始归并段和对归并段进行逐趟归并的时间（ ） 5．快速排序方法在任何情况下均可以得到最快的排序效果。 （×） 6．基数排序的设计思想是依照对单个关键字值的比较来实施的。 （×） 7．用希尔（Shell）排序方法进行排序的时候，关键字越是有序效率越高，关键字越是杂乱则排序效率越低。 （ ） 8．减少初始归并数量，可以使外部排序的时间缩短。 （×） 9．直接插入排序是一种稳定的排序算法。 （ ） 10．希尔排序是一种稳定的排序算法。 （×） 11．冒泡排序是一种稳定的排序算法。 （ ） 12．冒泡排序算法的时间复杂度最佳情况下为O(n2)。 （×） 13．快速排序是一种稳定的排序算法。 （×） 14．直接选择排序是一种稳定的排序算法。 （×） 15．堆排序是一种稳定的排序算法。 （×） 16．快速排序、堆排序和归并排序平均时间复杂度为O(nlog2n)。 （ ） 17．归并排序是一种稳定的排序算法。 （ ） 18．基数排序是一种稳定的排序算法。 （ ） 19．目前归并排序在内部排序和外部排序中都广为使用。 （ ） 20．当排序的记录数量很多，可能出现正序或逆序情况的时候，可以选择堆排序，如果进一步要求排序方法稳定的时候，则要选择归并排序。 （ ） 21．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。 （ ） 22．二路归并排序的核心操作是将两个有序序列归并为一个有序序列。 （ ） 四、综合题 1．已知一组记录的关键字序列为{41，60，39，72，25，44，90，31}，请写出直接插入排序的每一趟过程。 2．已知一组记录的关键字序列为{36，55，31，28，79，66，12，07，89}，请写出进行冒泡排序的每一趟过程。 3．已知一组记录的关键字序列为{35，27，60，72，50，40，17，81，29，69，30}，请写出以第一个记录为基准记录，一趟快速排序时记录的移动情况。 4．已知一组记录的关键字序列为{76，98，23，65，40，39，52，65，87，11}，请写出直接选择排序的每一趟过程。 5．已知一组记录的关键字序列为{22，96，15，37，10，68，44，85，70，20，11}，请写出用归并排序进行排序的每一趟过程。 6．设计一个函数，实现冒泡排序的双向排序，即每一趟通过每两个相邻的关键字进行比较，产生最小和最大的关键字值的元素。 7．用递归的方法实现一趟归并排序，并写出完整的归并算法。 8．有一种算法称为奇偶转换排序，它的思路是：第一趟对所有的奇数i将a[i]和a[i+l]进行比较，第二趟对所有的偶数的i将a[i]和a[i+l]进行比较，每次比较时，若a[i]＞a［i＋l］，则将二者进行交换，直至所有记录关键字有序。试写出此算法。