作业4部分答案
一、单项选择题
1．D
2．C
3．C 4．C
5．D
6．A
7．C 8．D
9．B 10．D
11．A 12．C
13．A 14．C
15．D
16．B 17．B
18．D 19．D
20．D
21．D 22．D
23．A 24．A 25．C
26．D
27．B 28．A
29．B 30．C
二、填空题
1.散列 2.特征项
数据元素 3.主键
4.平均值 5.顺序
6.二分查找 升序有序
7.顺序存储 8.索引查找
顺序查找 9.小于根结点的值
大于（或大于等于）根结点的值
10.自变量 地址值 11.9， 14， 16
，17 12．内部排序
外部排序
13．交换排序
14．3
15．4 8
16．堆排序 快速排序
17．主关键字 18．关键字相等的记录
19．n-1,n-j
20．堆尾 堆顶 向下
三、综合题
1．已知序列（70,83,100,65,10,32,7,9），请写出对此序列采用插入排序法进行升序排序时各趟的结果。
答：
原始序列：（70），83，100，65，10，32，7，9
第1趟： （70，83），100，65，10，32，7，9
第2趟：（70，83，100），65，10，32，7，9
第3趟：（65，70，83，100），10，32，7，9
第4趟：（10，65，70，83，100），32，7，9
第5趟：（10，32，65，70，83，100），7，9
第6趟：（7，10，32，65，70，83，100），9
第7趟：（7，9，10，32，65，70，83，100）
2．已知序列（10,18,4,3,6,12,1,9,15,8），请写出对此序列采用归并排序法进行升序排序时各趟的结果。
答：
原始序列：10，18，4，3，6，12，1，9，15，8
第1趟： [10，18][ 3，4][6，12][1，9][ 8，15]
第2趟： [3，4，10，18，][ 1，6，9，12][ 8，15]
第3趟： [3，4，10，18，][ 1，6，8，9，12，15]
第4趟： [1，3，4，6，8，9，10，12，15，18]
3．已知序列（256，301，751，129，937，863，742，694，076，438）请给出采用冒泡排序法对该序列作升序排列时的每一趟结果。
答：
原始序列：256，301，751，129，937，863，742，694，076，438
第1趟：
256，301，129，751，863，742，694，076，438，937
第2趟：
256，129，301，751，742，694，076，438，863，937
第3趟：
129，256，301，742，694，076，438，751，863，937
第4趟：
129，256，301，694，076，438，742，751，863，937
第5趟：
129，256，301，076，438，694，742，751，863，937
第6趟：
129，256，076，301，438，694，742，751，863，937
第7趟：
129，076，256，301，438，694，742，751，863，937
第8趟：
076，129，256，301，438，694，742，751，863，937
第9趟：
076，129，256，301，438，694，742，751，863，937
4．已知序列（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趟： [87，61]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，653，897[908]
第10趟： 61 ，87，170，275，462，503，653，897，908
5．设一组记录的关键字序列为（49，83，59，41，43，47），采用堆排序算法完成以下操作：（要求小根堆，并画出中间过程）
（1）以二叉树描述6个元素的初始堆
（2）以二叉树描述逐次取走堆顶元素后，经调整得到的5个元素、4个元素的堆
答：
（1）
（2）
6．
(1)原序列16
15 20
53 64 7
15 16
20 53
7
64
n-1趟
15 16
20 7
53
64
n-j次
15 16
7 20
53 64
15
7
16 20 53
64
7
15 16
20 53 64
（3）
平均查找长度=（1*1+2*2+3*3）/6=14/6
7． （1）
|
(2)
中序遍历：2，3，4，5，6，7，14，16，18
四、程序填空题
1.
（1）①j>=0
（2）②a[j]
（3）③j--
（4）④temp
2．
（1）j<=n-1
（2）i<=n-j
（3）a[i]=a[i+1]
（4）a[i+1]=temp
（5）…当某趟冒泡中没有出现交换则已排好序结束循环。
五、算法设计题
1．编写折半查找算法。
折半查找算法如下；
int Binary_Search(NODE a[],int n, int k)
{
int low,mid,high;
low=0;
high=n-1;
while(low<=high)
{
mid=(low+high)/2;
if(a[mid].key==k)
return
mid;
else if(a[mid].key<k)
low=mid+1;
else high=mid-1;
}
return -1;
}
2. 编写顺序查找算法。
顺序查找算法如下：
int search(NODE a[],int n, int k)
{
int i=0;
while(i<n
&& a[i].key!=k)
i++;
if(a[i].key=k)
return i;
else return
-1;
}
六、完成：实验3――栈、队列、递归程序设计,
实验4——图的存储方式和应用
根据实验要求（见教材P203）认真完成本实验，并提交实验报告。
|
|
加载中，请稍候......
加载中…
(2009-03-31 20:19:06)