数据结构复习资料

第二章 线性表二、填空题1.为了便于讨论，有时将含n(n=0)个结点的线性结构表示成(a1，a2,an)，其中每个ai代表一个结点。a1称为起始结点，an称为终端结点，i称为ai在线性表中的位置或序号。对任意一对相邻结点ai、ai1(1=i=1)个内存单元，其中，b是顺序表的第一个存储结点的第一个单元的内存位置，那么，第i个结点ai的存储位置为b+(i-1)Xk。10.以下为顺序表的插入运算，分析算法，请在_处填上正确的语句。Void insert_sqlist(sqlist L，datatype x，int i)/*将X插入到顺序表L的第i-1个位置*/ if( L.last = maxsize) error(“表满”)；if(iL.last+1)error(“非法位置”);for(j=L.last;j=i;j-)L.dataj=l.dataj-1;L.datai-1=x;L.last=L.last+1;11.对于顺序表的插入算法insert_sqlist来说，若以结点移动为标准操作，则插入算法的最坏时间复杂性为_n_，量级是_O(n)_。插入算法的平均时间复杂性为n/2，平均时间复杂性量级是O(n)。12.以下为顺序表的删除运算，分析算法，请在_处填上正确的语句。 void delete_sqlist(sqlist L,int i) /*删除顺序表L中的第i-1个位置上的结点*/if(iL.last)error(“非法位置”)； for(j=i+1;j=L.last;j+)_L.dataj-2=L.dataj-1_; L.last=L.last-1;13.对于顺序表的删除算法delete_sqlist来说，若以结点移动为标准操作，最坏情况时间复杂性及其量级分别是_n-1_和_O(n)_,其平均时间复杂性及其量级分别为_(n-1)/2_和_O(n)_。14.以下为顺序表的定位运算，分析算法，请在_处填上正确的语句。int locate_sqlist(sqlist L,datatype X) /*在顺序表L中查找第一值等于X的结点。若找到回传该结点序号；否则回传0*/_; while(iL.last)&(L.datai-1!=X)i+; if(_i=1 inext=NULL; return(t);24.以下为求单链表表长的运算，分析算法，请在 _处填上正确的语句。 int length_lklist(lklist head) /*求表head的长度*/ p=head;j=0;while(p-next!=NULL) p=p-next; j+;return(j); /*回传表长*/25.以下为单链表按序号查找的运算，分析算法，请在_处填上正确的语句。 pointer find_lklist(lklist head,int i) p=head;j=0; while(p-next!=NULL)&(jnext; j+; if(i=j) return(p); else return(NULL);26.以下为单链表的定位运算，分析算法，请在_处填上正确的语句。 int locate_lklist(lklist head,datatype x) /*求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0*/ p=head;j=0;while(p-next!=NULL)&(p-data!=x)p=p-next;j+;if (p-data=x) return(j);else return(0);27.以下为单链表的删除运算，分析算法，请在_处填上正确的语句。 void delete_lklist(lklist head,int i) p=find_lklist(head,i-1); if(p!=NULL)&(p-next!=NULL) q=p-next; p-next=p-next; free(q); else error(“不存在第i个结点”)28.以下为单链表的插入运算，分析算法，请在_处填上正确的语句。 void insert_lklist(lklist head,datatype x,int i) /*在表head的第i个位置上插入一个以x为值的新结点*/ p=find_lklist(head,i-1);if(p=NULL)error(“不存在第i个位置”)；else s=malloc(size);s-data=x; s-next=p-next; p-next=s; 29.以下为单链表的建表算法，分析算法，请在_处填上正确的语句。 lklist create_lklist1() /*通过调用initiate_lklist和insert_lklist算法实现的建表算法。假定$是结束标志*/ ininiate_lklist(head);i=1;scanf(“%f”,&x);while(x!=$) insert_lklist(head,x,i); i+; scanf(“%f”,&x);return(head); 该建表算法的时间复杂性约等于n(n-1)/2，其量级为O(n2)。30.以下为单链表的建表算法，分析算法，请在_处填上正确的语句。 lklist create_lklist2() /*直接实现的建表算法。*/ head=malloc(size); p=head; scanf(“%f”,&x); while(x!=$) q=malloc(size); q-data=x; p-next=q; p=q; scanf(“%f”,&x); p-next=NULL; return(head); 此算法的量级为O(n)。31除单链表之外，线性表的链式存储结构还有单项循环链表和双向循环链表等。32循环链表与单链表的区别仅仅在于其尾结点的链域值不是NULL，而是一个指向头结点的指针。33在单链表中若在每个结点中增加一个指针域,所含指针指向前驱结点，这样构成的链表中有两个方向不同的链，称为双链表。34C语言规定，字符串常量按字符数组处理，它的值在程序的执行过程中是不能改变的。而串变量与其他变量不一样，不能由赋值语句对其赋值。35含零个字符的串称为空串，用表示。其他串称为非空串。任何串中所含字符的个数称为该串的长度。36当且仅当两个串的长度相等并且各个对应位置上的字符都相同_时，这两个串相等。一个串中任意个连续字符组成的序列称为该串的子串，该串称为它所有子串的主串。37串的顺序存储有两种方法：一种是每个单元只存一个字符，称为非紧缩格式，另一种是每个单元存放多个字符，称为紧缩格式。38通常将链串中每个存储结点所存储的字符个数称为结点大小。当结点大小大于1时，链串的最后一个结点的各个数据域不一定总能全被字符占满，此时，应在这些未用的数据域里补上不属于字符集的特殊符号。三、单向选择题 1对于线性表基本运算，以下结果是正确的是 ( 2 ) 初始化INITIATE(L)，引用型运算，其作用是建立一个空表L= . 求表长LENGTH(L)，引用型运算，其结果是线性表L的长度 读表元GET(L,i), 引用型运算。若1=idata是一个数据元素，p-next的值是一个指针11.单链表的一个存储结点包含（4） 数据域或指针域 指针域或链域 指针域和链域 数据域和链域12.对于单链表表示法，以下说法错误的是（3） 数据域用于存储线性表的一个数据元素 指针域或链域用于存放一个指向本结点所含数据元素的直接后继所在结点的指针 所有数据通过指针的链接而组织成单链表 NULL称为空指针，它不指向任何结点，只起标志作用13.对于单链表表示法，以下说法错误的是（5） 指向链表的第一个结点的指针，称为头指针 单链表的每一个结点都被一个指针所指 任何结点只能通过指向它的指针才能引用终端结点的指针域就为NULL尾指针变量具标识单链表的作用，故常用尾指针变量来命名单链表14有时为了叙述方便，可以对一些概念进行简称，以下说法错误的是 （ 4 ）将“指针型变量”简称为“指针”将“头指针变量”称为“头指针”将“修改某指针型变量的值”称为“修改某指针”将“p中指针所指结点”称为“P值”15设指针P指向双链表的某一结点，则双链表结构的对称性可用（ 3 ）式来刻画 p-prior-next-=p-next-next p-prior-prior-=p-next-prior p-prior-next-=p-next-prior p-next-next=p-prior-prior16.以下说法错误的是 （ 1 ） 对循环链表来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表对单链表来说，只有从头结点开始才能扫描表中全部结点双链表的特点是找结点的前趋和后继都很容易对双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。17在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置分别是 （ 2 ）real和rear-next-nextrear-next 和realrear-next-next和rearrear和rear-next18.以下说错误的是 ( 3 ) 对于线性表来说，定位运算在顺序表和单链表上的量级均为O（n）读表元运算在顺序表上只需常数时间O（1）便可实现，因此顺序表是一种随机存取结构在链表上实现读表元运算的平均时间复杂性为O（1）链入、摘除操作在链表上的实现可在O（1）时间内完成链入、摘除操作在顺序表上的实现，平均时间复杂性为O（n）19在串的基本运算中，属于加工型运算的有 （ 4 ）EQAL(S,T) LENGTH(S)CONCAT(S,T) REPLACE(S,T,R) INDEX(S,T)20. 在串的基本运算中，属于引用型运算的有 （ 4 ）ASSIGN(S,T) INSERT(S1,i,S2)DELETE(S,i,j) SUBSTR(S,i,j) REPLACE(S,T,R)21循环链表主要优点是 （ 4 ）不再需要头指针了已知某个结点的位置后，能够容易找到它的直接前趋在进行插入、删除运算时，能更好地保证链表不断开从表中任一结点出发都能扫描到整个链表22，每种数据结构都具备三个基本操作:插入、删除和查找，这种说法 （ 2 ）正确 错误23以下说法错误的是 （ 2 ）数据的物理结构是指数据在计算机内实际的存储形式算法和程序没有区别，所以在数据结构中二者是通用的对链表进行插人和删除操作时，不必移动结点双链表中至多只有一个结点的后继指针为空24以下说法正确的是 3线性结构的基本特征是：每个结点有且仅有一个直接前趋和一个直接后继线性表的各种基本运算在顺序存储结构上的实现均比在链式存储结构上的实现效率要低在线性表的顺序存储结构中，插人和删除元素时，移动元素的个数与该元素位置有关顺序存储的线性表的插人和删除操作不需要付出很大的代价，因为平均每次操只有近一半的元素需要移动25以下说法错误的是 （ 4 ）求表长、定位这二种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低顺序存储的线性表可以随机存取由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活线性表的链式存储结构优于顺序存储结构26以下说法错误的是 （2 ）线性表的元素可以是各种各样的，逻辑上相邻的元素在物理位置上不一定相邻在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素27以下说法正确的是（ 3 ）在单链表中，任何两个元素的存储位置之间都有固定的了解，因为可以从头结点进行查找任何一个元素在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构顺序存储结构属于静态结构，链式结构属于动态结构顺序存储方式只能用于存储线性结构28.以下说法正确的是（ 4 ）顺序存储方式的优点是存储密度大、且插入、删除运算效率高链表的每个结点中都恰好包含一个指针线性表的顺序存储结构优于链式存储结构顺序存储结构属于静态结构，链式结构属于动态结构29.下面关于线性表的叙述正确的是( 1 )线性表采用顺序存储，必须占用一片连续的存储单元线性表采用顺序存储，便于进行插人和删除操作线性表采用链接存储，不必占用一片连续的存储单元线性表采用链接存储，不便于插人和删除操作30.线性表L=(a1,a2,.,ai,.,an),下列说法正确的是( 4 )每个元素都有一个直接前驱和直接后继线性表中至少要有一个元素表中诸元素的排列顺序必须是由小到大或由大到小的除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继31.线性表的逻辑顺序与存储顺序总是一致的，这种说法( 2 )正确 不正确32.设p,q是指针,若p=q,则*p=*q ,这种说法( 2 ) 正确 不正确33.线性表若采用链表存储结构时，要求内存中可用存储单元的位置( 4 )必需是了解的 部分位置必须是连续的一定是不连续的 连续不连续都可以34.设REAR是指向非空带头结点的循环单链表的尾指针,则删除表首结点的操作可表示为( 4 )p=rear; rear=rear-next;rear=rear-next; free(rear);free(p)rear=rear-next-next; p=rear-next-next;free(rear); rear-next-next=p-next; free(p); 35. 单链表中，增加头结点的目的是为了 ( 3 )使单链表至少有一个结点 标示表结点中首结点的位置方便运算的实现 说明单链表是线性表的链式存储实现36线性结构中的一个结点代表一个数据元素，通常要求同一线性结构的所有结点所代表的数据元素具有相同的特性，这意味着 3 每个结点所代表的数据元素都一样。 每个结点所代表的数据元素包含的数据项的个数要相等 不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致 结点所代表的数据元素有同一特点37带头结点的单链表Head为空的判定条件是 2Head=Null Head-next=NULL Head-next=Head38.非空的单循环链表L的尾结点*P,满足 3P-next=NULL P=NULL P-next=L P=L.39.双向链表结点结构如下： LLink dataRLink其中：LLink是指向前驱结点的指针域：data是存放数据元素的数据域；Rlink是指向后继结点的指针域。下面给出的算法段是要把一个新结点*Q作为非空双向链表中的结点*p的前驱，插入到此双向链表中。不能正确完成要求的算法段是 2Q-LLink=P-LLink; P-LLink=Q;Q-Rlink=P; Q-Rlink=P;P-LLink=Q; P-LLink-Rlink=Q;P-LLink-Rlink=Q; Q-LLink=P-LLink;Q-LLink=P-LLink;Q-Rlink=P;P-LLink-Rlink=Q;P-LLink=Q;40.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ 1 ）存储方式最节省时间。顺序表 单链表 双链表 单循环链表41串是任意有限个4符号构成的集合 符号构成的序列字符构成的集合 字符构成的序列第三、四章练习题3.1设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：(1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈)?(2) 能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。(3)请分析 1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。 答：(1)出栈序列为：1324 (2)不能得到1423序列。因为要得到14的出栈序列，则应做Push(1),Pop(),Push(2),Push (3),Push(4),Pop()。这样，3在栈顶，2在栈底，所以不能得到23的出栈序列。能得到1432的出栈序列。具体操作为：Push(1), Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。(3)在1，2 ，3 ，4 的24种排列中，可通过相应入出栈操作得到的序列是： 1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321 不能得到的序列是：1423,2413,3124,3142,3412,4123,4132,4213,4231,43123.2链栈中为何不设置头结点? 答： 链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。3.3设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢?答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。3.4指出下述程序段的功能是什么?(1) void Demo1(SeqStack *S) int i; arr64 ; n=0 ; while ( StackEmpty(S) arrn+=Pop(S); for (i=0, i n; i+) Push(S, arri); /Demo1(1) 程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在64个以内。 (2) SeqStack S1, S2, tmp; DataType x; ./假设栈tmp和S2已做过初始化 while ( ! StackEmpty (&S1) x=Pop(&S1) ; Push(&tmp,x); while ( ! StackEmpty (&tmp) ) x=Pop( &tmp); Push( &S1,x); Push( &S2, x); (2) 程序段的功能是利用tmp栈将一个非空栈s1的所有元素按原样复制到一个栈s2当中去。 (3) void Demo2( SeqStack *S, int m) / 设DataType 为int 型 SeqStack T; int i; InitStack (&T); while (! StackEmpty( S) if( i=Pop(S) !=m) Push( &T,i); while (! StackEmpty( &T) i=Pop(&T); Push(S,i); (3) 程序段的功能是利用栈T，将一个非空栈S中值等于m的元素全部删去。 (4)void Demo3( CirQueue *Q) / 设DataType 为int 型 int x; SeqStack S;InitStack( &S); while (! QueueEmpty( Q )x=DeQueue( Q); Push( &S,x); while (! StackEmpty( &s) x=Pop(&S); EnQueue( Q,x ); / Demo3(4) 程序段的功能是将一个循环队列Q经过S栈的处理，反向排列，原来的队头变成队尾，原来的队尾变成队头。 (5) CirQueue Q1, Q2; / 设DataType 为int 型 int x, i , n= 0; . / 设Q1已有内容， Q2已初始化过 while ( ! QueueEmpty( &Q1) ) x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); n+; for (i=0; i=1)层上至多有_2i-1_个结点。5.深度为k(k=1)的二叉树至多有2k-1 个结点。6.对任何二叉树，若度为2的节点数为n2，则叶子数n0=n2+1 。7.满二叉树上各层的节点数已达到了二叉树可以容纳的最大值。满二叉树也是完全二叉树，但反之不然。8.具有n个结点的完全二叉树的深度为floor(log2n)+1。9.如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1=in，则结点X无左孩子且无右孩子；否则，X的左孩子LCHILD(X)的编号为2i。（3） 若2i+1n，则结点X无右孩子；否则，X的右孩子RCHILD(X)的编号为2i+1。10.二叉树通常有顺序存储结构和链式存储结构两类存储结构。11.每个二叉链表的访问只能从根结点的指针，该指针具有标识二叉链表的作用。12.对二叉链表的访问只能从根指针开始，若二叉树为空，则root=NULL.13.二叉链表中每个存储结点的每个指针域必须有一个值，这个值或者是指向该结点的一个孩子的指针，或者是空指针NULL。14.具有n个结点的二叉树中,一共有2n个指针域,其中只有n-1个用来指向结点的左右孩子，其余的n+1个指针域为NULL。15二叉树有不同的链式存储结构，其中最常用的是二叉链表与三叉链表。16可通过在非完全二叉树的“残缺”位置上增设“虚结点”将其转化为完全二叉树。17以下程序段采用先根遍历方法求二叉树的叶子数，请在横线处填充适当的语句。Void countleaf(bitreptr t,int *count)/*根指针为t，假定叶子数count的初值为0*/ if(t!=NULL) if(t-lchild=NULL)&(t-rchild=NULL)*count+ ; countleaf(t-lchild,&count); countleaf(l-rchile,count)； 18一棵二叉树由根、左子树和右子树三部分组成，因此对二叉树的遍历也可相应地分解成_访问根结点，遍历左子树，遍历右子树三项“子任务”。19若以D、L、R分别表示二叉树的三项子任务，限定“先左后右”，这样可能的次序有：DLR ,LDR,LRD三种，按这三种次序进行的遍历分别称为前序遍历，中序遍历，后序遍历。20树的主要遍历方法有_先根遍历，后根遍历，层次遍历等三种。21判定树的每个非终端结点包含一个条件，对应于一次比较或判断，每个终端结点对应一种分类结果。22设定T是一判定树，其终端结点为n1,，nk。每个终端结点ni对应的百分为pi（通常将pi称为n1的权）。再假定ni的祖先数为li，这样，按T进行分类的平均比较次数为WPL（T） 。23根据文字说明，请在以下横线处填充适当的语句。采用静态链表作存储结构，设置一个大小为2n-1的数组,令数组每个元素由四个域组成：wt是结点的权值；lchild、rchild分别为结点的左、右孩子指针；parent是结点的双亲在数组中的下标。其数组元素类型定义如下：typedef struct float wt /*权值*/int parent,lchild rchild; /*指针域*/ node; typedef node hftree2*n-1;在这种存储结构上的哈夫曼算法可描述如下：void Huffman(int k,float Wk,hftree T) /*求给定权值W的哈夫曼树T*/int i,j,x,y;float m,n;for(i=0;i2*k-1;i+) Ti.parent=-1;Ti.lchild=-1;Ti.rchild=-1; if(ik)Ti.wt=Wi; else Ti.wt=0for(i=0;ik-1;i+) x=0;y=0;m=maxint;n=maxint; for(j=0;jk=i;j+) if(Tj.wtm)&(Tj.parent=-1)n=m;y=x;m=Tj.wt;x=j; else if(Tj.wtn)&(Tj.parint=-1)n=Tj.wt;y=j; Tx.parent=k+i;Ty.parent=k+i; Tk+i.wt=m+n; Tk+i.lchild=x;Tk+i.rchild=y;24若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后根遍历序列中的第一个结点。25在先根遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。26具有n个结点的完全二叉树，若按层次从上到下、从左到右对其编，号（根结点为1号），则编号最大的分支结点序号是floor(n/2) ，编号最小的分支结点序号是l，编号最大的叶子结点序号是n，编号最小的叶子结点序号是floor(n/2)+1。27二叉树的先根遍历序列中，除根结点外，任一结点均处在其双亲结点的后面。28先根遍历树和先根遍历与该树对应的二叉树，其结果相同。29树与二叉树之间最主要的差别是：二叉树中各结点的子树要区分为左子树和右子树，即使在结点只有一棵子树的情况下，也要明确指出该子树是左子树还是右子树。30由树转换成二叉树时，其根结点的右子树总是空的。31哈夫曼树是带权路径度最短的树，通常权值较大的结点离根较近。32有m个叶子结点的哈夫曼树，其结点总数为2m-1。33一棵树的形状如图填空题33所示，它的根结点是A，叶子结点是E,G,I,J,K,L,N,O,P,Q,R，结点H的度是3，这棵树的度是4，这棵树的深度是5，结点F的儿子结点是J,K，结点G的父结点是C。34树的结点数目至少为1，二叉树的结点数目至少为0。35树中结点的最大度数允许大于2，而二叉树中结点的最大度数不允许大于2。36结点最少的树为只有一个根节点的树，结点最少的二叉树为空二叉树。37若一棵二叉树的叶子数为n，则该二叉树中，左、右子树皆非空的结点个数为n-1。38任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度数为1的结点为n-2m+1个。39现有按中序遍历二叉树的结果为ABC，问有5种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是_。40以数据集4，5，6，7，10，12，18为叶结点权值所构造的哈无曼树为_,其带权路径长度为WPL165_。41有m个叶子结点的哈夫曼树上的结点数是m-1。42已知一棵度为3的树有2个度为1的结点，3个度过为2的结点，4个度为3的结点，则该树中有_本题有一定的难度，其求解方法如下：设总结点数为n度为0、1、2、3的结点数分别为n0,n1,n3,则有下面两个等式成立：n=n0+n1+n2+n3 /*结点数*/n-1=n1+2n2+3n3 /*分支数*/两式相减得 n0=1+n2+2n3=1+3+2x4=12 _个叶子结点。43设树T的度为4，其中度为1、2、3和4的结点个数分别是4、2、1和1，则T中叶子结点的个数是_。三、单向选择题1 以下说法错误的是 ( 1 )树形结构的特点是一个结点可以有多个直接前趋线性结构中的一个结点至多只有一个直接后继树形结构可以表达(组织)更复杂的数据树(及一切树形结构)是一种分支层次结构任何只含一个结点的集合是一棵树2，以下说法错误的是 ( 3 ) 二叉树可以是空集二叉树的任一结点都有两棵子树二叉树与树具有相同的树形结构二叉树中任一结点的两棵子树有次序之分3、以下说法错误的是 ( 4 )完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达在三叉链表上，二叉树的求双亲运算很容易实现在二叉链表上，求根，求左、右孩子等很容易实现在二叉链表上，求双亲运算的时间性能很好4、以下说法错误的是 ( 2 ) 一般在哈夫曼树中，权值越大的叶子离根结点越近哈夫曼树中没有度数为1的分支结点若初始森林中共有n裸二叉树，最终求得的哈夫曼树共有2n-1个结点若初始森林中共有n裸二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树5深度为6的二叉树最多有( )个结点 ( 2 )64 63 32 316将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双结点编号为 ( 4 )42 40 21 207任何一棵二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置 ( 3 ) 肯定发生变化 有时发生变化肯定不发生变化 无法确定8设二叉树有n个结点，则其深度为 ( 4 )n-1 n 5floor(log2n) 无法确定9设深度为k的二叉树上只有度为0和度为2的节点，则这类二叉树上所含结点总数最少（3 ）个k+1 2k 2k-1 2k+110.下列说法正确的是 ( 1 )树的先根遍历序列与其对应的二叉树的先根遍历序列相同树的先根遍历序列与其对应的二叉树的后根遍历序列相同树的后根遍历序列与其对应的二叉树的先根遍历序列相同树的后根遍历序列与其对应的二叉树的后根遍历序列相同11下列说法中正确的是 ( 4 )任何一棵二叉树中至少有一个结点的度为2任何一棵二叉树中每个结点的度都为2任何一棵二叉树中的度肯定等于2任何一棵二叉树中的度可以小于212一棵二叉树满足下列条件：对任意结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用（ 2 ）遍历方式就可以得到这棵二叉树所有结点的递增序列。先根 中根 后根 层次13设森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的右子树上有（ 4 ）个结点。n1-1 n1 n1+n2+n3 n2+n3+n4 14森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的左孩子上有（ 1 ）个结点。n1-1 n1 n1+n2+n3 n2+n3+n415.对含有（ 2 ）个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。0 1 2 不存在这样的二叉树16讨论树、森林和二叉树的关系，目的是为了（ 1 ）借助二叉树上的运算方法去实现对树的一些运算将树、森林按二叉树的存储方式进行存储将树、森林转换成二叉树体现一种技巧，没有什么实际意义 17如图选择题17所示二叉树的中序遍历序列是（ 2 ）abcdgef dfebagc dbaefcg defbagc18.已知某二叉树的后续遍历序列是dabec,中序遍历序列是deabc,它的前序遍历序列是（4 ）acbed deabc decab cedba19.如果T2是由有序树T转化而来的二叉树，那么T中结点的前序就是T2中结点的（1 ）前序 中序 后序 层次序20如果T2是由有序树T转化而来的二叉树，那么T中结点的后序就是T2中结点的（ 2 ）前序 中序 后序 层次序21某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是 （4 ）bdgcefha gdbecfha bdgechfa gdbehfca22.在图选择题22中的二叉树中，（ 3 ）不是完全二叉树。 23、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法 ( 1 )正确 错误24、由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法 ( 2 )五确 错误25，二叉树是每个结点的度不超过2的有序树的特殊情况，这种说法 ( 2 )正确 错误26树最适合用来表示 ( 3 )有序数据元素 无序数据元素元素之间具有分支层次关系的数据 元素之间无了解的数据27，深度为5的二叉树至多有( 3 )个结点。16 32 31 1028、在计算递归函数时，如不使用递归过程，则一般情况下必须借助于（ 1 ）数据结构栈