数据结构 第5章 数组和广义表 练习题

（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））。

类似本题的另外叙述有：

(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))

(6) 画出广义表A=（a,（b,()）,(((),c))）的第一种存储结构（表结点第二指针指向余表）图，并用取首元（head()）和取尾元（tail()）函数表示原子c。 43. 画出下列广义表的两种存储结构图((),A,(B,(C,D)),(E,F))。

44. 假设采用以下两种结点的链表作为广义表的存贮结构，表结点：(tag=1,hp,tp), 元素结点；(tag=0,data)。请画出下列广义表的存储结构图，并求它的深度和长度。 ( ( ) , ( ( ( ) ) , ( ( ( ) ) ) ) ) 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,()）的存贮表示。 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的值:

p0a10d0e?0b0c?类似本题的另外叙述有：

题目基本相同，差别仅在于子表(b,c)与原子d的前后顺序颠倒。【浙江大学 1994 六 (7分)】

48. 写出对广义表A=(x,((a,b),c,d))作运算head(head(tail(A)))后的结果。 49．写出广义表的运算结果: TAIL[HEAD[TAIL[((a,b),(c,d))]]]=? 50. 广义表中原子个数是否即为广义表的长度？

51. 给出下列所示的3元多项式的广义表表示（分别以X1，X2，X3第一到第三层变元）

P（X1X2X3）=X15X23X3+2X15X22X34+5X15X23X33+3X1X24X32+X2X3+6 52. 设某表H如下：

A a1

B a2 b1

C c1

X c2

其中A,B,C为子表名，a1,a2,b1,c1,c2,x为其元素。

（1）试用广义表形式表示H,并写出运算HEAD(H)和TAIL(H) 函数从H中取出单元素a2的

运算； （2）画出表H的链式存储结构；

五 算法设计题

1. 设有大小不等的n 个数据组（n个数据组中数据的总数为m），顺序存放在空间区D内,每个数据占一个存储单元，数据组的首地址由数组S给出，（如下图所示），试编写将新数据x插入到第i个数据组的末尾且属于第i 个数据组的算法，插入后，空间区D和数组S的相互关系仍保持正确。

2. 以三元组表存贮的稀疏矩阵A，B非零元个数分别为m和n。试用类PASCAL语言编写时间复杂度为O（m+n）的算法将矩阵B加到矩阵A上去。A的空间足够大，不另加辅助空间。要求描述所用结构。

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。 类似本题的另外叙述有：

（1）题目基本相同，只是叙述不同，要求用PASCAL语言。【东南大学 2001 三 （10分）】 4．编写一个过程，对一个n×n矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。 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]

END；

编程将经过上述处理后的A还原成原来的A。

6．请编写完整的程序。如果矩阵A中存在这样的一个元素A[i,j]满足条件:A[i,j]是第i行中值最小的元素,且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵A的所有马鞍点。

7．给定一个整数数组b[0..N-1]，b中连续的相等元素构成的子序列称为平台。试设计算法，求出b中最长平台的长度。

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)。

类似本题的另外叙述有： （1）给定整型数组B[0..m,0..n] 。已知B中数据在每一维方向上都按从小到大的次序排列，且整型变量x在B中存在。试设计一个程序段找出一对满足B[i,j]=x的(i,j)值，要求比较次数不超过m+n.。

(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中。

9. 编写算法，将自然数1～n按“蛇形”填入n×n矩阵中。例（1～4）如图所示：（用

程序实现）

12635849121011157131416

10. 设二维数组a[1..m, 1..n] 含有m*n 个整数。

(1) 写出算法(pascal过程或c函数)：判断a中所有元素是否互不相同?输出相关信息(yes/no)；

(2) 试分析算法的时间复杂度。 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

(1)试写一个递归算法，根据以上公式生成C（n,k）。（6分） (2)试画出计算C（6，4）的递归树。（4分）

(3)试写一个非递归算法，既不用数组也不用栈，对于任意的0<=k<=n计算C(n,k)（6分）

11118728621561151415357013102035561261310141521281567811111n=0n=1n=2n=3n=4n=5n=6n=7n=812． 设任意n个整数存放于数组A(1:n)中，试编写程序，将所有正数排在所有负数前面（要求算法复杂性为0( n)）。. 类似本题的另外叙述有： （1）已知数组A[1..n]的元素类型为整型，设计算法调整A，使其左边的所有元素小于零，右边的所有元素大于等于零。（要求算法的时间复杂度和空间复杂度均为0（n）） （2）设计一个算法，把整数数组中所有的偶数放到所有的奇数之前。要求时间、空间效率尽可能高。

（3）设一系列正整数存放在一个数组中，试设计算法，将所有奇数存放在数组的前半部分，将所有的偶数存放在数组的后半部分。要求尽可能少用临时存储单元并使时间最少。请试着分析你实现的算法的时间复杂度和空间复杂度。

（4）设计算法将数组A[1..n]调整为左右两部分，使的左边所有的元素小于右边的所有元素，并给出这一划分的分界位置。要求算法的时间复度为O(n)。

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)。

14．编写算法打印出由指针Hm指向总表头的以十字链表形式存储的稀疏矩阵中每一行的非

零元的个数。注意：行、列及总表头结点的形式为：

row col val down right

它们已用val域链接成循环链表。非零元的结点形式也同上，每一行（列）的非零元由right（down）域把它们链接成循环链表，该行（列）的表头结点即为该行（列）循环链表的表头。 15. 试编写建立广义表存储结构的算法，要求在输入广义表的同时实现判断、建立。设广义表按如下形式输入（a1,a2,a3,?,an） n>=0，其中ai或为单字母表示的原子或为广义表，n=0时为只含空格字符的空表。(注:算法可用类pascal 或类c书写)

16. 广义表是n(n>=0)个数据元素a1,a2,a3,?,an的有限序列。其中ai (1<=i<=n)或者是单个数据元素（原子），或仍然是一个广义表。广义表的结点具有不同的结构，即原子结点和