7.数据结构与算法考试范围题与答案

数据结构与算法考试参考题

二、填空（ 20分 ）

1.若一棵完全二叉树中含有121个结点,则该树的深度为（ 7 ）

2.若以邻接矩阵表示有向图,则邻接矩阵上第i行中非零元素的个数之和即为顶点Vi的 。

3.二叉树的遍历主要有先序遍历、后序遍历和（ 中序遍历 ）三种。 4.深度为3的完全二叉树至少有（ 4 ）个结点。

5.若图的邻接矩阵是一个对称矩阵,则该图一定是一个（ 无向图 ）

6.若某无向图G的邻接表如下图所示,试给出以顶点V3为出发点,按广度优先搜索所产生的结点序列（ V3-2V1-V4-V5 ）

V1V2V3V4V5ΛV2V1ΛV3V1V4V5ΛV4V1V3V5ΛV5V1V3V4Λ 7.在无向图中,若从顶点a到顶点b存在（ 路径 ）,则称a与b之间是连通的。 8.我们通常把队列中允许删除的一端称为（ 队头 ）

9.表头和表尾均为（ a,(b,c) ）的广义表L= （ ） 10.假定对有序表：（ 3.4.5.7.24.30.42.54.63.72.87.95 ）进行折半查找,若查找元素24（ 程序设定为向下取整 ）,需依次与（ 30.5.7.24 ）元素进行比较。 三、解答（ 50分 ）

1. 二维数组A[10.20]采用按行为主序的存储方式,每个元素占4个存储单元,若A[1.1]的存储地址为300,则请算A[10,10]的存储地址。 答： 300+（ 9*20+10 ）*

4=300+190*4=300 +760=1060

2. 已知树如右图所示：

（1）画出由该树转换得到的二叉树；

原图: 答图： AABBCDECFDEFGHIJGKHJK I （2）写出该二叉树的后序序列：

答： 后序序列为：E B K J I H G F D C A 3. 试给出如图所示的邻接矩阵和邻接表表示。 原图：

V21V281347V5V113V46 答： 邻接矩阵

?02460??000?A???80??00000???

?071100???013000???邻接表1V1223446Λ2V238Λ3V3Λ4V427311Λ5V5213Λ

4. 已知某二叉排序树10个结点的值依次为1-10,其结构如图所示,试标出该二叉排序树各结点所对应的具体值。

原图： 答图：

6593710482 1 5. 试构造下图的最小生成树,要求分步给出构造过程。 原图：

V1462V25V538V47V5 答图：

V1V1V2V3V2V322551.

V4VV5 2.

V4

VV1155VV3V3V222525653.

V4VV5 4.

V4

6. 从一个空的二叉排序树开始,依次插入关键字25.13.15.14.7.20.37试画出插入关键字后的二叉排序树,并计算查找成功时的平均查找长度。average search length平均

查找长度ASL

答： ASL=(1*1+2*2+3*3+4*1)/7=18/7

2513347153720 解题：主要思想是以第一个数为标准,将比此数小的放在左边,大的放在右边,再一一插入,通过比较,找到末端为止。如13比25小,便在左边,后15小于25,又在25左端,但是比13大,故放在了13的右边,每个数都是这样找到自己的位置的。

7.为关键字（ 17.33.31.40.48 ）构造一个长度为7的散列表,设散列函数为h(key)=key%7,用开放定址法解决冲突的探查序列是 Hi=(h(key)+(key%5+1))%7 0≤i≤6 (1)画出构造所得的散列表；

(2)求出在等概率情况下查找成功时的平均查找长度。 答：

ASL=(1+1+3+2+4)/5=11/5 H(17)=17%7=3 H(33)=33%7=5

H(31)=31%7=3 冲突

？%=（ 3+1（ 31%5+1 ） ）%7 =5%7=5 冲突 Hi=(3+2(31%5+1))%7 =(3+4)%7=0

H(40)=40%7=5 冲突 Hi=(5+1(40%5+0))%7 =6%7=6

H(48)=48%7=6 冲突 Hi=(6+1(48%5+1))%7 =(6+4)%7=3 冲突 Hi=(6+2(48%5+1))%7 =(6+8)%7=0 冲突

Hi=(6+3(48%5+1))%7 =(6+12)%7 =18%7 =4

0

1

2

3

4

5

6

31 17 48 33 40 8.…… 顶点C出发进行深度优先遍历的序列。 原图：

邻接点权值链域0A207111Λ1B011509415320Λ2C308007Λ3D120208Λ4E514115Λ5F109414Λ

答：C D A B F E 答图：

A117B9C1520FE148D

完

1.已知一棵树边的集合为{,,,,,,,,,,,,},请画出这棵树,并回答下列问题：

（ 1 ）哪个是根结点？ （ 2 ）哪些是叶子结点？ （ 3 ）哪个是结点g的双亲？ （ 4 ）哪些是结点g的祖先？ （ 5 ）哪些是结点g的孩子？ （ 6 ）哪些是结点e的孩子？

（ 7 ）哪些是结点e的兄弟？哪些是结点f的兄弟？ （ 8 ）结点b和n的层次号分别是什么？ （ 9 ）树的深度是多少？ （ 10 ）以结点c为根的子树深度是多少？ 1. 解答：

根据给定的边确定的树如图5-15所示。 其中根结点为a； 叶子结点有：d、m、n、j、k、f、l； c是结点g的双亲； a、c是结点g的祖先；

j、k是结点g的孩子； m、n是结点e的子孙； e是结点d的兄弟； g、h是结点f的兄弟；

结点b和n的层次号分别是2和5； 树的深度为5。

4. 已知用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL,写出该二叉树的先序、中序和后序遍历序列。 解答：

先序序列：ABDHIEJKCFLG 中序序列：HDIBJEKALFCG 后序序列：HIDJKEBLFGCA 数据结构：在一棵空的二叉查找树中依次插入关键字学列为54,18,66,87,36,12 请画出所得到的二叉排序树

数据结构题：二维数组A[10][20]采用列序为主方式存储,每个元素占一个存储单元并且A[0][0]的存储地址是200

则A[6][12]的地址是326。

还有这题：二维数组A[10..20][5..10]采用行序为主方式存储,每个元素占4个存储单元,并且A[10][5]的存储地址是1000,则A[18][9]的地址是1208。 答案

第一题:列序存储,则A[6][12]的地址的A[0][0]的地址加上\行序是6*20+12)

第二题:行序存储,A[18][9]=A[10][5]+(8*6+4)*4=1000+208=1208;

A[10...20][5...10]等同于A[11][6] 然后已知A[0][0]的地址为1000,求A[8][4]的地址,注意每个元素占4个存储单元了 需要乘上4

3、已知一组元素为(46、25、78、62、18、34、12、40、73),试画出按元素排列顺序输入而生成的一棵二叉排序树。 解答：得到的二叉排序树如下图所示。

462578183462124073

10、有5个元素,其进栈次序为A、B、C、D、E,在各种可能的出栈次序中,以元素C、D最先出栈(即C第一个且D第一个出栈)的次序有哪几个? 答：三个：CDEBA,CDBEA,CDBAE 4、已知一棵树的边的集合表示为：(L,N),(G,K),(G,L),(G,M),(B,E),(B,F),(D,G),(D,H),(D,I),(D,J),(A,B),(A,C),(A,D))画出这棵树,并回答下列问题：

(1)树根是哪个结点？哪些是叶子结点？哪些是非终端结点？ (2)树的度是多少？各个结点的度是多少？

(3)树的深度是多少？各个结点的层数是多少？以结点Ｇ为根的子树的深度是多少？

(4)对于结点Ｇ,它的双亲是哪个结点？它的祖先是哪些结点？它的孩子是哪些结点？ 它的子孙是哪些结点？它的兄弟和堂兄弟分别是哪些结点？

解答：(1)树的根是A,而E、F、C、H、I、J、K、M、N是叶子结点,其它为非终端结点。

(2)树的度为4。deg(A)＝3,deg(B)＝2,deg(D)＝4,deg(G)＝3,deg(L)＝1,其它各叶子结点的度均为0。

(3)树的深度为5（设根结点的深度为1）。level(A)＝1,level(B)＝2,level(C)＝2, …,level(G)＝3,…,level(K)＝4,…,level(N)＝5。

(4)D是G的双亲；A、D是G的祖先；K、L、M是G的孩子；K、L、M和N是G的子孙；H、I、 J是G的兄弟；E、F是G的堂兄弟。

7、已知一棵二叉树先序遍历结果为ABCDEFGHIJ,中序遍历的结果为CBEDAHGIJF,试画出该二叉树。

解答：由前序遍历结果可知该二叉树的根结点为Ａ。

由此及中序遍历结果可知,该二叉树在中序遍历下的左、右子树为CBED和HGIJF依此可推出前序遍历的左、右子树的结点序列为BCDE和FGHIJ

B和F又分别为左、右子树的根结点,进而又可推出以B为根结点的左、右子树,以及 以F为根结点的左、右子树。依此类推,可推出二叉树见下图：

ABFCDGEHIJ 6、己知一棵二叉树的中序序列为cbedahgijf,后序序列为cedbhjigfa,画出该二叉树的先序线索二叉树.

答：二叉树及线索二叉树。

先序序列为：abcdefghij

7、下列整数序列由选序遍历一棵二叉排序树得到:50,40,30,45,65,55,70,80.试构造一棵这样的二叉排序树。 答图： 50 4065 304555 70

80

4. 已知用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL,写出该二叉树的先序、中序和后序遍历序列。

解答：先序序列：ABDHIEJKCFLG 中序序列：HDIBJEKALFCG 后序序列：HIDJKEBLFGCA 7. 假设一棵二叉树的先序序列为EBADCFHGIKJ,中序序列为ABCDEFGHIJK,请写出该二叉树的后序遍历序列。

7. 解答：后序序列：ACDBGJKIHFE

8. 假设一棵二叉树的后序序列为DCEGBFHKJIA,中序序列为DCBGEAHFIJK,请写出该二叉树的后序遍历序列。

. 解答：先序序列：ABCDGEIHFJK 17、已知某二叉树的先序遍历结果是：A,B,D,G,C,E,H,L,I,K,M,F和J,它的中序遍历结果是：G,D,B,A,L,H, E,K,I,M,C,F和J,请画出这棵二叉树,并写出该该二叉树后序遍历的结果。答：二叉树图形表示如下：

该二叉树后序遍历的结果是：G D B L H K M I E J F C A

20、 假设通信用的报文由9个字母A、B、C、D、E、F、G、H和I组成,它们出现的频率分别是：10、20、5、15、8、2、3、7和 30。请请用这9个字母出现的频率作为权值求： （1）设计一棵哈夫曼树； （2）计算其带权路径长度WPL； （3）写出每个字符的哈夫曼编码。 答：（1）哈夫曼树如图B-4所示

（2）其带权路径长度WPL值为270。

（3）每个字符的哈夫曼编码为：A:100, B:11, C:1010, D:000, E:0010, F:10110, G:10111, H:0011, I:01 21、 请根据以下带权有向图G （1）给出从结点v1出发分别按深度优先搜索遍历G和广度优先搜索遍历G所得的结点序列； （2）给出G的一个拓扑序列； （3）给出从结点v1到结点v8的最短路径。 答：（1）深度优先遍历：v1,v2,v3,v8,v5,v7,v4,v6 广度优先遍历：v1,v2,v4,v6,v3,v5,v7,v8

（2）G的拓扑序列为：v1,v2,v4,v6,v5,v5,v3,v5,v7,v8 （3）最短路径为：v1,v2,v5,v7,v8

22、 已知无向图G描述如下：

G=（V,E） V={V1,V2,V3,V4,V5} E={（V1,V2）,（V1,V4）,（V2,V4）,（V3,V4）,（V2,V5）,（V3,V4）,（V3,V5）} （1）画出G的图示； （2）然后给出G的邻接矩阵和邻接表； （3）写出每个顶点的度。 答：（1）g1的图示和图g1的邻接表如下图所示。

(2)中序遍历：2.3.4.5.6.7.14.16.18

本文来源：https://www.bwwdw.com/article/olpr.html