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

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

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

2、-data)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；设置数组低、高端指针下标。whilei/判定t字符向量能否为回文，若是，返回1，否则返回0SeqStacks;inti,len;chartemp;InitStack(len=strlen(t);/求

4、向量长度for(i=0;iclassQueue/循环队列的类定义public:Queue(int=10);Queue()deleteQ;voidEnQueue(Type&item);TypeDeQueue();TypeGetFront();voidMakeEmpty()front=rear=tag=0;/置空队列intIsEmpty()constreturnfront=rear&tag=0;/判队列空否intIsFull()constreturnfront=rear&tag=1;/判队列满否private:intrear,front,tag;/队尾指针、队头指针和队满标志Type*Q;/存放队

5、列元素的数组intm;/队列最大可包容元素个数构造函数templateQueue:Queue(intsz):rear(0),front(0),tag(0),m(sz)/建立一个最大具有m个元素的空队列。Q=newTypem;/创立队列空间assert(Q!=0);/断言:动态存储分配成功与否插入函数templatevoidQueue:EnQueue(Type&item)assert(!IsFull();/判队列能否不满，满则出错处理rear=(rear+1)%m;/队尾位置进1,队尾指针指示实际队尾位置Qrear=item;/进队列tag=1;/标志改1，表示队列不空删除函数templateT

6、ypeQueue:DeQueue()assert(!IsEmpty();/判定队列能否不空，空则出错处理front=(front+1)%m;/队头位置进1,队头指针指示实际队头的前一位置tag=0;/标志改0,表示栈不满returnQfront;/返回原队头元素的值读取队头元素函数templateTypeQueue:GetFront()assert(!IsEmpty();/判定队列能否不空，空则出错处理returnQ(front+1)%m;/返回队头元素的值第4章串、数组和广义表1选择题BBCABBBCBBABDCBC2.综合应用题1已知形式串t=abcaabbabcab写出用KMP法求得的每

7、个字符对应的next和nextval函数值。形式串t的next和nextval值如下：3数组A中，每个元素Ai,j的长度均为32个二进位,行下标从-1到9，列下标从1到11，从首地址S开场连续存放主存储器中，主存储器字长为16位。求：存放该数组所需多少单元？存放数组第4列所有元素至少需多少单元？数组按行存放时，元素A7,4的起始地址是多少？数组按列存放时，元素A4,7的起始地址是多少？每个元素32个二进制位，主存字长16位，故每个元素占2个字长，行下标可平移至1到11。12422223s+1824s+142(4)请将香蕉banana用工具H()Head()，T()Tail()从L中取出。L=(

8、apple,(orange,(strawberry,(banana),peach),pear)HHTHTHTL5写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件字符串中的合法字符为A-Z这26个字母和0-9这10个数字。voidCount/统计输入字符串中数字字符和字母字符的个数。inti，num36；charch；fori0；i2应用题2设一棵二叉树的先序序列：ABDFCEGH，中序序列：BFDAGEHC画出这棵二叉树。画出这棵二叉树的后序线索树。将这棵二叉树转换成对应的树或森林。 (1)(2)3假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.

9、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,21,32100406019213228117106523方案比拟：ABMFD(3)CEMHG2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61方案2的WPL3(0.19+0.32+0

10、.21+0.07+0.06+0.10+0.02+0.03)=3结论：哈夫曼编码优于等长二进制编码3算法设计题以二叉链表作为二叉树的存储构造，编写下面算法：1统计二叉树的叶结点个数。intLeafNodeCount(BiTreeT)if(T=NULL)return0;/假如是空树，则叶子结点个数为0elseif(T-lchild=NULL&T-rchild=NULL)return1;/判定该结点能否是叶子结点左孩子右孩子都为空，若是则返回1elsereturnLeafNodeCount(T-lchild)+LeafNodeCount(T-rchild);3交换二叉树每个结点的左孩子和右孩子。vo

11、idChangeLR(BiTree&T)BiTreetemp;if(T-lchild=NULL&T-rchild=NULL)return;elsetemp=T-lchild;T-lchild=T-rchild;T-rchild=temp;ChangeLR(T-lchild);ChangeLR(T-rchild);第6章图1选择题CBBBCBABAADCCDDB2应用题1已知如图6.27所示的有向图，请给出：每个顶点的入度和出度；邻接矩阵；邻接表；当前位置：文档视界数据构造(c语言版)课后习题答案完好版数据构造(c语言版)课后习题答案完好版当前位置：文档视界数据构造(c语言版)课后习题答案完好版

12、数据构造(c语言版)课后习题答案完好版第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元素比拟；求ASL之前，需要统计每个元素的查

13、找次数。断定树的前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，构造哈希表，试回答下列问题：画出哈希表的示意图；若

14、查找关键字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次，“47需要3次，所以ASL=1/

15、116233+623/116设有一组关键字9，01，23，14，55，20，84，27，采用哈希函数：Hkey=key%7，表长为10，用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。平均查找长度：ASLsucc=1+1+1+2+3+4+1+2/8=15/8以关键字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，试分别写出使用下面排序方法，每趟排序结束后关键字序列的状态。直接插入排序折半插入排序希尔排序增量选取5，3，1冒泡排序快速排序简单项选择择排序堆排序二路归并排序直接插入排序2121630281016*206182121630281016*206182121630281016*206182121628301016*206182101216283016*20618210121616*283020618