数据结构第六章

一、单项选择题

1.已知一个长度为16的顺序L，气元素按关键字有序排列，或采用折半查找法查找一个不在L中存在的元素，则关键字的比较次数最多的是（）。

A．4 B. 5

C. 6

D. 7

2.顺序查找适合于存储结构为（）的线性表。

A.顺序存储结构或链式存储结构

B.散列存储结构

C.索引存储结构

D.压缩存储结构

3.对长度为n的有序单链表，若查找每个元素的概率相等，则顺序查找表中任意一个元素的查找成功的平均查找长度为（）。

2 B.(n+1)/2

C.(n-1)/2 4

4.对长度为3的顺序表进行查找，若查找的第一个元素概率为1/2，查找第二个元素的概率为1/3，查找第三个元素的概率为1/6，则查找表中任意一个元素的平均查找长度为( )。

3

3 3

5.当采用分块查找时，数据的组织方式为（）。

A.数据分成若干块，每块内数据有序

B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块

C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块

D. 数据分成若干块，每块（除最后一块外）中数据个数需相同

6.下列关于二分查找的叙述中，正确的是（）。

A．表必须有序，表可以顺序方式存储，也可以链表方式存储

B. 表必须有序且表中数据必须是整型，实型或字符型

C. 表必须有序，而且只能从小到大排列

D．表必须有序，且表只能以顺序方式存储

7.使用二分（折半）查找元素的速度比用顺序法（）。

A.必然快

B.必然慢

C.相等

D.不能确定

8.已知一个长度为16的顺序表，其元素按关键字有序排列，若采用折半查找查找一个不存在的元素，则比较的次数至少是（），至多是（）。

9.已知一个有序表（13,18,24,35,47,50,62,83,90,115,134），当二分查找值为90的元素师，查找成功的比较次数为（ ）。

10.折半查找过程所对应的判定树是一颗（ ）。

A.最小二叉树

B.平衡二叉树

C.完全二叉树

D.满二叉树

11.在有11个元素的 有序表A[1,2,3，…，11]中折半查找(()/2low high +????),查找元素为A[11]时，被比较元素的下标依次是（ ）。

，8，10，11 ，9，10，11

，7，9，11 ，8，9，11

12.具有12个关键字的有序表中，对每个关键字的查找概率相同，遮半查找查找成功的平均查找长度为（ ），折半查找查找失败的平均查找长度为（ ）。

12 12

13 13

13.对有2500个记录的索引顺序表（分块表）进行查找，最理想的块长为（ ）。

D. 2log 2500????

14.为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素最多需要执行（ ）次关键字比较。

15.设顺序存储的某线性表共有123个元素，按分块查找的要求等分为3块。若对索引表采用顺序查找法来确定子块，且确定的字块中也采用顺序查找法，则在等概率情况下，分块查找成功的平均查找长度为（ ）。

16.对长为n 的有序表进行折半查找，其判定树的高度为（ ）。

A. 2log (1)n +????

B. 2log (1)1n +-????

C. 2log n ????

D. 2log 1n -?

??? 17.下列叙述中，不符合m 介B 树定义要求的是（ ）。

A.根节点最多的有m 课子树

B.所有叶节点都在同一层上

C.各节点内关键字均升序或者降序排列

D.叶节点之间通过指针连接

18.下列关于m 介B-树的说法错误的是（ ）。

A.根节点至多有m 棵子树

B.所有节点都在用一层次上

C.非叶节点至少有m/2(m 为偶数)或m/2+1(m 为奇数)棵子树

D.根节点中的数据是有序的

19.当在一颗m 阶B 树中做插入操作时，若一个结点中的关键字等于（ ），则必须分裂成两个结点，当向一颗树m 阶的B 树做删除操作时，若一个结点中的关键字个数等于（ ），则可能需要同它的做兄弟或有兄弟结点合并成一个结点。

A. ,/22m m -????

B. 1,/22m m --????

C. 1,/2m m +????

D. /2,/21m m +????

20.下列关于m 阶B 树的说法正确的是（ ）。

I.

每个结点至少有两颗非空子树 II.

树中每个结点至多有m-1个关键字 III.

所有叶结点都在同一层 IV.

当插入一个元素引起B 树结点分裂后，树长高一层 、II 、III

、IV 、II 、IV 21.下列关于B 树和B+树叙述中，不正确的是（ ）。

A. B 树和B+树都能有效支持顺序查找

B. B 树和B+树都能有效支持随机查找

C. B 树和B+树都是平衡的多叉树

D. B 树和B+树都可以用于文件索引结构

22.含有n 个非叶结点的m 阶B-树中至少包含（ ）个关键字。

A. (1)n m +

B. n

C. ()/21n m -????

D. ()(1)/211n m --+?

??? 23.已知一课3阶B 树中有2047个关键字，则此B 树的最大高度为（ ），最小高度为（ ）。

24.高度为5的3阶B 树至少有（ ）个结点，至少有（ ）个结点。

25.已知一棵5阶B 树中共有53个关键字，则树的最大高度为（ ），最小高度为（ ）。

.

26.具有n 个关键字的m 阶B-树，应有（ ）个叶结点。

+1

2

27.设有一个含有200个表项的散列表，用线性探测法解决冲突，按关键字查询时找到一个表项的平均探测次数不超过，则散列表项应能够容纳（ ）个表项。（设查找成功的平均查找长度为[]11/(1)/2ASL α=+-，其中α填装因子）

A ．400 B. 526

C ．624 D. 676

28.在开址法中散列到同一个地址而引起的“堆积”问题是由于（ ）引起的。

A.同义词之间发生冲突

B. 同义词之间发生冲突之间发生冲突

C.同义词或同义词之间发生冲突之间发生冲突

D.散列表“溢出”

查找一般适用于（ ）情况下的查找。

A.查找表为链表

B. 查找表为有序表

C.关键字集合比地址集合大得多

D. 关键字集合比地址集合存在对应关系

30.假定有K 个关键字互为同义词，若用线性探测法把这K 个关键字填入Hash 表中，至少要进行（ ）次探测。

B. K

+1 D. K(K+1)/2

B A B A

二 综合应用题

1.若对有N 个元素的有序顺序表和无序顺序表进行顺序查找，试就下列三种情况讨论两者在相等查找概率时的平均查找长度是否相同

1).查找失败。

2).查找成功，且表中只有一个关键字等于给定值k 的元素。

3).查找成功，且表中只有若干个关键字等于给定值k 的元素，要求一次能查找所有的元素。

2.设有序顺序表中的元素依次为017、094、154、170、275、503、509、

512、553、612、677、765、897、908。

1)

试画出对其进行折半查找的判定树。 2)

若查找275或684的元素，将依次与表中那些元素比较 3) 计算查找成功的平均查找长度和查找不成功的平均查找长度。

3．已知一个有序顺序表[0...81]A N - 的表厂为8N ，并且表中没有关键字相同的数据元素。假设按如下所述的方法查找一个关键字值等于给定值X 的数据元素：先在A[7],A[15],A[23],…,A[8K-1],…,A[8N-1]中进行顺序查找，若查找成功，则算法报告成功位置并返回；若不成功，[]81[8(1)1]A K X A K -<-的关键字，则查找失败。

1)画出上述查找过程的判定树。

2)计算相等查找概率下查找成功的平均查找长度。

4.类比二分查找法，设计K 分查找法（k 为大于2的整数）如下：首先检查n/k 处（n 为查找表的长度）的元素是否等于要搜索的值，然后检查2n/k 处的元素…这样，或者找到要查找的元素，或者把集合缩小到原来的1/k,如果未找到要查找的元素，则继续在得到的集合上进行K 分查找；如此进行，直到找到要查找的元素或者查找失败。试求，查找成功和查找失败的时间复杂度。

5.线性表中各结点的检索概率不等，则可用如下策略提高顺序检索的效率：若找到指定的结点，将该结点和其前驱结点交换，使经常被检索的结点尽量位于表的前端。是设计在顺序结构和链式结构的线性表实现上述策略的顺序检索算法。

6.一个长度为(1)L L ≥的升序序列S ，处在第/2n ????个位置的数为S 的中位数。例如，若序列S1=(11，13，15，17，19)，则S1的中位数是15，两个序列的中位数是含他们所有元素的的升序序列的中位数。例如，若S2=(2，4，6，8，20),则S1和S2的中位数是11。现在有两个等长升序序列A 和B ，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A 和B 的中位数。要求：

（1）给出算法的基本思想。

（2）根据设计思想，采用C 或者C++或JAVA 语言描述算法，关键之处给注释。

（3）说明你所涉及的算法的时间复杂度和空间复杂度。

7.写出折半查找的递归算法。初始调用时，low 为1，high 为

8.利用B 树做文件索引时，若假设磁盘的页块的大小是4000字节（实际应该是2的次幂，为了计算方便），指示磁盘地址的指针需要五个字节。现有个记录构成的文件，每个记录为200字节，其中包括五个关键字节。

试问在次采用B树做索引的文件中，B树的阶数应为多少假定文件数据部分未按关键字有序排列，则索引部分需要占多少磁盘页块

9.假定把关键字key散列到有n个表项（从0到n-1编址）的散列表中。对于下面的每一个散列函数H(key)(key为整数)，这些函数能够当做散列函数吗如果能够，他是好的散列函数吗请说明理由。设函数random(n)返回一个0到n-1之间的随机整数

1）H(key)=key/n。

2）H(key)=1.

3）H(key)=(key+random(n))%n。

4）H(key)=key%p(n);其中p(n)是不大于n的最大素数。

10.使用散列函数H(key)=key%11，把一个整数值转换成散列列表的下标，现在要把数据{1,13,34,38,33,27,22}依次插入到散列表中。

1）使用线性探测在散列法来构造散列表。

2）使用链表地址法构造散列表。

答案部分

一、选择题

1-10 B A B A B D D AB B B

11-20 B AD A C B A D C A B

21-30 A D AD BD CB A A C D D

二、综合题

1解答：(1)平均查找长度不同。因为有序顺序表查找到其关键字值比要查找值大的元素时就停止查找，并报告失败信息，不必查找到表尾；而无需表必须查找到表尾才能确定查找失败。

(2)平均查找长度相同。两者查找到表中元素的关键字值等于给定值时就停止查找。

(3)平均查找长度不同。有序顺序表中关键字相等的元素相继排列在一起，只要查找到第一个就可以连续查找到其他关键字相同的元素。而无序顺序表必须查找全部表中元素才能才能确定相同关键字的元素都找出来，所需时间就不相同了。

2解答：1）判定树如下图所示。

2)若查找元素275，依次与表中元素509、154、275进行比较，共比较3次。若查找684，依次与表中元素509、677、897、765进行比较，共进行四次。

3)在查找功能时，会找到图中某个圆形结点，其平均长度为

1411145(1223447)141414

succ i i ASL C ===+?+?+?=∑ 在查找失败时，会找到图中某个方形结点，但这个结点是虚构的，最后一次的比较元素为其父节点（圆形结点），故其平均长度为

15'11159(31414)152515

unsucc i i ASL C ===?+?=∑ 1. 解答：1)相应的判定树如下图所示。其中，每个关键字下的数字为其查找成功时的关键字比较次数。

n+3n+3

2)查找成功的平均查找长度为 8112301234111124881((1)2(2)4(3))81117817828n n n n n succ i i i i i i n i n i ASL C i i i i n n i i i i n n i n -+++=======??==+++ ???

??=++++++ ???

+??=+=+ ???∑∑∑∑∑∑∑

4解答：与二分法查找类似，k 分查找法可用k 叉树来描述。K 分查找法在查找成功时进行比较的关键字个数最多不超过根的深度，而具有n 个结点的k 叉树的深度为log 1k n +????，所以k 分查找法在查找成功时和给定值比较的关键字个数至多为log 1k n +????，

即时间复杂度为(log )k O n 。同理，查找不成功时，和给定值进行比较的关键字个数至多为log 1k n +????，故时间复杂度也为(log )k O n 。

5 解答：算法的基本思想：检索时可从开头开始向后顺序扫描，若找到指定

结点，将该结点和其前驱结点（若存在）交换。采用顺序结构的存储结构的算法实现如下：

int seqsrch(RcdType R[],ElemType k){

ey!=k)&&(i

i++

if(i0){ //找到，交换

temp=R[i];

R[i]=R[i-1];

R[i-1]=temp;

Return –-i; //返回交换后位置

}

else return -1; //查找失败

}

链表的实现方式类比这个方式自己完成。

6 解答：（1）算法的基本思想如下：

分别求出序列A和B的中位数，设为a和b，求序列A和B的中位数的过程如下：1）若a=b,则a或者b即为所求的中位数，算法结束。

2）若a

3）若a>b，则舍弃序列A中较大的一半，同时舍弃B中较小一半，要求舍弃长度相等。

在保留两个升序序列中，重复过程1,2,3，直到两个序列中只含一个元素为止，较小者即为所求的中位数。

(2)算法实现如下：

Int M_search(int A[],int B[],int n)

int s1=0,d1=n-1,m1,s2=1,d2=n-1,m2;

//分别表示序列A和B中的首位数、末尾数和中位数

While (s1!=d1||s2!=d2){

m1=(s1+d1)/2;

m2=(s2+d2)/2;

if(A[m1])==B[m1])

return A[m1]; //满足条件1

if(A[m1])

if((s1+d1)%2==0){ //若元素个数为奇数

s1=m1;//舍弃A中间点以前的部分且保留中间点

d2=m2;//舍弃B中间点以后的部分且保留中间点}

else{ //元素个数为偶数

s1=m1+1; //舍弃A中间点及中间点以前的部分

d2=m2; //舍弃B中间点以后的部分且保留中间点

}

}

else{ //满足条件3

if((s1+d1)%2==0){//若元素为奇数

d1=m1; //舍弃A 中间点以后的部分且保留中间点 s2=m2; //舍弃B 中间点以前的部分且保留中间点 }

else{ //元素个数为偶数

d1=m1+1; //舍弃A 中间点以前的部分且保留中间点 s2=m2; //舍弃B 中间点及中间点的以前部分

}

}

}

return A[s1]

}

(3) 算法的时间复杂度为2(log )O n ，空间复杂度(1)O 。

7 解答：算法的基本思想：根据查找的起始位置和终止位置，将查找序列一分为二，判断所查找的关键在那一部分，然后用新的序列起始位置和终止位置递归求解。

算法代码：

Typedef struct{//查找表的数据结构

ElemType *elem; //存储空间基址，建表时按实际长度分配，0号留空

int length;//表的长度

}SSTable

Int BinsearchRec(SSTable ST, ElemType key ,int low,int high){

//在有序表中递归折半查找其关键字为key 的元素，返回在表中的序号 If(low>high)

return 0;

mid=(low+high)/2; //取中间位置

if(key>[mid]) //向后半部分查找

Search(ST,key,mid+1,high);

Else if (key< [mid]) //向前半部分查找

Search(ST,key,low,mid-1);

Else //查找成功

Return mid;

}

算法把规模为n 复杂问题经过多次递归调用转化我规模减半的子问题求解。时间复杂度为2(log )O n ，算法中用到了一个递归工作栈，其规模于递归深度有关，也是2(log )O n

8 解答：根据B 树的概念，一个索引结点应适应操作系统一次读写的物理记录大小，其大小应取不超过单最接近一个磁盘页块的大小。假设B 树为M 阶，一个B 树最多存放m-1个关键字（5个字节）和对应的记录地址（5字节）、m 个子树指针（5个字节）和一个指示结点中实际关键字个数的整数（2字节）。则

有：(2(1))524000m m ?-+?+≤

计算结果，267m ≤。

一个索引结点最多可存放m-1=256个索引项，最少可存放/21133m -=????

个索引项。全部有n=个记录，每个记录占用空间200个字节，每个页块可存放4000/200=20个记录，则全部记录分布在/20=1000000页块中，最多需要占用1000000/133=7519个磁盘页块作为B 树的索引，最少占用1000000/266=3759个磁盘页块作为B 树索引。

9 解答：1)不能当做散列函数，因为key/n 可能大于n,这样无法找到合适的位置。

2)能当做散列函数，但不是一个好的散列函数，因为所有的关键字都映射到同一位置，造成大量的冲突机会。

3)不能当做散列函数，因为该函数的返回值不确定，这样无法进行正常查找。

4)能当做散列函数,是一个好的散列函数。

10 解答：1)由装载因子，数据总数为7，得一维数组大小为7/=10，数组下

在计算查找失败时的平均查找长度时，要特别注意防止定势。在查找失败时既不是根据表中元素个数，也不是根据表长来计算平均查找长度的。

查找失败时，在概率相等情况下，经过散列函数计算后只可能映射到表中0-6位置，且映射到0-6中任一位置的概率是相等的。因此，是根据散列函数（MOD

=(3+2+1+2+1+5+4)/7=18/7

数据结构课后习题与解析第六章

第六章习题 1．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。2．对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。 3．已知一棵度为k的树中有n 1个度为1的结点，n 2 个度为2的结点，……，n k 个度为k的结点， 则该树中有多少个叶子结点并证明之。 4.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。 5．已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？ 6．给出满足下列条件的所有二叉树： ①前序和后序相同 ②中序和后序相同 ③前序和后序相同 7． n个结点的K叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的Child 域有多少个？ 8．画出与下列已知序列对应的树Ｔ： 树的先根次序访问序列为GFKDAIEBCHJ； 树的后根次序访问序列为DIAEKFCJHBG。 9．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为： 0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10 请为这8个字母设计哈夫曼编码。 10．已知二叉树采用二叉链表存放,要求返回二叉树T的后序序列中的第一个结点指针,是否可不用递归且不用栈来完成?请简述原因. 11. 画出和下列树对应的二叉树：

12．已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。 13．编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。 14．分别写函数完成：在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。 15．分别写出算法，实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。 16．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。 17．对以孩子-兄弟链表表示的树编写计算树的深度的算法。 18．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出后序遍历非递归的算法。 19．设二叉树按二叉链表存放，写算法判别一棵二叉树是否是一棵正则二叉树。正则二叉树是指：在二叉树中不存在子树个数为1的结点。 20．计算二叉树最大宽度的算法。二叉树的最大宽度是指：二叉树所有层中结点个数的最大值。 21．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。 22. 证明：给定一棵二叉树的前序序列与中序序列，可唯一确定这棵二叉树； 给定一棵二叉树的后序序列与中序序列，可唯一确定这棵二叉树； 23. 二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。 24. 二叉树按照二叉链表方式存储，编写算法，将二叉树左右子树进行交换。 实习题 1.[问题描述] 建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序）， 打印输出遍历结果。

数据结构第六章一二次作业

上机题 （1）编写完整程序，用先序遍历法建立二叉树的二叉链 表存储结构。输出该二叉树的先、中、后序遍历结 点访问次序以及层次遍历结点访问次序。（建议结 点数据域类型为char） // erchashu.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include #include typedef struct node { char data; struct node *lchild, *rchild; }*BiT, BiTNode; BiT crtBT() { char ch; BiT bt; ch=getchar(); if(ch=='#') return NULL; bt=new BiTNode(); bt->data=ch; bt->lchild=crtBT(); bt->rchild=crtBT(); return bt;

} void preorder(BiT bt) { if(bt) { printf("%c",bt->data); preorder(bt->lchild); preorder(bt->rchild); } //printf("\n"); } void midorder(BiT bt) { if(bt) { midorder(bt->lchild); printf("%c",bt->data); midorder(bt->rchild); } //printf("\n"); } void lasorder(BiT bt) { if(bt) { lasorder(bt->lchild); lasorder(bt->rchild); printf("%c",bt->data); } //printf("\n"); } int main(int argc, char* argv[]) { BiT bt; bt=crtBT(); preorder(bt); printf("\n"); midorder(bt); printf("\n"); lasorder(bt); printf("\n"); return 0; } （2)从键盘输入n个数据建立n元完全二叉树顺序存储结

数据结构-第六章-图-练习题及答案详细解析(精华版)

图 1. 填空题 ⑴ 设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵ 任何连通图的连通分量只有一个，即是（）。 【解答】其自身 ⑶ 图的存储结构主要有两种，分别是（）和（）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。 【解答】求第j列的所有元素之和 ⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。 【解答】出度

⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 ⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼ 如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 ⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。 【解答】vi, vj, vk 【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。 2. 选择题 ⑴ 在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。 A 1/2 B 1 C 2 D 4 【解答】C 【分析】设无向图中含有n个顶点e条边，则。

数据结构第六章习题课

1、下图所示的4棵二叉树中，不是完全二叉树的是（） 2、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法（）。 A 、正确 B 、错误 C 、不一定 3、已知某二叉树的后序遍历序列是dabec ，中序遍历序列是debac ，它的前序遍历序列是（）。 A 、acbed B 、decab C 、deabc D 、cedba 4、如果T2是由有序树T 转换而来的二叉树，那么T 中结点的后序就是T2中结点的（）。 A 、前序 B 、中序 C 、后序 D 、层次序 5、深度为5的二叉树至多有（）个结点。 A 、16 B 、32 C 、31 D 、10 6、在一个非空二叉树的中序遍历序列中，根结点的右边（）。 A 、只有右子树上的所有结点 B 、只有右子树上的部分结点 C 、只有左子树上的部分结点 D 、只有左子树上的所有结点 7、树最适合用来表示（）。 A 、有序数据元素 B 、无序数据元素 C 、元素之间具有分支层次关系的数据 D 、元素之间无联系的数据。 8、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。 A 、不发生改变 B 、发生改变 C 、不能确定 D 、以上都不对 9、实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用（）存储结构。 A 、二叉链表 B 、广义表存储结构 C 、三叉链表 D 、顺序存储结构 10、对一个满二叉树，m 个树叶，n 个结点，深度为h ，则（）。 A 、n=m+h B 、h+m=2n C 、m=h-1 D 、n=2h -1 11、设n ，m 为二叉树上的两个结点，在中序遍历时，n 在m 前的条件是（）。 A 、n 在m 右方 B 、n 是m 祖先 C 、n 在m 左方 D 、n 是m 子孙 12．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/- ， A B C D

数据结构(C++版)课后作业6-8章附答案

第6 章图 课后习题讲解 1. 填空题 ⑴设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵任何连通图的连通分量只有一个，即是（）。【解答】其自身 ⑶图的存储结构主要有两种，分别是（）和（）。【解答】邻接矩阵，邻接表 ⑸已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。【解答】求第j列的所有元素之和 ⑹有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。【解答】出度 ⑺图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 （8）如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 2. 选择题 ⑵n个顶点的强连通图至少有（）条边，其形状是（）。A n B n+1 C n-1 D n×(n-1) E 无回路 F 有回路G 环状H 树状【解答】A，G ⑶含n 个顶点的连通图中的任意一条简单路径，其长度不可能超过（）。 A 1 B n/2 C n-1 D n 【解答】C 【分析】若超过n-1，则路径中必存在重复的顶点。 （4）最小生成树指的是（）。 A 由连通网所得到的边数最少的生成树 B 由连通网所得到的顶点数相对较少的生成树 C 连通网中所有生成树中权值之和为最小的生成树 D 连通网的极小连通子图 【解答】C （5）下面关于工程计划的AOE网的叙述中，不正确的是（） A 关键活动不按期完成就会影响整个工程的完成时间 B 任何一个关键活动提前完成，那么整个工程将会提前完成 C 所有的关键活动都提前完成，那么整个工程将会提前完成 D 某些关键活动若提前完成，那么

数据结构第六章树和二叉树习题及答案

习题六树和二叉树 一、单项选择题 1．以下说法错误的是（） A. 树形结构的特点是一个结点可以有多个直接前趋 B. 线性结构中的一个结点至多只有一个直接后继 C. 树形结构可以表达（组织）更复杂的数据 D. 树（及一切树形结构）是一种”分支层次”结构 E. 任何只含一个结点的集合是一棵树 2. 下列说法中正确的是（） A. 任何一棵二叉树中至少有一个结点的度为2 B. 任何一棵二叉树中每个结点的度都为2 C. 任何一棵二叉树中的度肯定等于2 D. 任何一棵二叉树中的度可以小于2 3. 讨论树、森林和二叉树的关系，目的是为了（） A. 借助二叉树上的运算方法去实现对树的一些运算 B. 将树、森林按二叉树的存储方式进行存储 C. 将树、森林转换成二叉树 D. 体现一种技巧，没有什么实际意义4．树最适合用来表示（） A. 有序数据元素 B .无序数据元素 C.元素之间具有分支层次关系的数据 D .元素之间无联系的数据 5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B ．11 C ．15 D ．不确定 6. 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1, M2和M3与森林F 对应的二叉树根结点的右子树上的结点个数是（）。 A．M1 B ．M1+M2 C ．M3 D ．M2+M3 7．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（） A．250 B ．500 C ．254 D ．505 E ．以上答案都不对 8. 设给定权值总数有n 个，其哈夫曼树的结点总数为（） A. 不确定 B . 2n C . 2n+1 D . 2n-1 9．二叉树的第I 层上最多含有结点数为（） I I-1 I-1 I A．2I B ．2 I-1 -1 C ．2 I-1 D ．2 I -1 10．一棵二叉树高度为h, 所有结点的度或为0，或为2，则这棵二叉树最少有（）结点A．2h B ．2h-1 C ．2h+1 D ．h+1 11. 利用二叉链表存储树，则根结点的右指针是（）。 A.指向最左孩子 B .指向最右孩子 C .空D .非空 12．已知一棵二叉树的前序遍历结果为为（）。 A．CBEFDA B ．FEDCBA 13．已知某二叉树的后序遍历序列是（）。 ABCDEF中序遍历结果 为 C ．CBEDFA D dabec, 中序遍历序列是 CBAEDF则后序遍历的结 果 ．不定 debac , 它的前序遍历是

数据结构 第六章 图 练习题及答案详细解析

图 1. 填空题 ⑴设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵任何连通图的连通分量只有一个，即是（）。 【解答】其自身 ⑶图的存储结构主要有两种，分别是（）和（）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。 【解答】求第j列的所有元素之和 ⑹有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。 【解答】出度 ⑺图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 ⑻对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 ⑽在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。 【解答】vi, vj, vk

数据结构与算法第六章课后答案第六章 树和二叉树

第6章 树和二叉树（参考答案） 6.1 (1)根结点a 6.2 三个结点的树的形态： 三个结点的二叉树的形态： （1） （1） （2） （4） （5） 6．3 设树的结点数是n ，则 n=n0+n1+n2+……+nm+ (1) 设树的分支数为B ，有 n=B+1 n=1n1+2n2+……+mnm+1 (2) 由（1）和（2）有： n0=n2+2n3+……+(m-1)nm+1 6.4 (1) k i-1 (i 为层数) (2) (n-2)/k+1 (3) (n-1)*k+i+1 (4) (n-1)%k !=0; 其右兄弟的编号 n+1 6.5（1）顺序存储结构 注：#为空结点

6.6 (1) 前序 ABDGCEFH (2) 中序 DGBAECHF (3) 后序 GDBEHFCA 6.7 (1) 空二叉树或任何结点均无左子树的非空二叉树 (2) 空二叉树或任何结点均无右子树的非空二叉树 (3) 空二叉树或只有根结点的二叉树 6.8 int height(bitree bt) // bt是以二叉链表为存储结构的二叉树，本算法求二叉树bt的高度 { int bl,br; // 局部变量，分别表示二叉树左、右子树的高度 if (bt==null) return(0); else { bl=height(bt->lchild); br=height(bt->rchild); return(bl>br? bl+1: br+1); // 左右子树高度的大者加1（根） } }// 算法结束 6.9 void preorder(cbt[],int n,int i); // cbt是以完全二叉树形式存储的n个结点的二叉树，i是数 // 组下标，初始调用时为1。本算法以非递归形式前序遍历该二叉树 { int i=1,s[],top=0; // s是栈，栈中元素是二叉树结点在cbt中的序号 // top是栈顶指针，栈空时top=0 if (n<=0) { printf(“输入错误”);exit（0）；} while (i<=n ||top>0) { while(i<=n) {visit(cbt[i]); // 访问根结点 if (2*i+1<=n) s[++top]=2*i+1; //若右子树非空，其编号进栈 i=2*i;// 先序访问左子树 } if (top>0) i=s[top--]; // 退栈，先序访问右子树 } // END OF while (i<=n ||top>0) }// 算法结束 //以下是非完全二叉树顺序存储时的递归遍历算法，“虚结点”用‘*’表示void preorder(bt[],int n,int i); // bt是以完全二叉树形式存储的一维数组，n是数组元素个数。i是数 // 组下标，初始调用时为1。 { if (i<=n && bt[i]!=’*’) { visit(bt[i]); preorder(bt,n,2*i); preorder(bt,n,2*i+1); }// 算法结束 6.10 int equal(bitree T1,bitree T2); // T1和T2是两棵二叉树，本算法判断T1和T2是否等价 // T1和T2都是空二叉树则等价 // T1和T2只有一棵为空，另一棵非空，则不等价 // T1和T2均非空，且根结点值相等，则比较其左、右子树

数据结构课后习题答案第六章

第六章树和二叉树（下载后用阅读版式视图或web版式可以看清） 习题 一、选择题 1．有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最适合的数据结构为( )。 A.向量 B.树C图 D.二叉树 2．树最合适用来表示( )。 A.有序数据元素 B元素之间具有分支层次关系的数据 C无序数据元素 D.元素之间无联系的数据 3．树B的层号表示为la，2b，3d，3e，2c，对应于下面选择的( )。 A. la (2b (3d,3e),2c) B. a(b(D,e),c) C. a(b(d,e),c) D. a(b,d(e),c) 4.高度为h的完全二叉树至少有( )个结点，至多有( )个结点。 A. 2h_l B.h C．2h-1 D. 2h 5.在一棵完全二叉树中，若编号为f的结点存在右孩子，则右子结点的编号为( )。 A. 2i B. 2i-l C. 2i+l D. 2i+2 6.一棵二叉树的广义表表示为a(b(c)，d(e(，g(h))，f))，则该二叉树的高度为( )。 A.3 B.4 C.5 D.6 7.深度为5的二叉树至多有( )个结点。 A. 31 B. 32 C. 16 D. 10 8.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为( )个。 A. 15 B. 16 C. 17 D. 47 9.题图6-1中，( )是完全二叉树，( )是满二叉树。 10.在题图6-2所示的二叉树中：

(1)A结点是 A.叶结点 B根结点但不是分支结点 C根结点也是分支结点 D.分支结点但不是根结点 (2)J结点是 A.叶结点 B．根结点但不是分支结点 C根结点也是分支结点 D.分支结点但不是根结点 (3)F结点的兄弟结点是 A.E B.D C．空 D.I (4)F结点的双亲结点是 A.A B.B C.C D.D (5)树的深度为 A.1 B.2 C.3 D.4 (6)B结点的深度为 A.1 B.2 C.3 D.4 (7)A结点所在的层是 A.1 B.2 C.3 D.4 11.在一棵具有35个结点的完全二叉树中，该树的深度为( )。 A.5 B.6 C.7 D.8 12. 一棵有124个叶结点的完全二叉树，最多有( )个结点。 A．247 B．248 C．249 D．250 13.用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R[1…n]中，结点R[i]若 有左子树，则左子树是结点( )。 A. R[2i+l] B. R[2i] C.R[i/2] D. R[2i-1] 14.在一非空二叉树的中序遍历序列中，根结点的右边( )。 A.只有右子树上的所有结点 B.只有右子树上的部分结点 C.只有左子树上的部分结点 D.只有左子树上的所有结点 15．一棵度为m的树中，有n i个度为1的结点，有n2个度为2的结点……，有n m个度为m的结点，则该树的叶结点数为( )。 A. n1+n2+...+n m B. (m-l) n m+...+n2+1

数据结构第六章题目讲解

02一选择题：1、以下说法错误的是 ①树形结构的特点是一个结点可以有多个直接前趋 ②线性结构中的一个结点至多只有一个直接后继③树形结构可以表达(组织)更复杂的数据④树(及一切树形结构)是一种"分支层次"结构⑤任何只含一个结点的集合是一棵树 2．深度为6的二叉树最多有( )个结点①64 ②63 ③32 ④31 3 下列说法中正确的是 ①任何一棵二叉树中至少有一个结点的度为2 ②任何一棵二叉树中每个结点的度都为2 二叉树可空 ③任何一棵二叉树中的度肯定等于2 ④任何一棵二叉树中的度可以小于2 4 设森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的右子树上有（）个结点。 ①n1-1 ②n1③n1+n2+n3④n2+n3+n4 二．名词解释：1 结点的度 3。叶子 4。分支点 5。树的度 三填空题二叉树第i(i>=1)层上至多有_____个结点。 1、深度为k(k>=1)的二叉树至多有_____个结点。 2、如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1<=i<=n)的结点X 有：若i=1,则结点X是_ ____；若i〉1,则X的双亲PARENT(X)的编号为__ ____。 若2i>n，则结点X无_ _____且无_ _____；否则，X的左孩子LCHILD(X)的编号为____。若2i+1>n，则结点X无__ ____；否则，X的右孩子RCHILD(X)的编号为_____。 4．以下程序段采用先根遍历方法求二叉树的叶子数，请在横线处填充适当的语句。 Void countleaf(bitreptr t,int *count)/*根指针为t，假定叶子数count的初值为0*/ {if(t!=NULL) {if((t->lchild==NULL)&&(t->rchild==NULL))__ __; countleaf(t->lchild,&count); countleaf(t->rchild,&count);} } 5 先根遍历树和先根遍历与该树对应的二叉树，其结果_____。 6 由____转换成二叉树时，其根结点的右子树总是空的。 7 哈夫曼树是带权路径度___ _____的树，通常权值较大的结点离根__ ______。 8 一棵树的形状如图填空题33所示，它的根结点是_____，叶子结点是______，结点H的度是_____，这棵树的度是_____，这棵树的深度是________，结点F的儿子结点是______，结点G的父结点是_____。

数据结构(C语言版)第6章习题答案

第6章树和二叉树自测卷解答 一、下面是有关二叉树的叙述，请判断正误（每小题1分，共10分） （√）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。（×）2.二叉树中每个结点的两棵子树的高度差等于1。 （√）3.二叉树中每个结点的两棵子树是有序的。 （×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。 （×）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。（应当是二叉排序树的特点） （×）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2i-1） （×）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （×）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。（应2i-1）（√）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （正确。用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。）即有后继链接的指针仅n-1个。 （√）10. 〖01年计算机系研题〗具有12个结点的完全二叉树有5个度为2的结点。 最快方法：用叶子数＝[n/2]＝6，再求n2=n0-1=5 二、填空（每空1分，共15分） 1．由３个结点所构成的二叉树有5种形态。 2. 【计算机研2000】一棵深度为6的满二叉树有n1+n2=0+ n2= n0-1=31 个分支结点和26-1 =32个叶子。 注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。 3．一棵具有２５７个结点的完全二叉树，它的深度为9。 （注：用? log2(n) ?+1= ? 8.xx ?+1=9 4.【全国专升本统考题】设一棵完全二叉树有700个结点，则共有350个叶子结点。 答：最快方法：用叶子数＝[n/2]＝350 5. 设一棵完全二叉树具有1000个结点，则此完全二叉树有500个叶子结点，有499个度为2的结点，有1个结点只有非空左子树，有0个结点只有非空右子树。 答：最快方法：用叶子数＝[n/2]＝500 ，n2=n0-1=499。另外，最后一结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝0. 6.【严题集6.7③】一棵含有n个结点的k叉树，可能达到的最大深度为n，最小深度为2。 答：当k=1(单叉树)时应该最深，深度＝n（层）；当k=n-1（n-1叉树）时应该最浅，深度＝2（层），但不包括n=0或1时的特例情况。教材答案是“完全k叉树”，未定量。) 7. 【试题1】二叉树的基本组成部分是：根（N）、左子树（L）和右 子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即 按N L R次序），后序法（即按L R N次序）和中序法（也称

数据结构第六章知识题课

1、下图所示的4棵二叉树中，不是完全二叉树的是（ ） 2、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法（ ）。 A 、正确 B 、错误 C 、不一定 3、已知某二叉树的后序遍历序列是dabec ，中序遍历序列是debac ，它的前序遍历序列是（ ）。 A 、acbed B 、decab C 、deabc D 、cedba 4、如果T2是由有序树T 转换而来的二叉树，那么T 中结点的后序就是T2中结点的（ ）。 A 、前序 B 、中序 C 、后序 D 、层次序 5、深度为5的二叉树至多有（ ）个结点。 A 、16 B 、32 C 、31 D 、10 6、在一个非空二叉树的中序遍历序列中，根结点的右边（ ）。 A B C D

A、只有右子树上的所有结点 B、只有右子树上的部分结点 C、只有左子树上的部分结点 D、只有左子树上的所有结点 7、树最适合用来表示（）。 A、有序数据元素 B、无序数据元素 C、元素之间具有分支层次关系的数据 D、元素之间无联系的数据。 8、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。 A、不发生改变 B、发生改变 C、不能确定 D、以上都不对 9、实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用（）存储结构。 A、二叉链表 B、广义表存储结构 C、三叉链表 D、顺序存储结构 10、对一个满二叉树，m个树叶，n个结点，深度为h，则（）。 A、n=m+h B、h+m=2n C、m=h-1 D、n=2h-1 11、设n，m为二叉树上的两个结点，在中序遍历时，n在m前的条件是（）。 A、n在m右方 B、n是m祖先 C、n在m左方 D、n是m子孙12．已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，

数据结构 第6章习题答案

第6章树和二叉树习题解答 一、下面是有关二叉树的叙述，请判断正误（每小题1分，共10分） （√）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。（×）2.二叉树中每个结点的两棵子树的高度差等于1。 （√）3.二叉树中每个结点的两棵子树是有序的。 （×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。 （×）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。（应当是二叉排序树的特点） （×）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2i-1） （×）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （×）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。（应2i-1）（√）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （正确。用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。）即有后继链接的指针仅n-1个。 （√）10. 〖01年考研题〗具有12个结点的完全二叉树有5个度为2的结点。 最快方法：用叶子数＝[n/2]＝6，再求n2=n0-1=5 二、填空（每空1分，共15分） 1．由３个结点所构成的二叉树有5种形态。 2. 【计算机研2000】一棵深度为6的满二叉树有n1+n2=0+ n2= n0-1=31 个分支结点和26-1 =32个叶子。 注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。 3．一棵具有２５７个结点的完全二叉树，它的深度为9。 （注：用? log2(n) ?+1= ? 8.xx ?+1=9 4.【全国专升本统考题】设一棵完全二叉树有700个结点，则共有350个叶子结点。 答：最快方法：用叶子数＝[n/2]＝350 5. 设一棵完全二叉树具有1000个结点，则此完全二叉树有500个叶子结点，有499个度为2的结点，有1个结点只有非空左子树，有0个结点只有非空右子树。 答：最快方法：用叶子数＝[n/2]＝500 ，n2=n0-1=499。另外，最后一结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝0. 6.【严题集6.7③】一棵含有n个结点的k叉树，可能达到的最大深度为n，最小深度为2。 答：当k=1(单叉树)时应该最深，深度＝n（层）；当k=n-1（n-1叉树）时应该最浅，深度＝2（层），但不包括n=0或1时的特例情况。教材答案是“完全k叉树”，未定量。) 7. 【试题1】二叉树的基本组成部分是：根（N）、左子树（L）和右 子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即 按N L R次序），后序法（即按L R N次序）和中序法（也称

数据结构第六章

一、单项选择题 1.已知一个长度为16的顺序L，气元素按关键字有序排列，或采用折半查找法查找一个不在L中存在的元素，则关键字的比较次数最多的是（）。 A．4 B. 5 C. 6 D. 7 2.顺序查找适合于存储结构为（）的线性表。 A.顺序存储结构或链式存储结构 B.散列存储结构 C.索引存储结构 D.压缩存储结构 3.对长度为n的有序单链表，若查找每个元素的概率相等，则顺序查找表中任意一个元素的查找成功的平均查找长度为（）。 2 B.(n+1)/2 C.(n-1)/2 4 4.对长度为3的顺序表进行查找，若查找的第一个元素概率为1/2，查找第二个元素的概率为1/3，查找第三个元素的概率为1/6，则查找表中任意一个元素的平均查找长度为( )。 3 3 3 5.当采用分块查找时，数据的组织方式为（）。 A.数据分成若干块，每块内数据有序 B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中数据个数需相同 6.下列关于二分查找的叙述中，正确的是（）。 A．表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序且表中数据必须是整型，实型或字符型 C. 表必须有序，而且只能从小到大排列 D．表必须有序，且表只能以顺序方式存储 7.使用二分（折半）查找元素的速度比用顺序法（）。 A.必然快 B.必然慢 C.相等 D.不能确定 8.已知一个长度为16的顺序表，其元素按关键字有序排列，若采用折半查找查找一个不存在的元素，则比较的次数至少是（），至多是（）。

数据结构_第六章_考试题目

一选择 1．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（） A．250 B．500 C．254 D．505 E．以上答案都不对 2. 有关二叉树下列说法正确的是（） A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 3．二叉树的第I层上最多含有结点数为（） A．2I B．2I-1-1 C．2I-1D．2I -1 4. 一棵树高为K的完全二叉树至少有（）个结点 A．2k -1 B. 2k-1-1 C. 2k-1 D. 2k 5．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。 A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历 6．在下列存储形式中，哪一个不是树的存储形式？（） A．双亲表示法B．孩子链表表示法C．孩子兄弟表示法D．顺序存储表示法 7．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。 A．CBEFDA B．FEDCBA C．CBEDFA D．不定 8. 某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则前序序列是：A．E,G,F,A,C,D,B B．E,A,C,B,D,G,F C．E,A,G,C,F,B,D D．上面的都不对 9．二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是： A、E B、F C、G D、H 二判断 1. 二叉树是度为2的有序树。× 2. 完全二叉树一定存在度为1的结点。× 3. 对于有N个结点的二叉树，其高度为log2n。× 4. 二叉树的遍历结果不是唯一的. √

《数据结构》第六章作业参考答案

第六章 树和二叉树 6.3 6.14 (a)右单支树 (b) 左单支树 (c)只有根结点的二叉树 6.15 后序遍历序列：GDBEHFCA 后序线索二叉树 6.19 (b) (c) 具有3个结点的树的形态有两种： 具有3个结点的二叉树形态有五种

(d) 6.21 (a) (b) (c) (d) (e)

6.22 (1) (a)A (b)ABC (c)ABC (d)ABCEIJFGKHD (2) (a)A (b)CBA (c)BCA (d)BIJEFKGHCDA 6.26 赫夫曼树 提高通信信道的利用率，提高报文发送速度和节省存储空间。 6．27 6.42 解:依题意:计算一棵二叉树的叶子结点数的递归模型如下: ?? ? ??>-+>-==>-=>-===其它 且若若)()()(1 )(0)(rchild b f lchild b f b f NULL rchild b NULL lchild b b f NULL b b f

int LeafCount_BiTree(Bitree T)//求二叉树中叶子结点的数目 { if(!T) return 0; //空树没有叶子 else if(!T->lchild && !T->rchild) return 1; //叶子结点 else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加上右子树的叶子数}//LeafCount_BiTree 6.43 void Bitree_Revolute(Bitree T)//交换所有结点的左右子树 { if(T) { T->lchild<->T->rchild; //交换左右子树 Bitree_Revolute(T->lchild); Bitree_Revolute(T->rchild); //左右子树再分别交换各自的左右子树 } }//Bitree_Revolute 6.47 void LayerOrder(Bitree T)//层序遍历二叉树 { InitQueue(Q); //建立工作队列 if(T) EnQueue(Q,T); while(!QueueEmpty(Q)) { DeQueue(Q,p); visit(p->data); if(p->lchild) EnQueue(Q,p->lchild); if(p->rchild) EnQueue(Q,p->rchild); } }//LayerOrder 6.56 BTNode *PreOrder_Next(BTNode *p)//在先序后继线索二叉树中查找结点p的先序后继,并返回指针 { if(p->RTag==Thread) return p->rchild; else if(p->lchild) return p->lchild; else return p->rchild; }//PreOrder_Next

第六章 数据结构习题pll

习题6解答 判断题： 1.二叉树中每个结点有两个子女结点，而对一般的树则无此限制，因此二叉树是树的特殊情形。（） 2.二叉树就是结点度为2的树。 ( ) 3.二叉树中不存在度大于2的结点，当某个结点只有一棵子树时无所谓左、右子树之分。 ( ) 4.当k≥1时，高度为k的二叉树至多有21 k个结点。 5.完全二叉树的某结点若无左孩子，则它必是叶结点。 ( ) 6.用一维数组存放二叉树时，总是以前序遍历顺序存储结点。（） 7.若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点。（） 8.存在这样的二叉树，对它采用任何次序的遍历，结果相同。（） 9.中序线索二叉树的优点之一是便于在中序下查找前驱结点和后继结点。（） 10.将一棵树转换成二叉树后，根结点没有左子树。（） 11.由树转换成二叉树，其根结点的右子树总是空的。（） 12.前序遍历森林和前序遍历与该森林对应的二叉树其结果不同。（） 13.在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树。（） 14.在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理。（） 15.霍夫曼树一定是满二叉树。（） 16.树的度是树内各结点的度之和。（） 17.由二叉树的结点构成的集合可以是空集合。（） 18.一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。（） 选择题： 19.树最适合用来表示( )。 A．有序数据元素 B. 无序数据元素 C．元素之间具有分支层次关系的数据 D. 元素之间无联系的数据 20.如果结点A有3个兄弟，而且B是A的双亲，则B的度是( )。 A. 4 B. 5 C. 1 D. 3 21.下列有关二叉树的说法正确的是( )。 A．二叉树的度为2 B. 一棵二叉树度可以小于2 C．二叉树中至少有一个结点的度为2 D. 二叉树中任一个结点的度都为2 22.以下说法错误的是( )。 A．二叉树可以是空集 B. 二叉树的任一结点都可以有两棵子树 C．二叉树与树具有相同的树形结构 D. 二叉树中任一结点的两棵子树有次序之分 23.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为( )个。 A．15 B. 16 C. 17 D.47 24. 用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组R[1..n]中，结点R[i]若有左子女，则左子女是结点( )。

数据结构复习题-第6章答案2014-6-16

第6章树和二叉树 一、选择题（每小题1分，共10分） 1.以下数据结构中，（ A ）是非线性数据结构。 A.树 B.线性表 C.队列 D.栈 2.在一棵二叉树中第五层上的结点数最多为（ B ）。 A.8 B.15 C.16 D.32 3. 已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ A ）。 A. CBEFDA B. FEDCBA C. CBEDFA D. 不定 4.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是( B ）。 A.9 B.11 C.15 D.不确定 5.给定二叉树如图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3,7,5,6,1,2,4，则其遍历方式是（D ）。 A. LRN B. NRL C. RLN D. RNL 6.在下列存储形式中，哪一个不是树的存储形式？（ D ） A.双亲表示法 B.孩子表示法 C.孩子兄弟表示法 D.顺序存储表示法 7.有n个叶子的哈夫曼树的结点总数为（D ）。 A．不确定B．2n C．2n+1 D．2n-1 8.设i为n个结点的完全二叉树结点编号，i=1，2，3...n；若i≤（n-1）/2时，结点i的右孩子为（ B ） A.2i B.2i+1 C.2i-1 D.i+1 9. 由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（ C ）。 A.23 B.37 C.44 D.46 10.一棵具有n个结点的完全二叉树的树高度（深度）是（ A ）。 A. +1 B. log2n+1 C. D. log2n-1 11.由权值分别为7，9，4，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ B ）。 A.36 B.60 C.48 D.53 12.由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ B ）。 A. 24 B. 71 C. 48 D. 53 13.具有35个结点的完全二叉树的深度为( B )。 A. 5 B. 6 C. 7 D. 8 14.由权值分别为３,８,６,２,５的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ D ）． A．24 B．55 C．72 D．53 15.任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序( A )。 A．不发生改变 B．发生改变 C．不能确定 D．以上都不对