数据结构C语言版课后习题全套完整答案及详解 答案由李冬梅老师撰写.docx
《数据结构C语言版课后习题全套完整答案及详解 答案由李冬梅老师撰写.docx》由会员分享,可在线阅读,更多相关《数据结构C语言版课后习题全套完整答案及详解 答案由李冬梅老师撰写.docx(51页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、数据结构(C语言版)课后习题全套完整答案及详解(答案由李冬梅老师撰写)这时OPND栈中只有一个数就是结果。算法描绘floatexpr()/从键盘输入逆波兰表达式以表示输入完毕本算法求逆波兰式表达式的值。floatOPND30;/OPND是操作数栈。init(OPND);/两栈初始化。floatnum0.0;/数字初始化。cinx;/x是字符型变量。while(x!KaTeXparseerror:Expected,gotatposition51:while(x0 x9)|x.cout“后缀表达式的值为pop(OPND);/算法完毕。算法讨论假设输入的后缀表达式是正确的未作错误检查。算法中拼数局部
2、是核心。假设遇到大于等于0且小于等于9的字符认为是数。这种字符的序号减去字符0的序号得出数。对于整数每读入一个数字字符前面得到的局部数要乘上10再加新读入的数得到新的局部数。当读到小数点认为数的整数局部已完要接着处理小数局部。小数局部的数要除以10或者10的幂数变成特别位百分位千分位数等等与前面局部数相加。在拼数经过中假设遇非数字字符表示数已拼完将数压入栈中并且将变量num恢复为0准备下一个数。这时对新读入的字符进入、-、*、/及空格的判断因此在完毕处理数字字符的case后不能参加break语句。5假设以I以及O分别表示入栈以及出栈操作。栈的初态以及终态均为空入栈以及出栈的操作序列可表示为仅由
3、I以及O组成的序列称可以操作的序列为合法序列否那么称为非法序列。下面所示的序列中哪些是合法的A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO通过对的分析写出一个算法断定所给的操作序列是否合法。假设合法返回true否那么返回false假定被断定的操作序列已存入一维数组中。答案A以及D是合法序列B以及C是非法序列。设被断定的操作序列已存入一维数组A中。intJudge(charA)/判断字符数组A中的输入输出序列是否是合法序列。如是返回true否那么返回false。i/i为下标。jk/j以及k分别为I以及字母O的的个数。while(Ai!0)/当未到字符数组尾就作。
4、switch(Ai)caseI:jbreak;/入栈次数增1。caseO:kif(kj)cout“序列非法ednlexit(0);i/不管Ai是I或者O指针i均后移。if(j!k)cout“序列非法endlreturn(false);elsecout“序列合法endlreturn(true);/算法完毕。算法讨论在入栈出栈序列即由I以及O组成的字符串的任一位置入栈次数I的个数都必须大于等于出栈次数即O的个数否那么视作非法序列立即给出信息退出算法。整个序列即读到字符数组中字符串的完毕标记0入栈次数必须等于出栈次数题目中要求栈的初态以及终态都为空否那么视为非法序列。 (6假设以带头结点的循环链表表
5、示队列并且只设一个指针指向队尾元素站点(注意不设头指针)试编写相应的置空队、判队空、入队以及出队等算法。题目分析置空队就是建立一个头节点并把头尾指针都指向头节点头节点是不存放数据的判队空就是当头指针等于尾指针时队空入队时将新的节点插入到链队列的尾部同时将尾指针指向这个节点出队时删除的是队头节点要注意队列的长度大于1还是等于1的情况这个时候要注意尾指针的修改假如等于1那么要删除尾指针指向的节点。算法描绘/先定义链队构造:typedefstructqueuenodeDatatypedata;structqueuenode*next;QueueNode;/以上是结点类型的定义typedefstruc
6、tqueuenode*rear;LinkQueue;/只设一个指向队尾元素的指针 (1)置空队voidInitQueue(LinkQueue*Q)/置空队就是使头结点成为队尾元素QueueNode*s;Q-rearQ-rear-next;/将队尾指针指向头结点while(Q-rear!Q-rear-next)/当队列非空将队中元素逐个出队sQ-rear-next;Q-rear-nexts-next;deletes;/回收结点空间 (2)判队空intEmptyQueue(LinkQueue*Q)/判队空。当头结点的next指针指向自己时为空队returnQ-rear-next-nextQ-rea
7、r-next; (3)入队voidEnQueue(LinkQueue*Q,Datatypex)/入队。也就是在尾结点处插入元素QueueNode*pnewQueueNode;/申请新结点p-datap-nextQ-rear-next;/初始化新结点并链入Q-rear-nextQ-rear/将尾指针移至新结点 (4)出队DatatypeDeQueue(LinkQueue*Q)/出队,把头结点之后的元素摘下Datatypet;QueueNode*p;if(EmptyQueue(Q)Error(“Queueunderflow);pQ-rear-next-next;/p指向将要摘下的结点xp-data
8、;/保存结点中数据if(pQ-rear)/当队列中只有一个结点时p结点出队后要将队尾指针指向头结点Q-rearQ-rear-next;Q-rear-nextp-next;elseQ-rear-next-nextp-next;/摘下结点pdeletep;/释放被删结点returnx;7假设以数组Qm存放循环队列中的元素,同时设置一个标志tag以tag0以及tag1来区别在队头指针(front)以及队尾指针(rear)相等时队列状态为“空还是“满。试编写与此构造相应的插入(enqueue)以及删除(dlqueue)算法。算法描绘(1)初始化SeQueueQueueInit(SeQueueQ)/初始
9、化队列Q.frontQ.rearQ.tagreturnQ;(2)入队SeQueueQueueIn(SeQueueQ,inte)/入队列if(Q.tag1)(Q.rearQ.front)cout“队列已满endl;elseQ.rear(Q.rear1)%m;Q.dataQ.rearif(Q.tag0)Q.tag/队列已不空returnQ;(3)出队ElemTypeQueueOut(SeQueueQ)/出队列if(Q.tag0)cout“队列为空endl;exit(0);elseQ.front(Q.front1)%m;eQ.dataQ.front;if(Q.frontQ.rear)Q.tag/空队
10、列return(e); (8假如允许在循环队列的两端都可以进展插入以及删除操作。要求写出循环队列的类型定义写出“从队尾删除以及“从队头插入的算法。题目分析用一维数组v0M-1实现循环队列其中M是队列长度。设队头指针front以及队尾指针rear约定front指向队头元素的前一位置rear指向队尾元素。定义frontrear时为队空(rear1)%mfront为队满。约定队头端入队向下标小的方向开展队尾端入队向下标大的方向开展。算法描绘#defineM队列可能到达的最大长度typedefstructelemtpdataM;intfront,rear;cycqueue;elemtpdelqueue
11、(cycqueueQ)/Q是如上定义的循环队列本算法实现从队尾删除假设删除成功返回被删除元素否那么给出出错信息。if(Q.frontQ.rear)cout“队列空endl;exit(0);Q.rear(Q.rear-1M)%M;/修改队尾指针。return(Q.data(Q.rear1M)%M);/返回出队元素。/从队尾删除算法完毕voidenqueue(cycqueueQ,elemtpx)/Q是顺序存储的循环队列本算法实现“从队头插入元素x。if(Q.rear(Q.front-1M)%M)cout“队满endl;exit(0)Q.dataQ.front/x入队列Q.front(Q.front
12、-1M)%M;/修改队头指针。/完毕从队头插入算法。9已知Ackermann函数定义如下:写出计算Ack(m,n)的递归算法并根据此算法给出出Ack(2,1)的计算经过。写出计算Ack(m,n)的非递归算法。算法描绘intAck(intm,n)if(m0)return(nelseif(m!0n0)return(Ack(m-1,1);elsereturn(Ack(m-1,Ack(m,m-1);/算法完毕Ack(2,1)的计算经过Ack(2,1)Ack(1,Ack(2,0)/因m0,n0而得Ack(1,Ack(1,1)/因m0,n0而得Ack(1,Ack(0,Ack(1,0)/因m0,n0而得Ac
13、k(1,Ack(0,Ack(0,1)/因m0,n0而得Ack(1,Ack(0,2)/因m0而得Ack(1,3)/因m0而得Ack(0,Ack(1,2)/因m0,n0而得Ack(0,Ack(0,Ack(1,1)/因m0,n0而得Ack(0,Ack(0,Ack(0,Ack(1,0)/因m0,n0而得Ack(0,Ack(0,Ack(0,Ack(0,1)/因m0,n0而得Ack(0,Ack(0,Ack(0,2)/因m0而得Ack(0,Ack(0,3)/因m0而得Ack(0,4)/因n0而得5/因n0而得intAckerman(intm,intn)intakmMN;inti,j;for(jjj)akm0
14、jjfor(iii)akmi0akmi-11;for(jjj)akmijakmi-1akmij-1;return(akmmn);/算法完毕10已知f为单链表的表头指针,链表中存储的都是整型数据试写出实现以下运算的递归算法求链表中的最大整数求链表的结点个数求所有整数的平均值。算法描绘intGetMax(LinkListp)if(!p-next)returnp-data;elseintmaxGetMax(p-next);returnp-datamax?p-data:max;intGetLength(LinkListp)if(!p-next)return1;elsereturnGetLength(p
15、-next)doubleGetAverage(LinkListp,intn)if(!p-next)returnp-data;elsedoubleaveGetAverage(p-next,n-1);return(ave*(n-1)p-data)/n;第4章串、数组以及广义表1选择题1串是一种特殊的线性表其特殊性表达在。A可以顺序存储B数据元素是一个字符C可以链式存储D数据元素可以是多个字符假设答案B2串下面关于串的的表达中是不正确的A串是字符的有限序列B空串是由空格构成的串C形式匹配是串的一种重要运算D串既可以采用顺序存储可以以采用链式存储答案B解释空格常常是串的字符集合中的一个元素有一个或者多
16、个空格组成的串成为空格串零个字符的串成为空串其长度为零。3串“ababaaababaa的next数组为。A012345678999B012121111212C011234223456D0123012322345答案C4串“ababaabab的nextval为。A010104101B010102101C010100011D010101011答案A5串的长度是指。A串中所含不同字母的个数B串中所含字符的个数C串中所含不同字符的个数D串中所含非空格字符的个数答案B解释串中字符的数目称为串的长度。6假设以行序为主序存储二维数组Aarray1100,1100设每个数据元素占2个存储单元基地址为10那么L
17、OC5,5。A808B818C1010D1020答案B解释以行序为主那么LOC5,55-11005-1210818。7设有数组Ai,j数组的每个元素长度为3字节i的值为1到8j的值为1到10数组从内存首地址BA开场顺序存放当用以列为主存放时元素A5,8的存储首地址为。ABA141BBA180CBA222DBA225答案B解释以列序为主那么LOC5,88-185-13BABA180。8设有一个10阶的对称矩阵A采用压缩存储方式以行序为主存储a11为第一元素其存储地址为1每个元素占一个地址空间那么a85的地址为。A13B32C33D40答案C9假设对n阶对称矩阵A以行序为主序方式将其下三角形的元素
18、(包括主对角线上所有元素)依次存放于一维数组B1(n(n1)/2中那么在B中确定aijij的位置k的关系为。Ai(i-1)/2jBj(j-1)/2iCi(i1)/2jDj(j1)/2i答案B10二维数组A的每个元素是由10个字符组成的串其行下标i0,1,8,列下标j1,2,10。假设A按行先存储元素A8,5的起始地址与当A按列先存储时的元素的起始地址一样。设每个字符占一个字节。AA8,5BA3,10C.A5,8DA0,9答案B解释设数组从内存首地址M开场顺序存放假设数组按行先存储元素A8,5的起始地址为M8-0*105-11M84假设数组按列先存储易计算出元素A3,10的起始地址为M10-19
19、3-01M84。应选B。11设二维数组A1m1n即m行n列按行存储在数组B1mn中那么二维数组元素Ai,j在一维数组B中的下标为。A(i-1)njB(i-1)nj-1Ci(j-1)Djmi-1答案A解释特殊值法。取ij1易知A1,1的的下标为1四个选项中仅有A选项能确定的值为1应选A。12数组A04,-1-3,57中含有元素的个数。A55B45C36D16答案B解释共有53345个元素。13广义表A(a,b,(c,d),(e,(f,g)那么Head(Tail(Head(Tail(Tail(A)的值为。A(g)B(d)CcDd答案D解释Tail(A)(b,(c,d),(e,(f,g)Tail(T
20、ail(A)(c,d),(e,(f,g)Head(Tail(Tail(A)(c,d)Tail(Head(Tail(Tail(A)(d)Head(Tail(Head(Tail(Tail(A)d。14广义表(a,b,c,d)的表头是表尾是。AaB()C(a,b,c,d)D(b,c,d)答案C、B解释表头为非空广义表的第一个元素可以是一个单原子可以以是一个子表(a,b,c,d)的表头为一个子表(a,b,c,d)表尾为除去表头之外由其余元素构成的表表为一定是个广义表(a,b,c,d)的表尾为空表()。15设广义表L(a,b,c)那么L的长度以及深度分别为。A1以及1B1以及3C1以及2D2以及3答案C
21、解释广义表的深度是指广义表中展开后所含括号的层数广义表的长度是指广义表中所含元素的个数。根据定义易知L的长度为1深度为2。2应用题1已知形式串tabcaabbabcab写出用KMP法求得的每个字符对应的next以及nextval函数值。答案形式串t的next以及nextval值如下j123456789101112t串abcaabbabcabnextj011122312345nextvalj0110213011052设目的为t“abcaabbabcabaacbacba,形式为p“abcabaa计算形式p的naxtval函数值不写出算法,只画出利用KMP算法进展形式匹配时每一趟的匹配经过。答案p的
22、nextval函数值为0110132。p的next函数值为0111232。利用KMP(改良的nextval)算法每趟匹配经过如下第一趟匹配abcaabbabcabaacbacbaabcab(i5,j5)第二趟匹配abcaabbabcabaacbacbaabc(i7,j3)第三趟匹配abcaabbabcabaacbacbaa(i7,j1)第四趟匹配abcaabbabcabaacbacba(成功)abcabaa(i15,j8)3数组A中每个元素Ai,j的长度均为32个二进位,行下标从-1到9列下标从1到11从首地址S开场连续存放主存储器中主存储器字长为16位。求存放该数组所需多少单元存放数组第4列
23、所有元素至少需多少单元数组按行存放时元素A7,4的起始地址是多少数组按列存放时元素A4,7的起始地址是多少答案每个元素32个二进制位主存字长16位故每个元素占2个字长行下标可平移至1到11。12422223s1824s142 (4)请将香蕉banana用工具H()Head()T()Tail()从L中取出。L(apple,(orange,(strawberry,(banana),peach),pear)答案HHTHTHTL3算法设计题1写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件字符串中的合法字符为A-Z这26个字母以及0-9这10个数字。题目分析由于字母共26个加上数字符
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构C语言版课后习题全套完整答案及详解 答案由李冬梅老师撰写 数据结构 语言版 课后 习题 全套 完整 答案 详解 李冬梅 老师 撰写
限制150内