第 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分）】
39,约瑟夫环问题：设有n个人围坐一圈，并按顺时针方向1—n编号。从第s个人开始进行报数，报数到第m个人，此人出圈，再从他的下一个人重新开始从1到m的报数进行下去,直到所有的人都出圈为止。
PROCEDURE Josef (A:ARRAY [1..n] OF integer; s,m:integer);
BEGIN
FOR i:= 1 TO n DO A[i]:=i;
sl:=s;
FOR i:=n DOWNTO 2 DO
BEGIN sl:= (1) __；//计算出圈人s1
IF sl=0 THEN (2) _；
w:=A[sl]; //A[s1]出圈
FOR j:= (3) __ DO A[j]:=A[j+1];
A[i]:=w;
END;
write('出圈序列为：’)；//输出出圈序列
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条对角线上的非零元存储在一维数组中，每个数据元素占Ｌ个存储单元，存储基地址为Ｓ，请用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分）】
9,若按照压缩存储的思想将n×n阶的对称矩阵A的下三角部分（包括主对角线元素）以行序为主序方式存放于一维数组B[1..n(n+1)/2]中，那么，A中任一个下三角元素aij(i≥j),在数组B中的下标位置k是什么？【北京航空航天大学 1998 一、4（4分）】
10,设m×n阶稀疏矩阵A有t个非零元素，其三元组表表示为LTMA[1..（t+1）,1..3]，试问：非零元素的个数t达到什么程度时用LTMA表示A才有意义？【北京航空航天大学 1998 一、5（4分）】
11,利用三元组存储任意稀疏数组时，在什么条件下才能节省存储空间。【西北工业大学1998三、2(5分)】
12,对一个有t个非零元素的Amn 矩阵,用B[0..t][1..3]的数组来表示，其中第0行的三个元素分别为m,n,t,从第一行开始到最后一行，每行表示一个非零元素；第一列为矩阵元素的行号，第二列为其列号，第三列为其值。对这样的表示法，如果需要经常进行该操作---确定任意一个元素A[i][j]在B中的位置并修改其值，应如何设计算法可以使时间得到改善？【长沙铁道学院 1998 四、4 (6分)】
13,有一个二维数组A[0:8,1:5],每个数组元素用相邻的4个字节存储,存储器按字节编址,假设存储数组元素A[0,1]的第一个字节的地址是0,那么存储数组的最后一个元素的第一个字节的地址是多少?若按行存储,则A[3,5]和A[5,3]的第一个字节的地址是多少?若按列存储,则A[7,1]和A[2,4]的第一个字节的地址是多少?【上海海运学院 1999 三（10分）】
14,设有三对角矩阵(ai,j)m╳n,将其三条对角线上的元素逐行的存于数组B(1:3n-2)中，使得B[k]=ai,j，求：
（1）用i,j表示k的下标变换公式；
（2）若n=103,每个元素占用L个单元，则用B[K]方式比常规存储节省多少单元。
【西安电子科技大学 1996 二、4 （5分）】
15,已知A为稀疏矩阵，试从空间和时间角度，比较采用两种不同的存储结构（二维数组和三元组表）完成求运算的优缺点。【西安电子科技大学 1996 二、6（5分）】
16,特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能？为什么？
【北京邮电大学 2001 三、1（5分）】
17,试叙述一维数组与有序表的异同。【西安电子科技大学 1999计应用一、2（5分）】
18,一个n╳n的对称矩阵，如果以行或列为主序存入内存，则其容量为多少？
【西安电子科技大学 1999计应用 一、3（5分）】
19,给出数组 A∶ARRAY[3..8,2..6] OF INTEGER;当它在内存中按行存放和按列存放时，分别写出数组元素A[i,j]地址计算公式（设每个元素占两个存储单元）。【南开大学 1998 一 (8分)】
20,已知n阶下三角矩阵A（即当i<j时，有aij=0），按照压缩存储的思想，可以将其主对角线以下所有元素(包括主对角线上元素 )依次存放于一维数组B中，请写出从第一列开始采用列序为主序分配方式时在B中确定元素aij的存放位置的公式。【北京航空航天大学 1999二(10分)】 【中山大学 1999三 2】
21,设有三对角矩阵(aij)n*n，将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得B[k]=aij，求：（1）用i,j表示k的下标变换公式；
（2）用k表示i,j的下标变化公式。
【山东科技大学 2001 一、6 （6分）】【长沙铁道学院 1997 五、1 (10分)】
【东北大学 2002 一 (4分)】【北京工业大学 2000 二、1 (9分)】【南京航空航天大学 2000 四】
22,算法Print及所引用的数组A的值如下，写出调用Print(1)的运行结果（其中n=15）。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A
B
C
D
E
F
G
O
O
H
0
I
J
K
L
PROCEDURE print（i：integer）；
BEGIN
IF（i<=n〉 AND （A[i] <>‘0’） THEN
BEGIN Print（2*i）；write（A[i]）；Print（2*i+1）； END；
END；
【合肥工业大学 1999 四、1（5分）】
23,设数组A的长度为2N，前N个元素A[1..N]递减有序，后N个元素A[N+1.,2N]递增有序，且2N是2的整数次幂，即k=log22N为整数。例如A[1..8]=[90,85,50,10,30,65,80,100]满足上述要求，这里N=4,k=3,A的前4个元素和后4个元素分别递减和递增有序。用此例调用如下的Demo过程，并要求：
（1）给出for循环中每次执行PerfectShuffle（A,N）和CompareExchange（A,N）的结果；
（2）解释Demo的功能； （3）给出Demo的时间复杂度。
PROCEDURE PerfectShuffle(VAR A:arraytype; N:integer)
[ i:=1; j:=1;
WHILE i<=N DO
[ B[j]:=A[i]; B[j+1]:=A[i+N]; i:=i+1; j:=j+2; ]
A[1..2N]:=B[1..2N]; //B copy to A
]
PROCEDURE CompareExchange(VAR A:arraytype; N:integer)
[ j:=1;
WHILE j<2N DO
[ IF A[j]>A[j+1] THEN A[j]←→A[j+1]; //交换A[j]和A[j+1]
j:=j+2; ]
]
PROCEDURE Demo (VAR A:arraytype;N:integer)
//A的长度为2N,k=log22N为整数
[ FOR i:=1 TO log22N DO
[ PerfectShuffle(A,N); CompareExchange(A,N); ]
] 【中科院计算所 1998 四 （15分）】 【中国科技大学 1998 4（15分）】
24,现有算法及正整数n和数组A如下，求数组C的值。
VAR A,B,C:Array[1..100] of integer;
FUNC AAA(s,t:integer):integer;
IF s=t THEN IF B[s]=0 THEN AAA:=S ELSE AAA:=-s ELSE
BEGIN
l:=AAA(s,(s+t) DIV 2);
r:=AAA((s+t) DIV 2+1,t);
IF l>0 THEN AAA:=l ELSE AAA:=r;
IF (r>0) AND (A[l]>A[r]) THEN AAA:=r
END
ENDF;
PROC BBB;
FOR i:=1 TO n DO B[i]:=0;
FOR i:=1 TO n DO B[AAA(1,n)]:=i;
FOR i:=1 TO n DO C[B[i]]:=A[i];
ENDP;
初始值：n=10,A={121,22,323,212,636,939,828,424,55,262};
【北京邮电大学 2002 五、1（10分）】
25,设有矩阵ａ且a=执行下列语句后，矩阵ｃ和ａ的结果分别是什么？
（1） FOR i:=1 TO 3 DO
FOR j:=1 TO 3 DO c[i,j]:=a[a[i,j],a[j,i]]
（2） FOR i:=1 TO 3 DO
FOR j:=1 TO 3 DO a[i,j]:=a[a[i,j],a[j,i]]
【浙江大学 1997 三 (8分)】
26,设矩阵A为
（1）执行语句
FOR i:=1 TO 3 DO
FOR j:=1 TO 3 DO ①
C[i,j]:=A[A[i,j],A[j,i]]
结果C矩阵的值是什么？
（2）所选择的下标i,j的次序有关系吗？
（3）在语句①中，用A代替C，A的结果值是什么？
（4）对i,j这对下标取反序，即
（3，3），（3，2），（3，1），……，（1，3），（1，2），（1，1）
重复执行（3）,把所得结果与（3）中所得结果作比较。 【吉林大学 1995 二 (15分)】
27,指出下列算法中错误、低效之处，并将其改成一个正确且高效的算法。
PROCEDURE delk(A,m,last,i,k) ;
｛从数组A[１..last]中删除第i个元素起的 k个元素，m为A上限｝
BEGIN
IF(i<1) OR (i>last) OR(k<0) OR(last>m)
THEN write ('error')
ELSE FOR count,= 1 TO k TO
[FOR j:=last DOWNTO i+1 DO
A[j-1]:=A[j];
last:=last-1]
ENDP;{delk} 【北方交通大学 1997 一 （10分）】
28,设输入为整数数组A[1..n]，其中1<=A[i]<=k(1<=i<=n)；输出数组为b[1..n]；c[1..k]是临时工作空间；阅读下述算法后，回答下列问题：
PROC Demo(A,B,k){
(1)FOR i:=1 TO k DO C[i]:=0;
(2)FOR j:=1 TO n DO C[A[j]]:= C[A[j]]+1;
(3)FOR i:=2 TO k DO C[i]:= C[i]+ C[i-1]
(4)FOR j:=n DOWNTO 1 DO {
(5) B[C[A[j]]]:=A[j];
(6)C[A[j]]:=C[A[j]]-1 } }
(a).当标号（2）行的循环执行完后，C[i](1<=i<=n)的值有何意义？
(b).当标号（3）行的循环执行完后，C[i](1<=i<=n)的值有何意义？
(c).算法执行后，B的内容有何特点？
(d).当k=O(n)时，算法的时间复杂度是多少？ 【中科院软件所 1997 二、2（9分）】
29．上三角阵A（N*N）按行主序压缩存放在数组B中，其中A[i,j]=B[k].写出用i，j表示的k。
【北京工业大学 2001 二、1 (5分)】
30,设有上三角矩阵(aij)n*n，将其上三角中的元素按先行后列的顺序存于数组B（1:m）中，使得B[k]= aij且k=f1(i)+f2(j)+c，请推导出函数f1,f2和常数c，要求f1和f2中不含常数项。
【中科院自动化所 1999】 【山东科技大学 2002 一、5 （6分）】
31,设矩阵A=
(1) 若将A视为对称矩阵，画出对其压缩存储的存储表，并讨论如何存取A中元素aij (0<=i,j<4)；
(2) 若将A视为稀疏矩阵，画出A的十字链表结构。 【北京科技大学 1997 三 （10分）】
32,设对称矩阵A=
（1）若将A中包括主对角线的下三角元素按列的顺序压缩到数组S中,即S:
1
0
0
2
3
0
0
0
5
0
下标：1 2 3 4 5 6 7 8 9 10
试求出A中任一元素的行列下标[i,j](1<=i,j<=4)与S中元素的下标K之间的关系.
（2）若将A视为稀疏矩阵时,画出其三元组表形式压缩存储表。【北京科技大学1999 三（10分）】
33,设对角线矩阵A=（ 行列下标i,j 满足：1≤i,j≤5）
（1）若将矩阵A压缩存储到数组S 中,
1
2
1
0
1
2
1
0
0
0
1
3
5
下标,1 2 3 4 5 6 7 8 9 10 11 12 13
试求出A中已存储之元素的行列下标（i,j）与S中元素的下标K之间的关系
（2）若将A视为稀疏距阵时，请画出其行逻辑链接顺序表。【北京科技大学2000 三(10分)】
34．设有一个三维数组a[c1:d1,c2:d2,c3:d3]，其中ci:di是第i维的界偶，如该数组在内存中按行排列，且a[c1,c2,c3]的地址为a0，那么请导出下标变量a[i1,i2,i3]的地址，假设每个元素占L个单元。
【山东师范大学 1999 四、1 （5分）】
35．假定有下列nⅹn矩阵（n为奇数）A=
如果用一维数组B按行主次序存储A的非零元素，问：
（1）A中非零元素的行下标与列下标的关系；
（2）给出A中非零元素aij 的下标(i,j)与B中的下标R的关系;
（3）假定矩阵中每个元素占一个存贮单元且B的起始地址为A0，给出利用aij的下标(i,j)定位在B中的位置公式。 【上海交通大学 1998 三(12分)】
36,对于一个对称矩阵采用压缩存储，只存放它的上三角部分，
并按列存放。例如对于一个n*n的对称矩阵A (如右图),用一个一维数组B来存放它的上三角部分：
B=[A11，A12，A22，A13，A23，A33，A14，…，A1n，A2n，…，Ann]
同时有两个函数：MAX(i,j)和MIN(i,j)，分别计算下标i和
j中的大者与小者。试利用它们给出求任意一个Aij在B中存放位置的公式。（若式中没有MAX(I,j)和MIN（i，j）则不给分）
【清华大学 1997 五 (10分)】
37,用三元数组表示稀疏矩阵的转置矩阵,并简要写出解题步骤。【山东工业大学 1995 五 （10分）】
38,简述广义表属于线性结构的理由。【西北大学 2000 一、5 (3分)】
39,数组，广义表与线性表之间有什么样的关系？【西北工业大学 1998 一、2 (4分)】
40,什么是广义表？请简述广义表和线性表的主要区别。 【北京大学 1997 二、2 （5分）】
41,求下列广义表的运算结果。【南京航空航天大学 1998 三 （10分）】
（1）CAR(CDR(((a,b),(c,d),(e,f))))
（2）CDR(CAR(((a,b),(c,d),(e,f))))
（3）CAR(CDR(CAR(((a,b),(e,f)))))
（4）CDR(CAR(CDR(((a,b),(e,f)))))
（5）CDR(CDR(CAR(((a,b),(e,f)))))
注：CAR运算相当于有些教材中的Head运算，CDR运算相当于Tail运算。
42,利用广义表的Head和Ｔail运算，把原子d分别从下列广义表中分离出来，L1＝(((((a),b),d),e))；L2＝（a,(b,((d)),e））。 【北方交通大学 1996 一、2（5分）】
类似本题的另外叙述有：
(1) 已知广义表L=((((a))),((b)),(c),d)，试利用head和tail运算把原子项c从L中分离出来。
【北京邮电大学 1992 三、2（25/4分）】【青岛海洋大学 1999 一、6 （5分）】
(2) 画出下列广义表的存储结构图，并利用取表头和取表尾的操作分离出原子e。
（ a,（（）,ｂ）,（（（ｅ））））。
【清华大学 1995 二 （10分）】
(3) 已知广义表A=((a,b,c),(d,e,f)) 试写出从表A中取出原子元素e的运算。
【西安电子科技大学 1996 二、3 （5分）】
(4)请将香蕉banana用工具 H( )—Head( )，T( )—Tail( )从L中取出。
L=(apple,(orange,(strawberry,(banana)),peach),pear)
【北京邮电大学 2000 三、2 （5分）】
(5) 试利用广义表取表头head(ls)和取表尾tail(ls)的基本运算，将原子d从下列表中分解出来，请写出每一步的运算结果。
L=((a,(b)),((c,d)),(e,f)) 【北京工商大学 2001 三 （10分）】
(6) 画出广义表A=（a,（b,()）,(((),c))）的第一种存储结构（表结点第二指针指向余表）图，并用取首元（head()）和取尾元（tail()）函数表示原子c。【北京工业大学 2001 二、2 (5分)】
43,画出下列广义表的两种存储结构图((),A,(B,(C,D)),(E,F))。【南京航空航天大学 1999 三（10分）】
44,假设采用以下两种结点的链表作为广义表的存贮结构，表结点：(tag=1,hp,tp),元素结点；(tag=0,data)。请画出下列广义表的存储结构图，并求它的深度和长度。
( ( ),( ( ( ) ),( ( ( ) ) ) ) )
【北方交通大学 1998 一（13分）】
45．知广义表A=（（（a）），（b），c，（a），（（（d，e））））
（1）画出其一种存贮结构图；
（2）写出表的长度与深度；
（3）用求头部，尾部的方式求出e。【东北大学 1997 一、2 (5分)】
46．画出具有共享结构广义表（（（b,c）,d）,(a),((a),((b,c),d)),e,()）的存贮表示。
【北京工业大学 1996 一、3 (6分)】
47,广义表的结点结构如下:(TAG,DATA,LINK)。其中LINK为指向表中下一元素的指针;TAG为标志域；DATA为数据域，具体含义如下,TAG=0表示该结点为原子结点，DATA为其数据；TAG=1表示该结点为一个子表，DATA为指向该子表的指针。
（1）说明下列算法A的功能(注:算法中p,t,m,n,r,q为指针;算法中的NIL对应图中的^)
PROCEDURE A(p,t)
BEGIN
q:=NIL;
WHILE p<>NIL DO
BEGIN
IF p^.TAG<>0 THEN
BEGIN
m:=p^.DATA;
A(m,n);
p^.DATA:=n;
END;
r:=p^.LINK;
p^.LINK:=q;
q:=p;
p:=r
END;
t:=q;
END.
（2）对于 p所指的广义表,画出执行算法A后的表结构以及p，t的值:
【北方交通大学 1993 六（20分）】
类似本题的另外叙述有：
题目基本相同，差别仅在于子表(b,c)与原子d的前后顺序颠倒。【浙江大学 1994 六 (7分)】
48,写出对广义表A=(x,((a,b),c,d))作运算head(head(tail(A)))后的结果。
【西安电子科技大学 2000计应用 一、5（5分）】
49．写出广义表的运算结果,TAIL[HEAD[TAIL[((a,b),(c,d))]]]=?
【武汉交通科技大学 1996 二、7 (3分)】
50,广义表中原子个数是否即为广义表的长度？ 【西安电子科技大学 2000计应用一、9（5分）】
51,给出下列所示的3元多项式的广义表表示（分别以X1，X2，X3第一到第三层变元）
P（X1X2X3）=X15X23X3+2X15X22X34+5X15X23X33+3X1X24X32+X2X3+6
【华南理工大学 2001 一、2（4分）】
52,设某表H如下：
A
B
C
X
a1
a2
b1
c1
c2
其中A,B,C为子表名，a1,a2,b1,c1,c2,x为其元素。
（1）试用广义表形式表示H,并写出运算HEAD(H)和TAIL(H) 函数从H中取出单元素a2的运算；
（2）画出表H的链式存储结构；【北京科技大学 1998 三（10分）】
五 算法设计题
1,设有大小不等的n?个数据组（n个数据组中数据的总数为m），顺序存放在空间区D内,每个数据占一个存储单元，数据组的首地址由数组S给出，（如下图所示），试编写将新数据x插入到第i个数据组的末尾且属于第i 个数据组的算法，插入后，空间区D和数组S的相互关系仍保持正确。
【东北大学 2000 六 (15分)】
2,以三元组表存贮的稀疏矩阵A，B非零元个数分别为m和n。试用类PASCAL语言编写时间复杂度为O（m+n）的算法将矩阵B加到矩阵A上去。A的空间足够大，不另加辅助空间。要求描述所用结构。
【北京工业大学 1997 三 (10分)】
3,设整数x1,x2,…,xN已存放在数组A中，编写一PASCAL递归过程，输出从这n个数中取出所有k 个数的所有组合（k<=n）。例：若A中存放的数是1，2，3，4，5，k为3，则输出结果应为：543，542，541，532，531，521，432，431，421，321。 【山东大学 1992 五 (13分)】
类似本题的另外叙述有：
（1）题目基本相同，只是叙述不同，要求用PASCAL语言。【东南大学 2001 三 （10分）】
4．编写一个过程，对一个n×n矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。
【中科院软件所 1996 】
5,设原来将N个自然数1,2,…,N按某个顺序存于数组A中，经过下面的语句计算，使A[I]的值变为A[1]到A[I-1]中小于原A[I]值的个数。
FOR I:=N DOWNTO 1 DO
BEGIN
C：=0；
FOR J：=1 TO I-1 DO
IF A[J]<A[I] THEN C：=C+1；
A[I]：=C
END；
编程将经过上述处理后的A还原成原来的A。 【上海大学 1996 二 （16分）】
6．请编写完整的程序。如果矩阵A中存在这样的一个元素A[i,j]满足条件:A[i,j]是第i行中值最小的元素,且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵A的所有马鞍点。 【上海大学 2000 三 （20分）】【中科院自动化所 1997】
7．给定一个整数数组b[0..N-1]，b中连续的相等元素构成的子序列称为平台。试设计算法，求出b中最长平台的长度。【中科院计算所 1999 五、2 （20分）】
8,给定nxm矩阵A[a..b,c..d],并设A[i,j]≤A[i,j+1](a≤i≤b,c≤j≤d-1)和A[i,j]≤A[i+1,j](a≤i≤b-1,c≤j≤d).设计一算法判定X的值是否在A中,要求时间复杂度为O(m+n)。【东南大学2001六(13分)】
类似本题的另外叙述有：
（1）给定整型数组B[0..m,0..n] 。已知B中数据在每一维方向上都按从小到大的次序排列，且整型变量x在B中存在。试设计一个程序段找出一对满足B[i,j]=x的(i,j)值，要求比较次数不超过m+n.。
【清华大学 1998 六（10分）】
(2) 给定n×m矩阵A[a..b,c..d]，并设A[i,j]<=A[i,j+1]（a<=i<=b,c<=j<=d-1）知A[i,j]<=A[i+1,j],(a<=i<=b-1,c<=j<=d)。设计一算法以比O(n*m)小的最坏时间复杂性判定值x是否在A中。【东南大学1994三(17分)】
9,编写算法，将自然数1～n按“蛇形”填入n×n矩阵中。例（1～4）如图所示：（用程序实现）
【南京航空航天大学 1997 八 （12分）】 【中科院计算所 1996】
10,设二维数组a[1..m,1..n] 含有m*n 个整数。
(1) 写出算法(pascal过程或c函数)：判断a中所有元素是否互不相同?输出相关信息(yes/no)；
(2) 试分析算法的时间复杂度。【华中理工大学 1999 五 （10分）】
11,二项式(a+b)n展开式的系数为
C（n，0）=1，C（n，n）=1，对于n>=0
C（n，k）=C（n-1，k）+C（n-1，k-1），对于0<k<n 形成著名的杨辉三角形，如图所示。
(1)试写一个递归算法，根据以上公式生成C（n,k）。（6分）
(2)试画出计算C（6，4）的递归树。（4分）
(3)试写一个非递归算法，既不用数组也不用栈，对于任意的0<=k<=n计算C(n,k)（6分）
【清华大学 1999 五 （16分）】
12,设任意n个整数存放于数组A(1:n)中，试编写程序，将所有正数排在所有负数前面（要求算法复杂性为0( n)）。 【山东大学 1993 三 (12分)】.
类似本题的另外叙述有：
（1）已知数组A[1..n]的元素类型为整型，设计算法调整A，使其左边的所有元素小于零，右边的所有元素大于等于零。（要求算法的时间复杂度和空间复杂度均为0（n））
【北京理工大学 2000 四、1 （4分）】
（2）设计一个算法，把整数数组中所有的偶数放到所有的奇数之前。要求时间、空间效率尽可能高。
【华南师范大学 1999 六、1 (10分)】
（3）设一系列正整数存放在一个数组中，试设计算法，将所有奇数存放在数组的前半部分，将所有的偶数存放在数组的后半部分。要求尽可能少用临时存储单元并使时间最少。请试着分析你实现的算法的时间复杂度和空间复杂度。 【南开大学 2000 三、2】
（4）设计算法将数组A[1..n]调整为左右两部分，使的左边所有的元素小于右边的所有元素，并给出这一划分的分界位置。要求算法的时间复度为O(n)。 【合肥工业大学 2001 五、3 （8分）】
13.若S是n个元素的集合，则S的幂集P(S)定义为S所有子集的集合。例如,S=(a,b,c),P(S)={(),(a),(b),(c),(a,b),(a,c),(b,c),(a,b,c)}给定S，写一递归算法求P(S)。
【东南大学 1993 五 （15分）】【东南大学 1997 五 （15分）】
14．编写算法打印出由指针Hm指向总表头的以十字链表形式存储的稀疏矩阵中每一行的非零元的个数。注意：行、列及总表头结点的形式为：
row
col
val
down
right
它们已用val域链接成循环链表。非零元的结点形式也同上，每一行（列）的非零元由right（down）域把它们链接成循环链表，该行（列）的表头结点即为该行（列）循环链表的表头。
【上海大学 1998 五 （16分）】
15,试编写建立广义表存储结构的算法，要求在输入广义表的同时实现判断、建立。设广义表按如下形式输入（a1,a2,a3,…,an） n>=0，其中ai或为单字母表示的原子或为广义表，n=0时为只含空格字符的空表。(注:算法可用类pascal 或类c书写) 【北京工业大学 1998 十 (15分)】
16,广义表是n(n>=0)个数据元素a1,a2,a3,…,an的有限序列。其中ai (1<=i<=n)或者是单个数据元素（原子），或仍然是一个广义表。广义表的结点具有不同的结构，即原子结点和子表元素结点，为了将两者统一，用了一个标志tag，当其为0时表示是原子结点，其data域存储结点值，link域指向下一个结点，当其tag为1时表示是子表结点，其sublist为指向子表的指针。因此，广义表可采用如下结构存储：
TYPE glist=^gnode;
gnode=RECORD
link:glist;
CASE tag:0..1 OF
0:(data:char);
1:(sublist:glist)
END;
（1）画出广义表((a,b),c)的存储结构；
（2）写出计算一个广义表的原子结点个数的递归算法表示式；
（3）编写实现上述算法的过程或函数程序。【厦门大学 2002 三 （12分）】
17,广义表GL=(a1,a2,…,an),其中 ak(k=1,2,...,n)或是单个数据元素（原子），或仍然是个广义表。给定如下有关广义表的类型定义：
TYPE tagtype=0..1;
glist=^gnode;
gnode=RECORD
link:glist; {link 域指向下一个结点}
CASE tag:tagtype OF ｛tag=0 表示原子结点｝
0,(data,integer);
1:(sublist,glist)
END;
编写一个过程或函数计算一个广义表的所有原子结点数据域之和，例如对广义表(3,(2,4,5),(6,3）) 数据域之和为23。【厦门大学 2000 四、2 （9分）】
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分）】
39,约瑟夫环问题：设有n个人围坐一圈，并按顺时针方向1—n编号。从第s个人开始进行报数，报数到第m个人，此人出圈，再从他的下一个人重新开始从1到m的报数进行下去,直到所有的人都出圈为止。
PROCEDURE Josef (A:ARRAY [1..n] OF integer; s,m:integer);
BEGIN
FOR i:= 1 TO n DO A[i]:=i;
sl:=s;
FOR i:=n DOWNTO 2 DO
BEGIN sl:= (1) __；//计算出圈人s1
IF sl=0 THEN (2) _；
w:=A[sl]; //A[s1]出圈
FOR j:= (3) __ DO A[j]:=A[j+1];
A[i]:=w;
END;
write('出圈序列为：’)；//输出出圈序列
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条对角线上的非零元存储在一维数组中，每个数据元素占Ｌ个存储单元，存储基地址为Ｓ，请用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分）】
9,若按照压缩存储的思想将n×n阶的对称矩阵A的下三角部分（包括主对角线元素）以行序为主序方式存放于一维数组B[1..n(n+1)/2]中，那么，A中任一个下三角元素aij(i≥j),在数组B中的下标位置k是什么？【北京航空航天大学 1998 一、4（4分）】
10,设m×n阶稀疏矩阵A有t个非零元素，其三元组表表示为LTMA[1..（t+1）,1..3]，试问：非零元素的个数t达到什么程度时用LTMA表示A才有意义？【北京航空航天大学 1998 一、5（4分）】
11,利用三元组存储任意稀疏数组时，在什么条件下才能节省存储空间。【西北工业大学1998三、2(5分)】
12,对一个有t个非零元素的Amn 矩阵,用B[0..t][1..3]的数组来表示，其中第0行的三个元素分别为m,n,t,从第一行开始到最后一行，每行表示一个非零元素；第一列为矩阵元素的行号，第二列为其列号，第三列为其值。对这样的表示法，如果需要经常进行该操作---确定任意一个元素A[i][j]在B中的位置并修改其值，应如何设计算法可以使时间得到改善？【长沙铁道学院 1998 四、4 (6分)】
13,有一个二维数组A[0:8,1:5],每个数组元素用相邻的4个字节存储,存储器按字节编址,假设存储数组元素A[0,1]的第一个字节的地址是0,那么存储数组的最后一个元素的第一个字节的地址是多少?若按行存储,则A[3,5]和A[5,3]的第一个字节的地址是多少?若按列存储,则A[7,1]和A[2,4]的第一个字节的地址是多少?【上海海运学院 1999 三（10分）】
14,设有三对角矩阵(ai,j)m╳n,将其三条对角线上的元素逐行的存于数组B(1:3n-2)中，使得B[k]=ai,j，求：
（1）用i,j表示k的下标变换公式；
（2）若n=103,每个元素占用L个单元，则用B[K]方式比常规存储节省多少单元。
【西安电子科技大学 1996 二、4 （5分）】
15,已知A为稀疏矩阵，试从空间和时间角度，比较采用两种不同的存储结构（二维数组和三元组表）完成求运算的优缺点。【西安电子科技大学 1996 二、6（5分）】
16,特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能？为什么？
【北京邮电大学 2001 三、1（5分）】
17,试叙述一维数组与有序表的异同。【西安电子科技大学 1999计应用一、2（5分）】
18,一个n╳n的对称矩阵，如果以行或列为主序存入内存，则其容量为多少？
【西安电子科技大学 1999计应用 一、3（5分）】
19,给出数组 A∶ARRAY[3..8,2..6] OF INTEGER;当它在内存中按行存放和按列存放时，分别写出数组元素A[i,j]地址计算公式（设每个元素占两个存储单元）。【南开大学 1998 一 (8分)】
20,已知n阶下三角矩阵A（即当i<j时，有aij=0），按照压缩存储的思想，可以将其主对角线以下所有元素(包括主对角线上元素 )依次存放于一维数组B中，请写出从第一列开始采用列序为主序分配方式时在B中确定元素aij的存放位置的公式。【北京航空航天大学 1999二(10分)】 【中山大学 1999三 2】
21,设有三对角矩阵(aij)n*n，将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得B[k]=aij，求：（1）用i,j表示k的下标变换公式；
（2）用k表示i,j的下标变化公式。
【山东科技大学 2001 一、6 （6分）】【长沙铁道学院 1997 五、1 (10分)】
【东北大学 2002 一 (4分)】【北京工业大学 2000 二、1 (9分)】【南京航空航天大学 2000 四】
22,算法Print及所引用的数组A的值如下，写出调用Print(1)的运行结果（其中n=15）。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A
B
C
D
E
F
G
O
O
H
0
I
J
K
L
PROCEDURE print（i：integer）；
BEGIN
IF（i<=n〉 AND （A[i] <>‘0’） THEN
BEGIN Print（2*i）；write（A[i]）；Print（2*i+1）； END；
END；
【合肥工业大学 1999 四、1（5分）】
23,设数组A的长度为2N，前N个元素A[1..N]递减有序，后N个元素A[N+1.,2N]递增有序，且2N是2的整数次幂，即k=log22N为整数。例如A[1..8]=[90,85,50,10,30,65,80,100]满足上述要求，这里N=4,k=3,A的前4个元素和后4个元素分别递减和递增有序。用此例调用如下的Demo过程，并要求：
（1）给出for循环中每次执行PerfectShuffle（A,N）和CompareExchange（A,N）的结果；
（2）解释Demo的功能； （3）给出Demo的时间复杂度。
PROCEDURE PerfectShuffle(VAR A:arraytype; N:integer)
[ i:=1; j:=1;
WHILE i<=N DO
[ B[j]:=A[i]; B[j+1]:=A[i+N]; i:=i+1; j:=j+2; ]
A[1..2N]:=B[1..2N]; //B copy to A
]
PROCEDURE CompareExchange(VAR A:arraytype; N:integer)
[ j:=1;
WHILE j<2N DO
[ IF A[j]>A[j+1] THEN A[j]←→A[j+1]; //交换A[j]和A[j+1]
j:=j+2; ]
]
PROCEDURE Demo (VAR A:arraytype;N:integer)
//A的长度为2N,k=log22N为整数
[ FOR i:=1 TO log22N DO
[ PerfectShuffle(A,N); CompareExchange(A,N); ]
] 【中科院计算所 1998 四 （15分）】 【中国科技大学 1998 4（15分）】
24,现有算法及正整数n和数组A如下，求数组C的值。
VAR A,B,C:Array[1..100] of integer;
FUNC AAA(s,t:integer):integer;
IF s=t THEN IF B[s]=0 THEN AAA:=S ELSE AAA:=-s ELSE
BEGIN
l:=AAA(s,(s+t) DIV 2);
r:=AAA((s+t) DIV 2+1,t);
IF l>0 THEN AAA:=l ELSE AAA:=r;
IF (r>0) AND (A[l]>A[r]) THEN AAA:=r
END
ENDF;
PROC BBB;
FOR i:=1 TO n DO B[i]:=0;
FOR i:=1 TO n DO B[AAA(1,n)]:=i;
FOR i:=1 TO n DO C[B[i]]:=A[i];
ENDP;
初始值：n=10,A={121,22,323,212,636,939,828,424,55,262};
【北京邮电大学 2002 五、1（10分）】
25,设有矩阵ａ且a=执行下列语句后，矩阵ｃ和ａ的结果分别是什么？
（1） FOR i:=1 TO 3 DO
FOR j:=1 TO 3 DO c[i,j]:=a[a[i,j],a[j,i]]
（2） FOR i:=1 TO 3 DO
FOR j:=1 TO 3 DO a[i,j]:=a[a[i,j],a[j,i]]
【浙江大学 1997 三 (8分)】
26,设矩阵A为
（1）执行语句
FOR i:=1 TO 3 DO
FOR j:=1 TO 3 DO ①
C[i,j]:=A[A[i,j],A[j,i]]
结果C矩阵的值是什么？
（2）所选择的下标i,j的次序有关系吗？
（3）在语句①中，用A代替C，A的结果值是什么？
（4）对i,j这对下标取反序，即
（3，3），（3，2），（3，1），……，（1，3），（1，2），（1，1）
重复执行（3）,把所得结果与（3）中所得结果作比较。 【吉林大学 1995 二 (15分)】
27,指出下列算法中错误、低效之处，并将其改成一个正确且高效的算法。
PROCEDURE delk(A,m,last,i,k) ;
｛从数组A[１..last]中删除第i个元素起的 k个元素，m为A上限｝
BEGIN
IF(i<1) OR (i>last) OR(k<0) OR(last>m)
THEN write ('error')
ELSE FOR count,= 1 TO k TO
[FOR j:=last DOWNTO i+1 DO
A[j-1]:=A[j];
last:=last-1]
ENDP;{delk} 【北方交通大学 1997 一 （10分）】
28,设输入为整数数组A[1..n]，其中1<=A[i]<=k(1<=i<=n)；输出数组为b[1..n]；c[1..k]是临时工作空间；阅读下述算法后，回答下列问题：
PROC Demo(A,B,k){
(1)FOR i:=1 TO k DO C[i]:=0;
(2)FOR j:=1 TO n DO C[A[j]]:= C[A[j]]+1;
(3)FOR i:=2 TO k DO C[i]:= C[i]+ C[i-1]
(4)FOR j:=n DOWNTO 1 DO {
(5) B[C[A[j]]]:=A[j];
(6)C[A[j]]:=C[A[j]]-1 } }
(a).当标号（2）行的循环执行完后，C[i](1<=i<=n)的值有何意义？
(b).当标号（3）行的循环执行完后，C[i](1<=i<=n)的值有何意义？
(c).算法执行后，B的内容有何特点？
(d).当k=O(n)时，算法的时间复杂度是多少？ 【中科院软件所 1997 二、2（9分）】
29．上三角阵A（N*N）按行主序压缩存放在数组B中，其中A[i,j]=B[k].写出用i，j表示的k。
【北京工业大学 2001 二、1 (5分)】
30,设有上三角矩阵(aij)n*n，将其上三角中的元素按先行后列的顺序存于数组B（1:m）中，使得B[k]= aij且k=f1(i)+f2(j)+c，请推导出函数f1,f2和常数c，要求f1和f2中不含常数项。
【中科院自动化所 1999】 【山东科技大学 2002 一、5 （6分）】
31,设矩阵A=
(1) 若将A视为对称矩阵，画出对其压缩存储的存储表，并讨论如何存取A中元素aij (0<=i,j<4)；
(2) 若将A视为稀疏矩阵，画出A的十字链表结构。 【北京科技大学 1997 三 （10分）】
32,设对称矩阵A=
（1）若将A中包括主对角线的下三角元素按列的顺序压缩到数组S中,即S:
1
0
0
2
3
0
0
0
5
0
下标：1 2 3 4 5 6 7 8 9 10
试求出A中任一元素的行列下标[i,j](1<=i,j<=4)与S中元素的下标K之间的关系.
（2）若将A视为稀疏矩阵时,画出其三元组表形式压缩存储表。【北京科技大学1999 三（10分）】
33,设对角线矩阵A=（ 行列下标i,j 满足：1≤i,j≤5）
（1）若将矩阵A压缩存储到数组S 中,
1
2
1
0
1
2
1
0
0
0
1
3
5
下标,1 2 3 4 5 6 7 8 9 10 11 12 13
试求出A中已存储之元素的行列下标（i,j）与S中元素的下标K之间的关系
（2）若将A视为稀疏距阵时，请画出其行逻辑链接顺序表。【北京科技大学2000 三(10分)】
34．设有一个三维数组a[c1:d1,c2:d2,c3:d3]，其中ci:di是第i维的界偶，如该数组在内存中按行排列，且a[c1,c2,c3]的地址为a0，那么请导出下标变量a[i1,i2,i3]的地址，假设每个元素占L个单元。
【山东师范大学 1999 四、1 （5分）】
35．假定有下列nⅹn矩阵（n为奇数）A=
如果用一维数组B按行主次序存储A的非零元素，问：
（1）A中非零元素的行下标与列下标的关系；
（2）给出A中非零元素aij 的下标(i,j)与B中的下标R的关系;
（3）假定矩阵中每个元素占一个存贮单元且B的起始地址为A0，给出利用aij的下标(i,j)定位在B中的位置公式。 【上海交通大学 1998 三(12分)】
36,对于一个对称矩阵采用压缩存储，只存放它的上三角部分，
并按列存放。例如对于一个n*n的对称矩阵A (如右图),用一个一维数组B来存放它的上三角部分：
B=[A11，A12，A22，A13，A23，A33，A14，…，A1n，A2n，…，Ann]
同时有两个函数：MAX(i,j)和MIN(i,j)，分别计算下标i和
j中的大者与小者。试利用它们给出求任意一个Aij在B中存放位置的公式。（若式中没有MAX(I,j)和MIN（i，j）则不给分）
【清华大学 1997 五 (10分)】
37,用三元数组表示稀疏矩阵的转置矩阵,并简要写出解题步骤。【山东工业大学 1995 五 （10分）】
38,简述广义表属于线性结构的理由。【西北大学 2000 一、5 (3分)】
39,数组，广义表与线性表之间有什么样的关系？【西北工业大学 1998 一、2 (4分)】
40,什么是广义表？请简述广义表和线性表的主要区别。 【北京大学 1997 二、2 （5分）】
41,求下列广义表的运算结果。【南京航空航天大学 1998 三 （10分）】
（1）CAR(CDR(((a,b),(c,d),(e,f))))
（2）CDR(CAR(((a,b),(c,d),(e,f))))
（3）CAR(CDR(CAR(((a,b),(e,f)))))
（4）CDR(CAR(CDR(((a,b),(e,f)))))
（5）CDR(CDR(CAR(((a,b),(e,f)))))
注：CAR运算相当于有些教材中的Head运算，CDR运算相当于Tail运算。
42,利用广义表的Head和Ｔail运算，把原子d分别从下列广义表中分离出来，L1＝(((((a),b),d),e))；L2＝（a,(b,((d)),e））。 【北方交通大学 1996 一、2（5分）】
类似本题的另外叙述有：
(1) 已知广义表L=((((a))),((b)),(c),d)，试利用head和tail运算把原子项c从L中分离出来。
【北京邮电大学 1992 三、2（25/4分）】【青岛海洋大学 1999 一、6 （5分）】
(2) 画出下列广义表的存储结构图，并利用取表头和取表尾的操作分离出原子e。
（ a,（（）,ｂ）,（（（ｅ））））。
【清华大学 1995 二 （10分）】
(3) 已知广义表A=((a,b,c),(d,e,f)) 试写出从表A中取出原子元素e的运算。
【西安电子科技大学 1996 二、3 （5分）】
(4)请将香蕉banana用工具 H( )—Head( )，T( )—Tail( )从L中取出。
L=(apple,(orange,(strawberry,(banana)),peach),pear)
【北京邮电大学 2000 三、2 （5分）】
(5) 试利用广义表取表头head(ls)和取表尾tail(ls)的基本运算，将原子d从下列表中分解出来，请写出每一步的运算结果。
L=((a,(b)),((c,d)),(e,f)) 【北京工商大学 2001 三 （10分）】
(6) 画出广义表A=（a,（b,()）,(((),c))）的第一种存储结构（表结点第二指针指向余表）图，并用取首元（head()）和取尾元（tail()）函数表示原子c。【北京工业大学 2001 二、2 (5分)】
43,画出下列广义表的两种存储结构图((),A,(B,(C,D)),(E,F))。【南京航空航天大学 1999 三（10分）】
44,假设采用以下两种结点的链表作为广义表的存贮结构，表结点：(tag=1,hp,tp),元素结点；(tag=0,data)。请画出下列广义表的存储结构图，并求它的深度和长度。
( ( ),( ( ( ) ),( ( ( ) ) ) ) )
【北方交通大学 1998 一（13分）】
45．知广义表A=（（（a）），（b），c，（a），（（（d，e））））
（1）画出其一种存贮结构图；
（2）写出表的长度与深度；
（3）用求头部，尾部的方式求出e。【东北大学 1997 一、2 (5分)】
46．画出具有共享结构广义表（（（b,c）,d）,(a),((a),((b,c),d)),e,()）的存贮表示。
【北京工业大学 1996 一、3 (6分)】
47,广义表的结点结构如下:(TAG,DATA,LINK)。其中LINK为指向表中下一元素的指针;TAG为标志域；DATA为数据域，具体含义如下,TAG=0表示该结点为原子结点，DATA为其数据；TAG=1表示该结点为一个子表，DATA为指向该子表的指针。
（1）说明下列算法A的功能(注:算法中p,t,m,n,r,q为指针;算法中的NIL对应图中的^)
PROCEDURE A(p,t)
BEGIN
q:=NIL;
WHILE p<>NIL DO
BEGIN
IF p^.TAG<>0 THEN
BEGIN
m:=p^.DATA;
A(m,n);
p^.DATA:=n;
END;
r:=p^.LINK;
p^.LINK:=q;
q:=p;
p:=r
END;
t:=q;
END.
（2）对于 p所指的广义表,画出执行算法A后的表结构以及p，t的值:
【北方交通大学 1993 六（20分）】
类似本题的另外叙述有：
题目基本相同，差别仅在于子表(b,c)与原子d的前后顺序颠倒。【浙江大学 1994 六 (7分)】
48,写出对广义表A=(x,((a,b),c,d))作运算head(head(tail(A)))后的结果。
【西安电子科技大学 2000计应用 一、5（5分）】
49．写出广义表的运算结果,TAIL[HEAD[TAIL[((a,b),(c,d))]]]=?
【武汉交通科技大学 1996 二、7 (3分)】
50,广义表中原子个数是否即为广义表的长度？ 【西安电子科技大学 2000计应用一、9（5分）】
51,给出下列所示的3元多项式的广义表表示（分别以X1，X2，X3第一到第三层变元）
P（X1X2X3）=X15X23X3+2X15X22X34+5X15X23X33+3X1X24X32+X2X3+6
【华南理工大学 2001 一、2（4分）】
52,设某表H如下：
A
B
C
X
a1
a2
b1
c1
c2
其中A,B,C为子表名，a1,a2,b1,c1,c2,x为其元素。
（1）试用广义表形式表示H,并写出运算HEAD(H)和TAIL(H) 函数从H中取出单元素a2的运算；
（2）画出表H的链式存储结构；【北京科技大学 1998 三（10分）】
五 算法设计题
1,设有大小不等的n?个数据组（n个数据组中数据的总数为m），顺序存放在空间区D内,每个数据占一个存储单元，数据组的首地址由数组S给出，（如下图所示），试编写将新数据x插入到第i个数据组的末尾且属于第i 个数据组的算法，插入后，空间区D和数组S的相互关系仍保持正确。
【东北大学 2000 六 (15分)】
2,以三元组表存贮的稀疏矩阵A，B非零元个数分别为m和n。试用类PASCAL语言编写时间复杂度为O（m+n）的算法将矩阵B加到矩阵A上去。A的空间足够大，不另加辅助空间。要求描述所用结构。
【北京工业大学 1997 三 (10分)】
3,设整数x1,x2,…,xN已存放在数组A中，编写一PASCAL递归过程，输出从这n个数中取出所有k 个数的所有组合（k<=n）。例：若A中存放的数是1，2，3，4，5，k为3，则输出结果应为：543，542，541，532，531，521，432，431，421，321。 【山东大学 1992 五 (13分)】
类似本题的另外叙述有：
（1）题目基本相同，只是叙述不同，要求用PASCAL语言。【东南大学 2001 三 （10分）】
4．编写一个过程，对一个n×n矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。
【中科院软件所 1996 】
5,设原来将N个自然数1,2,…,N按某个顺序存于数组A中，经过下面的语句计算，使A[I]的值变为A[1]到A[I-1]中小于原A[I]值的个数。
FOR I:=N DOWNTO 1 DO
BEGIN
C：=0；
FOR J：=1 TO I-1 DO
IF A[J]<A[I] THEN C：=C+1；
A[I]：=C
END；
编程将经过上述处理后的A还原成原来的A。 【上海大学 1996 二 （16分）】
6．请编写完整的程序。如果矩阵A中存在这样的一个元素A[i,j]满足条件:A[i,j]是第i行中值最小的元素,且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵A的所有马鞍点。 【上海大学 2000 三 （20分）】【中科院自动化所 1997】
7．给定一个整数数组b[0..N-1]，b中连续的相等元素构成的子序列称为平台。试设计算法，求出b中最长平台的长度。【中科院计算所 1999 五、2 （20分）】
8,给定nxm矩阵A[a..b,c..d],并设A[i,j]≤A[i,j+1](a≤i≤b,c≤j≤d-1)和A[i,j]≤A[i+1,j](a≤i≤b-1,c≤j≤d).设计一算法判定X的值是否在A中,要求时间复杂度为O(m+n)。【东南大学2001六(13分)】
类似本题的另外叙述有：
（1）给定整型数组B[0..m,0..n] 。已知B中数据在每一维方向上都按从小到大的次序排列，且整型变量x在B中存在。试设计一个程序段找出一对满足B[i,j]=x的(i,j)值，要求比较次数不超过m+n.。
【清华大学 1998 六（10分）】
(2) 给定n×m矩阵A[a..b,c..d]，并设A[i,j]<=A[i,j+1]（a<=i<=b,c<=j<=d-1）知A[i,j]<=A[i+1,j],(a<=i<=b-1,c<=j<=d)。设计一算法以比O(n*m)小的最坏时间复杂性判定值x是否在A中。【东南大学1994三(17分)】
9,编写算法，将自然数1～n按“蛇形”填入n×n矩阵中。例（1～4）如图所示：（用程序实现）
【南京航空航天大学 1997 八 （12分）】 【中科院计算所 1996】
10,设二维数组a[1..m,1..n] 含有m*n 个整数。
(1) 写出算法(pascal过程或c函数)：判断a中所有元素是否互不相同?输出相关信息(yes/no)；
(2) 试分析算法的时间复杂度。【华中理工大学 1999 五 （10分）】
11,二项式(a+b)n展开式的系数为
C（n，0）=1，C（n，n）=1，对于n>=0
C（n，k）=C（n-1，k）+C（n-1，k-1），对于0<k<n 形成著名的杨辉三角形，如图所示。
(1)试写一个递归算法，根据以上公式生成C（n,k）。（6分）
(2)试画出计算C（6，4）的递归树。（4分）
(3)试写一个非递归算法，既不用数组也不用栈，对于任意的0<=k<=n计算C(n,k)（6分）
【清华大学 1999 五 （16分）】
12,设任意n个整数存放于数组A(1:n)中，试编写程序，将所有正数排在所有负数前面（要求算法复杂性为0( n)）。 【山东大学 1993 三 (12分)】.
类似本题的另外叙述有：
（1）已知数组A[1..n]的元素类型为整型，设计算法调整A，使其左边的所有元素小于零，右边的所有元素大于等于零。（要求算法的时间复杂度和空间复杂度均为0（n））
【北京理工大学 2000 四、1 （4分）】
（2）设计一个算法，把整数数组中所有的偶数放到所有的奇数之前。要求时间、空间效率尽可能高。
【华南师范大学 1999 六、1 (10分)】
（3）设一系列正整数存放在一个数组中，试设计算法，将所有奇数存放在数组的前半部分，将所有的偶数存放在数组的后半部分。要求尽可能少用临时存储单元并使时间最少。请试着分析你实现的算法的时间复杂度和空间复杂度。 【南开大学 2000 三、2】
（4）设计算法将数组A[1..n]调整为左右两部分，使的左边所有的元素小于右边的所有元素，并给出这一划分的分界位置。要求算法的时间复度为O(n)。 【合肥工业大学 2001 五、3 （8分）】
13.若S是n个元素的集合，则S的幂集P(S)定义为S所有子集的集合。例如,S=(a,b,c),P(S)={(),(a),(b),(c),(a,b),(a,c),(b,c),(a,b,c)}给定S，写一递归算法求P(S)。
【东南大学 1993 五 （15分）】【东南大学 1997 五 （15分）】
14．编写算法打印出由指针Hm指向总表头的以十字链表形式存储的稀疏矩阵中每一行的非零元的个数。注意：行、列及总表头结点的形式为：
row
col
val
down
right
它们已用val域链接成循环链表。非零元的结点形式也同上，每一行（列）的非零元由right（down）域把它们链接成循环链表，该行（列）的表头结点即为该行（列）循环链表的表头。
【上海大学 1998 五 （16分）】
15,试编写建立广义表存储结构的算法，要求在输入广义表的同时实现判断、建立。设广义表按如下形式输入（a1,a2,a3,…,an） n>=0，其中ai或为单字母表示的原子或为广义表，n=0时为只含空格字符的空表。(注:算法可用类pascal 或类c书写) 【北京工业大学 1998 十 (15分)】
16,广义表是n(n>=0)个数据元素a1,a2,a3,…,an的有限序列。其中ai (1<=i<=n)或者是单个数据元素（原子），或仍然是一个广义表。广义表的结点具有不同的结构，即原子结点和子表元素结点，为了将两者统一，用了一个标志tag，当其为0时表示是原子结点，其data域存储结点值，link域指向下一个结点，当其tag为1时表示是子表结点，其sublist为指向子表的指针。因此，广义表可采用如下结构存储：
TYPE glist=^gnode;
gnode=RECORD
link:glist;
CASE tag:0..1 OF
0:(data:char);
1:(sublist:glist)
END;
（1）画出广义表((a,b),c)的存储结构；
（2）写出计算一个广义表的原子结点个数的递归算法表示式；
（3）编写实现上述算法的过程或函数程序。【厦门大学 2002 三 （12分）】
17,广义表GL=(a1,a2,…,an),其中 ak(k=1,2,...,n)或是单个数据元素（原子），或仍然是个广义表。给定如下有关广义表的类型定义：
TYPE tagtype=0..1;
glist=^gnode;
gnode=RECORD
link:glist; {link 域指向下一个结点}
CASE tag:tagtype OF ｛tag=0 表示原子结点｝
0,(data,integer);
1:(sublist,glist)
END;
编写一个过程或函数计算一个广义表的所有原子结点数据域之和，例如对广义表(3,(2,4,5),(6,3）) 数据域之和为23。【厦门大学 2000 四、2 （9分）】
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分）】
