发布时间 : 星期二 文章数据结构练习 - 第三章 - 栈和队列- 更新完毕开始阅读54472da1561252d381eb6e7f
A. 对队列中的元素排序 B. 取出最近进队的元素 C. 在队头元素之前插入元素 D. 删除队头元素
53．用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时( )
A．仅修改队头指针 B.仅修改队尾指针
C．队头，队尾指针都可能要修改 D.队头，队尾指针都要修改 54．对于循环队列( )。
A. 无法判断队列是否为空 B. 无法判断队列是否为满 C. 队列不可能满 D. 以上说法都不是
55．循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( )。
A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front
56．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )
A. 1和 5 B. 2和4 C. 4和2 D. 5和1 57．栈和队的共同点是( )。
A. 都是先进后出 B. 都是后进先出 C. 只允许在端点处插入和删除元素 D. 没有共同点
58．设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。
A． 6 B. 4 C. 3 D. 2 59．4个园盘的Hahoi塔，总的移动次数为( ). A.7 B.-8 C.15 D.16 60．和顺序栈相比，链栈有一个比较明显的优势是（ ）。
A. 通常不会出现栈满的情况 B. 通常不会出现栈空的情况 C. 插入操作更容易实现 D. 删除操作更容易实现 61．执行（ ）操作时，需要使用队列作辅助存储空间。 A. 查找哈希(Hash)表 B. 广度优先搜索网 C. 先序(根)遍历二叉树 D. 深度优先搜索网 62．设有一顺序栈已经含有3个元素，如图3.1所示元素a4正等待进栈。下列不可能出现的出栈序列是（ A ）
A.a3,a1,a4,a2 B. a3,a2,a4,a1 C. a3,a4,a2,a1 D. a4,a3,a2,a1
a1 a2 Top a3
63．在一个链队中，若f,r分别为队首、队尾指针，则插入s所指结点的操作为（ B）
A.f->next=s;f=s; B.r->next=s;r=s; C.s->next=r;r=s; D.s->next=f;f=s;
5
64．若用一个大小为6的数组来实现循环队列，且当rear和front的值分别是0和3。
当从队列中删除一个元素，再加入两个元素后，rear 和front 的值分别是（A ） A. 2和4 B. 1和5 C. 4和2 D. 5和1
65．有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ C ）
A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6
二、填空题
1．后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式为___________________________。-1，3 4 X * + 2 Y * 3 / - 2．下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。 typedef struct {int s[100]; int top;} sqstack;
void push(sqstack &stack,int x) {
if (stack.top==m-1) printf(“overflow”);
else {____________________;_________________;} } stack.top++，stack.s[stack.top]=x
3．设输入序列为1、2、3，则经过栈的作用后可以得到___________种不同的输出序列。5
4．不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为____________。O(1)
5．设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储________个队列元素；当前实际存储________________个队列元素（设头指针F指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置）。m-1，(R-F+M)%M
6．设有一个顺序共享栈S[0：n-1]，其中第一个栈项指针top1的初值为-1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是____________________。top1+1=top2
7．栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为__________表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为_________表。FILO，FIFO
8．设某顺序循环队列中有m个元素，且规定队头指针F指向队头元素的前一个位置，队尾指针R指向队尾元素的当前位置，则该循环队列中最多存储_______队列元素。m-1
9．设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为_____________________。F==R
10．从一个栈删除元素时，首先取出 ，然后再前移一位 。栈顶元素、栈顶指针
11．后缀表达式“2 10 + 5 * 6 – 9 /”的值为 。6
12．中缀表达示3+X*（2.4/5-6）所对应的后缀表达示为______________。3 x 2.4 5 ／6 －*＋
13．用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342的出栈顺序，相应的S和X操作串为__SXSSXSXX______。
6
14．在循环队列中，存储空间为0～n-1,设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么队满标志为front=(rear+1)%n，队空标志为__front=rear______。
15．对于栈只能在___栈顶位置_____插入和删除元素。
16．设输入元素的顺序是A，B，C，D，通过栈的变换，在输出端可得到各种排列。若输出序列的第一个元素为D，则输出序列为__DCBA_____________。 17．队列中允许进行删除的一端为____队头___________。
18．我们通常把队列中允许插入的一端称为________队尾________。 19．队列的原则是 。先进先出；
20．顺序存储的队列如果不采用循环方式，则会出现 问题。假溢出 21．栈的原则是 。先进后出。
22．对于一个顺序栈作进栈运算时，应先判断栈是否为 ，判断的条件是 ，作出栈运算时，应先判断栈是否为 ，判断的条件是 。满 ;top==MAXSIZE-1 ;空 ;top==-1。
23．在长度为Maxsize的循环队列中，删除一个新元素，修改front队头指针为 。front=(front+1)/Maxsize
24．在链队列中，与入队相关的指针是 、与出队有关的指针是 （头指针或尾指针）。尾指针 、 头指针
25．当用长度为N的一维数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件为 。top = = 0
26．向一个栈顶指针为HS的链栈中插入一个新结点*P果，应执行 和 操作。p->next = HS 、HS = p
27．从一个栈顶指针为HS的非空链栈中删除结点并不需要返回栈顶结点的值和回收结点时，应执行 操作。HS = HS->next
28．假定front和rear分别为一个链队的队首和队尾指针，则该链队中只有一个结点的条件为 。( front = = rear ) && ( front <>NULL )
29．中缀算术表达式3+4/(25-(6+15))*8 所对应的后缀算术表达式为 。3 4 25 6 15 + - / 8 * + 30．后缀算术表达式24 8 + 3 * 4 10 7 - * / 所对应的中缀算术表达式为 ，值为 。(24+8)*3/(4*(10-7)) 、8
31．在一个具有n个单元的顺序栈中，假定以地址高端（即下标为n的单元）作为栈底，以top作为栈顶指针，则当向栈中压入一个元素时，top的变化是top=_____。 top-1
32．在作进栈运算时应先判别栈是否_(1)_;在作退栈运算时应先判别栈是否_(2)_；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_(3)_。
为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_(4)_分别设在内存空间的两端，这样只有当_(5)_时才产生溢出。 (1)满 (2)空 (3)n (4)栈底 (5)两栈顶指针相邻（即值之差的绝对值为1） 33．多个栈共存时，最好用_______作为存储结构。链式存储结构
34．顺序栈用data[1..n]存储数据，栈顶指针是top,则值为x的元素入栈的操作是_______。if(top!=n) data[++top]=x；
35．循环队列的引入，目的是为了克服_______。假溢出时大量移动数据元素。 36．设a=6, b=4, c=2, d=3, e=2, 则后缀表达式abc-/de*+的值为____。9
7
37．在循环队列中，队列长度为n ,存储位置从0到n-1编号，以rear指示实际的队尾元素，现要在此队列中插入一个新元素，新元素的位置是（ ）。 rear=(rear+1)%n
38．已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_______。 s=(LNode *)malloc(sizeof(Lnode))；
s->data=x;s->next=r->next；r->next=s；r=s；
39．区分循环队列的满与空，只有两种方法，它们是______和______。 牺牲一个存储单元 设标记
40．已知一循环队列的存储空间为[m..n]，其中n＞m，队头和队尾指针分别为front和rear，则此循环队列判满的条件是( ) (rear+1)%(n-m+1)==front 41．设有元素序列的入栈次序为：（a1,a2,?,an）,其出栈的次序为(ap1,ap2?,apn) 现已知pl=n,则pi=____。n-i+1
42．用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是 ____和____；若只设尾指针，则出队和入队的时间复杂度分别是____和____。O(1),O(n),O(1),O(1) 43．下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空： #include
void convert(char *a, int n) { int i;
if(i=n/10) convert(______,i); *a=__________; }
main()
{int number; char str[10]=””; scanf(“%d”,&number);
convert(str,number); puts(str); } a+1 n
44．写出下面程序的运行结果 program priout(input，output); procedure print(f1,f2:integer); var f3:integer;
begin if fl<=f2 then
begin if f2 mod fl=0 then f3:=f1+1 else f3:=f1+3； print(f3,f2-1); end
writeln(fl,’’,f2); end
begin print (4,16); end.
(13 11),(12 12),(9 13),(6 14),(5 15),(4 16) ∥输出每组两个数占一行，也没括号
三、判断题
1．（ ）不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。T
8