(题)数据结构复习题

《(题)数据结构复习题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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个元

3、素84、设有一个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]==415、设有三对角矩阵A[n][n]，将其三条对角线中的元素逐行存储到一维数组B[

4、3n-2]中，使得B[k]=A[i][j]。试求：（1）用i，j表示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）和常数

5、C，要求f1（i）和f2（j）中不包含常数项。Key：若i≤j，数组元素在数组B中的存放位置为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均为下三角矩阵，每一个都有

6、n行。因此在下三角区域中各有n（n+1）/28个元素。另设有一个二维数组C，它有n行n+1列。试设计一个方案，将两个矩阵A和B中的下三角区域元素存放于同一个C中。要求将A的下三角区域中的元素存放于C的下三角区域中，B的下三角区域中的元素转置后存放于C的上三角区域中。并给出计算A的矩阵元素aij和B的矩阵元素bij在C中的存放位置下标的公式。9、设带状矩阵A[n][n]是n´n阶的方阵，其中所有的非零元素都在由主对角线及主对角线上下各b条对角线构成的带状区域内，其它都为零元素。试问：（1）该带状矩阵中

7、有多少个非零元素？（2）若用一个一维数组B[]按行顺序存放各行的非零元素，且设A[1][1]存放在B[0]中，请给出一个公式，计算任一非零元素aij在一维数组B中的存放位置。四、算法设计题10、已知整数数组A[]中有n个元素，试设计一个算法，求数组中所有元素值的和。Key：intsum_array（array，n）intarray[]，n；{inti，sum=0；for（i=0；i

8、、已知整数数组A[]中有n个元素，试设计一个算法，求数组中所有元素值的平均值。Key：intsum_array（array，n）8intarray[]，n；{inti，sum=0；floatave；for（i=0；i