2013数据结构 概述 线性表 栈与队列 习题及答案
第一章概论
一、填空题
1、数据的存储结构可用四种基本的存储方法表示，分别是顺序、链式、索引和散列。
2、一个算法具有5个特性:有穷性、确定性、可行性，有零个或多个输入、有一个或多个输出。
3、数据结构包括数据的逻辑结构、存储结构和运算（或基本操作）这三个方面的内容。
4、数据结构中评价算法的两个重要指标是时间效率和空间效率。
5、一个数据结构在计算机中的表示称为存储结构。
6、从逻辑上可以把数据结构分为线性结构、非线性结构两大类
7、数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构。
8、数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。
9、数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）3个方面的内容。
10、算法效率的度量可以分为事先估算和事后统计法。
二、单项选择题
1、数据结构中，与所使用的计算机无关的是数据的是（C）；
A、存储结构
B、物理结构
C、逻辑结构
D、物理和逻辑结构
2、算法分析的目的是（C）
A)找出数据结构的合理性B)研究算法中的输入和输出的关系
C)分析算法的效率以求改进D)分析算法的易懂性和文档性
3、计算机算法指的是（C）
A)计算方法B)排序方法C)解决问题的有限运算序列D)调度方法
4、计算机算法必须具备输入、输出和（B）等5个特性。
A)可行性、可移植性和可扩充性B)可行性、确定性和有穷性
C)确定性、有穷性和稳定性D)易读性、稳定性和安全性
5、从逻辑上可以把数据结构分为（C）两大类。
A）动态结构、静态结构B）顺序结构、链式结构
C）线性结构、非线性结构D）初等结构、构造型结构
6、下列数据中，（C）是非线性数据结构。
A．栈 B.队列 C.完全二叉树 D.堆
7、算法分析的两个主要方面是（A）。
A)空间复杂性和时间复杂性B)正确性和简明性
C)可读性和文档性D)数据复杂性和程序复杂性
8、在下面程序段的时间复杂度（D）
i=1;
while(i<=n)
i=i*3;
n) A．O(3n)B．O(n)C．O(n3)D．O(log
3
9、在下面的程序段中，对x的赋值语句的频度为（C）
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
x=x+1;
n) A．O(2n)B．O(n)C．O(n2)D．O(log
2
10、下面关于算法说法错误的是（D）
A．算法最终必须由计算机程序实现
B.为解决某问题的算法同为该问题编写的程序含义是相同的
C.算法的可行性是指指令不能有二义性
D.以上几个都是错误的
11、数据结构通常是研究数据的（A）及它们之间的相互关系。
A．存储结构和逻辑结构B．存储和抽象
C．联系和抽象D．联系与逻辑
12、数据在计算机中存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（C）。A．存储结构B．逻辑结构C．顺序存储结构D．链式存储结构13、非线性结构中的每个结点（D）。
A．无直接前趋结点B．无直接后继结点
C．只有一个直接前趋和一个直接后继结点D．可能有多个直接前趋和多个直接后继结点14、链式存储结构所占存储空间（A）。
A．分两部分，一部分存储结点的值，另一部分存放表示结点间关系的指针
B．只有一部分，存放结点的值
C．只有一部分，存储表示结点间关系的指针
D．分两部分，一部分存放结点的值，另一部分存放结点所占单元数
15、数据的基本单位是（B）。
A．数据结构B．数据元素C．数据项D．文件
16、每个结点只含有一个数据元素，所有存储结点相继存放在一个连续的存储空间里。这种存储结构称为（A）结构。
A．顺序存储B．链式存储C．索引存储D．散列存储
17、每一个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是（B）存储方式。
A．顺序B．链式C．索引D．散列
18、算法分析的两个主要方面是（A）。
A．空间复杂性和时间复杂性B．正确性和简明性
C．可读性和文档性D．数据复杂性和程序复杂性
19、算法能正确的实现预定功能的特性称为算法的（A）。
A．正确性B．易读性C．健壮性D．高效性
20、算法在发生非法操作时可以作出相应处理的特性称为算法的（C）。
A．正确性B．易读性C．健壮性D．高效性
21、计算机算法必须具备输入、输出和（C）。
A．计算方法B．排序方法
C．解决问题的有限运算步骤D．程序设计方法
三、判断题
1.数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构.(×)
2.数据的逻辑结构是指数据的各数据项之间的逻辑关系；(×)
3.数据的物理结构是指数据在计算机内的实际存储形式。(√)
4．算法的优劣与算法描述语言无关，但与所用计算机有关。(×)
5．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。(√)
6．算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。(×)
四、简答题
1、当为解决某一问题而选择数据结构时，应从哪些方面考虑？
答：通常考虑算法所需要的存储空间量和算法所需要的时间量。后者又涉及到四方面：程序运行时所需输入的数据总量，对源程序进行编译所需时间，计算机执行每条指令所需时间和程序中指令重复执行的次数。
第2章线性表
一、填空
1．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用顺序存储结构。
2．顺序存储的线性表存储特点是用物理位置的相邻表示元素之间的关系的，在顺序表中插入或删除一个元素，移动的元素个数与表长和该元素在表中的位置有关。如果线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需
要移动元素的个数是（n-1）/2_；第i个元素（1<=i<=n）之前插入一个元素时，需向后移动n-i+1_个元素。如果要在第1个元素前插入一个元素，要后移n个元素；删除第i个元素(1≤i≤n)时，需向前移动n-i个元素。
3．设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点,若将结点y插入结点x之后，则需要执行以下语句:__py->next=px->next;_px->next=py
4．在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。
5、链接存储的特点是利用__指针来表示数据元素之间的逻辑关系。在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示，查找结点都必须从头结点开始，因此，链表也称为顺序存取的数据结构。在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n），在给定值为x的结点后插入一个新结点的时间复杂度为O(n)_。
7．已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：u=p->next;为空表的条件是：_L->next==L&&L->prior==L p->next=u->next;
8．带头结点的双循环链表L中只有一个元素结点的条件是：L->next->next==L；
二、判断正误（在正确的说法后面打勾，反之打叉）
（×）1.线性表的特点是每个元素都有一个前驱和一个后继。
（×）2.链表的物理存储结构具有同链表一样的顺序。
（×）3.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
（×）4.取线性表的第i个元素的时间同i的大小有关.
（×）5.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
（×）6.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
(√)7．链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。
（×）8.线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。（×）9.顺序存储方式只能用于存储线性结构。
（×）10.线性表的逻辑顺序与存储顺序总是一致的。
(×)11.链表中的头结点仅起到标识的作用。
(√)12.顺序存储结构的主要缺点是不利于插入或删除操作。
(√)13．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。(×)14．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。(×)15.对任何数据结构链式存储结构一定优于顺序存储结构。
三、单项选择题
1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（C）（A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构2．一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（B）（A）110（B）108（C）100（D）120
3.在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（A）
（A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
（B）在第i个结点后插入一个新结点（1≤i≤n）
（C）删除第i个结点（1≤i≤n）
（D）将n个结点从小到大排序
4.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（B）个元素
（A）8（B）63.5（C）63（D）7
5.线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（C）
A．O（i）B．O（1）C．O（n）D．O（i-1）
6.链表是一种采用（B）存储结构存储的线性表；
（A）顺序（B）链式（C）星式（D）网状
7.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D）
（A）必须是连续的（B）部分地址必须是连续的
（C）一定是不连续的（D）连续或不连续都可以
8．线性表Ｌ在（B）情况下适用于使用链式结构实现。
（Ａ）需经常修改Ｌ中的结点值（Ｂ）需不断对Ｌ进行删除插入
（Ｃ）Ｌ中含有大量的结点（Ｄ）Ｌ中结点结构复杂
9．单链表的存储密度（C）
（Ａ）大于1；（Ｂ）等于1；（Ｃ）小于1；（Ｄ）不能确定
10．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（B）A．head==NULL B．head→next==NULL C．head→ext==head D．head!=NULL 11．下面关于线性表的叙述中，错误的是哪一个？（B）
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
12．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采
用（D）存储方式最节省运算时间。
A．单链表B．仅有头指针的单循环链表
C．双链表D．仅有尾指针的单循环链表
13．链表不具有的特点是（B）
A．插入、删除不需要移动元素B．可随机访问任一元素
C．不必事先估计存储空间D．所需空间与线性长度成正比
14、设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用(D)最节省时间。
A.单链表
B.单循环链表
C.带尾指针的单循环链表
D.带头结点的双循环链
表
15、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（C）(1<=i<=n+1)。
A.O(0)
B.O(1)
C.O(n)
D.O(n2)
16、下述哪一条是顺序存储结构的优点？（A）
A、存储密度大B．插入运算方便
C．删除运算方便D．可方便地用于各种逻辑结构的存储表示
17．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（B）。
A．p->next=s;s->next=p->next;B．s->next=p->next;p->next=s;
C．p->next=s;p->next=s->next;D．p->next=s->next;p->next=s;
18、线性表是具有n个（C）的有限序列（n>0）。
A．表元素B．字符C．数据元素D．数据项
19、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）存储方式最节省时间。
A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表
20．在双向链表指针p的结点前插入一个指针q的结点操作是（C）。
A.p->prior=q;q->next=p;p->prior->next=q;q->prior=q；
B.p->prior=q;p->prior->next=q;q->next=p;q->prior=p->prior;
C.q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q;
D.q->prior=p->prior;q->next=q;p->prior=q;p->prior=q;
21、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（D）存储方式最节省时间。
A、单链表
B、双链表
C、单向循环
D、顺序表
22.链表不具有的特点是（B）
A．插入、删除不需要移动元素B．可随机访问任一元素
C．不必事先估计存储空间D．所需空间与线性长度成正比
24.单链表中，增加一个头结点的目的是为了（C）。
A．使单链表至少有一个结点B．标识表结点中首结点的位置
C．方面运算的实现D．说明单链表是线性表的链式存储
25、在含有n个结点的顺序存储的线性表中，在任一结点前插入一个结点所需移动结点的平均次数为(B)。
A．n B．n/2C．(n+1)/2D．(n-1)/2
26、设指针变量p指向单向链表中结点A，若删除单向链表中结点A，则需要修改指针的操作序列为（A）（q是指向该类结点的空指针）
A．q=p->next;p->data=q->data;p->next=q->next;free(q);
B．q=p->next;q->data=p->data;p->next=q->next;free(q);
C．q=p->next;p->next=q->next;free(q);
D．q=p->next;p->data=q->data;free(q);
27、与单链表相比，双链表的优点之一是（D）。
A、插入、删除操作更简单
B、可以进行随机访问
C、可以省略表头指针或表尾指针
D、顺序访问相邻结点更灵活
28、对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（C）。
A．O(n)O(n) B.O(n)O(1) C.O(1)O(n) D. O(1)O(1)
四、简答题
1.试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？
答：①顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。
优点：存储密度大（＝1？），存储空间利用率高。缺点：插入或删除元素时不方便。
②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。
若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；
若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。
2、在单链表和双向链表中，能否从当前结点出发访问到任何一个结点?
答：在单链表中不能从当前结点（若当前结点不是第一结点）出发访问到任何一个结点，链表只能从头指针开始，访问到链表中每个结点。在双链表中求前驱和后继都容易，从当前结点向前到第一结点，向后到最后结点，可以访问到任何一个结点。
五、算法设计题
1、有一个单链表，其头指针为head，编写一个函数计算数据域为x的结点的个数。
Int count（Node*head）{
node*p;
int n=0;p＝head；
While（P！＝NULL）｛
if（P－＞data==X）n＋＋；
P=p＞next；｝
return（n）d
}
2、试编写在带头结点的单链表中删除一个最小值结点的高效算法。
void delete（Linklist&L）
∥L是带头结点的单链表，本算法删除其最小值结点。
{p=L->next；∥p为工作指针。指向待处理的结点。假定链表非空。
pre=L；∥pre指向最小值结点的前驱。
q=p；∥q指向最小值结点，初始假定第一元素结点是最小值结点。
while（p->next!=null）
{if（p->next->data
}
pre->next=q->next；∥从链表上删除最小值结点
free（q）；∥释放最小值结点空间
}∥结束算法delete。
3、已知不带头结点的线性链表list，链表中结点构造为（data、link），其中data为数据域，link为指针域。请写一算法，将该链表按结点数据域的值的大小从小到大重新链接。要求链接过程中不得使用除该链表以外的任何链结点空间。
LinkedList LinkListSort(LinkedList list)
∥list是不带头结点的线性链表，链表结点构造为data和link两个域，data是数据域，link是指针域。本算法将该链表按结点数据域的值的大小，从小到大重新链接。
{p=list->link;∥p是工作指针，指向待排序的当前元素。
list->link=null;∥假定第一个元素有序，即链表中现只有一个结点。
while(p!=null)
{r=p->link;∥r是p的后继。
q=list;
if(q->data>p->data)∥处理待排序结点p比第一个元素结点小的情况。
{p->link=list;
list=p;∥链表指针指向最小元素。
}
else∥查找元素值最小的结点。
{while(q->link!=null&&q->link->data
p->link=q->link;∥将当前排序结点链入有序链表中。
q->link=p;}
p=r;∥p指向下个待排序结点。
}
}
4、L1、L2分别为两循环单链表的头结点指针，m,n分别为L1、L2表中数据结点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。
[题目分析]循环单链表L1和L2数据结点个数分别为m和n，将二者合成一个循环单链表时，需要将一个循环链表的结点（从第一元素结点到最后一个结点）插入到另一循环链表的第一元素结点前即可。题目要求“用最快速度将两表合并“，因此应找结点个数少的链表查其尾结点。
LinkedList Union(LinkedList L1,L2;int m,n)
∥L1和L2是两循环单链表的头结点的指针，m和n分别是L1和L2的长度。
∥本算法用最快速度将L1和L2合并成一个循环单链表。
{
if(m<0||n<0){
printf(“表长输入错误\n”)；exit(0);
}
if(m {∥若m if(m==0)return(L2);∥L1为空表。 else{ p=L1; while(p->next!=L1)p=p->next;∥查最后一个元素结点。 p->next=L2->next; ∥将L1循环单链表的元素结点插入到L2的第一元素结点前。 L2->next=L1->next; free(L1);∥释放无用头结点。 } }∥处理完m else∥下面处理L2长度小于等于L1的情况 {if(n==0)return(L1);∥L2为空表。 else{ p=L2; while(p->next!=L2)p=p->next;∥查最后元素结点。 p->next=L1->next; ∥将L2的元素结点插入到L1循环单链表的第一元素结点前。 L1->next=L2->next; free(L2);∥释放无用头结点。 }}∥算法结束。 5、设计算法：将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）。【北京理工大学2000四、2（4分）】 void DisCreat1(LinkedList A) ∥A是带头结点的单链表，链表中结点的数据类型为整型。本算法将A分解成两个单链表B和C，B中结点的数据小于零，C中结点的数据大于零。 {B=A; C=(LinkedList)malloc(sizeof(LNode));∥为C申请结点空间。 C->next=null∥C初始化为空表。 p=A->next;∥p为工作指针。 B->next=null;∥B表初始化。 while(p!=null) {r=p->next;∥暂存p的后继。 if(p->data<0)∥小于0的放入B表。 {p->next=B->next;B->next=p;}∥将小于0的结点链入B表。 else{p->next=C->next;C->next=p;} p=r;∥p指向新的待处理结点。 } }∥算法结束。 [算法讨论]因为本题并未要求链表中结点的数据值有序，所以算法中采取最简单方式：将新结点前插到头结点后面（即第一元素之前）。 6、请写一个算法将顺序存储结构的线性表（a 1...a n ）逆置为(a n ...a 1 )。【大连海事大学1996 八(６分)】 [题目分析]顺序存储结构的线性表的逆置，只需一个变量辅助空间。算法核心是选择循环控制变量的初值和终值。 void SeqInvert（ElemType a[]，int n） ∥a是具有n个元素用一维数组存储的线性表，本算法将其逆置。 {for（i=0；i<=（n-1）/2；i++） {t=a[i]；a[i]=a[n-1-i]；a[n-1-i]=t；} }∥算法结束 [算法讨论]算法中循环控制变量的初值和终值是关键。C中数组从下标0开始，第n 个元素的下标是n-1。因为首尾对称交换，所以控制变量的终值是线性表长度的一半。当n 为偶数，“一半”恰好是线性表长度的二分之一；若n是奇数，“一半”是小于n/2的最大整数，这时取大于1/2的最小整数的位置上的元素，恰是线性表中间位置的元素，不需要逆置。另外，由于pascal数组通常从下标1开始，所以，上下界处理上略有不同。这点请读者注意。 类似本题的另外叙述有： (1)设有一带头结点的单链表,编程将链表颠倒过来.要求不用另外的数组或结点完成.【南京航空航天大学1999八（10分）】 (2)设有一个带头结点的单向链表，数据项递减有序。写一算法，重新排列链表，使数据项递增有序，要求算法时间复杂度为O（n）。（注：用程序实现）【南京航空航天大学1997七（12分）】 本题要求将数据项递减有序的单链表重新排序，使数据项递增有序，要求算法复杂度为O （n）。虽没说要求将链表逆置，这只是叙述不同，本质上是将单链表逆置，现编写如下： LinkedList invert2（LinkedList la） ∥la是带头结点且数据项递减有序的单链表，本算法将其排列成数据项递增有序的单链表。{p=la->next；/*p为工作指针*/ la->next=null； while（p!=null） {r=p->next；/*暂存p的后继。*/ p->next=la->next；/*将p结点前插入头结点后。*/ la->next=p；p=r； } }∥结束算法 第3章栈和队列 一、填空题 1.对于队列只能在队尾插入和队首删除元素。 2.栈是_操作受限__的线性表，其运算遵循___后进先出的原则。 3、对于栈只能在栈顶插入和删除元素；最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。 4.循环队列的引入，目的是为了克服__假溢出时大量移动数据元素_，区分循环队列的满与空，只有两种方法，它们是___牺牲一个存储单元__和__设标记__。 5.在具有n个单元的循环队列中，队满时共有n-1个元素。 6.向栈中压入元素的操作是先移动栈顶指针，后存入元素。 7.从循环队列中删除一个元素时，其操作是先移动队首指针，后取出元素。 8、循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列的元素个数是_（rear-front+m）%m；_____。 9．设循环队列存放在向量sq.data[0:M]中，则队头指针sq.front在循环意义下的出队操作可表示为__sq.front=(sq.front+1)%(M+1)；return(sq.data(sq.front))；，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为 _(sq.rear+1)%(M+1)==sq.front； 10．对顺序栈作操作运算时，进栈应先判别栈是否_满_，出栈时应先判别栈是否_空_； 11、假设为循环队列分配的向量空间为Q[20]（下标从0开始），若队列的长度和队头指针值分别为13和17，则当前队尾指针的值为10。 二、判断正误（判断下列概念的正确性，并作出简要的说明。）（每小题1分，共10分）（×）1.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 （×）2.在表结构中最常用的是线性表，栈和队列不太常用。 （√）3.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）4.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（×）5.队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 （√）6.循环队列也存在空间溢出问题。 （√）7栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。 （√）8、栈和队列都是限制存取点的线性结构 （×）9.队列和栈都是运算受限的线性表，只允许在表的两端进行运算 （×）10.通常使用队列来处理函数或过程的调用。 （√）11.栈与队列是一种特殊操作的线性表。 （√）12.栈和队列都是限制存取点的线性结构。 （×）13.循环队列通常用指针来实现队列的头尾相接 三、单项选择题（每小题1分，共20分） 1.栈中元素的进出原则是（B） Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出 2.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（C） Ａ．iＢ．n=iＣ．n-i+1Ｄ．不确定 3.判定一个栈ST（最多元素为m0）为空的条件是（B） Ａ．ST->top<>0Ｂ．ST->top=0Ｃ．ST->top<>m0Ｄ．ST->top=m0 4.判定一个队列QU（最多元素为m）为满队列的条件是（A） Ａ．QU->rear－QU->front==mＢ．QU->rear－QU->front－1==m Ｃ．QU->front==QU->rearＤ．QU->front==QU->rear+1 5．数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为（D） （Ａ）r－f;（Ｂ）（n＋f－r）%n;（Ｃ）n＋r－f;（Ｄ）（n＋r－f）%n 6．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为(B)。 A.1和5 B.2和4 C.4和2 D. 5和1 7.栈和队列的共同点是（C）。 A.都是先进先出 B.都是先进后 出 C.只允许在端点处插入和删除元素 D.没有共同点 8．栈和队都是（C） A．顺序存储的线性结构 B.链式存储的非线性结构 C.限制存取点的线性结构 D.限制存取点的非线性结构 9、栈与一般线性表的区别在于（B）。 A、数据元素的类型不同 B、运算是否受限制 C、数据元素的个数不同 D、逻辑结构不同 10、有六个元素6，5，4，3，2，1的顺序进栈，下列哪一个不是合法的出栈序列？（C） A.543612 B.453126 C.346521 D.234156 11.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（B）。 A.不确定 B. n-i+1 C.i D.n-i 12.若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（D）。 A.i-j-1 B.i-j C.j-i+1 D.不确定的 13.设栈的输入序列是1，2，3，4,则（D）不可能是其出栈序列。 A.1，2，4，3， B.2，1，3，4， C.1，4，3，2， D.4，3，1，2， E.3，2，1，4， 14.设一个栈的输入序列是1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（D）。 A.51234 B.45132 C.43125 D.3 2154 15.循环队列存储在数组A[0..m]中，则入队时的操作为（D）。 A.rear=rear+1 B.rear=(rear+1)mod(m-1) C.rear=(rear+1)mod m D.rear=(rear+1)mod(m+1) 16.假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（A）。 A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m 17.栈在（D）中应用。 A.递归调用 B.子程序调用 C.表达式求值 D.以上三种 18.用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时(D)。 A．仅修改队头指针 B.仅修改队尾指针 C.队头、队尾指针都要修改 D.队头,队尾指针都可能要修改 19.设计一个判别表达式中左，右括号是否配对出现的算法，采用（D）数据结构最佳。 A．线性表的顺序存储结构 B.队列 C.线性表的链式存储结构 D.栈 20、设顺序循环队列Ｑ［0：M-1］的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（D）。 A．R-F B．F-R C．(R-F+M)%M D．(F-R+M)%M 21、设用链表作为栈的存储结构，则退栈操作（B） A．必须判别栈是否满B．必须判别栈是否空 C．判别栈元素的类型D．对栈不作任何操作 四、简答题（每小题4分，共20分） 1.说明线性表、栈与队的异同点。 答：相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。 不同点：①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。 ②用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。 2、顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？ 答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。采用循环队列是解决假溢出的途径。另外，解决队满队空的办法有三：设置一个布尔变量以区别队满还是队空；浪费一个元素的空间，用于区别队满还是队空。使用一个计数器记录队列中元素个数（即队列长度）。 我们常采用法②，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。 判断循环队列队空标志是：f=rear队满标志是：f=(r+1)%N 五、算法设计 1、设计一个算法，判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的单循环链表中，每个结点有两个域：ch和link，其中ch域为字符类型。 表达式中的括号有以下三对：‘（’、‘）’、‘[’、‘]’、‘{’、‘}’，使用栈，当为左括号时入栈，右括号时，若栈顶是其对应的左括号，则退栈，若不是其对应的左括号，则结论为括号不配对。当表达式结束，若栈为空，则结论表达式括号配对，否则，结论表达式括号不配对。 int Match(LinkedList la) //算术表达式存储在以la为头结点的单循环链表中，本算法判断括号是否正确配对 {char s[];//s为字符栈，容量足够大 p=la->link;//p为工作指针，指向待处理结点 StackInit(s);//初始化栈s while(p!=la)//循环到头结点为止 {switch(p->ch) {case‘(’:push(s,p->ch);break; case‘)’:if(StackEmpty(s)||StackGetTop(s)!=‘(’) {printf(“括号不配对\n”);return(0);}else pop(s);break; case‘[’:push(s,p->ch);break; case‘]’:if(StackEmpty(s)||StackGetTop(s)!=‘[’) {printf(“括号不配对\n”);return(0);}else pop(s);break; case‘{’:push(s,p->ch);break; case‘}’:if(StackEmpty(s)||StackGetTop(s)!=‘{’) {printf(“括号不配对\n”);return(0);}else pop(s);break; }p=p->link;后移指针 }//while if(StackEmpty(s)){printf(“括号配对\n”);return(1);} else{printf(“括号不配对\n”);return(0);} }//算法match结束 [算法讨论]算法中对非括号的字符未加讨论。遇到右括号时，若栈空或栈顶元素不是其对应的左圆（方、花）括号，则结论括号不配对，退出运行。最后，若栈不空，仍结论括号不配对。 2、请利用两个栈S1和S2来模拟一个队列。已知栈的三个运算定义如下：PUSH(ST,x):元素x入ST栈；POP(ST,x)：ST栈顶元素出栈，赋给变量x；Sempty(ST)：判ST栈是否为空。那么如何利用栈的运算来实现该队列的三个运算：enqueue:插入一个元素入队列；dequeue:删除一个元素出队列；queue_empty：判队列为空。 栈的特点是后进先出，队列的特点是先进先出。所以，用两个栈s1和s2模拟一个队列时，s1作输入栈，逐个元素压栈，以此模拟队列元素的入队。当需要出队时，将栈s1退栈并逐个压入栈s2中，s1中最先入栈的元素，在s2中处于栈顶。s2退栈，相当于队列的出队，实现了先进先出。显然，只有栈s2为空且s1也为空，才算是队列空。 (1)int enqueue(stack s1,elemtp x) //s1是容量为n的栈，栈中元素类型是elemtp。本算法将x入栈，若入栈成功返回1，否则返回0。 {if(top1==n&&!Sempty(s2))//top1是栈s1的栈顶指针，是全局变量。 {printf(“栈满”);return(0);}//s1满s2非空,这时s1不能再入栈。 if(top1==n&&Sempty(s2))//若s2为空，先将s1退栈,元素再压栈到s2。 {while(!Sempty(s1)){POP(s1,x);PUSH(s2,x);} PUSH(s1,x);return(1);//x入栈，实现了队列元素的入队。 } (2)void dequeue(stack s2,s1) //s2是输出栈，本算法将s2栈顶元素退栈，实现队列元素的出队。 {if(!Sempty(s2))//栈s2不空，则直接出队。 {POP(s2,x);printf(“出队元素为”,x);} else//处理s2空栈。 if(Sempty(s1)){printf(“队列空”);exit(0);}//若输入栈也为空，则判定队空。 else//先将栈s1倒入s2中，再作出队操作。 {while(!Sempty(s1)){POP(s1,x);PUSH(s2,x);} POP(s2,x);//s2退栈相当队列出队。 printf(“出队元素”，x); } }//结束算法dequue。 (3)int queue_empty() //本算法判用栈s1和s2模拟的队列是否为空。 {if(Sempty(s1)&&Sempty(s2))return(1);//队列空。 else return(0);//队列不 空。 } 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，请写出相应的入队列和出队列算法。 （1）void EnQueue(LinkedList rear,ElemType x) //rear是带头结点的循环链队列的尾指针，本算法将元素x插入到队尾。 {s=(LinkedList)malloc(sizeof(LNode));//申请结点空间 s->data=x;s->next=rear->next;//将s结点链入队尾 rear->next=s;rear=s;//rear指向新队尾 } （2）void DeQueue(LinkedList rear) //rear是带头结点的循环链队列的尾指针，本算法执行出队操作，操作成功输出队头元素；否则给出出错信息。 {if(rear->next==rear){printf(“队空\n”);exit(0);} s=rear->next->next;//s指向队头元素， rear->next->next=s->next;//队头元素出队。 printf(“出队元素是”，s->data); if(s==rear)rear=rear->next;//空队列 free(s); } 4、已知求两个正整数m与n的最大公因子的过程用自然语言可以表述为反复执行如下动作： 第一步：若n等于零，则返回m；第二步：若m小于n，则m与n相互交换；否则，保存m，然后将n送m，将保存的m除以n的余数送n。写出求解该递归函数的非递归算法。 int gcd(int m,n) //求正整数m和n的最大公因子的递归算法 {if(m if(n==0)return(m);else return(gcd(n,m%n)); }//算法结束 使用栈，消除递归的非递归算法如下： int gcd(int m,n) {int s[max][2];//s是栈，容量max足够大 top=1;s[top][0]=m;s[top][1]=n; while(s[top][1]!=0) if(s[top][0] {t=s[top][0];s[top][0]=s[top][1];s[top][1]=t;} else{t=s[top][0]%s[top][1];top++;s[top][0]=s[top-1][1]; s[top][1]=t;} return(s[top][0]); }//算法结束 由于是尾递归，可以不使用栈，其非递归算法如下 int gcd(int m,n) //求正整数m和n的最大公因子 {if(m while(n!=0){t=m;m=n;n=t%n;} return(m); }//算法结束 第3章栈和队列 一、选择题 1.栈结构通常采用的两种存储结构是（A ）。 A、顺序存储结构和链表存储结构 B、散列和索引方式 C、链表存储结构和数组 D、线性链表结构和非线性存储结构 2.设栈ST 用顺序存储结构表示，则栈ST 为空的条件是（ B ） A、ST.top-ST.base<>0 B、ST.top-ST.base==0 C、ST.top-ST.base<>n D、ST.top-ST.base==n 3.向一个栈顶指针为HS 的链栈中插入一个s 结点时，则执行（ C ） A、HS->next=s; B、s->next=HS->next；HS->next=s; C、s->next=HS；HS=s; D、s->next=HS；HS=HS->next; 4.从一个栈顶指针为HS 的链栈中删除一个结点，用x 保存被删除结点的值，则执行（ C） A 、x=HS；HS=HS->next; B 、HS=HS->next；x=HS->data; C 、x=HS->data；HS=HS->next; D 、s->next=Hs；Hs=HS->next; 5.表达式a*(b+c)-d 的后缀表达式为（ B ） A、abcdd+- B、abc+*d- C、abc*+d- D、-+*abcd 6.中缀表达式A-（B+C/D）*E 的后缀形式是（ D ） A、AB-C+D/E* B、ABC+D/E* C、ABCD/E*+- D、ABCD/+E*- 7.一个队列的入列序列是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 8.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为空的条件是（） A、Q.rear-Q.front==n B、Q.rear-Q.front-1==n C、Q.front==Q.rear D、Q.front==Q.rear+1 9.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为满的条件是（） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 10.若在一个大小为6 的数组上实现循环队列，且当前rear 和front 的值分别为0 和3，当从 队列中删除一个元素，再加入两个元素后，rear 和front 的值分别为（） A、1，5 B、2, 4 C、4，2 D、5，1 11.用单链表表示的链式队列的队头在链表的（）位置 A、链头 B、链尾 C、链中 12.判定一个链队列Q（最多元素为n 个）为空的条件是（） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 13.在链队列Q 中，插入s 所指结点需顺序执行的指令是（） A 、Q.front->next=s；f=s; B 、Q.rear->next=s；Q.rear=s; 实验三栈和队列的应用 1、实验目的 （1）熟练掌握栈和队列的结构以及这两种数据结构的特点、栈与队列的基本操作。 （2）能够在两种存储结构上实现栈的基本运算，特别注意栈满和栈空的判断条件及描述方法； （3）熟练掌握链队列和循环队列的基本运算，并特别注意队列满和队列空的判断条件和描述方法； （4）掌握栈和队列的应用； 2、实验内容 1）栈和队列基本操作实现 （1）栈的基本操作：采用顺序存储或链式存储结构（数据类型自定义），实现初始化栈、判栈是否为空、入栈、出栈、读取栈顶元素等基本操作，栈的存储结构自定义。 （2）队列的基本操作：实现循环队列或链队列的初始化、入队列、出队列、求队列中元素个数、判队列空等操作，队列的存储结构自定义。 2）栈和队列的应用 （1）利用栈的基本操作将一个十进制的正整数转换成二进制数据，并将其转换结果输出。 提示：利用栈的基本操作实现将任意一个十进制整数转化为R进制整数算法为： 十进制整数X和R作为形参 初始化栈 只要Ｘ不为0重复做下列动作 将x%R入栈 X=X/R 只要栈不为空重复做下列动作 栈顶出栈 输出栈顶元素 (2) 利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“Right”，否则输出“Wrong”。 (3) 假设循环队列中只设rear（队尾）和quelen（元素个数据）来分别表示队尾元素的位置和队中元素的个数，写出相应的入队和出队程序。 （4）选作题：编写程序实现对一个输入表达式的括号配对。 3、实验步骤 （1）理解栈的基本工作原理； （2）仔细分析实验内容，给出其算法和流程图； （3）用C语言实现该算法； （4）给出测试数据，并分析其结果； （5）在实验报告册上写出实验过程。 4、实验帮助 算法为： 1) 定义栈的顺序存取结构 2) 分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等） 3) 定义一个函数用来实现上面问题： 十进制整数X和R作为形参 初始化栈 只要X不为0重复做下列动作 将X % R入栈 X=X/R 只要栈不为空重复做下列动作 栈顶出栈 输出栈顶元素 5、算法描述 （1））初始化栈S (创建一个空栈S) void initstack(sqstack *S) { S->base=(ElemType *) malloc(INITSIZE*sizeof(ElemType)); if(!S->base) exit (-1); S->top=0; /*空栈标志*/ S->stacksize = INITSIZE; } (2) 获取栈顶元素 int gettop(sqstack S,ElemType *e) //顺序钱 { if ( S.top==0 ) /* 栈空 */ 实验编号：3四川师大《数据结构》实验报告2016年10月29日 实验三栈和队列及其应用_ 一．实验目的及要求 （1）掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们； （2）本实验训练的要点是“栈”的观点及其典型用法； （3）掌握问题求解的状态表示及其递归算法，以及由递归程序到非递归程序的转化方法。 二．实验内容 （1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）； （2）应用栈的基本操作，实现数制转换（任意进制）； （3）编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队列、出队列）； （4）利用栈实现任一个表达式中的语法检查（括号的匹配）。 （5）利用栈实现表达式的求值。 注：（1）～（3）必做，（4）～（5）选做。 三．主要仪器设备及软件 （1）PC机 （2）Dev C++ ,Visual C++, VS2010等 四．实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）； A.顺序储存： 代码部分： 栈" << endl; cout << " 2.出栈" << endl; cout << " 3.判栈空" << endl; cout << " 4.返回栈顶部数据" << endl; cout << " 5.栈长" << endl; cout << " 0.退出系统" << endl; cout << "你的选择是：" ; } 链式储存： 代码部分： 栈"< 数据结构：栈和队列 单选题： 1.在一个具有n个单元的顺序栈中，假定以地址低端作为栈底，以top作为栈顶指针，则当做退栈处 理时，top变化为_____。 A. top不变 B. top＝-n C. top＝top-1 D.top=top+1 2.向顺序栈中压入元素时，是_____。 A.先移动栈顶指针，后存入元素 B.先存入元素，后移动栈顶指针 3.在一个顺序存储的循环队列中，队首指针指向队首元素的_____。 A.前一个位置 B.后一个位置 C.队首元素位置 4.若进栈序列为1,2,3,4,进栈过程中可以出栈，则_____不可能是一个出栈序列。 A.3,4,2,1 B.2,4,3,1 C.1,4,3,2 D.3,2,1,4 5.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队 空的条件是_____。 A.front= =rear+1 B.front+1= =rear C.front= =rear D.front= =0 6.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队 满的条件是_____。 A.\rear % n= =front B.(rear-1) % n= =front C.(rear-1) % n= =rear D.(rear+1) % n= =front 7.向一个栈项指针为hs的链栈中插入一个*s结点时，则执行_____。 A.hs->next=s; B.s->next=hs->next; hs->next=s; C.s->next=hs；hs=s; D.s->next=hs; hs=hs->next; 8.在一个链队列中，假定front和rear分别为队首指针和队尾指针，则进行插入*s结点的操作时应执 行_____。 A.front->next=s; front=s; B.rear->next=s; rear=s; C.front=front->next; D.front=rear->next; 9.栈的特点是_______队的特点是______ A.先进先出 B.先进后出B|A 10.栈和队列的共同点是_______。 A.都是先进后出 B.都是先进先出 C.只允许在端点处插入和删除元素 D.没有共同点 11.一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是________。 A.edcba B.decba C.dceab D.abcde 12.若己知一个栈的进栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,…,pn,若p1=n,则pi(1 实验二堆栈和队列 实验目的： 1.熟悉栈这种特殊线性结构的特性； 2.熟练并掌握栈在顺序存储结构和链表存储结构下的基本运算； 3.熟悉队列这种特殊线性结构的特性； 3.熟练掌握队列在链表存储结构下的基本运算。 实验原理： 堆栈顺序存储结构下的基本算法； 堆栈链式存储结构下的基本算法； 队列顺序存储结构下的基本算法； 队列链式存储结构下的基本算法； 实验内容： 第一题链式堆栈设计。要求 （1）用链式堆栈设计实现堆栈，堆栈的操作集合要求包括：初始化StackInitiate（S）,非空否StackNotEmpty(S)，入栈StackiPush(S,x),出栈StackPop（S,d）,取栈顶数据元素StackTop(S,d); （2）设计一个主函数对链式堆栈进行测试。测试方法为：依次把数据元素1，2，3，4，5入栈，然后出栈并在屏幕上显示出栈的数据元素； （3）定义数据元素的数据类型为如下形式的结构体， Typedef struct { char taskName[10]; int taskNo; }DataType; 首先设计一个包含5个数据元素的测试数据，然后设计一个主函数对链式堆栈进行测试，测试方法为：依次吧5个数据元素入栈，然后出栈并在屏幕上显示出栈的数据元素。 第二题对顺序循环队列，常规的设计方法是使用対尾指针和对头指针，对尾指针用于指示当前的対尾位置下标，对头指针用于指示当前的対头位置下标。现要求： （1）设计一个使用对头指针和计数器的顺序循环队列抽象数据类型，其中操作包括：初始化，入队列，出队列，取对头元素和判断队列是否为空； （2）编写主函数进行测试。 程序代码： 第一题： （1）源程序"LinStack.h"如下： #define NULL 0 typedef struct snode { DataType data; struct snode *next; } LSNode; /*（1）初始化StackInitiate(LSNode ** head) */ void StackInitiate(LSNode ** head) /*初始化带头结点链式堆栈*/ 实验二栈、队列的实现及应用 实验课程名：数据结构与算法 专业班级：学号：： /*构造空顺序栈*/ int InitStack(SqStack *S) //InitStack() sub-function { S->base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if (!S->base) { printf("分配空间失败!\n"); return (ERROR); } S->top = S->base; S->stacksize = STACK_INIT_SIZE; printf("栈初始化成功！\n"); return (OK); } //InitStack() end /*取顺序栈顶元素*/ int GetTop(SqStack *S, SElemType *e) //GetTop() sub-function { if (S->top == S->base) { printf("栈为空!\n"); //if empty SqStack return (ERROR); } *e = *(S->top - 1); return (OK); } //GetTop() end /*将元素压入顺序栈*/ int Push(SqStack *S) //Push() sub-function { SElemType e; if (S->top - S->base>S->stacksize) { S->base = (SElemType *)realloc(S->base, (S->stacksize + STACKINCREMENT*sizeof(SElemType))); if (!S->base) { printf("存储空间分配失败!\n"); return (ERROR); } S->top = S->base + S->stacksize; S->stacksize += STACKINCREMENT; } fflush(stdin);//清除输入缓冲区，否则原来的输入会默认送给变量x 第三章栈和队列试题 一、单项选择题 1.栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 2.当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时， 首先应执行（）语句修改top指针。 A. top++; B. top--; C. top = 0; D. top; 3.若让元素1,2,3依次进栈，则出栈次序不可能出现（）种情况。 A. 3, 2, 1 B. 2, 1, 3 C. 3, 1, 2 D. 1, 3, 2 4.在一个顺序存储的循环队列中，队头指针指向队头元素的（）位置。 A. 前一个 B. 后一个 C. 当前 D. 后面 5.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。 A. n-2 B. n-1 C. n D. n+1 6.从一个顺序存储的循环队列中删除一个元素时，需要（）。 A. 队头指针加一 B. 队头指针减一 C. 取出队头指针所指的元素 D. 取出队尾指针所指的元素 7.假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front+1 == rear B. rear+1 == front C. front == 0 D. front == rear 8.假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front == rear B. front != NULL C. rear != NULL D. front == NULL 9.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一 个由指针s所指的结点，则应执行操作（）。 A. top->link = s; B.s->link = top->link; top->link = s; C. s->link = top; top = s; D. s->link = top; top = top->link; 10.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点， 并将被摘除结点的值保存到x中，则应执行操作（）。 A. x = top->data; top = top->link; B. top = top->link; x = top->data; C. x = top; top = top->link; D. x = top->data; 11.设循环队列的结构是 #define MaxSize 100 typedef int ElemType; 数据结构练习第三章栈和队列 一、选择题 1．栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2．向顺序栈中压入新元素时，应当（）。 A．先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针C．先后次序无关紧要 D．同时进行 3．允许对队列进行的操作有( )。 A. 对队列中的元素排序 B. 取出最近进队的元素 C. 在队头元素之前插入元素 D. 删除队头元素 4．用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 5．设用链表作为栈的存储结构则退栈操作（）。 A. 必须判别栈是否为满 B. 必须判别栈是否为空 C. 判别栈元素的类型 D.对栈不作任何判别 6．设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（）。 A.front->next=s；front=s； B. s->next=rear；rear=s； C. rear->next=s；rear=s； D. s->next=front；front=s； 7．设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。 A.top=top+1; B. top=top-1; C. top->next=top; D. top=top->next; 8．队列是一种（）的线性表。 A. 先进先出 B. 先进后出 C. 只能插入 D. 只能删除 9．设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。 A. n-i B. n-1-i C. n+l -i D.不能确定 10．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（）。 A. 5，3，4，6，1，2 B. 3，2，5，6，4，1 C. 3，1，2，5，4，6 D. 1，5，4，6，2，3 11．队列的删除操作是在（）进行。 A．队首 B．队尾 C．队前 D．队后 12．当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（）语句修改top指针。 A．top++; B．top=0; C．top--; D．top=N; 13．队列的插入操作是在（）进行。 南京信息工程大学实验（实习）报告 实验（实习）名称栈和队列日期2017.11.8 得分指导老师崔萌萌 系计算机系专业软件工程年级2016 班次(1) 姓名学号 一、实验目的 1、学习栈的顺序存储和实现，会进行栈的基本操作 2、掌握递归 3、学习队列的顺序存储、链式存储，会进行队列的基本操作 4、掌握循环队列的表示和基本操作 二、实验内容 1、用栈解决以下问题： （1）对于输入的任意一个非负十进制数，显示输出与其等值的八进制数，写出程序。（2）表达式求值，写出程序。 2、用递归写出以下程序： （1）求n！。 （2）汉诺塔程序，并截图显示3、4、5个盘子的移动步骤,写出移动6个盘子的移动次数。 3、编程实现：（1）创建队列，将asdfghjkl依次入队。（2）将队列asdfghjkl依次出队。 4、编程实现创建一个最多6个元素的循环队列、将ABCDEF依次入队，判断循环队列是否队满。 三、实验步骤 1.栈的使用 1.1 用栈实现进制的转换： 代码如下： #include printf("转换为%d进制： ",radix); while(n) { s.push(n%radix); n /= radix; } while(!s.empty()) { //非空 printf("%d",s.top()); s.pop(); } printf("\n"); return 0; } 运行结果如下： 2.2 求表达式的值 代码如下： #include 百度文库-让每个人平等地提升自我 实验二栈、队列的实现及应用 实验课程名：数据结构与算法 专业班级：_ 学号：__________ 姓名： _ 实验时间： ____ 实验地点：指导教师：冯珊__________ 一、实验目的 1掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。 2、掌握栈和队列的特点，即先进后出与先进先出的原则。 3、掌握栈和队列的基本操作实现方法。 /*顺序栈的存储类型*/ typedef struct 1 2 3 4 5远 兀 1 一 7U- 元 谴 段 囑 :> o 1 2 3 R * 元 元 栈 書 t 出 一 ^ 零 遐 次 :± 谨 虚 1 2 3 ^ 5 I B D 认戯握结IVl 匚on&ol eAp pli cation!\[>ebu g\Con 5 o-leApp li cation 1 .exe :1 刖人操作谊睪代码(05):2 : h E s 选 的 操 一 兀 一 b 一 丁 一 丁 栈 ? 遐 次 嘆 區 1 2 3 4 5 5 ^ 元 元 栈 S 退 、 灵 岀 祓 S I ■ i 9 I I I i 主 至 ..T' 一 兀 元 栈 ￡ 1 2 3 4 5 \Z 百度文库 -让每个人平等地提升自我 P入操隹选择代码（0-5>:4 派元素的是 ; 栈 化 出 取 示 艮 i元一一 选 的 操 元 -> 入 中 >c 1- 苴翻（05）: 5 栈 化 亍 1 2 元 元 Is 务一（2）:完成下列程序，该程序实现栈的链式存储结构，构建链栈（栈中的元素依次为China , Japan, France，India ，Australia ），依次进行进栈和出栈操作，判断栈空和栈满操作，返回栈顶元素操作。 要求生成链栈时，从键盘上读取数据元素。 （1）源代码：#i nclude<> #in clude<> #in clude<> # define OK 1 # define ERROR 0 typedef char DataType; /*链式栈的存储类型*/ typedef struct SNode 习题三栈和队列 一单项选择题 1. 在作进栈运算时,应先判别栈是否(① ),在作退栈运算时应先判别栈是否(② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③ )。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 2．若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为( )。 A 可能是2 B 一定是2 C 可能是1 D 一定是1 3. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） 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 4.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6, s5,s1,则栈的容量至少应该是（） A.2 B. 3 C. 5 D.6 5. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。 A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 6. 执行完下列语句段后，i值为：（） int f(int x) { return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1)); A．2 B. 4 C. 8 D. 无限递归 7. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。 A. 3,2,4,1,1；(*^(+*- B. 3,2,8；(*^- C. 3,2,4,2,2；(*^(- D. 3,2,8；(*^(- 8. 用链接方式存储的队列，在进行删除运算时（）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 9. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表 10．设C语言数组Data[m+1]作为循环队列SQ的存储空间， front为队头指针，rear为队尾指针，则执行出队操作的语句为（） A.front=front+1 B. front=（front+1）% m C.rear=(rear+1)%(m+1) D. front=(front+1)%(m+1) 11.循环队列的队满条件为 ( ) A. (sq.rear+1) % maxsize ==(sq.front+1) % maxsize; B. (sq.front+1) % maxsize ==sq.rear C. (sq.rear+1) % maxsize ==sq.front D.sq.rear ==sq.front 实验二栈和队列 一、实验目的 1. 掌握栈的顺序表示和实现 2. 掌握队列的链式表示和实现 二、实验内容 1. 编写一个程序实现顺序栈的各种基本运算。 2. 实现队列的链式表示和实现。 三、实验步骤 1. 初始化顺序栈 2. 插入元素 3. 删除栈顶元素 4. 取栈顶元素 5. 遍历顺序栈 6. 置空顺序栈 7. 初始化并建立链队列 8. 入链队列 9. 出链队列 10. 遍历链队列 四、实现提示 1. /*定义顺序栈的存储结构*/ typedef struct { ElemType stack[MAXNUM]; int top; }SqStack; /*初始化顺序栈函数*/ void InitStack(SqStack *p) {q=(SqStack*)malloc(sizeof(SqStack) /*申请空间*/) /*入栈函数*/ void Push(SqStack *p,ElemType x) {if(p->top 《数据结构》课程实验报告 实验名称栈和队列实验序号实验日期 姓名院系班级学号 专业指导教师成绩 教师评语 一、实验目的和要求 (1)理解栈和队列的特征以及它们之间的差异，知道在何时使用那种数据结构。 (2)重点掌握在顺序栈上和链栈上实现栈的基本运算算法，注意栈满和栈空的条件。 (3)重点掌握在顺序队上和链队上实现队列的基本运算算法，注意循环队队列满和队空的条件。 (4)灵活运用栈和队列这两种数据结构解决一些综合应用问题。 二、实验项目摘要 编写一个程序algo3-1.cpp，实现顺序栈的各种基本运算，并在此基础上设计一个主程序并完成如下功能：（1）初始化栈s； （2）判断栈s是否非空； （3）依次进栈元素a,b,c,d,e； （4）判断栈s是否非空； （5）输出栈长度； （6）输出从栈顶到栈底元素； （7）输出出栈序列； （8）判断栈s是否非空； （9）释放栈。 编写一个程序algo3-3.cpp，实现顺序环形队列的各种基本运算，并在此基础上设计一个主程序并完成如下功能： （1）初始化队列q； （2）判断队列q是否非空； （3）依次进队列a,b,c； （4）出队一个元素，输出该元素； （5）输出队列q的元素个数； （6）依次进队列元素d,e,f； （7）输出队列q的元素个数； （8）输出出队序列； （9）释放队列。 三、实验预习内容 栈的顺序存储结构及其基本运算实现（初始化栈，销毁栈，求栈的长度，判断栈是否为空，进栈，取栈顶元素，显示栈中元素） 队列的顺序存储结构及其基本运算实现（初始化队列，销毁队列，判断队列是否为空，入队列，出队列） 三、实验结果与分析 3-1 #define maxsize 100 #include 栈和队列综合实验报告 一、实验目的 （1）能够利用栈和队列的基本运算进行相关操作。 （2）进一步熟悉文件的应用 （3）加深队列和栈的数据结构理解，逐步培养解决实际问题的编程能力。 二、实验环境 装有Visual C＋＋的计算机。 本次实验共计4学时。 三、实验内容 以下两个实验任选一个。 1、迷宫求解 设计一个迷宫求解程序，要求如下： 以M × N表示长方阵表示迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 能任意设定的迷宫 （选作）如果有通路，列出所有通路 提示： 以一个二维数组来表示迷宫，0和1分别表示迷宫中的通路和障碍，如下图迷宫数据为：11 01 01 01 01 01 01 01 11 入口位置：1 1 出口位置：8 8 四、重要数据结构 typedef struct{ int j[100]; int top;栈顶指针，一直指向栈顶 }stack;//存放路径的栈 int s[4][2]={{0,0},{0,0},{0,0},{0,0}}; //用于存放最近的四步路径坐标的数组，是即使改变的，即走一步，便将之前的坐标向前移一步，将最早的一步坐标覆盖掉，新的一步放入数组末尾其实功能和队列一样。 其作用是用来判断是否产生了由于本程序算法产生的“田”字方格内的死循环而准备的，用于帮助跳出循环。 五、实现思路分析 if(a[m][n+1]==0&&k!=3){ n++; k=1; o=0; }else if(a[m+1][n]==0&&k!=4){ m++; k=2; o=0; }else if(a[m][n-1]==0&&k!=1){ n--; k=3; o=0; }else if(a[m-1][n]==0&&k!=2){ m--; k=4; o=0; }else{ o++;} if(o>=2){ k=0; }//向所在方格的四个方向探路，探路顺序为→↓←↑（顺时针），其中if判断条件内的&&k!=n和每个语句块中的对k赋值是为防止其走回头路进入死循环，而最后一个else{}内语句是为了防止进入死路时，不能走回头路而造成的死循环。 push(q,m,n);//没进行一次循环都会讲前进的路径入栈。 if (pushf(&s[0][0],m,n)==0){ k=3;}//用来判断是否产生了由于本程序探路算法产生的“田”字方格内的死循环而准备的，用于帮助跳出田字循环。同时会将路径存入用于下次判断 六、程序调试问题分析 最开始写完时是没有死路回头机制的，然后添加了两步内寻路不回头机制。 第二个是“田”字循环问题，解决方法是加入了一个记录最近四步用的数组和一个判断田字循环的函数pushf。 栈和队列 1 简述栈和线性表的区别。 2 简述栈和队列这两种数据结构的相同点和不同点。 3 如果进栈的元素序列为A，B，C，D，则可能得到的出栈序列有多少种？写出全部的可能序列。 4 如果进栈的元素序列为1，2，3，4，5，6，能否得到4，3，5，6，1，2和1，3，5，4，2，6的出栈序列？并说明为什么不能得到或如何得到。 5 写出下列程序段的运行结果（栈中的元素类型是char）： main( ) { SEQSTACK s,*p; char x, y; p = &s; initstack(p); x = ′c′; y = ′k′; push(p,x); push(p,′a′); push(p,y); x = pop(p); push(p,′t′); push(p,x); x = pop(p); push(p,′s′); while(!empty(p)) { y = pop(p); printf(″%c″,y);} printf(″%c＼n″,x); } 6 将一个非负十进制整数转换成二进制数，用非递归算法和递归算法来实现。 7 写一算法将一顺序栈中的元素依次取出，并打印元素值。 8 设单链表中存放着n个字符，试编一算法，判断该字符串是否有中心对称关系，例如xyzzyx，xyzyx都算是中心对称的字符串。 9 写出下列程序段的运行结果（队列中的元素类型是char）： main( ) { SEQQUEUE a, *q; char x, y; q = &a; x=′e′; y=′c′; initqueue(q); enqueue(q,′h′); enqueue(q,′r′); enqueue(q,y); x = dequeue(q); 数据结构实验报告 实验名称：栈和队列及其应用 班级：12级电气本2 学号：2012081227 姓名：赵雪磊 指导教师：梁海丽 日期：2013年9月23日 数学与信息技术学院 一、实验目的 1. 掌握栈和队列的概念。 2．掌握栈和队列的基本操作（插入、删除、取栈顶元素、出队、入队等）。 3．理解栈和队列的顺序、链式存储。 二、实验要求 利用顺序栈将任意一个给定的十进制数转换成二进制、八进制、十六进制数并输出。 三、算法描述 #include "stdafx.h" #include "iomanip.h" void D10to2_8_16(int i,char radix) { char m; if(i>=radix) D10to2_8_16(i/radix,radix); if((m=i%radix+'0')>0x39) m+=7; cout << m; } void main(void) { int nDec; cout << "请输入一个十进制正整数...\n" << "nDec="; cin >> nDec; cout << "转换为二进制是:"; D10to2_8_16(nDec,2); cout << endl; cout << "转换为八进制是:0"; D10to2_8_16(nDec,8); cout << endl; cout << "转换为十六进制是:0x"; D10to2_8_16(nDec,16); cout << endl; } 四、程序清单 #include 《数据结构》实验指导及报告书 2014 / 2015 学年第 1学期 姓名： 学号： 班级： 指导教师：徐江 计算机科学与工程学院 2014 实验二栈和队列 一、实验目的 1、掌握栈的结构特性及其入栈，出栈操作； 2、掌握队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作。 二、实验内容和要求 1、阅读下面程序，将函数Push和函数Pop补充完整。要求输入元素序列1 2 3 4 5 e，运行结果如下所示。 #include完整版数据结构习题集第3章栈和队列
实验三 栈和队列的应用
数据结构_实验三_栈和队列及其应用
数据结构：栈和队列学习资料
数据结构堆栈与队列实验报告
实验二_栈、队列地实现与应用
数据结构第三章栈和队列3习题
数据结构练习 第三章 栈和队列
数据结构栈和队列实验报告.doc
实验二栈队列的实现及应用
数据结构栈和队列习题及答案
数据结构栈和队列
数据结构栈和队列实验报告
栈和队列综合实验报告
《数据结构练习题》栈和队列
栈和队列及其应用实验报告
《数据结构》实验二 栈和队列
- 《数据结构》栈和队列实验报告
- JAVA数据结构复习栈和队列
- 数据结构第三章栈和队列3习题
- 《数据结构练习题》栈和队列
- 数据结构之线性表与栈和队列
- 数据结构栈和队列(参考代码)
- 数据结构实验三栈和队列的应用
- 数据结构栈和队列习题及答案
- 数据结构-栈和队列-实验
- 数据结构栈和队列实验报告
- 数据结构实验3栈和队列
- 数据结构栈和队列实验报告
- 数据结构堆栈与队列实验报告
- 第三章栈和队列习题_数据结构
- 数据结构详细讲解(栈和队列)
- 数据结构第3章栈和队列
- 数据结构 C语言版 第二版(严蔚敏) 第3章 栈和队列 答案
- 数据结构_实验三_栈和队列及其应用
- 《数据结构》习题集：第3章 栈和队列
- 数据结构_实验三_栈和队列及其应用