大话备考之数据结构综合题

时间:2024-04-11 09:40:07

综合题

题型1 深度优先遍历与广度优先遍历

1.已知二维数组表示的图的邻接矩阵如下图所示。试分别给出深度优先和广度优先遍历序列,并画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。

大话备考之数据结构综合题
首先看邻接矩阵,矩阵中1代表相邻,0代表不相邻,
首先根据图表画出深度优先生成树,从1开始,找到7,7找到3,3找到4,4找到5,5找到6,(6找到1),代表主干已经找完
从6逆序向上找,6找到2,5找到10,4找到9,3找到8.故深度优先遍历序列:1,7,3,4,5,6,2,10,9,8

大话备考之数据结构综合题
广度有先则是从1开始,全部找出,1找到7和9
7找到3和10,9找到5,7,10, 7和10之前重复了,故只有5
以此规则画出广度优先生成树
广度优先遍历序列:1,7,9,3,10,5,4,8,6,2

题型2 哈夫曼树题型

一组字符{A,B,C,D,E,F,G}出现的频率分别是{9,11,5,7,8,2,3,},完成以下各题:
(1)设计最经济的编码方案。
(2)求此编码方案的平均长度、

此题应该用哈夫曼树来解决
从7个数中找到最小的两个自下而上组成哈夫曼树。
大话备考之数据结构综合题
步骤如上,最后左子树为0,右子树为1 ,容易得
A01
B10
C001
D110
E111
F0000
G0001

平均长度等于,(长度×权值)的和除以权值的和
2×9+2×11+3×5+3×7+3×8+4×2+4×3=120
120/45=8/3

题型3 哈希题型

设有一组关键字{32,13,49,24,38,21,4,12},其哈希函数为:H(key)=key % 7,采用开放地址法的线性探查法解决冲突,试在0~9的哈希地址空间中对该关键字序列构造哈希表,并求等概率下查找成功和查找失败的平均查找长度。(10分)

读题有八个关键字,0-9的哈希地址空间,
大话备考之数据结构综合题

大话备考之数据结构综合题

首先按照顺序将关键字加入哈希表中,
红色区域为查找次数,绿色为红色列的和,将元素个数比上17即为查找成功的值,即ASL=17/8;
此题mod7,共有0123456 ,7种可能性,
这7项每一项离空位的查找次数分别为,3,2,1,7,6,5,4.和为28,故不成功的ASL=28/7=4

题型4 堆排序

5.有一组关键字序列{66,89,8,123,9,44,55,37,200,127,98}:
(1)请将其调整成初始大根堆,并画出初始大根堆的树型表示。(5分)
大话备考之数据结构综合题
(2)采用堆排序实现按关键字递增排序,请画出当有1个最大的关键字已放置到最终位置时,剩余关键字构成的大根堆。(5分)

大话备考之数据结构综合题
将最终结果最大位,即200输出,200与66替换,继续调整堆,得到以上答案。

题型4 二叉树综合

有一棵二叉排序树按先序遍历得到的序列为:(12,5,2,8,6,10,16,15,18,20)。回答以下问题:
(1)画出该二叉排序树。
(2)给出该二叉排序树的中序遍历序列。
(3)求在等概率下的查找成功和不成功情况下的平均查找长度。

首先看题:
已知先序遍历,而中序遍历即为此序列的顺序排列,得中序遍历结果为(2,5,6,8,10,12,15,16,18,20)。

体干解读完成,看第一小题:

画出二叉树

先序(12,5,2,8,6,10,16,15,18,20)
中序(2,5,6,8,10,12,15,16,18,20)
第一步: 根据先序遍历可知12 为根,根据中序遍历结果从12 分为左右两部分。
第二步:看左边,左边有2,5,6,8,10,五个元素,看右边,有15,16,18,20四个元素
第三步:先序遍历中5比2 先出现,故5是2的根,以此结合顺序得到二叉树图。
大话备考之数据结构综合题

中序遍历序列

第二题求
刚才已经给出,切记,中序序列是一个顺序序列

等概率下查找成功/不成功查找长度

第三题,在二叉树中,

成功长度的求法

是,看元素所在的深度,该深度的元素个数的乘积比上总元素数

(1* 1 + 2* 2 + 3* 4 + 4* 3)/10=2.9

不成功的求法

是首先补全二叉树,如图,补全的元素的深度减一乘以元素个数,比上新填的补全元素
(3 * 5+4 * 6)/11=39/11