发布时间 : 星期四 文章数据结构与算法离线作业题目及答案更新完毕开始阅读00bccabf6294dd88d0d26bc6
答：可以生成如上二叉排序树的关键字的初始排列有30种
任写5个序列如下：
（5， 4， 6，2，2，3，1） （5， 7， 6，2，2，3，1） （5， 4， 2，3，2，1，6） （5， 7， 4，2，2，3，1） （5， 7， 4，2，2，1，3）
【13，4，5】给定关键字序列（11、7、16、4、22、13、5），请回答： （1）画出依次插入到一棵空的二叉排序树后的最终二叉树（6分）； （2）画出依次把给定序列关键字插入一棵空的平衡二叉树后的结果（4分）；
【14，4，6】 假设一个文本使用的字符集为{a,b,c,d,e,f,g}, 字符的哈夫曼编码依次为{0110，10，110，111，00，0111，010}。
（1）请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应的字符； （2）若这些字符在文本中出现的频率分别为：{3,35,13,15,20,5,9}，求该哈夫曼树的带权路径长度。
【15，5，3】用公式5.6计算一下你的身份证号码的散列值是多少。
【16，5，4】设有一组关键字{29，01，13，15，56，20，87，27，69，9，10，74}，散列函数为：H(key) = key % 17，采用平方探测方法解决冲突。试在0到18的散列地址空间中对该关键字序列构造散列表。
【17，5，4】将关键字序列（7，8，30，11，18，9，14）散列存储到散列列表中，散列表的存储空间是一个下标从0开始的一个一维数组。处理冲突采用线性探测法，散列函数为：H（key）=（key×3）mod TableSize，要求装入因子为0.7。
【18，6，3】已知一个无向图的顶点集为{V0，V1，…，V7}，其邻接矩阵如下所示：
9
V0 0 1 0 1 1 0 0 0 V1 1 0 1 0 1 0 0 0 V2 0 1 0 0 0 1 0 0 V3 1 0 0 0 0 0 1 0 V4 1 1 0 0 0 0 1 0 V5 0 0 1 0 0 0 0 0 V6 0 0 0 1 1 0 0 1 V7 0 0 0 0 0 0 0 1
(1) 画出该图的图形；
(2) 给出从V0出发的深度优先遍历序和广度优先遍历序。 【19，6，3】已知有向图如右图所示，请给出该图的 （1） 每个顶点的入度和出度； （2） 邻接矩阵； （3） 邻接表； （4） 逆邻接表；
（5） 各个强连通分量。
答：（1）各顶点的入/出度如下：顶点1:3/0；顶点2:2/2； 顶点3:1/2；顶点4:1/2；顶点5:2/1；顶点6:2/3。
（2）邻接矩阵如下： 1 0 1 0 0 1 1 （3）邻接表如下： 1 ^ 2 1 3 6
1 3 4 5 6 2 0 0 1 0 0 1 3 0 0 0 1 0 0 4 0 1 0 0 0 0 5 0 0 0 1 0 1 6 0 0 1 1 0 0 4 2
10
4 3 5 6 5 1 6 1 2 5
（4）逆邻接表如下： 1 2 5 6 2 3 6 3 4 4 2 5 4 6 6 3 4
(5)有意向3个强连通分量 6 ○1 ○5 ○2 ○4 ○
○3
【20，6，3】试利用Dijkstra算法求下图在从顶点A到其它顶点的最短距离及对应的路径，写出计算过程中各步状态。
【21，6，3】给出如下图所示的具有7个结点的网G。请：
（1） 画出该网的邻接矩阵；
（2） 采用Prim算法，从4号结点开始，给出该网的最小生成树（画出Prim算法
的执行过程及最小生成树的生成示意图）。
11
1
4 3 7 2 1 6 0 5 6 2 5 1 3 5 3 2 4 4 【22，7，4】给定数组{48, 25, 6, 90, 17, 84, 62, 48, 27, 96, 49, 72, 17}，请分别用简单选择排序、直接插入排序和冒泡排序分别进行排序，写出排序过程中每一步操作后的结果，分析各自比较和交换的次数，以及排序结果是否稳定。
【23，7，4】给定数组{48, 25, 6, 90, 17, 84, 62, 48, 27, 96, 49, 72, 17}，请分别用堆排序、快速排序和归并排序分别进行排序，写出排序过程中每一步操作后的结果，分析各自比较和交换的次数，以及排序结果是否稳定。
【24，7，4】给定数组{48, 25, 6, 90, 17, 84, 62, 48, 27, 96, 49, 72, 17}，请用3种不同的增量序列分别进行希尔排序，写出排序过程中每一步操作后的结果，分析各自比较和交换的次数，以及排序结果是否稳定。
12