内容发布更新时间 : 2024/11/6 3:43:13星期一 下面是文章的全部内容请认真阅读。
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) {printf(“队满”; exit(0);) 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)); }//算法结束
（1）Ack(2,1)的计算过程
Ack(2,1)=Ack(1,Ack(2,0)) //因m<>0,n<>0而得 =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而得 （2）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为单链表的表头指针, 链表中存储的都是整型数据，试写出实现下列运算 的递归算法： ① 求链表中的最大整数； ② 求链表的结点个数； ③ 求所有整数的平均值。 #include //链表结点类 class ListNode { friend class List; private: }; class List { private: }; ListNode* List :: NewNode ( const int item ) { } void List :: NewList ( const int retvalue ) { cout << \; cin >> value; while ( value != retvalue ) { //建立链表, 以输入retvalue结束 //提示 first = NULL; int value; ListNode *q; //输入 //输入有效 ListNode *newnode = new ListNode (item); return newnode; //创建新链表结点 ListNode *first, current; int Max ( ListNode *f ); int Num ( ListNode *f ); float Avg ( ListNode *f, int& n ); List ( ) : first(NULL), current (NULL) { } ~List ( ){ } ListNode* NewNode ( const int item ); void NewList ( const int retvalue ); void PrintList ( ); //构造函数 //链表类 int data; //结点数据 //结点指针 ListNode *link; //定义在头文件\中 ListNode ( const int item ) : data(item), link(NULL) { } //构造函数 public: //析构函数 //创建链表结点, 其值为item //建立链表, 以输入retvalue结束 //输出链表所有结点数据 //求链表所有数据的最大值 //求链表中数据个数 //求链表所有数据的平均值 int GetMax ( ) { return Max ( first ); } int GetNum ( ) { return Num ( first ); } float GetAvg ( ) { return Avg ( first ); } } void List :: PrintList ( ) { } int List :: Max ( ListNode *f ) { } int List :: Num ( ListNode *f ) { } float List :: Avg ( ListNode *f , int& n ) { if ( f ->link == NULL ) //递归算法 : 求链表中所有元素的平均值 //链表中只有一个结点, 递归结束条件 //递归算法 : 求链表中结点个数 //空表, 返回0 //否则, 返回后继链表结点个数加1 if ( f == NULL ) return 0; return 1+ Num ( f ->link ); //递归算法 : 求链表中的最大值 //递归结束条件 //在当前结点的后继链表中求最大值 //如果当前结点的值还要大, 返回当前检点值 //否则返回后继链表中的最大值 if ( f ->link == NULL ) return f ->data; int temp = Max ( f ->link ); else return temp; if ( f ->data > temp ) return f ->data; ListNode *p = first; while ( p != NULL ) { cout << p->data << ' '; p = p->link; cout << ‘\\n’; } //输出链表 cout << \; } current->link = NULL; //链尾封闭 q = NewNode ( value ); //建立包含value的新结点 //非空表时, 新结点链入链尾 if ( first == NULL ) first = current = q; else { current->link = q; current = q; } cin >> value; //空表时, 新结点成为链表第一个结点 //再输入 { n = 1; return ( float ) (f ->data ); } else { float Sum = Avg ( f ->link, n ) * n; n++; return ( f ->data + Sum ) / n; } //定义在主文件中 } #include \ int main ( int argc, char* argv[ ] ) { List test; int finished; cout << “输入建表结束标志数据 ：”; cin >> finished; } test.PrintList ( ); //输入建表结束标志数据 //建立链表 //打印链表 test.NewList ( finished ); cout << \test.GetMax ( ); cout << \test.GetNum ( ); cout << \test.GetAve () << '\\n'; printf ( \return 0; 第4章 串、数组和广义表 习题 1．选择题 （1）串是一种特殊的线性表，其特殊性体现在（ ）。 A．可以顺序存储 B．数据元素是一个字符 C．可以链式存储 D．数据元素可以是多个字符若 （2）串下面关于串的的叙述中，（ ）是不正确的？ A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 （3）串“ababaaababaa”的next数组为（ ）。 A．012345678999 B．012121111212 C．011234223456 D．0123012322345 （4）串“ababaabab”的nextval为（ ）。 A．010104101 B．010102101 C．010100011 D．010101011 （5）串的长度是指（ ）。 A．串中所含不同字母的个数 B．串中所含字符的个数 C．串中所含不同字符的个数 D．串中所含非空格字符的个数 （6）假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=（ ）。 A．808 B．818 C．1010 D．1020 （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 （8）设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。 A．13 B．33 C．18 D．40 （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 （10）A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N(N+1)/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（ ）。 A．i(i-1)/2+j B．j(j-1)/2+i C．i(j-i)/2+1 D．j(i-1)/2+1 （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 （12）数组A[0..4,-1..-3,5..7]中含有元素的个数（ ）。 A．55 B．45 C．36 D．16 （13）广义表A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))的值为（ ）。 A．(g) B．(d) C．c D．d （14）广义表((a,b,c,d))的表头是（ ），表尾是（ ）。 A．a B．( ) C．(a,b,c,d) D．(b,c,d) （15）设广义表L=((a,b,c))，则L的长度和深度分别为（ ）。 A．1和1 B．1和3 C．1和2 D．2和3 （1）已知模式串t=‘abcaabbabcab’写出用KMP法求得的每个字符对应的next和nextval函数值。 模式串t的next和nextval值如下： j t串 next[j] nextval[j] 1 2 3 4 5 6 7 8 9 10 11 12 a b c a a b b a b c a b 0 1 1 1 2 2 3 1 2 3 4 5 0 1 1 0 2 1 3 0 1 1 0 5 （2）设目标为t=“abcaabbabcabaacbacba”,模式为p=“abcabaa” ① 计算模式p的naxtval函数值； ② 不写出算法,只画出利用KMP算法进行模式匹配时每一趟的匹配过程。 ① p的nextval函数值为0110132。（p的next函数值为0111232）。 ② 利用KMP(改进的nextval)算法，每趟匹配过程如下： 第一趟匹配： abcaabbabcabaacbacba abcab(i=5,j=5) 第二趟匹配： abcaabbabcabaacbacba abc(i=7,j=3) 第三趟匹配： abcaabbabcabaacbacba a(i=7,j=1) 第四趟匹配： abcaabbabcabaac bacba (成功) abcabaa(i=15,j=8) （3）数组A中，每个元素A[i,j]的长度均为32个二进位,行下标从-1到9，列下标从1到11，从首地址S开始连续存放主存储器中，主存储器字长为16位。求： ① 存放该数组所需多少单元？ ② 存放数组第4列所有元素至少需多少单元？ ③ 数组按行存放时，元素A[7,4]的起始地址是多少？ ④ 数组按列存放时，元素A[4,7]的起始地址是多少？ 每个元素32个二进制位，主存字长16位，故每个元素占2个字长，行下标可平移至1到11。 （1）242 （2）22 （3）s+182 （4）s+142 (4)请将香蕉banana用工具 H( )—Head( )，T( )—Tail( )从L中取出。 L=(apple,(orange,(strawberry,(banana)),peach),pear)