《数据结构(C语言版)第三四章习题答案解析》由会员分享，可在线阅读，更多相关《数据结构(C语言版)第三四章习题答案解析（15页珍藏版）》请在金锄头文库上搜索。
1、.第3章 栈和队列习题1选择题1若让元素1,2,3,4,5依次进栈,则出栈次序不可能出现在 种情况。A5,4,3,2,1 B2,1,5,4,3 C4,3,1,2,5 D2,3,5,4,12若已知一个栈的入栈序列是1,2,3,n,其输出序列为p1,p2,p3,pn,若p1=n,则pi为 。 Ai Bn-i Cn-i+1 D不确定3数组用来表示一个循环队列,为当前队列头元素的前一位置,为队尾元素的位置,假定队列中元素的个数小于,计算队列中元素个数的公式为 。Ar-f B%n Cn+r-f Dn+r-f%n4链式栈结点为：,top指向栈顶.若想摘除栈顶结点,并将删除结点的值保存到x中,则应执行操作。
2、Ax=top-data;top=top-link； Btop=top-link;x=top-link； Cx=top;top=top-link； Dx=top-link；5设有一个递归算法如下 int fact /n大于等于0 ifn return 1; else return n*fact; 则计算fact需要调用该函数的次数为。An+1Bn-1C nD n+26栈在中有所应用。A递归调用B函数调用C表达式求值D前三个选项都有7为解决计算机主机与打印机间速度不匹配问题,通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是。
3、A队列 B栈 C 线性表 D有序表8设栈S和队列Q的初始状态为空,元素e1、e2、e3、e4、e5和e6依次进入栈S,一个元素出栈后即进入Q,若6个元素出队的序列是e2、e4、e3、e6、e5和e1,则栈S的容量至少应该是。A2 B3 C4 D 69在一个具有n个单元的顺序栈中,假设以地址高端作为栈底,以top作为栈顶指针,则当作进栈处理时,top的变化为。 Atop不变 Btop=0 Ctop- Dtop+10设计一个判别表达式中左,右括号是否配对出现的算法,采用数据结构最佳。A线性表的顺序存储结构B队列C. 线性表的链式存储结构 D. 栈11用链接方式存储的队列,在进行删除运算时。A. 仅
4、修改头指针 B. 仅修改尾指针C. 头、尾指针都要修改 D. 头、尾指针可能都要修改12循环队列存储在数组A0.m中,则入队时的操作为。A. rear=rear+1 B. rear=% C. rear=%m D. rear=% 13最大容量为n的循环队列,队尾指针是rear,队头是front,则队空的条件是。 A. %n=front B. rear=front Crear+1=front D. %n=front14栈和队列的共同点是。A. 都是先进先出 B. 都是先进后出C. 只允许在端点处插入和删除元素 D. 没有共同点15一个递归算法必须包括。A. 递归部分B. 终止条件和递归部分C. 迭
5、代部分 D. 终止条件和迭代部分2回文是指正读反读均相同的字符序列,如abba和abdba均是回文,但good不是回文。试写一个算法判定给定的字符向量是否为回文。根据提示,算法可设计为：/以下为顺序栈的存储结构定义#define StackSize 100 /假定预分配的栈空间最多为100个元素typedef char DataType;/假定栈元素的数据类型为字符typedef structDataType dataStackSize;int top;SeqStack;int IsHuiwen/判断t字符向量是否为回文,若是,返回1,否则返回0SeqStack s;int i , len;c
6、har temp;InitStack;len=strlen; /求向量长度for i=0; i/将一半字符入栈Push;while !EmptyStack/ 每弹出一个字符与相应字符比较temp=Pop ;if return 0 ;/ 不等则返回0else i+;return 1 ; / 比较完毕均相等则返回 13设从键盘输入一整数的序列：a1, a2, a3,an,试编写算法实现：用栈结构存储输入的整数,当ai-1时,将ai进栈；当ai=-1时,输出栈顶整数并出栈。算法应对异常情况入栈满等给出相应的信息。#define maxsize 栈空间容量void InOutS /s是元素为整数的栈,
7、本算法进行入栈和退栈操作。 int top=0; /top为栈顶指针,定义top=0时为栈空。fori=1; i /n个整数序列作处理。 scanf; /从键盘读入整数序列。if / 读入的整数不等于-1时入栈。ifprintf;exit;else s+top=x; /x入栈。else /读入的整数等于-1时退栈。 ifprintf;exit; else printf； /算法结束。4从键盘上输入一个后缀表达式,试编写算法计算表达式的值。规定：逆波兰表达式的长度不超过一行,以$符作为输入结束,操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如：234 34+2*$。 题目分析逆波
8、兰表达式求值规则如下：设立运算数栈OPND,对表达式从左到右扫描,当表达式中扫描到数时,压入OPND栈。当扫描到运算符时,从OPND退出两个数,进行相应运算,结果再压入OPND栈。这个过程一直进行到读出表达式结束符$,这时OPND栈中只有一个数,就是结果。float expr/从键盘输入逆波兰表达式,以$表示输入结束,本算法求逆波兰式表达式的值。float OPND30; / OPND是操作数栈。init; /两栈初始化。float num=0.0; /数字初始化。 scanf ;/x是字符型变量。while switch case0=x=9:while=0&x|x=. /拼数if /处理整数
9、num=num*10+ord-ord; scanf;else /处理小数部分。 scale=10.0; scanf;while=0&x num=num+ord-ord/scale; scale=scale*10; scanf; /else push; num=0.0;/数压入栈,下个数初始化case x= :break; /遇空格,继续读下一个字符。case x=+:pushOPND,pop+pop;break;case x=-:x1=pop;x2=pop;push;break;case x=*:pushOPND,pop*pop;break;case x=/:x1=pop;x2=pop;pus
10、h;break;default: /其它符号不作处理。 /结束switch scanf;/读入表达式中下一个字符。 /结束whilex！=$ printf后缀表达式的值为%f,pop;/算法结束。算法讨论假设输入的后缀表达式是正确的,未作错误检查。算法中拼数部分是核心。若遇到大于等于0且小于等于9的字符,认为是数。这种字符的序号减去字符0的序号得出数。对于整数,每读入一个数字字符,前面得到的部分数要乘上10再加新读入的数得到新的部分数。当读到小数点,认为数的整数部分已完,要接着处理小数部分。小数部分的数要除以10或10的幂数变成十分位,百分位,千分位数等等,与前面部分数相加。在拼数过程中,若遇
11、非数字字符,表示数已拼完,将数压入栈中,并且将变量num恢复为0,准备下一个数。这时对新读入的字符进入+、-、*、/及空格的判断,因此在结束处理数字字符的case后,不能加入break语句。5假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空,入栈和出栈的操作序列可表示为仅由I和O组成的序列,称可以操作的序列为合法序列,否则称为非法序列。下面所示的序列中哪些是合法的？ A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO通过对的分析,写出一个算法,判定所给的操作序列是否合法。若合法,返回true,否则返回false假定被判定的操作序列已存入一维数组中。A和D是合法序列,B和C 是非法序列。设被判定的操作序列已存入一维数组A中。int Judge /判断字符数组A中的输入输出序列是否是合法序列。如是,返回true,否则返回false。
