数据结构习题集附答案.docx

《数据结构习题集附答案.docx》由会员分享，可在线阅读，更多相关《数据结构习题集附答案.docx（57页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构习题集附答案数据结构习题集附答案 第一章 绪 论 一、选择题 1.组成数据的基本单位是（ ） A数据项 B数据类型 C数据元素 D数据变量 2.数据结构是探讨数据的（ ）以及它们之间的相互关系。A志向结构，物理结构 B志向结构，抽象结构 C物理结构，逻辑结构 D抽象结构，逻辑结构 3.在数据结构中，从逻辑上可以把数据结构分成（ ）。A动态结构和静态结构 B紧凑结构和非紧凑结构 C线性结构和非线性结构 D内部结构和外部结构 4.数据结构是一门探讨非数值计算的程序设计问题中计算机的 （）以及它们之间的（）和运算等的学科。A数据元素 B计算方法 C逻辑存储 D数据映像 A结构 B关系 C运算

2、 D算法 5.算法分析的两个主要方面是（ ）。A数据困难性和程序困难性 B正确性和简明性 C可读性和简明性 D空间困难性和时间困难性 6.算法分析的目的是（ ）。A找出数据结构的合理性 B探讨算法中的输入和输出的关系 C分析算法的效率以求改进 D分析算法的易懂性和文档性 7.计算机算法指的是（）,它必需具备输入、输出和（）等5个特性。A计算方法 B排序方法 C解决问题的有限运算序列 D调度方法 A可执行性，可移植性和可扩充性 B可行性，确定性和有穷性 C确定性、有穷性和稳定性 D易读性、稳定性和平安性 二、推断题 1.数据的机内表示称为数据的存储结构。（ ） 2.算法就是程序。（ ） 3.数据

3、元素是数据的最小单位。（ ） 4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。（ ） 5.算法的时间困难度取决于问题的规模和待处理数据的初态。（ ） 三、填空题 1.数据逻辑结构包括_、_、_和_四种类型,其中树形结构和图形结构合称为_。2.在线性结构中,第一个结点_前驱结点,其余每个结点有且只有_个前驱结点；最终一个结点_后续结点,其余每个结点有且只有_个后续结点。3.在树形结构中,树根结点没有_结点,其余每个结点有且只有_个前驱结点；叶子结点没有_结点,其余每个结点的后续结点可以_。 4.在图形结构中,每个结点的前驱结点数和后续结点数可以_。 5.线性结构中元素之间存在_关系,树

4、形结构中元素之间存在_关系,图形结构中元素之间存在_关系。 6.算法的五个重要特性是_、_、_、_、_。7.数据结构的三要素是指_、_和_。8.链式存储结构与依次存储结构相比较,主要优点是_。9.设有一批数据元素,为了最快的存储某元素,数据结构宜用_结构,为了便利插入一个元素,数据结构宜用_结构。 四、算法分析题 1.求下列算法段的语句频度刚好间困难度 for(i=1; i<=n; i+) for(j =1; j <=i ; j+) x=x+1; 分析：该算法为一个二重循环，执行次数为内、外循环次数相乘，但内循环次数不固定，与外循环有关，因些，时间频度T(n)=1+2+3+n=n*

5、(n+1)/2 有 1/4T(n)/n21，故它的时间困难度为(n2), 即(n)与n2 数量级相同。 2.分析下列算法段的时间频度刚好间困难度 for （i=1;i<=n;i+） for (j=1;j<=i;j+) for ( k=1;k<=j;k+) x=i+j-k; 分析算法规律可知时间频度T(n)=1+(1+2)+(1+2+3)+.+(1+2+3+n) 由于有1/6 T（n）/ n3 1，故时间困难度为(n3) 其次章 线性表 一、选择题 1.一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( )。A110 B108 C100 D120

6、 2.向一个有127个元素的依次表中插入一个新元素并保持原来依次不变，平均要移动（ ）个元素。A64 B63 C63.5 D7 3.线性表采纳链式存储结构时，其地址（ ）。A必需是连续的 B部分地址必需是连续的 C肯定是不连续的 D连续与否均可以 4.在一个单链表中，若p所指结点不是最终结点，在p之后插入s所指结点，则执行（ ）。As->next=p;p->next=s; Bs->next=p->next;p->next=s; Cs->next=p->next;p=s; Dp->next=s;s->next=p; 5.在一个单链表中，若删除

7、p所指结点的后续结点，则执行（ ）。Ap->next=p->next->next; Bp=p->next; p->next=p->next->next; Cp->next=p->next; Dp=p->next->next; 6.下列有关线性表的叙述中，正确的是（ ）。A线性表中的元素之间隔是线性关系 B线性表中至少有一个元素 C线性表中任何一个元素有且仅有一个干脆前趋 D线性表中任何一个元素有且仅有一个干脆后继 7.线性表是具有n个（ ）的有限序列（n0)。A表元素 B字符 C数据元素 D数据项 二、推断题 1.线性表的链接存

8、储，表中元素的逻辑依次与物理依次肯定相同。（ ） 2.假如没有供应指针类型的语言，就无法构造链式结构。（ ） 3.线性结构的特点是只有一个结点没有前驱，只有一个结点没有后继，其余的结点只有一个前驱和后继。（ ） 4.语句p=p->next完成了指针负值并使p指针得到了p指针所指后继结点的数据域值。（ ） 5.要想删除p指针的后继结点，我们应当执行q=p->next ； p->next=q->next； free(q)。（ ） 三、填空题 1.已知P为单链表中的非首尾结点，在P结点后插入S结点的语句为：_。2.依次表中逻辑上相邻的元素物理位置( )相邻， 单链表中逻辑上相

9、邻的元素物理位置_相邻。3.线性表L（a1，a2，.，an）采纳依次存储，假定在不同的n1个位置上插入的概率相同，则插入一个新元素平均须要移动的元素个数是_。4.在非空双向循环链表中，在结点q的前面插入结点p的过程如下： p->prior=q->prior; q->prior->next=p; p->next=q; _; 5.已知L是无表头结点的单链表，是从下列供应的答案中选择合适的语句序列，实现： 表尾插入s结点的语句序列是_。Ap->next=s; Bp=L; CL=s; Dp->next=s->next; Es->next=p->

10、;next; Fs->next=L; Gs->next=null; Hwhile(p->next!=0) p=p->next; Iwhile(p->next!=null) p=p->next; 四、算法设计题 1.试编写一个求已知单链表的数据域的平均值的函数（数据域数据类型为整型）。2.已知带有头结点的循环链表中头指针为head,试写出删除并释放数据域值为x的全部结点的c函数。3.某百货公司仓库中有一批电视机，按其价格从低到高的次序构成一个循环链表，每个结点有价格、数量和链指针三个域。现出库（销售）m台价格为h的电视机，试编写算法修改原链表。 4.某百货公司

11、仓库中有一批电视机，按其价格从低到高的次序构成一个循环链表，每个结点有价格、数量和链指针三个域。现新到m台价格为h的电视机，试编写算法修改原链表。 5.线性表中的元素值按递增有序排列，针对依次表和循环链表两种不同的存储方式，分别编写C函数删除线性表中值介于a与b（ab）之间的元素。6.设A=(a0,a1,a2,.,an-1),B=(b0,b1,b2,.,bm-1)是两个给定的线性表,它们的结点个数分别是n和m,且结点值均是整数。若n=m，且 ai= bi （0i<n ），则A=B； 若n<m ，且ai=bi （0i<n ），则A<B； 若存在一个j， j<m ，j

12、<n ，且ai=bi （0i<j ）， 若aj<bj，则A<B，否则 A>B。试编写一个比较A和B的C函数，该函数返回 -1或 0或 1，分别表示 A<B或 A=B或 A>B。7.试编写算法,删除双向循环链表中第k个结点。8.线性表由前后两部分性质不同的元素组成(a0,a1,.,an-1,b0,b1,.,bm-1),m和n为两部分元素的个数,若线性表分别采纳数组和链表两种方式存储,编写算法将两部分元素换位成(b0,b1,.,bm-1,a0,a1,.,an-1),分析两种存储方式下算法的时间和空间困难度。9.用循环链表作线性表(a0,a1,.,an-1)

13、和（b0,b1,.,bm-1）的存储结构,头指针分别为ah和bh，设计C函数，把两个线性表合并成形如（a0,b0,a1,b1,）的线性表，要求不开拓新的动态空间,利用原来循环链表的结点完成合并操作,结构仍为循环链表,头指针为head,并分析算法的时间困难度。 10.试写出将一个线性表分解为两个带有头结点的循环链表，并将两个循环链表的长度放在各自的头结点的数据域中的C函数。其中,线性表中序号为偶数的元素分解到第一个循环链表中,序号为奇数的元素分解到其次个循环链表中。 11.试写出把线性链表改为循环链表的C函数。12.己知非空线性链表中x结点的干脆前驱结点为y,试写出删除x结点的C函数。第三章 栈

14、和队列 一、选择题 1.一个栈的入栈序列是a,b,c,d,e,则栈的不行能的输出序列是（ ）。Aedcba Bdecba Cdceab Dabcde 2.栈结构通常采纳的两种存储结构是（ ）。A线性存储结构和链表存储结构 B散列方式和索引方式 C链表存储结构和数组 D线性存储结构和非线性存储结构 3.判定一个栈ST(最多元素为m0)为空的条件是（ ）。AST-top!=0 BST-top=0 CST-top!=m0 DST-top=m0 4.判定一个栈ST(最多元素为m0)为栈满的条件是（ ）。AST->top!=0 BST->top=0 CST->top!=m0-1 DST

15、->top=m0-1 5.一个队列的入列序列是1,2,3,4,则队列的输出序列是（ ）。A4,3,2,1 B1,2,3,4 C1,4,3,2 D3,2,4,1 6.循环队列用数组A0,m-1存放其元素值，已知其头尾指针分别是front和rear则当前队列中的元素个数是（ ）。A(rear-front+m)%m Brear-front+1 Crear-front-1 Drear-front 7.栈和队列的共同点是（ ） A都是先进后出 B都是先进先出 C只允许在端点处插入和删除元素 D没有共同点 8.表达式a*(b+c)-d的后缀表达式是（ ）。Aabcd*+- Babc+*d- Cabc

16、*+d- D-+*abcd 9.4个元素a1，a2，a3和a4依次通过一个栈，在a4进栈前，栈的状态，则不行能的出栈序是（ ）。Aa4，a3，a2，a1 Ba3，a2，a4，a1 Ca3，a1，a4，a2 Da3，a4，a2，a1 10.以数组Q0.m1存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是（ ）。Arearqulen Brearqulenm Cmqulen D1（rearmqulen）%m 二、填空题 1.栈的特点是_，队列的特点是_。2.线性表、栈和队列都是_结构,可以在线性表的_位置插入和删除元

17、素，对于栈只能在_插入和删除元素，对于队列只能在_插入元素和_删除元素。3.一个栈的输入序列是12345,则栈有输出序列12345是_。(正确/错误) 4.设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的依次是a3，a5，a4，a6，a2，a1则栈S至少应当容纳_个元素。三、算法设计题 1.假设有两个栈s1和s2共享一个数组stackM,其中一个栈底设在stack0处，另一个栈底设在stackM-1处。试编写对任一栈作进栈和出栈运算的C函数push（x,i)和pop(i),i=l,2。其中i=1表示左边的栈，,

18、i=2表示右边的栈。要求在整个数组元素都被占用时才产生溢出。2利用两个栈s1,s2模拟一个队列时,如何用栈的运算来实现该队列的运算?写出模拟队列的插入和删除的C函数。一个栈s1用于插入元素,另一个栈s2用于删除元素。第四章 串 一、选择题 1.下列关于串的叙述中，正确的是（ ） A一个串的字符个数即该串的长度 B一个串的长度至少是1 C空串是由一个空格字符组成的串 D两个串S1和S2若长度相同，则这两个串相等 2.字符串“abaaabab“的nextval值为( ) A(0,1,01,1,0,4,1,0,1) B(0,1,0,0,0,0,2,1,0,1) C(0,1,0,1,0,0,0，1,1

19、) D(0,1,0,1,0,1,0,1,1) 3.字符串满意下式,其中head和tail的定义同广义表类似,如head(xyz)=x,tail(xyz)= yz,则s=( )。concat(head(tail(s),head(tail(tail(s)= dc。Aabcd Bacbd Cacdb Dadcb 4.串是一种特别的线性表,其特别性表现在（ ） A可以依次存储 B数据元素是一个字符 C可以链式存储 D数据元素可以是多个字符 5设串S1=ABCDEFG,s2=PQRST,函数CONCAT（X，Y）返回X和Y串的连接串，SUBSTR（S，I，J）返回串S从序号I起先的J个字符组成的字串，L

20、ENGTH（S）返回串S的长度，则CONCAT（SUBSTR（S1，2，LENGTH（S2），SUBSTR（S1，LENGTH（S2），2）的结果串是（ ）。ABCDEF BBCDEFG CBCPQRST DBCDEFEF 二、算法设计 1.分别在依次存储和一般链接存储两种方式下,用C语言写出实现把串s1复制到串s2的串复制函数strcpy(s1,s2)。2.在一般链接存储(一个结点存放一个字符)方式下,写出采纳简洁算法实现串的模式匹配的C语言函数int L_index(t,p)。第五章 数组与广义表 一、选择题 1常对数组进行的两种基本操作是（ ） A建立与删除 B索引和修改 C查找和修改

21、D查找与索引 2.二维数组M的元素是4个字符(每个字符占一个存储单元)组成的串,行下标i的范围从0到4,列下标j的范围从0到5,M按行存储时元素M35的起始地址与M按列存储时元素( )的起始地址相同。AM24 BM34 CM35 DM44 3.数组A810中,每个元素A的长度为3个字节,从首地址SA起先连续存放在存储器内,存放该数组至少须要的单元数是（ ）。A80 B100 C240 D270 4.数组A810中,每个元素A的长度为3个字节,从首地址SA起先连续存放在存储器内,该数组按行存放时,元素A74的起始地址为（ ）。ASA+141 BSA+144 CSA+222 DSA+225 5.数

22、组A810中,每个元素A的长度为3个字节,从首地址SA起先连续存放在存储器内,该数组按列存放时,元素A47的起始地址为（ ）。ASA+141 BSA+180 CSA+222 DSA+225 6.稀疏矩阵一般的压缩存储方法有两种,即（ ）。A二维数组和三维数组 B三元组和散列 C三元组和十字链表 D散列和十字链表 7.若采纳三元组压缩技术存储稀疏矩阵,只要把每个元素的行下标和列下标互换,就完成了对该矩阵的转置运算,这种观点（ ）。A正确 B错误 8.设矩阵A是一个对称矩阵,为了节约存储,将其下三角部分按行序存放在一维数组B1,n(n-1)/2中,对下三角部分中任一元素ai,j(i<=j),

23、在一组数组B的下标位置k的值是（ ）。Ai(i-1)/2+j-1 Bi(i-1)/2+j Ci(i+1)/2+j-1 Di(i+1)/2+j 二、填空题 1.己知二维数组Amn采纳行序为主方式存储,每个元素占k个存储单元,并且第一个元素的存储地址是LOC(A00),则A00的地址是_。2.二维数组A1020采纳列序为主方式存储,每个元素占一个存储单元,并且A00的存储地址是200,则A612的地址是_。3.有一个10阶对称矩阵A,采纳压缩存储方式(以行序为主,且LOC(A00)=1),则A85的地址是_。4.设n行n列的下三角矩阵A已压缩到一维数组S1.n*(n+1)/2中,若按行序为主存储,

24、则Aij对应的S中的存储位置是_。5.若A是按列序为主序进行存储的46的二维数组,其每个元素占用3个存储单元,并且A00的存储地址为1000,元素A13的存储地址为_，该数组共占用_个存储单元。三、算法设计 1.假如矩阵A中存在这样的一个元素Aij满意条件:Aij是第i行中值最小的元素,且又是第j列中值最大的元素,则称之为该矩阵的一个马鞍点。编写一个函数计算出1n的矩阵A的全部马鞍点。算法思想：依题意,先求出每行的最小值元素,放入minm之中,再求出每列的最大值元素,放入maxn之中,若某元素既在mini中,又在maxj中,则该元素Aij便是马鞍点,找出全部这样的元素,即找到了全部马鞍点。 2

25、.n只猴子要选大王,选举方法如下:全部猴子按1,2,.,n编号围坐一圈,从1号起先按1、2、.、m报数,凡报m号的退出到圈外,如此循环报数,直到圈内剩下只猴子时,这只猴子就是大王。n和m由键盘输入,打印出最终剩下的猴子号。编写一程序实现上述函数。 算法思想:本题用一个含有n个元素的数组a,初始时ai中存放猴子的编号i,计数器似的值为0。从ai起先循环报数,每报一次,计数器的值加1,凡报到m时便打印出ai值(退出圈外的猴子的编号),同时将ai的值改为O(以后它不再参与报数),计数器值重新置为0。该函数始终进行到n只猴子全部退出圈外为止,最终退出的猴子就是大王。因此,现本题功能的程序如下: 3.数

26、组和广义表的算法验证程序 编写下列程序: (1)求广义表表头和表尾的函数head()和tail()。(2)计算广义表原子结点个数的函数count_GL()。(3)计算广义表全部原子结点数据域(设数据域为整型之和的函数sum_GL()。#include “stdio.h“ #include “malloc.h“ typedef struct node int tag; union struct node *sublist; char data; dd; struct node *link; NODE; NODE *creat_GL(char *s) NODE *h; char ch; ch=*(

27、*s); (*s)+; if(ch!=0) h=(NODE*)malloc(sizeof(NODE); if(ch=() h->tag=1; h->dd.sublist=creat_GL(s); Else h->tag=0; h->dd.data=ch; else h=NULL; ch=*(*s); (*s)+; if(h!=NULL) if(ch=,) h->link =creat_GL(s); else h->link=NULL; return(h); void prn_GL(NODE *p) if(p!=NULL) if(p->tag=1) pr

28、intf(“(“); if(p->dd.sublist =NULL) printf(“ “); else prn_GL(p->dd.sublist ); else printf(“%c“,p->dd.data); if(p->tag=1) printf(“)“); if(p->link!=NULL) printf(“,“); prn_GL(p->link); NODE *copy_GL(NODE *p) NODE *q; if(p=NULL) return(NULL); q=(NODE *)malloc(sizeof(NODE); q->tag=p-&

29、gt;tag; if(p->tag) q->dd.sublist =copy_GL(p->dd.sublist ); else q->dd.data =p->dd.data; q->link=copy_GL(p->link); return(q); NODE *head(NODE *p) /*求表头函数 */ return(p->dd.sublist); NODE *tail(NODE *p) /*求表尾函数 */ return(p->link); int sum(NODE *p) /*求原子结点的数据域之和函数 */ int m,n; i

30、f(p=NULL) return(0); else if(p->tag=0) n=p->dd.data; else n=sum(p->dd.sublist); if(p->link!=NULL) m=sum(p->link); else m=0; return(n+m); int depth(NODE *p) /*求表的深度函数 */ int h,maxdh; NODE *q; if(p->tag=0) return(0); else if(p->tag=1p->dd.sublist=NULL) return 1; else maxdh=0; w

31、hile(p!=NULL) if(p->tag=0) h=0; else q=p->dd.sublist; h=depth(q); if(h>maxdh)maxdh=h; p=p->link; return(maxdh+1); main() NODE *hd,*hc; char s100,*p; p=gets(s); hd=creat_GL(p); prn_GL(head(hd); prn_GL(tail(hd); hc=copy_GL(hd); printf(“copy after:“); prn_GL(hc); printf(“sum:%dn“,sum(hd); p

32、rintf(“depth:%dn“,depth(hd); 第六章 树 一、选择题 1.在线索化二叉树中,t所指结点没有左子树的充要条件是（ ）。At-left=NULL Bt-ltag=1 Ct-ltag=1且t-left=NULL D以上都不对 2.二叉树按某种依次线索化后,任一结点均有指向其前趋和后继的线索,这种说法（ ）。A正确 B错误 C不怜悯况下答案不确定 3.二叉树的前序遍历序列中,随意一个结点均处在其子女结点的前面,这种说法（ ）。A正确 B错误 C不怜悯况下答案不确定 4.由于二叉树中每个结点的度最大为2,所以二叉树是一种特别的树,这种说法（ ）。A正确 B错误 C不怜悯况下答

33、案不确定 5.设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为（ ）。A2h B2h-1 C2h+1 Dh+1 6.已知某二叉树的后序遍历序列是dabec。中序遍历序列是debac,它的前序遍历序列是（ ）。Aacbed Bdecab Cdeabc Dcedba 7.假如T2是由有序树T转换而来的二叉树,那么T中结点的前序就是T2中结点的（ ） A前序 B中序 C后序 D层次序 8.某二叉树的前序遍历结点访问依次是abdgcefh,中序遍历的结点访问依次是dgbaechf,则其后序遍历的结点访问依次是（ ）。Abdgcefha Bgdbecfha Cbdgaec

34、hf Dgdbehfca 9.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法（ ）。A正确 B错误 C不怜悯况下答案不确定 10.根据二叉树的定义,具有3个结点的二叉树有（ ）种。A3 B4 C5 D6 11.在一非空二叉树的中序遍历序列中,根结点的右边（ ）。A只有右子树上的全部结点 B只有右子树上的部分结点 C只有左子树上的部分结点 D只有左子树上的全部结点 12.树最适合用来表示（ ）。A有序数据元素 B无序数据元素 C元素之间具有分支层次关系的数据 D元素之间无联系的数据 13.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序

35、（ ）。A不发生变更 B发生变更 C不能确定 D以上都不对 14.实现随意二叉树的后序遍历的非递归算法而不运用栈结构,最佳方案是二叉树采纳（ ）存储结构。A二叉链表 B广义表存储结构 C三叉链表 D依次存储结构 15.对一个满二叉树,m个树叶,n个结点,深度为h,则（ ）。An=h+m Bh+m=2n Cm=h-1 Dn=2h-1 16.假如某二叉树的前序为stuwv,中序为uwtvs,那么该二叉树的后序为（ ）。Auwvts Bvwuts Cwuvts Dwutsv 17.具有五层结点的二叉平衡树至少有（ ）个结点。A10 B12 C15 D17 二、推断题 1.二叉树中任何一个结点的度都是

36、2。（ ） 2.由二叉树结点的先根序列和后根序列可以唯一地确定一棵二叉树。（ ） 3.一棵哈夫曼树中不存在度为1的结点。（ ） 4.平衡二叉排序树上任何一个结点的左、右子树的高度之差的肯定值不大于2（ ） 三、填空题 1.指出树和二叉树的三个主要差别_,_,_。2.从概念上讲,树与二叉树是两种不同的数据结构,将树转化为二叉树的基本目的是_。3.若结点A有三个兄弟(包括A本身),并且B是A的双亲结点,B的度是_。4.若一棵具有n个结点的二叉树采纳标准链接存储结构,那么该二叉树全部结点共有_个空指针域。5.已知二叉树的前序序列为ABDEGCFHIJ,中序序列为DBGEAHFIJC,写出后序序列_。

37、6.已知二叉树的后序序列为FGDBHECA,中序序列为BFDGAEHC ,并写出前序序列_。7.找出满意下列条件的二叉树 1）先序和中序遍历，得到的结点访问依次一样。_。2）后序和中序遍历，得到的结点访问依次一样。_。3）先序和后序遍历，得到的结点访问依次一样。_。8.一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各是多少？_。9.一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有_个。10.含有100个结点的树有_条边。 四、问答题 1.一棵深度为h的满m叉树具有如下性质:第h层上的结点都是叶结点,其余各层上每个结点都有m棵非空子树。若按层次从上到下,

38、每层从左到右的依次从1起先对全部结点编号,试计算: (1)第k层结点数(1kh)。 (2)整棵树结点数。(3)编号为i的结点的双亲结点的编号。(4)编号为i的结点的第j个孩子结点(若有)的编号。2.证明：一个满k叉树上的叶子结点数n0和非叶子结点数n1之间满意以下关系： n0=（k-1）n1+1 3.已知一组元素为(50,28,78,65,23,36,13,42,71）,请完成以下操作: (1)画出按元素排列依次逐点插入所生成的二叉排序树BT。(2)分别计算在BT中查找各元素所要进行的元素间的比较次数及平均比较次数。(3)画出在BT中删除(23后的二叉树。4.有七个带权结点,其权值分别为3,7

39、,8,2,6,10,14,试以它们为叶结点构造一棵哈夫曼树(请根据每个结点的左子树根结点的权小于等于右子树根结点的权的次序构造,并计算出带权路径长度WPL及该树的结点总数。5.有一电文共运用五种字符a,b,c,d,e,其出现频率依次为4,7,5,2,9。(1)试画出对应的编码哈夫曼树(要求左子树根结点的权小于等于右子树根结点的权)。(2)求出每个字符的晗夫曼编码。(3)求出传送电文的总长度。(4)并译出编码系列1100011100010101的相应电文。五、算法设计 已知一棵具有n个结点的完全二叉树被依次存储在一维数组An中,试编写一个算法输出Ai结点的双亲和全部孩子。二叉树其他运算的算法（只

40、作参考） #include “stdio.h“ #include “malloc.h“ typedef struct node char data; struct node *lchild,*rchild; NODE; NODE *T; void create(NODE *T) /创建二叉树 char ch; ch=getchar(); if(ch= ) *T=NULL; else *T=(NODE *)malloc(sizeof(NODE); (*T)->data=ch; create(*T)->lchild); create(*T)->rchild); void inor

41、der(NODE *p) /中序编历二叉树 if(p!=NULL) inorder(p->lchild); printf(“%c “,p->data); inorder(p->rchild); int num=0; void count(NODE *p) /统计出二叉树中单孩子的结点数方法1 if(p!=NULL) count(p->lchild); if(p->lchild!=NULLp->rchild=NULL|p->lchild=NULLp->rchild!=NULL) num+; count(p->rchild); void cou

42、nt1(NODE *p,int *num1) if(p!=NULL) count1(p->lchild,num1); if(p->lchild!=NULLp->rchild=NULL|p->lchild=NULLp->rchild!=NULL) (*num1)+; count1(p->rchild,num1); int onechild(NODE *t) /统计出二叉树中单孩子的结点数方法2 int num1,num2; if(t=NULL) return(0); else if(t->lchild=NULLt->rchild!=NULL|t-&

43、gt;lchild!=NULLt->rchild=NULL) return(onechild(t->lchild)+onechild(t->rchild)+1); else num1=onechild(t->lchild); num2=onechild(t->rchild); return(num1+num2); int sum(NODE *t) /统计出二叉树中全部结点数 if(t=NULL) return(0); else return(sum(t->lchild)+sum(t->rchild)+1); int leaf(NODE *t) /统计出二叉树中叶子结点数 if(t=NULL) return(0); else if(t->lchild=NULLt->rchild=NULL) return(leaf(t->lchild)+leaf(t->rchild)+1); else return(leaf(t->lchild)+leaf(t->rchild); void preorder1(NOD