新書推薦：
《
十一年夏至
》
售價：NT$
347.0
《
如何打造成功的商业赛事
》
售價：NT$
407.0
《
万千教育学前·透视学前儿童的发展：解析幼儿教师常问的那些问题
》
售價：NT$
265.0
《
慈悲与玫瑰
》
售價：NT$
398.0
《
启蒙的辩证：哲学的片简（法兰克福学派哲学经典，批判理论重要文本）
》
售價：NT$
347.0
《
心跳重置
》
售價：NT$
269.0
《
云中记
》
售價：NT$
347.0
《
中国古代妇女生活（中国古代生活丛书）
》
售價：NT$
214.0
|
| 編輯推薦： |
|
各章中除给出本章练习题的参考答案外，还总结了本章的知识体系结构，并补充了大量的练习题并予以解析。附录中给出了几份近年来本科生、研究生数据结构考试试题及参考答案。书中列出了全部的练习题，因此自成一体，可以脱离主教材单独使用。
|
| 內容簡介： |
本书是《数据结构教程（第5版）》（李春葆等编著，清华大学出版社出版）的配套学习指导书。两书章节一一对应，内容包括绪论、线性表、栈和队列、串、递归、数组和广义表、树和二叉树、图、查找、内排序、外排序和文件。各章中除给出本章练习题的参考答案以外还总结了本章的知识体系结构，并补充了大量的练习题且予以解析，因此自成一体，可以脱离主教材单独使用。
本书适合高等院校计算机和相关专业的本科生及研究生使用。
|
| 目錄：
|
目录
第1章绪论
1.1本章知识体系
1.2教材中的练习题及参考答案
1.3补充练习题及参考答案
1.3.1单项选择题
1.3.2填空题
1.3.3判断题
1.3.4简答题
1.3.5算法设计及算法分析题
第2章线性表
2.1本章知识体系
2.2教材中的练习题及参考答案
2.3补充练习题及参考答案
2.3.1单项选择题
2.3.2填空题
2.3.3判断题
2.3.4简答题
2.3.5算法设计题
第3章栈和队列
3.1本章知识体系
3.2教材中的练习题及参考答案
3.3补充练习题及参考答案
3.3.1单项选择题
3.3.2填空题
3.3.3判断题
3.3.4简答题
3.3.5算法设计题
第4章串
4.1本章知识体系
4.2教材中的练习题及参考答案
4.3补充练习题及参考答案
4.3.1单项选择题
4.3.2填空题
4.3.3判断题
4.3.4简答题
4.3.5算法设计题
第5章递归
5.1本章知识体系
5.2教材中的练习题及参考答案
5.3补充练习题及参考答案
5.3.1单项选择题
5.3.2填空题
5.3.3判断题
5.3.4简答题
5.3.5算法设计题
第6章数组和广义表
6.1本章知识体系
6.2教材中的练习题及参考答案
6.3补充练习题及参考答案
6.3.1单项选择题
6.3.2填空题
6.3.3判断题
6.3.4简答题
6.3.5算法设计题
第7章树和二叉树
7.1本章知识体系
7.2教材中的练习题及参考答案
7.3补充练习题及参考答案
7.3.1单项选择题
7.3.2填空题
7.3.3判断题
7.3.4简答题
7.3.5算法设计题
第8章图
8.1本章知识体系
8.2教材中的练习题及参考答案
8.3补充练习题及参考答案
8.3.1单项选择题
8.3.2填空题
8.3.3判断题
8.3.4简答题
8.3.5算法设计题
第9章查找
9.1本章知识体系
9.2教材中的练习题及参考答案
9.3补充练习题及参考答案
9.3.1单项选择题
9.3.2填空题
9.3.3判断题
9.3.4简答题
9.3.5算法设计题
第10章内排序
10.1本章知识体系
10.2教材中的练习题及参考答案
10.3补充练习题及参考答案
10.3.1单项选择题
10.3.2填空题
10.3.3判断题
10.3.4简答题
10.3.5算法设计题
第11章外排序
11.1本章知识体系
11.2教材中的练习题及参考答案
11.3补充练习题及参考答案
11.3.1单项选择题
11.3.2填空题
11.3.3判断题
11.3.4简答题
第12章文件
12.1本章知识体系
12.2教材中的练习题及参考答案
12.3补充练习题及参考答案
12.3.1单项选择题
12.3.2填空题
12.3.3判断题
12.3.4简答题
附录A两份本科生期末考试试题
本科生期末考试试题1
本科生期末考试试题1参考答案
本科生期末考试试题2
本科生期末考试试题2参考答案
附录B两份研究生入学考试单考数据结构
部分试题
研究生入学考试单考数据结构部分试题1
研究生入学考试单考数据结构部分试题1参考答案
研究生入学考试单考数据结构部分试题2
研究生入学考试单考数据结构部分试题2参考答案
附录C两份全国计算机学科专业考研题数据结构
部分试题
2014年试题
2014年试题参考答案
2015年试题
2015年试题参考答案
|
| 內容試閱：
|
第3章栈和队列
3.1本章知识体系1. 知识结构图
本章的知识结构如图3.1所示。
图3.1第3章知识结构图
2. 基本知识点1 栈、队列和线性表的异同。2 顺序栈的基本运算算法设计。3 链栈的基本运算算法设计。4 顺序队的基本运算算法设计。5 环形队列和非环形队列的特点。6 链队的基本运算算法设计。7 利用栈队列求解复杂的应用问题。3. 要点归纳1 栈和队列的共同点是它们的数据元素都呈线性关系，且只允许在端点处插入和删除元素。2 栈是一种后进先出的数据结构，只能在同一端进行元素的插入和删除。3 栈可以采用顺序栈和链栈两类存储结构。4 n个不同元素的进栈顺序和出栈顺序不一定相同。5 在顺序栈中通常用栈顶指针指向当前栈顶的元素。6 在顺序栈中用数组data［0..MaxSize-1］存放栈中元素，只能将一端作为栈底，另一端作为栈顶，通常的做法是将data［0］端作为栈底，data［MaxSize-1］端作为栈顶。用户也可以将data［MaxSize-1］端作为栈底，data［0］端作为栈顶，但不能将中间位置作为栈底或者栈顶。7 初始时栈顶指针top设置为-1，栈空的条件为top=-1，栈满的条件为top=MaxSize-1，元素x的进栈操作是top; data［top］=x，出栈操作是x=data［top］; top--。这是经典做法，但不是唯一的方法，如果初始时top设置为0，可以设置栈空的条件为top=0，栈满的条件为top=MaxSize，元素x的进栈操作是data［top］=x; top，出栈操作是top--; x=data［top］。8 在顺序栈或链栈中，进栈和出栈操作不涉及栈中元素的移动。9 在链栈中，由于每个结点是单独分配的，通常不考虑上溢出问题。10 无论是顺序栈还是链栈，进栈和出栈运算的时间复杂度均为O1。11 队列是一种先进先出的数据结构，只能从一端插入元素，从另一端删除元素。12 队列可以采用顺序队和链队两类存储结构。13 n个元素进队的顺序和出队顺序总是一致的。14 在顺序队中的元素个数可以由队头指针和队尾指针计算出来。15 环形队列也是一种顺序队，是通过逻辑方法使其首尾相连的，解决非环形队列的假溢出现象。16 在环形队列中，队头指针f指向队头元素的前一个位置，队尾指针r指向队尾元素，这是一种经典做法，但不是唯一的方法，也可以让队头指针f指向队头元素。17 无论是顺序队还是链队，进队和出队运算的时间复杂度均为O1。18 在实际应用中，一般栈和队列都是用来存放临时数据的，如果先保存的元素先处理，应该采用队列； 如果后保存的元素先处理，应该采用栈。
3.2教材中的练习题及参考答案1. 有5个元素，其进栈次序为A、B、C、D、E，在各种可能的出栈次序中以元素C、D最先出栈即C第一个且D第二个出栈的次序有哪几个？答： 要使C第一个且D第二个出栈，应是A进栈，B进栈，C进栈，C出栈，D进栈，D出栈，之后可以有以下几种情况：1 B出栈，A出栈，E进栈，E出栈，输出序列为CDBAE；2 B出栈，E进栈，E出栈，A出栈，输出序列为CDBEA；3 E进栈，E出栈，B出栈，A出栈，输出序列为CDEBA。所以可能的次序有CDBAE、CDBEA、CDEBA。2. 在一个算法中需要建立多个栈假设3个栈或以上时可以选用以下3种方案之一，试问这些方案相比各有什么优缺点？1 分别用多个顺序存储空间建立多个独立的顺序栈。2 多个栈共享一个顺序存储空间。3 分别建立多个独立的链栈。答： 1 优点是每个栈仅用一个顺序存储空间时操作简单； 缺点是分配空间小了容易产生溢出，分配空间大了容易造成浪费，各栈不能共享空间。2 优点是多个栈仅用一个顺序存储空间，充分利用了存储空间，只有在整个存储空间都用完时才会产生溢出； 缺点是当一个栈满时要向左、右查询有无空闲单元，如果有，则要移动元素和修改相关的栈底和栈顶指针。当接近栈满时要查询空闲单元、移动元素和修改栈底、栈顶指针，这一过程计算复杂且十分耗时。3 优点是多个链栈一般不考虑栈的溢出； 缺点是栈中元素要以指针相链接，比顺序存储多占用了存储空间。3. 在以下几种存储结构中哪个最适合用作链栈？1 带头结点的单链表。2 不带头结点的循环单链表。3 带头结点的双链表。答： 栈中元素之间的逻辑关系属线性关系，可以采用单链表、循环单链表和双链表之一来存储，而栈的主要运算是进栈和出栈。当采用1时，前端作为栈顶，进栈和出栈运算的时间复杂度为O1。当采用2时，前端作为栈顶，当进栈和出栈时首结点都发生变化，还需要找到尾结点，通过修改其next域使其变为循环单链表，算法的时间复杂度为On。当采用3时，前端作为栈顶，进栈和出栈运算的时间复杂度为O1。但单链表和双链表相比，其存储密度更高，所以本题中最适合用作链栈的是带头结点的单链表。4. 简述以下算法的功能假设ElemType为int类型。
void funElemType a［］,int n
{int i;ElemType e;
SqStack *st1,*st2;
InitStackst1;
InitStackst2;
for i=0;irear-qu-front MaxSize%MaxSize;
if jn return false;
for j=1;j=''0'' && a=''a'' && a
#include
#define MAXQNode 10队列的个数
typedef struct node
{int data;
struct node *next;
} QNode;
void InsertQNode *quh［］,QNode *qut［］,int x将x插入到相应队列中
{QNode *s;
s=QNode *mallocsizeofQNode;创建一个结点s
s-data=x; s-next=NULL;
if quh［x］==NULLx号队列为空队时
{quh［x］=s;
qut［x］=s;
}
elsex号队列不空队时
{qut［x］-next=s;将s结点链到qut［x］所指的结点之后
qut［x］=s;让qut［x］仍指向尾结点
}
}
void CreateQNode *quh［］,QNode *qut［］根据用户的输入创建队列
{int n,x,i;
printf"n：";
scanf"%d",&n;
for i=0;i10;
Insertquh,qut,x;
}
}
void DestroyListQNode *&head释放单链表
{QNode *pre=head,*p=pre-next;
while p!=NULL
{
freepre;
pre=p; p=p-next;
}
freepre;
}
void DispListQNode *head输出单链表的所有结点值
{printf"＼n输出所有元素：";
while head!=NULL
{printf"%d ",head-data;
head=head-next;
}
printf"＼n";
}
QNode *LinkQNode *quh［］,QNode *qut［］将非空队列链接起来并输出
{QNode *head=NULL,*tail;总链表的首结点指针和尾结点指针
int i;
for i=0;inext=quh［i］;
tail=qut［i］;
}
}
tail-next=NULL;
return head;
}
int main
{int i;
QNode *head;
QNode *quh［MAXQNode］,*qut［MAXQNode］;各队列的队头quh和队尾指针qut
for i=0;itop== MaxSize2B. st-top!= MaxSize2C. st-top!=MaxSize-1D. st-top==MaxSize-1答： 顺序栈总是以一端0或者MaxSize-1端作为栈底，栈空是指栈不存在元素，合适的栈空条件为st-top== MaxSize-1。本题的答案为D。12. 若一个栈用数组data［1..n］存储，初始栈顶指针top为n 1，则以下元素x进栈的操作正确的是。A. top;data［top］=x;B. data［top］=x;top;C. top--;data［top］=x;D. data［top］=x;top--;答： 初始栈顶指针top为n 1，说明是将data［n］端作为栈底、data［1］端作为栈顶，在进栈时top应递减，由于不存在data［n 1］的元素，所以在进栈时应先将top递减，再将x放在top处。本题的答案为C。13. 若一个栈用数组data［1..n］存储，初始栈顶指针top为n，则以下元素x进栈的操作正确的是。A. top;data［top］=x;B. data［top］=x;top;C. top--;data［top］=x;D. data［top］=x; top--;答： 初始栈顶指针top为n，说明是将data［n］端作为栈底、data［1］端作为栈顶，在进栈时top应递减，由于存在data［n］的元素，所以在进栈时应先将x放在top处，再将top递减。本题的答案为D。14. 若一个栈用数组data［1..n］存储，初始栈顶指针top为0，则以下元素x进栈的操作正确的是。A. top;data［top］=x;B. data［top］=x;top;C. top--;data［top］=x;D. data［top］=x; top--;答： 初始栈顶指针top为0，说明是将data［1］端作为栈底、data［n］端作为栈顶，在进栈时top应递增，由于不存在data［0］的元素，所以在进栈时应先将top递增，再将x放在top处。本题的答案为A。
15. 若一个栈用数组data［1..n］存储，初始栈顶指针top为1，则以下元素x进栈的操作正确的是。A. top;data［top］=x;B. data［top］=x;top;C. top--;data［top］=x;D. data［top］=x; top--;答： 初始栈顶指针top为1，说明是将data［1］端作为栈底、data［n］端作为栈底，在进栈时top应递增，由于存在data［1］的元素，所以在进栈时应先将x放在top处，再将top递增。本题的答案为B。
说明： 从12~15小题可以看出，顺序栈的设计并不是唯一的，只要能满足栈的操作特点又能充分利用存储空间就是一种合适的设计。
16. 以下各链表均不带有头结点，其中最不适合用作链栈的链表是。A. 只有表头指针没有表尾指针的循环双链表B. 只有表尾指针没有表头指针的循环双链表C. 只有表尾指针没有表头指针的循环单链表D. 只有表头指针没有表尾指针的循环单链表答： 只有表头指针没有表尾指针的循环单链表不带头结点在进栈和出栈操作后需要保持循环单链表形式不变，实现进栈和出栈运算的时间复杂度均为On。本题的答案为D。17. 由两个栈共享一个数组空间的好处是。A. 减少存取时间，降低上溢出发生的几率B. 节省存储空间，降低上溢出发生的几率C. 减少存取时间，降低下溢出发生的几率D. 节省存储空间，降低下溢出发生的几率答： B。18. 表达式a*b c-d的后缀表达式是。A. abcd* -B. abc *d-C. abc* d-D. - *abcd答： 选项A对应的中缀表达式为a-b c*d，选项B对应的中缀表达式为a*b c-d，选项C对应的中缀表达式为a b*c-d，选项D不是合法的后缀表达式。本题的答案为B。19. 在将算术表达式1 68-5*3转换成后缀表达式的过程中，当扫描到5时运算符栈从栈顶到栈底次序为。A. - B. - C. D. -答： 算术表达式1 68-5*3的后缀表达式是1 6 8 5 - 3 *，当扫描到5时，前面的运算符 、、和-均在栈中，运算符栈中从栈顶到栈底次序为- 。本题的答案为B。20. 在利用栈求表达式的值时，设立运算数栈OPND，设OPND只有两个存储单元，在求下列表达式中不发生上溢出的是。A. a-b*c dB. a-b*c d
C. a-b*c dD. a-b*c d答： 选项A对应的后缀表达式为a b c d * -，在求值时OPND的最少存储单元为4。选项B对应的后缀表达式为a b - c * d，在求值时OPND的最少存储单元为2。选项C对应的后缀表达式为a b c * - d，在求值时OPND的最少存储单元为3。选项D对应的后缀表达式为a b - c d *，在求值时OPND的最少存储单元为3。本题的答案为B。21. 经过以下队列运算后QueueEmptyqu的值是。
InitQueuequ;enQueuequ，a;enQueuequ，b;deQueuequ，x;deQueuequ，y;
A. aB. bC. trueD. false答： C。22. 环形队列。A. 不会产生下溢出B. 不会产生上溢出C. 不会产生假溢出D. 以上都不对答： C。23. 在环形队列中元素的排列顺序。A. 由元素进队的先后顺序确定B. 与元素值的大小有关C. 与队头和队尾指针的取值有关D. 与队中数组大小有关答： A。24. 某环形队列的元素类型为char，队头指针front指向队头元素的前一个位置，队尾指针rear指向队尾元素，如图3.3所示，则队中元素为。A. abcd123456B. abcd123456cC. dfgbcaD. cdfgbcab
图3.3一个环形队列
答： front=12，队头元素应为下标13的元素，rear=2，队尾元素应为下标2的元素，队中元素从队头到队尾是data［13..2］，本题的答案为C。25. 已知环形队列存储在一维数组A［0..n-1］中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列空，且要求第一个进入队列的元素存储在A［0］处，则初始时front和rear的值分别是。A. 0，0B. 0，n-1C. n-1，0D. n-1，n-1答： 在环形队列中，进队操作是队尾指针rear循环加1，再在该处放置进队的元素，这里要求第一个进队元素存储在A［0］处，则rear应为n-1，因为这样rear 1%n=0。而队头指向队头元素，此时队头位置为0，所以front的初值为0。本题的答案为B。26. 若某环形队列有队头指针front和队尾指针rear，在队不满时进队操作仅会改变。A. frontB. rearC. front和rearD. 以上都不对答： B。27. 设环形队列中数组的下标是0~N-1，其队头指针为f指向队头元素的前一个位置、队尾指针为r指向队尾元素，则其元素个数为。A. r-fB. r-f-1C. r-f％N 1D. r-f N％N答： 对于非环形队列，每次是先移动指针，再存取元素，其中的元素个数=r-f，但由于是环形队列，r可能小于f，为此求环形队列中元素个数的公式改为r-f N％N。本题的答案为D。28. 设环形队列的存储空间为a［0..20］，且当前队头指针f指向队首元素的前一个位置和队尾指针r指向队尾元素的值分别为8和3，则该队列中的元素个数为。A. 5B. 6C. 16D. 17答： 这里MaxSize=21，其中的元素个数=r-f MaxSize%MaxSize=16。本题的答案为C。29. 设环形队列中数组的下标是0~N-1，已知其队头指针ff指向队首元素的前一个位置和队中元素个数n，则队尾指针rr指向队尾元素的位置为。A. f-nB. f-n%NC. f n％ND. f n 1％N答： C。30. 设环形队列中数组的下标是0~N-1，已知其队尾指针rr指向队尾元素的位置和队中元素个数n，则队尾指针ff指向队头元素的前一个位置为。A. r-nB. r-n%N
C. r-n N％ND. r n％N答： C。31. 若用一个大小为6的数组来实现环形队列，rear作为队尾指针指向队列中的尾部元素，front作为队头指针指向队头元素的前一个位置。现在rear和front的值分别是0和3，当从队列中删除一个元素再加入两个元素后rear和front的值分别是。A. 1和5B. 2和4C. 4和2D. 5和1答： 删除一个元素时front循环增1，进队两个元素时rear循环增2。本题的答案为B。32. 有一个环形队列qu存放元素位置0~MaxSize-1，rear作为队尾指针指向队列中的尾部元素，front作为队头指针指向队头元素的前一个位置，则队满的条件是。A. qu-front==qu-rearB. qu-front 1==qu-rearC. qu-front==qu-rear 1%MaxSizeD. qu-rear==qu-front 1%MaxSize答： 根据环形队列的结构很快可以排除选项A和B因为它们与MaxSize无关。环形队列中约定，当进队一个元素后到达了队头就表示队满，进队操作是rear循环增1。本题的答案为C。33. 假设用Q［0..M］实现环形队列，f作为队头指针指向队头元素的前一个位置，r作为队尾指针指向队尾元素。若用r 1%M 1==f作为队满的标志，则。A. 可用f==r作为队空的标志B. 可用fr作为队空的标志C. 可用f 1%M 1==r作为队空的标志D. 队列中最多可以有M l个元素答： 这里MaxSize等于M 1，若用r 1%M 1==f作为队满的标志，队列中最多可以有M个元素。本题的答案为A。34. 环形队列存放在一维数组A［0.. M-1］中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可以进行入队和出队操作，队列中最多能容纳M-1个元素，初始时为空。下列判断队空和队满的条件中正确的是。A. 队空： end1==end2;队满： end1==end2 1 mod MB. 队空： end1==end2;队满： end2==end1 1 mod M-1C. 队空： end2==end1 1 mod M;队满： end1==end2 1 mod MD. 队空： end1==end2 1 mod M;队满： end2==end1 1 mod M-1答： 这里环形队列是让队头指针指向队头元素、队尾指针指向队尾元素的后一个位置，和经典做法让队头指针指向队头元素的前一个位置、队尾指针指向队尾元素，在判断队空和队满的条件上是相同的，都是通过少放一个元素来区分队空和队满。本题的答案为A。35. 若用data［0.. n-1］数组来实现环形队列，初始时队头指针front指向队头元素的前一个位置和队尾指针rear指向队列中的尾部元素均为0，现有1~6的6个元素进队，然后出队8次，发现原来存放元素4的位置变为队头，则n为。A. 5B. 4C. 8D. 10答： 初始时，front=rear=0，进队1~6元素，此时元素4的位置为3，出队8次后，队头指针front=front 8%n=8%n，即8%n=3，则n=5。本题的答案为A。36. 假设用一个不带头结点的单链表表示队列，队尾应该在链表的位置。A. 链头B. 链尾C. 链中D. 以上都可以答： B。37. 最适合用作链队的链表是。A. 带队首指针和队尾指针的循环单链表B. 带队首指针和队尾指针的非循环单链表C. 只带队首指针的非循环单链表D. 只带队首指针的循环单链表答： 对于链队，进队操作是在队尾插入结点，出队操作是删除队首结点。对于带队首指针和队尾指针的非循环单链表，这两种操作的时间复杂度均为O1，所以本题的答案为B。38. 最不适合用作链队的链表是。A. 只带队首指针的非循环双链表B. 只带队首指针的循环双链表C. 只带队尾指针的循环双链表D. 只带队尾指针的循环单链表答： 选项A和B均可用作链式队列，但不必采用循环单链表，这样反而降低了队列基本运算的效率。本题的答案为A。3.3.2填空题1. 栈是一种具有特性的线性表。答： 后进先出或先进后出。2. 设栈S和队列Q的初始状态均为空，元素a，b，c，d，e，f，g依次进栈S。若每个元素出栈后立即进入队列Q，且7个元素出列的顺序是b，d，c，f，e，a，g，则栈S的容量至少是。答： 3。由于队列不改变进出序列，这里变为求通过一个栈将a，b，c，d，e，f，g序列变为b，d，c，f，e，a，g序列时栈空间至少多大？从其进出栈过程可以看到，栈中最多有3个元素，即栈大小至少为3。3. 一个初始输入序列1,2,,n，出栈序列是p1,p2,,pn，若p1=1，则p2的可能取值个数为。答： n-1。p2不可能取值1，其他2~n的值都可能。4. 一个初始输入序列1,2,,n，出栈序列是p1,p2,,pn，若p1=4，则p2的可能取值个数为。答： n-3。p2不可能取值4、2、1，其他值都可能。5. 栈的常用运算是进栈和出栈，设计栈的一种好的存储结构应尽可能保证进栈和出栈运算的时间复杂度为。答： O1。6. 当利用大小为n的数组data［0..n-1］存储一个顺序栈时，假定用top==n表示栈空，则向这个栈插入一个元素时首先应执行语句修改top指针。答： top--。7. 当利用大小为n的数组data［0..n-1］存储一个顺序栈时，假定用top==-1表示栈空，则向这个栈插入一个元素时首先应执行语句修改top指针。答： top。8. 若用data［1..m］作为顺序栈的存储空间，栈空的标志是栈顶指针top的值等于m 1，则每进行一次①操作，需将top的值加1； 每进行一次②操作，需将top的值减1。答： ①出栈②进栈。这里以data［m］端作为栈底、data［1］端作为栈顶。9. 当两个栈共享一个存储区时，栈利用一维数组data［1..n］表示，栈1在低下标处，栈2在高下标处。两栈顶指针为top1和top2，初始值分别为0和n 1，则当栈1空时top1为①，栈2空时②，栈满时为③。答： ①top1=0②top2=n 1③top1 1=top2。10. 表达式a b*c-de f*gh ij的后缀表达式是。答： a b c * d - e f g * h i j 。11. 如果栈的最大长度难以估计，则其存储结构最好使用。答： 链栈。12. 若用带头结点的单链表st来表示链栈，则栈空的标志是。答： st-next==NULL。13. 若用不带头结点的单链表st来表示链式栈，则创建一个空栈所要执行的操作是。答： st=NULL。14. 在用栈求解迷宫路径时，当找到出口时，栈中所有方块。答： 构成一条迷宫路径。15. 若用Q［1..m］作为非环形顺序队列的存储空间，则最多只能执行次进队操作。答： m。16. 若用Q［1..100］作为环形队列的存储空间，f、r分别表示队头和队尾指针，f指向队头元素的前一个位置，r指向队尾元素，则当f=70，r=20时，队列中共有个元素。答： 50。这里MaxSize=100，元素个数=r-f MaxSize%MaxSize=50。17. 环形队列用数组A［m..n］mdata［i］输出栈中的元素。对应的算法如下：
#include "SqStack.cpp"包含顺序栈的定义及运算函数
void DispStackSqStack *st
{ElemType x;
SqStack *tmpst;定义临时栈
InitStacktmpst;初始化临时栈
while !StackEmptyst临时栈tmpst中包含st栈中的逆转元素
{Popst,x;
printf"%d ",x;
Pushtmpst,x;
}
printf"＼n";
while !StackEmptytmpst恢复st栈中原来的内容
{Poptmpst,x;
Pushst,x;
}
DestroyStacktmpst;
}
3. 【顺序栈算法】 设计一个算法，利用顺序栈的基本运算求栈中从栈顶到栈底的第k个元素，要求仍保持栈中元素不变。解： 先建立并初始化一个临时栈tmpst。退栈st中的所有元素x，并用i累计元素个数，当i==k时置e=x，并将所有元素进栈到tmpst中，然后将临时栈tmpst中的元素逐一出栈并进栈到st中，这样恢复st栈中原来的元素。如果栈中没有第k个元素，返回假； 否则返回真，并通过引用型参数e保存第k个元素。注意本题要求只能使用栈的基本运算来完成，不能直接用st-data［i］求第k个栈中元素。对应的算法如下：
#include "SqStack.cpp"包含顺序栈的定义及运算函数
bool FindkSqStack *st,int k,ElemType &e
{int i=0;
bool flag=false;
ElemType x;
SqStack *tmpst;定义临时栈
InitStacktmpst;初始化临时栈
while !StackEmptyst临时栈tmpst中包含st栈中的逆转元素
{i;
Popst,x;
if i==k
{e=x;
flag=true;
}
Pushtmpst,x;
}
while !StackEmptytmpst恢复st栈中原来的内容
{Poptmpst,x;
Pushst,x;
}
DestroyStacktmpst;
return flag;
}
4. 【顺序栈算法】 有abcde共nn=5个字符，通过一个栈可以产生多种出栈序列，设计一个算法判断序列str是否为一个合适的出栈序列，并给出操作过程，要求用相关数据进行测试。解： 先建立一个字符顺序栈st，将进栈序列abcde存放到字符数组A中。用i、j分别扫描数组A和str，它们的初始值均为0。当数组A和str都没有扫描完时循环： 比较栈顶元素e和str［j］，若两者不相同，则将A［i］进栈，i加1； 若两者相同，则出栈栈顶元素e，j加1。上述循环结束后退栈所有元素。如果序列str是一个合适的出栈序列，必有j==n，否则str不是一个合适的出栈序列。对应的算法如下：
#include "SqStack.cpp"包含顺序栈的定义及运算函数
bool isSerialchar str［］,int n
{int i,j;
char A［MaxSize］,e;
SqStack *st;建立一个顺序栈
InitStackst;
for i=0;i
#define MaxSize 100
typedef char ElemType;
typedef struct
{ElemType S［MaxSize］;存放共享栈中的元素
int top1,top2;两个栈顶指针
} StackType;声明共享栈类型
-----栈初始化算法------
void InitStack1StackType &st
{st.top1=-1;
st.top2=MaxSize;
}
-----判栈空算法： i=1：栈1，i=2：栈2------
bool StackEmpty1StackType st,int i
{if i==1
returnst.top1==-1;
else i=2
returnst.top2==MaxSize;
}
-----进栈算法： i=1：栈1，i=2：栈2------
bool Push1StackType &st,int i,ElemType x
{if st.top1==st.top2-1栈满
return false;
if i==1x进栈S1
{st.top1;
st.S［st.top1］=x;
}
else if i==2x进栈S2
{st.top2--;
st.S［st.top2］=x;
}
else参数i错误返回false
return false;
return true;操作成功返回true
}
-----出栈算法： i=1：栈1，i=2：栈2------
bool Pop1StackType &st,int i,ElemType &x
{if i==1S1出栈
{if st.top1==-1S1栈空
return false;
else出栈S1的元素
{x=st.S［st.top1］;
st.top1--;
}
}
else if i==2S2出栈
{if st.top2==MaxSizeS2栈空
return false;
else出栈S2的元素
{x=st.S［st.top2］;
st.top2;
}
}
else参数i错误返回false
return false;
return true;操作成功返回true
}
6. 【环形队列算法】 设计一个算法，利用环形队列的基本运算返回指定队列中的队尾元素，要求算法的空间复杂度为O1。解： 由于算法要求空间复杂度为O1，所以不能使用临时队列。先求出队列qu中的元素个数m。循环m次，出队一个元素x，再将元素x进队，最后的x即为队尾元素。对应的算法如下：
#include "SqQueue.cpp"包含顺序队的类型定义和运算函数
ElemType LastSqQueue *qu
{ElemType x;
int i,m=qu-rear-qu-front MaxSize%MaxSize;
for i=1;irear-qu-front MaxSize%MaxSize;
if kcount
return false;
for i=1;irear=0;
q-count=0;
}
bool EnQuQuType *&q,ElemType x进队运算
{if q-count==MaxSize队满上溢出
return false;
else
{q-rear=q-rear 1%MaxSize;
q-data［q-rear］=x;
q-count;
return true;
}
}
bool DeQuQuType *&q,ElemType &x出队运算
{int front;局部变量
if q-count==0队空下溢出
return false;
else
{front=q-rear-q-count MaxSize%MaxSize;
front=front 1%MaxSize;队头位置进1
x=q-data［front］;
q-count--;
return true;
}
}
bool QuEmptyQuType *q判空运算
{
returnq-count==0;
}
9. 【环形队列算法】 设计一个环形队列，用front和rear分别作为队头和队尾指针，另外用一个标志tag标识队列可能空0或可能满1，这样加上front==rear可以作为队空或队满的条件，要求设计队列的相关基本运算算法。解： 设计的队列类型如下：
typedef struct
{ElemType data［MaxSize］;
int front,rear;队头和队尾指针
int tag;为0表示队可能空,为1时表示队可能满
} QueueType;
初始时tag=0，front=rear=0，成功的进队操作后tag=1任何进队操作后队列可能满，但不一定满，任何进队操作后队列不可能空，成功的出队操作后tag=0任何出队操作后队列可能空，但不一定空，任何出队操作后队列不可能满，因此这样的队列的4要素如下。
① 队空条件： qu.front==qu.rear && qu.tag==0；② 队满条件： qu.front==qu.rear && qu.tag==1；③ 元素x进队： qu.rear=qu.rear 1%MaxSize; qu.data［qu.rear］=x; qu.tag=1;④ 元素x出队： qu.front=qu.front 1%MaxSize; x=qu.data［qu.front］; qu.tag=0。对应的算法如下：
void InitQueue1QueueType &qu初始化队列算法
{qu.front=qu.rear=0;
qu.tag=0;为0表示队空可能为空
}
bool QueueEmpty1QueueType qu判队空算法
{
returnqu.front==qu.rear && qu.tag==0;
}
bool QueueFull1QueueType qu判队满算法
{
returnqu.tag==1 && qu.front==qu.rear;
}
bool EnQueue1QueueType &qu,ElemType x进队算法
{if QueueFull1qu==1队满
return false;
qu.rear=qu.rear 1%MaxSize;
qu.data［qu.rear］=x;
qu.tag=1;至少有一个元素,可能满
return true;
}
bool DeQueue1QueueType &qu,ElemType &x出队算法
{if QueueEmpty1qu==1队空
return false;
qu.front=qu.front 1%MaxSize;
x=qu.data［qu.front］;
qu.tag=0;出队一个元素,可能空
return true;
}
10. 【双端队列应用】 假设有一个整型数组存放n个学生的分数，将分数分为3个等级，分数高于或等于90的为A等，分数低于60的为C等，其他为B等。要求采用双端队列，先输出A等分数，再输出C等分数，最后输出B等分数。解： 设计双端队列的从队头出队算法deQueue1、从队头进队算法enQueue1和从队尾进队算法enQueue2。对于含有n个分数的数组a，扫描所有元素a［i］，若a［i］为A等，直接输出； 若为B等，将其从队尾进队； 若为C等，将其从队头进队。最后从队头出队并输出所有的元素。对应的算法如下：
#include "SqQueue.cpp"包含顺序队的类型定义和运算函数
bool deQueue1SqQueue *&q,ElemType &e从队头出队算法
{if q-front==q-rear队空下溢出
return false;
q-front=q-front 1%MaxSize;修改队头指针
e=q-data［q-front］;
return true;
}
bool enQueue1SqQueue *&q,ElemType e从队头进队算法
{if q-rear 1%MaxSize==q-front队满
return false;
q-data［q-front］=e;e元素进队
q-front=q-front-1 MaxSize%MaxSize;修改队头指针
return true;
}
bool enQueue2SqQueue *&q,ElemType e从队尾进队算法
{if q-rear 1%MaxSize==q-front队满上溢出
return false;
q-rear=q-rear 1%MaxSize;修改队尾指针
q-data［q-rear］=e;e元素进队
return true;
}
void funint a［］,int n
{int i;
ElemType e;
SqQueue *qu;
InitQueuequ;
for i=0;i=90
printf"%d ",a［i］;
else if a［i］=60
enQueue2qu,a［i］;从队尾进队
else
enQueue1qu,a［i］;从队头进队
}
while !QueueEmptyqu
{deQueue1qu,e;从队头出队
printf"%d ",e;
}
printf"＼n";
DestroyQueuequ;
}
11. 【顺序栈和顺序队算法】 用于列车编组的铁路转轨网络是一种栈结构，如图3.7所示，其中右边轨道是输入端、左边轨道是输出端。当右边轨道上的车皮编号顺序为1、2、3、4时，如果执行操作进栈、进栈、出栈、进栈、进栈、出栈、出栈、出栈，则在左边轨道上的车皮编号顺序为2、4、3、1。
图3.7铁路转轨网络
设计一个算法，输入n个整数，表示右边轨道上n节车皮的编号，用上述转轨栈对这些车皮重新编排，使得编号为奇数的车皮都排在编号为偶数的车皮的前面。解： 将转轨栈看成一个栈，将左边轨道看成是一个队列。从键盘逐个输入表示右边轨道上车皮编号的整数，根据其奇偶性做以下处理： 若是奇数，则将其插入到表示左边轨道的顺序队列的队尾； 若是偶数，则将其插入到表示转轨栈的顺序栈的栈顶。当n个整数都检测完之后，这些整数已全部进入队列或栈中。此时，首先按先进先出的顺序输出队列中的元素，然后再按后进先出的顺序输出栈中的元素。算法中直接使用两个数组st和qu分别存放栈和队列中的元素。对应的算法如下：
#include
#define MaxSize 100
void fun1
{int i,n,x;
int st［MaxSize］,top=-1;顺序栈和栈顶指针
int qu［MaxSize］,front=0,rear=0;队列和队指针
printf"n：";
scanf"%d",&n;
for i=0;i=0栈中的所有元素出栈
{printf"%d出栈 ",st［top］;
top--;
}
printf"＼n";
}
int main
{fun1;
return 1;
}
本程序的一次求解结果如下：
n：4↙
第1个车皮编号：4↙4进栈
第2个车皮编号：1↙1进队
第3个车皮编号：3↙3进队
第4个车皮编号：2↙2进栈
出轨操作：
1出队3出队2出栈4出栈
|
|
購物車/收銀台(0) | 在線留言板
| 付款方式
| 聯絡我們
| 運費計算
| 幫助中心 |
加入書簽
HOME
新書上架
