回文序列判断实验报告
系别：通信工程
班级： 0905班
学号： 18 号
1．实验目的：熟悉栈的各项操作
2．实验内容：
利用栈的操作完成读入的一个以@结尾的字符序列是否是回文序列的判断.
回文序列即正读与反读都一样的字符序列;
例如:123&321@是;
123&4321@、123&312@不是
算法思想：从键盘上读取一个字符，同时存储在顺序栈与链队列之中，直到字符序列的最后一个字符为@停止输入，因为要满足特定的要求：序列1&序列2，故设置夜歌标记量falg=1,判断输入的元素个数是否为奇数个，若为偶数个则令flag=0，若为奇数个继续判断栈的中间元素是否为&,若不是则令flag=0，若是，将栈和队列中的元素依次出列，判断是否相等，若不相等则令flag=0,最后将flag的值返回给主函数，若flag被修改为0说明不是回文序列，否则反之！！
判断回文序列的流程图：
3．实验感想与体会
通过本次的上机，对栈的各项基本操作都有了更好的掌握，同时明白了一些小的细节问题可能会影响到整个程序的正确的运行，本次的实验我通过了运用栈和队列，可以说对队列的一些基本的操作也得以了巩固和提高！更加体会到，自己写程序上机操作的重要性，它要比课本上学的要多得多！
4．附录（源代码及运行图）
#include
#define MAX 100
typedef struct//栈结构体
{
char e[MAX];
int top;
}SeqStack;
typedef struct NODE//队列结构体
{
char d;
struct NODE *next;
}LinkQN;
typedef struct//封装头指针为指针
{
LinkQN *front;
LinkQN *rear;
}LinkQ;
InitS(SeqStack *s)//初始化顺序栈
{
s->top=-1;
}
int push(SeqStack *s,char ch)//入栈
{
if(s->top==MAX-1)
return(0);
s->top++;
s->e[s->top]=ch;
return(1);
}
int pop(SeqStack *s,char *x)//出栈
{
if(s->top==-1)
return(0);
*x=s->e[s->top];
s->top--;
return(1);
}
void InitQ(LinkQ *q)//链队列初始化
{
q->front=(LinkQN *)malloc(sizeof(LinkQN));
if(!q->front)
{
printf("分配空间失败!");
}
q->rear=q->front;
q->front->next=NULL;
}
int enter(LinkQ *q,char ch)//入队
{
LinkQN *np;
np=(LinkQN *)malloc(sizeof(LinkQN));
if(!np)
return(0);
np->d=ch;
np->next=NULL;
q->rear->next=np;
q->rear=np;
return(1);
}
int deleteq(LinkQ *q,char *c)//出队
{ LinkQN *p;
if(q->front==q->rear)
return(0);
p=q->front->next;
q->front->next=p->next;
if(q->rear==p)
q->rear=q->front;
*c=p->d;
free(p);
return(0);
}
int huiwen(SeqStack *s,LinkQ *q)//回文判断
{
int flag=1,m=0,t=1;
int i;
char ch1,ch2,ch;
InitS(&s);
InitQ(&q);
printf("请输入字符序列当输入字符@时输入结束:\n");
while(ch!='@')
{
ch=getch();
if(ch!='@')
{ printf("%c",ch);
push(&s,ch);
enter(&q,ch);
m++;
}
}
printf("\n输入完成!\n");
printf("按任意键予以判断!\n");
getch();
if(m%2)
{
if(s->e[m/2]=='&')
{
for(i=1;i<(m+1)/2;i++)
{
pop(&s,&ch1);
deleteq(&q,&ch2);
if(ch1!=ch2)
flag=0;
}
}
else flag=0;
}
else flag=0;
return(flag);
}
main()
{
SeqStack *s;
LinkQ *q;
int m;
m=huiwen(*s,&q);
printf("\n");
if(m)
printf("该字符序列是回文序列!\n");
else
printf("该字符序列不是回文序列!\n"); }
实验课题一：回文（palindrome）是指一个字符串从前面读和从后面读都一样，仅使用若干栈和队列、栈和队列的ADT函数以及若干个int类型和char类型的变量，设计一个算法来判断一个字符串是否为回文。假设字符串从标准输入设备一次读入一个字符，算法的输出结果为true或者false。 可以用一些字符串测试输出结果，如： "abcdeabcde"，"madamimadam" 等 #include
栈和队列的应用 1.题目要求： 输入一段字符串，判断字符串是否是回文。回文字符串的定义：字符串的顺序输入和逆序输出内容完全一样。要求出入一段字符串，以‘#’为结束符；判断是否是回文，并输出； 2.实验目的： 通过做回文的题，来熟悉栈和队列的结构以及内容，最终达到掌握 3.实验步骤 1.定义栈的结构体： typedef struct { //栈结构的定义 int *top; int *base; int stacksize; }sqstack; 2.定义队列的结构体： typedef struct queue{ //队列的结构体定义 int data; struct queue *next; }queue,*que; typedef struct { que front; //队列的头指针 que rear; //队列的尾指针 }Q; 4.相关函数： void inistack(sqstack &s)//初始化一个空栈 bool just(sqstack &s)//判断栈是否为空，返回bool类型 void push(sqstack &s,int e)//入栈 char pop(sqstack &s,int &e)//出栈，返回char类型 void initQ(Q &q)//初始化一个空队列 pushq(Q &q,int e)//入队 char popq(Q &q,int &e)//出队，返回char类型 5.总体结构图
6.运行结果分析 完成对字符串的判断以及输出； 7.程序清单
#include 实验三栈和队列的应用 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 ) /* 栈空 */ 出栈序列相对入栈序列关系 在数据结构的定义里，栈是只允许一端进行插入或删除操作的线性表。人们总结简化为后进先出原则。栈的定义给定以后引出了另一类问题——出栈序列问题。就是在给定一个入栈序列（如a1,a2…a n）的条件下，在进栈操作时，允许出栈操作，来判断一下哪些序列是可能的出栈序列，而哪些必不是出栈序列。当然，前提是要保证要求判断的序列里面的元素要与给定入栈序列里的元素一一映射。否则就没有再往下判断的必要了。 对于这类问题一般的方法是在本子上画表格模拟一个栈然后实际操作一下，看看哪些是可调度实现的，哪些是不可能实现的。这种方法是很不严谨的，而且 n 种工作量很大，对于一个具有n个元素的入栈序列，它的出栈序列有(1/(n+1))*C 2n 可能。如果n稍大一点，工作量会颇具规模。到这来，您也许会有点被忽悠了，其实给定一个如栈序列，a1,a2,……a n ，再给定出要判断的出栈队列a i ,a j , a k,……判断他们是否匹配，很简单，用一个大小为n的数组模拟栈，以a1,a2,……a n 做输入，对照着要判断的序列a i ,a j , a k,…… ，有目的的操作在线性时间内就可以完成。只是这种操作人工来说稍微麻烦一点罢了。 对于人工做判断，研究发现这类问题是具有一般规律的。在此先给出这一定律的定义，然后举几个常见的应用，最后给出证明。 这一定律是：在给定入栈顺序序列的前提下，对于其出栈序列里任意元素a n ，晚于其出栈且先于入栈的元素必须按入栈的逆序排列。 先后几个应用实例： 1.设a,b,c,d,e,f 以所给的次序进栈，若在进栈操作时，允许出栈 操作，则下面得不到的序列为： A. fedcba B. bcafed C. dcefba D. cabdef 答案是 D .因为 A. B. C 项都满足规律，但 D 项里a,b 晚于c 出栈且先于 c 入栈，它们的排列顺序应是ba。 2.元素a,b,c,d,e 依次进入初始为空的栈中，若元素进栈后可停 留，可出栈，直到所有元素都出栈，则在所有可能出栈序列中，以元素 d开头的序列个数是多少个？ 这一问题是可以很方便用上面给的规律来解决。序列以元素d开头说明d 第3章栈和队列 一选择题 1. 对于栈操作数据的原则是（）。【青岛大学 2001 五、2（2分）】 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 2. 在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否( ② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。 为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时，才产生上溢。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶 D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点. B. 其中一个栈的栈顶到达栈空间的中心点. C. 两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底. 【上海海运学院 1997 二、1（5分）】【上海海运学院 1999 二、1（5分）】 3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。 A. 不确定 B. n-i+1 C. i D. n-i 【中山大学 1999 一、9(1分)】 4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 【武汉大学 2000 二、3】 5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p 1,p 2 ,p 3 ，…，p N ,若p N 是n，则 p i 是( )。 A. i B. n-i C. n-i+1 D. 不确定 【南京理工大学 2001 一、1（1.5分）】 6. 有六个元素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 【北方交通大学 2001 一、3（2分）】 7. 设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。【中科院计算所2000一、10(2分)】 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， 8. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 【南开大学 2000 一、1】【山东大学 2001 二、4 (1分)】【北京理工大学 2000 一、2（2分）】 9. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（）。 A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4 【合肥工业大学 2001 一、1（2分）】 10. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是 （C语言版数据结构）利用栈和队列判断回文 (2010-11-03 11:51:45) 标签： it // File Name: palindrome.h // // Destination:利用栈和队列判断字符串是否是回文 // #ifndef PALINDROME #define PALINDROME #include // 链式队列的基本操作 bool InitQueue(LinkQueue *Q); bool EnQueue(LinkQueue *Q, ElemType e); bool DeQueue(LinkQueue *Q, ElemType *e); // 栈的基本操作 bool InitStack(SqStack *S); bool Push(SqStack *S, ElemType e); bool Pop(SqStack *S, ElemType *e); #endif // File Name: palindrome.cpp // // Destination:利用栈和队列判断字符串是否是回文 #include 实验编号：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，2，3，…，n，有多少个不同的出栈序列?[4- ] 常规分析 首先，我们设f（n）=序列个数为n的出栈序列种数。同时，我们假定，从开始到栈第一次出到空为止，这段过程中出栈的序数最大的是k。特别地，如果栈直到整个过程结束时才空，则k=n 首次出空之前第一个出栈的序数k将1~n的序列分成两个序列，其中一个是1~k-1，序列个数为k-1，另外一个是k+1~n，序列个数是n-k。 此时，我们若把k视为确定一个序数，那么根据乘法原理，f（n）的问题就等价于——序列个数为k-1的出栈序列种数乘以序列个数为n - k的出栈序列种数，即选择k这个序数的f（n）=f（k-1）×f（n-k）。而k可以选1到n，所以再根据加法原理，将k取不同值的序列种数相加，得到的总序列种数为：f（n）=f （0）f（n-1）+f（1）f（n-2）+……+f（n-1）f（0）。 看到此处，再看看卡特兰数的递推式，答案不言而喻，即为f（n）=h（n）= C （2n,n）/（n+1）= c（2n,n）-c（2n,n+1）（n=0，1，2，……）。 最后，令f（0）=1，f（1）=1。 非常规分析 对于每一个数来说，必须进栈一次、出栈一次。我们把进栈设为状态‘1’，出栈设为状态‘0’。n个数的所有状态对应n个1和n个0组成的2n位二进制数。由于等待入栈的操作数按照1‥n的顺序排列、入栈的操作数b大于等于出栈的操作数a(a≤b)，因此输出序列的总数目=由左而右扫描由n个1和n个0组成的2n位二进制数，1的累计数不小于0的累计数的方案种数。 在2n位二进制数中填入n个1的方案数为c(2n,n),不填1的其余n位自动填0。从中减去不符合要求（由左而右扫描，0的累计数大于1的累计数）的方案数即为所求。 数据结构练习第三章栈和队列 一、选择题 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．队列的插入操作是在（）进行。 习题三参考答案 备注: 红色字体标明的是与书本内容有改动的内容。 一、选择题 1.在栈中存取数据的原则是（ B ）。 A．先进先出 B. 先进后出 C. 后进后出 D. 没有限制 2．若将整数1、2、3、4依次进栈，则不可能得到的出栈序列是（ D ）。 A．1234 B. 1324 C. 4321 D. 1423 3．在链栈中，进行出栈操作时（B ）。 A．需要判断栈是否满 B. 需要判断栈是否为空 C. 需要判断栈元素的类型 D. 无需对栈作任何差别 4．在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize，则顺序栈的判空条件是（ A ）。 A．top==0 B.top==-1 C. top==maxSize D.top==maxSize-1 5．在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize。则顺序栈的判满的条件是（ C ）。 A．top==0 B.top==-1 C. top==maxSize D.top==maxSize-1 6．在队列中存取数据元素的原则是（ A ）。 A．先进先出 B. 先进后出 C. 后进后出 D. 没有限制 7．在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判空条件是（A ）。 A．front==rear B. front!=rear C. front==rear+1 D. front==(rear+1)% maxSize 8．在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判满条件是（D ）。 A．front==rear B. front!=rear C. front==rear+1 D. front==(rear+1)% maxSize 9.在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首 和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的长度是（C ）。 A．rear-front B. rear-front+1 C. (rear-front+maxSize)%maxSize D. (rear-front+1)%maxSize 10.设长度为n的链队列采用单循环链表加以表示，若只设一个头指针指向队首元素，则入队操作的时间复杂度 为（ B ）。 A．O(1) B．O(n) C．O(log2n) D．O(n2) 二、填空题 1.栈是一种操作受限的特殊线性表，其特殊性体现在其插入和删除操作都限制在表尾进行。允许插入和删除 操作的一端称为栈顶，而另一端称为栈底。栈具有后进先出的特点。 2.栈也有两种存储结构，一种是顺序存储，另一种是链式存储；以这两种存储结构存储的栈分别称为顺序 栈和链栈。 3.在顺序栈中，假设栈顶指针top是指向栈顶元素的下一个存储单元，则顺序栈判空的条件是 top==0 ; 栈顶 第3章栈与队列 一、单项选择题 1．元素A、Ｂ、C、D依次进顺序栈后，栈顶元素是，栈底元素是。 A．A B．B C．C D．D 2．经过以下栈运算后，x的值是。 InitStack(s)；Push(s,a)；Push(s,b)；Pop(s,x)；GetTop(s,x); A．a B．b C．1 D．0 3．已知一个栈的进栈序列是ABC，出栈序列为CBA，经过的栈操作是。 A．push,pop,push,pop,push,pop B．push,push,push,pop,pop,pop C．push,push,pop,pop,push,pop D．push,pop,push,push,pop,pop 4．设一个栈的输入序列为A、B、C、D，则借助一个栈所得到的序列是。 A．A,B,C,D B．D,C,B,A C．A,C,D,B D．D,A,B,C 5．一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是。 A．edcba B．decba C．dceab D．abcde 6．已知一个栈的进栈序列是1，2，3，……,n，其输出序列的第一个元素是i，则第j个出栈元素是。 A．i B．n-i C．j-i+1 D．不确定 7．已知一个栈的进栈序列是1，2，3，……，n，其输出序列是p1,p2,…,Pn，若p1=n，则pi的值。 A．i B．n-i C．n-i+1 D．不确定 8．设n个元素进栈序列是1，2，3，……，n，其输出序列是p 1,p 2 ,…,p n ，若p 1 =3, 则p 2 的值。 A．一定是2 B．一定是1 C．不可能是1 D．以上都不对 9．设n个元素进栈序列是p 1,p 2 ,…,p n ，其输出序列是1，2，3，……，n，若p 3 =1, 则p 1 的值。 A．可能是2 B．一定是1 C．不可能是2 D．不可能是3 10．设n个元素进栈序列是p 1,p 2 ,…,p n ，其输出序列是1，2，3，……，n，若 p 3=3,则p 1 的值。 A．可能是2 B．一定是2 C．不可能是1 D．一定是1 11．设n个元素进栈序列是p 1,p 2 ,…,p n ，其输出序列是1，2，3，……，n，若 p n =1,则p i (1≤i≤n-1)的值。 A．n-i+1 B．n-i C．i D．有多种可能 12．判定一个顺序栈S为空的条件为。 A．= = B．!= C．!= + D．= = + 13．判定一个顺序栈S为栈满的条件是。 A． = B．= = C．D．!= 14．链栈与顺序栈相比有一个明显的优点，即。 A．插入操作方便B．通常不会出现栈满的情况C．不会出现栈空的情况D．删除操作更加方便15．最不适合用作链栈的链表是。 A．只有表头指针没有表尾指针的循环双链表 习题三栈和队列 一单项选择题 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 回文判断实验二 洛阳理工学院实验报告 系别计算机系班级B13053 学号B13053235 姓名李登辉 2 课程名称数据结构实验日期2014.3.28 实验名称栈和队列的基本操作成绩 实验目的： 熟悉掌握栈和队列的特点，掌握与应用栈和队列的基本操作算法，训练和提高结构化程序设计能力及程序调试能力。 实验条件： 计算机一台，Visual C++6.0 实验内容： 1.问题描述 利用栈和队列判断字符串是否为回文。称正读与反读都相同的字符序列为“回文”序列。要求利用栈和队列的基本算法实现判断一个字符串是否为回文。栈和队列的存储结构不限。 2.数据结构类型定义 typedef struct { char elem[MAX]; int top; }SeqStack; 顺序栈 3.模块划分 void InitStack(SeqStack *S)：栈初始化模块， int Push(SeqStack *S,char x,int cnt)：入栈操作 int Pop(SeqStack * S,char * x)：出栈操作 void InitQuene(SeqQuene *Q)：队列初始化 int EnterQuene(SeqQuene *Q,char x,int cnt)：入队操作 int DeleteQuene(SeqQuene *Q,char *x,int cnt)：出队操作 void main()：主函数 4.详细设计 #include 实验二栈、队列的实现及应用 实验课程名：数据结构与算法 专业班级：学号：： /*构造空顺序栈*/ 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 第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; C 、s->next=Q.rear；Q.rear=s; D 、s->next=Q.front；Q.front=s; 14.在一个链队列Q 中，删除一个结点需要执行的指令是（） A、Q.rear=Q.front->next; B、Q.rear->next=Q.rear->next->next; C、Q.front->next=Q.front->next->next; D、Q.front=Q.rear->next; 一、（本题10分）栈与队列的区别和共同点是什么？队列主要有哪两种物理实现？ 答： 区别：栈在表尾进行插入和删除，具有“后进先出”的特点；队列在表尾插入，在表头删除，具有“先进先出”的特点； 共同点：栈和队列都是特殊的线性表，都是n 个数据元素的有限序列，都是数据结构的逻辑结构。 队列的物理实现：链队列和循环队列。 二、（本题10分）给出二叉树的定义，并画出具有3个结点的二叉树的所有形态。 答：所谓二叉树或者是空树，或者是如下定义的树：每个结点至多只有两棵子树，并且二叉树的子树有左右之分，其次序不能颠倒。 3个结点的二叉树的所有形态如下： 三、(本题15分)考虑下图： 1) 从顶点A 出发，求它的深度优先生成树(字母小的优先访问)。 2) 从顶点E 出发，求它的广度优先生成树(字母小的优先访问)。 3) 使用克鲁斯卡尔算法，求它的最小生成树（给出树的生成过程）。 答：深度优先生成树为: 广度优先生成树为: 最小生成树为：（因为有相同的权值，树的生成过程可能不相同） 评分标准：每小题5分。 四、（本题15分）假定一个待哈希存储的线性表为(32,75,29,63,48,94,25,46,18,70)，哈希地址空间为0～12，若采用除留余数法H(K)=K % 13构造哈希函数，并使用链地址法处理冲突，试画出最后得到的哈希表，并求出平均查找长度。 解： 元素 哈希地址 查找次数 平均查找长度为（1*8+2*2）/10=1.2 评分标准： 画出哈希表得10分，平均查找长度得5分。 五、（本题15分）已知键值序列为｛45,56,83,31,72,35,14,47,89,19｝，要求给出： （1） 按键值排列次序构造一棵二叉排序树。 （2） 在等概率的情况下，该二叉排序树查找成功的平均查找长度。 （3） 针对上述10个键值，在不同的排列次序下所构造出的不同形态的二叉排序树中， 在最坏和最好情况下，二叉排序树的高度各是多少？ 解：总分为15分，每一小步5分。 （1） （2）在等概率情况下，该二叉排序树的平均检索长度是： ASL=(1+2*2+3*4+4*3)/10=29/10=2.9 （3）对于上述10个键值，在最坏情况下，每个结点（除了叶子结点）只有右孩子（或者只有左孩子），高度为10。在最好情况下，高度为└log 210┘+1=4。 六、（本题10分）设关键字序列为：49，38，66，90，75，10，20。把这些关键字调整成堆顶元素取最小值的堆（写出过程）。 实验二栈和队列的基本操作及其应用 一、实验目的 1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际中灵活应用。 2、掌握栈和队列的特点，即后进先出和先进先出的原则。 3、掌握栈和队列的基本运算，如：入栈与出栈，入队与出队等运算在顺序 存储结构和链式存储结构上的实现。 二、实验内容 本次实验提供4个题目，每个题目都标有难度系数，*越多难度越大，学生 可以根据自己的情况任选一个！ 题目一：回文判断（*） [问题描述] 对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如 “abba”是回文，而“abab”不是回文。 [基本要求] （1）数据从键盘读入； （2）输出要判断的字符串； （3）利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出 “Yes”，否则输出“No”。 [测试数据] 由学生任意指定。 题目二：顺序栈和循环队列基本操作（*） [基本要求] 1、实现栈的基本操作 六项基本操作的机制是：初始化栈：init_stack(S)；判断栈空：stack_empty(S)；取栈顶元素：stack_top(S,x)；入栈：push_stack(S,x)；出栈：pop_stack(S)；判断栈满：stack_full(S) 2、实现队列的基本操作 六项基本操作的机制是：初始化队列：init_queue(Q)；判断队列是否为空：queue_empty(Q)；取队头元素：queue_front(Q,x)；入队：enqueue(Q,x)；出队：outqueue(Q,x)；判断队列是否为满：queue_full(Q) [测试数据] 由学生任意指定。 题目三：商品货架管理（**） [问题描述] 商店货架以栈的方式摆放商品。生产日期越近的越靠近栈底，出货时从栈顶取货。一天营业结束，如果货架不满，则需上货。入货直接将商品摆放到货架上，则会使生产日期越近的商品越靠近栈顶。这样就需要倒货架，使生产日期越近的越靠近栈底。 [基本要求] 设计一个算法，保证每一次上货后始终保持生产日期越近的商品越靠近栈底。 [实现提示] 可以用一个队列和一个临时栈作为周转。 [测试数据] 由学生任意指定。 三、实验前的准备工作 1、掌握栈的逻辑结构和存储结构。 2、熟练掌握栈的出栈、入栈等操作。 3、掌握队列的逻辑结构和存储结构。 4、熟练掌握队列的出队、入队等操作 四、实验报告要求 1、实验报告要按照实验报告格式规范书写。 *2、写出算法设计思路。 3、实验上要写出多批测试数据的运行结果。 4、结合运行结果，对程序进行分析。 题目四：Rails（ACM训练题） Description There is a famous railway station in PopPush City. Country there is incredibly hilly. The station was built in last century. Unfortunately, funds were extremely limited that time. It was possible to establish only a surface track. Moreover, it turned out that the实验三 栈和队列的应用
出栈序列相对入栈序列关系
数据结构考研真题 栈和队列
栈和队列判断回文
数据结构_实验三_栈和队列及其应用
一个栈进栈序列为1,2,3,…,n,有多少个不同的出栈序列
数据结构练习 第三章 栈和队列
栈与队列习题参考答案
数据结构第3章栈与队列习题
数据结构栈和队列习题及答案
回文判断实验二
实验二_栈、队列地实现与应用
(完整版)《数据结构》习题集：第3章栈和队列
本题10分栈与队列的区别和共同点是什么队列主要
数据结构实验二(栈和队列)
相关主题
文本预览