栈、队列、串、数组和广义表 习题
一、选择题
1 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ ）。
A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2
2 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是( )。
A. i B. n-i C. n-i+1 D. 不确定
3 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )
A. 1和 5 B. 2和4 C. 4和2 D. 5和1
4 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。
A． 6 B. 4 C. 3 D. 2
5 设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）
A．求子串 B．联接 C．匹配 D．求串长
6 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。
A. 13 B. 33 C. 18 D. 40
7 已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( )。
第 1 页 共 8 页 开放大学数据结构(本科)单元5数组和广义表
单元测试题含答案
试题 1一维数组A采用顺序存储结构，每个元素占用4个字节，第8个元素的存储地址为120，则该数组的首地址是（ ）。
选择一项：
A.88
B.92
C.32
D.90
反馈
正确答案是：92
试题 2稀疏矩阵采用压缩存储的目的主要是（ ）。
选择一项：
A.对矩阵元素的存取变得简单
B.表达变得简单
C.去掉矩阵中的多余元素
D.减少不必要的存储空间的开销
反馈
正确答案是：减少不必要的存储空间的开销
试题 3一个非空广义表的表头（ ）。 第 2 页 共 8 页 选择一项：
A.只能是子表
B.可以是子表或原子
C.不可能是原子
D.只能是原子
反馈
正确答案是：可以是子表或原子
试题 4常对数组进行的两种基本操作是（ ）。
选择一项：
A.索引与、和修改
B.查找与索引
C.查找和修改
D.建立与删除
反馈
正确答案是：查找和修改
试题
5在二维数组A[8][10]中，每一个数组元素A[i][j] 占用3个存储空间，所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储空间是（ ）。
选择一项：
A.80
B.270 第 3 页 共 8 页 C.240
D.100
反馈
正确答案是：240
试题 6设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素A10,8在一维数组B中的下标是（ ）。
选择一项：
A.18
B.53
C.45
D.58
反馈
正确答案是：53
试题 7广义表((a))的表尾是（ ）。
选择一项：
A.((a))
B.(a)
C.0
D.a
反馈 第 4 页 共 8 页 正确答案是：0
试题 8设有一个10阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素A8,5在一维数组B中的下标是（ ）。
习题五 数组和广义表
一、单项选择题
1．常对数组进行的两种基本操作是（ ）
A.建立与删除 B. 索引与修改 C. 查找与修改 D. 查找与索引
2．对于C语言的二维数组DataType A[m][n],每个数据元素占K个存储单元，二维数组中任意元素a[i,j] 的存储位置可由( )式确定.
A.Loc[i,j]=A[m,n]+[(n+1)*i+j]*k
B.Loc[i,j]=loc[0,0]+[(m+n)*i+j]*k
C.Loc[i,j]=loc[0,0]+[(n+1)*i+j]*k
D.Loc[i,j]=[(n+1)*i+j]*k
3．稀疏矩阵的压缩存储方法是只存储 ( )
A.非零元素 B. 三元祖（i,j, aij） C. aij D. i,j
4. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。
A. 1175 B. 1180 C. 1205 D. 1210
5. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（ ）。
A. i（i-1）/2+j B. j（j-1）/2+i C. i（j-i）/2+1 D. j（i-1）/2+1
6. 用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j 沿链移动的操作为( )。
A. j=r[j].next B. j=j+1 C. j=j->next D. j=r[j]-> next
我下vip免费资源网
第五章 数组和广义表答案
一、选择题
1.B 2.1L 2.2J 2.3C 2.4I 2.5C 3.B 4.B 5.A 6.1H 6.2C 6.3E
6.4A 6.5F 7.B 8.1E 8.2A 8.3B 9.B 10.B 11.B 12.B 13.A 14.B
15.B 16.A 17.C 18.D 19.C 20.D 21.F 22.C 23.D 24.C 25.A 26.C
27.A
二、判断题
1. × 2.√ 3.√ 4.× 5.× 6. × 7.√ 8.× 9.× 10.× 11.× 12.√
13.√ 14.√
部分答案解释如下。
1. 错误。对于完全二叉树，用一维数组作存储结构是效率高的（存储密度大）。
4. 错误。数组是具有相同性质的数据元素的集合，数据元素不仅有值，还有下标。因此，可以说数祖是元素值和下标构成的偶对的有穷集合。
5. 错误。数组在维数和界偶确定后，其元素个数已经确定，不能进行插入和删除运算。
6. 错误。稀疏矩阵转置后，除行列下标及行列数互换外，还必须确定该元素转置后在新三元组中的位置。
8. 错误。广义表的取表尾运算，是非空广义表除去表头元素，剩余元素组成的表，不可能是原子。
9. 错误。广义表的表头就是广义表的第一个元素。只有非空广义表才能取表头。
10. 错误。广义表中元素可以是原子，也可以是表（包括空表和非空表）。
11. 错误。广义表的表尾，指去掉表头元素后，剩余元素所组成的表。
三、填空题
1. 顺序存储结构 2.（1）9572（2）1228 3.（1）9174（2）8788 4. 1100
5. 1164 公式：LOC(aijk)=LOC(a000)+[v2*v3*(i-c1)+v3*(j-c2)+(k-c3)]*l (l为每个元素所占单元数)
6. 232 7. 1340 8. 1196 9. 第1行第3列
