[复习]数据结构(本科)期末综合练习三(运算题).doc

数据结构(本科)期末综合练习三(运算题) 愚昧从来没有给人带来幸福；幸福的根源在于知识。——左拉 数据结构（本科）期末综合练习三（运算题） 　　1. 对于一个n?n的矩阵A的任意矩阵元素a[i][j]，按行存储时和按列存储时的地址之差是多少。（设两种存储时的开始存储地址均为LOC(0, 0)，元素所占存储单元数均为d） 　　2. 设有一个二维数组A[10][20]，按行存放于一个连续的存储空间中，A[0][0]的存储地址是200，每个数组元素占1个存储字，则A[6][2]的地址是多少。 　　3. 设有一个二维数组A[10][20]，按列存放于一个连续的存储空间中，A[0][0]的存储地址是200，每个数组元素占1个存储字，则A[6][2]的地址是多少。 　　4. 设有一个10?10的矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么A[8][5]存放于B中什么位置。 　　5. 设有一个10?10的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么A[8][5]存放于B中什么位置。 　　6. 设有一个二维数组A[m][n]采用按行存储，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个存储字，则A[4][4]存放在什么位置。 　　7. 设有一个二维数组A[11][6]，按行存放于一个连续的存储空间中，A[0][0]的存储地址是1000，每个数组元素占4个存储字，则A[8][4]的地址在什么地方。 　　8. 设有一个三维数组A[10][20][15]，按页∕行∕列存放于一个连续的存储空间中，每个数组元素占4个存储字，首元素A[0][0][0]的存储地址是1000，则A[8][4][10]存放于什么地方。 9. 假定一棵二叉树广义表表示为a(b(c),d(e,f))，分别写出对它进行中序、后序、按层遍历的结果。 中序： 后序： 按层： 10. 假定一棵二叉树的广义表表示为A(B(,D(G)),C(E,F))，分别写出对它进行前序、中序、按层遍历的结果。 前序： 中序： 按层： 11. 假定一棵普通树的广义表表示为a(b(e),c(f(h,i,j),g),d)，分别写出先根、后根、按层遍历的结果。 先根： 后根： 按层： 12. 已知一棵二叉树的前序和中序序列，求该二叉树的后序序列。 先根序列：A,B,C,D,E,F,G,H,I,J 中根序列：C,B,A,E,F,D,I,H,J,G 　　　　后根序列： 13. 已知一棵二叉树的中序和后序序列如下，求该二叉树的前序序列。 中根序列：c,b,d,e,a,g,i,h,j,f 后根序列：c,e,d,b,i,j,h,g,f,a 　　　　先根序列： 14. 已知一棵二叉树的中序和后序序列如下，求该二叉树的高度（假定空树的高度为-1）和度为2、度为1及度为0的结点个数。 中序序列：c,b,d,e,a,g,i,h,j,f 后序序列：c,e,d,b,i,j,h,g,f,a 高度： 度为2的结点数： 度为1的结点数： 度为0的结点数： 15. 已知一棵二叉树的静态数组表示（即顺序存储）如下，其中-1表示空，请分别写出该二叉树的前序、中序、后序遍历序列。 0 1 2 3 4 5 6 7 8 9 10 11 12 20 8 46 5 15 30 -1 -1 -1 10 18 -1 35 前序序列： 中序序列： 后序序列： 16. 已知一棵树的静态双亲表示如下，其中用-1表示空指针，树根结点存于0号单元，分别求出该树的叶子结点数、单分支结点数、两分支结点数和三分支结点数。 序号： 0 1 2 3 4 5 6 7 8 9 10 a b c d e f g h i j k -1 0 1 1 3 0 5 6 6 0 9 data: parent: 　　叶子结点数： 　　单分支结点数： 　　两分支结点数： 　　三分支结点数： 17. 有7个带权结点，其权值分别为3,7,8,2,6,10,14，试以它们为叶子结点生成一棵霍夫曼树，求出该树的带权路径长度、高度、双分支结点数。 带权路径长度：