我下vip免费资源网 www.woxia.net 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 a1 a2 B b1 c1 C c2 X 其中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语言编写时
我下vip免费资源网 www.woxia.net 间复杂度为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）如图所示：（用程序实现）
我下vip免费资源网 www.woxia.net
【南京航空航天大学 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 (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)。 我下vip免费资源网 www.woxia.net 【东南大学 1993 五 （15分）】【东南大学 1997 五 （15分）】 14．编写算法打印出由指针Hm指向总表头的以十字链表形式存储的稀疏矩阵中每一行的非 零元的个数。注意：行、列及总表头结点的形式为： row down col val 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 我下vip免费资源网 www.woxia.net 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分）】 我下vip免费资源网 www.woxia.net