欢迎来到天天文库
浏览记录
ID:14093297
大小:55.00 KB
页数:8页
时间:2018-07-26
《(题)数据结构复习题》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、Ch2数组(共23题,其中14道算法设计题)一、填空题1、填空题(每小空1分,共5分)一维数组的逻辑结构是(①),存储结构是(②)。对于二维数组,有(③)和(④)两种不同的存储方式。对于一个二维数组A[m][n],若采取按行存储的方式,则任一数组元素A[i][j]相对于A[0][0]的地址为(⑤)。Key:①线性结构②顺序存储表示③行优先顺序④列优先顺序⑤n*i+j二、判断题2、判断下列叙述的对错。如果正确,在题前的括号内填入“Ö”,否则填入“´”。(´)线性表的逻辑顺序与物理顺序总是一致的。(´)线性表的顺序存储表示优
2、于链式存储表示。(Ö)线性表若采用链式存储表示时所有存储单元的地址可连续可不连续。(´)二维数组是其数组元素为线性表的线性表。(Ö)每种数据结构都应具备三种基本运算:插入、删除和搜索。三、简答题3、顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下,对有127个元素的顺序表进行插入,平均需要移动多少个元素?删除一个元素,又平均需要移动多少个元素?Key:插入时平均移动元素个数AMN=,所以平均移动63.5个元素删除时平均移动元素个数AMN=,所以平均移动63个元素84、设有一个10´10的对称矩阵A[10
3、][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]==415、设有三对角矩阵A[n][n],将其三条对角线中的元素逐行存储到一维数组B[3n-2]中,使得B[k]=A[i][j]。试求:(1)用i,j表
4、示k的地址转换公式;(2)用k表示i,j的地址转换公式;Key:1)在一维数组B中A[i][j]在第i行,它前面有3*i-1个非零元素,在本行第j列前面有j-i+1个,所以元素A[i][j]在B中的位置为k=2*i+j。2)i=┗(k+1)/3┛j=k-2*i6、上三角矩阵A[n][n],将其上三角元素逐行存储到一维数组B[m]中,使得B[k]=A[i][j],且k=f1(i)+f2(j)+C。试推导出函数f1(i)、f2(j)和常数C,要求f1(i)和f2(j)中不包含常数项。Key:若i≤j,数组元素在数组B中的存放
5、位置为n+(n-1)+……+(n-i+1)+j-i即为:,……若i>j,数组元素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)/28个元素。另设有一个二维数组C,它有n行n+1列。试设计一个方案,
6、将两个矩阵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]中,请给出一个公式,计算任
7、一非零元素aij在一维数组B中的存放位置。四、算法设计题10、已知整数数组A[]中有n个元素,试设计一个算法,求数组中所有元素值的和。Key:intsum_array(array,n)intarray[],n;{inti,sum=0;for(i=0;i8、;{inti,sum=0;floatave;for(i=0;i
8、;{inti,sum=0;floatave;for(i=0;i
此文档下载收益归作者所有