发布时间 : 星期一 文章数据结构习题集与实验指导更新完毕开始阅读1112372ef5ec4afe04a1b0717fd5360cbb1a8d68
.
0 1 2 3 4 5 6 7 8 9 10 11 12
其散列函数为h(key)=key, 处理冲突的方法为双重散列法，探查序列为： hi=(h(key)+ *h1(key))%m =0,1,…，m－1 其中 h1(key)=key+1
问：对表中关键字35，20，33和48进行查找时，所需进行的比较次数各为多少？ 答：对关键字35、20、33和48进行查找的比较次数为３、２、１、１；
2．设散列表的长度m=13；散列函数为H(K)=K mod m,给定的关键码序列为
19,14,23,01,68,20,84,27,55,11,试画出用线性探查法解决冲突时所构造的散列表。并求出在等概率的情况下，这种方法的搜索成功时的平均搜索长度 和搜索不成功时的平均搜索长度。 0 1 2 3 4 5 6 7 8 9 10 11 12 搜索成功时的平均搜索长度：ASLsucc= 搜索不成功时的平均搜索长度：ASLsucc=
解答：
设散列表的长度m=13；散列函数为H(K)=K mod m，给定的关键码序列为 19,14,23,01,68,20,84,27,55,11,则有
H(19)=6，成功； H(14)=1,成功； H(23)=10,成功；
H(01)=1，冲突，=2，成功； H(68)=3,成功； H(20)=7,成功； H(84)=6，冲突，=7，冲突，=8，成功；
H(27)=1，冲突，=2，冲突，=3，冲突，=4，成功；
H(55)=3，冲突，=4，冲突，=5，成功； H(11)=11,成功。 0 1
2
3
4
5
6
7
8
9
10 11 (1) (1)
12
14 01 68 27 55 19 20 84 (1) (2) (1) (4) (3) (1) (1) (3)
23 11 在等概率的情况下，搜索成功时的平均搜索长度 ASLsucc=18/10=1.8 搜索不成功时的平均搜索长度 ASLunsucc=52/13=4
3、m = 2的平衡m路查找树是AVL树，m = 3的平衡m路查找树。它们的叶结点必须在同一层吗？
m阶B_树是平衡m路搜索树，反过来，平衡m路搜索树一定是B_树吗？为什么？
【解答】
AVL树与平衡m路查找树的叶结点可以不在同一层，B_树的叶结点必须在同一层。因此，m阶
B_树是平衡的m路搜索树，而平衡的m路搜索树不一定是B_树。
例2、对于一棵有1999999个关键码的199阶B_树，试估计其最大层数(不包括失败结点)及最小层数(不包括失败结点)。 【解答】
.
m阶B_树的最大高度为，包括失败结点所在层次。因此，总共有层（不包括失败结点层）。那么，
.
有1999999个关键码的199阶B_树的最大高度为：
?log1001000000? +1 = 4层。
最小层数为 ?logm(n + 1)? = ?log1992000000? = 3 层。 4、回答下列问题：
(1) 在向二叉排序树中插入新结点时, 新结点是否必须作为叶结点插入？ (2) 在散列法中采取链地址法来解决冲突时, 其装填因子的取值是否一定在 (3) 在散列法中采取开地址法来解决冲突时可否立刻做物理删除？为什么？ (4) 若二叉排序树中结点个数为n, 则其高度是否为 ?log2n? ？为什么？
(0, 1) 之间。
【解答】 (1) 是。
(2) 不一定。因为溢出链是分离存放的，其结点数可以多于散列地址数。 (3) 不可以。因为做物理删除会中断其它关键字的探查序列，造成查找出错。
(4) 不是。高度指从根到最远叶结点的路径条数。若根的层次号设为0，则该树的高度最小为 ?log2(n+1)?，最大为n-1。
5、设散列表为HT[0..12], 散列函数为 H (key) = key mod 13。用开地址法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。
(1) 采用线性探查法寻找下一个空位, 画出相应的散列表, 并计算等概率下查找成功的平均查找(2) 采用双散列法寻找下一个空位, 再散列函数为 RH (key) = (7*key) mod 10 + 1, 寻找下一个空
长度和查找所查找不成功的平均查找长度。
位的公式为 Hi = (Hi-1 + RH (key)) mod 13, H1 = H (key)。画出相应的散列表, 并计算等概率下查找成功的平均查找长度。 【解答】
使用散列函数 H(key) = key mod 13，有
H(12) = 12, H(23) = 10, H(20) = 7, H(15) = 2,
H(03) = 3, H(36) = 10.
5 57 6 45 7 20 8 31 9 10 11 23 36 12 12 H(45) = 6,
H(57) = 5,
H(31) = 5,
H(78) = 0,
(1) 利用线性探查法造表： 0 1 2 3 4 78 15 03 (1)
(1) (1)
(1) (1) (1) (4) (1) (2) (1)
查找成功的平均查找长度为
ASLsucc = (1 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 2 + 1) = 14
查找不成功的平均查找长度为
ASLunsucc = (2 + 1 + 3 + 2 + 1 + 5 + 4 + 3 + 2 + 1 + 5 + 4 + 3) =36
(2) 利用双散列法造表：
Hi = (Hi-1 + RH (key)) mod 13, H1 = H (key) 0 1 2 3 4 5 6 7 78 15 03 57 45 20 (1)
(1) (1)
8 31 9 36 10 11 23 12 12 (1) (1) (1) (1) (3) (5) (1)
.
查找成功的平均查找长度为
.
ASLsucc = (1 + 1 + 1 + 1 + 1 + 1 + 3 + 5 + 1 + 1) =16
第九章 排序
一、填空
1．在一个堆的顺序存储中，若一个元素的下标为i(0≤i≤n-1)，则它的左孩子元素的下标为_ 2i+1 ，右孩子元素的下标为_2i+2_。
2．在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_ O(log2n)_，整个堆排序过程的时间复杂度为_ O(nlog2n)_。
3. 快速排序在平均情况下的时间复杂度为 O(nlog2n)_，在最坏情况下的时间复杂度为_ O(n)_。 4.假定一组记录的排序码为(46,79,56,38,40,80,25,34)，则对其进行快速排序的第一次划分的结果为[40 34 25 38] 46 [80 56 79] 。
5.用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：
20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是 快速排序 。 二、解答题
1． 已知序列{ 503，87，512，61，908，170，897，275，653，462}，采用快速排序方法对该序列
作升序排序时的每一趟的结果。 答：初始：503，87，512，61，908，170，897，275，653，462
1趟：[462，87，275，61，170] 503 [897，908，653，512] 2趟：[170，87，275，61] 462，503 [897，908，653，512] 3趟：[61，87] 170 [275] 462，503 [897，908，653，512] 4趟：61 [87] 170 [275] 462，503 [897，908，653，512] 5趟：61，87，170 [275] 462，503 [897，908，653，512] 6趟：61，87，170，275，462，503 [897，908，653，512] 7趟：61，87，170，275，462，503 [512，653] 897 [908] 8趟：61，87，170，275，462，503，512 [653] 897 [908] 9趟：61，87，170，275，462，503，512，653，897 [908] 10趟：61，87，170，275，462，503，512，653，897 ，908
2. 已知序列{ 503，87，512，61，908，170，897，275，653，462}，采用堆排序方法对该序列作降序排序时的每一趟的结果。
答：初始化为极大堆：908，653，897，503，462，170，512，275，61，87
（1） 908（897，653，512，503，462，170，87，275，61）
.
2
.
（2） 908，897（653，503，512，275，462，170，87，61） （3） 908，897，653（512，503，170，275，462，61，87） （4） 908，897，653，512（503，462，170，275，87，61） （5） 908，897，653，512，503（462，275，170，61，87） （6） 908，897，653，512，503，462（275，87，170，61） （7） 908，897，653，512，503，462，275（170，87，61） （8） 908，897，653，512，503，462，275，170（87，61） （9） 908，897，653，512，503，462，275，170，87（61） （10） 908，897，653，512，503，462，275，170，87，61
3.写出下列算法的功能：
void AA（Heap&HBT，const Elem type item）
//HBT为一个小根堆 {
HBT.heap[HBT.size]=item; HBT.size++； eLemType x=item； int i=HBT.size—1； while（i！=0）{
int j=（i—1）/2； if（x>=HBT.heap[j]）break; HBT.heap[i]=HBT.heap[j]; i=j;}HBT.heap[i]=x; }
该算法的功能为：
向HBT堆中插入一个值为item的元素，使得插入后仍是一个堆。
数据结构实验指导
实验一 线性表的应用
[实验目的]：掌握线性表的逻辑结构定义、线性表的两种存储结构（顺序和链式）；
掌握顺序表和链表的定义及基本操作，运用其解决一些实际问题。
[实验题目]：
1、 请编写26个字母按特定字母值插入或删除的完整程序，可自行选用顺序存储或链表结构。 答：
.