数据构造c语言版课后习题答案完好版.docx

《数据构造c语言版课后习题答案完好版.docx》由会员分享，可在线阅读，更多相关《数据构造c语言版课后习题答案完好版.docx（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据构造c语言版课后习题答案完好版第1章绪论5选择题：CCBDCA6试分析下面各程序段的时间复杂度。1O12Om*n3On24Olog3n5由于x+共执行了n-1+n-2+1=n(n-1)/2，所以执行时间为On26O(n)第2章线性表1选择题babadbcabdcddac2算法设计题6设计一个算法，通过一趟遍历在单链表中确定值最大的结点。ElemTypeMax(LinkListL)if(L-next=NULL)returnNULL;pmax=L-next;/假定第一个结点中数据具有最大值p=L-next-next;while(p!=NULL)/假如下一个结点存在if(p-datapmax-d

2、ata)pmax=p;p=p-next;returnpmax-data;7设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。voidinverse(LinkList&L)/逆置带头结点的单链表Lp=L-next;L-next=NULL;while(p)q=p-next;/q指向*p的后继p-next=L-next;L-next=p;/*p插入在头结点之后p=q;10已知长度为n的线性表A采用顺序存储构造，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。题目分析在顺序存储的线性表上删除元素，通常要涉及到一系列元

3、素的移动删第i个元素，第i+1至第n个元素要依次前移。此题要求删除线性表中所有值为item的数据元素，并未要求元素间的相对位置不变。因而能够考虑设头尾两个指针i=1，j=n，从两端向中间移动，凡碰到值item的数据元素时，直接将右端元素左移至值为item的数据元素位置。voidDeleteElemTypeA，intnA是有n个元素的一维数组，本算法删除A中所有值为item的元素。i=1；j=n；设置数组低、高端指针下标。whileiintIsHuiwen(char*t)/判定t字符向量能否为回文，若是，返回1，否则返回0SeqStacks;inti,len;chartemp;InitStack

4、(len=strlen(t);/求向量长度for(i=0;i当前位置：文档视界数据构造c语言版课后习题答案完好版数据构造c语言版课后习题答案完好版第4章串、数组和广义表1选择题BBCABBBCBBABDCBC2.综合应用题1已知形式串t=abcaabbabcab写出用KMP法求得的每个字符对应的next和nextval函数值。形式串t的next和nextval值如下：到9，列下标从1到11，从首地址S开场连续存放主存储器中，主存储器字长为16位。求：存放该数组所需多少单元？存放数组第4列所有元素至少需多少单元？数组按行存放时，元素A7,4的起始地址是多少？数组按列存放时，元素A4,7的起始地址

5、是多少？每个元素32个二进制位，主存字长16位，故每个元素占2个字长，行下标可平移至1到11。12422223s+1824s+142(4)请将香蕉banana用工具H()Head()，T()Tail()从L中取出。L=(apple,(orange,(strawberry,(banana),peach),pear)HHTHTHTL5写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件字符串中的合法字符为A-Z这26个字母和0-9这10个数字。voidCount/统计输入字符串中数字字符和字母字符的个数。inti，num36；charch；fori0；i第5章树和二叉树1选择题ADD

6、CACCBDCCCACC2应用题2设一棵二叉树的先序序列：ABDFCEGH，中序序列：BFDAGEHC画出这棵二叉树。画出这棵二叉树的后序线索树。将这棵二叉树转换成对应的树或森林。(1)(2)3假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计赫夫曼编码。试设计另一种由二进制表示的等长编码方案。对于上述实例，比拟两种方案的优缺点。解：方案1；哈夫曼编码先将概率放大100倍，以方便构造哈夫曼树。w=7,19,2,6,32,3,21,10，按哈夫曼规则：【2,3，6,(7,10)】,19

7、,21,3210040601921322817117106523方案比拟：elseif(T-lchild=NULL&T-rchild=NULL)return1;/判定该结点能否是叶子结点左孩子右孩子都为空，若是则返回1elsereturnLeafNodeCount(T-lchild)+LeafNodeCount(T-rchild);3交换二叉树每个结点的左孩子和右孩子。voidChangeLR(BiTree&T)ABMFD(3)CEMHGBiTreetemp;if(T-lchild=NULL&T-rchild=NULL)return;elsetemp=T-lchild;T-lchild=T-r

8、child;T-rchild=temp;ChangeLR(T-lchild);ChangeLR(T-rchild);第6章图1选择题CBBBCBABAADCCDDB2应用题1已知如图6.27所示的有向图，请给出：每个顶点的入度和出度；邻接矩阵；邻接表；逆邻接表。2已知如图6.28所示的无向网，请给出：邻接矩阵；邻接表；最小生成树图6.28无ab4c3ba4c5d5e9ca3b5d5h5db5c5e7f6g5h4eb9d7f3fd6e3g2gd5f2h6hc5d4g63已知图的邻接矩阵如6.29所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。4有向网如图6.29所示，试

9、用迪杰斯特拉算法求出从顶点a到其他各顶点间的最短途径，完成表6.9。第7章查找1选择题CDCABCCCDCBCADA2应用题1假定对有序表：3，4，5，7，24，30，42，54，63，72，87，95进行折半查找，试回答下列问题：画出描绘折半查找经过的断定树；若查找元素54，需依次与哪些元素比拟？若查找元素90，需依次与哪些元素比拟？假定每个元素的查找概率相等，求查找成功时的平均查找长度。先画出断定树如下注：mid=?(1+12)/2?=6：30563374287424547295查找元素54，需依次与30,63,42,54元素比拟；查找元素90，需依次与30,63,87,95元素比拟；求A

10、SL之前，需要统计每个元素的查找次数。断定树的前3层共查找12243=17次；但最后一层未满，不能用84，只能用54=20次，所以ASL1/12172037/123.082在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉排序树。1271721116214913验算方法：用中序遍历应得到排序结果：2,4,7,9,11,12,13,16,17，215设哈希表的地址范围为017，哈希函数为：Hkey=key%16。用线性探测法处理冲突，输入关键字序列：10，24，32，17，31，30，46，47，40，63，49，构造哈希表，试回答下

11、列问题：画出哈希表的示意图；若查找关键字63，需要依次与哪些关键字进行比拟？若查找关键字60，需要依次与哪些关键字比拟？假定每个关键字的查找概率相等，求查找成功时的平均查找长度。画表如下：查找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次，“

12、47需要3次，所以ASL=1/116233+623/116设有一组关键字9，01，23，14，55，20，84，27，采用哈希函数：Hkey=key%7，表长为10，用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希表，并计算查找成功的succ以关键字27为例：H27=27%7=6冲突H1=6+1%10=7冲突H2=6+22%10=0冲突H3=6+33%10=5所以比拟了4次。第8章排序1选择题CDBDCBCDBCBCCCA2应用题1设待排序的关键字序列为12，2，16，30，28，10，16*，20，6，18，试分别写出使用下面排序方法，每趟排序结束后关键字序列的状态。直接插入排

13、序折半插入排序希尔排序增量选取5，3，1冒泡排序快速排序简单项选择择排序堆排序二路归并排序直接插入排序2121630281016*206182121630281016*206182121630281016*206182121628301016*206182101216283016*20618210121616*283020618210121616*2028306182610121616*202830182610121616*18202830折半插入排序排序经过同希尔排序增量选取5，3，1102166181216*203028增量选取5621210181616*203028增量选取3261012

14、1616*18202830增量选取1冒泡排序21216281016*2061830212161016*206182830212101616*6182028302101216616*182028302101261616*182028302106121616*182028302610121616*182028302610121616*18202830快速排序12621012283016*2016186261012283016*20161828261012181616*2028301826101216*161820283016*26101216*1618202830左子序列递归深度为1，右子序列递归

15、深度为3简单项选择择排序2121630281016*20618261630281016*201218261030281616*201218261012281616*203018261012162816*2030182610121616*282030182610121616*182030282610121616*182028302610121616*18202830二路归并排序2121630102816*2061821216301016*2028618210121616*2028306182610121616*18202830堆排序第一步,构成初始大根堆具体经过略，第二步做堆排序。初始排序不是大根堆构成初始大根堆交换1与10对象从1到9重新构成堆