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第一到第三层变元）
5352453342
P（X1X2X3）=X1X2X3+2X1X2X3+5X1X2X3+3X1X2X3+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还原成原来的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分）】
n
11. 二项式(a+b)展开式的系数为
C（n，0）=1，C（n，n）=1，对于n>=0 C（n，k）=C（n-1，k）+C（n-1，k-1），对于0 (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 seek I n 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分）】