数据结构实用教程习题答案

1、1 绪论回答下列概念：数据结构，数据的逻辑结构，数据的存储结构，算法数据结构 : 按照某种逻辑关系组织起来的一批数据，用一定的存储方式存储在计算机的存储器中，并在这些数据上定义一个运算的集合，就称为一个数据结构。数据的逻辑结构: 数据元素之间的逻辑关系，是根据实际问题抽象出来的数学模型。数据的存储结构: 是指数据的逻辑结构到计算机存储器的映射。算法 : 是指对数据元素进行加工和处理数据结构研究的三方面内容是什么？它们之间有什么联系和区别？三方面内容 : 数据的逻辑结构、数据的存储结构和数据运算的集合。联系和区别：数据的逻辑结构是数学模型，数据的存储结构是指逻辑结构到存储区域的映射，运算是定义在

2、逻辑结构上，实现在存储结构上。简述数据结构中讨论的三种经典结构及其逻辑特征。三种经典结构：线性表、树和图。线性表：有且仅有一个开始结点和一个终端结点，其余的内部结点都有且仅有一个前趋结点和一个后继结点，数据元素间存在着一对一的相互关系。树： 有且仅有一个开始结点， 可有若干个终端结点， 其余的内部结点都有且仅有一个前趋结点，可以有若干个后继结点，数据元素间存在着一对多的层次关系。图：可有若干个开始结点和终端结点，其余的内部结点可以有若干个前趋结点和若干个后继结点，数据元素间存在着多对多的网状关系。实现数据存储结构的常用存储方法有哪几种？简述各种方法的基本思想。常用存储方法有四种：顺序存储、链接

3、存储、索引存储、散列存储。各种方法的基本思想：顺序存储：把逻辑上相邻的数据元素存储在物理位置上相邻的存储单元里。链接存储：通过附加指针域表示数据元素之间的关系。索引存储：除了存储数据元素，还要建立附加索引表来标识数据元素的地址。散列存储：根据数据元素的关键字直接计算出该结点的存储地址，称为关键字地址转换法。算法的特性是什么？如何定性的评价一个算法的优劣？算法的特性：有穷性、确定性、可行性、输入、输出。算法的定性评价标准有：正确性、可读性、健壮性、简单性。算法的定量评价标准是什么？算法的定量评价标准有：时间复杂度和空间复杂度。时间复杂度：是一个算法运行时所耗费的系统时间，也就是算法的时间效率。空

4、间复杂度：是一个算法运行时所耗费的存储空间，也就是算法的空间效率。写出下列程序段中带标号语句的频度，并给出执行各程序段的时间复杂度（ n 为整数） 。i=1;while ( in ) do【 1】 i+;s=0;for(i=l;i=i;j-)【 1 】 s=s+i+j;5) i=1 ；while ( in ) do( 2) s=1;for(i=1;i=n;i+)【 1】 s=s*i;( 4) i=1;while(i*i=n)【 1 】 i+;x=1;y=100;do1 i=i*2;答：(1) n-1, O(n)(4)而O()而2线性表【1】While(x0)个数据元素的有限序列。顺序表：顺序表

5、(Sequential List)是采用顺序存储结构的线性表。单链表：每个结点只附加一个指向后继的指针域，这样的链表称为单链表(Single Linked List )静态链表：用数组实现的链表，指针就变换为数组的下标，结点即为数组中的下标变量，由于 需要预先分配一个较大的数组空间，因此这种链表称之为静态链表。比较顺序表和链表这两种线性表不同存储结构的特点。.逻辑关系的表示：顺序表隐含表示关系，链表显示表示关系。.存储密度：顺序表的存储密度大，而链表的存储密度小。.存储分配方式：顺序表的存储空间是预先静态分配的一块连续存储空间，在程序执行之前必须明确规定它的存储规模。链表不用事先估计存储规模，

6、动态分配和释放存 储空间，存储空间可连续也可不连续。.存取方法：顺序表可以随机存取，链表必须顺序存取。.插入、删除操作：在顺序表中做插入、删除时平均移动表中一半的元素；在链表中作插入、 删除时，只要修改指针域，而不需要移动元素。所以顺序表的插入、删除 效率低，链表的插入、删除效率高。.实现语言：顺序表容易实现，任何高级语言中都有数组类型。而链表的操作是基于指针的， 对于没有提供指针类型的高级语言，必须采用静态链表。总之，两种存储结构各有长短，选择那一种由实际问题中的主要因素决定。通常“较稳定”的 线性表选择顺序存储，而频繁做插入、删除的线性表，即动态性较强的线性表宜选择链接存储。.3 已知长度

7、为n的线性表A中的元素是整数，写算法求线性表中值大于item的元素个数。分两种情况编写函数：(1)线性表采用顺序存储；(2)线性表采用单链表存储。(1)线性表采用顺序存储#define MAX 1024typedef int DataType;typedef struct DataType dataMAX;int last; SeqList;int LocateElem (SeqList *L, DataType item) int i,j=0;for(i=0;ilast ;i+)if( L-datai item )j+;return j;( 2 )线性表采用单链表存储typedef int

8、DataType;typedef struct Node DataType data;struct Node *next;LinkList;LinkList *locateElem(LinkList *L, DataType item ) LinkList *p=L-next;int i=0;while ( p )if( p-data item) i+; p=p-next; return i ;.4 已知长度为 n 的线性表 A 中的元素是整数，写算法删除线性表中所有值为 item 的数据元素。 分两种情况编写函数： ( 1 )线性表采用顺序存储；( 2 )线性表采用单链表存储。( 1 )线性

9、表采用顺序存储#define MAX 1024typedef int DataType;typedef struct DataType dataMAX;int last; SeqList;int LocateElem (SeqList *L, DataType item) int i=0;While(ilast)if( L-datai =item )for(j=i+1;jlast;j+) L-dataj-1=L-dataj; L-last -; Else i+;( 2 )线性表采用单链表存储typedef int DataType;typedef struct NodeDataType dat

10、a;struct Node *next;LinkList;int deleteDupNode(LinkList *L, DataType item)LinkList *p,*q,*r;q= L; p=L-next;while (p)if (p-data=item) q-next=p-next; free(p); p=q-next; else q=p; p=p-next; 设长度为Max 的顺序表L 中包含 n 个整数且递增有序。试写一算法，将x 插入到顺序表的适当位置上，以保持表的有序性，并且分析算法的时间复杂度。#define MAX 1024typedef int DataType; ty

11、pedef struct DataType dataMAX; int last; SeqList; int inserts(SeqList *L, DataType x) int i;if (L-last = Max-1) printf( full); return 0; i= L-last;while(i=0& L-datai x)L-data i+1= L-data i-;/ “相当于 L-data i+1= L-data i ; i-;“L-data i+1=x; L-last +; return 1; 设带头结点的单链表L中的数据元素是整型数且递增有序。试写一算法，将 x插入到单链表的

12、适当位置上，以保持表的有序性，并且分析算法的时间复杂度。typedef int DataType;typedef struct Node DataType data;struct Node *next;LinkList;void InsertList(LinkList *L,datetype x)LinkList *p,*s;s=(LinkList *)malloc(sizeof(Linklist);s-data=x;p=L;while(p-next)&(p-next-datanext;s-next=p-next; p-next=s; 试写一算法实现对不带头结点的单链表H进行就地逆置。type

13、def int DataType;typedef struct Node DataType data;struct Node *next;LinkList;LinkList * Reverse(LinkList * H) LinkList *p,*q;if (!H) return;p=H-next; q=H-next; H-next=NULL;While(q)q=q-next; p-next= H; H =p;p=q;return H;若带头结点的单链表L 中的数据元素是整型数，编写算法对单链表L 进行排序。typedef int DataType;typedef struct Node Da

14、taType data;struct Node *next;LinkList;void InsertList(LinkList *L)LinkList *p,*q,*s;if (!L-next | ！ L-next-next) return;q= L-next-next; L-next-next= NULL;while(q)s=q; q=q-next;p=L;while(p-next)&(p-next-datadata ) p=p-next;s-next=p-next; p-next=s;设单链表X和单链表Y分别存储了两个字符串，设计算法找出X中第一个不在 Y中出现的字符。typedef ch

15、ar DataType;typedef struct Node DataType data;struct Node *next;LinkList;linklist *search(linklist *x, linklist *y)linklist *p,*q;p=x; q=y;while(p&q)if(p-data!=q-data) q=q-next; else p=p-next; q=y; return p; 已知递增有序的两个单链表A 和 B 各存储了一个集合。设计算法实现求两个集合的交集运算C=AO Botypedef int DataType;typedef struct NodeDa

16、taType data;struct Node *next;LinkList;LinkList *union(LinkList *A,LinkList *B)LinkList *C, *p,*q,*s*r;p=A-next;q=B-next;C=A; r=C;while (p&q) if (p-data=q-data) r-next=p; r=p;p=p-next; q=q-next;else if (p-datadata) p=p-next;else q=q-next;r-next= NULL ; free(B); return C;已知递增有序的两个单链表A和B,编写算法将 A、B归并成一

17、个递增有序的单链表C。typedef int DataType;typedef struct NodeDataType data;struct Node *next;LinkList;LinkList *union(LinkList *A,LinkList *B)LinkList *C, *p,*q,*s*r;p=A-next;q=B-next;C=A; r=C;while (p&q) if (p-datadata) s=p; p=p-next; else s=q; q=q-next; r-next=s;r=s;if (!q) r-next=q;else r-next=p;free(B); r

18、eturn C;3 栈和队列回答下列概念：栈，队列，顺序栈，链队列栈： 栈( Stack )是运算受限的线性表，限制它的插入和删除操作仅在表的一端进行。队列： 只允许在表的一端进行插入，而在表的另一端进行删除，将这种线性表称为队或队列( Queue) 。顺序栈： 采用顺序方式存储的栈称为顺序栈(Sequential Stack) 。链队列： 采用链接方法存储的队列称为链队列( Linked Queue ) 。栈和队列各有什么特点？简述栈、队列和线性表的差别。栈(Stack)是运算受限的线性表，限制它的插入和删除操作仅在表的一端进行，又称为后进先出的线性表( Last In First Out

19、) ，简称 LIFO 表。只允许在表的一端进行插入，而在表的另一端进行删除，将这种线性表称为队或队列(Queue) ，又叫先进先出的线性表，简称为 FIFO (First In First Out ) 表。这三种结构有很多的相似之处，其差别主要体现在运算上，具有不同的运算特点。同线性表的运算相比，栈和队列在操做上受到限制。线性表可以在元素序列的任何位置上进行插入、删除操作，查找运算往往是线性表上使用频率最高的操作。查找、插入、删除的时间复杂度一般为 O （ n ） 。栈和队列的插入和删除运算都限制在线性表的表端完成，在栈和队列上不需要查找运算。栈和队列的插入及删除运算时间复杂度都可以为 O （

20、 1）。设有编号为 1， 2， 3， 4 的四辆车，顺序进入一个栈式结构的站台，试写出这四辆车开出车站的所有可能的顺序。 TOC o 1-5 h z 1234213412432143132423141342234114322431若数列1、2、3、4、5、6顺序进栈，假设 P表示入栈操作，S表示出栈操作，例如：操作序列PSPSPSPSPSPST得到出栈序列为：123456。依此类推，请回答:（ 1）能否得到出栈序列325641？若能，请写出对应的操作序列。（ 2）能否得到出栈序列154623？若能，请写出对应的操作序列。（3）对应操作序歹U:PPSSPPSPSPSS导至IJ的出栈序歹U是什么?

21、（4）对应操作序歹U:PPPPSPSSPSSS导至IJ的出栈序歹U是什么?（ 5）从上面的结果中你能总结出什么结论？（ 1）能得到325641。在123 依次进栈后， 3 和 2 出栈，得部分输出序列 32 ；然后 4 ， 5 入栈， 5出栈，得部分出栈序列325； 6 入栈并出栈，得部分输出序列3256 ；最后退栈，直到栈空。得输出序歹U 325641。其操作序歹U为 PPPSSPPSPSSS（2）不能得到输出顺序为154623的序列。部分合法操作序列为ADAAAADDAD导到部分输出序列 1546 后，栈中元素为 23， 3 在栈顶，故不可能2 先出栈，得不到输出序列 154623 。21

22、4563453621（5）借助栈由输入序列12n得到输出序列pip2pn,则在输出序列中不可能存在这样的情形： 存在着 ijk 使 pj pkfront=sq-rear判断队满的条件是：（ sq-rear+1 ） % MAXSIZE= = sq-front求队列长度的公式为： m = （sq-rear - sq-front+ MAXSIZE ） % MAXSIZE;通常称正读和反读都相同的字符序列为回文，例如，abcdeedcba、abcdcba”是回文。若字符序列存储在一个单链表中， 编写算法判断此字符序列是否为回文。 （提示： 将一半字符先依次进栈）#define maxsize 100t

23、ypedef char datatype1;typedef structdatatype1 datamaxsize; int top; seqstack;typedef int datatype;typedef struct node datatype data;struct node *next; Linklist;Duichen(Linklist *head)int i=1;Linklist *p;seqstack *s;s=initSeqStack();p= head-next;n=0;while(p)n+; p=p-next;p=head-next;while(idata); i+;

24、if (n%2!=0) p=p-next;while(p&p-data=pop(s) p=p-next;if (p) return 0 else return 1;两个栈共享数组 am 空间，栈底分别设在两端，此时栈空、栈满的条件是什么？试写出两个栈公用的算法： Top(i), Push(i,x) 和 Pop(i) ，其中 i 为栈的序号0 或 1 。#define m 100typedef char datatype;typedef struct nodedatatype am;int top0 , top1; seqstack;Seqstack ss,*s=&ss;int push(int

25、 i, datatype x) if (s-top1 = s-top0+1) printf( “full ”); return 0;if(i=0)s-top0+;s-as-top0=x;else s-top1-;s-as-top1=x;return 1;datatype pop(int i)if(i=0) if (s-top0= -1) printf( “empty ”); return 0;s-top0-; return s-as-top0+1;else if (s-top1= m) printf( “empty”); return 0;s-top1+; return s-as-top1-1

26、;datatype top(int i)if(i=0) if (s-top0= -1) printf( “empty ”); return 0; return s-as-top0;else if (s-top1=m) printf( “empty”); return 0; return s-as-top1;假设以数组 am 存放循环队列的元素，同时设变量rear 和 length 分别作为队尾指针和队中元素个数，试给出判别此循环队列的队满条件，并写出相应入队和出队的算法(在出队的算法中要返回队头元素) 。#define m 100int enqueue(int a, int rear, int

27、 length, int x) if(length = m)printf( “queue is full ”); return 0;rear=(rear+1)% m;arear=x;length +;return length;int dequeue(int a, int rear, int length, int *x) if(length =0)printf( “queueempty”); return 0;*x= a (rear- length +m)%m;length -;return length;4 多维数组及广义表回答下列概念：三元组表、广义表、十字链表三元组表：稀疏矩阵中的非零

28、元素三元组组成的线性表。广义表：也称为列表(Lists)是n (nn。个元素a1，现 ，a,，an的有限序列，元素ai 可以是原子或者是子表(子表亦是广义表)。十字链表：稀疏矩阵(即三元组表)的一种链接存储结构。稀疏矩阵中每个非零元素都用一个包含五个域的结点来表示，存储非零元素所在行的行号域i ，存储非零元素所在列的列号域j ，存储非零元素值的值域v ，以及行指针域 right 和列指针域down ，分别指向同一行中的下一个非零元素结点和同一列中的下一个非零元素 结点。二维数组在采用顺序存储时，元素的排列方式有哪两种？行优先和列优先。矩阵压缩存储的目的是什么？请写出对称阵压缩存储四种方式的地址

29、公式。压缩存储的目的：节省矩阵的存储空间。将对称矩阵的下(上)三角存储在数组长度为n (n+1) /2的数组sa中，设矩阵中的某一个元素aj在数组中的下标为k,则对称阵压缩存储四种方式下k的计算公式如下：(1)行优先顺序存储下三角i(i+1)/2+j i 河(下三角)k= ，右I j(j+1)/2+i ivj (上三角)(2)列优先顺序存储下三角,1(2n-j+1 ) /2+i-j i 河(下三角) k=4J (2n-i+1 ) /2+j-i i vj (上三角)(3)行优先顺序存储上三角ji (2n-i+1) /2+j-i i j (下三角)(4)列优先顺序存储上三角k= fj (j+1)

30、/2+i iwj (上三角)1i (i+1) /2+j i j (下三角)在特殊矩阵和稀疏矩阵中，哪一种经过压缩存储后会失去随机存取的特性？稀疏矩阵。设有一个10阶的对称矩阵 A,以行优先顺序存储下三角元素，其中a00为第一元素，其存储地址为1,每个元素占一个字节，则a85的地址为多少？若aii为第一元素，那么a85的地址又会是多少？若aoo为第一元素，则 a85的地址为：41若aii为第一元素，则 a85的地址为：32请给出图4.10中稀疏矩阵A6的三元组顺序表和十字链表存储结构图示。矩阵A6X7的三元组顺序表：01234133462164311-3765矩阵A6X7及十字链表表示:H1H2

31、H3H4H5H6H7广义表分几类？它们之间有什么关系？广义表分为：线性表、纯表、再入表和递归表四种。它们之间的关系满足：递归表 再入表 纯表 线性表。分别求出下列广义表的表头、表尾及表长、表深。A= (a)表头：a表尾：()表长：1表深：1B= (a,b) , (c,d)表头：(a,b)表尾：(c,d)表长：2表深：2C= (a, (b,c) ,d,e)表头：a表尾：(b,c),d,e)表长：4表深：2D= (a,b, (c,d) , (e, (f,g)表头：a表尾：(b, (c,d) , (e, (f,g)表长：4表深：4请画出下列广义表的图形表示。A= (a,b,c)B= (A,d)C=

32、(x ,A , B)ABC回答下列概念：树、二叉树、满二叉树、完全二叉树、哈夫曼树树：可以用二元组或递归两种方法定义树。树的二元组定义如下：设tree= (D, S),其中D是数据元素的集合，S是D中数据元素之间关系的集合。设 关系rCS,相对r,满足下列条件：(1) D中有且仅有一个开始结点，该结点被称为树的根(Root);(2)除树根结点外，D中其余的结点有且仅有一个前趋结点；(3)从根到其余结点都有路径。则称tree是相对r的树形结构。二叉树：二叉树(Binary Tree)是n (n0个结点的有限集合，满足：(1)当n=0时，为空二叉树。(2)当n0时，是由一个根结点和两棵互不相交的分

33、别称作这个根的左子树和右子树的二叉树组成。满二叉树：每层结点数都达到最大值的二叉树。完全二叉树：除最下面一层外其余各层的结点数都达到最大值，并且最下一层上的结点都集中在最左边的若干位置上的二叉树。哈夫曼树：又称最优二叉树，是在含有n个叶子结点，权值分别为 W1, W2, , Wn的所有二叉树中，带权路径长度 WPL最小的二叉树。对于图5.37给出的树，回答下列问题：(1)写出它的二元组表示；(2)根结点、叶结点和分支结点分别都为哪些；(3)结点F的度数和层数分别为多少；(4)结点B的兄弟和孩子分别为哪些？(5)从结点B到结点N是否存在路径？若存在请写出具体路径。(6)从结点C到结点L是否存在路

34、径？若存在请写出具体路径。图 5.37(1)该树采用二元组表示如下:设 tree = ( D, D = A , R = AI,rC SC,AG,J,E,AG, H, I, J, K, L, , , , , , , N5.3包含三个结点的二叉树:5.4判断下列说法是否正确：(1)二叉树是度为 2的有序树。(2)二叉树中至少有一个结点的度为2。(3)完全二叉树一定存在度为 1的结点。(X)(X)(X)画出包含三个结点的树和二叉树的所有不同形态，说明树和二叉树之间的区别与联系。包含三个结点的树:5.5少？设树T的度为4,其中度为1, 2, 3和4的结点个数分别为4, 2, 1, 1则T中的叶子数为多

35、叶子数为8。5.6结点数为n的二叉树，高度最大是多少？最小是多少？将其扩充成完全二叉树时最多需要附加 多少个虚点？结点数为n的二叉树，高度最大是 n,最小是log；1或log2n 1) 。将其扩充成完全二叉树时最多需要附加的虚点个数:2n-1-n。5.7分别画出图5.38中的二叉树的顺序存储结构和二叉链表存储结构的图示。1 I C口5.8分别写出图 前序遍历序列： 中序遍历序列： 后序遍历序列：图 5.38顺序存储结构的图示：012345678 9101112131415 27 2829ABCDE#F#G#H#IJ二叉链表存储结构的图示:root/ B中二叉树的前序、中序和后序遍历序列。ABD

36、EGCFHIJDBGEACIHJFDGEBIJHFCA出满足下面条件的二叉树：(1)前序遍历与中序遍历结果相同(2)前序遍历和后序遍历结果相同(3)中序遍历和后序遍历结果相同(1)只有右分支的单分支树。(2)只有一个根结点的二叉树。(3)只有左分支的单分支树。以二叉链表为存储结构，请写出前序遍历的非递归算法。#define MAXSIZE 100typedef char DataType;typedef struct Node/* 二叉链表存储结构 */ DataType data;struct Node *lchild,*rchild;BiTree;typedef BiTree* SElem

37、Type ; /*栈中数据元素类型，栈中保存结点指针*/typedef struct SElemType dataMAXSIZE;int top;SeqStack;/*栈的类型定义，顺序栈 */*栈的基本操作的实现*/*初始化栈*/*首先建立栈空间，然后初始化栈顶指针*/SeqStack *initSeqStack() SeqStack *s;s=(SeqStack*)malloc(sizeof(SeqStack);s-top= -1;return s; intpush (SeqStack *s, SElemType x)if (s-top=MAXSIZE-1)/* 栈满不能入栈 */ pri

38、ntf(overflow);s-top+;s-datas-top=x;return 1;void pop (SeqStack *s) s-top-;int empty (SeqStack *s) if (s-top= -1)return 1;else return 0;SElemType top (SeqStack *s) return (s-datas-top );return 0;/* 出栈，假设栈不空*/* 设栈不空 */void PreOrderFei(BiTree *p)/* 前序遍历二叉树的非递归算法 */ SeqStack *s;s=initSeqStack();while(1)

39、 while(p) printf(%c, p-data); push(s,p); p=p-lchild; /*先访问结点，后压栈*/if (empty(s) break;p=top(s); pop(s); p=p-rchild;引入线索二叉树的目的是什么？ n 个结点的线索二叉树上含有多少条线索？有效利用空指针域，提高遍历运算的效率，简化遍历算法。n 个结点的线索二叉树上含有n+1 条线索。设一棵二叉树的中序、 后序遍历序列分别为： G L D H B E I A C J F K 和 L G H D I E B J K F C A ，请回答：( 1)画出二叉树逻辑结构的图示。( 2)画出上题中

40、二叉树的中序线索二叉树。( 3)画出中序线索二叉链表存储结构图示并给出C 语言描述。( 4)给出利用中序线索求结点中序后继的算法。typedef char DataType;typedef struct Node DataType data;struct Node *lchild,*rchild;int ltag,rtag;BiThrTree;BiThrTree * InOrderNext(BiThrTree *p)/* 求中序后继 */ if(p-rtag=1) p=p-rchild;/*分两种情况查找结点后继*/elsep=p-rchild;while(p-ltag=0) p=p-lchi

41、ld; return p;以二叉链表为存储结构，设计一个求二叉树高度的算法。typedef char DataType;typedef struct Node/* 二叉链表存储结构*/ DataType data;struct Node *lchild,*rchild;BiTree;int height（BiTree *T）/* 求树高 */ int i,j;if（!T） return 0; TOC o 1-5 h z i=height（T-lchild）; /* 求左子树的高度*/j=height（T-rchild）; /* 求右子树的高度*/return ij?i+1:j+1;/*二叉树的

42、高度为左右子树中较高的高度加1*/试设计一个算法，根据二叉树的前序序列和中序序列创建一棵二叉树。算法思想：确定二叉树的根节点。树根是二叉树前序遍历的第一个元素。求解二叉树的左右子树。找出根结点在中序遍历中的位置， 根左边的所有元素是左子树，根右边的所有元素是右子树。若根结点左边或右边为空，则该方向子树为空；若根结点 左边和右边都为空，则此结点为叶子节点。递归求解树。将左子树和右子树分别看成一棵二叉树，重复（ 1 ）（ 2 ）（ 3 ）步，直到 所有的结点完成定位。typedef char DataType;typedef struct Node/* 二叉链表存储结构*/ DataType da

43、ta;struct Node *lchild,*rchild;BiTree;char pre50 = ABDHLEKCFG;/全局变量-前序序列char mid50 = HLDBEKAFCG; / 中序序列int position(char c)/* 求解字符在中序遍历序列中的位置*/return strchr(mid,c)-mid;/* strchr()#include 功能：查找字符串s中首次出现字符c的位置(指针)，如果s中不存在c则返回NULL*/void preMidCreateTree(BiTree *p, int i, int j, int len) /* i: 子树的前序序列的

44、首字符在pre 中的下标j: 子树的中序序列的首字符在mid 中的下标len: 子树的遍历序列长度，即子树中的字符数*/int m;if(len data = prei;m = position(prei);preMidCreateTree(p-left, i+1, j, m-j);/m-j 为左子树字符数preMidCreateTree(p-right, i+(m-j)+1, m+1, len-1-(m-j); /len-1-(m-j)为右子树字符数 void main()BiTree *root = NULL;preMidCreateTree(root, 0, 0, strlen(mid)

45、;BCFD请画出5.37中的树对应的二叉树。请画出5.39中的各二叉树对应的森林。(a)(b)图 5.39(a)(b)(c)(d)设森林F对应的二叉树为 B,它有m个结点，B的根为p, p的右子树结点个数为n,森林F中第一棵树的结点个数是多少？m-n。假设用于通信的电文由字符集a, b, c, d, e, f, g, h中的字母构成，这 8个字母在电文中出现的概率分别为0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10。(1)为这8个字母设计 Huffman编码。(2)求出哈夫曼树的带权路径长度 WPL。(3)若用三位二进制数对这8个字母进行等长编码，

46、则Huffman编码的平均码长是等长编码的百分之几？(1)哈夫曼树:对应的哈夫曼编码:字符编码a1010b00c10000d1001e11f10001g01h1011(2)带权路径长度为:nWPLWili =0.07 4+0.19 2+0.02 5+0.06 4+0.32 2+0.03 5+0.21 2+0.10 4=2.61i 1(3) 2.61/3*100%=87%6图回答下列概念：完全图、子图、连通分量、网络、最小生成树、拓扑序列完全图：任意两个顶点之间都有边的图。子 图：设有图G=(V,E),若V是V的子集(V V) , E是E的子集(E E),且E中的边 所邻接的点均在 V中出现，则

47、G=(V,E)也是一个图，并且称之为G的子图。连通分量：无向图 G的极大连通子图。网 络：边上带权的图。最小生成树：连通网络的所有生成树中边上权值之和最小的生成树。拓扑序列：有向无环图中所有顶点按照拓扑排序的思想排成的一个线性序列。n个顶点的无向图，若采用邻接矩阵为存储结构，如何求边的条数？如何求某个顶点的度？如 果该图为有向图呢？无向图的邻接矩阵是对称的，“1的个数则是图中边的条数的2倍，第i行或第i列上“1的个数都是序号为i的顶点的度。有向图中，“1的个数则是图中边的条数，第i行“1的个数是序号为i的顶点的出度，第i列上“1的个数是序号为i的顶点的入度。对于一个具有n个顶点和e条边的无向图

48、，若采用邻接表为存储结构，所有边表中的结点总数 为多少？ 如何求某个顶点的度？当该图为有向图时，所有边表中的结点总数为多少？如何求某 个顶点的入度和出度？(1)无向图的边表中的结点总数为：2*e;某个顶点的度：该顶点的边表中的结点个数。(2)若该图为有向图，且采用邻接表(通常称为出边表)为存储结构，则所有边表中的结点总数为e;出边表中，顶点 Vi对应的边表结点的个数即为顶点Vi的出度；求顶点vi的入度，需要遍历整个出边表，求边表结点中adjvex域的值为i的结点个数。6.4 设一个有向图为 G=(V,E),其中 V= V 1,V2,V3,V4, E=, 请回答下列各问：(1)画出该有向图，求出

49、每个顶点的入度和出度。(2)画出该图的邻接矩阵存储结构图示并给出C语言描述。(3)画出该图的邻接表和逆邻接表的存储结构图示并给出C语言描述。(4)写出从顶点 V2出发的DFS序列和BFS序列。(1)有向图如下：顶点Vi的入度是2,出度是1;顶点V2的入度是1 ,出度是2;顶点V3的入度是1,出度是0； 顶点V4的入度是1,出度是2。01234V1V2V3V4数组 TOC o 1-5 h z 00011010A1=0000C语言描述：#define N 4/*图的顶点数*/typedef char VexType; /* 顶点类型 */typedef int AdjType; /* 权值类型 *

50、/ typedef struct VexType vertexN+1; /* 顶点数组 */ AdjType edgeN+1N+1;/* 邻接矩阵 */AdjMatrix;C语言描述:typedef struct node int adjvex;struct node *next;EdgeNode;typedef struct VexType vertex;EdgeNode *link;VexNode;#define N 10/*邻接点域*/*指针域*/*定义边表结点*/*顶点域*/*指针域*/*定义顶点表结点*/VexNode adjlistN+1;邻接表图示：逆邻接表图示:DFS 序歹U：

51、V2, V1,V4,V3BFS 序列：V2, V1,V3,V46.5对图6.50所示的无向图，依次输入各边：（V1,V2）、（V1,V4）、（V2,V3）、（V3,V4）、（V3,V5）,请回答下列各问：（1）写出该无向图的二元组表示。（2）画出该图的邻接矩阵和邻接表（头插法建表）存储结构图示。（3）对（2）中的邻接矩阵，给出从顶点V1出发的DFS序列和DFS生成树。（4）对（2）中的邻接表，给出从顶点Vi出发的BFS序列和BFS生成树。（1）无向图G的二元组表示：设G=（V, E） , V为顶点集，E为边集，则V= V1, V2, V3, V4, V5E=（V1,V2）、（V1,V4）、（V

52、2,V3）、（V3,V4）、（V3,V5）（2）邻接矩阵图示：门 012345经V1V2V3V4V5 TOC o 1-5 h z 0101010100A1= 0101110100邻接表图示:_ 00100（3）对（2）中的邻接矩阵，从顶点V1出发的DFS序列是V1,V2,V3,V4,V5DFS生成树是：(4)对(2)中的邻接表，从顶点 V1出发的BFS序列是:V1,V4,V2,V3,V5BFS生成树：画出图6.51的所有可能的最小生成树。图 6.50图 6.51求出图6.52从顶点V1到其他各顶点之间的最短路径。然占S八、路径长度路径V10V1 V1V220V1 V2V35V1 7 V3V41

53、9V1 -V3V6V4V525V1 V3-V6V5V615V1 V3V66.8给出图6.53所有可能的拓扑序歹U。图 6.53图 6.52V2, V1, V3, V5, V4, V7, V8, V6 或 V5, V2, V1, V3, V4, V7, V8, V6 或 V7, V2, V1 , V3, V5, V4, V8, V66.9设计一个算法将一个无向图的邻接矩阵转换成邻接链表。邻接矩阵的C语言描述#define N 5typedef char VexType;typedef int AdjType; typedef struct VexType vertexN+1;AdjType ed

54、geN+1N+1;AdjMatrix;邻接表的C语言描述 typedef struct node int adjvex;struct node *next;EdgeNode; typedef struct VexType vertex;EdgeNode *link;VexNode;VexNode adjlistN+1;void creatAdjList(AdjMatrix *adj) int i,j;EdgeNode *s;for(i=1;ivertexi;adjlisti.link =NULL;/* 边表指针初始为空*/for(i=1;i=1;j-) if(adj-edgeij=1) s=(

55、EdgeNode*)malloc(sizeof(EdgeNode); /* 生成边表结点 */ s-adjvex=j;s-next=adjlisti.link;/* 插入到顶点 vi 的边表头部*/adjlisti.link=s; /* creatAdjList */6.10 以邻接矩阵作为图的存储结构，试写出图的非递归的深度优先搜索算法。/ 邻接矩阵的 C 语言描述#define N 5/* 图的顶点数 */#define MAXSIZE 10typedef char VexType;/* 顶点类型*/typedef int AdjType;/* 权值类型*/typedef struct V

56、exType vertexN+1; /* 顶点数组 */ AdjType edgeN+1N+1;/* 邻接矩阵 */AdjMatrix;int visitedN+1; /* 全局标志数组，标注顶点是否被访问 */typedef int SElemType ; /* 栈中数据元素类型，栈中保存顶点序号 */ typedef struct SElemType dataMAXSIZE;int top;SeqStack;/* 栈的类型定义，顺序栈*/void DFS(AdjMatrix *adj,int i) /* 从顶点 i 出发进行深度优先搜索，用邻接矩阵adj 存储图 */ SeqStack *

57、s;int v=i;s=initSeqStack();push(s,v);while(!empty(s) v= top(s);if(!visitedv) visitedv=1;/* 标记 v 已经访问过 */printf ( 输出序号为 %d 的顶点 : %cn,v,adj-vertexv); /* 访问顶点 v*/for (j=1;jedgevj)&(!visitedj) push(s,j);break; if(jN) pop(s);6.11 修改 Prim 算法，使之能在邻接表存储结构上实现求图的最小生成树，并分析其时间复杂度。由于图上的边都带有权值， 因此邻接表结构中的边表结点除了保存邻

58、接点的序号外， 还要保存边的权值。最小生成树的存储结构采用边集数组。/邻接表存储结构#define N 5#define MAX 10000 typedef int AdjType; typedef struct node int adjvex;AdjType weight; struct node *next;EdgeNode;typedef struct VexType vertex;EdgeNode *link;VexNode;VexNode adjlistN+1;/最小生成树的存储结构typedef struct edge int fromvex;int endvex;int weig

59、ht;EdgeSetArray; EdgeSetArray TN;/邻接表存储结构上的Prim 算法void prim() int i,j,w,min,minest;EdgeNode *p=null; EdgeSetArray edtemp; for (i=1;i adjvex;Tj.weight=p- weight; p=p-next;/* 依次搜索顶点 1 的邻接点 */* 邻接点的序号 */* 求当前最短边，下标为minest */for (i=1;i=N-1;i+) min=MAX;for(j=i;j=N-1;j+)if (Tj.weightmin)/* 求生成树中的第i 条边 */

60、min=Tj.weight; minest=j;/* Tminest 是当前最短的边*/if (i!=minest)/* 将当前最短的边保存到 Ti ，如果不是则交换*/ edtemp=Tminest;Tminest=Ti;Ti=edtemp;/* 调整边集数组 */ k= Ti.endvex;for(j=i+1;j adjvex= Tj.endvex & p-weightweight;Tj.formvex=k;break; /*for-j*/ /*for-i*/* prim */6.12 以邻接表作为图的存储结构，试写出从源点到其他各顶点的最短路径的Dijkstra 算法。/ 邻接表存储结构