习题三栈和队列
一单项选择题
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
12. 栈和队列的共同点是（）。
A. 都是先进先出
B. 都是先进后出
C. 只允许在端点处插入和删除元素
D. 没有共同点
二、填空题
1．栈是_______的线性表，其运算遵循_______的原则。
2. 一个栈的输入序列是：1，2，3则不可能的栈输出序列是_______。
3．用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为_______。
4. 循环队列的引入，目的是为了克服_______。
5．队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是_______。
6. 已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_______。
7．表达式求值是_______应用的一个典型例子。
8．循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear ，则当前队列的元素个数是_______。
9. 以下运算实现在链栈上的初始化，请在________________处用请适当句子予以填充。
Void InitStacl(LstackTp *ls){ ________________;}
10.` 以下运算实现在链栈上的进栈，请在处用请适当句子予以填充。
Void Push（LStackTp *ls,DataType x）
{ LstackTp *p;p=malloc(sizeof(LstackTp));
________________;
p->next=ls;
________________;
}
11．以下运算实现在链栈上的退栈，请在________________处用请适当句子予以填充。
Int Pop(LstackTp *ls,DataType *x)
{LstackTp *p;
if(ls!=NULL)
{ p=ls;
*x=________________;
ls=ls->next;
________________;
return(1)；
}else return(0);
}
12. 以下运算实现在链队上的入队列，请在________________处用适当句子予以填充。
Void EnQueue(QueptrTp *lq,DataType x)
{ LqueueTp *p;
p=(LqueueTp *)malloc(sizeof(LqueueTp));
________________=x;
p->next=NULL;
(lq->rear)->next=________________;
________________;
}
三、应用题
1．给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？
2. 画出对算术表达式A-B*C/D-E↑F求值时操作数栈和运算符栈的变化过程。
3. 将两个栈存入数组V[1..m]应如何安排最好？这时栈空、栈满的条件是什么？
4. 怎样判定循环队列的空和满？
四、算法设计题
1．借助栈(可用栈的基本运算)来实现单链表的逆置运算。
2. 设表达式以字符形式已存入数组E[n]中，‘#’为表达式的结束符，试写出判断表达式中括号（‘（’和‘）’）是否配对的C语言描述算法：EXYX(E); (注：算法中可调用栈操作的基本算法。)
3. 假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。（1）下面所示的序列中哪些是合法的？
A. IOIIOIOO
B. IOOIOIIO
C. IIIOIOIO
D. IIIOOIOO
（2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。
4. 设有两个栈S1,S2都采用顺序栈方式，并且共享一个存储区[O..maxsize-1],为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。
5. 请利用两个栈S1和S2来模拟一个队列。已知栈的三个运算定义如下：PUSH(ST,x):元素x入ST栈；POP(ST,x)：ST栈顶元素出栈，赋给变量x；Sempty(ST)：判ST栈是否为空。那么如何利用栈的运算来实现该队列的三个运算：enqueue:插入一个元素入队列； dequeue:删除一个元素出队列；queue_empty：判队列为空。（请写明算法的思想及必要的注释）
6．要求循环队列不损失一个空间全部都能得到利用，设置一个标志tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此相应的入队与出队算法。
7. 已知Q是一个非空队列，S是一个空栈。仅用队列和栈的ADT函数和少量工作变量，编写一个算法，将队列Q中的所有元素逆置。栈的ADT函数有：
makeEmpty(s:stack); 置空栈
push(s:stack;value:datatype); 新元素value进栈
pop(s:stack):datatype; 出栈，返回栈顶值
isEmpty(s:stack):Boolean; 判栈空否
队列的 ADT函数有：
enqueue(q:queue:value:datatype); 元素value进队
deQueue(q:queue):datatype; 出队列，返回队头值
isEmpty(q:queue):boolean; 判队列空否
第3章栈和队列
一单项选择题
1. B A B
2． A
3. C
4.B
5. B
6. B
7. D
8. D
9. C
10．D
11.C
12. C
二、填空题
1．操作受限（或限定仅在表尾进行插入和删除操作）后进先出
2. 3 1 2
3．S×SS×S××
4. 假溢出时大量移动数据元素
5．先进先出
6. s=(LinkedList)malloc(sizeof(LNode))； s->data=x;s->next=r->next；r->next=s；
r=s；
7．栈
8．（rear-front+m）% m；
9．ls=NULL
10． p->data=x, ls=p
11．p->data, free(p)
12． p->data, p, lq->rear=p
三、应用题
1．【解答】（1）顺序栈（top用来存放栈顶元素的下标）
判断栈S空：如果S->top==-1表示栈空。
判断栈S满：如果S->top==Stack_Size-1表示栈满。
(2) 链栈（top为栈顶指针，指向当前栈顶元素前面的头结点）
判断栈空：如果top->next==NULL表示栈空。
判断栈满：当系统没有可用空间时，申请不到空间存放要进栈的元素，此时栈满。
3. 设栈S1和栈S2共享向量V[1..m]，初始时，栈S1的栈顶指针top[0]=0，栈S2的栈顶指针top[1]=m+1，当top[0]=0为左栈空，top[1]=m+1为右栈空；当top[0]=0并且top[1]=m+1时为全栈空。当top[1]-top[0]=1时为栈满。
4. 设顺序存储队列用一维数组q[m]表示，其中m为队列中元素个数，队列中元素在向量中的下标从0到m-1。设队头指针为front，队尾指针是rear，约定front指向队头元素的前一位置，rear指向队尾元素。当front等于-1时队空，rear等于m-1时为队满。由于队列的性质（“删除”在队头而“插入”在队尾），所以当队尾指针rear等于m-1时，若front 不等于-1，则队列中仍有空闲单元，所以队列并不是真满。这时若再有入队操作，会造成假“溢出”。其解决办法有二，一是将队列元素向前“平移”（占用0至rear-front-1）；二是将队列看成首尾相连，即循环队列（0..m-1）。在循环队列下，仍定义front=rear时为队空，而判断队满则用两种办法，一是用“牺牲一个单元”，即rear+1=front（准确记是（rear+1）%m=front，m是队列容量）时为队满。另一种解法是“设标记”方法，如设标记tag，tag等于0情况下，若删除时导致front=rear为队空；tag=1情况下，若因插入导致front=rear则为队满。
四算法设计题
1．解：方法是先依次让单链表上的元素进栈，然后再依次出栈。
Void invert (lklist head)
{LstackTp s;
initstack(s);
p= head;
while (p<>null)
{Push (s,p->data);p=p->next;}
p=head;
while(not emptystack(s))
{pop(s,p->data); p=p->next;}
}
2. [题目分析]判断表达式中括号是否匹配，可通过栈，简单说是左括号时进栈，右括号时退栈。退栈时，若栈顶元素是左括号，则新读入的右括号与栈顶左括号就可消去。如此下去，输入表达式结束时，栈为空则正确，否则括号不匹配。
int EXYX(char E[],int n)
//E[]是有n字符的字符数组，存放字符串表达式，以‘#’结束。本算法判断表达式中圆括号是否匹配。
{char s[30]; //s是一维数组，容量足够大，用作存放括号的栈。
int top=0; //top用作栈顶指针。
s[top]= ‘#’; //‘#’先入栈，用于和表达式结束符号‘#’匹配。
int i=0; //字符数组E的工作指针。
while(E[i]!= ‘#’) //逐字符处理字符表达式的数组。
switch(E[i])
{case‘(’: s[++top]=‘(’; i++ ; break ;
case‘)’: if(s[top]==‘(’{top--; i++; break;}
else{printf(“括号不配对”);exit(0);}
case‘#’: if(s[top]==‘#’){prin tf(“括号配对\n”);return (1);}
else{printf(“ 括号不配对\n”);return (0);} //括号不配对 default : i++; //读入其它字符，不作处理。
}
}//算法结束。
[算法讨论]本题是用栈判断括号匹配的特例：只检查圆括号的配对。一般情况是检查花括号（‘{’，‘}’）、方括号（‘[’，‘]’）和圆括号（‘（’，‘）’）的配对问题。编写算法中如遇左括号（‘{’，‘[’，或‘（’）就压入栈中，如遇右括号（‘}’，‘]’，或‘）’），则与栈顶元素比较，如是与其配对的括号（左花括号，左方括号或左圆括号），则弹出栈顶元素；否则，就结论括号不配对。在读入表达式结束符‘#’时，栈中若应只剩‘#’，表示括号全部配对成功；否则表示括号不匹配。
另外，由于本题只是检查括号是否匹配，故对从表达式中读入的不是括号的那些字符，一律未作处理。再有，假设栈容量足够大，因此入栈时未判断溢出。
3. （1）A和D是合法序列，B和C 是非法序列。
（2）设被判定的操作序列已存入一维数组A中。
int Judge(char A[])
//判断字符数组A中的输入输出序列是否是合法序列。如是，返回true，否则返回false。
{i=0; //i为下标。
j=k=0; //j和k分别为I和字母O的的个数。
while(A[i]!=‘\0’) //当未到字符数组尾就作。
{switch(A[i])
{case‘I’: j++; break; //入栈次数增1。
case‘O’: k++; if(k>j){printf(“序列非法\n”)；exit(0);}
}
i++; //不论A[i]是‘I’或‘O’，指针i均后移。}
if(j!=k) {printf(“序列非法\n”)；return(false);}
else{printf(“序列合法\n”)；return(true);}
}//算法结束。
[算法讨论]在入栈出栈序列（即由‘I’和‘O’组成的字符串）的任一位置，入栈次数（‘I’的个数）都必须大于等于出栈次数（即‘O’的个数），否则视作非法序列，立即给出信息，退出算法。整个序列（即读到字符数组中字符串的结束标记‘\0’），入栈次数必须等于出栈次数（题目中要求栈的初态和终态都为空），否则视为非法序列。
4． [题目分析]两栈共享向量空间，将两栈栈底设在向量两端，初始时，s1栈顶指针为-1，s2栈顶为maxsize。两栈顶指针相邻时为栈满。两栈顶相向，迎面增长，栈顶指针指向栈顶元素。
#define maxsize 两栈共享顺序存储空间所能达到的最多元素数
#define elemtp int //假设元素类型为整型
typedef struct
{elemtp stack[maxsize]; //栈空间
int top[2]; //top为两个栈顶指针
}stk;
stk s; //s是如上定义的结构类型变量，为全局变量。
(1)入栈操作：
int push(int i,int x)
//入栈操作。i为栈号，i=0表示左边的栈s1，i=1表示右边的栈s2，x是入栈元素。
入栈成功返回1，否则返回0。
{if(i<0||i>1){printf(“栈号输入不对”);exit(0);}
if(s.top[1]-s.top[0]==1) {printf(“栈已满\n”);return(0);}
switch(i)
{case 0: s.stack[++s.top[0]]=x; return(1); break;
case 1: s.stack[--s.top[1]]=x; return(1);
}
}//push
（2）退栈操作
elemtp pop(int i)
//退栈算法。i代表栈号，i=0时为s1栈，i=1时为s2栈。退栈成功返回退栈元素，否则返回-1。
{if(i<0 || i>1){printf(“栈号输入错误\n”)；exit(0);}
switch(i)
{case 0: if(s.top[0]==-1) {printf(“栈空\n”)；return（-1）；}
else return(s.stack[s.top[0]--]);
case 1: if(s.top[1]==maxsize {printf(“栈空\n”); return(-1);}
else return(s.stack[s.top[1]++]);
}
}//算法结束
[算法讨论] 请注意算法中两栈入栈和退栈时的栈顶指针的计算。两栈共享空间示意图
略，s1栈是通常意义下的栈，而s2栈入栈操作时，其栈顶指针左移（减1），退栈时，栈顶指针右移（加1）。
5. [题目分析]栈的特点是后进先出，队列的特点是先进先出。所以，用两个栈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); //队列不空。
}
[算法讨论]算法中假定栈s1和栈s2容量相同。出队从栈s2出，当s2为空时，若s1不空，则将s1倒入s2再出栈。入队在s1，当s1满后，若s2空，则将s1倒入s2，之后再入队。因此队列的容量为两栈容量之和。元素从栈s1倒入s2，必须在s2空的情况下才能进行，即在要求出队操作时，若s2空，则不论s1元素多少（只要不空），就要全部倒入s2中。
6．【解答】入队算法：
int EnterQueue(SeqQueue *Q, QueueElementType x)
{ /*将元素x入队*/
if(Q->front==Q->front && tag==1) /*队满*/
return(FALSE);
if(Q->front==Q->front && tag==0) /*x入队前队空，x入队后重新设置标志*/
tag=1;
Q->elememt[Q->rear]=x;
Q->rear=(Q->rear+1)%MAXSIZE; /*设置队尾指针*/
Return(TRUE);
}
出队算法：
int DeleteQueue( SeqQueue *Q , QueueElementType *x)
{ /*删除队头元素，用x返回其值*/
if(Q->front==Q->rear && tag==0) /*队空*/
return(FALSE);
*x=Q->element[Q->front];
Q->front=(Q->front+1)%MAXSIZE; /*重新设置队头指针*/
if(Q->front==Q->rear) tag=0; /*队头元素出队后队列为空，重新设置标志域*/
Return(TUUE);
}
7. [题目分析] 根据队列先进先出和栈后进先出的性质，先将非空队列中的元素出队，并压入初始为空的栈中。这时栈顶元素是队列中最后出队的元素。然后将栈中元素出栈，依次插入到初始为空的队列中。栈中第一个退栈的元素成为队列中第一个元素，最后退栈的元素（出队时第一个元素）成了最后入队的元素，从而实现了原队列的逆置。
void Invert(queue Q)
//Q是一个非空队列，本算法利用空栈S和已给的几个栈和队列的ADT函数，将队列Q中的元素逆置。
{makempty(S); //置空栈
while (!isEmpty(Q)) // 队列Q中元素出队
{value=deQueue(Q); push(S,value); }// 将出队元素压入栈中
while(!isEmpty(S)) //栈中元素退栈
{value=pop(S); enQueue(Q,value); }//将出栈元素入队列 Q
}//算法invert 结束
第三章习题 1.按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答： ⑴如进站的车厢序列为123，则可能得到的出站车厢序列是什么？ ⑵如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。（即写出 以“S”表示进栈、以“X”表示出栈的栈操作序列）。 2.设队列中有A、B、C、D、E这5个元素，其中队首元素为A。如果对这个队列重复执行下列4步 操作： （1）输出队首元素； （2）把队首元素值插入到队尾； （3）删除队首元素； （4）再次删除队首元素。 直到队列成为空队列为止，得到输出序列： （1）A、C、E、C、C （2） A、C、E （3） A、C、E、C、C、C （4） A、C、E、C 3.给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？ 4.按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，画出对下列算术表达式求值时操 作数栈和运算符栈的变化过程： A－B＊Ｃ／Ｄ＋Ｅ↑Ｆ 5.试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1& 序列2’ 模式的字符序列。其中序列1和序列2中都不含字符’&’，且序列2是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。 6.假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式且书写 正确的表达式转换为逆波兰式。 7.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针）， 试编写相应的队列初始化、入队列和出队列的算法。 8.要求循环队列不损失一个空间全部都能得到利用, 设置一个标志域tag , 以tag为0或1来区分 头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。
第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.熟悉栈这种特殊线性结构的特性； 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．队列的插入操作是在（）进行。
第一章绪论 一、选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 2 A.结构 B.关系 C.运算 D.算法 2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。 1 A.算法 B.数据元素 C.数据操作 D.逻辑结构 2 A.操作 B.映像 C.存储 D.关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。A.随机存取 B.顺序存取 C.索引存取 D.散列存取 5.算法分析的目的是1，算法分析的两个主要方面其一是指2，其二是指正确性和简单性。1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系 C.可读性和文档性 D.数据复杂性和程序复杂性k 6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。 1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。A.正确 B.不正确 8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。 A.必须连续的 B.部分地址必须连续的 C.一定是不续的D连续不连续都可以 9.以下的叙述中，正确的是。A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。A.正确B.不正确 二、填空题1.数据逻辑结构包括三种类型、和，树形结构和图形结构合称为。2.在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。3.算法的五个重要特性是、、、、。 4.下面程序段的时间复杂度是。 for( i = 0; i < n; i++) for( j = 0; j < m; j++) A[i][j] = 0; 5.下面程序段的时间复杂度是。 i = s = 0; while ( s < n) { i ++; /* i = i +1*/ s += i; /* s = s + i*/ } 6.下面程序段的时间复杂度是。 s = 0; for( i = 0; i < n; i++) for( j = 0; j < n; j++) s += B[i][j]; sum = s; 7.下面程序段的时间复杂度是。 i = 1; while ( i <= n ) i = i * 3;
南京信息工程大学实验（实习）报告 实验（实习）名称栈和队列日期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.顺序栈 3.链栈 4.递归 5.队列、队尾、队头 6.顺序队 7.循环队 8.队满 9.链队10.随机存储结构11.特殊矩阵12.稀疏矩阵13.对称方阵14.上（下）三角矩阵 二、填空题： 1.栈修改的原则是_________或称________，因此，栈又称为________线性表。在栈顶 进行插入运算，被称为________或________，在栈顶进行删除运算，被称为________ 或________。 2.栈的基本运算至少应包括________、________、________、________、________五 种。 3.对于顺序栈，若栈顶下标值top=0,此时，如果作退栈运算，则产生“________”。 4.对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生“________”。 5.一般地，栈和线性表类似有两种实现方法，即________实现和________实现。 6.top=0表示________，此时作退栈运算，则产生“________”；top=sqstack_maxsize-1 表示________，此时作进栈运算，则产生“________”。 7.以下运算实现在顺序栈上的初始化，请在________处用适当的句子予以填充。 int InitStack(SqStackTp *sq) { ________; return(1);} 8.以下运算实现在顺序栈上的进栈，请在________处用适当的语句予以填充。 Int Push(SqStackTp *sq,DataType x) { if(sp->top==sqstack_maxsize-1}{error(“栈满”);return(0);} else{________________: ________________=x; return(1);} } 9.以下运算实现在顺序栈上的退栈，请在________________用适当句子予以填充。 Int Pop(SqStackTp *sq,DataType *x) {if(sp->top==0){error(“下溢”);return(0);} else{*x=________________; ________________; return(1);} } 10. 以下运算实现在顺序栈上判栈空，请在________________处用适当句子予以填充。 Int EmptyStack(SqStackTp *sq) {if(________________) return(1); else return(0); } 11.以下运算实现在顺序栈上取栈顶元素，请在________________处用适当句子予以填充。 Int GetTop(SqStackTp *sq,DataType *x) {if(________________) return(0);
实验二栈和队列 一、实验目的 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
3.1 选择题 第3章线性表的链式存储 （1）两个有序线性表分别具有n个元素与m个元素且n≤m，现将其归并成一个有序表，其最少的比较次数是（ A ）。 A．n B．m C．n? 1D．m + n （2）非空的循环单链表 head 的尾结点（由 p 所指向）满足（ C ）。 A．p->next==NULL B．p==NULL C．p->next==head D．p==head （3）在带头结点的单链表中查找x应选择的程序体是（ C ）。 A．node *p=head->next; while (p && p->info!=x) p=p->next; if (p->info==x) return p else return NULL; B．node *p=head; while (p&& p->info!=x) p=p->next; return p; C．node *p=head->next; while (p&&p->info!=x) p=p->next; return p; D．node *p=head; while (p->info!=x) p=p->next ; return p; （4）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ D ）。 A．必须是连续的C．一定是不连续的B．部分地址必须是连续的D．连续不连续都可以 （5）在一个具有n个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间复杂度是（ B ）。 A．O(1) B．O(n)C．O(n2)D．O(n log2n )（6）用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时（D ）。 A．仅修改队头指针 C．队头、队尾指针都要修改B．仅修改队尾指针 D．队头,队尾指针都可能要修改 （7）若从键盘输入n个元素，则建立一个有序单向链表的时间复杂度为（ B ）。 A．O(n)B．O(n2)C．O(n3)D．O(n× log2n)（8）下面哪个术语与数据的存储结构无关（D）。 A．顺序表B．链表C．散列表D．队列 （9）在一个单链表中，若删除 p 所指结点的后续结点，则执行（ A ）。 A．p->next=p->next->next; B．p=p->next; p->next=p->next->next; C．p->next=p->next; D．p =p->next->next; （10）在一个单链表中，若 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; 3.2 设计一个算法，求一个单链表中的结点个数。 【答】：单链表存储结构定义如下（相关文件：linklist.h）
《数据结构》课程实验报告 实验名称栈和队列实验序号实验日期 姓名院系班级学号 专业指导教师成绩 教师评语 一、实验目的和要求 (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
数据结构第三章习题 3．1 单项选择题 2.一个栈的入栈序列a, b, c, d, e, 则栈的不可能的输出序列是。 A. edcba B. Decba C. Dceab D. abcde 3. 若已知一个栈的入栈序列是1，2，3，………..n, 其输出序列为p1, p2, p3,……,pn, 若p1=n, 则pi为。 . B. n=I C. n- i+1 D.不确定4．栈结构通常采用的两种存储结构是。 A. 顺序存储结构和链表存储结构 B. 散链方式和索引方式 C.链表存储结构和数组 D. 线性存储结构和非线性存储结构5．判定一个栈ST（最多元素为m0）为空的条件是。 A. ST->top<>0 B. ST->top=0 >top<>m0 >top=m0 6．判定一个栈ST（最多元素为m0）为栈满的条件是。 A. ST->top!=0 >top==0 >top!=m0 >top==m0 7.栈的特点是，队列的特点是。 A先进先出 B. 先进后出 8. 一个队列的入栈序列是1，2，3，4，则队列的输出序列是。 A. 4,3,2,1 B. 1,2,3,4 C. 1,4,3,2 D. 3,2,4,1 9. 判定一个队列QU(最多元素为m0)为空的条件是。 >rear- QU->front==m0 >rear- QU->front-1==m0 >front== QU->rear D. QU->front== QU->rear+1
10.判定一个队列QU（最多元素为m0）为满队列的条件是。 >rear- QU->front==m0 >rear- QU->front-1==m0 >front== QU->rear >front== QU->rear+1 11. 判定一个循环队列QU(最多元素为m0)为空的条件是。 A. QU->front== （QU->rear+1）%m0 B. QU->front！= （QU->rear+1）%m0 >front== QU->rear >front！= QU->rear 12. 判定一个循环队列QU（最多元素为m0）为满队列的条件是。 A. QU->front== （QU->rear+1）%m0 B. QU->front！= （QU->rear+1）%m0 >front== QU->rear >front！= QU->rear+1 12. 向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行。 HS->next=s; A. s->next=HS->next; HS->next=s; B. s->next=HS; HS=s; C. s->next=HS; HS=HS->next; 13. 从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行。 A x=HS; HS=HS->next; B. x=HS->data; C. HS=HS->next; x=HS->data;