第五章 数组和广义表

第五章 数组和广义表 一、选择题

1．设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

A．688 B．678 C．692 D．696 2．设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为（ ）。

A. 10 B. 19 C. 28 D. 55

3．在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相

同的（ ）。

A．行号 B．列号 C．元素值 D．地址

4．设有50行60列的二维数组A[50][60]，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A[18][25]的存储地址为（）。

A．3700 B．4376 C．3900 D．4620 5．数组A［0..5］［0..5］的每个元素占5个字节，将其以列为主序存储在起始地址为1000的内存单元中，则元素A［5］［5］的地址是（ ） A.1175 B.1180 C.1205 D.1210

?124???35???， 则A［i］6. 设有二维数组A［n］［n］表示如下：?［i］（0≤

?6???????i≤n-1）的值为（ ）

A．i*(i-1)/2 B.i*(i+1)/2 C.(i+2)*(i+1)/2 D.i2/2 7．二维数组A［10］［20］采用按行为主序的存储方式，每个元素占4个存储单元，若A［0］［0］的存储地址为300，则A［10］［10］的地址为（ ） A.700 B.1120 C.1180 D.1140 8．设有一5阶上三角矩阵A［1..5，1..5］，现将其上三角中的元素按列优先顺序存放在一堆数组B［1..15］中。已知B［1］的地址为100，每个元素占用2个存储单元，则A［3，4］的地址为（ ）

A．116 B．118 C．120 D．122

9．在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的（ ）。

A.行号 B. 列号 C.元素值 D.地址

10．设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为（ ）。

A. O(1) B. O(n) C. O(n2) D. O(log2n)

11．设有一个10阶的对称矩阵A[10][10]，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B[ ]中，A[0][0]存入B[0]中，则A[8][5]在B[ ]

1

中（ ）位置。

A．32 B．33 C．41 D．65 12．设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为( B )。 A. 13 B. 33 C. 18 D. 40 13．数组通常具有的两种基本操作是（ A ）。

A.查找和修改 B. 查找和索引 C. 索引和修改 D.建立和删除

14．数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( A )。

A. 1175 B. 1180 C. 1205 D. 1210

15．若6行5列的数组以列序为主序顺序存储，基地址为1000，每个元素占2个存储单元，则第3行第4列的元素（假定无第0行第0列）的地址是(A)。 A. 1040 B. 1042 C. 1026 D.备选答案A，B，C都不对 16．稀疏矩阵一般的压缩存储方法有两种，即( C )。 A.二维数组和三维数组 B.三元组和散列 C.三元组和十字链表 D.散列和十字链表

17．若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（i

A. i*(i-1)/2+j B. j*(j-1)/2+i C. i*(i+1)/2+j D. j*(j+1)/2+i 18．A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N(N+1)/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（B ）。 A. i（i-1）/2+j B. j（j-1）/2+i C. i（j-i）/2+1 D. j（i-1）/2+1 19．设有一个n行n列的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]存放于B中( A )处。

A.(i+3)*i/2 B. (i+1)*i/2 C. (2n-i+1)*i/2 D.(2n-i-1)*i/2

20．用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j 沿链移动的操作为(A )。

A. j=r[j].next B. j=j+1 C. j=j->next D. j=r[j]-> next 21．对矩阵压缩存储是为了(D )。

A.方便运算 B.方便存储 C.提高运算速度 D.减少存储空间 22．一个非空广义表的表尾( B )。

A. 不能是子表 B. 只能是子表 C. 只能是原子 D. 是原子或子表 23．某字符串满足：concat(head(s),head(tail(tail(s))))=“ac”,(head,tail的定义同广义表),则S=( C ) 。

A. aabc B. acba C. accc D. acac

24．将线性表的数据元素进行扩充，允许是带结构的线性表是( C ）。 A. 串 B. 树 C. 广义表 D. 栈

25．广义表（（a,b,c,d））的表头是(C )，表尾是( B)。

A. a B.（） C.（a,b,c,d） D.（b,c,d） 26．已知Head(Tail([Head(S),Head(Tail(Tail(S)))]))=[a]，广义表S满足上式，则S为( F )(其中，方括号表示广义表，圆括号表示函数，如[a,b]表示由

2

a,b 构成的广义表，而Head()表示取广义表的头部）。

A.[[a,b],b,a] B.[[b,a],[a],[b]] C.[[a],[a,b],[b]] D.[b,[a],[a,b]] E.[[a],[b],[b,a]] F.[[b],[b,a],[a]] 27．下面说法不正确的是( A )。

A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表 C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构 28．广义表（（））的表头是( A )，表尾是( A )。

A.（） B. NIL C. （（）） D.（（（））） 29．将一个A[1..100][1..100]的三对角矩阵，按行优先存入一维数组B[1..298]中，A中元素a66,65（即该元素下标i=66，j=65）在B数组中的位置K为（A ） A 195 B 196 C 197 D 198 30．广义表 ((a)) 的表尾是（ C ） A、a B、(a) C、( ) D、((a))

31．已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果:

tail(head(tail(C))) =( F )。 A.（a） B. A C. a D. (b) E. b F. (A) 32．设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为( B )。

A. i(i-l)/2+j B. j(j-l)/2+i C. j(j-l)/2+i-1 D. i(i-l)/2+j-1

33. 对矩阵压缩存储是为了（ D ）。

A.方便运算 B.方便存储 C.提高运算速度 D.减少存储空间 34. 下面说法不正确的是: （ ）

A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表 C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构 【解答】A

二、填空题

1．设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_______个数据元素。i(i+1)/2+j-1

2．从一维数组a[n]中顺序查找出一个最大值元素的时间复杂度为________，输出一个二维数组b[m][n]中所有元素值的时间复杂度为________。O(n)、O(m*n) 3．在稀疏距阵所对应的三元组线形表中，每个三元组元素按____________为主序，__________为辅序的次序排列。行号，列号

4．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为________________域和______________域。值（或data）， 子表指针（或sublist）

5．对稀疏矩阵进行压缩存储的目的是节省______存储空间______。 6．设数组A［0..8］［0..8］的起始元素位置为a，每个元素占2 L个存储单元，按行序为主序存储。若元素A［i］［j］的存储位置为a+66 L，则元素A［j］［i］

3

的存储位置为a+120L_______。

7．二维数组在机器级的具体实现，通常均采用__顺序和二叉链表___存储结构。 8．在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的________、________和________三项。行号、列号、元素值

9．在稀疏矩阵所对应的三元组线性表中，每个三元组元素按________为主序、________为辅序的次序排列。行号、列号

10．在稀疏矩阵的顺序存储中，利用一个数组来存储非零元素，该数组的长度应________对应三元组线性表的长度。等于

11．在稀疏矩阵的带行指针向量的链接存储中，每个结点包含有________个域，在相应的十字链接存储中，每个结点包含有________个域。4 、5

12．在稀疏矩阵的十字链接存储中，每个结点的down指针域指向________相同的下一个结点，right指针域指向________相同的下一个结点。列号、行号 13．一个广义表中的元素分为________元素和________元素两类。单、表 14．一个广义表的深度等于________嵌套的最大层数。括号

15．在广义表的存储结构中，每个结点均包含有________个域。3

16．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为________域和________域。元素值、子表指针 17．若把整个广义表也看为一个表结点，则该结点的tag域的值为________，next域的值为________。true、NULL

18．设二维数组A的行和列的下标范围分别为[0：8]和[0：10]，每个元素占2个单元，按行优先顺序存储，第一个元素的存储起始位置为b，则存储位置为b+50处的元素为 。A[2][3]

19．设数组a[1..50,1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45,68]的存储地址为_（1）_;若以列序为主序顺序存储，则元素a[45,68]的存储地址为_（2）_。（1）9174（2）8788

20．三维数组a[4][5][6]（下标从0开始计，a有4*5*6个元素），每个元素的长度是2，则a[2][3][4]的地址是____。(设a[0][0][0]的地址是1000,数据以行为主方式存储) 1164

公式：LOC(aijk)=LOC(a000)+[v2*v3*(i-c1)+v3*(j-c2)+(k-c3)]*l (其中，l为每个元素所占单元数,vi是第i维的元素个数=(di-ci+1)，ci和di分别是第i维的界偶。)

21．已知二维数组A[1..10，0..9]中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，A[5，9]的地址是：_______。1196 22．用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j](1≤i≤n,i-2≤j≤i+2),B中的第8个元素是A中的第（1）_行，第（2）_列的元素。第1行第3列，这是一个五对角矩阵。 23．设数组A[0..8,1..10],数组中任一元素A[i,j]均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么 （l） 存放该数组至少需要的单元数是_______;

（2） 存放数组的第8列的所有元素至少需要的单元数是_______; （3） 数组按列存储时，元素A[5,8]的起始地址是_______。 (1)270 (2)27 (3)2204

24．己知三对角矩阵A【1..9,1..9】的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为1000的连续的内存单元中，则元素A[7,8]的

4

地址为______。

1038 三对角矩阵按行序存储的地址公式：k=2(i-1)+j (1<=i,j<=n) 25．所谓稀疏矩阵指的是_______。非零元很少(t<

27．设广义表L=((),()), 则head(L)是(1)___；tail(L)是(2)____；L的长度是(3)___；深度是 (4)__。（1）（） （2）（（）） （3）2 （4）2 28．广义表(a,(a,b),d,e,((i,j),k))的长度是（1）_，深度是（2）_。 （1）5 （2）3

29．设有广义表Ａ＝(((a,b), x), ((a),(b)),(c,(d, (y))))，得到 y的对广义表Ａ的操作序列是_____。head(head(tail(head(tail(head(tail(tail(A))))))))

30．Tail[Tail[Head[(((a,b),((c))),(d),((e,f)))]]]的运算结果是______，其中“[]”是函数的符号；() 31．已知广义表A=（（（a，b），（c），（d，e））），head（tail（tail（head（A））））的结果是_______。(d,e)

32. 广义表((a,b),c,d)的表头是 ,表尾是 。(a,b) 、 (c,d) 三、判断题 1．（ ）二维数组和多维数组均不是特殊的线性结构。F 2．（ ）稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。T

3．（ ）从逻辑结构上看，n维数组的每个元素均属于n个向量。√ 4．（ ）数组是同类型值的集合。×

5．( )二维以上的数组其实是一种特殊的广义表。√ 6．（ ）广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。×

7．（ ）所谓取广义表的表尾就是返回广义表中最后一个元素。×

8．（ ）广义表的同级元素（直属于同一个表中的各元素）具有线性关系。√ 9．（ ）对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。√

10．（ ）一个广义表可以为其它广义表所共享。√ 11．（ ）数组是一种线性结构，因此只能用来存储线性表。× 12．（ ）广义表（（（a,b,c）,d,e,f））的长度是4。× 13．( ) 广义表的深度是指其中所含的不同原子的个数。X

14．（ ）若一个广义表的表头为空表，则此广义表亦为空表。× 15．（ ）稀疏矩阵压缩存储后，必会失去随机存取功能。√

四、简答题

1．数组A[0..8, 1..10] 的元素是6 个字符组成的串，则存放A至少需要多少个字节？ A 的第8列和第5行共占多少个字节 ？若A 按行优先方式存储，元素A[8,5]的起始地址与当A按列优先方式存储时的哪个元素的起始地址一致？ 【厦门大学 2000 五.3（14%/3分）】

（1）540 （2）108 （3）i=3,j=10，即A[3,10] 2．设有三对角矩阵(aij)n*n，将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得B[k]=aij，求：

5

WHILE(8) _DO

BEGIN c[k]:=d[j]; k:=k+1; j:=j+1；END; END. {sort}

【解答】本算法中，首先数组b中元素以逆置顺序放入d数组中，然后数组a和数组d的元素比较，将大者拷贝到数组c。第一个WHILE循环到数组a或数组d结尾，第二个和第三个WHILE语句只能执行其中的一个。 （1）b[m-i+1] （2）x:=a[i] （3）i:=i+1 （4）x:=d[j] （5）j:=j+1 （6）k:=k+1 （7）i<=l （8）j<=m

3．完善下列程序，每小题在PASCAL语言（a）和C语言（b）中任选一题。下面是一个将广义表逆置的过程。例如原来广义表为（（a,b）,c,（d,e）），经逆置后为：（（e,d）,c,（b,a））。 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); }

【解答】逆置广义表的递归模型如下

11

上面append(a,b)功能是将广义表a和b作为元素的广义表连接起来。 （1）(p->tag==0) ∥处理原子 （2）h=reverse(p->val.ptr.hp) ∥处理表头

（3）(p->val.ptr.tp) ∥产生表尾的逆置广义表 （4）s->val.ptr.tp=t; ∥连接

（5）q->val.ptr.hp=h ∥头结点指向广义表

4．完善下列程序，每小题在PASCAL语言（a）和C语言（b）中任选一题。下面的程序将数列1,2,3,?,n*n,依次按蛇型方式存放在二维数组A[1..n,1..n]中。即 (示意圖编者略)。 #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”); } } }

【解答】本题要求将1，2，...,n*n个自然数，按蛇形方式存放在二位数组A[n][n]中。“蛇型”方式，即是按“副对角线”平行的各对角线，从左下到右上，再从右上到左下，存放n2个整数。对角线共2n-1条，在副对角线上方的对角线，题目中用k表示第k条对角线（最左上角k=1），数组元素的x和y方向坐标之和为k+1（即题目中的i+j=k+1）。副对角线下方第k条对角线与第2n-k条对角线对称，其元素的下标等于其对称元素的相应坐标各加(k-n)。 (1)k<=2*n-1∥共填2*n-1条对角线

(2)q=2*n-k ∥副对角线以下的各条对角线上的元素数

12

(3)k%2！=0 ∥k为偶数时从右上到左下，否则从左下向右上填数(本处计算下标i和j）

(4)k>=n ∥修改副对角线下方的下标i和j。

(5)m++；或m=m+1 ∥为填下个数作准备，m变化范围1..n*n。 本题解法的另一种思路见本章算法设计题第9题。

5．约瑟夫环问题：设有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;

【解答】本题难点有二：一是如何求下一出圈人的位置，二是某人出圈后对该人的位置如何处理。

按题中要求，从第s个人开始报数，报到第m个人，此人出圈。n个人围成一圈，可看作环状，则下个出圈人，其位置是(s+m-1)%n。n是人数，是个变量，出圈一人后人数减1，算法中用i表示。对第二个问题，算法中用出圈人后面人的位置依次前移，并把出圈人的位置（下标）存放到当时最后一个人的位置（下标）。算法最后打印出圈人的顺序。 (1)(s+m-1)MOD i∥计算出圈人s1

(2)s1:=i ∥若s1=0,说明是第i个人出圈（i%i=0）

(3)s1 TO i-1 ∥从s1到i依次前移,人数减1,出圈人放到当前最后一个位置A[i]=w

6．对于正整数n,输出其和等于n且满足以下限制条件的所有正整数的和式，组成和式的数字自左至右构成一个非递增的序列，如n=4，程序输出为； 4=4 4=3+1 4=2+2 4=2+1+1 4=1+1+1+1

test 是实现该功能的C程序段，请将未完成的部分补足，使之完整。test函数为一递归函数，参数n为被分解和式的数，k为当前的分解深度。算法思想是对n的所有合理的和式分解，将分解出的数（称为和数）存于数组a[]中。当其中一个分解已不再需要进一步进行时，即找到一个解，将存于a[] 中的一个完整

13

和式的和数输出。当还需要进一步分解的数及分解时，以要进一步分解的数及分解深度为参数，递归调用test函数。 #define MAXN 100 int a[MAXN]；

test(int n, int k) {int i,j;

for(j= ; j>=1;j--) (3分) {a[k]=j;

if( ) (3分) {printf(“%d= %d”,a[0],a[1]);

for (i=2;i<=k;i++) printf(“ + %d”,a[i]); printf(“\\n”);

}

else test( ;k+1); （4分） } } main()

{ test(4,1)； }

【解答】(1)n (2)j==n (3)n-j

七、算法设计题

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

[题目分析]本题是在向量D内插入元素问题。首先要查找插入位置，数据x插入到第i个数据组的末尾，即是第i+1个数据组的开始，而第i（1≤i≤n）个数据组的首地址由数组S（即数组元素S[i]）给出。其次，数据x插入后，还要维护数组S，以保持空间区D和数组S的正确的相互关系。 void Insert（int S[]，ElemType D[]，x，int i,m）

∥在m个元素的D数据区的第i个数据组末尾，插入新数据x，第i个数据组的首址由数组S给出

｛if（i<１|| i>n）｛printf（“参数错误\\n”）；exit（０）；｝

14

if（i==n） D[m]=x； ∥ 在第n个数据组末尾插入元素

else｛for（j=m-1;j>=S[i+1];j--）D[j+1]=D[j]; ∥ 第i＋１个数据组及以后元素后移

D[S[i+1]]=x; ∥ 将新数据x插入

for(j=i+1;j<=n;j++) S[j]++; ∥ 维护空间区D和数组S的的关系 } ∥结束元素插入

m++; ∥空间区D的数据元素个数增1 }∥ 算法Insert结束

[算法讨论] 数据在空间区D中从下标0开始，最后一个元素的下标是m-1。设空间区容量足够大，未考虑空间溢出问题。数组S随机存数，而向量D数据插入，引起数组元素向后移动，时间复杂度是O（n）。

2．设整数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。【东南大学2001三(10分）】 [题目分析]从n个数中，取出所有k个数的所有组合。设数已存于数组A[1..n]中。为使结果唯一，可以分别求出包括A[n]和不包括A[n]的所有组合。即包括A[n]时，求出从A[1..n-1]中取出k-1个元素的所有组合，不包括A[n]时，求出从A[1..n-1]中取出k个元素的所有组合。 CONST n=10；k=3；

TYPE ARR=ARRAY[1..n] OF integer；

VAR A，B：ARR；∥ A中存放n个自然数，B中存放输出结果 PROC outresult；∥输出结果

FOR j：=1 TO k DO write（B[j]）；writeln； ENDP；

PROC nkcombination（i,j,k：integer）；

∥从i个数中连续取出k个数的所有组合，i个数已存入数组A中，j为结果数组B中的下标

IF k=0 THEN outresult

ELSE IF(i-k≥0）THEN [B[j]:=A[i]；j:=j+1；

nkcombination（i-1，k-1，j）； nkcombination（i-1，k，j-1）； ]

ENDP；

[算法讨论]本算法调用时，i是数的个数（题目中的n），k≤i，j是结果数组的下标。按题中例子，用nkcombination（5，1，3）调用。若想按正序输出，如123，124，?，可将条件表达式i-k≥0改为i+k-1≤n，其中n是数的个数，i初始调用时为1，两个调用语句中的i-1均改为i+1。 3．请编写完整的程序。如果矩阵A中存在这样的一个元素A[i,j]满足条件:A[i,j]是第i行中值最小的元素,且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵A的所有马鞍点。 【上海大学 2000 三 （20分）】【中科院自动化所 1997】

[题目分析] 寻找马鞍点最直接的方法,是在一行中找出一个最小值元素,然后检查该元素是否是元素所在列的最大元素,如是,则输出一个马鞍点,时间复杂度

15

本文来源：https://www.bwwdw.com/article/vylg.html