数据结构第5章例题与答案-计算机等级考试-233网校
第 5 章 数组和广义表
一、选择题
1.设有一个10阶的对称矩阵a，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。【燕山大学 2001 一、2 （2分）】
a. 13 b. 33 c. 18 d. 40
2. 有一个二维数组a[1:6，0:7] 每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组的体积是（①）个字节。假设存储数组元素a[1，0]的第一个字节的地址是0，则存储数组a的最后一个元素的第一个字节的地址是（②）。若按行存储，则a[2，4]的第一个字节的地址是（③）。若按列存储，则a[5，7]的第一个字节的地址是（④）。就一般情况而言，当（⑤）时，按行存储的a[i，j]地址与按列存储的a[j，i]地址相等。供选择的答案：【上海海运学院 1998 二、2 （5分）】
①-④： a．12 b. 66 c. 72 d. 96 e. 114 f. 120
g. 156 h. 234 i. 276 j. 282 k. 283 l. 288
⑤： a．行与列的上界相同 b. 行与列的下界相同
c. 行与列的上、下界都相同 d. 行的元素个数与列的元素个数相同
3. 设有数组a[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址ba开始顺序存放，当用以列为主存放时，元素a[5，8]的存储首地址为( )。
a. ba+141 b. ba+180 c. ba+222 d. ba+225
【南京理工大学 1997 一、8 （2分）】
4. 假设以行序为主序存储二维数组a=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则loc[5，5]=（ ）。【福州大学 1998 一、10 (2分)】
a. 808 b. 818 c. 1010 d. 1020
5. 数组a[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素a[5，5]的地址是( )。【南京理工大学 2001 一、13 （1.5分）】
a. 1175 b. 1180 c. 1205 d. 1210
6. 有一个二维数组a[0:8,1:5],每个数组元素用相邻的4个字节存储，存储器按字节编址，假设存储数组元素a[0,1]的第一个字节的地址是0，存储数组a的最后一个元素的第一个字节的地址是（ ① ）。若按行存储，则a[3,5]和 a[5,3]的第一个字节的地址是（ ② ） 和（ ③ ）。若按列存储，则a[7,1]和a[2,4]的第一个字节的地址是（ ④ ）和（ ⑤ ）。【上海海运学院 1996 二、1 （5分）】
①-⑤:a.28 b.44 c.76 d.92 e.108 f.116 g.132 h.176 i.184 j.188
7. 将一个a[1..100，1..100]的三对角矩阵，按行优先存入一维数组b[1‥298]中，a中元素a6665（即该元素下标i=66，j=65），在b数组中的位置k为（ ）。供选择的答案：
a. 198 b. 195 c. 197 【北京邮电大学 1998 二、5 （2分）】
8. 二维数组a的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中（ ）内的正确答案。
（1）存放a至少需要（ ）个字节；
（2）a的第8列和第5行共占（ ）个字节；
（3）若a按行存放，元素a[8，5]的起始地址与a按列存放时的元素（ ）的起始地址一致。
供选择的答案：
（1）a. 90 b. 180 c. 240 d. 270 e. 540
（2）a. 108 b. 114 c. 54 d. 60 e. 150
（3）a. a[8,5] b. a[3,10] c. a[5,8] d. a[0,9]
【山东工业大学 2000 三、1 （4分）】 【山东大学 1998 三、1 (4分)】
9. 二维数组a的每个元素是由6个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。若a按行先存储，元素a[8,5]的起始地址与当a按列先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。【西安电子科技大学 1998 一、2 （2分）】
a. a[8,5] b. a[3,10] c. a[5,8] d. a[0,9]
10. 若对n阶对称矩阵a以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组b［1..(n(n+1))/2］中，则在b中确定aij（i<j）的位置k的关系为( )。
a. i*(i-1)/2+j b. j*(j-1)/2+i c. i*(i+1)/2+j d. j*(j+1)/2+i
【北京航空航天大学 2000 一、2 （2分）】
11. 设a是n*n的对称矩阵，将a的对角线及对角线上方的元素以列为主的次序存放在一维数组b[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在b中的位置为( )。
a. i(i-l)/2+j b. j(j-l)/2+i c. j(j-l)/2+i-1 d. i(i-l)/2+j-1
【南京理工大学 1999 一、9（2分）】
12. a[n，n]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组t[n（n+1）/2]中，则对任一上三角元素a[i][j]对应t[k]的下标k是（ ）。【青岛大学 2002 二、6 （2分）】
a. i（i-1）/2+j b. j（j-1）/2+i c. i（j-i）/2+1 d. j（i-1）/2+1
13. 设二维数组a[1.. m，1.. n]（即m行n列）按行存储在数组b[1.. m*n]中，则二维数组元素a[i，j]在一维数组b中的下标为( )。【南京理工大学 1998 一、2 （2分）】
a.（i-1）*n+j b.（i-1）*n+j-1 c. i*（j-1） d. j*m+i-1
14. 有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（ ）。【南京理工大学 1999 二、8 （2分）】
a. 60 b. 66 c. 18000 d. 33
15. 数组a[0..4,-1..-3,5..7]中含有元素的个数（ ）。【中山大学 1998 二、5（2分）】
a. 55 b. 45 c. 36 d. 16
16. 用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j 沿链移动的操作为( )。【南京理工大学 2001 一、16（1.5分）】
a. j=r[j].next b. j=j+1 c. j=j->next d. j=r[j]-> next
17. 对稀疏矩阵进行压缩存储目的是（ ）。【北京工商大学 2001 一、1 (3分)】
a．便于进行矩阵运算 b．便于输入和输出 c．节省存储空间 d．降低运算的时间复杂度
18. 已知广义表l=（（x,y,z），a，（u，t，w）），从l表中取出原子项t的运算是（ ）。
a. head（tail（tail（l））） b. tail（head（head（tail（l））））
c. head（tail（head（tail（l）））） d. head（tail(head（tail（tail（l）））)）
【北京邮电大学 1998 二、4（2分）】
19. 已知广义表ls＝((a,b,c),(d,e,f)),运用head和tail函数取出ls中原子e的运算是( )。
a. head(tail(ls)) b. tail(head(ls))
c. head(tail(head(tail(ls))) d. head(tail(tail(head(ls))))
【西安电子科技大学 2001应用一、3（2分）】
20. 广义表a=(a,b,(c,d),(e,(f,g))),则下面式子的值为（ ）。【北京邮电大学1999一、2（2分）】
head(tail(head(tail(tail(a)))))
a. (g) b. (d) c. c d. d
21. 已知广义表: a=(a,b), b=(a,a), c=(a,(b,a),b), 求下列运算的结果:
tail(head(tail(c))) =( )。【长沙铁道学院 1998 三、4 (2分)】
a.（a） b. a c. a d. (b) e. b f. (a)
22. 广义表运算式tail(((a,b),(c,d)))的操作结果是（ ）。【西安电子科技大学1998 一、4（2分）】
a. (c,d) b. c,d c. ((c,d)) d. d
23. 广义表l=（a，（b，c）），进行tail（l）操作后的结果为（ ）。【中山大学 1999 一、10】
a. c b. b，c c.（b，c） d.（（b，c））
24. 广义表（（a,b,c,d））的表头是（ ），表尾是（ ）。【青岛大学 2002 二、7 （2分）】
a. a b.（） c.（a,b,c,d） d.（b,c,d）
25. 广义表（a,(b,c),d,e）的表头为（ ）。【中山大学 1998 二、6（2分）】
a. a b. a,(b,c) c. (a,(b,c)) d. (a)
26. 设广义表l=（（a,b,c）），则l的长度和深度分别为（ ）。【武汉大学 2000 二、9】
a. 1和1 b. 1和3 c. 1和2 d. 2和3
27. 下面说法不正确的是( )。 【南京理工大学 2001 一、3 （1.5分）】
a. 广义表的表头总是一个广义表 b. 广义表的表尾总是一个广义表
c. 广义表难以用顺序存储结构 d. 广义表可以是一个多层次的结构
二、判断题
1. 数组不适合作为任何二叉树的存储结构。（ ）【南京航空航天大学 1995 五、2 （1分）】
2. 从逻辑结构上看，n维数组的每个元素均属于n个向量。（ ）
【东南大学 2001 一、2 （1分）】【中山大学 1994 一、2 （2分）】
3. 稀疏矩阵压缩存储后，必会失去随机存取功能。（ ）【中科院软件所 1997 一、1 （1分）】
4. 数组是同类型值的集合。（ ）【上海海运学院 1996 一、3（1分）1999 一、4（1分）】
5. 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（ ）
【上海交通大学 1998 一、5】
6. 一个稀疏矩阵am*n采用三元组形式表示， 若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了am*n的转置运算。（ ） 【西安交通大学 1996 二、8 (3分)】
7. 二维以上的数组其实是一种特殊的广义表。（ ） 【北京邮电大学 2002 一、5 （1分）】
8. 广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（ ）
【南京航空航天大学 1996 六、2 （1分）】
9. 若一个广义表的表头为空表，则此广义表亦为空表。（ ）
【中科院软件所 1997 一、8（1分）】 【长沙铁道学院 1998 一、8 (1分)】
10. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。（ ）
【合肥工业大学 2000 二、3 （1分）】
11. 所谓取广义表的表尾就是返回广义表中最后一个元素。（ ）【合肥工业大学 2001 二、3 （1分）】
12. 广义表的同级元素（直属于同一个表中的各元素）具有线性关系。（ ）
【华南理工大学 2002 一、9（1分）】
13. 对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。（ ）
【华南理工大学 2002 一、10（1分）】
14. 一个广义表可以为其它广义表所共享。（ ） 【山东大学 2001 一、2（1分）】
三、 填空题
1. 数组的存储结构采用_______存储方式。【中山大学 1998 一、6（1分）】
2. 设二维数组a[-20..30,-30..20], 每个元素占有4 个存储单元, 存储起始地址为200.如按行优先顺序存储,则元素 a[25,18]的存储地址为__（1）_；如按列优先顺序存储,则元素a[-18,-25]的存储地址为__（2）_。 【北方交通大学 1999 二、3（4分）】
3. 设数组a[1..50,1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45,68]的存储地址为_（1）_;若以列序为主序顺序存储，则元素a[45,68]的存储地址为_（2）_。
【华中理工大学 2000 一、5（2分）】
4. 将整型数组a[1..8，1..8]按行优先次序存储在起始地址为1000的连续的内存单元中，则元素a[7，3]的地址是：_______。【合肥工业大学 1999 三、4（2分）】
5. 二维数组a[4][5][6]（下标从0开始计，a有4*5*6个元素），每个元素的长度是2，则a[2][3][4]的地址是____。(设a[0][0][0]的地址是1000,数据以行为主方式存储)
【南京理工大学2000 二、11（1.5分）】
6. 设有二维数组a[0..9,0..19],其每个元素占两个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素a[6,6]存储地址为_______。 【北京工商大学 2001 二、5 （4分）】
7. 已知数组a[0..9,0..9]的每个元素占5个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素a[6，8]的地址为_______。【合肥工业大学 2001 三、4（2分）】
8. 已知二维数组a[1..10，0..9]中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，a[5，9]的地址是：_______。【厦门大学 2002 六、5 （4分）】
9. 用一维数组b与列优先存放带状矩阵a中的非零元素a[i,j] (1≤i≤n,i-2≤j≤i+2),b中的第8个元素是a 中的第_（1）_行，第_（2）_列的元素。【北京邮电大学 2001 二、3（4分）】
10. 设数组a[0..8,1..10],数组中任一元素a[i,j]均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么
（l） 存放该数组至少需要的单元数是_______;
（2） 存放数组的第8列的所有元素至少需要的单元数是_______;
（3） 数组按列存储时，元素a[5,8]的起始地址是_______。【中国矿业大学 2000 一、4（4分）】
11．设n行n列的下三角矩阵a已压缩到一维数组b[1..n*（n+1）/2]中，若按行为主序存储，则a[i,j]对应的b中存储位置为_______。 【武汉大学 2000 一、1】
12. n阶对称矩阵a满足a[i][j]=a[j][i],i,j=1..n,，用一维数组t存储时，t的长度为__(1)______，当i=j，a[i][j]=t[(2)],i>j,a[i][j]=t[(3)],i<j,a[i][j]=t[(4)]。【青岛大学 2001 六、1（3分）】
13．己知三对角矩阵a【1..9,1..9】的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为1000的连续的内存单元中，则元素a[7,8]的地址为______。【合肥工业大学 2000 三、4（2分）】
14. 设有一个10阶对称矩阵a采用压缩存储方式（以行为主序存储：a11=1），则a85 的地址为_______。
【西安电子科技大学 1999软件 一、3 （2分）】
15. 所谓稀疏矩阵指的是_______。【厦门大学 2001 一、2 （14%/5分）】
16. 对矩阵压缩是为了_______。 【北京理工大学 2000 二、3（2分）】
17. 上三角矩阵压缩的下标对应关系为：_______。【福州大学 1998 二、6 (2分)】【南京大学 1999】
18. 假设一个15阶的上三角矩阵a按行优先顺序压缩存储在一维数组b中，则非零元素a9,9在b中的存储位置k=_______。（注：矩阵元素下标从1开始）【北京工商大学 2001 二、1 （4分）】
19．设下三角矩阵a=
如果按行序为主序将下三角元素ai j (i,j)存储在一个一维数组b[ 1..n(n+1)/2]中，对任一个三角矩阵元素aij ,它在数组b中的下标为_______。【北方交通大学 2001 二、3】
20. 当广义表中的每个元素都是原子时，广义表便成了_______。【长沙铁道学院 1998 二、8 (2分)】
21. 广义表的表尾是指除第一个元素之外，_______。 【中山大学 1998 一、7 （1分）】
22. 广义表简称表，是由零个或多个原子或子表组成的有限序列，原子与表的差别仅在于 (1)____。为了区分原子和表，一般用 (2)____表示表，用 (3)_____表示原子。一个表的长度是指 (4)__，而表的深度是指__(5)__【山东工业大学 2000 一、3（3分）】 【山东大学 1998 一、2 (3分)】
23. 广义表的_______ 定义为广义表中括弧的重数。【重庆大学 2000 一、5】
24．设广义表l=((),()), 则head(l)是(1)___；tail(l)是(2)____；l的长度是(3)___；深度是 (4)__。
【中科院计算所 1998 一、2（4分）】【中国科技大学 1998 一、2（4分）】
25. 已知广义表a=(9,7,( 8,10,(99)),12)，试用求表头和表尾的操作head( )和tail( )将原子元素99从a中取出来。 【西安交通大学 1996 四、5 (5分)】
26. 广义表的深度是_______。【北京轻工业学院 2000 一、1（2分）】
27. 广义表(a,(a,b),d,e,((i,j),k))的长度是（1）_，深度是（2）_。【山东大学 2001 三、9 (2分)】
【西安电子科技大学 2001软件 一、5 （2分）】 【哈尔滨工业大学 2001 一、2 （2分）】
28. 已知广义表ls=(a，(b，c，d)，e),运用head和tail函数取出ls中原子b的运算是_______。
【燕山大学 2001 二、2 （3分）】
29. 广义表a=（（（a，b），（c，d，e））），取出a中的原子e的操作是: _______。
【合肥工业大学 1999 三、5（2分）】
30. 设某广义表h=（a，（a,b,c）） ，运用head函数和tail函数求出广义表h中某元素b的运算式_______。
【北京科技大学 1997 一、5】
31. 广义表a((( ),(a,(b),c)))，head(tail(head(tail(head(a))))等于 。
【合肥工业大学 2000 三、5（2分）】
32. 广义表运算式head(tail(((a,b,c),(x,y,z))))的结果是_______。
【西安电子科技大学 1999软件 一、9（2分）】
33. 已知广义表a=（（（a，b），（c），（d，e））），head（tail（tail（head（a））））的结果是_______。
【合肥工业大学 2001 三、5 （2分）】
34. 利用广义表的gethead和gettail操作，从广义表l=（（apple，pear），（banana，orange））中分离出原子banana的函数表达式是_______。 【山东大学 2001 三、6 (2分)】
35. 已知a数组元素共5个，依次为12，10，5，3，1；b数组元素共4个，依次为4,6,8,15，则执行如下所示的过程语句sort后得到c数组各元素依次为15,12,10,8,6,5,4,3,1；数组a,b,c的长度分别为l=5,m=4,n=9请在程序中方框内填入正确的成分，完成上述要求。
procedure sort;
var i, j, k, x: integer; d: array[1..m] of integer;
begin
for i:=1 to m do d[i]:=(1) ;
i:=1; j:=1; k:=1;
while (i<=l) and (j<=m) do
begin
if a[i]>d[j] then begin(2) ; (3) _end
else begin (4)__; (5) __end;
c[k]:=x; (6)
end;
while(7) _do
begin c[k]:=a[i]; k:=k+1; i:=i+1；end;
while(8) _do
begin c[k]:=d[j]; k:=k+1; j:=j+1；end;
end. {sort} 【上海交通大学 1998 七 (12分)】
36. 下列程序段search(a,n,k)在数组a的前n(n>=1)个元素中找出第k(1<=k<=n)小的值。这里假设数组a中各元素的值都不相同。
#define maxn 100
int a[maxn],n,k;
int search_c(int a[], int n, int k)
{int low, high, i, j, m, t;
k--,;low=0 ;high=n-1;
do {i=low; j=high ; t=a[low];
do{while (i<j && t<a[j]) j--;
if (i<j) a[i++]=a[j];
while (i<j && t>=a[i]) i++
if (i<j) a[j--]=a[i];
} while (i<j);
a[i]=t;
if (1) ;
if (i<k) low= (2) ; else high= (3) ;
}while(4) _;
return(a[k]);
} 【上海大学 1999 一、1（8分）】
37. 完善下列程序，每小题在pascal语言（a）和c语言（b）中任选一题。下面是一个将广义表逆置的过程。例如原来广义表为（（a,b）,c,（d,e）），经逆置后为：（（e,d）,c,（b,a））。
（a）算法的pascal语言过程描述（编者略）：（b）算法的c语言过程描述：
typedef struct glistnode
{int tag;
struct glistnode *next;
union{char data;
struct{struct glistnode *hp,*tp;}ptr;
}val;
}*glist,gnode;
glist reverse(p)
glist p;
{glist q,h,t,s;
if(p==null) q=null;
else
{if(1) { q=(glist)malloc(sizeof(gnode)); q->tag=0;
q->val.data=p->val.data; }
else {(2)
if (3)
{t=reverse(p->val.ptr.tp); s=t;
while(s->val.ptr.tp!=null) s=s->val.ptr.tp;
s->val.ptr.tp=(glist)malloc(sizeof(gnode));
s=s->val.ptr.tp;s->tag=1;s->val.ptr.tp=null;
s->val.ptr.hp=h; (4) __ }
else {q=(glist)malloc(sizeof(gnode));q->tag=1;
q->val.ptr.tp=null; (5) ; }
}
}
return(q);
}
【上海大学 2002 六、3 （10分）】
38. 完善下列程序，每小题在pascal语言（a）和c语言（b）中任选一题。下面的程序将数列1,2,3,…,n*n,依次按蛇型方式存放在二维数组a[1..n,1..n]中。即 (示意圖编者略)。
（a）算法的pascal 语言程序描述（编者略）：（b）算法的c语言程序描述：
#define nmax 10
#include “stdio.h”
main()
{ int i,j,n,k,p,q,m;
int a [nmax][nmax];
scanf(“%d”,&n);
m=1;
for(k=1；(1) ；k++)
{if（k<n） q=k； else(2) __;
for(p=1;p<=q;p++)
{if(3) {i=q-p+1；j=p；}
else{i=p；j=q-p+1；}
if(4) {i=i+n-q；j=j+n-q；}
a[i][j]=m；(5) _;
}
for（i=1；i<=n;i++）
{ for（j=1；j<=n；j++）
printf（“%4d”,a[i][j]）;printf(“\n”);
}
}
} 【上海大学 2002 六、1 （10分）】
18. 数组 h[ 1：1000] 中存放着1000个大小不同的正整数;
（1） 选择一分类算法使能最快地得到其中10个最大的数，简要说明理由；
（2） 编写一程序seek() ，执行该程序时，在命令行中提供二个参数；
seek a n<enter> 表示需打印h[ ]中n个最大数。
seek i n<enter> 表示需打印h[ ]中n个最小数。 【浙江大学 1994 八 (18分)】
19．已知两个定长数组，它们分别存放两个非降序有序序列，请编写程序把第二个数组序列中的数逐个插入到前一个数组序列中，完成后两个数组中的数分别有序（非降序）并且第一数组中所有的数都不大于第二个数组中的任意一个数。注意，不能另开辟数组，也不能对任意一个数组进行排序操作。例如，
第一个数组为：4,12,28
第二个数组为：1,7,9,29,45
输出结果为：1,4,7--------------第一个数组
9,12,28,29,45---------第二个数组 【上海大学 1998 四 （20分）】
20. 设数组a[1..n]中，a[n-2k+1..n-k]和[n-k+1..n]中元素各自从小到大排好序，试设计一个算法使a[n-2k+1..n]按从小到大次序排好序。并分析算法所需的计算时间。【福州大学 1998 四、3 (10分)】
21. 设a[1..100]是一个记录构成的数组，b[1..100]是一个整数数组，其值介于1至100之间，现要求按b[1..100]的内容调整a中记录的次序，比如当b[1]=ll时，则要求将a[1]的内容调整到a[11]中去。规定可使用的附加空间为o(1)。【中科院计算所 2000 七（15分）】
22. 给定有m个整数的递增有序数组a[1..m]和有n个整数的递减有序数组b[1..n]，试写出算法:将数组a和b归并为递增有序数组c[l..m+n]。(要求：算法的时间复杂度为o(m+n))
【华中理工大学 2000 八、1（10分）】
23．在数组 a[1..n]中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个。【南京理工大学 1998 七、2 （7分）】
一、选择题
1.设有一个10阶的对称矩阵a，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。【燕山大学 2001 一、2 （2分）】
a. 13 b. 33 c. 18 d. 40
2. 有一个二维数组a[1:6，0:7] 每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组的体积是（①）个字节。假设存储数组元素a[1，0]的第一个字节的地址是0，则存储数组a的最后一个元素的第一个字节的地址是（②）。若按行存储，则a[2，4]的第一个字节的地址是（③）。若按列存储，则a[5，7]的第一个字节的地址是（④）。就一般情况而言，当（⑤）时，按行存储的a[i，j]地址与按列存储的a[j，i]地址相等。供选择的答案：【上海海运学院 1998 二、2 （5分）】
①-④： a．12 b. 66 c. 72 d. 96 e. 114 f. 120
g. 156 h. 234 i. 276 j. 282 k. 283 l. 288
⑤： a．行与列的上界相同 b. 行与列的下界相同
c. 行与列的上、下界都相同 d. 行的元素个数与列的元素个数相同
3. 设有数组a[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址ba开始顺序存放，当用以列为主存放时，元素a[5，8]的存储首地址为( )。
a. ba+141 b. ba+180 c. ba+222 d. ba+225
【南京理工大学 1997 一、8 （2分）】
4. 假设以行序为主序存储二维数组a=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则loc[5，5]=（ ）。【福州大学 1998 一、10 (2分)】
a. 808 b. 818 c. 1010 d. 1020
5. 数组a[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素a[5，5]的地址是( )。【南京理工大学 2001 一、13 （1.5分）】
a. 1175 b. 1180 c. 1205 d. 1210
6. 有一个二维数组a[0:8,1:5],每个数组元素用相邻的4个字节存储，存储器按字节编址，假设存储数组元素a[0,1]的第一个字节的地址是0，存储数组a的最后一个元素的第一个字节的地址是（ ① ）。若按行存储，则a[3,5]和 a[5,3]的第一个字节的地址是（ ② ） 和（ ③ ）。若按列存储，则a[7,1]和a[2,4]的第一个字节的地址是（ ④ ）和（ ⑤ ）。【上海海运学院 1996 二、1 （5分）】
①-⑤:a.28 b.44 c.76 d.92 e.108 f.116 g.132 h.176 i.184 j.188
7. 将一个a[1..100，1..100]的三对角矩阵，按行优先存入一维数组b[1‥298]中，a中元素a6665（即该元素下标i=66，j=65），在b数组中的位置k为（ ）。供选择的答案：
a. 198 b. 195 c. 197 【北京邮电大学 1998 二、5 （2分）】
8. 二维数组a的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中（ ）内的正确答案。
（1）存放a至少需要（ ）个字节；
（2）a的第8列和第5行共占（ ）个字节；
（3）若a按行存放，元素a[8，5]的起始地址与a按列存放时的元素（ ）的起始地址一致。
供选择的答案：
（1）a. 90 b. 180 c. 240 d. 270 e. 540
（2）a. 108 b. 114 c. 54 d. 60 e. 150
（3）a. a[8,5] b. a[3,10] c. a[5,8] d. a[0,9]
【山东工业大学 2000 三、1 （4分）】 【山东大学 1998 三、1 (4分)】
9. 二维数组a的每个元素是由6个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。若a按行先存储，元素a[8,5]的起始地址与当a按列先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。【西安电子科技大学 1998 一、2 （2分）】
a. a[8,5] b. a[3,10] c. a[5,8] d. a[0,9]
10. 若对n阶对称矩阵a以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组b［1..(n(n+1))/2］中，则在b中确定aij（i<j）的位置k的关系为( )。
a. i*(i-1)/2+j b. j*(j-1)/2+i c. i*(i+1)/2+j d. j*(j+1)/2+i
【北京航空航天大学 2000 一、2 （2分）】
11. 设a是n*n的对称矩阵，将a的对角线及对角线上方的元素以列为主的次序存放在一维数组b[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在b中的位置为( )。
a. i(i-l)/2+j b. j(j-l)/2+i c. j(j-l)/2+i-1 d. i(i-l)/2+j-1
【南京理工大学 1999 一、9（2分）】
12. a[n，n]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组t[n（n+1）/2]中，则对任一上三角元素a[i][j]对应t[k]的下标k是（ ）。【青岛大学 2002 二、6 （2分）】
a. i（i-1）/2+j b. j（j-1）/2+i c. i（j-i）/2+1 d. j（i-1）/2+1
13. 设二维数组a[1.. m，1.. n]（即m行n列）按行存储在数组b[1.. m*n]中，则二维数组元素a[i，j]在一维数组b中的下标为( )。【南京理工大学 1998 一、2 （2分）】
a.（i-1）*n+j b.（i-1）*n+j-1 c. i*（j-1） d. j*m+i-1
14. 有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（ ）。【南京理工大学 1999 二、8 （2分）】
a. 60 b. 66 c. 18000 d. 33
15. 数组a[0..4,-1..-3,5..7]中含有元素的个数（ ）。【中山大学 1998 二、5（2分）】
a. 55 b. 45 c. 36 d. 16
16. 用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j 沿链移动的操作为( )。【南京理工大学 2001 一、16（1.5分）】
a. j=r[j].next b. j=j+1 c. j=j->next d. j=r[j]-> next
17. 对稀疏矩阵进行压缩存储目的是（ ）。【北京工商大学 2001 一、1 (3分)】
a．便于进行矩阵运算 b．便于输入和输出 c．节省存储空间 d．降低运算的时间复杂度
18. 已知广义表l=（（x,y,z），a，（u，t，w）），从l表中取出原子项t的运算是（ ）。
a. head（tail（tail（l））） b. tail（head（head（tail（l））））
c. head（tail（head（tail（l）））） d. head（tail(head（tail（tail（l）））)）
【北京邮电大学 1998 二、4（2分）】
19. 已知广义表ls＝((a,b,c),(d,e,f)),运用head和tail函数取出ls中原子e的运算是( )。
a. head(tail(ls)) b. tail(head(ls))
c. head(tail(head(tail(ls))) d. head(tail(tail(head(ls))))
【西安电子科技大学 2001应用一、3（2分）】
20. 广义表a=(a,b,(c,d),(e,(f,g))),则下面式子的值为（ ）。【北京邮电大学1999一、2（2分）】
head(tail(head(tail(tail(a)))))
a. (g) b. (d) c. c d. d
21. 已知广义表: a=(a,b), b=(a,a), c=(a,(b,a),b), 求下列运算的结果:
tail(head(tail(c))) =( )。【长沙铁道学院 1998 三、4 (2分)】
a.（a） b. a c. a d. (b) e. b f. (a)
22. 广义表运算式tail(((a,b),(c,d)))的操作结果是（ ）。【西安电子科技大学1998 一、4（2分）】
a. (c,d) b. c,d c. ((c,d)) d. d
23. 广义表l=（a，（b，c）），进行tail（l）操作后的结果为（ ）。【中山大学 1999 一、10】
a. c b. b，c c.（b，c） d.（（b，c））
24. 广义表（（a,b,c,d））的表头是（ ），表尾是（ ）。【青岛大学 2002 二、7 （2分）】
a. a b.（） c.（a,b,c,d） d.（b,c,d）
25. 广义表（a,(b,c),d,e）的表头为（ ）。【中山大学 1998 二、6（2分）】
a. a b. a,(b,c) c. (a,(b,c)) d. (a)
26. 设广义表l=（（a,b,c）），则l的长度和深度分别为（ ）。【武汉大学 2000 二、9】
a. 1和1 b. 1和3 c. 1和2 d. 2和3
27. 下面说法不正确的是( )。 【南京理工大学 2001 一、3 （1.5分）】
a. 广义表的表头总是一个广义表 b. 广义表的表尾总是一个广义表
c. 广义表难以用顺序存储结构 d. 广义表可以是一个多层次的结构
二、判断题
1. 数组不适合作为任何二叉树的存储结构。（ ）【南京航空航天大学 1995 五、2 （1分）】
2. 从逻辑结构上看，n维数组的每个元素均属于n个向量。（ ）
【东南大学 2001 一、2 （1分）】【中山大学 1994 一、2 （2分）】
3. 稀疏矩阵压缩存储后，必会失去随机存取功能。（ ）【中科院软件所 1997 一、1 （1分）】
4. 数组是同类型值的集合。（ ）【上海海运学院 1996 一、3（1分）1999 一、4（1分）】
5. 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（ ）
【上海交通大学 1998 一、5】
6. 一个稀疏矩阵am*n采用三元组形式表示， 若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了am*n的转置运算。（ ） 【西安交通大学 1996 二、8 (3分)】
7. 二维以上的数组其实是一种特殊的广义表。（ ） 【北京邮电大学 2002 一、5 （1分）】
8. 广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（ ）
【南京航空航天大学 1996 六、2 （1分）】
9. 若一个广义表的表头为空表，则此广义表亦为空表。（ ）
【中科院软件所 1997 一、8（1分）】 【长沙铁道学院 1998 一、8 (1分)】
10. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。（ ）
【合肥工业大学 2000 二、3 （1分）】
11. 所谓取广义表的表尾就是返回广义表中最后一个元素。（ ）【合肥工业大学 2001 二、3 （1分）】
12. 广义表的同级元素（直属于同一个表中的各元素）具有线性关系。（ ）
【华南理工大学 2002 一、9（1分）】
13. 对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。（ ）
【华南理工大学 2002 一、10（1分）】
14. 一个广义表可以为其它广义表所共享。（ ） 【山东大学 2001 一、2（1分）】
三、 填空题
1. 数组的存储结构采用_______存储方式。【中山大学 1998 一、6（1分）】
2. 设二维数组a[-20..30,-30..20], 每个元素占有4 个存储单元, 存储起始地址为200.如按行优先顺序存储,则元素 a[25,18]的存储地址为__（1）_；如按列优先顺序存储,则元素a[-18,-25]的存储地址为__（2）_。 【北方交通大学 1999 二、3（4分）】
3. 设数组a[1..50,1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45,68]的存储地址为_（1）_;若以列序为主序顺序存储，则元素a[45,68]的存储地址为_（2）_。
【华中理工大学 2000 一、5（2分）】
4. 将整型数组a[1..8，1..8]按行优先次序存储在起始地址为1000的连续的内存单元中，则元素a[7，3]的地址是：_______。【合肥工业大学 1999 三、4（2分）】
5. 二维数组a[4][5][6]（下标从0开始计，a有4*5*6个元素），每个元素的长度是2，则a[2][3][4]的地址是____。(设a[0][0][0]的地址是1000,数据以行为主方式存储)
【南京理工大学2000 二、11（1.5分）】
6. 设有二维数组a[0..9,0..19],其每个元素占两个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素a[6,6]存储地址为_______。 【北京工商大学 2001 二、5 （4分）】
7. 已知数组a[0..9,0..9]的每个元素占5个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素a[6，8]的地址为_______。【合肥工业大学 2001 三、4（2分）】
8. 已知二维数组a[1..10，0..9]中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，a[5，9]的地址是：_______。【厦门大学 2002 六、5 （4分）】
9. 用一维数组b与列优先存放带状矩阵a中的非零元素a[i,j] (1≤i≤n,i-2≤j≤i+2),b中的第8个元素是a 中的第_（1）_行，第_（2）_列的元素。【北京邮电大学 2001 二、3（4分）】
10. 设数组a[0..8,1..10],数组中任一元素a[i,j]均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么
（l） 存放该数组至少需要的单元数是_______;
（2） 存放数组的第8列的所有元素至少需要的单元数是_______;
（3） 数组按列存储时，元素a[5,8]的起始地址是_______。【中国矿业大学 2000 一、4（4分）】
11．设n行n列的下三角矩阵a已压缩到一维数组b[1..n*（n+1）/2]中，若按行为主序存储，则a[i,j]对应的b中存储位置为_______。 【武汉大学 2000 一、1】
12. n阶对称矩阵a满足a[i][j]=a[j][i],i,j=1..n,，用一维数组t存储时，t的长度为__(1)______，当i=j，a[i][j]=t[(2)],i>j,a[i][j]=t[(3)],i<j,a[i][j]=t[(4)]。【青岛大学 2001 六、1（3分）】
13．己知三对角矩阵a【1..9,1..9】的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为1000的连续的内存单元中，则元素a[7,8]的地址为______。【合肥工业大学 2000 三、4（2分）】
14. 设有一个10阶对称矩阵a采用压缩存储方式（以行为主序存储：a11=1），则a85 的地址为_______。
【西安电子科技大学 1999软件 一、3 （2分）】
15. 所谓稀疏矩阵指的是_______。【厦门大学 2001 一、2 （14%/5分）】
16. 对矩阵压缩是为了_______。 【北京理工大学 2000 二、3（2分）】
17. 上三角矩阵压缩的下标对应关系为：_______。【福州大学 1998 二、6 (2分)】【南京大学 1999】
18. 假设一个15阶的上三角矩阵a按行优先顺序压缩存储在一维数组b中，则非零元素a9,9在b中的存储位置k=_______。（注：矩阵元素下标从1开始）【北京工商大学 2001 二、1 （4分）】
19．设下三角矩阵a=
如果按行序为主序将下三角元素ai j (i,j)存储在一个一维数组b[ 1..n(n+1)/2]中，对任一个三角矩阵元素aij ,它在数组b中的下标为_______。【北方交通大学 2001 二、3】
20. 当广义表中的每个元素都是原子时，广义表便成了_______。【长沙铁道学院 1998 二、8 (2分)】
21. 广义表的表尾是指除第一个元素之外，_______。 【中山大学 1998 一、7 （1分）】
22. 广义表简称表，是由零个或多个原子或子表组成的有限序列，原子与表的差别仅在于 (1)____。为了区分原子和表，一般用 (2)____表示表，用 (3)_____表示原子。一个表的长度是指 (4)__，而表的深度是指__(5)__【山东工业大学 2000 一、3（3分）】 【山东大学 1998 一、2 (3分)】
23. 广义表的_______ 定义为广义表中括弧的重数。【重庆大学 2000 一、5】
24．设广义表l=((),()), 则head(l)是(1)___；tail(l)是(2)____；l的长度是(3)___；深度是 (4)__。
【中科院计算所 1998 一、2（4分）】【中国科技大学 1998 一、2（4分）】
25. 已知广义表a=(9,7,( 8,10,(99)),12)，试用求表头和表尾的操作head( )和tail( )将原子元素99从a中取出来。 【西安交通大学 1996 四、5 (5分)】
26. 广义表的深度是_______。【北京轻工业学院 2000 一、1（2分）】
27. 广义表(a,(a,b),d,e,((i,j),k))的长度是（1）_，深度是（2）_。【山东大学 2001 三、9 (2分)】
【西安电子科技大学 2001软件 一、5 （2分）】 【哈尔滨工业大学 2001 一、2 （2分）】
28. 已知广义表ls=(a，(b，c，d)，e),运用head和tail函数取出ls中原子b的运算是_______。
【燕山大学 2001 二、2 （3分）】
29. 广义表a=（（（a，b），（c，d，e））），取出a中的原子e的操作是: _______。
【合肥工业大学 1999 三、5（2分）】
30. 设某广义表h=（a，（a,b,c）） ，运用head函数和tail函数求出广义表h中某元素b的运算式_______。
【北京科技大学 1997 一、5】
31. 广义表a((( ),(a,(b),c)))，head(tail(head(tail(head(a))))等于 。
【合肥工业大学 2000 三、5（2分）】
32. 广义表运算式head(tail(((a,b,c),(x,y,z))))的结果是_______。
【西安电子科技大学 1999软件 一、9（2分）】
33. 已知广义表a=（（（a，b），（c），（d，e））），head（tail（tail（head（a））））的结果是_______。
【合肥工业大学 2001 三、5 （2分）】
34. 利用广义表的gethead和gettail操作，从广义表l=（（apple，pear），（banana，orange））中分离出原子banana的函数表达式是_______。 【山东大学 2001 三、6 (2分)】
35. 已知a数组元素共5个，依次为12，10，5，3，1；b数组元素共4个，依次为4,6,8,15，则执行如下所示的过程语句sort后得到c数组各元素依次为15,12,10,8,6,5,4,3,1；数组a,b,c的长度分别为l=5,m=4,n=9请在程序中方框内填入正确的成分，完成上述要求。
procedure sort;
var i, j, k, x: integer; d: array[1..m] of integer;
begin
for i:=1 to m do d[i]:=(1) ;
i:=1; j:=1; k:=1;
while (i<=l) and (j<=m) do
begin
if a[i]>d[j] then begin(2) ; (3) _end
else begin (4)__; (5) __end;
c[k]:=x; (6)
end;
while(7) _do
begin c[k]:=a[i]; k:=k+1; i:=i+1；end;
while(8) _do
begin c[k]:=d[j]; k:=k+1; j:=j+1；end;
end. {sort} 【上海交通大学 1998 七 (12分)】
36. 下列程序段search(a,n,k)在数组a的前n(n>=1)个元素中找出第k(1<=k<=n)小的值。这里假设数组a中各元素的值都不相同。
#define maxn 100
int a[maxn],n,k;
int search_c(int a[], int n, int k)
{int low, high, i, j, m, t;
k--,;low=0 ;high=n-1;
do {i=low; j=high ; t=a[low];
do{while (i<j && t<a[j]) j--;
if (i<j) a[i++]=a[j];
while (i<j && t>=a[i]) i++
if (i<j) a[j--]=a[i];
} while (i<j);
a[i]=t;
if (1) ;
if (i<k) low= (2) ; else high= (3) ;
}while(4) _;
return(a[k]);
} 【上海大学 1999 一、1（8分）】
37. 完善下列程序，每小题在pascal语言（a）和c语言（b）中任选一题。下面是一个将广义表逆置的过程。例如原来广义表为（（a,b）,c,（d,e）），经逆置后为：（（e,d）,c,（b,a））。
（a）算法的pascal语言过程描述（编者略）：（b）算法的c语言过程描述：
typedef struct glistnode
{int tag;
struct glistnode *next;
union{char data;
struct{struct glistnode *hp,*tp;}ptr;
}val;
}*glist,gnode;
glist reverse(p)
glist p;
{glist q,h,t,s;
if(p==null) q=null;
else
{if(1) { q=(glist)malloc(sizeof(gnode)); q->tag=0;
q->val.data=p->val.data; }
else {(2)
if (3)
{t=reverse(p->val.ptr.tp); s=t;
while(s->val.ptr.tp!=null) s=s->val.ptr.tp;
s->val.ptr.tp=(glist)malloc(sizeof(gnode));
s=s->val.ptr.tp;s->tag=1;s->val.ptr.tp=null;
s->val.ptr.hp=h; (4) __ }
else {q=(glist)malloc(sizeof(gnode));q->tag=1;
q->val.ptr.tp=null; (5) ; }
}
}
return(q);
}
【上海大学 2002 六、3 （10分）】
38. 完善下列程序，每小题在pascal语言（a）和c语言（b）中任选一题。下面的程序将数列1,2,3,…,n*n,依次按蛇型方式存放在二维数组a[1..n,1..n]中。即 (示意圖编者略)。
（a）算法的pascal 语言程序描述（编者略）：（b）算法的c语言程序描述：
#define nmax 10
#include “stdio.h”
main()
{ int i,j,n,k,p,q,m;
int a [nmax][nmax];
scanf(“%d”,&n);
m=1;
for(k=1；(1) ；k++)
{if（k<n） q=k； else(2) __;
for(p=1;p<=q;p++)
{if(3) {i=q-p+1；j=p；}
else{i=p；j=q-p+1；}
if(4) {i=i+n-q；j=j+n-q；}
a[i][j]=m；(5) _;
}
for（i=1；i<=n;i++）
{ for（j=1；j<=n；j++）
printf（“%4d”,a[i][j]）;printf(“\n”);
}
}
} 【上海大学 2002 六、1 （10分）】
18. 数组 h[ 1：1000] 中存放着1000个大小不同的正整数;
（1） 选择一分类算法使能最快地得到其中10个最大的数，简要说明理由；
（2） 编写一程序seek() ，执行该程序时，在命令行中提供二个参数；
seek a n<enter> 表示需打印h[ ]中n个最大数。
seek i n<enter> 表示需打印h[ ]中n个最小数。 【浙江大学 1994 八 (18分)】
19．已知两个定长数组，它们分别存放两个非降序有序序列，请编写程序把第二个数组序列中的数逐个插入到前一个数组序列中，完成后两个数组中的数分别有序（非降序）并且第一数组中所有的数都不大于第二个数组中的任意一个数。注意，不能另开辟数组，也不能对任意一个数组进行排序操作。例如，
第一个数组为：4,12,28
第二个数组为：1,7,9,29,45
输出结果为：1,4,7--------------第一个数组
9,12,28,29,45---------第二个数组 【上海大学 1998 四 （20分）】
20. 设数组a[1..n]中，a[n-2k+1..n-k]和[n-k+1..n]中元素各自从小到大排好序，试设计一个算法使a[n-2k+1..n]按从小到大次序排好序。并分析算法所需的计算时间。【福州大学 1998 四、3 (10分)】
21. 设a[1..100]是一个记录构成的数组，b[1..100]是一个整数数组，其值介于1至100之间，现要求按b[1..100]的内容调整a中记录的次序，比如当b[1]=ll时，则要求将a[1]的内容调整到a[11]中去。规定可使用的附加空间为o(1)。【中科院计算所 2000 七（15分）】
22. 给定有m个整数的递增有序数组a[1..m]和有n个整数的递减有序数组b[1..n]，试写出算法:将数组a和b归并为递增有序数组c[l..m+n]。(要求：算法的时间复杂度为o(m+n))
【华中理工大学 2000 八、1（10分）】
23．在数组 a[1..n]中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个。【南京理工大学 1998 七、2 （7分）】