课后习题
别妄想泡我
692次浏览
2021年01月28日 19:49
最佳经验
本文由作者推荐
残疾人工作总结-青岛科技大学怎么样
第三章
课后习题
3
．
3
．
2
对角矩阵的压缩存储
所谓对角矩阵是指矩阵中的所有非零元素都集中在以主对角 线为中心的带状区域中，
即
除了主对角线上和直接在主对角线上、
下方对称的若干条对 角线上的元素之外，
其余元素均
为零。
下面给出的矩阵
B
就是一个对角矩阵
(
确切地说是一个三对角矩阵，这里，我们仅以三
对角矩阵为例子< br>)
。
三对角矩阵一共有
3n
—
2
个非零元素。我们可以按照某个原则
(
或者以行序为主序的分
配方式，或者以列序为 主序的分配方式，或者按照对角线的顺序进行分配
)
将对角矩阵
B
的
所有非零元素压缩存储到一个一维数组
LTB[3n
—
2]
中。这里，不妨仍 然以行序为主序的分
配方式对
B
进行压缩存储，当
B
中任一非零元素
Bij
与
LTB[k]
之间存在着如下一一对应关
系
k=2 *i+j-3
时，则有
Bij=LTB[k]
。称
LTB[3n
—< br>2]
为对角矩阵
B
的压缩存储，如下图所示。
上面讨论的几种特殊矩阵中，非零元素的分布都具有明显的规律，因而都可以被压缩
存储到一个一维数组中，并且能够确定这些矩阵的每一个元素
(
或非零元素
)
在一维数组
中的位置。但是，对于那些非零元素在 矩阵中的分布没有规律的特殊矩阵
(
如稀疏矩阵
)
，
则需要寻求其他的方法来解决压缩存储问题。
3
．
5
稀疏矩阵的十字链表表示
上 一节讨论了用三元组表的形式来存储一个稀疏矩阵的方法。
但是，
在实际应用中，
当< br>稀疏矩阵中非零元素的位置或者个数经常发生变化时，使用三元组表就不太方便了。
本节将介绍稀疏矩阵的另一种表示方法，即十字链表表示。
如何用链表形式来表示一 个稀疏矩阵呢
?
方法之一就是将所有非零元素以行序为主序方式
(
当然也可以 以列序为主序方式
)
采用循环链表链接起来。链结点的构造由四个域组成：
其中
i,j
分别表示某一个非零元素所在的行号与列号；
value
表示该非零元素的值；
link
域用来指向下一个非零元素所在的链结点，它是一个 指针。另外，再设置一个链表头结点，
其构造如下：
其中，
m
，
n
分别表示稀疏矩阵的行数与列数 ；
t
为稀疏矩阵非零元素的总个数；
link
域
用来指向第一个非零 元素对应的链结点。
例如，对于如下一个稀疏矩阵：
若采用行 序为主序方式
(
每行又按列的先后顺序
)
依次将所有非零元素链接起来，则得到
如图
3
．
4
所示的一个带有头结点的循环链表。
这种表示方法最明显的一个缺点就是 ，当要访问某行某列的一个非零元素时，必须从
链表的最前面那个链结点开始进行搜索，其效率之低可想 而知。
一个能提高访问效率的方法就是采用十字 链表表示。
这种方法为稀疏矩阵的每一行设置
一个单独的行循环链表，
同样也为每一列 设置一个单独的列循环链表。
这样，
稀疏矩阵中的
每一个非零元素同时包含在两个链表 中，
即包含在它所在的行链表与所在的列链表中，
也就
是这两个链表的交汇处。
对于一个
mXn
的稀疏矩阵，
分别建立
m
个行的循环链 表与
n
个列的循环链表，
每个非
零元素用一个链结点来存储。链结点的结构可 以设计为
其中，
rOW，
c01
，
value
分别表示某非零元素所在的行号、列号和相应的元 素值；
down
与
right
分别称为向下指针与向右指针，它们分别用来链 接同一列中的与同一行中的某非零
元素结点。也就是说，稀疏矩阵中同一行的所有非零元素是通过
right
指针链接成一个行链
表，同一列中的所有非零元素是通过
down
指针链接成一个列链表。而对每一个非零元素而
言，
它既是某个行链表中的一个链结点，同时又是某个列链表中的一个链结点，
这个非零元
素好比处在一个十字路口，故称这种链表 表示为十字链表表示法。
作为链表，应该用某种 方式能访问表中的第一个结点，为此，对于
m
个行链表，分别
设置
m
个行链表表头结点。表头结点的构造与链表中其他链结点一样，只是令
row
与凹
1< br>域的值均为
0
，
right
域指向相应行链表的第一个链结点。同理， 对于
n
个列链表，分别设置
n
个列链表表头结点。
头结点结构也同其 他链结点一样，
只是令
rOW
与
c01
的值均为
0
，
down
域指向相应列链表的第一个链结点。另外，通过
value
域把所 有这些表头链结点也链接成一
个循环链表。
十字链表中的链结点类型可以描述如下：
typedefstructnode{
int row,col
；
union{
ElemType val
；
struct node'ptr
；
1value
；
struct node 1 right
，
'down
；
1 CNode
，
xCrossLink
；
／‘定义十字链表结点类型
x
／
从
m
个行链表的表头结点与
n
个列链表的表头结点的设置情况看到，行链表的头结点
只用了
right
域作为指针，而列链表的头结点只用了
down
域与
< br>value
域，其他域没有使用。
因此，可以设想原来的
(m+n)
个 头结点实际上可以合并成
MAX(m
，
n)
。为此，再设置一个< br>结点作为头结点链表的头结点，不妨称之为总头结点，其结构如下所示：
m
t
n
Link
其中，
m
，
n
分别为稀疏矩阵的行数与列数；
t
为 非零元素的总个数；
1ink
指向头结点
链表的第一个头结点。
总头结点的类型可以如下描述：
typedefstruct{
int m
，
n
，
t,nil
；
CrossLink x link
；
}HNode,*HLink
；
／
x
定义十字链表总头结点类型
x
／
‘
综上所述，若给出一个稀疏矩阵
B
如下，则它的十字 链表表示如图
3
．
5
所示。
下面给出创建一个具有
m
行
n
列、有
t
个非零元素的稀 疏矩阵的十字链表的算法。
稀疏矩阵用三元组表 的形式作为输入。
首先输入稀疏矩阵的行数、
列数以及非零元素总
个数
(m< br>，
n
，
t)
，然后依次读入个三元组。
算法中用到了一个辅助 数组
hdnode [MAX(m
，
n)]
。
其中，
hdn ode[i]
用来分别存放第
i
列
(
也是第
i
行< br>)
链表的头结点的指针
(1
≤
i
≤
MAX (m
，
n))
。
#defineMaxNl00
HLinkMREAD()
{
HLinkHEAD
，
p
，
las t
，
hdnode[MaxN]
；
iht m,n t
，
k
，
i
，
Current_row
，
int rrow,ccol
，
val
；
scanf(
％
d
％
d
％
，
&n
，
&n
，
&t)
；
／
x
读入矩阵的行、列和非零元素的个数‘／
if(t<=0)
return NULL
；
k=(m>n)?m
：
n
；
for(i=0
；
i
i++){
p=(HLink)malloc(sizeof(HNode))
；
hdnode[i]=p
；
p->row=0
；
p->col=0
；
p->=P
；
p->rlght=p
；
p->down=p
；
}
／
*
建立
k
个头结点；初始时第< br>i
个头结点的地址存放于
hdnode[i-1]
中
x
／
Current_row=1
；
last=hdnode[0];
for(i=1
；
i<=t
；
i++){
scanf(
％
d
％
d
％
d
，
&rrow,&ccol
，
&val)
；< br>
／
x
读人一个某非零元素的三元组
x
／
if(rrow>current_row){
last
—
>right=hdnode[Current_r ow
—
1]
；
current_row=rrow
；
last=hdnode[rrow
—
1]
；
}
p=(CrossLink)malloc(sizeof(CNode))
；
／
x
申请一个新的链结点空间
x
／
p
—
>row=rrow
；
p->col=ccol
；
p
—
>=val
；
last->right=p
；
／
x
生成一个新的链结点
x
／
last=p
；
hdnode[ccol
—
1)->value
．ptr->down=p
；
／‘将新结点链接到相应行链表中，／
kfnode[ccol
—
1)->value
．
ptr=p
；
／
x
将新结点链接到相应列链表中，／
；
if(t!=0)
last->right
：
hdnode [current
—
row
—
1]
；
／
x
封闭最后——行
x
／
for(i=0;i
i++)
／
x
通过
value
域将头结点链接为一条循环链表。／
hdnode[i]->value
．
p tr->down=hdnode[i]
；／
x
封闭所有列链表
x
／
HEAD=(HLink)malloc(sizeof(HNode))
；
／，申请一个总的头结点
x
／
HEAD->m=m
；
HEAD->n=n
；
HEAD->t=t
；
for(i=0
；
i
i++)
hdnode[i]->=nanode[i+1]
；
if(k==0)
HEAD->=HEAD
；
else{
hdnode[k-1]->=HEAD
；
HEAD->=hdnode[0]
；
return HEAD
；
}
习
题
3
．
1
判断题
(
在你认为正确的题后的括号中打√，否则打
X)
。
(1)
数组是一种线性表结构。
(
)
(2)
数组最基本的操作是插入和删除。
(
)
(3)
对数组的操作是基于数组下标进行的。
(
)
(4)
具有特殊用途的矩阵称为特殊矩阵。
(
)
(5)
只需存储
n
阶对称矩阵的下三角部分的元素。
(
)
(6)
在
n
阶三对角矩阵中，矩阵的每一列都有
3
个非零元素。
(
)
(7)
稀疏矩阵的特点就是矩阵中的元素较少。
(
)
(8)
采用三元组表方法存储稀疏矩阵的优点之一是可以随机地访问矩阵中的每一个非零
元< br>
素。
(
)
(9)
用一维数组存储特殊矩阵的目的是为了节省存储空间。
(
)
(10)
从理论上说，
任何一个矩阵都可以采用三元组表方法进行存储。
(
) 3
．
2
填
空题。
(1)
一般情况下，数组最基本的操作是——。
(2)
一个
m
行
n
列的矩阵可以看成 是长度为——的线性表，表中的每一个元素是长度为
m
的线性表。
(3)
一个
m
行
n
列的矩阵可以看成是长度为——的线性表，表中的每一个元素是长 度为
n
的线性表。
(4)已知二维数组
A(4)[6]
采用行序为主序方式存储，每个元素占用
4
个存储单元，该数
组一
共占用了——个存储单元。
(5)已知二维数组
A[4
爪
6]
采用行序为主序方式存储，每个元素占用3
个存储单元，并
且
A1 0
爪
0]
的存储地址为
1200
，元素
A12)14]的存储地址是——。
(6)
已知二 维数组
A14
爪
6]
采用列序为主序方式存储，每个元素占用
4个存储单元，
并且
A[ 3][4]
的存储地址为
1234
，元素
A[0][0]
的存储地址 是——。
(7)
对特殊矩阵采用压缩存储方法的目的是——。
(8)
一个
20
阶五对角矩阵一共有——个元素，其中有——个非 零元素。
(9)
将
n
阶三对角矩阵
A
中所有非零元素按照行序为主序方式依次存放于数组
B
中，非
零元素
A[i][j]
在
B
中的位置是——。
3
．
3
单项选择题。
(1)
所谓稀疏矩阵是指——的矩阵。
A
．零元素较多且分布无规律
·
B
非零元素较少
C
．元素较少
D
．不适合采用二维数组表示
(2)
下面的说法中，不正确的是——。
A
．只需存放对称矩阵中包括主对角线元素在内的下
(
或上
)
三角部分的元素即可
B
‘只需存放对角矩阵中的非零元素即可
C
．稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储
D
．稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储
(3)
与三元组表方法相比，稀疏矩阵采用十字链表表示的优点在于——。
A
．便于实现增加或减少矩阵中非零元素的操作
B
．便于实现增加或减少矩阵元素的操作
C
．节省存储空间
D.
可以更快地查找到某个矩阵元素
(4)
对稀疏矩阵采用压缩存储，其缺点之一是——。
A
．无法判断矩阵的行数和列数
B
．无法根据行列号计算矩阵元素的存储地址
C
．无法根据行列号查找某个矩阵元素
D
．使得矩阵元素之间的逻辑关系更加复杂
(5)
将一个
20
阶的五对角矩阵中所有非零元素压缩存储到一个 一维数组中，该一维数组
至少应该有——个数组元素。
A
．
90
B
．
92
C
．
94
D
．
96
(6)
将
10
阶三对角矩阵中的所有非零元素按照行序为主序方式 依次存放于一维数组中，
矩阵的第
7
行第
8
列的元素在该一维数组中 ————。
A
．是第
22
个数组元素
B
．是第
21
个数组元素
C
．是第
20
个数组元素
D
．不存在
(7)
将
10
阶三对角矩阵中的所有非零元素按照行序为主序方式依次存放于一维数组中，< br>一维数组中的第
18
个数组元素是矩阵——的那个元素。
A
．第
6
行第
3
列
B
．第
6
行第
7
列
C
。第
7
行第
7
列、
D
．第
7
行第
6
列
(8)
若将
n
阶对称矩阵
A
按照行序 为主序方式将包括主对角线元素在内的下三角形的所
有元素依次存放在一个一维数组
B
中，则该对称矩阵在
B
中占用了一个数组元素。
A
．
n2
B
．
n*(n-1)
C
．
n*(n+1)/2
D
．
n*(n-1)
／
2
(9)
若将
n
阶三对角矩阵
A
按照行序为主序方 式将所有非零元素依次存放在一个一维数
组
B
中，则该三对角矩阵在
B
中占用了——个数组元素。
A
．
n2
B
．
3n-2
C
．
3n
D
．
3n+2
(10)
若将对称矩阵
A
按照行序为主序方式将包括主对角线元素在内的下三角形的所有
元素 依次存放在一个一维数组
B
中，那么，
A
中某元素
Aij(i
B
中的位置是——。
A
．
(i*(i
—
1))/2+j-1
B
．
(i*(i
—
1))/2
—
j—
1
C
．
(j *(j
—
1))
／
2
十
i
—
1
D
．
(j*(j-1))/2
—
i
—
1
(11)
对三对角矩阵
A
采用压缩存储的方 法将所有非零元素存放于一个一维数组
BC3n
—
2]
中，某非零元素
Aij
在
B
中位置是——。
A
．
2*i+j-2
B
．
2*i+j+2
C
．
2*i+j-3
D
．
2*i+j-1
3
．
4
已知一元多项式f(x)=4X(6)
—
5X(4)
十
7X(2)-1
，
请写出
f(x)
的一维数组表示的两种方法。
3
．< br>5
按照压缩存储的思想，对于一个具有
t
个非零元素的
mXn
阶稀疏矩阵，若采用三元组
表存储方法，
t
到达什么程度时这样做才有意义
?
3
．
6
已知稀疏矩阵
A[6][5]
如下所示，请分别写出它的三元组表表示与十字链表表示。
3
．
8
已知稀疏矩阵
A
为
m
行
n
列，请写出将该稀疏矩阵转换为三元组表表示的算法。
3
．
9
设
A
为一个
n
阶上三 角矩阵，若将此三角矩阵的所有非零元素按照列序为主序分配
方式存放在数组
B[n*(n+1 )/2]
中，
a11
存放于
B[0]
中，请写出此三角矩阵的非零元 素
Aij(i
≤
j)
的寻址公式。
3
．
10
请写算法，该算法将一个
n
阶矩阵< br>A
主对角线以下的所有元素
(
不包括主对角线上
的元素
)按照列序为主序方式依次存放于一个一维数组
B
中。
3
．
11
请写算法，
该算法将一个
n
阶矩阵
A
主对角线以下的所有元素
(
包括主对角线上的元
素
)
按照行序为主序方式依次存放于一个一维数组
B
中。
3
．
12
已知
n
阶对称矩阵
A
的下三角部分元素按照行序为主序方式依次存放于一个一维数
组
B[m]
中，请写出 输出该对称矩阵的算法。
3
．
13
已知某 二维数组
A[n][n]
按照行序为主序方式依次为每个数组元素获取值，
请写一算< br>法，求该数组两条对角线上的元素之乘积。
3
．
14
< br>已知二维数组
A[m][n]
，请写一算法，求出该数组最外围一圈的元素之和。
已知二维数组
A[n][n]
，请写一时间复杂度为
O(1)
的 算法，将该数组按照顺时针方向旋转若
稀疏矩阵采用三元组表表示，请写出求两个具有相同行、列数的稀 疏矩阵相加的算法。
3
．
17
若在
m*n
阶的矩阵
A
中有一元素
Aij
满足条件：
Aij< br>既是第
i
行元素的最小值，同
时又是第
j
列元素的最大值，此 时称
Aij
为
A
的鞍点。试写出求矩阵鞍点的算法。若矩阵中
不存在 鞍点，应给出相应信息。
3
．
18
编写一个将十字链 表表示的矩阵
A
转置的算法，转置的结果仍采用十字链表表示。
3
．
19
若稀疏矩阵采用十字链表表示，请设计两个稀疏矩阵进 行相乘运算的算法，即已知
A
矩阵与
B
矩阵，求矩阵
C=A*B，并且要求
C
也采用十字链表表示。
3
．
20
试设计一个算法，将数组
A[n]
中的元素循环右移
k
位 ，要求只用一个元素大小的附
加空间。
3
．
21
试设计一个时间复杂度为
O(n)
的算法，该算法将数组
A[n]
中的元 素循环
右移
k
位，要求采用尽可能少的附加空间。
3
．
22
n
阶三对角矩阵
A
按行序为 主序分配方式把所有非零元素存放于数组
B[3n
—
2]
中，
Aij
存放于
B[0]
中，请设计一个算法以确定数组
B
中元素～的值(1
≤
i
，
j
≤
n)
。
3
．
23
已知存放整型数据的一维数组
A[n]
，请写一时间复杂度为
O(n)
的算法，该算法将数
组调整为左右两部分，使得左边 所有元素均为奇数，右边所有元素均为偶数。
3
．
24
已知具有
n
个数组元素的一维数组
A
，请写一算法，将该 数组中所有值为
0
的元素
都依次移到数组的前端
A[i](0
≤i
≤
n-1)
。
历年试题
1
．执行下列程序段后，串
X
的值为（
）
S=
〞
abcdefgh
〞
;
T=
〞
xyzw
〞
;
substr (X,S,2,strlen(T));
substr (Y
,S, stelen(T),2);
strcat (X,Y);
A
．〞
cdefgh
〞
B
．〞
cdxyzw
〞
C
．〞
cdefxy
〞
D
．〞
cdefef
〞
2
．多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为（
）
A
．数组的元素处在行和列两个关系中
B
．数组的元素必须从左到右顺序
排列
C
．数组的元素之间存在次序关系
D
．数组是多维结构，内存是一维
结构
3
．从广义表
LS
＝（
(p, q), r, s
）中分解出原子
q
的运算是（
）
A
．
tail (head (LS))
B
．
head (tail (head (LS)))
C
．
head (tail (LS))
D
．
tail (tail (head (LS)))
4
．数组通常具有两种基本运算，即（
）
A
．创建和删除
B
．索引和修改
C
．读和写
D
．排序和查找
5
．设有一5
阶上三角矩阵
A
［
1..5
，
1..5
］< br>，现将其上三角中的元素按列优先顺序
存放在一堆数组
B
［
1..15
］中。已知
B
［
1
］的地址为
100
，每个元素占 用
2
个存
储单元，则
A
［
3
，
4
］的地址为（
）
A
．
116
B
．
118
C
．
120
D
．
122
6.
为查找某一特定单词在文本中出现的位置，可应用的串运算是
(
)
A.
插入
B.
删除
C.
串联接
D.
子串定位
7.
已知函数
Sub (s,i,j)
的功能是返回串
s
中从第
i
个字符起长度为
j
的子串，函数
Scopy(s,t)
的功能为复制串
t
到
s
。若字符串
S=
″
SCIENCESTUDY
″，则调用
函数
Scopy(P,Sub(S,1,7))
后得到
(
)
A.P=
″
SCIENCE
″
B.P=
″
STUDY
″
C.S=
″
SCIENCE
″
D.S=
″
STUDY
″