当前位置:

首页 智能方案

数据结构第一次作业答案

点击数:42更新时间:2010-07-03

  数据结构第一次作业答案

  一、单项选择题1. A     2. D     3. B     4. D     5. C     6. A7. C     8. A     9. A     10. A    11. D    12. D

  二、填空题1. 存储结构    2. 数据结构            3. 继承            4. 数据类型5. 静态        6. LOC(0,0)+(i*n+j)*d  7. (2n-I-1)*I/2+J  8. 169. 删除        10. 不一定             11. 删除

  三、判断题1. 错   2. 错   3. 错   4. 对   5. 对   6. 错   7. 对   8. 对

  四、运算题1. (i - j) * (n - 1) * d解释:    按行存储时与按列存储时,计算A[j]地址的公式分别为        LOC(i,j)=LOC(0,0)+(i*n+j)*d    及  LOC’(i,j)=LOC(0,0)+(j*n+i)*d    两者相减,得         LOC(i,j)–LOC’(i,j)=LOC(0,0)+(i*n+j)*d–LOC(0,0)–(j*n+i)*d                          =(i-j)*(n-1)*d

  2. 41解释:    根据题意,矩阵A中当元素下标I与J满足I≥J时,任意元素A[I][J]在一维数组B中的存放位置为        I * (I + 1) / 2 + J    因此,A[8][5]在数组B中位置为    8 * (8 + 1) / 2 + 5 = 41

  3. 1208解释:    对于二维数组,若第一、第二维的元素个数为m和n,每个元素所占存储字数为d,首地址为LOC(0, 0),则对于任一数组元素A[j],它的存储地址为:        LOC(i, j) = LOC(0, 0) + (i * n + j) * d    根据题意,LOC(8, 4) = LOC(0, 0) + (8 * 6 + 4) * 4 = 1000 + 52 * 4 = 1208

  4.    前序:A,B,D,G,C,E,F    中序:B,G,D,A,E,C,F    按层:A,B,C,D,E,F,G

  5.    先根序列:a,b,c,d,e,f,g,h,i,j

  五、算法分析题1.    功能为: 矩阵相乘,即a[M][N]×b[N][L]→c[M][L]。    时间复杂性为:O(M×N×L)

  2.    算法执行的结果是:函数返回值等于5。该算法即字符串的模式匹配。    3.    计算单链表的长度或计算单链表中结点的个数4.    运行结果:stack

  六、算法设计题1.    template <class T>    void merge ( SeqList<int>& A, SeqList<int>& B, SeqList<int>& C ) {    int m = A.Length( ), n = B.Length( ), mpn = m + n;    if ( mpn > C.maxLength( ) ) {    cerr << “合并后表的长度超出表C的最大允许长度” << endl;    exit (1);    }    int i=0, j=0, k=0, av=A.getData(i), bv=B.getData(j);    while(i<m && j<n) {        if(av<=bv) {C.setData(k++, av); av=A.getData(++i);}            if(av>=bv){C.setData(k++, bv); bv=B.getData(++j);}        }    if(i<m)            while(k<mpn){C.setData(k++,av); av=A.getData(++i);}    else             while(k<mpn){C.setData(k++, bv); bv=B.getData(++j);}}

  2.    while ( p != NULL) {        if(p->data >= min && p->data <=max) {           q->link=p->link; delete p; p=q->link;        }   else {q=p; p=p->link;}    }

  3.// 将x插入至队尾   if (Q.rear == Q.front && Q.tag == 1) return false;   Q.elem[Q.rear] = x;   Q.rear = (Q.rear+1) % M;   if (Q.rear == Q.front) Q.tag = 1;   return true;

  // 删除队头元素   if (Q.front == Q.rear && Q.tag == 0) return false;   x = Q.elem[Q.front];   Q.front = (Q.front+1) % M;   if (Q.front == Q.rear) Q.tag = 0;   return true;


版权所有:赤峰智能教育网 copy 2005-2010总裁:柴春泽常务站长:高颖E-mail: cfccz@263.net 电 话:13704765925(专收短信)站长:赵杰电话:0476-8666066 8668099

技术支持:启天网络蒙公网安备15040202150519号蒙ICP备20002477号蒙网警:150402010196号