数据结构题目+答案

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

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