发布时间 : 星期日 文章数据结构c语言版试题大全（含答案）更新完毕开始阅读13adb34dc850ad02de804116
23、栈
24、1223334444 25、285 26、O(1) 27、O(n) 28、O(n)
31、大于等于
数据结构复习题：栈和队列 问答题
1、试述栈的基本性质?
2、何谓队列的上溢现象?解决它有哪些方法，且分别简述其工作原理。 3、假定用一个循环单链表表示队列（称此为循环链队），该队列只设一个队尾指针， 不设队首指针，试编写下列算法：
(1)向循环链队插入一个元素为x的结点。
(2)从循环链队中删除一个结点（假定不需要保留被删除结点的值和不需要回收结点）。
4、为什么说栈是一种后进先出表?
5、对于一个栈,给出输入项A,B,C。如果输入项序列由A,B,C所组成,试给出全部可能的输出序列。
6、有字符串次序为3*y-a/y↑2,试利用栈给出将次序改变为3y-*ay2↑/-的操作步骤。(可用X代表扫描该字符串函数中顺序取一字符进栈的操作,用S代表从栈中取出一个字符加到新字符串尾的出栈的操作)。例如:ABC变为BCA,则操作步骤为XXSXX。
7、跟踪以下代码,显示每次调用后队列中的内容。 InitQueue(qu); EnQueue(qu,'A'); EnQueue(qu,'B); EnQueue(qu,'C); EnQueue(qu,x; EnQueue(qu,x; EnQueue(qu,'D); EnQueue(qu,'E); EnQueue(qu,'F); EnQueue(qu,x) EnQueue(qu,'G); EnQueue(qu,X) EnQueue(qu,X) EnQueue(qu,X) 8、假设Q[0..10]是一个线性队列,初始状态为front=rear=0,画出做完下列操作后队列的头尾指针的状态变化情况,若不能入队,请指出其元素,并说明理由。 d,e,b,g,h入队 d,e出队 i,j,k,l,m入队 n,o,p入队
9、假设CQ[0..10]是一个环形队列,初始状态为front=rear=0,画出做完下列操作后队列的头尾指针的状态变
- 41 -
化情况,若不能入队,请指出其元素,并说明理由。 d,e,b,g,h入队 d,e出队 i,j,k,l,m入队 b出队 n,o,p入队
10、有5个元素,其进栈次序为A、B、C、D、E,在各种可能的出栈次序中,以元素C、D最先出栈(即C第一个且D第一个出栈)的次序有哪几个?
11、设输入元素为1、2、3、P和A,入栈次序为123PA,元素经过栈后到达输出序列,当所有元素均到达输出序列后,有哪些序列可以作为高级语言的变量名? 12、简要叙述栈和队列的特点.
数据结构复习题答案：栈和队列 问答题
1、解答：由栈的定义可知，这种结构的基本性质综述如下：
(1)集合性。栈是由若干个元素集合而成，当没有元素的空集合称为空栈；
(2)线性结构。除栈底元素和栈顶元素外，栈中任一元素均有唯一的前驱元素和后继元素； (3)受限制的运算。只允许在栈顶实施压入或弹出操作，且栈顶位置由栈指针所指示；
(4)数学性质。当多个编号元素依某种顺序压入，且可任意时刻弹出时，所获得的编号元素排列的数目，恰好满足卡塔南数列的计算，即： Ｃn ＝Ｃn 2n /(n＋1)
其中，n为编号元素的个数，Cn 是可能的排列数目。
2、解答：在队列的顺序存储结构中，设队头指针为front,队尾指针为rear,队的容量（存储空间的大小）为m。当有元素要加入队列时，若rear＝m（初始时reat＝0），则发生队列的上溢现象，该元素不能加入队列。
这里要特别注意的是：队列的假溢出现象，队列中还有空余的空间，但元素不能进队 列。造成这种现象的原因是由于队列的操作方式所致。 解决队列的上溢有以下几种方法：
(1)建立一个足够大的存储空间，但这样做往往会造成空间使用的效率低。 (2)当出现假溢出时，可采用以下几种方法：
①采用平移元素的方法。每当队列中加入一个元素时，队列中已有的元素向队头 移动一个位置（当然要有空余的空间可移）；
②每当删去一个队头元素时，则依次序移队中的元素，始终使front指针指向队列 中的第一个位置；
③采用循环队列方式。把队头队尾看成是一个首尾相邻的循环队列，虽然物理上 队 3、解答： (1) 解答:status insert(Rear,x){
// 假定Rear为循环链队的队尾指针，x为待插入的元素 (1) malloc(p);
p->data＝x; // 建立值为x的新结点p＾ (2) if( Rear＝nil){
Rear＝p; Rear->next＝p; }
else {p->next＝Rear->next;
- 42 -
Rear->next＝p; Rear＝p; }
// 若条件成立则建立循环链队的第一个结点，否则在队尾插入p＾结点 }
(2) 解答:status delete(Rear){
if( Rear＝nil ) error('underflow'); if (Rear->next= =Rear) Rear＝nil; else Rear->next＝Rear->next->next;
} //Rear＾.next 所指向的结点为循环链队的队首结点
4、栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。 栈也称为后进先出表（LIFO--Last IN First Out表）。 5、AＢＣ，ＢＡＣ，ＣＢＡ
6、X:进栈 S:出栈XSXXXSSSXXSXXSXXSSSS 7、解答：InitQueue(qu); 队列为空 EnQueue(qu,'A'); 队列为A EnQueue(qu,'B); 队列为AB EnQueue(qu,'C); 队列为ABC EnQueue(qu,x; 队列为ABCx EnQueue(qu,x; 队列为ABCxx EnQueue(qu,'D); 队列为ABCxxD EnQueue(qu,'E); 队列为ABCxxDE EnQueue(qu,'F); 队列为ABCxxDEF EnQueue(qu,x) 队列为ABCxxDEFx EnQueue(qu,'G); 队列为ABCxxDEFxG EnQueue(qu,X) 队列为ABCxxDEFxGX EnQueue(qu,X) 队列为ABCxxDEFxGXX EnQueue(qu,X) 队列为ABCxxDEFxGXXX
8、解答：d,e,b,g,h入队 d e b g h F r d,e出队
b g h F r i,j,k,l,m入队 b g h i j k l m F r n,o,p入队 b g h i j k l m n o p
F r
所有元素均正好能入队，共有11个存储空间，恰好11个元素。
- 43 -
9、解答： 图略 。
p不能入队，共有11个地址，p为第12个元素，故不能入队。
10、答：三个：CDEBA，CDBEA，CDBAE
11、答：一般说，高级语言的变量名是以字母开头的字母数字序列。故本题答案是: AP321,PA321,P3A21,P32A1,P321A。
12、 答：栈和队列都是插入和删除操作的位置受限制的线性表。栈是限定仅在表尾进行插入和删除的线性表，是后进先出的线性表，而队列是限定在表的一端进行插入，在另一端进行删除的线性表，是先进先出的线性表。
- 44 -