数据结构真题分类整理new

1、第一章 概述 真题16.下列程序段的时间复杂度为_。for(i=1；i=n；i+)for(j=1；j=n；j+)for(k=1；k=n；k+)s=i+j+k；17.在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为_。16.下列程序段的时间复杂度为_。i=0；s=0；while（in） i+；s=s+i；17.数据的逻辑结构被分为集合结构、_、树形结构和图状结构4种。1.数据的不可分割的最小标识单位是（）A.数据项 B.数据记录 C.数据元素 D.数据变量2. for（i=0；im；i+）for（j=0；jt；j+）cij=0；for（i=0；im；i+）for（j=0；

2、jt；j+）for（k=0；kn；k+）cij=cij+aik*bkj；上列程序的时间复杂度为（） A.O(m+nt) B.O(m+n+t) C.O(mnt) D.O(mt+n)16.在数据结构中，数据的存储结构有顺序存储方式、链式存储方式、_和散列存储方式等四种。17.作为一个算法输入的数据所含数据元素的数目，或与此数目有关的其他参数，称为_。 1.从逻辑上可以把数据结构分为（） A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构2.关于算法的描述，不正确的是（） A.算法最终必须由计算机程序实现 B.所谓时间复杂度是指最坏情况下，估算算法执行

3、时间的一个上界 C.健壮的算法不会因非法的输入数据而出现莫名其妙的状态 D.算法的优劣与算法描述语言无关16.在任何问题中，数据元素都不是孤立的，它们之间总存在某种关系，通常称这种关系为_。 17.存储结点之间通常有四种基本存储方式，即顺序存储方式、索引存储方式、_和散列存储方式。1.在数据结构中，数据的基本单位是( ) A.数据项 B.数据元素 C.数据对象 D.数据文件2. k=1; for（i=0；in；i+）for（j=0；jn；j+） Aij=k+；上述程序段的时间复杂度为( ) A.O（n2） B.O（n） C.O（2n） D.O（1）16.数据的逻辑结构通常包括集合、线性结构、_

4、和图状结构。1.在数据结构中，从逻辑上可以把数据结构分成( )A.线性结构和非线性结构 B.紧凑结构和非紧凑结构C.动态结构和静态结构 D.内部结构和外部结构2.for（i=0；im；i+）for（j=0；jn；j+）Aij=i*j；上面算法的时间复杂度为( ) A.O(m2) B.O(n2) C.O(mn) D.O(m+n）16.如果操作不改变原逻辑结构的“值”，而只是从中提取某些信息作为运算结果，则称该类运算为_ _型运算。3从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（ ）A线性结构 B.树形结构 C.线性结构和树型结构 D.线性结构和图状结构16在数据结构中，各个结点

5、按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为_。17每个存储结点只含一个数据元素，所有存储结点连续存放。此外增设一个索引表，索引表中的索引指示各存储结点的存储位置或位置区间端点。按这种方式组织起来的存储结构称为_。1.数据的基本单位是（）A.数据项 B.数据类型 C.数据元素 D.数据变量2.下列程序的时间复杂度为（）i=0；s=0；while（sn） i+；s=s+i；A.O（） B.O（） C.O（n） D.O（n2）16.在数据结构中，数据的逻辑结构分为集合、_、树形结构和图状结构等四类。17.通常从正确性、易读性、_和高效率等4个方面评价算法（包括程序）的质量。1.数据结构中所定

6、义的数据元素，是用于表示数据的（）A.最小单位 B.最大单位 C.基本单位 D.不可分割的单位2.数据的四种基本存储结构是指（）A.顺序存储结构、索引存储结构、直接存储结构、倒排存储结构B顺序存储结构、索引存储结构、链式存储结构、散列存储结构C顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构D.顺序存储结构、链式存储结构、树型存储结构、图型存储结构16.数据表示和_是程序设计者所要考虑的两项基本任务。17.一个算法通常可从正确性、易读性、健壮性和_等四个方面评价、分析。1.若要描述数据处理的变化过程，其正确的次序应为( )A.处理要求、基本运算和运算、算法 B.处理要求、算法、基本运算

7、和运算C.基本运算和运算、处理要求、算法 D.算法、处理要求、基本运算和运算2.从运算类型角度考虑，属于引用型的运算是( )A.插入、删除B.删除、修改 C.查找、读取D.查找、删除16.算法通常可分为程序、伪语言算法和_三种类型。17.时间复杂性描述量级中，若某算法达到_量级，则该算法通常是不可计算的。1.数据的四种基本逻辑结构是指( )A.数组、链表、树、图形结构 B.线性表、链表、栈队列、数组广义表C.线性结构、链表、树、图形结构 D.集合、线性结构、树、图形结构2.数据结构中，通常采用两种方法衡量算法的时间复杂性，即( )A.最大时间复杂性和最小时间复杂性B.最好时间复杂性和最坏时间复

8、杂性C.部分时间复杂性和总体时间复杂性 D.平均时间复杂性和最坏时间复杂性16.根据不同的描述方式，对数据的操作运算通常可分为加工型运算和_两种基本类型。17.数据结构中的算法，通常采用最坏时间复杂度和_两种方法衡量其效率。1.要将现实生活中的数据转化为计算机所能表示的形式，其转化过程依次为（）A.逻辑结构、存储结构、机外表示B.存储结构、逻辑结构、机外表示C.机外表示、逻辑结构、存储结构D.机外表示、存储结构、逻辑结构2.若评价算法的时间复杂性，比较对数阶量级与线性阶量级，通常（）A.对数阶量级复杂性大于线性阶量级 B.对数阶量级复杂性小于线性阶量级C.对数阶量级复杂性等于线性阶量级 D.两

9、者之间无法比较16.从数据结构的观点，数据通常可分为三个层次，即：数据、数据元素和_。17.用程序设计语言、伪程序设计语言并混合自然语言描述的算法称为_算法。1下列数据组织形式中，（）的各个结点可以任意邻接。A集合B树形结构 C线性结构D图状结构2设某二维数组A1.n，1.n，则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为（AO（log2n）BO(n) CO(nlog2n)DO(n2)16下列程序段的时间复杂性量级是_。for (i=1;in; i+) for (j=1; jnext=pnextnext B.p=pnext C.p=pnextnext D.pnext=p5.向一个栈顶

10、指针为hs的链栈中插入一个*s结点时，应执行的操作为（） A.hsnext=s; B.snext=hs;hs=s; C.snext=hsnext;hsnext=s; D.snext=hs;hs=hsnext;6.设循环队列的元素存放在一维数组Q030中，队列非空时，front指示队头元素的前一个位置，rear指示队尾元素。如果队列中元素的个数为11，front的值为25，则rear应指向的元素是（） A.Q4 B.Q5 C.Q14 D.Q157.定义二维数组A18，010，起始地址为LOC，每个元素占2L个存储单元，在以行序为主序的存储方式下，某数据元素的地址为LOC+50L，则在以列序为主序

11、的存储方式下，该元素的存储地址为（） A.LOC+28L B.LOC+36L C.LOC+50L D.LOC+52L18.在双链表中，存储一个结点有三个域，一个是数据域，另两个是指针域，分别指向_和_。 19.在有n个元素的链队列中，入队和出队操作的时间复杂度分别为_和_。 20.在栈结构中，允许插入的一端称为_;在队列结构中，允许插入的一端称为_。 21.在循环队列中，存储空间为0n-1。设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么其队空标志为rear=front，队满标志为_。 3.在单链表中，存储每个结点需要有两个域，一个是数据域，另一个是指针域，指针域指向

12、该结点的（） A.直接前趋 B.直接后继 C.开始结点 D.终端结点4.将两个各有n个元素的有序表合并成一个有序表，其最少的比较次数为（） A.n B.2n-1 C.2n D.n25.栈和队列共同具有的特点是（）A.都是先进后出 B.都是先进先出 C.只允许在端点进行操作运算 D.既能先进先出，也能先进后出6.若用一个有6个单元的数组来实现循环队列，rear和front的初值分别为0和3。则从队列中删除一个元素，再添加两个元素后，rear和front的值分别为（） A.1和5 B.2和4 C.4和2 D.5和17.数组A0.50.5的每个元素占5个字节，将其以列为主序存储在起始地址为1000的

13、内存单元中，则元素A55的地址是（） A.1175 B.1180 C.1205 D.121018.在一个长度为n的顺序表中第i个元素（1in）之前插入一个元素时，需向后移动_个元素。24.两个串是相等的，当且仅当两个串的长度相等且_的字符都相同。 34.设两个数据元素均为整型数据的线性表A=(a1，a2，an)和B=(b1，b2，bm)。若n=m且ai=bi（i=1，2,，n）则认为A=B；若ai=bi（i=1，2,，j）且aj+1BJ+1，（Jnext-next!=h) p=p-next;p-next=h; 后（其中，p-next为p指向结点的指针域），则( )A.p-next指针指向链尾结

14、点 B.h指向链尾结点 C.删除链尾前面的结点 D.删除链尾结点 5.设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为( ) A.236 B.239 C.242 D.2456.一个栈的入栈序列是a,b,c,d,e，则栈的输出序列不可能是( )A.dceab B.decba C.edcba D.abcde7.元素大小为1个单元，容量为n个单元的非空顺序栈中，以地址高端为栈底，以top作为栈顶指针，则出栈处理后，top的值应修改为( ) A.top=top B.top=n-1 C.top=top-1 D.top=top+117.设双链表中结点的前趋指

15、针和后继指针的域名分别为t1和r1，指针s指向双链表中的一个结点（该结点既非头结点，也非尾结点），则删除s指针所指向结点的操作为“s-tl-r1=s-r1；”和“_”。32.如题32图所示，在栈的输入端有6个元素，顺序为A，B，C，D，E，F。能否在栈的输出端得到序列DCFEBA及EDBFCA？若能，给出栈操作的过程，若不能，简述其理由。 35.某带头结点的单链表的结点结构说明如下： typedef struct node1 int data; struct node1 *next node；试设计一个算法int copy(node *head1, node *head2)，将以head1为头

16、指针的单链表复制到一个不带头结点且以head2为头指针的单链表中。3.设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为( )A.5 B.6 C.7 D.94.设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用pllink和prlink表示，则同样表示p指针所指向结点的表达式是( )A.pllink B.prlink C.pllinkllink D.pllinkrlink5.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是( )A. 110 B. 108 C. 100 D. 1206.设有一个栈，按A、B、C、D的顺序进栈

17、，则可能为出栈序列的是( )A.DCBA B.CDAB C.DBAC D.DCAB7.在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top为栈顶指针，则当做出栈处理时，top变化为( )A.top+ B.top- C.top不变 D.top=017.设有指针head指向不带表头结点的单链表，用next表示结点的一个链域，指针p指向与链表中结点同类型的一个新结点。现要将指针p指向的结点插入表中，使之成为第一个结点，则所需的操作为“pnext=head；”和“_”。18.单链表中逻辑上相邻的两个元素在物理位置上_相邻。19.在一个长度为n的数组中删除第i个元素（1in）时，需

18、要向前移动的元素的个数是_。31.如题31图所示，输入元素为A，B，C，在栈的输出端得到一个输出序列ABC，试写出在栈的输入端三个可能的输入序列。34.下面程序段为删除循环链表中第一个info域值等于x的结点，请填上程序中缺少的部分。循环链表的结构如题34图所示：struct node int info;struct node *link; int Delete (struct node *head, int x) struct node *p, *q; /*p:当前处理的结点；q：p的前驱结点*/ if (! head ) return (0);if (headlink =head) if

19、(headinfo=x) free (head); head=NULL； return (x) return (0); p=head; q=head; while (qlink!=head) q=(1) ; while (plink!=head) if (pinfo=x) (2) ; if (p=head) head=(3) ; free (p);return (x); else q=p ;（4） ; return (0);1关于栈和队列的说法中正确的是（ ）A栈和队列都是线性结构 B.栈是线性结构，队列不是线性结构 C.栈不是线性结构，队列是线性结构 D.栈和队列都不是线性结构2关于存储相同

20、数据元素的说法中正确的是（ ）A顺序存储比链式存储少占空间 B.顺序存储比链式存储多占空间C.顺序存储和链式存储都要求占用整块存储空间 D.链式存储比顺序存储难于扩充空间3从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（ ）A线性结构 B.树形结构 C.线性结构和树型结构 D.线性结构和图状结构4已知一个单链表中，指针q指向指针p的前趋结点，若在指针q所指结点和指针p所指结点之间插入指针s所指结点，则需执行（ ）Aqnext=s；pnext=s；B.qnext=s；snext=p； C.qnext=s；qnext=p；D.qnext=s；snext=q；5在长度为n的线性表中删

21、除一个指针p所指结点的时间复杂度是（ ）AO(n) B.O(1) C.O(log2n) D.O(n2)6设一个栈的输入序列是a,b,c,d，则所得到的输出序列（输入过程中允许出栈）不可能出现的是（ ）Aa，b，c，d B.a，b，d，c C.d，c，b，a D.c，d，a，b7关于串的叙述中，正确的是（ ）A空串是只含有零个字符的串 B.空串是只含有空格字符的串C.空串是含有零个字符或含有空格字符的串 D.串是含有一个或多个字符的有穷序列8在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是（ ）Afront=rear B.(front+1)%m=rear C.

22、rear+1=front D.(rear+1)%m=front9设有二维数组Ann表示如下： ， 则Aii（0in-1）的值为（ ）Ai*(i-1)/2 B.i*(i+1)/2 C.(i+2)*(i+1)/2 D.i2/218在顺序表上读表元算法的时间复杂度为_。19双链表中前驱指针为prior，后继指针为next，在指针P所指结点前插入指针S所指的结点，需执行下列语句：Snext=P;Sprior=Pprior;Pprior=S;_;20设数组A0.80.8的起始元素位置为a，每个元素占2 L个存储单元，按行序为主序存储。若元素Aij的存储位置为a+66 L，则元素Aji的存储位置为_。29

23、有一字符串序列为5*-x-y/x+2，利用栈的运算将其输出结果变为5x-*yx+/-2，试写出该操作的入栈和出栈过程（采用push(a)表示a入栈，pop(a)表示a出栈）。34设单链表的结点结构如下：struct nodedatatype data;struct node*next;试编写一个函数int count(struct node *head,datatype x)统计单链表中数据域为x的结点个数。3.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（）A.单链表 B.仅有头指针的单循环链表 C.双链表 D.仅有尾指针的单循环链表

24、4.从一个长度为n的顺序表中删除第i个元素（1in）时，需向前移动的元素的个数是（）A.n-i B.n-i+1 C.n-i-1 D.i5.顺序栈S中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为（）A.s.elemtop=e；s.top=s.top+1；B.s.elemtop+1=e；s.top=s.top+1；C.s.top=s.top+1；s.elemtop+1=e； D.s.top=s.top+1； s.elemtop=e；6.循环队列sq中，用数组elem025存放数据元素，sq.front指示队头元素的前一个位置，sq.rear指示队尾

25、元素的当前位置，设当前sq.front为20，sq.rear为12，则当前队列中的元素个数为（）A.8 B.16 C.17 D.187.设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a45的地址为（）A.13 B.35 C.17 D.3618.顺序表的存储密度为_，而链表的存储密度为_。19.对于栈只能在_插入和删除元素。20.在循环队列中，存储空间为0n-1,设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么队满标志为front=(rear+1)%n，队空标志为_。3.对于长度为n的顺

26、序表执行删除操作，则其结点的移动次数（）A.最少为0，最多为n B.最少为1，最多为n C.最少为0，最多为n-1 D.最少为1，最多为n-14.在一个单链表中，若p所指结点是q所指结点的前驱结点，则删除结点q的正确操作是（A. p-next=q B. p-next=q-next C. p=q-next D. p-next=q-next-next5.有关栈的描述，正确的是（）A.栈是一种先进先出的特殊的线性表B.只能从栈顶执行插入、删除操作C.只能从栈顶执行插入、栈底执行删除D.栈顶和栈底均可执行插入、删除操作6.二维数组A1020采用按行为主序的存储方式，每个元素占4个存储单元，若A00的存

27、储地址为300，则A1010的地址为（）A.700 B.1120 C.1180 D.114018.对长度为n的顺序表执行删除操作，其删除算法在最坏情况下的时间复杂性为_。19.串是一种特殊的线性表，串常见的存储结构有顺序存储和_两种方式。20.我们通常把队列中允许插入的一端称为_。21.二维数组在机器级的具体实现，通常均采用_存储结构。34.试编写一个函数，以读取单链表的第i个元素。3.若在长度为n的顺序表中插入一个结点，则其结点的移动次数( )A.最少为0，最多为nB.最少为1，最多为n C.最少为0，最多为n+1D.最少为1，最多为n+14.在一个单链表中，若p所指结点是q所指结点的前驱结

28、点，则在结点p、q之间插入结点s的正确操作是( )A.s-next=q；p-next=s-next B.p-next=q；p-next=s C.s-next=q-next；p-next=s D.s-next=q-next；p-next=s-next5.若有一串数字5、6、7、8入栈，则其不可能的输出序列为( )A.5、6、7、8B.8、7、6、5 C.8、7、5、6D.5、6、8、76.FORTRAN语言对数组元素的存放方式通常采用( )A.按行为主的存储结构B.按列为主的存储结构 C.按行或列为主的存储结构D.按行和列为主的存储结构18.对顺序表执行删除操作，其删除算法的平均时间复杂性为_。

29、19.若head表示循环链表的头指针，t表示尾结点，则头指针head与尾结点t之间的关系可表示为_。20.我们通常把队列中允许删除的一端称为_。21.二维数组A56采用按列为主序的存储方式，每个元素占3个存储单元，若A00的存储地址是100，则A43的存储地址是_。34.若循环单链表长度大于1，p为指向链表中某结点的指针，试编写一算法删除p结点的前驱结点。3.下列关于线性表的叙述中，不正确的是( )A.线性表是n个结点的有穷序列 B.线性表可以为空表C.线性表的每一个结点有且仅有一个前趋和一个后继 D.线性表结点间的逻辑关系是1:1的联系4.在一个单链表中，若p所指结点不是最后结点，则删除p所

30、指结点的后继结点的正确操作是( )A.p=p-next B.p-next=p-next C.p-next=p-next-next D.p-next=p5.栈和队列( )A.共同之处在于二者都是先进先出的特殊的线性表 B.共同之处在于二者都是先进后出的特殊的线性表C.共同之处在于二者都只允许在顶端执行删除操作 D.没有共同之处6.二维数组A56采用按列为主序的存储方式，每个元素占3个存储单元，若A00的存储地址是100，则A43的存储地址是( )A.127 B.142 C.150 D.15718.判断带头结点head的单链表为空的条件是_。19.若顺序表每个元素长度均为5，其中第一个元素的存储地

31、址为30，则第6个元素的存储地址为_。20.若front和rear分别表示循环队列Q的头指针和尾指针，m0表示该队列的最大容量，则判断循环队列为满的条件是_。21.对于顺序存储结构的二维数组，通常采用_两种存放方式存储数据元素。34.试编写一算法，以完成在带头结点单链表L中第i个位置前插入元素X的操作。3.下列关于线性表的基本操作中，属于加工型的操作是（）A.初始化、求表长度、插入操作B.初始化、插入、删除操作C.求表长度、读元素、定位操作D.定位、插入、删除操作4.在一个单链表中，若p所指结点不是最后结点，s指向已生成的新结点，则在p之后插入s所指结点的正确操作是（）A.snext=pnex

32、t; pnext=s;B.pnext=snext; snext=p;C.snext=p; pnext=s;D.snext=pnext; p=s;5.若有三个字符的字符串序列执行入栈操作，则其所有可能的输出排列共有（）A.3种B.4种 C.5种D.6种6.C语言对数组元素的存放方式通常采用（）A.按行为主的存储结构B.按列为主的存储结构C.按行或列为主的存储结构D.具体存储结构无法确定18.对顺序表执行插入操作，其插入算法的平均时间复杂性为_。19.在具有n个单元、且采用顺序存储的循环队列中，队满时共有_个元素。20.若front和rear分别表示循环队列Q的头指针和尾指针，m0表示该队列的最大

33、容量，则循环队列为空的条件是_。21.二维数组A1020采用按行为主序的存储方式，每个元素占4个存储单元，若A00的存储地址为300，则A1010的地址为_。34.设某单链表中，存在多个结点其数据值均为D，试编写一算法统计该类结点的个数。2设某二维数组A1.n，1.n，则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为（AO（log2n）BO(n) CO(nlog2n)DO(n2)3在线性表的下列存储结构中，读取元素花费时间最少的是（）A单链表B双链表 C循环链表D顺序表4将一个头指针为p的单链表中的元素按与原单链表相反的次序存放，则下列算法段中的空白处应为（）q=NULL;while

34、(p!=NULL)（）p=q;Ar=q; q=p; p=p - next; q - next=r; Bq=p; r=q; p=p - next; q - next=r;Cr=q; p=p - next; q=p; q - next=r; Dq=p; p=p - next; r=q; q - next=r;5数组通常具有两种基本运算，即（）A创建和删除B索引和修改 C读和写D排序和查找17在顺序存储的线性表（a1,a2，an）中的第i (1in)个元素之前插入一个元素，则需向后移动_个元素。18在栈的顺序实现中，若栈不满，则进栈操作可以用下列算法片断实现：_；sq - datasq - top=

35、x；19链队列实际上是一个同时带有头指针和尾指针的单链表，尾指针指向该单链表的_。29如图所示，输入元素为A，B，C，在栈的输出端得到一个输出序列ABC，求出在栈的输入端所有可能的输入序列。（5分）34设某头指针为head的单链表的结点结构说明如下：（6分）typedef struct node1int data;struct node1*nextnode;试设计一个算法void change (node*head),将该单链表中的元素按原单链表相反的次序重新存放，即第一个结点变成最后一个结点，第二个结点变为倒数第二个结点，如此等等。35编写一个算法void DisplayQueue ()，产

36、生50个300600之间的随机整数（调用一次MyRand()可产生一个符合条件的随机整数）。每产生一个数据，若是奇数，则入队列，若是偶数，则从队首取出一个数据。要求：（8分）（1）队列用链表实现；（2）每产生一个数显示一次相应操作后的队列当前状态；（3）无需定义函数int MyRand()；（4）显示队列可调用函数void DisOne (QueptrTp lq)，也无需定义；（5）设链队列定义为：typedef struct linked_queue int data; struct linked_queue*next;LqueueTp;typedef struct queueptr Lqu

37、eueTp *front, *rear;QueptrTp;QueptrTp lq;第四章 树 真题2.某二叉树的后根遍历序列为dabec，中根遍历序列为debac，则先根遍历序列为（ ）A.acbed B.becab C.deabc D.cedba3.含有n个结点的二叉树用二叉链表表示时，空指针域个数为( )A.n-1 B.n C.n+1 D.n+212.有关树的叙述正确的是( )A.每一个内部结点至少有一个兄弟 B.每一个叶结点均有父结点C.有的树没有子树 D.每个树至少有一个根结点与一个叶结点。24.对于一棵满二叉树，若有m个叶子，则树中结点数为_。30.已知一棵二叉树的先根遍历序列为AB

38、CDEGHF，中根遍历序列为CBEDAGFH，画出该二叉树。34.二叉树按二叉链表形式存储，编写一个算法判别给定的二叉树是否为完全二叉树。5.由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（ ）A.23 B.37 C.44 D.4612.用n个值构造一棵二叉排序树，它的最大高度为（ ）A.n/2 B. n C. n+1 D.log2n21.若满二叉树的结点数为n，则其高度为_。22.在一棵具有n个结点的完全二叉树中，从树根起，自上而下、从左到右地给所有结点编号。若编号为i的结点有父结点，那么其父结点的编号为_。23.深度为k的二叉树，结点数最多有_个。24.某二叉树

39、的后根遍历为ABKCBPM，则该二叉树的根为_。29.某通讯电文由A，B，C，D，E，F六个字符编码组成，每个字符编码在电文中出现的次数分别是6，5，9，10，20，1，试画出这六个字符编码所用的哈夫曼树。30.已知一棵二叉树的顺序存储结构如题30图所示，其中表示虚结点，试构造该二叉树。ABGCDHEF题30图34.若两棵二叉树B1和B2皆为空，或者皆不空且B1的左、右子树和B2的左、右子树分别相似，则称二叉树B1和B2相似。试编写算法，判别给定两棵二叉树是否相似。8.具有n个结点的二叉树，拥有指向孩子结点的分支数目是（） A.n-1 B.n C.n+1 D.2n9.对一棵有100个结点的完全

40、二叉树按层序编号，则编号为49的结点，它的左孩子的编号为（） A.99 B.98 C.97 D.5010.有m个叶子结点的哈夫曼树，其结点总数是（）A.2m-1 B.2m C.2m+1 D.2(m+1)22.深度为k的二叉树至多有_个结点，最少有_个结点。 29.已知一棵二叉树的前序序列是ABCDEFG，中序序列是CBDAEGF。请构造出该二叉树，并给出该二叉树的后序序列。 30.将题30图所示的由三棵树组成的森林转化为一棵二叉树。8.含有n个结点的二叉树采用二叉链表存储时，空指针域的个数为（） A.n-1 B.n C.n+1 D.n+2 9.在一棵深度为H的完全二叉树中，所含结点的个数不少于

41、（）A.2H-1-1 B.2H-1 C.2H-1 D.2H19.对一棵深度为10的满二叉树按层编号，则编号为51的结点，它的双亲结点编号为_。 21.具有n个叶子结点的哈夫曼树，其结点总数为_。22.一棵具有n个结点的树，所有非终端结点的度均为k，则该树中叶子结点个数为_。 25.某二叉树的后根遍历序列为abd，中根遍历序列为adb，则它的先根遍历序列为_。 30.画出题30图所示的二叉树的二叉链表存储结构。 35.设二叉树的结点类型定义如下： typedef struct node datatype data; struct node*lchild,*rchild;Bitree;Bitree

42、*t; 试编写一个计算二叉树深度的递归算法(int Depth(Bitree*t)。8.某二叉树的先根遍历序列和后根遍历序列正好相反，则该二叉树具有的特征是( )A.高度等于其结点数 B.任一结点无左孩子 C.任一结点无右孩子 D.空或只有一个结点9.在完全二叉树中，若一个结点是叶结点，则它没有( )A.左孩子结点 B.右孩子结点 C.左孩子结点和右孩子结点 D.左孩子结点，右孩子结点和兄弟结点12.若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不超过( )A.n/2 B.n C.n+1/2 D.n+119.在一个具有n个结点的单链表中查找值为m的某结点，若查找成功，则需平均比较的结点数为_。20.深度为15的满二叉树上，第11层有_个结点。21.对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的左孩子的编号为_。30.已知一棵二叉树的中根遍历序列和后根遍历序列分别为BDAFEHGC和DBFHGECA，试画出这棵二叉树。8.除根结点外，树上每个结点( )A