第五章 数组与广义表
一．选择题
1．下面的说法不正确的是____________。
A．数组是一种线性结构 B．数组是一种定长的线性表结构
C．除了插入与删除操作外，数组的基本操作还有存取、修改、检索和
排序等
D．数组的基本操作有存取、修改、检索和排序等，没有插入和删除操
作
分析：数组的主要操作是存取、修改、检索和排序。数组没有插入和修改
错误。答案应选择 C。
2． 一维数组 A 采用顺序存储结构，每个元素占用 6 个字节，第 6 个元素
的起始地址为 100，则该数组的首地址是
。
A．64 B．28 C．70 D．90
分析：设数组元素的首地址为 x，则存在关系 x+5*6=100，因此 x 为 70，答
案应选择 C。
3．稀疏矩阵采用压缩存储的目的主要是______________ 。
A．表达变得简单 B．对矩阵元素的存取变得简单
C．去掉矩阵中的多余元素 D．减少不必要的存储空间的开销
分析：答案应选择 D。
4．若对 n 阶对称矩阵 A 以行序为主序方式将其下三角形的元素(包括主对
数组和链表角线上所有元素)依次存放于一维数组 B［1..(n(n+1))/2］中，则在 B 中确
定 aij(i<j)的位置 k 的关系为______。
A. i*(i+1)/2+j B. j*(j+1)/2+i C. i*(i+1)/2+j+1 D.
j*(j+1)/2+i+1
分析： 设以行为主序放对称矩阵的下三 角元素， 其存储结
构如 5.4 所示， a00 存储在 B[1],a10 存储 在 B[2], ……
an-1n-1 存储在 B[n (n+1)/2]，则对称矩阵 k 与(i，j)的对应关系为：故答案
应选择 B。
B[ ] 1 2
3 4 5 6 … k …
(n(n+1))/2-1
(n(n+1))/2
A a00 a10 a11 a20 a21 a22 … aij … a(n-1)
(n-2) a(n-1)
(n-1)
图 5.4 对称矩阵的存储示意图
5．已知广义表 LS=((a,b,c), (d,e,f))，运用 GetHead 和 GetTail 运算取
出 LS 中的元素 e 的运算是
。
A． GetHead(GetTail(LS)) B． GetHead(GetTail(GetTail (GetHead
(LS))))
C ．
GetTail (GetHead (LS))
D．GetHead(GetTail(GetHead(GetTail(LS))))
分析：本题的解答过程要应用排除法，分别对 A、B、C、D 选项进行计算并
判断。根据选项 D 可知：GetHead(GetTail(GetHead(GetTail(LS))))＝
GetHead(GetTail(GetHead
((d,e,f))))= GetHead(GetTail(d,e,f))= GetHead((e,f))=e。答案应选
择 D。
6. 设广义表 L=((a,b,c))，则 L 的长度和深度分别为
。
A. 1 和 1 B. 1 和 3 C. 1 和 2 D. 2 和 3
i(i+1)/2+j+1ij
k=
j(j+1)/2+i+1i<j
分析：该题目主要考查广义表的长度和深度的基本概念，广义表的长度是
广义表中层次为 1 的元素个数，而广义表的深度是指广义表展开后所含括
号的层数。因此本题中的 L 的长度为 1，L 的深度为 2。答案应选择 C。
7. 一个 100*90 的稀疏矩阵，非 0 元素有 10 个整型数，设每个整型数占 2
字节，则用三元组表示该矩阵时，所需的字节数是_____________。
A. 60 B. 66 C. 18000 D. 33
分析：三元组表结构为(行，列，元素值)，用三元组表表示稀疏矩阵时，
还需记录稀疏矩阵的行数、列数以及非零元素个数，本题中所需的字节数
应为 10*(1+1+1)*2+3*2＝66。答案应选择 D。
二 判断题
1．稀疏矩阵压缩后，必会失去随机存取功能。
正确
分析： 具有存取任一个元素的时间相等这一特点的存储结构称为随机存取结
构。对稀疏矩阵压缩存储所用的存储结构是三元组表或十字链表。十字链
表因其链表结构而不能随机存取；而使用三元组表存储矩阵时，若要访问
元素 aij，则必须扫描三元组表，显然查三元组表中前后元素所消耗的时
间不同。
2．线性表可以看成是广义表的特例，如果广义表中的每个元素都是原子，
则广义表便成为线性表。
正确
3． 广义表中的元素可以是一个不可分割的原子， 或者是一个非空的广义表。
错误。
分析：该题目主要考查广义表的定义，广义表中元素可以是原子，也可以
是表(包括空表和非空表)。
4．广义表中原子个数即为广义表的长度。
错误
分析：该题目主要考查广义表长度的定义，广义表的长度是广义表中层次
为 1 的元素个数。因此本题说法是片面的。
5．数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插
入，删除等操作。
错误
分析：数组可以看成一种特殊的线性表，数组在维数和上下界确定后，其
元素个数已经确定，不能进行插入和删除运算。但线性表可以插入删除。
二．填空题
1． 需要压缩存储的矩阵可分为
矩阵和
矩阵两种。
答案：特殊矩阵 稀疏矩阵
分析：关于矩阵的压缩存储方法，根据矩阵的特点分为特殊矩阵和稀疏矩
阵。特殊矩阵要求进行压缩存储时保持其随机存取特性不变，而稀疏矩阵
则会失去随机存取功能。
2． 设数组 A[0..8,1..10],数组中任一元素 A[i,j]均占内存 48 个二进制位，
从首地址 2000 开始连续存放在主内存里，主内存字长为 16 位，那么
(1) 存放该数组至少需要的单元数是 (1)
；
(2) 存放数组的第 8 列的所有元素至少需要的单元数是 (2)
；
(3) 数组按列优先存储时，元素 A[5,8]的起始地址是 (3)
。
答案：(1) 270 (2) 27 (3) 2204
分析：(1)数组 A[0..8,1..10]的数组元素个数为 9*10＝90，因此存放该数
组的单元个数为 90*48/16＝270，其中每个单元占据 48/16=3 个字长。(2)
存放数组的第 8 列的所有元素应为 9*48/16＝27。 (3)若数组按列优先存储，
元素 A[5,8]的起始地址为 2000+(7*9+5)*3＝2204。
3．设数组 A[1..50,1..80]的基地址为 2000，每个元素占 2 个存储单元，
若以行序为主序顺序存储，则元素 A[45,68]的存储地址为 (1)
;
若以列序为主序顺序存储， 则元素 A[45,68]的存储地址为 (2)
。
答案：(1)9174 (2)8878
分析：本题主要考查计算某元素的存储地址，注意区分按行为主序和以列
为主序的存储方式。
(1)A[45,68]的存储地址=2000+((45-1)*80+67)*2＝9174；
(2)A[45,68]的存储地址=2000+((68-1)*50+44)*2＝8788。
4．设广义表 L=(()，()) ，则 GetHead(L)是
；GetTail(L)
是
；L 的长度是
；L 的深度
是
。
答案：() (()) 2 2
分析：对于广义表 LS=(a1,a2,a3,…,an)，各个运算如下：
表头：GetHead(LS)=a1
表尾：GetTail(LS)= (a2,a3,…,an)
长度：Length(LS)=n
深度：
故答案为：GetHead(L)=()；GetTail(L)=(())； L 的长度为 2；L 的深度为
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论