国开电大数据结构(本)形考作业4参考答案.pdf

国开电大数据结构(本)形考作业4参考答
案

1.对于二分查找，要求线性表必须以顺序存储方式，并且
数据元素有序。

2.在采用顺序查找方法查找长度为n的线性表时，每个元

素的平均查找长度为(n+1)/2.
3.对于一个长度为10的有序表，按折半查找对该表进行

查找，在等概率情况下查找成功的平均比较次数为29/10.

4.已知一个有序表为{11,22,33,44,55,66,77,88,99}，则顺序
查找元素55需要比较5次。

5.对于数据{53,30,37,12,45,24,96}，从空二叉树开始逐个

插入数据来形成二叉排序树，若希望高度最小，应该选择的序
列是37,24,12,30,53,45,96.

6.对于顺序存储的有序表{5,12,20,26,37,42,46,50,64}，若

采用折半查找，则查找元素26的比较次数是4次。

7.在所有的排序方法中，关键字比较的次数与记录初始排

列秩序无关的是直接选择排序。
8.插入排序是一种将未排序序列中的元素依次取出与已经
排好序的序列中的元素作比较，将其放入已排序序列的正确位

置上的排序方法。

9.归并排序是一种依次将每两个相邻的有序表合并成一个
有序表的排序方法。

10.交换排序是一种当两个元素出现逆序的时候就交换位

置的排序方法。

if(kkey)

p=p->left;
elseif(k>p->key)

p=p->right;

else
return(p);

return(NULL);

答案】：(NULL)，(p->key)
题目26.

1)对关键字序列(36,69,46,28,30,74)采用快速排序，以第一

个关键字为分割元素，经过一次划分后的结果序列为

正确答案：C。28，30，46，36，69，74

改写后：对关键字序列(36,69,46,28,30,74)进行快速排序，
以第一个关键字36为分割元素，经过一次划分后的结果序列

为28，30，46，36，69，74.

2)用冒泡法对上述序列排序，经两趟冒泡的结果序列为

正确答案：A。36,28,30,46,69,74

改写后：用冒泡法对关键字序列(36,69,46,28,30,74)进行排

序，经过两趟冒泡的结果序列为36,28,30,46,69,74.

题目27.

1)一组记录的关键字序列为{45，40，65，43，35，95}，
写出利用快速排序的方法，以第一个记录为基准得到的一趟划

分的结果为

正确答案：C。354043456595

改写后：对关键字序列{45，40，65，43，35，95}进行快
速排序，以第一个记录45为基准得到的一趟划分的结果为35

4043456595.

2)对上述序列利用直接插入排序，逐次插入过程中，共

进行了次元素间的比较。

正确答案：B。11

改写后：对关键字序列{45，40，65，43，35，95}进行直

接插入排序，逐次插入过程中，共进行了11次元素间的比较。