数据结构第一次作业答案
一、单项选择题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号