云南开放大学数据结构（C#语言）第三次离线作业

第3章
习题
一、填空题
1、线性表、栈和队列都是结构，可以在线性表的位置插入和删除元素，对于栈只能在位置插入和删除元素，对于队列只能在位置插入和位置删除元素。
2、对于顺序存储的栈，因为栈的空间是有限的，在进行运算时，可能发生栈的上溢，在进行运算时，可能发生栈的下溢。
3、向栈中压入元素的操作是。
4、对栈进行退栈的操作是。
5、在一个循环队列中，队首指针指向队首元素的。
6、从循环队列中删除一个元素时，其操作是。
7、在栈顶指针为s的链栈中，判定栈空的条件是。
二、选择题
1、栈和队列是两种特殊的线性表，栈的特点是（），队列的特点是（），二者的共同特点是只能在它们的（）处添加和删除结点。
A．端点 B．中间点 C．先进先出 D．后进先出
2、已知元素(8，25，14，87，5l，90，6，19，20)，问这些元素以怎样的顺序进入栈，才能使出栈的顺序满足：8在5l前面；90在87后面；20在14后面；25在6前面；19在90后面（）。
A．20，6，8，51，90，25，14，19，87
B．51，6，19，20，14，8，87，90，25
C．19，20，90，8，6，25，5l，14，87
D．6，25，51，8，20，19，90，87，14
3、已知队列(4，4l，5，7，18，26，15)，第一个进入队列的元素是4，则第五个出队列的元素是（）。
A．5 B．41 C．18 D．7
4、对于顺序存储的循环队列，存储空间大小为n，头指针为F，尾指针为R，队列中元素的个数应为（）。
A．R-F B．n+R-F C．(R-F+1)% n D．(n+R-F)% n
5、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（）。
A．4, 3, 2, 1 B． 2, 4, 3, 1 C．1, 2, 3, 4 D． 3, 2, 1, 4
6、下列关于栈的叙述中正确的是（）。
A．在栈中只能插入数据 B．在栈中只能删除数据
C．栈是先进先出的线性表 D．栈是先进后出的线性表
7、设栈S和队列Q的初始状态为空。元素a,b,c,d,e,f依次通过栈S，并且一个元素出栈后即进入队列Q，若出队的顺序为b,d,c,f,e,a,则栈S的容量至少应该为（）。
A． 3 B．4 C．5 D．6
三、判断题
1、栈和队列逻辑上都是线性表。　　（）
2、采用循环链表作为存储结构的队列就是循环队列。　　（）
3、栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。　　（）
4、在栈中只能插入数据。　　（）
5、在栈满情况下不能作进栈运算，否则产生“上溢”。　　　　　　　（）
6、判定一个队列q(最多元素为m)为空的条件是(q->rear+1) % m=q->front。　（）
四、应用题
1、数据元素进栈的次序为：a、b、c、d，进栈过程中允许出栈，试写出各种可能的出栈元素序列。
2、分析下面程序段的功能，下面程序段中所调用函数为顺序栈和循环队列的基本操作函数。
(1)void function1(SEQSTACK *s)
{ int i, array[MAXSIZE] , n=0 ;
while (!Stack_Empty(s)) {array[n++]=Pop_Stack(s);}
for (i=0;i< n; i++)
Push_Stack(s, arr[i]);
}
(2)SEQSTACK * function2(SEQSTACK *s1)
{ SEQSTACK *s2, *temp;
datatype x;
Init_Stack(s2);
Init_Stack(temp);
while (!Stack_Empty (s1))
{ x=Pop_Stack(s1) ;
Push_Stack(temp,x);
}
while (!Stack_Empty (temp) )
{ x=Pop_Stack(temp);
Push_Stack(s1,x);
Push_Stack(s2, x);
}
free(temp);
return s2;
}
(3)void function3( SEQQUEUE *q)
{/*设datatype 为int 型*/
int x;
SEQSTACK *s;
Init_Stack(s);
while (! Queue_Empty(q))
{ x=Del_Queue(q);
Push( s,x);
}
while (!Stack_Empty(s))
{ x=Pop_Stack(s);
Add_Queue( q,x );
}
free(s);
}
(4)SEQQUEUE *fuction4(SEQQUEUE *q1)
{ /* 设datatype 为int 型*/
SEQQUEUE *q2;
int x, i , len;
len=QueueLenth(q1);
Init_Queue(q2);
for (i=0; i< len; i++)
{ x=Del_Queue(q1 ) ;
Add_Queue(q2, x);
Add_Queue(q1,x);
}
return q2;
}
五、算法设计题
1、回文是指正读、反读均相同的字符序列，如”abba”和”abdba”均是回文，但”good”不是回文。试写一个算法，判定给定的字符向量是否为回文。
2、写一个算法，返回链栈中结点个数。
3、假设循环队列中只设rear和length分别指示循环队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件，并写出相应的入队(Add_Queue)和出队(Del_Queue)算法。