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

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

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-datapm

2、ax-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根据提示，算法可设计为：/下面为顺序栈的存储构造定义#defineStackSize100/假定预分配的栈空间最多为100个元素typedefcharDat

4、aType;/假定栈元素的数据类型为字符typedefstructDataTypedataStackSize;inttop;SeqStack;intIsHuiwen(char*t)/判定t字符向量能否为回文，若是，返回1，否则返回0SeqStacks;inti,len;chartemp;InitStack(len=strlen(t);/求向量长度for(i=0;i当前位置：文档视界数据构造(c语言版)课后习题答案完好版资料数据构造(c语言版)课后习题答案完好版资料Type*Q;/存放队列元素的数组intm;/队列最大可包容元素个数构造函数templateQueue:Queue(intsz):r

5、ear(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，表示队列不空删除函数templateTypeQueue:DeQueue()assert(!IsEmpty();/判定队列能否不空，空则出错处理fro

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

7、,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=(apple,(orange,(strawberry,(banana),peach),pear)HHTHTHTL

8、当前位置：文档视界数据构造(c语言版)课后习题答案完好版资料数据构造(c语言版)课后习题答案完好版资料ADDCACCBDCCCACC2应用题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,21,32ABMFD (3)CEMHG当前位置：文档视界数据构造(c语言版)课后习题答案完好版资料数据构造(c语言版)课后习题答案完好版资料