当前位置:首页 >> 其它课程 >> 数据结构(本科)期末综合练习三(运算题)

数据结构(本科)期末综合练习三(运算题)


任何节约归根到底是时间的节约。——马克思
数据结构(本科)期末综合练习三(运算题)

  1. 对于一个n?n的矩阵A的任意矩阵元素a[i][j],按行存储时和按列存储时的地址之差是多少。(设两种存储时的开始存储地址均为LOC(0, 0),元素所占存储单元数均为d)

  2. 设有一个二维数组A[1

0][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,试以它们为叶子结点生成一棵霍夫曼树,求出该树的带权路径长度、高度、双分支结点数。
带权路径长度:
高度:
双分支结点数:

18. 一个一维数组a[10]中存储着有序表 (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)顺序存储于一维数组a[12]中,根据折半搜索过程填写成功搜索下表中所给元素34, 56, 58, 63, 94时的比较次数。

34 56 58 63 94 元素
比较次数

20. 假定一个线性序列为 (38,52,25,74,68,16,30,54,90,72),根据此线性序列中元素的排列次序生成的一棵二叉搜索树,求出对该二叉搜索树搜索38,74,68,30,72等元素时的比较次数。
38 74 68 30 72
待查元素:
比较次数:

21. 假定一个线性序列为 (56,27,34,95,73,16,50,62,65),根据此线性序列中元素的排列次序生成一棵二叉搜索树,求出该二叉搜索树的高度(假定树根结点的高度为0)、度为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结点后,得到的二叉搜索树的广义表表示。假定每次删除双支结点时是用它的中序后继结点的值来取代,接着删除其中序后继结点。

  广义表表示:

24. 假定一组记录为(40,28,16,56,50,32,30,63),按次序插入每个结点生成一棵AVL树,根据插入过程填写下表,在相应位置填写所需要的调整类型:"左单旋转"、"右单旋转"、"先左后右双旋转"、"先右后左双旋转",若不需要旋转则填写"无"。

40 28 16 56 50 32 30 63 数据:
调整:

25. 假定一组记录为(40,28,16,56,50,32,30,63,44,38),按次序插入每个记录生成一棵AVL树,请回答插入时造成不平衡的结点个数。

  插入时造成不平衡的结点个数:

26. 假定一组记录为(36,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),其中V={a,b,c,d,e},E={<a,b>,<b,a>,<c,b>,<c,d>,<d,e>,<e,a>,<e,c>},请写出各结点的出度和入度。

  结点 a b c d e
  出度
  入度

  29. 已知图G=(V,E),其中V={a,b,c,d,e},E={<a,b>,<b,a>,<c,b>,<c,d>,<d,e>,<e,a>,<e,c>},请问该图的邻接表中,每个顶点单链表各有多少边结点。

  顶点: a b c d e
  边结点数:

  30. 已知一个图的顶点集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):

  31. 已知一个图的顶点集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):

  32. 已知一个图的顶点集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) 从顶点2出发进行深度优先搜索所得到的顶点序列;
(2) 从顶点2出发进行广度优先搜索所得到的顶点序列。

  答(1):
(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)};
假定该图采用邻接表表示,并且每个顶点邻接表中的边结点都是按照终点序号(即数值域的值)从大到小的次序链接的,试按照遍历算法写出:
(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,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,(1,5)5,(2,3)26,(2,4)15,(3,4)18,
(4,5)6,(4,6)6,(5,6)12};

试根据迪克斯特拉(Dijkstra)算法求出从顶点0到其余各顶点的最短路径,在下面填写对应的路径长度。
顶点: 0 1 2 3 4 5 6
路径长度: 0

  39. 已知一个带权图的顶点集V和边集G分别为:
V={0,1,2,3,4,5,6};
E={(0,1)19,(0,2)10,(0,3)14,(1,2)6,(1,5)5,(2,3)26,(2,4)15,(3,4)18,
(4,5)6,(4,6)6,(5,6)12};

试根据迪克斯特拉(Dijkstra)算法求出从顶点0到其余各顶点的最短路径,即给出所经过的所有顶点。如顶点0到达顶点j需依次经过顶点k1和k2,则最短路径表示为0,k1,k2,j。

顶点: 0 1 2 3 4 5 6
最短路径: 0

  40. 已知一个带权图的顶点集V和边集G分别为:
V={0,1,2,3,4,5,6};
E={(0,1)19,(0,2)10,(0,3)14,(1,2)6,(1,5)5,(2,3)26,(2,4)15,(3,4)18,
(4,5)6,(4,6)6,(5,6)12};

试根据迪克斯特拉(Dijkstra)算法求出从顶点0到其余各顶点的最短路径,即给出依次求得的各顶点及路径长度(注意所求顶点的先后次序)。

顶点:
最短长度:

  41. 已知一个AOV网络的顶点集V和边集G分别为:
V={0,1,2,3,4,5,6,7};
E={<0,2>,<1,3>,<1,4>,<2,4>,<2,5>,<3,6>,<3,7>,<4,7>,<5,7>,<6,7>};
若存储它采用邻接表,并且每个顶点邻接表中的边结点都是按照终点序号(即dest域的值)从小到大的次序链接的,则按主教材中介绍的进行拓扑排序的算法,写出得到的拓扑序列(提示:先画出对应的图形,然后再运算)。

拓扑序列:

  42. 已知一个AOV网络的顶点集V和边集G分别为:
V={0,1,2,3,4,5,6,7};
E={<0,2>,<1,3>,<1,4>,<2,4>,<2,5>,<3,6>,<3,7>,<4,7>,<5,7>,<6,7>};
若存储它采用邻接表,并且每个顶点邻接表中的边结点都是按照终点序号(即dest域的值)从大到小的次序链接的,则按主教材中介绍的进行拓扑排序的算法,写出得到的拓扑序列(提示:先画出对应的图形,然后再运算)。

拓扑序列:

  43. 已知一个AOE网络的顶点集V和边集G分别为:
V={0,1,2,3,4,5};
E={<0,1>2,<0,2>15,<1,3>12,<1,4>9,<2,1>4,<2,4>11,<3,5>5,<4,5>10};
若存储它采用邻接表,则按主教材中介绍的求关键路径的方法,依次写出所有的关键活动(用边表示),并求出关键路径长度(提示:先画出对应的图形,然后再运算)。

所有关键活动:
关键路径长度

  44. 已知一个AOE网络的顶点集V和边集G分别为:
V={0,1,2,3,4,5};
E={<0,1>5,<0,2>8,<1,2>7,<1,3>10,<1,4>6,<2,4>3,<3,4>9,<3,5>15,<4,5>12};
若存储它采用邻接表,则按主教材中介绍的求关键路径的方法,依次写出所有的关键活动(用边表示),并求出关键路径长度(提示:先画出对应的图形,然后再运算)。

所有关键活动:
关键路径长度

  45. 已知数据序列为{6,45,27,23,41,5,56,64},请把它调整为最大堆并给出进行两趟堆排序后的结果(即尾部得到3个最大数)。

  最大堆:
  两趟排序结果:

46. 假设文件有4500个记录,在磁盘上每个页块可放75个记录,计算机中用于排序的内存区可容纳450个记录。试问:
(1) 可建立初始归并段的个数。
(2)每个初始归并段包含的记录数。
(3)每个初始归并段占有的页块数。
(4) 应采用归并的最大路数。
(5)每趟需要读写的页块数。

  答:(1) (2) (3) (4) (5)

47. 如果某个文件经内排序得到80个初始归并段,试问
(1) 若使用多路归并执行3趟完成排序,那么应取的归并路数至少应为多少?
(2) 如果操作系统要求一个程序同时可用的输入/输出文件的总数不超过15个,则按多路归并至少需要几趟可以完成排序?

  答(1)归并路数: (2)需要归并躺数:

48. 已知一个数据表为{512, 275, 275*, 630},请写出快速排序后的数据表。

  结果数据表:

49. 已知一个数据表为{48,25,56,32,40},请写出在进行快速排序的过程中每次划分后数据表的变化。

(0) [48 25 56 32 40]
(1)

任何节约归根到底是时间的节约。——马克思
(2)
(3)

50. 已知一个数据表为{36,25,25*,62,40,53},请写出在进行快速排序的过程中每次划分后数据表的变化。

(0) [36 25 25* 62 40 53]
(1)
(2)
(3)

51. 已知有一个四元素的数据表{75,75*,60,18}已经为最大堆,给出堆排序的过程中进行每一趟交换和调整后的数据表变化。

(0) {75 75* 60 18}
(1)
(2)
(3)

52. 已知有一个四元素的数据表{30,18,20,15}已经为最大堆,给出在堆排序过程中进行每一趟交换和调整后的数据表变化。

(0) {30 18 20 15}
(1)
(2)
(3)

53. 已知有一个数据表为{30,18,20,15,38,12,44,53,46,18*,26,86},给出进行归并排序的过程中每一趟排序后的数据表变化。

(0) [30 18 20 15 38 12 44 53 46 18* 26 86]
(1)
(2)
(3)
(4)

54. 设散列表的长度m=13;散列函数为H (K)=K mod m,给定的关键码序列为{19, 14, 23, 1, 68, 20, 84, 27, 55, 11},并假定用线性探查法解决冲突,在最后得到的散列表中,关键码55,19,20和84的存储位置各是多少?

  55,19,20,84的存储位置依次为:

55. 设散列表的长度m=13,散列函数为H(K)=K mod m,采用线性探查法解决冲突,待依次插入的关键码序列为{19, 14, 23, 01, 68, 20, 84, 27, 55, 11}。问查找68,55和84的搜索长度各是多少?。

  查找68,55,84的搜索长度:

56. 设散列表的长度m=11,散列函数为H(K)=K mod m,采用线性探查法解决冲突,被依次插入的关键码序列为{1,13,12,34,38,33,27,22}。根据构成的散列表回答:
(1) 在等概率的情况下,搜索成功时的平均搜索长度;
(2) 在等概率的情况下,搜索失败时的平均搜索长度。

  答(1)
(2)

57. 设散列表的长度m=11,散列函数为H(K)=K mod m,采用链地址法解决冲突,待依次插入的关键码序列为{1,13,12,34,38,33,27,22}。根据构成的开散列表回答:
(1) 在等概率的情况下,搜索成功时的平均搜索长度;
(2) 在等概率的情况下,搜索失败时的平均搜索长度。

  答(1)
(2)

58. 设散列表为HT[17], 待插入关键码序列为{"Jan", "Feb", "Mar", "Apr", "May", "June", "July", "Aug","Sep","Oct","Nov","Dec"},散列函数为H(key)=?i?2?,其中i是关键码第一个字母在字母表中的序号(字母'A'在字母表中的序号为1,以下类推),采用线性探查法解决冲突。根据建立的闭散列表,搜索长度大于等于3的关键码有那些?

  搜索长度大于等于3的关键码有:

59. 设散列表为HT[13],即表大小m=13,采用双散列法解决冲突。散列函数和再散列函数分别为:
H0 = Hash(key) = key % 13; 注:%是求余数运算(= mod );
Hi = ( Hi-1 + REV ( key + 1) % 11 + 1) % 13,i = 1, 2, ..., m-1。
其中,函数 REV(x)表示颠倒10进制数x的各位,如 REV(37)=73,REV(7)=7等。
待依次插入的关键码序列为{2,8,31,20,19,18,53,27},请根据上述条件填列下表。





60. 设有150个表项要存储到散列表中, 要求利用线性探查法解决冲突, 同时要求找到所需表项的平均比较次数不超过2次。试问散列表需要设计多大?
提示:设?是散列表的装载因子,则有

  散列表长度m至少为:

运算题参考解答
四、运算题
  1. 按行存储时与按列存储时,计算A[i][j]地址的公式分别为
  LOC( i, j ) = LOC(0, 0) + ( i*n + j ) * d
  及LOC'( i, j ) = LOC(0, 0) + ( j*n + i) * d
  两者相减,得
  LOC(i,j) - LOC'(i,j) = LOC(0,0)+(i*n+j)*d-LOC(0,0)-(j*n+i)*d
    =(i-j)*(n-1)*d //2分

  2. 按行存储时,计算A[i][j]地址的公式为
  LOC( i, j ) = LOC(0, 0) + ( i*n + j ) * d
  其中首地址LOC(0, 0) = 200, 每个数组元素的存储占用数d = 1, 二维数组的列数n = 20,根据题意,元素A[6][2]的存储地址为
  LOC(6, 2) = 200 + (6*20 + 2)*1 = 322.

  3. 按列存储时,计算A[i][j]地址的公式为
  LOC(i, j) = LOC(0, 0) + ( j*m + i) * d
  其中首地址LOC(0, 0) = 200, 每个数组元素的存储占用数d = 1, 二维数组的行数m = 10,则数组元素A[6][2]的存储地址为
LOC(6, 2) = 200 + (2 * 10 + 6)*1 = 226。

  4. 根据题意,矩阵A中当元素下标I与J满足I≥J时,
任意元素A[I][J]在一维数组B中的存放位置为
I * (I + 1) / 2 + J,
因此,A[8][5]在数组B中位置为
8 * (8 + 1) / 2 + 5 = 41。
  
  5. 根据题意,矩阵A中当元素下标I与J满足I≤J时,任意元素A[I][J]在一维数组B中的存放位置为
(2 * n - I - 1) * I / 2 + J。

任何节约归根到底是时间的节约。——马克思
  但当I>J时,需要计算其对称元素A[J][I]在B中的存放位置
(2 *n - J - 1) * J / 2 + I,
因此,A[8][5]在数组B中对称元素A[J][I]的位置为
(2 * 10 - 5 - 1) * 5 / 2 + 8 = 43。

  6. 根据二维数组地址计算公式:
  LOC(i, j) = LOC(0, 0) + (i * n + j) * d
  根据题意,LOC(0, 0) = 644, LOC(2, 2) = 676, d = 1,有
676 = 644 + (2 * n + 2)
  解得n = 15。代入LOC(i, j) = LOC(0, 0) + (i * n + j) * d,得
  LOC(4, 4) = 644 + 4 * 15 + 4 = 708

7. 对于二维数组,若第一、第二维的元素个数为m和n,每个元素所占存储字数为d,首地址为LOC(0, 0),则对于任一数组元素A[i][j],它的存储地址为:
LOC(i, j) = LOC(0, 0) + (i * n + j) * d
  根据题意,LOC(8, 4) = LOC(0, 0) + (8 * 6 + 4) * 4 = 1000 + 52 * 4 = 1208。

  8. 对于三维数组,若第一、第二、第三维的元素个数为m1、m2、m3,每个元素所占存储字数为d,首地址为LOC(0, 0, 0),则对于任一数组元素A[i][j][k],它的存储地址为:
LOC(i, j, k) = LOC(0, 0, 0) + (i * m2 * m3 + j * m3 + k) * d
  根据题意,m1 = 10, m2 = 20, m3 = 15, d = 4, LOC(0, 0, 0) = 1000,则有
LOC(8, 4, 10) = LOC(0, 0, 0) + (8 * 20 * 15 + 4 * 15 + 10) * 4
= 1000 + 2470 * 4 = 10880

  9. 中序:c,b,a,e,d,f
后序:c,b,e,f,d,a
按层:a,b,d,c,e,f

  10. 前序:A,B,D,G,C,E,F
中序:B,G,D,A,E,C,F
按层:A,B,C,D,E,F,G

  11. 先根:a,b,e,c,f,h,i,j,g,d
后根:e,b,h,i,j,f,g,c,d,a
按层:a,b,c,d,e,f,g,h,i,j

  12. 后根序列:C,B,F,E,I,J,H,G,D,A

  13. 先根序列:a,b,c,d,e,f,g,h,i,j

  14. 高度:4 //2分
    度为2的结点数:3
    度为1的结点数:3
    度为0的结点数:4

  15. 前序序列:20,8,5,15,10,18,46,30,35
    中序序列:5,8,10,15,18,20,30,35,46
    后序序列:5,10,18,15,8,35,30,46,20

  16. 叶子结点数: 5
    单分支结点数:3
    两分支结点数:2
    三分支结点数:1

  17. 带权路径长度:131
高度:4
双分支结点数:6

  18. 度为1的结点个数:3
    平均搜索长度:29/10

  19. 元素 34 56 58 63 94
比较次数 2 1 3 4 4

  20. 待查元素:38 74 68 30 72
    比较次数:1 3 4 3 5

  21. 高度:4
    度为2的结点个数:2
    叶子结点数:3

  22. 左子树为空的所有单支结点:15,23,42,44
    右子树为空的所有单支结点:30

  23. 广义表表示:30(16,63(34))

  24. 数据: 40 28 16 56 50 32 30 63
调整: 无 无 右单 无 先右后左 先右后左 无 左单

  25. 插入时造成不平衡的结点个数:4

  26. 左单旋转结点个数:1
    右单旋转结点个数:0
    先左后右双旋转结点个数:1
    先右后左双旋转结点个数:0
    不调整结点个数:6

  27. 度为2的结点个数:4
    度为1的结点个数:1
    度为0的结点个数:5

  28. 结点 a b c d e
    出度 1 1 2 1 2
    入度 2 2 1 1 1

  29. 顶点: a b c d e
    边结点数: 1 1 2 1 2

  30. (1) 1,2,4,5,3,6
    (2) 1,2,3,4,5,6

  31. (1) 1,3,4,6,5,2

任何节约归根到底是时间的节约。——马克思
(2) 1,3,2,4,5,6

  32. (1) 2,4,5,1,3,6
(2) 2,4,5,6,1,3

  33. (1) 1,2,4,3,5,6
(2) 1,2,3,5,4,6

  34. (1) 1,5,6,4,3,2
(2) 1,5,3,2,6,4

  35. 最小生成树的权:54

  36. (0,3)14,(3,4)18,(4,5)6,(5,1)5,(4,2)11

  37. (1,5)5,(4,5)6,(2,4)11,(0,4)14,(3,4)18

  38. 顶点: 0 1 2 3 4 5 6
    路径长度: 0 16 10 14 25 21 31

  39. 顶点: 0 1 2 3 4 5 6
最短路径: 0 0,2,1 0,2 0,3 0,2,4 0,2,1,5 0,2,4,6

  40. 顶点: 2 3 1 5 4 6
最短长度: 10 14 16 21 25 31

  41. 拓扑序列:1,3,6,0,2,5,4,7

  42. 拓扑序列:1,3,6,0,2,4,5,7

  43. 所有关键活动:<0,2>15,<2,1>4,<1,4>9,<4,5>10
    关键路径长度:38

  44. 所有关键活动:<0,1>5,<1,3>10,<3,4>9,<4,5>12
    关键路径长度:36

  45. 最大堆: {64,45,56,23,41,5,27,6}
    两趟排序结果:{5,41,27,23,6,45,56,64}

  46. (1)10 (2)450 (3)6 (4)5 (5)60
  答案解释:
文件有4500个记录,计算机中用于排序的内存区可容纳450个记录,可建立的初始归并段有4500∕450 = 10个。每个初始归并段中有450个记录,存于450∕75 = 6个页块中。
内存区可容纳6个页块,可建立6个缓冲区,其中5个缓冲区用于输入,1个缓冲区用于输出,因此,可采用5路归并。共需做2趟归并,每趟需要读60个磁盘页块,写出60个磁盘页块。

  47. (1)归并路数:5 (2)需要归并躺数:2
  答案解释:
(1) 设归并路数为k,初始归并段个数m = 80,根据归并趟数计算公式S = ?logkm? = ?logk80? = 3得:k3≥80。由此解得k≥5,即应取的归并路数至少为5。
(2) 设多路归并的归并路数为k,需要k个输入缓冲区和1个输出缓冲区。1个缓冲区对应1个文件,有k +1 = 15,因此k = 14,可做14路归并。由S = ?logkm? = ?log1480? = 2。即至少需2趟归并可完成排序。

  48. 结果数据表:{275*, 275, 512, 630}

  49. (0) [48 25 56 32 40]
    (1) [40 25 32] 48 56
    (2) [32 25] 40 48 56
    (3) 25 32 40 48 56

  50. (0) [36 25 25* 62 40 53]
    (1) [25* 25] 36 [62 40 53] //2分
    (2) 25* 25 36 [53 40] 62 //2分
    (3) 25* 25 36 40 53 62 //2分

  51. (0) {75 75* 60 18}
    (1) {75* 18 60 75} //2分
    (2) {60 18 75* 75} //2分
    (3) {18 60 75* 75} //2分

  52. (0) {30 18 20 15}
    (1) {20 18 15 30} //2分
    (2) {18 15 20 30} //2分
    (3) {15 18 20 30} //2分

  53. (0) [30 18 20 15 38 12 44 53 46 18* 26 86]
    (1) [18 30][15 20][12 38][44 53][18* 46][26 86]
    (2) [15 18 20 30][12 38 44 53][18* 26 46 86]
    (3) [12 15 18 20 30 38 44 53][18* 26 46 86]
    (4) [12 15 18 18* 20 26 30 38 44 46 53 86]

  54. 55,19,20,84的存储位置依次为:5,6,7,8

  55. 查找68,55,84的搜索长度: 1,3,3

  56. (1) (1+1+1+3+4+1+2+8)/8=21/8
(2) (9+8+7+6+5+4+3+2+1+1+1)/11=47/11

  57. (1) (1*4+2*3+3)/8=13/8
(2) (3+4+2+1+1+3+1+1+1+1+1)/11=19/11

  58. 搜索长度大于等于3的关键码有:"June","July","Oct","Nov"

  59.






  60. 散列表长度m至少为:225
  答案说明:
已知要存储的表项数为n=150,搜索成功的平均搜索长度为ASLsucc ? 2,则有
,解得

任何节约归根到底是时间的节约。——马克思
又有,则 m ? 225






1



任何节约归根到底是时间的节约。——马克思

更多相关文档:

数据结构(本科)期末综合练习五(算法设计题)

数据结构(本科)期末综合练习五(算法设计题) 1.设有一个线性表 (e0, e1, ?...原型中的参数表给出参加运算的三个顺序表 A、B 与 C。从 C 中得到执行结 ...

《数据结构(本)(本科必修)》2016期末试题及答案

数据结构()(本科必修)》2016 期末试题及答案 一、单项选择题(每小题 2 分,共 30 分) 1.一种逻辑结构在存储时( A.只要存储数据元素间的关系 C.可...

数据结构(本科)期末综合练习(算法分析题)

数据结构(本科)期末综合练习(算法分析题) 1. 指出算法的功能并求出其时间复杂...设顺序表 SeqList 具有下列操作: int Length( ) const; //计算表长度并返回...

大学数据结构期末考试试题(有答案)

大学数据结构期末考试试题(有答案)_计算机软件及应用_IT/计算机_专业资料。大学...3. 数据结构包括数据的 逻辑结构 、数据的 存储结构 和数据的 运算 这三个...

数据结构期末考试题

2. 3. 4. 二、 运算题(每题 6 分,共 24 分) 1. 数据结构是指数据及其相互之间的___联系__。当结点之间存在 M 对 N (M:N)的联系时,称这种结构为...

数据结构期末练习题

数据结构期末练习题_工学_高等教育_教育专区。数据结构期末复习题 ...计算机处理数据的最小单位是( A.元素 3. 算法是指 ( A.计算方法 C.解决...

《数据结构与算法》期末练习题(含答案)

数据结构与算法》期末练习题(含答案)_理学_高等教育_教育专区。《数据结构与...的结构为 adjvex vertex next firstedge 下列算法计算有向图 G 中顶点 vi 的...

东华大学数据结构期末复习题

东华大学数据结构期末复习题_信息与通信_工程科技_专业资料。研究生复试也可作为复习参考第1 章 绪论一、选择题 1. 算法的计算量的大小称为计算( )。 A.效率...

数据结构期末习题答案

数据结构期末习题答案_工学_高等教育_教育专区。数据...O(n) O(n ) 3 四,应用题 1.什么是数据? 它...数据结构是一门研究在非数值计算的程序设计问题中,...

本科-数据结构(本)期末综合练习

数据结构()期末综合练习 期末综合练习一 一、单项选择题 1.数据的物理结构(...在一个链队中,假设 f 和 r 分别为队头和队尾指针,则删除一个结点的运算为...
更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com