FOR i :=n DOWNTO 1 DO write(A[i]); writeln ;
END; 【华南师范大学 2000 五、2 (9 分)】
40. 设有一个背包可以放入的物品重量为 S,现有 n 件物品,重量分别为 W1,W2,...,
Wn。问能否从这 n 件物品中选择若干件放入背包,使得放入的重量之和正好是 S。设
布尔函数 Knap(S,n)表示背包问题的解,Wi(i=1,2,...,n)均为正整数,并已顺序存储地
在数组 W 中。请在下列算法的下划线处填空,使其正确求解背包问题。
Knap(S,n)
若 S=0
则 Knap←true
否则若(S<0)或(S>0 且 n<1)
则 Knap←false
否则若 Knap(1) , _=true
则 print(W[n]);Knap ←true
否则 Knap←Knap(2) _ , _
【山东工业大学 1996 五(10 分)1998 二、1 (4 分)】
四 应用题
1. 数组 A[1..8,-2..6,0..6]以行为主序存储,设第一个元素的首地址是 78,每个元素的
长度为 4,试求元素 A[4,2,3]的存储首地址。【厦门大学 1998 五、1 (5 分)】
2. 已知 b 对角矩阵(aij)n*n,以行主序将 b 条对角线上的非零元存储在一维数组中,
每个数据元素占L个存储单元,存储基地址为S,请用 i,j 表示出 aij 的存储位置。【北
方交通大学 1996 三(10 分)】
3. 数组 A 中,每个元素 A[i,j]的长度均为 32 个二进位,行下标从-1 到 9,列下标从 1 到
11,从首地址 S 开始连续存放主存储器中,主存储器字长为 16 位。求:
(1)存放该数组所需多少单元?
(2)存放数组第 4 列所有元素至少需多少单元?
(3)数组按行存放时,元素 A[7,4]的起始地址是多少?
(4)数组按列存放时,元素 A[4,7]的起始地址是多少? 【大连海事大学 1996 四、1 (6
分)】
4.假设按低下标优先存储整型数组 A(-3:8,3:5,-4:0,0:7)时,第一个元素的字节存储地
址是 100,每个整数占 4 个字节,问 A(0,4,-2,5)的存储地址是什么?【清华大学
1996 三】
5.设有三维数组 A[-2:4,0:3,-5:1]按列序存放,数组的起始地址为 1210,试求 A(1,3,-2)
所在的地址。【长沙铁道学院 1997 三、1 (3 分)】
6. 三维数组 A[1..10,-2..6,2..8]的每个元素的长度为 4 个字节,试问该数组要占多少个字
节的存储空间?如果数组元素以行优先的顺序存贮,设第一个元素的首地址是 100,试
求元素 A[5,0,7] 的存贮首地址。
【上海海运学院 1995 三(6 分) 1997 三(8 分)】
7. 设有五对角矩阵 A=(aij)20*20,按特殊矩阵压缩存储的方式将其五条对角线上的元素
存于数组 A[-10:m]中,计算元素 A[15,16]的存储位置。【东北大学 1999 一、2(4 分)】
8.数组 A[0..8, 1..10] 的元素是 6 个字符组成的串,则存放 A 至少需要多少个字节? A
的第 8 列和第 5 行共占多少个字节?若 A 按行优先方式存储,元素 A[8,5]的起始地址与
当 A 按列优先方式存储时的哪个元素的起始地址一致? 【厦门大学 2000 五、3(14%/3
分)】