第5章数组和广义表自测题含答案一、单选题1•假设有二维数组A6-8,每个元素用相邻的6个字节存储，存储器按字节编址已知A的起始存储位置(基地址)为1000,则数组A的体积(存储量)为288B;末尾元素A57的第一个字节地址为1282;若按行存储时，元素A口的第一个字节地址为(8+4)X6+1000=1072;若按列存储时，元素A47的第一个字节地址为(6X7+4)X6+1000)=1276〖00年计算机系考研题〗设数组a[1…60,1…70]的基地址为2048,每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为_89502. 答：不考虑0行0列，利用列优先公式：LOC(aij)=LOC(ac1,c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L得：LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2=8950三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的_行下标、—列下标和_元素值3. 求下列广义表操作的结果：(1) GetHead【((a,b),(c,d))】===_a,b);〃头元素不必加括号(2) GetHead【GetTail【((a,b),(c,d))】】===(c,d);(3) GetHead【GetTail【GetHead【((a,b),(c,d))】】】===b;GetTail【GetHead【GetTail【((a,b),(c,d))】】】===(d);二、单选题(A)1.〖01年计算机系考研题〗假设有60行70列的二维数组a[1-60,1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为。
无第0行第0列元素)A.16902B.16904C.14454D.答案A,B,C均不对答：此题与填空题第8小题相似57列X60行+31行)X2字节+10000=16902(B)2.设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分(如下图所示)按行序存放在一维数组B[1,n(n-1)/2]中，对下三角部分中任一元素a,j(i
若按列存储，则A[7,1]和A[2,4]的第一个字节的地址分别是D和E供选择的答案：A〜E:①28②44③76④92⑤108⑥116⑦132⑧176⑨184⑩188答案：ABCDE=8,3,5,1,6【94程P12】有一个二维数组A，行下标的范围是1到6,列下标的范围是0到7,每个数组元素用相邻的6个字节存储，存储器按字节编址那么，这个数组的体积是A个字节假设存储数组元素A[1,0]的第一个字节的地址是0,则存储数组A的最后一个元素的第一个字节的地址是B若按行存储，则A[2,4]的第一个字节的地址是C若按列存储，则A[5,7]的第一个字节的地址是D供选择的答案A〜D:①12②66③72④96⑤114⑥120⑦156⑧234⑨276⑩282(11)283(12)288答案：ABCD=12,10,3,9三、简答题【其他教材】已知二维数组Am,m采用按行优先顺序存放，每个元素占K个存储单元,并且第一个元素的存储地址为Loc(a11)，请写出求Loc(aij)的计算公式如果采用列优先顺序存放呢？1. 解：公式教材已给出，此处虽是方阵，但行列公式仍不相同；按行存储的元素地址公式是：Loc(aij)=Loc(a11)+[(i-1)*m+(j-1)]*K按列存储的元素地址公式是：Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K【全国专升本资格考试】递归算法比非递归算法花费更多的时间，对吗？为什么？答：不一定。
时间复杂度与样本个数n有关，是指最深层的执行语句耗费时间，而递归算法与非递归算法在最深层的语句执行上是没有区别的，循环的次数也没有太大差异仅仅是确定循环是否继续的方式不同，递归用栈隐含循环次数，非递归用循环变量来显示循环次数而已1. 四、计算题(P604-18)用三元组表表示下列稀疏矩阵:(1)P0000000]00000000100000-2]030008000000900000000000000000060000(2)0050000000000000000000000005[000030_Z0000000一解：参见填空题4.三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有885323368546785812个数据项，分别表示该元素的行下标所以(1)可列表为：66416-2259435653列下标和元素值(2)可列表为：2. (P604-19)下列各三元组表分别表示一个稀疏矩阵，试写出它们的稀疏矩阵6461222112(1)313444536455'6116一[437解：(1)为6X4矩阵，非零元素有6个2)为4X5矩阵，非零元素有5个020000700120003000-0—00-^五、算法设计题1.【严题集5.18⑤】试设计一个算法，将数组An中的元素A[0]至A[n-1]循环右移k位,并要求只用一个元素大小的附加存储，元素移动或交换次数为O(n)解：分析:要把A的元素循环右移k位，则A[0]移至A[k],A[k]移至A[2k]……直到最终回到A[0].然而这并没有全部解决问题,因为有可能有的元素在此过程中始终没有被访问过,而是被跳了过去•分析可知，当n和k的最大公约数为p时,只要分别以A[0],A[1],...A[p-1]为起点执行上述算法,就可以保证每一个元素都被且仅被右移一次,从而满足题目要求.也就是说,A的所有元素分别处在p个"循环链"上面.举例如下:n=15,k=6,则p=3.第一条链:A[0]->A[6],A[6]->A[12],A[12]->A[3],A[3]->A[9],A[9]->A[0]./已“顺便”移动了A[6]、A[12]…第二条链:A[1]->A[7],A[7]->A[13],A[13]->A[4],A[4]->A[10],A[10]->A[1].第三条链:A[2]->A[8],A[8]->A[14],A[14]->A[5],A[5]->A[11],A[11]->A[2].恰好使所有元素都右移一次.虽然未经数学证明,但作者相信上述规律应该是正确的.程序如下：voidRSh(intA[n],intk)〃把数组A的元素循环右移k位，只用一个辅助存储空间{for(i=1;i<=k;i++)if(n%i==0&&k%i==0)p=i;//求n和k的最大公约数pfor(i=0;i