文档介绍:该【数据结构答案第4章 】是由【森林书屋】上传分享,文档一共【8】页,该文档可以免费在线阅读,需要了解更多关于【数据结构答案第4章 】的内容,可以使用淘豆网的站内搜索功能,选择自己适合的文档,以下文字是截取该文章内的部分文字,如需要获得完整电子版,请下载此文档到您的设备,方便您编辑和打印。第 4章 广性表——多数和广表
2005-07-14
第4章广义线性表——多维数组和广义表
课后****题讲解
填空
⑴数通常只有两种运算:( )和( ),决定了数通常采用( )构来存。
【解答】存取,修改,序存
【分析】数是一个具有固定格式和数量的数据集合,在数上一般不能做插入、除元素的操作。除了初始化和之外,在数中通常只有存取和修改两种操作。
⑵二数A中行下从10到20,列下从5到10,按行先存,每个元素占4个存元,A[10][5]的存地址是1000,元素A[15][10]的存地址是()。
【解答】1140
【分析】数A中每行共有6个元素,元素A[15][10]的前面共存了(15-10)×6+5个元素,每个元素占
4个
存元,所以,其存地址是1000+140=1140。
⑶有一个10的称矩A采用存,A[0][0]第一个元素,其存地址
d,每个元素占
1个
存元,元素A[8][5]的存地址(
)。
【解答】d+41
【分析】元素A[8][5]的前面共存了(1+2+⋯+8)+5=41个元素。
⑷稀疏矩一般存方法有两种,分是(
)和()。
【解答】三元序表,十字表
⑸广表((a),(((b),c)),(d))的度是(
),深度是(
),表是(
),表尾是(
)。
【解答】3,4,(a),((((b),c)),(d))
⑹已知广表 LS=(a,(b,c,d),e),用Head和Tail函数取出 LS中原子b的运算是( )。
【解答】Head(Head(Tail(LS)))
选择题
⑴二维数组A的每个元素是由 6个字符组成的串,行下标的范围从 0~8,列下标的范围是从 0~9,则存放
A至少需要( )个字节,A的第8列和第5行共占( )个字节,若 A按行优先方式存储,元
素A[8][5]的起始地址与当 A按列优先方式存储时的( )元素的起始地址一致。
A90B180C240D540E108F114G54
HA[8][5]IA[3][10]JA[5][8]KA[4][9]
【解答】D,E,K
【分析】数组 A为9行10列,共有90个元素,所以,存放 A至少需要 90×6=540个存储单元,第 8列和
第5行共有18个元素(注意行列有一个交叉元素),所以,共占 108个字节,元素 A[8][5]按行优先存储的
起始地址为d+8×10+5=d+85,设元素A[i][j]按列优先存储的起始地址与之相同,则d+j×9+i=d+85,解此方程,得i=4,j=9。
⑵将数组称为随机存取结构是因为( )
A数组元素是随机的 B对数组任一元素的存取时间是相等的
C随时可以对数组进行访问 D数组的存储结构是不定
【解答】B
⑶下面的说法中,不正确的是( )
A数组是一种线性结构 B数组是一种定长的线性结构
除了插入与删除操作外,数组的基本操作还有存取、修改、检索和排序等
数组的基本操作有存取、修改、检索和排序等,没有插入与删除操【解答】C
【分析】数组属于广义线性表,数组被创建以后,其维数和每维中的元素个数是确定的,所以,数组通常没有插入和删除操作。
⑷对特殊矩阵采用压缩存储的目的主要是为了( )
A表达变得简单 B对矩阵元素的存取变得简单
C去掉矩阵中的多余元素 D减少不必要的存储空间
【解答】D
【分析】在特殊矩阵中,有很多值相同的元素并且他们的分布有规律, 没有必要为值相同的元素重复存储。
⑸下面( )不属于特殊矩阵。
A对角矩阵 B三角矩阵 C稀疏矩阵 D对称矩阵
【解答】C
⑹若广义表A满足Head(A)=Tail(A),则A为( )
A()B(())C((),())D((),(),())
【解答】B
⑺下面的说法中,不正确的是( )
A广义表是一种多层次的结构 B广义表是一种非线性结构
C广义表是一种共享结构 D广义表是一种递归
【解答】B
【分析】从各层元素各自具有的线性关系讲,广义表属于线性结构。
⑻下面的说法中,不正确的是( )
对称矩阵只须存放包括主对角线元素在内的下(或上)三角的元素即可。
对角矩阵只须存放非零元素即可。
稀疏矩阵中值为零的元素较多,因此可以采用三元组表方法存储。
稀疏矩阵中大量值为零的元素分布有规律,因此可以采用三元组表方法存储【解答】D
【分析】稀疏矩阵中大量值为零的元素分布没有规律, 因此采用三元组表存储。 如果零元素的分布有规律,
就没有必要存储非零元素的行号和列号,而需要按其压缩规律找出相应的映象函数。
判断题
⑴数组是一种复杂的数据结构,数组元素之间的关系既不是线性的,也不是树形的。
【解答】错。例如二维数组可以看成是数据元素为线性表的线性表。
⑵使用三元组表存储稀疏矩阵的元素,有时并不能节省存储空间。
【解答】对。因为三元组表除了存储非零元素值外,还需要存储其行号和列号。
⑶稀疏矩阵压缩存储后,必会失去随机存取功能。
【解答】对。因为压缩存储后,非零元素的存储位置和行号、列号之间失去了确定的关系。
⑷线性表可以看成是广义表的特例,如果广义表中的每个元素都是单元素,则广义表便成为线性表。
【解答】对。
⑸若一个广义表的表头为空表,则此广义表亦为空表。
【解答】错。如广义表 L=((),(a,b))的表头为空表,但 L不是空表。
4-4所示,写出对应的三元组顺序表和十字链表存储表示。
【解答】对应的三元组顺序表如图 4-5所示,十字链表如图 4-6所示。
,试从空间和时间角度比较采用二维数组和三元组顺序表两种不同的存储结构完成求运算的优缺点。
【解答】设稀疏矩阵为m行n列,如果采用二维数组存储,其空间复杂度为O(m×n);因为要将所有的矩阵元素累加起来,所以,需要用一个两层的嵌套循环,其时间复杂度亦为O(m×n)。如果采用三元组顺序表进行压缩存储,假设矩阵中有t个非零元素,其空间复杂度为O(t),将所有的矩阵元素累加起来只需将三元组顺序表扫描一遍,其时间复杂度亦为O(t)。当t<<m×n时,采用三元组顺序表存储可获得较好的时、空性能。
“工资”、“扣除”和“实发金额”三项组成,其中工资项包括“基本工资”、“津贴”和“奖金”,扣除项包括“水”、“电”和“煤气”。
⑴请用广义表形式表示所描述的工资表 ST,并用表头和表尾求表中的 “奖金”项;
⑵画出该工资表 ST的存储结构。
【解答】⑴ ST=((基本工资,津贴,奖金 ),(水,电,煤气),实发金额)
Head(Tail(Tail(Head(ST))))=奖金
⑵工资表ST的头尾表示法如图 4-7所示。
A中存在一个元素 ai,j(0≤i≤n-1,0≤j≤m-1),该元素是第 i行元素中最小值且又是第 j列元素
中最大值,则称此元素为该矩阵的一个马鞍点。假设以二维数组存储矩阵 A,试设计一个求该矩阵所有马
鞍点的算法,并分析最坏情况下的时间复杂度。
【解答】在矩阵中逐行寻找该行中的最小值,然后对其所在的列寻找最大值,如果该列上的最大值与该行上的最小值相等,则说明该元素是鞍点,将它所在行号和列号输出。
具体算法如下:
分析算法,外层for循环共执行 n次,内层第一个 for循环执行m次,第二个for循环最坏情况下执行 n次,
所以,最坏情况下的时间复杂度为O (mn+n2)。
学****自测及答案
M中每个元素的长度是 3个字节,行下标从 0到7,列下标从 0到9,从首地址 d开始存储。
若按行优先方式存储,元素 M[7][5]的起始地址为( ),若按列优先方式存储,元素 M[7][5]的起始地
址为( )。
【解答】d+22,d+141
×n的对称矩阵,按行优先或列优先进行压缩存储,则其存储容量为( )。
【解答】n(n+1)/2
n行n列的下三角矩阵
A(行列下标均从
1开始)已压缩到一维数组
S[1]~S[n(n+1)/2]中,若按行优先
存储,则
A[i][j]
在数组
S中的存储位置是(
)。
【解答】i×(i-1)/2+j
LS=(a,(b,c),(d,e,a)),运用Head函数和Tail函数取出 LS中原子d的运算是( )。
【解答】Head(Head(Tail(Tail(LS))))
(a,b,(c,(d)))的表尾是( )。
A(d)B(c,(d))Cb,(c,(d))D(b,(c,(d)))
【解答】D
使得B[k]=aij求:
An×n(行、列下标均从
0开始),将其三条对角线上的元素逐行存于数组
B[3n-2]中,
⑴用
i,j
表示
k的下标变换公式;
⑵用
k表示
i,j
的下标变换公式。
【解答】⑴ 要求i,j表示k的下标变换公式,就是要求在 k之前已经存储了多少个非零元素,这些非零元
素的个数就是 k的值。元素 aij求所在的行为 i,列为j,则在其前面的非零元素的个数是; k=2+3(i-1)+(j
i+1)=2i+j。
⑵因为k和i,j之间是一一对应的关系,k+1是当前非零元素的个数,整除即为其所在行号,取余表示当前行中第几个非零元素,加上前面零元素所在列数就是当前列号,即:
n×n的对称矩阵按压缩存储方法存储在已维数组 A和B中,编写算法计算对称矩阵的乘积。
【解答】对称矩阵采用压缩存储,乘积矩阵也采用压缩存储。注意矩阵元素的表示方法。
关闭