栈与队列习题参考答案
更新时间:2024-03-25 08:35:01 阅读量: 综合文库 文档下载
- 栈和队列的共同点推荐度:
- 相关推荐
习题三参考答案
备注: 红色字体标明的是与书本内容有改动的内容。
一、选择题
1. 在栈中存取数据的原则是( B )。
A. 先进先出 B. 先进后出 C. 后进后出 D. 没有限制
2.若将整数1、2、3、4依次进栈,则不可能得到的出栈序列是( D )。 A.1234 B. 1324 C. 4321 D. 1423 3.在链栈中,进行出栈操作时( B )。
A.需要判断栈是否满 B. 需要判断栈是否为空 C. 需要判断栈元素的类型 D. 无需对栈作任何差别
4.在顺序栈中,若栈顶指针top指向栈顶元素的下一个存储单元,且顺序栈的最大容量是maxSize,则顺序栈的判空条件是( A )。
A.top==0 B.top==-1 C. top==maxSize D.top==maxSize-1
5.在顺序栈中,若栈顶指针top指向栈顶元素的下一个存储单元,且顺序栈的最大容量是maxSize。则顺序栈的判满的条件是( C )。
A.top==0 B.top==-1 C. top==maxSize D.top==maxSize-1 6.在队列中存取数据元素的原则是( A )。
A.先进先出 B. 先进后出 C. 后进后出 D. 没有限制
7.在循环顺序队列中,假设以少用一个存储单元的方法来区分队列判满和判空的条件,front和rear分别为队首和队尾指针,它们分别指向队首元素和队尾元素的下一个存储单元,队列的最大存储容量为maxSize,则队列的判空条件是( A )。
A.front==rear B. front!=rear
C. front==rear+1 D. front==(rear+1)% maxSize
8.在循环顺序队列中,假设以少用一个存储单元的方法来区分队列判满和判空的条件,front和rear分别为队首和队尾指针,它们分别指向队首元素和队尾元素的下一个存储单元,队列的最大存储容量为maxSize,则队列的判满条件是( D )。
A.front==rear B. front!=rear
C. front==rear+1 D. front==(rear+1)% maxSize
9. 在循环顺序队列中,假设以少用一个存储单元的方法来区分队列判满和判空的条件,front和rear分别为队首和队尾指针,它们分别指向队首元素和队尾元素的下一个存储单元,队列的最大存储容量为maxSize,则队列的长度是( C )。
A.rear-front B. rear-front+1
C. (rear-front+maxSize)%maxSize D. (rear-front+1)%maxSize
10.设长度为n的链队列采用单循环链表加以表示,若只设一个头指针指向队首元素,则入队操作的时间复杂度为( B )。
A.O(1) B.O(n) C.O(log2n) D.O(n2) 二、填空题
1. 栈是一种操作受限的特殊线性表,其特殊性体现在其插入和删除操作都限制在 表尾 进行。允许插入和删除操作的一端称为 栈顶 ,而另一端称为 栈底 。栈具有 后进先出 的特点。
2. 栈也有两种存储结构,一种是 顺序存储 ,另一种是 链式存储 ;以这两种存储结构存储的栈分别称为 顺序栈 和 链栈 。
3. 在顺序栈中,假设栈顶指针top是指向栈顶元素的下一个存储单元,则顺序栈判空的条件是 top==0 ; 栈顶
元素的访问形式是 stackElem[top-1] ;
4. 在不带表头结点的链栈中,若栈顶指针top直接指向栈顶元素,则将一个新结点p入栈时修改链的两个对应语句为 p.setNext(top) ; top=p; 。
5. 在不带表头结点的链栈中,若栈顶指针top直接指向栈顶元素,则栈顶元素出栈时的修改链的对应语句为 top=top.getNext(); 。
6. 队列也是一种操作受限的线性表,它与栈不同的是,队列中所有的插入操作均限制在表的一端进行,而所有的删除操作都限制在表的另一端进行,允许插入的一端称为 队尾 ,允许删除的一端称为 队首 。队列具有 先进先出 的特点。
7. 由于队列的删除和插入操作分别在队首和队尾进行,因此,在链式存储结构描述中分别需要设置两个指针分别指向 队首结点 和 队尾结点 ,这两个指针又分别称为 队首指针 和 队尾指针 。
8. 循环顺序队列是将顺序队列的存储区域看成是一个首尾相连的环,首尾相连的状态是通过数学上的 求模(或
取余) 运算来实现的。
9. 在循环顺序队列中,若规定当front==rear时,循环队列为空;当front==(rear+1)%maxSize时,循环队列
为满,则入队操作时的队尾指针变化的相应语句是 rear=(rear+1)% maxSize ;出队操作时的队首指针变化的相应语句是 front=(front+1)%maxSize 。 10. 无论是顺序栈还是顺序队列,插入元素时必须先进行 栈或队列是否为满的 判断,删除元素时必须先进行 栈
或队列是否为空的 判断;而链栈或链队列中,插入元素无需进行栈或队列是否为满的判断,只要在删除元素时先进行 栈或队列是否为空的 判断。 三、算法设计题
1. 编写一个函数,要求借助一个栈把一个数组中的数据元素逆置。
参考答案:
//借助一个顺序栈将已知一个数组中的数据元素逆置
public reverse(Object [] a) throws Exception {
SqStack S=new SqStack(a.length); //构造一个容量为a.length的顺序栈 for(int i=0;i
for( int i=0;i
2. 编写一个函数判断一个字符序列是否为回文序列,所谓回文序列就是正读与反读都相同的字符序列,例如:
abba和abdba均是回文序列。要求只使用栈来实现。 参考答案:
//判断字符序列是否为回文序列,若是则返回true值,否则返回false。 public boolean isPalindSeq(String str) { LinkStack S = new LinkStack(); int i = 0; for (; i < str.length(); i++) S.push(str.charAt(i)); for (i = 0; i < str.length(); i++) { char c = ((Character) S.pop()).charValue(); if (c != str.charAt(i)) return false; } return true;
}
3. 假设以一个数组实现两个栈:一个栈以数组的第一个存储单元作为栈底,另一个栈以数组的最后一个存储单
元作为栈底,这种栈称为顺序双向栈。试编写一个顺序双向栈类DuSqStack,类中要求编写3个方法。一个是构造方法DuDuSqStack(int maxSize),此方法实现构造一个容量为maxSize的顺序双向空栈;一个是实现入栈操作的方法push(Object X,int i),此方法完成将数据元素X压入到第i(i=0或1)号栈中的操作;一个是实现出栈操作的方法pop(int i),此方法完成将第i号栈的栈顶元素出栈的操作。 参考答案:
class DuSqStack{ private Object[] stackElem; // 栈存储空间 private int top0; //栈顶指针,指示第0号的栈顶元素的下一个位置 private int top1; //栈顶指针,指示第1号的栈顶元素的下一个位置 private int base0;//栈尾指针,指示第0号的栈底元素 private int base1;//栈尾指针,指示第1号的栈底元素
//构造方法
public DuSqStack(int maxSize) { // 初始化栈,即构造一个双向空栈
stackElem = new Object[maxSize];// 为栈分配maxSize个存储单元 top0=base0=0;
top1=base1=maxSize-1; }
//入栈操作方法
public void push(Object X, int i) throws Exception { // 将数据元素X压入到第i(i的值为0或1)号栈中 if (top0 > top1) //栈满
throw new Exception(\栈已满\抛出异常 else if (i==0)
stackElem[top0++]=X; else if (i==1)
stackElem[top1--]=X; }
//出栈操作方法
public Object pop(int i) throws Exception {
// 将S中第i号栈的栈顶元素出栈,并返回栈顶元素值 Object x=null; if(i==0)
if (top0==base0)
throw new Exception(\第0号栈为空\ else
x=stackElem[--top0]; else if (i==1)
if (top1==base1)
throw new Exception(\第0号栈为空\ else
x=stackElem[++top1];
return x; }
} // DuSqStack类结束
4. 循环顺序队列类采用设置一个计数器的方法来区分循环队列的判空和判满。试分别编写顺序循环队列中入队
和出队操作的函数。 参考答案:
//循环顺序队列存储结构类描述如下: class CircleSqQueue_num {
private Object[] queueElem; // 队列存储空间
private int front;// 队首的引用,若队列不空,指向队首元素,初值为0
private int rear;// 队尾的引用,若队列不空,指向队尾元素的下一个位置,初值为0 private int num; // 计数器用来记录队列中的数据元素个数
……
} // CircleSqQueue_num类结束
为类CircleSqQueue_num所编写的入队和出队操作方法如下: // 入队操作方法
public void offer(Object x) throws Exception {//把指定的元素x插入队列
if (num==queueElem.length)// 队列满
throw new Exception(\队列已满\输出异常 else {// 队列未满
queueElem[rear] = x;// x加入队尾
rear=(rear + 1) % queueElem.length; //更改队尾的位置 ++num; //计数器加1 } }
// 出队操作方法
public Object poll() {
//移除队首元素并作为此函数的值返回该对象,如果此队列为空,则返回 null if (num==0)// 队列为空 return null; else {
Object t = queueElem[front];// 取出队首元素
front = (front + 1) % queueElem.length;// 更改队首的位置 --num; //计数器减1 return t;// 返回队首元素 } }
5. 假设采用带头结点的循环链表来表示队列,并且只设一个指向队尾元素的指针(不设队首指针),试编写相
应的队列置空、队列判空、入队和出队操作的函数。 参考答案:
用队尾指针标识的循环链队列的类描述如下: class CircleLinkQueue {
private Node rear;// 循环链队列的尾指针
…… }
为此类编写的队列置空、队列判空、入队和出队操作的方法分别如下:
// 队列置空操作方法 public void clear() {
//将一个已经存在的带头结点的循环链队列置成空队列 rear.setNext(rear); } // 入队操作方法 public void offer ( Object x) throws Exception { //将指定的元素x插入到带头结点的循环链队列中
Node p= new Node(x); // 生成新结点
p.setNext(rear.getNext());// 插入链列列的尾部 rear.setNext(p); rear=p; } // 出队操作方法 public void poll() throws Exception {
// 移除带头结点的循环链队列中的队首元素并作为此函数的值返回该对象,如果此队列为空,则返回 null
Node p = rear.getNext().getNext();// p指向待删除的队首结点 if (p==rear)
rear.setNext(rear); //删除队首结点后,链队列变成了空链队列 else
rear.getNext().setNext(p.getNext());// 删除队首结点 }
正在阅读:
栈与队列习题参考答案03-25
政务服务数据管理局2022年工作总结和工作计划优秀参考04-26
2016监理试题及答案311-24
女子一路不带钱搭便车 13个月穷游22国04-30
四年级上册数学-检测题一二单元测试卷01-07
大学物理练习下册(1)01-07
第2讲局域网组网技术06-10
深空网页防篡改系统 管理员指南05-03
- 小学生造句大全
- 增压泵投资项目可行性研究报告(模板)
- 高中语文人教版粤教版必修1-5全部文言文知识点归纳
- 两学一做专题民主生活会组织生活会批评与自我批评环节个人发言提
- 管理处环境保洁工作操作标准作业指导书
- 2012六一儿童节活动议程 - 图文
- 移树申请报告
- 《贵州省市政工程计价定额》2016定额说明及计算规则
- 计算机长期没有向WSUS报告状态
- 汉语拼音教学策略研究
- 发展西部领先的航空货运枢纽
- 司法所上半年工作总结4篇
- 如何提高银行服务水平
- 发电厂各级人员岗位职责
- 丰田汽车的外部环境分析
- 2017—2018年最新冀教版四年级数学下册《混合运算》教案精品优质
- 中建八局样板策划 - 图文
- 戚安邦《项目管理学》电子书
- 2015年高级项目经理笔记
- 弯桥的设计要点
- 队列
- 习题
- 答案
- 参考
- 李少波真气运行法
- 口腔溃疡吃什么蔬菜
- 三年级英语期中学情调研试卷
- CA-谈谈载波聚合 - 图文
- 南阳市中小学优秀教育教学论文和学生习作辅导奖名单
- 二1《观赏植物学》教学大纲汇总
- 市政道路工程施工合同书doc2
- 10月计算机专业毕业生实习总结
- 2019年上学期高二语文教学计划
- 《金色的草地》导学案设计
- 上海市特殊教育考察报告
- 台州中学2012学年第一学期第二次统练考试(含答案)
- 人力资源统计学题库
- 2016-2017年最新青岛版(六三制)小学数学一年级下册厘米、米的
- Microsoft Office Word 重启问题修复
- 2012年度个人教学工作总结
- C++程序设计实验指2013导
- 临床路径管理小组职责
- 浅谈有机合成新技术(DOC)
- 奎香乡中心学校教育十二五规划