它在数组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)__。
25. 已知广义表A=(9,7,( 8,10,(99)),12)，试用求表头和表尾的操作Head( )和Tail( )将原子元素99从A中取出来。
26. 广义表的深度是_______。【北京轻工业学院 2000 一、1（2分）】 27. 广义表(a,(a,b),d,e,((i,j),k))的长度是（1）_，深度是（2）_。【山东大学 2001 三、9 (2分)】 28. 已知广义表LS=(a，(b，c，d)，e),运用head和tail函数取出LS中原子b的运算是_______。 29. 广义表A=（（（a，b），（c，d，e））），取出A中的原子e的操作是: _______。 30. 设某广义表H=（A，（a,b,c）） ，运用head函数和tail函数求出广义表H中某元素b的运算式_______。 31. 广义表A((( ),(a,(b),c)))，head(tail(head(tail(head(A))))等于 。 32. 广义表运算式HEAD(TAIL(((a,b,c),(x,y,z))))的结果是_______。 33. 已知广义表A=（（（a，b），（c），（d，e））），head（tail（tail（head（A））））的结果是_______。 34. 利用广义表的GetHead和GetTail操作，从广义表L=（（apple，pear），（banana，orange））中分离出原子banana的函数表达式是_______。 【山东大学 2001 三、6 (2分)】
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 a[i]=t; if (1) ; if (i } 【上海大学 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); } 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 {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（“M”,a[i][j]）;printf(“\\n”); } } } 【上海大学 2002 六、1 （10分）】 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) _ , _ 四 应用题 1. 数组A[1..8，-2..6，0..6]以行为主序存储，设第一个元素的首地址是78，每个元素的长度为4，试求元素A[4,2,3]的存储首地址。【厦门大学 1998 五、1 （5分）】 2. 已知b对角矩阵（aij）以行主序将b条对角线上的非零元存储在一维数组中，每个数据元素占Ｌ个存储单元，n*n， 存储基地址为Ｓ，请用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）所在的地址。 6. 三维数组A[1..10,-2..6,2..8]的每个元素的长度为4个字节，试问该数组要占多少个字节的存储空间？如果数组元素以行优先的顺序存贮，设第一个元素的首地址是100，试求元素A[5,0,7] 的存贮首地址。 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按列优先方式存储时的哪个元素的起始地址一致？ 9. 若按照压缩存储的思想将n×n阶的对称矩阵A的下三角部分（包括主对角线元素）以行序为主序方式存放于一维数组B[1..n(n+1)/2]中，那么，A中任一个下三角元素aij(i≥j),在数组B中的下标位置k是什么？ 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]的第一个字节的地址是多少? 14. 设有三对角矩阵(ai,j)m╳n,将其三条对角线上的元素逐行的存于数组B(1:3n-2)中，使得B[k]=ai,j，求： 3 （1）用i,j表示k的下标变换公式；（2）若n=10,每个元素占用L个单元，则用B[K]方式比常规存储节省多少单元15. 已知A为稀疏矩阵，试从空间和时间角度，比较采用两种不同的存储结构（二维数组和三元组表）完成求运算的优缺点。【西安电子科技大学 1996 二、6（5分）】 16. 特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能？为什么？ 17. 试叙述一维数组与有序表的异同。【西安电子科技大学 1999计应用一、2（5分）】 18. 一个n╳n的对称矩阵，如果以行或列为主序存入内存，则其容量为多少？ 19. 给出数组 A∶ARRAY[3..8,2..6] OF INTEGER;当它在内存中按行存放和按列存放时，分别写出数组元素A[i,j]地址计算公式（设每个元素占两个存储单元）。【南开大学 1998 一 (8分)】 20. 已知n阶下三角矩阵A（即当i 主对角线上元素 )依次存放于一维数组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的下标变化公式。 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； 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]] 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分)】 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。 30. 设有上三角矩阵(aij)n*n，将其上三角中的元素按先行后列的顺序存于数组B（1:m）中，使得B[k]= aij且k=f1(i)+f2(j)+c，请推导出函数f1,f2和常数c，要求f1和f2中不含常数项。 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个单元。 35．假定有下列nⅹn矩阵（n为奇数）A= 如果用一维数组B按行主次序存储A的非零元素，问： （1）A中非零元素的行下标与列下标的关系； （2）给出A中非零元素aij 的下标(i,j)与B中的下标R的关系; （3）假定矩阵中每个元素占一个存贮单元且B的起始地址为A0，给出利用aij的下标(i,j)定位在B中的位置公式。 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）则不给分） 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中分离出来。 (2) 画出下列广义表的存储结构图，并利用取表头和取表尾的操作分离出原子e。 （ a,（（）,ｂ）,（（（ｅ））））。 (3) 已知广义表A=((a,b,c),(d,e,f)) 试写出从表A中取出原子元素e的运算。 (4)请将香蕉banana用工具 H( )—Head( )，T( )—Tail( )从L中取出。 L=(apple,(orange,(strawberry,(banana)),peach),pear) (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分）】