2022年第二单元课后练习题 .pdf

《2022年第二单元课后练习题 .pdf》由会员分享，可在线阅读，更多相关《2022年第二单元课后练习题 .pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二单元课后练习题（知识点范围：第3 章栈和队列）班级：学号：姓名：成绩：一、选择题（每小题1 分，共 20 分）1. 若 top 为栈顶指针，则判定一个顺序栈ST（最多元素为MAX ）为空的条件是B 。A. top !=0 B. top= =0 C. top !=MAX D. top= =MAX-1 2. 若 top 为栈顶指针， 则判定一个顺序栈ST （最多元素为MAX ） 为栈满的条件是D。A. top！=0 B. top= =0 C. top！=MAX D. top= =MAX-1 3一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是C。Aedcba Bdecba Cdce

2、ab Dabcde 4设有一个栈，元素依次进栈的顺序为A、B、C、D、E。下列B是可能的出栈序列。AD,B,C,A,E BB,C,D,E,A CE,A,B,C,D DE,D,C,A,B 5以下B 不是队列的基本运算？A从队尾插入一个新元素B从队列中删除第i 个元素C判断一个队列是否为空D读取队头元素的值6若已知一个栈的进栈序列是1，2，3， n，其输出序列为p1，p2，p3， pn，若p1 n，则 pi 为A 。Ai Bni Cni1 D不确定7设计一个判别表达式中左、右括号是否配对出现的算法，采用D数据结构最佳。A线性表的顺序存储结构B队列C线性表的链式存储结构D栈8. 从一个栈顶指针为HS

3、 的链栈中删除一个结点时，用 x 保存被删结点的值， 则执行D 。(不带空的头结点) A. x=HS; HS= HS-next; B. x=HS-data; C. HS= HS-next; x=HS-data; D. x=HS-data; HS= HS-next; 9一个队列的入队序列是1，2，3，4，则队列的输出序列是B 。A4，3，2，1 B1，2，3，4 C1，4， 3，2 D3，2，4，1 10判定一个循环队列qu（最多元素为MaxSize）为空的条件是C。Aqu-rear qu-front =MaxSize Bqu-rear qu-front -1=MaxSize Cqu-rear

4、=qu-front D qu-rear =qu-front -1 11若用一个循环队列空间大小为6，且当前 rear 和 front 的值分别为0 和 3，当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别为B。A1 和 5B2 和 4 C4 和 2 D5 和 1 12向一个栈顶指针为h 的带头结点的链栈中插入指针s 所指的结点时， 应执行D操作。Ah-next=s ; Bs-next=h ; Cs-next=h ;h =s ; Ds-next=h-next ;h-next=s ; 13输入序列为ABC ，若用 S表示入栈， X 表示出栈操作，则得到CBA 输出序列要

5、经过的栈操作序列为B 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - A SXSXSX B SSSXXXC SSXSX D SXSSXX 14和顺序栈相比，链栈有一个比较明显的优势是A 。A通常不会出现栈满的情况B 通常不会出现栈空的情况C插入操作更容易实现D删除操作更容易实现15若一个顺序栈中元素为n 个, 做进栈运算时发生上溢, 则说明该栈的最大容量为B 。A. n-1 B. n C. n+1 D. n/2 16若一个带头

6、结点的链栈的栈顶指针用top 表示，当 p 指向的结点进栈时，执行的操作是C。Ap-next=top ;top=top-next; Btop=p-p; p-next=top; Cp-next=top-next; top-next=p; Dp-next=top; top=p; 17若一个循环队列，其最多元素个数为MAXSIZE ，front 为头指针， rear 为尾指针，则判定满队列的条件是A 。A(rear+1)%MAXSIZE=front B rear+1=front Crear=front D(front+1)%MAXSIZE=rear 18设输入序列为1、2、3、4、5、6，则通过栈的

7、作用后可以得到的输出序列为B。A5，3，4，6，1，2 B3，2，5，6，4，1 C 3 ，1，2，5，4，6 D1，5，4，6，2，3 19在链队列 Q 中，front指向链队列的头结点，rear 指和队尾元素，若让s 所指结点入队需执行的指令是B A Q.front-next=s ；f=s; BQ.rear-next=s ；Q.rear=s; C s-next=Q.rear；Q.rear=s; Ds-next=Q.front ；Q.front=s;20设栈 ST 用顺序存储结构表示，若top 、base分别为指向栈顶和栈底的指针，则栈ST 为空的条件是BA、ST.top-ST.base0

8、B、ST.top-ST.base=0 C、ST.top-ST.basen D、ST.top-ST.base=n 二、填空题（每空1 分，共 25 分）1. 向栈中压入元素的操作是_入栈 _。2. 对栈进行退栈时的操作是_出栈_。3. 在一个循环队列中，队首指针指向队首元素的_ 前一个位置_。4. 从循环队列中删除一个元素时，其操作是_出队_。5. 在具有 n 个单元的循环队列中，队满时共有_ n-1_个元素。6. 一个栈的输入序列是12345，则栈的输出序列43512 是_ 不可能的 _。7. 一个栈的输入序列是12345，则栈的输出序列12345 是_ 可能的 _。8下面程序段的功能实现数据

9、x 进栈，要求在下划线处填上正确的语句。#define MAXSIZE 100 typedef struct int sMAXSIZE; int top; sqstack; void push(sqstack *stack , int x) if (stack-top=MAXSIZE) printf(“overflow”);else stack-sstack-top=x ; stack-top+; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - - - -

10、 - - - - 9设输入序列为1、2、3，则经过栈的作用后可以得到5种不同的输出序列。10不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为O(1) 。11 栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为_ FILO_ 表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为_FIFO_表。12设 F 和 R分别表示顺序循环队列的头指针和尾指针，或F 指向队头元素的前一个位置，R指向队尾元素则判断该循环队列为空的条件为F=R 。13. 栈是限定在表的一端进行插入或删除操作的线性表，其运算遵循FILO的原则。

11、14.若 addQ(n)表示元素 n 入队列 Q 的入队运算， delQ( )表示队列Q 的出队运算，当前队列状态为空，则经过addQ(1)，addQ(2)， delQ( ) ，addQ(5)，addQ(7)， delQ( )，addQ(9)操作后，队头元素为5 ，队尾元素为9 ；若使队列中剩余元素全部出队，还需要经过3次delQ() 操作。15.栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。16. 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。18. 对于顺序存储结构的栈，在做入栈运算时应先判断栈是否栈满；在做出栈运

12、算时应先判断栈是否为空。三、判断题 (每题 1 分，共 10 分) 1队列是一种插入和删除操作分别在表的两端进行的线性表，是一种先进后出的结构。（ ）2不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（）3在顺序栈栈满情况下，不能做进栈运算，否则会产生“上溢”。( ) 4. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（）5. 循环队列中若front指向队头元素的前一个位置，rear 指向队尾元素则元素个数为rear-front 。 （）错，元素个数为(rear-front+MAX)%MAX6. 栈和链表是两种不同的数据结构。( ) 错，

13、栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 8 页 - - - - - - - - - 7. 栈和队列是一种非线性数据结构。( ) 错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。8. 栈和队列的存储方式既可是顺序方式，也可是链接方式。（）9. 若以链表作为栈的存储结构，则进栈需要判断栈是否满。( ) 10. 一个栈的输入序列是12345，则栈的输出序列不可能是1

14、2345。 ( ) 四、计算题 ( 每小题 5 分，共 10 分) 1、画出下列循环队列出队三个元素后的图示，并说明此时队列处于个什么状态。图 2.2 循环队列状态图示答：三个元素出队后图示为：出队顺序为： W Y G 此时队列为空队列2、铁道进行车厢调度，如下图 2.2 所示 a,b 二条铁道均为单向行驶，设有 16 编号的 6 节车厢，若进站的车厢序列为123456，则求解如下问题。(1) 能否得到634512 和 564321 的出站序列？(2)写出三种不可能的出站序列。(3)写出 2 种可能的出站序列及用S表示进栈、 X 表示出栈的栈操作序列。图 2.2q.front 3 4 5 0

15、1 2 Y q.rear W G q.front 3 4 5 0 1 2 Y q.rear W G 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - - - - - - - - - 答：(1) 可以得到135426 出站序列，栈操作序列如下：入栈车厢号：1 23 45 6 栈操作： SXSSXSSXXXSX 出栈车厢号：1 3 5 4 2 6 不能得到435612 出站序列因为若 4356 出栈，说明12 已在栈中，则1 不可能在 2 之前出栈，(2)三种不可能

16、的出站序列为：653412 、 312645、423615 (3)二种可能的出站序列及栈操作序列如下：654321 SSSSSSXXXXXX 321456 SSSXXXSXSXSX 五、算法设计题( 第 1 题 17 分，第 2 题 18 分，共 35 分) 1应用顺序栈或链栈操作（栈初始化，入栈，出栈）实现进制转换。编程实现输入十进制数转换为八进制输出。例如，输入十进制数56，输出八进制数70 /*应用顺序栈实现十进制DEX 转换为八进制 */ #include #define MAXSIZE 50 #define N 8 /*N 为转换的进制*/ typedef struct stack

17、/*顺序栈类型定义*/ int dMAXSIZE; int top; Seqstack; Seqstack *init() /*顺序栈初始化*/ Seqstack *s; s=(Seqstack *)malloc(sizeof(Seqstack); s-top=0; return s; void push(Seqstack *s,int x) /*入栈操作 */ /*在此编写实现入栈操作的代码*/ (5 分)if(s-topds-top=x; s-top+; int pop(Seqstack *s) /*出栈操作 */ int x; 名师资料总结 - - -精品资料欢迎下载 - - - - -

18、 - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 8 页 - - - - - - - - - /* 在此编写实现出栈操作的代码*/ (5 分 )if(s-top0) s-top-; x=s-ds-top; return x; int main(int argc, char *argv) Seqstack *s ; int dex,x; s=init(); printf(input DEX:); scanf(%d,&dex); /*输入十进制整数*/ /*在此编写调用入栈或出栈函数实现十进制转换为八进制的代码*/ (7 分)x=dex

19、; while(x0) push(s,x%N); /*N 为转换的进制*/ x=x/N; printf(%d-,dex); while(s-top0) printf(%d,pop(s); 2回文是指正读反读均相同的字符序列，如“abba”和“ abdba”均是回文，但“good”不是回文。试应用顺序栈或链栈操作（建立链栈，入栈，出栈）写一个算法判定给定的字符向量是否为回文。/*链栈实现回文判断*/ #include typedef struct node /*链栈结点类型定义*/ char data; /*数据域为字符型*/ struct node *next; Node ,*Linkstac

20、k; /*链栈初始化 */ Linkstack init() Linkstack top; top=(Linkstack)malloc(sizeof(Node); top-next=NULL; return top; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 8 页 - - - - - - - - - /* 入栈操作 */ void push(Linkstack top,char x) Linkstack p; /*在此编写实现入栈操作的代码*/ (5 分)p=(L

21、inkstack)malloc(sizeof(Node); p-data=x; p-next=top-next; top-next=p; /*出栈操作 */ char pop(Linkstack top) char x; Linkstack p; /*在此编写实现出栈操作的代码*/ (5 分)p=top-next; if(p!=NULL) x=p-data; top-next=p-next; free(p); return x; int main( ) Linkstack top ; char s120,s220; int i=0; top=init(); printf(input a str

22、ing:); gets(s1); /* 输入待判断字符串s1*/ /* 在此编写通过调用入栈或出栈函数实现判断s1 中字符串是否为回文的代码*/ (8 分)while(s1i!=0) /* 字符串 s1 中字符入栈 */ push(top,s1i); i+; i=0; while(top-next!=NULL) /*字符串 s1 中字符出栈 */ s2i=pop(top); i+; s2i=0; if(strcmp(s1,s2)=0)printf(%s是回文 ,s1); else printf(%s 不是回文 ,s1); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -