数据结构题目+答案

数据结构题目+答案

ID:12862822

大小:35.50 KB

页数:3页

时间:2018-07-19

数据结构题目+答案_第1页
数据结构题目+答案_第2页
数据结构题目+答案_第3页
资源描述:

《数据结构题目+答案》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、1.线性表哟两种存储结构:一是顺序表,二是链表。问1,如果有N个线性表同时并存,并且在处理过程中各表的长度会动态变化,线性表的总数也会有自动改变,在此情况下,应选用那种存储结构?为什么?(2)若线性表的总数基本稳定,且很少进行插入和删除但要求以最快的速度存取线性表中的语速,那么应采用哪种存储结构为什么?答:(1)选链式存储结构。它可动态申请内存空间,不受表长度(即表中元素个数)的影响,插入、删除时间复杂度为O(1)。(2)选顺序存储结构。顺序表可以随机存取,时间复杂度为O(1)。2.如何通过改链的方法,把一个单向链表变成一个与原来链接方向相反的单

2、向链表?答:设该链表带头结点,将头结点摘下,并将其指针域置空。然后从第一元素结点开始,直到最后一个结点为止,依次前插入头结点的后面,则实现了链表的逆置。3设输入序列为23456利用一个栈能得到序列25346么?栈可以用单链表实现么?答:不能得到序列2,5,3,4,6。栈可以用单链表实现,这就是链栈。由于栈只在栈顶操作,所以链栈通常不设头结点。4.用一个数组S(改大小为MAX)作为两个堆栈的共享空间请说明共享方法,栈满/栈空的判断条件,并用C设计入栈操作PUSH(i,x)其中i为0或1,用于表示栈号,x为入栈值。答:两栈共享一向量空间(一维数组),

3、栈底设在数组的两端,两栈顶相邻时为栈满。设共享数组为S[MAX],则一个栈顶指针为-1,另一个栈顶指针为MAX时,栈为空。用C写的入栈操作push(i,x)如下:constMAX=共享栈可能达到的最大容量typedefstructnode{elemtypes[MAX];inttop[2];}anode;anodeds;intpush(inti,elemtypex)//ds为容量有MAX个类型为elemtype的元素的一维数组,由两个栈共享其空间。i的值为0或1,x为类型为elemtype的元素。本算法将x压入栈中。如压栈成功,返回1;否则,返回0

4、。{if(ds.top[1]-ds.top[0]==1){printf(“栈满”);return(0);}switch(i){case0:ds.s[++ds.top[i]]=x;break;case1:ds.s[--ds.top[i]]=x;return(1);}//入栈成功。}5.用栈实现将中缀表达式8-(3+5)*(5-6/2)转换成后缀表达式,画出栈的变化过程图.答:中缀表达式8-(3+5)*(5-6/2)的后缀表达式是:835+562/-*-,表达式生成过程为:中缀表达式exp1转为后缀表达式exp2的规则如下:设操作符栈s,初始为空

5、栈后,压入优先级最低的操作符‘#’。对中缀表达式从左向右扫描,遇操作数,直接写入exp2;若是操作符(记为w),分如下情况处理,直至表达式exp1扫描完毕。(1)w为一般操作符(’+’,’-‘,’*’,’/’等),要与栈顶操作符比较优先级,若w优先级高于栈顶操作符,则入栈;否则,栈顶运算符退栈到exp2,w再与新栈顶操作符作上述比较处理,直至w入栈。(2)w为左括号(’(’),w入栈。(3)w为右括号(’)’),操作符栈退栈并进入exp2,直到碰到左括号为止,左括号退栈(不能进入exp2),右括号也丢掉,达到exp2中消除括号的目的。(4)w为‘

6、#’,表示中缀表达式exp1结束,操作符栈退栈到exp2,直至碰到‘#’,退栈,整个操作结束。这里,再介绍一种简单方法。中缀表达式转为后缀表达式有三步:首先,将中缀表达式中所有的子表达式按计算规则用嵌套括号括起来;接着,顺序将每对括号中的运算符移到相应括号的后面;最后,删除所有括号。例如,将中缀表达式8-(3+5)*(5-6/2)转为后缀表达式。按如上步骤:执行完上面第一步后为:(8-((3+5)*(5-(6/2))));执行完上面第二步后为:(8((35)+(5(62)/)-)*)-;执行完上面第三步后为:835+562/-*-。可用类似方法将

7、中缀表达式转为前缀表达式。6.如果用一个循环数组q[0..m-1]表示队列时,该队列只有一个队列头指针front,不设队列未指针rear,而改设计数器count用以记录队列中节点的个数(1)编写实现队列的山三个基本运算判控,入队,出队(2)队列中能容纳元素的最多个数是多少?答:typedefstruct{elemtpq[m];intfront,count;//front是队首指针,count是队列中元素个数。}cqnode;//定义类型标识符。(1)判空:intEmpty(cqnodecq)//cq是cqnode类型的变量{if(cq.count

8、==0)return(1);elsereturn(0);//空队列}入队:intEnQueue(cqnodecq,elemtpx){if

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。