第五章 数组和广义表
一、选择题
1. 常对数组进行的两种基本操作是（ ）
（A）建立与删除（B）索引和修改（C）查找和修改（D）查找与索引 参考答案：C
2.二维数组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] 参考答案：B
3.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,存放该数组至少需要的单元数是（ ）。
（A）80（B）100（C）240（D）270 参考答案：C
4.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按行存放时,元素A[7][4]的起始地址为（ ）。
（A）SA+141（B）SA+144（C）SA+222（D）SA+225 参考答案：C
5.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按列存放时,元素A[4][7]的起始地址为（ ）。
（A）SA+141（B）SA+180（C）SA+222（D）SA+225 参考答案：B
6.稀疏矩阵一般的压缩存储方法有两种,即（ ）。 （A） 二维数组和三维数组（B）三元组和散列 （C）三元组和十字链表 （D）散列和十字链表 参考答案：C
7.若采用三元组压缩技术存储稀疏矩阵,只要把每个元素的行下标和列下标互换,就完成了对该矩阵的转置运算,这种观点（ ）。
（A）正确（B）错误 参考答案：B
8.设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中,对下三角部分中任一元素ai,j(i<=j),在一组数组B的下标位置k的值是（ ）。
（A）i(i-1)/2+j-1（B）i(i-1)/2+j（C）i(i+1)/2+j-1 (D)i(i+1)/2+j 参考答案：B 二、填空题
1.己知二维数组A[m][n]采用行序为主方式存储,每个元素占k个存储单元,并且第一个元素的存储地址是LOC(A[0][0]),则A[0][0]的地址是_____________________。
loc(A[0][0])
2.二维数组A[10][20]采用列序为主方式存储,每个元素占一个存储单元,并且A[0][0]的存储地址是200,则A[6][12]的地址是________________。
326
3.有一个10阶对称矩阵A,采用压缩存储方式(以行序为主,且A[0][0]=1),则A[8][5]的地址是__________________。
42
4.设n行n列的下三角矩阵A已压缩到一维数组S[1..n*(n+1)/2]中,若按行序为主存储,则A[i][j]对应的S中的存储位置是________________。
i*(i+1)/2+j+1
5.若A是按列序为主序进行存储的4×6的二维数组,其每个元素占用3个存储单元,并且A[0][0]的存储地址为1000,元素A[1][3]的存储地址为___________,该数组共占用_______________个存储单元。
1039；72 三、算法设计
1.如果矩阵A中存在这样的一个元素A[i][j]满足条件:A[i][j]是第i行中值最小的元素,且又是第j列中值最大的元素,则称之为该矩阵的一个马鞍点。编写一个函数计算出1×n的矩阵A的所有马鞍点。
算法思想：依题意,先求出每行的最小值元素,放入min[m]之中,再求出每列的最大值元素,放入max[n]之中,若某元素既在min[i]中,又在max[j]中,则该元素A[i][j]便是马鞍点,找出所有这样的元素,即找到了所有马鞍点。因此,实现本题功能的程序如下:
#include
void minmax(int a[m][n]) {
int i1,j,have=0; int min[m],max[n];
for(i1=0;i1 min[i1]=a[i1][0]; for(j=1;j if(a[i1][j] for(j=0;j max[j]=a[0][j]; for(i1=1;i1 if(a[i1][j]>max [j]) max[j]=a[i1][j]; } for(i1=0;i1 printf(\ have=1; } if(!have) printf(\没有鞍点＼n\ } 2.n只猴子要选大王,选举办法如下:所有猴子按1,2,...,n编号围坐一圈,从1号开始按1、2、...、m报数,凡报m号的退出到圈外,如此循环报数,直到圈内剩下只猴子时,这只猴子就是大王。n和m由键盘输入,打印出最后剩下的猴子号。编写一程序实现上述函数。 算法思想:本题用一个含有n个元素的数组a,初始时a[i]中存放猴子的编号i,计数器似的值为0。从a[i]开始循环报数,每报一次,计数器的值加1,凡报到m时便打印出a[i]值
数据结构习题及答案 (7)
