判断题

　　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分）】

[page]

填空题

　　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分）】

[page]

    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】

[page]

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分）】

[page]

　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分）】