三、简答题(每小题5分,共15分) 1.【其他教材】已知二维数组Am,m采用按行优先顺序存放,每个元素占K个存储单元,并且第一个元 素的存储地址为Loc(al),请写出求Loc(aj)的计算公式。如果采用列优先顺序存放呢? 解:公式教材已给出,此处虽是方阵,但行列公式仍不相同 按行存储的元素地址公式是:Loc(aj)=Loc(a1)+[(i-1)*m+(-1)]*K 按列存储的元素地址公式是:Loc(aj)=Loc(a1)+[(-1)*m+(-1)]*K 2.【全国专升本资格考试】递归算法比非递归算法花费更多的时间,对吗?为什么? 答:不一定。时间复杂度与样本个数n有关,是指最深层的执行语句耗费时间,而递归算法与非递归算法 在最深层的语句执行上是没有区别的,循环的次数也没有太大差异。仅仅是确定循环是否继续的方式不同, 递归用栈隐含循环次数,非递归用循环变量来显示循环次数而已 四、计算题(每题5分,共20分) 1.设s=' LAMA STUDENT,t='GOOD,q= WORKER,求 Replace(s,' STUDENT,q)和 Concat( SubString(s, 6, 2), Concat(t, SubString(s, 7, 8) 解:① Replace(s,' STUDENT,q)=’ LAMA WORKER ②因为 SubString(s,6,2)=‘A'; Substring(s,7,8)=‘ STUDENT Concat(t, SubString(s, 7, 8))=GOOD STUDENT BT LA Concat( SubString(s, 6, 2), Concat(t, SubString(s, 7, 8))='A GOOD STUDENT 2.(P604-18)用三元组表表示下列稀疏矩阵: 00000000 00000-2 03000800 000090 00000000 000000 (1) 00060000 005000 00000000 000000 00000005 000030 20000000 解:参见填空题4.三元素组表中的每个结点对应于稀疏矩阵的一个非零元素,它包含有三个数据项,分 别表示该元素的行下标 下标和_元素亻 所以(1)可列表为: (2)可列表为: 833578 538652 246 66535 3.(P604-19)下列各三元组表分别表示一个稀疏矩阵,试写出它们的稀疏矩阵,3 三、简答题（每小题 5 分，共 15 分） 1. 【其他教材】已知二维数组 Am,m 采用按行优先顺序存放，每个元素占 K 个存储单元，并且第一个元 素的存储地址为 Loc(a11)，请写出求 Loc(aij)的计算公式。如果采用列优先顺序存放呢？ 解：公式教材已给出，此处虽是方阵，但行列公式仍不相同； 按行存储的元素地址公式是： Loc(aij)= Loc(a11) +[ (i-1)*m+(j-1) ] * K 按列存储的元素地址公式是： Loc(aij)= Loc(a11) +[ (j-1)*m+(i-1) ] * K 2.【全国专升本资格考试】递归算法比非递归算法花费更多的时间，对吗？为什么？ 答：不一定。时间复杂度与样本个数 n 有关，是指最深层的执行语句耗费时间，而递归算法与非递归算法 在最深层的语句执行上是没有区别的，循环的次数也没有太大差异。仅仅是确定循环是否继续的方式不同， 递归用栈隐含循环次数，非递归用循环变量来显示循环次数而已。 四、计算题（每题 5 分，共 20 分） 1. 设 s=’I AM A STUDENT’, t=’GOOD’, q=’WORKER’, 求 Replace(s,’STUDENT’,q) 和 Concat(SubString(s,6,2), Concat(t,SubString(s,7,8)))。 解：① Replace(s,’STUDENT’,q)＝’I AM A WORKER’ ② 因为 SubString(s,6,2)＝‘A ’；SubString(s,7,8)＝‘ STUDENT’ Concat(t,SubString(s,7,8))＝’GOOD STUDENT’ 所以 Concat(SubString(s,6,2), Concat(t,SubString(s,7,8)))＝‘AGOOD STUDENT’ 2. （P60 4-18）用三元组表表示下列稀疏矩阵：                         20000000 00000005 00000000 00060000 00000000 03000800 00000000 00000000 (1)                   − 00003 0 00000 0 00500 0 00000 0 00009 0 00000 2 (2) 解：参见填空题 4. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分 别表示该元素的 行下标 、 列下标 和 元素值 。 所以（1）可列表为： （2）可列表为： 8 8 5 3 2 3 3 6 8 5 4 6 7 8 5 8 1 2 3. （P60 4-19）下列各三元组表分别表示一个稀疏矩阵，试写出它们的稀疏矩阵。 6 6 4 1 6 -2 2 5 9 4 3 5 6 5 3