第三章参考答案
一、填空题
1． 线性，任何，栈顶，队尾，队头 2． 先进后出（FILO），队尾，队头，先进先出（FIFO） 3． top==0，top==m 4． 23541
5． 前一个位置，所在位置，m-1
分析：在顺序循环队列中约定头指针front和尾指针rear所指向的位置，是牺牲掉一个存储单元而方便表示队列空和队列满的条件，因此顺序循环队列中实际可用的存储单元只有m-1个。 6． (rear+1)%m==front，rear==front 7． O(1)
8． 返回地址，返回地址
二、选择题 1. (3)
分析：设栈的输入序列是1、2、3、??、n，输出序列的第一个元素是n，则输出序列必定是n、n-1、n-2、??、1，因此第i个输出元素是n+1-i。 2. (3) 3. (3) 4. (2) 5. (2) 6. (3) 7. (1) 8. (4)
?rear?front??rear?front分析：顺序循环队列中的元素个数=?，整理合并可写成
rear?front?m??rear?front?(rear-front+m)%m。
9. (3) 10. (2)
三、算法设计题
1. 设有两个顺序栈S1和S2共享一个存储区S[0：m-1]，为了尽量利用存储空间减少溢出的可能性，采用栈顶相向、迎面增长的存储方式，要求分别设计两个栈的入栈和出栈操作。
分析：本题算法思想是引入形式参数flag，当形式参数flag的值为1时表示对栈1进行操作，flag的值为2时表示对栈2进行操作。
typedef struct {int s[m]; int top1; int top2;} sqstack; void push(sqstack &stack , int x,int flag) {
if (stack.top1+1==stack.top2) printf(“stack is full\\n”); else {
if (flag==1) {stack.top1++; stack.s[stack.top1]=x;}
else if(flag==2){stack.top2--; stack.s[stack.top2]=x;}else printf(“input error\\n”); } }
11
void pop(sqstack &stack , int &y, int flag) {
if (flag==1)
if(stack.top1<0) printf(“empty\\n”); else { y=stack.s[stack.top1];stack.top1--; } else if(flag==2)
if(stack.top2>=m) printf(“empty\\n”); else { y=stack.s[stack.top2];stack.top2--; } else printf(“input error\\n”); }
2. 设计算法判断表达式中的圆括号是否配对出现。
分析：本题的算法思想是顺序扫描表达式，当扫描到左圆括号时进栈而扫描到右圆括号时出栈，如果扫描到右圆括号时不能出栈或扫描表达式结束时栈中仍有左圆括号则意味表达式中圆括号不匹配，否则表达式中圆括号匹配。
typedef struct {int s[m]; int top;} sqstack; int matchbracket() {
char ch; sqstack stack; stack.top= -1; do {
ch=getchar();
if (ch==?(?) {stack.top=stack.top+1; stack.s[stack.top]=ch;}
else if (ch==?)?) if (stack.top<0) return(0); else stack.top=stack.top-1; }while(ch!= ?#?);
if (stack.top<0) return(1); else return(0); }
3. 设用一个单向循环链表来表示队列（也称链式循环队列），该队列只设一个队尾指针rear，不设队头指针front，要求设计出该队列的入队列和出队列操作。
typedef struct node {int data; struct node *next;} lklist; void inlkqueue(lklist *&rear, int x) {
lklist *p;
p=(lklist *) malloc(sizeof(lklist)); p->data=x;
if (rear==0) {rear=p; rear->next=rear;}else {p->next=rear->next; rear->next=p; rear=p;} }
void outlkqueue(lklist *&rear, int &y) {
lklist *p;
if (rear==0) printf(“queue is empty\\n”);
else if {rear->next==rear} {y=rear->data; rear=0; }
else { p=rear->next; y=p->data; rear->next=p->next; free(p);} }
4. 假设以一个一维向量q[0：m-1]作为顺序循环队列的存储空间，同时设变量rear和len分别指示顺序循环队列中的队尾元素的位置和实际队列中的元素个数，要求设计出该队列的入队列和出队列操作。
分析：本题中出队列的算法思路是设置一个临时变量front指向当前队列中队头元素的实际位置，考虑到表达式queue.rear+1-queue.len的值可能为负，因此设置front的值为(queue.rear+1-queue.len+m)%m。
typedef struct{ int q[m]; int rear; int len; } sqqueue; void insqqueue(sqqueue &queue, int x) {
if (queue.len==m) printf(“queue is full\\n”);
12
else {queue.rear=(queue.rear+1)%m; queue.q[queue.rear]=x;queue.len++;}
}
void outsqqueue(sqqueue &queue, int *y) {
int front;
if (queue.len==0) printf(“queue is emptyl\\n”);
else {front=queue.rear+1-queue.len+m}%m; y=queue.q[queue.front];queue.len--;} }
5. 编写一个算法解决约瑟夫（Josephus）环问题。其问题是：设有n个人围坐在一张圆桌周围，现从第一个人开始从1报数，报到k的人出离开圆桌，接着从下一个人从1开始重新报数，??，以此类推，直到他们都离开圆桌，求出他们离开圆桌的先后顺序。
分析：本题的算法思路是设置变量sum和num，其中变量 sum表示当前已经离开圆桌的人数个数，变量num表示当前的报数。
void Josephus( int n, int k) {
int i,num,sum,r[100]; for(i=0;i for(sum=num=i=0; sum if (r[i]!=-1) {num++; if (num % k==0) {printf(\} 13 第四章 字符串和数组 一、填空题 1. 设字符串S1=“ABCDEF”，S2=“PQRS”，则运算S=CONCAT(SUB(S1，2，LEN(S2))，SUB(S1，LEN(S2)， 2)的结果为S=_________________。 2. 判断两个字符串相等的充要条件是____________________________。 3. 下列程序段实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。 int index(char s[ ], char t[ ]) { i=j=0; while(i 4. 设二维数组A有m行n列，每个数组元素占L个字节的存储单元，按行的顺序存放在m*n个连续的存储 单元中。已知A[0][0]的地址为1000，则A[i][j]的地址为______________________________________。 5. 设三维数组A[3][4][5]中的每个元素占10个字节的存储单元，按行的顺序存放在一组连续的存储空间中。 已知A[0][0][0]的首地址为1000，则数组元素A[1][2][3]的首地址为___________________________。 6. 设对称矩阵A有n行n列，每个数组元素占L个字节的存储单元，按行的顺序将下三角矩阵中的元素（包 括对角线上的元素）存放在n*(n+1)/2个存储单元中，已知A[0][0]的地址为1000，则A[i][j]（i>=j）的地址为___________________________。 7. 设有n行n列的三对角矩阵A，每个数组元素占L个字节的存储单元，按照从上到下从左到右的顺序将三 条对角线上的元素存放在3n-2个连续的存储单元中，已知A[0][0]的地址为1000，则三对角线上元素A[i][j]的地址为_________________。 ?0?3?8. 已知稀疏矩阵A=??0??000000?00???，则A的三元组表为__________________。 ?15?00??2 二、算法设计题 1. 设用顺序存储结构存储字符串S1和S2，要求设计一个函数完成对两个字符串的比较。若S1>S2时则返回 正数；若S1=S2时则返回0；若S1 2. 用顺序存储结构实现在字符串S中删除所有其值等于ch的字符的算法。 3. 设单链表中存放n个字符，试设计算法判断字符串是否关于中心对称。 14 第四章参考答案 一、填空题 1. “ABCDDE” 2. 字符串的长度相等且对应位置上的字符相等 3. i-j+1，0 分析：在查找子串位置的过程中，当发现s[i]!=t[j]时需要重新调整指针i和j的值后继续查找。指针j的值肯定调整到子串的开始位置0，而指针i的值则相应调整到i-j的后一个位置i-j+1。 4. 1000+(i*n+j)*L 5. 1330 分析：A[1][2][3]的首地址=1000+(1*4*5+2*5+3)*10=1330。 6. 1000+(i*(i+1)/2+j)*L 分析：A[i][j]的首地址=1000+(1+2+??+i+j)*L=1000+(i*(i+1)/2+j)*L。 7. (2*i+j)*L ?j*L????i?0分析：A[i][j]的首地址=?，经合并整理可得A[i][j] ((i?1)*3?2?(j?i?1))*L?(2*i?j)*L???i?0?的首地址=(2*i+j)*L。 ?0??1?2??2?20232??3? ?1??5??8. 二、算法设计题 1. 设用顺序存储结构存储字符串S1和S2，要求设计一个函数完成对两个字符串的比较。若S1>S2时则返回正数；若S1=S2时则返回0；若S1 int comparestring(char s1[ ], char s2[ ]) { int i; for(i=0;s1[i]!=0;i++) if (s1[i]!=s2[i]) break; return(s1[i]-s2[i]); } 2. 用顺序存储结构实现在字符串S中删除所有其值等于ch的字符的算法。 void deletestring(char s[ ],char ch) { int i=0,j; while(s[i]!=0) if (s[i]==ch) {for(j=i+1; s[j]!=0; j++) s[j-1]=s[j]; s[j-1]=0;}else i++; } 3. 设计一个算法判断字符串S中的字符是否关于中心对称。 typedef struct {char s[m]; int top;} sqstack; int stringsymmetry(char s[ ]) { int i; sqstack stack; stack.top= -1; for(i=0;s[i]!=0;i++) {stack.top++; stack.s[stack.top]=s[i];} for(i=0;s[i]!=0;i++) if (s[i]==stack.s[stack.top]) stack.top=stack.top-1; else return(0); return(1); } 15