A)front=front->next B)rear=rear->next C) rear=front->next D)front=rear-> 6、写出下列程序段的输出结果(其中栈的元素类型 SElemType为char) i Stack S; char y: InitStack(S) Push(S, x): Push(S, 'a): Push(S, y): Pop(s, x) Push(s, 't'): Push(S, x): Pop (S, x ): Push(S, 's") while(! StackEmpty(S))(Pop(s, y): printf(y): 1 7、写出以下程序段的输出结果(队列中的元素类型 QElemType为char) id @ ueue Q; char x=’e Queue(Q) EnQueue( Q,'h): EnQueue(Q, r ) EnQueue( Q, y): DeQueue(Q, x) EnQueue(Q, x): DeQueue(Q, x): EnQueue(Q, ' a) while(! QueueEmpty(Q))[ DeQueue(, y): printf (y): 1 printf(x) 8、若栈用顺序存储表示,其栈的元素类型为整型,类型定义如下 #define maXsize 1000 typedef struct i int elem[ MAXSIZE];/用来存放栈元素的数组,下标从0开始 Int top //指向栈顶位置的域,栈底为位置0 STack 请补全以下栈操作函数:(用C语言) (1)判断栈S是否为空栈:若为空,则返回1,不为空则返回0 int StackEmpty (Stack S) else (2)入栈操作:若栈满,则返回0,不满,则入栈,返回1 int push( Stack*p,inte)//p为指向栈的指针,e为待入栈的元素 ) return(0);//栈满,则返回0 =e;//栈 p->top+=l /栈顶位置变化 return (1) 、简述栈、队列和线性表的差别和联系。 参考解答:1、C2、D3、C4、C5、A6、 stack7、char return(O p>top>=MAXSIZE-1 D->elemlp->topl 本章其它习题解答请参看本系网站
6 A) front=front->next; B)rear=rear->next; C) rear=front->next; D)front=rear->next; 6、写出下列程序段的输出结果（其中栈的元素类型 SElemType 为 char） void main() { Stack S; char x,y; InitStack(S); x=’c’; y=’k’; Push(S,x); Push(S,’a’); Push(S,y); Pop(S,x); Push(S,’t’); Push(S,x); Pop(S,x); Push(S,’s’); while(!StackEmpty(S)){Pop(S,y); printf(y); }; printf(x); } 7、写出以下程序段的输出结果（队列中的元素类型 QElemType 为 char）。 void main() { Queue Q; char x=’e’,y=’c’; InitQueue(Q); EnQueue(Q,’h’); EnQueue(Q,’r’); EnQueue(Q,y); DeQueue(Q,x); EnQueue(Q,x); DeQueue(Q,x); EnQueue(Q,’a’); while(!QueueEmpty(Q)){ DeQueue(Q,y); printf(y);} printf(x); } 8、若栈用顺序存储表示，其栈的元素类型为整型，类型定义如下： #define MAXSIZE 1000 typedef struct{ int elem[MAXSIZE]; //用来存放栈元素的数组，下标从 0 开始 int top; //指向栈顶位置的域，栈底为位置 0 }Stack; 请补全以下栈操作函数：（用 C 语言） （1）判断栈 S 是否为空栈：若为空，则返回 1，不为空则返回 0 int StackEmpty(Stack S){ if( )return (1); else ; } （2）入栈操作：若栈满，则返回 0，不满，则入栈，返回 1 int Push(Stack *p,int e){ //p 为指向栈的指针，e 为待入栈的元素 if( )return(0);//栈满，则返回 0 =e; //入栈 p->top+=1; //栈顶位置变化 return(1); } 9、简述栈、队列和线性表的差别和联系。 参考解答：1、C 2、D 3、C 4、C 5、A 6、stack 7、char 8、S.top==0 或!(S.top) return(0) p->top>=MAXSIZE-1 p->elem[p->top] 本章其它习题解答请参看本系网站
第4章串 要求:逻辑结构和顺序存储表示算法(顺序串) 1、简述空串和空格串(或称空格字符串)的区别 2、已知下列字符串 a=THIS’,f= A SAMPLE’,c='600D’,d='NE,b=’‘, S=Concat(a, Concat(SubString(f, 2, 7), Concat(b, SubString(a, 3, 2)))) t=Replace(f, SubString(f, 3, 6), c), u=Concat(SubString(c, 3, 1), d) g='IS, v=Concat(s, Concat(b, Concat(t, Concat(b, u)))) 其中 Concat(a,b)为将串b联接到串a之后,其他操作与教材P71页串的抽象数据类型中定义的操作 致,试问:s,t,v, Strength(s), Index(v,g), Index(u,g)各是什么? 3、已知:s=(XYZ)+*,t=(X+Z)*Y。试用联接、求子串和置换等操作,将s转化为t 4、编写算法,求串s所含不同字符的总数和每种字符的个数 5、两个字符串相等的充要条件是 和 设字符串S1= ABCDEF,S2=PQRS°’,则运算S= CONCAT(SUB(S1,2,LEN(S2),SUB(S1,LEN(S2),2)) 后的串值为 参考解答: 1、空串是指长度为零的串,而空格串是指串中字符是空格的字符串 2、s=‘ THIS SAMPLE IS’t= A GOODU='ONE’v= THIS SAMPLE IS A GOOD ONE’14,3,0 Replace(s, Substring(s, 3, 5), Concat(Substring(3, 6, 1), Concat(Substring(s, 4, 2) Concat(Substring(s, 7, 1), Substring(s, 3, 1))))) 4、算法1 void count(String T) i StrCopy (s, T) mFStrlength(S for(i=l: i<=m: i++) Substring(Sub1, S, i, 1) if(! StrCompare(Subl, #'))continue I Substring (Sub2, S, j, 1) if(!StrCompare(Sub1, Sub2)) Replace(S,sub1,"#”) nutt printf(Sub1, n) printf(num) 5、长度相等每一对应位置字符相等 第5章数组和广义表 要点 7
7 第 4 章 串 要求：逻辑结构和顺序存储表示算法（顺序串） 1、简述空串和空格串（或称空格字符串）的区别。 2、已知下列字符串 a=’THIS’, f=’A SAMPLE’, c=’GOOD’, d=’NE’, b=’ ‘, s=Concat(a,Concat(SubString(f,2,7),Concat(b,SubString(a,3,2)))), t=Replace(f,SubString(f,3,6),c), u=Concat(SubString(c,3,1),d), g=’IS’, v=Concat(s,Concat(b,Concat(t,Concat(b,u)))) 其中 Concat(a,b)为将串 b 联接到串 a 之后，其他操作与教材 P71 页串的抽象数据类型中定义的操作 一致，试问：s,t,v,StrLength(s),Index(v,g),Index(u,g)各是什么？ 3、已知：s=’(XYZ)+*’, t=’(X+Z)*Y’。试用联接、求子串和置换等操作，将 s 转化为 t。 4、编写算法，求串 s 所含不同字符的总数和每种字符的个数。 5、两个字符串相等的充要条件是 和 。 6、设字符串 S1=’ABCDEF’, S2=’PQRS’, 则运算 S=CONCAT(SUB(S1,2,LEN(S2)),SUB(S1,LEN(S2),2)) 后的串值为 。 参考解答： 1、空串是指长度为零的串，而空格串是指串中字符是空格的字符串。 2、s= ‘THIS SAMPLE IS’ t=’A GOOD’ u=’ONE’ v=’THIS SAMPLE IS A GOOD ONE’ 14, 3, 0 3 、 Replace(s,Substring(s,3,5) ,Concat(Substring(3,6,1) ,Concat(Substring(s,4,2), Concat(Substring(s,7,1),Substring(s,3,1))))) 4、算法 1： void count(String T) { StrCopy(S,T); m=Strlength(S); num=0; for(i=1;i<=m;i++) { n=1; Substring(Sub1,S,i,1); if(!StrCompare(Sub1,’#’))continue; for(j=i+1;j<=m;j++) { Substring(Sub2,S,j,1); if(!StrCompare(Sub1,Sub2)) n++; } Replace(S,sub1,’#’); num++; printf(Sub1,n); } printf(num); } 5、长度相等 每一对应位置字符相等 6、BCDEDE 第 5 章 数组和广义表 要点：