云南开放大学数据结构（C#语言）第五次离线作业

第5章
习题
一、填空题
1、二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元，并且A[0][0]的存储地址是200，则A[6][2]的地址是 。
2、二维数组A[-2..5，2..8]以行主序存储，设第一个元素的首地址是54，每个元素的长度为5，则元素A[0,6,5]的存储首地址为 。
3、有一个10阶段对称矩阵A，采用压缩存储方式（以行序为主存储，且A[0][0]=1），则A[8][5]的地址是 。
4、设广义表L=（（），（）），则Head（L）是 ；Tail（L）是 ；L的长度是 ；深度是 。
5、已知广义表L=（（x,y,z）,a,（u,t,w）），从L表中取出原子项t的运算是 。
二、选择题
1、数组通常具有的两种基本操作是（ ）。
A．建立和删除 B．索引和修改 C．查找和修改 D．查找和索引
2、二维数组A[10..20,5..10]采用以行主序的方式存储，每个数据元素占4个存储单元，且A[10,5]的存储地址是1000，则A[18,9]的存储地址是（ ）。
A．1208 B．1212 C．1368 D．1364
3、稀疏矩阵的压缩存储方法通常有两种，即（ ）。
A．二元数组和三元数组 B．三元组和散列 C．三元组和十字链表 D．散列和十字链表
4、二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储是元素M[3][5]的起始地址与M按列存储是元素（ ）的起始地址相同。
A．M[2][4] B．M[3][4] C．M[3][5] D．M[4][4]
5、已知Head（Tail）[Head（S），Head（Tail（Tail（S）））]））=[a]，广义表S满足上式，则S为（ ）。
A．[a,b]b,a] B．[[b,a],[a][b]] C．[[a],[a,b][b]] D．[[b],[b,a],[a ]]
三、判断题
1、十字链表不是顺序存储结构。 （ ）
2、三元组表不是一个随机存储结构。 （ ）
3、稀疏矩阵压缩存储后，必然会失去随机存取功能。 （ ）
4、若一个广义表的表头为空表，则此广义表也为空表。 （ ）
5、任何一个非空广义表，其表头可能是单元素或广义表，其表尾必定是广义表。 （ ）
6、一个稀疏矩阵Am*n,采用三元组形式表示，若把三元组中有关行下标和列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。 （ ）
7、如果广义表中的每个元素都是原子，则广义表便成为线性表。 （ ）
8、广义表中原子个数即为广义表长度。 （ ）
9、广义表最大子表的深度为广义表的深度。 （ ）
10、广义表中元素最大的层数称为广义表的深度。 （ ）
四、应用题
1、数组M中每个元素的长度是3个字节，行下标i从0到7，列下标从0到9，从首地址EA开始连续存放在存储器中。若按行优先方式存放，元素M[7][5]起始地址为多少？；若按列优先方式存放，元素M[7][5]起始地址为多少？
2、二维数组M的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到8，列下标j的范围从0到9，则存放M至少需要多少个字节？M的第8列和第5行共占多少个字节？若M 按行优先方式存储，元素M[8][6]的起始地址与当M按列优先方式存储时哪个的元素的起始地址一致？
3、设二维数组A5*6的每个元素占4个字节，已知LOC（a00）=1000，A共占多少个字节？A的终端结点的起始位置是多少？按行和列优先存储时，a25的起始地址分别为多少？
4、 设矩阵A=
(1)若将A视为对称矩阵，画出对其压缩存储的存储表，并讨论如何存取A中元素aij (0<=i,j<4)；
(2)若将A视为稀疏矩阵，画出A的十字链表结构。
5、画出具有共享结构广义表（（（b,c）,d）,(a),((a),((b,c),d)),e,()）的存贮表示。
五、算法设计题
1、用二维数组实现“魔方阵”的打印，所谓“魔方阵”是指满足每一行、每一列和对角线上的元素之和均相等的方阵。例如：
8 1 6
3 5 7
4 9 2
就是一个三阶的魔方阵。现在要求编程实现任意输入一个自然数n，打印出相应的n阶方阵。
1、找出并打印一个二维数组中的鞍点，所谓鞍点是指该位置上的元素在该行上最大，在该列上最小。

AI创作