2015年珍藏答案

1、1)填空题：序号1-80【1 , 1 , 2】线性结构中元素之间存在一对一关系，树形结构中元素之间存在 一对多关系，图形结构中元素之间存在 多对多关系。【2，2】为了最快地存取数据元素，物理结构宜采用顺序存储结构。【3，2】数据结构的三要素是逻辑结构,物理结构操作 。【4,的有限集合1,2】数据的逻辑结构可形式地用一个二元组 ,R是 K上关系的有限集_。B= (K, R)来表示，其中 K是 数据元素顺序存储结构【5, 1 ,2】存储结构可根据数据元素在机器中的位置是否一定连续分为 链式存储结构。【6,1, 4】度量算法效率可通过时间复杂度来进行。【7, 出。1 , 4】算法的五个重要特性是确定

2、性、可行性有穷性、输入和输【8,1, 4】设n为正整数，则下面程序段的时间复杂度是0(n)。i=1; k=0;while(i< n)k=k+10*i ； i+；【9, 1 ,4】设n为正整数，下面程序段中前置以记号的语句的频度是for (i=0; i< n; i+)for (j=0; j< n; j+)if (i+j=n-1)aij=0;【10, 1,(1) i=1;while (i<=n-1) i+; k+=10 * i; /语句的频度是 k=0;for (i=1;i<=n;i+)n(n +1)/24】设n为正整数，试确定下列各程序段中前置以记号的语句的频度：k

3、=0;n-1for (j=i; j<=n;j+)k+;/语句的频度是n(n +1)/2.【11 , 1, 4】按增长率由大到小排列下列函数的结果是Iog2 (Iog2 n).2 1/2n n Iog2 n n nIog2 noIog2 (Iog2 n), n Iog2 n, n2, n1/2, Iog2 n, n【12,2,1】当线性表的规模比较大，难以估计其存储规模时，一般以采用 动态链表 存储结构为好。【13, 2, 1】线性表(a1, a2,，an)有两种存储结构:就这两种存储结构完成下列填充：顺序 存储密度较大；顺序存储利用率较高；可以随机存取；链式 插入和删除操作比较方便。顺序

4、存储结构和链式存储结构，请.顺序 可以随机存取:链式不【14, 2, 个元素。从一个长度为n的顺序表中删除第i个元素(K i于n寸，需向前移动n-i【15，2,带头结点的双链表L为空的条件是L->next=L 或 L->pnor=L【16,2,带头结点的单链表Head为空的条件是Head-next=NULL【17,2,非空单循环链表L中*p是尾结点的条件是p->n ext=L【18, 2,结点，应执行在一个单链表中s->n ext=p->n extp所指结点(p所指不是最后结点)之后插入一个由指针s所指;禾n p->next= s_ 的操作。【19 , 2,

5、 3】在一个单链表中的指针 P所指结点之前插入一个由指针s所指结点，可执行以下操作序列：s->next=p->next;p->n ext=s;t=p->data;p->data= s->data;s->data=t;【20, 2, 3】在一个单链表中删除P所指结点时，应执行以下操作:q= p->n ext;p->data= p->n ext->data;p->n ext= p-> next->next ;free(q);p所指结点的后继结点的语句是P->next【21 , 2 , 3】在单链表中，删除指针

6、P->n ext- >n ext：o【22 , 2, 3】带头结点的单循环链表 头结点的单循环链表的判空条件是Head 的判空条件是 _ Head->next = Head：; 不带Head = NULL： o【23, 2, 3】删除带头结点的单循环链表Head的第一个结点的操作是Head-next-next: ;删除不带头结点的单循环链表的第一个结点的操作是Head->nextHead = Head->n ext:o【24 , 2, 3】已知L是带表头结点的非空单链表 ，且P结点既然不首元结点 试从下列提供的答案中选择合适的语句序列。a.删除P结点的直接前驱结点

7、的语句序列是，也不是尾元结点，10 1281141410127314ob. 删除结点P的语句序列是911314c. 删除尾元结点的语句序列是(1) P = P-> next：(2) P->next = P：(3) P->next = P->n ext ->n ext： P = P->next ->n ext： while (P != NULL) P = P-> next： while (Q-> next != NULL) P = Q： Q = Q-> next： while (P-> next != Q) P = P->

8、next：(8) while (P-> next-next != Q) P = P-> next：(9) while (P->n ext-> next != NULL) P = P-> next：(10) Q = P：(11) Q = P-> next：(12) P = L：(13) L = L-> next：(14) free (Q)：【25 , 3, 1】栈操作的原则是先进后出/后进先出【26 , 3, 1】对一个栈，给定输入的顺序是A、B C,则全部不可能的输出序列有不可能得到的输出序列有 CAB o【27 , 3, 1】数据A、B、C、D依次进

9、栈后，再从栈中取一数据，则它是 则本栈得到 DCBA的输出序列， 其理由是 根据后讲先出的原则， 首先得到 D,在栈内的数由底到顶依 次是A、B C而出栈的次序刚好相反，即 DCBAo o【28 ,3 ,1】.在栈顶指针为 HS的链栈中，判定栈空的条件是head->next=NUII8【29 , 3, 1】将递归算法改写成等价的非递归算法，通常应该设置堆栈的数据结构【30, 3, 2】下列程序把十进制数转换为十六进制数，请填写合适的语句成分。void con versio n10_16()(每空2分)In itStack(&s); scanf(“ d' ，&N);

10、while(N) Push(s, N%16)_N = N/16; while(!StackE mp ty(s) Pop(s, e)if(e<=9)printf(“ d' ,e);else printf(“1%+'A；e);/* conversion */【31 ,元素是3 , 4】若一个栈的输入序列为1,2,3, - ,n输出序列的第一个元素为n i+ 1 on,则第i个输出【32 , 3, 4】若用一个大小为 6个元素的数组来实现循环队列，且当前当从队列中删除一个元素， 再加入两个元素后，rear和front的值分别是rear=0 禾R front=3。2 和 4【33

11、, 3, 4】已知一个栈的输入序列为1, 2, 3,，n,输出序列为a1,a2,a3,盟那么a2=n的输出序列共有 n-1种。【34 ,3 ,4】堆栈和队列都是线性表，堆栈是列是的线性表，而队 的线性表。_后进先出 先进先出【35 , 3 , 4】从循环队列中删除一个元素时，其操作是 素先移动队首元素，后取出元【36 , 3, 4】若用一个大小为 6个元素的数组来实现循环队列，且当前 当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是4rear=0 禾R front=3。2和,o【37, 3, 4】下面是关于循环队列的操作，请在划线空白处填写合适语句成分。Status E

12、n Queue(SqQueue &Q, QelemT ype e)if( (Q.rear+1)%MAXSIZE=Q fro nt) ERROR;Q.base(Q.rear) = e;)retrunQ.rear= (Q.rear+1)%MAXSIZE return OK; / En Queue【38 , 4, 1】空串是 零个字符的串，其长度为零 。【39 , 4 , 1 】 设串 S仁” teachers and “ ,s2= ” student则"StrLength(s2)=Con cat(s1,s2)="teachers and stude nts ” o【40

13、, 4, 1 】设 s = AM A TEACHER 其长度是 14【41 , 4, 1】两个串相等的充分必要条件是 同两个串的长度相等且对应位置的字符相顺序存储方式和链接存储方【42 , 4 , 2】串的两种最基本的存储方式是 式【43, 4, 3】令有串 u=" aabcaab和 v=" abcaabcaabcaaba",(1) 求 Index(v,u,5)的值：Index(v,u,5)=8; (2 分)(2) 求出u作为模式串时在 KMP算法中的nextj值。(2分)j1234567uaabcaabn extj0121123【44 , 5, 1】二维数组 A

14、1020采用列序为主方式存储，每个元素占一个存储单元，并且A00的存储地址是 200,则A610的地址是 332 o【45 , 5, 1】设每个元素需要 8个字节，顺序存储100个元素，若首地址是2500 ,那么第50 个元素的地址是2892【46 , 5, 2】已知二维数组 Amn采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A00)，则Aij的地址是 LOC (A00) + (n*i + i) k【47 , 5, 2】C语言采用行优先方式存放数组元素，数组下标从0开始。设维数为(5,6,7)的数组 A5x6x7的起始存储地址为Loc000=1000，每个数

15、组元素占用4个字节。则元素A444所在的地址 Loc444= 1800【48 , 5, 2】按行优先次序列出三维数组A232的所有12个元素在内存中的存储次序,它们依次是：A000A001A010A011A020A021A100A101A110A111A120A121【49，5，3】对一个10阶对称矩阵A,采用压缩存储方式(以行序为主序，且A00的地址为1)，则A85的地址是34 o【50, 5,地址为1 ,3】对一个10阶三对角矩阵 A,采用压缩存储方式(以行序为主序，且A00的每个元素占4个字节),则A65的地址是 69 o【51，5，组S1.M中(以行序为主序，且A00=S1),则Aij

16、 (i>=j)对应S中的下标是 + j+1;维数组 S的大小 M至少为(n +1)*(n+1)3】对一个对称矩阵A( aj=aji,0<=i,j<=n)，采用下三角压缩存储方式存储在一维数i*(i+1)/2【52 , 6, 1】已知一棵树边的集合是<a,d><d,c>,<d,j>,<e,a>,<f,g><d,b>,<g,h>,<g,i>,<e,f>o 那么根结点是e，结点 b的双亲是d ，结点 a的子孙有 bcdj，树的深度是4树的度是 3 ，结点g在树的第3层。【53

17、, 6,2】通常使用二叉链表来表示二叉树结构。【54，6,目的是_题【55,叉树，6, 2】在图1至图5中,1,2,3,4,5123是完全二叉树，是树,1,3123,4是二是满二叉树。AB2】从概念上讲，树与二叉树是二种不同的数据结构，将树转化为二叉树的基本的.树可采用二叉树的存储结构并利用二叉树的已有算法解决树的有关问6【56 , 6, 3】在图4中，结点H在这棵树的前序、中序和后序遍历次序中分别是 第 5 和第 3 个结点。【57, 6, 2】 结点。满三叉树的第i层的结点个数为3i-1，深度为h时该树中共有h .3-1【58， 6, 2】 B是G的在图4中，A是_根_结点,.祖先,D是E

18、的兄弟_D是叶子结点,。这棵树的度是6B是E的_父亲，深度是_4_【60，编号， 号结点的双亲结点是6, 2】根结点为 1号。则该完全二叉树总共结点有 111 .45号；第63号结点的左孩子结点是【61 , 6, 2】下列表示的图中,共有5个是树；有 _3个是二叉树；有 _2.【59，6, 2】程序填空：下列算法是求以二叉链表存储的二叉树中的最小值，设数据域的类 型为int ovoid minno de(BiTree T, int *min)if(T!=NULL)if( *min>T->data ) *min = T->data; mi nno de(T->lchild

19、,mi n);minnode(T->rchild,min);已知一棵完全二叉树有 56个叶子结点，从上到下、从左到右对它的结点进行个；有7_层；第91号O个是完全二叉树。【62 , 6 , 3】下列二叉树的中序遍历序列是DBNGOAEC；后序遍历序列是DNIGBECA先序遍历的序列中的第一个元素是【63，6，3】一棵二叉树的中序遍历序列是DBNGOAEC后序遍历序列是 DNOGBECA则其A _，第五个元素是_N_，最后一个元素是_E_【64 , 6, 3】下列二叉树的先序遍历序列的第5个结点是 N_;第8个结点是_E.后序遍历序列的第 2个结点是_N;第6个结点是_E_O【65，6，3

20、】如果某二叉树的后序遍历序列是 其先序遍历序列的第一个字母是【66，6, 3】程序填空：设算法历算法。下列算法是判断无向图int isc onn ect(Mgra ph *G) int i,k=0;ABCDEFGHJ中序遍历序列是 ACBIDFEHG则I，最后一个字母是 G oDFS(Mgraph *G, int i)是无向图G从i顶点开始的深度优先遍G是否是连通的。for(i=0; i<G->vex num; i+) visitedi = 0;for(i=0; i<G->vex num; i+) if(!visitedi)k+；DFS(G, i);return 1 i

21、f(k=1)else return 0;【67,2】图有邻接矩阵和 邻接表 等存储结构。【68,等于【69 , 7, 2】若一个图用邻接矩阵表示, 列非零元素之和。则计算第i个结点的入度的方法是求矩阵第i【70 ,乙2】若一个图用邻接矩阵表示, 阵第i行全部置为零。则删除从第i个顶点出发的所有边的方法是【71，7，4】n个顶点的连通图至少有条边。2】设无权图G的邻接矩阵为A,若（vi,vj）属于图G的边集合，则对应元素 Aij ，设无向图G的邻接矩阵为A,若Aij等于0,则Aji等于 0 o【72 ,乙4】设一个图G=V,A,V=a,b,c,d,e,f,A=<a,b><b,e

22、><a,e><c,a><e,d><d,f><f,c>。那么顶点 e 的入度是2;出度是 1;通过顶点f的简单回路有2 条；就连通性而言，该图是强连通 图；它的强连通分量有1 个；其生成树可能的最大深度是5_ Ov3 v3【73 ,乙5】下面有向图共有 4_个顶点；从v3到v2的最短简单路径之一是v4 v2; v1的出度是_2;包含所有顶点的简单路径之一是O【74 , 9, 2】n个结点的二叉排序树的最大深度是n，最小深度为log 2n+1【75 ,9, 3】设有一组关键字9,01,23,14,55,20,84,27，采用哈希函数

23、:H(key)=key mod 7,表长为10，用开放地址法的二次探测再哈希方法Hi=(H(key)+di) mod 10(di = 12,22,32，,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找 长度。【76, 10,1】排序过程一般需经过两个基本操作，它们是比较 和 移动 。哈希 地址0123456789关键字140192384275520比较 次数11123412平均查找长度： ASL = (1+1+1+2+3+4+1+2)8 = 158以关键字 27 为例，H(27)=27%7=8(冲突)，H1=(6+1)%10=7(冲突)，H2=(6+22)%10=0(冲突

24、)， H3=(6+33)%10=5，所以比较了 4 次。【77, 10,如果采用(A,B,D,C,E) O2】结点的关键字序列是(F,B,J,G,E,A,I,D,C,)对它按字母的字典序进行排列。Shell排序方法，那么步长取5时，第一次扫描结果的前5个字母分别是【78 , 10, 2】在对一组关键字是(54,38,96,45,15,72,60,23,83 )的记录进行直接插入排序时,当把第七个记录(关键字是60 )插入到有序表时，为寻找插入位置需比较3次。54,38,96,45,15,72,60,23,83 )的记录进(设第一次调用深度为1)为 3:(23, 38, 15, 45)的一组【7

25、9，10，3】在利用快速排序方法对一组关键字是( 行排序时，需要递归调用partition函数，递归的最大深度 共需5次递归调用，其中第二次递归调用是对关键字是 记录进行的。【80，10, 4】插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序、和基数排 序方法中，不稳定的排序方法有希尔排序、快速排序、堆排序4)分析计算作图题：序号1-55 (选自数据结构题集 一严蔚敏等编)【1,1, 4】(选自数据结构题集1.8,选做题)设n为正整数，试确定下列各段程序中前置以记号的语句的频度(语句的频度指的是该语句重复执行的次数)。(1)i=1; k=0;while (i<=n-1)i+;k+

26、=10*i;答：该语句的频度为n-1(2)x=91;y=100;while(y>0)if(x>100) x-=10; y-;else x+;答：在循环中，if语句为真1次，else语句执行10次，所以if语句执行11次y的值减1。该语句的频度为100x(1+10) = 1100【2,1, 4】(选自数据结构题集1.9,选做题)假设n为2的乘幕，并且n>2,试求下列算法的时间复杂度及变量count的值(以n函数形式表示)int Time (int n) count =0; x=2;while( x<n/ 2 )x*=2; cou nt+;return (cou nt);

27、/ Time答：从while的循环控制可以看出，n每增加一倍,count的值增加1。所以该算 法的时间复杂度为 O(log2 n),根据初值，变量count的值为Iog2 (n-2)-1【3，2, 3】(选自数据结构题集2.6,必做题)已知L是无表头结点的单链表，且P既不是首元结点，也不是尾元结点，试 从下列提供的答案中选择合适的语句序列。(4) (1)(7) (11) (8) (4) (1)(5) ( 12) (9) (1) ( 6)a.在P结点后插入S结点的语句序列是 b 在P结点前插入S结点的语句序列是 C.在表首插入S结点的语句序列是 _ d .在表尾插入S结点的语句序列是 _(1)

28、P > n ext = S ;(2) P> n ext = P -> next(3) P> n ext = S -> next;(4) S> n ext = P -> next;(5) S> n ext = L;(6) S> n ext = NULL;(7) Q=P；> n ext;(8)while(P -> next ! = Q) P = P> n ext;(9)while(P -> next ! = NULL) P :=P > next;(10)P =Q;(11)P =L；(12)L =S；(13)L =P

29、;【4,2,2】(:选自数据结构题集2.10,选做题)指出以下算法中的错误和低效(即费时)之处，并将它改写为一个既正确又 咼效的算法。Status DeleteK ( SqList &a, int i , int k) /本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素if (i < 1 II k < 0 II i + k > a.length ) return INFEASIBLE; / 参数不合法 else for (count = 1; count < k ; count + ) /删除一个元素for (j = a.Iength ； j >

30、= i +1 ； j) a.elem|j 1 = a.elemj；a. len gth;return OK ; / DeleteK答：错误之处：题中有下划线处应改为：for (j = i+1; j <= a.length； j+)a.elemj 1 = a.elemj;低效费时之处：该算法每删除一个元素，其后所有的元素都向前移一位，包括 将要删除的元素，比较耗时间。(其中n = a.length)下 划 线 的 语 句 的 频 度 为n i + (n i !+ ' + d i k +1 = kfn i) k(k1)/2改进方法是将k个元素在一个循环内删除，算法如下：Status

31、DeleteK (SqList &a, int i，int k) /本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素if (i < 1| k < 0 | i + k > a.length) return INFEASIBLE / 参数不合法else for (count = 0; count < a.length k i； count +)a.elemi-1+ count = a.elemk + i-1 + cou nt ；/删除k个元素a.le ngth = a.le ngth k；return OK； / DeleteK5， 3，1】（选自数据结构

32、题集 3.4，必做题）简述以下算法的功能（栈的元素类型SElemType为int）（ 1 ） Status algo1 （ Stack S） int i， n ， A255 ;StackEmpty (S) n +；Pop (S， An )；1; i < = n ; i +) Push (S, Ai);n = 0;whilefor （ i 功能：利用数组A，将栈中所有的元素倒置。Stack S，int e) int d ； (T)；StackEmpty2) Status algo2 Stack T； InitStack while (！ Pop(S，d)；if (d != e) Pushw

33、hile (！ StackEmpty Pop( T， d)； Push( S， d)；S）T，d）；T） 功能：将栈S中与e相同的元素删除。6，3,1】（选自数据结构题集 3.15,选做题） 假设以顺序存储结构实现一个双向栈, 即在一堆数组的存储空间中存在着两 个栈,它们的栈底分别设在数组的两个端点。 试编写实现这个双向栈 tws 的三个 操作：初始化 inistack （tws）、入栈 push （tws, i, x）和出栈 pop （tws, i）的算 法，其中 i 为 0 或 1，用以分别指示设在数组两端的两个栈，并讨论按过程（正/误状态变量可设为变参）或函数设计这些操作算法各有什么优缺

34、点。typedef struct SElemType *base2;SElemType *top2;int stacksize; SqStack;/ 初始化，构造一个空栈 twsbaseO = ( SEIemType *) malloc (STACK_INIT_SIZE * sizeo();tws.base0 )exit ( OVERFLOW ;/ 存储分配失败stacksize = STACK_INIT_SIZEbase1 = tws. base0 + tws.stacksize 1;Status initstack （ SqStack &tws） tws.if（！twstws.tw

35、s topOtws top1 returnOK； / initstack=tws. baseO;=tws. base1;Status push( SqStack &tws， int i ，ElemType x) / 插入元素 x 为新的栈顶元素- base1 >= tws.stacksize)if(tws.topO baseO + tws.top1/ 栈满，追加存储空间incrementO = tws.topO baseO;increment1 = tws.top1 base1;>=/ 0端的元素个数/ 1端的元素个数tws . baseO = ( SEIemType *)

36、 realloc (tws.base0 ,(tws.base0+STACKINCREMENT) * sizeo(f ElemType)； if(！ tws.base0 ) exit( OVERFLOW)； / 存储分配失败 tws.stzcksize += STACKINCREMENT;temp=tws.base1;tws. base1 = tws . base0 + tws.stacksize- 1; for(i=0; i<increment1; i+)*(tws.base1 - i) =tws . top0 = tws.tws . top 1 = tws .*(temp - i);/

37、把1端栈中元素移到新的双向栈的1端baseO + incrementO;base1 - increment1;if(i)* tws.top1 - = x ；else* tws.topO + = x ； return OK; / pushStatus/ififpop ( SqStack &tws， int i )若栈不空，则删除tws的栈顶元素，并返回 OK;否则返回ERROR(tws.to p0 = base0 | tws.to p1= base1) return ERROR;i)+ tws.top1 ;else tws.topO ； return OK； / pop7， 3，4】(选

38、自数据结构题集 3.13，必做题) 简述以下算法的功能(栈和队列的元素类型均为 int ) void algo3(Queue &Q)Stack S; int d;InitStack (S);while (!QueueEmpty (Q) DeQueue (Q, d); Push (S,d);while (!StackEmpty (S) Pop (S, d); EnQueue(Q, d);答：将队列Q中的元素变成倒置排列。【8，3， 2】(选自数据结构题集 3.19，选做题)假设一个算术表达式中可以包含三种括号：圆括号“ (”和“)”，方括号“ ” 和“ ”和花括号“ ”和“ ”，且这三种

39、括号可以按任意的次序嵌套使用(如：()。编写判别给定表达式所含括号是 否正确配对出现的算法(已知表达式已存入数据元素为字符的顺序表中) 。 解：算法如下：Status MatchBrackets ( ) SqStack &S;n')'&& GetTop (S)= c= ' c=' 判断括号是否匹配InitStack (S);('| '| ' ) )while (c=getchar()!=if(!StackEmpty (S) && (c=&& GetTop (S)=&&

40、 GetTop (S)=； / 判断是否是括号Pop (S); / else if(IsLeftBracket(c) Push (S, c)if(!StackEmpty(S) return ERROR; else return TRUE;必做题)'WORKER 求:9， 4，1】(选自数据结构题集 4.3，设 s =I AM A STUDENT',t = GOO'D,q = StrLength(s), StrLength(t), SubString(s,8,7), SubString(t,2,1), Index(s, A'), Index(s, t), Repl

41、ace(s,STUDEN'T,q ),O',Concat(SubString(s,6,2),Concat(t,SubString(s,7,8) 答： StrLength(s) = 14, StrLength(t) = 4, SubString(s,8,7) =STUDEN'T, SubString(t,2,1) =Index(s, A') = 3, Index(s, t) = 0, Replace(s, STUDEN'T,q ) =I AM A WORKER',Concat(SubString(s,6,2),Concat(t,SubString(

42、s,7,8) =A GOOD STUDE'NT10， 5，1】(选自数据结构题集 5.1，必做题)假设有两维数组A6X8，每个元素用相邻的6个字节存储，存储按字节编址。 已知A的起始地址为1000,计算：(1) 数组A的存储量；=6x8x6 = 288字节)(2) 数组A的最后一个元素a57的第一个字节的地址；=1000+288-6=1282按行存储时，元素ai4的第一个字节的地址；=1000+(8x1+4)x6=1072 按列存储时，元素347的第一个字节的地址；=1000+(7x6+4)x6=12766, 11 (选自数据结构题集6.1,必做题)已知一棵树边的集合为VI, M>

43、;, <I, N>, <E, I>, <B, E>, <B, D>, <A, B>, vG, J>, vG, K>, VC G>, vC, F>, vH, 并回答下列问题：(1)(2)(3)(4)(5)(6)(7)(8)(9)【11,哪个是根结点？ 哪些是叶子结点？ 哪个是结点 哪些是结点 哪些是结点 哪些是结点 哪些是结点G的双亲？G的祖先？G的孩子？E的子孙？E的兄弟？哪些是结点结点B和N的层次号分别是什么？ 树的深度是多少？(10)以结点C为根的子树的深度是多少 解：这棵树为：<M) IN)所以，根

44、结点为A;叶子结点是D, M , 结点G双亲为C；N,L>, <C, H>, <A, C>,请画出这棵树,F的兄弟?J <K) CL；(JiF, J, K,L；结点G的祖先为A, C； 结点E的子孙为I, M., 结点E的兄弟有D,结点F的兄弟有 结点B和N的层次号分别是2, 5； 树的深度是5；以结点C为根的子树的深度为3。N；G, H;【12, 6 , 11 (选自数据结构题集6.4 ,一棵深度为H的满k叉树有如下性质第层上每个结点都有k棵非空子树。如果按层次顺序从1开始对全部结点编号，问:(1) 各层的结点数目是多少？(2) 编号为P的父结点(若存在)

45、的编号是多少？选做题)H层上的结点都是叶子节点，其余各（3）编号为p的结点的第i个儿子结点（若存在）的编号是多少？（4）编号为P的结点有右兄弟的条件是什么？其右兄弟的编号是多少?解：（1）各层的结点数为k"' （n= 1, 2,，H）;（2）首先，p = 1时，没有父结点，pl时，通过归纳可得，编号为a的结点，它的所有子结点的编号为从*匕一町+ £至衣3 + 1,贝U编号为P的结点的父结点为(3)由上可得，第i个儿子结点的编号为kCp-O+a+i-i；(4)P有右兄弟，即P不为最右的结点，条件为，右兄弟的编号为p+ 1 0【13, 6, 21 （选自数据结构题集6.

46、5,选做题）已知一棵度为k的树中有6个度为1的结点，口:个度为2的结点，个 度为k的结点，问该树中有多少个叶子结点？ 解：设结点总数为n,则有n= n0+n1+n2+nk,因为除了根结点外，所有结点都有边进入，所以有n=B+1,而B = 1*n 1+2*n2+k*nk =刀i*ni 所以有 no+n 1+02+-+ nk = 刀 i*ni + 1 no = E（ i-1） *ni + 1【14, 6, 31 （选自数据结构题集6.13，必做题） 假设n和m为二叉树中的两结点，用“ 1 ”、“0”、“”（分别表示肯定、恰 恰相反或者不一定）填写下表：已知问答：前序遍历时 n在m前？中序遍历时 n

47、在m前？后序遍历时 n在m前？n在m左方111n在m右方000n是m祖先10n是m子孙01注：如果（1）离a和b最近的共同祖先P存在，且（2） a在p的左子树中，b 在P的右子树中，则称a在b的左方（即b在a的右方）【15, 6，31 （选自数据结构题集6.14，选做题） 找出所有满足下列条件的二叉树：（a）它们在先序遍历和中序遍历时，得到的结点访问序列相同；（b）它们在后序遍历和中序遍历时，得到的结点访问序列相同；（C）它们在先序遍历和后序遍历时，得到的结点访问序列相同； 答：（a）除叶子结点外所有结点都只有右孩子的树或只有根结点的树;（b）只有根结点以及除叶子结点外所有结点都只有左孩子的树

48、；（C）只有根结点的树。【16, 6, 4】（选自数据结构题集6.19,必做题） 分别画出和下列树对应的各二叉树：(a)(b)(c)E(d)答：用孩子兄弟表示法将树表示成二叉树, 子结点和下一个兄弟结点，表示如下：二叉树的左右结点分别为第一个孩a:b:BC：【17,6,画出和下列已知序列对应的树T树的先根次序访问序列为GFKDAIEBCHJ 树的后根次序访问序列为DIAEKFCJHBG 解：对应的树如下：3】（选自数据结构题集6.23,选做题）6.26，必做题）【18，6, 5】（选自数据结构题集假设用于通信的电文仅有 8个字母组成，字母在电文中出现的频率分别为 0.07，0.19，0.02，

49、0.06，0.32，0.03，0.21，0.10试为这 8 个字母设计哈夫曼编 码。使用0-7的二进制表示形式是另一种编码方案。对于上述实例，比较两种 方案的优缺点。解：哈夫曼编码树如下：O0 1C n0 1 0厂1-f一二 O1 w 1所以编码如下:字母0.070.190.020.060.320.030.210.10编码1010001000010011110001011011带权路径长度 WPL= 0.19X 2+ 0.21 X 2+ 0.02X 5 + 0.03X 5+ 0.06X 4 + 0.07X 4 + 0.10X4+ 0.32X 2 = 2.61，而采用等长编码时，每个字母至少 3位，故带权路 径长度WPL= 3.采用哈夫曼编码