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

《数据结构习题集(包含全部答案)》由会员分享，可在线阅读，更多相关《数据结构习题集(包含全部答案)（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

2、 和 B6一个算法应该是 。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. 以下数据中， 是线性数据结构

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

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

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

6、后将结点按某种方式存人该地址的一种方法。 散列存储或哈希存储 14、所谓算法Algorithm是对特定问题求解步骤的一种描述，它是指令的其中每个指令表示一个或多个操作。算法的五个重要特性是_、_、_、_和_。 有限序列、有穷性、确定性、可行性、输入、输出15、算法的_性是指算法必须能够在执行有限个步骤之后结束，并且每个步骤都必须在有穷的时间内完成。 有穷性16、算法的_性是指算法中的每一个步骤必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。并且，在任何条件下，算法只能有惟一的一条执行路径，即只要输人是相同的就只能得到_的输出结果。确定性、相同 17、 算法的_性又称为算法的能行性

7、，是指算法中描述的操作是可以通过已经实现的基本运算执行有限次来实现。 可行性 18、 判断一个算法的好坏主要以下几个标准： _、 _、 _、_。 正确性、可读性、健壮性、时间效率和空间效率 19、算法分析是对一种算法所消耗的电脑资源的估算，其中包括电脑_的长短和_的大小。 运行时间、所占据空间 20、空间复杂度SPace ComPlexity也是度量一个算法好坏的标准，它所描述的是算法在运行过程中所占用_的大小。 存储空间2 2 / 5252三、判断题 1顺序存储方式只能用于存储线性结构。 2数据元素是数据的最小单位。 3算法的优劣与算法描述语言无关，但与所用电脑有关。() 4健壮的算法不会因

8、非法的输入数据而出现莫名其妙的状态。()5数据的逻辑结构是指各元素之间的逻辑关系，是根据用户需要而建立的。6数据结构、数据元素、数据项在电脑中的映像分别称为存储结构、结点、数据域。 7数据的物理结构是指数据在电脑中实际的存储形式。 8具有存取任一元素的时间相等这一特点的存储结构称为随机存取结构。9算法实际上就是程序，程序也一定是算法。()10. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。()11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。()12. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。()13. 数据的逻辑结构说明数据元素之间的顺

9、序关系,它依赖于电脑的储存结构。 ()14. 判断一个算法的好坏主要以下几个标准：正确性、有穷性、健壮性和可行性。()15算法的时间复杂度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+ fo

10、rk=0；kn；k ci jai k*bkj;4写出下面算法的时间复杂度：i=1;whilein i=i*3;5求下面函数中各条语句的频度和算法的时间复杂度：3 3 / 5252primeint 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.该算法的时间复杂度为：log

11、3(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, 2n/2,(3/2)n, n!,4 4 / 5252第二章第二章 线性表线性表一、选择题 1在一个长度为 n 的顺序表中删除第 i 个元素0inext=p-next-nextBp-next=p-nextCp=p-next-nextDp=p-next

12、; p-next=p-next-next14在一个单链表中，已知 q 所指结点是 p 所指结点的前驱，假设在 q 和 p之间插入 s 所指的结点，则执行操作。5 5 / 5252As-next=p-next;p-next=s;Bq-next=s; s-next=p;Cp-next=s-next;s-next=p;Dp-next=s; s-next=q;15在单链表中附加头结点的目的是为了 。A保证单链表中至少有一个节点B标识单链表中首结点的位置C方便运算的实现D说明单链表是线性表的链式存储16循环单链表的主要优点是 。A不再需要头指针了B从表中任意一个结点出发都能扫描到整个链表C已知某个结点的

13、位置后，能够容易找到它的前驱D在进行插入、删除操作时，能更好地保证链表不断开17非空的循环单链表 L 的尾结点 p 满足 。Ap-next=NULLBp=NULLCp-next=LDp=L18在双向循环链表中,在 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；Cq-next=p；

14、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-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线

15、性表Linear List是最简单、最常用的一种数据结构。线性表中的元素存在着_的相互关系。 一对一2线性表中有且仅有一个开始结点，表中有且仅有一个终端结点，除开始结点外，其他每个元素有且仅有一个_，除终端结点外，其他每个元素有且仅有一个_。3线性表是 nn=0个数据元素的_。其中 n 为数据元素的个数，定义为线性表的_。当 n 为零时的表称为_。4所谓顺序表Sequential LISt是线性表的_，它是将线性表中的结点按其_依次存放在内存中一组连续的存储单元中，使线性表中相邻的结点存放在_的存储单元中。5单链表不要求逻辑上相邻的存储单元在物理上也一定要相邻。它是分配一些_的存储单元来存储线

16、性表中的数据元素， 这些存储单元可以分散在内存中的_的位置上，它们在物理上可以是一片连续的存储单元，也可以是_的。因此在表示线性表这种数据结构时，必须在存储线性表元素的同时，也存储线性表的。6 6 / 52526线性表的链式存储结构的每一个结点Node需要包括两个部分：一部分用来存放元素的数据信息， 称为结点的_； 另一部分用来存放元素的指向直接后继元素的指针 (即直接后继元素的地址信息)，称为 _或_。7线性链表的逻辑关系是通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不再一致， 而是一种_存储结构， 又称为_。8如果将单链表最后一个结点的指针域改为存放链表中的头结点的地址值，

17、这样就构成了_。9为了能够快速地查找到线性表元素的直接前驱，可在每一个元素的结点中再增加一个指向其前驱的指针域，这样就构成了_。10双向链表某结点的指针 P，它所指向结点的后继的前驱与前驱的后继都是p_。11在单链表中，删除指针 P 所指结点的后继结点的语句是_。12在双循环链表中，删除指针P 所指结点的语句序列是 P-prior-nextp-next 及_。13单链表是_的链接存储表示。14可以使用_表示树形结构。15向一个长度为 n 的向量的第 i 个元素(lin+1之前插人一个元素时，需向后移动_个元素。16删除一个长度为n 的向量的第 i 个元素lin时，需向前移动_个元素。17在单链

18、表中，在指针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.非顺序、非顺序

19、映像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-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线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。(

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

21、。6.错误：顺序存储结构是静态存储结构，链式存储结构是动态存储结构。7.错误：先行表的长度是线性表中结点的个数。8.错误：注意最后一个结点。9.错误：也可以有顺序存储的形式。8 8 / 5252第三章第三章 栈和队列栈和队列一、选择题 l一个栈的序列是：a，b，c，d，e，则栈的不可能输出的序列是 。Aa，b，c，d，e Bd，e，c，b，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！0B

22、S-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；top-nextS；DS-nexttop；topS-next；6向一个带头结点、栈顶指针为top 的链栈中插人一个*S 结点的时候，应当执行语句 。 Atop-next=S； BS-next=top；top=S；CS-ne

23、xt=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-Q-front+1= =n CQ-rear = = Q-front DQ-rear +1= = Q-front9判定一个循环队列 Q最多有 n 个元素为空的条件是 。AQ-rear

24、 = = 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 的操作是 。 Afrontfront-next BS-next=rear；rear=SCrear-next=S

25、；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，3，1 D4，3，2，l9 9 / 5252 15在解决电脑主机与打印机之间速度不匹配问题

26、时通常设置一个打印数据缓冲区， 主机将要输出的数据依次写人该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个结构。 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根据栈的定义，每一次进栈的元素都在原_之上，并成为新的_；每一次出栈的元素总是当前的_，因此最后进栈的元素总是_， 所以

27、栈也称为_线性表， 简称为_表。4栈是一种操作受到限制的线性表，是一种特殊的线性表，因此栈也有_和_两种存储结构， 分别称为_和_5当栈满的时候，再进行人栈操作就会产生_，这种情况的溢出称为_；当栈空的时候，如果再进行出栈操作，也会 _，这种情况下的溢出称为_。6栈的链式存储结构简称为_，是一种_。7人们日常计算用到的表达式都被称为_，这是由于这种算术表达式的运算符被置于两个操作数中间。8 电脑中通常使用_， 这是一种将运算符置于两个操作数后面的算术表达式。这种表达式是由波兰科学家谢维奇提出的，因此又称为_9队列Queue也是一种_，但它与栈不同，队列中所有的插人均限定在表的一端进行，而所有的

28、删除则限定在表的另一端进行。允许插人的一端称为_，允许删除的一端称为_。10队列的特点是_，因此队列又被称为_的线性表，或称为_表。11队列的_又称为_，是用一组地址连续的存储单元依次存放队列中的元素。12 由于队列中的元素经常变化， 对于队列的删除和插人分别在队头和队尾进行，因此需要设置两个指针分别指向_和_，这两个指针又称为_和_。13循环顺序队列Circular Sequence Queue经常简称为_，它是将存储顺序队列的存储区域看成是一个首尾相连的一个环， 即将队首和队尾元素连接起来形成一个环形表。首尾相连的状态是通过数学上的_来实现的。14 在算法或程序中，当一个函数直接调用自己或

29、通过一系列语句间接调用自己的时候，则称这个函数为，也称为_。函数直接调用自己，则称为_； 当一个函数通过另一个函数来调用自己则称为_。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一个栈的输人序列是 12345，则栈的输出序列为 12345 是_填是

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

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

32、特殊的线性表、队尾、队头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.队尾三、判断题1栈和队列都是限制存取点的线性结构

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

34、DCACBADCBDACDBADCBA不可能的出栈序列： 共 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串与普通的线性表相比较，它的特殊性表达在串与普通的线性表相比

35、较，它的特殊性表达在 。 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

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

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

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

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

40、。其中_域用于存放数域用于存放数据，据，_域用于存放下一个结点的指针。域用于存放下一个结点的指针。 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.顺序存储

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

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

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

44、个广义表，这种说法 。 A A正确正确 B B错误错误 C C无法确定无法确定 D D以上均不以上均不对对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

45、 9广义表广义表 a a ，a a的表尾是的表尾是 。 A A ( ( ) B) B a a C Ca a D D a a 1010广义表广义表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. B

46、2. B3. B3. B4. B4. B5. A5. A6. C6. C7. A7. A8. C8. C9. C9. C10. A10. A11. B 12. B11. B 12. B二、填空题二、填空题1 1数组数组arrayarray是是 n nn n1 1个个_的有序组合，数组中的数据是的有序组合，数组中的数据是按顺序存储在一块按顺序存储在一块_的存储单元中。的存储单元中。2 2数组中的每一个数据通常称为数组中的每一个数据通常称为_，_用下标区分，其中下标的用下标区分，其中下标的个数由数组的个数由数组的_决定。决定。3 3由于电脑内存中的存储单元是一个一维的存储结构，因此对于多维数组由于

47、电脑内存中的存储单元是一个一维的存储结构，因此对于多维数组要想按顺要想按顺序存储到电脑存储单元中就必须有一个排列顺序问题。序存储到电脑存储单元中就必须有一个排列顺序问题。对于二维数组，对于二维数组，有两有两种排列形式：一种是种排列形式：一种是_；另一种是；另一种是_。4 4对于需要压缩存储的矩阵可以分为对于需要压缩存储的矩阵可以分为_和和_。对那些具有对那些具有1515 / 5252相相同同值值元元素素或或零零元元素素在在矩矩阵阵中中分分布布具具有有一一定定规规律律的的矩矩阵阵，我我们们称称之之为为_；而对于那些零元素数目远远多于非零元素数目，并且非零元素的；而对于那些零元素数目远远多于非零元

48、素数目，并且非零元素的分布没有规律的矩阵称为分布没有规律的矩阵称为_。5 5在一个在一个 n n 阶方阵阶方阵 a a 中，假设元素满足性质：中，假设元素满足性质：a aijija ajiji0=i0=i，j=n-lj=0n=0个元素的序列。记作：个元素的序列。记作：A Aa1a1，a2a2，anan ，其，其中中，A A 是是广广义义表表的的_，n n 是是它它的的_，当当 n=0n=0 的的时时候候称称为为_。9 9在一个非空的广义表中，其元素在一个非空的广义表中，其元素 a ai i可以是某一确定类型的单个元素，称可以是某一确定类型的单个元素，称为为_，也可以又是一个广义表，称为，也可以

49、又是一个广义表，称为_。1010广义表的定义是一种递归的定义，广义表是一种递归的数据结构。当广广义表的定义是一种递归的定义，广义表是一种递归的数据结构。当广义表非空的时候，称第一个元素义表非空的时候，称第一个元素 a a1 1为广义表为广义表 A A 的的_，称其余元素组成，称其余元素组成的表的表a2a2，a3a3，anan是是 A A 的的_。1111广义表的深度一般定义为广义表元素广义表的深度一般定义为广义表元素_，或者说是广义表，或者说是广义表_ 。 利利 用用 递递 归归 的的 定定 义义 ， 广广 义义 表表 的的 深深 度度 就就 是是 所所 有有 子子 表表 中中_。1.1.相同

50、类型数据、地址连续相同类型数据、地址连续2.2.数组元素、数组元素、维数数组元素、数组元素、维数3.3.以行序为主、以列序为主以行序为主、以列序为主4.4.特殊矩阵、稀疏矩阵、特殊矩阵、稀疏矩阵特殊矩阵、稀疏矩阵、特殊矩阵、稀疏矩阵5.5.对称矩阵对称矩阵6.6.三元组顺序表、三元组三元组顺序表、三元组7.7.矩阵转置矩阵转置8.8.名称、长度、空表名称、长度、空表9.9.原子、子表原子、子表10.10.表头、表尾表头、表尾11.11.最大的层数、括号的重数、最大深度加最大的层数、括号的重数、最大深度加 1 1三、判断题三、判断题1 1十字链表不是顺序存储结构。十字链表不是顺序存储结构。 2

51、2三元组表不是一个随机存取结构。三元组表不是一个随机存取结构。 3 3稀疏矩阵压缩存储后，必然会失去随机存取功能。稀疏矩阵压缩存储后，必然会失去随机存取功能。 4 4假设一个广义表的表头为空表，则此广义表也为空表。假设一个广义表的表头为空表，则此广义表也为空表。 5 5广义表是线性表的推广，是一类线性数据结构。广义表是线性表的推广，是一类线性数据结构。 6 6任何一个非空广义表，其表头可能是单元素或广义表，其表尾必定是广任何一个非空广义表，其表头可能是单元素或广义表，其表尾必定是广义义表表。7 7一个稀疏矩阵一个稀疏矩阵 Am*nAm*n 采用三元组形式表示，采用三元组形式表示，假设把三元组中

52、有关行下标与假设把三元组中有关行下标与列下标的值互换，列下标的值互换，并把并把 m m 和和 n n 的值互换，的值互换，则就完成了则就完成了 Am*nAm*n 的转置运算。的转置运算。 1616 / 52528 8数组中每个元素必定具有相同的数据类型。数组中每个元素必定具有相同的数据类型。 9 9线性表是广义表的特例。线性表是广义表的特例。 1010如果广义表中的每个元素都是原子，则广义表便成为线性表。如果广义表中的每个元素都是原子，则广义表便成为线性表。 1111广义表中原子个数即为广义表的长度。广义表中原子个数即为广义表的长度。 1212广义表最大子表的深度为广义表的深度。广义表最大子表

53、的深度为广义表的深度。 1313广义表中元素最大的层数称为广义表的深度。广义表中元素最大的层数称为广义表的深度。 1414广义表是一种多层次结构。广义表是一种多层次结构。 1515广义表是一种线性结构。广义表是一种线性结构。 1616广义表是一种共享结构。广义表是一种共享结构。 1717广义表是一种递归结构。广义表是一种递归结构。 1818广义表是一种单链表结构。广义表是一种单链表结构。 1.1.正确：十字链表是链接存储结构。正确：十字链表是链接存储结构。2.2.正确：正确： 具有存取任一元素的时间相等这一特点的存储结构称为随机存取具有存取任一元素的时间相等这一特点的存储结构称为随机存取结构，

54、三元组表存储矩阵的时候，要访问第结构，三元组表存储矩阵的时候，要访问第 i i 行行 j j 列元素必须扫描三元组表，列元素必须扫描三元组表，显然查找三元组表前面的元素与后面元素所消耗的时间不同，因此三元组表不显然查找三元组表前面的元素与后面元素所消耗的时间不同，因此三元组表不是一个随机存取结构。是一个随机存取结构。3.3.正确：随机存取结构是指存取任一元素的时间相等这一特点的存储结正确：随机存取结构是指存取任一元素的时间相等这一特点的存储结构，对稀疏矩阵压缩存储所用的存储结构是十字链表和三元组，而这两种存储构，对稀疏矩阵压缩存储所用的存储结构是十字链表和三元组，而这两种存储结构都不是随机存取

55、结构。结构都不是随机存取结构。4.4.错误：如广义表错误：如广义表 L=(),(A, B)L=(),(A, B)为非空，而表头为空表。为非空，而表头为空表。5.5.错误：广义表是线性表的推广，是一类非线性数据结构。错误：广义表是线性表的推广，是一类非线性数据结构。6.6.正确：表尾的定义是除表头元素以外其余元素可以为空构成的表，正确：表尾的定义是除表头元素以外其余元素可以为空构成的表，所以必定是广义表。所以必定是广义表。7.7.错误：应该在互换行列后再按照行优先重新存储。错误：应该在互换行列后再按照行优先重新存储。8.8.正确。正确。9.9.正确。正确。10.10.正确。正确。11.11.错误

56、：广义表中元素个数为广义表的长度。错误：广义表中元素个数为广义表的长度。12.12.错误：广义表最大子表的深度加错误：广义表最大子表的深度加 1 1 为广义表的深度。为广义表的深度。13.13.正确。正确。14.14.正确。正确。15.15.错误：广义表是一种非线性结构。错误：广义表是一种非线性结构。16.16.正确。正确。17.17.正确。正确。18.18.正确：注意单链表结构不一定是线性的。正确：注意单链表结构不一定是线性的。1717 / 5252第六章第六章 树和二叉树树和二叉树一、选择题一、选择题l l 在二叉树后序遍历中，在二叉树后序遍历中， 任一个结点均在其子女结点后面，任一个结点

57、均在其子女结点后面， 这种说法这种说法 。A A正确正确 B B不正确不正确 C C无法判断无法判断 D D以上均不对以上均不对2 2 在二叉树先序遍历中，在二叉树先序遍历中， 任一个结点均在其子女结点前面，任一个结点均在其子女结点前面， 这种说法这种说法 。A A正确正确 B B不正确不正确 C C无法判断无法判断 D D以上均不对以上均不对3 3设深度为设深度为 h h 的二叉树上只有叶子结点和同时具有左右子树的结点，则此的二叉树上只有叶子结点和同时具有左右子树的结点，则此类二叉树中所包含的结点数目至少为类二叉树中所包含的结点数目至少为 。 A A 2h B2h B 2h C2h C 2h

58、2h1 1D D 2h-l2h-l4 4二叉村第二叉村第 k k 层上最多有层上最多有个结点。个结点。 A A 2k B2k B 2 2k k-1-1C C 2 2k-1k-1 D D 2k+12k+15 5二叉树的深度为二叉树的深度为 k k，则二叉树最多有，则二叉树最多有个结点。个结点。k-1k-1k k A A2k B2k B2k-1 C2k-1 C2 2D D2 2 -1-16 6设某一二叉树先序遍历为设某一二叉树先序遍历为abdecabdec，中序遍历为，中序遍历为dbeacdbeac，则该二叉树后序遍，则该二叉树后序遍历的顺序是历的顺序是 。 A A abdec Babdec B

59、debacdebacC C debcadebca D D abedcabedc7 7设某一二叉树中序遍历为设某一二叉树中序遍历为badcebadce，后序遍历为，后序遍历为bdecabdeca，则该二叉树先序遍，则该二叉树先序遍历的顺序是历的顺序是 。 A A adbec Badbec B decab Cdecab C debacdebacD D abodeabode8 8将一棵树将一棵树 T T 转换为一棵二叉树转换为一棵二叉树 T2T2，则，则 T T 的先序遍历是的先序遍历是 T2T2 的的 。A A先序先序 B B中序中序 C C后序后序 D D无法确定无法确定9 9将一棵树将一棵树

60、T T 转换为一棵二叉树转换为一棵二叉树 T2T2，则，则 T T 的后序遍历是的后序遍历是 T2T2 的的 。A A先序先序B B中序中序 C C后序后序 D D无法碉定无法碉定l0l0树最适合于用来表示树最适合于用来表示 。A A线性结构的数据线性结构的数据 B B顺序结构的数据顺序结构的数据C C元素之间无前驱和后继关系的数据元素之间无前驱和后继关系的数据D D元素之间有包含和层次关系的数据元素之间有包含和层次关系的数据1111二叉树的叶子结点在先序、中序和后序遍历过程中的相对秩序二叉树的叶子结点在先序、中序和后序遍历过程中的相对秩序 。A A发生改变发生改变B B不发生改变不发生改变C

61、 C无法确定无法确定 D D以上均不正确以上均不正确1212 设一棵二叉树度为设一棵二叉树度为 2 2 的结点数是的结点数是 7 7，度为，度为1 1 的结点数是的结点数是 6 6，则叶子结点，则叶子结点数是数是 。A A6 B6 B7 7C C8 8 D D9 91313用顺序存储的方法，用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组存放在一维数组 R1R1 nn中，假设结点中，假设结点 RiRi有左孩子，则其左孩子是有左孩子，则其左孩子是 。A AR2i-1 BR2i-1 BR2i+1R2i+1C CR2iR2i D

62、 DR2/iR2/i144144用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组序存放在一维数组 R1R1 nn中，中， 假设结点假设结点 RiRi有右孩子，有右孩子， 则其右孩子是则其右孩子是 。A AR2i-1R2i-1B BR2iR2ill C CR2i DR2i DR2/iR2/i1515 一棵非空的二叉树，一棵非空的二叉树， 先序遍历与后序遍历正好相反，先序遍历与后序遍历正好相反， 则该二叉树满足则该二叉树满足 。A A无左孩子无左孩子 B B无右孩子无右孩子C C只有一个叶子结点只有一个叶子结点

63、 D D任意二叉树任意二叉树1616设设 a a、b b 为一棵二叉树的两个结点，为一棵二叉树的两个结点，在后序遍历中，在后序遍历中，a a 在在 b b 前的条件是前的条件是 。A Aa a 在在 b b 上方上方 B Ba a 在在 b b 下方下方1818 / 5252C Ca a 在在 b b 左方左方 D Da a 在在 b b 右方右方1717线索二叉树是一种线索二叉树是一种 。A A逻辑结构逻辑结构 B B线性结构线性结构C C逻辑和线性结构逻辑和线性结构D D物理结构物理结构1818N N 个结点的线索二叉树中，线索的数目是个结点的线索二叉树中，线索的数目是 。A AN-1N-

64、1B BN N1 1 C C2N D2N D2N2N1 11919 权值为权值为 l l， 2 2， 6 6， 8 8 的四个结点构成的哈夫曼树的带权路径长度是的四个结点构成的哈夫曼树的带权路径长度是 。A A18 B18 B28 C28 C1919D D29292020实现任意二叉树的后序遍历的非递归算法而不使用栈结构，实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最正确方案最正确方案是二叉村采用是二叉村采用存储结构。存储结构。A A二叉链表二叉链表 B B广义表存储结构广义表存储结构C C三叉链表三叉链表 D D顺序存储结构顺序存储结构2121对一个满二叉树，对一个满二叉树，m m

65、个树叶，个树叶，k k 个分枝结点，个分枝结点，n n 个结点，则个结点，则 。A An nm m1 B1 Bm+1=2n Cm+1=2n Cm mk-1k-1D Dn=2k+1n=2k+12323具有五层结点的二叉平衡树至少有具有五层结点的二叉平衡树至少有个结点。个结点。A A1010B B1212 C C15 D15 D17172424设设 n n，m m 为一棵二叉树上的二个结点，在中序遍历时，为一棵二叉树上的二个结点，在中序遍历时，n n 在在 m m 前的条件前的条件是是 。A An n 在在 m m 右方右方 B Bn n 是是 m m 祖先祖先C Cn n 在在 m m 左方左方

66、 D Dn n 是是 m m 子孙子孙2525线索二又树是一种线索二又树是一种结构。结构。A A逻辑逻辑 B B逻辑和物理逻辑和物理C C物理物理 D D线性线性2626将一棵有将一棵有 100100 个结点的完全二又树从根这一层开始，个结点的完全二又树从根这一层开始，每一层上从左到右每一层上从左到右依次对结点进行编号，根结点的编号为依次对结点进行编号，根结点的编号为 1 1，则编号为，则编号为 4949 的结点的左孩子编号为的结点的左孩子编号为 。A A9898 B B99 C99 C50 D50 D4848二、填空题二、填空题 1 1树树(Tree)(Tree)是是 n(nn(n0)0)个

67、结点的个结点的_集。集。 2 2任何任何 一个非空树一个非空树 中：有且仅有中：有且仅有 一个特一个特 定的结点，称定的结点，称 为该树为该树 的的_的结点，的结点，_结点之外的其余结点可分为结点之外的其余结点可分为 m(mm(m0)0)个互个互不相交的有限集合不相交的有限集合 T1T1，T2T2，TmTm，且其中每一个集合又是一棵树，称之为，且其中每一个集合又是一棵树，称之为_的的_。 3 3树的树的_是指一个数据元素及指向其子树的分支。通常通过是指一个数据元素及指向其子树的分支。通常通过一个一个_来描述，在树型表示中，用一个圆圈及短线表示。来描述，在树型表示中，用一个圆圈及短线表示。 4

68、4结点的度是指结点所拥有的结点的度是指结点所拥有的_。 5 5树内各结点度的树内各结点度的_为树的度。为树的度。 6 6 度大于度大于 0 0 的结点称为的结点称为_或或_。 7 7_称为叶子结点，简称为叶子，又称作终端结点。称为叶子结点，简称为叶子，又称作终端结点。 8 8一个结点的一个结点的_，或者说一个结点的，或者说一个结点的_称为该称为该结点的孩子结点，简称为孩子。结点的孩子结点，简称为孩子。 9 9一个结点称为其后继结点即孩子结点的一个结点称为其后继结点即孩子结点的_。 10 10一个结点的子树中的任一结点都称为该结点的一个结点的子树中的任一结点都称为该结点的_。 11 11 从根到

69、该结点所经分支上的所有结点称为该结点的从根到该结点所经分支上的所有结点称为该结点的_。1919 / 5252 12 12具有具有_的结点互称为兄弟结点，的结点互称为兄弟结点，简称为兄弟。简称为兄弟。 13 13从根结点开始定义，根为从根结点开始定义，根为_层，根的孩子为层，根的孩子为_层，层，依次往下类推，假设某结点在第依次往下类推，假设某结点在第 k k 层，则其子树的根就在层，则其子树的根就在_层。层。 14 14其双亲在同一层次上的结点互称为其双亲在同一层次上的结点互称为_。 15 15树中结点的树中结点的_称为树的深度，又称为树的高度。称为树的深度，又称为树的高度。 16 16如果树中

70、各结点的各子树从左至右是有序排列，不可互换的，则称如果树中各结点的各子树从左至右是有序排列，不可互换的，则称该树为该树为_。 17 17如果树中各结点的各子树无排列顺序，即可以互换位置，则称为该如果树中各结点的各子树无排列顺序，即可以互换位置，则称为该树为树为_。 18 18n(nn(n0)0)棵互不相交的树的集合称为棵互不相交的树的集合称为_。 19 19二又树二又树Binary TreeBinary Tree是结点的有限集合，这个集合或者是空，是结点的有限集合，这个集合或者是空，或者是由一个根结点和或者是由一个根结点和 _的称为的称为_和和_的二的二叉树构成。叉树构成。 20 20二叉树第

71、二叉树第 i i 层上最多有层上最多有_个结点。个结点。 21 21深度为深度为 k k 的二又树最多有的二又树最多有_个结点个结点(k(kl)l)。 22 22在任意二叉树中，叶子结点的数目在任意二叉树中，叶子结点的数目( (即度为即度为 0 0 的结点数的结点数) )等于度为等于度为 2 2的结点数的结点数_。 23 23一棵深度为一棵深度为 k k 且具有且具有 2 2k k-1-1 个结点的二叉树称为个结点的二叉树称为_。这类。这类二叉树的特点是，二叉树中每一层结点的个数都是二叉树的特点是，二叉树中每一层结点的个数都是_的个数。的个数。 24 24_是那种在一棵二叉树中，除最后一层外，

72、假设其余层都是那种在一棵二叉树中，除最后一层外，假设其余层都是满的，并且最后一层或者是满的，或者所缺少的结点都在右边。是满的，并且最后一层或者是满的，或者所缺少的结点都在右边。 25 25具有具有 n n 个结点的完全二叉树的深度是个结点的完全二叉树的深度是_。 26 26对于一棵有对于一棵有n n 个结点的完全二叉树的结点进行编号自上而下，自个结点的完全二叉树的结点进行编号自上而下，自左至右左至右 ，则对任一结点，则对任一结点 i il li in n ，如果结点，如果结点 i=li=l，则结点，则结点 i i 是二叉树的是二叉树的_，无双亲；如果结点，无双亲；如果结点ilil，则其双亲，则

73、其双亲Parent(i)Parent(i)的序号是结点的序号是结点_； 如果如果 2i2in n， 则结点则结点 i i 的左孩子的左孩子 Lchild(BT,Lchild(BT,， i i 是是_，否则结点否则结点 i i 无左孩子无左孩子( (结点结点 i i 必为叶子结点必为叶子结点) )；如果；如果 2i2il ln n，则结点，则结点 i i 的右孩的右孩子子 RChild RChildBTBT，i i的序号是的序号是_；否则该结点无右孩子。；否则该结点无右孩子。 27 27二叉树的顺序存储结构是用二叉树的顺序存储结构是用_存储二叉树的数据存储二叉树的数据元素。元素。 28 28_是

74、指按照某条搜索路径访问树中的某个结点，是指按照某条搜索路径访问树中的某个结点，使得树使得树中每个结点均被访问一次，而且仅被访问一次。中每个结点均被访问一次，而且仅被访问一次。 29 29先序遍历二叉树的操作定义为：假设二叉树为空，则为空操作；否先序遍历二叉树的操作定义为：假设二叉树为空，则为空操作；否则进行如下操作：访问二叉树则进行如下操作：访问二叉树 _；先序遍历二叉树；先序遍历二叉树_；先序遍历二叉树先序遍历二叉树_。 30 30中序遍历二叉树的操作定义为：假设二叉树为空，则为空操作；否中序遍历二叉树的操作定义为：假设二叉树为空，则为空操作；否则进行如下操作：中序遍历二叉树则进行如下操作：

75、中序遍历二叉树 _；访问二又树；访问二又树_；中序；中序遍历二又树遍历二又树_。 31 31后序遍历二叉树的操作定义为：假设二叉树为空，则为空操作；否后序遍历二叉树的操作定义为：假设二叉树为空，则为空操作；否则进行如下操作：后序遍历二叉树则进行如下操作：后序遍历二叉树 _；后序遍历二叉树；后序遍历二叉树_；访问二叉树访问二叉树_。 32 32线索二叉树线索二叉树ThreadedThreaded BinaryBinary TreeTree是充分利用二义链表的是充分利用二义链表的 n+1 n+1个空的指针域作为线索来标志每一个结点的个空的指针域作为线索来标志每一个结点的 _和和_信息。当某信息。当

76、某个结点有左孩子的时候，使其个结点有左孩子的时候，使其_指向其左孩子，无左孩子的时候，使指向其左孩子，无左孩子的时候，使2020 / 5252其左指针域指向该结点的其左指针域指向该结点的_；当某个结点有有孩子的时候，使其右指；当某个结点有有孩子的时候，使其右指针域指向该结点的针域指向该结点的_，无右孩子的时候，使其有指针域指向该结点的，无右孩子的时候，使其有指针域指向该结点的_。 33 33线索二叉树的线索链表中，指向结点前驱和后继的指针称为线索二叉树的线索链表中，指向结点前驱和后继的指针称为_；加上线索的二叉树称为；加上线索的二叉树称为 _；对二叉树以某种次序进；对二叉树以某种次序进行遍历使

77、其成为线索二叉树的过程称为行遍历使其成为线索二叉树的过程称为_。 34 34 树树 的的 存存 储储 结结 构构 常常 见见 的的 有有 _ 、 _ 和和_。 35 35 树的先序遍历过程如下：树的先序遍历过程如下：假设树为空，假设树为空，则进行空操作；则进行空操作；假设树非空，假设树非空，则：访问树的则：访问树的_；依次先序遍历树的；依次先序遍历树的_。 36 36树的后序遍历过程为：假设树为空，则进行空操作；假设树非空，树的后序遍历过程为：假设树为空，则进行空操作；假设树非空，则：依次后序遍历则：依次后序遍历_；访问；访问_。 37 37森林的先序遍历过程为：假设森林非空，则：森林的先序遍

78、历过程为：假设森林非空，则：1 1访问森林中第一棵树的访问森林中第一棵树的_。2 2先序遍历第一棵树中先序遍历第一棵树中_。3 3先序遍历先序遍历_。 38 38森林的后序遍历过程为：假设森林非空，则：森林的后序遍历过程为：假设森林非空，则：l l后序遍历森林中第一棵树的后序遍历森林中第一棵树的_。2 2访问第一棵树的访问第一棵树的_。3 3后序遍历后序遍历_。 39 39从树中一个结点到另一个结点之间的从树中一个结点到另一个结点之间的_称为这两个结点的称为这两个结点的路径。路径。 40 40路径上的分支数目称为路径上的分支数目称为_。 41 41树的路径长度是指从树根到每一结点的树的路径长度

79、是指从树根到每一结点的_。 42 42将树中的结点赋上一个有着某种意义的实数，将树中的结点赋上一个有着某种意义的实数，称此实数为该结点的称此实数为该结点的_。 43 43树的带权路径长度为树中所有叶子结点的树的带权路径长度为树中所有叶子结点的_。 44 44哈夫曼树哈夫曼树Huffman TreeHuffman Tree又称又称_。它是。它是 n n 个带权叶子个带权叶子结点构成的所有二叉树中，带权路径长度结点构成的所有二叉树中，带权路径长度 WPL_WPL_。 45 45，所谓前缀编码是指在所有对字符的编码中，任何一个字符都不是，所谓前缀编码是指在所有对字符的编码中，任何一个字符都不是_。4

80、646 已已 知知完完全全 二二叉叉树树 的的第第八八 层层有有 8 8 个个结结 点点，则则 其其叶叶子子 结结点点 数数是是_。4747在有在有 n n 个叶子结点的哈夫曼树中，总结点数是个叶子结点的哈夫曼树中，总结点数是_。4848已知完全二又树的第已知完全二又树的第 7 7 层有层有 1010 个叶子结点，则整个二又树的结点数最个叶子结点，则整个二又树的结点数最多是多是_。4949已知二叉树中叶子数为已知二叉树中叶子数为 5050，仅有一个孩子的结点数为，仅有一个孩子的结点数为 3030，则总结点数，则总结点数为为_。5050一棵树一棵树 T T 采用二叉链表采用二叉链表 BTBT 存

81、储，如果树存储，如果树 T T 中某结点为叶子结点，则在中某结点为叶子结点，则在二叉链表二叉链表 BTBT 中所对应的结点一定满足中所对应的结点一定满足_。5151 在二叉链表中，在二叉链表中， 判断某指针判断某指针 P P 所指结点为叶子结点的条件是所指结点为叶子结点的条件是_。5252假设以假设以44，5 5，6 6，7 7，88作为叶子结点的权值构造哈夫曼树，则其带权作为叶子结点的权值构造哈夫曼树，则其带权路径长度是路径长度是_。5353已已知知二二叉叉树树有有 5050 个个叶叶子子结结点点，则则该该二二叉叉树树的的总总结结点点数数至至少少是是2121 / 5252_。54543 3

82、个结点可构成个结点可构成_棵不同形态的树。棵不同形态的树。5555 已已 知知完完全全 二二叉叉树树 的的第第七七 层层有有 8 8 个个结结 点点，则则 其其叶叶子子 结结点点 数数是是_._.5656将一棵有将一棵有 100100 个结点的完全二叉树从根这一层开始，个结点的完全二叉树从根这一层开始，每一层上从左到右每一层上从左到右依次对结依次对结点进行编号，根结点的编号为点进行编号，根结点的编号为 1 1，则编号为，则编号为 4949 的结点的左孩子编号的结点的左孩子编号为为_。5757假设要对某二叉排序树进行遍历，假设要对某二叉排序树进行遍历，保证输出的所有结点序列按键值递增保证输出的所

83、有结点序列按键值递增次序排列，次序排列，应对该二叉树采用应对该二叉树采用_遍历法。遍历法。1.1.有限有限2.2.根、根、根、子树根、根、根、子树3.3.结点、记录结点、记录4.4.子树数目子树数目5.5.最大值最大值6.6.分支结点、非终端结点分支结点、非终端结点7.7.度为零的结点度为零的结点8.8.后继结点、子树的根后继结点、子树的根9.9.双亲结点双亲结点10.10.子孙结点子孙结点11.11.祖先结点祖先结点12.12.同一双亲同一双亲13.13.第一、第二、第第一、第二、第 k+1k+114.14.堂兄弟堂兄弟15.15.最大层次最大层次16.16.有序树有序树17.17.无序树无

84、序树18.18.森林森林19.19.两棵互不相交、左子树、右子树两棵互不相交、左子树、右子树20. 2i-120. 2i-121. 2k-121. 2k-122.22.加加 1 123.23.满二叉树、最大结点满二叉树、最大结点24.24.完全二叉树完全二叉树25.25.log2n126.26.根、根、i/2、2i2i、2i+12i+127.27.一组连续的存储单元一组连续的存储单元28.28.遍历二叉树遍历二叉树29.29.根结点、左子树、右子树根结点、左子树、右子树30.30.左子树、根结点、右子树左子树、根结点、右子树31.31.左子树、右子树、根结点左子树、右子树、根结点32.32.前

85、驱、后继、左指针域、直接前驱结点、右孩子、直接后继结点前驱、后继、左指针域、直接前驱结点、右孩子、直接后继结点33.33.线索、线索二叉树、线索化线索、线索二叉树、线索化2222 / 525234.34.双亲表示法、孩子表示法、孩子兄弟表示法双亲表示法、孩子表示法、孩子兄弟表示法35.35.根结点、各子树根结点、各子树36.36.根的各子树、根结点根的各子树、根结点37.37.根结点、根结点的子树、除第一棵树之外剩余的树构成的森林根结点、根结点的子树、除第一棵树之外剩余的树构成的森林38.38.根结点的子树、根结点、除第一棵树之外剩余的树构成的森林根结点的子树、根结点、除第一棵树之外剩余的树构

86、成的森林39.39.分支分支40.40.路径长度路径长度41.41.路径长度之和路径长度之和42.42.权权43.43.带权路径长度之和带权路径长度之和44.44.最优二叉树、最小的二叉树最优二叉树、最小的二叉树45.45.另一个字符的前缀另一个字符的前缀46. 6846. 6847. 2n-147. 2n-148. 7448. 7449. 12949. 12950.50.左子树为空左子树为空51. (p-lchild=nil)&(p-rchild=nil)51. (p-lchild=nil)&(p-rchild=nil)52. 6952. 6953. 9953. 9954. 254. 255

87、. 3655. 3656. 9856. 9857.57.中序中序三、判断题三、判断题1 1完全二叉树的某个结点假设无左孩子，则它必然是叶结点。完全二叉树的某个结点假设无左孩子，则它必然是叶结点。 2 2存在这样一种二叉树，对它采用任何次序的遍历结果相同。存在这样一种二叉树，对它采用任何次序的遍历结果相同。 3 3度为二的树称为二叉树。度为二的树称为二叉树。 4 4二叉树中不存在度大于二叉树中不存在度大于 2 2 的结点。的结点。 5 5当二叉树中某个结点只有一棵子树的时候，无左右子树之分。当二叉树中某个结点只有一棵子树的时候，无左右子树之分。 6 6任何一棵二叉树都可以不用栈实现前序线索树的前

88、序遍历。任何一棵二叉树都可以不用栈实现前序线索树的前序遍历。 7 7哈夫曼编码是一种前缀编码，不允许出现两个字符编码相同的情况。哈夫曼编码是一种前缀编码，不允许出现两个字符编码相同的情况。8 8完全二叉树某结点有右子树，则必然有左子树。完全二叉树某结点有右子树，则必然有左子树。 9 9前序遍历一棵二叉树的结点就可以得到排好序的结点序列。前序遍历一棵二叉树的结点就可以得到排好序的结点序列。 1010 将一棵拥有子树的树转换为二叉树后，将一棵拥有子树的树转换为二叉树后， 根结点可能没有左子树。根结点可能没有左子树。 1111根据二叉树的前序遍历和中序遍历可以得到二又树的后序遍历。根据二叉树的前序遍

89、历和中序遍历可以得到二又树的后序遍历。 1212哈夫曼树是带权路径长度最短的二叉树。哈夫曼树是带权路径长度最短的二叉树。 1313哈夫曼树上权值较大的结点离根较远。哈夫曼树上权值较大的结点离根较远。 1414中序遍历森林与后序遍历与森林相对应的二叉树结果相同。中序遍历森林与后序遍历与森林相对应的二叉树结果相同。 1515在二叉树中，具有一个孩子的结点，在中序遍历序列中，没有后继子女在二叉树中，具有一个孩子的结点，在中序遍历序列中，没有后继子女结结点点。2323 / 52521616先序遍历森林与先序遍历相对应的二叉树结果不同。先序遍历森林与先序遍历相对应的二叉树结果不同。 1717假设一棵二叉

90、树的任一非叶子结点的度为假设一棵二叉树的任一非叶子结点的度为 2 2，则该二叉树为满二叉树。，则该二叉树为满二叉树。1818二叉树只能采用二叉链表来存储。二叉树只能采用二叉链表来存储。 1919给定结点数的平衡二叉树的高度是惟一的。给定结点数的平衡二叉树的高度是惟一的。 1.1.正确：根据完全二叉树定义可以知道，假设完全二叉树无左孩子，则它正确：根据完全二叉树定义可以知道，假设完全二叉树无左孩子，则它必然无右孩子。必然无右孩子。2.2.正确：二叉树只有一个结点的时候。正确：二叉树只有一个结点的时候。3.3.错误：二叉树子树还有左右次序之分。错误：二叉树子树还有左右次序之分。4.4.正确。正确。

91、5.5.错误。错误。6.6.正确。正确。7.7.正确。正确。8.8.正确：根据完全二叉树定义可以知道，正确：根据完全二叉树定义可以知道，9.9.错误：中序遍历一棵二叉树的结点就可以得到排好序的结点序列。错误：中序遍历一棵二叉树的结点就可以得到排好序的结点序列。10.10.错误：将一棵拥有子树的树转换为二叉树后，根结点必然有左子树。错误：将一棵拥有子树的树转换为二叉树后，根结点必然有左子树。11.11.正确。正确。12.12.正确。正确。13.13.错误：哈夫曼树的路径上权值较大的结点离根较近。错误：哈夫曼树的路径上权值较大的结点离根较近。14.14.错误：后序遍历森林与中序遍历与森林相对应的二

92、叉树结果相同。错误：后序遍历森林与中序遍历与森林相对应的二叉树结果相同。15.15.错误：在二叉树中，具有一个左孩子的结点，在中序遍历序列中，没错误：在二叉树中，具有一个左孩子的结点，在中序遍历序列中，没有后继子女结点。有后继子女结点。16.16.错误：前序遍历森林与前序遍历与森林相对应的二叉树结果相同。错误：前序遍历森林与前序遍历与森林相对应的二叉树结果相同。17.17.错误：错误： 任一非叶子结点的度为任一非叶子结点的度为 2 2 也不能保证满足满足满二叉树的定义。也不能保证满足满足满二叉树的定义。18.18.错误：也可以采用顺序存储和三叉链表等形式进行表示。错误：也可以采用顺序存储和三叉

93、链表等形式进行表示。19.19.错误：给定结点数的平衡二叉树的高度不一定是惟一的。错误：给定结点数的平衡二叉树的高度不一定是惟一的。四、综合题四、综合题1 1一棵树表达成如下形式：一棵树表达成如下形式：D DAA，B B，C C，D D，E E，F F，G G， H H，I I，J J，K K，L L，M M，N N，OOR=R=A A，B B，A A，C C，A A，D D，B B，E E，B B，F F，C C，G G，D D，H H，D D，I I，D D，J J，K K，F F，K K，L L，F F，M M，I I，N N，I I，O O其中其中 D D 为结点集合，为结点集合，R

94、R 为边的集合。请根据以上内容答复以下问题：为边的集合。请根据以上内容答复以下问题：(1)(1) 画出这棵树。画出这棵树。(2)(2) 该树的根结点是哪一个？该树的根结点是哪一个？(3)(3) 哪些是叶子结点？哪些是叶子结点？(4) F(4) F 结点的双亲是谁？结点的双亲是谁？(5) F(5) F 结点的祖先是哪些？结点的祖先是哪些？(6) F(6) F 结点的孩子是哪些？结点的孩子是哪些？(7) F(7) F 结点的兄弟是哪些？结点的兄弟是哪些？(8) F(8) F 结点的堂兄弟是哪些？结点的堂兄弟是哪些？(9) F(9) F 结点的度是多少？结点的度是多少？(10)F(10)F 结点的层

95、次是多少？结点的层次是多少？2424 / 5252(11)D(11)D 结点的子孙有哪些？结点的子孙有哪些？(12)(12) 以结点以结点 D D 为根的子树度是多少？为根的子树度是多少？(13)(13) 以结点以结点 D D 为根的子树层是多少？为根的子树层是多少？(14)(14) 该树的层是多少？该树的层是多少？(15)(15) 该树的度是多少？该树的度是多少？2 2画出图画出图 6-16-1 中树的二叉树表示形式。中树的二叉树表示形式。a ab bc c图图 6-l6-l3 3已知某二叉树的先序遍历的结果是：已知某二叉树的先序遍历的结果是：A A，B B，D D，QCQC，E E，H H

96、，L L，I I，K K，M M，F F 和和 J J，它的中序遍历的结果是：，它的中序遍历的结果是：QDQD，B B，A A，L L，H H，E E，K K，LMLM，C C，F F 和和 J J，请画，请画出这棵二叉树，并且写出该二叉树后序通历的结果。出这棵二叉树，并且写出该二叉树后序通历的结果。4 4写一个将一棵二叉树复制给另一棵二又树的算法。写一个将一棵二叉树复制给另一棵二又树的算法。5 5已知个二叉树用二叉链表表示，其根指针为已知个二叉树用二叉链表表示，其根指针为 t t，请写一个算法，从根，请写一个算法，从根结点开始按层次通历该二叉树，同层的结点接从左到右的次序进行访问。结点开始按

97、层次通历该二叉树，同层的结点接从左到右的次序进行访问。6 6已知一棵二叉树的先序遍历序列和中序遍历序列，请写出根据二又树先已知一棵二叉树的先序遍历序列和中序遍历序列，请写出根据二又树先序遍历序列和中序遍历序列构造一棵二叉树的算法。序遍历序列和中序遍历序列构造一棵二叉树的算法。7 7假设一棵哈夫曼树共有假设一棵哈夫曼树共有 n0n0 个叶子结点，试证明树中共有个叶子结点，试证明树中共有 2no-l2no-l 个结点。个结点。8 8假设通信用的报文由假设通信用的报文由 9 9 个字母个字母 A A、B B、C C、D D、E E、F F、G G、H H 和和 I I 构成，它们构成，它们出现的频率

98、分别是：出现的频率分别是：1010、2020、5 5、1515、8 8、2 2、3 3、7 7 和和 3030。请用这。请用这 9 9 个字母出现个字母出现得频率作为权值求：得频率作为权值求：l l设计一棵哈夫曼树。设计一棵哈夫曼树。2 2计算其带权路径长度计算其带权路径长度 WPLWPL 值。值。3 3写出每个字符的哈夫曼编码。写出每个字符的哈夫曼编码。1.1.1 1该树的图形如图该树的图形如图 B-1B-1 所示。所示。ABCDEFGHIJKLMNO图图 B-1B-12 2该树的根结点是该树的根结点是 A A。3 3叶子结点是：叶子结点是：E E、K K、L L、M M、G G、H H、N

99、 N、O O 和和 J J。4 4F F 结点的双亲是结点的双亲是 B B。5 5F F 结点的祖先是结点的祖先是 A A 和和 B B。2525 / 52526 6F F 结点的孩子是结点的孩子是 K K、L L 和和 M M。7 7F F 结点的兄弟是结点的兄弟是 E E。8 8F F 结点的堂兄弟是结点的堂兄弟是 G G、H H、I I 和和 J J。9 9F F 结点的度是结点的度是 3 3。1010F F 结点的层是结点的层是 3 3。1111D D 结点的子孙有结点的子孙有 I I、N N 和和 O O。1212以结点以结点 D D 为根的子树度为为根的子树度为 3 3。1313以

100、结点以结点 D D 为根的子树层为为根的子树层为 3 3。1414该树的层是该树的层是 4 4。1515该树的度是该树的度是 3 3。2.2.此题树对应的二叉树形式如图此题树对应的二叉树形式如图 B-2B-2 所示。所示。AAABBBCDCECEFGDKHLMIJN(a)(b)(c)图图 B-2B-23.3.该二叉树的图形表示如图该二叉树的图形表示如图 B-3B-3 所示，所示， 该二叉树后序遍历的结果是：该二叉树后序遍历的结果是： G G、 D D、B B、L L、H H、K K、M M、I I、E E、J J、F F、C C 和和 A A。ABDGLHKEIMCFJ图图 B-3B-34.4

101、.用递归方法建立二叉树并求其深度的算法如下所示：用递归方法建立二叉树并求其深度的算法如下所示：define NULL 0define NULL 0typedef struct btnodetypedef struct btnode elemtype data;elemtype data;struct btnode *lchild, *rchild;struct btnode *lchild, *rchild;bitnode, *bitree;bitnode, *bitree;2626 / 5252bitnode *CreateBiTree()bitnode *CreateBiTree() /*

102、/*用递归方法建立一棵二叉树用递归方法建立一棵二叉树*/*/bitnode *t;bitnode *t;char c;char c;printf(Please input the data,# is the end.n)printf(Please input the data,# is the end.n)c=getchar();c=getchar();if ( c=# )if ( c=# )return(NULL);return(NULL);elseelse t=( bitnode * )malloc (sizeof(bitnode); /*t=( bitnode * )malloc (si

103、zeof(bitnode); /*生成新结点生成新结点*/*/t-data=c;t-data=c; /*/*为数据域赋值为数据域赋值*/*/t-lchild=CreateBiTree();t-lchild=CreateBiTree();/*/*递归创建左子树递归创建左子树*/*/t-rchild=CreateBiTree();t-rchild=CreateBiTree();/*/*递归创建右子树递归创建右子树*/*/return(t);return(t); /*CreateBiTree()*/*CreateBiTree()*/int TreeDepth(bitnode *p)int TreeD

104、epth(bitnode *p) /*/*递归求二叉树深度递归求二叉树深度*/*/int hl,hr,h;int hl,hr,h;if ( p!=NULL )if ( p!=NULL ) hl=TreeDepth(p-lchild);hl=TreeDepth(p-lchild); /*/*递归求左子树深度递归求左子树深度*/*/hr=TreeDepth(p-rchild);hr=TreeDepth(p-rchild); /*/*递归求右子树深度递归求右子树深度*/*/if ( hlhr )if ( hlhr )h=hl;h=hl;elseelseh=hr;h=hr;return(hreturn

105、(h1);/*1);/*返回较大左右子树深度加返回较大左右子树深度加 1*/1*/ elseelsereturn(0);return(0);/*TreeDepth*/*TreeDepth*/5.5.将一棵二叉树复制给另一棵二叉树的算法如下所示：将一棵二叉树复制给另一棵二叉树的算法如下所示：define NULL 0define NULL 0typedef struct btnodetypedef struct btnode elemtype data;elemtype data;struct btnode *lchild, *rchild;struct btnode *lchild, *rch

106、ild;bitnode, *bitree;bitnode, *bitree;2727 / 5252bitree *CopyTree( bitnode *p )bitree *CopyTree( bitnode *p ) /*/*复制一棵二叉树复制一棵二叉树*/*/bitnode *t;bitnode *t;if ( p!=NULL )if ( p!=NULL ) t=(bitnode *)malloc (sizeof (bitnode);t=(bitnode *)malloc (sizeof (bitnode);t-data=p-data;t-data=p-data;t-lchild=Copy

107、Tree(p-lchild);t-lchild=CopyTree(p-lchild);t-rchild=CopyTree(p-rchild);t-rchild=CopyTree(p-rchild);return(t);return(t); elseelsereturn(NULL);return(NULL);/*CopyTree*/*CopyTree*/6.6.可以使用队列可以使用队列 Q Q 来保存遍历过程中的各个结点，来保存遍历过程中的各个结点， 队列可以设定为队列可以设定为 bitreebitree类型的指针数组，下标从类型的指针数组，下标从 1 1 开始，同层结点按从左到右的顺序存放。算

108、法如下：开始，同层结点按从左到右的顺序存放。算法如下：define NULL 0define NULL 0define MAXSIZE 100define MAXSIZE 100typedef char elemtype;typedef char elemtype;typedef struct btnodetypedef struct btnode elemtype data;elemtype data;struct btnode *lchild, *rchild;struct btnode *lchild, *rchild;bitnode, *bitree;bitnode, *bitree;

109、void LevelOrderTraverse( bitree t )void LevelOrderTraverse( bitree t ) /*/*使用队列对二叉树进行按层序遍历使用队列对二叉树进行按层序遍历*/*/bitree *QMAXSIZE;bitree *QMAXSIZE;/*/*队列队列 Q Q 是一个指向是一个指向 bitreebitree 类型的指针数组，下标从类型的指针数组，下标从 1 1 开始开始*/*/int rear, front;int rear, front;if (t!=NULL)if (t!=NULL) front=0; /*front=0; /*置空队列置空

110、队列*/*/rear=1;rear=1;Q1=t;Q1=t;dodo front=front%MAXSIZE+1; /*front=front%MAXSIZE+1; /*元素出队列元素出队列*/*/t=Qfront;t=Qfront;printf(%c,t-data);printf(%c,t-data);if ( t-lchild!=NULL ) /*if ( t-lchild!=NULL ) /*左子树根结点入队左子树根结点入队*/*/2828 / 5252 rear=rear%MAXSIZE+1;rear=rear%MAXSIZE+1;Qrear=t-lchild;Qrear=t-lchi

111、ld; if( t-rchild!=NULL ) /*if( t-rchild!=NULL ) /*右子树根结点入队右子树根结点入队*/*/ rear=rear%MAXSIZE+1;rear=rear%MAXSIZE+1;Qrear=t-rchild;Qrear=t-rchild; while(rear=front);while(rear=front); /*LevelOrderTraverse*/*LevelOrderTraverse*/7.7.一棵二叉树的先序遍历序列和中序遍历序列可以惟一确定一棵二叉树。一棵二叉树的先序遍历序列和中序遍历序列可以惟一确定一棵二叉树。现已知一棵二叉树的先序遍

112、历序列和中序遍历序列，可依次从先序遍历序列中现已知一棵二叉树的先序遍历序列和中序遍历序列，可依次从先序遍历序列中取结点，每次取出一个结点就与中序遍历的序列进行比较，当相等的时候，中取结点，每次取出一个结点就与中序遍历的序列进行比较，当相等的时候，中序遍历序列就被分成以该结点为根的二叉树子树，该结点左部分为左子树，右序遍历序列就被分成以该结点为根的二叉树子树，该结点左部分为左子树，右部分为右子树，直到取完先序列里的所有结点，则二叉树构造完毕。可设数组部分为右子树，直到取完先序列里的所有结点，则二叉树构造完毕。可设数组A A存放先序遍历序列，数组存放先序遍历序列，数组 B B 存放中序遍历序列，为

113、处理方便可设存放中序遍历序列，为处理方便可设 B B 为结构体类为结构体类型，包括型，包括 lchildlchild、rchildrchild 和和 chch 三个域。同时可设立一个顺序栈作为工作单元。三个域。同时可设立一个顺序栈作为工作单元。int CreaBitree( char A, char B )int CreaBitree( char A, char B ) /*/*根据二叉树先序遍历序列和中序遍历序列构造一棵二叉树的算法根据二叉树先序遍历序列和中序遍历序列构造一棵二叉树的算法*/*/seqstack *s;seqstack *s;int i, j, k;int i, j, k;s

114、-top=-1;s-top=-1;for( i=1; i=n; i+ )for( i=1; itop=-1)if(s-top=-1) s-top+;s-top+;s-datas-top=j;/*js-datas-top=j;/*j 入栈入栈*/*/ elseelseif (jdatas-top)if (jdatas-top) Bs-data s-top.lchild =j;Bs-data s-top.lchild =j;s-top+;s-top+;s-datas-top=j;s-datas-top=j; elseelse 2929 / 5252while(j datas-top) &(s-to

115、p!=-1)while(j datas-top) &(s-top!=-1) k=s-datas-top; /*k=s-datas-top; /*栈不空时退栈栈不空时退栈*/*/s-top-;s-top-; Bk.rchild=j;Bk.rchild=j;s-top+;s-top+;s-datas-top=j;s-datas-top=j; return(1);return(1);/*CreaBitree*/*CreaBitree*/8.8.设该哈夫曼树中度为设该哈夫曼树中度为 1 1 的结点个数是的结点个数是 n1n1，度为，度为 2 2 的结点个数是的结点个数是 n2n2，总，总的结点数目是的

116、结点数目是 n n，根据二叉树的定义有：，根据二叉树的定义有：n=n0+n1+n2n=n0+n1+n21 1根据二叉树的性质又有：根据二叉树的性质又有：n0=n2+1n0=n2+12 2又由于在哈夫曼树中不存在度为又由于在哈夫曼树中不存在度为 1 1 的结点，因此上面的式子的结点，因此上面的式子1 1中中 n1=0n1=0，即：即：n=n0+n2n=n0+n23 3再由再由2 2式得：式得：n2=n0-1n2=n0-14 4将将4 4代入代入3 3得到结论：得到结论：n=2n0-1n=2n0-1命题证毕。命题证毕。9.9.1 1哈夫曼树如图哈夫曼树如图 B-4B-4 所示。所示。0112010

117、5C02F13G1B0015D08E11130I010A07H图图 B-4B-42 2其带权路径长度其带权路径长度 WPLWPL 值为值为 280280。3 3每个字符的哈夫曼编码为：每个字符的哈夫曼编码为： A:100, B:11, C:1010, D:000, E:0010,A:100, B:11, C:1010, D:000, E:0010,F:10110, G:10111, H:0011, I:01F:10110, G:10111, H:0011, I:01。第七章一、选择题 1 在一个无向图 G 中， 所有顶点的度数之和等于所有边数之和的 倍。 Al/2 B1C2 D43030 /

118、5252 2在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。 Al/2B1 C2 D4 3一个具有 n 个顶点的无向联通图至少包含条边。 An Bn1Cn-1 Dn/2 4一个具有 n 个顶点的无向完全图包含条边。 An(n-l) Bn(n+l)Cn(n-l)/2 Dn(n+l)/2 5 一个具有 n 个顶点的有向完全图包含条边。An(n-1) Bn(n+l) Cn(n-l)/2 Dn(n+l)/2 6对于具有 n 个顶点的图，假设采用邻接矩阵表示，则该矩阵的大小为 。 AnBn2 Cn-1 D(n-l)2 7对于一个具有 n 个顶点和 e 条边的无向图，假设采用邻接表表示，则表

119、头向量的大小为 。An Be C2n D2e 8对于一个具有 n 个顶点和 e 条边的无向图，假设采用邻接表表示，则所有顶点邻接表中的结点总数为 。 An Be C2nD2e 9在有向图的邻接表中，每个顶点邻接链表链接着该顶点所有邻接点。 A入边B出边 C入边和出边 D不是入边也不是出边 10在有向图的逆邻接表中，每个顶点邻接链表链接着该顶点所有邻接点。A入边 B出边 C入边和出边 D不是人边也不是出边 11以下说法中不正确的选项是 。 A无向图中的极大连通子图称为连通分量 B连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D有向图

120、的遍历不可采用广度优先搜索方法 12设无向连通图 G=(V, E) 和 G= (V, E)，如果 G为 G 的生成树，则以下说法中不正确的选项是 。AG为 G 的连通分量 BG为 G 的无环子图 CG为 G 的子图 DG为 G 的极小连通子图且 VV 13 如果无向图 G 必须进行二次广度优先搜索才能访问其所有顶点，则以下说法中不正确的选项是 。 AG 肯定不是完全图 BG 一定不是连通图CG 中一定有回路 DG 有二个连通分量 14邻接表是图的一种 。 A顺序存储结构B 链式存储结构 C索引存储结构 D 散列存储结构 15如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶3131

121、/ 5252点，则该图一定是 。 A完全图B连通图 C有回路 D一棵树 16以下有关图遍历的说法不正确的选项是 。 A连通图的深度优先搜索是一个递归过程 B图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C非连通图不能用深度优先搜索法 D图的遍历要求每一顶点仅被访问一次 17 一个无向连通图的生成树是含有该连通图的全部顶点的 。A极小连通子图 B极小子图 C极大连通子图 D极大子图 18无向图的邻接矩阵是一个 。A对称矩阵 B零矩阵 C上三角矩阵 D对角矩阵19 已知一个图如以下图所示，假设从顶点 a 出发按深度优先搜索法进行遍历，则可能得到的一种顶点序列为 。A、abecdfB、acf

122、ebd C、acebfdD、acfdebabcedf二、填空题 1在图中，任何两个数据元素之间都可能存在关系，因此图的数据元素之间是一种_的关系。 2在图 G 中，如果代表边的顶点偶对是_，则称 G 为无向图。 3在图 G 中，如果代表边的顶点偶对是_，则称 G 为有向图。 4 在图 G 中， vi，vj表示从 vi到 vj的一条边， 在有向图中又称为一条_，且称 vi为_或_，称 vj为_或_。显然在有一向图中vi,vj和代表的是_。 5具有 n (n-1)/2 条边的无向图称为_，简称为_，其中n 表示无向图中顶点的个数， n(n-1)/2 是具有 n 个顶点无向图所拥有边的_。 6具有

123、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在有向图中，假设存在一条弧，则称顶点 v_顶点 w

124、，称弧和顶点 v,w_。3232 / 525212顶点 v 的度定义为_的数目，记为 D(v)。 13 在有向图中， 顶点 v 的度又分为_和_， _是以顶点 v 为头的弧的数目， 或者说是以该顶点为终点的边的数目， 记为 ID(v)；_是以顶点 v 为尾的弧的数目，或者说是以顶点为起点的边的数目，记为 OD(v)；顶点 v 的度是它的_和_之和，即 D(v)=ID(v)OD(v)。 14_是指一条路径上所经过的边或弧的数目。 15假设一条路径上除开始结点和结束结点外(开始结点和结束结点也可以为不同顶点 ，其余顶点均不相同，则称该路径为_。 16 假设一条路径上的开始结点和结束结点为同一个顶点

125、，则称该路径为_或_。同时除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路称_或_。 17在无向图 G 中，如果从顶点 v 到顶点 v有路径，则称 v 和 v是_的。如果对于图中任意两个顶点 v 和 v都是连通的，则称图 G是 _ ， 否 则 称 为 _ 。 无 向 图 中 ， 极 大 的 连 通 子 图 称 为_。 18在有向图中，假设任意两个顶点vi，vjV，vivj，从 vi 到 vj 和从vj 到 vi 都存在路径，则称该图是_。有向图中的极大强连通子图称为有向同的_。 19一个连通图的生成树是一个_，它含有图中全部以点，但只有构成一棵树的_条边。如果在一棵生成树添加一条边，

126、必定构成一个_，因为新添加的这条边使得依附在它两端的两个顶点有了_。 20如果有一个有向图恰有一个顶点的人度_，其余以顶点的人度均_，则该有向图是一棵有向树。一个有向图的_由假设干棵有向树构成，含有图中全部顶点，但只有构成假设干棵不相交的有向树的弧。 21图的邻接矩阵Adjacency Matrix表示法是用一个_来表示图中顶点之间的相邻关系。 22邻接表(Adjacency List)是图的一种_存储结构。在邻接表中，对图中每个顶点建立一个_，第 i 个单链表中的结点表示依附于顶点 vi的边(对无向图)或弧对有向图 。 23 逆邻接表只有_图才具有。 是为了便于确定有向图中顶点的_而建立的。

127、 24一个图的邻接矩阵的表示是_，但是图的邻接表的表示并_。这是因为邻接表中各边结点的连接次序取决于建立邻接表时输入的次序，由于输入的时候是随机的，所以图的邻接表建立的结果也有可能_。 25从邻接表的定义可以看到，假设无向图有 n 个结点和 e 条边，则它的邻接表需要_个头结点和_个表结点。 26图的遍历(Traversing Graph)是从图的某一顶点出发访问图中_，并且使每一个顶点_的过程。 27图的深度优先搜索的基本思想是：从中某个顶点v 出发，首先访问_，然后访问_顶点 w，接着访问一个_的顶点，依此类推， 直到图中所有和 v 有路径相通的顶点都被访问到；假设此时图中仍有3333 /

128、 5252顶点未被访问，则选择图中未被访问的顶点作为_，重复上述过程，直到图中所有顶点_为止。28图的深度优先搜索遍历类似于树的_遍历。 29图的广度优先搜索的基本思想是：从某个顶点 v 出发，首先访问此顶点，然后按广度优先搜索依次访问所有 v 的_，接着从这些_出发仍然进行广度优先搜索依次访问其他结点，直至图中所有已被访问的顶点的_全部被访问到。假设此时图中依然有未被访问的顶点。则另选一个图中_作为起始点，重复上述过程，直到图中所有顶点_为止。 30图的广度优先搜索类似于树的_遍历。 31如果连通图是一个网络，生成树的_称为这棵生成树的代价，则称该网络中所有生成树中权值最小的生成树为 _ ，

129、简称为_。 32构造一棵最小生成树往往都要利用最小生成树的一种简称为 MST 的性质。常见的构造最小生成树的_算法和_算法都利用了MST 性质。 33路径上的第一个顶点称为_，最后一个顶点称为_。 34 迪杰斯特拉算法是求_的最短路径，弗洛伊德Floyd算法是求_的最短路径。 35一个_称为有向无环图，简称为 DAG 图。 36DAG 图比有向树更一般，因为在有向树中不允许出现_的结点，而在 DAG 图中则可以；另外 DAG 图不允许_，因此又是一种特殊的图。 37用顶点表示_，用弧表示活动之间_的有向图，称为顶点表示活动的网Activity On Vertex Network ，简称 AOV

130、 网。 38在 AOV 网中不可以出现有向环或回路，如果出现环或回路，这意味着某项活动是_，这样的工程无法进行，对于电脑中的程序流程图来说就是_，也相当于操作系统中的_。 39检测 AOV 网是否有回路的方法是构造_。从构造拓扑序列过程中可以发现是否有_。 40拓扑排序是对 AOV 网构造一个_，使得所有结点的_在序列中得以表达，即在序列中某个结点的前驱必须在后继之前。拓扑排序的序列_。 41如果用数学上的术语进行描述，拓扑排序是由某个集合上的一个_关系得到该集合上的一个_的操作。 42 构造拓扑有序序列的过程可以发现有向图中_， 同时构造拓扑有序序列的过程就是利用拓扑排序算法进行_的过程。

131、43拓扑排序的结果使得当前图中_全部被输出，但仍然有结点未被输出，这说明有向图中存在_。 44如果含 n 个顶点的图形成一个环，则它有_棵生成树。 45有 n 个结点的无向图的边数最多为_。 46有 n 个顶点的强连通有向图 G 至少有_条边。 47用邻接矩阵存储有向图 G，其第 i 行的所有元素之和等于顶点 i 的3434 / 5252_。 48设有向图 G 的邻接矩阵为 A，图中 i 和 j 之间不存在弧，则 Ai,j的值为_。49有 n 个顶点的连通图的边数至少为_。50在有 n 个顶点的有向图中，每个顶点的度最大可达_。 51在无向图 G 的邻接矩阵 A 中，假设(vi,vj)属于图

132、G 的边集，则对应元素 Ai,j为_，否则等于_用逗号分开 。 52已知一个有向图用邻接矩阵表示，计算第 i 个结点的人入度的方法是_。53对于一个具有n 个顶点和 e 条边的无向图，假设采用邻接表表示，则表头 向 量 的 大 小 为 _ ， 所 有 邻 接 表 中 的 结 点 总 数 是_。1.多对多2.无序的3.有序的4.弧、弧尾、初始点、弧头、终端点、不同的边5.无向完全图、完全图、最大数目6.有向完全图、最大数目7.稀疏图8.网9.子图10.邻接点、依附于、相关联11.邻接到、相关联12.以该顶点为一个端点的边13.入度、出度、入度、出度、入度、出度14.路径长度 15.简单路径16.

133、回路、环、简单回路、简单环17.连通、连通图、非连通图、连通分量18.强连通图、强连通分量19.极小连通子图、n-1、环、第二条路径20.为 0、为 1、生成森林21.二维数组 22.链式、单链表23.有向、入度24.惟一的、不惟一、不一样25. n、2e26.所有顶点、仅被访问一次27.顶点 v、与 v 相邻的、与 w 相邻且未被访问、起始点、全部被访问完28.先序29.未被访问过的邻接点、邻接点、邻接点、未被访问的顶点、均被访问完30.按层次31.各边权值之和、最小代价生成树、最小生成树32.普里姆Prim 、克鲁斯卡尔Kruskal33.源点Source 、终点(Destination)

134、34.某个源点到其余各顶点、每一对顶点之间35.无环的有向图3535 / 525236.入度大于 1、出现环或回路37.活动、优先关系38.自己的先决条件、死循环、死锁39.拓扑有序序列、有向环或回路40.线性序列、优先关系、并不一定惟一41.偏序、全序42.是否有环、拓扑排序43.无前驱的顶点、环44. n45. n(n-1)/246. n47.出度48. 049. n-150. 2(n-1)51. 1,052.求矩阵第 i 列非 0元素之和53. n,2e三、判断题 1有 n 个结点的无向图中，假设边数大于 n-1，则该图是连通的。 2假设一个有向图的邻接矩阵中对角线以下元素均为零，则该图

135、的拓扑有序序列必定存。 3AOV 网拓扑排序的结果是惟一的。 4图的广度优先搜索序列是惟一的。 5具有 n 个顶点的无向图采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素之和的一半。 6假设连通图上各边权值均不相同，则该图的最小生成树是惟一的。 7无向图的邻接矩阵一定是对称的。 8有向图的邻接矩阵一定是非对称的。 9用邻接矩阵存储图的时候，占用空间大小不但与图的结点个数有关还与图的边数有关。 10图的连通分量是无向图的极小连通子图。 11图的强连通分量是无向图的极大连通子图。 12 对任意一个图从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。 13一个有向图的邻接

136、表和逆邻接表中的节点个数一定相等。 14 有向图用邻接矩阵表示后， 顶点 i 的出度等于第 i 行中非 0 且非无穷的元素个数。 15图 G 的某一最小生成树的代价一定小于其他生成树的代价。 1.错误：有 n 各结点的无向图中，图是连通的则边数大于 n-1，但反过来不正确。2.正确： 有向图的邻接矩阵中对角线以下元素均为零，说明一定不存在回路并满足偏序关系，故拓扑有序序列必定存在。3.错误：AOV 网拓扑排序的结果是不惟一的。4.错误： 图的广度优先搜索序列不是惟一的， 一个图中可能存在多个子图，即使在一个图中从不同的结点出发其遍历结果也可能不同。5.正确。3636 / 52526.正确：由图

137、的最小生成树定义可以得到。7.正确。8.错误：有向图的邻接矩阵也可能是对称的。9.错误：用邻接矩阵存储图的时候，占用空间大小与图的结点个数有关，而与图的边数无关。10.错误：图的连通分量是无向图的极大连通子图。11.错误：强连通分量是有向图的极大连通子图。12.错误：该图不一定是连通的。13.正确。14.正确。15.错误：图中可能存在多个相同权值的边，图的最小生成树可能不只一棵。四、综合题l请写出如图 7-1 所示无向图的邻接矩阵和邻接表两种存储结构。邻接矩阵如图 B-5 所示。00000A 001001000001000100000010010000010101000000010100000

138、00001010000010100000001010000010100110000000图 B-5邻接表如图 B-6 所示。3737 / 5252datafirstarcadjvexdatanext123456789102343476162234347616281010569878381010569878399551212图 B-62依据无向图 7-1，请写出：1从顶点 1 出发图的深度优先搜索序列。2从顶点回出发图广度优先搜索的序列。3写出图的深度优先搜索算法。4写出图的广度优先搜索算法。1从顶点 1 出发图的深度优先搜索序列为：187695432102从顶点 1 出发图广度优先搜索的序列为

139、：182791036453图的深度优先搜索算法参考例题 7-1 的内容。4图的广度优先搜索算法参考例题 7.2 节内容。3使用 Prim 算法，依据无向图 7-2 做以下问题；图 7-2l写出构造该图的最小生成树的过程。 (2) 写出相应的构造最小生成树算法。1使用 Prim 算法，构造该图的最小生成树的过程如图 B-7 所示。3838 / 5252100190206507570526010301212082536755838011044（a）12067554583650752120（b）2834（c）1206507554583650751002120（d）100210834（e）120650

140、75548255100210365075120（f）1002103082543（g）（h）图 B-74使用 Kruskal 算法，依据无向图 7-2 做以下问题：l写出构造该图的最小生成树的过程。 (2) 写出相应的构造最小生成树算法的形式描述。1使用 Kruskal 算法，构造该图的最小生成树的过程如图 B-8 所示。3939 / 5252100190206507570526010301212082536755838011044（a）121067554583675120（b）210834（c）1206755482552103675120（d）2108254303（e）120506755482

141、5521030365075120（f）1002103082543（g）（h）图 B-85 假设图采用邻接表表示，写出一个从顶点 v0 对图按深度优先搜索遍历的非递归算法。6有一个无向图采用邻接表的存储结构，请编写算法，以遍历的形式输出从顶点 v 到顶点 w 的路径中长度为 len 的简单路径。7以邻接表作为存储结构，编写一个算法，利用深度优先搜索法，求出在无向图中通过给定点 w 的简单回路的算法。4040 / 5252第九章一、选择题1.顺序查找方法适合于存储结构为的线性表A.散列存储 B.索引存储C.散列存储或索引存储D.顺序存储或链接存储2.对线性表进行二分查找的时候，要求线性表必须 。A

142、.以顺序存储方式 B.以链接存储方式C.以顺序存储方式，且数据元素有序 D.以链接存储方式，且数据元素有序3. 如果要求一个线性表既能较快地查找，又能动态适应变化要求，可以采用查找方法。A.顺序B.分块 C.折半D.散列4. 对于一个线性表，假设要求既能进行较快地插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该( ) 。A.以顺序存储方式B.以链接存储方式C.以索引存储方式 D.以散列存储方式5. 在线性表的存储结构中,查找、插入和删除速度慢，但顺序存储和随机存取第 i 个元素速度快。A.顺序表B.链接表 C.散列表D.索引表6. 在( )上查找和存取速度快,但插入和删除速度慢

143、。A.顺序表B.链接表C.顺序有序表 D.散列表7. 在( )上查找、插入和删除速度快,但不能进行顺序存取。A.顺序表 B.链接表 C.顺序有序表D.散列表8. 在( )上插入、删除和顺序存取速度快,但查找速度慢。A.顺序表B.链接表 C.顺序有序表 D.散列表9. 采用顺序查找方法查找长度为 n 的线性表,查找每个元素的平均比较次数为( )A. nB. n/2C. (n+1)/2D.(n-1)/210.顺序查找具有 n 个元素的线性表,其时间复杂度为( ) 。A.O(n)B.O(log2n) C.O(n2)D.O(nlog2n)11.折半查找具有 n 个元素的线性表,其时间复杂度为( ) 。

144、A.O(n)B.O(log2n) C.O(n2)D.O(nlog2n)12.己知一个有序表为(11,22,33,44,55,66,77, 88,99), 则折半查找元素 55 需要比较( )次。A.1B.2 C.3 D.413.已知一个有序表为(11,22,33,44,55,66,77,88,99), 则顺序查找元素 55 需要比较( )次。A.3B.4C.5D.614.顺序查找法与二分查找法对存储结构的要求是( ) 。A. 顺序查找与二分查找均只是适用于顺序表B. 顺序查找与二分查找均既适用于顺序表 , 也适用于链表C. 顺序查找只是适用于顺序表D. 二分查找适用于顺序表15.在对查找表的查

145、找过程中,假设被查找的数据元素不存在,则把该数据元素插4141 / 5252到集合中。这种方式主要适合于( ) 。A.静态查找表B.动态查找表C.静态查找表与动态查找表 D.两种表都不适合16.假设用二分查找取得的中间位置元素关键字值大于被查找值，则说明被查找值位于中间值的前面,下次的查找区间为从原开始位置至( ) 。A.该中间位置B.该中间位置-1C.该中间位置+1 D.该中间位置 1/217.二叉排序树遍历序列是从小到大有序的。A. 先序B.中序C. 后序 D.层序二、填空题1.查找表是由同一类型的数据元素 ( 或记录 ) 组成的,是查找所依赖。2. 如果对查找表只进行查询某个特定的数据元

146、素是否在查找表中, 以及查找某特定的数据元素的各种属性两种类型的基本操作,而不进行插入和删除数据元素的查找表称为。3. 如果在查找表中进行查找的过程中，同时插入查找表中不存在的数据元素，或者查 找 表 中 删 除 已 存 在 的 某 个 数 据 元 素 ， 则 称 此 类 查 找 表为。4.关键字是数据元素(或记录)中某个，用它可以标识(识别)一个查表中5. 在一个查找表中，能够惟一的标识一个数据元素 (或记录)的关键字称为。6. 次关键字也称为或，是在查找表中可以标识的关键字。7.查找又称，它是根据给定的某个值，在查找表中确定是否有元素(或记 录)的关键字的操作。假设操作之后确定表中存在这样

147、的记录，则称为查找的，否则称为。 8. 平均查找长度是指为确定所查找的记录在查找表中的位置，需要与给定值进行比较关键字个数的。 9. 最大查找长度是指为确定所查找的记录在查找表中的位置，需要与给定值进行比较关键字个数的。最大查找长度随所查找的、和都有关系。最大查找长度通常是在考虑查找给定值在查找表中的情况。10.是一种最简单、最基本的查找方法，它的基本思想是：从表的一端开始， 依次顺序扫描线性表，将扫描到记录的关键字逐个与给定值进行比较，假设某个记录的关键字和给定的值相等，则说明找到所要的记录，查找成功；假设扫描结束后，仍未找到关键字等于给定值的记录，则说明表中没有所查找的记录，查找不成功。1

148、1. 折半查找( Binary Search)又称为， 是一种效率较高的一种查找算法。12. 折半查找的思路是：每次将给定值与查找表中所要查找区域的关键字进行比较，而不是查找表中的第一条或最后一条。13. 分析折半查找的性能可以用二叉树来进行描述 。把当前查找区间的中间位置上的结点作为根结点，左半区间和右半区间中结点分别作为左子树和右子4242 / 5252树，由此得到的二叉可称为。14.分块查找 (Blocking Search)又称为，是一种以的形式来来进行的查找方法。分块查找是的一种改良， 它是一种介于和折半查找之间的查找方法。15. 二叉排序树(Binary Sort Tree)，又称

149、为，它或者是一棵空树，或者是具有以下性质的一棵二叉树：(1) 假设左子树不空，则左子树上所有结点的值。(2) 假设右子树不空，则右子树上所有结点的值。(3) 左右子树又分别是。16.平衡二叉树定义为：它或者是一棵空树；或者是具有这样性质的二叉树:它的左子树和右子树都是且左子树和右子树的深度之差的绝对值。 17. 我们称在构造平衡二叉排序树的过程中，离插入结点最近，且以平衡因子绝对值大 于 1 的结点作为根结点的子树为。18. 哈希表查找就是一种通过某种映射建立起之间的对应关系，希望或经过很少次比较即可获得所要查找的记录。19. 哈希(Hash)表查找又称为查找，它是一种重要的查找技术。哈希表查

150、找因使用哈希函数(又称为 ) 而得名。哈希函数是一种的函数。20. 利用哈希函数可以实现记录关键字和关键字所对应记录存储地址的转换或映像， 这种映像过程称为或， 映像结果产生的哈希函数值 h (key)作为存储位置称为或，利用哈希函数映像哈希地址，所得到的存储表称为21. 有时候在向哈希表中存储关键字的时候， 会出现一个待插入关键字的记录已经被占用的情况， 这种的现象称为冲突 ( Collision) 。22.具有相同哈希函数值的关键字对相应的哈希函数来说称为，由同义词产生的冲突称为。23. 构造哈希函数的是取关键字或关键字的某个线性函数作为哈希地址。24. 构造哈希函数的是对关键字中数字进行

151、分析， 然后用提取其中一部分分布较为均匀的数字位作为哈希地址的方法。25. 构造哈希函数的是用关键字 key 除以某个正整数 p，所得余数作为哈希地址的方法。26. 构造哈希函数的是取关键字平方的中间几位作为哈希地址的方法。27. 构造哈希函数的是先将关键字分割成位数相等的几段(其中最后一段的位数可以不相等 )，然后取这几位的叠加和作为哈希地址。中 数 位 的 叠 加 可 以 分 为 移 位 叠 加 和 间 界 叠 加 两 种 。 所 谓 移 位 叠 加是， 然后相加； 间界叠加是然后对齐相加。28. 构造哈希函数应当尽量减少冲突，但是还是无法防止冲突的发生。一旦冲突发生了， 就必须寻求合适的

152、方法来解决冲突。通常解决冲突可以采用和。29. 开放定址法(Open Addressing)是指将哈希表中的空单元向处理冲突开4343 / 5252放。开放定址法解决冲突，形成下一个地址的形式是：Hi=(h(key)+di)%m,i=1,2, ,k(km-l)其中，h (key) 为哈希函数，m 为哈希表长，di为增量序列。根据上式形成增量序列di的不同，开放定址法又可以分成如下三种形式：、。30. 分析哈希表的查找过程可以知道，造成哈希表冲突的首要因素是，第二个因素是，第三个因素是。31. 在有序表 A1.18中， 采用二分查找算法查找元素值等于 A7的元素，所比较过的元素的下标依次为。 3

153、2. 有 17 个元素的有序表 A1.17作二分查找， 在查找其等于 A8的元素时，被比较的元素的下标依次是。 33. 假定有 K 个关键字互为同义词， 假设用线性探测再散列法把这 K 个关键字存入散列表中，至少要进行次探测。34. 一个无序序列可以通过构造一个树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。 35. 在有序表 a 1.20中，采用二分查找算法查找元素值等于 a12的元素，所比较过的元素的下标依次为。36. 对于长度为 n 的线形 表 , 假设进行顺序查找 , 则时间复杂性为； 假设用二分法查找， 则复杂性为； 假设用分块法查找(假定总块数和每块长度均接近 )，

154、则时间复杂性为。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 Search11.二分查找、有序表12.中间那条记录13.折半查找判定树14.索引顺序查找、索引顺序表、顺

155、序查找、顺序查找15.二叉查找树、均小于根结点的值、均大于根结点的值、二叉排序树16. AVL 树、平衡二叉树、不超过 117.最小不平衡树18.关键字和关键字所在记录的存储地址、不经过比较19.散列表、散列函数、把关键字映射成记录存储地址20.哈希造表、散列、哈希地址、散列地址、哈希表、散列表4444 / 525221.不同的关键字具有相同地址22.同义词、同义词冲突23.直接定地址法或 Immediately allocate24.数字分析法或 Digital Analysis method25.除留余数法或 Division Method26.平方取中法或 Mid-square meth

156、od27.折叠法或 Folding Method 、折叠法或 Folding Method 、将分割后的每一部分的最低位对齐、从每段的一端向另一端沿分割界来回折叠28.开放定址法、链地址法等方法29.线性探测再散列、二次探测再散列、随机探测再散列30.哈希函数、处理冲突的方法、装填因子31. 9 4 6 732. 9，4，6，7，833. 1+2+k=k(k+1)/234.二叉排序35. 10,15,1236. O(n);O(log2n);O(n)37. L+138. 339.左子树三、判断题1. 用向量表示的有序表可以使用折半查找。 ( )2. 用单链表表示的有序表可以使用折半查找。 3.

157、顺序查找的平均查找长度 ASL 与数据的排列有关。 4.在任意非空的二叉排序树中，删除某个结点之后，再将该结点插入在二叉排序树中，则所得到的二叉排序树与原二叉排序树相同。 5. 哈希表的装载因子越小则发生冲突的可能性越大。 6. 二叉排序树中，关键字最小的结点必然无右孩子，关键字最大的结点必然无左孩子。 7. 在分块查找、折半查找和顺序查找中，分块查找平均查找长度最大、折半查找平均查找长度最小。 8. 顺序查找的方法适合于顺序存储结构而不适合于链接存储结构。 9. 前序遍历一棵二叉排序树的结点 , 就可以得到排好序的结点序列。 10. AVL 树是一棵二叉树，该树上的任意一个结点的平衡因子的绝

158、对值均不大于 1。 11. 在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表的个数有关，而且与每一块中的元素的个数有关。 ( )12. 对一个堆按层次遍历，不一定能得到一个有序序列。4545 / 52521.正确。2.错误：用单链表表示的有序表不可以使用折半查找。3.错误：顺序查找的平均查找长度 ASL 与数据的排列无关。4.错误：由于二叉排序树插入结点均在二叉排序树的叶子结点上，因此假设删除的结点不是叶子结点则删除再重新插入后是不同于原来二叉树的。5.错误： 哈希表的负载因子越小则发生冲突的可能性越小。6.错误： 二叉排序树中， 关键字最小的结点必然无左孩子，关键字最大

159、的结点必然无右孩子。7.错误：在分块查找、折半查找和顺序查找中，顺序查找平均查找长度最大、折半查找平均查找长度最小。8.错误：顺序查找的方法适合于顺序存储结构和链接存储结构。9.错误：中序遍历一棵二叉排序树的结点，就可以得到排好序的结点序列。10.正确。11.正确。12.正确。四、综合题l. 用 C 语言写出顺序查找算法。2. 用 C 语言写出折半查找算法。3. 用 C 语言写出分块查找算法。4. 写出二叉排序树的插入结点的递归算法，并利用插入算法写出建立一个有 n 个结点的二叉排序树算法。5. 简述平衡二叉树调整平衡的具体方法。6. 关键字序列 A=(36,27,68,33,97,40,81

160、,24,23,90,32,14)共 12 个数据，哈希表长为13，采用的哈希函数为： h (key) = key% 13。如果采用开放定址的线性探测再散列方法解决冲突，请构造哈希表并求其平均查找长度。7. 写出折半查找的递归算法。8. 编写算法，用折半查找算法在一个有序的顺序表中插入x 结点，并保持结点的有序性。9. 编写判定给定的二叉树是否是二叉排序树的算法。10. 设哈希函数为 h (key)=key % 19，编写一个用链接表解决冲突的哈希表插入函数。11. 设哈希函数为 h (key)=key %19，解决冲突的方法是链地址方法，编写一个从哈希表中删除关键字为 key 的一个记录的算法

161、。4646 / 5252习题十一、选择题 1在所有的排序方法中，关键字比较的次数与记录初始排列秩序无关的是 。 A冒泡排序 B希尔排序C直接选择排序 D直接插人排序 2从未排序序列中依次取出元素与已经排好序的序列中的元素作比较，将其放入已排序序列的正确位置上，此方法称为 。 A插人排序 B选择排序C交换排序 D归并排序 3从未排序序列中挑选元素，并将其放人已排序序列的一端，此方法称为 。 A插入排序 B交换排序C选择排序 D归并排序 4依次将每两个相邻的有序表合并成一个有序表的排序方法称为 。 A插人排序 B交换排序C选择排序D归并排序 5当两个元素出现逆序的时候就交换位置，这种排序方法称为

162、。 A插人排序B交换排序C选择排序 D归并排序 6每次把待排序的区间划分为左、右两个子区间，其中左区间中的记录的关键字均小于等于基准记录的关键字， 右区间中记录的关键字均大于等于基准记录的关键字，这种排序称为 。 A 插人排序B快速排序C堆排序 D归并排序 7在正常情况下，直接插人排序的时间复杂度为 。AO(log2n) BO(n)CO(n log2n) DO(n2) 8在正常情况下，冒泡排序的时间复杂度为 。 AO(log2n) BO(n)CO(nlog2n)DO(n2) 9在归并排序中，归并趟数的数量级为 。AO(log2n BO(n)CO(nlog2n) DO(n2) 10在归并排序中，

163、每趟需要进行的记录比较和移动次数的数量级为 。 AO(log2nBO(n)CO(nlog2n) DO(n2) 11归并排序算法时间复杂度为 。 AO(log2n BO(n)CO(nlog2n) DO(n2) 12平均情况下，快速排序的时间复杂度为 。 AO(log2n BO(n)4747 / 5252CO(nlog2n) DO(n2) 13最坏情况下，快速排序的时间复杂度为 。 AOlog2n BO(n)CO(nlog2n)DO(n2) 14堆排序中，在每次筛运算中，记录比较和移动次数的数量级为 。AOlog2n BO(n)CO(nlog2n) DO(n2) 15堆排序算法时间复杂度为 。 A

164、Olog2n BO(n)CO(nlog2n) DO(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要排序

165、的数据中含有多个相同值C要排序的数据已基本有序 D要排序的数据个数为奇数 21假设构造一棵具有 n 个结点的二又树排序，在最坏的情况下，其深度不会超过 。 An/2BnC nl/2 Dnl23.考察以下排序算法的稳定性， 是稳定的排序算法。 A 直接插人排序归并排序冒泡排序B 简单项选择择排序 C快速排序 D堆排序、希尔排序二、填空题 1假设对记录的次关键字进行排序，记录之中有两条记录 Ri 和 Rj，它们的关键字 Ki 和 Kj 相等， 在排序之前记录 Ri 在 Rj 之前， 假设排序之后记录 Ri仍在 Rj 之前，则称排序方法是_; 相反，假设经过某种排序之后 Ri在 Rj 之后，则称所用

166、的排序方法是_。 2根据所排序过程中所用存储器的不同，可以将排序方法分为_和_。 3如果按排序过程中所需要的工作量来分，又可以分为_、_4848 / 5252和_，其中_的时间复杂度为 O(n2),_的时间复杂度为 O(nlogn)，_时间复杂度为 Odn 。 4_的基本思想是：每一趟将一个待排序的记录按其关键字的大小，插入到已经排好序的部分记录之中，使之构成一个新的有序序列，直到所有记录全部插入完成，所有待排记录的关键字都成为一个有序序列。 5直接插人排序是一种_ 填是否稳定的排序算法。 6 希尔排序 Shell s Sort 又称_， 它是由 D L Shell 于 1959年提出来的一种

167、改良的插入排序方法。希尔排序属于_的一种， 但比普通的插人排序效率要高。 7希尔排序是一种_填是否稳定的排序算法. 8_是通过两两比较待排序记录的关键字，假设发现两个记录关键字的大小次序相反， 即进行交换， 直到所有记录关键字全部满足排序要求为止。这种排序方法可以包括有_和_两种交换排序方法。 9_是通过无序区中相邻记录关键字之间相互比较和交换位置，使之关键字较小的记录在关键字较大的记录之上， 从下标较大的单元逐步向下标较小的位置移动。 10冒泡排序是一种_填是否稳定的排序算法。 11快速排序Quick Soft又称_是由霍尔 (Hoare) 提出的的一种对冒泡排序改良的交换排序。 因其排序速

168、度快，故而称为快速排序。 12快速排序是一种_填是否稳定的排序算法。 13 _的基本思想是： 每一趟排序在待排序的记录中选关键字最小的记录， 依次放在已经排序记录序列的最后，直至全部记录的关键字成为一个有序序列为止。这种排序方法又可以分为：_和_。 14堆排序的关键是构造堆。RWFIOyd 提出了一个_算法来建堆。 15 归并就是将两或两个或两个以上的有序数据序列合并成一个有序数据序列的过程。归并排序有_和_，可以用于_，也可以用于_， 但一般情况下说归并排序都是指_ 它是最简单也是最基础的一种归并排序方法。 16归并排序是一种_填是否稳定的排序算法。 17.是利用关键字本身的结构，借助于多关

169、键字排序的思想，通过“分配”和“收集”的方法实现排序。 18基数排序是一种_填是否稳定的排序方法。 19对于多关键字排序，可以有两种方法。一种称为 _法，简称-_法，另一种方法称为_法。 20当排序的记录数量很多，可能出现正序或逆序情况的时候，并且要求排序方法稳定的时候，则要选择_。 21直接选择排序算法在最好情况下所作的交换元素的次数为_。 22简单项选择择排序方法所执行的元素交换次数最多为_。 23简单项选择择排序方法在最好的情况下所做的交换元素的次数为4949 / 5252_。 24冒泡排序方法在最好情况下的元素交换次数为_。 25有 n 个求队参加的足球联赛按主、客场进行比赛，共需进行

170、_场比赛。 26在对一组记录54，38，96，23，15，72，60，45，83进行直接插入排序假设干趟后，当需要把第 7 个记录 60 插入到有序表时，为寻找 60 的插入位置需比较_次。 27分别采用选择排序、堆排序、快速排序和归并排序方法对初始状态为递增序列按递增顺序排序，最省时间的是_排序，最浪费时间的是_排序。三、判断题1快速排序在所有排序方法中最快，而且所需要的附加空间也最少。2外部排序是把外存文件调入内存，可利用内部排序方法进行排序，因此排序所花费的时间取决于内部排序的时间。3一般来说，外排序所需要的时问取决于内部排序时间、外存信息读写时间和内部归井所需要的时间。4外排序过程主要

171、分为两个阶段：生成初始归并段和对归并段进行逐趟归5 快 速 排 序 方 法 在 任 何 情 况 下 均 可 以 得 到 最 快 的 排 序 效 果 。6基数排序的设计思想是依照对单个关键字值的比较来实施的。7用希尔Shell排序方法进行排序的时候，关键字越是有序效率越高，关键字越是杂乱则排序效率越低。8 减 少 初 始 归 并 数 量 ， 可 以 使 外 部 排 序 的 时 间 缩 短 。9 直 接 插 入 排 序 是 一 种 稳 定 的 排 序 算 法 。10希尔排序是一种稳定的排序算法。5050 / 5252并的时间11冒泡排序是一种稳定的排序算法。12 冒 泡 排 序 算 法 的 时 间

172、 复 杂 度 最 正 确 情 况 下 为O(n2) 。13快速排序是一种稳定的排序算法。14 直 接 选 择 排 序 是 一 种 稳 定 的 排 序 算 法 。15堆排序是一种稳定的排序算法。16快速排序、堆排序和归并排序平均时间复杂度为 O(nlog2n)。17归并排序是一种稳定的排序算法。18基数排序是一种稳定的排序算法。19 目 前 归 并 排 序 在 内 部 排 序 和 外 部 排 序 中 都 广 为 使 用 。20当排序的记录数量很多，可能出现正序或逆序情况的时候，可以选择堆排 序 ，如 果进 一步 要 求 排 序方 法 稳 定 的时 候， 则 要选 择归 并 排序 。21 在执行某

173、个排序算法过程中， 出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。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，5

174、2，65，87，11，请写出直接选择排序的每一趟过程。5已知一组记录的关键字序列为22，96，15，37，10，68，44，85，70，20，11，请写出用归并排序进行排序的每一趟过程。6设计一个函数，实现冒泡排序的双向排序，即每一趟通过每两个相邻的关键字进行比较，产生最小和最大的关键字值的元素。7用递归的方法实现一趟归并排序，并写出完整的归并算法。8有一种算法称为奇偶转换排序，它的思路是：第一趟对所有的奇数 i 将ai和 ai+l进行比较，第二趟对所有的偶数的 i 将 ai和 ai+l进行比较，每次比较时，假设 aiail ，则将二者进行交换，直至所有记录关键字5151 / 5252有序。试写出此算法。5252 / 5252