数据结构习题.doc

第1章 概论
一、选择题
1. 要求同一逻辑结构的所有数据元素具有相同的特性，这意味着（ B ）
A、数据元素具有同一的特点。
B、不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致。
C、每个数据元素都一样。
D、数据元素所包含的数据项的个数要相等。
2. 数据结构是一门研究非数值计算的程序设计问题中计算机的（ （c） ）以及它们之间的（ B ）和运算的学科。
（1）A、操作对象 B、计算方法 C、逻辑存储 D、数据映象
（2）A、结构 B、关系 C、运算 D、算法
3. 数据结构被形式的定义为（D，R），其中D是（ （B） ）的有限集合，R是D上（ （D） ）的有限集合。
（1）A、算法 B、数据元素 C、数据操作 D、逻辑结构
（2）A、操作 B、映象 C、存储 D、关系
4. 在数据结构中，从逻辑上可以把数据结构分为（ C ）
A、动态结构和静态结构 B、紧凑结构和非紧凑结构
C、线性结构和非线性结构 D、内部结构和外部结构
5. 线性-表的顺序存储结构是一种（ A ）的存储结构。
A、随机存取 B、顺序存取 C、索引存取 D、Hash存取
6. 算法分析的目的是（ C ）
A、找出数据结构的合理性 B、研究算法中的输入和输出的关系
C、分析算法的效率以求改进 D、分析算法的易懂性和文档性
7. 计算机算法指的是（ （C） ）。它必需具备输入、输出和（ （B） ）等五个特征。
（1） A、计算方法 B、排序方法
C、解决某一问题的有限运算序列 D、调度方法
（2） A、可行性、可移植性和可扩充性
B、可行性、确定性和有穷性
C、确定性、有穷性和稳定性
D、易读性、稳定性和安全性
8. 线性表若采用链表存储结构时，要求内存中可用存储单元的地址（ D）
A、必须是连续的 B、部分地址必须是连续的
C、一定是不连续的 D、连续不连续都可以
9. 在以下的叙述中，正确的是（B ）
A、线性表的线性存储结构优于链式存储结构
B、二维数组是它的每个数据元素为一个线性表的线性表
C、栈的操作方式是先进先出
D、队列的操作方式是先进后出
10. 根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的
数据组织形式。以下解释错误的是 ( A )
A、集合中任何两个结点之间都有逻辑关系但组织形式松散
B、线性结构中结点按逻辑关系依次排列形成一条"锁链"
C、树形结构具有分支、层次特性，其形态有点像自然界中的树
D、图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接
11. 以下说法正确的是( D )
A、数据元素是数据的最小单位
B、数据项是数据的基本单位
C、数据结构是带有结构的各数据项的集合
D、数据结构是带有结构的数据元素的集合
二、判断题
1. 数据元素是数据的最小单位。0
2. 数据结构是带有结构的数据元素的集合。1
3. 数据结构，数据元素，数据项在计算机中的映象分别称为存储结构，结点，数据域。1
4. 数据项是数据的基本单位。0
5. 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。1
6. 数据的物理结构是数据在计算机中实际的存储形式。1
7. 算法和程序没有区别，所以在数据结构中二者是通用的。0
8. 顺序存储结构属于静态结构，链式存储结构属于动态结构。0
三、填空题
1. 所谓数据的逻辑结构指的是数据元素之间的 __逻辑关系
_____。
2. 数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容数据的逻辑结构、数据的存储结构、对数据施加的操作。
3. 数据的逻辑结构包括 集合 、 线性结构 、 树形结构 和图状构图 四种类型。
4. 在线性结构中，开始结点_没有____前驱结点，其余每个结点有且只有_1___个结点。
5. 在树形结构中，树根结点只有__1____，其余每个结点有且只有__1____前驱结点；叶子结点没有_后继_____结点，其余每个结点的后继结点可以_任意个____。
6. 在图形结构中，每个结点的前驱结点和后继结点可以有__任意个_____。
7. 算法的五个重要特性是_有穷性____、_确定性____、_可行性____、_输入____、_输出____。
8. 下列程序段的时间复杂度是_____。
for (i=1;i<=n;i++)
A[i][j]=0;
9. 下列程序段的时间复杂度是_____。
s=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
s=s+B[i][j];
sum=s;
10. 存储结构是逻辑结构的__物理________实现。
11. 从数据结构的观点看，通常所说的"数据"应分成三个不同的层次，即__数据________、_数据元素_________和_数据项_________。
12. 根据需要，数据元素又被称为__结点________、___记录_______、___元素_______或__顶点________。
13. 通常，存储结点之间可以有__顺序存储、链式存储、索引存储、散列存储________、__________、__________、________四种关联方式，称为四种基本存储方式。
14. 通常从_正确性、可读性、健壮性、高效性__________、___________、___________、___________等几方面评价算法的(包括程序)的质量。
15. 一个算法的时空性能是指该算法的__时间复杂度______________和___空间复杂度_____________，前者是算法包含的__计算量_________，后者是算法需要的___存储量________。
16. 在一般情况下，一个算法的时间复杂性是___问题规模
________的函数。
17. 常见时间复杂性的量级有：常数阶O(____1_______)、对数阶O(___________)、线性阶O ( ___n________)、平方阶O(___________)、和指数阶O(___________)。通常认为，具有指数阶量级的算法是__不可行_________的。
18. 数据结构的基本任务是数据结构的__设计_________和___实现________。
19. 数据对象是性质相同的 数据元素 的集合。
20. 抽象数据类型是指一个 数学模型 以及定义在该模型上的一组操作。
四、应用题
1. 分析下列程序段的时间复杂度。
……
i=1；
WHILE（i<=n）
i=i*2；
……
2. 叙述算法定义及其重要特性。
3. 简述下列术语：数据，数据元素，数据结构，数据对象。
4. 逻辑结构与存储结构是什么关系?
5. 将数量级，n，n2，n3，nlog2n，log2n，2n，，n!，，，按增长率进行排列。
6. 设有数据逻辑结构为：D={k1,k2,k3,………,k9}
R={<k1,k3>,<k1,k8>,<k2,k3>,<k2,k4>,<k2,k5>,<k3,k9>,<k5,k6>,<k8,k9>,<k9,k7>,<k4,k6>}
画出这个逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点？
7. 设有如图1.1所示的逻辑结构图，给出它的逻辑结构，并说出它是什么类型的逻辑结构。

k1
k5
k8
k2
k3
k6
k4
k7
图1.1

8. 分析下列程序的时间复杂度（设n为正整数）
(1) int rec(int n)
{if(n==1) return(1);
else return(n*rec(n-1));
}
(2) x=91;y=100;
while(y>0)
if(x>10) y--;
(3) i=1;j=0;
while(i+j<=n)
if(i>j) j++;
else i++;
(4) x=n;y=0;
while(x>=(y+1)*(y+1)) y++;
9. 设n为正数。试确定下列各程序段中前置以记号@的语句的频度：
（1）i=1;k=0;
while(i<=n-1)
{@k+=10*i;
i++;
}
(2) k=0;
for(i=1;i<=n;i++)
for(j=i;j<=n;j++)
@ k++;
第2章 线性表
一、选择题
1. 线性结构中的一个结点代表一个（ A ）
A、数据元素 B、数据项 C、数据 D、数据结构
2. 非空线性表L=(a1,a2,...,ai,...,an)，下列说法正确的是（ D ）
A、每个元素都有一个直接前驱和直接后继
B、线性表中至少要有一个元素
C、表中诸元素的排列顺序必须是由小到大或由大到小的
D、除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继
3. 顺序表是线性表的（ B ）
A、链式存储结构 B、顺序存储结构 C、索引存储结构 D、散列存储结构
4. 对于顺序表，以下说法错误的是（ A ）
A、顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址
B、顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列
C、顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻
D、顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中
5. 对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（ B ）为标准操作。
A、插入操作 B、结点移动 C、算术表达式 D、删除操作
6. 对于顺序表的优缺点，以下说法错误的是（ C ）
A、无需为表示结点间的逻辑关系而增加额外的存储空间
B、可以方便地随机存取表中的任一结点
C、插入和删除运算较方便
D、由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)
7. 在含有n个结点的顺序存储的线性表中，在任一结点前插入一个结点所需移动结点的平均次数为（ B ）
A、n B、n/2 C、(n-1)/2 D、(n+1)/2
8. 在含有n个结点的顺序存储的线性表中，删除一个结点所需移动结点的平均次数为（ C ）
A、n B、n/2 C、(n-1)/2 D、(n+1)/2
9. 带头结点的单链表head为空的条件是（B ）
A、head=NULL B、head->next=NULL C、head->next=head D、head!=NULL
10. 非空循环单链表head的尾结点*p满足（ C ）
A、p->next=NULL B、p=NULL C、p->next=head D、p=head
11. 在循环双链表的*p结点之后插入*s结点的操作是（ D ）
A、p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;
B、p->next=s; p->next->prior=s; s->prior=p; s->next=p->next;
C、s->prior=p; s->next=p->next;p->next:=s; p->next->prior=s;
D、s->prior =p; s>next=p>next; p>next->prior =s;p->next=s;
12. 在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q和*p之间插入结点*s，则执行（ C ）
A、s->next=p->next; p->next=s;
B、p->next=s->next; s->next=p;
C、q->next=s; s->next=p;
D、p->next=s; s->next=q;
13. 在一个单链表中，若*p结点不是最后结点，在*p之后插入结点*s，则执行（ B ）
A、s->next=p; p->next=s;
B、s->next=p->next; p->next=s;
C、s->next= p->next; p=s;
D、p->next=s; s->next=p;
14. 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ A ）存储方式最节省时间。
A、顺序表 B、单链表 C、双链表 D、单循环链表
15. 设rear是指向非空带头结点的循环单链表的尾指针，则删除表中第一元素的操作可表示为（D ）
A、p=rear; rear=rear->next; free(p)
B、rear=rear->next; free(rear);
C、rear=rear->next->next; free(rear);
D、p=rear->next->next; rear->next->next=p->next; free(p);
16. 在一个单链表中，若删除*p结点的后继结点，则执行（ A ）
A、q=p→next; p→next=q→next; free(q);
B、p=p->next; p->next= p->next->next;free(p);
C、p->next= p->next;free(p->next);
D、p= p->next->next;free(p->next);
17. 设指针P指向双链表的某一结点，则双链表结构的对称性可用（ C ）式来刻画
A、p->prior->next==p->next->next
B、p->prior->prior==p->next->prior
C、p->prior->next==p->next->prior
D、p->next->next==p->prior->prior
18. 在循环链表中，将头指针改设为尾指针rear后，其头结点和尾结点的存储位置分别是 （ B ）
A、rear和rear->next->next
B、rear->next 和rear
C、rear->next->next和rear
D、rear和rear->next
19. 循环链表主要优点是（ D ）
A、不再需要头指针了
B、已知某个结点的位置后，能够容易找到它的直接前趋
C、在进行插入、删除运算时，能更好地保证链表不断开
D、从表中任一结点出发都能扫描到整个链表
20. 在线性表的下列存储结构中，读取元素花费时间最少的是（ D ）
A、单链表 B、双链表 C、循环链表 D、顺序表
二、判断题
1. 顺序存储的线性表可以随机存取。A
2. 顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动。B
3. 线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。A
4. 在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。B
5. 在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。A
6. 在单链表中，可以从头结点进行查找任何一个元素。A
7. 线性表的链式存储结构优于顺序存储结构。B
8. 在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。A
9. 在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。B
10. 顺序存储方式只能用于存储线性结构。B
三、填空题
1. 为了便于讨论，有时将含n(n≥0)个结点的线性结构表示成(a1，a2,…,an)，其中每个ai代表一个__结点____。a1称为__第一个____结点，an称为__最后一个____结点，i称为ai在线性表中的__位置______。对任意一对相邻结点ai、ai┼1(1≤i<n),ai称为ai┼1的直接_前驱_____，ai┼1称为ai的直接_后继_____。
2. 线性结构的基本特征是：若至少含有一个结点，则除起始结点没有直接_前驱_____外，其他结点有且仅有一个直接__前驱____；除终端结点没有直接_后继_____外，其它结点有且仅有一个直接__后继____.
3. 所有结点按1对1的邻接关系构成的整体就是__线性____结构。
4. 线性表的逻辑结构是_线性_____结构。其所含结点的个数称为线性表的__长度________。
5. 在单链表中，删除p所指结点的直接后继的操作是__ q=p→next; p→next=q→next; free(q);______。
6. 非空的循环单链表head的尾结点（由指针p所指）满足__ p→next=head ___。
7. rear是指向非空带头结点的循环单链表的尾指针，则删除起始结点的操作可表示为__ p=rear→next; q=p→next;p→next=q→next; free(q)___。
8. 对于一个具有n个结点的单链表，在p所指结点后插入一个结点的是时间复杂度为_______，在给定值为x的结点后插入新结点的时间复杂度为______。
9. 单链表表示法的基本思想是用__指针______表示结点间的逻辑关系。
10. 在顺序表中插入或删除一个元素，需要平均移动_一半___元素，具体移动的元素个数与_元素位置______有关。
11. 向一个长度为n的向量的第i个元素（1≤i≤n+1）之前插入一个元素时，需向后移动___ n-i+1________个元素。
12. 向一个长度为n的向量中删除第i个元素（1≤i≤n〉时，需向前移动__ n-i+______个元素。
13. 在双链表中，每个结点有两个指针域，一个指向___前驱______，另一个指向__后继________。
14. 在一个带头结点的单向循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head= p→next→next 。
15. 设head指向单链表的表头，p指向单链表的表尾结点，则执行p->next=head后，该单链表构成 单循环链表 。
16. 在单链表中，若p和s是两个指针，且满足p->next与s相同，则语句p->next=s->next作用是 删除 s指向的结点。
17. 设r指向单循环链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是__ s→next=r->next_________；r->next=s; r=s;。
18. 在单链表中，指针p所指结点为最后一个结点的条件是__ p→next=NULL _________。
19. 在双循环链表中，若要在指针p所指节点前插入s所指的节点，则需执行下列语句：
s->next=p；
s->prior=p->prior；
1. __ p→prior→next________________=s；
p->prior=s；
20. 在单链表中的p所指结点之前插入一个s所指结点时，可进行下列操作：
s->next=_______；
p->next=s;
temp=p->data；
p->data=_______；
s->data=________；
四、应用题
1. 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。
2. 何时选用顺序表、何时选用链表作为线性表的存储结构为宜？
3. 在顺序表中插入和删除一个结点需平均移动多少个结点？具体的移动次数取决于哪两个因素？
4. 为什么在单循环链表中设置尾指针比设置头指针更好？
5. 双链表和单循环链表中，若仅知道指针p指向某个结点，不知道头指针，能否将结点*p从相应的链表中删除？若可以，其时间复杂度各为多少？
6. 下列算法的功能是什么？
LinkedList test1(LinkedList L)
{//L是无头结点的单链表
ListNode *q,*p;
if(L&&L->next)
{q=L ; L=L->next; p=L;
while(p->next) p=p->next;
p->next=q; q->next=NULL;
}
return L;
}
7. 如果有n个线性表同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度也会自动地改变。在此情况下，应选择哪一种存储结构。为什么？
8. 若线性表的总数基本稳定，且很少进行插入删除操作，但要求以最快的方式存取线性表的元素，应该用哪种存储结构。为什么？
9. 设有多项式a(x)=9+8x+9x4+5x10
b(x)=-2x+22x7-5x10
（1） 用单链表给出a(x)、b(x)的存储表示；
（2） 设c (x)=a(x)+b(x)，求得c(x)并用单链表给出其存储表示。
第3章 栈和队列
一、选择题
1. 设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1，则栈的容量至少应该是（ b ）
A、2 B、 3 C、 5 D、 6
2. 若一个栈的输入序列是a,b,c，则通过入、出栈操作可能得到a,b,c的不同排列个数为（ b ）
A、 4 B、 5 C、 6 D、 7
3. 设有一顺序栈已经含有3个元素，如图3.1所示元素a4正等待进栈。下列不可能出现的出栈序列是（ a ）
0 maxsize-1
A、a3,a1,a4,a2 B、 a3,a2,a4,a1 C、 a3,a4,a2,a1 D、 a4,a3,a2,a1

a1
a2
Top
a3

图3.1
4. 链栈和顺序栈相比，有一个比较明显的优势是（ a ）
A、通常不会出现栈满的情况 B、 通常不会出现栈空的情况
C、 插入操作更容易实现 D、 删除操作更加容易实现
5. 若一个栈的输入序列是1,2,3,4,…,n，输出序列的第一个元素是n，则第i个输出元素是（ c ）
A、不确定 B、 n-i C、 n-i+1 D、n-i-1
6. 以下说法正确的是( a )
A、因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况
B、因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况
C、对于链栈而言,在栈满状态下,如果此时再作进栈运算，则会发生“上溢”
D、对于顺序栈而言在栈满状态下如果此时再作进栈运算，则会发生“下溢”。
7. 顺序队列的入队操作应为（ a ）
A、 sq.rear=sq.rear+1; sq.data[sq.rear]=x;
B 、sq.data[sq.rear]=x; sq.rear=sq.rear+1;
C 、sq.rear=(sq.rear+1)% maxsize; sq.data[sq.rear]=x;
D 、sq.data[sqrear]=x; sq.rear=(sq.rear+1)% maxsize;
8. 循环队列的入队操作应为（ c ）
A 、sq.rear=sq.rear+1; sq.data[sq.rear]=x
B 、sq.data[sq.rear]=x;sq.rear=sq.rear+1;
C 、sq.rear=(sq.rear+1)% maxsiae; sq.data[sq.rear]=x;
D 、sq.data[sq.rear]=x; sq.rear=(sq.rear+1)% maxsize;
9. 顺序队列的出队操作为（ b ）
A 、sq.front=(sq.front+1)% maxsize；
B 、sq.front=sq.front+1；
C 、sq.rear=(sq.rear+1)% maxsize；
D 、sq.rear=sq.rear+1 ；
10. 循环队列的出队操作为( a )
A 、sq.front=(sq.front+1)% maxsize；
B 、sq.front=sq.front+1；
C 、sq.rear=(sq.rear+1)% maxsize；
D 、sq.rear=sq.rear+1；
11. 循环队列的队满条件为（ c ）
A、 (sq.rear+1) % maxsize = =(sq.front+1) % maxsize;
B 、(sq.rear+1) % maxsize = =sq.front+1
C 、(sq.rear+1) % maxsize = =sq.front
D 、sq.rear = =sq.front
12. 循环队列的队空条件为（ d ）
A 、(sq.rear+1) % maxsize = =(sq.front+1) % maxsize；
B 、(sq.rear+1) % maxsize = =sq.front+1；
C 、(sq.rear+1) % maxsize = =sq.front；
D 、sq.rear = = sq.front；
13. 如果以链表作为栈的存储结构,则退栈操作时（ c ）
A、必须判别栈是否满 B、判别栈元素的类型
C、必须判别栈是否空 D、 对栈不做任何判别
14. 向一个栈顶指针为Top的链栈中插入一个s所指结点时，其操作步骤为（ c ）
A、Top->next=s; B、 s->next=Top->next;Top->next=s;
C、s->next=Top;Top=s; D、 s->next=Top;Top=Top->next;
15. 从栈顶指针为Top的链栈中删除一个结点，并将被删节点的值保存到x中，其操作步骤为（ a ）
A、x=Top->data;Top=Top->next; B、Top=Top->next;x=Top->data;
C、x=Top;Top=Top->next; D、x=Top->data;
16. 在一个链队中，若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;
17. 一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（ c ）
A 、e d c b a B、d e c b a C、d c e a b D、a b c d e
18. 一个队列的入队序列是1，2，3，4，则队列的可能的输出系列是（ b ）
A、 4，3，2，1 B、 1，2，3，4 C、1，4，3，2 D、 3，2，4，1
19. 设计一个判别表达式中左、右括号是否配对出现的算法，采用（ b ）数据结构最佳。
A、线性表的顺序存储结构 B、栈
C 、队列 D、 线性表的链式存储结构
20. 若以1234作为双端队列的输入序列，则既不能由输入受限双端队列得到，也不能由输出受限双端队列得到的输出序列是（ c ）
A、1234 B、4132 C、4231 D、4213
二、 判断题
1. 在顺序栈栈满情况下，不能做进栈运算，否则会产生“上溢”。a
2. 链栈与顺序栈相比的一个优点是链栈插入和删除操作更加方便。b
3. 若一个栈的输入序列为1，2，3，…，n，其输出序列的第一个元素为n，则其输出序列的每个元素ai一定满足ai=i+1(i=1,2, …,n)。b
4. 在链队列中，即使不设置尾指针也能进行入队操作。a
5. 在对链队列（带头指针）做出队操作时，不会改变front指针的值。a
6. 循环队列中元素个数为rear-front。b
7. 一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到4,3,1,2。b
8. 一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到1,2,3,4。a
9. 若以链表作为栈的存储结构，则进栈需要判断栈是否满。b
10. 若以链表作为栈的存储结构，则出栈需要判断栈是否空。a
三、 填空题
1. 向一个栈顶指针为Top的链栈中插入一个s所指的结点时，其进行的操作是__ s->next=Top; Top=s ____。
2. 从栈顶指针为Top的链栈中删除一个结点，并将结点保存在x中，进行的操作是_ x=Top->data; ______。在具有n个单元的循环队列中，队满时共有_ n-1____个元素。
3. 假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为 b c e d a 。
4. 设有数组A[0..m]作为循环队列的存储空间，front为队头指针，rear为队尾指针，则元素x执行入队操作的语句是 if((rear+1)%(m+1)!=front) {rear=(rear+1) % (m+1); A[rear]=x;} 。
5. 在一个链队列中，如f,r分别为队首，队尾指针，则插入s所指结点的操作是__ r->next=s; r=s;____。
6. 栈的逻辑特点是 后进先出 ，队列的逻辑特点是_先进先出_______，二者共同特点是__操作受限_____。
a) _栈______可以作为实现递归函数调用的一种数据结构。
b) 在队列中，新插入的结点只能添加到 队尾 。
data
next
7. 链队在一定范围内不会出现 队满 的情况。当lq.front= =lq.rear时，队中无元素，此时 队空 。
8. 设一个链栈的栈顶指针为ls，栈中结点的格式为 ，栈空的条件是___________；如果栈不为空，则退栈操作为p=ls; ;free(p)。
9. 对带有头结点的链队列lq,判定队列中只有一个数据元素的条件是___________。
10. 设有一个空栈，现在输入序列为1，2，3，4，5，经过push，push，pop，push，pop，push，后栈顶指针所指元素是____4______。
11. 设用一维数组A[1..n]来表示一个栈，令A[n]为栈底。用整型变量t来指示当前栈顶的位置，A[t]为栈顶元素。往栈中压入一个新元素时，变量t的值__减1_______，从栈中弹出一个元素时，变量t的值__加1_________。设空栈时，有输入序列a,b,c经过push，pop，push，push，pop操作后，从栈中弹出的元素是___c________。
四、应用题
1. 试证明：若借助栈由输入序列1，2，3，…… ，n得到输出序列p1，p2，…… ，pn(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着i<j<k, 使pi<pj<pk。
2. 设有字符串为3*-y-a/y^2，试利用栈写出将其转换为3y-*ay2^/-的操作过程。假定用X代表扫描该字符串过程中顺序取一个字符进栈的操作，用S代表从栈中取出一个字符加入到新字符串尾的出栈操作。例如，ABC变为BCA的操作步骤为XXSXSS。
3. 设有一个输入序列abcd，元素经过一个栈到达输出序列，而且元素一旦离开输入序列就不能再回到输入序列，试问经过这个栈后可以得到多少种输出序列？
4. 按照运算符优先数法，画出对下面算术表达式求值时，操作数栈和运算符栈的变化过程：
9-2*4+(8+1)/3。
5. 设有一个双端队列，元素进入该队列的次序为abcd，试分别求出满足以下条件的输出序列： （1）能由输入受限双端队列得到，但不能由输出受限双端队列得到的输出序列。
（2）能由输出受限双端队列得到，但不能由输入受限双端队列得到的输出序列。
（3）既不能由输入受限双端队列得到，也不能由输出受限双端队列得到的输出序列。
6. 链栈中为何不设置头结点？
7. 证明：在求解n阶汉诺塔问题中，至少应执行的move操作次数为。
8. 设栈S＝（1，2，3，4，5，6，7），其中7为栈顶元素。写出调用algo后栈S的状态。
void algo(Stack *S)
{int i=0;
Queue Q; Stack T;
InitQueue(Q); InitStack(T);
while(!StackEmpty(S))
{if(i%2==0) Push(T,Pop(S));
else EnQueue(Q,Pop(S));
i++;
}
while(!QueueEmpty(Q))
Push(S,DeQueue(Q));
while(!StackEmpty(T))
Push(S,Pop(T));
}
9. 试将下列递推过程改写为递归过程。
void ditui(int n)
{i=n;
while(i>1