《数据结构复习题第5章答案2014616.pdf》由会员分享，可在线阅读，更多相关《数据结构复习题第5章答案2014616.pdf（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第 5 章 数组与广义表 一、选择题(每小题 1 分,共 10 分）1.一个向量第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个元素的地址是（A )。A。110 B。108 C.100 D.120 2。在数组 A 中，每一个数组元素 Aij占用 3 个存储字节，行下标 i 从 1 到 8，列下标j 从 1 到 10。所有数组元素相继存放于一个连续的存储空间中,则存放该数组至少需要的存储字节数是（C ）。A。80 B。100 C。240 D。270 3。假设有 60 行 70 列的二维数组 a160，170以列序为主序顺序存储，其基地址为10000,每个元素占 2 个存储单元,
2、那么第 32 行第 58 列的元素 a32,58的存储地址为（C ）。（无第 0 行第 0 列元素）A.16902 B.16904 C。14454 D.答案 A，B，C 均不对 4。将一个 A1。100,1.100的三对角矩阵，按行优先存入一维数组 B1298中,A 中元素 A6665（即该元素下标 i=66，j=65），在 B 数组中的位置 K 为(A ）。A。198 B。195 C。197 D.196 5.数组 A0.5,0.6的每个元素占五个字节，将其按列优先次序存储在起始地址为 1000 的内存单元中，则元素 A5，5的地址是(A ）.A。1175 B.1180 C.1205 D.12
3、10 6。假设以行序为主序存储二维数组 A=array1.。100，1.。100，设每个数据元素占 2 个存储单元,基地址为 10,则 LOC5，5=（B ）.A。808 B.818 C.1010 D。1020 7.设有数组 Ai,j，数组的每个元素长度为 3 字节，i 的值为 1 到 8，j 的值为 1 到 10，数组从内存首地址 BA 开始顺序存放，当用以列为主存放时,元素 A5，8的存储首地址为(B ）.A.BA+141 B。BA+180 C。BA+222 D。BA+225 8。设有一个 10 阶的对称矩阵 A，采用压缩存储方式，以行序为主存储,a11 为第一元素，其存储地址为 1，每个
4、元素占一个地址空间，则 a85 的地址为（B ）。A、13 B、33 C、18 D、40 9.二维数组 A 的每个元素是由 6 个字符组成的串，其行下标 i=0，1,8,列下标 j=1，2,，10。若 A 按行先存储,元素 A8,5的起始地址与当 A 按列先存储时的元素(B ）的起始地址相同.设每个字符占一个字节.A、A8,5 B、A3，10 C、A5,8 D、A0,9 10.若对 n 阶对称矩阵 A 以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组 B1.（n（n+1）)/2中，则在 B 中确定 aij（ij）的位置 k 的关系为（B ）。A、i*(i-1)/2
5、+j B、j*(j1）/2+I C、i（i+1）/2+j D、j（j+1)/2+i 11.对稀疏矩阵进行压缩存储目的是（C ）。A、便于进行矩阵运算 B、便于输入和输出 C、节省存储空间 D、降低运算的时间复杂度 12.数组 r 存储静态链表，结点的 next 域指向后继，工作指针 j 指向链中结点,使 j 沿链移动的操作为（A ）。A、j=rj.next B、j=j+1 C、j=j-next D、j=rj-next 13.数组 A0。.4，3。.-1,5.7中含有元素的个数为(B ）。A、55 B、45 C、36 D、16 14。有一个 100*90 的稀疏矩阵，非 0 元素有 10 个，设
6、每个整型数占 2 字节，则用三元组表示该矩阵时，所需的字节数是(B ）。A、60 B、66 C、18000 D、33 15.设二维数组 A1。.m,1。.n（即 m 行 n 列)按行存储在数组 B1.mn中，则二维数组元素 Ai,j在一维数组 B 中的下标为（A ）。A、（i1)*n+j B、（i-1）n+j1 C、i*（j1）D、j*m+i-1 16。AN，N是对称矩阵，将下面三角（包括对角线)以行序存储到一维数组 TN（N+1）/2中，则对任一上三角元素 aij对应 Tk的下标 k 是（B ）。A。i(i-1）/2+j B.j（j1）/2+I C.i（j-i）/2+1 D.j（i1）/2+
7、1 17.设 A 是 nn 的对称矩阵，将 A 的对角线及对角线上方的元素以列为主的次序存放在一维数组 B1.。n（n+1)/2中，对上述任一元素 aij(1i，jn，且 ij）在 B 中的位置为（B ).A、i（il)/2+j B、j(jl）/2+I C、j(j-l）/2+i1 D、i(i-l)/2+j-1 18.对于以行为主序的存储结构来说在数组 Ac1。.d1，c2.d2中,c1 和 d1 分别为数组 A的第一维下标的下、上界,c2 和 d2 分别为第二维下标的下、上界每个数据元素占 k 个存储单元，二维数组中任一元素 ai,j的存储位置可由（B ）确定。A、Loci，j=（d2c2+1
8、）（i-c1)+（j-c2)k B、Loci，j=Locc1，c2+（d2c2+1）（i-c1）+（jc2)k C、Loci，j=Ac1,c2+（d2c2+1）(i-c1)+(jc2）k D、Loci,j=Loc0，0+(d2c2+1)（ic1）+(jc2）k 19。设矩阵 A 是一个对称矩阵，为了节省存储，将其下三角部分(如下图所示)按行序存放在一维数组 B1.。n（n-1）/2|中,对下三角部分中任一元素(i=j）在一维数组 B的下标位置 k 值是（B ）.A、i(i-1)/2+j-l B、i(i-1）2+j C、i(i+1)/2+j1 D、i(i+1)2+j 20.稀疏矩阵一般的压缩存储
9、方法有(C )两种.A、二维数组和三维数组 B、三元组和散列表 C、三元组和十字链表 D、散列表和十字链表 参考题:21。数组 SZ35，O 10含有元素数目为(B ）。A、88 B、99 C、80 D、90 22.二维数组 A 的每个元素是由 6 个字符组成的串，其行下标 i=0、1、8列下标 i=1、2、10。若 A 按行先存储，元素 A 8，5 的起始地址与当 A 按列先存储时的元素(B ）的起始地址相同。设每个字符占一个字节。A、A8，5 B、A3，10 C、A5，8 D、A0，9 23。设有一个 10 阶的对称矩阵 A，采用压缩破除计方式，以行序为主存储，a1，1 为第一个元素，其存
10、储地址为 1，每个元素占 1 个地址空间，则 a8,5 的地址为（B ).A、13 B、33 C、18 D、40 24。稀疏矩阵进行压缩存储目的是（C )。A、便于进行矩阵运算 B、便于输入和输出 C、节省存储空间 D、降低运算的时间复杂度 25。用数组 r 存储静态链表，结点的 next 域指向后继，工作指针 j 指向链中结点，使 沿链移动的操作为（A ）.A、j=r j。next B、j=j+1 C、j=j-next D、j=rj next 26.数组的基本操作主要包括(C ）A、建立与删除 B、索引与修改 C、访问与修改 D、访问与索引 27。设矩阵 A 是一个对称矩阵，为了节省空间，将
11、其下三角矩阵按行序存放在一维数组 B 1，n（n+1）/2中，对下三角部分中任一元素 aij（ij），在一维数 B 中下标 k 的值是（B ）。A、i（i1)/2+j1 B、i（i-1）/2+j C、i（i+1)/2+j-1 D、i（i+1）/2+j 8.设有数组 Ai，j，数组的每个元素长度为 3 字节，i 的值为 1 到 8，j 的值为 1 到 10,数组从内存首地址 BA 开始顺序存放,当用以列为主存放时,元素 A8，5的存储首地址为（B ）。A、BA+141 B、BA+180 C、BA+222 D、BA+225 数组 A 中，每个元素的长度为 3 个字节，行下标 i 从 1 到 8,列
12、下标 j 从 1 到 10，从首地址SA 开始连续存放的存储器内,该数组按行存放，元素 A8 5的起始地址为 C 。A SA141 B SA144 CSA222 D SA225 二、判断题（每小题 1 分，共 10 分）1。一个稀疏矩阵 Am*n 采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把 m 和 n 的值互换，则就完成了 Amn 的转置运算。（）2.二维以上的数组其实是一种特殊的广义表。()3。数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入,删除等操作。（）4.稀疏矩阵压缩存储后，必会失去随机存取功能。(）5.所谓取广义表的表尾就是返回广义表中最后一个
13、元素.()6。广义表是由零或多个原予或子表所组成的有限序列,所以广义表可能为空表。（)7.广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。（)8.线性表可以看成是广义表的特例,如果广义表中的每个元素都是原子，则广义表便成为线性表。(）9.若一个广义表的表头为空表，则此广义表亦为空表.（）10.数组元素的下标值越大，存取时间越长.(）11.数组是一种复杂的数据结构：数组元素之间的关系既不是线性的，也不是树形的(）12.从逻辑结构上看，n 维数组的每个元素均属于 n 个向量。(）13.二维数组是其数据元素为线性表的线性表（）14.数组是同类型值的集合.()三、填空题（每空 1 分，
14、共 10 分）1。已知二维数组按“行优先顺序存储在内存中，a11的存储地址为 LOC（a11），则元素 aij的存储地址为 LOC（aij)=.（假定每一个元素占 2 个存储单元,1in,1jm)答案：Loc(a11)+(i-1)m+j-1)*2 2。二维数组 A44(即 A0.。30。.3）的元素起始地址是 loc(A0 0)=1000，元素的长度为 2，则 LOC（A22）的地址为 .答案：1020 3。设有一个二维数组 A10 20，按行存放于一个连续的存储空间中，A00的存储地址是 200，每个数组元素占 1 个存储字，则 A62的存储字地址是_。答案：322 4。二维数组 a456（
15、下标从 0 开始计，a 有 456 个元素），每个元素的长度是 2，则 a234的地址是 1164 。(设 a000的地址是 1000，数据以行为主方式存储）解释:LOC（aijk）=LOC(a000）+v2v3(ic1)+v3*（jc2)+（k-c3）l（l 为每个元素所占单元数）5。对矩阵压缩是为了 节省存储空间 。6。所谓稀疏矩阵指的是 非零元很少（tmn）且分布没有规律 。7。设有一个 10 阶对称矩阵 A 采用压缩存储方式（以行为主序存储:a11=1），则 a85 的地址为 33 。解释:（k=i（i1)/2+j)（1=i，j=n）8。己知三对角矩阵 A1。.9，1.9的每个元素占
16、2 个单元,现将其三条对角线上的元素逐行存储在起始地址为 1000 的连续的内存单元中，则元素 A7,8的地址为 1038 。解释:三对角矩阵按行存储：k=2(i-1)+j(1=i，jj,ai j=t i(i-1）/2+j ，ij，aij=t j（j-1）/2+i（1=i,j=n）。10。设 n 行 n 列的下三角矩阵 A 已压缩到一维数组 B1。.n*（n+1）/2中，若按行为主序存储，则 Ai，j对应的 B 中存储位置为 i（i-1）/2+j(1=i，j=n)。10.设数组 A0。8，1.10，数组中任一元素 Ai，j均占内存 48 个二进制位，从首地址2000 开始连续存放在主内存里，主
17、内存字长为 16 位,那么 （l）存放该数组至少需要的单元数是 270 ;(2）存放数组的第 8 列的所有元素至少需要的单元数是 27 ；(3）数组按列存储时，元素 A5,8的起始地址是 2204 。11.用一维数组 B 与列优先存放带状矩阵 A 中的非零元素 A i,j (1in,i-2ji+2),B 中的第 8 个元素是 A 中的第 1 行，第 3 列的元素。12.设数组 a1.50，1。.80的基地址为 2000，每个元素占 2 个存储单元，若以行序为主序顺序存储，则元素 a45，68的存储地址为 9174 ;若以列序为主序顺序存储,则元素 a45,68的存储地址为 8788 .13。一维数组的逻辑结构是 线性结构 ,存储结构是 顺序结构 ,对二维或多维数组，分为按 以行序为主序 和 以列为主序 两种不同的存储方式。14.广义表(a)的表头是 （a），表尾是 （).15。对于元素是整数(占 2 个字节)的对称矩阵 A，采用以行序为主的压缩存储方式存储（下三角），若 A0 0的地址是 400，则元素 A8 5的的存储地址是 482 。