数据结构c语言版课后习题答案完整版

1、5 .选择题：CCBDCA6 .试分析下面各程序段的时间复杂度。(1) O(1)(2) O(m*n)2(3) O(n2)(4) O(log3n)(5)因为x+共执行了n-1+n-2+1=n(n-1)/2,所以执行时间为O(n2)(6) O(.n)第2章线性表1 .选择题babadbcabdcddac2 .算法设计题(6)设计一个算法，通过一趟遍历在单链表中确定值最大的结点。ElemTypeMax(LinkListL)if(L->next=NULL)returnNULL;pmax=L->next;法设计题(2)回文是指正读反读均相同的字符序列，如"abba"和&q

2、uot;abdba”均是回文，但"good"不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)?根据提示，算法可设计为：合应用题(1)已知模式串t='abcaabbabcab'写出用KMP法求得的每个字符对应的next和nextval函数值。模式串t的next和nextval值如下:j123456789101112t串abcaabbabcabnextj011122312345nextvalj011021301105(3)数组A中，每个元素Ai,j的长度均为32个二进位，行下标从-1到9,列下标从1到11,从首地址S开始连续存放主存储

3、器中，主存储器字长为16位。求：存放该数组所需多少单元存放数组第4列所有元素至少需多少单元数组按行存放时，元素A7,4的起始地址是多少数组按列存放时，元素A4,7的起始地址是多少每个元素32个二进制位，主存字长16位，故每个元素占2个字长，行下标可平移至1到11。(1) 242(2)22(3)s+182(4)s+142(4)请将香蕉banana用工具H()Head(),T()-Tail()从L中取出。L=(apple,(orange,(strawberry,(banana),peach),pear)H(H(T(H(T(H(T(L)(5)写一个算法统计在输入字符串中各个不同字符出现的频度并将结果

4、存入文件(字符串中的合法字符为A-Z这26个字母和0-9这10个数字)。voidCount()/统计输入字符串中数字字符和字母字符的个数。inti,num36;charch;for(i=0;i<36;i+)numi=0;/初始化while(ch=getchar()!=#')/'#'表示输入字符串结束。if('0'<=ch<='9')i=ch48;numi+;/数字字符elseif('A'<=ch<='Z')i=ch-65+10;numi+;/字母字符for(i=0;i<1

5、0;i+)/输出数字字符的个数printf("数字%d的个数=%dn”,i,numi);for(i=10;i<36;i+)/求出字母字符的个数printf("字母字符c的个数=%dn”,i+55,numi);/算法结束。第5章树和二叉树1 .选择题ADDCACCBDCCCACC2 .应用题(2)设一棵二叉树的先序序列：ABDFCEGH,中序序列：BFDAGEHC画出这棵二叉树。画出这棵二叉树的后序线索树。FGH)(1)(2)(3)假设用于通信白电文仅由8个字母组成，字母在电文中出现的频率分别为，°试为这8个字母设计赫夫曼编码。试设计另一种由二进制表示的等长编

6、码方案。对于上述实例，比较两种方案的优缺点。解：方案1;哈夫曼编码先将概率放大100倍，以方便构造哈夫曼树。w=7,19,2,6,32,3,21,10，按哈夫曼规则：(2,3),6,(7,10),19,21,32(100)(401'60)19，21、2/(28)>17<7-106字母编R对应编码出现频率1110020031111041110510方案比较:方案1的WP2+4+5+=+=方案2的WP3+=3结论：哈夫曼编码优于等长二进制编码?3.算法设计题以二叉链表作为二叉树的存储结构，编写以下算法:(1)统计二叉树的叶结点个数。intLeafNodeCount(BiTree

7、T)字母编R对应编码出现频率10002001301040115100610if(T=NULL)return0;/如果是空树，则叶子结点个数为02elseif(T->lchild=NULL&&T->rchild=NULL)return1;/判断该结点是否是叶子结点(左孩子右孩子都为空)，若是则返回1elsereturnLeafNodeCount(T->lchild)+LeafNodeCount(T->rchild);(3)交换二叉树每个结点的左孩子和右孩子。voidChangeLR(BiTree&T)BiTreetemp;if(T->lchi

8、ld=NULL&&T->rchild=NULL)return;elsetemp=T->lchild;T->lchild=T->rchild;T->rchild=temp;ChangeLR(T->lchild);ChangeLR(T->rchild);1 .选择题CBBBCBABAADCCDDB2 .应用题(1)已知如图所示的有向图，请给出:每个顶点的入度和出度；邻接矩阵；邻接表；逆邻接表。便亘1I3in5631tt出生Q3（，）足鞠皋(2)已知如图所示的无向网，邻接矩阵；邻接表；最小生成树图无向网1(13(2)邪援建降10010尊J00

9、0fl00110000JL001三*S3-4H44IE4345535555976554957654332266ab4c3ba4c5ca3b5db5c5eb9d7fd6e3gd5f2hc5d4d5d5e7f3g2h6g6e9h5f6g5/h4A(3)已知图的邻接矩阵如所示。试分别画出臼顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。深度优先生成树DOOooiocaDOO000110001io100DOOIoa00D000I001aoIo1091qooa广度优先生成树a到其他各顶点间的最短路径,图邻接矩阵(4)有向网如图所示，试用迪杰斯特拉算法求出从顶点V'、飞点、i=1i=2i=

10、3i=4i=5i=6b15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)t5(a,b)c2(a,c)_d12(a,d)12(a,d)11(a,c,f,d)11(a,c,f,d)eoo10(a,c,e)10(a,c,e)foo6(a,c,f)_gooOO16(a,c,f,g)16(a,c,f,g)14(a,c,f,d,g)S终点集a,ca,c,fa,c,f,ea,c,f,e,da,c,f,e,d,ga,c,f,e,d,g,b第7章查找1 .选择题CDCABCCCDCBCADA2 .应用题(1)假定对有序表：(3,4,5,7,24,30,42,54,63,72,87,95)进行

11、折半查找,试回答下列问题：画出描述折半查找过程的判定树；若查找元素54,需依次与哪些元素比较若查找元素90,需依次与哪些元素比较假定每个元素的查找概率相等，求查找成功时的平均查找长度。先画出判定树如下(注：mid=?(1+12)/2?=6):30查找元素54,需依次与查找元素90,需依次与30,63,42,54元素比较;30,63,87,95元素比较；3层共查找1+2X2+4X3=17求ASL之前，需要统计每个元素的查找次数。判定树的前次；但最后一层未满，不能用8X4,只能用5X4=20次,所以ASL=1/12(17+20)=37/12"(2)在一棵空的二叉排序树中依次插入关键字序列

12、为12,7,17,11,16,2,13,9,21,4,请画出所得到的二叉排序树。12/、71八2111621/4913验算方法：用中序遍历应得到排序结果：2,4,7,9,11,12,13,16,17,21(5)设哈希表的地址范围为017,哈希函数为：H(key)=key%1&用线性探测法处理冲突，输入关键字序列：(10,24,32,17,31,30,46,47,40,63,49),构造哈希表，试回答下列问题：画出哈希表的示意图；若查找关键字63,需要依次与哪些关键字进行比较若查找关键字60,需要依次与哪些关键字比较假定每个关键字的查找概率相等，求查找成功时的平均查找长度。画表如下：01

13、2345678910111213141516173217634924401030314647查找63,首先要与H(63)=63%16=15号单元内容比较，即63vs31,no;然后顺移，与46,47,32,17,63相比，一共比较了6次！查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空(应当有空标记)，所以应当只比较这一次即可。对于黑色数据元素，各比较1次；共6次；对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=1/11(6+2+3X3+6)=23/11(6)设有一组

14、关键字(9,01,23,14,55,20,84,27),采用哈希函数：H(key)=key%7,表长为10,用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。散列地址0123456789关键字140192384275520?比较次数11123412?平均查找长度：ASLcc=(1+1+1+2+3+4+1+2)/8=15/8以关键字27为例：H(27)=27%7=6(冲突)H1=(6+1)%10=7(冲突)H2=(6+22)%10=0(冲突)H3=(6+33)%10=5所以比较了4次。第8章排序1 .选择题CDBDCBCDBCBCCCA2 .应用题(

15、1)设待排序的关键字序列为12,2,16,30,28,10,16*,20,6,18,试分别写出使用以下排序方法，每趟排序结束后关键字序列的状态。直接插入排序折半插入排序希尔排序(增量选取冒泡排序快速排序简单选择排序堆排序二路归并排序5,3,1)直接插入排序2121630281016*206182121630281016*206182121630281016*206182121628301016*206182101216283016*20618210121616*283020618210121616*202830618261012161618202830折

16、半插入排序排序过程同希尔排序（增量选取5,3,1）102166181216*203028（增量选取5）621210181616*203028（增量选取3）2610121616*18202830（增量选取1）冒泡排序21216281016*2061830212161016*206182830212101616*6182028302101216616*182028302101261616*182028302106121616*182028302610121616*182028302610121616*18202830快速排序12621012283016*2016186261012283016*20

17、161828261012181616*2028301826101216*161820283016*26101216*1618202830左子序列递归深度为1,右子序列递归深度为3简单选择排序2121630281016*20618261630281016*201218261030281616*201218261012281616*203018261012162816*2030182610121616182030282610121616*182028302610121616*18202830二路归并排序2121630102816*20618212163010

18、16*2028618210121616*2028306182 610121616*18202830堆排序第一步，形成初始大根堆（详细过程略），第二步做堆排序。初始排序不是大根堆交换1与10对象交换1与9对象从1到8重新形成堆16*16*121612162610182610183030交换1到6重新形成堆1016121612102616*182616*1820283030交换1到5重新形成堆612121061021616*1821616*1820283030交换121061062121616*181216164重新形成堆202820282028202820282610121616*18202830交换1与3对象6210121616*18202830从1到2重新形成堆交换1与2对象得到结果3 .算法设计题(1)试以单链表为存