数据结构习题解答

1、数据结构习题解答第1章 绪论一、基本内容数据、数据元素、数据对象、数据结构、存储结构和数据类型等概念术语的确定含义；抽象数据类型的定义、表示和实现方法；描述算法的类C语言；算法设计的基本要求以及从时间和空间角度分析算法的方法。二、学习要点1熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。2了解抽象数据类型的定义、表示和实现方法。3熟悉类C语言的书写规范，特别要注意值调用和引用调用的区别，输入、输出的方式以及错误处理方式。4理解算法五个要素的确切含义：动态有穷性（能执行结束）；确定性（对于相同的输入执行相同的路径）；

2、有输入；有输出；可行性（用以描述算法的操作都是足够基本的）。5掌握计算语句频度和估算算法时间复杂度的方法。三、基础知识题1.1 简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。答：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对象是性质相同的数据元素的集合，是数据的一个子集。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。存储结构是数据结构在计算机中的表示（又称映像）。数据类型是一个值的集合和定义在这个值集上的一组操作的总

3、称。抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。程序设计语言中的数据类型是一个值的集合和定义在这个值集上的一组操作的总称。而抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。1.8 设n为正整数，试确定下列各程序段中前置以记号的语句的频度。（1）i=1; k=0;while (i=n-1) k + =10 * i; i+ +; 答：n-1（2）i=1; k=0; d

4、o k + =10 * i; i+ +; while (i=n-1);答：（3）i=1; k=0;while (i=n-1) i+ +; k + =10 * i;答：n-1（4）k=0;for ( i=1; i=n; i+ +) for (j=i; j=n; j+ +) k+ +; 答：（5）for ( i=1; i=n; i+ +) for (j=i; j=i; j+ +) for (k=1; k=j; k+ +) x+ =delta; 答：（6）i=1; j=0;while (i+jj) j+ +; else i+ +; 答：n（7）x=n; y=0;while (x=(y+1)*(y+1

5、) y+ +; 答：（8）x=91; y=100;while (y0) if (x100) x- =100; y- -; else x+ +; 答：1100四、算法设计题1.16 试写一算法，自大至小依次输出顺序读入的三个整数X，Y，Z的值。答：void print_descending(int x,int y,int z)/按从大到小顺序输出三个数 scanf(%d,%d,%d,&x,&y,&z); if(xy)temp=x; x=y; y=temp; if(y=temp) y=temp; else y=x; x=temp; printf(%d %d %d,x,y,z);/print_des

6、cending五、附加题5.1填空题1.数据结构是一门研究非数值计算的程序设计问题中计算机的 以及它们之间的 和运算等的学科。操作对象，关系2. 数据结构被形式地定义为（D, R），其中D是 的有限集合，R是D上的 有限集合。数据元素，关系3. 数据结构包括数据的 、数据的 和数据的 这三个方面的内容。4. 数据结构按逻辑结构可分为两大类，它们分别是 和 。线性结构，非线性结构5. 线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 关系。一对一，一对多，多对多6数据的存储结构可用四种基本的存储方法表示，它们分别是 。顺序存储结构，链式存储结构，索引存储结构，散

7、列存储结构7. 一个算法的效率可分为 效率和 效率。时间，空间5.2 选择题（ ）1.线性结构是数据元素之间存在一种：DA一对多关系 B多对多关系 C多对一关系 D一对一关系（ ）2. 数据结构中，与所使用的计算机无关的是数据的 结构。CA存储 B物理 C逻辑 D物理和存储（ ）3. 算法分析的目的是：CA找出数据结构的合理性 B研究算法中的输入和输出的关系C分析算法的效率以求改进 D分析算法的易懂性和文档性（ ）4. 计算机算法指的是：CA计算方法 B排序方法 C解决问题的有限运算序列 D调度方法（ ）5. 计算机算法必须具备输入、输出和 等5个特性。BA可行性、可移植性和可扩充性 B可行性

8、、确定性和有穷性C确定性、有穷性和稳定性 D易读性、稳定性和安全性第2章 线性表一、基本内容线性表的逻辑结构定义、抽象数据类型定义和各种存储结构的描述方法；在线性表的两类存储结构（顺序的和链式的）上实现基本操作；稀疏多项式的抽象数据类型定义、表示和加法的实现。二、学习要点1了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。2熟练掌握这两类存储结构的描述方法，如一维数据中一个区域i.j的上、下界和长度之间的变换公式（L=j-i+1,i=j-L+1,j=i+L-

9、1）,链表中指针P和结点*p的对应关系（结点*(p-next)是结点*p的后继等），链表中的头结点、头指针和首元结点的区别及循环链表、双向链表的特点等。链表是本章的重点和难点。扎实的指针操作和内在动态分配的编程技术是学好本章的基本要求。3熟练掌握线性表在顺序存储结构上实现基本操作：查找、插入和删除的算法。4熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构。了解静态链表，能够加深对链表本质的理解。5能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。三、基础知识题2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）

10、。答：首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是当对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。这3个概念对单链表、双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。2.2 填空题1. 在顺序表中插入或删除一个元素，需要平均移动 元素，具体移动的元素个数与 有关。

11、答：表中一半，表长和该元素在表中的位置2. 顺序表中逻辑上相邻的元素的物理位置 相邻。单链表中逻辑上相邻的元素的物理位置 相邻。答：必定，不一定3. 在单链表中，除了首元结点外，任一结点的存储位置由 指示。其前驱结点的链域的值4在单链表中设置头结点的作用是 。插入和删除首元素时不必进行特殊处理2.6 已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。a.在P结点后插入S结点的语句序列是 。4，1b.在P结点前插入S结点的语句序列是 。7，11，8，4，1c.在表首插入S结点的语句序列是 。5，12d.在表尾插入S结点的语句序列是 。9，

12、1，6（1）P-next=S;（2）P-next=P-next-next;（3）P-next=S-next;（4）S-next=P-next;（5）S-next=L;（6）S-next=NULL;（7）Q=P;（8）while (p-next!=Q) P=P-next;（9）while (P-next!=NULL) P=P-next;（10）P=Q;（11）P=L;（12）L=S;（13）L=p;2.7 已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。a.删除P结点的直接后继结点的语句序列是 。11，3，14b.删除P结点的直接前

13、驱结点的语句序列是 。10，12，8，11，3，14c.删除P结点的语句序列是 。10，12，7，3，14d.删除首元结点的语句序列是 。12，11，3，14e.删除尾元结点的语句序列是 。9，11，3，14（1）P=P-next;（2）P-next=P;（3）P-next=P-next-next;（4）P=P-next-next;（5）while (P!=NULL) P=P-next;（6）while (Q-next!=NULL) P=Q; Q=Q-next;（7）while (P-next!=Q) P=P-next;（8）while (p-next-next!=Q) P=P-next;（9

14、）while (P-next-next!=NULL) P=P-next;（10）Q=P;（11）Q=P-next;（12）P=L;（13）L=L-next;（14）free(Q);2.8 已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。a.在P结点后插入S结点的语句序列是 。7，12，3，6b.在P结点前插入S结点的语句序列是 。8，13，5，4c.删除P结点的直接后继结构的语句序列是 。15，1，11，18d.删除P结点的直接前驱结点的语句序列是 。16，2，10，18e.删除P结点的语句序列是 。9，14，17（1）P-next=P-next-next;（2）P-

15、priou=P-priou-priou;（3）P-next=S;（4）P-priou=S;（5）S-next=P;（6）S-priou=P;（7）S-next=P-next;（8）S-priou=P-priou;（9）P-priou-next=P-next;（10）P-priou-next=P;（11）P-next-priou=P;（12）P-next-priou=S;（13）P-priou -next =S;（14）P-next-priou=p-priou;（15）Q=P-next;（16）Q=P-priou;（17）free(P);（18）free(Q);2.7 简述以下算法的功能。（1）

16、 Status A(LinkedList L) /L是无表头结点的单链表 if (L&L-next) Q=L; L=L-next; P=L; While (P-next) P=P-next; P-next=Q; Q-next=NULL; return OK; /A答：如果L的长度不小于2，则将首元结点删去并插入到表尾。（2） void BB(LNode *s, LNode *q) p=s;while (p-next!=q) p=p-next;p-next=s; /BBvoid AA(LNode *pa, LNode *pb) /pa和pb分别指向单循环链表中的两个结点BB(pa,pb);BB(

17、pb,pa); /AA 答：将s至q之前的结点组成一个新的单循环链表，将q断开。四、算法设计题2.11设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。答：Status Insert_SqList(SqList &va,int x)/把x插入递增有序表va中 if(va.length+1va.listsize) return ERROR; va.length+; for(i=va.length-1;va.elemix&i=0;i-) va.elemi+1=va.elemi; va.elemi+1=x;return OK; /Insert_SqLis

18、t2.13 试写一算法在带头结点的单链表结构上实现线性表操作LOCATE(L,X)。答：LNode* Locate(LinkList L,int x)/链表上的元素查找,返回指针for(p=l-next;p&p-data!=x;p=p-next);return p;/Locate2.14 试写一算法在带头结点的单链表结构上实现线性表操作LENGTH（L）。答：int Length(LinkList L)/求链表的长度for(k=0,p=L;p-next;p=p-next,k+);return k;/Length4已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中

19、所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删结点空间，并分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。5已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不相同），同时释放被删结点空间，并分析你的算法的时间复杂度。6试写一算法，实现顺序表的就地逆置，即得用原表的存储空间将线性表(a1,a2,a3,an)逆置为(an,an-1a1)。7试写一算法，对单链表实现就地逆置。答：void LinkList_rever

20、se(Linklist &L)/链表的就地逆置;为简化算法,假设表长大于2p=L-next;q=p-next;s=q-next;p-next=NULL;while(s-next)q-next=p;p=q;q=s;s=s-next; /把L的元素逐个插入新表表头q-next=p;s-next=q;L-next=s;/LinkList_reverse五、附加题5.1 判断正误（ ）1. 链表的每个结点中都恰好包含一个指针。 对（ ）2. 链表的物理存储结构具有同链表一样的顺序。错 （ ）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。 错（ ）4. 线性表

21、的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。错（ ）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 错（ ）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。错（ ）7. 线性表在物理存储空间中也一定是连续的。错（ ）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。错（ ）9. 顺序存储方式只能用于存储线性结构。错（ ）10. 线性表的逻辑顺序与存储顺序总是一致的。对4.2 单项选择题（ ）1数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：CA存储结构 B逻辑结构 C顺序存储结构 D链式存储结构

22、（ ）2. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 BA110 B108 C100 D120（ ）3. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：AA访问第i个结点（1in）和求第i个结点的直接前驱（2in） B在第i个结点后插入一个新结点（1in）C删除第i个结点（1in） D将n个结点从小到大排序（ ）4. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 个元素BA8 B63.5 C63 D7（ ）5. 链接存储的存储结构所占存储空间：AA分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B只有一

23、部分，存放结点值C只有一部分，存储表示结点间关系的指针D分两部分，一部分存放结点值，另一部分存放结点所占单元数（ ）6. 链表是一种采用 存储结构存储的线性表；BA顺序 B链式 C星式 D网状（ ）7. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址:DA必须是连续的 B部分地址必须是连续的C一定是不连续的 D连续或不连续都可以（ ）8 线性表L在 情况下适用于使用链式结构实现。BA需经常修改L中的结点值 B需不断对L进行删除插入 CL中含有大量的结点 DL中结点结构复杂（ ）9 单链表的存储密度（ ）。BA大于1； B等于1； C小于1； D不能确定（ ）10 设a1、a2、a3为

24、3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为（ ）。A、P034P0a13a24a30A循环链表 B单链表 C双向循环链表 D双向链表第3章 栈和队列一、基本内容栈和队列的结构特性；在两种存储结构上如何实现栈和队列的基本操作以及栈和队列在程序设计中的应用。二、学习要点1掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。2熟练掌握栈类型的两种实现方法，即两种存储结构表示时的基本操作实现算法，特别应注意栈满和栈空的条件以及它们的描述方法。3熟练掌握循环队列和链队列的基本操作实现方法，特别注意队满和队空的描述方法。三、基础知识题3.2 说明栈和线性表的异同点。

25、答：栈是限定仅在表尾进行插入或删除操作的线性表。3.3 写出下列程序段的输出结果（栈的元素类型SElem Type为char）。void main( )Stack S;Char x,y;InitStack(S);X=c;y=k;Push(S,x); Push(S,a); Push(S,y);Pop(S,x); Push(S,t); Push(S,x);Pop(S,x); Push(S,s);while(!StackEmpty(S) Pop(S,y);printf(y); ;Printf(x);答：stack3.4 简述以下算法的功能（栈的元素类型SElemType为int）。(1)Status

26、 algo1(Stack S) int i，n，A255； n=0； while (!StackEmpty(S) n+； Pop(S，An)； for (i=1；itop0 ST-top=0 ST-topm0 ST-top=m0（ ）4. 判定一个队列QU（最多元素为m0）为满队列的条件是：BQU-rear QU-front = = m0 QU-rear QU-front 1= = m0 QU-front = = QU-rear QU-front = = QU-rear+1（ ）5数组用来表示一个循环队列，为当前队列头元素的前一位置，为队尾元素的位置，假定队列中元素的个数小于，计算队列中元素的

27、公式为：Drf; （nfr）% n; nrf; （nrf）% n6. 设有4个数据元素a1、a2、a3和a4，对他们分别进行栈操作或队操作。在进栈或进队操作时，按a1、a2、a3、a4次序每次进入一个元素。假设栈或队的初始状态都是空。现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是 A ，第二次出栈得到的元素是 B ；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是 C ，第二次出队得到的元素是 D 。经操作后，最后在栈中或队中的元素还有 E 个。供选择的答案： AD：a1 a2 a3 a4

28、 E： 1 2 3 0答：A、B、C、D、E分别为 、 、 、 、 7. 栈是一种线性表，它的特点是 A 。设用一维数组A1,n来表示一个栈，An为栈底，用整型变量T指示当前栈顶位置，AT为栈顶元素。往栈中推入（PUSH）一个新元素时，变量T的值 B ；从栈中弹出（POP）一个元素时，变量T的值 C 。设栈空时，有输入序列a，b，c，经过PUSH，POP，PUSH，PUSH，POP操作后，从栈中弹出的元素的序列是 D ，变量T的值是 E 。供选择的答案：A： 先进先出 后进先出 进优于出 出优于进 随机进出B，C： 加1 减1 不变 清0 加2 减2D： a,b b,c c,a b,a c,b

29、 a,cE： n+1 n+2 n n-1 n-2答：A、B、C、D、E分别为 、 、 、 、 8. 在做进栈运算时，应先判别栈是否 A ；在做退栈运算时，应先判别栈是否 B 。当栈中元素为n个，做进栈运算时发生上溢，则说明该栈的最大容量为 C 。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的 D 分别设在这片内存空间的两端，这样，只有当 E 时，才产生上溢。供选择的答案：A，B：空 满 上溢 下溢C： n-1 n n+1 n/2D： 长度 深度 栈顶 栈底E：两个栈的栈顶同时到达栈空间的中心点 其中一个栈的栈顶到达栈空间的中心点 两个栈的栈顶在达栈空间

30、的某一位置相遇 两个栈均不空，且一个栈的栈顶到达另一个栈的栈底答：A、B、C、D、E分别为 、 、 、 、 第4章 串一、基本内容串的数据类型定义；串的三种存储表示；定长顺序存储结构、块链存储结构和堆分配存储结构；串的各种基本操作的实现及其应用；串的模式匹配算法。二、学习要点1熟悉串的七种基本操作的定义，并能利用这些基本操作实现串的其他操作的方法。2熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。三、基础知识题4.2 简述空串和空格串的区别。答：空格串是由一个或多个空格组成的串，它的长度为串中空格字符的个数；空串用符号“”表示，它的长度为0。4.3 设s=I AM A STUDENT,

31、t=GOOD,q=WORKER。求：StrLength(s), StrLength(t), SubString(s,8,7), SubString(t,2,1),Index(s,A), Index(s,t), Replace(s,STUDENT,q),Concat(Substring(s,6,2),Concat(t,SubString(s,7,8)。答：StrLength(s)=14 StrLength(t)=4 SubString(s,8,7)= STUDENTSubString(t,2,1)= O Index(s,A)=3 Index(s,t)=0Replace(s,STUDENT,q)I

32、 AM A WORKERConcat(t,SubString(s,7,8)A GOOD STUDENT4.4 已知下列字符串a=THIS, f=A SAMPLE,c=GOOD,d=NE,b= ,s=Concat(a,Concat(SubString(f,2,7),Concat(b,SubString(a,3,2),t=Replace(f,SubString(f,3,6),c), u=Concat(SubString(c,3,1),d),v=Concat(s,Concat(b,Concat(t,Concat(b,u),试问：s,t,v,StrLength(s),Index(v,g),Index(

33、u,g)各是什么？答：v=THIS SAMPLE IS A GOOD ONEINDEX(v,g)=3INDEX(u,g)=04.12 编写一个实现串的置换操作Replace(&S, T, V)的算法。解：int Replace(Stringtype &S,Stringtype T,Stringtype V);/将串S中所有子串T替换为 V,并返回置换次数 for(n=0,i=1;i=Strlen(S)-Strlen(T)+1;i+) /注意i的取值范围 if(!StrCompare(SubString(S,i,Strlen(T),T) /找到了与T匹配的子串 /分别把T的前面和后面部分保存为h

34、ead和tail StrAssign(head,SubString(S,1,i-1); StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+1); StrAssign(S,Concat(head,V); StrAssign(S,Concat(S,tail); /把head,V,tail连接为新串 i+=Strlen(V); /当前指针跳到插入串以后 n+; n+; /if return n; /Replace分析:i+=Strlen(V);这一句是必需的,也是容易忽略的.如省掉这一句,则在某些情况下, 会引起不希望的后果,虽

35、然在大多数情况下没有影响。四、附加题4.1 选择题（ ）1. 串是一种特殊的线性表，其特殊性体现在：B可以顺序存储 数据元素是一个字符 可以链式存储 数据元素可以是多个字符（ ）2. 设有两个串p和q，求q在p中首次出现的位置的运算称作：B连接 模式匹配 求子串 求串长（ ）3. 设串s1=ABCDEFG，s2=PQRST，函数con(x,y)返回x和y串的连接串，subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1, 2, len(s2), subs(s1, len(s2), 2)的结果串是：DBCDEF BCDEFG B

36、CPQRST BCDEFEF第5章 数组与广义表一、基本内容数组的类型定义和表示方式；特殊矩阵和稀疏矩阵的压缩存储方法以及运算的实现；广义表的逻辑结构和存储结构。二、学习要点1了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。2掌握对特殊矩阵进行压缩存储时的下标变换公式。3了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。4掌握广义表的结构特点及其存储表示方法，可根据自己的习惯，熟练掌握任意一种结构的链表。三、基础知识题5.1 假设有二维数组A68，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置

37、（基地址）为1000，计算：（1）数组A的体积（存储量）；（2）末尾元素A57的第一个字节地址为；（3）若按行存储时，元素A14的第一个字节地址为；（4）若按列存储时，元素A47的第一个字节地址为。答：（1）6*6*8=288（2）1000+288-6=1282（3）1000+(1-0)*8+(4-0)*6=1072（4）1000+(7-0)*6+(4-0)*6=12765.10 求下列广义表操作的结果。(1) GetHead(p,h,w)(2) GetTail(b,k,p,h)(3) GetHead(a,b),(c,d)(4) GetTail(a,b),(c,d)(5) GetHeadGet

38、Tail(a,b),(c,d)(6) GetTailGetHead(a,b),(c,d)(7) GetHeadGetTailGetHead(a,b),(c,d)(8) GetTailGetHeadGetTail(a,b),(c,d)答：(1) p (2) (k,p,h) (3) (a,b) (4) (c,d) (5) (c,d) (6) (b) (7) b (8) (d)5.12 按教科书5.5节中图5.8所示结点结构，画出下列广义表的存储结构图，并求它的深度。（1）（），a，（b，c），（），d），（e）；（2）（a），b），（），d），（e，f）；答：（1）深度为4（2）深度为4四、附加题

39、4.1 用三元组表表示下列稀疏矩阵： 答：（1） (3,2,3),(3,6,8),(5,4,6),(7,8,5),(8,1,2)（2） (1,6,-2),(2,5,9),(4,3,5),(6,5,3)第6章 树和二叉树一、基本内容二叉树的定义、性质和存储结构；二叉树的遍历和线索化以及遍历算法的各种描述形式；树和森林的定义、存储结构与二叉树的转换、遍历；树的多种应用。本章是课程的重点内容之一。二、学习要点1熟练掌握二叉树的结构特性，了解相应的证明方法。2熟悉二叉树的各种存储结构的特点及适用范围。3遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。不仅要熟练掌握各种

40、遍历策略的递归和非递归算法，了解遍历过程中“栈”的作用和状态，而且能灵活运算遍历算法实现二叉树的其他操作。层次遍历是按另一种搜索策略进行的遍历。4理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟练掌握二叉树的线索化过程以及在中序线索树上找给定结点的前驱和后继的方法。二叉树的线索化过程是基于对二叉树进行遍历，而线索二叉树上的线索又为相应的遍历提供了方便。5熟悉树的各种存储结构和特点，掌握树和森林与二叉树的转换方法。建立存储结构是进行其他操作的前提，要掌握1至2种建立二叉树和树的存储结构的方法。6了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。三、基础知识题6.1

41、 已知一棵树边的集合为,，请画出这棵树，并回答下列问题。（1）哪个是根结点？ （2）哪些是叶子结点？（3）哪个是结点G的双亲？ （4）哪些是结点G的祖先？（5）哪些是结点G的孩子？ 6）哪些是结点E的子孙？（7）哪些是结点E的兄弟？哪些是结点F的兄弟？ABCDEFHIGJKMNL（8）结点B和N的层次号分别是什么？（9）树的深度是多少？ （10）以结点C为根的子树的深度是多少？答：（1） A （2）D,M,N,F,J,K,L (3）C （4）A,C （5）J,K （6）I,M,N （7）E的兄弟是D,F的兄弟是G和H （8）2，5 （9）5 （10）36.2 一棵度为2的树与一棵二叉树有何区别？答：度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。即，在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。6.3 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。（1）（2）ABCABCCBAABCABC（一）（二）（三）（