1 9-12章 数据结构作业 答案
第九章 查找
选择题
1、 对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( A )
A．（n+1）/2 B. n/2 C. n D. [（1+n）*n ]/2
2. 下面关于二分查找的叙述正确的是 ( D )
A. 表必须有序，表可以顺序方式存储，也可以链表方式存储
B. 表必须有序且表中数据必须是整型，实型或字符型
C. 表必须有序，而且只能从小到大排列
D. 表必须有序，且表只能以顺序方式存储
3. 二叉查找树的查找效率与二叉树的( （1）C)有关, 在 (（2)C ）时其查找效率最低
(1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置
(2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。
4. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需 (（1）A) 个链表。这些链的链首指针构成一个指针数组，数组的下标范围为 (（2）C)
（1） A．17 B. 13 C. 16 D. 任意
（2） A．0至17 B. 1至17 C. 0至16 D. 1至16
判断题
1．Hash表的平均查找长度与处理冲突的方法无关。 (错)
2. 若散列表的负载因子α<1，则可避免碰撞的产生。（错）
3. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。（错）
填空题
1. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为 4 .
10.1排序的相关知识
一、 填空题
1. 将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫
2. 大多数排序算法都有两个基本的操作： ____________ 和 ___________ 。
二、 选择题
1. （ ）排序算法的稳定性是指（ ）。
A. 经过排序后，能使关键字相同的元素保持原顺序中的相对位置不变
B. 经过排序后，能使关键字相同的元素保持原顺序中的绝对位置不变
C. 排序算法的性能与被排序元素的个数关系不大
D. 排序算法的性能与被排序元素的个数关系密切
2. （ ）关于排序的以下叙述中，正确的是 （ ）。
A. 稳定的排序方法优于不稳定的排序方法，因为稳定的排序方法效率高
B. 对同一个线性表使用不同的排序方法进行排序，得到的排序结果可能不同
C. 排序方法都是在顺序表上实现的，在链表上无法实现排序方法
D. 在顺序表上实现的排序方法都可以在链表上实现
3. （ ）以下不属于内部排序方法的是（ ）。
A.选择排序 B. 插入排序 C. 归并排序 D. 拓扑排序
10.2插入排序
个记录60插入到有序表时，为寻找插入位置至少需比较 ______________ 次。
二、 选择题：
1. （ ）排序方法中，从未排序序列中依次取出元素与已排序序列（初始时空）中的元素进行比较，
将其放入已排序序列的正确位置上的方法，称为 （） 。
A. 希尔排序 B. 冒泡排序 C. 插入排序 D. 选择排序
2. （ ）折半插入排序算法的平均情况下的时间复杂度为 （） 。
2 3
A. O（n） B. O （nlog 2n） C. O （n ） D. O （n ）
3. （ ）对含有n个元素的顺序表采用直接插入排序方法进行排序，在最坏情况下所需的比较次数是
（） 。
A.n-1 B. n+1 C. n/2 D. n（n-1）/2 第10章排序
填空题
1. 在对一组记录（ 54, 38, 96, 23， 15， 72， 60， 45, 83）进行直接插入排序时，当把第 三、简答题
第十章 内部排序
10.23
void Insert_Sort1(SqList &L)//监视哨设在高下标端的插入排序算法
{
k=L.length;
for(i=k-1;i;--i) //从后向前逐个插入排序
if(L.r[i].key>L.r[i+1].key)
{
L.r[k+1].key=L.r[i].key; //监视哨
for(j=i+1;L.r[j].key>L.r[i].key;++j)
L.r[j-1].key=L.r[j].key; //前移
L.r[j-1].key=L.r[k+1].key; //插入
}
}//Insert_Sort1
10.24
void BiInsert_Sort(SqList &L)//二路插入排序的算法
{
int d[MAXSIZE]; //辅助存储
x=L.r.key;d=x;
first=1;final=1;
for(i=2;i<=L.length;i++)
{
if(L.r[i].key>=x) //插入前部
{
for(j=final;d[j]>L.r[i].key;j--)
d[j+1]=d[j];
d[j+1]=L.r[i].key;
final++;
}
else //插入后部
{
for(j=first;d[j]
d[j-1]=d[j];
d[(j-2)%MAXSIZE+1]=L.r[i].key;
first=(first-2)%MAXSIZE+1; //这种形式的表达式是为了兼顾first=1的情况
}
}//for for(i=first,j=1;d[i];i=i%MAXSIZE+1,j++)//将序列复制回去
9.1 选择题
1．从末排序的序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在排序序列的合适位置，该排序方法称为（ ）排序法。
A）插入 B）选择 C）希尔 D）二路归并
【答案】A
2．下面各种排序方法中，最好情况下时间复杂度为O(n)的是（ ）
A）快速排序 B）直接插入排序 C）堆排序 D）归并排序
【答案】B
3．用某种排序方法对线性表（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
则所采用的排序方法是（ ）
Ａ）选择排序 Ｂ）希尔排序 Ｃ）归并排序 Ｄ）快速排序
【答案】Ｄ
4．下面给出的四种排序法中，（ ）排序是不稳定排序法。
A）插入 B）冒泡 C）二路归并 D）堆
【答案】D
5．快速排序方法在（ ）情况下最不利于发挥其长处。
Ａ）要排序的数据量太大
Ｂ）要排序的数据中含有多个相同值
Ｃ）要排序的数据已基本有序
Ｄ）要排序的数据个数为奇数
【答案】Ｃ
6．一组记录的关键码为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）
Ａ）38,40,46,56,79,84
B）40,38,46,79,56,84
C）40,38,46,56,79,84
D）40,38,46,84,56,79
【答案】Ｃ
7．对记录的关键码{50，26，38，80，70，90，8，30，40，20}进行排序，各趟排序结束时的结果为：
50,26,38,80,70,90 ,8,30,40,20
50,8,30,40,20,90,26,38,80,70
