数据结构教程李春葆课后答案第6章数组和广义表.pdf

《数据结构教程李春葆课后答案第6章数组和广义表.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第6章数组和广义表教材中练习题及参考答案1.如何理解数组是线性表的推广。答：数组可以看成是线性表在下述含义上的扩展：线性表中的数据元素本身也是一个线性表。在d（d≥1）维数组中的每个数据元素都受着d个关系的约束，在每个关系中，数据元素都有一个后继元素（除最后一个元素外）和一个前驱元素（除第一个元素外）。因此，这d个关系中的任一关系，就其单个关系而言，仍是线性关系。例如，m×n的二维数组的形式化定义如下：A=(D，R)其中：D={aij

2、0≤i≤m-1，0≤j≤n-1}//数据元素的集合R={ROW，COL}ROW={

3、,j，ai+1,j>

4、0≤i≤m-2，0≤j≤n-1}//行关系COL={

5、0≤i≤m-1，0≤j≤n-2}//列关系2.有三维数组a[0..7，0..8，0..9]采用按行序优先存储，数组的起始地址是1000，每个元素占用2个字节，试给出下面结果：（1）元素a1,6,8的起始地址。（2）数组a所占用的存储空间。答：（1）LOC(a1,6,8)=LOC(a0,0,0)+[1×9×10+6×10+8]×2=1000+316=1316。（2）数组a所占用存储空间=8×9×10×2=1440字节。3.如

6、果某个一维数组A的元素个数n很大，存在大量重复的元素，且所有元素值相同的元素紧挨在一起，请设计一种压缩存储方式使得存储空间更节省。答：设数组的元素类型为ElemType，采用一种结构体数组B来实现压缩存储，该结构体数组的元素类型如下：struct{ElemTypedata;//元素值intlength;//重复元素的个数}如数组A[]={1，1，1，5，5，5，5，3，3，3，3，4，4，4，4，4，4}，共有17个元素，对应的压缩存储B为：{1，3}，{5，4}，{3，4}，{4，6}}。从中看出，如果重复元素越多，采用

7、这种压缩存储方式越节省存储空间。2数据结构教程学习指导4.一个n阶对称矩阵A采用压缩存储在一维数组B中，则B包含多少个元素？答：通常B中包含n阶对称矩阵A的下三角和主对角线上的元素，其元素个数为1+2+…n(n1)n(n1)+n=。所以B包含个元素。225.设n×n的上三角矩阵A[0..n-1，0..n-1]已压缩到一维数组B[0..m]中，若按列为主序存储，则A[i][j]对应的B中存储位置k为多少，给出推导过程。答：对于上三角部分或者主对角中的元素A[i][j（]i≤j），按列为主序存储时，前面有0～j-1共j列，

8、第0列有1个元素，第1列有2个元素，…，第j-1列有j个元素，所以这j列的元素个数=1+2+…+j=j(j+1)/2；在第j列中，A[i][j]元素前有A[0..i-1，j]共i个元素。所以A[i][j]元素前有j(j+1)/2+i个元素，而B的下标从0开始，所以A[i][j]在B中的位置k=j(j+1)/2+i。6.利用三元组存储任意稀疏数组A时，假设其中一个元素和一个整数占用的存储空间相同，问在什么条件下才能节省存储空间。答：设稀疏矩阵A有t个非零元素，加上行数rows、列数cols和非零元素个数nums（也算一个三元

9、组），那么三元组顺序表的存储空间总数为3(t+1)，若用二维数组存储时占用存储空间总数为m×n，只有当3(t+1)

10、清楚起见，在括号层次较多时，将head和tail的参数用中括号表示。例如head[G]、tail[G]分别表示求广义表G的表头和表尾。答：（1）head[(x，y，z)]=x。（2）tail[((a，b)，(x，y))]=((x，y))。9.设定二维整数数组B[0..m-1，0..n-1]的数据在行、列方向上都按从小到大的顺序排序，且整型变量x中的数据在B中存在。设计一个算法，找出一对满足B[i][j]=x的i、j值。要求比较次数不超过m+n。解：从二维数组B的右上角的元素开始比较。每次比较有三种可能的结果：若相等，则比较

11、结束；若x大于右上角元素，则可断定二维数组的最上面一行肯定没有与x相等的数据，下次比较时搜索范围可减少一行；若x小于右上角元素，则可断定二维数组的最右面一列肯定不包含与x相等的数据，下次比较时可把最右一列剔除出搜索范围。这样，每次比较可使搜索范围减少一行或一列，最多经过m+n次比较就可找到要求的与x相等