1、计算机四级-数据结构与算法及答案解析(总分：60.00，做题时间：90 分钟)一、B选择题/B(总题数：44，分数：45.00)1.在有向图 G的拓扑序列中，如果顶点 Vi在 Vi之前，则在下列情况中一定不可能出现的是( )。（分数：1.00）A.G中有弧V i，V iB.G中没有弧V i，V( iC.G中有一条从 Vi到 Vi的路径D.G中有一条从 Vi到 Vi的路径2.如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则可采用的方法是 ( )。（分数：1.00）A.分块法B.顺序法C.二分法D.散列法3.一个序列中有若干个元素，若只想得到其中第 i个元素之前的部分排序，最好采用什么
2、排序方法?( )（分数：1.00）A.起泡排序B.堆排序C.插入排序D.归并排序4.栈 S最多能容纳 4个元素。现有 6个元素按 1，2，3，4，5，6 的顺序进栈，则下列哪一个序列是可能的出栈序列?( )（分数：1.00）A.5，4，3，2，1，6B.2，3，5，6，1，4C.3，2，5，4，1，6D.1，4，6，5，2，35.若待排序序列已基本有序，要使它完全有序，从关键码比较次数和移动次数考虑，应当使用的排序方法是( )。（分数：1.00）A.归并排序B.直接插入排序C.直接选择排序D.快速排序6.下列排序方法中，哪一种方法的比较次数与记录的初始排列状态无关?( )（分数：1.00）A.
3、直接插入排序B.起泡排序C.快速排序D.直接选择排序7.下面关于数据结构的叙述中，正确的叙述是( )。（分数：1.00）A.顺序存储方式的优点是存储密度大，且插入、删除运算效率高B.链表中的每一个结点都包含恰好一个指针C.包含 n个结点的二叉排序树的最大检索长度为 log2nD.将一棵树转换为二叉树后，根结点没有右子树8.用快速排序法对包含 n个关键字的序列进行排序，最坏情况下的执行时间为( )。（分数：1.00）A.O(nlog2B.O(n2)C.O(log2D.O(9.An algorithm to solve a given problem has time complexity T(n
4、) = nlog2n-(n-1) Given that the algorithm takes 0.8 second for a problem in which n=1024, how long should it take for a problem in which n=4096? ( )（分数：1.00）A.39 secondsB.0.8 secondsC.3.9 minutesD.3.9 seconds10.二叉树的先序遍历和中序遍历如下； 先序遍历：EFHIGJK 中序遍历：HFIEJKG 该二叉树根结点的右子树由哪些结点组成?( )（分数：1.00）A.FHIB.EFHC.JKG
5、D.EJKG11.对无向图 G(下图)，若从顶点 V1开始，按深度优先搜索法进行遍历，则可能的访问顺序是( )。（分数：1.00）A.V1V2V3V4V5V6V7V8B.V1V2V3V5V4V6V7V8C.V1V2V6V3V4V7V8V5D.V1V2V6V3V5V4V7V812.对包含 n个元素的散列表进行检索，平均检索长度为( )。（分数：1.00）A.不直接依赖于 nB.O(n2)C.O(D.O(log213.下面关于有向图的叙述中，哪个(些)是正确的?( ) 求有向图结点的拓扑序列，其结果必定是惟一的 求两个指向结点间的最短路径，其结果必定是惟一的 求事件结点网络的关键路径，其结果必定是
6、惟一的（分数：1.00）A.只有B.和C.都正确D.都不正确14.用堆排序方法，最坏情况下，所需时间为( )。（分数：1.00）A.O(B.O(n2)C.O(log2D.O(n log215.以下关键码序列用快速排序法进行排序，速度最慢的是( )。（分数：1.00）A.23，27，7，19，11，25，32B.23，11，19，32，27，25，7C.7，11，19，23，25，27，32D.27，25，32，19，23，7，1116.设有 100个结点，用二分法查找时，最大比较次数是( )。（分数：1.00）A.25B.50C.10D.717.一个 nn的带状矩阵 A=aij如下 （分数：1
7、.00）A.i+2j-1B.2i+j-2C.3i-j+1D.i+j+218.在待排序文件已基本有序的前提下，下述排序方法中效率最高的是( )。（分数：1.00）A.直接插入排序B.堆排序C.二路归并排序D.起泡排序19.设树 T的度为 4，其中度为 1、2、3 和 4的结点的个数分别为 4、2、1、1，则 T中叶子结点的个数是( )。（分数：1.00）A.6B.7C.8D.920.设仅包含根结点的二叉树的高度为 0，则高度为 k的二叉树的最大结点数为( )。（分数：1.00）A.2k+1B.2k+1-1C.2k+1+1D.2k+121.设有向图 G有 n个顶点，它的邻接矩阵为 A，G 中第 i
8、个顶点 Vi的度为( )。（分数：1.00）A.B.C.D.22.设散列表的存储空间大小为 19，所用散列函数为 H(key)key mod 19，用开地址线性探查法解决碰撞。散列表的当前状态如下： （分数：1.00）A.0B.11C.15D.1723.A hash table with hash function is shown below.H1(k)=k mod 13 （分数：1.00）A.1B.2C.3D.424.The sorting method described by the following code is called( ). FOR i:=1 TO n1 do BEGI
9、N k: =i; FOR j: =i+1 TO n DO IF AjAK THEN k:=j; IF ki THEN BEGIN x:=Ak; Ak: = Ai; Ai:=x END END;（分数：1.00）A.insertion sortB.selection sortC.radix sortD.merge sort25.图的广度优先周游类似于树的( )。（分数：1.00）A.先序遍历B.中序遍历C.按层遍历D.后序遍历26.The figure below Shows a record used for recording information about a named event.
10、 Which of the following statement is incorrect? ( ) VAR r: RECORD event: ARRAY1 10 of Char; place: ARRAY1 20 of RECORD plname: ARRAY1 15of Char; date: ARRAY1 5 of RECORD mo: 1 12; day: 131; year: Integer END END END;（分数：1.00）A.This is a onedimensional array of records, also called a tableB.The event
11、 can occur in up to 20 places and on up to 5 different dates in each placeC.This is so called record of arraysD.A reference to place, date, mo will access the month of the jth occurrence, in the ith place, of the event named in event27.用链接方式存储的队列，在进行删除运算时，下面操作正确的是( )。（分数：1.00）A.仅修改头指针B.仅修改尾指针C.头、尾指针
12、都要修改D.头、尾指针可能都要修改28.对线性表进行二分法查找，其前提条件是( )。（分数：1.00）A.线性表以顺序方式存储，并且按关键码值排好序B.线性表以顺序方式存储，并且按关键码值的检索频率排好序C.线性表以链接方式存储，并且按关键码值排好序D.线性表以链接方式存储，并且按关键码值的检索频率排好序29.下列关于二叉树周游的叙述中，正确的是( )。（分数：1.00）A.若一个结点是某二叉树的后序最后一个结点，则它必是该二叉树的根结点B.若一个结点是某二叉树的前序最后一个结点，则它必是该二叉树的中序最后一个结点C.若一个结点是某二叉树的中序最后一个结点，则它必是该二叉树的前序最后一个结点D
13、.若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序最后一个结点30.对关键码集合 K=53，30，37，12，45，24，96，从空二叉树开始逐个插入每个关键码，建立与集合K相对应的二叉排序树，若希望得到最佳二叉排序树，应选择下列( )输入序列。（分数：1.00）A.45，24，53，12，37，96，30B.30，24，12，37，45，96，53C.12，24，30，37，45，53，96D.37，24，12，30，53，45，9631.有关二叉树的下列说法正确的是( )。（分数：1.00）A.二叉树的度为 2B.一棵二叉树的度可以小于 2C.二叉树中任何一个结点的度都为 2
14、D.任何一棵二叉树中至少有一个结点的度为 232.若二叉树前序周游访问结点顺序为 ABCDEFG，中序周游访问结点顺序为 CBDAFGE，则其后序周游访问结点顺序为( )。（分数：1.00）A.CDBAGFEB.CDBGFEAC.CDBFAGED.CDGFEAB33.在二叉树结点的先序序列、中序序列、后序序列中，所有叶子结点的先后顺序( )。（分数：1.00）A.完全相同B.都不相同C.先序和中序相同，而与后序不同D.中序和后序相同，而与先序不同34.二叉排序树的平均检索长度为( )。（分数：1.00）A.O(B.O(n2)C.O(log2D.O(nlog235.有向图 G(下图)的结点可以排
15、成( )个不同的拓扑序列。 （分数：1.00）A.3B.5C.7D.936.When the adjacency list method is used to store a graph，Which of the statements is(are) true?( ) The space required depends on the number of vertices The space required depends on the number of edges（分数：1.00）A.andB. onlyC.onlyD.None试题 8、9 基于下面的叙述：现有关键码值分别为 11、23
16、、31、54 的 4个结点，按所有可能的插入顺序去构造二叉排序树。（分数：2.00）(1).能构造出( )种不同的二叉排序树。（分数：1.00）A.20B.14C.16D.8(2).这些二叉排序树中有( )棵是最佳二叉排序树。（分数：1.00）A.6B.5C.4D.337.以下( )不是队列的基本运算。（分数：1.00）A.从队尾插入一个新元素B.从队列中删除第 i个元素C.判断一个队列是否为空D.读取队头元素的值38.下面序列是堆的是( )。（分数：1.00）A.97，56，38，66，23，42，12B.23，86，48，?3，35，39，42C.05，56，20，23，40，38，29D
17、.05，23，16，68，94，72，71，7339.下面的二叉树，( )是完全二叉树。 （分数：1.00）A.B.C.D.40.下面哪种情况用直接插入排序方法进行由小到大排序，元素比较次数最少?( )（分数：1.00）A.元素的关键码值按由小到大排列B.元素的关键码值按由大到小排列C.部分元素按由小到大排列D.元素任意排放41.对以下序列22，86，19，49，12，30，65，35，18进行排序，排序过程如下： (1) 22，86，19，49，12，30，65，35，18 (2) 18，12，19，22，49，30，65，35，86 (3) 12，18，19，22，35，30，49，65，
18、86 (4) 12，18，19，22，30，35，49，65，86 则可以认为使用了( )排序方法。（分数：1.00）A.选择排序B.起泡排序C.快速排序D.插入排序42.设栈 S和队列 Q的初始状态为空，元素 e1、e 2、e 3、e 4、e 5和 e6依次通过栈 S，一个元素出栈后即进入队列 Q，若 6个元素出队的顺序是 e2、e 4、e 3、e 6、e 5、e 1，则栈 S的容量至少应该是( )。（分数：1.00）A.3B.4C.5D.243.如下图 G，它的拓扑序列是( )。 （分数：1.00）A.a，c，b，dB.a，d，b，cC.a，b，d，cD.b，a，d，c二、B论述题/B(总
19、题数：3，分数：15.00)44.散列表是一种重要的存储方式，在散列表里可快速进行检索。 (1)散列表的基本思想是什么? (2)常用的散列函数有哪些，请举例说明(至少三个)。 (3)怎样用拉链法和开地址法处理碰撞?（分数：5.00）_45.(1)试说明给定一棵二叉树结点的后序序列和中序序列，则此二叉树可构造出来。 (2)一棵二叉树的中序序列为 BFDGAEHC，后序序列为 FGDBHECA，构造出此二叉树。（分数：5.00）_46.要在 n个居民点之间铺设煤气管道。工人们面临如下问题： (1)设计一种付出经济代价最小的解决问题的方案。 (2)给出解决该问题的具体方法。 (3)图 G是一个居民点
20、的煤气管道铺设代价网，给出它的经济代价最小的图示。 （分数：5.00）_计算机四级-数据结构与算法答案解析(总分：60.00，做题时间：90 分钟)一、B选择题/B(总题数：44，分数：45.00)1.在有向图 G的拓扑序列中，如果顶点 Vi在 Vi之前，则在下列情况中一定不可能出现的是( )。（分数：1.00）A.G中有弧V i，V iB.G中没有弧V i，V( iC.G中有一条从 Vi到 Vi的路径 D.G中有一条从 Vi到 Vi的路径解析：2.如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则可采用的方法是 ( )。（分数：1.00）A.分块法 B.顺序法C.二分法D.散列法解
21、析：3.一个序列中有若干个元素，若只想得到其中第 i个元素之前的部分排序，最好采用什么排序方法?( )（分数：1.00）A.起泡排序B.堆排序 C.插入排序D.归并排序解析：4.栈 S最多能容纳 4个元素。现有 6个元素按 1，2，3，4，5，6 的顺序进栈，则下列哪一个序列是可能的出栈序列?( )（分数：1.00）A.5，4，3，2，1，6B.2，3，5，6，1，4C.3，2，5，4，1，6 D.1，4，6，5，2，3解析：5.若待排序序列已基本有序，要使它完全有序，从关键码比较次数和移动次数考虑，应当使用的排序方法是( )。（分数：1.00）A.归并排序B.直接插入排序C.直接选择排序 D
22、.快速排序解析：6.下列排序方法中，哪一种方法的比较次数与记录的初始排列状态无关?( )（分数：1.00）A.直接插入排序B.起泡排序C.快速排序 D.直接选择排序解析：7.下面关于数据结构的叙述中，正确的叙述是( )。（分数：1.00）A.顺序存储方式的优点是存储密度大，且插入、删除运算效率高B.链表中的每一个结点都包含恰好一个指针C.包含 n个结点的二叉排序树的最大检索长度为 log2nD.将一棵树转换为二叉树后，根结点没有右子树 解析：8.用快速排序法对包含 n个关键字的序列进行排序，最坏情况下的执行时间为( )。（分数：1.00）A.O(nlog2B.O(n2) C.O(log2D.O
23、(解析：9.An algorithm to solve a given problem has time complexity T(n) = nlog2n-(n-1) Given that the algorithm takes 0.8 second for a problem in which n=1024, how long should it take for a problem in which n=4096? ( )（分数：1.00）A.39 secondsB.0.8 secondsC.3.9 minutesD.3.9 seconds 解析：10.二叉树的先序遍历和中序遍历如下； 先
24、序遍历：EFHIGJK 中序遍历：HFIEJKG 该二叉树根结点的右子树由哪些结点组成?( )（分数：1.00）A.FHIB.EFHC.JKG D.EJKG解析：11.对无向图 G(下图)，若从顶点 V1开始，按深度优先搜索法进行遍历，则可能的访问顺序是( )。（分数：1.00）A.V1V2V3V4V5V6V7V8B.V1V2V3V5V4V6V7V8 C.V1V2V6V3V4V7V8V5D.V1V2V6V3V5V4V7V8解析：12.对包含 n个元素的散列表进行检索，平均检索长度为( )。（分数：1.00）A.不直接依赖于 n B.O(n2)C.O(D.O(log2解析：13.下面关于有向图的
25、叙述中，哪个(些)是正确的?( ) 求有向图结点的拓扑序列，其结果必定是惟一的 求两个指向结点间的最短路径，其结果必定是惟一的 求事件结点网络的关键路径，其结果必定是惟一的（分数：1.00）A.只有B.和C.都正确D.都不正确 解析：14.用堆排序方法，最坏情况下，所需时间为( )。（分数：1.00）A.O(B.O(n2)C.O(log2D.O(n log2 解析：15.以下关键码序列用快速排序法进行排序，速度最慢的是( )。（分数：1.00）A.23，27，7，19，11，25，32B.23，11，19，32，27，25，7C.7，11，19，23，25，27，32 D.27，25，32，1
26、9，23，7，11解析：16.设有 100个结点，用二分法查找时，最大比较次数是( )。（分数：1.00）A.25B.50C.10D.7 解析：17.一个 nn的带状矩阵 A=aij如下 （分数：1.00）A.i+2j-1B.2i+j-2 C.3i-j+1D.i+j+2解析：18.在待排序文件已基本有序的前提下，下述排序方法中效率最高的是( )。（分数：1.00）A.直接插入排序 B.堆排序C.二路归并排序D.起泡排序解析：19.设树 T的度为 4，其中度为 1、2、3 和 4的结点的个数分别为 4、2、1、1，则 T中叶子结点的个数是( )。（分数：1.00）A.6B.7C.8 D.9解析：
27、20.设仅包含根结点的二叉树的高度为 0，则高度为 k的二叉树的最大结点数为( )。（分数：1.00）A.2k+1B.2k+1-1 C.2k+1+1D.2k+1解析：21.设有向图 G有 n个顶点，它的邻接矩阵为 A，G 中第 i个顶点 Vi的度为( )。（分数：1.00）A.B.C. D.解析：22.设散列表的存储空间大小为 19，所用散列函数为 H(key)key mod 19，用开地址线性探查法解决碰撞。散列表的当前状态如下： （分数：1.00）A.0 B.11C.15D.17解析：23.A hash table with hash function is shown below.H1(
28、k)=k mod 13 （分数：1.00）A.1 B.2C.3D.4解析：24.The sorting method described by the following code is called( ). FOR i:=1 TO n1 do BEGIN k: =i; FOR j: =i+1 TO n DO IF AjAK THEN k:=j; IF ki THEN BEGIN x:=Ak; Ak: = Ai; Ai:=x END END;（分数：1.00）A.insertion sortB.selection sortC.radix sortD.merge sort 解析：25.图的广度优
29、先周游类似于树的( )。（分数：1.00）A.先序遍历B.中序遍历C.按层遍历 D.后序遍历解析：26.The figure below Shows a record used for recording information about a named event. Which of the following statement is incorrect? ( ) VAR r: RECORD event: ARRAY1 10 of Char; place: ARRAY1 20 of RECORD plname: ARRAY1 15of Char; date: ARRAY1 5 of RE
30、CORD mo: 1 12; day: 131; year: Integer END END END;（分数：1.00）A.This is a onedimensional array of records, also called a table B.The event can occur in up to 20 places and on up to 5 different dates in each placeC.This is so called record of arraysD.A reference to place, date, mo will access the month
31、 of the jth occurrence, in the ith place, of the event named in event解析：27.用链接方式存储的队列，在进行删除运算时，下面操作正确的是( )。（分数：1.00）A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改 解析：28.对线性表进行二分法查找，其前提条件是( )。（分数：1.00）A.线性表以顺序方式存储，并且按关键码值排好序 B.线性表以顺序方式存储，并且按关键码值的检索频率排好序C.线性表以链接方式存储，并且按关键码值排好序D.线性表以链接方式存储，并且按关键码值的检索频率排好序解析：
32、29.下列关于二叉树周游的叙述中，正确的是( )。（分数：1.00）A.若一个结点是某二叉树的后序最后一个结点，则它必是该二叉树的根结点 B.若一个结点是某二叉树的前序最后一个结点，则它必是该二叉树的中序最后一个结点C.若一个结点是某二叉树的中序最后一个结点，则它必是该二叉树的前序最后一个结点D.若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序最后一个结点解析：30.对关键码集合 K=53，30，37，12，45，24，96，从空二叉树开始逐个插入每个关键码，建立与集合K相对应的二叉排序树，若希望得到最佳二叉排序树，应选择下列( )输入序列。（分数：1.00）A.45，24，53
33、，12，37，96，30B.30，24，12，37，45，96，53C.12，24，30，37，45，53，96D.37，24，12，30，53，45，96 解析：31.有关二叉树的下列说法正确的是( )。（分数：1.00）A.二叉树的度为 2B.一棵二叉树的度可以小于 2 C.二叉树中任何一个结点的度都为 2D.任何一棵二叉树中至少有一个结点的度为 2解析：32.若二叉树前序周游访问结点顺序为 ABCDEFG，中序周游访问结点顺序为 CBDAFGE，则其后序周游访问结点顺序为( )。（分数：1.00）A.CDBAGFEB.CDBGFEA C.CDBFAGED.CDGFEAB解析：33.在二叉
34、树结点的先序序列、中序序列、后序序列中，所有叶子结点的先后顺序( )。（分数：1.00）A.完全相同 B.都不相同C.先序和中序相同，而与后序不同D.中序和后序相同，而与先序不同解析：34.二叉排序树的平均检索长度为( )。（分数：1.00）A.O(B.O(n2)C.O(log2 D.O(nlog2解析：35.有向图 G(下图)的结点可以排成( )个不同的拓扑序列。 （分数：1.00）A.3B.5C.7 D.9解析：36.When the adjacency list method is used to store a graph，Which of the statements is(are)
35、 true?( ) The space required depends on the number of vertices The space required depends on the number of edges（分数：1.00）A.and B. onlyC.onlyD.None解析：试题 8、9 基于下面的叙述：现有关键码值分别为 11、23、31、54 的 4个结点，按所有可能的插入顺序去构造二叉排序树。（分数：2.00）(1).能构造出( )种不同的二叉排序树。（分数：1.00）A.20B.14 C.16D.8解析：(2).这些二叉排序树中有( )棵是最佳二叉排序树。（分数：
36、1.00）A.6 B.5C.4D.3解析：37.以下( )不是队列的基本运算。（分数：1.00）A.从队尾插入一个新元素B.从队列中删除第 i个元素 C.判断一个队列是否为空D.读取队头元素的值解析：38.下面序列是堆的是( )。（分数：1.00）A.97，56，38，66，23，42，12B.23，86，48，?3，35，39，42C.05，56，20，23，40，38，29D.05，23，16，68，94，72，71，73 解析：39.下面的二叉树，( )是完全二叉树。 （分数：1.00）A.B. C.D.解析：40.下面哪种情况用直接插入排序方法进行由小到大排序，元素比较次数最少?( )
37、（分数：1.00）A.元素的关键码值按由小到大排列 B.元素的关键码值按由大到小排列C.部分元素按由小到大排列D.元素任意排放解析：41.对以下序列22，86，19，49，12，30，65，35，18进行排序，排序过程如下： (1) 22，86，19，49，12，30，65，35，18 (2) 18，12，19，22，49，30，65，35，86 (3) 12，18，19，22，35，30，49，65，86 (4) 12，18，19，22，30，35，49，65，86 则可以认为使用了( )排序方法。（分数：1.00）A.选择排序B.起泡排序C.快速排序 D.插入排序解析：42.设栈 S和队列
38、 Q的初始状态为空，元素 e1、e 2、e 3、e 4、e 5和 e6依次通过栈 S，一个元素出栈后即进入队列 Q，若 6个元素出队的顺序是 e2、e 4、e 3、e 6、e 5、e 1，则栈 S的容量至少应该是( )。（分数：1.00）A.3 B.4C.5D.2解析：43.如下图 G，它的拓扑序列是( )。 （分数：1.00）A.a，c，b，dB.a，d，b，cC.a，b，d，c D.b，a，d，c解析：二、B论述题/B(总题数：3，分数：15.00)44.散列表是一种重要的存储方式，在散列表里可快速进行检索。 (1)散列表的基本思想是什么? (2)常用的散列函数有哪些，请举例说明(至少三个
39、)。 (3)怎样用拉链法和开地址法处理碰撞?（分数：5.00）_正确答案：()解析：(1)散列表的基本思想是；由结点的关键码值决定结点的存储地址。即以关键码值 k为自变量，通过一定的函数关系 H(称为散列函数)，计算出对应的函数值 H(k)来，把这个值解释为结点的存储地址，将结点存入该地址中去，检索时，按同样的方法计算出结点的地址，然后到相应的地址中取结点即可。(2)常用的散列函数有：除余法：即选择一个适当的正整数 p(通常选 p为小散列表存储区域大小的最大素数)，用 p去除关键码值，取其余数作为地址。折叠法：即将关键码值从某些地方断开，分为几段，折叠相加，作为地址。中平方法：即将关键码值平方
40、，取中间的几位数作为地址。(3)用拉链法处理碰撞就是给散列表的每个结点增加一个 link字段，当碰撞发生时利用 link字段拉链，建立链接方式的同义词子表。每个同义词子表的第一个元素都在散列表基本区域中，同义词子表的其他元素的存储又有两种解决方法，一种是建立溢出区，存放各同义词子表的其他元素，另一种是不建立溢出区，同义词子表的其他元素就存放在散列表中没有占用的单元中，用开地址法处理碰撞就是当碰撞发生时形成一个探查序列，沿着这个序列逐个地址探查，直到找到一个未被占用的地址，将发生碰撞的关键码值存入该地址中。最简单的探查序列是线性探查，即若发生碰撞的地址为 d，则探查的地址序列为；d+1，d+2，
41、m-1，0，1，d-1其中，m 是散列表存储区域的大小，另一种效果更好的探查序列是再散列探查，即用第二个散列函数 H2来确定探查序列，若发生碰撞的地址为 d，则探查的地址序列为：(d+H2(k)mod m，(d+2H 2(k)mod m，(d+3H 2(k)mod m，45.(1)试说明给定一棵二叉树结点的后序序列和中序序列，则此二叉树可构造出来。 (2)一棵二叉树的中序序列为 BFDGAEHC，后序序列为 FGDBHECA，构造出此二叉树。（分数：5.00）_正确答案：()解析：根据二叉树的定义，一棵二叉树通常由一棵左子树和一棵右子树及一个根结点组成，假设二叉树T，它的左子树和右子树分别为
42、T1和 T2，已知-X 树 T的后序序列和中序序列，根据后序序列定义，可知二叉树 T的根结点必定为其后序序列的最后一个结点，由此我们得到二叉树 T的根结点；而根据中序序列的定义，二叉树 T必定具有这样的性质，即其根结点左端的结点序列必为其左子树 T1所包含的所有结点的中序序列，根结点右端的结点序列必为其右子树 T2所包含的所有结点的中序序列。这样二叉树 T左右子树所包含的结点及中序序列也知道了。接下来，我们只要证明二叉树 T的左子树 T1可构造出来，其右子树 T2也可构造出来。同理，对于二叉树 T1，已知它的中序序列，从二叉树 T的后序序列中也可得出它的后序序列，因此，可得出了 I的根结点及
43、T1的左子树 T11和右子树 T12的中序序列，很明显，就这样一直下去，直到把左子树 T1的所有结点分析完，此时必可构造出二叉树 T1。同理，右子树 T2也可构造出来。因此，知道二叉树 T的根结点和它的左右子树，二叉树 T也就构造出来了。46.要在 n个居民点之间铺设煤气管道。工人们面临如下问题： (1)设计一种付出经济代价最小的解决问题的方案。 (2)给出解决该问题的具体方法。 (3)图 G是一个居民点的煤气管道铺设代价网，给出它的经济代价最小的图示。 （分数：5.00）_正确答案：()解析：每个居民点与其余 n-1个居民点之间都可能铺设煤气管道，因此，在 n个居民点之间，最多可能铺设 n(
44、n-1)/2条煤气管道，而连接 n个居民点的煤气管道最少需要 n-1条。也就是说，只需要 n-1条管道就可以把 n个居民点间的煤气管道连通，而要代价最小，这就是求图中网的最小生成树问题，即把居民点看成图的顶点，把居民点之间的煤气管道看作边，而把铺设管道的代价当作权付给相应的边，这样便构成一个带权图，即网，此网的一棵最小生成树即为代价最小的铺设管道路径。 (2)求网的最小生成树的方法为：将网中的边按其权值由小到大的次序顺序选取，若选某边后不形成回路，则将其保留为最小生成树的一条边，若选某条边后形成回路，则将其舍弃，以后不再考虑，如此依次进行，直到选够(n-1)条边即得到此网的一棵最小生成树。(注：按此法生成的最小生成树不惟一) (3)图 G的最小生成树为：
