数据结构 (6)

第六章树和二叉树一．选择题1. 以下说法错误的是。

A.树形结构的特点是一个结点可以有多个直接前趋B.线性结构中的一个结点至多只有一个直接后继C.树形结构可以表达(组织)更复杂的数据D.树(及一切树形结构)是一种"分支层次"结构2. 如图6-2所示的4 棵二叉树中，不是完全二叉树。

图6-2 4 棵二叉树3. 在线索化二叉树中，t 所指结点没有左子树的充要条件是。

A. t->left == NULLB. t->ltag==1C. t->ltag==1 且t->left==NULL D .以上都不对4. 以下说法错误的是。

A.二叉树可以是空集B.二叉树的任一结点最多有两棵子树C.二叉树不是一种树D.二叉树中任一结点的两棵子树有次序之分5. 以下说法错误的是。

A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达B.在三叉链表上，二叉树的求双亲运算很容易实现C.在二叉链表上，求根，求左、右孩子等很容易实现D.在二叉链表上，求双亲运算的时间性能很好6. 如图6-3所示的4 棵二叉树，是平衡二叉树。

图6-3 4 棵二叉树7. 如图6-4所示二叉树的中序遍历序列是。

A. abcdgefB. dfebagcC. dbaefcgD. defbagc图6-4 1 棵二叉树8. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是。

A. acbedB. decabC. deabcD. cedba9. 如果T2 是由有序树T 转换而来的二叉树，那么T 中结点的前序就是T2 中结点的。

A. 前序B.中序C. 后序D. 层次序10. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是。

A. bdgcefhaB. gdbecfhaC. bdgaechfD. gdbehfca11. 将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双亲结点编号为。

30
Move Disk 2 from Peg A to Peg C Move Disk 1 from Peg B to Peg C Move Disk 3 from Peg A to Peg B Move Disk 1 from Peg C to Peg A Move Disk 2 from Peg C to Peg B Move Disk 1 from Peg A to Peg B Move Disk 4 from Peg A to Peg C Move Disk 1 from Peg B to Peg C Move Disk 2 from Peg B to Peg A Move Disk 1 from Peg C to Peg A
" from peg "， fromPeg， " to peg
/*把n-1个圆盘从auxPeg借助fromPeg移至
29
towers(n-1，auxPeg，toPeg，fromPeg); }设计一个测试主函数如下： ＃include <stdio.h> void main(void) {
Towers(4， 'A'， 'C'， 'B'); }程序运to Peg B
26
Move Disk i from Peg X to Peg Y 这样， 汉
诺塔问题的递归算法可设计如下： void towers(int n，
char fromPeg， char toPeg， char auxPeg)
{
if(n＝＝1)
/*递归出口*/
{
printf("%s%c%s%c＼n"， "move disk
并不是每个问题都适宜于用递归算法求解。 适宜于用递归 算法求解的问题的充分必要条件是：

数据结构-6(总分99,考试时间90分钟)一、单项选择题在每小题列出的四个选项中只有一个选项是符合题目要求的。

1. 具有12个记录的序列，采用冒泡排序最少的比较次数是( )A. 1B. 144C. 11D. 662. 任何一个带权的无向连通图的最小生成树( )A. 只有一棵B. 有一棵或多棵C. 一定有多棵D. 可能不存在3. 在一棵具有5层的满二叉树中，结点总数为( )个。

A. 33B. 32C. 31D. 304. 在循环双链表的p所指结点之后插入s所指结点的操作是( )A. P—＞next=s；B. p—＞next=s；s—＞prior=p；p—＞next—＞prior=s；p—＞next—＞prior=s；s—＞prior=p；s—＞next=p—＞next；s—＞next=p—＞nextC. s—＞prior=p；D. s—＞prior=p；s—＞next=p—＞next；s—＞next=p—＞next；p—＞next=s；p—＞next—＞prior=s；p—＞next—＞prior=s；p—＞next=s；5. 在下面的程序中，语句S的执行次数为( ) for(i=1;i＜=n-1;i++) {for(j=n;j＞=i;j--) {S; }6. 若用冒泡排序法对序列18,14,6,27,8,12,16,52,10,26,47,29,41,24从小到大进行排序，共要进行( )次比较。

A. 33B. 45C. 70D. 917. 用数组A[0..N-1]存放循环队列的元素值，若其头尾指针分别为front和rear，则循环队列中当前元素的个数为( )A. (rear-front+mod mB. (rear-front+1)mod mC. (rear-front-1+mod mD. (rear-fronmod m8. 若已知一个栈的输入序列为1,2,3…,n，其输出序列为P1，P2，…，Pn。

数据结构第六章题⽬讲解02⼀选择题：1、以下说法错误的是①树形结构的特点是⼀个结点可以有多个直接前趋②线性结构中的⼀个结点⾄多只有⼀个直接后继③树形结构可以表达(组织)更复杂的数据④树(及⼀切树形结构)是⼀种"分⽀层次"结构⑤任何只含⼀个结点的集合是⼀棵树2．深度为6的⼆叉树最多有( )个结点①64 ②63 ③32 ④313 下列说法中正确的是①任何⼀棵⼆叉树中⾄少有⼀个结点的度为2②任何⼀棵⼆叉树中每个结点的度都为2 ⼆叉树可空③任何⼀棵⼆叉树中的度肯定等于2 ④任何⼀棵⼆叉树中的度可以⼩于24 设森林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 先根遍历树和先根遍历与该树对应的⼆叉树，其结果_____。