北理工珠海学院《数据结构》习题集:第3章 栈和队列(第1次更新2012-3)
更新时间:2023-11-28 03:48:01 阅读量:2 教育文库 文档下载
- 北理工珠海学院录取分数线推荐度:
- 相关推荐
数据结构课后练习题 第3章 栈和队列
第3章 栈和队列
一、 选择题
1. 栈结构通常采用的两种存储结构是( )。【*】
A、顺序存储结构和链表存储结构 B、散列和索引方式
C、链表存储结构和数组 D、线性链表结构和非线性存储结构 2. 设栈ST 用顺序存储结构表示,则栈ST 为空的条件是( )【*,★】
A、ST.top-ST.base<>0 B、ST.top-ST.base==0 C、ST.top-ST.base<>n D、ST.top-ST.base==n
3. 向一个栈顶指针为HS 的链栈中插入一个s 结点时,则执行( )(龚注:栈无头结点)【*,★】
A、HS->next=s; B、s->next=HS->next;HS->next=s; C、s->next=HS;HS=s; D、s->next=HS;HS=HS->next;
4. 从一个栈顶指针为HS 的链栈中删除一个结点,用x 保存被删除结点的值,则执行( )(龚注:栈无头结点)
【*,★】
A 、x=HS;HS=HS->next; B 、HS=HS->next;x=HS->data; C 、x=HS->data;HS=HS->next; D 、s->next=Hs;Hs=HS->next; 5. 表达式a*(b+c)-d 的后缀表达式为( )【**,★】
A、abcdd+- B、abc+*d- C、abc*+d- D、-+*abcd 6. 中缀表达式A-(B+C/D)*E 的后缀形式是( )【**】
A、AB-C+D/E* B、ABC+D/E* C、ABCD/E*+- D、ABCD/+E*- 7. 一个队列的入列序列是1,2,3,4, 则队列的输出序列是( )【*,★】
A、4,3,2,1 B、1,2,3,4 C、1,4,3,2 D、3,2,4,1
8. 循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值,已知其头尾指针分别是front 和rear,则判定此循环队
列为空的条件是( )【*,★】 A、Q.rear-Q.front==n B、Q.rear-Q.front-1==n C、Q.front==Q.rear D、Q.front==Q.rear+1
9. 循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值,已知其头尾指针分别是front 和rear,则判定此循环队
列为满的条件是( )【**,★】 A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n
10. 若在一个大小为6 的数组上实现循环队列,且当前rear 和front 的值分别为0 和3,当从队列中删除一个元素,
再加入两个元素后,rear 和front 的值分别为( )【**】 A、1,5 B、2, 4 C、4,2 D、5,1 11. 用单链表表示的链式队列的队头在链表的( )位置【*】
A、链头 B、链尾 C、链中
12. 判定一个链队列Q(最多元素为n 个)为空的条件是( )【*】
A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 13. 在链队列Q 中,插入s 所指结点需顺序执行的指令是( )【*】
A 、Q.front->next=s;f=s; B 、Q.rear->next=s;Q.rear=s; C 、s->next=Q.rear;Q.rear=s; D 、s->next=Q.front;Q.front=s;
1/7
北京理工大学珠海学院计算机学院 “数据结构”课程组编制 2011-3-1
数据结构课后练习题 第3章 栈和队列
14. 在一个链队列Q 中,删除一个结点需要执行的指令是( )【*】
A、Q.rear=Q.front->next; B、Q.rear->next=Q.rear->next->next; C、Q.front->next=Q.front->next->next; D、Q.front=Q.rear->next; 15. 用不带头结点的单链表存储队列,其队头指针指向队头结点,队尾指针指向队尾结点,则在进行出队操作时( )
A、仅修改队头指针 B、仅修改队尾指针【**,★】 C、队头尾指针都要修改 D、队头尾指针都可能要修改。 16. 栈和队列的共同点是( )【*】
A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点 17. 消除递归( )需要使用栈。【**,★】
A、一定 B、不一定
18. 设有一顺序栈S,元素s1,s2,s3,s4,s5,s6 依次进栈,如果6 个元素出栈的顺序是s2,s3,s4,s6,s5,s1,
则栈的容量至少应该是( )【**,★】 A、2 B、3 C、 5 D、 6
19. 若一个栈的输入序列是a,b,c,则通过入、出栈操作可能得到a,b,c 的不同排列个数为( )【**,★】
A、 4 B、 5 C、 6 D、 7
20. 设有一顺序栈已经含有3 个元素,如图3.1 所示元素a4 正等待进栈。下列不可能出现的出栈序列是( )【*
*,★】
A、a3,a1,a4,a2 B、 a3,a2,a4,a1 C、 a3,a4,a2,a1 D、 a4,a3,a2,a1
图3.1
21. 链栈和顺序栈相比,有一个比较明显的优势是( )【*】
A、通常不会出现栈满的情况 B、通常不会出现栈空的情况 C、插入操作更容易实现 D、删除操作更加容易实现
22. 若一个栈的输入序列是1,2,3,4,?,n,输出序列的第一个元素是n,则第i 个输出元素是( )【**,
★】
A、不确定 B、 n-i C、 n-i+1 D、n-i-1 23. 以下说法正确的是( ) 【**】
A、因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 B、因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 C、对于链栈而言,在栈满状态下,如果此时再作进栈运算,则会发生“上溢” D、对于顺序栈而言在栈满状态下如果此时再作进栈运算,则会发生“下溢”。 (续:第1次2012-3)
24. 某队列允许在两端进行入队操作,但仅允许在一端进行出队操作,若a、b、c、d、e元素进队,则不可能得到
的顺序是( )。【***,★,考研2010】
A. bacde B. dbace C. dbcae D. ecbad
25. 已知输入序列为abcd,经过输出受限的双端队列后能得到的输出序列是( )。【***,联考】
A. dacb B. cadb C. dbca D. 以上序列都不能得到 26. 栈和队列具有相同的( )。【**,★,联考】
2/7
北京理工大学珠海学院计算机学院 “数据结构”课程组编制 2011-3-1
数据结构课后练习题 第3章 栈和队列
A. 抽象数据类型 C. 存储结构 B. 逻辑结构 D. 运算
二、 判断题
1. 在顺序栈栈满情况下,不能做进栈运算,否则会产生“上溢”。 【*】 2. 链栈与顺序栈相比的一个优点是链栈插入和删除操作更加方便。【*】
3. 若一个栈的输入序列为 1,2,3,?,n,其输出序列的第一个元素为n,则其输出序列的每个元素一定满足
ai=i+1(i=1,2, ?,n)。【**】
4. 在链队列中,即使不设置尾指针也能进行入队操作。【*】
5. 在对链队列(带头结点)做出队操作时,不会改变 front 指针的值。【*】 6. 循环队列中元素个数为 rear-front。【**,★】
7. 一个栈的输入序列是 1,2,3,4,则在栈的输出序列中可以得到4,3,1,2。【*】 8. 一个栈的输入序列是 1,2,3,4,则在栈的输出序列中可以得到1,2,3,4。【*】 9. 若以链表作为栈的存储结构,则进栈需要判断栈是否满。【*】 10. 若以链表作为栈的存储结构,则出栈需要判断栈是否空。【*】
三、 填空题
1. 1、2、3、4顺序入栈,则出入栈的序列共有( )种。【***,★】 2. 栈的特点是( ),队列的特点是( )。【*】
3. 线性表、栈、队列都是( )结构,可以在线性表的( )位置插入和删除元素;对于栈只能在(入和删除元素;对于队列只能在( )插入元素和在( )位置删除元素。【*,★】
4. 有程序如下,则此程序的输出结果(栈的元素类型是SelemType 为char)是( )。【*,★】
void main(){
stack s; char x,y;
initstack (s); x=’c’; y=’k’;
push(s,x); push(s,’a’); push(s,y); pop(s,x); push(s,’t’); push(s,x); pop(s,x); push(s,’s’);
while(!stackempty(s)){
pop(s,y);
printf(y);//(龚注:printf(“%c”,y); }
printf(x);//(龚注:printf(“%c”,x);
北京理工大学珠海学院计算机学院 “数据结构”课程组编制 2011-3-1
3/7
)插
数据结构课后练习题 第3章 栈和队列
} 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.
在栈顶指针为HS 的链栈中,判定栈空的条件是( )。(龚注:文字描述)【*】
向栈中压入元素的操作是先( )后( )。(龚注:应是顺序存储结构栈)【*,★】 对栈进行退栈操作是先( )后( )。(龚注:应是顺序存储结构栈)【*,★】
用循环链表表示的队列长度为n,若只设头指针,则出队和入队的时间复杂度分别是( )和( );若只设尾指针,则出队和入队的时间复杂度分别是( )和( )。【*,★】
从循环队列中删除一个元素时,其操作是( )。(龚注:文字描述)【**,★】 在一个循环队列中,队首指针指向队首元素的( )。【*,★,?】 在具有n 个单元的循环队列中,队满时共有( )个元素。【*,★】
在HQ 的链队列中,判断只有一个结点的条件是( )。(龚注:C语言描述)【*】
设栈S 和队列Q 的初始状态为空,元素a、b、c、d、e、f 依次通过栈S,一个元素出栈后即进入队列Q。若这6个元素出队列的顺序是b、d、c、f、e、a 则栈S 的容量至少应该是( )。【**】
有程序如下,则此程序的输出结果(队列的元素类型是QSelemType 为char)是( )。【*,★】
void main(){
char x=’e’,y=’c’;
enqueue(q,’h’);enqueue(q,’r’);enqueue(q,y);dequeue(q,x);enqueue(q,x);degueue(q,x);
enqueue(q,’a’);
while(!queueempty(q)){
dequeue(q,y);printf(y);//龚注:printf(“%c”,y); }
printf(x);//龚注:printf(“%c”,x);
}
15. 有如下递归函数:【**】
int dunno(int m){
int value; if(m==0)
value=3; else
value=dunno(m-1)+5; return(value); }
执行语句printf(“%d\\n”,dunno(3));的结果是( )。
四、 简答题
1. 对于堆栈,给出三个输入项A,B,C,如果输入项序列为ABC,试给出全部可能的输出序列,并写
出每种序列对应的操作。例如:A 进B 进C 进C 出B 出A 出,产生的序列为CBA。【**】 2. 简述以下算法的功能(栈的元素类型是 SelemType 为int)。【**,★】
(1)
status algo1(stack s){
int I,n,a[255]; n=0;
while(!stackempty(s)){
n++;
4/7
北京理工大学珠海学院计算机学院 “数据结构”课程组编制 2011-3-1
数据结构课后练习题 第3章 栈和队列
pop(s,a[n]); }
for(I=1;I<=n;I++)
push(s,a[I]); } (2)
status algo2(stack s,int e){
stack t;int d; initstack(t);
while(!stackempty(s)){
pop(s,d); if(d!=e)
push(t,d);
}
while(!stackempty(t)){
pop(t,d); push(s,d); } }
3. 内存中一片连续空间(不妨假设地址从0 到m-1)提供给两个栈s1 和s2 使用,怎样分配这部分存储空间,
使得对任一栈仅当这部分空间全满时才发生溢出。【**】 4. 有递归过程如下:【**】
void print(int w){
int I; if(w!=0){
print(w-1);
for(I=1;I<=w;I++)
printf(“=”,w); printf(“\\n”);
} } 问:调用语句print(4)的结果是什么?
5. 简述以下算法的功能(栈和队列的元素类型均为 int)【*,★】
void algo(queue &q){
stack s; int d;
initstack(s);
while(!queueempty(q)){
dequeue(q,d); push(s,d); }
while(!stackempty(s)){
pop(s,d);
enqueue(q,d);
5/7
北京理工大学珠海学院计算机学院 “数据结构”课程组编制 2011-3-1
![](https://wxpay.100changshi.com/Public/Pay/v1/wxpay/native/img/download/icon_word.2.png)
![](https://wxpay.100changshi.com/Public/Pay/v1/wxpay/native/img/download/icon_star.png)
![](https://wxpay.100changshi.com/Public/Pay/v1/wxpay/native/img/download/icon_star.png)
![](https://wxpay.100changshi.com/Public/Pay/v1/wxpay/native/img/download/icon_star.png)
![](https://wxpay.100changshi.com/Public/Pay/v1/wxpay/native/img/download/icon_star.png)
![](https://wxpay.100changshi.com/Public/Pay/v1/wxpay/native/img/download/icon_star.png)
正在阅读:
北理工珠海学院《数据结构》习题集:第3章 栈和队列(第1次更新2012-3)11-28
2022云南农信社考试公基备考:彩礼能否要回.doc04-20
电力行业工人先锋号申报材料02-11
律师所章程(草稿)05-16
第二架1700冷轧机设计10-22
清华斯维尔三维算量工程实例教程04-10
浅论历史学科任务驱动式作业与练习的设计04-12
《状元360》2013届高考历史一轮总复习 第二十三单元 综合测试卷01-04
电子排版技术CAI-CHAP0405-15
小型工资管理系统 java 报告书05-02
- exercise2
- 铅锌矿详查地质设计 - 图文
- 厨余垃圾、餐厨垃圾堆肥系统设计方案
- 陈明珠开题报告
- 化工原理精选例题
- 政府形象宣传册营销案例
- 小学一至三年级语文阅读专项练习题
- 2014.民诉 期末考试 复习题
- 巅峰智业 - 做好顶层设计对建设城市的重要意义
- (三起)冀教版三年级英语上册Unit4 Lesson24练习题及答案
- 2017年实心轮胎现状及发展趋势分析(目录)
- 基于GIS的农用地定级技术研究定稿
- 2017-2022年中国医疗保健市场调查与市场前景预测报告(目录) - 图文
- 作业
- OFDM技术仿真(MATLAB代码) - 图文
- Android工程师笔试题及答案
- 生命密码联合密码
- 空间地上权若干法律问题探究
- 江苏学业水平测试《机械基础》模拟试题
- 选课走班实施方案
- 珠海
- 数据结构
- 习题集
- 队列
- 理工
- 更新
- 学院
- 2012
- 古代汉语专题基础汉字学教程试题解答举例及考核知识点
- 2017-2018学年江苏省徐州市七年级(上)期末语文试卷
- 高三第一轮英语单项选择题扎实冲刺004
- 民用爆炸物品库装卸、运输、储存安全试题(带答案)
- 2018小升初语文专项复习口语交际与综合性学习精编习题
- 2、职业卫生管理档案
- 税务系统“业务竞赛” 试题
- H-E染色
- 人事行政工作内容
- 固体废物处理与处置工程
- 单片机编程习题
- 中国石油大学远程教育《机械制图》在线考试(主观题)奇数题答案
- 《大学物理习题集》(上)习题解答 - 20030106 - 图文
- 农村社会调查研究方法
- 2010年北京中考一模语文分类汇编 - 议论文
- 仪器分析复习题(1)
- 2005年下半年网络工程师试题
- 保通方案
- 浙江省中学生研究性学习活动成果评比获奖名单
- 烟台市2019年高考一模诊断性测试理科数学