《数据结构(本科)期末综合练习三(运算题)》由会员分享，可在线阅读，更多相关《数据结构(本科)期末综合练习三(运算题)（28页珍藏版）》请在金锄头文库上搜索。
1、数据结构数据结构( (本科本科) )期末综合练习三期末综合练习三( (运算题运算题) )精品文档！欢迎下载大家下载阅读！数据结构（本科）期末综合练习三（运算题）1. 对于一个 n?n 的矩阵 A 的任意矩阵元素 aij，按行存储时和按列存储时的地址之差是多少。 （设两种存储时的开始存储地址均为 LOC(0, 0)，元素所占存储单元数均为 d）2. 设有一个二维数组 A1020，按行存放于一个连续的存储空间中，A00的存储地址是 200，每个数组元素占 1 个存储字，则 A62的地址是多少。3. 设有一个二维数组 A1020，按列存放于一个连续的存储空间中，A00的存储地址是 200，每个数组元
2、素占 1 个存储字，则 A62的地址是多少。4. 设有一个 10?10 的矩阵 A，将其下三角部分按行存放在一个一维数组 B 中，A00存放于 B0中，那么 A85存放于 B 中什么位置。5. 设有一个 10?10 的对称矩阵 A，将其上三角部分按行存放在一个一维数组 B 中，A00存放于 B0中，那么 A85存放于 B中什么位置。6. 设有一个二维数组 Amn采用按行存储，假设 A00存放位置在 644(10)，A22存放位置在 676(10)，每个元素占一个存储字，则 A44存放在什么位置。7. 设有一个二维数组 A116，按行存放于一个连续的存储空间中，A00的存储地址是 1000，每个
3、数组元素占 4 个存储字，则 A84的地址在什么地方。8. 设有一个三维数组 A102015，按页行列存放于一个连续的存储空间中，每个数组元素占 4 个存储字，首元素 A000的存储地址是 1000，则 A8410存放于什么地方。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)，分别写出先根、后根、按层遍
4、历的结果。先根：后根：按层：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高度：
5、 度为 2 的结点数： 度为 1 的结点数： 度为 0 的结点数：15. 已知一棵二叉树的静态数组表示（即顺序存储）如下，其中-1 表示空，请分别写出该二叉树的前序、中序、后序遍历序列。0 1 2 3 4 5 6 7 8 9 10 11 12 2084651530-1-1-11018-135前序序列：中序序列：后序序列：16. 已知一棵树的静态双亲表示如下，其中用-1 表示空指针，树根结点存于 0 号单元，分别求出该树的叶子结点数、单分支结点数、两分支结点数和三分支结点数。序号： 0 1 2 3 4 5 6 7 8 9 10abcdefghijk-10113056609data: parent
6、:叶子结点数： 单分支结点数：两分支结点数：三分支结点数：17. 有 7 个带权结点，其权值分别为 3,7,8,2,6,10,14，试以它们为叶子结点生成一棵霍夫曼树，求出该树的带权路径长度、高度、双分支结点数。带权路径长度：高度：双分支结点数：18. 一个一维数组 a10中存储着有序表 (15,26,34,39,45,56,58,63,74,76)，根据折半搜索所对应的判定树，写出该判定树中度为 1 的结点个数，并求出在等概率情况下进行成功搜索时的平均搜索长度。度为 1 的结点个数：平均搜索长度：19. 已知一个有序表(15,26,34,39,45,56,58,63,74,76,83,94)
7、顺序存储于一维数组 a12中，根据折半搜索过程填写成功搜索下表中所给元素 34, 56, 58, 63, 94 时的比较次数。3456586394元素比较次数20. 假定一个线性序列为 (38,52,25,74,68,16,30,54,90,72)，根据此线性序列中元素的排列次序生成的一棵二叉搜索树，求出对该二叉搜索树搜索 38,74,68,30,72 等元素时的比较次数。3874683072待查元素：比较次数：21. 假定一个线性序列为 (56,27,34,95,73,16,50,62,65)，根据此线性序列中元素的排列次序生成一棵二叉搜索树，求出该二叉搜索树的高度（假定树根结点的高度为 0
8、） 、度为 2 的结点个数和叶子结点个数。高度：度为 2 的结点个数：叶子结点数：22. 假定一个线性序列为 (38,42,55,15,23,44,30,74,48，26)，根据此线性序列中元素的排列次序生成一棵二叉搜索树，求出该二叉搜索树中左子树为空的所有单支结点和右子树为空的所有单支结点，请按照结点值从小到大的次序写出。左子树为空的所有单支结点：右子树为空的所有单支结点：精品文档！欢迎下载大家下载阅读！23. 已知一棵二叉搜索树的广义表表示为：28(12(,16),49(34(30),72(63)，求出从中依次删除 72,12,49,28 结点后，得到的二叉搜索树的广义表表示。假定每次删除
9、双支结点时是用它的中序后继结点的值来取代，接着删除其中序后继结点。广义表表示：24. 假定一组记录为(40,28,16,56,50,32,30,63)，按次序插入每个结点生成一棵 AVL 树，根据插入过程填写下表，在相应位置填写所需要的调整类型：“左单旋转“、“右单旋转“、“先左后右双旋转“、“先右后左双旋转“，若不需要旋转则填写“无“。4028165650323063数据：调整：25. 假定一组记录为(40,28,16,56,50,32,30,63,44,38)，按次序插入每个记录生成一棵 AVL 树，请回答插入时造成不平衡的结点个数。插入时造成不平衡的结点个数：26. 假定一组记录为(36
10、,75,83,54,12,67,60,40)，按次序插入每个结点生成一棵 AVL 树，请回答在插入时需进行“左单旋转“、“右单旋转“、“先左后右双旋转“、“先右后左双旋转“，“不调整“的结点数各是多少？左单旋转结点个数：右单旋转结点个数：先左后右双旋转结点个数：先右后左双旋转结点个数：不调整结点个数：27. 假定一组记录为(38,42,55,15,23,44,30,74,48,26)，按次序插入每个结点生成一棵 AVL 树，给出最后得到的 AVL 树中度为2、度为 1 和度为 0 的结点个数。度为 2 的结点个数：度为 1 的结点个数：度为 0 的结点个数：28. 已知图 G=(V,E)，其中
11、 V=a,b,c,d,e，E=，请写出各结点的出度和入度。 结点 a b c d e 出度入度29. 已知图 G=(V,E)，其中 V=a,b,c,d,e，E=，请问该图的邻接表中，每个顶点单链表各有多少边结点。顶点： a b c d e边结点数：30. 已知一个图的顶点集 V 和边集 G 分别为：V=1,2,3,4,5,6;E=,6,5;假定该图采用邻接表表示，每个顶点邻接表中的边结点都是按照终点序号（即数值域的值）从小到大的次序链接的，试写出：(1) 从顶点 1 出发进行深度优先搜索所得到的顶点序列；(2) 从顶点 1 出发进行广度优先搜索所得到的顶点序列。答（1）：（2）：31. 已知一
12、个图的顶点集 V 和边集 G 分别为：V=1,2,3,4,5,6;E=,6,5;假定该图采用邻接表表示，每个顶点邻接表中的边结点都是按照终点序号（即数值域的值）从大到小的次序链接的，试按照遍历算法写出：(1) 从顶点 1 出发进行深度优先搜索所得到的顶点序列；(2) 从顶点 1 出发进行广度优先搜索所得到的顶点序列。答（1）：（2）：32. 已知一个图的顶点集 V 和边集 G 分别为：V=1,2,3,4,5,6;E=,6,5;假定该图采用邻接矩阵表表示，试按照遍历算法写出：(1) 从顶点 2 出发进行深度优先搜索所得到的顶点序列；(2) 从顶点 2 出发进行广度优先搜索所得到的顶点序列。答（1
13、）：（2）：33. 已知一个图的顶点集 V 和边集 G 分别为：V=1,2,3,4,5,6;E=(1,2),(1,3),(2,4),(2,5),(3,4),(4,5),(4,6),(5,1),(5,3),(6,5);假定该图采用邻接矩阵表表示，试按照遍历算法写出：(1) 从顶点 1 出发进行深度优先搜索所得到的顶点序列；(2) 从顶点 1 出发进行广度优先搜索所得到的顶点序列。答（1）：（2）：34. 已知一个图的顶点集 V 和边集 G 分别为：V=1,2,3,4,5,6;E=(1,2),(1,3),(2,4),(2,5),(3,4),(4,5),(4,6),(5,1),(5,3),(6,5)
14、;假定该图采用邻接表表示，并且每个顶点邻接表中的边结点都是按照终点序号（即数值域的值）从大到小的次序链接的，试按照遍历算法写出：(1) 从顶点 1 出发进行深度优先搜索所得到的顶点序列；(2) 从顶点 1 出发进行广度优先搜索所得到的顶点序列。答（1）：（2）：35. 已知一个带权图的顶点集 V 和边集 G 分别为：V=0,1,2,3,4,5;E=(0,1)19,(0,2)21,(0,3)14,(1,2)16,(1,5)5,(2,3)26, (2,4)11,(3,4)18,(4,5)6;则求出该图的最小生成树的权。最小生成树的权：36. 已知一个带权图的顶点集 V 和边集 G 分别为：V=0,
15、1,2,3,4,5;E=(0,1)19,(0,2)21,(0,3)14,(1,2)16,(1,5)5,(2,3)26, (2,4)11,(3,4)18,(4,5)6;精品文档！欢迎下载大家下载阅读！试根据普里姆算法从顶点 0 出发得到最小生成树，在下面填写依次得到的各条边。_, _, _, _, _。37. 已知一个带权图的顶点集 V 和边集 G 分别为：V=0,1,2,3,4,5;E=(0,1)19,(0,2)21,(0,3)14,(1,2)16,(1,5)5,(2,3)26, (2,4)11,(3,4)18,(4,5)6;试根据克鲁斯卡尔算法求出最小生成树，在下面填写依次得到的各条边。_, _, _, _, _。38. 已知一个带权图的顶点集 V 和边集 G 分别为：V=0,1,2,3,4,5,6;E=(0,1)19,(0,2)10,(0,3)14,(1,2)6,(
