admin 管理员组文章数量: 1087139
2024年4月21日发(作者：vb是什么语言表达)
数组和广义表
作业4
单项选择题
1
．有一矩阵为
A[-3:1,2:6]
，每个元素占一个存储单元，存储的首地址为
100
，以行序
为主，则元素
a
-1,4
的地址为（ ）。
A
）
111 B
）
112 C
）
113 D
）
125
【分析】对于二维数组
A[c
1
:d
1
,c
2
:d
2
]
，设每个元素占用
l
个存储单元，
LOC(c
1
,c
2
)
是第
一个元素
a
c
1
,c
2
的存储位置，则按行存放时，
a
ij
的存储位置如下：
LOC(i,j)=LOC(c
1
,c
2
)+[(d
2
-c
2
+1)(i-c
1
)+(j-c
2
)]
l
对于本题，
c
1
=-3
，
c
2
=2
，
d
1
=1
，
d
2
=6
，
l
=1
，
LOC(c
1
,c
2
)=100
，所以元素
a
-1,4
的地址为：
LOC(-1,4)=100+[(6-2+1)*(-1-(-3))+(4-2)]*1=112
。
【答案：
B
】
2
．一
n
×
n
的三角矩阵
A=[a
ij
]
如下：
a
11
a
12
a
22
a
1n
a
2n
a
nn
将三角矩阵中元素
a
ij
(i
≤
j)
按行序为主序的顺序存储在一维数组
(n+1)/2]
中，则
a
ij
在
B
中的位置是（ ）。
A
）
(i-1)(2n+i)/2+i-j+1 B
）
(i-1)(2n-i+2)/2+j-i+1
C
）
(i-1)(2n-i)/2+j-i D
）
(i-1)(2n-i+2)/2+j-i
【分析】存储位置
=n+(n-1)+…+(n-i+2)+i-j+1=(i-1)(2n-i+2)/2+j-i+1
。
【答案：
B
】
3
．广义表
((a,b),(c,d))
的表尾是
(
)
。（四川大学计算机学院
2004
年试题）
A
）
(c,d) B
）
((c,d)) C
）
(d) D
）
d
【分析】广义表
((a,b),(c,d))
可看成是
(d1,d2)
所组成，其中
d1=(a,b)
，
d2=(c,d)
，所以表
尾为
(d2)=((c,d))
。
【答案：
B
】
4
．若广义表
A
满足
Head(A)==Tail(A)
，则
A
为（ ）。（北方名校经典试题）
A
）
() B
）
(()) C
）
((),()) D
）
((),(),())
326
数据结构
【分析】根据广义表
Head
运算和
Tail
运算的定义，可用代入法求解：
A
）
Head(A)
，
Tail(A)
：无定义
B
）
Head(A)=()
，
Tail(A)=()
C
）
Head(A)=()
，
Tail(A)=(()) D
）
Head(A)=()
，
Tail(A)=((),())
【答案：
B
】
二、综合题
1
．有三维数组
A[0:7,0:8,0:9]
，数组的起始地址是
1000
，每个元素长为
2
，试给出下
面结果：（南方名校经典试题）
（
1
）元素
a
1,6,8
的起始地址；
（
2
）数组
a
所占用的存储空间。
【解答】
（
1
）对于三维数组
A[c
1
:d
1
,c
2
:d
2
,c
3
:d
3
]
，设每个元素占用
l
个存储单元，
LOC(c
1
,c
2
,c
3
)
是第一个元素
a
c
1
,c
2
,c
3
的存储位置，则按行存放时，
a
j1,j2,j3
的存储位置如下：
LOC(j1,j2,j3)=LOC(c
1
,c
2
,c
3
)+[ (j1-c
1
) (d
2
-c
2
+1)(d
3
-c
2
+1) +(j
2
-c
2
)(d
3
-c
2
+1)+ (j
3
-c
3
)]
l
对于本题，
c
1
=0
，
c
2
=0
，
c
3
=0
，
d
1
=7
，
d
2
=8
，
d
3
=9
，
l
=2
，
LOC(c
1
,c
2
,c
3
)=1000
，所以元
素
a
1,6,8
的地址为：
LOC(1,6,8)=1000+[(1-0) (8-0+1)(9-0+1) +(6-0)(9-0+1)+(8-0)]*2=1316
。
（
2
）数组
A
所占用的存储空间：
=
数组
a
的元素个数
*
每个元素的长度
=(d
1
-c
1
+1)(d
2
-c
2
+1) (d
3
-c
2
+1)
l
= (7-0+1) (8-0+1)(9-0+1)*2=1440
2
．已知稀疏矩阵如下图所示，试写出三元组表示。（南方名校经典试题）
15
0
0
9
0016
6000
0800
00180
0
【解答】
4
1
1
2
3
4
4
5
1
5
2
3
1
4
6
15
16
6
8
9
18
其中，第一行的（
4
，
5
，
6
）表示稀疏矩阵的行数，列数及非零元素的值，其他各行
为三元组。
3
．若在矩阵
A
n
×
n
中存在一个元素
a
i-1,j-1
满足
a
i-1,j-1
是第
i
行元素中最小值且又是第
j
列元素中的最大值，则称此元素为该矩阵的一个马鞍点。假设以二维数组存储矩阵
A
n
×
n
，
第
9
章
文件与动态存储管理
327
试设计一个求该矩阵所有马鞍点的算法。（北方名校经典试题）
注：本题选择作。
【解答】用数组
S[n]
存储某一行（如第
i
行，
i=1~m
）的元素值最小的元素的下标，
c
表示此行的元素值等于最小值的元素的个数（元素值等于最小值的元素可能不止一个），对
每个元素值最小的元素再验证是否是所在列的元素值最大的元素，如是则为马鞍点，将其输
出。
C++
语言版测试程序见
4_2_3c++
，具体算当如下：
template
void SaddlePoint(ElemType *A,int m,int n)
输出矩阵
A
所有马鞍点
//
{
ElemType *S=new ElemType[n+1]; //
存储某一行的元素值最小元素的下标
int c; //
表示此行的最小值等于最小的元素的个数
int count=0; //
马鞍点的个数
int i,j,k;
ElemType min; //
某一行的最小元素值
for(i=1;i<=m;i++)
{
min=*(A+(i-1)*n+(1-1)); //*(A+(i-1)*n+(1-1))
等价于
A(i,1)
c=1;S[1]=1; //
当前已得的元素值最小的元素下标与个数
for(j=2;j<=n;j++)
if(*(A+(i-1)*n+(j-1)) 等价于 A(i,j) { //A(i,j) min=*(A+(i-1)*n+(j-1)); //A(i,j) 为新的最小值 c=1;S[1]=j; // 当前已得的元素值最小的元素下标与个数 } else if(*(A+(i-1)*n+(j-1))==min) //*(A+(i-1)*n+(j-1)) 等价于 A(i,j) { //A(i,j)==min c++; // 元素值最小的元素值自加 1 S[c]=j; } for(j=1;j<=c;j++) { // 对第 i 行的 c 个元素值最小的元素判断是否是马鞍点 k=1; // 判断是否第 S[j] 列有大于 A(i,S[j]) 的元素 while(k<=m&&*(A+(i-1)*n+(S[j]-1))>=*(A+(k-1)*n+(S[j]-1))) /* *(A+(i-1)*n+(S[j]-1)) 等价于 A(i,S[j]) *(A+(k-1)*n+(S[j]-1)) 等价于 A(k,S[j]) *(A+(i-1)*n+(S[j]-1))>=*(A+(k-1)*n+(S[j]-1)) 等价于 A(i,S[j])>=A(k,S[j]) */ k++; if(k>m) { // 表示 A[i][S[j]] 是第 S[j] 列的最大元素 , 它是马鞍点 328 数据结构 } count++; // 马鞍点个数自加 1 cout< //*(A+(i-1)*n+(S[j]-1)) 等价于 A(i,S[j]) cout<<*(A+(i-1)*n+(S[j]-1))<<")"; } } } if(count==0) cout< 无马鞍点 else cout< 有 count 个马鞍点 C++ 语言版测试程序见 4_2_3c ，具体算当如下： void SaddlePoint(ElemType *A,int m,int n) 输出矩阵 A 所有马鞍点 // { ElemType *S=new ElemType[n+1]; // 存储某一行的元素值最小元素的下标 int c; // 表示此行的元素值等于最小值的元素的个数 int count=0; // 马鞍点的个数 int i,j,k; ElemType min; // 某一行的最小元素值 for(i=1;i<=m;i++) { min=*(A+(i-1)*n+(1-1)); //*(A+(i-1)*n+(1-1)) 等价于 A(i,1) c=1;S[1]=1; // 当前已得的元素值最小的元素下标与个数 for(j=2;j<=n;j++) if(*(A+(i-1)*n+(j-1)) 等价于 A(i,j) { //A(i,j) min=*(A+(i-1)*n+(j-1)); //A(i,j) 为新的最小值 c=1;S[1]=j; // 当前已得的元素值最小的元素下标与个数 } else if(*(A+(i-1)*n+(j-1))==min) //*(A+(i-1)*n+(j-1)) 等价于 A(i,j) { //A(i,j)==min c++; // 元素值最小的元素值自加 1 S[c]=j; } for(j=1;j<=c;j++) { // 对第 i 行的 c 个元素值最小的元素判断是否是马鞍点 k=1; // 判断是否第 S[j] 列有大于 A(i,S[j]) 的元素 while(k<=m&&*(A+(i-1)*n+(S[j]-1))>=*(A+(k-1)*n+(S[j]-1))) /* *(A+(i-1)*n+(S[j]-1)) 等价于 A(i,S[j]) *(A+(k-1)*n+(S[j]-1)) 等价于 A(k,S[j]) *(A+(i-1)*n+(S[j]-1))>=*(A+(k-1)*n+(S[j]-1)) 等价于 A(i,S[j])>=A(k,S[j]) */ 第 9 章 文件与动态存储管理 329 } k++; if(k>m) { // 表示 A[i][S[j]] 是第 S[j] 列的最大元素 , 它是马鞍点 count++; // 马鞍点个数自加 1 cout< //*(A+(i-1)*n+(S[j]-1)) 等价于 A(i,S[j]) cout<<*(A+(i-1)*n+(S[j]-1))<<")"; } } } if(count==0) cout< 无马鞍点 else cout< 有 count 个马鞍点 注意：本例中矩阵 A 的元素 A(i,j) 等价于数组元素的下标为 (i-1) 、 (j-1) ，所以 可用 *(A+(i-1)*n+(j-1)) 表示。
版权声明：本文标题：数据结构-数组和广义表作业解答 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://roclinux.cn/b/1713665601a646064.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论