2022年数据结构基础练习 .pdf

《2022年数据结构基础练习 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构基础练习 .pdf（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构基础练习（栈和队列）学号姓名蓝礼巍班级 . 一、选择题1有 5 个元素 a,b,c,d,e依次进栈，允许任何时候出栈，则可能的出栈序列是c 。Abaecd Bdceab Cabedc D aebcd 2下列有关递归的叙述，不正确的是b 。A在计算机系统内，执行递归函数是通过自动使用栈来实现的。B在时间和空间效率方面，递归算法比非递归算法好。C递归函数的求解过程分为递推（进栈）和回推（出栈）两个阶段。D在递归函数中必须有终止递归的条件。3栈和队列均属于哪一种逻辑结构A 。A线性结构B顺序结构C非线性结构D链表结构4设输入元素为1 、2、3、P 和 A，输入次序为123PA ，元素经过栈后

2、得到各种输出序列，则可以作为高级语言变量名的序列有 d 种。A4 B5 C6 D7 5一个队列的入队序列为a，b， c，d，则该队列的输出序列是b 。Adcba Babcd Cadcb Dcbda 6在一个链式队列中， 假设 f 和 r 分别为队头和队尾指针，则插入 s 所指结点的运算是b 。A. f-next=s; f=s; B. r-next=s; r=s; C. s-next=s; r=s; D. s-next=f; f=s; 7如果 5 个元素出栈的顺序是1、2、3、4、5，则进栈的顺序可能是c 。A3、5、4、1、2 B1、4、5、3、2 C 5、4、1、3、2 D2、4、3、1、5

3、 8若已知一个栈的入栈序列是1，2，3， n，其输出序列为p1 ，p2 ，p3 ， pn ，若 p1=n，则 pi 为。Ai Bn-i C n-i+1 D不确定二、填空题1栈和队列是一种特殊的线性表，其特殊性体现在是运算受限线性表。设现有元素 e1,e2,e3,e4,e5和 e6 依次进栈，若出栈的序列是e2,e4,e3,e6,e5,e1，则栈 S 的容量至少是3 。2顺序循环队列中，设队头指针为front ，队尾指针为rear ，队中最多可有MAX个元素，采用少用一个存储单元的方法区分队满与队空问题，则元素入队列时队尾指针的变化为 Rear=(rear+1)%MAX ； 元 素 出 队 列

4、时 队 头 指 针 的 变 化 为fort=(fotr+1)%MAX ；队列中的元素个数为 (rear-fort+MAX)%MAX 。 若则可用表示队满的判别条件，队空的判别条件仍然为 rear=fort 。三、解答题名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 3 页 - - - - - - - - - 1 用一维数组a7 顺序存储一个循环队列，队首和队尾指针分别用front和 rear表示，当前队列中已有5 个元素： 22 ，30 ， 16 ，36 ，58 ，其中

5、22 是队首，front值为 5，请画出对应的存储状态图，当连续做两次出队运算后，再做两次入队运算，让元素80 ，55依次进队，请再画出对应的存储状态图。22 58 36 16 30 55 80 58 36 16 2. 用一个带头结点的循环链表来表示循环队列，且该队列只设尾指针。编写初始化、入队、出队操作算法。StructLNode ElemType data; LNode *next; LinkQueue; LinkQueue *rear; Void EnQueue(LinkQueue *&rear ,ElemType item) LNode *newPtr=new LNode; Newpt

6、r-data=item; Newptr-next=NULL；If(rear=NULL) Rear=newptr; Newptr-next=Newptr; Else Newptr-next=rear-next; Rear-next=newptr; Rear=newptr; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 3 页 - - - - - - - - - ElemType outQueue(LinkQueue &rear) If(rear=NULL) Cout错误 next; If(p=rear) Rear=NULL; Else Rear-neat=p-next; Temp=p-data; Delept p; Return temp; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 3 页 - - - - - - - - -