front=rear时为队空，(rear+1)%m=front 为队满。约定队头端入队向下标小的方向发展，队尾端入队向下标大的方向发展。
[算法描述] ①
#define M 队列可能达到的最大长度 typedef struct {elemtp data[M]; int front,rear; }cycqueue; ②
elemtp delqueue ( cycqueue Q)
//Q是如上定义的循环队列，本算法实现从队尾删除，若删除成功，返回被删除元素，
否则给出出错信息。
{if (Q.front==Q.rear) { cout<<\队列空\Q.rear=(Q.rear-1+M)%M; //修改队尾指针。 return(Q.data[(Q.rear+1+M)%M]); //返回出队元素。 }//从队尾删除算法结束
void enqueue (cycqueue Q, elemtp x)
// Q是顺序存储的循环队列，本算法实现“从队头插入”元素x。 {if (Q.rear==(Q.front-1+M)%M) { cout<<\队满\ Q.data[Q.front]=x; //x 入队列 Q.front=(Q.front-1+M)%M; //修改队头指针。 }// 结束从队头插入算法。
（9）已知Ackermann函数定义如下:
① 写出计算Ack(m,n)的递归算法，并根据此算法给出出Ack(2,1)的计算过程。 ② 写出计算Ack(m,n)的非递归算法。 [算法描述] int Ack(int m,n) {if (m==0) return(n+1);
else if(m!=0&&n==0) return(Ack(m-1,1)); else return(Ack(m-1,Ack(m,m-1)); }//算法结束
① Ack(2,1)的计算过程
24
Ack(2,1)= Ack(1,Ack(2,0)) //因m<>0,n<>0而得 ②
int Ackerman(int m, int n) {int akm[M][N];int i,j;
for(j=0;j {akm[i][0]=akm[i-1][1]; for(j=1;j akm[i][j]=akm[i-1][akm[i][j-1]]; } return(akm[m][n]); }//算法结束 （10）已知f为单链表的表头指针, 链表中存储的都是整型数据，试写出实现下列运算的递归算法： ① 求链表中的最大整数； ② 求链表的结点个数； ③ 求所有整数的平均值。 [算法描述] ① int GetMax(LinkList p) { = Ack(1,Ack(1,1)) //因m<>0,n=0而得 = Ack(1,Ack(0,Ack(1,0))) // 因m<>0,n<>0而得 = Ack(1,Ack(0,Ack(0,1))) // 因m<>0,n=0而得 = Ack(1,Ack(0,2)) // 因m=0而得 = Ack(1,3) // 因m=0而得 = Ack(0,Ack(1,2)) //因m<>0,n<>0而得 = Ack(0,Ack(0,Ack(1,1))) //因m<>0,n<>0而得 = Ack(0,Ack(0,Ack(0,Ack(1,0)))) //因m<>0,n<>0而得 = Ack(0,Ack(0,Ack(0,Ack(0,1)))) //因m<>0,n=0而得 = Ack(0,Ack(0,Ack(0,2))) //因m=0而得 = Ack(0,Ack(0,3)) //因m=0而得 = Ack(0,4) //因n=0而得 =5 //因n=0而得 if(!p->next) else 25 return p->data; } { } int max=GetMax(p->next); return p->data>=max ? p->data:max; ② int GetLength(LinkList p) { } if(!p->next) else { } return GetLength(p->next)+1; return 1; ③ double GetAverage(LinkList p , int n) { } if(!p->next) else { } double ave=GetAverage(p->next,n-1); return (ave*(n-1)+p->data)/n; return p->data; 26 第4章 串、数组和广义表 1．选择题 （1）串是一种特殊的线性表，其特殊性体现在（ ）。 A．可以顺序存储 B．数据元素是一个字符 C．可以链式存储 D．数据元素可以是多个字符若 答案：B （2）串下面关于串的的叙述中，（ ）是不正确的？ A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 答案：B 解释：空格常常是串的字符集合中的一个元素，有一个或多个空格组成的串成为空格 串，零个字符的串成为空串，其长度为零。 （3）串“ababaaababaa”的next数组为（ ）。 A．012345678999 B．012121111212 C．011234223456 D．0123012322345 答案：C （4）串“ababaabab”的nextval为（ ）。 A．010104101 B．010102101 C．010100011 D．010101011 答案：A （5）串的长度是指（ ）。 A．串中所含不同字母的个数 B．串中所含字符的个数 C．串中所含不同字符的个数 D．串中所含非空格字符的个数 答案：B 解释：串中字符的数目称为串的长度。 （6）假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=（ ）。 A．808 B．818 C．1010 D．1020 答案：B 解释：以行序为主，则LOC[5,5]=[（5-1）*100+（5-1）]*2+10=818。 （7）设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为（ ）。 A．BA+141 B．BA+180 C．BA+222 D．BA+225 答案：B 解释：以列序为主，则LOC[5,8]=[（8-1）*8+（5-1）]*3+BA=BA+180。 （8）设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。 27 A．13 B．32 C．33 D．40 答案：C （9）若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1..(n(n+1))/2]中，则在B中确定aij（i A．i*(i-1)/2+j B．j*(j-1)/2+i C．i*(i+1)/2+j D．j*(j+1)/2+i 答案：B （10）二维数组A的每个元素是由10个字符组成的串，其行下标i=0,1,?,8,列下标 j=1,2,?,10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。 A．A[8,5] B．A[3,10] C. A[5,8] D．A[0,9] 答案：B 解释：设数组从内存首地址M开始顺序存放，若数组按行先存储，元素A[8,5]的起 始地址为：M+[（8-0）*10+（5-1）]*1=M+84；若数组按列先存储，易计算出元素A[3,10]的起始地址为：M+[（10-1）*9+（3-0）]*1=M+84。故选B。 （11）设二维数组A[1.. m，1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i,j]在一维数组B中的下标为（ ）。 A．(i-1)*n+j B．(i-1)*n+j-1 C．i*(j-1) D．j*m+i-1 答案：A 解释：特殊值法。取i=j=1，易知A[1,1]的的下标为1，四个选项中仅有A选项能 确定的值为1，故选A。 （12）数组A[0..4,-1..-3,5..7]中含有元素的个数（ ）。 A．55 B．45 C．36 D．16 答案：B 解释：共有5*3*3=45个元素。 （13）广义表A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))的值为（ ）。 A．(g) B．(d) C．c D．d 答案：D 解释：Tail(A)=(b,(c,d),(e,(f,g)))；Tail(Tail(A))=( (c,d),(e,(f,g)))； Head(Tail(Tail(A)))= (c,d)；Tail(Head(Tail(Tail(A))))=(d)；Head(Tail(Head(Tail(Tail(A)))))=d。 （14）广义表((a,b,c,d))的表头是（ ），表尾是（ ）。 A．a B．( ) C．(a,b,c,d) D．(b,c,d) 答案：C、B 解释：表头为非空广义表的第一个元素，可以是一个单原子，也可以是一个子表， ((a,b,c,d))的表头为一个子表(a,b,c,d)；表尾为除去表头之外，由其余元素构成的表，表为一定是个广义表，((a,b,c,d))的表尾为空表( )。 （15）设广义表L=((a,b,c))，则L的长度和深度分别为（ ）。 A．1和1 B．1和3 C．1和2 D．2和3 答案：C 28