(题)数据结构复习题.docVIP

Ch2数组 （共23题，其中14道算法设计题） 一、填空题 1、填空题 （1分，共5分）（）（）（ ）（ ）A[m][n]，若采取按行存储的方式，则任一数组元素A[i][j]相对于A[0][0]的地址为（ ） Key： ① 线性结构 ② 顺序存储表示 ③ 行优先顺序 ④ 列优先顺序 ⑤ n * i + j 二、判断题 2、判断下列叙述的对错。如果正确，在题前的括号内填入“?”，否则填入“?”。 （?） （?） （?） （?） （?） 三、简答题 3、顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下， 127个元素的顺序表进行插入， ? 删除一个元素， ? Key： 插入时平均移动元素个数AMN = ， 所以平均移动 63.5 个元素 删除时平均移动元素个数AMN = ， 所以平均移动 63 个元素 4、设有一个10?10的对称矩阵A[10][10]，采取按行压缩存储的方式存放于一个一维数组B[ ]中，则数组B[ ]的容量应有多大？若设A[0][0]为第一个元素，存放于B[0]，且数组A[ ][ ]的每一个数组元素在数组B[ ]中占一个数组元素位置，则A[8][5]在数组B[ ]中的地址是多少？ Key： 1）数组B共应有 = 55个元素。 2）对于上三角矩阵，A[8][5] = A[5][8] = = 43 对于下三角矩阵，A[8][5] = = 41 5、设有三对角矩阵A[n][n]，将其三条对角线中的元素逐行存储到一维数组B[3n-2 ]中，使得B[k] = A[i][j]。试求： （1） i， jk的地址转换公式； （2） k表示i， ji-1个非零元素，在本行第j列前面有j-i+1个，所以元素A[i][j]在B中的位置为k=2*i + j。 2） i = ┗（k+1）/3 ┛ j= k-2*i 6、上三角矩阵A[n][n]，将其上三角元素逐行存储到一维数组B[m]中，使得B[k] = A[i][j]，且k = f1 （i） + f2 （j） + Cf1 （i）f2 （j）C，要求f1 （i）f2 （j）i+1）+j-i 即为：，…… 若ij，数组元素A[i][j]在矩阵的下三角部分，在数组B中没有存放，因此找它们的对称元素A[j][i]，即，…… 7、设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（10）A[2][2]存放位置在676（10）A[4][4]在什么位置，下标（10）10进数表示。 8、设A和B均为下三角矩阵，每一个都有n行。因此在下三角区域中各有n（n+1）/2C，它有n行n+1列。试设计一个方案，将两个矩阵A和B中的下三角区域元素存放于同一个C中。要求将A的下三角区域中的元素存放于C的下三角区域中，B的下三角区域中的元素转置后存放于C的上三角区域中。并给出计算A的矩阵元素aij和B的矩阵元素bij在C中的存放位置下标的公式。 9、设带状矩阵A[n][n] 是n?n阶的方阵，其中所有的非零元素都在由主对角线及主对角线上下各b条对角线构成的带状区域内，其它都为零元素。试问： （1） （2） B[ ] 按行顺序存放各行的非零元素，且设A[1][1]存放在B[0]中，请给出一个公式，计算任一非零元素aij在一维数组B中的存放位置。 四、算法设计题 10、已知整数数组A[ ]中有n个元素，试设计一个算法，求数组中所有元素值的和。 Key： int sum_array（array，n） int array[]，n； { int i，sum = 0； for（i=0；in；i++） { sum += array[i]； } printf（”the sum of array is %d\n”，sum）； } 11、已知整数数组A[ ]中有n个元素，试设计一个算法，求数组中所有元素值的平均值。 Key： int sum_array（array，n） int array[]，n； { int i， sum = 0； float ave； for（i=0；in；i++） { sum += array[i]； ave = （float）（sum/n）； } printf（”the ave of array is %f\n”，ave）； } 12、设有一个线性表 （e0， e1， ， en-2， en-1）A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个地址的内容置换为 （en-1， en-2， ， e1， e