{
k=p->adjvex;
if(!visited[k]&&exist_path(k,j)) return 1;假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：
（1） 画出描述折半查找过程的判定树； （2） 若查找元素54，需依次与哪些元素比较 （3） 若查找元素90，需依次与哪些元素比较
（4） 假定每个元素的查找概率相等，求查找成功时的平均查找长度。
解：
（1） 先画出判定树如下（注：mid=(1+12)/2
30 5 63
3 7 42 87
4 24 54 72 95 (2) 查找元素54，需依次与30, 63, 42, 54 等元素比较； (3) 查找元素90，需依次与30, 63,87, 95, 72等元素比较；
（4） 求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次；
但最后一层未满，不能用8×4，只能用5×4=20次， 所以ASL＝1/12（17＋20）＝37/12≈
2. 设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝K MOD 16。
K为关键字，用线性探测法再散列法处理冲突，输入关键字序列： （10，24，32，17，31，30，46，47，40，63，49） 造出Hash表，试回答下列问题： （1） 画出哈希表的示意图；
（2） 若查找关键字63，需要依次与哪些关键字进行比较
=6）：
（3） 若查找关键字60，需要依次与哪些关键字比较
（4） 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。
解： （1）画表如下： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 30 31 46 47 32 17 63 49 24 40 10 （2） 查找63,首先要与H(63)=63=15号单元内容比较，即63 vs 31 ,no; 然后顺移，与46,47,32,17,63相比，一共比较了6次！
（3）查找60,首先要与H(60)=60=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。
（4） 对于黑色数据元素，各比较1次；共6次；
对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次， 所以ASL=1/11（6＋2＋3×3）＝17/11=≈
3. 在一棵空的二叉查找树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉查找树。 答：
12
7
17
2 11 16 21 4 9 13
验算方法： 用中序遍历应得到排序结果： 2,4,7,9,11,12,13,16,17，21
4. 试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。
解：注意仔细研究二叉排序树的定义。易犯的典型错误是按下述思路进行判别：“若一棵非空的二叉树其左、右子树均为二叉排序树，且左子树的根的值小于根结点的值，又根结点的值不大于右子树的根的值，则是二叉排序树”
（刘注：即不能只判断左右孩子的情况，还要判断左右孩子与双亲甚至根结点的比值也要遵循（左小右大）原则）。
若要采用递归算法，建议您采用如下的函数首部：
bool BisortTree(BiTree T, BiTree&PRE)，其中PRE为指向当前访问结点的前驱的指针。 （或者直接存储前驱的数值，随时与当前根结点比较） 一个漂亮的算法设计如下：
int last=0, flag=1; 用某种排序方法对线性表（25, 84，21,47,15,27,68,35,20）进行排序时，元素序列的变化情况如下：
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， 问采用的是什么排序方法 答：用的是快速排序方法。注意每一趟要振荡完全部元素才算一个中间结果。
2. 对于整数序列100，99，98，…3，2，1，如果将它完全倒过来，分别用冒泡排序和快速排序法，它们的比较次数和交换次数各是多少
答：冒泡排序的比较和交换次数将最大，都是1+2+…+n-1=n(n-1)/2＝50×99=4545次 快速排序则看按什么数据来分子表。
如果按100来分，则很惨，也会是n(n-1)/2！ 若按中间数据50或51来分表，则：
第1轮能确定1个元素，即在1个子表中比较和交换了n－1个元素；n－（2-1） 第2轮能再确定2个元素，即在2个子表中比较和交换了n－3个元素；n－（2-1） 第3轮能再确定4个元素，即在4个子表中比较和交换了n－7个元素；n－（2-1） 第4轮能再确定8个元素，即在8个子表中比较和交换了n－15个元素；n－（2-1）
……
4321
第6轮能再确定32个元素，即在32个子表中比较和交换了n－65个元素；n－（2-1） 第7轮则能全部确定，（因为2=128）， 在100个子表中比较和交换了n－（100－1）个元素；
比较和交换总次数为：7n－(2－1＋2－1＋2－1……＋2－1＋100－1) ＝7n+7－(1＋2＋4＋……＋64+100)=7n－(8+16+32+164)=700-220=480次
若从中间选择初始元素，则ASL=（n+1）log2n－(2＋2＋2+……＋2)= nlog2n+log2n－(2＋2＋2+……＋n)≈O（nlog2n）
3. 以关键字序列（256，301，751，129，937，863，742，694，076，438）为
2
3
1
2
3
m
1
1
2
3
6
7
6
例，分别写出执行以下算法的各趟排序结束时，关键字序列的状态，并说明这些排序方法中，哪些易于在链表（包括各种单、双、循环链表）上实现 ① 直接插入排序 ② 希尔排序 ③冒泡排序 ④快速排序
⑤直接选择排序 ⑥ 堆排序 ⑦ 归并排序 ⑧ 基数排序 （8分）
解：先回答第2问： ① ⑤ ⑦ ⑧皆易于在链表上实现。
① 直接插入排序的中间过程如下： ② 希尔排序的中间过程如下：
③ 冒泡排序的中间过程如下： ④快速排序的中间过程如下：
⑤ 直接选择排序的中间过程如下： ⑥堆排序（大根堆）的中间过程如下：
⑦ 归并排序排序的中间过程如下：
⑧ 基数排序的中间过程如下：
4. 序列的“中值记录”指的是：如果将此序列排序后，它是第[n/2]个记录。试写一个求
南京工业大学数据结构作业答案(全)
