选择题: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的父结点是_____。
9任意一棵具有n个结点的二叉树,若它有m个叶子,则该二叉树上度数为1的结点为_____ ___个。
1.由3个结点所构成的二叉树有种形态。
2. 一棵深度为6的满二叉树有个分支结点和个叶子。
3.一棵具有257个结点的完全二叉树,它的深度为。
4. 设一棵完全二叉树具有1000个结点,则此完全二叉树有(100-511)= 个叶子结点,有个度为2的结点,有个结点只有非空左子树,有个结点只有非空右子树。
5. 二叉树的基本组成部分是:根(N)、左子树(L)和右子树(R)。因而二叉树的遍历次序有六种。最常用的是三种:前序法(即按N L R次序),后序法(即按次序)和中序法(也称对称序法,即按L N R次序)。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH,中序序列是FEBGCHD,则它的后序序列必是。
6. 用5个权值{3, 2, 4, 5, 1}构造的哈夫曼(Huffman)树的带权路径长度是。
7.一个深度为h的二叉树最多有结点,最少有结点。
二、选择题1.二叉树是非线性数据结构,所以。
(A)它不能用顺序存储结构存储; (B)它不能用链式存储结构存储; (C)顺序存储结构和链式存储结构都能存储; (D)顺序存储结构和链式存储结构都不能使用2. 具有n(n>0)个结点的完全二叉树的深度为。
(A) ?log2(n)? (B) ? log2(n)? (C) ? log2(n) ?+1 (D) ?log2(n)+1?
3.把一棵树转换为二叉树后,这棵二叉树的形态是。(A)唯一的(B)有2种(C)有多种,但根结点都没有左孩子(D)有多种,但根结点都没有右孩子
4. 树是结点的有限集合,它根结点,记为T。其余的结点分成为m(m≥0)个
的集合T1,T2,…,Tm,每个集合又都是树,此时结点T称为Ti的父结点,Ti称为T的子结点(1≤i≤m)。一个结点的子结点个数为该结点的。
供选择的答案
A:①有0个或1个②有0个或多个③有且只有1个④有1个或1个以上B: ①互不相交②允许相交③允许叶结点相交④允许树枝结点相交C:①权②度③次数④序
答案:A= B= C=
三、简答题1. 给定如图所示二叉树
T,请画出与其对应的中序线索二叉树。
1、如图所示的4棵二叉树中,()不是完全二叉树。
2、在线索化二叉树中,t所指结点没有左子树的充要条件是()。
A、t->left==NULL
B、t->ltag==1
C、t->ltag==1且t->left==NULL
D、以上都不对
3、已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是()
A、acbed
B、decab
C、deabc
D、cedba
4、如果T2是由有序树T转换而来的二叉树,那么T中结点的后序就是T2中结点的()
A、前序
B、中序
C、后序
D、层次序
5、对一个满二叉树,m个树叶,n个结点,深度为h,则()
A、n=h+m
B、h+m=2n
C、m=h-1
D、n=2(h次方)-1
6、具有5层结点的二叉平衡树至少有()个结点。A、10 B、12 C、15 D、17
二、填空题1、结点最少的树为____,结点最少的二叉树为_____。
2、从概念上讲,树与二叉树是两种不同的数据结构,将树转化为二叉树的基本目的是_____。
三、问答题1、假设二叉树采用顺序存储结构,如图(1)所示
(1)
(1)画出二叉树表示;(2)写出先序遍历,中序遍历和后序遍历的结果;
(3)写出结点值c得双亲结点,其左、右孩子;
(4)画出把此二叉树还原成森林的图。
在线索化二叉树中,t所指结点没有左子树的充要条件是______。
A、t->left==NULL
B、t->ltag==1
C、t->ltag==1且t->left==NULL
D、以上都不对
1、设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为______。A.2h B.2h-1 C.2h+1 D.h+1
2、如图所示的4棵二叉树,____不是完全二叉树。
3、树的基本遍历策略可分为先根遍历和后根遍历;二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里,我们把由树转化得到的二叉树叫做这个数对应的二叉树。结论正确的是_____。
A、树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B、树的后根遍历序列与其对应的二叉树的后序遍历序列相同
C、树的先根遍历序列与其对应的二叉树的中序遍历序列相同
D、以上都不对
5、线索二叉树是一种______结构A、逻辑B、逻辑与存储C、物理D、线性
二、简答题
1、指出树和二叉树的三个主要差别。
2、假设二叉树采用顺序存储结构,如图所示。
(1)画出二叉树表示
(2)写出先序遍历,中序遍历,后序遍历的结果
(3)写出结点值c的双亲结点,其左、右孩子
(4)画出把此二叉树还原成森林的图
1.讨论树、森林和二叉树的关系,目的是为了()
A.借助二叉树上的运算方法去实现对树的一些运算
B.将树、森林按二叉树的存储方式进行存储
C.将树、森林转换成二叉树D.体现一种技巧,没有什么实际意义
2.树最适合用来表示 ( )
A.有序数据元素 B.无序数据元素
C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据
3.若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是()A.9 B.11 C.15 D.不确定
4.设森林F中有三棵树,第一,第二,第三棵树的结点个数分别为M1,M2和M3。与森林F 对应的二叉树根结点的右子树上的结点个数是()。
A.M1 B.M1+M2 C.M3 D.M2+M3
5.利用二叉链表存储树,则根结点的右指针是()。
A.指向最左孩子 B.指向最右孩子 C.空 D.非空
二填空题1.深度为k的完全二叉树至少有___ ____个结点,至多有___ ____个结点2.具有n个结点的二叉树中,一共有________个指针域,其中只有________个用来指向结点的左右孩子,其余的________个指针域为NULL。
3.树的主要遍历方法有________、________、________等三种。
4.二叉树的先序序列和中序序列相同的条件是___ ___。
5.一个无序序列可以通过构造一棵___ ___树而变成一个有序序列,构造树的过程即为对无序序列进行排序的过程。
判断题 1. 一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。( ) 2.二叉树只能用二叉链表表示。()
3.用一维数组存储二叉树时,总是以前序遍历顺序存储结点。()
程序填空 1.以下程序是二叉链表树中序遍历的非递归算法,请填空使之完善。二叉树链表的结点类型的定义如下:
typedef struct node /*C语言/
{char data; struct node *lchild,*rchild;}*bitree;
void vst(bitree bt) /*bt为根结点的指针*/
{ bitree p; p=bt; initstack(s); /*初始化栈s为空栈*/
while(p || !empty(s)) /*栈s不为空*/
if(p) { push (s,p); (1)___ ; } /*P入栈*/
else { p=pop(s); printf(“%c”,p->data);(2)__ __; }/*栈顶元素出栈*/ }
2.二叉树存储结构同上题,以下程序为求二叉树深度的递归算法,请填空完善之。
int depth(bitree bt) /*bt为根结点的指针*/
{int hl,hr;
if (bt==NULL) return((1)_ __);
hl=depth(bt->lchild); hr=depth(bt->rchild);
if((2)_ __) (3)_ ____;
return(hr+1);}
1 .某二叉树的先序和后序遍历序列正好相反,则该二叉树一定是()。
A )空或只有一个结点
B )完全二叉树
C )二叉排序树
D )
2 .树的基本遍历策略可分为先根遍历和后根遍历;二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里,我们把由树转化得到的二叉树叫做这棵树对应的二叉树,其中结论()是正确的。 A )树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B )树的后根遍历序列与其对应的二义树的后序遍历序列相同
c )树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D )以上都不对
3 .按照二叉树的定义,具有3 个结点的二叉树有()种。 A ) 3B ) 4C ) SD ) 6
4 .深度为
5 的二叉树至多有()个结点。 A ) 16B ) 32C ) 3lD ) 10
5.二叉树前序遍历和中序遍历序列如下:前序遍历序列:EFHIJK 中序遍历序列:HFIEJK 则该二叉树根结点的右子树的根为:( )。 A ) E B ) F C ) D ) H
6 .树的基本遍历策略可分为先根遍历和后根遍历;二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里,我们把由树转化得到的二叉树叫做这棵树对应的二叉树,其中结论()是正确的。 A )树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B )树的后根遍历序列与其对应的二义树的后序遍历序列相同
c )树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D )以上都不对
二、填空题1、由10000个结点构成的二叉排序树 在等概率查找的假设下 查找成功时的平均查找长度的最大值可能达到______________________。
2、深度为k的完全二叉树至少有______个结点 至多有____个结点 若按自上而下 从左到右次序给结点编号(从1开始)
三、算法设计题
(1)假设二叉树T采用如下定义的存储结构 typedef struct node{ DataType data; struct node *lchild,*rchild,*parent; }PBinTree;其中 结点的lchild域和rchild 域已分别填有指向其左 右孩子的指针 而parent域中的值为空指针 拟作为指向双亲结点的指针域 。请编写一个递归算法 将该存储结构中各结点的parent域的值修改成指向其双亲结点的指针
.已知一算术表达式的中缀形式为 A+B*C-D/E,后缀形式为ABC*+DE/-,其前缀形式为( ) A.-A+B*C/DE B. -A+B*CD/E C.-+*ABC/DE D. -+A*BC/DE
2. 在下述结论中,正确的是()
①只有一个结点的二叉树的度为0; ②二叉树的度为2;③二叉树的左右子树可任意交换;
④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A.①②③ B.②③④ C.②④ D.①④
6. 设森林F 对应的二叉树为B,它有m 个结点,B 的根为p,p 的右子树结点个数为n,森林F 中第一棵树的结点个数是()A.m-n B.m-n-1 C.n+1 D.条件不足,无法确定
3.二叉树的第I 层上最多含有结点数为()A.2I B. 2I-1-1 C. 2I-1 D.2I -1 4.一棵二叉树的前序遍历序列为ABCDEFG,它的中序遍历序列可能是()A.CABDEFG B.ABCDEFG C.DACEFBG D.ADCFEG
5.下面的说法中正确的是().
(1)任何一棵二叉树的叶子结点在三种遍历中的相对次序不变;
(2)按二叉树定义,具有三个结点的二叉树共有6 种。
A.(1)(2) B.(1) C.(2) D.(1)、(2)都错
6.由3 个结点可以构造出多少种不同的有向树?()A.2 B.3 C.4 D.5
7.从下列有关树的叙述中,选出5 条正确的叙述()
A.二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。
B.当K≥1 时高度为K 的二叉树至多有2k-1 个结点。
C.用树的前序周游和中序周游可以导出树的后序周游。
D.线索二叉树的优点是便于在中序下查找前驱结点和后继结点。
E.将一棵树转换成二叉树后,根结点没有左子树。
F.一棵含有N 个结点的完全二叉树,它的高度是?LOG2N?+1。
G.在二叉树中插入结点,该二叉树便不再是二叉树。
H.采用二叉树链表作树的存储结构,树的前序周游和其相应的二叉树的前序周游的结果是一样的。
I.哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。
J.用一维数组存储二叉树时,总是以前序周游存储结点
2.判断题1.任何二叉树的后序线索树进行后序遍历时都必须用栈。
2.由一棵二叉树的前序序列和后序序列可以唯一确定它。
3.完全二叉树中,若一个结点没有左孩子,则它必是树叶。
4. 二叉树只能用二叉链表表示.
5. 一棵有n 个结点的二叉树,从上到下,从左到右用自然数依次给予编号,则编号为i 的结点的左儿子的编号为2i(2i< n),右儿子是2i+1(2i+1 三、填空题1.二叉树由_(1)__,__(2)_,_(3)__三个基本单元组成。 2.树在计算机内的表示方式有_(1)__,_(2)__,_(3)__。 3.在二叉树中,指针p 所指结点为叶子结点的条件是______。 4.中缀式a+b*3+4*(c-d)对应的前缀式为__(1)_,若a=1,b=2,c=3,d=4,则后缀式db/cc*a-b*+的运算结果为_(2)__。 5.二叉树中某一结点左子树的深度减去右子树的深度称为该结点的_____. 6.具有256 个结点的完全二叉树的深度为______。 7.已知一棵度为3 的树有2 个度为1 的结点,3 个度为2 的结点,4 个度为3 的结点,则该树有______个叶子结点。 8.深度为k 的完全二叉树至少有___(1)____个结点,至多有___(2)____个结点 9.下面的类PASCAL 语言递归算法的功能是判断一棵二叉树(采用二叉链表存贮结构)是否为完全二叉树。请把空缺的两部分补写完整。(提示:利用完全二叉树结点序号性质)TYPE link=^node; node=RECORD key:keytype; l,r:link; END; VAR all:boolean; n:integer; root:link; FUNC num(t:link):integer; BEGIN (1)______END; PROC chk(t:link;m{t 所指结点应有序号}:integer) BEGIN (2)_______END; BEGIN {建二叉树,其根由root 指出 } n:=num(root);{求结点数} all:=true; chk(root,1); IF all THEN writeln(‘该树为完全二叉树!’)ELSE writeln (’该树非完全二叉树!’) END; 10.将二叉树bt 中每一个结点的左右子树互换的C 语言算法如下,其中 ADDQ(Q,bt),DELQ(Q),EMPTY(Q) 分别为进队,出队和判别队列是否为空的函数,请填写算法中得空白处,完成其功能。typedef struct node {int data ; struct node *lchild, *rchild; }btnode; void EXCHANGE(btnode *bt) {btnode *p, *q; if (bt){ADDQ(Q,bt); while(!EMPTY(Q)) {p=DELQ(Q); q=(1)___; p->rchild=(2)___; (3)___=q; if(p->lchild) (4)___; if(p->rchild) (5)___; 11.下面使用类pascal 语言写的对二叉树进行操作的算法,请仔细阅读 TYPE pointer=^tnodetp; tnodetp=RECORD data: char; llink,rlink: pointer;END; linkstack=^linknodet; linknodet=RECORD data:pointer; next;linkstack;END; PROC unknown (VAR t:pointer); VAR p,temp:pointer; BEGIN p:=t; IF p<> NIL THEN [temp:=p^.llink ;p^.llink:=p^.rlink;;p^.rlink:=temp; unknown(p^.llink); unknown(p^.rlink); ] END; ①指出该算法完成了什么功能 ②用栈将以上算法改为非递归算法unknown1,其中有若干语句或条件空缺请在空缺处填写上适当的语句或条件 PROC inistack(VAR s:linkstack); (1)_______; s^.next:=NIL; ENDP; FUNC empty (s:linkstack):boolean; IF (2)_______THEN empty:=true ELSE empty:=false; ENDF; FUNC gettop(s:linkstack):pointer; gettop:= (3)_______; ENDF; FUNC pop(VAR s:linkstack):pointer; VAR p:linkstack; pop:=s^.next^.data; p:=s^.next; (4)_______;(5)_______; ENDF; PROC push (VAR s:linkstack;x:pointer); VAR p:linkstack; new(p); p^.data:=x; (6)_______; s^.next:=p; ENDP; PROC unknown1(VAR t:pointer); VAR p,temp: pointer; finish: boolean; BEGIN inistack(s); finish:=false; p:=t; REPEAT WHILE p<> NIL DO [temp:=p^.llink; p^.llink:=p^.rlink; p^.rlink:=temp; (7)_______; p:=p^.llink; ]; IF (8)____THEN [p:=gettop(s);temp;=pop(s);] ELSE (9)_______ UNTIL (10)___ ENDP; 若二叉树的后序遍历序列为dabec,中序遍历序列为debac,则前序序列遍历为()。 A、acbed B、decab C、deabc D、cedba 2. 具有35个结点的完全二叉树的深度为()A、5 B、6 C、7 D、8 3. 在线索化二叉树中,t所指结点没有左子树的充足条件是() A、t-lchild==NULL B、t->ltag==1 C、t->ltag==1&&t->lchild==NULL D、以上都不对 4. 设n,m为一棵二叉树上的两个结点,在中序遍历时,n在m前的条件是() A、n在m右方 B、n是m祖先 C、n在m左方 D、n是m子孙 5. 线索二叉树是一种()结构A、逻辑B、逻辑和存储C、物理D、线性 1、由一棵二叉树后序序列和()可唯一确定这棵二叉树。 2、含有n个结点的二叉树用二叉链表表示时,有()个空链域。 3、有m个叶子结点的哈夫曼树有()个结点。 4、前序为a,b,c且后序c,b,a的二叉树共有()棵。 5、已知完全二叉树的第4层有6个结点,则其叶子结点数是()。 一棵完全二叉树有500个结点,请问该完全二叉树有多少个叶子结点?有多少个度为1的结点?有多少个度为2的结点?如果完全二叉树有501个结点,结果如何?请写出推导过程。 1.设二叉树中每个结点均用一个字母表示,若一个结点的左子树或右子树为空,用#表示, 现前序遍历二叉树,访问的结点序列为ABD##C#E##F##,写出中序和后序遍历二叉树时结点的访问序列。 1.若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是()A.9 B.11 C.15 D.不确定 2.二叉树的第I层上最多含有结点数为()A.2I B.2I-1-1 C.2I-1 D.2I -1 3.已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为()。A.CBEFDA B.FEDCBA C.CBEDFA D.不定4.下面几个符号串编码集合中,不是前缀编码的是()。A.{0,10,110,1111} B.{11,10,001,101,0001} C.{00,010,0110,1000} D.{b,c,aa,ac,aba,abb,abc} 5. 树的基本遍历策略可分为先根遍历和后根遍历;二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里,我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论()是正确的。 A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D.以上都不对 二、判断1. 二叉树中所有结点 如果不存在非空左子树 则不存在非空右子树。() 2. 用一维数组存储二叉树时,总是以前序遍历顺序存储结点。( ) 3. 二叉树中序线索化后,不存在空指针域。() 三、填空1.深度为k的完全二叉树至少有_______个结点,至多有_______个结点 2. 在二叉树中,指针p所指结点为叶子结点的条件是______ 3.设一棵完全二叉树有700个结点,则共有_____个叶子结点。 四、程序1.试写出复制一棵二叉树的算法。二叉树采用标准链接结构 2.将下列由三棵树组成的森林转换为二叉树。(只要求给出转换结果) 列出图所示二叉树的叶结点、分支结点和每个结点的层次。 2. 如果一棵树有n1个度为1的结点, 有n2个度为2的结点, …, nm个度为m的结点, 试问有多少个度为0的结点? 试推导之。 3. 试分别找出满足以下条件的所有二叉树: (1) 二叉树的前序序列与中序序列相同; (2) 二叉树的中序序列与后序序列相同; (3) 二叉树的前序序列与后序序列相同 4. 请画出右图所示的树所对应的二叉树。 5. 已知一棵二叉树的先序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树。 选择题1.由三个结点可以构造出多少种不同的二叉树( ) 。A) 3 B) 4 C) 5 D) 6 2.在一棵深度为k的完全二叉树中,所含结点个数不小于( )。A)2k B) 2k+1C) 2k-1 D) 2k-1 3.对于任何一棵二叉树,如果其终端结点数为n0,度为2的结点数为n2,则n0=()。 A. n2-1 B. n2+1 C. n2 D. n2-2 4.已知二叉树的后序遍历序列是d a b e c,中序序列是d e b a c,则它的前序遍历是( )。 A) c e d b a B) a c b e d C) d e c a b D) d e a b c 二、填空题1.如果结点A有3个兄弟,而且B是A的双亲,则B的度是______。 2.若以{4,5,6,7,8}作为叶子结点的权值构造哈夫曼树,则其带权路径长度是______。 三、应用题1.要求二叉树按二叉链表形式存储, (1)写一个建立二叉树的算法。(2)写一个判别给定的二叉树是否是完全二叉树的算法。完全二叉树定义为:深度为K,具有N个结点的二叉树的每个结点都与深度为K的满二叉树中编号从1至N的结点一一对应。此题以此定义为准。 2.将下列由三棵树组成的森林转换为二叉树。(只要求给出转换结果) 1.4 A. 2 B. 4 C. 6 D. 8 2.用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1..n],结点R[i]若有左孩子,其左孩子的编号为结点()。A. R[2i+1] B. R[2i] C. R[i/2] D. R[2i-1] 3.已知一棵完全二叉树的结点总数为9个,则最后一层的结点数为()。A. 1 B. 2C. 3D. 4 4.对二叉排序树进行 ( )遍历,可以得到该二叉树所有结点构成的排序序列。 A、前序 B、中序 C、后序 D、按层次 5.在一棵具有n个结点的二叉树第i层上,最多具有 ( ) 个结点。 A、2i B、2i+1 C、2i-1 D、2n 判断题6.完全二叉树的某结点若无左孩子,则它必是叶结点。() 7.存在这样的二叉树,对它采用任何次序的遍历,结果相同。() 8.二叉树就是结点度为2的树。() 9.二叉树中不存在度大于2的结点,当某个结点只有一棵子树时无所谓左、右子树。() 10.已知二叉树的前序遍历序列和后序遍历序列并不能唯一地确定这棵树,因为不知道树的根结点是哪一个。() 11.中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。() 12.将一棵树转换成二叉树后,根结点没有左子树。() 13.用树的前序遍历和中序遍历可以导出树的后序遍历。() 14.哈夫曼树是带权路径长度最短的树,路径上权值较大的结点离根较近。() 15.不使用递归也能实现二叉树前序、中序和后序遍历。() 填空题16.一棵具有257个结点的完全二叉树,它的深度为。 17.若已知一棵二叉树的前序序列是BEFCGDH,中序序列是FEBGCHD,则它的后序序列必是。 18.用5 个权值{3, 2, 4, 5, 1}构造的哈夫曼(Huffman)树的带权路径长度是。 解答题19.已知二叉树的中序遍历序列是DBGEAFHC,后序遍历序列是DGEBHFCA,请构造一棵二叉树,并给出前序遍历序列。 以下说法错误的是( ) A.树形结构的特点是一个结点可以有多个直接前趋 B.线性结构中的一个结点至多只有一个直接后继 C.树形结构可以表达(组织)更复杂的数据D.树(及一切树形结构)是一种"分支层次"结构E.任何只含一个结点的集合是一棵树 2.下列说法中正确的是 ( ) A.任何一棵二叉树中至少有一个结点的度为2 B.任何一棵二叉树中每个结点的度都为2 C.任何一棵二叉树中的度肯定等于2 D.任何一棵二叉树中的度可以小于2 3.讨论树、森林和二叉树的关系,目的是为了() A.借助二叉树上的运算方法去实现对树的一些运算 B.将树、森林按二叉树的存储方式进行存储 C.将树、森林转换成二叉树D.体现一种技巧,没有什么实际意义 4.树最适合用来表示 ( ) A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据12.已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为()。A.CBEFDA B. FEDCBA C. CBEDFA D.不定 13.已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是()。A.acbed B.decab C.deabc D.cedba 二、判断题(在各题后填写“√”或“×”) 1. 完全二叉树一定存在度为1的结点。( ) 2.对于有N个结点的二叉树,其高度为log2n。( ) 3. 二叉树的遍历只是为了在应用中找到一种线性次序。( ) 4. 一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。( ) 三、填空题1.在二叉树中,指针p所指结点为叶子结点的条件是___ ___。 2.深度为k的完全二叉树至少有_______个结点,至多有___ ____个结点。 3.高度为8的完全二叉树至少有______个叶子结点。 4.具有n个结点的二叉树中,一共有________个指针域,其中只有________个用来指向结点的左右孩子,其余的________个指针域为NULL。 5.树的主要遍历方法有________、________、________等三种。 选择题1..如果T2是由数T转换而来的二叉树,那么对T中结点的后序遍历就是对T2中结点的___遍历。A 先序 B 中序 C 后序 D 层次序 2. 设数T的度是4,其中度为1,2,3和4的结点个数分别为4,2,1,1,则T中的叶子 数为_______ A.5 B.6 C.7 D.8 3. 由4个结点可以构造出________种不同的二叉树。A.10 B.12 C.14 D.16 4. 二叉树在线索后,人不能有效求解的问题是______ A. 在先序线索二叉树中求先序后继 B. 在中序线索二叉树中求中序后继 C. 在中序线索二叉树中求中序前驱 D.. 在后序线索二叉树中求后序后继 5. 一颗二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是____ A.9 B.11 C.15 D.不确定 6.设高度为h的二叉树只有度为0和2的结点,则此类二叉树中所包含的结点数至少为__个 A. 2h B. 2h-1 C.2h+1 D. h+1 7.设给定权值的叶子总数为n 个,其哈夫曼数的结点总数为_____ A. 不确定 B 2n C. 2n+1 D.2n-1 8. 某二叉树的先序遍历和后序遍历正好相反,则此二叉树一点是________ A. 空或只有一个结点 B. 完全二叉树 C. 单支数 D. 高度等与结点数 9. 在二叉树的先序序列,中序遍历和后序遍历中,所有叶子结点的先后顺序_____- A 都不相同 B. 完全相同 C. 先序和中序相同,而与后序不同 D. 中序和后序相同,而与先序不同 10. 根据使用频率,为五个字符设计的哈夫曼编码不可能是____ A.111,110,10,01,00 B. 000,001,010,011,1 C. 100,11,10,1,0 D. 001,000,01,11,10 二.填空题1.已知二叉树有50个叶子结点,则二叉树的总结点数至少是_____ 2.树在计算机中的存储结构有_________._________-和__________ 3.在一棵二叉树中,度为0的结点个数为N0,度为2的结点个数是N2,则有N0=_____ 4.叶子权数(5,6,17,8,19)所构造的哈夫曼数带权路径长度为_______ 5.设一棵完全二叉树叶子结点数为k ,最后一层结点数为偶数时,则该二叉树的高度为____,,最后一层结点数为奇数时,则该二叉树的高度为________ 6.有______种不同形态的二叉树可以按照中序遍历得到相同的abc序列 7.已知二叉树先序为ABDEGCF,中序为DBGEACF,则后序一定是_______ 8.深度为k的完全二叉树至少有______个结点,至多有_________个节点 9.具有10个叶子的哈夫曼树,其最大高度为_______,最小高度为________ 10.设F是一个森林,B是由F转换得到的二叉树,F中有n个非终端节点,则B中右指针 域为空的结点有________个 三.判断题1.哈夫曼树的结点个数不可能是偶数 2.二叉树中序线索化后,不存在空指针域 3.二叉树线索化后,任意一个结点均有指向其前驱和后继的线索 4.哈夫曼编码是前缀编码 5.非空的二叉树一定满足:某结点若有左孩子,则其中序前驱一定没有右孩子 6.必须把一般数转换成二叉树以后才能进行存储 7.由先序和后序遍历序列不能唯一确定一棵二叉树 8.一棵树中的叶子数一定等于与其对应的二叉树的叶子数 9.一个树的叶子数,在前序遍历和后序遍历下,皆以相同的相对位置出现 10.在哈夫曼树中权值相同的叶节点都在同一层上 四.综合题1.已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA,写出其先序遍历序列 五.程序填空1.一棵以孩子兄弟表示法存储,递归算法计算并返回根为r的数中叶子结点的个数(NULL代表空指针) Typedef struct tnode{ Struct tnode *firstson, *nextbrother; }Tnode; Int numberofleaf(Tnode*r) { Int num; If(r==NULL) num=0; Else if(r->firstson==NULL) Num=_____+numberrofleaf(r->nextbrother); Else____; Return(num); } 2. 假设二叉树t的结点有四个字段,它们分别是:data. Lchild .rchild.parent,,其中data存放结点值,lchild和rchild分别指向左子结点和右子结点,parent指向父结点。在下列程序中,非递归函数mid_order(t)实现了对二叉树t的中序遍历 Type struct node{ Int data; Struct node *ichild,*rchild; Struct node*parent; }Node; Void mid_order(Node *t) { Node *p,*q; P=NULL;q=t; Do{ While(q!=NULL) { __(1)_____; q=q->lchild; } If( (2) ) { printf(“%5d,p->data”); ___(3)______ } While(p!=NULL&&q==NULL) { do{ q=p; __(4)______; }while(p!=NULL&&q==p->rchild); If(p!=NULL) { printf(“5%d”,p->data); __(5)______; } } }while(_(6)_); printf(”\n”); 1. 在下述结论中,正确的是() ①只有一个结点的二叉树的度为0; ②二叉树的度为2;③二叉树的左右子树可任意交换; ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A.①②③ B.②③④ C.②④ D.①④ 2.若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是()A.9 B.11 C.15 D.不确定 3.若二叉树采用二叉链表存储结构,要交换其所有分支结点左、右子树的位置,利用( )遍历方法最合适。A.前序 B.中序 C.后序 D.按层次 4.()的遍历仍需要栈的支持.A.前序线索树 B.中序线索树 C.后序线索树5.下面几个符号串编码集合中,不是前缀编码的是()。 A.{0,10,110,1111} B.{11,10,001,101,0001} C.{00,010,0110,1000} D.{b,c,aa,ac,aba,abb,abc} 判断题 1. 一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。 2.将一棵树转成二叉树,根结点没有左子树; 3. 一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。 4. 用链表(llink-rlink)存储包含n个结点的二叉树时,结点的2n个指针区域中有n+1 个空指针。( ) 5.必须把一般树转换成二叉树后才能进行存储。 填空题1.树在计算机内的表示方式有_(1)__,_(2)__,_(3)__。 2.如果结点A有 3个兄弟,而且B是A的双亲,则B的度是______。 3.已知二叉树前序为ABDEGCF,中序为DBGEACF,则后序一定是____。 4.若以{4,5,6,7,8}作为叶子结点的权值构造哈夫曼树,则其带权路径长度是______。 1若二叉树用二叉链表作存贮结构,则在n个结点的二叉树链表中只有n—1个非空指针域。 2二叉树中每个结点的两棵子树的高度差等于1。3二叉树中每个结点的两棵子树是有序的。4二叉树中每个结点有两棵非空子树或有两棵空子树。 5二叉树中所有结点个数是2k-1-1,其中k是树的深度。 二选择题 1.树最适合用来表示__。A)有序数据元素B)无序数据元素 C)元素之间具有分支层次关系的数据D)元素之间无联系的数据 2.在一棵二叉树上第5层的结点数最多为__。A)8 B)16 C)15 D)32 ( ) 3、用顺序存储方法将完全二叉树中的所有结点逐层存放在数组R[1..n]中,结点R[i]若有子树,则左子树是结点__。A)R[2i+1] B)R[2i] C)R[i/2] D)R[2i-1] ( ) 4.在一棵具有k层的满三叉树中,结点总数为__。 A)(3k-1)/2 B)3k-1 C)(3k-1)/3 D) 3k ( ) 5.由带树为9,2,5,7的四个叶子结点树造一棵哈夫曼树,该树的带权路径长度为__。 A)29 B)37 C)46 D)44 ( )08、具有n(n>0)个结点的完全二叉树的深度为 三简答题试写出下图所示二叉树的“先序、中序、后序”遍功时得到的结点序列。 2把下图所示的树转换成二叉树。、 1.在二叉树的第i层上至多有2^(i-1)个结点(i>=1).()。 2.深度为k的二叉树至多有2^k-1个结点()。 3.对任何一颗二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n2=n0+1。()。 二、算法填空归Status PreOrderTraverse(BiTree T,Status(* Visit)(TElemType e)) { if(T) { if(Visit(T->data)) if(____[1]___) if(__[2]___) return OK; } } 一、按先序次序构造二叉链表表示的二叉树T Status CreatBiTree(BiTree &T) { char ch; scanf("%d",&ch); if(ch==' ')T==NULL; else{ if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW); T->data=ch; __[3]__; __[4]__; } return OK; } 三:名词解释结点的度:叶子:树的深度:满二叉树: 四:算法设计 1. 一棵n个结点的完全二叉树存放在二叉树的顺序存储结构中,试编写非递归算法对该树进行先序遍历 2. 已知一棵高度为K具有n个结点的二叉树,按顺序方式存储,编写将树中最大序号叶子结点的祖先结点全部打印输出的算法。 1.若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是()A.9 B.11 C.15 D.不确定 2.一棵完全二叉树上有1001个结点,其中叶子结点的个数是() A. 250 B. 500 C.254 D.505 E.以上答案都不对 3. 设给定权值总数有n 个,其哈夫曼树的结点总数为( ) A.不确定 B.2n C.2n+1 D.2n-1 4.一棵二叉树高度为h,所有结点的度或为0,或为2,则这棵二叉树最少有( )结点A.2h B.2h-1 C.2h+1 D.h+1 5.已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为()。A.CBEFDA B. FEDCBA C. CBEDFA D.不定 二、判断题(在各题后填写“√”或“×”) 1. 完全二叉树一定存在度为1的结点。( ) 2. 一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。( ) 3.中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。 ( ) 4.完全二叉树中,若一个结点没有左孩子,则它必是树叶。( ) 5. 给定一棵树,可以找到唯一的一棵二叉树与之对应。( ) 三、填空题1.在二叉树中,指针p所指结点为叶子结点的条件是___ ___。2.高度为8的完全二叉树至少有______个叶子结点。 3.具有n个结点的二叉树中,一共有________个指针域,其中只有________个用来指向结点的左右孩子,其余的________个指针域为NULL。 4.树的主要遍历方法有________、________、________等三种。 5.如果结点A有 3个兄弟,而且B是A的双亲,则B的度是______。 6.若以{4,5,6,7,8}作为叶子结点的权值构造哈夫曼树,则其带权路径长度是______。 1.树是一种________结构。在树结构中,________结点没有直接前趋。 2.一棵树上的任何结点(不包括根本身)称为根的________。若B是A的子孙,则称A 是B的________。 3.二叉树有______二叉树、______的二叉树、只有______的二叉树、只有______的二叉树、同时有______的二叉树五种基本形态。 4.树在计算机内的表示方式有_______、_______、_________。 5.对任何二叉树,若度为2的节点数为n2,则叶子数n0=______。 6. 高度为k(k>=1)的二叉树至多有______个结点。 7. 二叉树第i(i>=1)层上至多有______个结点。 8. 满二叉树上各层的结点数已达到了二叉树可以容纳的______。满二叉树也是______二叉树,但反之不然。 9.具有n个结点的完全二叉树的高度为______。 10. 如果将一棵有n个结点的完全二叉树按层编号,则对任一编号为i(1<=i<=n)的结点X有: (1)若i=1,则结点X是______;若i〉1,则X的双亲PARENT(X)的编号为______。( (2) 若2i>n,则结点X无______且无______;否则,X的左孩子LCHILD(X)的编号为______。(左孩子,右孩子,2i)(3)若2i+1>n,则结点X无______;否则,X的右孩子RCHILD(X)的编号为______。 11. 二叉树通常有______存储结构和______存储结构两类存储结构。 12.具有n个结点的二叉链表中,一共有________个指针域,其中只有________个用来指向结点的左右孩子,其余的________个指针域为NULL。 13. 一棵二叉树由根、左子树和右子树三部分组成,因此对二叉树的遍历也可相应地分解成________、________、________三项“子任务”。 14. 若以N、L、R分别表示二叉树的三项子任务,限定“先左后右”,这样可能的次序有:________、_____、_____三种,按这三种次序进行的遍历分别称为_____、_____、________。 15. 在二叉链表中,指针p所指结点为叶结点的条件是______。 1.以下说法错误的是( ) A. 树型结构的特点是一个结点可以有多个直接前趋 B. 线性结构中的一个结点至多只有一个直接后继 C. 树型结构可以表达(组织)更复杂的数据D.树型是一种"层次"结构 2.以下说法错误的是( ) A.二叉树可以是空集B.二叉树的任一结点都有两棵子树C.二叉树的任一结点最多有两棵子树D.二叉树中任一结点的两棵子树有次序之分 3.以下说法错误的是( ) A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达B. 在三叉链表上,二叉树的求结点双亲运算很容易实现C. 在二叉链表上,求结点的左、右孩子等很容易实现D. 在二叉链表上,求结点的双亲运算很容易实现 4.高度为6的二叉树最多有( )个结点A.64 B. 63 C. 32 D. 31 5. 将含有83个结点的完全二叉树从根结点开始编号,根为1号,后面按从上到下、从左到右的顺序对结点编号,那么编号为41的双亲结点编号为( ) A. 42 B. 40 C. 21 D. 20 6. 任何一棵二叉树的叶结点在其先根、中根、后根遍历序列中的相对位置( ) A.一定不相同 B. 有时不相同 C. 一定相同 D. 无法确定 7. 下列说法正确的是( ) A.树的先根遍历序列与其对应的二叉树的先根遍历序列相同 B.树的先根遍历序列与其对应的二叉树的后根遍历序列相同 C.树的后根遍历序列与其对应的二叉树的先根遍历序列相同 D.树的后根遍历序列与其对应的二叉树的后根遍历序列相同 8.一棵二叉树满足下列条件:对任意结点,若存在左、右子树,则其值都小于它的左子树上所有结点的值,而大于右子树上所有结点的值。现采用(B )遍历方式就可以得到这棵二叉树所有结点的递增序列。A.先根 B. 中根 C. 后根 D. 层次 9.设森林T中有4棵树,第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后,且根结点的右子树上有()个结点。 A.n1-1 B. n1 C. n1+n2+n3 D. n2+n3+n4 10. 已知某二叉树的后序遍历序列是dabec,中序遍历序列是deabc,则它的前序遍历序列是()A. acbed B. deabc C. decab D. ced 简答及应用题4.1中的二叉树和树回答下列问题 (1)哪个是根结点? (2)哪些是叶结点? (3)哪个是G的双亲? (4)哪些是G的祖先? (5)哪些是G的孩子? (6)哪些是E的子孙? (7)哪些是E的兄弟? 哪些是C的兄弟? (8)结点B和I的层数分别是多少? (9)树的深度是多少? (10)以结点G为根的子树的深度是多少? (11)树的度数是多少? 五,算法设计 1、以二叉链表为存储结构,分别实现二叉树的下列运算: (1)PARENT (BT,X);(2) CREATE ( X, LBT.RBT);(3)DELLEFT(BT,X) 以二叉链表作存储结构,试编写求二叉树深度的算法 1.设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1 则T中的叶子 数为()A.5 B.6 C.7 D.8 2.在下述结论中,正确的是() ①只有一个结点的二叉树的度为0; ②二叉树的度为2;③二叉树的左右子树可任意交换; ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A.①②③ B.②③④ C.②④D.①④ 3.设森林F对应的二叉树为B,它有m个结点,B的根为p,p的右子树结点个数为n,森 4.F中第一棵树的结点个数是() A.m-n B.m-n-1 C.n+1 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. 二叉树是指度为2的____________________树。一棵结点数为N的二叉树,其所有结点的度的总和是_____________。 8. 对一棵二叉搜索树进行中序遍历时,得到的结点序列是一个______________。对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的__________________。 9. 对于一棵具有n个结点的二叉树,用二叉链表存储时,其指针总数为_____________个,其中_______________个用于指向孩子,_________________个指针是空闲的。 10. 若对一棵完全二叉树从0开始进行结点的编号,并按此编号把它顺序存储到一维数组A 中,即编号为0的结点存储到A[0]中。其余类推,则A[ i ]元素的左孩子元素为________,右孩子元素为_______________,双亲元素为____________。 三算法填空 二叉搜索树的查找——递归算法: bool Find(BTreeNode* BST,ElemType& item) { if (BST==NULL) return false; //查找失败 else { if (item==BST->data){ item=BST->data;//查找成功 return ___________;} else if(item return Find(______________,item); else return Find(_______________,item); }//if } 已知一颗二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历结果为()A .CBEFDA B .FEDCBA C .CBEDFA D .不定 在下列情况下,可称为二叉树的是() A每个结点至多有两颗子树的树B哈夫曼树 C每个结点至多有两颗子树的有序树D每个结点只有一颗右子树 在二叉树结点的先序序列,中序序列和后序序列中,所有叶子结点的先后顺序()A都不相同B完全相同C先序和中序相同,与后序不同 D中序和后序相同,与先序不同 在完全二叉树中,若一个结点是叶结点,则它没() A左子结点B右子结点C左右子结点D左右子结点和兄弟结点 引入二叉树线索树的目的是() A加快查找结点的前驱或后继的速度 B为了能在二叉树中方便的进行插入与删除 C为了能方便的找到双亲D使二叉树的遍历结果唯一 二.填空题 1. 在二叉树中,指针p所指结点为叶子结点的条件是__________。 2. 深度为k的完全二叉树至少有_______个结点,至多有________个结点。 3. 高度为8的完全二叉树至少有_______个叶子结点。 4. 树的主要遍历方法有______、_______、________三种。 5. 如果结点A有3个兄弟,且B是A的双亲,则B的度是_______. 三.简答题。1.对于二叉树的链接实现,完成非递归的中序遍历过程。 2.分别写出下图所示二叉树的先根、中根和后根序列。 名词解释 1.树 2.结点的度 3.树的深度 4.二叉树 二.找出所有满足下列条件的二叉树 它们在先序遍历和中序遍历时,得到的结点访问序列相同; 它们在后序遍历和中序遍历时,得到的结点访问序列相同; 它们在后序遍历和先序遍历时,得到的结点访问序列相同; 三.1.二叉树是度为2的有序树() 2.完全二叉树一定存在度为1的结点() 3.深度为K的二叉树中结点总数≤2k-1() 4.由一棵二叉树的先序序列和后序序列可以惟一确定它() 5.完全二叉树中,若一个结点没有左孩子,则它必是树叶() 6.用二叉链表存储n个结点的二叉树时,结点的2n个指针中有n+1个空指针() 7.完全二叉树的存储结构通常采用顺序存储结构() 一棵124个叶结点的完全二叉树,最多有多少个结点。 某二叉树有20个叶子结点,有30个结点仅有一个孩子,则该二叉树的总结点数是多少 一棵二叉树高度为h,所有结点的度或为0,或为2,则这棵二叉树最少有多少结点 已知一棵二叉树的后序遍历序列为EICBGAHDF,同时知道该二叉树的中序遍历序列为CEIFGBADH,试画出该二叉树。 已知一棵二叉树的前序遍历的结果是ABECDFGHIJ,中序遍历的结果是EBCDAFHIGJ,试画出这棵二叉树,对二叉树进行中序线索化,并将该二叉树转换为森林 1. 下列说法中正确的是( ) A.任何一棵二叉树中至少有一个结点的度为2 B.任何一棵二叉树中每个结点的度都为2 C.任何一棵二叉树中的度肯定等于2 D.任何一棵二叉树中的度可以小于2 2. 设森林F中有三棵树,第一,第二,第三棵树的结点个数分别为M1,M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是()。 A.M1 B.M1+M2 C.M3 D.M2+M3 3.设X施树T中的一个非根节点,B是T所对应的二叉树,在B中,X是其双亲的右孩子,下列结论正确的是() A.在树T中,X是其双亲的第一个孩子 B.在树T中,X一定无右边兄弟 C.在树T中,X一定是叶子结点 D 在树T中,X一定有左边兄弟 4.设n,m为一颗二叉树上的两个结点,在中序遍历时,n在m之前的条件是() A. n在m右方 B. n是m祖先 C. n在m左方 D. n是m子孙 5.在一颗二叉树结点的先序序列、中序序列、后序序列中,所有叶子结点的先后顺序() A.都不相同 B.先序和中序相同,而与后序不同 C.完全相同 D.中序和后序相同,而与先序不同 6. 设给定权值总数有n 个,其哈夫曼树的结点总数为() A.不确定B.2n C.2n+1 D.2n-1 7. .已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为()。A.CBEFDA B.FEDCBA C.CBEDFA D.不定 8.一颗满二叉树中共有n个结点,其中有m个叶子结点,深度为h,则() A. n=h +m B. h +m=2n C. m=h-1 D. n=2h-1 9.设森林中有3 棵树,其中第1、第2和第3棵树的结点个数分别为n1,n2,n3,则与森林对应的二叉树中根结点的右子树上的结点个数是()A.n1 B.n1+n2 C.n3 D.n2+n3 10、.n个结点的线索二叉树上含有的线索数为()A.2n B.n-l C.n+l D.n 二、填空题1. 中某结点的子树的个数称为该结点的(),子树的根结点称为该结点的(),该结点称为其子树根结点的()。 2. 棵二叉树的第i(i≥1)层最多有()个结点;一棵有n(n>0)个结点的满二叉树共有()个叶子结点和()个非终端结点。 3.N个结点的二叉树按某种遍历规则对结点从1到N依次递增编号,如果: (1)任一结点的编号等于它的左子树中的最小编号减1,则为()遍历 (2)某结点右子树中最小编号等于左子树中的最大编号加1,则为()遍历 4.由带权为3,9,6,2,5的5个叶子结点构成一颗赫夫曼树,则带权路径长度为() 5.在一颗二叉树中,度为0的结点的个数为n0,度为2的结点的个数为n2,则有n0=() 6.设F施一个森林,B是由F转换得到的二叉树,F中有n个非终端结点,则B中右指针域空的结点有() 7. 若以{4,5,6,7,8}作为叶子结点的权值构造哈夫曼树,则其带权路径长度是____ 8. 一个深度为k的,具有最少结点数的完全二叉树按层次,(同层次从左到右)用自然数依此对结点编号,则编号最小的叶子的序号是___;编号是i的结点所在的层次号是___(根所在的层次号规定为1层)。 9. 如果结点A有3个兄弟,而且B是A的双亲,则B的度是_____。 10.完全二叉树的第7层有8个结点,则此完全二叉树的叶子结点树为(),768个结点的完全二叉树有()叶子结点,19个结点的赫夫曼树有()叶子结点 1.由3个结点所构成的二叉树有种形态。 2. 一棵深度为6的满二叉树有个分支结点和个叶子。 3. 设一棵完全二叉树具有1000个结点,则此完全二叉树有个叶子结点,有个度为2的结点,有个结点只有非空左子树,有个结点只有非空右子树。 4. 二叉树的基本组成部分是:根(N)、左子树(L)和右子树(R)。因而二叉树的遍历次序有六种。最常用的是三种:前序法(即按N L R 次序),后序法(即按次序)和中序法(也称对称序法,即按L N R次序)。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH,中序序列是FEBGCHD,则它的后序序列必是。 5. 用5个权值{3, 2, 4, 5, 1}构造的哈夫曼(Huffman)树的带权路径长度是。 6. 一棵度为2的树与一棵二叉树有何区别? 7. 设如下图所示的二叉树B的存储结构为二叉链表,root为根指 针,结点结构为:(lchild,data,rchild)。其中lchild,rchild分别 为指向左右孩子的指针,data为字符型,root为根指针,试回答 下列问题: 对下列二叉树B,执行下列算法traversal(root),试指出其输出结果;C的结点类型定义如下: struct node {char data; struct node *lchild, rchild; }; C算法如下: void traversal(struct node *root) {if (root) {printf(“%c”, root->data); traversal(root->lchild); printf(“%c”, root->data); 第六章习题 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.画出与下列已知序列对应的树T: 树的先根次序访问序列为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)一个算法应该就是()。 A)程序???B)问题求解步骤得描述 C)要满足五个基本属性??D) A与C (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)下列程序得时间复杂度为() i=0;s=0; while(s 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 《数据结构》题库及答案 一、选择题 1.线性表的顺序存储结构是一种 的存储结构,线性表的链式存储结构是一种 的存储结构。 a. 随机存储; b.顺序存储; c. 索引存取; d. HASH 存取 2.一个栈的入栈序列是a,b,c,d,e ,则栈的不可能的输出序列是 。 a. edcba; b. decba; c. dceab; d.abcde 3.一个队列的入队序列是1,2,3,4,则队列的输出序列是 。 a. 4,3,2,1; b. 1,2,3,4; c. 1,4,3,2; d.3,2,4,1 4.在一个单链表中,已知p 结点是q 结点的直接前驱结点,若在p 和q 之间插入结点s ,则执行的操作是 。 a. s->nxet=p->next; p->next=s; b. p->next=s->next; s->next=p; c. q->next=s; s->next=p; d. p->next=s; s->next=q; 5.设有两个串p,q ,求q 在p 中首次出现的位置的运算称作 。 a.联接 b.模式匹配 c.求子串 d.求串长 6.二维数组M 的成员是6个字符(每个字符占一个存储单元)组成的串,行下标i 的范围从0到8,列下标j 的范围从1到10,则存放M 至少需要 个字节。 a. 90 b.180 c.240 d.540 7.在线索二叉树中,结点p 没有左子树的充要条件是 。 a. p->lch==NULL b. p->ltag==1 c. p->ltag==1且p->lch=NULL d. 以上都不对 8.在栈操作中,输入序列为(A ,B ,C ,D ),不可能得到的输出序列为:______ A 、(A , B , C , D ) B 、(D ,C ,B ,A ) C 、(A ,C ,D ,B ) D 、(C ,A ,B ,D ) 9.已知某二叉树的后序序列是dabec ,中序序列是debac ,则它的先序序列是 。 A 、acbed B 、decab C 、deabc D 、cedba 10.设矩阵A 是一个对称矩阵,为了节省存储空间,将其下三角部分(见下图)按行序存放在一维数组B[1..n(n-1)/2]中,对任一上三角部分元素)(j i a ij ,在一维数组B 的存放位置是 。 2017年数据结构期末考试题及答案 一、选择题(共计50分,每题2分,共25题) 1 ?在数据结构中,从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中,与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时,通常不仅要存储各数据元素的值,而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时,一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中,正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出 8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性,这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同,而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点,则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间,插入和删除不需要移动元素的线性表,其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点(由p所指向)满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点 图 1. 填空题 ⑴ 设无向图G中顶点数为n,则图G至少有()条边,至多有()条边;若G为有向图,则至少有()条边,至多有()条边。 【解答】0,n(n-1)/2,0,n(n-1) 【分析】图的顶点集合是有穷非空的,而边集可以是空集;边数达到最多的图称为完全图,在完全图中,任意两个顶点之间都存在边。 ⑵ 任何连通图的连通分量只有一个,即是()。 【解答】其自身 ⑶ 图的存储结构主要有两种,分别是()和()。 【解答】邻接矩阵,邻接表 【分析】这是最常用的两种存储结构,此外,还有十字链表、邻接多重表、边集数组等。 ⑷ 已知无向图G的顶点数为n,边数为e,其邻接表表示的空间复杂度为()。 【解答】O(n+e) 【分析】在无向图的邻接表中,顶点表有n个结点,边表有2e个结点,共有n+2e个结点,其空间复杂度为O(n+2e)=O(n+e)。 ⑸ 已知一个有向图的邻接矩阵表示,计算第j个顶点的入度的方法是()。 【解答】求第j列的所有元素之和 ⑹ 有向图G用邻接矩阵A[n][n]存储,其第i行的所有元素之和等于顶点i的()。 【解答】出度 ⑺ 图的深度优先遍历类似于树的()遍历,它所用到的数据结构是();图的广度优先遍历类似于树的()遍历,它所用到的数据结构是()。 【解答】前序,栈,层序,队列 ⑻ 对于含有n个顶点e条边的连通图,利用Prim算法求最小生成树的时间复杂度为(),利用Kruskal 算法求最小生成树的时间复杂度为()。 【解答】O(n2),O(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条边,则。 单选题(每题2分,共20分) 1. 1. 对一个算法的评价,不包括如下(B )方面的内容。 A .健壮性和可读性 B .并行性 C .正确性 D .时空复杂度 2.2. 在带有头结点的单链表HL 中,要向表头插入一个由指针 p 指向 的结点,则执行(A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; 都具有相同的(A )。 A.行号 B .列号 C .元素值 D .非零元素个数 9. 快速排序在最坏情况下的时间复杂度为(D )。 A. O(log 2n) B . O(nlog 2n) C . 0(n) D 10.10. 从二叉搜索树中查找一个元素时,其时间复杂度大致 为 A. O(n) B. O(1) C. O(log 2 n) D. O(n 二、 运算题(每题6分,共24分) 1. 1. 数据结构是指数据及其相互之间的 _________________ 。当结点之 间存在M 对N (M N)的联系时,称这种结构为 __________________________ 。 2. 2. 队列的插入操作是在队列的_ _尾 ________ 行,删除操作是在队 列的 ____ 首 _____ 行。 3. 3. 当用长度为N 的数组顺序存储一个栈时,假定用top==N 表示栈 C. p->next=HL; p=HL; 3. 3. A. C. D. HL=p; p-> next=HL; 对线性表,在下列哪种情况下应当采用链表表示? 经常需要随机地存取元素 B. 表中元素需要占据一片连续的存储空间 一个栈的输入序列为1 2 3, 4. 4. 列的是(C ) A. 2 3 1 C. 3 1 2 AOV 网 是一种(D ) 有向 图 B .无向图 (B ) 经常需要进行插入和删除操作 D.表中元素的个数不变 则下列序列中不可能是栈的输出序 B. 3 2 1 5. 5. 6. .无向无环图 D .有向无环图 采用 开放定址法处理散列表的冲突时,其平均查找长度( B. 高于链接法处理冲突 D .高于二分查找 7. 8. 6. A.低于链接法处理冲突 .与链接法处理冲突相同 7. 参数。 A.值 8. B)。 若需要利用形参直接访问实参时,应将形参变量说明为( B .函数 C .指针 D .引用 在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点 9. .0(n 2) (C )。 2 ) 数据结构习题(,,章) ————————————————————————————————作者:————————————————————————————————日期: 第四章串 一.选择题 1.若串S='software',其子串的数目是() A.8 B.37 C.36 D.9 2.设有两个串p和q,求q在p中首次出现的位置的运算称作() A.连接B.模式匹配C.求串长D.求子串 3.设字符串S1=“ABCDEFG”,S2=“PQRST”,则运算: S=CONCAT(SUBSTR(S1,2,LEN(S2));SUBSTR(S1,LEN(S2),2));后的串值为() A.A BCDEF B.BCDEFG C.BCDPQRST D. BCDEFEF 4.下面的说法中,只有()是正确的 A.串是一种特殊的线性表B.串的长度必须大于零 C.串中元素只能是字母D.空串就是空白串 5.两个字符串相等的条件是() A.两串的长度相等 B.两串包含的字符相同 C.两串的长度相等,并且两串包含的字符相同 D.两串的长度相等,并且对应位置上的字符相同 二.填空题 1.串“ababcbaababd”的next函数值为,nextval函数值为。2.子串的长度为。 第五章数组和广义表 一.选择题 1.设有数组A[i,j],数组的每个元素长度为3字节,i的值为1 到8 ,j的值为1 到10,数组从内存首地址BA开始顺序存放,当用以列为主存放时,元素A[5,8]的存储首地址为( ) A. BA+141 B. BA+180 C. BA+222 D. BA+225 2.假设以行序为主序存储二维数组A=array[1..100,1..100],设每个数据元素占2个存储单元,基地址为10,则LOC[5,5]=() A. 808 B. 818 C. 1010 D. 1020 3.对稀疏矩阵进行压缩存储目的是() A.便于进行矩阵运算B.便于输入和输出C.节省存储空间D.降低运算的时间复杂度 4.假设以三元组表表示稀疏矩阵,则与如图所示三元组表对应的4×5的稀疏矩阵是(注:矩阵的行列下标均从1开始)() 数据结构-习题-第六章-树和二叉树 E F D G A B / + + * - C * 第六章 树和二叉树 一、选择题 1.已知一算术表达式的中缀形式为 A+B*C-D/E ,后缀形式为ABC*+DE/-,其前缀形式为( ) A .-A+B*C/DE B. -A+B*CD/E C .-+*ABC/DE D. -+A*BC/DE 【北京航空航天大学 1999 一、3 (2分)】 2.算术表达式a+b*(c+d/e )转为后缀表达式 后为( )【中山大学 1999 一、5】 A .ab+cde/* B .abcde/+*+ C .abcde/*++ D .abcde*/++ 3. 设有一表示算术表达式的二叉树(见下图), 它所表示的算术表达式是( ) 【南京理工大学1999 一、20(2分)】 A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+(F-G )) D. A*B+C/D*E+F-G 4. 设树T 的度为4,其中度为1,2,3和4的 结点个数分别为4,2,1,1 则T 中的叶子数 为( ) A .5 B .6 C .7 D.8 【南京理工大学 2000 一、8 (1.5分)】5. 在下述结论中,正确的是()【南京理工大学 1999 一、4 (1分)】 ①只有一个结点的二叉树的度为0; ②二叉树的度为2;③二叉树的左右子树可任意交换; ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A.①②③ B.②③④ C.② ④ D.①④ 6. 设森林F对应的二叉树为B,它有m个结点,B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是() A.m-n B.m-n-1 C.n+1 D.条件不足,无法确定【南京理工大学2000 一、17(1.5分)】 7. 树是结点的有限集合,它( (1))根结点,记为T。其余结点分成为m(m>0)个((2))的集合T1,T2,…,Tm,每个集合又都是树,此时结点T称为Ti的父结点,Ti称为T的子结点(1≤i≤m)。一个结点的子结点个数称为该结 一、单项选择题 1 某算法的时间复杂度是O(n 2 ) ,表明该算法()。 A 问题规模是n2 B 问题规模与n2成正比 C 执行时间等于n2 D 执行时间与n2成正比 2、关于数据结构的描述,不正确的是()。 A数据结构相同,对应的存储结构也相同。 B数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。 C数据结构操作的实现与存储结构有关。 D定义逻辑结构时可不考虑存储结构。 3、按排序策略分来,起泡排序属于()。 A插入排序B选择排序C交换排序D归并排序 4、利用双向链表作线性表的存储结构的优点是()。 A便于进行插入和删除的操作 B 提高按关系查找数据元素的速度 C节省空间D便于销毁结构释放空间 5、一个队列的进队顺序为1,2,3,4,则该队列可能的输出序列是()。 A 1,2,3,4 B 1,3,2,4 C 1,4,2,3 D 4,3,2,1 6、 Dijkstra算法是按()方法求出图中从某顶点到其余顶点最短路径的。 A按长度递减的顺序求出图的某顶点到其余顶点的最短路径 B按长度递增的顺序求出图的某顶点到其余顶点的最短路径 C通过深度优先遍历求出图中从某顶点到其余顶点的所有路径 D通过广度优先遍历求出图的某顶点到其余顶点的最短路径 7、字符串可定义为n( n≥ 0)个字符的有限()。其中,n是字符串的长度,表明字符串中字符的个数。 A集合B数列C序列D聚合 8、在二维数组A[9][10]中,每个数组元素占用 3 个存储单元,从首地址SA 开始按行连续存放。在这种情况下,元素A[8][5]的起始地址为()。 A SA+141 B SA+144 C SA+222 D SA+255 9、已知广义表为L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h)),则它的长度是()。 A2B3C4D5 10.对于具有n(n>1)个顶点的强连通图,其有向边条数至少有_____。 A. n+1 B. n C. n-1 D. n-2 11.一个递归算法必须包括 __________ 。 A. 递归部分 B . 结束条件和递归部分 C. 迭代部分 D. 结束条件和迭代部分 12.从逻辑上看可以把数据结构分为__________两大类。 A.动态结构、静态结构B.顺序结构、链式结构 C.线性结构、非线性结构D.初等结构、构造型结构 13、若在长度为n 的顺序表的表尾插入一个新元素的渐进时间复杂度为()。 A O(n) B O(1) C O(n 2) D O(log 2n) 14.采用顺序搜素方式搜索长度为 n 的线性表时,在等概率情况下,搜索成功时的平均搜索 长度为 __________。 A. n B. n/2 C . (n+1)/2 D. (n-1)/2 15、非空的循环单链表first的链尾结点(由p 所指向)满足()。 A p->link==NULL; B P==NULL; 2011-2012学年第一学期期末考查 《数据结构》试卷 (答案一律写在答题纸上,在本试卷上做答无效) 一、选择(每题1分,共10分) 1.长度为n的线性表采用顺序存储结构,一个在其第i个位置插入新元素的算法时间复杂度为(D) A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6,5,4,3,2,1的顺序入栈,下列哪一个是合法的出栈序列?(D) A.543612 B.453126 C.346512 D.234156 3.设树的度为4,其中度为1、2、3、4的结点个数分别是4、2、1、2,则树中叶子个数为(B ) A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点,B的右子树结点个数为n,森林F中第一棵树的结点个数是( B ) A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是(B) A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。(A) A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有(B )个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树,与用其他三个序列构造的结果不同的是(B) A.(100,80,90,60,120,110,130) B.(100, 120, 110,130,80, 60,90) C.(100,60,80,90,120,110,130) D.(100,80, 60,90, 120, 130,110) 9.对一组数据(84,47,25,15,21)排序,数据的排列次序在排序过程中变化如下:(1)84 47 25 15 21 (2)15 47 25 84 21 (3)15 21 25 84 47(4)15 21 25 47 84则采用的排序方法是(B ) A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时,要求线性表必须(D) A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 第六章树和二叉树试题 一、单项选择题 1.树中所有结点的度等于所有结点数加()。 A. 0 B. 1 C. -1 D. 2 2.在一棵树中,()没有前驱结点。 A. 分支结点 B. 叶结点 C. 根结点 D. 空结点 3.在一棵二叉树的二叉链表中,空指针域数等于非空指针域数加()。 A. 2 B. 1 C. 0 D. -1 4.在一棵具有n个结点的二叉树中,所有结点的空子树个数等于()。 A. n B. n-1 C. n+1 D. 2*n 5.在一棵具有n个结点的二叉树的第i层上(假定根结点为第0层,i大于等 于0而小于等于树的高度),最多具有()个结点。 A. 2i B. 2i+1 C. 2i-1 D. 2n 6.在一棵高度为h(假定根结点的层号为0)的完全二叉树中,所含结点个数不 小于()。 A. 2h-1 B. 2h+1 C. 2h-1 D. 2h 7.在一棵具有35个结点的完全二叉树中,该树的高度为()。假定空树 的高度为-1。 A. 5 B. 6 C. 7 D. 8 8.在一棵具有n个结点的完全二叉树中,分支结点的最大编号为()。假 定树根结点的编号为0。 A. ?(n-1)/2? B. ?n/2? C. ?n/2? D. ?n/2? -1 9.在一棵完全二叉树中,若编号为i的结点存在左孩子,则左子女结点的编号 为()。假定根结点的编号为0 A. 2i B. 2i-1 C. 2i+1 D. 2i+2 10.在一棵完全二叉树中,假定根结点的编号为0,则对于编号为i(i>0)的结 点,其双亲结点的编号为()。 A. ?(i+1)/2? B. ?(i-1)/2? C. ?i/2? D. ?i/2? -1 11.在一棵树的左子女-右兄弟表示法中,一个结点的右孩子是该结点的() 结点。 A. 兄弟 B. 子女 C. 祖先 D. 子孙 12.在一棵树的静态双亲表示中,每个存储结点包含()个域。 A. 1 B. 2 C. 3 D. 4 13.已知一棵二叉树的广义表表示为a (b (c), d (e ( , g (h) ), f ) ),则 该二叉树的高度为()。假定根结点的高度为0。 A. 3 B. 4 C. 5 D. 6 习题六树和二叉树 一、单项选择题 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层上最多含有结点数为() A.2I B. 2I-1-1 C. 2I-1 D.2I -1 10.一棵二叉树高度为h,所有结点的度或为0,或为2,则这棵二叉树最少有( )结点A.2h B.2h-1 C.2h+1 D.h+1 11. 利用二叉链表存储树,则根结点的右指针是()。 A.指向最左孩子 B.指向最右孩子 C.空 D.非空 14.在二叉树结点的先序序列,中序序列和后序序列中,所有叶子结点的先后顺序()A.都不相同 B.完全相同 C.先序和中序相同,而与后序不同 D.中序和后序相同,而与先序不同 15.在完全二叉树中,若一个结点是叶结点,则它没()。 A.左子结点 B.右子结点 C.左子结点和右子结点 D.左子结点,右子结点和兄弟结点 16.在下列情况中,可称为二叉树的是() 2017《数据结构》期末考试试题及答案 《数据结构》期末考试试题及答案 1 ................................................................. 2..试题 1 答案............................................................ 7..《数据结构》期末考试试题及答案 2 ................................................................. 9..试题 2 答案........................................................................ 1.. 4. 《数据结构》期末考试试题及答案 3 ............................................................... 1..6试题 3 答案........................................................................ 2.. 1. 数据结构》期末考试试题及答案 1 单选题(每题 2 分,共 20 分) 1. 栈和队列的共同特点是 ( )。 A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 2. 用链接方式存储的队列,在进行插入运算时 ( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D .头、尾指针可能都要修改 3. 以下数据结构中哪一个是非线性结构? ( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4. 设有一个二维数组A[m][n],假设A[0][0]存放位置在644(io ), A[2][2]存放 若有18个元素的有序表存放在一维数组 A[19]中,第一个元素放A[1]中, 现进行二分查找,则查找 A [3]的比较序列的下标依次为( A. 1 , 2, 3 B. 9, 5, 2, 3 C. 9, 5, 3 D. 9, 4, 2, 3 8. 对n 个记录的文件进行快速排序,所需要的辅助存储空间大致为 A. O (1) B. O (n ) C. O ( 1 og 2n ) D. O (n2) 9. 对于线性表( 7, 34, 55, 25, 64, 46, 20, 10)进行散列存储时,若选 用 H (K )=K %9 作为散列函数,则散列地址为 1 的元素有( )个, 位置在 676(10),每个元素占一个空间, 表示用 10 进制表示。 问 A[3][3] (10)存放在什么位置?脚注 (10) 5. A .688 B .678 C . 692 D . 696 树最适合用来表示 ( )。 A.有序数据元素 B.无序数据元素 6. C.元素之间具有分支层次关系的数据 D .元素之间无联系的数据 二叉树的第 k 层的结点数最多为 ( ). A .2-1 B.2K+1 C.2K-1 D. 2k-1 7. void PreOrder_Nonrecursive(Bitree T)//先序遍历二叉树的非递归算法 { InitStack(S); Push(S,T); //根指针进栈 while(!StackEmpty(S)) { while(Gettop(S,p)&&p) { visit(p->data); push(S,p->lchild); } //向左走到尽头 pop(S,p); if(!StackEmpty(S)) { pop(S,p); push(S,p->rchild); //向右一步 } }//while }//PreOrder_Nonrecursive 一、下面是有关二叉树的叙述,请判断正误 1.二叉树中每个结点的两棵子树的高度差等于1。() 2.二叉树中所有结点,如果不存在非空左子树,则不存在非空右子树。() 3.对于一棵非空二叉树,它的根结点作为第一层,则它的第i层上最多能有2i —1个结点。() 4.用二叉链表法(link-rlink)存储包含n个结点的二叉树,结点的2n个指针区域中有n+1个为空指针。() 5.具有12个结点的完全二叉树有5个度为2的结点。() 最快方法:用叶子数=[n/2]=6,再求n2=n0-1=5 6.二叉树是度为2的有序树() 7.完全二叉树一定存在度为1的结点() 8.深度为K的二叉树中结点总数≤2k-1() 9.由一棵二叉树的先序序列和后序序列可以惟一确定它() 10.完全二叉树中,若一个结点没有左孩子,则它必是树叶() 11.用二叉链表存储n个结点的二叉树时,结点的2n个指针中有n+1个空指针()12.完全二叉树的存储结构通常采用顺序存储结构() 13.哈夫曼树是带权路径长度最短的树,路径上权值较大的结点离根较近()14.在中序线索二叉树中,每一非空的线索均指向其祖先结点() 二、填空 1. 一棵具有257个结点的完全二叉树,它的深度为。 2. 用5个权值{3, 2, 4, 5, 1}构造的哈夫曼(Huffman)树的带权路径长度是 3.深度为H 的完全二叉树至少有_____________个结点;至多有_____________个结点4.已知二叉树有50个叶子结点,则该二叉树的总结点数至少是_____________。 5. n(n大于1)个结点的各棵树中,其深度最小的那棵树的深度是_____________。它共有_____________个叶子结点和_____________个非叶子结点,其中深度最大的那棵树的深度是_____________,它共有_____________个叶子结点和_____________个非叶子结点。 三、单项选择题 1.有关二叉树下列说法正确的是() A)二叉树的度为2 B)一棵二叉树的度可以小于2 C)二叉树中至少有一个结点的度为2 D)二叉树中任何一个结点的度都为2 2.二叉树的第I层上最多含有结点数为() A)2I B)2I-1-1 C)2I-1D)2I-1 3.具有10个叶结点的二叉树中有()个度为2的结点 A)8 B)9 C)10 D)11 4.在下述结论中,正确的是() ①只有一个结点的二叉树的度为0; ②二叉树的度为2; ③二叉树的左右子树可任意交换; ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A)①②③B)②③④C)②④D)①④ 5.由3 个结点可以构造出多少种不同的二叉树?() A)2 B)3 C)4 D)5 6.引入二叉线索树的目的是() 一、单选题(每题 2 分,共20分) 1. 1.对一个算法的评价,不包括如下(B )方面的内容。 A.健壮性和可读性B.并行性C.正确性D.时空复杂度 2. 2.在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结 点,则执行(A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表,在下列哪种情况下应当采用链表表示?( B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3,则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种(D )。 A.有向图B.无向图C.无向无环图D.有向无环图 6. 6.采用开放定址法处理散列表的冲突时,其平均查找长度(B)。 A.低于链接法处理冲突 B. 高于链接法处理冲突 C.与链接法处理冲突相同D.高于二分查找 7.7.若需要利用形参直接访问实参时,应将形参变量说明为(D )参数。 A.值B.函数C.指针D.引用 8.8.在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点都具 有相同的( A )。 A.行号B.列号C.元素值D.非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为(D )。 A.O(log2n) B.O(nlog2n) C.0(n) D.0(n2) 10.10.从二叉搜索树中查找一个元素时,其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、运算题(每题 6 分,共24分) 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N(M:N)的联系时,称这种结构为_____________________。 2. 2.队列的插入操作是在队列的_ _尾______进行,删除操作是在队列的____ 首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时,假定用top==N表示栈空,则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表,在表头插入元素的时间复杂度 为_________,在表尾插入元素的时间复杂度为____________。 贵州大学理学院数学系信息与计算科学专业 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 一、单项选择题 1.对于一个算法,当输入非法数据时,也要能作出相应的处理,这种要求称为()。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2.设S为C语言的语句,计算机执行下面算法时,算法的时间复杂度为()。 for(i=n-1;i>=0;i--) for(j=0;jnext; p->next= Q.rear->next; (D)、p=Q->next; Q->next=p->next; 9. Huffman树的带权路径长度WPL等于() (A)、除根结点之外的所有结点权值之和(B)、所有结点权值之和 (C)、各叶子结点的带权路径长度之和(D)、根结点的值 10.线索二叉链表是利用()域存储后继结点的地址。 (A)、lchild (B)、data (C)、rchild (D)、root 二、填空题数据结构第6章习题集
数据结构课后习题与解析第六章
数据结构试题库答案
数据结构第六章习题课
《数据结构》题库及答案
2017年数据结构期末考试题及答案A
数据结构-第六章-图-练习题及答案详细解析(精华版)
数据结构试题及答案(10套最新)
数据结构习题(,,章)
数据结构-习题-第六章-树
算法与数据结构题库与答案
《数据结构》期末考试题及答案
《数据结构》习题汇编06第六章树和二叉树试题
第六章树和二叉树习题数据结构
2017数据结构期末考试试题及答案
数据结构第6章树练习
数据结构试题及答案(10套最新)
数据结构期末考试试题及答案