《数据结构(c语言版)课后习题答案》由会员分享，可在线阅读，更多相关《数据结构(c语言版)课后习题答案（19页珍藏版）》请在金锄头文库上搜索。
1、第1章绪论5.选择题：CCBDCA6试分析下面各程序段的时间复杂度。(1)O(1)(2) O(m*n)(3)O(n2)(4)O(log3n)(5) 因为x+共执行了n-l+n-2+1=n(n-l)/2,所以执行时间为O(n2)(6) O(n)第2章线性表1. 选择题babadbcabdcddac2. 算法设计题(6)设计一个算法,通过一趟遍历在单链表中确定值最大的结点。ElemTypeMax(LinkListL)if(L-next=NULL)returnNULL;pmax=L-next;/假定第一个结点中数据具有最大值p=L-next-next;while(p!=NULL)/如果下一个结点存在
2、if(p-datapmax-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=q;/*p插入在头结点之后(10)已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为0(1)的算法，该算法删除线性表中所有值为item的数据元素。题目分析在顺序存储
3、的线性表上删除元素，通常要涉及到一系列元素的移动(删第i个元素，第i+1至第n个元素要依次前移)。本题要求删除线性表中所有值为item的数据元素，并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针(i=1，j=n),从两端向中间移动，凡遇到值item的数据元素时，直接将右端元素左移至值为item的数据元素位置。voidDelete(ElemTypeA，intn)A是有n个元素的一维数组，本算法删除A中所有值为item的元素。i=1;j=n；设置数组低、高端指针(下标)。while(ij)while(ij&Ai!=item)i+；若值不为item，左移指针。if(ij)while(ij&A
4、j=item)j；若右端元素值为item,指针左移if(ij)Ai+=Aj-；算法讨论因元素只扫描一趟，算法时间复杂度为0(n)。删除元素未使用其它辅助空间，最后线性表中的元素个数是j。第3章栈和队列1选择题CCDAADABCDDDBCB2.算法设计题(2)回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)根据提示，算法可设计为：/以下为顺序栈的存储结构定义#defineStackSize100/假定预分配的栈空间最多为100个元素typedefcharDataType;/假定栈元
5、素的数据类型为字符typedefstructDataTypedataStackSize;inttop;SeqStack;intIsHuiwen(char*t)/判断t字符向量是否为回文，若是，返回1,否则返回0SeqStacks;inti,len;chartemp;InitStack(&s);len=strlen(t);/求向量长度for(i=0;ilen/2;i+)/将一半字符入栈Push(&s,ti);while(!EmptyStack(&s)/每弹出一个字符与相应字符比较temp=Pop(&s);if(temp!=Si)return0;/不等则返回0elsei+;return1;/比较完
6、毕均相等则返回1(7)假设以数组Qm存放循环队列中的元素，同时设置一个标志tag,以tag=0和tag=1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。【解答】循环队列类定义#includetemplateclassQueue/循环队列的类定义public:Queue(int=10);Queue()deleteQ;voidEnQueue(Type&item);TypeDeQueue();TypeGetFront();voidMakeEmpty()front=rear=tag=0;/
7、置空队列intIsEmpty()constreturnfront=rear&tag=0;/判队列空否intIsFull()constreturnfront=rear&tag=1;/判队列满否private:intrear,front,tag;/队尾指针、队头指针和队满标志Type*Q;/存放队列元素的数组intm;/队列最大可容纳元素个数构造函数templateQueue:Queue(intsz):rear(0),front(0),tag(0),m(sz)/建立一个最大具有m个元素的空队列。Q=newTypem;/创建队列空间assert(Q!=0);/断言:动态存储分配成功与否插入函数tem
8、platevoidQueue:EnQueue(Type&item)assert(!IsFull();rear=(rear+1)%m;Qrear=item;tag=1;删除函数templateTypeQueue:DeQueue()assert(!IsEmpty();front=(front+1)%m;tag=0;returnQfront;读取队头元素函数templateTypeQueue:GetFront()assert(!IsEmpty();returnQ(front+1)%m;/判队列是否不满，满则出错处理/队尾位置进1,队尾指针指示实际队尾位置/进队列/标志改1，表示队列不空/判断队列是否
9、不空，空则出错处理/队头位置进1,队头指针指示实际队头的前一位置/标志改0,表示栈不满/返回原队头元素的值/判断队列是否不空，空则出错处理/返回队头元素的值第4章串、数组和广义表1选择题BBCABBBCBBABDCBC2. 综合应用题(1) 已知模式串t=abcaabbabcab写出用KMP法求得的每个字符对应的next和nextval函数值。模式串t的next和nextval值如下：j123456789101112t串abcaabbabcabnextj011122312345nextvalj011021301105(3) 数组A中，每个元素Ai,j的长度均为32个二进位，行下标从-1到9,列
10、下标从1到11，从首地址S开始连续存放主存储器中，主存储器字长为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=(apple,(orange,(strawberry,(banana),peach),pear)H(H(T(H(T(H(T(L)(5)
11、写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件(字符串中的合法字符为A-Z这26个字母和0-9这10个数字)。voidCount()/统计输入字符串中数字字符和字母字符的个数。inti,num36；charch；for(i=0；i36；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；i10；i+)/输出数字字符的个数printf“数字d的个数=%dn”，i，numi)；for(i=10
12、；i36；i+)/求出字母字符的个数printf“字母字符c的个数=%dn”，i+55,numi)；/算法结束。第5章树和二叉树1选择题ADDCACCBDCCCACC2应用题2)设一棵二叉树的先序序列：ABDFCEGH，中序序列：BFDAGEHC画出这棵二叉树。 画出这棵二叉树的后序线索树。 将这棵二叉树转换成对应的树(或森林)。ACBMDEMFG(3)(40)1921(11)6(5)2字母编号对应编码出现频率111000.072000.193111100.02411100.065100.32方案比较：字母编号对应编码出现频率10000.0720010.1930100.0240110.0651
13、000.326003方案1的WPL3)假设用于通信的电文仅由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,32100)(60)32(28)(17)7102(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的WPL=3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3结论：哈夫曼编码优于等长二进制编码3. 算法设计题以二叉链表作为二叉树的存储结构，编写以下算法：(1)统计二叉树的叶结点个数。intLeafNodeCount(BiTreeT)if(T=NULL)return0;/如果是空树，则叶子结点个数为0elseif(T-lchild=NUL
