《天津商业大学 计算机科学与技术专业 高职升本 课件2》由会员分享，可在线阅读，更多相关《天津商业大学 计算机科学与技术专业 高职升本 课件2（30页珍藏版）》请在金锄头文库上搜索。
1、综合练习二,一.单选题,1. 字符A、B、C依次进入一个栈，按出栈的先后顺序组成不 同的字符串，至多可以组成_个不同的字符串。 A) 5 B) 4 C) 6 D) 1,ABC,BAC,BCA,CBA,ACB,CAB,一.单选题,2. 栈和队列都是 。 A) 顺序存储的线性结构 B) 链式存储的非线性结构 C) 限制存取点的线性结构 D) 限制存取点的非线性结构,一.单选题,3. 设有x，y，z三个元素顺序进栈，在进栈过程可 以出栈，不可能出现的出栈序列为 。 A) xyz B) yzx C) zxy D) zyx,一.单选题,4. 设一环形队列用一维数组Am表示，队头和队尾的指针 分别为fro
2、nt和tail，则入队时判定队列满的条件是_。 A) front=tail B) front=tail+1 C) front=(tail+1) % m D) front=tail % m,一.单选题,5. 单链表L中，P所指结点为尾结点的条件为 _ 。 A) PL B) P-next=NULL C) P.next:L D) Pnil,一.单选题,6.借助栈输入A、B、C三个元素，则不可能的输出序列 是 _。 A) ABC B) CAB C) CBA D) BAC,一.单选题,7. 设top为栈顶指针，判定一个栈S(最多元素为m)为栈满的 条件是_。A）S-top!=0 B）S-top=0 C）
3、S-top!=m-1 D）S-top=m-1,一.单选题,8. 在一个栈顶指针为HS的链栈中删除一个结点时，用x保存 被删除的结点，则执行的操作是_。P47图3.3A）x= HS, HS = HS -next ; B）x= HS -data ; C）x= HS -data , HS = HS -next ;D）HS = HS -next , x= HS -data ;,一.单选题,9.设用一维数组An存储一个栈，令A0为栈底，用整型变 量T指示当前栈顶位置，AT为栈顶元素。当压入栈中一个 元素时，变量T的变化为_。 A) T=T+1 B) T=T-1 C) T不变 D) T=n,一.单选题,1
4、0.设用一维数组An存储一个栈，令An-1为栈底，用整型 变量T指示当前栈顶位置，AT为栈顶元素。当压入栈中一 个元素时，变量T的变化为_。 A) T=T+1 B) T=T-1 C) T不变 D) T=n,一.单选题,11.和顺序栈相比，链栈有一个明显的优势是_。 A）通常不会出现栈空的现象 B）通常不会出现栈满的现象 C）插入操作更容易实现 D）删除操作更容易实现,一.单选题,12.循环队列用数组Am存放其元素值,已知其头尾指针分别 是front和rear则当前队列中的元素个数是_。P64 A）(rear-front+m)%m B）rear-front+1 C）rear-front-1 D）
5、rear-front,一.单选题,13.在一个链队中，若front和rear分别为队头、队尾指针，则 所插入s所指结点操作为_。 A）front-next=s，front=s； B）rear-next=s，rear=s； C）s-next=rear，rear=s； D）s-next=front，front=s；,一.单选题,14.栈和队列的共同点是_。 A）都是先进后出 B）都是先进先出 C）只允许在端点处插入和删除元素 D）没有共同点,一.单选题,15.设数组0m作为循环链队列lq的存储空间，若front和 rear分别为队头、队尾指针，则入队时修改指针的语句是 _。 A）lq.front=
6、(lq.front+1)%m B）lq.front=(lq.front+1)%(m+1) C）lq.rear=(lq.rear+1)%m D）lq.rear=(lq.rear+1)%(m+1),二.多选题,1. 栈的基本运算包括_。A) 删除栈底元素 B) 将栈置为空栈 C) 判断栈是否为空 D) 删除栈顶元素BCD,二.多选题,2. 队列的基本运算包括_。A) 从队尾插入一个新元素 B) 判断一个队列是否为空C) 从队列中删除第i个元素 D) 读取队头元素的值ABD,二.多选题,3. 从逻辑上讲，下列属于线性结构的是_。 A) 队列 B) 栈 C) 线索二叉树 D) 线性表 ABD,二.多选
7、题,4. 下列术语为数据结构的是_。 A) 栈 B) 队列 C) 散列表 D) 串ABD,二.多选题,5.以下说法错误的是 。 A）因链栈本身没有容量限制，故在用户内存空间范围内 不会出现栈满情况 B）因顺序栈本身没有容量限制，故在用户内存空间范围 内不会出现栈满情况 C）对链栈而言，在栈满情况下，如果再入栈操作，则会 发生“上溢” D）对顺序栈而言，在栈满情况下，如果再入栈操作，则 会发生“下溢”BCD,三、判断题,1. 栈和队列既可采用顺序存储方式，也可采用链接存储方式。 2. 队列是允许在队头一端进行插入，在队尾一端进行删除操作 的线性表。 3. 链栈的每个结点都含有两个指针。 4.顺序
8、队列和循环队列的队空和队满判断条件是不一样的。 5.单链表形式的队列，头指针F指向队列的第一个结点，尾 指针R指向队列的最后一个结点。正确 1 4 5,四、填空题,1. 队列和栈都是线性表。在栈中， 称为栈顶，栈操作的 原则是 ；队列操作的原则是_。 2.假设以S和X分别表示进栈和出栈操作，若对输入序列a， b，c，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输 出序列为_。 3.设有一个顺序栈S，元素s1， s2， s3， s4， s5， s6依次进 栈，如果6个元素的出栈顺序为s2， s3， s4， s6， s5， s1， 则顺序栈的容量至少应为_。 答：1. 表尾(允许操作的一
9、端)、后进先出、先进先出 2. bceda3. 3,四、填空题,4. 设栈S的初始状态为空，队列Q的初始状态为a1 a2 a3 a4 队头 队尾 对栈S和队列Q进行如下两步操作： (1) Q中的元素依次出队，并压入栈S中，直至Q为空； (2) 依次弹出S中的元素并进入Q，直至S为空。 在上述两步操作后，队列Q的状态是 。答：a4a3a2a1,四、填空题,5. 具有n个单元的循环队列中，队满时共有 _个元素。 6.通常程序在调用另一个程序时，都需要使用一个_来保存 被调用程序内分配的局部变量、形式参数的存储空间以及返回 地址。 7. 定义一维数组，int Am+1；作为循环队列的存储空间， fr
10、ont为队头指针，rear为队尾指针，则元素x执行入队操作的语 句是_。 8.设top为栈顶指针，判定一个栈S(最多元素为m)为栈满的条件 是_ 。答： 5. n-1 6. 栈7. rear=(rear+1)%(m+1) , Arear=x8. S-top = m-1,四、填空题,9.假设以S和X分别表示进栈和出栈操作，若对输入序列 1,2,3,4,5进行一系列栈操作SSSXXSXSXX之后，得到的输出序 列为 。 答： 32451 10. 设有一个顺序栈S，元素a，b，c，d，e，f依次进栈，如果6 个元素的出栈顺序为b，c，d，f，e，a，则顺序栈的容量至少 应为。答： 3,五、简答题,1
11、如图所示，在栈的输入端有6个元素，输入顺序为A、B、 C、D、E、F。能否在栈的输出端得到序列ACEDFB及 EDFCAB？若能，写出对栈的操作过程（用push表示进栈， pop表示退栈）；若不能，简述其理由。 PUSH(S,A)A元素进栈 POP(S) 栈顶元素出栈,五、简答题,1参考答案： 可以产生ACEDFB， ACEDFB进栈过程： PUSH(S,A) ，POP(S)， PUSH(S,B) ，PUSH(S,C) ，POP(S)， PUSH(S,D)，PUSH(S,E)， POP(S)，POP(S)， PUSH(S,F) ，POP(S)，POP(S) 不能产生EDFCAB，原因：不能产生
12、EDFCAB原因：栈是一种特殊的线性表，其操作原则“先进后出”或“后进先出”。在进栈系列ABCDEF中，B比A后进栈，在出栈时应比A先出栈，故不可以得到EDFCAB系列。,六、编程题,写一个算法，借助栈将一个单链表(带有头结点)置逆；给定函数如下，Iin_stack(S)，初始化栈；Pop_stack(S,p),入栈； Push_stack(S,P)，出栈； Enmpty_stack(S)，栈空。单链表的结点结构说明及函数名如下： typedef struct node /*定义结点结构*/ datatype data;struct node *next;LinkNode， *lklist; 函数首部为： Lklist Re_Linklist (lklist L),Lklist Re_Linklist (lklist L) Linknode *p, *q, *r ;p=L-next, r = L, L-next=NULL； Iin_stack(S)while(p) Push_stack(S,P)； P=P-next；while(！Enmpty_stack(S) Pop_stack(S,q)； r-next =q；r=q； r-next =NULL； return L； ,1题参考答案,
