数据结构简明教程(第2版)学习与上机实验指导

　　第5章数组和稀疏矩阵　　5.1练习题5及参考答案　　5.1.1练习题5　　1. 单项选择题　　（1） 有一个三维数组A［-2..2］［-4..5］［2..6］，其元素个数是（）。　　A. 60B. 250C. 144D. 396　　（2） 设二维数组A［1..5］［1..8］，若按行优先的顺序存放数组的元素，则A［4］［6］元素的前面有（）个元素。　　A. 6B. 28C. 29D. 40　　（3） 设二维数组A［1..5］［1..8］，若按列优先的顺序存放数组的元素，则A［4］［6］元素的前面有（）个元素。　　A. 6B. 28C. 29D. 40　　（4） 一个n阶对称矩阵A采用压缩存储方式，将其下三角部分按行优先存储到一维数组B中，则B中元素个数是（）。　　A. nB. n2　　C. n（n+1）/2D. n（n+1）/2+1　　（5） 一个n阶对称矩阵A［1..n，1..n］采用压缩存储方式，将其下三角部分按行优先存储到一维数组B［1..m］中，则A［i］［j］（i≥j）元素在B中的位置k是（）。　　A. j（j-1）/2+iB. j（j-1）/2+i-1　　C. i（i-1）/2+jD. i（i-1）/2+j-1　　（6） 一个对称矩阵A［1..10,1..10］采用压缩存储方式，将其下三角部分按行优先存储到一维数组B［0..m］中，则A［8］［5］元素在B中的位置k是（）。　　A. 32B. 37C. 45D. 60　　（7） 一个对称矩阵A［1..10,1..10］采用压缩存储方式，将其下三角部分按行优先存储到一维数组B［0..m］中，则A［5］［8］元素值在B中的位置k是（）。　　A. 18B. 32C. 45D. 60　　（8） 一个对称矩阵A［1..10，1..10］采用压缩存储方式，将其上三角部分按行优先存储到一维数组B［1..m］中，则A［8］［5］元素值在B中的位置k是（）。　　A. 10B. 37C. 45D. 60　　（9） 一个n阶上三角矩阵A按列优先顺序压缩存放在一维数组B，则B中元素个数是（）。　　A. nB. n2C. n（n+1）/2D. n（n+1）/2+1　　（10） 一个10阶下三角矩阵A［0..9，0..9］按行优先压缩存放在一维数组B［0..m］中，则A［3］［2］在B中的位置k是（）。　　A. 1B. 8C. 10D. 21　　（11） 对特殊矩阵采用压缩存储的目的主要是为了（）。　　A. 表达变得简单B. 对矩阵元素的存取变得简单　　C. 去掉矩阵中的多余元素D. 减少不必要的存储空间　　（12） 稀疏矩阵是指（）的矩阵。　　A. 非零元素较多且分布无规律B. 非零元素较少且分布无规律　　C. 总元素个数较少D. 不适合用二维数组表示　　（13） 稀疏矩阵一般的压缩存储方法有两种，即（）。　　A. 二维数组和三维数组B. 三元组和散列　　C. 三元组和十字链表D. 散列和十字链表　　（14） 一个稀疏矩阵采用压缩后，和直接采用二维数组存储相比会失去（）特性。　　A. 顺序存储B. 随机存取C. 输入输出D. 以上都不对　　（15） 一个m行n列的稀疏矩阵采用十字链表表示时，其中总的头结点的个数为（）。　　A. m+1B. n+1　　C. m+n+1D. MAX{m，n}+1　　2. 填空题　　（1） 三维数组A［c1..d1，c2..d2，c3..d3］（c1≤d1，c2≤d2，c3≤d3）共含有（）个元素。　　（2） 已知二维数组A［m］［n］采用行序为主序存储，每个元素占k个存储单元，并且**个元素的存储地址是LOC（A［0］［0］），则A［i］［j］的地址是（）。　　（3） 二维数组A［10］［20］采用列序为主序存储，每个元素占一个存储单元，并且A［0］［0］的存储地址是200，则A［6］［12］的地址是（）。　　（4） 二维数组A［10..20］［5..10］采用行序为主方式存储，每个元素占4个存储单元，并且A［10］［5］的存储地址是1000，则A［18］［9］的地址是（）。　　（5） 有一个10阶对称矩阵A，采用压缩存储方式（以行序为主存储下三角部分，且A［0］［0］存放在B［1］中），则A［8］［5］在B中的地址是（）。　　（6） 设n阶下三角矩阵A［1..n］［1..n］已压缩到一维数组B［1..n（n+1）/2］中，若按行序为主存储，则A［i］［j］对应的B中的存储位置是（）。　　（7） 稀疏矩阵的三元组表示中，每个结点对应于稀疏矩阵的一个非零元素，它包含三个数据项，分别表示该元素的（）。　　3. 简答题　　（1） 简述数组的主要基本运算。　　（2） 为什么说数组是线性表的推广或扩展，而不说数组就是一种线性表呢？　　（3） 为什么数组一般不采用链式结构存储？　　（4） 如果一维数组A中元素个数n很大，存在大量重复的元素，且所有元素值相同的元素紧挨在一起，请设计一种压缩存储方式使得存储空间更节省。　　4. 算法设计题　　（1） 假定数组A［0..n-1］的n个元素中有多个零元素，设计一个算法将A中所有的非零元素全部移到A的前端。　　（2） 有一个含有n个整数元素的数组a［0..n-1］，设计一个算法通过比较求a［i..j］中的**个*小元素的下标。　　（3） 设计一个算法，求一个n×n的二维整型数组A的下三角和主对角部分的所有元素之和。　　（4） 设计一个算法，给定一个n×n的二维整型数组A，按位置输出其中左上右下和左下右上两条对角线的元素。　　5.1.2练习题5参考答案　　1. 单项选择题　　（1） B（2） C（3） B（4） C（5） C　　（6） A（7） B（8） B（9） D（10） B　　（11） D（12） B（13） C（14） B（15） D　　2. 填空题　　（1） （d1-c1+1）×（d2-c2+1）×（d3-c3+1）　　（2） LOC（A［0］［0］）+（n×i+j）×k　　（3） 326　　（4） 1208　　（5） 42　　（6） i（i-1）/2+j　　（7） 行下标、列下标和元素值　　3. 简答题　　（1） 答： 数组的主要基本运算如下。　　① 取值运算： 给定一组下标，读取其对应的数组元素。　　② 赋值运算： 给定一组下标，存储或修改与其相对应的数组元素。　　（2） 答： 从逻辑结构的角度看，一维数组是一种线性表； 二维数组可以看成数组元素为一维数组的一维数组，所以二维数组是线性结构，可以看成是线性表，但就二维数组的形状而言，它又是非线性结构，因此将二维数组看成是线性表的推广更准确。三维及以上维的数组也是如此。　　（3） 答： 因为数组使用链式结构存储时需要额外占用更多的存储空间，而且不具有随机存取特性，使得相关操作更复杂。　　（4） 答： 设数组的元素类型为ElemType，采用一种结构体数组B来实现压缩存储，该结构体数组的元素类型如下。　　……